數(shù)據(jù)倉庫與數(shù)據(jù)挖掘基礎(chǔ)第6章關(guān)聯(lián)規(guī)則趙志升

1、1、關(guān)聯(lián)規(guī)則挖掘2、挖掘事務(wù)數(shù)據(jù)庫的單維布爾關(guān)聯(lián)規(guī)則3、挖掘事務(wù)數(shù)據(jù)庫的多層關(guān)聯(lián)規(guī)則4、挖掘關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫的多維關(guān)聯(lián)規(guī)則5、由關(guān)聯(lián)挖掘到相關(guān)分析,第六章 挖掘大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則,關(guān)聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數(shù)據(jù)中項(xiàng)集之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系。 從大量商務(wù)事務(wù)記錄中發(fā)現(xiàn)有趣的關(guān)聯(lián)關(guān)系，可以幫助許多商務(wù)決策的制定，如分類設(shè)計(jì)、交叉購物和賤賣分析。 關(guān)聯(lián)規(guī)則挖掘的一個(gè)典型的例子是購物籃分析。,第六章 挖掘大型數(shù)據(jù)庫中的

2、關(guān)聯(lián)規(guī)則,第一節(jié) 關(guān)聯(lián)規(guī)則挖掘,1、購物籃分析,問題：什么商品組或集合顧客多半會(huì)在一次購物時(shí)同時(shí)購買？ 回答：需要分析商店的顧客事務(wù)零售數(shù)據(jù)，并在其上運(yùn)行購物籃分析。 分析的結(jié)果可以用于市場(chǎng)規(guī)劃、廣告策劃、分類設(shè)計(jì)。例如，購物籃分析可以幫助經(jīng)理設(shè)計(jì)不同的商店布局，以及規(guī)劃什么商品降價(jià)。,第一節(jié) 關(guān)聯(lián)規(guī)則挖掘,1、購物籃分析 策略一：經(jīng)常購買的商品可以放近一些，以便進(jìn)一步刺激這些商品一起銷售。 策略二：將經(jīng)常購買的商品放

3、在商店的兩端，可能誘發(fā)買這些商品的顧客一路挑選其他商品。,第一節(jié) 關(guān)聯(lián)規(guī)則挖掘,1、購物籃分析 可以想象全域是商店中可利用的商品的集合，則每鐘商品有一個(gè)布爾變量，表示該商品的有無。每個(gè)籃子可以用一個(gè)布爾向量表示。可以分析布爾向量，得到反映商品頻繁關(guān)聯(lián)或同時(shí)購買的購買模式。 這些模式可以用關(guān)聯(lián)規(guī)則的形式表示：,第一節(jié) 關(guān)聯(lián)規(guī)則挖掘,1、購物籃分析 規(guī)則的支持度和置信度是兩個(gè)規(guī)則興趣度度量，反映規(guī)則的有用性和確定性，上述規(guī)則

4、的支持度2%意味分析中的全部事務(wù)的2%同時(shí)購買計(jì)算機(jī)和操作系統(tǒng)軟件。置信度60%意味購買計(jì)算機(jī)的顧客60%也購買操作系統(tǒng)軟件。 關(guān)聯(lián)規(guī)則被認(rèn)為是有趣的，如果它滿足最小支持度閾值和最小置信度閾值。這些閾值可由用戶和領(lǐng)域?qū)＜以O(shè)定。,第一節(jié) 關(guān)聯(lián)規(guī)則挖掘,2、基本概念 設(shè)I={i1，i2，…，im}是項(xiàng)的集合，。設(shè)任務(wù)相關(guān)的數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合，其中每個(gè)事務(wù)T是項(xiàng)的集合，使得T?I。每一個(gè)事務(wù)有一個(gè)標(biāo)識(shí)符TID。設(shè)A是一個(gè)項(xiàng)

5、集，事務(wù)T包含A，當(dāng)且僅當(dāng)A?T。關(guān)聯(lián)規(guī)則是形如A?B的蘊(yùn)涵式，其中A?I， B?I，且A?B=Ø。,第一節(jié) 關(guān)聯(lián)規(guī)則挖掘,2、基本概念 項(xiàng)的集合稱為項(xiàng)集，包含K個(gè)項(xiàng)的項(xiàng)集稱為K-項(xiàng)集。集合{computer，software}是一個(gè)2-項(xiàng)集。項(xiàng)集的出現(xiàn)頻率是包含項(xiàng)集的事務(wù)數(shù)簡(jiǎn)稱為頻率、支持計(jì)數(shù)或計(jì)數(shù)。 項(xiàng)集滿足最小支持度，若項(xiàng)集的出現(xiàn)頻率大于或等于最小支持度與D中事務(wù)總數(shù)的乘積。 如果項(xiàng)集滿足最小支持度，則稱它為頻繁

6、項(xiàng)集。,第一節(jié) 關(guān)聯(lián)規(guī)則挖掘,2、基本概念 關(guān)聯(lián)規(guī)則的挖掘包含兩個(gè)基本步驟： 找出所有頻繁項(xiàng)集：這些項(xiàng)集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持計(jì)數(shù)一樣。 由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則：這些規(guī)則必須滿足最小支持度和最小置信度。挖掘關(guān)聯(lián)規(guī)則的總體性能由第一步?jīng)Q定。,第一節(jié) 關(guān)聯(lián)規(guī)則挖掘,3、關(guān)聯(lián)規(guī)則挖掘的分類標(biāo)準(zhǔn) 購物籃分析只是關(guān)聯(lián)規(guī)則挖掘的一種形式。根據(jù)下列標(biāo)準(zhǔn)，關(guān)聯(lián)規(guī)則有多種分類方法： 根據(jù)規(guī)則中所處理的值

7、的類型：若規(guī)則考慮項(xiàng)的在與不在，則它是布爾關(guān)聯(lián)規(guī)則；若規(guī)則描述的是量化的項(xiàng)或?qū)傩灾g的關(guān)聯(lián)，則它是量化關(guān)聯(lián)規(guī)則。如，下列為一個(gè)量化關(guān)聯(lián)規(guī)則：,第一節(jié) 關(guān)聯(lián)規(guī)則挖掘,3、關(guān)聯(lián)規(guī)則挖掘的分類標(biāo)準(zhǔn) 根據(jù)規(guī)則中涉及的數(shù)據(jù)維：若關(guān)聯(lián)規(guī)則中的項(xiàng)或?qū)傩悦總€(gè)只涉及一個(gè)維，則它是單維關(guān)聯(lián)規(guī)則；若關(guān)聯(lián)規(guī)則涉及兩個(gè)或多個(gè)維，則它是多維關(guān)聯(lián)規(guī)則。如,第一節(jié) 關(guān)聯(lián)規(guī)則挖掘,3、關(guān)聯(lián)規(guī)則挖掘的分類標(biāo)準(zhǔn) 根據(jù)規(guī)則集所涉及的抽象層：有些挖掘關(guān)聯(lián)規(guī)則的方法可

8、以在不同的抽象層發(fā)現(xiàn)規(guī)則。如，,第一節(jié) 關(guān)聯(lián)規(guī)則挖掘,購買的商品涉及不同的抽象層，稱所挖掘的規(guī)則集由多層關(guān)聯(lián)規(guī)則組成。否則，規(guī)則只涉及單一抽象層的項(xiàng)或?qū)傩?，則該集合包含單層關(guān)聯(lián)規(guī)則。,3、關(guān)聯(lián)規(guī)則挖掘的分類標(biāo)準(zhǔn) 根據(jù)關(guān)聯(lián)規(guī)則的各種擴(kuò)充：關(guān)聯(lián)規(guī)則可以擴(kuò)充到相關(guān)分析，以識(shí)別項(xiàng)是否相關(guān)。用最大模式（最大的頻繁模式）或頻繁閉項(xiàng)集顯著壓縮挖掘所產(chǎn)生的頻繁項(xiàng)集數(shù)。,第一節(jié) 關(guān)聯(lián)規(guī)則挖掘,第二節(jié) 挖掘事務(wù)數(shù)據(jù)庫的單維布爾關(guān)聯(lián)規(guī)則,1、Apr

9、iori算法 Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法，通過侯選項(xiàng)集找頻繁項(xiàng)集。基本思路： Apriori使用一種稱作逐層搜索的迭代方法，K-項(xiàng)集用于探索（K+1）-項(xiàng)集。首先，找出頻繁1-項(xiàng)集的集合，記為L(zhǎng)1； L1用于找頻繁2-項(xiàng)集的集合L2 ，而L2用于找L3，如此下去，直到找到頻繁K-項(xiàng)集。找每個(gè)LK需要一次數(shù)據(jù)庫掃描。其過程包括：連接和剪枝兩個(gè)方面。,第二節(jié) 挖掘事務(wù)數(shù)據(jù)庫的單維布爾關(guān)

10、聯(lián)規(guī)則,1、Apriori算法 例如，設(shè)已有包含9個(gè)事務(wù)的事務(wù)數(shù)據(jù)庫，即|D|=9，各事務(wù)按字典次序存放，設(shè)最小事務(wù)支持度計(jì)數(shù)為2 。,第二節(jié) 挖掘事務(wù)數(shù)據(jù)庫的單維布爾關(guān)聯(lián)規(guī)則,1、Apriori算法,侯選集C1,頻繁集L1,,,掃描D，對(duì)每個(gè)侯選1-項(xiàng)集計(jì)數(shù),比較侯選支持度計(jì)數(shù)與最小支持度計(jì)數(shù),設(shè)最小事務(wù)支持度計(jì)數(shù)為2，2/9=22%,第二節(jié) 挖掘事務(wù)數(shù)據(jù)庫的單維布爾關(guān)聯(lián)規(guī)則,1、Apriori算法,,,由L1產(chǎn)

11、生侯選2-項(xiàng)集C2,掃描D，對(duì)每個(gè)侯選2-項(xiàng)集計(jì)數(shù)C2,第二節(jié) 挖掘事務(wù)數(shù)據(jù)庫的單維布爾關(guān)聯(lián)規(guī)則,1、Apriori算法,,,由L2?L2,比較侯選支持度計(jì)數(shù)與最小支持度計(jì)數(shù)，得到頻繁項(xiàng)集L2,第二節(jié) 挖掘事務(wù)數(shù)據(jù)庫的單維布爾關(guān)聯(lián)規(guī)則,1、Apriori算法,,,掃描D，對(duì)每個(gè)侯選3-項(xiàng)集計(jì)數(shù)C3,由L2產(chǎn)生侯選3-項(xiàng)集C3,比較侯選支持度計(jì)數(shù)與最小支持度計(jì)數(shù)，得到L3,,由于L3?L3產(chǎn)生的C4={{I1，I2，I3，I5}}的子

12、集{I2，I3，I5}不是頻繁的，所以C4=Ø，算法終止。,第二節(jié) 挖掘事務(wù)數(shù)據(jù)庫的單維布爾關(guān)聯(lián)規(guī)則,2、由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則 一旦由數(shù)據(jù)庫D中的事務(wù)找出頻繁項(xiàng)集，由它們可以產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則（滿足最小支持度和最小置信度）。對(duì)于置信度，可以用項(xiàng)集支持度計(jì)數(shù)表示：其中，Support_count(A?B)是包含項(xiàng)集A?B的事務(wù)數(shù)， Support_count(A)是包含項(xiàng)集A的事務(wù)數(shù)。,第二節(jié) 挖掘事務(wù)數(shù)據(jù)

13、庫的單維布爾關(guān)聯(lián)規(guī)則,2、由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則 可以產(chǎn)生關(guān)聯(lián)規(guī)則如下： 對(duì)于每個(gè)頻繁集l，產(chǎn)生l的所有非空子集； 對(duì)于l的每個(gè)非空子集s；若則輸出規(guī)則：s?(l-s)。其中min_confidence是最小置信度閾值。,第二節(jié) 挖掘事務(wù)數(shù)據(jù)庫的單維布爾關(guān)聯(lián)規(guī)則,2、由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則 例如，按照前例的事務(wù)數(shù)據(jù)庫，設(shè)數(shù)據(jù)包含頻繁項(xiàng)集l={I1，I2，I5}，則l的非空子集有：{I1，I2}， {I1，

14、I5} ， {I2，I5} ， {I1} ， {I2} ， {I5}。可得到關(guān)聯(lián)規(guī)則如：,第二節(jié) 挖掘事務(wù)數(shù)據(jù)庫的單維布爾關(guān)聯(lián)規(guī)則,2、由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則 如果最小置信度預(yù)值為70%，則規(guī)則2、3和6可以輸出，因?yàn)檫@些規(guī)則滿足強(qiáng)關(guān)聯(lián)規(guī)則條件。,第二節(jié) 挖掘事務(wù)數(shù)據(jù)庫的單維布爾關(guān)聯(lián)規(guī)則,3、冰山查詢 冰山查詢?cè)跀?shù)據(jù)挖掘中經(jīng)常使用，特別是對(duì)購物籃分析，apriori算法可以用來提高冰山查詢的效率。冰山查詢（

15、iceberg query）在一個(gè)屬性或?qū)傩约嫌?jì)算一個(gè)聚集函數(shù)，以找出大于某個(gè)指定閾值的聚集值。,第二節(jié) 挖掘事務(wù)數(shù)據(jù)庫的單維布爾關(guān)聯(lián)規(guī)則,3、冰山查詢 給定關(guān)系R，它具有屬性a_1， a_2，…， a_n和b，一個(gè)聚集函數(shù)agg_fuc，冰山查詢形如：Select R. a_1， R. a_2， …，R. a_n，agg_fuc(R. b)From relation RGr

16、oup by R. a_1， R. a_2， …，R. a_nHaving agg_fuc(R. b)>=threshold給定大量輸入元組，滿足having子句中閾值的輸出元組數(shù)量相對(duì)很少。輸入數(shù)據(jù)集為“冰山”，輸出結(jié)果為“冰山頂”。,第二節(jié) 挖掘事務(wù)數(shù)據(jù)庫的單維布爾關(guān)聯(lián)規(guī)則,3、冰山查詢 例，設(shè)給定銷售數(shù)據(jù)，期望產(chǎn)生一個(gè)顧客-商品對(duì)的列表，要求這些顧客購買商品數(shù)量達(dá)到5件或更多，則冰山查

17、詢表示如：Select P. cust_ID， P. item_ID ，SUM(P. qty)From Purchases P Group by P. cust_ID， P. item_ID Having SUM(P. qty) >=5,第二節(jié) 挖掘事務(wù)數(shù)據(jù)庫的單維布爾關(guān)聯(lián)規(guī)則,3、冰山查詢 可以采用apriori算法，不考慮每個(gè)顧客購買的每種

18、商品的數(shù)量，按照以下步驟： 產(chǎn)生cust_list，總共購買5件以上商品的顧客表： Select P. cust_ID From Purchases P Group by P. cust_ID Having SUM(P. qty) >=5,第二節(jié) 挖掘事務(wù)數(shù)據(jù)庫的單維布爾關(guān)聯(lián)規(guī)則,3、冰山查詢

19、 可以采用apriori算法，不考慮每個(gè)顧客購買的每種商品的數(shù)量，按照以下步驟： 產(chǎn)生item_list，被顧客購買數(shù)量5件以上商品表： Select P. item_ID From Purchases P Group by P. item _ID Having SUM(P. qty) >

20、;=5,第三節(jié) 挖掘事務(wù)數(shù)據(jù)庫的多層關(guān)聯(lián)規(guī)則,1、多層關(guān)聯(lián)規(guī)則 由于許多應(yīng)用環(huán)境下，多維數(shù)據(jù)空間數(shù)據(jù)的稀疏性，在低層或原始層的數(shù)據(jù)項(xiàng)之間很難找出強(qiáng)關(guān)聯(lián)規(guī)則。而在較高的概念層尋找強(qiáng)關(guān)聯(lián)規(guī)則可以得到具有普遍意義的知識(shí)。對(duì)于某用戶代表普遍意義的知識(shí)，對(duì)另一用戶可能是新穎的。所以，DMS應(yīng)當(dāng)提供一種能力，在多個(gè)抽象層挖掘關(guān)聯(lián)規(guī)則，并容易在不同的抽象空間轉(zhuǎn)換。,第三節(jié) 挖掘事務(wù)數(shù)據(jù)庫的多層關(guān)聯(lián)規(guī)則,1、多層關(guān)聯(lián)規(guī)則

21、 例如，給定某事務(wù)的任務(wù)相關(guān)數(shù)據(jù)集D，它是計(jì)算機(jī)部的銷售數(shù)據(jù)，對(duì)每個(gè)事務(wù)TID給出了購買的商品。,第三節(jié) 挖掘事務(wù)數(shù)據(jù)庫的多層關(guān)聯(lián)規(guī)則,1、多層關(guān)聯(lián)規(guī)則商品的概念分層如：,第三節(jié) 挖掘事務(wù)數(shù)據(jù)庫的多層關(guān)聯(lián)規(guī)則,1、多層關(guān)聯(lián)規(guī)則 概念分層定義了由低層概念到更一般的高層概念的映射序列，可以通過將數(shù)據(jù)內(nèi)的低層概念用概念分層的高層概念替換，對(duì)數(shù)據(jù)概化。例中概念分層為4層，記為0，1，2和3。 在最低的原始層很難

22、找出有趣的購買模式，如{IBM臺(tái)式機(jī)，HP激光打印機(jī)}不太可能滿足最小支持度。而{計(jì)算機(jī)，打印機(jī)}更容易滿足最小支持度。,第三節(jié) 挖掘事務(wù)數(shù)據(jù)庫的多層關(guān)聯(lián)規(guī)則,2、挖掘多層關(guān)聯(lián)規(guī)則的方法 問題：如何使用概念分層有效挖掘多層關(guān)聯(lián)規(guī)則?？疾煲恍┗谥С侄?置信度框架的方法。 對(duì)于所有層使用一致的最小支持度 在較低層使用遞減的最小支持度 逐層獨(dú)立 層交叉單項(xiàng)過濾 層交叉K-項(xiàng)集過濾,第三節(jié) 挖掘事務(wù)數(shù)據(jù)庫的多層關(guān)聯(lián)規(guī)

23、則,2、挖掘多層關(guān)聯(lián)規(guī)則的方法 對(duì)于所有層使用一致的最小支持度：在每一層挖掘時(shí)，使用相同的最小支持度閾值。如整個(gè)使用最小支持度閾值5%。,第三節(jié) 挖掘事務(wù)數(shù)據(jù)庫的多層關(guān)聯(lián)規(guī)則,2、挖掘多層關(guān)聯(lián)規(guī)則的方法 在較低層使用遞減的最小支持度：在每個(gè)抽象層有自己的最小支持度閾值。抽象層越低，對(duì)應(yīng)的閾值越小。如層1和層2的最小支持度閾值分別為5%和3%。,第三節(jié) 挖掘事務(wù)數(shù)據(jù)庫的多層關(guān)聯(lián)規(guī)則,2、挖掘多層關(guān)聯(lián)規(guī)則的方法 逐層獨(dú)立：完全的寬

24、度搜索，沒有頻繁項(xiàng)集的背景知識(shí)用于剪枝?？疾烀總€(gè)節(jié)點(diǎn)，不管它的父節(jié)點(diǎn)是否是頻繁的。,第三節(jié) 挖掘事務(wù)數(shù)據(jù)庫的多層關(guān)聯(lián)規(guī)則,2、挖掘多層關(guān)聯(lián)規(guī)則的方法 層交叉單項(xiàng)過濾：一個(gè)第i層的項(xiàng)被考察，當(dāng)且僅當(dāng)它在第（i-1）層的父節(jié)點(diǎn)是頻繁的。根據(jù)遞減支持度，如果父節(jié)點(diǎn)是頻繁的，它的子女將被考察；否則，它的子孫將由搜索中剪枝。,第三節(jié) 挖掘事務(wù)數(shù)據(jù)庫的多層關(guān)聯(lián)規(guī)則,2、挖掘多層關(guān)聯(lián)規(guī)則的方法 層交叉k-項(xiàng)集過濾：一個(gè)第i層的k-項(xiàng)集被考察，

25、當(dāng)且僅當(dāng)它在第（i-1）層的對(duì)應(yīng)父節(jié)點(diǎn)k-項(xiàng)集是頻繁的。,第三節(jié) 挖掘事務(wù)數(shù)據(jù)庫的多層關(guān)聯(lián)規(guī)則,2、挖掘多層關(guān)聯(lián)規(guī)則的方法 逐層獨(dú)立策略的條件寬松，而層交叉k-項(xiàng)集過濾策略的限制太強(qiáng)，層交叉單項(xiàng)過濾策略是一個(gè)折衷。進(jìn)一步改進(jìn)為受控層交叉單項(xiàng)過濾策略。通過設(shè)置一個(gè)層傳遞閾值，用于向較低層“傳遞”相對(duì)頻繁的項(xiàng)。,第三節(jié) 挖掘事務(wù)數(shù)據(jù)庫的多層關(guān)聯(lián)規(guī)則,2、挖掘多層關(guān)聯(lián)規(guī)則的方法 受控的層交叉單項(xiàng)過濾策略：如果滿

26、足層傳遞閾值，則允許考察不滿足最小支持度閾值項(xiàng)的子女。,第三節(jié) 挖掘事務(wù)數(shù)據(jù)庫的多層關(guān)聯(lián)規(guī)則,2、挖掘多層關(guān)聯(lián)規(guī)則的方法 交叉層關(guān)聯(lián)規(guī)則：規(guī)則中的項(xiàng)不屬于同一概念層，挖掘交叉層i與j層關(guān)聯(lián)規(guī)則應(yīng)當(dāng)使用較低層j的最小支持度閾值，使得j層的項(xiàng)可以包含在分析中。 前面所討論的5種方法屬于發(fā)現(xiàn)的頻繁項(xiàng)集的所有項(xiàng)都屬于同一概念層1層。如 計(jì)算機(jī)?軟件 或 臺(tái)式機(jī)?彩色打印機(jī)對(duì)于不屬于同一

27、概念層（1層和2層）的規(guī)則： 計(jì)算機(jī)?彩色打印機(jī),第三節(jié) 挖掘事務(wù)數(shù)據(jù)庫的多層關(guān)聯(lián)規(guī)則,3、檢查冗余的多層關(guān)聯(lián)規(guī)則 概念分層在數(shù)據(jù)挖掘中允許不同的抽象層的知識(shí)發(fā)現(xiàn)，如多層關(guān)聯(lián)規(guī)則。然而，當(dāng)挖掘多層關(guān)聯(lián)規(guī)則時(shí)，由于項(xiàng)之間的“祖先”關(guān)系，有些發(fā)現(xiàn)的規(guī)則將是冗余的。,第三節(jié) 挖掘事務(wù)數(shù)據(jù)庫的多層關(guān)聯(lián)規(guī)則,3、檢查冗余的多層關(guān)聯(lián)規(guī)則 例如，考慮下面的規(guī)則：臺(tái)式機(jī)?彩色打印機(jī) [sup=8%，

28、conf=70%] ... (1)IBM臺(tái)式機(jī)?彩色打印機(jī) [sup=2%，conf=72%]…(2) 不難發(fā)現(xiàn)規(guī)則R1是R2的祖先，若將R2中的項(xiàng)用它在概念分層中的祖先替換，就可以得到R1。 定義：如果根據(jù)規(guī)則的祖先，一個(gè)規(guī)則的支持度和置信度都接近于“期望”值，則規(guī)則被認(rèn)為是冗余的。冗余的規(guī)則應(yīng)當(dāng)刪除。,第四節(jié) 挖掘關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫的多維關(guān)聯(lián)規(guī)則,1、多維關(guān)聯(lián)規(guī)則 考察關(guān)聯(lián)規(guī)則

29、 buys（X，”IBM臺(tái)式機(jī)”） ? buys（X，”HP激光打印機(jī)”） 其中，X表示變量，代表顧客，謂詞buys在多維數(shù)據(jù)庫中稱作維，上述規(guī)則為單維關(guān)聯(lián)規(guī)則或維內(nèi)關(guān)聯(lián)規(guī)則。這種規(guī)則通常由事務(wù)數(shù)據(jù)或從事務(wù)數(shù)據(jù)庫挖掘。,第四節(jié) 挖掘關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫的多維關(guān)聯(lián)規(guī)則,1、多維關(guān)聯(lián)規(guī)則 關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫中的數(shù)據(jù)的存儲(chǔ)是多維的。如購物顧客的信息可能包括年齡、

30、職業(yè)、收入和地址等。將數(shù)據(jù)庫的每個(gè)屬性或數(shù)據(jù)倉庫的每個(gè)維看作一個(gè)謂詞，這樣就可以挖掘多維關(guān)聯(lián)規(guī)則，如age（X，”23…33”）? occupation （X，”teacher”） ?buys （X，”laptop”）涉及兩個(gè)以上維或謂詞的關(guān)聯(lián)規(guī)則稱為多維關(guān)聯(lián)規(guī)則。每個(gè)謂詞不重復(fù)出現(xiàn)，稱為不重復(fù)謂詞。具有不重復(fù)謂詞的關(guān)聯(lián)規(guī)則稱作維間關(guān)聯(lián)規(guī)則。,第四節(jié)

31、 挖掘關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫的多維關(guān)聯(lián)規(guī)則,1、多維關(guān)聯(lián)規(guī)則 對(duì)于規(guī)則形如age（X，”23…33”）? buys （X，”laptop”） ?buys （X，”b/w printer”） 包含某些謂詞的多次出現(xiàn)的關(guān)聯(lián)規(guī)則稱為混合多維關(guān)聯(lián)規(guī)則。數(shù)據(jù)庫屬性可能是分類的或量化的。分類屬性是指具有有限個(gè)不同值，值之間無序，又稱標(biāo)稱屬

32、性，如（age，brand，color）。量化屬性是數(shù)值的，并在值之間具有一個(gè)隱含的序，如（age，income， price）。,第四節(jié) 挖掘關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫的多維關(guān)聯(lián)規(guī)則,1、多維關(guān)聯(lián)規(guī)則 挖掘多維關(guān)聯(lián)規(guī)則的技術(shù)可以根據(jù)量化屬性的處理分為三種基本方法： 使用預(yù)定義的概念分層對(duì)量化屬性離散化，該方法稱為使用量化屬性的靜態(tài)離散化挖掘多維關(guān)聯(lián)規(guī)則； 根據(jù)數(shù)據(jù)的分布，將量化的屬性離散化到“箱”，這種方法挖掘的

33、關(guān)聯(lián)規(guī)則稱為量化關(guān)聯(lián)規(guī)則； 量化屬性離散化，以符合區(qū)間數(shù)據(jù)的語義，這種量化關(guān)聯(lián)規(guī)則稱作基于距離的關(guān)聯(lián)規(guī)則。,第四節(jié) 挖掘關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫的多維關(guān)聯(lián)規(guī)則,2、使用量化屬性挖掘多維關(guān)聯(lián)規(guī)則,（age）,（buys）,（income）,（age，income）,（age，buys）,（income，buys）,（age，income，buys）,（）,0-D 頂點(diǎn)方體,1-D 方體,2-D 方體,3-D 基本方體,第四節(jié)

34、 挖掘關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫的多維關(guān)聯(lián)規(guī)則,3、挖掘量化關(guān)聯(lián)規(guī)則 量化關(guān)聯(lián)規(guī)則是多維關(guān)聯(lián)規(guī)則，其中數(shù)值屬性動(dòng)態(tài)離散化，以滿足某種挖掘標(biāo)準(zhǔn)，如最大挖掘規(guī)則的置信度。量化關(guān)聯(lián)規(guī)則如：age（X，”23…33”）? income（X，”32k…42k”） ?buys （X，”laptop”） 這種規(guī)則包含左邊兩個(gè)量化維（量化屬性），右

35、邊一個(gè)分類屬性，稱為2-維量化關(guān)聯(lián)規(guī)則。,第四節(jié) 挖掘關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫的多維關(guān)聯(lián)規(guī)則,3、挖掘量化關(guān)聯(lián)規(guī)則 對(duì)于量化關(guān)聯(lián)規(guī)則可以通過關(guān)聯(lián)規(guī)則聚類系統(tǒng)ARCS（association rule clustering system）方法找出關(guān)聯(lián)規(guī)則。ARCS的基本步驟有： 分箱：等寬分箱、等深分箱、基于同質(zhì)的分箱 找頻繁謂詞集 關(guān)聯(lián)規(guī)則聚類,第四節(jié) 挖掘關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫的多維關(guān)聯(lián)規(guī)則,4、挖掘基于距離的關(guān)聯(lián)規(guī)

36、則 關(guān)聯(lián)規(guī)則的一個(gè)缺點(diǎn)是它們不允許近似的屬性值，而往往在一些情形下，需要考察屬性值的接近性，支持度和置信度均不支持這種近似，所以需要引入基于距離的關(guān)聯(lián)規(guī)則挖掘。這種規(guī)則緊扣區(qū)間數(shù)據(jù)的語義，并允許數(shù)據(jù)值的近似。量化關(guān)聯(lián)規(guī)則無法實(shí)現(xiàn)，因?yàn)槲纯疾鞌?shù)據(jù)點(diǎn)之間或區(qū)間之間的相對(duì)距離。,第四節(jié) 挖掘關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫的多維關(guān)聯(lián)規(guī)則,4、挖掘基于距離的關(guān)聯(lián)規(guī)則 通常使用一個(gè)兩遍算法挖掘基于距離的關(guān)聯(lián)規(guī)則。 第一遍使用聚類

37、找出區(qū)間或簇； 第二遍搜索頻繁地一起出現(xiàn)的簇組得到基于 距離的關(guān)聯(lián)規(guī)則。,第五節(jié) 關(guān)聯(lián)挖掘到關(guān)聯(lián)分析,問題：挖掘了關(guān)聯(lián)規(guī)則后，數(shù)據(jù)挖掘系統(tǒng)如何指出哪些規(guī)則是用戶感興趣的？ 大部分關(guān)聯(lián)規(guī)則挖掘算法使用支持度-置信度框架。盡管使用最小支持度-置信度閾值排除了一些無趣的規(guī)則的探察，仍然會(huì)產(chǎn)生一些對(duì)用戶來說不感興趣的規(guī)則。,第五節(jié) 關(guān)聯(lián)挖掘到關(guān)聯(lián)分析,1、強(qiáng)關(guān)聯(lián)規(guī)則不一定是有趣的 例如，假設(shè)對(duì)分析涉

38、及購買計(jì)算機(jī)游戲和錄像的事務(wù)感興趣。設(shè)事件game表示包含計(jì)算機(jī)游戲的事務(wù)，video表示包含錄像的事務(wù)。在分析的10000個(gè)事務(wù)中，數(shù)據(jù)顯示6000個(gè)顧客事務(wù)包含計(jì)算機(jī)游戲，7500個(gè)事務(wù)包含錄像，而4000個(gè)事務(wù)同時(shí)包含計(jì)算機(jī)游戲和錄像。假設(shè)發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘程序在該數(shù)據(jù)上運(yùn)行，使用最小支持度30%，最小置信度60%。,第五節(jié) 關(guān)聯(lián)挖掘到關(guān)聯(lián)分析,1、強(qiáng)關(guān)聯(lián)規(guī)則不一定是有趣的 將發(fā)現(xiàn)以下關(guān)聯(lián)規(guī)則：buys（X，

39、”computer games”）? buys（X，”videos”） [support=40%，confidence=66%] 該規(guī)則為強(qiáng)關(guān)聯(lián)規(guī)則，滿足最小支持度和最小置信度閾值。然而，購買錄像的可能性是75%，比66%大，所以計(jì)算機(jī)游戲和錄像是負(fù)相關(guān)的，買其中一種實(shí)際上減少了買另一種的可能性。,第五節(jié) 關(guān)聯(lián)挖掘到關(guān)聯(lián)分析,2、由關(guān)聯(lián)分析到相關(guān)分析 當(dāng)A的出現(xiàn)并不蘊(yùn)涵B的出現(xiàn)時(shí)，識(shí)別出規(guī)則

40、A?B是有趣的。支持度-置信度框架在一些情形下不適用，所以考慮根據(jù)相關(guān)性挖掘數(shù)據(jù)項(xiàng)之間的有趣聯(lián)系，選擇一種框架代替支持度-置信度框架。 項(xiàng)集A的出現(xiàn)獨(dú)立于項(xiàng)集B ，若P（A?B）=P（A）P（B）；否則，項(xiàng)集A和B作為事件是依賴的或相關(guān)的。,第五節(jié) 關(guān)聯(lián)挖掘到關(guān)聯(lián)分析,2、由關(guān)聯(lián)分析到相關(guān)分析 A和B的出現(xiàn)的相關(guān)性通過下式計(jì)算： 結(jié)果小于1，表示負(fù)相關(guān)；大于1，表示正相關(guān)；等于1，表示互相獨(dú)立

41、。,第五節(jié) 關(guān)聯(lián)挖掘到關(guān)聯(lián)分析,2、由關(guān)聯(lián)分析到相關(guān)分析例如，P({game})=0.6， P({video})=0.75， P({game，video})=0.4，則P({game，video})/（ P({game}) ×P({video}) ） =0.4/(0.6 × 0.75)=0.89所以， {game}和{video}之間存在負(fù)相關(guān)。,