基于智能手機(jī)用戶行為習(xí)慣的App使用預(yù)測算法研究

王克強(qiáng) 王保群 張雨帥 王紀(jì)超

1(重慶郵電大學(xué)通信與信息工程學(xué)院 重慶 400065)2(重慶郵電大學(xué)移動通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室 重慶 400065)

0 引 言

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

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

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

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

本文的主要貢獻(xiàn)為：

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

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

1 相關(guān)概念

1.1 PrefixSpan算法介紹

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

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

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

定義2序列長度。序列中所有事件元素?cái)?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ò)直觀地表示為一個(gè)復(fù)雜的賦值因果關(guān)系圖，完整的貝葉斯網(wǎng)絡(luò)是一個(gè)二元組B=，其中：

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

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

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

(1)

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

2 特征提取與分析

2.1 時(shí)間特征提取與分析

智能手機(jī)用戶將要使用的下一個(gè)App與用戶使用App的時(shí)間息息相關(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個(gè)時(shí)間段進(jìn)行分析。

圖1 各時(shí)間段APP使用情況表

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

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

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

3 WAPA算法設(shè)計(jì)

3.1 問題分析

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

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

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

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

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

3.2.1相關(guān)定義

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

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

(2)

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

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

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

定義6App序列模式。給定一個(gè)最小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è)計(jì)

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

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

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

3.3 WAPA算法

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

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

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

4.1 實(shí)驗(yàn)配置

實(shí)驗(yàn)軟硬件配置如表1所示。

表1 實(shí)驗(yàn)配置

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

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

4.3 評價(jià)指標(biāo)

指標(biāo)1準(zhǔn)確率(Accuracy)表示App預(yù)測過程中預(yù)測正確的次數(shù)占總預(yù)測次數(shù)的比值。計(jì)算公式如下：

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

指標(biāo)2訓(xùn)練時(shí)間指在實(shí)驗(yàn)中，模型訓(xùn)練所用運(yùn)行時(shí)間越短，占用資源越少，對用戶影響越小，算法越好。

4.4 實(shí)驗(yàn)結(jié)果分析

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

圖3 不同個(gè)數(shù)候選App下預(yù)測準(zhǔn)確率

綜上所述，我們預(yù)加載App時(shí)，只需要預(yù)加載準(zhǔn)確率最高的3～4個(gè)App即可，此時(shí)可在保證準(zhǔn)確率的情況下盡量少地占用手機(jī)資源。

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

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

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

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

圖5 序列長度與預(yù)測準(zhǔn)確率

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

(4) 不同算法訓(xùn)練時(shí)間比較 不同算法的準(zhǔn)確率和訓(xùn)練時(shí)間如表2所示。

表2 各算法訓(xùn)練時(shí)間

由表2可知，WAPA算法因?yàn)榧尤肓酥悄苁謾C(jī)用戶對App的喜愛程度，我們得到的下一個(gè)App就是用戶喜愛程度較高的App，所以預(yù)測準(zhǔn)確率較其他算法稍高。由于WAPA算法采用Weighted-Prefixspan算法挖掘序列模式過程中，采用剪枝過程大大減少了挖掘序列模式的運(yùn)行時(shí)間，故算法的訓(xùn)練時(shí)間較其他算法有了很大改善。

5 結(jié) 語

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