一種面向大數據的用戶行為挖掘的APP推薦算法

南楠 楊昌堯

（湛江幼兒師范專科學校 廣東省湛江市 524048）

大數據背景下，各種數據成幾何式快速增長。據統計，2019年全球移動用戶在App Store 和Google Play 的下載量突破了1200億次，同比去年增長了5%。面對如此海量的APP，如何幫助用戶高效地挑選出感興趣的應用，已經成為各大手機應用市場關注的焦點。

目前很多APP 推薦系統使用的都是基于項目的協同推薦算法[1]。但是該算法對于APP 的評分數據具有很高的依賴性，甚至，有的用戶對于APP 并不進行任何打分，這樣，就造成原始數據很難獲得，或者數據很稀少。本文試圖通過用戶屬性和用戶行為序列模式的挖掘，解決上述問題。

1 用戶屬性和用戶行為模式

手機上的APP 與用戶有著非常緊密的聯系，能夠反映用戶的基本屬性、行為習慣，興趣愛好等信息。本文從兩個方面來定義APP 用戶：用戶屬性[2]和用戶行為。

1.1 用戶屬性

用戶屬性包括很多方面，例如：年齡、性別、地區、職業等，還包括一些愛好、習慣、興趣、性格等。更好的理解用戶屬性，能夠幫助我們根據用戶的屬性和偏好來改進應用、服務和內容等。

1.2 用戶行為

智能手機能夠全面并詳細的記錄下用戶行為的信息，從而能更加客觀全面的分析客戶，挖掘他們自己都不知道的屬性。用戶的行為包括用戶在APP 內的行為和在APP 外的行為。APP 內的行為[3]包括收藏、點贊、轉發、評論等，利用爬蟲技術可以實現對這些數據進行收集，從而，通過這些關鍵內容對用戶的屬性進行分析，對用戶的性別、性格特點、興趣愛好等進行提取；APP 外的行為包括下載時間、使用時長、使用頻率和使用順序、APP 權限等。其中，用戶的APP 安裝數據通過APP 安裝列表[4]（APPList）來體現，用戶在APP 外的行為由使用APP 序列（APPUsage）記錄。

1.3 用戶APP行為序列模式

移動環境下用戶的APP 行為序列可以看作為時間序列，將APP 用戶一天調用的APP 記錄為一連串的二元組數據，基于這些數據進行劃分，轉化為序列數據集。

用戶使用行為序列中，可能包含多個應用。假如已有如下移動對象行為序列集D，(<1，2，3，4，5><2，3，6，12>)，其中所有的應用已經用唯一標識id 表示。

圖1：IncSPM 算法第一階段流程圖

圖2：IncSPM 算法第二階段流程圖

圖3：數據集下不同算法的性能比較

用戶行為序列模式挖掘時，對于使用序列<1，2，3，4，5>，如果當前用戶已經產生了序列<1,2,3,4>，最后可能使用的應該就是5，如果當前用戶產生序列<2,3>，則用戶下次可能用的APP 為{4,5,6}，但是，使用5 的概率高于使用4、6.因此<1，2，3，4，5>這個應該看作一個具有高可行度的行為模式序列。

將這些高行為模式序列加入到集合K 中，即為頻繁序列。但是，在大數據背景下，當頻繁序列的項目數量增加時，現有的序列挖掘算法[4]具有挖掘效率較低，挖掘得到的序列模式集過多，效用性不高，所發現的模式數量呈爆炸式增長等問題。本文引入了一種改進的序列挖掘算法，來應對序列中的增量挖掘問題。

2 后向挖掘與高效分布式增量序列模式挖掘（Incremental Sequential Pattern Mining, IncSPM）算法[5]

2.1 后向挖掘

后向挖掘算法用于高效序列模式的增量挖掘，具有以下優點：提供一種簡單的方法來檢測穩定序列；引入了唯一的穩定序列性質，即穩定序列的任何擴張也是穩定的；通過跳過對穩定序列的支持計數來提高挖掘速度；序列的新支持計數的過程簡單。

2.2 IncSPM算法

本文設計了新的同現反轉映射（Co-occurrence Reverse Map, CRMAP）[6]數據結構用來解決大多數序列模式挖掘算法的性能瓶頸，處理候選序列的組合爆炸問題，通過構造CRMAP 數據結構生成出現在輸入數據庫中有希望的候選對象。

2.2.1 挖掘頻繁1 序列

算法的第一階段用來挖掘頻繁1 序列。每個Mapper1 讀取輸入的序列數據集并識別項目x 是否屬于相應序列的增量數據集（Increment Sequence Dataset, IncSD）[7]，如果項目屬于IncSD，在分布式緩存F 中將項目x 存儲為1，否則存儲為0。Mapper 將項目x 及其在F 中的相應值作為輸出。

Reducer1 將作為輸入，將項目計數和標志變量初始化為0，標志變量用來標識該項是否屬于IncSD。Reducer1 計算與每個項目相關的值的數量，在收到關于項目的值1 之后，Reducer1立即將標志變量更改為1，最后將頻繁1 項集及其對應的計數和標志作為第一階段的輸出，并將其存儲在名為Litems 的分布式緩存文件中。算法流程圖如圖1。

2.2.2 挖掘頻繁k 序列

將第一階段輸出的原始數據集中的頻繁1 項集、最小支持計數和標志作為第二階段的輸入，Mapper2 創造增量并集和構造CRMAP 數據結構，使用早期修剪屬性進行后向挖掘，最后使用Reducer2 挖掘頻繁k 序列。具體流程圖如圖2 所示。

3 實驗過程

3.1 數據收集

手機APP 數據收集有兩種思路，一是抓包，二是HOOK。本文使用的是第二種。

HOOK 是一種通過操作系統內核的技術，安卓系統是開源的，可以借助如Xposed 框架修改內核，實現所需功能。Xposed 是可以在不修改任何其他開發者開發的應用（包括系統服務）的情況下，改變程序運行的一個開源框架服務。通過它進行編碼，可以自動化的控制手機APP。Xposed 每走一步，APP 與服務端交互的數據，均可獲取下來。這種方式廣泛用于一些成熟的APP。

3.2 數據預處理

在數據挖掘之前，使用了數據清理，數據集成，數據變換等技術進行預處理。

數據清理多采用格式標準化，清除異常數據和重復數據，糾正錯誤。數據集成將多個數據源中的數據結合起來并統一存儲，建立數據倉庫。并通過平滑聚集，數據概化，規范化等方將數據轉換成適用于數據挖掘的形式。

3.3 算法實現和比較

本實驗在Hadoop 集群上進行，具有一個主節點和八個數據節點，配置的硬件環境為：CPU2.5GHz/6-Core 處理器和16GB 內存。每個節點都運行在裝有Hadoop 1.2.1 的CentOS 6.5 服務器上，所有算法均使用JDK 1.8.0_31 實現。

采用HOOK 技術獲得一個模擬數據集，獲取了208 個用戶的10 天之內使用APP 的4731 個不同的序列項目。

圖3 給出了本文所提出的算法與SPAMC-UDLT[8]算法最在本數據集上的性能評估。可以看出，由于本文算法通過簡單地將末端投影和SD 投影的大小相加來計算支持計數，其執行時間隨著最小支持度的增加而減少，在時間上優于SPAMC-UDLT 算法，并且，使用CRMAP 數據結構的新的候選生成減少了搜索空間的大小，在后向挖掘期間應用的早期修剪屬性在很大程度上減少了錯誤候選的數量。

4 結語

從上述實驗可見上述后向增量序列模式挖掘算法能夠提高數據挖掘算法的效率。將此算法應用在推薦算法中，能在一定程度上提高推薦的效率和準確度。但是，本算法的實驗是基于模擬數據的，數據量也相對較小，后續研究將試圖對實際移動運營商數據進行分析，加大數據量規模進行測試。