【導(dǎo)讀】并行關(guān)聯(lián)規(guī)則挖掘。關(guān)聯(lián)規(guī)則反映一個(gè)事物與其他事物之間的相互依存性。如果兩個(gè)或者多個(gè)事物之間存在一定的關(guān)。關(guān)聯(lián)規(guī)則表示了項(xiàng)之間的關(guān)系。我們是否可假定?通常,數(shù)據(jù)包含:. 在事務(wù)數(shù)據(jù)庫,關(guān)系數(shù)據(jù)庫和其它信息。模式,關(guān)聯(lián),相關(guān),或因果關(guān)系的結(jié)構(gòu).條件概率P(B|A)表示A發(fā)生的條件下B也發(fā)生的概率.關(guān)聯(lián)規(guī)則根據(jù)以下兩個(gè)標(biāo)準(zhǔn)(包含或排。最小支持度–表示規(guī)則中的所有項(xiàng)在事務(wù)。項(xiàng)集–仸意項(xiàng)的集合。頻繁(戒大)項(xiàng)集–滿足最小支持度的項(xiàng)。給定一個(gè)項(xiàng)集,容易生成關(guān)聯(lián)規(guī)則.找出所有的頻繁項(xiàng)集。保留滿足最小可信度的規(guī)則。IBM公司Almaden研究中心的等。人在1993年提出的AIS和SETM。在1994年提出Apriori和AprioriTid。為每一個(gè)子集掃描n個(gè)事務(wù)。測(cè)試s為T的子集:O. 隨著項(xiàng)的個(gè)數(shù)呈指數(shù)級(jí)增長(zhǎng)!我們能否做的更好?

　　

【正文】 關(guān)聯(lián)規(guī)則 , 相關(guān) (correlation)和因果 (causality), 比率 (ratio)規(guī)則 , 序列 (sequential) 模式 ,浮現(xiàn) (emerging)模式 , temporal associations, 局部周期 (partial periodicity) ? 分類 (classification),聚類 (clustering),冰山立方體( iceberg cubes), 等等 . 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 86 多層關(guān)聯(lián)規(guī)則 ? 項(xiàng)常常構(gòu)成層次 ? 可伸縮的 (flexible)支持度設(shè)置 : 在較低層的項(xiàng)預(yù)期有較低的支持度 . ? 事務(wù)數(shù)據(jù)庫可以基于維度和層次編碼 ? 探尋共享多層挖掘 統(tǒng)一支持度 Milk [support = 10%] 2% Milk [support = 6%] Skim Milk [support = 4%] Level 1 min_sup = 5% Level 2 min_sup = 5% Level 1 min_sup = 5% Level 2 min_sup = 3% 減少的支持度 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 87 可伸縮的支持度約束的多層 /多維 (ML/MD)關(guān)聯(lián)規(guī)則 ? 為什么設(shè)置 可伸縮 的支持度 ? ? 實(shí)際生活中項(xiàng)的出現(xiàn)頻率變化巨大 ? 在一個(gè)商店購物籃中的鉆石 ,手表 ,鋼筆 ? 統(tǒng)一的支持度未必是一個(gè)有趣的模型 ? 一個(gè) 可伸縮 模型 ? 較低層的 ,較多維的組合以及長(zhǎng)模式通常具有較小的支持度 ? 總體規(guī)則應(yīng)該要容易說明和理解 ? 特殊的項(xiàng)和特殊的項(xiàng)的組合可以特別設(shè)定 (最小支持度 )以及擁有更高的優(yōu)先級(jí) 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 88 多維關(guān)聯(lián)規(guī)則 ? 單維規(guī)則 : buys(X, “milk”) ? buys(X, “bread”) ? 多維規(guī)則 : ? 2 個(gè)維度或謂詞 ( predicates) ? 跨維度 (Interdimension)關(guān)聯(lián)規(guī)則 (無重復(fù)謂詞 ) age(X,”1925”) ? occupation(X,“student”) ? buys(X,“coke”) ? 混合維度 (hybriddimension)關(guān)聯(lián)規(guī)則 (重復(fù)謂詞 ) age(X,”1925”) ? buys(X, “popcorn”) ? buys(X, “coke”) ? 分類 (Categorical)屬性 ? 有限的幾個(gè)可能值 ,值之間不可排序 ? 數(shù)量 (Quantitative)屬性 ? 數(shù)值的 ,值之間有固有的排序 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 89 多層關(guān)聯(lián)規(guī)則 :冗余濾除 ? 根據(jù)項(xiàng)之間的 ”先輩 ” (ancestor)關(guān)系 ,一些規(guī)則可能是冗余的 . ? 示例 ? milk ? wheat bread [support = 8%, confidence = 70%] ? 2% milk ? wheat bread [support = 2%, confidence = 72%] ? 我們說第 1個(gè)規(guī)則是第 2個(gè)規(guī)則的先輩 . ? 一個(gè)規(guī)則是冗余的 ,當(dāng)其支持度接近基于先輩規(guī)則的 ”預(yù)期 ”(expected)值 . 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 90 多層關(guān)聯(lián)規(guī)則 :逐步深化 (Progressive Deepening) ? 一個(gè)自上而下的 ,逐步深化的方法 : ? 首先挖掘高層的頻繁項(xiàng) : milk (15%), bread (10%) ? 然后挖掘它們的較低層 ”較弱 ” (weaker)頻繁項(xiàng) : 2% milk (5%), wheat bread (4%) ? 多層之間不同的最小支持度閾值導(dǎo)致了不同的算法 : ? 如果在多個(gè)層次間采用了相同的最小支持度 ,若 t的任何一個(gè)先輩都是非頻繁的則扔棄 (toss)t. ? 如果在較低層采用了減少的最小支持度，則只檢驗(yàn)?zāi)切┫容叺闹С侄仁穷l繁的／不可忽略的派生（ descendents）即可． 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 91 多維關(guān)聯(lián)規(guī)則挖掘的技術(shù) ? 搜索頻繁 k謂詞集 (predicate set): ? 示例 : {age, occupation, buys}是一個(gè) 3謂詞集 以 age處理 的方式 ,技術(shù)可以如下分類 1. 利用數(shù)量屬性的統(tǒng)計(jì)離散 (static discretization)方法 利用預(yù)先確定的概念層次對(duì)數(shù)量屬性進(jìn)行統(tǒng)計(jì)離散化 2. 量化關(guān)聯(lián)規(guī)則 ? 基于數(shù)據(jù)的分布 ,數(shù)量屬性被動(dòng)態(tài)地離散化到不同的容器空間(bins) 3. 基于距離 (Distancebased)的關(guān)聯(lián)規(guī)則 ? 這是一個(gè)動(dòng)態(tài)離散化的過程 ,該過程考慮數(shù)據(jù)點(diǎn)之間的距離 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 92 數(shù)量屬性的統(tǒng)計(jì)離散化 ? 挖掘之前利用概念層次離散化 ? 數(shù)值被范圍 (ranges)替代 . ? 關(guān)系數(shù)據(jù)庫中 ,找出所有的頻繁 k謂詞 (predicate)集要求 k 或 k+1次表掃描 . ? 數(shù)據(jù)立方體 (data cube)非常適合數(shù)據(jù)挖掘 . ? N維立方體的 cells 與謂詞集 ( predicate sets)相對(duì)應(yīng) . ? 通過數(shù)據(jù)立方體挖掘會(huì)非?？焖?. (ine) (age) () (buys) (age, ine) (age,buys) (ine,buys) (age,ine,buys) 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 93 量化關(guān)聯(lián)規(guī)則 age(X,”3034”) ? ine(X,”24K 48K”) ? buys(X,”high resolution TV”) ? 數(shù)值屬性動(dòng)態(tài)離散化 ? 這樣挖掘的規(guī)則的可信度或緊密度最大化 ? 2維 量化關(guān)聯(lián)規(guī)則 : Aquan1 ? Aquan2 ? Acat ? 示例 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 94 Mining Distancebased Association Rules ? Binning methods do not capture the semantics of interval data ? Distancebased partitioning, more meaningful discretization considering: ? density/number of points in an interval ? “closeness” of points in an interval P ric e($ )Eq uiw idt h(w idt h $1 0)Eq uid ep t h(de pt h 2)D is t an c eba s ed7 [ 0 , 1 0 ] [ 7 , 2 0 ] [ 7 , 7 ]20 [ 1 1 , 2 0 ] [ 2 2 , 5 0 ] [ 2 0 , 2 2 ]22 [ 2 1 , 3 0 ] [ 5 1 , 5 3 ] [ 5 0 , 5 3 ]50 [ 3 1 , 4 0 ]51 [ 4 1 , 5 0 ]53 [ 5 1 , 6 0 ]2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 95 Interestingness Measure: Correlations (Lift) ? play basketball ? eat cereal [40%, %] is misleading ? The overall percentage of students eating cereal is 75% which is higher than %. ? play basketball ? not eat cereal [20%, %] is more accurate, although with lower support and confidence ? Measure of dependent/correlated events: lift Basketball Not basketball Sum (row) Cereal 2020 1750 3750 Not cereal 1000 250 1250 Sum(col.) 3000 2020 5000 )()()(, BPAPBAPc or rBA??2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 96 內(nèi)容提要 ? 引言 ? Apriori 算法 ? FPgrowth 算法 ? 并行關(guān)聯(lián)規(guī)則挖掘 ? 多維關(guān)聯(lián)規(guī)則挖掘 ? 相關(guān)規(guī)則 ? 關(guān)聯(lián)規(guī)則改進(jìn) ? 總結(jié) 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 97 相關(guān)規(guī)則 (Correlation Rules) ? “ Beyond Market Baskets,” Brin et al. ? 假設(shè)執(zhí)行關(guān)聯(lián)規(guī)則挖掘 c c row t 20 5 25 t 70 5 75 col 90 10 100 tea = coffee 20% support 80% confidence but 90% of the people buy coffee anyway! 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 98 相關(guān)規(guī)則 ? 一種度量是計(jì)算相關(guān)性 ? 若兩個(gè)隨機(jī)變量 A 和 B 是統(tǒng)計(jì)獨(dú)立的 ? 對(duì) tea 和 coffee: 1)()( )( ?? BPAP BAP)()( )( ?? cPtP ctP2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 99 相關(guān)規(guī)則 ? 利用 ?2 統(tǒng)計(jì)檢驗(yàn)來測(cè)試獨(dú)立性 ? 設(shè) n為購物籃的總數(shù) ? 設(shè) k為考慮的項(xiàng)的總數(shù) ? 設(shè) r 為一個(gè)包含項(xiàng) (ij, ij)的規(guī)則 ? 設(shè) O(r) 表示包含規(guī)則 r的購物籃的數(shù)量 (即頻率 ) ? 對(duì)單個(gè)項(xiàng) ij,設(shè) E[ij] = O(ij) (反過來即為 n E[ij]) ? E[r] = n * E[r1]/n * … * E[rk] / n 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 100 相關(guān)規(guī)則 ? ?2 統(tǒng)計(jì)量定義為 ? Look up for significance value in a statistical textbook ? There are k1 degrees of freedom ? If test fails cannot reject independence, otherwise contigency table represents dependence. ????Rr rErErO][])[)(( 22?2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 101 示例 ? Back to tea and coffee ? E[t] = 25, E[t]=75, E[c]=90, E[c]=10 ? E[tc]=100 * 25/100 * 90 /100= ? O(tc) = 20 ? Contrib. to ?2 = (20 )2 / = ? Calculate for the rest to get ?2= ? Not significant at 95% level ( for k=2) ? Cannot reject independence assumption c c row t 20 5 25 t 70 5 75 col 90 10 100 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 102 興趣度（ Interest） ? If ?2 test shows significance, then want to find most interesting cell(s) in table ? I(r) = O(r)/E[r] ? Look for values far away from 1 ? I(tc) = 20/ = ? I(tc) = 5/ = 2 ? I(tc) = 70/ = ? I(tc) = 5/ = 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 103 ?2 統(tǒng)計(jì)量的性質(zhì) ? 上封閉性 (Upward closed) ? 若一個(gè) k項(xiàng)集是相關(guān)的 ,則其所有的超集也是相關(guān)的 . ? 尋找最小的相關(guān)的項(xiàng)集 ? 沒有子集是相關(guān)的 ? 能否將 apriori and ?2 統(tǒng)計(jì)量有效地結(jié)合 ? No generate and prune as in supportconfidence 2020/11/4 史忠植 關(guān)聯(lián)規(guī)則 104 其它度量 (Measures) ??l ( A ? B ) ? P ( A , B )P ( A ) P ( B )TID Items