?？?，左 羽，崔忠偉

（1.貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽(yáng) 550025；2.貴州師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，貴州 貴陽(yáng) 550018）

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

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

（1.貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽(yáng) 550025；2.貴州師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，貴州 貴陽(yáng) 550018）

針對(duì)于Slope One算法不精確不具有解釋性的缺點(diǎn)提出了一種融合關(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ù)集上的對(duì)比實(shí)驗(yàn)結(jié)果表明，在數(shù)據(jù)集稀疏以及鄰居數(shù)目較少的情況下，平均絕對(duì)誤差（MAE）大大降低。

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

引言

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

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

1 相關(guān)研究

1.1 Slope One算法模型

（1）

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

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

（2）

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

（3）

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

（4）

把上面的預(yù)測(cè)公式簡(jiǎn)化為

（5）

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

1.2 Weighted-Slope One算法模型

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

（6）

其中

（7）

1.3 頻繁模式挖掘Apriori算法

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

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

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

核心思想是：連接步和剪枝步。連接步是自連接，原則是保證前k-2項(xiàng)相同，并按照字典順序連接。剪枝步，任何的非空子集的頻繁項(xiàng)集也肯定是屢次出現(xiàn)的。恰恰相反，如果某一個(gè)的候選非空子集不是屢次出現(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ù)舉例

其尋找頻繁項(xiàng)集的過程可以用下圖來(lái)表示：

圖2 Apriori算法尋找頻繁項(xiàng)集的過程

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

通過最后的結(jié)果我們可以認(rèn)為，當(dāng)用戶購(gòu)買物品I1時(shí)，很有可能購(gòu)買物品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%

當(dāng)我們?cè)趯?shí)際應(yīng)用中得到相關(guān)項(xiàng)之后，我們只需要構(gòu)建未評(píng)分項(xiàng)和其相關(guān)項(xiàng)的R（m*n）矩陣，接著使用Weight-SlopeOne算法預(yù)測(cè)評(píng)分即可。

2 算法

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

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

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

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

整個(gè)Aprior算法的偽代碼如下：

◆當(dāng)集合中項(xiàng)的個(gè)數(shù)大于0時(shí)

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

◆計(jì)算候選項(xiàng)集的支持度，刪除非頻繁項(xiàng)集

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

算法使用python語(yǔ)言完成：

whileTrue:

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

cur_item_set_size+= 1

ifcur_item_set_size== 1:

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

cur_candiate_set=gen_cand_set（data_set, ,cur_item_set_size）

#將候選集分成要滿足支持度的集合和不滿足支持度的集合，同時(shí)記錄滿足支持度集合對(duì)應(yīng)的支持度分值

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）

#去除候選集中不符合非頻繁項(xiàng)集的那些元素

cur_candiate_set,cur_dis_item_set_1 =subtract_item_set（discard_item_set,cur_candiate_set）

#對(duì)剩下的候選集，進(jìn)行遍歷數(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)生任何頻繁項(xiàng)集，則下一輪也不會(huì)產(chǎn)生新的頻繁項(xiàng)集了，退出

break

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

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

discard_item_set.extend（cur_dis_item_set_2）

item_set_support.append（support_data） #item_set_support存儲(chǔ)每一輪產(chǎn)生的頻繁項(xiàng)集對(duì)應(yīng)的支持度值

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

圖3 rating.txt示意圖

圖4 item.txt的示意圖

選第一條記錄作為說(shuō)明:

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

3.2 推薦質(zhì)量評(píng)價(jià)指標(biāo)

對(duì)于算法的評(píng)估，本文采用了平均絕對(duì)誤差（MeanAbsoluteTime，MAE）以及平均評(píng)估時(shí)間（MeanAssessTime，MAT）作為度量標(biāo)準(zhǔn)。

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

（8）

3.3 實(shí)驗(yàn)過程及結(jié)果

實(shí)驗(yàn)環(huán)境：Python

首先使用Apriori得出頻繁項(xiàng)集

圖5 利用Apriori算法迭代出頻繁項(xiàng)集

再與Weighted-SlopeOne算法結(jié)合預(yù)測(cè)評(píng)分并進(jìn)行Top-N推薦：

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

最后進(jìn)行算法評(píng)估：

圖7 各算法的MAT評(píng)估折線圖

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

4 結(jié)束語(yǔ)

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

[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]鄭丹，王明揚(yáng)，陳廣勝．基于Weighted-slopeOne的用戶聚類推薦算法研究[J]．計(jì)算機(jī)技術(shù)與發(fā)展，2016,35（5）:161-165.

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

[5]胡旭，魯漢榕，陳新,等.基于項(xiàng)目屬性相似和MapReduce并行化的SlopeOne算法[J].空軍預(yù)警學(xué)院學(xué)報(bào),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]項(xiàng)亮．推薦系統(tǒng)實(shí)踐[M]．北京:人民郵電出版社，2012．

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

[責(zé)任編輯：黃 梅]

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年貴州省省級(jí)重點(diǎn)支持學(xué)科“計(jì)算機(jī)應(yīng)用技術(shù)”（黔學(xué)位合字ZDXK[2016]20號(hào)）；2016年度貴州省科技平臺(tái)及人才團(tuán)隊(duì)專項(xiàng)資金項(xiàng)目（項(xiàng)目編號(hào)：黔科合平臺(tái)人才[2016]5609）；2016年度省教育廳高校自然科學(xué)研究項(xiàng)目（黔教合字[2016]015、黔教合KY字[2016]040）；2015年省級(jí)高技術(shù)產(chǎn)業(yè)示范工程專項(xiàng)（黔發(fā)改投資[2015]1588號(hào)）。

?？崳?991-），女，山東淄博人，貴州大學(xué)2014級(jí)在讀碩士研究生，研究方向：大數(shù)據(jù)管理與應(yīng)用。

TN918；TP309

A

1674-7798（2016）12-0037-06