關(guān)聯(lián)規(guī)則基本算法

1、關(guān)聯(lián)規(guī)則基本算法及其應(yīng)用1關(guān)聯(lián)規(guī)則挖掘1.1 關(guān)聯(lián)規(guī)則提出背景1993年，Agrawal等人在首先提出關(guān)聯(lián)規(guī)則概念，同時給出了相應(yīng)的挖掘算法AIS，但是性能較差。1994年，他們建立了項目集格空間理論，并依據(jù)上述兩個定理，提出了著名的Apriori算法，至今Apriori仍然作為關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法被廣泛討論，以后諸多的研究人員對關(guān)聯(lián)規(guī)則的挖掘問題進(jìn)行了大量的研究。關(guān)聯(lián)規(guī)則挖掘在數(shù)據(jù)挖掘中是一個重要的課題，最近幾年已被業(yè)界所廣泛研究。關(guān)聯(lián)規(guī)則最初提出的動機是針對購物籃分析(Market Basket Analysis)問題提出的。假設(shè)分店經(jīng)理想更多的了解顧客的購物習(xí)慣（如下圖）。特別是，想知

2、道哪些商品顧客可能會在一次購物時同時購買？為回答該問題，可以對商店的顧客事物零售數(shù)量進(jìn)行購物籃分析。該過程通過發(fā)現(xiàn)顧客放入“購物籃”中的不同商品之間的關(guān)聯(lián)，分析顧客的購物習(xí)慣。這種關(guān)聯(lián)的發(fā)現(xiàn)可以幫助零售商了解哪些商品頻繁的被顧客同時購買，從而幫助他們開發(fā)更好的營銷策略。1.2 關(guān)聯(lián)規(guī)則的基本概念關(guān)聯(lián)規(guī)則定義為：假設(shè)I=i1,i2,.im是項的集合，給定一個交易數(shù)據(jù)庫D=t1,t2,.,tm， 其中每個事務(wù)(Transaction)t是I的非空子集，即tI，每一個交易都與一個唯一的標(biāo)識符TID(Transaction ID)對應(yīng)。關(guān)聯(lián)規(guī)則是形如XY的蘊涵式， 其中X和Y分別稱為關(guān)聯(lián)規(guī)則的先導(dǎo)(a

3、ntecedent或left-hand-side, LHS)X,YI且XY=，和后繼(consequent或right-hand-side, RHS)。關(guān)聯(lián)規(guī)則XY在D中的支持度(support)是D中事務(wù)包含XY的百分比，即概率P(XY)；置信度(confidence)是包含X的事務(wù)中同時包含Y的百分比，即條件概率P(Y|X)。如果滿足最小支持度閾值和最小置信度閾值，則稱關(guān)聯(lián)規(guī)則是有趣的。這些閾值由用戶或者專家設(shè)定。用一個簡單的例子說明。上表是顧客購買記錄的數(shù)據(jù)庫D，包含6個事務(wù)。項集I=網(wǎng)球拍,網(wǎng)球,運動鞋,羽毛球。考慮關(guān)聯(lián)規(guī)則：網(wǎng)球拍網(wǎng) 球，事務(wù)1,2,3,4,6包含網(wǎng)球拍，事務(wù)1,2,

4、5,6同時包含網(wǎng)球拍和網(wǎng)球，支持度support=36 置信度confident=0.5，35 若給定最小支持度 = 0.5，=0.6。最小置信度 = 0.8，關(guān)聯(lián)規(guī)則網(wǎng)球拍在關(guān)聯(lián)。網(wǎng)球是有趣的，認(rèn)為購買網(wǎng)球拍和購買網(wǎng)球之間存1.3 關(guān)聯(lián)規(guī)則的分類按照不同標(biāo)準(zhǔn)，關(guān)聯(lián)規(guī)則可以進(jìn)行分類如下：（1）基于規(guī)則中處理的變量的類別，關(guān)聯(lián)規(guī)則可以分為布爾型和數(shù)值型。布爾型關(guān)聯(lián)規(guī)則處理的值都是離散的、種類化的，它顯示了這些變量之間的關(guān)系；而數(shù)值型關(guān)聯(lián)規(guī)則 可以和多維關(guān)聯(lián)或多層關(guān)聯(lián)規(guī)則結(jié)合起來，對數(shù)值型字段進(jìn)行處理，將其進(jìn)行動態(tài)的分割，或者直接對原始的數(shù)據(jù)進(jìn)行處理，當(dāng)然數(shù)值型關(guān)聯(lián)規(guī)則中也可以包含種類 變量。例如

5、：性別=“女”=>職業(yè)=“秘書” ，是布爾型關(guān)聯(lián)規(guī)則；性別=“女”=>avg（收入）=2300，涉及的收入是數(shù)值類型，所以是一個數(shù)值型關(guān)聯(lián)規(guī)則。（2）基于規(guī)則中數(shù)據(jù)的抽象層次，可以分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則。在單層的關(guān)聯(lián)規(guī)則中，所有的變量都沒有考慮到現(xiàn)實的數(shù)據(jù)是具有多個不同的層次的；而在多層的關(guān) 聯(lián)規(guī)則中，對數(shù)據(jù)的多層性已經(jīng)進(jìn)行了充分的考慮。例如：IBM臺式機=>Sony打印機，是一個細(xì)節(jié)數(shù)據(jù)上的單層關(guān)聯(lián)規(guī)則；臺式機=> Sony打印機，是一個較高層次和細(xì)節(jié)層次之間的多層關(guān)聯(lián)規(guī)則。（3）基于規(guī)則中涉及到的數(shù)據(jù)的維數(shù)，關(guān)聯(lián)規(guī)則可以分為單維的和多維的。在單維的關(guān)聯(lián)規(guī)則中

6、，我們只涉及到數(shù)據(jù)的一個維，如用戶購買的物品；而在多維的關(guān)聯(lián)規(guī)則中，要 處理的數(shù)據(jù)將會涉及多個維。換成另一句話，單維關(guān)聯(lián)規(guī)則是處理單個屬性中的一些關(guān)系；多維關(guān)聯(lián)規(guī)則是處理各個屬性之間的某些關(guān)系。例如：啤酒=>尿 布，這條規(guī)則只涉及到用戶的購買的物品；性別=“女”=>職業(yè)=“秘書”，這條規(guī)則就涉及到兩個字段的信息，是兩個維上的一條關(guān)聯(lián)規(guī)則。2關(guān)聯(lián)規(guī)則挖掘的相關(guān)算法關(guān)聯(lián)規(guī)則最為經(jīng)典的算法是Apriori算法。由于它本身有許多固有缺陷，后來的研究者又紛紛提出了各種改進(jìn)算法或者不同的算法，頻繁樹（FP-Tree）算法應(yīng)用也十分廣泛。本文將就這兩種典型算法進(jìn)行研究。2.1 Apriori算法

7、關(guān)聯(lián)規(guī)則的挖掘分為兩步：(1)找出所有頻繁項集；(2)由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則。而其總體性能由第一步?jīng)Q定。在搜索頻繁項集的時候，最簡單、基本的算法就是Apriori算法。它是R.Agrawal和R.Srikant于1994年提出的為布爾關(guān)聯(lián)規(guī)則挖掘頻繁項集的原創(chuàng)性算法。算法的名字基于這樣一個事實：算法使用頻繁項集性質(zhì)的先驗知識。Apriori使用一種稱作逐層搜索的迭代方法，k項集用于探索（k+1）項集。首先，通過掃描數(shù)據(jù)庫，累積每個項的計數(shù)，并收集滿足最小支持度的項，找出頻繁1項集的集合。該集合記作L1。然后，L1用于找頻繁2項集的集合L2，L2用于找L3，如此下去，直到不能再找到頻繁k項集。

8、找每個Lk需要一次數(shù)據(jù)庫全掃描。為提高頻繁項集逐層產(chǎn)生的效率，一種稱作Apriori性質(zhì)的重要性質(zhì)用于壓縮搜索空間。Apriori性質(zhì)：頻繁項集的所有非空子集也必須是頻繁的。Apriori性質(zhì)基于如下觀察。根據(jù)定義，如果項集I不滿足最小支持度閾值min_sup，則I不是頻繁的，即P(I)<min_sup。如果項A添加到項集I，則結(jié)果項集（即I是頻繁的，即P(IA)<min_sup。 A）不可能比I 更頻繁出現(xiàn)。因此，IA也不2.1.2 Apriori算法的核心思想文獻(xiàn)1中對Apriori核心算法思想簡要描述如下：該算法中有兩個關(guān)鍵步驟連接步和剪枝步。 (1) 連接步：為找出Lk(頻

9、繁k項集)，通過Lk-1與自身連接，產(chǎn)生候選k項集，該候選項集記作Ck；其中Lk-1的元素是可連接的。(2) 剪枝步：Ck是Lk的超集，即它的成員可以是也可以不是頻繁的，但所有的頻繁項集都包含在Ck中。掃描數(shù)據(jù)庫，確定Ck中每一個候選的計數(shù)，從而確定Lk(計數(shù)值不小于最小支持度計數(shù)的所有候選是頻繁的，從而屬于Lk)。然而，Ck可能很大，這樣所涉及的計算量就很大。為壓縮Ck，使用Apriori性質(zhì)：任何非頻繁的(k-1)項集都不可能是頻繁k項集的子集。因此，如果一個候選k項集的(k-1)項集不在Lk中，則該候選項也不可能是頻繁的，從而可以由Ck中刪除。這種子集測試可以使用所有頻繁項集的散列樹快速

10、完成。2.1.3 Apriori算法描述Apriori算法，使用逐層迭代找出頻繁項集。輸入：事務(wù)數(shù)據(jù)庫D；最小支持度閾值min_sup。輸出：D 中的頻繁項集L。1） L1 = find_frequent_1_itemsets（D）；2） for （k = 2； Lk-1 ； k+） 3） Ck = aproiri_gen（Lk-1，min_sup）；4） for each transaction t D /掃描 D 用于計數(shù)5） Ct = subset（Ck，t）； /得到 t 的子集，它們是候選6） for each candidate c7） c.count+；8） 9） Lk=c10）

11、 Ct Ck | c.count min_sup11） return L = kLk；Procedure apriori_gen (Lk-1:frequent(k-1)-itemsets)1) for each itemsets l1Lk-12) for each itemsets l2Lk-13) if (l11=l21) (l12=l22)(l1k-2=l2k-2) (l1k-1<l2k-1) then4) c=l1l2; / 連接步：產(chǎn)生候選5) if has_infrequent_subset(c,Lk-1) then6) delete c; / 剪枝步：刪除非頻繁的候選7) e

12、lse add c to Ck;8) 9) return Ck;Procedure has_infrequent_subset (c:candidate k-itemset;Lk-1:frequent(k-1)-itemsets) /使用先驗知識1) for each(k-1)-subset s of c2) If s3) return TRUE;4) return FALSE; Lk-1 then2.1.4 Apriori算法評價基于頻繁項集的Apriori算法采用了逐層搜索的迭代的方法，算法簡單明了，沒有復(fù)雜的理論推導(dǎo)，也易于實現(xiàn)。但其有一些難以克服的缺點：（1）對數(shù)據(jù)庫的掃描次數(shù)過多。在

13、Apriori算法的描述中，我們知道，每生成一個候選項集，都要對數(shù)據(jù)庫進(jìn)行一次全面的搜索。如果要生成最大長度為N的頻繁項集，那么就要對數(shù)據(jù)庫進(jìn)行N次掃描。當(dāng)數(shù)據(jù)庫中存放大量的事務(wù)數(shù)據(jù)時，在有限的內(nèi)存容量下，系統(tǒng)I/O負(fù)載相當(dāng)大，每次掃描數(shù)據(jù)庫的時間就會很長，這樣其效率就非常低。（2）Apriori算法會產(chǎn)生大量的中間項集。Apriori_gen函數(shù)是用Lk-1產(chǎn)生候選Ck，所產(chǎn)生Ck由個k項集組成。顯然，k越大所產(chǎn)生的候選k項集的數(shù)量呈幾何級數(shù)增加。如頻繁1項集的數(shù)量為104個，長度為2的候選項集的數(shù)量將達(dá)到5*107個，如果要生成一個更長規(guī)則，其需要產(chǎn)生的候選項集的數(shù)量將是難以想象的，如同天

14、文數(shù)字。（3）采用唯一支持度，沒有將各個屬性重要程度的不同考慮進(jìn)去。在現(xiàn)實生活中，一些事務(wù)的發(fā)生非常頻繁，而有些事務(wù)則很稀疏，這樣對挖掘來說就存在一個問題：如果最小支持度閾值定得較高，雖然加快了速度，但是覆蓋的數(shù)據(jù)較少，有意義的規(guī)則可能不被發(fā)現(xiàn)；如果最小支持度閾定得過低，那么大量的無實際意義的規(guī)則將充斥在整個挖掘過程中，大大降低了挖掘效率和規(guī)則的可用性。這都將影響甚至誤導(dǎo)決策的制定。（4）算法的適應(yīng)面窄。該算法只考慮了單維布爾關(guān)聯(lián)規(guī)則的挖掘，但在實際應(yīng)用中，可能出現(xiàn)多維的、數(shù)量的、多層的關(guān)聯(lián)規(guī)則。這時，該算法就不再適用，需要改進(jìn)，甚至需要重新設(shè)計算法。2.1.5 Apriori算法改進(jìn)鑒于Ap

15、riori算法本身存在一些缺陷，在實際應(yīng)用中往往不能令人感到滿意。為了提高Apriori算法的性能，已經(jīng)有許多變種對Apriori進(jìn)一步改進(jìn)和擴展?？梢酝ㄟ^以下幾個方面對Apriori算法進(jìn)行改進(jìn)：通過減少掃描數(shù)據(jù)庫的次數(shù)改進(jìn)I/O的性能。改進(jìn)產(chǎn)生頻繁項集的計算性能。尋找有效的并行關(guān)聯(lián)規(guī)則算法。引入抽樣技術(shù)改進(jìn)生成頻繁項集的I/O和計算性能。擴展應(yīng)用領(lǐng)域。如：定量關(guān)聯(lián)規(guī)則、泛化關(guān)聯(lián)規(guī)則及周期性的關(guān)聯(lián)規(guī)則的研究。目前許多專家學(xué)者通過大量的研究工作，提出了一些改進(jìn)的算法以提高Apriori的效率，簡要介紹如下：（1）基于抽樣(Sampling)技術(shù)該方法的基本思想是:選取給定數(shù)據(jù)庫D的隨機樣本S，

16、然后，在S中搜索頻繁項目集。樣本S的大小這樣選取，使得可以在內(nèi)存搜索S中的頻繁項目集，它只需要掃描一次S中的事務(wù)。由于該算法搜索S中而不是D中的頻繁項目集，可能會丟失一些全局頻繁項目集。為了減少這種可能性，該算法使用比最小支持度低的支持度閾值來找出樣本S中的頻繁項目集(記作LS)。然后，計算LS中每個項目集的支持度。有一種機制可以用來確定是否所有的頻繁項目集都包含在LS中。如果LS包含了D中的所有頻繁項目集，則只需要掃描一次D，否則，需要第二次掃描D，以找出在第一次掃描時遺漏的頻繁項目集。（2）基于動態(tài)的項目集計數(shù)3該算法把數(shù)據(jù)庫分成幾塊，對開始點進(jìn)行標(biāo)記，重復(fù)掃描數(shù)據(jù)庫。與Apriori算法

17、不同，該算法能在任何開始點增加新的候選項目集，而不是正好在新數(shù)據(jù)庫的開始，在每個開始點，該算法估計所有項目集的支持度，如果它的所有子集被估計為是頻繁的，增加該項目集到候選項目集中。如果該算法在第一次掃描期間增加了所有的頻繁項目集和負(fù)邊界到候選項目集中，它會在第二次掃描期間精確計算每個項目集的支持度，因此，該算法在第二次掃描后完成所有操作。（3）基于劃分的方法PARTITION算法4首先將事務(wù)數(shù)據(jù)庫分割成若干個互不重疊的子數(shù)據(jù)庫，分別進(jìn)行頻繁項集挖掘:最后將所有的局部頻繁項集合并作為整個交易庫的候選項集。掃描一遍原始數(shù)據(jù)庫計算候選集的支持度。算法生成整個交易數(shù)據(jù)庫的頻繁項集只需要掃描數(shù)據(jù)庫兩次。

18、（4）基于hash技術(shù)通過使用hash技術(shù)，DHP(Direct-Hush and Prune)可以在生成候選集時過濾掉更多的項集。所以每一次生成的候選集都更加逼近頻繁集。這種技術(shù)對于2項候選集的剪枝尤其有效。另一方面DHP技術(shù)還可以有效地削減每一次掃描數(shù)據(jù)庫的規(guī)模。（5）事務(wù)壓縮（壓縮進(jìn)一步迭代掃描的事務(wù)數(shù)）這是算法Apriori-Tid的基本思想：減少用于未來掃描的事務(wù)集的大小。如果在數(shù)據(jù)庫遍歷中將一些不包含k-頻繁相集的事務(wù)刪除，那么在下一次循環(huán)中就可以減少掃描的事務(wù)量，而不會影響候選集的支持度闕值。522.2 頻繁樹（FP-Tree）算法在上面介紹的Apriori算法中，由于Aprio

19、ri方法的固有的缺陷還是無法克服，即使進(jìn)行了優(yōu)化，其效率也仍然不能令人滿意。在文獻(xiàn)6中Han Jiawei等人提出了基于頻繁模式樹（Frequent Pattern Tree，簡稱為FP-Tree）的發(fā)現(xiàn)頻繁項目集的算法FP-growth。這種方法在經(jīng)過第一遍掃描之后，把數(shù)據(jù)庫中的頻繁項目集壓縮成一棵頻繁模式樹，同時依然保留其中的管理信息。隨后再將FP-Tree分化成一些條件庫，每個庫和一個長度為L的頻繁項目集相關(guān)，然后再對這些條件庫分別進(jìn)行挖掘。當(dāng)原始數(shù)據(jù)庫很大時，也可以結(jié)合劃分的方法使得一個FP-Tree可以放入主存中。實驗證明，F(xiàn)P-growth對不同長度的規(guī)則都有很好的適應(yīng)性，同時在效

20、率上較Apriori算法有巨大的提高。這個算法只進(jìn)行兩次數(shù)據(jù)庫掃描，它不使用候選項目集，直接壓縮數(shù)據(jù)庫成一個頻繁模式樹，最后通過這棵樹生成關(guān)聯(lián)規(guī)則。3.1 關(guān)聯(lián)規(guī)則挖掘技術(shù)在國內(nèi)外的應(yīng)用現(xiàn)狀就目前而言，關(guān)聯(lián)規(guī)則挖掘技術(shù)已經(jīng)被廣泛應(yīng)用在西方金融行業(yè)企業(yè)中，它可以成功預(yù)測銀行客戶需求。一旦獲得了這些信息，銀行就可以改善自身營銷。各銀行在自己的ATM機上就捆綁了顧客可能感興趣的本行產(chǎn)品信息，供使用本行ATM機的用戶了解。同時，一些知名的電子商務(wù)站點也從強大的關(guān)聯(lián)規(guī)則挖掘中的受益。這些電子購物網(wǎng)站使用關(guān)聯(lián)規(guī)則對規(guī)則進(jìn)行挖掘，然后設(shè)置用戶有意要一起購買的捆綁包。也有一些購物網(wǎng)站使用它們設(shè)置相應(yīng)的交叉銷售

21、，也就是購買某種商品的顧客會看到相關(guān)的另外一種商品的廣告。但是目前在我國，“數(shù)據(jù)海量，信息缺乏”是商業(yè)銀行在數(shù)據(jù)大集中之后普遍所面對的尷尬。目前金融業(yè)實施的大多數(shù)數(shù)據(jù)庫只能實現(xiàn)數(shù)據(jù)的錄入、查詢、統(tǒng)計等較低層次的功能，卻無法發(fā)現(xiàn)數(shù)據(jù)中存在的各種有用的信息，譬如對這些數(shù)據(jù)進(jìn)行分析，發(fā)現(xiàn)其數(shù)據(jù)模式及特征，然后可能發(fā)現(xiàn)某個客戶、消費群體或組織的金融和商業(yè)興趣，并可觀察金融市場的變化趨勢?？梢哉f，關(guān)聯(lián)規(guī)則的挖掘技術(shù)在我國的研究與應(yīng)用并不是很廣泛深入。3.2 關(guān)聯(lián)規(guī)則在大型超市中應(yīng)用的步驟接下來本文對關(guān)聯(lián)規(guī)則在超級市場中的應(yīng)用進(jìn)行討論，提出了關(guān)聯(lián)規(guī)則在大型超市中應(yīng)用的步驟，得出了基于關(guān)聯(lián)規(guī)則的商品銷售模式

22、。超級市場的數(shù)據(jù)不僅十分龐大、復(fù)雜，而且包含著許多有用信息。隨著數(shù)據(jù)挖掘技術(shù)的發(fā)展以及各種數(shù)據(jù)挖掘方法的應(yīng)用，從大型超市數(shù)據(jù)庫中可以發(fā)現(xiàn)一些潛在的、有用的、有價值的信息來，從而應(yīng)用于超級市場的經(jīng)營。通過對所積累的銷售數(shù)據(jù)的分析，可以得出各種商品的銷售信息。從而更合理地制定各種商品的定貨情況，對各種商品的庫存進(jìn)行合理地控制。另外根據(jù)各種商品銷售的相關(guān)情況，可分析商品的銷售關(guān)聯(lián)性，從而可以進(jìn)行商品的貨籃分析和組合管理，以更加有利于商品銷售。這里我們以世紀(jì)聯(lián)華超市2010年1月25日和26日的所有銷售記錄為例進(jìn)行分析。該數(shù)據(jù)來源于世紀(jì)聯(lián)華超市的收銀臺。首先，通過ODBC連接access數(shù)據(jù)庫中的原始

23、表格，原始數(shù)據(jù)如表1所示。表1：原始數(shù)據(jù)庫然后，通過編寫Select語句，獲得CusCode,itemname有序編號和物品名稱，分別如表表2：存放顧客CusCode的數(shù)組表3：存放物品itemname的數(shù)組最后，將數(shù)據(jù)庫中的客戶購買信息轉(zhuǎn)化為0-1表（其中1代表購買，0代表沒有購買），結(jié)表4：0-1表根據(jù)超市各種商品銷售量、顧客購買情況等信息，不同的超市可以根據(jù)各自的實際情況設(shè)定不同的最小支持度和最小置信度。這里我們設(shè)定最小支持度為0.2，最小置信度為0.7。我們采用JAVA語言編程，計算機運行結(jié)果如圖1。圖1 計算機運行結(jié)果得出頻繁項集有廚房配件、蜜餞糖果零食類、蔬菜、水果、辦公設(shè)備、廚房

24、配件、貝殼類、蔬菜、貝殼類、水果、成品、廚房配件、急救用品、蜜餞糖果零食類、啤酒、水果。關(guān)聯(lián)規(guī)則有: 辦公設(shè)備=>廚房配件、貝殼類=>蔬菜、貝殼類=>水果、成品=>廚房配件、急救用品=>蜜餞糖果零食類、啤酒=>水果。由此可以看出，當(dāng)顧客購買辦公設(shè)備或者成品時，很有可能會同時購買廚房配件；當(dāng)顧客購買貝殼類時，很有可能會同時購買蔬菜、水果；當(dāng)顧客購買啤酒時，很有可能會同時購買水果。從總體上看，貝殼類、蔬菜、水果及啤酒很有可能被同時購買。以上分析結(jié)果對于世紀(jì)聯(lián)華超市的物品擺放、顧客的購買模式研究、商品的進(jìn)貨管理等方面都有一定指導(dǎo)意義。世紀(jì)聯(lián)華超市可以在商品擺放上將辦公設(shè)備和廚房配件就近擺放，將貝殼類、蔬菜、水果和啤酒就近擺放，而辦公設(shè)備和廚房配件則應(yīng)該與貝殼類、蔬菜、水果和啤酒相對分開。超市在進(jìn)貨及庫存管理上也應(yīng)該注意以上幾種商品數(shù)量的協(xié)調(diào)，從而更好地滿足顧客。參考文獻(xiàn)1 Jiawei Han Micheline Kamber, Data Mining Concepts and Techniques, SecondEditionM:151-1552 1. Toivonen H. Sampling large databases for association rulesC.In: Proceedings of the 22thInternatio