基于智能手機用戶行為習慣的App使用預測算法研究

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

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

0 引 言

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

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

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

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

本文的主要貢獻為：

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

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

1 相關概念

1.1 PrefixSpan算法介紹

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

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

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

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

定義3序列模式。若序列S在數據庫中發生的次數不小于規定的閾值，則稱S為序列模式。

PrefixSpan算法的步驟如下：

1)k=1；

2) 從數據庫中發現長度為k的序列模式S1；

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

4)k=k+1，S=L，轉步驟3)；

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

1.2 貝葉斯網絡

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

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

(2) 網絡參數θ構成的條件概率表達了節點之間的因果依賴程度。

貝葉斯網絡的數學基礎是貝葉斯公式，基于先驗概率，根據相關條件可推導后驗概率。并且網絡蘊含了條件獨立性假設，如果給定根節點的先驗概率分布和非根節點的條件概率分布，則可以通過推理得到包含所有節點的聯合概率分布，如下式所示：

(1)

式中：Vi為網絡節點；Pa(Vi)為節點Vi的父節點。

2 特征提取與分析

2.1 時間特征提取與分析

智能手機用戶將要使用的下一個App與用戶使用App的時間息息相關。我們將一天分為[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即工作時間使用次數較多，而YouTube視頻播放軟件在18 ∶00-22 ∶00即晚上休息時間使用次數較多，這說明了智能手機用戶使用App的行為與每天的時間段有很大關系，所以我們選擇時間段作為我們的一個特征。

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

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

3 WAPA算法設計

3.1 問題分析

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

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

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

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

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

3.2.1相關定義

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

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

(2)

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

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

式中：n為序列中App的個數。

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

3.2.2Weight-PrefixSpan序列模式挖掘算法設計

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

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

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

3.3 WAPA算法

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

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

4 實 驗

4.1 實驗配置

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

表1 實驗配置

4.2 數據集的選擇

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

4.3 評價指標

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

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

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

4.4 實驗結果分析

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

圖3 不同個數候選App下預測準確率

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

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

圖4 不同權重參數α下的預測準確率

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

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

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

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

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

表2 各算法訓練時間

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

5 結 語

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