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

1、關(guān)聯(lián)規(guī)那么挖掘算法綜述論文導(dǎo)讀：一個(gè)大型數(shù)據(jù)庫,其各個(gè)字段之間存在著各種各樣的關(guān)系,這些關(guān)系就隱含在數(shù)據(jù)庫所包含的數(shù)據(jù)中,關(guān)聯(lián)規(guī)那么挖掘的目的是找出這些隱藏的關(guān)聯(lián)。4頻繁項(xiàng)集：支持度不小于用戶給定的最小支持度的項(xiàng)集。Apriori性質(zhì)：頻繁項(xiàng)集的所有非空子集都必須也是頻繁的。通過實(shí)驗(yàn)可以發(fā)現(xiàn)尋找頻繁集主要的計(jì)算是在生成頻繁2-項(xiàng)集Lk上，Park等就是利用了這個(gè)性質(zhì)引入hash技術(shù)來改良產(chǎn)生頻繁2-項(xiàng)集的方法。的置信度最低。關(guān)鍵詞：關(guān)聯(lián)規(guī)那么,頻繁集,Apriori,FP-tree,支持度,置信度一、關(guān)聯(lián)規(guī)那么挖掘簡(jiǎn)介一個(gè)大型數(shù)據(jù)庫,其各個(gè)字段之間存在著各種各樣的關(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個(gè)不同的工程組成的集合,給定一個(gè)事務(wù)數(shù)據(jù)庫D,其中的每一個(gè)事務(wù)T是I中一組工程的集合,即 ,T有唯一的標(biāo)識(shí)符TID.一條關(guān)聯(lián)規(guī)那么就是一個(gè)形如 的蘊(yùn)含式,其中, 。關(guān)聯(lián)規(guī)那么 成立的條件是：它具有支持度S,即事務(wù)數(shù)據(jù)庫D中至少有S%的事務(wù)包含XY；它具有置信度C，即在事務(wù)數(shù)據(jù)庫D所包含X的事務(wù)中,至少有C%的事務(wù)同時(shí)也包含Y，關(guān)聯(lián)規(guī)那么的挖掘問題就是在事務(wù)數(shù)據(jù)庫D中找出具有用戶給定的最小支持度 和最小置信度 的關(guān)聯(lián)規(guī)那么。2、根

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

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

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

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

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

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

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

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

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

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

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

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

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

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