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

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

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

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

1 相關(guān)工作

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

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

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

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

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

2 上下文特征

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

2.1 提取上下文特征

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

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

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

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

表2 預(yù)測準(zhǔn)度和預(yù)處理時間對應(yīng)在不同數(shù)量的上下文特征數(shù)據(jù)Table 2 The prediction accuracy and preprocessing time with different numbers of session features

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

2.2 相似度值

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

具體來說，給定一組app事件序列E， 當(dāng)app打開事件e1∈E， 且有事件e2∈E， 它們對應(yīng)的上下文特征分別為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的點擊事件，啟動的應(yīng)用為Android.mms，它上一個打開的app為Android.setting．這次點擊事件是在用戶剛剛到達(dá)家，連接了WiFi名為CR502的無線網(wǎng)絡(luò)后發(fā)生的，操作時屏幕變亮了．

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

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

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

3 預(yù)測模型

3.1 預(yù)測模型概述

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

1)縮短建模時間．當(dāng)增量數(shù)據(jù)到來時促使周期性重建預(yù)測模型，導(dǎo)致建模時間越來越長．

2)提高預(yù)測準(zhǔn)度．調(diào)整預(yù)測模型中上下文特征的數(shù)量和特征權(quán)重在一個合適值．

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

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

3.2 增量模型

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

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

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

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

初始時建模使用默認(rèn)的kNN模型進(jìn)行訓(xùn)練．當(dāng)新數(shù)據(jù)到來時，利用帶有增量的kNN模型(IkNN)去更新新模型．

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

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

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

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

為計算ECI比例，首先需計算ECI中關(guān)于實例Ej的權(quán)重

(2)

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

(3)

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

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

3.3 聚類有效值

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

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

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

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

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

(4)

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

(5)

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

(6)

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

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

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

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

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

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

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

3.5 App使用的預(yù)測方案

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

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

4 實 驗

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

4.1 測 試

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

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

4.2 分 析

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

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

圖7 不同算法下預(yù)測app的平均準(zhǔn)確度和預(yù)測app數(shù)量間的關(guān)系Fig.7 The average accuracy versus the number of predicated apps for different algorithms

結(jié) 語

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

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