基于關聯規則挖掘的分類隨機游走算法

施海鷹

(上海大學 計算機工程與科學學院,上海 200444)

基于關聯規則挖掘的分類隨機游走算法

施海鷹

(上海大學 計算機工程與科學學院,上海 200444)

隨著互聯網技術的不斷進步和互聯網的飛速發展，人們可以很方便地在互聯網上尋找各種各樣的信息。用戶在尋找他們真正感興趣的信息時會花費大量的時間，從而導致效率不高，這種現象被稱作“信息過載”。推薦系統是解決信息過載問題的一種行之有效的方法。目前，推薦系統中應用最廣泛的兩種推薦技術是基于內容的推薦算法和協同過濾推薦算法，但其不能很好地處理冷啟動和稀疏性問題。為了更好地解決這兩個問題，在對傳統分類隨機游走算法進行改進的基礎上，提出了基于關聯規則挖掘的分類隨機游走算法。該算法利用關聯規則挖掘的特性，挖掘用戶屬性與項目之間的關聯，為新用戶構造初始的評分向量，彌補了經典算法的不足，較好地處理了冷啟動問題。驗證實驗結果表明，該算法具有較好的有效性和精確性。

推薦系統；關聯規則；分類隨機游走算法；信息過載

1 概 述

隨著互聯網的不斷發展，用戶在互聯網上查詢感興趣的信息的效率越來越低，用戶將大量時間花在了瀏覽不相關的信息上。為了解決上述問題，推薦系統應運而生。推薦系統的任務主要是將信息和用戶有效地聯系起來，一方面讓用戶發現自己需要的、感興趣的、有價值的信息；另一方面讓這些信息出現在用戶面前。推薦系統的出現就是為了解決“信息過載”問題[1]，讓用戶在查詢有價值的信息時具有更高的效率。推薦系統已經廣泛應用于各領域，最典型的就是類似于‘亞馬遜’的商業領域[2]。

推薦系統通過分析用戶的歷史興趣和偏好信息，可以在項目空間中確定用戶現在和將來可能會喜歡的項目，進而主動向用戶提供相應的項目推薦服務。推薦系統的優劣很大程度上依靠其采取的推薦算法，不同的推薦技術具有不同的推薦質量，產生的推薦結果也不同。推薦技術可以分為基于內容的推薦[3]、協同過濾[4]、混合式推薦[5]?；趦热莸耐扑]是最早應用的推薦算法，不需要征求用戶的評價意見，而是根據用戶喜歡的商品信息，分析信息的特征，根據這些信息來分析相似性。最早的基于內容的推薦應用于信息檢索中，所以很多與信息檢索相關的技術都可以用于基于內容的推薦中。

協同過濾是推薦系統中最常用也是最成功的推薦算法。協同過濾技術的基本思想是，相似的用戶喜歡的東西也可能是相似的。在現實生活中，如果一個用戶想要讀一本書，往往會選擇和自己品味相近的朋友的推薦。基于內容的推薦算法和協同過濾算法各有各的優缺點，可以通過這兩種推薦技術的組合來實現推薦算法的互補，這就是混合推薦算法。

當一個新的系統上線時，這個系統中并沒有任何用戶對項目的評分信息可以利用，那么協同過濾技術也就無法使用，這就是冷啟動問題[6]。除此之外，當一個新用戶或者新的項目加入系統時，這些項目既沒有得到其他用戶的評分，新用戶也沒有對系統中的其他項目進行過評分，這樣，新項目既不會被推薦出去，同時新用戶也不會得到推薦。新用戶和新項目都面臨著冷啟動的問題。由于基于內容的推薦算法和協同過濾算法無法很好地解決冷啟動問題，研究者們提出了新的算法，例如基于圖的推薦算法[7-8]。

文中研究了Zhang Liyan等提出的分類隨機游走算法[9]，并在此基礎上進行改進，提出了一種新的分類隨機游走算法。首先建立用戶—項目的相關圖，在相關圖上利用基于項目分類的隨機游走不斷迭代計算推薦結果。算法避免了傳統推薦算法的缺點，同時具有較好的推薦效果。

關聯規則挖掘問題是R.Agrawal等于1993年提出的[10]。關聯規則是描述數據庫中一組數據項之間的某種潛在關系的規則，即從數據集中識別出頻繁出現的屬性值集，也稱為頻繁項集[11]，然后再利用這些頻繁集的創建描述關聯規則。關聯規則可以找到數據項中的關聯關系[12]，應用到推薦算法中可以找到新用戶的相關性。

為了克服分類隨機游走算法不能為新用戶進行推薦的缺點[13-14]，將關聯規則算法引入到推薦系統，提出了基于關聯規則挖掘的分類隨機游走算法，較好地解決了冷啟動問題。

2 基于關聯規則挖掘的分類隨機游走算法

2.1相關圖模型

對于給定的數據集D，該推薦算法涉及的相關數據包括用戶集U={u1,u2,…,u|U|}、項目集M={m1,m2,…,m|M|}和用戶對項目的評分ri,j，算法的輸入可以看成是一個用戶—項目矩陣T，矩陣中的元素Ti,j的值為ri,j。

算法第一步是建立一個項目間的相關圖，以此表明各個項目之間的相關性。算法用同時選擇項目mi和項目mj的用戶數量來表示兩個項目間的相關性，即在矩陣T中第i列和第j列的值均不等于0的行的數量。

定義ui,j表示矩陣T中第i列和第j列的值均不等于0的行的數量，當i=j時ui,j=0。由于T中大部分數據都為0，為了減輕計算量，計算時對T中的每一行，將其不為0的提取出來，將其中可能的兩兩組合的ui,j置為1，之后所有行將對應位置的值相加，求得最后所有的ui,j的值。

定義|M|×|M|階的相關矩陣M，其中元素的值計算如下：

基于矩陣M構建相關圖G，在G中，項目mi和項目mj之間存在一條邊(當且僅當Mi,j>0)，邊的權重等于Mi,j。這樣就構建了算法的基本模型—相關圖。相關圖表明了各項目間的關聯度，項目mi和項目mj具有高的關聯度，潛在的原因是它們具有某些相似的特征。

假設用戶-項目矩陣T如下：

則矩陣M為：

根據M構建相關圖G，如圖1所示。

圖1 生成的相關圖

2.2算法描述

算法的基本思想是通過相關圖來預測用戶的喜好，相關圖揭示了項目與項目之間的關聯程度。訓練數據集時，通過給定的用戶-項目評分在相關圖中依靠項目間的連接來傳遞。例如，如果一個項目mi和用戶uj感興趣的多個項目之間都存在關聯，則mi可以作為一個好的推薦結果推薦給用戶uj。如果一個項目是用戶所喜好的，則其一定還與該用戶其他的喜好物品有較高的關聯度?；谶@樣的結論，可以用隨機游走的方法去計算用戶對其他物品的評分。

用戶對某一項目的評分可以從一個項目向該項目鄰近的項目傳遞，不僅僅因為這兩個項目同時出現在一個用戶的喜好項目里的次數多，而且因為兩個項目之間具有某些可見和不可見的相似性。由此定義一個新的概念—分類評分(Categorical Rank，CR),表示在特定分類上的項目評分，而分類隨機游走算法就是迭代計算每個用戶的CR值。

為了計算CR值，先迭代計算矩陣Ruk，具體的迭代公式如下：

(1)

其中，R為|M|×n階矩陣，|M|是項目的總數，n是項目類別的總數，元素Rig表示對于某一用戶，項目mi在類別g上的評分；M為項目相關矩陣；F為|M|×n階的輔助矩陣；I為|M|×n階的矩陣，其元素的值由原始的用戶—項目評分生成；d和α分別為鏈接相關性參數和主題相關性參數，通過實驗分別取0.15和0.1。

式(1)表明，對于某一用戶，項目mi在類別g上的評分由三部分組成：與項目mi所屬類別相同的近鄰項目的評分；與項目mi所屬類別不同的近鄰項目的評分；起始的用戶—項目評分。第一個方程的作用是在開始迭代之前初始化Ruk；第二個方程用來計算矩陣F，Pig表示項目mi屬于類別g的概率，由數據集中給出的項目分類信息可以計算得出；第三個方程中，Iuk中每一個元素的計算公式如下：

(2)

CRuk=Ruk(Profuk)T

(3)

其中，Profuk=RukP，揭示了用戶uk對不同類別項目的興趣。根據式(3)可以計算出用戶uk對所有項目的預測評分，如果一個項目最后的預測評分高，則表示用戶對該項目比其他項目更感興趣，將項目按照最后的預測評分逆序進行排序，把排在前面的項目作為最后的推薦結果推薦給用戶。

2.3改進的FP-Growth算法

分類隨機游走算法的缺點是不能為新用戶進行推薦，為了解決這個問題，需要為新用戶構建一個初始的評分向量，故提出了基于關聯規則的分類隨機游走算法。通過關聯規則找出用戶屬性與項目之間的關聯關系，根據新用戶的屬性給新用戶構建初始的評分向量，對經典關聯規則FP-Growth算法進行了改進。

FP-Growth算法需要掃描事務數據庫，數據集D生成的用戶-項目矩陣T就作為事務數據庫。設定一個最小支持度，對T進行第一次掃描，抽取出那些支持度大于最小支持度的項目和用戶屬性，并記錄其支持度計數(即其出現的次數)，生成候選1-項集，記為L，將其按照支持度大小逆序排序。

第二次掃描T，對它的每一行，選擇該行的頻繁項(項目和用戶屬性)，按照第一步中生成的L的順序進行排序。之后構造FP-tree，設定排序后的頻繁項表為[p|P]，其中p為第一個元素，P為剩余元素組成的表。過程如下：如果節點T有子女N與p是同一個項目，則N的計數加1，否則創建新的節點N，將其計數置為1，鏈接到它的父節點T，并且通過節點鏈結構將其鏈接到具有相同項目的節點，如果P非空，遞歸調用insert_tree(P,Tree)。

建立FP-tree對應的項頭表(item header table)，逆序遍歷項頭表，找出FP-tree中由該節點到根節點的路徑。根據每個頻繁元素對應的條件模式基，生成其對應的條件FP-tree，并刪除樹中節點記數不滿足給定的最小支持度的節點。對于每一棵條件FP-tree，生成所有從根節點到葉子節點的路徑，由路徑中的集合生成其所有非空子集，所有非空子集和每一個候選1-項集中的元素共同構成了原始數據集中的頻繁集，最后生成所有的用戶屬性與項目之間的關聯規則。

運用改進的FP-Growth算法，根據已有的數據集D產生用戶屬性和項目之間的關聯規則之后，對規則R：X?Y中后項Y的每一項計算初始評分，對于Y中沒有的項目，其初始評分設為0，這樣就構成了一個評分向量V；對于Y中有的項目，假設該項目在所有項目中是第i個項目，其初始評分的計算公式如下：

(4)

現有一新用戶uk=uk1,uk2,…,ukL，L為用戶的屬性總數，對于生成的規則集合R={R1,R2,…,R|R|}，其中的任一規則Ri：Xi?Yi，如果Xi包含于用戶uk的屬性集，則將Ri加入到R的子集R'中，這樣R'所有的規則都是前項中的用戶屬性是目標用戶屬性集的子集，即全部是與目標用戶相關的關聯規則，之后依據式(5)計算uk的初始評分向量：

(5)

其中，Vi為R'中第i個規則所生成的評分向量。

式(5)根據R'中所有規則的評分向量的加權平均來生成uk的初始評分向量。有了初始評分向量后，改進的分類隨機游走算法就可以開始為uk進行推薦。

3 算法流程

基于關聯規則挖掘的分類隨機游走算法在第一次運行時，需要進行用戶屬性與項目之間的關聯規則挖掘，之后只需要在一個新用戶對某個項目評分之后，再次進行關聯規則挖掘。

算法首先建立相關圖模型，之后對新用戶進行推薦，需要根據挖掘的所有關聯規則，選出與該用戶相關的關聯規則，對每個關聯規則中的所有項目進行初始評分，最后對所有與用戶屬性相關的關聯規則根據支持度和置信度計算加權平均值，得出為新用戶構建的初始評分向量。將所有項目分類，計算項目類別概率矩陣P，根據式(1)初始化矩陣R，并迭代計算，之后再根據式(3)計算該新用戶的CR值，將CR按照逆序排序，將前幾個項目作為結果推薦給該用戶。至此算法結束，具體流程如圖2所示。

圖2 算法流程圖

4 實驗結果

實驗環境：CPU為Intel(R) Core(TM) i3-2350M CPU @ 2.30 GHz ；內存4 GB；操作系統為Windows 7(32位)；編程語言為JAVA(JDK1.6)。

實驗使用了三個數據集，分別是MovieLens、Anonymous Microsoft Web Data和Entree Chicago Recommendation Data。MovieLens由著名的MovieLens網站上的電影推薦組成，該網站擁有超過50 000名用戶對3 000多部電影進行評分，數據集中有943個用戶對1 682部電影的100 000條評分，用戶自己擁有三個屬性，包括年齡、性別和職業。Anonymous Microsoft Web Data記錄了網站內38 000名匿名用戶過去一周在網站上的瀏覽記錄。Entree Chicago Recommendation Data記錄了用戶對芝加哥餐館主菜的評價。對每個數據集抽取100個用戶的數據作為測試數據，將這100名用戶作為新用戶，在三個數據集上分別使用基于FP-Growth的分類隨機游走算法和改進的FP-Growth分類隨機游走算法，以均方誤差(MSE)[13]為評價指標。

在三個數據集中，分別作10次隨機抽取100個用戶的實驗，結果如圖3～5所示。

圖3～5顯示了三個數據集上算法的性能，算法成功地為新用戶做出了推薦，且改進的FP-Growth分類隨機游走算法的性能普遍好于基于FP-Growth算法的性能。將每個數據集上10次實驗的MSE取平均，結果如表1所示。

從表1可見，改進的FP-Growth分類隨機游走成功解決了分類隨機游走算法中新用戶的評分向量問題，利用改進算法生成用戶屬性與項目之間的關聯規則去構造新用戶的初始評分向量，之后用分類隨機游走算法為新用戶進行推薦。相比于基于FP-Growth的分類隨機游走算法可以看出，該算法對新用戶具有較好的推薦結果。

圖3 MovieLens的實驗結果

圖4 Anonymous Microsoft Web Data的實驗結果

圖5 Entree Chicago Recommendation Data的實驗結果

表1 結果對比 s

5 結束語

針對隨機游走分類算法的不足，提出了基于關聯規則挖掘的隨機游走分類算法。為了彌補分類隨機游走算法不能為新用戶進行推薦的缺點，即新用戶沒有任何評分數據的問題，該算法利用關聯規則挖掘計算用戶屬性與項目之間的關聯規則，利用這些關聯規則為新用戶構建一個初始的評分向量，之后為該用戶計算推薦結果。實驗結果表明，該算法對于新用戶推薦具有較好的結果。隨著信息量的擴大，算法效率也必定會受到一定的影響，為了提高算法在運算大數據量時的效率，算法的并行化和分布式計算是未來研究的重要方向。

[1] 鄧愛林,朱揚勇,施伯樂.基于項目評分預測的協同過濾推薦算法[J].軟件學報,2003,14(9):1621-1628.

[2] 陳 健,印 鑒.基于影響集的協作過濾推薦算法[J].軟件學報,2007,18(7):1685-1694.

[3] 許海玲,吳 瀟,李曉東,等.互聯網推薦系統比較研究[J].軟件學報,2009,20(2):350-362.

[4] 曹 毅,賀衛紅.基于用戶興趣的混合推薦模型[J].系統工程,2009,27(6):68-72.

[5] 吳麗花,劉 魯.個性化推薦系統用戶建模技術綜述[J].情報學報,2006,25(1):55-62.

[6] 劉建國,周 濤,汪秉宏.個性化推薦系統的研究進展[J].自然科學進展,2009,19(1):1-15.

[7] 梁昌勇,冷亞軍,王勇勝,等.電子商務推薦系統中群體用戶推薦問題研究[J].中國管理科學,2013,21(3):153-158.

[8] Zhou T,Jiang L L,Su R Q,et al.Effect of initial configuration on network-based recommendation[J].Physics,2008,81(5):58-62.

[9] Zhang L,Xu J,Li C.A random-walk based recommendation algorithm considering item categories[J].Neurocomputing,2013,120(10):391-396.

[10] Agrawal R,Imieliński T,Swami A.Mining association rules between sets of items in large databases[C]//Proceedings of the 1993 ACM SIGMOD international conference on management of data.New York:ACM,1993:207-216.

[11] Minaei-Bidgoli B,Barmaki R,Nasiri M.Mining numerical association rules via multi-objective genetic algorithms[J].Information Sciences,2013,233:15-24.

[12] Soni R K,Gupta N,Sinhal A.An FP-growth approach to mining association rules[J].International Journal of Computer Science and Mobile Computing,2013,2(2):1-5.

[14] Tong Q L,Park Y,Park Y T.A time-based approach to effective recommender systems using implicit feedback[J].Expert Systems with Applications,2008,34(4):3055-3062.

Random-walk Classification Algorithm with Association Rules Mining

SHI Hai-ying

(Schoolof Computer Engineering and Science,Shanghai University,Shanghai 200444,China)

Along with the continuous progress of Internet technology and the rapid development of the Internet,people can easily find all kinds of information on the Internet.Users would spend a lot of time to search for information what they are really interested in,which is inefficient.The phenomenon is called information overload which is solved effectively by recommendation system as an effective method.However,the two most popular recommendation technologies in the current recommendation system are content-based recommendation and collaborative filtering recommendation,which cannot handle the problems of cold start and sparsity well.In order to better solve them,categorical random-walk algorithm based on association rules is proposed,which uses association rules to mine the association between user attributes and items and constructs the initial score vectors for new users.It has made up for the shortage of the classic algorithm and better handles the cold start problem.The results of experiments prove its effectiveness and accuracy.

recommendation system;association rules;categorical random-walk;information overload

2016-07-08

：2016-11-02 < class="emphasis_bold">網絡出版時間

時間：2017-07-11

上海市科委重點資助項目(91330116)

施海鷹(1979-),男,碩士研究生,研究方向為數據挖掘、人工智能；導師：楊洪斌，副教授，研究方向為數據挖掘、人工智能。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170711.1454.040.html

TP301.6

:A

:1673-629X(2017)09-0007-05

10.3969/j.issn.1673-629X.2017.09.002