融合關(guān)聯(lián)規(guī)則Apriori和Weighted-Slope One 算法的模型研究

?？崳?羽，崔忠偉

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

融合關(guān)聯(lián)規(guī)則Apriori和Weighted-Slope One 算法的模型研究

?？?，左 羽2，崔忠偉2

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

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

頻繁模式挖掘；關(guān)聯(lián)規(guī)則；線性模型；Apriori算法；Weighted-Slope One算法

引言

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

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

1 相關(guān)研究

1.1 Slope One算法模型

（1）

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

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

（2）

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

（3）

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

（4）

把上面的預測公式簡化為

（5）

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

1.2 Weighted-Slope One算法模型

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

（6）

其中

（7）

1.3 頻繁模式挖掘Apriori算法

關(guān)聯(lián)分析又被稱作關(guān)聯(lián)挖掘，其旨在大量的數(shù)據(jù)中搜尋項目集合或?qū)ο蠹现g的關(guān)聯(lián)[10]。而其關(guān)聯(lián)又由頻繁項集（frequentitemsets）和關(guān)聯(lián)規(guī)則（associationrules）兩種形式構(gòu)成，其中，頻繁項集（frequentitemsets）解釋為：經(jīng)常出現(xiàn)在一塊兒的物品的集合[11]。而關(guān)聯(lián)規(guī)則（associationrules）則被解釋為：暗示兩種物品之間可能存在很強的關(guān)系。被搜尋出的關(guān)聯(lián)可用支持度與可信度來衡量。一個項目所擁有的支持度（support）常被定義為該項集的記錄在數(shù)據(jù)集中所占的比例。而一個項集的置信度（confidence）被定義為n+1項集的支持度/n項集的支持度。

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

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

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

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

圖1Apriori算法數(shù)據(jù)舉例

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

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

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

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

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

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

2 算法

2.1 融合關(guān)聯(lián)規(guī)則Apriori和Weighted-Slope One算法

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

2.2 融合關(guān)聯(lián)規(guī)則Aprior和Weighted-Slope One算法步驟

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

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

◆當集合中項的個數(shù)大于0時

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

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

◆構(gòu)建由k+1項組成的候選項集的列表

算法使用python語言完成：

whileTrue:

#循環(huán)產(chǎn)生項集大小為1, 2的項集

cur_item_set_size+= 1

ifcur_item_set_size== 1:

#產(chǎn)生初始的候選集

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）

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

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

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

break

freq_item_set.append（saved_item_set） #freq_item_set存儲每一輪產(chǎn)生的頻繁項集

discard_item_set=cur_dis_item_set_1 #discard_item_set存儲每一輪產(chǎn)生的要丟棄的項集

discard_item_set.extend（cur_dis_item_set_2）

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

3 實驗結(jié)果與分析

3.1 實驗數(shù)據(jù)集

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

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

圖3 rating.txt示意圖

圖4 item.txt的示意圖

選第一條記錄作為說明:

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

3.2 推薦質(zhì)量評價指標

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

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

（8）

3.3 實驗過程及結(jié)果

實驗環(huán)境：Python

首先使用Apriori得出頻繁項集

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

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

圖6 結(jié)合Weighted-Slope One算法推薦的結(jié)果

最后進行算法評估：

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

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

4 結(jié)束語

本文提出了一種融合關(guān)聯(lián)規(guī)則Apriori和Weighted-SlopeOne的算法模型AW-SlopeOne。其策略是首先利用頻繁模式挖掘Apriori算法獲得一些關(guān)聯(lián)規(guī)則，得到頻繁項集也就是與未評分項相關(guān)的項集構(gòu)造相關(guān)項的輕量級矩陣；再在該輕量級矩陣中使用線性Weighted-SlopeOne算法模型進行評分計算，最后做Top-N推薦。算法評估在Movielens數(shù)據(jù)集上進行的對比實驗顯示，MAE平均誤差率大大降低。下一步工作可嘗試將關(guān)聯(lián)規(guī)則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]．計算機技術(shù)與發(fā)展，2016,35（5）:161-165.

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

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

[6]田松瑞.基于用戶相似度加權(quán)的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，F(xiàn)uYQ.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]項亮．推薦系統(tǒng)實踐[M]．北京:人民郵電出版社，2012．

[17]DietmarJannach,MarkusZanker.推薦系統(tǒng)[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年貴州省省級重點支持學科“計算機應用技術(shù)”（黔學位合字ZDXK[2016]20號）；2016年度貴州省科技平臺及人才團隊專項資金項目（項目編號：黔科合平臺人才[2016]5609）；2016年度省教育廳高校自然科學研究項目（黔教合字[2016]015、黔教合KY字[2016]040）；2015年省級高技術(shù)產(chǎn)業(yè)示范工程專項（黔發(fā)改投資[2015]1588號）。

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

TN918；TP309

A

1674-7798（2016）12-0037-06