數(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ù)中項集之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系。 從大量商務(wù)事務(wù)記錄中發(fā)現(xiàn)有趣的關(guān)聯(lián)關(guān)系，可以幫助許多商務(wù)決策的制定，如分類設(shè)計、交叉購物和賤賣分析。 關(guān)聯(lián)規(guī)則挖掘的一個典型的例子是購物籃分析。,第六章 挖掘大型數(shù)據(jù)庫中的

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

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

4、的支持度2%意味分析中的全部事務(wù)的2%同時購買計算機和操作系統(tǒng)軟件。置信度60%意味購買計算機的顧客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}是項的集合，。設(shè)任務(wù)相關(guān)的數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合，其中每個事務(wù)T是項的集合，使得T?I。每一個事務(wù)有一個標(biāo)識符TID。設(shè)A是一個項

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

6、項集。,第一節(jié) 關(guān)聯(lián)規(guī)則挖掘,2、基本概念 關(guān)聯(lián)規(guī)則的挖掘包含兩個基本步驟： 找出所有頻繁項集：這些項集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持計數(shù)一樣。 由頻繁項集產(chǎn)生強關(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ī)則考慮項的在與不在，則它是布爾關(guān)聯(lián)規(guī)則；若規(guī)則描述的是量化的項或?qū)傩灾g的關(guān)聯(lián)，則它是量化關(guān)聯(lián)規(guī)則。如，下列為一個量化關(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ī)則中的項或?qū)傩悦總€只涉及一個維，則它是單維關(guān)聯(lián)規(guī)則；若關(guān)聯(lián)規(guī)則涉及兩個或多個維，則它是多維關(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ī)則只涉及單一抽象層的項或?qū)傩裕瑒t該集合包含單層關(guān)聯(lián)規(guī)則。,3、關(guān)聯(lián)規(guī)則挖掘的分類標(biāo)準(zhǔn) 根據(jù)關(guān)聯(lián)規(guī)則的各種擴充：關(guān)聯(lián)規(guī)則可以擴充到相關(guān)分析，以識別項是否相關(guān)。用最大模式（最大的頻繁模式）或頻繁閉項集顯著壓縮挖掘所產(chǎn)生的頻繁項集數(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ī)則頻繁項集的算法，通過侯選項集找頻繁項集?；舅悸罚?Apriori使用一種稱作逐層搜索的迭代方法，K-項集用于探索（K+1）-項集。首先，找出頻繁1-項集的集合，記為L1； L1用于找頻繁2-項集的集合L2 ，而L2用于找L3，如此下去，直到找到頻繁K-項集。找每個LK需要一次數(shù)據(jù)庫掃描。其過程包括：連接和剪枝兩個方面。,第二節(jié) 挖掘事務(wù)數(shù)據(jù)庫的單維布爾關(guān)

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

11、生侯選2-項集C2,掃描D，對每個侯選2-項集計數(shù)C2,第二節(jié) 挖掘事務(wù)數(shù)據(jù)庫的單維布爾關(guān)聯(lián)規(guī)則,1、Apriori算法,,,由L2?L2,比較侯選支持度計數(shù)與最小支持度計數(shù)，得到頻繁項集L2,第二節(jié) 挖掘事務(wù)數(shù)據(jù)庫的單維布爾關(guān)聯(lián)規(guī)則,1、Apriori算法,,,掃描D，對每個侯選3-項集計數(shù)C3,由L2產(chǎn)生侯選3-項集C3,比較侯選支持度計數(shù)與最小支持度計數(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、由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則 一旦由數(shù)據(jù)庫D中的事務(wù)找出頻繁項集，由它們可以產(chǎn)生強關(guān)聯(lián)規(guī)則（滿足最小支持度和最小置信度）。對于置信度，可以用項集支持度計數(shù)表示：其中，Support_count(A?B)是包含項集A?B的事務(wù)數(shù)， Support_count(A)是包含項集A的事務(wù)數(shù)。,第二節(jié) 挖掘事務(wù)數(shù)據(jù)

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

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

15、iceberg query）在一個屬性或?qū)傩约嫌嬎阋粋€聚集函數(shù)，以找出大于某個指定閾值的聚集值。,第二節(jié) 挖掘事務(wù)數(shù)據(jù)庫的單維布爾關(guān)聯(lián)規(guī)則,3、冰山查詢 給定關(guān)系R，它具有屬性a_1， a_2，…， a_n和b，一個聚集函數(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ù)量相對很少。輸入數(shù)據(jù)集為“冰山”，輸出結(jié)果為“冰山頂”。,第二節(jié) 挖掘事務(wù)數(shù)據(jù)庫的單維布爾關(guān)聯(lián)規(guī)則,3、冰山查詢 例，設(shè)給定銷售數(shù)據(jù)，期望產(chǎn)生一個顧客-商品對的列表，要求這些顧客購買商品數(shù)量達到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算法，不考慮每個顧客購買的每種

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算法，不考慮每個顧客購買的每種商品的數(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ù)項之間很難找出強關(guān)聯(lián)規(guī)則。而在較高的概念層尋找強關(guān)聯(lián)規(guī)則可以得到具有普遍意義的知識。對于某用戶代表普遍意義的知識，對另一用戶可能是新穎的。所以，DMS應(yīng)當(dāng)提供一種能力，在多個抽象層挖掘關(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，它是計算機部的銷售數(shù)據(jù)，對每個事務(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)的低層概念用概念分層的高層概念替換，對數(shù)據(jù)概化。例中概念分層為4層，記為0，1，2和3。 在最低的原始層很難

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

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

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

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

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

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

28、conf=70%] ... (1)IBM臺式機?彩色打印機 [sup=2%，conf=72%]…(2) 不難發(fā)現(xiàn)規(guī)則R1是R2的祖先，若將R2中的項用它在概念分層中的祖先替換，就可以得到R1。 定義：如果根據(jù)規(guī)則的祖先，一個規(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臺式機”） ? buys（X，”HP激光打印機”） 其中，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ù)的存儲是多維的。如購物顧客的信息可能包括年齡、

30、職業(yè)、收入和地址等。將數(shù)據(jù)庫的每個屬性或數(shù)據(jù)倉庫的每個維看作一個謂詞，這樣就可以挖掘多維關(guān)聯(lián)規(guī)則，如age（X，”23…33”）? occupation （X，”teacher”） ?buys （X，”laptop”）涉及兩個以上維或謂詞的關(guān)聯(lián)規(guī)則稱為多維關(guān)聯(lián)規(guī)則。每個謂詞不重復(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ī)則 對于規(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ù)庫屬性可能是分類的或量化的。分類屬性是指具有有限個不同值，值之間無序，又稱標(biāo)稱屬

32、性，如（age，brand，color）。量化屬性是數(shù)值的，并在值之間具有一個隱含的序，如（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ù)定義的概念分層對量化屬性離散化，該方法稱為使用量化屬性的靜態(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 頂點方體,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ù)值屬性動態(tài)離散化，以滿足某種挖掘標(biāo)準(zhǔn)，如最大挖掘規(guī)則的置信度。量化關(guān)聯(lián)規(guī)則如：age（X，”23…33”）? income（X，”32k…42k”） ?buys （X，”laptop”） 這種規(guī)則包含左邊兩個量化維（量化屬性），右

35、邊一個分類屬性，稱為2-維量化關(guān)聯(lián)規(guī)則。,第四節(jié) 挖掘關(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ī)則聚類系統(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ī)則的一個缺點是它們不允許近似的屬性值，而往往在一些情形下，需要考察屬性值的接近性，支持度和置信度均不支持這種近似，所以需要引入基于距離的關(guān)聯(lián)規(guī)則挖掘。這種規(guī)則緊扣區(qū)間數(shù)據(jù)的語義，并允許數(shù)據(jù)值的近似。量化關(guān)聯(lián)規(guī)則無法實現(xiàn)，因為未考察數(shù)據(jù)點之間或區(qū)間之間的相對距離。,第四節(jié) 挖掘關(guān)系數(shù)據(jù)庫和數(shù)據(jù)倉庫的多維關(guān)聯(lián)規(guī)則,4、挖掘基于距離的關(guān)聯(lián)規(guī)則 通常使用一個兩遍算法挖掘基于距離的關(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ī)則的探察，仍然會產(chǎn)生一些對用戶來說不感興趣的規(guī)則。,第五節(jié) 關(guān)聯(lián)挖掘到關(guān)聯(lián)分析,1、強關(guān)聯(lián)規(guī)則不一定是有趣的 例如，假設(shè)對分析涉

38、及購買計算機游戲和錄像的事務(wù)感興趣。設(shè)事件game表示包含計算機游戲的事務(wù)，video表示包含錄像的事務(wù)。在分析的10000個事務(wù)中，數(shù)據(jù)顯示6000個顧客事務(wù)包含計算機游戲，7500個事務(wù)包含錄像，而4000個事務(wù)同時包含計算機游戲和錄像。假設(shè)發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘程序在該數(shù)據(jù)上運行，使用最小支持度30%，最小置信度60%。,第五節(jié) 關(guān)聯(lián)挖掘到關(guān)聯(lián)分析,1、強關(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ī)則為強關(guān)聯(lián)規(guī)則，滿足最小支持度和最小置信度閾值。然而，購買錄像的可能性是75%，比66%大，所以計算機游戲和錄像是負(fù)相關(guān)的，買其中一種實際上減少了買另一種的可能性。,第五節(jié) 關(guān)聯(lián)挖掘到關(guān)聯(lián)分析,2、由關(guān)聯(lián)分析到相關(guān)分析 當(dāng)A的出現(xiàn)并不蘊涵B的出現(xiàn)時，識別出規(guī)則

40、A?B是有趣的。支持度-置信度框架在一些情形下不適用，所以考慮根據(jù)相關(guān)性挖掘數(shù)據(jù)項之間的有趣聯(lián)系，選擇一種框架代替支持度-置信度框架。 項集A的出現(xiàn)獨立于項集B ，若P（A?B）=P（A）P（B）；否則，項集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)性通過下式計算： 結(jié)果小于1，表示負(fù)相關(guān)；大于1，表示正相關(guān)；等于1，表示互相獨立

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)。,