基于密度聚類的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.