基于Apriori性質(zhì)的多維關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘

1、基于Apriori性質(zhì)的多維關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘 匯報人：王雷背景知識 關(guān)于數(shù)據(jù)挖掘 關(guān)聯(lián)規(guī)則及Apriori算法數(shù)據(jù)挖掘是一項從大量的記錄數(shù)據(jù)中提取有價值的、人們感興趣的知識，這些知識是隱含的、事先未知的有用信息，提取的知識一般可表示為概念(Concepts)、規(guī)則(Rules)、規(guī)律(Regular ides)、模式(Patterns)等形式。關(guān)聯(lián)規(guī)則是當(dāng)前數(shù)據(jù)挖掘研究的主要方法之一，側(cè)重于確定數(shù)據(jù)中不同領(lǐng)域之間的聯(lián)系，找出滿足給定支持度和可信度閾值的多個域之間的依賴關(guān)系 。例：在銷售手機的商店中，70%的包含手機的交易中包含充電器,在所有交易中，有56%同時包含這兩種物品。 于是規(guī)則表示為手

2、機 充電器 （可信度70%，支持度56%）關(guān)聯(lián)規(guī)則的基本概念 設(shè) 是項的集合，設(shè)任務(wù)相關(guān)的數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合，其中每個事物T是項的集合，使得 每一個事務(wù)有一個標(biāo)識符TID，設(shè)A是一個項集，事務(wù)T包含A當(dāng)且僅當(dāng) 。關(guān)聯(lián)規(guī)則是形如 的蘊涵式，其中 ， 并且規(guī)則在事務(wù)D中成立具有支持度S和置信度C, 把滿足最小支持度閾值和最小置信度閾值的規(guī)則成為強規(guī)則。項的集合稱為項集（itemset），包含K個項集稱為K項集，如果項集滿足最小支持度，則稱它為頻繁項集。12, .mIiiiTIATABAIBIsupport(AB)=P(AB)confidence(AB)=P(B|A) 關(guān)聯(lián)規(guī)則的挖掘是一個兩步

3、的過程： 1、找出所有頻繁項集 2、由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則，根據(jù)定義，這些規(guī)則必須滿足最小支持度和最小置信度。Apriori算法Apriori算法是最有影響的關(guān)聯(lián)規(guī)則挖掘算法之一。它的中心思想是首先通過對事務(wù)數(shù)據(jù)庫進(jìn)行掃描,找出支持度不小于最小支持度的所有項目,即頻繁1 - 項集. 接下來的工作是循環(huán)的,每次循環(huán)分2步進(jìn)行: 1)連接，對頻繁k - 項集中的項進(jìn)行連接. 2)減枝，在減枝這一步主要根據(jù)一個頻繁項目集的任何一個子集都應(yīng)該是頻繁的這一思想對連接后的項目集進(jìn)行篩選,刪除那些子集不是頻繁集的項目集,得出候選( k + 1) - 項集.即 對數(shù)據(jù)庫進(jìn)行掃描, 計算候選項的支持度,從候選

4、集中刪除支持度小于最小支持度的候選項, 進(jìn)而得出頻繁( k + 1) - 項集. 循環(huán)的終止條件是頻繁k - 項集為空, 也就是說再也找不出相關(guān)聯(lián)的項目了.舉例說明Aporiori算法TID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5數(shù)據(jù)庫 Ditemset sup.1223334153itemset sup.12233353掃描 DC1L1itemset1 21 31 52 32 53 5itemset sup1 211 321 512 322 533 52itemset sup1 322 322 533 52L2C2C2掃描 DC3L3itemset

5、2 3 5掃描 Ditemset sup2 3 52Apriori性質(zhì) 頻繁項集的所有非空子集也是頻繁的 例如：如果AB 是頻繁項目集，則 A B 也一定是頻繁項目集加權(quán)關(guān)聯(lián)規(guī)則挖掘 傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法通常都認(rèn)為數(shù)據(jù)庫里每個項目都有相同的重要性，沒有主要、次要之分。但在實際中，往往存在一類這樣的情況：用戶對每個項目的看重程度不一樣，有的項目是用戶最看重、最關(guān)心的，有的項目是用戶關(guān)注性不大，因此需要引進(jìn)權(quán)重的概念。加權(quán)關(guān)聯(lián)規(guī)則的描述 設(shè) 是項的集合，每個項都有一個權(quán)值與之對應(yīng)。它們的權(quán)值分別是w1,w2,wk（wi 0,1）。事先指定最小加權(quán)支持度閾值為 wminsup和最小置信度閾值 mi

6、nconf。對于項目集X，如果 wsup(X)wminsup，則 X 是加權(quán)頻繁的。形如X Y 的關(guān)聯(lián)規(guī)則的加權(quán)支持度為： 置 信 度 的 定 義 仍 然 沿 用 Apriori算 法 里 的 定 義 ， 即 ：conf (X Y) = sup(X Y)/sup(X ) 。12 ,. mIi iisup(sup()wportwport XY加權(quán)關(guān)聯(lián)規(guī)則的描述對于項目集 X、Y， ，X Y = ，如果有 wsup( X Y )wminsup，且 conf(XY)minconf，則稱 XY 是一條加權(quán)關(guān)聯(lián)規(guī)則。XYI、權(quán)值的設(shè)定加權(quán)支持度 (1)、平均值： (2)、歸一化： (3)、最大值： 11

7、sup( )()sup( )kjjwxwxk12sup( )max,.sup( )kwxw wwx121/(.)sup( )sup( )/iikkjjwwwwwwxwxn令則想法 (1) 先不考慮項目的權(quán)值，利用傳統(tǒng)的 Apriori 算法找出支持度不小于最小加權(quán)支持度的所有的頻繁項目集。由于項目集的權(quán)值小于 1，所以項目集的加權(quán)支持度一定小于支持度，所以生成的頻繁集一定是加權(quán)頻繁集的超集。 (2) 計算所生成頻繁項目集中所有項目集的加權(quán)支持度，并把加權(quán)支持度小于最小加權(quán)支持度的項目集刪除，從而得到所有加權(quán)頻繁集。 (3) 利用加權(quán)頻繁集來生成所有的加權(quán)關(guān)聯(lián)規(guī)則。Apriori的瓶頸Aprio

8、ri算法的核心: 用頻繁的(k 1)-項集生成候選的頻繁 k-項集 用數(shù)據(jù)庫掃描和模式匹配計算候選集的支持度Apriori 的瓶頸: 候選集生成 巨大的候選集: 104 個頻繁1-項集要生成 107 個候選 2-項集 要找尺寸為100的頻繁模式，如 a1, a2, ,a100, 你必須先產(chǎn)生2100 1030 個候選集 多次掃描數(shù)據(jù)庫： 如果最長的模式是n的話，則需要 (n +1 ) 次數(shù)據(jù)庫掃描提高Apriori效率的方法事務(wù)壓縮: 不包含任何頻繁k-項集的交易也不可能包含任何大于k的頻繁集基于劃分: 一個項集要想在整個數(shù)據(jù)庫中是頻繁的，那么他至少在數(shù)據(jù)庫的一個分割上是頻繁的。采樣: 在給定

9、數(shù)據(jù)的子集上挖掘，使用小的支持度+完整性驗證方法動態(tài)項集計數(shù): 在添加一個新的候選集之前，先估計一下是不是他的所有子集都是頻繁的?；诠１淼乃惴ń窈蟮墓ぷ?加權(quán)關(guān)聯(lián)規(guī)則挖掘算法的研究，項目屬性加權(quán)后，Apriori性質(zhì)不再適用，算法如何優(yōu)化。參考文獻(xiàn)1 范明，孟小峰等譯.數(shù)據(jù)挖掘：概念與技術(shù).北京：機械工業(yè)出版社，2001.2 Agrawal R, Srikant R. Fast Algorithms for Mining Association Rules. In: Proc of 1994 Int1Conf of Very Large Data Base. Santiago, Chili: VLDB Endowment, 1994, 487499.3胡和平, 路松峰. 加權(quán)關(guān)聯(lián)規(guī)則的開采. 小型微型計算機系統(tǒng),2001,22(3): 347375.4張文獻(xiàn), 陸建江. 加權(quán)布爾型關(guān)聯(lián)規(guī)則的研究. 計算機工程, 2003, 29(9): 5557.5張智軍, 方穎, 許云濤. 基于Apriori算法的水平加權(quán)關(guān)聯(lián)規(guī)則挖掘. 計算機工程與應(yīng)用,2003, 39(14): 197199.6 R. Agrawal, et al. Mining association rules between sets of items in lage