融合關聯規則Apriori和Weighted-Slope One 算法的模型研究

牛俊潔，左 羽，崔忠偉

（1.貴州大學計算機科學與技術學院，貴州 貴陽 550025；2.貴州師范學院數學與計算機科學學院，貴州 貴陽 550018）

融合關聯規則Apriori和Weighted-Slope One 算法的模型研究

牛俊潔1，左 羽2，崔忠偉2

（1.貴州大學計算機科學與技術學院，貴州 貴陽 550025；2.貴州師范學院數學與計算機科學學院，貴州 貴陽 550018）

針對于Slope One算法不精確不具有解釋性的缺點提出了一種融合關聯規則Apriori和Weighted-Slope One的算法模型。利用關聯挖掘Apriori找出互相關聯的物品集大大提高了Slope One算法的推薦精度。融合后的AW-Slope One的算法在 Movielens數據集上的對比實驗結果表明，在數據集稀疏以及鄰居數目較少的情況下，平均絕對誤差（MAE）大大降低。

頻繁模式挖掘；關聯規則；線性模型；Apriori算法；Weighted-Slope One算法

引言

隨著信息資源的超載式增長，用戶對個性化服務需求逐步提高，推薦系統在電子商務、社交網絡和新聞推薦等領域已成為不可或缺的技術[1]。個性化推薦系統中，協同過濾（Collaborative filtering，CF）是應用最成功、最廣泛的技術之一[1]，但他們需要消耗大量的時間去計算用戶和物品相似度。為了提高效率及實時性，Lemire等[2]提出了Slope One算法，其核心思想是：線性回歸f（x）=x+b。借助大量用戶對item的評分，可以得到任意兩個item的回歸直線。未評分item由已評分item計算出分值，由計算出來分值的排序做最終推薦。它的優點是算法簡單，容易實現，可擴展性也不錯，但必須基于評分，如果沒有評分，需要構造評分。鄭丹等[3]提出一種基于Weighted-Slope One的用戶聚類推薦算法,使用改進的K-means方法聚類用戶后，利用User-CF搜索最近鄰居，結合Slope One為目標用戶推薦對應的產品。杜茂康等[4]等融合了領近項目的Slope One算法。胡旭等[5]提出了基于項目屬性相似和MapReduce并行化的Slope One算法。田松瑞[6]等提出了基于用戶相似度加權的Slope One算法。

這些算法都是在提高算法的精度上做出了一定的貢獻，但其關聯性和可解釋性相對較差。由此本文將推薦系統領域最著名“啤酒與尿布”故事中用到的關聯規則策略融合到Slope One算法中，進行這樣一個提高推薦效率嘗試。關聯規則的目的在于從一個數據集中找出項之間的關系，也稱之為購物藍分析（Market basket analysis）。本文提出基于關聯規則的Apriori與Weighted-Slope One相結合的推薦算法。根據數據分析整理，挖掘與目標項目N個項目相關值的計算，參與預測的項目、預測項目評分數據都得到優化。為了解決在使用Slope One算法計算預測值時被忽視的項目本身的相似性對項目評分的影響較大的問題，本文將提出用項目關聯的相關性來代替傳統形式中共同評價過項目的用戶數量，此方法不僅計算了用戶對目標項目的預測值，更增強了推薦的可信度。

1 相關研究

1.1 Slope One算法模型

（1）

運用（1）式可得到b的取值，而對于重新得到的數據點vnew，可以根據公式wnew=b+vnew得到一個較準確的預測值。直觀上我們可用wi和vi差值的平均值來代替求偏移b的公式。

利用上面的直觀，我們定義itemi相對于itemj的平均偏差：

（2）

其中，我們可用Sj,i（）統計在同一時間對物品i和j的評分的所有用戶的集合，另外，Sj,i（）所包含的元素總數則由card（）表示。通過對itemi相對于itemj的平均偏差的定義，我們便可得到用戶u對itemj的預測值，而此功能將由P（u）j,i=deνj,i+ui實現。當把所有這種可能的預測平均起來，可以預測出用戶u對物品j的評分：

（3）

其中，Rj表示所有用戶u已經給予評分且滿足條件（i≠j且Sj,i非空）的item集合。對于足夠稠密的數據集，我們可以使用近似：

（4）

把上面的預測公式簡化為

（5）

缺點：在使用SlopeOne計算itemi相對于itemj的平均偏差devj,l時，忽略了當使用不同的用戶平均所得到的devj,i，其計算結果的精確度和預設有一定的偏差。假設有2000個用戶同時評分了itemj和k，而只有20個用戶同時評分了itemj和l，那么顯然獲得的devj,k比devj,l更具有說服力。

1.2 Weighted-Slope One算法模型

所以對最終的平均使用加權進行一個修正，這也就是推薦更為合理的Weighted-SlopeOne[1]推薦算法。

（6）

其中

（7）

1.3 頻繁模式挖掘Apriori算法

關聯分析又被稱作關聯挖掘，其旨在大量的數據中搜尋項目集合或對象集合之間的關聯[10]。而其關聯又由頻繁項集（frequentitemsets）和關聯規則（associationrules）兩種形式構成，其中，頻繁項集（frequentitemsets）解釋為：經常出現在一塊兒的物品的集合[11]。而關聯規則（associationrules）則被解釋為：暗示兩種物品之間可能存在很強的關系。被搜尋出的關聯可用支持度與可信度來衡量。一個項目所擁有的支持度（support）常被定義為該項集的記錄在數據集中所占的比例。而一個項集的置信度（confidence）被定義為n+1項集的支持度/n項集的支持度。

Apriori的算法在各大領域中得到了廣泛應用，是一種最典型的挖掘布爾關聯規則頻繁項集的算法[13]。其算法的核心的是采用了具有層次分明搜索的迭代方法思想：k-項集用于尋找（k+1）-項集。第一步，搜索出1-頻繁項集的集合。記作L1。L1集合的作用是搜索出2-頻繁項集的集合L2,而L2的作用的搜素出3-頻繁項集L3，以此類推，直到k-頻繁項集不能找到[13]。舉例說明：

在這里可以理解為用戶1購買了I1,I2,I5，用戶2購買了I2,I4。

核心思想是：連接步和剪枝步。連接步是自連接，原則是保證前k-2項相同，并按照字典順序連接。剪枝步，任何的非空子集的頻繁項集也肯定是屢次出現的。恰恰相反，如果某一個的候選非空子集不是屢次出現，可判定該候選出現的不頻繁，將其刪除[14]。

TIDListofitem_ID’s1I1,I2,I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3

圖1Apriori算法數據舉例

其尋找頻繁項集的過程可以用下圖來表示：

圖2 Apriori算法尋找頻繁項集的過程

1.掃描D，對每個候選計數得到C1;2.比較候選支持度計數與最小支持度計數，得到L1；3由L1產生候選C2；4.掃描D,對切割候選計數；5.比較候選支持度計數與最小支出度計數得L2；6.由L2產生候選C3；7.掃描D,對每個候選計數得到L3；8.比較候選支持度計數與最小支持度計數。

通過最后的結果我們可以認為，當用戶購買物品I1時，很有可能購買物品I2，I3和I5；即物品I1，I2，I3，I5是相關聯的。

規則置信度If{I1,I2}then{I3}2/4*100%=50%If{I1,I5}then{I2}2/4*100%=50%

當我們在實際應用中得到相關項之后，我們只需要構建未評分項和其相關項的R（m*n）矩陣，接著使用Weight-SlopeOne算法預測評分即可。

2 算法

2.1 融合關聯規則Apriori和Weighted-Slope One算法

在本文提出的算法中，頻繁模式挖掘Apriori算法部分，通俗意義就是尋找與目標評分物相近、相關的N個物品。這樣就可以縮小計算范圍，提高數據可信度，從而達到提高推薦精度的目的。將通過關聯規則得到的結果集引入到關聯項目置信度為權重的Weighted-SlopeOne算法模型中，計算當前活躍用戶對目標項目的打分估計值，最后根據用戶對項目評分的預測值高低向用戶進行Top-N推薦項目。

2.2 融合關聯規則Aprior和Weighted-Slope One算法步驟

關聯分析的目標是一個集合的發現和一項規則的發現，即頻繁集和關聯項集。在Apriori算法中，輸入的兩個參數依次是最小支持度和數據元素組成的數據集合數。算法的第一個功能是把每一個元素項集列表實現，再對他們進行篩選，把滿足要求的留下，不滿足的則舍去。隨后，把那些不符合條件的集合重新組裝起來，形成新的集合。最后，重復上一步所做的操作，并刪除不符合最小支持度的集合，一直到所有集合都滿足條件。

整個Aprior算法的偽代碼如下：

◆當集合中項的個數大于0時

◆構建一個由k個項組成的候選項集的列表（k從1開始）

◆計算候選項集的支持度，刪除非頻繁項集

◆構建由k+1項組成的候選項集的列表

算法使用python語言完成：

whileTrue:

#循環產生項集大小為1, 2的項集

cur_item_set_size+= 1

ifcur_item_set_size== 1:

#產生初始的候選集

cur_candiate_set=gen_cand_set（data_set, ,cur_item_set_size）

#將候選集分成要滿足支持度的集合和不滿足支持度的集合，同時記錄滿足支持度集合對應的支持度分值

saved_item_set,cur_dis_item_set_1,support_data=scan_data_set（data_set,cur_candiate_set,min_support）

else:

#生成該輪候選集

cur_candiate_set=gen_cand_set（data_set,freq_item_set[-1],cur_item_set_size）

#去除候選集中不符合非頻繁項集的那些元素

cur_candiate_set,cur_dis_item_set_1 =subtract_item_set（discard_item_set,cur_candiate_set）

#對剩下的候選集，進行遍歷數據集，得到保存、丟棄、支持度集合

saved_item_set,cur_dis_item_set_2,support_data=scan_data_set（data_set,cur_candiate_set,min_support）

ifsaved_item_set== :# 如果該輪沒有產生任何頻繁項集，則下一輪也不會產生新的頻繁項集了，退出

break

freq_item_set.append（saved_item_set） #freq_item_set存儲每一輪產生的頻繁項集

discard_item_set=cur_dis_item_set_1 #discard_item_set存儲每一輪產生的要丟棄的項集

discard_item_set.extend（cur_dis_item_set_2）

item_set_support.append（support_data） #item_set_support存儲每一輪產生的頻繁項集對應的支持度值

3 實驗結果與分析

3.1 實驗數據集

到grouplens網站（http://www.grouplens.org/node/12）上下載DataSets，在該電影系統中我們使用了將近900多用戶為1683的電影評了近100000條的數據集。每個用戶看的電影數從1部到20部不等。將下載下來的數據集進行簡單處理，保存為u.data，數據格式如圖3所示：

電影信息數據集的格式比較復雜，文件名為item.txt這也是一個標簽分離的列表，如圖4所示：

圖3 rating.txt示意圖

圖4 item.txt的示意圖

選第一條記錄作為說明:

其中每一個標簽所代表的含義分別為：電影id|電影標題|發布日期| |視頻IMDbURL|動畫|冒險|行動|兒童|喜劇|犯罪|紀錄片|戲劇|幻想|黑色|恐怖|音樂|神秘|浪漫|科幻|驚悚|戰爭|西部

3.2 推薦質量評價指標

對于算法的評估，本文采用了平均絕對誤差（MeanAbsoluteTime，MAE）以及平均評估時間（MeanAssessTime，MAT）作為度量標準。

給定一個集合A={p1，p2，D，pE}，并給它賦上新定義“客戶評價”，同時定義B={q1，q2，…,qE}）為實際客戶評價，則定義MAE是平均絕對偏差，如公式（8）所示：

（8）

3.3 實驗過程及結果

實驗環境：Python

首先使用Apriori得出頻繁項集

圖5 利用Apriori算法迭代出頻繁項集

再與Weighted-SlopeOne算法結合預測評分并進行Top-N推薦：

圖6 結合Weighted-Slope One算法推薦的結果

最后進行算法評估：

圖7 各算法的MAT評估折線圖

分析實驗結果可得：AW-SlopeOne算法相比于W-SlopeOne和SlopeOne算法，平均絕對誤差（MeanAbsoluteTime，MAE）數值大大降低；隨著數據的增多，MAE的值都在減小。由此得出，本文提出的AW-SlopeOne算法在幾乎沒有增加評估時間的情況下大大降低了推薦誤差率。

4 結束語

本文提出了一種融合關聯規則Apriori和Weighted-SlopeOne的算法模型AW-SlopeOne。其策略是首先利用頻繁模式挖掘Apriori算法獲得一些關聯規則，得到頻繁項集也就是與未評分項相關的項集構造相關項的輕量級矩陣；再在該輕量級矩陣中使用線性Weighted-SlopeOne算法模型進行評分計算，最后做Top-N推薦。算法評估在Movielens數據集上進行的對比實驗顯示，MAE平均誤差率大大降低。下一步工作可嘗試將關聯規則Apriori算法替換為FP-Growth探索能否進一步提高推薦精度并降低平均誤差率和平均估算時間。

[1]SunH，ZhengZ，ChenJ，etal.PersonalizedWebServiceRecommendationviaNormalRecoveryCollaborativeFiltering[J].IEEETrans.ServiceComputing,2013，6（4）：573-579.

[2]LEMIRED，MACLACHLANA．SlopeOnePredictorsforOnlineRatingBasedCollaborativeFiltering[C]/ /InSIAMDataMining.California:SIAM，2005:21-23.

[3]鄭丹，王明揚，陳廣勝．基于Weighted-slopeOne的用戶聚類推薦算法研究[J]．計算機技術與發展，2016,35（5）:161-165.

[4]杜茂康，劉苗，李韶華等．基于鄰近項目的SlopeOne協同過濾算法[J]．重慶郵電大學學報：自然科學版， 2014， 26（3）：421-426．

[5]胡旭，魯漢榕，陳新,等.基于項目屬性相似和MapReduce并行化的SlopeOne算法[J].空軍預警學院學報,2015（1）:54-58.

[6]田松瑞.基于用戶相似度加權的SlopeOne算法[J].軟件，2016，37（4）：57（59.

[7]JIANGTongqiang，LUWei，XIONGHaitao．PersonalizedCollaborativeFilteringBasedOnImprovedSlopeOneAlgorithm[C]/ /2012InternationalConferenceonSystemsandInformatics（ICSAI2012）．Yantai：IEEE， 2012：2312-2315

[8]SUNMingtao,ZHANGHui，SONGShiyu，etal．USO-ANewSlopeOneAlgorithmBasedOnModifiedUserSimilarity[C]/ /2012InternationalConferenceonInformationManagement，InnovationManagementandIndustrialEngineering（ICIII）．Sanya:IEEE，2012：335-340

[9]WANGPu，YEHongwu.APersonalizedRecommendationAlgorithmCombiningSlopeOneSchemeandUserBasedCollaborativeFiltering[C]/ /2009InternationalConferenceonIndustrialandInformationSystems.Haikou：IEEE，2009:152-154.

[10]LopezJ，DahabR.NewPointCompressionAlgorithmsforBinaryCurves[C].InformationTheoryWorkshop,2006.ITW'06PuntadelEste.IEEE，March，2006.

[11]AgrawalR，SrikantR.Fastalgorithmsforminingassociationrules.In：Proc.oftheInt’lConf.onVeryLargeDataBases（VLDB）.Santiago，1994：487-499.

[12]ZakiMJ.Scalablealgorithmsforassociationmining.IEEETrans.onKnowledgeandDataEngineering（TKDE），2000，12（3）:372.

[13]HanJ，PeiJ，YinYW.Miningfrequentpatternswithoutcandidategeneration.In：Proc.oftheACMAnnualConf.onManagementofData（SIGMOD），2000，1（12）.

[14]HanJW，FuYQ.Discoveryofmultiple-levelassociationrulesfromlargedatabases.In：Proc.oftheInt’lConf.onVeryLargeDataBases（VLDB），1995：420-431.

[15]SrikantR，AgrawalR.Mininggeneralizedassociationrules.In：Proc.oftheInt’lConf.onVeryLargeDataBases（VLDB），1995：407-419.

[16]項亮．推薦系統實踐[M]．北京:人民郵電出版社，2012．

[17]DietmarJannach,MarkusZanker.推薦系統[M].蔣凡,譯.北 京：人民郵電出版社,2013:25-28.

[責任編輯：黃 梅]

Research on integrating association rules Apriori into Weighted- Slope One algorithm

NIU Jun-jie1, ZUO Yu2, CUI Zhong-wei2

（1.College of Computer Science & Information, Guizhou University, Guiyang, Guizhou,550025; 2.School of Mathematics and Computer Science, Guizhou Education University, Guiyang, Guizhou, 550018）

We integrate association rules Apriori into Weighted-Slope One algorithm because the Slope One algorithm is not accurate with explanatory faults .Using association rules Apriori to find related items set has greatly increased recommendation accuracy of the Slope One algorithm.And on Movielens data set of contrast experiment results show that the fusion of AW-Slope One algorithm has greatly reduced the mean absolute time （MAE） even though sparse data sets or the circumstances of less number of neighbors.

Frequent pattern mining; Association rules; Linear model; The Apriori algorithm; Weighted-Slope One algorithm

2016-10-09

2016年貴州省省級重點支持學科“計算機應用技術”（黔學位合字ZDXK[2016]20號）；2016年度貴州省科技平臺及人才團隊專項資金項目（項目編號：黔科合平臺人才[2016]5609）；2016年度省教育廳高校自然科學研究項目（黔教合字[2016]015、黔教合KY字[2016]040）；2015年省級高技術產業示范工程專項（黔發改投資[2015]1588號）。

牛俊潔（1991-），女，山東淄博人，貴州大學2014級在讀碩士研究生，研究方向：大數據管理與應用。

TN918；TP309

A

1674-7798（2016）12-0037-06