基于密度聚類的Android用戶界面構(gòu)件推薦方法與實現(xiàn)

黃海平 黃子平 陳湘萍 石曉紅

摘要：移動應(yīng)用有著交互密集的特點，這使得界面設(shè)計的質(zhì)量成為影響用戶評價的重要因素。在設(shè)計界面時，設(shè)計人員往往需要參考已有類似的應(yīng)用界面，而手工查找非常耗時，如果能夠基于主題獲得常用的頁面設(shè)計模版，就可以有效提高設(shè)計的效率。針對以上問題，面向移動應(yīng)用人機界面進行設(shè)計，提出一種用戶界面分析和生成的方法，在已有Android界面收集平臺的基礎(chǔ)上，基于界面信息建立倒排索引來提供獲取相同主題的用戶界面的方法，應(yīng)用密度聚類算法對用戶界面中的類似控件進行聚類，再通過組合的方式生成推薦方法給用戶。將該方法的設(shè)計輔助工具實現(xiàn)為一個Eclipse插件，通過實驗中生成的用戶界面可復用代碼，展示了本方法的檢索準確性和實用性，可應(yīng)用于Android移動應(yīng)用的界面開發(fā)。所提方法具有一定的實際意義。

關(guān)鍵詞：軟件開發(fā)環(huán)境與開發(fā)技術(shù)；Android構(gòu)件；圖形用戶界面；DBSCAN算法；輔助設(shè)計

中圖分類號：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

隨著智能移動設(shè)備的廣泛使用，移動應(yīng)用（mobile application，簡稱App）已經(jīng)成為在互聯(lián)網(wǎng)提供服務(wù)的重要途徑之一。目前，蘋果公司的App Store 和谷歌公司的Google Play作為主要的移動應(yīng)用商店，其分別擁有超過200萬和220萬款的應(yīng)用，2016年的下載總量就超過1 300億次[12]。

移動應(yīng)用有著交互密集的特點[3]，這使得界面設(shè)計的質(zhì)量成為影響用戶評價的重要因素。如何提供方法和工具來幫助開發(fā)人員設(shè)計人機界面成為軟件工程領(lǐng)域的一個關(guān)注點[4]。

對于移動應(yīng)用的開發(fā)和維護人員，在根據(jù)需求設(shè)計界面時，往往需要參考已有類似的應(yīng)用界面。如果能夠獲得具有參考價值的界面，開發(fā)人員通過借鑒或者部分修改參考界面的設(shè)計和源碼，從而減少開發(fā)工作量。

已有W3C組織和移動平臺為移動應(yīng)用的開發(fā)提供了詳細的指南[56]，這些指南總結(jié)了常見的UI構(gòu)件的特點和使用場景，介紹了如何使用常用的UI構(gòu)件來設(shè)計人機交互界面。這些總結(jié)的頁面實例大部分是關(guān)注常見的通用功能，在實踐中無法滿足不同的需求。而另一方面，已有移動應(yīng)用數(shù)量非常龐大，并且其數(shù)量在相當長的時間內(nèi)還將繼續(xù)快速增長，通過手工查看移動應(yīng)用界面來收集實例的方式難以滿足不同開發(fā)人員的需求。

基于已有工作建立了一個移動應(yīng)用界面庫[7]，基于界面上提取的構(gòu)件名稱、類型等屬性信息建立倒排索引來提供基于主題的檢索。在設(shè)計某一主題Android應(yīng)用的UI時，設(shè)計人員以該主題詞為輸入，可以在界面集合中檢索出一定數(shù)量的相似界面集合。本文應(yīng)用密度聚類算法（densitybased spatial clustering of applications with noise， DBSCAN），對用戶界面中的類似控件進行聚類，再通過組合的方式生成推薦方法給用戶。

1方法總覽

首先，用戶輸入關(guān)鍵字作為Android UI設(shè)計的主題。該方法通過搜索引擎，從預(yù)先按照界面控件關(guān)鍵字進行倒排索引的界面庫中，得到跟關(guān)鍵字主題相關(guān)的UI集合。接著對這些結(jié)果進行聚類，得到大部分在構(gòu)件庫中這個主題相關(guān)UI所包含共有的構(gòu)件類型[8]。例如：主題為Login的典型用戶界面。一般來說，應(yīng)該包含登錄標題欄TextView、登錄輸入框EditText、密碼輸入框EditText、登錄按鈕Button等幾個主要構(gòu)件。通過推薦排序，考慮元素和它們的主流樣式的詳細參數(shù)，生成一個或幾個UI實例，這些UI就是推薦的結(jié)果[9]，當用戶選定了某一套方案之后，部署代碼的工具把用戶選定的這套方案的代碼自動部署到設(shè)計者當前正在設(shè)計開發(fā)的Android UI的頁面中[10]。輔助設(shè)計方法的總覽圖如圖1所示。

關(guān)于推薦的結(jié)果，以關(guān)鍵字Login為例，通過聚類算法得到聚類結(jié)果，之后可以在組合推薦算法中對這些聚類結(jié)果按一定的規(guī)則進行組合，得到如下的幾種Android UI推薦方案思路圖，如圖2所示。

2基于密度聚類的構(gòu)件推薦方法

2.1相似構(gòu)件聚類算法

將Android UI構(gòu)件的屬性進行DBSCAN聚類，偽代碼如下所示：

DBSCAN算法（）{

設(shè)定聚類半徑和最少個數(shù)

獲得每個屬性的數(shù)據(jù)列表

for（每個屬性）{

for（單個屬性列表的每個點）{

if（某個點還未屬于某個聚類）{

計算這個點與列表所有點的歐氏距離

if（距離<聚類半徑）

該聚類的個數(shù)++

if（聚類個數(shù)達到最少個數(shù)）

加入這個屬性的聚類結(jié)果列表

}}}}

但即使采用了DBSCAN，依然需要輸入2個參數(shù)：聚類的半徑領(lǐng)域Eps和被選為核心對象的領(lǐng)域內(nèi)的最少點數(shù)minpts。前者可以通過改進的DBSCAN算法，即OPTICS來確定[11]，后者通常建議不要以自動化的方法，而是通過經(jīng)驗來確定。該算法的優(yōu)點就是對聚類半徑初始化的參數(shù)不敏感，因為它通過引入可達距離以及核心距離的概念，對聚類的點排序來識別聚類結(jié)構(gòu)。應(yīng)該把關(guān)注點放在距離算法的選取上，根據(jù)構(gòu)件的特點選擇合適的計算方法，不需要太過于依賴歐幾里德距離算法[12]。另外，Eps也不能全局唯一，應(yīng)當根據(jù)屬性的不同來確定各自的鄰域。這里的算法改進在于參數(shù)，根據(jù)類對象的特點，將五元數(shù)組中的1個一維參數(shù)num和2對二維參數(shù)x，y和width，height細分成了eNum，eLoc和eAre 3部分，分別進行聚類，以此提高數(shù)據(jù)的準確性。對于每個五元組，在同時滿足eNum，eLoc和eAre屬于同一聚類的情況下，才可以被歸為聚類簇中的一點[13]。因此，想要得到目前最準確的結(jié)果，最佳的方式是根據(jù)同一主題不同組件的分布特點，手動調(diào)整參數(shù)。由上述組件位置的分布圖可以發(fā)現(xiàn)，密集散點的范圍形狀可能是不一樣的。但是由于在該場景中，只需要找到聚類簇中的平均值即可，因此形狀對結(jié)果的影響不大。

除了組件間的數(shù)量、位置和大小需要聚類之外，相同和不同組件間的距離大小也需要被記錄下來并聚類。原因是聚類的結(jié)果在后期組合過程中可能出現(xiàn)重疊現(xiàn)象[14]，為了減少無用結(jié)果數(shù)的生成，也為了使得方案更加準確，必須對這種結(jié)果進行調(diào)整。

首先是篩選掉具有重疊組件的UI。將每個UI中的每個組件進行兩兩比較，對于兩兩比較之后組件皆不重疊的UI即為符合要求的結(jié)果。但這里的判定原則是：布局組件是其他組件的底層，因此可以與其他組件相互之間重疊[15]。另外，不同類型組件也可以實現(xiàn)包含。實現(xiàn)篩選的方法偽代碼如下所示。

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

}}}

數(shù)據(jù)輸出的文檔為csv格式，即Comma Separated Value（逗號分隔值），使用該格式的好處是可以很容易被導入各種表格和數(shù)據(jù)庫中，以逗號分隔，沒有多余的內(nèi)容，并且不能被追加內(nèi)容，因此可以作為每次生成新結(jié)果存放的容器。

當?shù)玫降木垲惤Y(jié)果過多時，會大大增加組合推薦后的結(jié)果數(shù)目，因此從效率最大化的程度出發(fā)，需要舍棄一些聚類的結(jié)果。方法是截取將要下降最快的點之前的點，這里以聚類結(jié)果中的“count”字段作為計算的標準，淘汰聚類結(jié)果中count減少最多的結(jié)果之后的所有結(jié)果。

2.2面向Android UI構(gòu)件的推薦方法分析與選擇

推薦的方法不同決定了在Android UI設(shè)計時所給出的推薦方案不同。根據(jù)需要，選擇兩種推薦方法：一種是基于內(nèi)容的推薦，在準備設(shè)計具有某一主題的Android UI時，通過算法，在資源庫中找出之前已聚類好的，與關(guān)鍵字匹配度最高的構(gòu)件推薦方案；另一種是基于用戶的推薦，即把資源庫具有相同功能的頁面搜索結(jié)果和當前的頁面當作興趣相同的用戶，根據(jù)這些相似用戶的特征來決定要推薦出來的Android UI和構(gòu)件的樣式。

在此基礎(chǔ)上，本文采用一種兩者相結(jié)合的更高效的推薦算法來產(chǎn)生Android UI的構(gòu)件推薦方案，即要考慮匹配相似度，又要考慮用戶的需求，最終目的是達到基于Android UI構(gòu)件庫的準確性，并且能夠達到用戶接受推薦結(jié)果的程度，如圖3所示。

2.3實現(xiàn)Android UI設(shè)計輔助工具的整體架構(gòu)

Android UI設(shè)計輔助工具的整體架構(gòu)包括基于Mongo數(shù)據(jù)庫和Elasticsearch搜索引擎搭建的界面設(shè)計搜索平臺，以DBSCAN聚類算法為核心的組合推薦方法，還有為實現(xiàn)Eclipse插件[16]的方案生成和展示工具。工程實現(xiàn)的整體流程以及所需要的開發(fā)工具、環(huán)境、技術(shù)、語言如圖4所示。

開發(fā)環(huán)境為裝在物理機和VMware Workstation 10[17]虛擬機上的Linux Ubuntu 14.3，實現(xiàn)語言為Java語言。其中物理機的配置是2.5 GHz，8 GB內(nèi)存，2 GB獨立顯卡，其操作系統(tǒng)Ubuntu負責ElsaticSearch的分布式搜索處理任務(wù)，VMware虛擬機中安裝了Linux 操作系統(tǒng)，并通過Samba實現(xiàn)物理機和虛擬機的數(shù)據(jù)交互，在Linux操作系統(tǒng)下使程序執(zhí)行的速度、ElasticSearch搜索引擎檢索速度、DBSCAN聚類算法的運行速度更快，效率更高。程序?qū)崿F(xiàn)的模塊圖如圖5所示。

3構(gòu)件推薦方法結(jié)果評價

Android UI設(shè)計輔助工具的核心價值在于推薦結(jié)果的準確性，以及與原來檢索推薦方式相比的效率提升程度。采用的來源是龐大的構(gòu)件庫，即對構(gòu)件庫中包含同一關(guān)鍵字的結(jié)果進行統(tǒng)計、聚類，得到大多數(shù)人開發(fā)該主題的UI時所設(shè)計的界面。比如，對于一個密碼修改頁面，通常都會是一個800*480大小的相對布局，會有一個標題和“原密碼”、“新密碼”、“確認密碼”的Textview、相對應(yīng)的帶有password=true屬性的3個Edittext、“確認修改”和“取消修改”的2個Button，以及它們所在位置通常都是在頁面的正中間，大小為20*300，顏色為白底黑字等特性。一個完整的Android應(yīng)用程序的UI中的構(gòu)件應(yīng)該具有布局、顏色等信息[18]。這款工具希望抓取出各種主題中的用戶界面應(yīng)該具有的通用骨架特征并且以代碼的形式呈現(xiàn)出來。雖然Android構(gòu)件庫中每個UI并沒有呈現(xiàn)出充分的屬性，如顏色等特征，但這些個性化的特征不是本課題打算實現(xiàn)的目標，有需要的話，這里提供一種方案：在Android構(gòu)件資源平臺中通過OCR（optical character recognition，光學字符識別）算法來獲取個性特征。因為這些數(shù)據(jù)都已經(jīng)存儲于構(gòu)件庫中，需要做的只是將它們?nèi)〕霾⑶疫M行聚類推薦的處理，而結(jié)果的準確性只需要把控住聚類的半徑和個數(shù)即可，所以該實驗是可行的。

驗證方式可以以離線實驗的方式完成，有兩方面需要驗證：一是驗證應(yīng)用推薦效率的提升；二是驗證推薦的準確性[19]。

考慮推薦效率，將前面提到的48個主題詞進行驗證，主要是和之前的平臺檢索結(jié)果進行對比[20]。在前面的論證中，常常以“Login”關(guān)鍵字進行例證，原因是登錄界面兼顧了典型和讀者易理解等特點。為了使結(jié)果更加具有一般性和說服力，需要關(guān)鍵字擴展到通過LDA工具得到的48個主題詞。方法是對每一個主題詞分別在Android 構(gòu)件檢索平臺和推薦工具中進行處理，取得2個結(jié)果呈現(xiàn)的數(shù)量進行對比，以此來說明之前、現(xiàn)在的推薦方法對于之前的檢索從效率上得到的提升。隨機挑選9個主題詞，得到的結(jié)果如表1所示。

通過聚類的方式使得推薦的方案數(shù)明顯減少，意味著作為Android UI設(shè)計人員，使用該工具進行設(shè)計時，與檢索的方式相比，得到的結(jié)果摒除了“無用”的UI，并且使相似的結(jié)果體現(xiàn)得更精練，更具有參考意義。

當然，這樣的比較并不一定具備說服力。雖然把本來具有2 578條搜索結(jié)果Android UI界面直接精煉成42套，從推薦效率上大大提高，但數(shù)據(jù)處理后的UI與基本檢索相比較，方案減少的結(jié)果似乎是必然的，因此，這樣的驗證只能部分證明提高了推薦的效率，還需要從準確性上來繼續(xù)驗證。

在推薦準確性方面，考慮了Android UI構(gòu)件推薦的準確性證明。除此之外，因為結(jié)果來源于Android UI構(gòu)件檢索平臺，因此可以選擇將得到的推薦結(jié)果進行逆向推導，即每個結(jié)果都能找到原始的頁面，以此驗證通過聚類的方式來生成Android UI基本布局的科學性，如圖6所示。

由于分別對各個組件進行聚類，得到的結(jié)果再進行排列組合，當組件個數(shù)較多時，會造成聚類方案數(shù)大大增加，需要通過分數(shù)從高到低的方式來排列，因此，推薦Android UI方案。

4結(jié)論

提出了以密度為中心的構(gòu)件屬性聚類，當?shù)玫降木垲愡^多則會增加組合的推薦結(jié)果數(shù)，從效率最大化的程度出發(fā)，舍棄某些聚類結(jié)果。在面向構(gòu)建的推薦方法方面，提出基于內(nèi)容和基于用戶的推薦方案，并詳細分析其結(jié)構(gòu)機理[20]。通過分析，綜合兩者優(yōu)點，進行結(jié)合構(gòu)造出更高效的推薦算法來產(chǎn)生Android UI的構(gòu)件推薦方案，即考慮匹配了相似度，又考慮了用戶的需求，最終達到了基于Android UI構(gòu)件庫的準確性，并且能夠達到用戶接受推薦結(jié)果的程度。通過研究發(fā)現(xiàn)，該構(gòu)造方案既提高了推薦效率，又提升了推薦的準確度。

在本文的方法中，參數(shù)的設(shè)定可能會影響生成方案的數(shù)量和質(zhì)量，今后將在數(shù)據(jù)集上進行更多實驗或者采用自適應(yīng)調(diào)整的方法來提高推薦質(zhì)量。

參考文獻/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]沈健，胡潔，馬進，等.支持生物激勵設(shè)計的跨領(lǐng)域知識元聚類方法[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設(shè)計[M].北京：機械工業(yè)出版社，2015.

[11]于亞飛，周愛武.一種改進的DBSCAN密度算法[J].計算機技術(shù)與發(fā)展，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]周其林，雷菊陽，王昱棟， 等. 一種引入?yún)?shù)無需確定聚類數(shù)的聚類算法[J]. 河北工業(yè)科技，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]劉青文.基于協(xié)同過濾的推薦算法研究[D].合肥：中國科學技術(shù)大學，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]寧卓，胡婷，孫知信.基于動態(tài)分析的Android應(yīng)用程序安全研究[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.