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

1、1、關(guān)聯(lián)規(guī)則挖掘2、挖掘事務(wù)數(shù)據(jù)庫(kù)的單維布爾關(guān)聯(lián)規(guī)則3、挖掘事務(wù)數(shù)據(jù)庫(kù)的多層關(guān)聯(lián)規(guī)則4、挖掘關(guān)系數(shù)據(jù)庫(kù)和數(shù)據(jù)倉(cāng)庫(kù)的多維關(guān)聯(lián)規(guī)則5、由關(guān)聯(lián)挖掘到相關(guān)分析第六章 挖掘大型數(shù)據(jù)庫(kù)中的關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則則挖掘發(fā)發(fā)現(xiàn)大量量數(shù)據(jù)中中項(xiàng)集之之間有趣趣的關(guān)聯(lián)聯(lián)或相關(guān)關(guān)聯(lián)系。從大量商商務(wù)事務(wù)務(wù)記錄中中發(fā)現(xiàn)有有趣的關(guān)關(guān)聯(lián)關(guān)系系，可以以幫助許許多商務(wù)務(wù)決策的的制定，如分類(lèi)類(lèi)設(shè)計(jì)、交叉購(gòu)購(gòu)物和賤賤賣(mài)分析析。關(guān)聯(lián)規(guī)則則挖掘的的一個(gè)典典型的例例子是購(gòu)物籃分分析。第六章挖挖掘掘大型數(shù)數(shù)據(jù)庫(kù)中中的關(guān)關(guān)聯(lián)規(guī)則則第一節(jié)關(guān)關(guān)聯(lián)聯(lián)規(guī)則挖挖掘顧客1顧客4顧客3顧客2牛奶 面包谷類(lèi)牛奶 面包糖 雞旦牛奶 面包黃油糖 雞旦市場(chǎng)分析員1、購(gòu)物

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

3、是是商店中中可利用用的商品品的集合合，則每每鐘商品品有一個(gè)個(gè)布爾變量量，表示該該商品的的有無(wú)。每個(gè)籃籃子可以以用一個(gè)個(gè)布爾向向量表示示。可以以分析布布爾向量量，得到到反映商商品頻繁關(guān)聯(lián)聯(lián)或同時(shí)購(gòu)購(gòu)買(mǎi)的購(gòu)購(gòu)買(mǎi)模式式。這些模式式可以用用關(guān)聯(lián)規(guī)規(guī)則的形形式表示示：第一節(jié)關(guān)關(guān)聯(lián)聯(lián)規(guī)則挖挖掘1、購(gòu)物物籃分析析規(guī)則的支持度和置信度是兩個(gè)規(guī)規(guī)則興趣趣度度量量，反映映規(guī)則的的有用性性和確定定性，上上述規(guī)則則的支持持度2%意味分分析中的的全部事事務(wù)的2%同時(shí)時(shí)購(gòu)買(mǎi)計(jì)計(jì)算機(jī)和和操作系系統(tǒng)軟件件。置信信度60%意味味購(gòu)買(mǎi)計(jì)計(jì)算機(jī)的的顧客60%也也購(gòu)買(mǎi)操操作系統(tǒng)統(tǒng)軟件。關(guān)聯(lián)規(guī)則則被認(rèn)為為是有趣的，如果它它滿足最小支持

4、持度閾值值和最小置信信度閾值值。這些閾閾值可由由用戶和和領(lǐng)域?qū)?zhuān)家設(shè)定定。第一節(jié)關(guān)關(guān)聯(lián)聯(lián)規(guī)則挖挖掘2、基本本概念設(shè)I=i1，i2，im是項(xiàng)的集合，。設(shè)任務(wù)相相關(guān)的數(shù)數(shù)據(jù)D是數(shù)據(jù)庫(kù)庫(kù)事務(wù)的的集合，其中每每個(gè)事務(wù)T是項(xiàng)的集集合，使使得TI。每一個(gè)事務(wù)務(wù)有一個(gè)個(gè)標(biāo)識(shí)符符TID。設(shè)A是一個(gè)項(xiàng)項(xiàng)集，事事務(wù)T包含A，當(dāng)且僅當(dāng)當(dāng)AT。關(guān)聯(lián)規(guī)則則是形如AB的蘊(yùn)涵式式，其中中AI， BI，且AB=。第一節(jié)關(guān)關(guān)聯(lián)聯(lián)規(guī)則挖挖掘2、基本本概念項(xiàng)的集合合稱(chēng)為項(xiàng)集，包含K個(gè)項(xiàng)的項(xiàng)項(xiàng)集稱(chēng)為為K-項(xiàng)集。集合computer，software是一個(gè)2-項(xiàng)集集。項(xiàng)集的出出現(xiàn)頻率率是包含項(xiàng)項(xiàng)集的事事務(wù)數(shù)簡(jiǎn)簡(jiǎn)稱(chēng)為頻率、支持計(jì)數(shù)數(shù)或計(jì)

5、數(shù)。項(xiàng)集滿足足最小支支持度，若項(xiàng)集的出出現(xiàn)頻率率大于或等等于最小支持持度與D中事務(wù)總數(shù)數(shù)的乘積。如果項(xiàng)集集滿足最小支持持度，則稱(chēng)它它為頻繁項(xiàng)集集。第一節(jié)關(guān)關(guān)聯(lián)聯(lián)規(guī)則挖挖掘2、基本本概念關(guān)聯(lián)規(guī)則則的挖掘掘包含兩兩個(gè)基本本步驟：找出所有有頻繁項(xiàng)項(xiàng)集：這這些項(xiàng)集集出現(xiàn)的的頻繁性性至少和和預(yù)定義義的最小小支持計(jì)計(jì)數(shù)一樣樣。由頻繁項(xiàng)項(xiàng)集產(chǎn)生生強(qiáng)關(guān)聯(lián)聯(lián)規(guī)則：這些規(guī)規(guī)則必須須滿足最最小支持持度和最最小置信信度。挖掘關(guān)聯(lián)聯(lián)規(guī)則的的總體性性能由第第一步?jīng)Q決定。第一節(jié)關(guān)關(guān)聯(lián)聯(lián)規(guī)則挖挖掘3、關(guān)聯(lián)聯(lián)規(guī)則挖挖掘的分分類(lèi)標(biāo)準(zhǔn)準(zhǔn)購(gòu)物籃分分析只是是關(guān)聯(lián)規(guī)規(guī)則挖掘掘的一種種形式。根據(jù)下列列標(biāo)準(zhǔn)，關(guān)聯(lián)規(guī)規(guī)則有多多種分類(lèi)類(lèi)方法：根

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

7、聯(lián)聯(lián)規(guī)則挖挖掘購(gòu)買(mǎi)的商商品涉及及不同的的抽象層層，稱(chēng)所所挖掘的的規(guī)則集集由多層關(guān)聯(lián)聯(lián)規(guī)則組成。否否則，規(guī)規(guī)則只涉涉及單一一抽象層層的項(xiàng)或或?qū)傩?，則該集集合包含含單層關(guān)聯(lián)聯(lián)規(guī)則。3、關(guān)聯(lián)聯(lián)規(guī)則挖挖掘的分分類(lèi)標(biāo)準(zhǔn)準(zhǔn)根據(jù)關(guān)聯(lián)聯(lián)規(guī)則的的各種擴(kuò)擴(kuò)充：關(guān)關(guān)聯(lián)規(guī)則則可以擴(kuò)擴(kuò)充到相關(guān)分析析，以識(shí)別別項(xiàng)是否否相關(guān)。用最大模式式（最大大的頻繁繁模式）或頻繁閉項(xiàng)項(xiàng)集顯著壓縮縮挖掘所所產(chǎn)生的的頻繁項(xiàng)項(xiàng)集數(shù)。第一節(jié)關(guān)關(guān)聯(lián)聯(lián)規(guī)則挖挖掘第二節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的單維布布爾關(guān)聯(lián)聯(lián)規(guī)則1、Apriori算法Apriori算法是一一種最有有影響的的挖掘布布爾關(guān)聯(lián)聯(lián)規(guī)則頻頻繁項(xiàng)集集的算法法，通過(guò)過(guò)侯選項(xiàng)項(xiàng)集找頻頻繁項(xiàng)集集?；?/p>

8、思路路：Apriori使用一種種稱(chēng)作逐逐層搜索索的迭代代方法，K-項(xiàng)集用于于探索（K+1）-項(xiàng)集。首首先，找找出頻繁繁1-項(xiàng)項(xiàng)集的集集合，記記為L(zhǎng)1； L1用于找頻頻繁2-項(xiàng)集的的集合L2，而L2用于找L3，如此下去去，直到到找到頻頻繁K-項(xiàng)集。找找每個(gè)LK需要一次次數(shù)據(jù)庫(kù)庫(kù)掃描。其過(guò)程程包括：連接和剪枝兩個(gè)方面面。第二節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的單維布布爾關(guān)聯(lián)聯(lián)規(guī)則1、Apriori算法例如，設(shè)設(shè)已有包包含9個(gè)個(gè)事務(wù)的的事務(wù)數(shù)數(shù)據(jù)庫(kù)，即|D|=9，各事務(wù)按按字典次次序存放放，設(shè)最小事事務(wù)支持持度計(jì)數(shù)數(shù)為2。TID項(xiàng)ID的列表T100I1，I2，I5T200I2，I4T300I2，I3T400I

9、1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3第二節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的單維布布爾關(guān)聯(lián)聯(lián)規(guī)則1、Apriori算法項(xiàng)集支持度計(jì)數(shù)I16I27I36I42I52項(xiàng)集支持度計(jì)數(shù)I16I27I36I42I52侯選集C1頻繁集L1掃描D，對(duì)每個(gè)侯侯選1-項(xiàng)集計(jì)計(jì)數(shù)比較侯選選支持度度計(jì)數(shù)與與最小支支持度計(jì)計(jì)數(shù)設(shè)最小事事務(wù)支持持度計(jì)數(shù)數(shù)為2，2/9=22%第二節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的單維布布爾關(guān)聯(lián)聯(lián)規(guī)則1、Apriori算法項(xiàng)集I1，I2I1，I3I1，I4I1，I5I2，I3I2，I4I2，I5I3，I4I3，I5I4，I

10、5由L1產(chǎn)生侯選選2-項(xiàng)項(xiàng)集C2掃描D，對(duì)每個(gè)侯侯選2-項(xiàng)集計(jì)計(jì)數(shù)C2項(xiàng)集支持度計(jì)數(shù)I1，I24I1，I34I1，I41I1，I52I2，I34I2，I42I2，I52I3，I40I3，I51I4，I50第二節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的單維布布爾關(guān)聯(lián)聯(lián)規(guī)則1、Apriori算法由L2L2比較侯選選支持度度計(jì)數(shù)與與最小支支持度計(jì)計(jì)數(shù)，得得到頻繁繁項(xiàng)集L2項(xiàng)集支持度計(jì)數(shù)I1，I24I1，I34I1，I52I2，I34I2，I42I2，I52項(xiàng)集I1，I2，I3I1，I2，I5I1，I3，I5I2，I3，I4I2，I3，I5I2，I4，I5第二節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的單維布布爾關(guān)聯(lián)聯(lián)規(guī)則1、Apri

11、ori算法掃描D，對(duì)每個(gè)侯侯選3-項(xiàng)集計(jì)計(jì)數(shù)C3由L2產(chǎn)生侯選選3-項(xiàng)項(xiàng)集C3項(xiàng)集I1，I2，I3I1，I2，I5項(xiàng)集支持度計(jì)數(shù)I1，I2，I32I1，I2，I52比較侯選選支持度度計(jì)數(shù)與與最小支支持度計(jì)計(jì)數(shù)，得得到L3項(xiàng)集支持度計(jì)數(shù)I1，I2，I32I1，I2，I52由于L3L3產(chǎn)生的C4=I1，I2，I3，I5的子集I2，I3，I5不是頻繁繁的，所所以C4=，算法終止止。第二節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的單維布布爾關(guān)聯(lián)聯(lián)規(guī)則2、由頻頻繁項(xiàng)集集產(chǎn)生關(guān)關(guān)聯(lián)規(guī)則則一旦由數(shù)數(shù)據(jù)庫(kù)D中的事務(wù)務(wù)找出頻頻繁項(xiàng)集集，由它它們可以以產(chǎn)生強(qiáng)強(qiáng)關(guān)聯(lián)規(guī)規(guī)則（滿滿足最小小支持度度和最小小置信度度）。對(duì)對(duì)于置信信度，可可

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

13、非空子子集有：I1，I2，I1，I5，I2，I5，I1，I2，I5?？傻玫疥P(guān)關(guān)聯(lián)規(guī)則則如：第二節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的單維布布爾關(guān)聯(lián)聯(lián)規(guī)則2、由頻頻繁項(xiàng)集集產(chǎn)生關(guān)關(guān)聯(lián)規(guī)則則如果最小小置信度度預(yù)值為為70%，則規(guī)規(guī)則2、3和6可以輸輸出，因因?yàn)檫@些些規(guī)則滿滿足強(qiáng)關(guān)關(guān)聯(lián)規(guī)則則條件。規(guī)則編號(hào)關(guān)聯(lián)規(guī)則置信度1I1I2I5Conf=2/4=50%2I1I5I2Conf=2/2=100%3I2I5I1Conf=2/2=100%4I1 I2 I5Conf=2/6=33%5I2 I1 I5Conf=2/7=29%6I5 I1 I2Conf=2/2=100%第二節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的單維布布爾關(guān)聯(lián)聯(lián)規(guī)則3

14、、冰山山查詢冰山查詢?cè)冊(cè)跀?shù)據(jù)據(jù)挖掘中中經(jīng)常使使用，特特別是對(duì)對(duì)購(gòu)物籃籃分析，apriori算法可以以用來(lái)提提高冰山山查詢的的效率。冰山查查詢（iceberg query）在一個(gè)屬屬性或?qū)賹傩约仙嫌?jì)算一一個(gè)聚集集函數(shù)，以找出出大于某某個(gè)指定定閾值的的聚集值值。第二節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的單維布布爾關(guān)聯(lián)聯(lián)規(guī)則3、冰山山查詢給定關(guān)系系R，它具有屬屬性a_1， a_2，a_n和b，一個(gè)聚集集函數(shù)agg_fuc，冰山查詢?cè)冃稳纾篠electR.a_1，R.a_2， ，R.a_n，agg_fuc(R.b)FromrelationRGroupbyR.a_1，R.a_2， ，R.a_nHavingagg_

15、fuc(R.b)=threshold給定大量量輸入元元組，滿滿足having子句中閾閾值的輸輸出元組組數(shù)量相相對(duì)很少少。輸入入數(shù)據(jù)集集為“冰冰山”，輸出結(jié)結(jié)果為“冰山頂頂”。第二節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的單維布布爾關(guān)聯(lián)聯(lián)規(guī)則3、冰山山查詢例，設(shè)給給定銷(xiāo)售售數(shù)據(jù)，期望產(chǎn)產(chǎn)生一個(gè)個(gè)顧客-商品對(duì)對(duì)的列表表，要求求這些顧顧客購(gòu)買(mǎi)買(mǎi)商品數(shù)數(shù)量達(dá)到到5件或或更多，則冰山山查詢表表示如：SelectP.cust_ID， P. item_ID，SUM(P.qty)FromPurchasesPGroupbyP.cust_ID， P. item_IDHavingSUM(P.qty)=5第二節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的

16、的單維布布爾關(guān)聯(lián)聯(lián)規(guī)則3、冰山山查詢可以采用用apriori算法，不不考慮每每個(gè)顧客客購(gòu)買(mǎi)的的每種商商品的數(shù)數(shù)量，按按照以下下步驟：產(chǎn)生cust_list，總共購(gòu)買(mǎi)買(mǎi)5件以以上商品品的顧客客表：SelectP.cust_IDFromPurchasesPGroupbyP.cust_IDHavingSUM(P.qty)=5第二節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的單維布布爾關(guān)聯(lián)聯(lián)規(guī)則3、冰山山查詢可以采用用apriori算法，不不考慮每每個(gè)顧客客購(gòu)買(mǎi)的的每種商商品的數(shù)數(shù)量，按按照以下下步驟：產(chǎn)生item_list，被顧客購(gòu)購(gòu)買(mǎi)數(shù)量量5件以以上商品品表：SelectP.item_IDFromPurchasesP

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

18、相關(guān)關(guān)數(shù)據(jù)集集D，它是計(jì)算算機(jī)部的的銷(xiāo)售數(shù)數(shù)據(jù)，對(duì)對(duì)每個(gè)事事務(wù)TID給出了購(gòu)購(gòu)買(mǎi)的商商品。TID購(gòu)買(mǎi)的商品T1IBM臺(tái)式機(jī)，HP激光打印機(jī)T2教學(xué)軟件，財(cái)務(wù)軟件，操作系統(tǒng)軟件T3雙飛燕鼠標(biāo)，康柏鍵盤(pán)，IBM臺(tái)式機(jī)T4DEC服務(wù)器，操作系統(tǒng)軟件，OFFICE軟件T5IBM筆記本電腦，佳能?chē)娔噬蛴C(jī)第三節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的多層關(guān)關(guān)聯(lián)規(guī)則則1、多層層關(guān)聯(lián)規(guī)規(guī)則商品的概概念分層層如：計(jì)算機(jī)類(lèi)商品軟件計(jì)算機(jī)計(jì)算機(jī)輔件打印機(jī)臺(tái)式機(jī)筆記本應(yīng)用系統(tǒng)彩色黑白鼠標(biāo)鍵盤(pán)IBM康柏財(cái)務(wù)操作系統(tǒng)佳能HP雙飛燕康柏第三節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的多層關(guān)關(guān)聯(lián)規(guī)則則1、多層層關(guān)聯(lián)規(guī)規(guī)則概念分層層定義了了由低層層概念到

19、到更一般般的高層層概念的的映射序序列，可可以通過(guò)過(guò)將數(shù)據(jù)據(jù)內(nèi)的低低層概念念用概念念分層的的高層概概念替換換，對(duì)數(shù)數(shù)據(jù)概化化。例中中概念分分層為4層，記記為0，1，2和3。在最低的的原始層層很難找找出有趣趣的購(gòu)買(mǎi)買(mǎi)模式，如IBM臺(tái)式機(jī)，HP激光打印印機(jī)不不太可能能滿足最最小支持持度。而而計(jì)算算機(jī)，打打印機(jī)更容易易滿足最最小支持持度。第三節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的多層關(guān)關(guān)聯(lián)規(guī)則則2、挖掘掘多層關(guān)關(guān)聯(lián)規(guī)則則的方法法問(wèn)題：如何使使用概念念分層有有效挖掘掘多層關(guān)關(guān)聯(lián)規(guī)則則?？疾觳煲恍┗谥С殖侄?置置信度框框架的方方法。對(duì)于所有有層使用用一致的的最小支支持度在較低層層使用遞遞減的最最小支持持度逐層獨(dú)立

20、立層交叉單單項(xiàng)過(guò)濾濾層交叉K-項(xiàng)集過(guò)濾濾第三節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的多層關(guān)關(guān)聯(lián)規(guī)則則2、挖掘掘多層關(guān)關(guān)聯(lián)規(guī)則則的方法法對(duì)于所有有層使用用一致的的最小支支持度：在每一一層挖掘掘時(shí)，使使用相同同的最小小支持度度閾值。如整個(gè)個(gè)使用最最小支持持度閾值值5%。計(jì)算機(jī) support=10%臺(tái)式機(jī) support=4%筆記本 support=6%層1min_sup=5%層2min_sup=5%第三節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的多層關(guān)關(guān)聯(lián)規(guī)則則2、挖掘掘多層關(guān)關(guān)聯(lián)規(guī)則則的方法法在較低層層使用遞遞減的最最小支持持度：在在每個(gè)抽抽象層有有自己的的最小支支持度閾閾值。抽抽象層越越低，對(duì)對(duì)應(yīng)的閾閾值越小小。如層層1和

21、層層2的最最小支持持度閾值值分別為為5%和和3%。計(jì)算機(jī) support=10%臺(tái)式機(jī) support=4%筆記本 support=6%層1min_sup=5%層2min_sup=3%第三節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的多層關(guān)關(guān)聯(lián)規(guī)則則2、挖掘掘多層關(guān)關(guān)聯(lián)規(guī)則則的方法法逐層獨(dú)立立：完全全的寬度度搜索，沒(méi)有頻頻繁項(xiàng)集集的背景景知識(shí)用用于剪枝枝?？疾觳烀總€(gè)節(jié)節(jié)點(diǎn)，不不管它的的父節(jié)點(diǎn)點(diǎn)是否是是頻繁的的。計(jì)算機(jī) support=10%臺(tái)式機(jī) support=4%筆記本 support=6%層1min_sup=12%層2min_sup=3%第三節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的多層關(guān)關(guān)聯(lián)規(guī)則則2、挖掘掘多層關(guān)關(guān)聯(lián)規(guī)則

22、則的方法法層交叉單單項(xiàng)過(guò)濾濾：一個(gè)個(gè)第i層的項(xiàng)被被考察，當(dāng)且僅僅當(dāng)它在在第（i-1）層的父節(jié)節(jié)點(diǎn)是頻頻繁的。根據(jù)遞遞減支持持度，如如果父節(jié)節(jié)點(diǎn)是頻頻繁的，它的子子女將被被考察；否則，它的子子孫將由由搜索中中剪枝。計(jì)算機(jī) support=10%臺(tái)式機(jī) （未考察）筆記本 （未考察）層1min_sup=12%層2min_sup=3%第三節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的多層關(guān)關(guān)聯(lián)規(guī)則則2、挖掘掘多層關(guān)關(guān)聯(lián)規(guī)則則的方法法層交叉k-項(xiàng)集過(guò)濾：一個(gè)第第i層的k-項(xiàng)集被考考察，當(dāng)當(dāng)且僅當(dāng)當(dāng)它在第第（i-1）層的對(duì)應(yīng)應(yīng)父節(jié)點(diǎn)點(diǎn)k-項(xiàng)集是頻頻繁的。計(jì)算機(jī)，打印機(jī) support=8%臺(tái)式機(jī)，彩色打印機(jī) support=

23、4%筆記本，黑白打印機(jī) support=2%層1min_sup=5%層2min_sup=3%第三節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的多層關(guān)關(guān)聯(lián)規(guī)則則2、挖掘掘多層關(guān)關(guān)聯(lián)規(guī)則則的方法法逐層獨(dú)立立策略的條條件寬松松，而層交叉k-項(xiàng)集過(guò)濾策略的限限制太強(qiáng)強(qiáng)，層交叉單單項(xiàng)過(guò)濾濾策略是一一個(gè)折衷衷。進(jìn)一一步改進(jìn)進(jìn)為受控層交交叉單項(xiàng)項(xiàng)過(guò)濾策略。通通過(guò)設(shè)置置一個(gè)層傳遞閾閾值，用于向向較低層層“傳遞遞”相對(duì)對(duì)頻繁的的項(xiàng)。第三節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的多層關(guān)關(guān)聯(lián)規(guī)則則2、挖掘掘多層關(guān)關(guān)聯(lián)規(guī)則則的方法法受控的層層交叉單單項(xiàng)過(guò)濾濾策略：如如果滿足足層傳遞遞閾值，則允許許考察不不滿足最最小支持持度閾值值項(xiàng)的子子女。計(jì)算機(jī) su

24、pport=10%臺(tái)式機(jī) support=4%筆記本 support=6%層1min_sup=12%Level_pass_sup=8%層2min_sup=3%第三節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的多層關(guān)關(guān)聯(lián)規(guī)則則2、挖掘掘多層關(guān)關(guān)聯(lián)規(guī)則則的方法法交叉層關(guān)關(guān)聯(lián)規(guī)則則：規(guī)則中中的項(xiàng)不不屬于同同一概念念層，挖挖掘交叉叉層i與j層關(guān)聯(lián)規(guī)規(guī)則應(yīng)當(dāng)當(dāng)使用較較低層j的最小支支持度閾閾值，使使得j層的項(xiàng)可可以包含含在分析析中。前面所討討論的5種方法法屬于發(fā)發(fā)現(xiàn)的頻頻繁項(xiàng)集集的所有有項(xiàng)都屬屬于同一一概念層層1層。如計(jì)算機(jī)軟件或臺(tái)式機(jī)彩色打打印機(jī)對(duì)于不屬屬于同一一概念層層（1層層和2層層）的規(guī)規(guī)則：計(jì)算機(jī)彩色打打印機(jī)第三

25、節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的多層關(guān)關(guān)聯(lián)規(guī)則則3、檢查查冗余的的多層關(guān)關(guān)聯(lián)規(guī)則則概念分層層在數(shù)據(jù)據(jù)挖掘中中允許不不同的抽抽象層的的知識(shí)發(fā)發(fā)現(xiàn)，如如多層關(guān)關(guān)聯(lián)規(guī)則則。然而而，當(dāng)挖挖掘多層層關(guān)聯(lián)規(guī)規(guī)則時(shí)，由于項(xiàng)項(xiàng)之間的的“祖先先”關(guān)系系，有些些發(fā)現(xiàn)的的規(guī)則將將是冗余余的。第三節(jié)挖挖掘掘事務(wù)數(shù)數(shù)據(jù)庫(kù)的的多層關(guān)關(guān)聯(lián)規(guī)則則3、檢查查冗余的的多層關(guān)關(guān)聯(lián)規(guī)則則例如，考考慮下面面的規(guī)則則：臺(tái)式機(jī)彩色打打印機(jī)sup=8%，conf=70% .(1)IBM臺(tái)式機(jī)彩色打打印機(jī)sup=2%，conf=72%(2)不難發(fā)現(xiàn)現(xiàn)規(guī)則R1是R2的祖先，若將R2中的項(xiàng)用用它在概概念分層層中的祖祖先替換換，就可可以得到到R1。定義：

26、如果根根據(jù)規(guī)則則的祖先先，一個(gè)個(gè)規(guī)則的的支持度度和置信信度都接接近于“期望”值，則則規(guī)則被認(rèn)為是是冗余的。冗余余的規(guī)則則應(yīng)當(dāng)刪刪除。第四節(jié)挖挖掘掘關(guān)系數(shù)數(shù)據(jù)庫(kù)和和數(shù)據(jù)倉(cāng)倉(cāng)庫(kù)的多多維關(guān)聯(lián)聯(lián)規(guī)則1、多維維關(guān)聯(lián)規(guī)規(guī)則考察關(guān)聯(lián)聯(lián)規(guī)則buys（X，”IBM臺(tái)式機(jī)”）buys（X，”HP激光打印印機(jī)”）其中，X表示變量量，代表表顧客，謂詞buys在多維數(shù)數(shù)據(jù)庫(kù)中中稱(chēng)作維，上述規(guī)規(guī)則為單維關(guān)聯(lián)聯(lián)規(guī)則或維內(nèi)關(guān)聯(lián)聯(lián)規(guī)則。這種規(guī)規(guī)則通常常由事務(wù)務(wù)數(shù)據(jù)或或從事務(wù)務(wù)數(shù)據(jù)庫(kù)庫(kù)挖掘。第四節(jié)挖挖掘掘關(guān)系數(shù)數(shù)據(jù)庫(kù)和和數(shù)據(jù)倉(cāng)倉(cāng)庫(kù)的多多維關(guān)聯(lián)聯(lián)規(guī)則1、多維維關(guān)聯(lián)規(guī)規(guī)則關(guān)系數(shù)據(jù)據(jù)庫(kù)和數(shù)數(shù)據(jù)倉(cāng)庫(kù)庫(kù)中的數(shù)數(shù)據(jù)的存存儲(chǔ)是多多維的。如購(gòu)物

27、物顧客的的信息可可能包括括年齡、職業(yè)、收入和和地址等等。將數(shù)數(shù)據(jù)庫(kù)的的每個(gè)屬屬性或數(shù)數(shù)據(jù)倉(cāng)庫(kù)庫(kù)的每個(gè)個(gè)維看作作一個(gè)謂謂詞，這這樣就可可以挖掘掘多維關(guān)關(guān)聯(lián)規(guī)則則，如age（X，”2333”）occupation （X，”teacher”）buys（X，”laptop”）涉及兩個(gè)個(gè)以上維維或謂詞詞的關(guān)聯(lián)聯(lián)規(guī)則稱(chēng)稱(chēng)為多維關(guān)聯(lián)聯(lián)規(guī)則。每個(gè)謂謂詞不重重復(fù)出現(xiàn)現(xiàn)，稱(chēng)為為不重復(fù)謂謂詞。具有不不重復(fù)謂謂詞的關(guān)關(guān)聯(lián)規(guī)則則稱(chēng)作維間關(guān)聯(lián)聯(lián)規(guī)則。第四節(jié)挖挖掘掘關(guān)系數(shù)數(shù)據(jù)庫(kù)和和數(shù)據(jù)倉(cāng)倉(cāng)庫(kù)的多多維關(guān)聯(lián)聯(lián)規(guī)則1、多維維關(guān)聯(lián)規(guī)規(guī)則對(duì)于規(guī)則則形如age（X，”2333”） buys（X，”laptop”）buys（X，”b/w

28、 printer”）包含某些些謂詞的的多次出出現(xiàn)的關(guān)關(guān)聯(lián)規(guī)則則稱(chēng)為混合多維維關(guān)聯(lián)規(guī)規(guī)則。數(shù)據(jù)庫(kù)庫(kù)屬性可可能是分分類(lèi)的或或量化的的。分類(lèi)屬性性是指具有有有限個(gè)個(gè)不同值值，值之之間無(wú)序序，又稱(chēng)稱(chēng)標(biāo)稱(chēng)屬性性，如（age，brand，color）。量化屬性性是數(shù)值的的，并在在值之間間具有一一個(gè)隱含含的序，如（age，income，price）。第四節(jié)挖挖掘掘關(guān)系數(shù)數(shù)據(jù)庫(kù)和和數(shù)據(jù)倉(cāng)倉(cāng)庫(kù)的多多維關(guān)聯(lián)聯(lián)規(guī)則1、多維維關(guān)聯(lián)規(guī)規(guī)則挖掘多維維關(guān)聯(lián)規(guī)規(guī)則的技技術(shù)可以以根據(jù)量量化屬性性的處理理分為三三種基本本方法：使用預(yù)定定義的概概念分層層對(duì)量化化屬性離離散化，該方法法稱(chēng)為使用量化化屬性的的靜態(tài)離離散化挖挖掘多維維關(guān)

29、聯(lián)規(guī)規(guī)則；根據(jù)數(shù)據(jù)據(jù)的分布布，將量量化的屬屬性離散散化到“箱”，這種方方法挖掘掘的關(guān)聯(lián)聯(lián)規(guī)則稱(chēng)稱(chēng)為量化關(guān)聯(lián)聯(lián)規(guī)則；量化屬性性離散化化，以符符合區(qū)間間數(shù)據(jù)的的語(yǔ)義，這種量量化關(guān)聯(lián)聯(lián)規(guī)則稱(chēng)稱(chēng)作基于距離離的關(guān)聯(lián)聯(lián)規(guī)則。第四節(jié)挖挖掘掘關(guān)系數(shù)數(shù)據(jù)庫(kù)和和數(shù)據(jù)倉(cāng)倉(cāng)庫(kù)的多多維關(guān)聯(lián)聯(lián)規(guī)則2、使用用量化屬屬性挖掘掘多維關(guān)關(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é)挖挖掘掘關(guān)系數(shù)數(shù)據(jù)庫(kù)和和數(shù)據(jù)倉(cāng)倉(cāng)庫(kù)的多多維關(guān)聯(lián)聯(lián)規(guī)則3、挖掘掘量化關(guān)關(guān)聯(lián)規(guī)則則量化關(guān)

30、聯(lián)聯(lián)規(guī)則是是多維關(guān)關(guān)聯(lián)規(guī)則則，其中中數(shù)值屬屬性動(dòng)態(tài)態(tài)離散化化，以滿滿足某種種挖掘標(biāo)標(biāo)準(zhǔn)，如如最大挖挖掘規(guī)則則的置信信度。量量化關(guān)聯(lián)聯(lián)規(guī)則如如：age（X，”2333”）income（X，”32k42k”）buys（X，”laptop”）這種規(guī)則則包含左左邊兩個(gè)個(gè)量化維維（量化化屬性），右邊邊一個(gè)分分類(lèi)屬性性，稱(chēng)為為2-維量量化關(guān)聯(lián)聯(lián)規(guī)則。第四節(jié)挖挖掘掘關(guān)系數(shù)數(shù)據(jù)庫(kù)和和數(shù)據(jù)倉(cāng)倉(cāng)庫(kù)的多多維關(guān)聯(lián)聯(lián)規(guī)則3、挖掘掘量化關(guān)關(guān)聯(lián)規(guī)則則對(duì)于量化化關(guān)聯(lián)規(guī)規(guī)則可以以通過(guò)關(guān)聯(lián)規(guī)則則聚類(lèi)系系統(tǒng)ARCS（associationruleclustering system）方法找出出關(guān)聯(lián)規(guī)規(guī)則。ARCS的基本步步驟有：分箱

31、：等等寬分箱箱、等深深分箱、基于同同質(zhì)的分分箱找頻繁謂謂詞集關(guān)聯(lián)規(guī)則則聚類(lèi)第四節(jié)挖挖掘掘關(guān)系數(shù)數(shù)據(jù)庫(kù)和和數(shù)據(jù)倉(cāng)倉(cāng)庫(kù)的多多維關(guān)聯(lián)聯(lián)規(guī)則4、挖掘掘基于距距離的關(guān)關(guān)聯(lián)規(guī)則則關(guān)聯(lián)規(guī)則則的一個(gè)個(gè)缺點(diǎn)是是它們不不允許近近似的屬屬性值，而往往往在一些些情形下下，需要要考察屬屬性值的的接近性性，支持持度和置置信度均均不支持持這種近近似，所所以需要要引入基于距離離的關(guān)聯(lián)聯(lián)規(guī)則挖掘。這這種規(guī)則則緊扣區(qū)區(qū)間數(shù)據(jù)據(jù)的語(yǔ)義義，并允允許數(shù)據(jù)據(jù)值的近近似。量量化關(guān)聯(lián)聯(lián)規(guī)則無(wú)無(wú)法實(shí)現(xiàn)現(xiàn)，因?yàn)闉槲纯疾觳鞌?shù)據(jù)點(diǎn)點(diǎn)之間或或區(qū)間之之間的相相對(duì)距離離。第四節(jié)挖挖掘掘關(guān)系數(shù)數(shù)據(jù)庫(kù)和和數(shù)據(jù)倉(cāng)倉(cāng)庫(kù)的多多維關(guān)聯(lián)聯(lián)規(guī)則4、挖掘掘基于距距離的關(guān)關(guān)聯(lián)規(guī)則則通常使用用一個(gè)兩兩遍算法法挖掘基基于距離離的關(guān)聯(lián)聯(lián)規(guī)則。第一遍使使用聚類(lèi)類(lèi)找出區(qū)區(qū)間或簇簇；第二遍搜搜索頻繁繁地一起起出現(xiàn)的的簇組得得到基于于距離的關(guān)關(guān)聯(lián)規(guī)則則。第五節(jié)關(guān)關(guān)聯(lián)聯(lián)挖掘到到關(guān)聯(lián)分分析問(wèn)題：挖挖掘了關(guān)關(guān)聯(lián)規(guī)則則后，數(shù)數(shù)據(jù)挖掘掘系統(tǒng)如如何指出出哪些規(guī)規(guī)則是用用戶感興興趣的？大部分關(guān)關(guān)聯(lián)規(guī)則則挖掘算算法使用用支持度度-置信信度框架架。盡管管使用最最小支持持度-置置信度閾閾值排除除了一些些無(wú)趣的的規(guī)則的的探察，仍然會(huì)會(huì)產(chǎn)生一一些對(duì)用用戶來(lái)說(shuō)說(shuō)不感興興趣的規(guī)規(guī)則。第五節(jié)關(guān)關(guān)聯(lián)聯(lián)挖掘到到關(guān)聯(lián)分分析1、強(qiáng)關(guān)關(guān)聯(lián)規(guī)則則不一定定是有趣趣的例如，假假設(shè)