1.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則的概念

　　

　　數(shù)據(jù)挖掘就是大量數(shù)據(jù)中提取或者挖掘知識(shí)，這種數(shù)據(jù)應(yīng)該是海量的。還有另一種說(shuō)法是把數(shù)據(jù)挖掘看成是數(shù)據(jù)庫(kù)中知識(shí)的發(fā)現(xiàn)過(guò)程的一個(gè)基本步驟。

　　

　　1.1關(guān)聯(lián)規(guī)則的概念

　　

　　關(guān)聯(lián)規(guī)則可以說(shuō)是在數(shù)據(jù)挖掘中相對(duì)來(lái)說(shuō)比較常用的一種方法了，Agmwal等于1993年首先提出了挖掘顧客交易數(shù)據(jù)庫(kù)中項(xiàng)集間的關(guān)聯(lián)規(guī)則問(wèn)題。在這以后有諸多的研宄員對(duì)數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則進(jìn)行了大量的研究。他們的工作有很多，其中就包括對(duì)原有的算法進(jìn)行了優(yōu)化處理。比如，引進(jìn)了隨機(jī)采樣、并行思想等。

　　

　　關(guān)聯(lián)規(guī)則挖掘的過(guò)程是這樣的一個(gè)流程，首先利用算法根據(jù)最小支持度找到頻繁項(xiàng)集，再依托找到的頻繁項(xiàng)集結(jié)合置信度生成形如X—Y的強(qiáng)關(guān)聯(lián)規(guī)則。在關(guān)聯(lián)關(guān)聯(lián)規(guī)則挖掘過(guò)程中用到兩個(gè)最重要的參數(shù)，支持度和置信度。

　　

　　設(shè)I={il’i是項(xiàng)集，其中ik(k=l，2，…,m)可以是購(gòu)物籃中的物品，也可以是保險(xiǎn)公司的顧客。設(shè)任務(wù)相關(guān)的數(shù)據(jù)D是事務(wù)集，其中每個(gè)事務(wù)T是項(xiàng)集，使得TSI。設(shè)A是一個(gè)項(xiàng)集，且A£T。關(guān)聯(lián)規(guī)則是如下形式的邏輯蘊(yùn)涵：A=>B,ASI，BGI,且AnB=A關(guān)聯(lián)規(guī)則具有如下兩個(gè)重要的屬性：

 

　　支持度：P(AUB)，即A和B這兩個(gè)項(xiàng)集在事務(wù)集D中同時(shí)出現(xiàn)的概率。

　　

　　置信度：P(BIA)，即在出現(xiàn)項(xiàng)集A的事務(wù)集D中，項(xiàng)集B也同時(shí)出現(xiàn)的概率。

　　

　　同時(shí)滿(mǎn)足最小支持度閾值和最小置信度閾值的規(guī)則稱(chēng)為強(qiáng)規(guī)則。給定一個(gè)事務(wù)集D，挖掘關(guān)聯(lián)規(guī)則問(wèn)題就是產(chǎn)生支持度和可信度分別大于用戶(hù)給定的最小支持度和最小可信度的關(guān)聯(lián)規(guī)則，也就是產(chǎn)生強(qiáng)規(guī)則的問(wèn)題。

　　

　　1.2  Apriori算法

　　

　　Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。很多的的挖掘算法是在A(yíng)priori算法的基礎(chǔ)上進(jìn)行改進(jìn)的，比如基于散列（Hash)的方法，基于數(shù)據(jù)分割(Partition)的方法以及不產(chǎn)生候選項(xiàng)集的FP-GROWTH方法等。因此要了解關(guān)聯(lián)規(guī)則算法不得不先要了解Apriori算法。

　　

　　Apriori算法使用的是頻繁項(xiàng)集性質(zhì)的先驗(yàn)知識(shí)，是使用了一種稱(chēng)為逐層搜索的迭代方法，其中k項(xiàng)集用于探索（k+1)項(xiàng)集。首先，通過(guò)對(duì)數(shù)據(jù)庫(kù)的掃描，累計(jì)每一項(xiàng)的計(jì)數(shù)，并收集滿(mǎn)足最小支持度的項(xiàng)，這樣就能找出頻繁項(xiàng)的集合。這樣得到的集合可以標(biāo)記L,。然后，使用3^找出頻繁項(xiàng)集L2,使用L2找出L3。這樣循環(huán)下去，直到找到頻繁項(xiàng)集k項(xiàng)集為止。這樣就對(duì)數(shù)據(jù)庫(kù)進(jìn)行了一次完整的掃描。

　　

　　2.關(guān)聯(lián)規(guī)則在電子商務(wù)圖書(shū)推薦系統(tǒng)中的具體應(yīng)用

 

　　2.1數(shù)據(jù)收集、預(yù)處理

　　

　　用戶(hù)可以通過(guò)登錄到公司的網(wǎng)站進(jìn)行個(gè)人信息的注冊(cè)，從而形成用戶(hù)個(gè)人信息注冊(cè)表。用戶(hù)可以進(jìn)行圖書(shū)信息瀏覽，或查看其他用戶(hù)對(duì)圖書(shū)產(chǎn)品的評(píng)價(jià)和感受。當(dāng)用戶(hù)對(duì)某件圖書(shū)產(chǎn)品進(jìn)行購(gòu)買(mǎi)行為，形成訂單之后。數(shù)據(jù)就會(huì)被采集，并進(jìn)行清洗、集成和轉(zhuǎn)換。當(dāng)此用戶(hù)再次進(jìn)行圖書(shū)購(gòu)買(mǎi)行為時(shí)，購(gòu)買(mǎi)記錄同樣會(huì)被采集，并根據(jù)圖書(shū)類(lèi)別進(jìn)行分析，逐漸形成關(guān)聯(lián)數(shù)據(jù)。并存儲(chǔ)到圖書(shū)交易數(shù)據(jù)庫(kù)中。

　　

　　2.2生成關(guān)聯(lián)規(guī)則

　　

　　假設(shè)某個(gè)項(xiàng)目集S={sl，s2...，sn}是頻繁項(xiàng)目集，假設(shè)D是一個(gè)數(shù)據(jù)集，其中T是一個(gè)非空的項(xiàng)集。再假設(shè)A是一個(gè)項(xiàng)集并且有T包含A。有這樣一個(gè)式子形如A=>B。其中A£I,B£i, B^0,并且AHB=0。

　　

　　這樣的規(guī)則人=>8在事物集D中是成立的，具有支持度s。概率是P(AUB)，還有就是置信度c，概率是P(BIA)。規(guī)則人=>8在事物集中的支持度為support,即

　　

　　support(AUB)=support(AUB,D)=So(3)規(guī)則A=>B的置信度可以容易的從A和AUB的支持度計(jì)數(shù)推出，即表示為P(Y|X)=c%。這樣給出式子：

　　

　　confidence(A^B)=P(B|A)=support(AUB^D)/siq)port(A*D)(4)

　　

　　其中，support(AUB,D)是包括項(xiàng)集AUB的支持度，support(A，D)是項(xiàng)集X的支持度。

　　

　　對(duì)于已經(jīng)給定的數(shù)據(jù)集D，求出同時(shí)滿(mǎn)足最小支持度minsup和最小置信度minconf的關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則須滿(mǎn)足這樣兩個(gè)條件：support(A=»B)>minsup；confidence(A=>B)>minconf。

　　

　　2.3關(guān)聯(lián)規(guī)則的改進(jìn)方法

　　

　　大部分關(guān)聯(lián)規(guī)則挖掘算法都使用支持度-置信度框架。但是由于算法本身的原因，可能即使?jié)M足了最小支持度和最小置信度對(duì)用戶(hù)不感興趣的信息的探查，仍然會(huì)產(chǎn)生一些讓用戶(hù)感到不用的信息。

　　

　　在獲得用戶(hù)購(gòu)買(mǎi)的行為模式后，并不一定所有的強(qiáng)關(guān)聯(lián)規(guī)則都能成為用戶(hù)所感興趣的，這樣就使得這個(gè)規(guī)則的可用性并不理想。此時(shí)，就需要用到其他的方法來(lái)判斷用戶(hù)的興趣所在。

　　

　　假設(shè)我們分析涉及購(gòu)買(mǎi)“Java入門(mén)經(jīng)典”和購(gòu)買(mǎi)“Java實(shí)戰(zhàn)”兩本書(shū)的事務(wù)興趣。假設(shè)事務(wù)A表示包含“Java入門(mén)經(jīng)典”，事務(wù)B表示包含“Java實(shí)戰(zhàn)”。在接下來(lái)要進(jìn)行分析的10000個(gè)事務(wù)中，得到數(shù)據(jù)顯示為6000個(gè)顧客事務(wù)包含“Java入門(mén)經(jīng)典”，7500個(gè)事務(wù)包含“Java實(shí)戰(zhàn)”，而4000個(gè)事務(wù)同時(shí)包含“Java入門(mén)經(jīng)典”和“Java實(shí)戰(zhàn)”�，F(xiàn)在假設(shè)有一個(gè)關(guān)聯(lián)規(guī)則要在這樣的數(shù)據(jù)上進(jìn)行分析，可以使用最小支持度為30%，最小置信度為60%。將發(fā)現(xiàn)下面規(guī)則：

　　

　　buys(X，’’A”）=>buys(X，”B”)[support=40%,confidence=66%]

　　

　　這樣可以很容易的看出來(lái)這個(gè)關(guān)系式是屬于強(qiáng)關(guān)聯(lián)的，因?yàn)樗�的支持度�?000/10000=40%。置信度為4000/6000=66%，同時(shí)滿(mǎn)足了最小支持度和最小置信度閾值。實(shí)際上，這是一種誤導(dǎo)，因?yàn)橘?gòu)買(mǎi)“Java實(shí)戰(zhàn)”的概率是7500/10000=75%，比66%還高，這就容易出現(xiàn)不明智的商業(yè)營(yíng)銷(xiāo)策略。

　　

　　正如上面出現(xiàn)的問(wèn)題，支持度和置信度度量不足以過(guò)濾掉無(wú)趣的關(guān)聯(lián)規(guī)則。為了解決這個(gè)問(wèn)題，可以使用其他關(guān)系式來(lái)進(jìn)行同時(shí)篩查強(qiáng)關(guān)聯(lián)規(guī)則，比如，使用相關(guān)性度量來(lái)進(jìn)行擴(kuò)充，可以使用這樣的相關(guān)規(guī)則（correlationrule)：

　　

　　A=>Bfsupport,confidence,correlation]

　　

　　通過(guò)這個(gè)關(guān)系式可以看出，相關(guān)規(guī)則不僅用支持度和置信度，而且還用項(xiàng)集A和B之間的相關(guān)度量。

　　

　　2.4 使用提升度相關(guān)分析

　　

　　提升度(lift)是一種簡(jiǎn)單的相關(guān)性度量，相關(guān)度的定義是：項(xiàng)集A的出現(xiàn)獨(dú)立于項(xiàng)集B的出現(xiàn)，如果P(AUB)=P(A)P(B);否則，作為事件，項(xiàng)集A和B是依賴(lài)的和相關(guān)的.這樣就得到計(jì)算式： .

　　

　　lift(A,B)=P(AUB)/P(A)P(B)(4)

　　

　　如果這個(gè)值小于1，則A的出現(xiàn)與B的出現(xiàn)是負(fù)相關(guān)的，意味著一個(gè)出現(xiàn)可能導(dǎo)致另一個(gè)不出現(xiàn)。如果值大于1，則A和B是正相關(guān)的，如果值等于1，則A和B是獨(dú)立的。這個(gè)式子也稱(chēng)關(guān)聯(lián)規(guī)則A=>B的提升度。

　　

　　這樣我們?cè)偃タ辞懊娴睦�子，容易得到�?gòu)買(mǎi)“Java入門(mén)經(jīng)典”的概率P(“A”)=0.6，購(gòu)買(mǎi)“Java實(shí)戰(zhàn)”的概率P(“B”）=0.75，而購(gòu)買(mǎi)兩者的概率是P({“A”，”B”})=0.4。則提升度為：

　　

　　P({“A”，”B”})/(P(“A”)xp(“B”))=0.4/(0.6x0.75)=0.89

　　

　　該值小于1，從而得出購(gòu)買(mǎi)這兩本書(shū)的事務(wù)是負(fù)相關(guān)的，因此這兩種圖書(shū)的購(gòu)買(mǎi)行為不會(huì)進(jìn)行推薦，但這種負(fù)相關(guān)是不能被支持度-置信度框架識(shí)別的。

　　

　　2.5 電子商務(wù)圖書(shū)推薦過(guò)程

　　

　　首先根據(jù)每個(gè)顧客的圖書(shū)產(chǎn)品購(gòu)買(mǎi)記錄或則是瀏覽記錄的數(shù)據(jù)進(jìn)行預(yù)處理，形成交易數(shù)據(jù)庫(kù)。在己經(jīng)得到的數(shù)據(jù)庫(kù)的基礎(chǔ)上使用選用好的關(guān)聯(lián)規(guī)則挖掘算法對(duì)數(shù)據(jù)庫(kù)進(jìn)行關(guān)聯(lián)規(guī)則分析和挖掘，形成關(guān)聯(lián)規(guī)則數(shù)據(jù)集合R。之后在通過(guò)分析得到的數(shù)據(jù)集合R為每個(gè)顧客設(shè)置一個(gè)候選推薦集，并將初始值設(shè)置為空。對(duì)每個(gè)用戶(hù)搜索關(guān)聯(lián)規(guī)則數(shù)據(jù)集合R，找出該用戶(hù)支持的所有關(guān)聯(lián)規(guī)則集合。將符合與當(dāng)前用戶(hù)購(gòu)買(mǎi)圖書(shū)產(chǎn)品相關(guān)聯(lián)的所有圖書(shū)產(chǎn)品加入到當(dāng)前用戶(hù)的候選推薦集中。將候選推薦集中用戶(hù)己經(jīng)購(gòu)買(mǎi)的圖書(shū)產(chǎn)品刪除。然后可以根據(jù)置信度對(duì)候選推薦集中的候選項(xiàng)進(jìn)行排序，從候選推薦集中選擇置信度高的圖書(shū)項(xiàng)作為推薦結(jié)果。

　　

　　3.結(jié)束語(yǔ)

　　

　　現(xiàn)在越來(lái)越多的電子商務(wù)網(wǎng)站都在出售圖書(shū)類(lèi)產(chǎn)品，這可以使用戶(hù)幾乎足不出戶(hù)就能購(gòu)買(mǎi)到需要的圖書(shū)，但是不像在以前到書(shū)店購(gòu)買(mǎi)圖書(shū)，沒(méi)有導(dǎo)購(gòu)員向顧客介紹圖書(shū)產(chǎn)品信息，顧客也就不會(huì)知道那種或那類(lèi)圖書(shū)銷(xiāo)售最好，最受歡迎。電子商務(wù)圖書(shū)推薦系統(tǒng)的出現(xiàn)，有效的解決了顧客對(duì)圖書(shū)類(lèi)產(chǎn)品進(jìn)行“盲選”的尷尬狀態(tài)。這也成為各商家競(jìng)爭(zhēng)的一大“主力”。關(guān)聯(lián)規(guī)則作為數(shù)據(jù)挖掘的主要方法之一，也逐漸的引起了人們?cè)絹?lái)越多的關(guān)注。在不久的未來(lái)，我相信像這一類(lèi)推薦系統(tǒng)，一定可以使得將來(lái)的電子商務(wù)網(wǎng)站更加的人性化，個(gè)性化，更符合不同顧客的需求。

　　

　　文／趙偉毅  作者單位  北方工業(yè)大學(xué)計(jì)算機(jī)學(xué)院北京市100144