王克強 王保群 張雨帥 王紀超

1(重慶郵電大學通信與信息工程學院 重慶 400065)2(重慶郵電大學移動通信技術(shù)重慶市重點實驗室 重慶 400065)

0 引 言

隨著智能手機進入人們的生活，涌現(xiàn)了各種各樣的移動App以滿足人們的生活需要。極光大數(shù)據(jù)在近日發(fā)布數(shù)據(jù)顯示，國內(nèi)高中低端機型的手機平均安裝App數(shù)量分別為56個、52個和39個。然而調(diào)查研究表明，智能手機用戶平均每天使用的應(yīng)用程序數(shù)量大約為9個，大量安裝的應(yīng)用程序增加了用戶查找APP的時間，占用了手機內(nèi)存，造成手機卡頓等現(xiàn)象，嚴重影響了用戶體驗。

Trinh等[1]通過收集智能手機用戶使用App數(shù)據(jù)，通過大數(shù)據(jù)分析得出手機用戶使用App的行為是有一定規(guī)律的，例如用戶在家或者工作中使用SMS最多，在休息時使用Media最多，在假期使用相機最多等行為，證明了用戶使用App的行為可以通過研究用戶使用App的行為習慣進行預測。因此，為了解決上述提出的問題，越來越多的人通過研究智能手機用戶使用App的行為習慣，尋找用戶與手機App使用之間的關(guān)系，以便預測用戶將要使用的下一個App，從而可以將App提前預加載到手機中，減少手機App的冷啟動時間，提升用戶體驗。

Huang等[2-4]根據(jù)用戶瀏覽網(wǎng)頁的行為習慣提出了基于貝葉斯模型和馬爾可夫模型的Web網(wǎng)頁預測模型。通過網(wǎng)頁預測模型的啟發(fā)，Ma等[5]提出了基于貝葉斯網(wǎng)絡(luò)模型和線性回歸模型的智能手機App使用預測算法，并且得到了較好的預測準確度；Song等[6]通過分析手機App后臺運行情況，提出基于App共存模式的應(yīng)用程序使用預測模型，實驗分析該模型可使手機App的重啟率降低10%；Shin等[7]分析設(shè)計了基于用戶的樸素貝葉斯模型和基于App的樸素貝葉斯模型，得到可能使用App的Topk列表，并設(shè)計了最可能使用的App UI界面，從而大大減少了用戶查找App的時間，得到了較好的用戶滿意度反饋；劉帥琪等[8]采用Apriori關(guān)聯(lián)規(guī)則挖掘算法挖掘智能手機用戶App使用記錄中的序列模式，得到的預測模型能夠為用戶提供較為理想的App列表。但是以上研究僅僅是對智能手機用戶使用App的記錄來進行預測，并沒有把單個用戶對App的喜愛程度考慮在內(nèi)，例如某些用戶比較喜歡聽音樂，那么該用戶對音樂播放器的喜愛程度顯然與其他手機APP的喜愛程度是不同的。

針對此問題，本文通過衡量智能手機用戶使用App頻次和使用App時長作為用戶對App喜愛程度的度量，采用Weight-PrefixSpan序列模式挖掘算法挖掘用戶使用App的行為習慣，結(jié)合貝葉斯網(wǎng)絡(luò)整合用戶App使用記錄、使用App時間等特征，提出了一種新的預測下一個將要使用的App的方法，使得預測用戶將要使用的App算法更加合理、準確。

本文的主要貢獻為：

(1) 考慮智能手機用戶對每個App的喜愛程度，設(shè)計實現(xiàn)了加入用戶對APP喜愛程度的Weight-PrefixSpan序列模式挖掘算法，并將其與貝葉斯網(wǎng)絡(luò)算法相結(jié)合，提出了一種新的預測用戶下一個最可能使用的App的算法模型——WAPA算法。與傳統(tǒng)Bayesian預測算法、Apriori預測算法相比，該算法有效地提高了預測準確度，且大大減少了算法模型的訓練時間。

(2) 在不同用戶數(shù)據(jù)集上的實驗表明，本文提出的WAPA算法可以有效地挖掘用戶使用App的行為習慣，提高預測準確率。

1 相關(guān)概念

1.1 PrefixSpan算法介紹

Han等[9]提出了一種挖掘序列模式的算法，其主要思想是檢測成為prefix前綴的序列，將數(shù)據(jù)庫在這個prefix上投影，挖掘其中的頻繁項，然后擴充到prefix中，繼續(xù)進行挖掘，直到挖掘出所有的頻繁序列，PrefixSpan算法在時間和空間效率上比Apriori算法有較大提高。

設(shè)I={x1,x2,…,xn}是一個事件集合，其中xi代表集合中的事件。

定義1事件序列。設(shè)S={xi,xj,xk,…}是集合I的一個有序子集，其中i

定義2序列長度。序列中所有事件元素數(shù)目的總和。

定義3序列模式。若序列S在數(shù)據(jù)庫中發(fā)生的次數(shù)不小于規(guī)定的閾值，則稱S為序列模式。

PrefixSpan算法的步驟如下：

1)k=1；

2) 從數(shù)據(jù)庫中發(fā)現(xiàn)長度為k的序列模式S1；

3) 以S1劃分投影數(shù)據(jù)庫，分別挖掘長度為k的序列模式為前綴prefix的長度為k+1的序列模式S=L，如果挖掘結(jié)果為空，則停止；

4)k=k+1，S=L，轉(zhuǎn)步驟3)；

5) 記錄所有挖掘到的序列模式。

1.2 貝葉斯網(wǎng)絡(luò)

貝葉斯網(wǎng)絡(luò)[10]，又稱貝葉斯信念網(wǎng)絡(luò)，是圖論與概率論的結(jié)合。貝葉斯網(wǎng)絡(luò)直觀地表示為一個復雜的賦值因果關(guān)系圖，完整的貝葉斯網(wǎng)絡(luò)是一個二元組B=，其中：

(1)G=(V(G),E(G))，是一個有向無環(huán)圖，V(G)是節(jié)點組合，節(jié)點表示所研究問題域中的變量；E(G)為弧集合，有向弧定性表示節(jié)點之間的概率依賴關(guān)系。

(2) 網(wǎng)絡(luò)參數(shù)θ構(gòu)成的條件概率表達了節(jié)點之間的因果依賴程度。

貝葉斯網(wǎng)絡(luò)的數(shù)學基礎(chǔ)是貝葉斯公式，基于先驗概率，根據(jù)相關(guān)條件可推導后驗概率。并且網(wǎng)絡(luò)蘊含了條件獨立性假設(shè)，如果給定根節(jié)點的先驗概率分布和非根節(jié)點的條件概率分布，則可以通過推理得到包含所有節(jié)點的聯(lián)合概率分布，如下式所示：

(1)

式中：Vi為網(wǎng)絡(luò)節(jié)點；Pa(Vi)為節(jié)點Vi的父節(jié)點。

2 特征提取與分析

2.1 時間特征提取與分析

智能手機用戶將要使用的下一個App與用戶使用App的時間息息相關(guān)。我們將一天分為[0 ∶00-6 ∶00]、[6 ∶00-9 ∶00]、[9 ∶00-12 ∶00]、[12 ∶00-14 ∶00]、[14 ∶00-18 ∶00]、[18 ∶00-22 ∶00]、[22 ∶00-24 ∶00]7個時間段進行分析。

圖1 各時間段APP使用情況表

分析用戶在各個時間段對于App的使用情況得圖1，可以看出SMS短信和Mobile mail郵件軟件在9 ∶00-12 ∶00或14 ∶00-18 ∶00即工作時間使用次數(shù)較多，而YouTube視頻播放軟件在18 ∶00-22 ∶00即晚上休息時間使用次數(shù)較多，這說明了智能手機用戶使用App的行為與每天的時間段有很大關(guān)系，所以我們選擇時間段作為我們的一個特征。

2.2 App使用記錄特征提取與分析

智能手機用戶使用App的記錄是預測下一個App算法的重要特征。手機用戶使用App時大多有一定的規(guī)律，根據(jù)分析數(shù)據(jù)統(tǒng)計可得某用戶一年內(nèi)12 000條使用記錄中，[SMS,Mobile mail]即使用完SMS后，下一個使用Mobile mail的頻次多達600多次；[Facebook,youtube]的頻次多達456次；類似使用記錄在其他用戶App使用記錄中也很明顯。故我們提取智能手機用戶App使用記錄作為我們的一個特征。

3 WAPA算法設(shè)計

3.1 問題分析

在預測用戶將要使用的下一個App的過程中，傳統(tǒng)的貝葉斯和其他App預測算法存在兩個問題：

1) 傳統(tǒng)App預測算法僅僅對App使用記錄進行統(tǒng)計分析，并沒有考慮用戶使用App的習慣，沒有挖掘出用戶使用App過程中各App之間的規(guī)律。

2) 用戶使用智能手機時大多數(shù)情況下僅僅喜歡使用其中幾款App，傳統(tǒng)App預測算法沒有考慮到用戶對各App的喜愛程度，而是認為所有App的重要程度相同，這顯然是不合理的。

針對以上問題，本文對智能手機用戶使用App的記錄進行分析，通過衡量用戶使用App的頻次和使用App的時長，得到每個App的權(quán)重，用來表示智能手機用戶對App的喜愛程度。采用Weight-PrefixSpan序列模式挖掘算法挖掘手機用戶使用App的序列模式，并采用貝葉斯網(wǎng)絡(luò)算法整合序列模式與使用時間段的關(guān)系，提出一種新的預測用戶將要使用的下一個App的算法——WAPA算法。

3.2 Weighted-PrefixSpan序列模式挖掘算法

3.2.1相關(guān)定義

定義4App權(quán)重。給定一個App使用記錄S={x1,x2,…,xn}，則App權(quán)重計算如下式所示：

w(xi)=αf(xi)+(1-α)t(xi)

(2)

式中:w(xi)為Appxi的權(quán)重，f(xi)為Appxi在使用記錄s中的使用頻次，t(xi)為Appxi在使用記錄s中的使用時長，α為權(quán)重參數(shù)，用來權(quán)衡使用頻次和使用時長兩個特征。

定義5序列權(quán)值。給定一個App序列S={x1,x2,…,xn}和App權(quán)重集合w={w(x1),w(x2),…,w(xn)}，則App序列s的權(quán)值計算如下所示：

式中：n為序列中App的個數(shù)。

定義6App序列模式。給定一個最小App序列權(quán)值min_weight，如果某App序列s的序列權(quán)值權(quán)值不小于min_weight，即W(s)≥min_weight，則稱該App序列s為App序列模式。

3.2.2Weight-PrefixSpan序列模式挖掘算法設(shè)計

本算法考慮智能手機用戶對每個App的喜愛程度，通過衡量用戶使用App的頻次和使用App的時長，得到每個App的權(quán)重，序列模式挖掘過程中采用序列權(quán)值對算法生成的序列進行剪枝，從而得到我們所需的App加權(quán)序列模式。

Weighted-PrefixSpan序列模式挖掘算法流程如圖2所示。

圖2 Weighted-PrefixSpan序列模式挖掘算法流程圖

3.3 WAPA算法

基于上述討論，我們可以了解智能手機用戶使用App的行為與該App的序列模式和使用時間段息息相關(guān)，本文采用貝葉斯網(wǎng)絡(luò)算法將與下一個將要使用App具有因果依賴關(guān)系的App加權(quán)序列模式和App使用時間等特征進行整合，提出WAPA算法。如下式所示：

式中：P(A,S′,T)為序列模式S′,使用時間T，AppA的聯(lián)合概率分布，序列模式S′由改進的Weight-PrefixSpan序列模式挖掘算法挖掘得來。由式(4)可得在使用時間段T內(nèi)序列模式S′發(fā)生的情況下，下一時刻使用AppA的條件概率。

4 實 驗

4.1 實驗配置

實驗軟硬件配置如表1所示。

表1 實驗配置

4.2 數(shù)據(jù)集的選擇

本文采用美國國家科學基金會資助的livelab項目提供的數(shù)據(jù)集，該數(shù)據(jù)集包含了34名學生在一年內(nèi)的手機使用情況，包含App使用記錄、使用App的時間、地點、手機、充電狀態(tài)、加速度狀態(tài)、CPU利用率、Wifi連接情況等等。我們對數(shù)據(jù)集中的特征進行分析，綜合每個特征的可利用性，最終簡化特征數(shù)量，選擇對于預測用戶將要使用的下一個App最重要的2個特征：智能手機用戶使用App的時間和App使用記錄。從數(shù)據(jù)集中隨機抽取70%作為訓練集，其余30%作為測試集。

4.3 評價指標

指標1準確率(Accuracy)表示App預測過程中預測正確的次數(shù)占總預測次數(shù)的比值。計算公式如下：

一般情況下，模型的準確率越高，說明模型的效果越好。

指標2訓練時間指在實驗中，模型訓練所用運行時間越短，占用資源越少，對用戶影響越小，算法越好。

4.4 實驗結(jié)果分析

(1) 候選App個數(shù)的確定 由圖3可以看出當候選App個數(shù)為3～4個時，WAPA等各種算法的預測準確率較好。當繼續(xù)增加候選App個數(shù)時，預加載App所占用資源會繼續(xù)增加，但是總預測準確率增加較少。

圖3 不同個數(shù)候選App下預測準確率

綜上所述，我們預加載App時，只需要預加載準確率最高的3～4個App即可，此時可在保證準確率的情況下盡量少地占用手機資源。

(2) 權(quán)重參數(shù)α的確定 首先，初始化α=0.1,0≤α≤1，采用輪詢方式獲取使得準確率(Accuracy)最高的α，此時的α即為App使用頻次和App使用時長最佳參數(shù)。實驗結(jié)果如圖4所示。

圖4 不同權(quán)重參數(shù)α下的預測準確率

由圖4可知，準確率(Accuracy)隨權(quán)重參數(shù)α(即使用時間和使用頻次的衡量變量)的改變而改變，當α=0.8左右時準確率最高，即此為衡量用戶使用App時長和使用頻次所占比重的最佳值。

(3) 序列長度的確定 序列模式挖掘過程中，我們會挖掘到序列長度為1的序列模式、長度為2的序列模式、長度為3的序列模式等等，分別計算在各序列長度下預測的準確率。實驗結(jié)果如圖5所示。

圖5 序列長度與預測準確率

如圖5所示在序列長度為3時，App預測的準確率最高，當序列長度為1時，相當于直接統(tǒng)計各App的使用頻次。當序列長度過長時，前面的App使用對下一個App的使用影響較小，對于用戶行為習慣不具有代表性，導致預測準確率降低。

(4) 不同算法訓練時間比較 不同算法的準確率和訓練時間如表2所示。

表2 各算法訓練時間

由表2可知，WAPA算法因為加入了智能手機用戶對App的喜愛程度，我們得到的下一個App就是用戶喜愛程度較高的App，所以預測準確率較其他算法稍高。由于WAPA算法采用Weighted-Prefixspan算法挖掘序列模式過程中，采用剪枝過程大大減少了挖掘序列模式的運行時間，故算法的訓練時間較其他算法有了很大改善。

5 結(jié) 語

本文針對智能手機用戶使用App過程中的行為習慣，將用戶對于App的喜愛程度考慮在內(nèi)，提出了一種新的基于用戶行為習慣的下一時刻將要使用App的預測算法。該方法首先采用序列模式挖掘技術(shù)挖掘用戶使用App過程中的序列模式，然后使用貝葉斯網(wǎng)絡(luò)將序列模式、使用時間等特征進行整合。實驗表明，相比于其他算法模型，本文提出的WAPA算法能夠有效地預測下一個App的使用，而且算法中的剪枝操作大大減少了模型的訓練時間。下一步的研究將著重于算法的應(yīng)用，同時考慮智能手機預加載App所占用的資源與用戶體驗提升之間的關(guān)系衡量。