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

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

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

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

1 相關(guān)工作

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

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

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

采用用戶上下文關(guān)系特征作為輸入數(shù)據(jù)時(shí)，默認(rèn)的kNN算法會(huì)隨著特征增加而變差．MILOUD-AOUIDATE等[14]介紹了此問題的解決方案，如BAILEY[15]提出的WkNN算法，在經(jīng)典的kNN中增加了權(quán)重設(shè)置．WkNN和kNN的區(qū)別在于前者并非簡(jiǎn)單的取一個(gè)平均的k值，而是考慮了每個(gè)數(shù)據(jù)的權(quán)重，做了動(dòng)態(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ù)面影響．

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

2 上下文特征

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

2.1 提取上下文特征

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

表1 一個(gè)app點(diǎn)擊事件流水片段Table 1 A sequence of app events

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

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

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

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

2.2 相似度值

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

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

(1)

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

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

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

從表3可見，編號(hào)為3025的點(diǎn)擊事件，啟動(dòng)的應(yīng)用為Android.mms，它上一個(gè)打開的app為Android.setting．這次點(diǎn)擊事件是在用戶剛剛到達(dá)家，連接了WiFi名為CR502的無線網(wǎng)絡(luò)后發(fā)生的，操作時(shí)屏幕變亮了．

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

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

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

3 預(yù)測(cè)模型

3.1 預(yù)測(cè)模型概述

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

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

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

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

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

3.2 增量模型

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

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

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

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

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

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

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

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

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

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

(2)

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

(3)

其中，ej為簇中的一個(gè)實(shí)例.

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

3.3 聚類有效值

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

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

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

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

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

(4)

穩(wěn)定性定義為上下文特征m變化的次數(shù)hm和該簇內(nèi)所有實(shí)例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)用在實(shí)際環(huán)境中的解決方案Predictor，其流程如圖4(a)，對(duì)應(yīng)的算法執(zhí)行過程如圖4(b)．

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

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

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

圖5 ICkNN模型的簇?cái)?shù)量Fig.5 The number of cluster in ICkNN

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

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

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

4 實(shí) 驗(yàn)

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

4.1 測(cè) 試

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

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

4.2 分 析

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

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

圖7 不同算法下預(yù)測(cè)app的平均準(zhǔn)確度和預(yù)測(cè)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ā)生變化時(shí)，如何減少預(yù)測(cè)的建模時(shí)間和提高預(yù)測(cè)的準(zhǔn)度．通過引入增量學(xué)習(xí)算法避免新到數(shù)據(jù)需要重新建模的問題．同時(shí)，提出帶有CEV策略的ICkNN模型來區(qū)分小概率實(shí)踐和噪點(diǎn)之間的區(qū)別，從而提高了預(yù)測(cè)的準(zhǔn)確度．通過實(shí)驗(yàn)測(cè)試了ICkNN模型和主流預(yù)測(cè)算法LU、MFU，以及TAN模型的性能．結(jié)果表明，MFU和LU有比較高的準(zhǔn)確度和很短的建模時(shí)間，但是當(dāng)預(yù)測(cè)的app較少時(shí)，他們的預(yù)測(cè)準(zhǔn)確度很低，IkNN和ICkNN模型要比TAN的建模時(shí)間要短，而ICkNN模型平均預(yù)測(cè)準(zhǔn)確度在所有主流預(yù)測(cè)算法中是最高的．

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