關(guān)聯(lián)規(guī)則--文檔整理.doc

_關(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ī)則的挖掘問題進行了大量的研究。關(guān)聯(lián)規(guī)則挖掘在數(shù)據(jù)挖掘中是一個重要的課題，最近幾年已被業(yè)界所廣泛研究。關(guān)聯(lián)規(guī)則最初提出的動機是針對購物籃分析(Market Basket Analysis)問題提出的。假設(shè)分店經(jīng)理想更多的了解顧客的購物習(xí)慣（如下圖）。特別是，想知道哪些商品顧客可能會在一次購物時同時購買？為回答該問題，可以對商店的顧客事物零售數(shù)量進行購物籃分析。該過程通過發(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è)是項的集合，給定一個交易數(shù)據(jù)庫， 其中每個事務(wù)(Transaction)t是I的非空子集，即，每一個交易都與一個唯一的標(biāo)識符TID(Transaction ID)對應(yīng)。關(guān)聯(lián)規(guī)則是形如的蘊涵式， 其中且， 和分別稱為關(guān)聯(lián)規(guī)則的先導(dǎo)(antecedent或left-hand-side, LHS)和后繼(consequent或right-hand-side, RHS)。關(guān)聯(lián)規(guī)則在D中的支持度(support)是D中事務(wù)包含的百分比，即概率；置信度(confidence)是包含X的事務(wù)中同時包含Y的百分比，即條件概率。如果滿足最小支持度閾值和最小置信度閾值，則稱關(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,5,6同時包含網(wǎng)球拍和網(wǎng)球，支持度， 置信度。 若給定最小支持度 = 0.5，最小置信度 = 0.8，關(guān)聯(lián)規(guī)則網(wǎng)球拍網(wǎng)球是有趣的，認為購買網(wǎng)球拍和購買網(wǎng)球之間存在關(guān)聯(lián)。1.3 關(guān)聯(lián)規(guī)則的分類按照不同標(biāo)準(zhǔn)，關(guān)聯(lián)規(guī)則可以進行分類如下：（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ù)值型字段進行處理，將其進行動態(tài)的分割，或者直接對原始的數(shù)據(jù)進行處理，當(dāng)然數(shù)值型關(guān)聯(lián)規(guī)則中也可以包含種類 變量。例如：性別=“女”=職業(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)進行了充分的考慮。例如：IBM臺式機=Sony打印機，是一個細節(jié)數(shù)據(jù)上的單層關(guān)聯(lián)規(guī)則；臺式機= Sony打印機，是一個較高層次和細節(jié)層次之間的多層關(guān)聯(lián)規(guī)則。（3）基于規(guī)則中涉及到的數(shù)據(jù)的維數(shù)，關(guān)聯(lián)規(guī)則可以分為單維的和多維的。在單維的關(guān)聯(lián)規(guī)則中，我們只涉及到數(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算法。由于它本身有許多固有缺陷，后來的研究者又紛紛提出了各種改進算法或者不同的算法，頻繁樹（FP-Tree）算法應(yīng)用也十分廣泛。本文將就這兩種典型算法進行研究。2.1 Apriori算法2.1.1預(yù)備知識關(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項集。找每個Lk需要一次數(shù)據(jù)庫全掃描。為提高頻繁項集逐層產(chǎn)生的效率，一種稱作Apriori性質(zhì)的重要性質(zhì)用于壓縮搜索空間。Apriori性質(zhì)：頻繁項集的所有非空子集也必須是頻繁的。Apriori性質(zhì)基于如下觀察。根據(jù)定義，如果項集I不滿足最小支持度閾值min_sup，則I不是頻繁的，即P(I)min_sup。如果項A添加到項集I，則結(jié)果項集（即IA）不可能比I 更頻繁出現(xiàn)。因此，IA也不是頻繁的，即P(IA)min_sup。2.1.2 Apriori算法的核心思想文獻1中對Apriori核心算法思想簡要描述如下：該算法中有兩個關(guān)鍵步驟連接步和剪枝步。 (1) 連接步：為找出Lk(頻繁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中刪除。這種子集測試可以使用所有頻繁項集的散列樹快速完成。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 c Ct 7） c.count+； 8） 9） Lk=c Ck| c.count min_sup 10） 11） return L = kLk； Procedure apriori_gen (Lk-1:frequent(k-1)-itemsets) 1) for each itemsets l1Lk-1 2) for each itemsets l2Lk-1 3) if (l11=l21) (l12=l22)(l1k-2=l2k-2) (l1k-1廚房配件、貝殼類=蔬菜、貝殼類=水果、成品=廚房配件、急救用品=蜜餞糖果零食類、啤酒=水果。由此可以看出，當(dāng)顧客購買辦公設(shè)備或者成品時，很有可能會同時購買廚房配件；當(dāng)顧客購買貝殼類時，很有可能會同時購買蔬菜、水果；當(dāng)顧客購買啤酒時，很有可能會同時購買水果。從總體上看，貝殼類、蔬菜、水果及啤酒很有可能被同時購買。以上分析結(jié)果對于世紀(jì)聯(lián)華超市的物品擺放、顧客的購買模式研究、商品的進貨管理等方面都有一定指導(dǎo)意義。世紀(jì)聯(lián)華超市可以在商品擺放上將辦公設(shè)備和廚房配件就近擺放，將貝殼類、蔬菜、水果和啤酒就近擺放，而辦公設(shè)備和廚房配件則應(yīng)該與貝殼類、蔬菜、水果和啤酒相對分開。超市在進貨及庫存管理上也應(yīng)該注意以上幾種商品數(shù)量的協(xié)調(diào)，從而更好地滿足顧客。參考文獻1 Jiawei Han Micheline Kamber, Data Mining Concepts and Techniques, Second EditionM:151-1552 1. Toivonen H. Sampling large databases for association rulesC.In: Proceedings of the 22th International Conference on Very Large Databases,Bombay,India,1996:1-123 2. Brin S, Motwani R, Ullman J D et al. Dynamic itemset counting and implication rules for market basket analysis. In: Proceedings of 1997 ACM-SIGMOD International Conference on Management of Data.Tucson,AZ,1997:255-2644 3. Savasere A, Omiecinski E,Navathe S. An efficient algorithm for mining association rulesC. In: Proceedings of the 21st International Conference on VLDB.Zurich,1995:432-4445 4. Park J S, Chen M S, Yu P S. An Effective Hash-Based Algorithm for Mining Association Rules. In: Proceedings of ACM SIGMOD International Conference Management of Data, San Jose,CA,1995:175-