基于LDA主題模型的移動應用相似度構建方法

褚 征,于 炯,2,王佳玉,王躍飛,2

1.新疆大學 軟件學院,烏魯木齊 830008; 2.新疆大學 信息科學與工程學院,烏魯木齊 830046)(*通信作者電子郵箱yujiong@ xju. edu.cn)

基于LDA主題模型的移動應用相似度構建方法

褚 征1,于 炯1,2*,王佳玉1,王躍飛1,2

1.新疆大學 軟件學院,烏魯木齊 830008; 2.新疆大學 信息科學與工程學院,烏魯木齊 830046)(*通信作者電子郵箱yujiong@ xju. edu.cn)

隨著移動互聯網的快速發展,如何從大量的移動應用中抽取有效的描述信息繼而為移動用戶提供有效準確的推薦策略變得尤為迫切。目前,移動應用市場對應用的推薦策略相對傳統,大多是根據應用的單一屬性進行推薦,如下載量、應用名稱、應用分類等。針對推薦粒度過粗和推薦不準確的問題,提出了一種基于潛在狄利克雷分布(LDA)主題模型的移動應用相似度構建方法。該方法從應用的標簽入手,構造應用的主題模型分布矩陣,利用該主題分布矩陣構建移動應用的相似度矩陣,同時提出了將移動應用相似度矩陣轉化為可行的存儲結構的方法。實驗結果表明該方法是有效的,相比現有的360應用市場推薦的應用其相似度提升130%。該方法解決了移動應用推薦過程中推薦粒度過粗的問題,可使推薦結果更加準確。

相似度矩陣;主題模型;隱含信息;應用推薦;標簽

0 引言

隨著互聯網和移動互聯網技術的飛速發展,全球的移動設備數量也在急速上升。根據來自iGR2015年的調查報告顯示,到2019年全球移動設備的總數將會從2014年的69億增加到95億,即2015年的全球移動設備普及率為96.4%,到2019年將達到125%的普及率。當前的移動設備高普及率意味著全球中的每個人能都擁有一個移動設備，每個移動設備中一般會安裝了幾個到幾十個的應用，而這些海量的移動應用散布在各個應用市場。僅360手機助手的應用總量就有11萬多項,而且這些應用還在不斷地增加。

有些應用的名稱從總體上概括了一個應用的主要內容,但是有時即使知道應用的名稱也不知道該應用的具體作用。應用介紹具有時效性，而且應用介紹不能全面客觀地描述應用的特征,它具有一定的廣告內容。應用標簽則能夠相對客觀準確地描述應用的特征，這些標簽很好地在細粒度范圍內刻畫了該應用的特征。

主題模型(Topic Model)[1]是一種概率產生式的模型(Generative Model),同時也是一種層次型的貝葉斯模型，其在自然語言處理、機器學習等領域具有廣泛的應用。由于隱含主題具有很強的抽象性,所以人們理解這些主題將具有很大的挑戰性。通過構建移動應用相似度矩陣,可以對當前移動應用市場中的移動應用建立全面的相似度關系,這些相似度關系不僅可以作為各種推薦策略的基礎內容之一,同時也可以使用構建好的相似度關系來作基于內容的推薦策略。

本文通過潛在狄利克雷分布(Latent Dirichlet Allocation, LDA)模型對移動應用標簽進行分析,抽取出隱含在應用標簽背后的潛在主題,構建出移動應用的主題矩陣。并通過應用的主題矩陣計算出應用主題相似度矩陣,最后還提出了將應用相似度轉化為鏈表的存儲結構的方法。

1 相關工作

本文可以看作是以移動應用為對象,利用LDA主題模型對應用隱含信息進行深層次挖掘,融合移動應用細粒度的描述信息(應用標簽)、LDA主題模型和移動應用推薦三者的研究。

1.1 移動應用的特征表示

經過仔細研究國內較大的移動應用市場(如360手機助手、豌豆夾、小米應用商店等)中的應用,發現移動應用的分類、描述和推薦都存在較大的問題。應用的描述中包含了基本信息和更新內容,但是這些內容大多是以廣告效果為導向,為了更好地吸引用戶的眼球,在內容中主要是新版應用的更新信息，同時應用截圖又不能很方便地提取出應用的特征。頁面中的應用標簽則能夠很好地展現移動應用的特點,故而可以用應用的標簽來表示移動應用的特征。

1.2 主題模型

近幾年,很多需要大規模文本分析的領域都成功地應用了主題模型,包括自然語言處理、文本分析[2-5]、數據挖掘、信息檢索、新聞分類[6]、商業智能[7]、微博可視化[8]、聚類算法[9-10]等領域。Salton等[5]提出的向量空間模型(Vector Space Model, VSM)是較早的文本數據挖掘算法。后來,Deerwester等[11]提出了一種新的潛在語義分析(Latent Semantic Analysis,LSA)方法,它是一種基于矩陣模型挖掘文本主題的思想。LSA利用奇異值分解(Singular Value Decomposition, SVD)的降維方法來對文檔的潛在結構(語義結構)進行挖掘, 此方法的優點是可以在較低維的語義空間中進行查詢并進行相關性分析, 挖掘出隱含在文檔中的語義相關性。主題模型中具代表性的是在1999年Hofmann等[12]提出的基于概率潛在語義分析(Probabilistic Latent Semantic Analysis,PLSA)模型和2003年Blei等[13]提出的LDA模型。概率潛在語義分析模型是基于雙模式和共現的數據分析方法延伸的經典的統計學方法。概率潛在語義分析模型用統計學的角度看待問題,它的概率變種有著巨大的影響；而LDA模型是一種文檔主題生成模型。LDA模型是一種非監督的機器學習技術,只要是用來識別大規模文檔集或者語料庫中潛在的主題信息。采用詞袋的方法,將每一篇文檔視為一個詞頻向量,從而將文本信息轉化為易于建模的數字信息。此外,詞袋模型中又不考慮詞和詞的順序,這樣就降低了需要解決的問題的復雜性。

1.3 推薦策略

按照所使用的數據進行分類[14],推薦策略可以分為協同過濾[15-16]、內容過濾[17-18]、社會化推薦等策略。Massa等[19-20]研究的是利用信任關系來改進協同過濾的方法。Ma等[21]研究的是一種新的基于矩陣分解的社會化推薦方法,它們利用一個共享的低維的潛在的用戶特征矩陣,將用戶間的信任關系網絡和評分矩陣結合在了一起。但是在移動應用市場中,推薦算法的應用相對不足和缺乏，而移動應用相似度又是研究應用推薦算法的內容之一。

2 移動應用的LDA主題提取

本章研究的主要內容是利用LDA主題模型挖掘出移動應用背后的潛在主題信息,在潛在主題信息的基礎上對移動應用構建主題分布矩陣。基于這個主要目標,確定了該研究內容的主要步驟：1)數據搜集,此步驟主要從移動應用市場抓取大量的應用信息,包含應用超鏈接、應用名稱、應用描述、應用標簽等信息。2)數據預處理,對步驟1)中搜集到的數據進行分析,去除一些抓取失敗的信息,將雜亂的數據標準化，同時也將沒有標簽的應用數據去除。3)訓練LDA主題模型,將步驟2)處理之后的數據輸入到LDA主題模型中,同時設置好模型參數進行模型訓練(本文使用Python中的LDA模型進行訓練)。4)輸出LDA主題,將數據輸入到訓練好的模型進行測試,然后將所有的移動應用構建出主題并輸出。5)優化LDA模型,觀測和分析移動應用的主題分布矩陣,發現不足并優化模型參數,重復步驟3)和步驟4),直到步驟4)中輸出的每個LDA主題標簽能夠明顯地表達出相同的主題。6)輸出移動應用LDA主題分布矩陣,在最終優化好的模型中測試數據并輸出應用的主題分布矩陣。以上描述的研究步驟如圖1所示。

圖1 移動應用構建主題分布矩陣過程

2.1 問題分析

由于移動互聯網的廣泛普及,移動設備的數量也隨之增多。每個移動設備都會或多或少地安裝一些移動應用。雖然當前的移動應用數量非常多(僅360手機助手中的移動應用就有12萬之多),但是應用市場中對應用的分類卻相對較少,與移動應用的數量不成匹配。在360手機助手市場中軟件的分類僅有13個,在游戲應用分類中則更少。所以,針對移動應用市場中的應用進行更多的和更小粒度的研究是必要的。

在應用的研究中選擇哪些屬性作為特征是很重要的。在移動應用市場中,應用的描述信息相對較少。應用介紹信息帶有太多的廣告成分,對應用的描述不具有客觀性。用戶對應用的評論則相對離散。此外,應用的評論信息還具有太多的噪聲,而選擇應用標簽則能夠比較客觀地描述應用的特征。

由于沒有開源的應用數據集,加上應用數量較多,這給研究移動應用帶來了較大的困難。通過長時間的爬蟲爬取網絡上的應用數據,很有可能造成惡意網絡攻擊的情況。此外,爬取的數據會存在很多的無用數據,這給數據處理也帶來了較大的困難。

在數據預處理階段,要從大量的數據中去除無用信息,然后對有用的應用信息進行標準化。如將爬取的網頁數據進行頁面分析,然后去除網頁標簽,再整理成適合LDA模型輸入的格式,最后還要去除無用數據等。

2.2 LDA主題模型的建立

2.2.1 LDA模型

LDA模型是當前文本表示方法的研究內容之一。它是一種產生式的主題模型,不僅在文本研究領域應用,還在其他一些領域內成功地應用。LDA是一個三層的貝葉斯網絡,也是一個多層的產生式全概率生成模型。LDA模型包含三層結構,分別是文檔、主題和詞,對應于本文的移動應用數據集即為移動應用、主題和標簽三層,如圖2所示。

圖2 LDA模型隱含主題拓撲結構

LDA主題模型是一種典型的有向概率圖的模型[22]。在一個給定的文檔數據集合中,LDA模型將每個文檔表示成主題,每個主題又表示成詞。從文檔到主題服從多項式分布,從主題到詞也服從多項式分布。在LDA模型中,所有的文檔都共享所有的主題,但是每個文檔都有一個具體的主題分布。針對文本數據集進行建模的方法[23], 如圖3所示。

圖3 LDA模型盤子表示

將移動應用數據集看作是文檔集合,每一個應用看作為一個文檔,應用的標簽看作是文檔中的詞。圖3中：α和β是應用層的兩個參數(也即文檔層的兩個參數)，α代表應用(文檔)集中隱含主題之間的強弱,β則代表了隱含主題的概率分布；φ代表主題下的標簽(詞)的概率分布；θ代表應用(文檔)中各個隱含主題的比重；z代表應用(文檔)在每個隱含主題中每個標簽(詞)分布的比重；w是應用(文檔)中的標簽(詞)向量；N為應用集合(文檔集合)中應用(文檔)的個數；D代表應用的標簽總數。

2.2.2 構建應用標簽的詞袋模型

應用標簽對應LDA主題模型中的單詞。在輸入LDA模型之前將移動應用名稱和標簽整理成統一格式的文本。此外由于應用標簽是移動應用的客觀特征,同時應用的名稱也在更高程度上描述了應用的信息。所以,本文將移動應用的標簽和應用的名稱都看作成LDA的單詞,從而構建出詞袋模型,表1例舉了4個移動應用標簽的詞袋模型。

表1 移動應用標簽的詞袋模型

2.2.3 移動應用中的LDA模型

一個移動應用通常包含幾個或者多個隱含主題,而應用中的特定標簽構成了這些隱含的主題。在本文的移動應用處理中,應用的潛在主題是應用標簽的概率分布,而移動應用又是潛在主題的隨機混合。

2.2.4Gibbs抽樣

在構建LDA模型過程中,模型的參數估計是必不可少的。常用的估計方法主要是變分貝葉斯推理、期望傳播算法、CollapsedGibbs抽樣等方法。相比其他抽樣方法,Gibbs抽樣比較容易理解，并且實現起來相對簡單，最重要的是Gibbs抽樣方法比較適合大規模數據集抽樣主題,所以本文也采用了當前流行的Gibbs抽樣方法[24]為LDA模型的抽樣算法。

Gibbs抽樣算法可以看作是移動應用生成的一個逆向過程。換句話說就是在已知應用數據集的情況下,通過參數聚集得到參數值。根據圖3可以計算出一個移動應用的概率值,如式(1)所示:

P(w|α,β)=

CollapsedGibbs抽樣方法中的Collpased所描述的是一種通過積分的形式避免了實際待估參數,轉而對每一個主題進行采樣的方法。一個標簽的主題一旦確定,參數便可以在統計頻次之后計算出。故而參數估計問題就變成了計算標簽序列下主題序列的條件概率,如式(2)所示:

P(zi=k|z,w)=

(2)

其中：zi是第i個標簽對應的主題變量；i代表不包含其中的第i項；是k主題中出現標簽t的次數；βt是標簽項t的Dirichlet先驗；代表應用m出現出題k的次數；αk是主題k的Dirichlet先驗。若取得每個標簽的主題標號,則參數的計算公式可以由式(3)～(4)取得:

(3)

(4)

其中：φk,t是主題k中標簽t的概率；θm,k是應用m中主題k的概率。

2.3 應用隱含主題矩陣構建

通過連續使用式(5),可以計算出應用數據集中每個應用在每個主題上的概率分布,繼而構建出對應的Y矩陣:

(5)

其中：N是應用數據集中應用的個數；T是應用數據集中所有標簽構建的主題個數。Y矩陣中的每一項都是由式(4)計算得到。Y矩陣實際上是一個稀疏矩陣,這是因為每個應用只包含了所有主題中的幾個主題,所以Y矩陣中的每一行都有很多的零值項。

2.4 問題描述

應用市場的推薦過程為:當用戶瀏覽應用A的詳情頁面時,在A頁面中推薦其他的應用。如，推薦應用1,推薦應用2,…,推薦應用q(q為指定的變量)。模型示例如表2所示。

表2 應用市場推薦模型

在應用市場推薦模型表中,推薦應用1與當前應用的相似度要比推薦應用2與當前應用的相似度高；推薦應用2與當前應用的相似度要比推薦應用3與當前應用的相似度高；之后的推薦應用也遵循此推薦原則。

本文提出了基于LDA主題模型的移動應用的相似度構建方法。該方法利用應用在隱含主題上的概率分布計算應用相似度矩陣,然后將相似度矩陣轉化為可實際應用的推薦模型存儲結構。

2.5 移動應用相似度矩陣構建

應用的相似度計算實際上是利用了式(6)的結果進行處理。應用的主題分布是應用空間的映射,利用將移動應用表示成主題的概率分布,計算應用數據集中兩個應用之間的相似度便轉化為計算兩個應用對應的主題概率分布。如計算應用數據集中應用1和應用2之間的相似度,便可以利用式(6)中的第一行概率分布和第二行的概率分布進行計算。這樣便計算出了兩個應用之間的相似度。

應用的相似度計算依據應用隱含主題矩陣Y,利用簡單易行的歐氏距離計算應用數據集中兩兩應用之間的相似度。歐氏距離計算公式為:

di, j=

其中：di, j代表應用i與應用j之間的相似度；θi,1是主題矩陣中第i個應用(行)中占第一個主題的概率值；θj,1是主題矩陣中第i個應用(行)中占第一個主題的概率值；T為主題個數,也即主題矩陣的列數。

通過循環使用式(6)便可計算出應用數據集中兩兩應用之間在主題分布上的相似度并構建出應用的相似度矩陣B：

(7)

其中：矩陣B是一個M×N的矩陣,M是應用數據集中應用的個數,N是主題數目(即每個應用包含的隱含主題個數)。在計算相似度時,矩陣主對角線上的數值都是0。因為主對角線的值是應用與自己之間的相似度,所以這個數值肯定是0。在構建時需要對矩陣主對角線上的項目賦予一個較大的數值,而且這個數據要比矩陣中的所有數值都大。

2.6 生成相似度矩陣算法

根據移動應用相似度矩陣構建的過程描述,以下給出了生成相似度矩陣(CreatingSimilarityMatrix,CSM)的算法。

算法1CSM算法。

輸入:移動應用數據集appdataset;標簽字典tagdict。 輸出:相似度矩陣matrix[][]。matrix[][]←null

//初始化相似度矩陣tfidfhead←TfidfMode(appdataset)

//對應用標簽做tfidf操作num_topicst←160

//賦值主題數量lda←LDAModel(tfidf,dict,num_topics)

//訓練LDA模型 Fori=0 toappdataset.len

//遍歷應用數據集合 Forj=1 toappdataset.lenmatrix[i][j]←distance(appdataset[i],appdataset[j])

//計算兩兩應用之間的相似度

max_distance←vmatrix.max()+1

//賦值最大值,將應用與自己之間的相似度設置為最小

Fori=0 toappdataset.len

//遍歷矩陣對角線,賦值為最大值,使其相似度最低matrix[i][j]←max_distance

returnmaxtrix

2.7 相似度矩陣轉化為鏈表結構

為將科學理論級別的應用矩陣相似度轉化為工業級別簡單易行的存儲結構和過程，本文提出了一種利用縱向鏈表和橫向鏈表的存儲結構來實現。

應用市場的應用相似度儲結構如圖4所示。

相似度矩陣轉化為存儲結構的轉化過程如下所述:

1)獲取移動應用相似度矩陣。

2)取得第i(i為相似度矩陣中的行標,1≤i≤N)個應用,在縱向列表尾部添加一個新節點。

3)在相似度中的第i行尋找最大前q個最大值(取得的最大值按照從大到小排列),分別是L1,L2,…,Lq。在當前縱向鏈表中新建q個橫向鏈表并按照從大到小的順序將L1,L2,…,Lq數據寫入橫向鏈表的節點中。q的數據是人為指定的,這里不對此值固定,目的是為了可以滿足不同的需求,在本文中q代表每個應用詳情頁面中推薦其他應用的個數。

4)重復步驟2)～3),直到縱向鏈表中的數據節點數量等于應用數據集和中應用的個數N。

使用該存儲結構的優點:

1)簡單。相對于復雜的矩陣,采用橫向鏈表和縱向鏈表更加直觀和容易理解。

2)快速。此結構可以快速訪問縱向鏈表并加載出該縱向鏈表節點對應的橫向鏈表。若采用矩陣直接計算,在每次計算過程都要將整個矩陣全部加載到內存，故而采用矩陣的形式會比該結構速度慢。

3)可擴展。若應用數量增加,可以在縱向鏈表尾部繼續增加節點;若推薦數據改變,可以在橫向鏈表中動態調整。如果采用矩陣的方式則需要重新構建整個矩陣。

4)離線與在線相結合。離線的是矩陣,在線的是該存儲結構。可以離線處理復雜的矩陣而不影響當前的應用服務,在必要時把離線處理好的矩陣結構重新更新到該存儲結構，保證了當前在線服務的正常運行。

2.8 相似度矩陣轉化為鏈表算法

針對相似度矩陣轉化為鏈表,本文給出了轉化算法SM2LL(SimilarityMatrixtoLinkedList)的偽代碼如算法2所示。

算法2SM2LL算法。

輸入:相似度矩陣matrix[][];推薦應用數量q。 輸出:鏈表head。head←null

//初始化縱向鏈表頭指針h_t←head

//初始化縱向鏈表臨時節點v_t←null

//初始化橫向鏈表臨時節點 Fori=0 tomatrix.len

//遍歷矩陣行h_linkedlist←null

//初始化縱向鏈表節點h_t.h_next←h_linkedlist

//建立縱向鏈表前驅關系h_Linklist.spp_id←matrix[i][0]

//復制當前縱向鏈app_idv_linkedlist←null

//初始化橫向鏈表節點v_t←null

//初始化橫向鏈表臨時節點matrix[i].sort()

//排序矩陣當前行的相似度數據(從小到大) Forj=1 toq+1

//遍歷前q個相似度最大的矩陣項目v_linklist.app_id←matrix[i][j]

//賦值當前橫向鏈表節點app_idv_t.nxet←v_linkedlist

// 構建橫向鏈表前驅關系h_t←linkedlist

//縱向鏈表臨時節點后移

returnhead

3 實驗與分析

本文實驗數據是從360應用市場爬取的約23 000條數據的應用數據集。

3.1LDA模型參數選擇

在訓練LDA主題模型時需要主題數目、樣本迭代次數、字典、超參數α、超參數β等參數。本文實驗過程中使用了自定義的詞典、160個主題數目,其他的參數則使用LDA模型默認值。

3.1.1 分詞工具選擇

本文實驗的分詞工具采用的是開源結巴分詞工具。結巴分詞是當前針對中文分詞較好的工具之一，它支持三種分詞模式,分別是精確模式、全模式和搜索引擎模式，本文采用的是精確模式。此外結巴分詞還支持繁體分詞和自定義詞典功能。本文在構建LDA模型時就為所有的移動應用標簽建立了自定義詞典。

3.1.2LDA模型主題數選擇

主題數是指整個移動應用數據集中包含的隱含主題個數，是LDA模型中必須給出的參數。從某種程度上講,主題數的不同會影響到應用的分布。在LDA主題模型建模過程中,參數估計是用Gibbs抽樣算法。在設置主題數目的過程中,實驗分別測試了主題數目分別為50、150、200、250不同的數值，然后在這些不同的主題數目下觀測移動應用的分布圖。結果顯示：主題數目為150下觀測到移動應用沒有主題數為0,也就是移動數據集中每個應用都有至少一個主題；而在主題數目為200時,有很小一部分移動應用是沒有隱含主題的,所以就在主題數為150～200重新尋找合適的主題數目。然后又進行了主題數目為160到190的測試，發現主題數目設置為169時，移動應用的分布更加合適。

3.2 主題分布

圖5是LDA模型在訓練過程中設置第一組不同的主題數目下的移動應用分布柱狀圖,如圖5所示。

從圖5可以很容易地看出,每個移動應用中只會出現一小部分主題。所以,主題模型是一個稀疏的模型,即便每個應用中有很多潛在主題,但是也只有一小部分會被利用。其中主題數為150時,在移動應用數據集中所有的應用都至少有一個隱含主題,但是當主題數為200時,有一小部分移動應用是沒有隱含主題。這里的結果不符合現實際,所以繼續在主題數為150～200探索合適的主題數設置，分別設置主題數為160、170、180和190,實驗得出對應的應用主題數分布,如圖6所示。

從圖6可看出,LDA主題模型中主題數設置為160相對合適。因為在主題數為160時,任何一個移動應用都至少包含一個隱含主題；當主題數增大到170時,就會有很小一部分應用是沒有隱含主題的。在主題數為160時,大約有11 124個應用中包含了1個主題,大多數文檔涵蓋了2～5個主題,還有一部分應用有6～9個主題，基本上沒有應用會擁有10個以上的主題(包含是10個主題)。平均下來每個移動應用只涉及1.7個主題,其中99.4%的移動應用設計的主題數目小于等于5。

圖5 不同主題數(間隔為50)下的移動應用分布

圖6 不同主題數(間隔為10)下的移動應用分布

通過LDA模型訓練后得到了160個主題,每個主題都包含了10個應用標簽。在這里列取了其中10個具有典型意義的主題和每個主題最具代表性的前5個標簽(按照每個標簽在當前隱含主題中的概率從大到下的排列順序),如表3所示。

表3 隱含主題標簽構成

這里并沒有將主題進行明確的命名,這是因為LDA模型訓練出來的主題是具有隱含性質的，有時可以很直接地從這些應用標簽中快速地反映出當前主題就是生活中很明確的含義，但有時LDA生成的主題也會很晦澀難懂。如果發現這種情況，就需要迭代地調整模型參數(主題個數)以達到較好的效果。

3.3 推薦評價

推薦算法常用的評價方法主要有平均絕對誤差(MeanAbsoluteError,MAE)、均方根誤差(RootMeanSquareError,RMSE)、 準確率(Precision)、召回率(Recall)、綜合評價指標(F1-measure)以及平均精度均值(Mean Average Precision, MAP)[25-26]。

MAE和RMSE是用來評價預測評分準確性的標準,反映了算法的預測評分和用戶實際評分的相似程度,其最終的值越小表示推薦的效果越好。定義如式(8)～(9)所示:

(8)

(9)

指標precision、recall、F1-measure和MAP是對推薦算法在分類準確率上進行評價的標準,它們所反映的是推薦算法對分類預測的準確程度。這四個評價指標相對比較適合具有明顯二分喜好的用戶。定義如式(10)～(13)所示:

(10)

其中：Nt, p代表應用推薦列表中用戶喜歡的應用數量,Q則表示推薦應用的數量。

(11)

其中：Nt, p同樣代表應用推薦列表中用戶喜歡的應用數量;Bu則表示擁護u喜愛的推薦應用數量。公式所表達的內涵是用戶所喜歡的推薦對象能被推薦的概率。

F1=(2×precision×recall)/(precision+recall)

(12)

式(12)是對式(10)和式(11)的融合。F1-measure同時考慮了precision和recall兩個評價標準,所以它可以比較全面地評價推薦算法的優劣。

(13)

其中：mu表示第u次推薦時用戶喜愛的推薦數量;P(Luq)則代表第u次推薦時推薦列表前q個推薦應用中用戶喜愛的推薦應用數量和位置q的比值。

為了更好地提高這些評價指標，需要推薦出相似度更高的對象，對象之間的相似度計算則必不可少。為此,提出了移動應用標簽相似度計算公式,如式(14)所示:

(14)

其中：N代表移動應用總量;L代表根據當前移動應用a推薦出的應用列表。為了計算推薦出來的移動應用與當前的移動應用之間標簽的相似度,需要利用c(a)計算推薦列表中的總標簽數,同時利用m(a)來計算當前移動應用a與推薦列表中的標簽匹配相同的標簽數,最后通過累加和除以N計算數據集總體的相似度。需要注意此處的數值越大代表相似度越高。通過式(14)計算出的不同推薦數量下的應用相似度結果,如圖7所示。從圖7中可以看出LDA主題模型在不同推薦數量上的相似度。隨著推薦數量的增加,推薦出的應用與當前應用的相似度不斷下降；但是提升了推薦的多樣性。

為了使推薦出的移動應用不僅具有較高的相似度，還要具有多樣性，故而需要選擇合適的推薦數量。當推薦數量為6時,使用LDA構建移動應用相似度為0.129，當前移動應用市場推薦的應用相似度為0.056。可看出，使用LDA主題模型構建移動相似度比當前移動應用市場推薦的應用相似度高130%。

圖7 不同推薦數量下的LDA構建相似度

4 結語

本文提出了一個基于LDA主題模型的移動應用相似度構建方法。該方法以移動應用市場中應用的標簽為特征來描述應用,利用LDA隱含主題模型對應用進行研究,實現了在應用標簽級別的小粒度的相似度構建方法。

利用移動應用數據集的隱含主題分布,構建了應用主題分布矩陣,進而構建了應用相似度矩陣,并將這種基于應用隱含主題的相似度矩陣簡單地應用到了基于內容的推薦策略。這種相似度的推薦策略不僅可以應用在移動應用中,也可以應用在其他領域中，如基于文本內容的推薦、圖像分類[27]等。

此外,由于每一個隱含主題都具有隨機性與不確定性,在LDA主題模型訓練過程中將導致輸出的隱含主題難于理解,此問題有待研究;在訓練LDA主題模型時,模型的參數還需探索與優化,從而獲得最佳的結果;在構建相似度矩陣的過程中,最終輸出的相似度矩陣有待優化與調整;在本文實驗數據集規模下,輸出的相似度矩陣保存為文本文件后約為10GB,這也說明相似度矩陣隨著應用數量的增加會呈現平方級別增長趨勢,這也將是今后的一個主要研究內容;應用的推薦策略在轉化過程中僅使用了一種縱向和橫向鏈表相結合的存儲結構,這種結構有著簡單、快速、可擴展、離線和在線相結合的優點,但還可再完善與提高,所以此內容也是今后需研究的內容之一。

)

[1]BLEIDM.Probabilistictopicmodels[J].CommunicationsoftheACM, 2012, 55(4): 77-84.

[2] 王李冬, 魏寶剛, 袁杰. 基于概率主題模型的文檔聚類[J]. 電子學報, 2012, 40(11):2346-2350.(WANGLD,WEIBG,YUANJ.Documentclusteringbasedonprobabilistictopicmodel[J].ActaElectronicaSinica, 2012, 40(11):2346-2350.)

[3]AL-SALEMIB,ABAZIZMJ,NOAHSA.LDA-AdaBoost.MH:acceleratedAdaBoost.MHbasedonlatentDirichletallocationfortextcategorization[J].JournalofInformationScience, 2015, 41(1): 27-40.

[4]FOULDSJ,BOYLESL,DUBOISC,etal.StochasticcollapsedvariationalBayesianinferenceforlatentDirichletallocation[C]//KDD2013:Proceedingsofthe19thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2013: 446-454.

[5]SALTONG,WONGA,YANGCS.Avectorspacemodelforautomaticindexing[J].CommunicationsoftheACM, 1975, 18(11): 613-620.

[6]LEEY-S,LOR,CHENC-Y,etal.NewstopicscategorizationusinglatentDirichletallocationandsparserepresentationclassifier[C]//Proceedingsofthe2015IEEEInternationalConferenceonConsumerElectronics.Piscataway,NJ:IEEE, 2015: 136-137.

[7]MOROS,CORTEZP,RITAP.Businessintelligenceinbanking:aliteratureanalysisfrom2002to2013usingtextminingandlatentDirichletallocation[J].ExpertSystemswithApplications, 2015, 42(3): 1314-1324.

[8]ANOOPVS,PREMSANKARC,ASHARAFS,etal.Generatingandvisualizingtopichierarchiesfrommicroblogs:aniterativelatentDirichletallocationapproach[C]//Proceedingsofthe2015InternationalConferenceonAdvancesinComputing,CommunicationsandInformatics.Piscataway,NJ:IEEE, 2015: 824-828.

[9]LIUX,ZENGJ,YANGX,etal.ScalableparallelEMalgorithmsforlatentDirichletallocationinmulti-coresystems[C]//WWW2015:Proceedingsofthe24thInternationalConferenceonWorldWideWeb.RepublicandCantonofGeneva,Switzerland:InternationalWorldWideWebConferencesSteeringCommittee, 2015: 669-679.

[10]DEEPAKNA,HARIHARANR,SINHAUN.ClusterbasedhumanactionrecognitionusinglatentDirichletallocation[C]//Proceedingsofthe2013InternationalConferenceonCircuits,ControlsandCommunications.Piscataway,NJ:IEEE, 2013: 1-4.

[11]DEERWESTERS,DUMAISST,FURNASGW,etal.Indexingbylatentsemanticanalysis[J].JournaloftheAmericanSocietyforInformationScience, 1990, 41(6): 391-407.

[12]HOFMANNT.Probabilisticlatentsemanticindexing[C]//SIGIR1999:Proceedingsofthe22ndAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.NewYork:ACM, 1999: 50-57.

[13]BLEIDM,NGAY,JORDANMI.LatentDirichletallocation[J].TheJournalofMachineLearningResearch, 2003, 3: 993-1022.

[14] 項亮. 推薦系統實戰[M]. 北京:人民郵電出版社, 2012: 1-2.(XIANGL.RecommendationinPractice[M].Beijing:Posts&TelecomPress, 2012: 1-2.)

[15]BELLR,KORENY,VOLINSKYC.Modelingrelationshipsatmultiplescalestoimproveaccuracyoflargerecommendersystems[C]//Proceedingsofthe13thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2007: 95-104.

[16]ONUMAK,TONGH,FALOUTSOSC.TANGENT:anovel, “surpriseme”,recommendationalgorithm[C]//Proceedingsofthe15thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2009: 657-666.

[17]MUSTOC.Enhancedvectorspacemodelsforcontent-basedrecommendersystems[C]//ProceedingsoftheFourthACMConferenceonRecommenderSystems.NewYork:ACM, 2010: 361-364.

[18]SONGY,ZHUANGZ,LIH,etal.Real-timeautomatictagrecommendation[C]//Proceedingsofthe31stAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.NewYork:ACM, 2008: 515-522.

[19]MASSAP,AVESANIP.Trust-awarecollaborativefilteringforrecommendersystems[C]//ProceedingsoftheOTMConfederatedInternationalConferences,CoopIS,DOA,andODBASE2004,LNCS3290.Berlin:Springer, 2004: 492-508.

[20]MASSAP,AVESANIP.Trust-awarerecommendersystems[C]//Proceedingsofthe2007ACMConferenceonRecommenderSystems.NewYork:ACM, 2007: 17-24.

[21]MAH,YANGH,LYUMR,etal.SoRec:socialrecommendationusingprobabilisticmatrixfactorization[C]//Proceedingsofthe17thACMConferenceonInformationandKnowledgeManagement.NewYork:ACM, 2008: 931-940.

[22]DONGX,WEIL,ZHUH,etal.Anefficientprivacy-preservingdata-forwardingschemeforservice-orientedvehicularAdHocnetworks[J].IEEETransactionsonVehicularTechnology, 2011, 60(2): 580-591.

[23]WEIX,CROFTWB.LDA-baseddocumentmodelsforAdHocretrieval[C]//Proceedingsofthe29thAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.NewYork:ACM, 2006: 178-185.

[24]HEB,AGRAWALDP.Anidentity-basedauthenticationandkeyestablishmentschemeformulti-operatormaintainedwirelessmeshnetworks[C]//Proceedingsofthe7thIEEEInternationalConferenceonMobileAd-HocandSensorSystems.Piscataway,NJ:IEEE, 2010: 71-78.

[25] 朱郁筱, 呂琳援. 推薦系統評價指標綜述[J]. 電子科技大學學報, 2012, 41(2):164-175.(ZHUYX,LYULY.Evaluationmetricsforrecommendersystems[J].JournalofUniversityofElectronicScienceandTechnologyofChina, 2012, 41(2): 164-175.)

[26]MANNINGCD,RAGHAVANP,SCHUTZEH.IntroductiontoInformationRetrieval[M].Cambridge:CambridgeUniversityPress, 2008:76-80.

[27]LIZ,TIANW,LIY,etal.Amoreeffectivemethodforimagerepresentation:topicmodelbasedonlatentDirichletallocation[C]//Proceedingsofthe2015 14thInternationalConferenceonComputer-AidedDesignandComputerGraphics.Piscataway,NJ:IEEE, 2015: 143-148.

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61462079,61262088,61562086,61363083).

CHU Zheng, born in 1991, M. S. candidate. His research interests include data mining, memory calculation, green computing.

YU Jiong, born in 1964, Ph. D., professor. His research interests include network security, grid computing, distributed computing.

WANG Jiayu, born in 1991, M. S. candidate. Her research interests include data mining, mobile computing.

WANG Yuefei, born in 1991, Ph. D. candidate. His research interests include data mining, memory computing, green computing.

Construction method of mobile application similarity matrix based on latent Dirichlet allocation topic model

CHU Zheng1,2, YU Jiong1,2*, WANG Jiayu1, WANG Yuefei1,2

(1.School of Software, Xinjiang University, Urumqi Xinjiang 830008, China;2.School of Information Science and Engineering, Xinjiang University, Urumqi Xinjiang 830046, China)

With the rapid development of mobile Internet, how to extract effective description information from a large number of mobile applications and then provide effective and accurate recommendation strategies for mobile users becomes urgent. At present, recommendation strategies are relatively traditional, and mostly recommend applications according to the single attribute, such as downloads, application name and application classification. In order to resolve the problem that the granularity of recommended applications is too coarse and the recommendation is not accurate, a mobile application similarity matrix construction method based on Latent Dirichlet Allocation (LDA) was proposed. Started from the application labels, a topic model distribution matrix of mobile applications was constructed, which was utilized to construct mobile application similarity matrix. Meanwhile, a method for converting the mobile application similarity matrix to the viable storage structure was also proposed. Extensive experiments demonstrate the feasibility of the proposed method, and the application similarity achieves 130 percent increasement by the proposed method compared with that by the existing 360 application market. The proposed method solves the problem that the recommended granularity is too coarse in the mobile application recommendation process, so that the recommendation result is more accurate.

similarity matrix; topic model; latent information; application recommendation; label

2016- 09- 26;

2016- 12- 25。

國家自然科學基金資助項目(61462079,61262088,61562086,61363083)。

褚征(1991—),男,河南南陽人,碩士研究生,CCF會員,主要研究方向:數據挖掘、內存計算、綠色計算; 于炯(1964—),男,新疆烏魯木齊人,教授,博士,CCF會員,主要研究方向:網絡安全、網格計算、分布式計算; 王佳玉(1991—),女,黑龍江哈爾濱人,碩士研究生,CCF會員,主要研究方向:數據挖掘、移動計算; 王躍飛(1991—),男,新疆烏魯木齊人,博士研究生,主要研究方向:數據挖掘、內存計算、綠色計算。

1001- 9081(2017)04- 1075- 08

10.11772/j.issn.1001- 9081.2017.04.1075

TP274.2

A