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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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