基于密度聚类的Android用户界面构件推荐方法与实现

黄海平 黄子平 陈湘萍 石晓红

摘要：移动应用有着交互密集的特点，这使得界面设计的质量成为影响用户评价的重要因素。在设计界面时，设计人员往往需要参考已有类似的应用界面，而手工查找非常耗时，如果能够基于主题获得常用的页面设计模版，就可以有效提高设计的效率。针对以上问题，面向移动应用人机界面进行设计，提出一种用户界面分析和生成的方法，在已有Android界面收集平台的基础上，基于界面信息建立倒排索引来提供获取相同主题的用户界面的方法，应用密度聚类算法对用户界面中的类似控件进行聚类，再通过组合的方式生成推荐方法给用户。将该方法的设计辅助工具实现为一个Eclipse插件，通过实验中生成的用户界面可复用代码，展示了本方法的检索准确性和实用性，可应用于Android移动应用的界面开发。所提方法具有一定的实际意义。

关键词：软件开发环境与开发技术；Android构件；图形用户界面；DBSCAN算法；辅助设计

中图分类号：TP319文献标志码：Adoi： 10.7535/hbgykj.2018yx01009

.Approach and implementation of Android UI component

recommendation based on DBSCAN

HUANG Haiping1， HUANG Ziping2， CHEN Xiangping2， SHI Xiaohong3

（1.Zhaoqing City Medical College， Zhaoqing， Guangdong 526020， China； 2. School of Data and Computer Science， Sun YatSen University， Guangzhou， Guangdong 510006，China； 3. Xinhua College， Sun YatSen University， Guangzhou， Guangdong 510006， China）

Abstract：Mobile application has the characteristic of interaction dense， which makes UI design become the important factor affecting user evaluation. In designing the UI， the designers often refer to the existing similar application interfaces， but manual look up is much timeconsuming. If the common page design model can be obtained based on the subject， it will improve the design efficiency effectively. Aiming at the above problems， in order to design mobile application humancomputer interface， a UI analysis and generation method is provided. The UI for obtaining the same subject is provided based on the existing Android interface collection platform and the interface information， and the similar controls in UI is clustered with densitycluster algorithm， then the recommendation method can be given to the users through combination. The design auxiliary means for the method is packed into an Eclipse plugin. The UI code from the experiment is reusable， which shows the searching accuracy and practicability of the method， and it can be used in Android mobile application interface development. The provided has certain practical meaning.

Keywords： software development environment and development technology； Android component； graphic userinterface； DBSCAN； auxiliary design

隨着智能移动设备的广泛使用，移动应用（mobile application，简称App）已经成为在互联网提供服务的重要途径之一。目前，苹果公司的App Store 和谷歌公司的Google Play作为主要的移动应用商店，其分别拥有超过200万和220万款的应用，2016年的下载总量就超过1 300亿次[12]。

移动应用有着交互密集的特点[3]，这使得界面设计的质量成为影响用户评价的重要因素。如何提供方法和工具来帮助开发人员设计人机界面成为软件工程领域的一个关注点[4]。

对于移动应用的开发和维护人员，在根据需求设计界面时，往往需要参考已有类似的应用界面。如果能够获得具有参考价值的界面，开发人员通过借鉴或者部分修改参考界面的设计和源码，从而减少开发工作量。

已有W3C组织和移动平台为移动应用的开发提供了详细的指南[56]，这些指南总结了常见的UI构件的特点和使用场景，介绍了如何使用常用的UI构件来设计人机交互界面。这些总结的页面实例大部分是关注常见的通用功能，在实践中无法满足不同的需求。而另一方面，已有移动应用数量非常庞大，并且其数量在相当长的时间内还将继续快速增长，通过手工查看移动应用界面来收集实例的方式难以满足不同开发人员的需求。

基于已有工作建立了一个移动应用界面库[7]，基于界面上提取的构件名称、类型等属性信息建立倒排索引来提供基于主题的检索。在设计某一主题Android应用的UI时，设计人员以该主题词为输入，可以在界面集合中检索出一定数量的相似界面集合。本文应用密度聚类算法（densitybased spatial clustering of applications with noise， DBSCAN），对用户界面中的类似控件进行聚类，再通过组合的方式生成推荐方法给用户。

1方法总览

首先，用户输入关键字作为Android UI设计的主题。该方法通过搜索引擎，从预先按照界面控件关键字进行倒排索引的界面库中，得到跟关键字主题相关的UI集合。接着对这些结果进行聚类，得到大部分在构件库中这个主题相关UI所包含共有的构件类型[8]。例如：主题为Login的典型用户界面。一般来说，应该包含登录标题栏TextView、登录输入框EditText、密码输入框EditText、登录按钮Button等几个主要构件。通过推荐排序，考虑元素和它们的主流样式的详细参数，生成一个或几个UI实例，这些UI就是推荐的结果[9]，当用户选定了某一套方案之后，部署代码的工具把用户选定的这套方案的代码自动部署到设计者当前正在设计开发的Android UI的页面中[10]。辅助设计方法的总览图如图1所示。

关于推荐的结果，以关键字Login为例，通过聚类算法得到聚类结果，之后可以在组合推荐算法中对这些聚类结果按一定的规则进行组合，得到如下的几种Android UI推荐方案思路图，如图2所示。

2基于密度聚类的构件推荐方法

2.1相似构件聚类算法

将Android UI构件的属性进行DBSCAN聚类，伪代码如下所示：

DBSCAN算法（）{

设定聚类半径和最少个数

获得每个属性的数据列表

for（每个属性）{

for（单个属性列表的每个点）{

if（某个点还未属于某个聚类）{

计算这个点与列表所有点的欧氏距离

if（距离<聚类半径）

该聚类的个数++

if（聚类个数达到最少个数）

加入这个属性的聚类结果列表

}}}}

但即使采用了DBSCAN，依然需要输入2个参数：聚类的半径领域Eps和被选为核心对象的領域内的最少点数minpts。前者可以通过改进的DBSCAN算法，即OPTICS来确定[11]，后者通常建议不要以自动化的方法，而是通过经验来确定。该算法的优点就是对聚类半径初始化的参数不敏感，因为它通过引入可达距离以及核心距离的概念，对聚类的点排序来识别聚类结构。应该把关注点放在距离算法的选取上，根据构件的特点选择合适的计算方法，不需要太过于依赖欧几里德距离算法[12]。另外，Eps也不能全局唯一，应当根据属性的不同来确定各自的邻域。这里的算法改进在于参数，根据类对象的特点，将五元数组中的1个一维参数num和2对二维参数x，y和width，height细分成了eNum，eLoc和eAre 3部分，分别进行聚类，以此提高数据的准确性。对于每个五元组，在同时满足eNum，eLoc和eAre属于同一聚类的情况下，才可以被归为聚类簇中的一点[13]。因此，想要得到目前最准确的结果，最佳的方式是根据同一主题不同组件的分布特点，手动调整参数。由上述组件位置的分布图可以发现，密集散点的范围形状可能是不一样的。但是由于在该场景中，只需要找到聚类簇中的平均值即可，因此形状对结果的影响不大。

除了组件间的数量、位置和大小需要聚类之外，相同和不同组件间的距离大小也需要被记录下来并聚类。原因是聚类的结果在后期组合过程中可能出现重叠现象[14]，为了减少无用结果数的生成，也为了使得方案更加准确，必须对这种结果进行调整。

首先是筛选掉具有重叠组件的UI。将每个UI中的每个组件进行两两比较，对于两两比较之后组件皆不重叠的UI即为符合要求的结果。但这里的判定原则是：布局组件是其他组件的底层，因此可以与其他组件相互之间重叠[15]。另外，不同类型组件也可以实现包含。实现筛选的方法伪代码如下所示。

for each UI{

if（component == Relativelayout‖Linearlayout‖

Framelayout）{

continue； //skip this UI

}else{

if（component == otherComponent && component contains otherComponent

‖ component intersects otherComponent ）{

if（otherComponent ！= Relativelayout ‖ Linearlayout ‖ Framelayout）{

mark this UI OverLapFlag；

break； //skip this component

}

}

if （UI OverLapFlag is marked ）{

break； // skip this UI

}}}

数据输出的文档为csv格式，即Comma Separated Value（逗号分隔值），使用该格式的好处是可以很容易被导入各种表格和数据库中，以逗号分隔，没有多余的内容，并且不能被追加内容，因此可以作为每次生成新结果存放的容器。

当得到的聚类结果过多时，会大大增加组合推荐后的结果数目，因此从效率最大化的程度出发，需要舍弃一些聚类的结果。方法是截取将要下降最快的点之前的点，这里以聚类结果中的“count”字段作为计算的标准，淘汰聚类结果中count减少最多的结果之后的所有结果。

2.2面向Android UI构件的推荐方法分析与选择

推荐的方法不同决定了在Android UI设计时所给出的推荐方案不同。根据需要，选择两种推荐方法：一种是基于内容的推荐，在准备设计具有某一主题的Android UI时，通过算法，在资源库中找出之前已聚类好的，与关键字匹配度最高的构件推荐方案；另一种是基于用户的推荐，即把资源库具有相同功能的页面搜索结果和当前的页面当作兴趣相同的用户，根据这些相似用户的特征来决定要推荐出来的Android UI和构件的样式。

在此基础上，本文采用一种两者相结合的更高效的推荐算法来产生Android UI的构件推荐方案，即要考虑匹配相似度，又要考虑用户的需求，最终目的是达到基于Android UI构件库的准确性，并且能够达到用户接受推荐结果的程度，如图3所示。

2.3实现Android UI设计辅助工具的整体架构

Android UI设计辅助工具的整体架构包括基于Mongo数据库和Elasticsearch搜索引擎搭建的界面设计搜索平台，以DBSCAN聚类算法为核心的组合推荐方法，还有为实现Eclipse插件[16]的方案生成和展示工具。工程实现的整体流程以及所需要的开发工具、环境、技术、语言如图4所示。

开发环境为装在物理机和VMware Workstation 10[17]虚拟机上的Linux Ubuntu 14.3，实现语言为Java语言。其中物理机的配置是2.5 GHz，8 GB内存，2 GB独立显卡，其操作系统Ubuntu负责ElsaticSearch的分布式搜索处理任务，VMware虚拟机中安装了Linux 操作系统，并通过Samba实现物理机和虚拟机的数据交互，在Linux操作系统下使程序执行的速度、ElasticSearch搜索引擎检索速度、DBSCAN聚类算法的运行速度更快，效率更高。程序实现的模块图如图5所示。

3构件推荐方法结果评价

Android UI设计辅助工具的核心价值在于推荐结果的准确性，以及与原来检索推荐方式相比的效率提升程度。采用的来源是庞大的构件库，即对构件库中包含同一关键字的结果进行统计、聚类，得到大多数人开发该主题的UI时所设计的界面。比如，对于一个密码修改页面，通常都会是一个800*480大小的相对布局，会有一个标题和“原密码”、“新密码”、“确认密码”的Textview、相对应的带有password=true属性的3个Edittext、“确认修改”和“取消修改”的2个Button，以及它们所在位置通常都是在页面的正中间，大小为20*300，颜色为白底黑字等特性。一个完整的Android应用程序的UI中的构件应该具有布局、颜色等信息[18]。这款工具希望抓取出各种主题中的用户界面应该具有的通用骨架特征并且以代码的形式呈现出来。虽然Android构件库中每个UI并没有呈现出充分的属性，如颜色等特征，但这些个性化的特征不是本课题打算实现的目标，有需要的话，这里提供一种方案：在Android构件资源平台中通过OCR（optical character recognition，光学字符识别）算法来获取个性特征。因为这些数据都已经存储于构件库中，需要做的只是将它们取出并且进行聚类推荐的处理，而结果的准确性只需要把控住聚类的半径和个数即可，所以该实验是可行的。

验证方式可以以离线实验的方式完成，有两方面需要验证：一是验证应用推荐效率的提升；二是验证推荐的准确性[19]。

考虑推荐效率，将前面提到的48个主题词进行验证，主要是和之前的平台检索结果进行对比[20]。在前面的论证中，常常以“Login”关键字进行例证，原因是登录界面兼顾了典型和读者易理解等特点。为了使结果更加具有一般性和说服力，需要关键字扩展到通过LDA工具得到的48个主题词。方法是对每一个主题词分别在Android 构件检索平台和推荐工具中进行处理，取得2个结果呈现的数量进行对比，以此来说明之前、现在的推荐方法对于之前的检索从效率上得到的提升。随机挑选9个主题词，得到的结果如表1所示。

通过聚类的方式使得推荐的方案数明显减少，意味着作为Android UI设计人员，使用该工具进行设计时，与检索的方式相比，得到的结果摒除了“无用”的UI，并且使相似的结果体现得更精练，更具有参考意义。

当然，这样的比较并不一定具备说服力。虽然把本来具有2 578条搜索结果Android UI界面直接精煉成42套，从推荐效率上大大提高，但数据处理后的UI与基本检索相比较，方案减少的结果似乎是必然的，因此，这样的验证只能部分证明提高了推荐的效率，还需要从准确性上来继续验证。

在推荐准确性方面，考虑了Android UI构件推荐的准确性证明。除此之外，因为结果来源于Android UI构件检索平台，因此可以选择将得到的推荐结果进行逆向推导，即每个结果都能找到原始的页面，以此验证通过聚类的方式来生成Android UI基本布局的科学性，如图6所示。

由于分别对各个组件进行聚类，得到的结果再进行排列组合，当组件个数较多时，会造成聚类方案数大大增加，需要通过分数从高到低的方式来排列，因此，推荐Android UI方案。

4结论

提出了以密度为中心的构件属性聚类，当得到的聚类过多则会增加组合的推荐结果数，从效率最大化的程度出发，舍弃某些聚类结果。在面向构建的推荐方法方面，提出基于内容和基于用户的推荐方案，并详细分析其结构机理[20]。通过分析，综合两者优点，进行结合构造出更高效的推荐算法来产生Android UI的构件推荐方案，即考虑匹配了相似度，又考虑了用户的需求，最终达到了基于Android UI构件库的准确性，并且能够达到用户接受推荐结果的程度。通过研究发现，该构造方案既提高了推荐效率，又提升了推荐的准确度。

在本文的方法中，参数的设定可能会影响生成方案的数量和质量，今后将在数据集上进行更多实验或者采用自适应调整的方法来提高推荐质量。

参考文献/References：

[1]Apple Inc. The Apple Worldwide Developers Conference （WWDC） 2016[EB/OL]. https：//developer.apple.com/videos/wwdc2016，20161201.

[2]Android Developers. Announcing Google Plays “Best of 2016”[EB/OL]. https：//blog.google/products/googleplay/announcinggoogleplaysbest2016，20160614.

[3]YANG Wei， PRASAD M R， XIE Tao. A greybox approach for automated GUImodel generation of mobile applications[C]// Fundamental Approaches to Software Engineering. Heidelberg：[s.n.]，2013：250265.

[4]WASSERMANA I.Software engineering issues for mobile application development[C]// Proceedings of the FSE/SDP Workshop on Future of Software Engineering Research. [S.l.]：[s.n.]， 2010：397400.

[5]Apple Inc. IOS Human interface guidelines： Introduction[EB/OL].https：//developer.apple.com/ios/humaninterfaceguidelines/overview/themes， 20170830.

[6]Google Inc.The Developers Guide[EB/OL]. http：//developer.android.com/guide/index.html，20121205.

[7]LI Kaiyuan， XU Zhensheng， CHEN Xiangping.A platform for searching UI component of Android application[C]//2014 5th International Conference on Digital Home（ICDH）. Guangzhou：[s.n.]， 2014：2830.

[8]沈健，胡洁，马进，等.支持生物激励设计的跨领域知识元聚类方法[J].河北科技大学学报，2017，38（3）：229236.

SHEN Jian，HU Jie，MA Jin，et al.Cross domain knowledge cell clustering method for biologically inspired design[J].Journal of Hebei University of Science and Technology， 2017， 38（3）：229236.

[9]BUDISELIC′ I， VLADIMIR K， SRBLJI C′ S.Component recommendation for composite application development[J]. Expert Systems with Applications， 2015， 42（22）：85738587.

[10]李维勇.Android UI设计[M].北京：机械工业出版社，2015.

[11]于亚飞，周爱武.一种改进的DBSCAN密度算法[J].计算机技术与发展，2011，21（2）：3033.

YU Yafei， ZHOU Aiwu. An improved algorithm of DBSCAN[J]. Computer Technology and Development， 2011，21（2）：3033.

[12]孙吉贵，刘杰，赵连宇.聚类算法研究[J].软件学报，2008，19（1）：4861.

SUN Jigui，LIU Jie，ZHAO Lianyu. Clustering algorithms research[J].Journal of Software，2008，19（1）：4861.

[13]周其林，雷菊陽，王昱栋， 等. 一种引入参数无需确定聚类数的聚类算法[J]. 河北工业科技，2015，32（2）：123128.

ZHOU Qilin，LEI Juyang，WANG Yudong， et al.A clustering algorithm with parameters that no need to determine the clustering number[J].Hebei Journal of Industrial Science and Technology，2015，32（2）：123128.

[14]HAN Jiawei， KAMBER M.Data Mining：Concepts and Techniques[M].3rd ed. Beijing：China Machine Press，2012.

[15]KIM Y， SHIM K， KIM M S， et al.DBCUREMR：An efficient densitybased clustering algorithm for large data using MapReduce[J].Information Systems，2014，42：1535.

[16]BLEWITT A.Eclipse 4 Plugin Development by Example：Beginners Guide[M].Birmingham：Packt Publishing Limited，2013.

[17]劉青文.基于协同过滤的推荐算法研究[D].合肥：中国科学技术大学，2013.

LIU Qingwen.Research on Recommender Systems Based on Collaborative Filtering[D].Hefei：University of Science and Technology of China，2013.

[18]RAYNALDO C.Android Ui Design with XML： Tutorial Book[M].Charleston：CreateSpace Independent Publishing Platform，2012.

[19]宁卓，胡婷，孙知信.基于动态分析的Android应用程序安全研究[J].计算机科学，2016，43（sup2）：324328.

NING Zhuo，HU Ting，SUN Zhixin.Security survey on Android application based on dynamic analysis[J].Computer Science，2016，43（sup2）：324328.

[20]栾咏红. 基于Android的XML解析器的分析与比较[J]. 南京晓庄学院学报，2011（6）：98100.

LUAN Yonghong.The analysis and comparison of XML parser based on Android[J]. Journal of Nanjing Xiaozhuang University， 2011（6）：98100.