關(guān)聯(lián)規(guī)則挖掘算法綜述

1、關(guān)聯(lián)規(guī)那么挖掘算法綜述論文導(dǎo)讀：一個大型數(shù)據(jù)庫,其各個字段之間存在著各種各樣的關(guān)系,這些關(guān)系就隱含在數(shù)據(jù)庫所包含的數(shù)據(jù)中,關(guān)聯(lián)規(guī)那么挖掘的目的是找出這些隱藏的關(guān)聯(lián)。4頻繁項集：支持度不小于用戶給定的最小支持度的項集。Apriori性質(zhì)：頻繁項集的所有非空子集都必須也是頻繁的。通過實驗可以發(fā)現(xiàn)尋找頻繁集主要的計算是在生成頻繁2-項集Lk上，Park等就是利用了這個性質(zhì)引入hash技術(shù)來改良產(chǎn)生頻繁2-項集的方法。的置信度最低。關(guān)鍵詞：關(guān)聯(lián)規(guī)那么,頻繁集,Apriori,FP-tree,支持度,置信度一、關(guān)聯(lián)規(guī)那么挖掘簡介一個大型數(shù)據(jù)庫,其各個字段之間存在著各種各樣的關(guān)系,這些關(guān)系就隱含在數(shù)據(jù)庫所

2、包含的數(shù)據(jù)中,關(guān)聯(lián)規(guī)那么挖掘的目的是找出這些隱藏的關(guān)聯(lián)。1、問題描述與根本概念1、問題描述關(guān)聯(lián)規(guī)那么的挖掘問題可形式化描述如下：設(shè)I=i 1 ,i 2 ,i m 是由m個不同的工程組成的集合,給定一個事務(wù)數(shù)據(jù)庫D,其中的每一個事務(wù)T是I中一組工程的集合,即 ,T有唯一的標(biāo)識符TID.一條關(guān)聯(lián)規(guī)那么就是一個形如 的蘊含式,其中, 。關(guān)聯(lián)規(guī)那么 成立的條件是：它具有支持度S,即事務(wù)數(shù)據(jù)庫D中至少有S%的事務(wù)包含XY；它具有置信度C，即在事務(wù)數(shù)據(jù)庫D所包含X的事務(wù)中,至少有C%的事務(wù)同時也包含Y，關(guān)聯(lián)規(guī)那么的挖掘問題就是在事務(wù)數(shù)據(jù)庫D中找出具有用戶給定的最小支持度 和最小置信度 的關(guān)聯(lián)規(guī)那么。2、根

3、本概念：1項集：項的集合。2k項集：包含k個項的項集。3項集的出現(xiàn)頻率：包含項集的事務(wù)數(shù)目。4頻繁項集：支持度不小于用戶給定的最小支持度的項集。5頻繁k項集：支持度不小于用戶給定的最小支持度的k項集。2、關(guān)聯(lián)規(guī)那么分類 ：3、關(guān)聯(lián)規(guī)那么價值衡量方法1、主觀興趣度度量：用戶決定規(guī)那么的有效性、可行性，沒有統(tǒng)一的標(biāo)準(zhǔn)。2、客觀興趣度度量：支持度置信度;框架:興趣度：IS度量：二、關(guān)聯(lián)規(guī)那么的挖掘算法挖掘關(guān)聯(lián)規(guī)那么可以分解為以下兩個過程：找出存在于事務(wù)數(shù)據(jù)庫中的所有頻繁項集。利用頻繁項集生成關(guān)聯(lián)規(guī)那么。一、Apriori算法：使用候選項集找頻繁項集Apriori性質(zhì)：頻繁項集的所有非空子集都必須也是

4、頻繁的。1、Apriori算法步驟：1)用Apriori算法產(chǎn)生頻繁項集連接步：為找 ,通過 與自己連接產(chǎn)生k項集的集合。該候選項集的集合記作： 。論文格式。設(shè) 表示 中的項集， 表示 中的第j項，假定項集中的項按字典序排列；連接 ： ：剪枝步:掃描事務(wù)集D,確定 中每個元素出現(xiàn)的次數(shù)，從而確定 。2)由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)那么a、對每個頻繁項集L產(chǎn)生其所有的非空真子集。b、對L的每個非空真子集S計算 置信度，大于 的留下來作為挖掘到的關(guān)聯(lián)規(guī)那么，小于 的去掉。2、Apriori算法的幾種優(yōu)化方法1) 基于劃分的方法：將事務(wù)集D分為n個非重疊的局部。找出每局部內(nèi)的頻繁項集局部。將所有的局部頻繁項

5、集作為整個D的候選項集，掃描D確定每個候選集的實際支持度。2)基于散列的技術(shù)散列表具有不同的桶，每個桶有個地址，在掃描D時對每個事務(wù)產(chǎn)生其所有的k項集，然后根據(jù)散列函數(shù)計算每個k項集的地址，并把齊放入相應(yīng)的桶中，相應(yīng)的桶技術(shù)加1，對所有的事務(wù)作完后，計數(shù)小于 的桶中的k項集那么不可能是頻繁的k項集，可把它從候選集中刪除。3)事務(wù)壓縮：壓縮進一步迭代掃描事務(wù)集根據(jù)：不包含任何k項集的事務(wù)是不可能包含任務(wù)k+1項集，可把這些事務(wù)加上標(biāo)記，掃描時不掃描它們。4)基于hash的方法：通過實驗可以發(fā)現(xiàn)尋找頻繁集主要的計算是在生成頻繁2-項集Lk上，Park等就是利用了這個性質(zhì)引入hash技術(shù)來改良產(chǎn)生頻

6、繁2-項集的方法。論文格式。5)基于采樣的方法根本思想是在給定數(shù)據(jù)的一個子集挖掘。對前一遍掃描得到的信息，仔細地組合分析，可以得到一個改良的算法，Mannila等先考慮了這一點，他們認為采樣是發(fā)現(xiàn)規(guī)那么的一個有效途徑。隨后又由Toivonen進一步開展了這個思想，先使用從數(shù)據(jù)庫中抽取出來的采樣得到一些在整個數(shù)據(jù)庫中可能成立的規(guī)那么，然后對數(shù)據(jù)庫的剩余局部驗證這個結(jié)果。Toivonen的算法相當(dāng)簡單并顯著地減少了I/O代價，但是一個很大的缺點就是產(chǎn)生的結(jié)果不精確，即存在所謂的數(shù)據(jù)扭曲(data skew)。分布在同一頁面上的數(shù)據(jù)時常是高度相關(guān)的，可能不能表示整個數(shù)據(jù)庫中模式的分布，由此而導(dǎo)致的是

7、采樣5%的交易數(shù)據(jù)所花費的代價可能同掃描一遍數(shù)據(jù)庫相近。6)動態(tài)項集計數(shù)Brin等人給出該算法。動態(tài)項集計數(shù)技術(shù)將數(shù)據(jù)庫劃分為標(biāo)記開始點的塊。不象Apriori僅在每次完整的數(shù)據(jù)庫掃描之前確定新的候選，在這種變形中，可以在任何開始點添加新的候選項集。該技術(shù)動態(tài)地評估以被計數(shù)的所有項集的支持度，如果一個項集的所有子集以被確定為頻繁的，那么添加它作為新的候選。結(jié)果算法需要的數(shù)據(jù)庫掃描比Apriori 少。7)FA(Fast Apriori)算法：在計算頻繁項集的同時記錄包含在頻繁集中相應(yīng)事務(wù)TID，每次計算 支持度時對不包含在 中的各事務(wù)直接刪除，不必進行支持度計算，同時刪除不包含 中的任何項的事

8、務(wù)，在以后的支持度計算中不加考慮，這樣計算候選項集支持度所涉及的記錄數(shù)目將小于事務(wù)數(shù)據(jù)庫中的原記錄數(shù)目，提高了整個算法的效率。3、Apriori算法的缺陷：1)算法可能會產(chǎn)生大量的候選集；2)算法必須屢次重復(fù)掃描數(shù)據(jù)庫，對候選集進行模式匹配，因此效率低下。二、FP-growth算法：不產(chǎn)生候選集挖掘頻繁項集1、FP-growth算法步驟1)掃描事務(wù)集D找出頻繁1項集，并按支持度降序排序，記作：L；2)創(chuàng)立FP樹的根節(jié)點，用null;標(biāo)記；3)對每個事務(wù)創(chuàng)立一個分支，按L中的次序處理每個項：第一項連接到根，第二項作為第一項的孩子，第三項作為第二項的孩子，如此下去，每個節(jié)點計數(shù)為1，假設(shè)樹中有此分

9、支的前假設(shè)干項，那么將這幾項合并。4)從L的最后一項l開始，構(gòu)造l的條件模式基，即FP樹種l出現(xiàn)的分支上l前的項的集合，這些分支構(gòu)成FP條件樹；5)將l與FP樹中的項連接，以產(chǎn)生頻繁項集。2、FP-growth算法的優(yōu)點：對于挖掘長的和短的頻繁模式，他都是有效的和可伸縮的，并且大約比Apriori算法快一個數(shù)量級。三、其他挖掘頻繁項集的算法Apriori算法得出的關(guān)系都是頻繁出現(xiàn)的，但是在實際的應(yīng)用中，我們可能需要尋找一些高度相關(guān)的元素，即使這些元素不是頻繁出現(xiàn)的。在apriori算法中，起決定作用的是支持度，而我們現(xiàn)在將把可信度放在第一位，挖掘一些具有非常高可信度的規(guī)那么。整個算法根本上分成

10、三個步驟：計算特征、生成候選集、過濾候選集。在三個步驟中，關(guān)鍵的地方就是在計算特征時Hash方法的使用。在考慮方法的時候，有幾個衡量好壞的指數(shù)：時空效率、錯誤率和遺漏率。根本的方法有兩類Min_Hashing(MH),Locality_Sensitive_Hashing(LSH):Min_Hashing的根本想法是：將一條記錄中的頭k個為1的字段的位置作為一個Hash函數(shù)。Locality_Sentitive_Hashing的根本想法是：將整個數(shù)據(jù)庫用一種基于概率的方法進行分類，使得相似的列在一起的可能性更大，不相似的列在一起的可能性較小。我們再對這兩個方法比擬一下。MH的遺漏率為零，錯誤率可

11、以由k嚴格控制，但是時空效率相對的較差。LSH的遺漏率和錯誤率是無法同時降低的，但是它的時空效率卻相對的好很多。所以應(yīng)該視具體的情況而定。這種方法能產(chǎn)生一些有用的規(guī)那么。(四)、多層和多維關(guān)聯(lián)規(guī)那么的挖掘1、多層關(guān)聯(lián)規(guī)那么：對于很多的應(yīng)用來說，由于數(shù)據(jù)分布的分散性，所以很難在數(shù)據(jù)最細節(jié)的層次上發(fā)現(xiàn)一些強關(guān)聯(lián)規(guī)那么。當(dāng)我們引入概念層次后，就可以在較高的層次上進行挖掘。雖然較高層次上得出的規(guī)那么可能是更普通的信息，但是對于一個用戶來說是普通的信息，對于另一個用戶卻未必如此。所以數(shù)據(jù)挖掘應(yīng)該提供這樣一種在多個層次上進行挖掘的功能。1)分類：根據(jù)規(guī)那么中涉及到的層次，多層關(guān)聯(lián)規(guī)那么可以分為同層和層間關(guān)

12、聯(lián)規(guī)那么。2)挖掘方法：多層關(guān)聯(lián)規(guī)那么的挖掘根本上可以沿用支持度-可信度;的框架。一般可采用自頂向下策略，由概念層1開始向下，到較低的更特定的概念層，在每個概念層累加計數(shù)計算頻繁項集，如此下去。對每一層可以使用發(fā)現(xiàn)頻繁項集的任何算法，Apriori或它的變形。只不過，在支持度設(shè)置的問題上有一些要考慮的東西。同層關(guān)聯(lián)規(guī)那么可以采用兩種支持度策略：統(tǒng)一的最小支持度。對于不同的層次，都使用同一個最小支持度閾值。這樣對于用戶和算法實現(xiàn)來說都比擬的容易，但是弊端也是顯然的：較低層次抽象地項不大可能像較高層次抽象的項出現(xiàn)得那么頻繁。如果最小支持度閾值設(shè)置太高，可能丟掉出現(xiàn)在較低抽象層中有意義的關(guān)聯(lián)規(guī)那么。

13、如果設(shè)置太低，可能會產(chǎn)生出現(xiàn)在較高抽象層的無興趣的關(guān)聯(lián)規(guī)那么。遞減的最小支持度。每個層次都有不同的最小支持度閾值，較低層次的最小支持度相對較小?？捎玫乃阉鞑呗裕篈、逐層獨立：這是完全的寬度搜索，沒有頻繁項集的背景知識用于剪枝?？疾烀恳粋€節(jié)點，不管它的父結(jié)點是否是頻繁的。B、層交叉用單項過濾：一個第i層的項被考察，當(dāng)且僅當(dāng)它在第(i-1)層的父結(jié)點是頻繁的。C、層交叉用k-項集過濾：一個第i層的k-項集被考察，當(dāng)且僅當(dāng)它在第(i-1)層的父結(jié)點k-項集是頻繁的。層間關(guān)聯(lián)規(guī)那么考慮最小支持度的時，應(yīng)該根據(jù)較低層次的最小支持度來定。2、多維關(guān)聯(lián)規(guī)那么：在挖掘維間關(guān)聯(lián)規(guī)那么和混合維關(guān)聯(lián)規(guī)那么的時候，還

14、要考慮不同的字段種類：種類型和數(shù)值型。1)對于種類型的字段，原先的算法都可以處理。2)對于數(shù)值型的字段，需要進行一定的處理之后才可以進行。處理數(shù)值型字段的方法根本上有以下幾種：數(shù)值字段被分成一些預(yù)定義的層次結(jié)構(gòu)。這些區(qū)間都是由用戶預(yù)先定義的。得出的規(guī)那么也叫做靜態(tài)數(shù)量關(guān)聯(lián)規(guī)那么。數(shù)值字段根據(jù)數(shù)據(jù)的分布分成了一些布爾字段。論文格式。每個布爾字段都表示一個數(shù)值字段的區(qū)間，落在其中那么為1，反之為0。這種分法是動態(tài)的。得出的規(guī)那么叫布爾數(shù)量關(guān)聯(lián)規(guī)那么。數(shù)值字段被分成一些能表達它含義的區(qū)間。它考慮了數(shù)據(jù)之間的距離的因素。得出的規(guī)那么叫基于距離的關(guān)聯(lián)規(guī)那么。直接用數(shù)值字段中的原始數(shù)據(jù)進行分析。使用一些統(tǒng)

15、計的方法對數(shù)值字段的值進行分析，并且結(jié)合多層關(guān)聯(lián)規(guī)那么的概念，在多個層次之間進行比擬從而得出一些有用的規(guī)那么。得出的規(guī)那么叫多層數(shù)量關(guān)聯(lián)規(guī)那么。五、實際情況解決1、辛普森悖論Simpcnsparadox在某些情況下，隱藏變量可能會導(dǎo)致一對變量間的聯(lián)系消失或逆轉(zhuǎn)方向。解決方法：采取適當(dāng)分層，考慮隱含變量的影響。2、傾斜支持度分布的影響在某些情況下，數(shù)據(jù)集的大多數(shù)項具有較低的或中等頻度，但少數(shù)項具有很高的頻率，此時如果把最小支持度閾值設(shè)置過高，那么包含進去的項偏少；如果設(shè)置過低，那么頻繁集過多，也會出現(xiàn)虛假設(shè)交叉支持模式。1)交叉支持模式：是一個項集 ，它的支持度比率 小于用戶指定的閾值 。2)檢

16、查交叉支持模式：通過提取 產(chǎn)生的所有規(guī)那么中最低置信度規(guī)那么的方法來檢查最低置信度規(guī)那么的左邊只包含一個項，即令 那么規(guī)那么 的置信度最低。 ，由于 那么：假設(shè) ，那么該模式不是交叉支持模式，假設(shè) ，那么該模式是交叉支持模式。三、結(jié)論與展望本文討論了數(shù)據(jù)挖掘中產(chǎn)生關(guān)聯(lián)規(guī)那么的方法以及它的應(yīng)用，這方面一些研究成果已取得很大的成績，并已被集成在一些系統(tǒng)中，如IBM的Quest工程，SimonFarse大學(xué)的DBMiner等。具體的內(nèi)容有經(jīng)典頻集算法，對頻集算法的優(yōu)化，擴展。對于關(guān)聯(lián)規(guī)那么的開展，可以在下面一些方向上進行近一步的深入研究。在處理極大量的數(shù)據(jù)時，如何提高算法效率的問題；對于挖掘迅速更新的數(shù)據(jù)的挖掘算法的進一步