韓 迪，李雯婷 ，王慶娟，周天劍

1)北京理工大學珠海學院，廣東珠海 519000；2)澳門科技大學資訊科技學院，澳門 999078；3)貴州商學院計算機與信息工程學院，貴州貴陽 550014

智能手機在人們日常生活中的應用現已非常普遍．Google研究表明[1]，全球一半以上的人擁有1部智能手機，而每部智能手機中平均約裝有96個應用(application, app)．大量的app和手機屏幕尺寸的限制，往往令用戶花費大量時間來尋找特定的app．因此，急需一些能夠幫助用戶快速定位所需app的機制，這也是app使用預測技術成為目前手機操作系統(tǒng)研究熱點的原因．但是，現有的大部分app預測機制都未考慮用戶的歷史數據是隨用戶愛好和app的狀態(tài)改變而改變，一旦訓練數據發(fā)生改變，部分app預測機制需要重建模型以保持預測的準確度，否則，預測準確度將大幅降低．

本研究首次提出app使用預測系統(tǒng)Predictor，利用優(yōu)化后的增量模型IkNN(incrementalk-nearest neighbors)作為app使用預測的解決方案，通過對模型的空間優(yōu)化排序，減少在app使用預測過程中的建模時間．值得注意的是，選擇合適的k值能提高預測過程中的分類準確度[2]．然而，隨著app的特征越來越多，人們已經無法僅靠k值來提高準確度．這是因為IkNN模型通常使用歐氏距離等方法[3]來計算樣本的相似性，當特征量超過閾值時，歐式距離很難發(fā)現樣本與樣本之間區(qū)別[4]．本研究利用上下文的特征在預測中的特點，設計了聚類有效值(cluster effective value, CEV)方法，并用于IkNN算法中，以期區(qū)別噪聲和小概率習慣(發(fā)生頻率都很低)，從而提高增量算法中的預測準確度．本研究首先實現了整套app使用預測系統(tǒng)Predictor，并用于真實環(huán)境中．該系統(tǒng)可根據不同的環(huán)境因素(如時間和地點等)和用戶習慣(如是否插入耳機、藍牙是否激活等)，來預測用戶期望打開5個apps預測結果，展現在用戶手機的桌面上．大量實驗表明， 與其他方法相比，Predictor方案能夠減少建模時間的同時提高預測的準確度．

1 相關工作

目前的apps使用預測工作有兩種優(yōu)化方案.

第1類工作是優(yōu)化組織數據．ZOU等[5]提出一些輕量級的預測方法(如LU和貝葉斯等算法)，根據用戶過往打開app的記錄來預測下一個app的使用概率．PARATE等[6]增加了傳感器的上下文來預測app啟動序列．YAN等[7]提出的 FALCON利用與用戶所處地點和空間信息有關的上下文來預測app的啟動．HUANG等[8-9]強調app歷史使用數據通過二次整理成上下文關系的數據比直接使用更準確有效．文獻[10]介紹了基于時間、地點、硬件狀態(tài)和環(huán)境等因素的上下文特征，作為預測app使用的數據．

第2類工作是優(yōu)化數據的處理方法．PAN等[11]通過對用戶社交網絡上社交信息進行矩陣分解來實現app預測．KESHET等[12]通過對AUC(area under curve)模型最大化求解，動態(tài)預測一組最有可能啟動的app集合．ZHANG等[13]提出app啟動預測系統(tǒng)Nihao，利用樸素貝葉斯將日期、周次、地點和最近使用的app序列作為特征，實現了服務器客戶端模型． Yahoo Aviate采用平行網絡貝葉斯模型，利用并行網絡結構解決了上下文關系中復雜的計算[1]．

采用用戶上下文關系特征作為輸入數據時，默認的kNN算法會隨著特征增加而變差．MILOUD-AOUIDATE等[14]介紹了此問題的解決方案，如BAILEY[15]提出的WkNN算法，在經典的kNN中增加了權重設置．WkNN和kNN的區(qū)別在于前者并非簡單的取一個平均的k值，而是考慮了每個數據的權重，做了動態(tài)的k值規(guī)劃．與此類似的方法還有壓縮最近鄰居規(guī)則(condensed nearest neighbour, condensed NN)算法[16]和減少鄰居最近鄰居規(guī)則RNN(reduced nearest neighbour)算法[17]．這兩種算法都通過多次優(yōu)化訓練數據來消除冗余數據，以此來減少默認kNN算法中的負面影響．

以上工作分別對縮短建模時間或者提高預測準確度都有較好效果．然而，這些方法要么預測準確度不夠理想，要么在移動設備上非常消耗計算資源，導致建模時間過長．我們認為在對app使用進行預測時，僅需區(qū)分噪點和小概率習慣，就能提高預測準度．所以，本研究首次將增量IkNN模型應用到app使用預測當中，并設計了聚類有效值CEV策略．本研究與以往工作主要區(qū)別在于：首先，本研究模型是動態(tài)更新的．在移動設備上，app訓練數據隨著用戶的喜好和環(huán)境變化而經常發(fā)生改變．本研究提出的增量優(yōu)化算法能夠平滑且容易對新加入的和改變的數據進行重構，顯著減少建模時間．其次，app使用預測的數據結構比較復雜．針對復雜結構設計一些復雜的策略雖然會帶來更精準的分類，但也會造成分類中的過擬合現象．本研究通過增加CEV策略來減少多維度特征帶來的分類錯誤，提高了分類的準確度，在不同的數據集的準度測試中，能夠體現穩(wěn)定的預測性能．

2 上下文特征

實現app使用預測的過程通常包含數據預處理和預測模型兩部分．這里討論數據預處理中上下文特征的處理，從app的使用數據中提取上下文特征，再將上下文特征轉換為可計算的相似度值．

2.1 提取上下文特征

常見的app點擊事件流水如表1．當某個app動作被執(zhí)行，會有一組相應的“基本特征”隨之產生[1]．例如，此次點擊事件的時間、地點，以及是否打開WiFi等．

表1 一個app點擊事件流水片段Table 1 A sequence of app events

值得注意的是，HUANG等[8]指出，若將以時間為順序的“基本特征”整理為以事件為中心的“上下文特征”，則會提高預測結果的準確度．具體來說，就是要將發(fā)生的事件整理為“鍵-值”隊的形式，即點擊的事件為“鍵”，而圍繞著事件發(fā)生的上下文特征為“值”．

如此又會產生新的問題——設置多少個上下文特征才適合呢？為此，本研究隨機選取了平均每個用戶在3個月內近1 500條app點擊事件中，關于特征數量與預測準確度和對應預處理時間的記錄．特征數量理論上沒有限制，但基于移動端的處理能力和處理時間在可接受的范圍內，本研究選取了2～12個特征所對應的記錄．

表2 預測準度和預處理時間對應在不同數量的上下文特征數據Table 2 The prediction accuracy and preprocessing time with different numbers of session features

由表2可見，上下文的特征設置越多，準確度就越高，但也需要更多的預處理時間．因為需要轉換為計算的向量，所以為了均衡預測準度和建模預處理時間，本研究采用以下8個上下文特征作為最終的輸入數據：① 上一個打開的app；② 是否連接音頻；③ 是否連接充電線；④ 是否發(fā)生位置改變；⑤ 是否連接WiFi；⑥ 是否有網絡數據連接；⑦ 是否有藍牙連接；⑧ 是否有光暗變化．

2.2 相似度值

取得上下文特征的目的是找出這些特征之間的相似性．而相似性的值可通過計算上下文特征之間的歐氏距離獲得．所以，需要將上下文特征轉換為距離向量，通用的方法是利用word2vec工具進行處理[18-19]．在word2vec中，如果兩個詞(特征)非常相似，它們相似度值就比較?。裕瑸楸阌诿枋龊屠斫?，本研究將相似度值序列化為0到1，再用1減去實際相似度值作為最終的呈現結果．

具體來說，給定一組app事件序列E， 當app打開事件e1∈E， 且有事件e2∈E， 它們對應的上下文特征分別為s1和s2， 則兩事件的距離為

(1)

其中，s1i∈s1，s2i∈s2，i∈{1, 2, …, 8}；s1i和s2i的相似度值similarity(s1i,s2i)可通過word2vec計得．

表3是部分上下文特征的記錄日志．基于演示的限制，在此僅羅列了事件編號為3025、3528和4115的索引．

表3 一個上下文特征片段Table 3 A snippet of session features

從表3可見，編號為3025的點擊事件，啟動的應用為Android.mms，它上一個打開的app為Android.setting．這次點擊事件是在用戶剛剛到達家，連接了WiFi名為CR502的無線網絡后發(fā)生的，操作時屏幕變亮了．

結合表3和式(1)可見，圖1顯示了事件3025、3582和4115兩兩之間的相似度關系．其中，事件3025和3582之間的距離是0.173 5，非常趨近于0，說明這兩個事件的操作類似．事件3582和4115之間歐氏距離是0.779 1，說明這兩個事件之間的聯系不是特別強．值得注意的是，圖1顯示是平面圖，而在實際環(huán)境中，實例之間的關系是多維度的空間向量圖．

圖1 事件3025、3582、和4115之間的距離關系Fig.1 The distance relationship between the events of 3025, 3582, and 4115

可見，本研究將上下文特征計算后的相似距離作為輸入數據傳送到預測模型．

3 預測模型

3.1 預測模型概述

在app使用預測模型中需要解決兩個問題：

1)縮短建模時間．當增量數據到來時促使周期性重建預測模型，導致建模時間越來越長．

2)提高預測準度．調整預測模型中上下文特征的數量和特征權重在一個合適值．

對于問題1)，帶有增量的預測模型可節(jié)省建模時間．本研究通過與主流的增量模型對比，并根據實際環(huán)境特點，選取時間復雜度最小的IkNN模型[20]，可縮短建模時間．

對于問題2)，采用輕量級權重策略CEV，能夠幫助區(qū)分在app使用過程中產生的噪聲和真實小概率習慣的區(qū)別，從而提高預測準度．

3.2 增量模型

在默認的kNN模型中包含了對形成分類簇描述的四元組〈Cls(Oi), Sim(Oi), Num(Oi), Rep(Oi)〉， 它們表述的屬性為：① Cls(Oi)為聚類Oi的名字； ② Sim(Oi)為聚類Oi的半徑； ③ Num(Oi)為聚類Oi的實例數量； ④ Rep(Oi)為聚類Oi的中心點．

默認kNN模型聚類示意如圖2．一個聚類的半徑距離是中心a點Rep(Oi)到邊際b點的距離．其中，圓圈表示正確分類樣本．

圖2 kNN模型中的一個聚類示意圖Fig.2 A cluster in kNN model

特別值得注意的是，若形成分類簇的過程中，包含的部分實例名與原類名不符，但又被劃分在該類中，則稱這些實例為“錯分樣本(erroneous classification instances, ECI)”，如圖2中的方框，正確被分類在簇外的異類點為實心圓點．

初始時建模使用默認的kNN模型進行訓練．當新數據到來時，利用帶有增量的kNN模型(IkNN)去更新新模型．

IkNN模型在默認的kNN模型中添加了新的元組“層”(layer)概念[20]，因此，IkNN模型屬性包含了〈Cls(Oi), Sim(Oi), Num(Oi), Rep(Oi), Lay(Oi)〉五元組． 其中， Lay(Oi)為分類簇之間層級描述，通過此屬性能夠體現分類簇之間遍歷的優(yōu)先級．

在每一次IkNN模型處理增量的過程中，都需要判斷新到增量數據是否能被已經形成的簇所覆蓋．若增量數據滿足被覆蓋的條件，則標記為已覆蓋集合(covered set, CS)；否則，標記為未覆蓋集合(uncovered set,US)．

CS定義為：當新增實例到來時，若能被已經存在的分類簇所覆蓋，則該聚類的五元組中的Num變量加1；否則，檢查是否能夠被最近擴展的簇所覆蓋，若可以，則除了該簇的Num變量更新加1外，其半徑Sim也需要更新．值得一提的是，當簇擴展時，關于該簇的錯分樣本ECI比例也會被更新，當該比例超過一定的閾值時，會被限定擴展．

US定義為：當新增實例不能被任何分類簇覆蓋時，系統(tǒng)將收集這些實例做為一個新的分類簇，該簇內也許包含了新的習慣或噪點，并等待下一次增量數據到來后再做處理．同樣，當未來該簇的ECI比例超過給定的閾值時，表明該分類簇需重新劃分新的層值Lay來保證簇的ECI比例滿足閾值．

為計算ECI比例，首先需計算ECI中關于實例Ej的權重

(2)

其中，dij是實例Ej距離簇Oi的歐氏距離；ri是Oi的半徑．由于一個樣本有可能被幾個簇所覆蓋，所以Qj表示Ej被覆蓋所有簇的集合．

(3)

其中，ej為簇中的一個實例.

為緩和由于多維度帶來的分類錯誤，本研究在形成新簇的過程中添加了CEV方法．

3.3 聚類有效值

值得注意的是，上下文特征在不同條件下對預測所起的作用不一樣．為充分解釋這一點，本研究分析了30位用戶在100 d的數據集，結果如圖3．

圖3 打開所有app、瀏覽器和音樂播放器3種情況下，8個上下文特征的占比Fig.3 Percentage of the eight session features for all apps, browsers and music players, respectively

圖3(a)給出了記錄中每個特征總數分別在所有特征總數中的比例．如圖3(a)，在所有數據集中，不同的上下文特征比例是不相同的，如“上一個打開app”的屬性是最高的，而“上一個藍牙連接”屬性是最低的，所以，不能采用相同的權重去處理不同屬性．

圖3(b)和圖3(c)分別展示了瀏覽器和音樂app中不同上下文特征的不同影響．圖3(b)顯示了瀏覽器app中“上一個打開app”的屬性是最高的，而圖3(c)顯示了音樂app中“上一個音頻連接”是最高的．

大部分相關工作對上下文特征并沒有區(qū)分對待．為此，本研究提出聚類有效值CEV方法來解決這個問題，在原有的IkNN模型中添加新的元組“貢獻度(contribution)”，從而使新模型的屬性包含了〈Cls(Oi), Sim(Oi), Num(Oi), Rep(Oi), Lay(Oi), Crb(Oi)〉六元組．本研究設計的最后一個元組包含高頻性和穩(wěn)定性兩部分.以分類簇Oi的上下文特征m為例，其高頻性定義為，上下文特征出現的頻率gm和該簇內所有實例Num(Oi)的比值， 即

(4)

穩(wěn)定性定義為上下文特征m變化的次數hm和該簇內所有實例Num(Oi)的比值．為讓比值結果和高頻性比例保持正相關，可用1減去該比值，即

(5)

最后如式(6)， Crb(Oi)由發(fā)生頻率最高和穩(wěn)定性最好的特征加和決定．

(6)

當Crb(Oi)高于給定的閾值，則設CEV=1；否則，設CEV=0．

3.4 帶有聚類有效值的增量模型

本研究將在增量學習的元組屬性中添加Crb(Oi)參數，即添加帶有CEV策略的增量模型，稱為ICkNN模型．將該模型應用在實際環(huán)境中的解決方案Predictor，其流程如圖4(a)，對應的算法執(zhí)行過程如圖4(b)．

當沒有增量數據到來時，使用kNN模型做第1次分類．當有數據改變或增加時，首先判斷這些新的數據是否能夠被已有的模型所覆蓋(CS)，如果可以，則更新模型半徑和數量等元組參數；如果不能被覆蓋(US)，就需要通過閾值判斷是否形成新的模型簇，沒有滿足閾值條件，則等待下一次增量到來再做計算；如果閾值滿足條件，即CEV=1，且ECI=1時，新的分類簇才會從頂層簇再次分離．最后，輸出的模型作為下次數據到來時建模依據．

若分類嚴格，則形成簇的數據量增加，建模時間也會增加；反之亦然．所以簇的數量在算法復雜度中扮演非常重要的角色．圖5分別顯示了在ICkNN和IkNN模型中，簇的數量和k值之間的關系．在IkNN模型中，k的取值范圍通常為5～13[14]．若k<5， 則模型的預測準確度會較高，也會產生較多的簇，從而增加建模時間；若k>13， 產生的簇數量會較少，從而模型的預測準確度也會較低．因此，在ICkNN模型中可將k設置在5～7內，則Predictor不僅提供了平滑的分類，且不增加建模時間．

(b)ICkNN增量模型建模過程偽代碼

圖5 ICkNN模型的簇數量Fig.5 The number of cluster in ICkNN

3.5 App使用的預測方案

Predictor對下一個app使用的預測方案如圖6．當事件e作為輸入數據送入ICkNN模型中，首先計算事件e和所有簇之間的距離．然后，若e被單個簇所覆蓋，模型輸出該簇的名字，如圖6(a)中輸出“電話”的app應用預測；若e同時被2個以上(含2個)的簇所覆蓋，模型輸出所有覆蓋簇中較高層簇的名字，如圖6(b)中輸出“短信”的app應用預測；若事件e不被任何簇所覆蓋，則模型輸出距離最近的簇名，如圖6(c)中輸出“郵件”的app應用預測結果．

圖6 App使用預測場景Fig.6 (Color online) Scenarios of app usage prediction

4 實 驗

為驗證ICkNN模型的性能，本研究選取30個活躍用戶在100 d內用Predictor記錄的數據．用戶群體為大學在校師生，年齡在18～55歲，且每位用戶所安裝的app超過50個．本研究在這些用戶的手機端以每5 s(不停止)1次的頻次記錄該手機的使用情況，并將所提取的上下文特征向量在電腦上利用VM ware模擬器來仿真分析主流手機的處理能力．

4.1 測 試

使用交叉驗證的方式測試不同算法的性能，這些算法包括lastest used (LU)算法[5]、most frequently used (MFU)算法[5]和tree augmented Naive byes (TAN) 算法[1]．將日志數據平均分為10份，在第1次測試中，將第1～5份數據作為訓練數據去建立app使用預測模型，并將第6份作為增量數據．而在第2輪測試中，將第1～6份作為訓練數據，第7份數據作為測試數據，依此類推．通過分析在此過程中的建模時間和平均準確度兩個推薦系統(tǒng)評價指標[10]，其結果如表4．

表4 不同app使用不同預測算法時的性能Table 4 Performance of different algorithms on app usage prediction

4.2 分 析

由表4可見，① LU和MFU算法的建模時間比其他算法更短，這是因為IkNN、ICkNN和TAN算法需要建模的計算時間，但是LU算法和MFU算法僅需簡單地計算app的使用頻率并排序； ② ICkNN算法的平均準度最高，且其在5輪不同的數據集中表現的預測準確度變化不大，亦即預測結果比IkNN算法顯得更穩(wěn)定一些．

圖7顯示了平均準確度和預測的app數量之間的關系．由圖7 可見，IkNN、ICkNN和TAN算法在輸出5個app時預測結果的平均準確度要比LU和MFU算法的準確度更高一些．IkNN、ICkNN、TAN、LU和MFU算法之間平均準確度隨著預測的app數量減少而變大．特別是TAN算法，在預測單個app時最準確．

圖7 不同算法下預測app的平均準確度和預測app數量間的關系Fig.7 The average accuracy versus the number of predicated apps for different algorithms

結 語

本研究關注當用戶偏好和app狀態(tài)發(fā)生變化時，如何減少預測的建模時間和提高預測的準度．通過引入增量學習算法避免新到數據需要重新建模的問題．同時，提出帶有CEV策略的ICkNN模型來區(qū)分小概率實踐和噪點之間的區(qū)別，從而提高了預測的準確度．通過實驗測試了ICkNN模型和主流預測算法LU、MFU，以及TAN模型的性能．結果表明，MFU和LU有比較高的準確度和很短的建模時間，但是當預測的app較少時，他們的預測準確度很低，IkNN和ICkNN模型要比TAN的建模時間要短，而ICkNN模型平均預測準確度在所有主流預測算法中是最高的．

下一步我們將結合云計算，當用戶第1次使用Predictor時，提供app使用預測的冷啟動工作，為新用戶在云端尋找最相似用戶作為該用戶的冷啟動的app推薦列表．