大型數據庫中的關聯規(guī)則挖掘

1、大型數據庫中的關聯規(guī)則挖掘,什么是關聯規(guī)則挖掘？,關聯規(guī)則挖掘：從事務數據庫，關系數據庫和其他信息存儲中的大量數據的項集之間發(fā)現有趣的、頻繁出現的模式、關聯和相關性。應用：購物籃分析、分類設計、捆綁銷售等,“尿布與啤酒”——典型關聯分析案例,采用關聯模型比較典型的案例是“尿布與啤酒”的故事。在美國，一些年輕的父親下班后經常要到超市去買嬰兒尿布，超市也因此發(fā)現了一個規(guī)律，在購買嬰兒尿布的年輕父親們中，有30%～40%的人同時要買一些

2、啤酒。超市隨后調整了貨架的擺放，把尿布和啤酒放在一起，明顯增加了銷售額。同樣的，我們還可以根據關聯規(guī)則在商品銷售方面做各種促銷活動。,購物籃分析,如果問題的全域是商店中所有商品的集合，則對每種商品都可以用一個布爾量來表示該商品是否被顧客購買，則每個購物籃都可以用一個布爾向量表示；而通過分析布爾向量則可以得到商品被頻繁關聯或被同時購買的模式，這些模式就可以用關聯規(guī)則表示（0001001100，這種方法丟失了什么信息？）關聯規(guī)則的兩個興趣

3、度度量支持度置信度,關聯規(guī)則：基本概念,給定：項的集合：I={i1,i2,...,in}任務相關數據D是數據庫事務的集合，每個事務T則是項的集合，使得每個事務由事務標識符TID標識；A,B為兩個項集，事務T包含A當且僅當則關聯規(guī)則是如下蘊涵式：其中 并且 ，規(guī)則 在事務集D中成立，并且具有支持度s和置信度c,,,,,,,基本概念——

4、示例,項的集合 I={A,B,C,D,E,F}每個事務T由事務標識符TID標識，它是項的集合 比如：TID(2000)={A,B,C}任務相關數據D是數據庫事務的集合,D,規(guī)則度量：支持度和置信度,,,,,,Customerbuys diaper,Customerbuys both,Customerbuys beer,,對所有滿足最小支持度和置信度的關聯規(guī)則支持度s是指事務集D中包含 的百分比置信度

5、c是指D中包含A的事務同時也包含B的百分比假設最小支持度為50%，最小置信度為50%，則有如下關聯規(guī)則A ? C (50%, 66.6%)C ? A (50%, 100%),,,,,,大型數據庫關聯規(guī)則挖掘 (1),基本概念k－項集：包含k個項的集合{牛奶，面包，黃油}是個3－項集項集的頻率是指包含項集的事務數如果項集的頻率大于（最小支持度×D中的事務總數），則稱該項集為頻繁項集,大型數據庫關聯規(guī)則挖

6、掘 (2),大型數據庫中的關聯規(guī)則挖掘包含兩個過程：找出所有頻繁項集大部分的計算都集中在這一步由頻繁項集產生強關聯規(guī)則即滿足最小支持度和最小置信度的規(guī)則,關聯規(guī)則挖掘分類 (1),關聯規(guī)則有多種分類：根據規(guī)則中所處理的值類型布爾關聯規(guī)則量化關聯規(guī)則（規(guī)則描述的是量化的項或屬性間的關聯性）根據規(guī)則中涉及的數據維單維關聯規(guī)則（僅涉及buys這個維）多維關聯規(guī)則,,,關聯規(guī)則挖掘分類 (2),根據規(guī)則集所涉及的抽象

7、層單層關聯規(guī)則多層關聯規(guī)則 （在不同的抽象層發(fā)現關聯規(guī)則）根據關聯挖掘的各種擴充挖掘最大的頻繁模式（該模式的任何真超模式都是非頻繁的）挖掘頻繁閉項集（一個項集c是頻繁閉項集，如果不存在其真超集c’，使得每個包含c的事務也包含c’）（最大的頻繁模式和頻繁閉項集可以用來減少挖掘中產生的頻繁項集）,由事務數據庫挖掘單維布爾關聯規(guī)則,最簡單的關聯規(guī)則挖掘，即單維、單層、布爾關聯規(guī)則的挖掘。,最小支持度 50%最小置信度 50

8、%,對規(guī)則A ? C，其支持度 =50%置信度,,,Apriori算法 (1),Apriori算法是挖掘布爾關聯規(guī)則頻繁項集的算法Apriori算法利用的是Apriori性質：頻繁項集的所有非空子集也必須是頻繁的。 模式不可能比A更頻繁的出現Apriori算法是反單調的，即一個集合如果不能通過測試，則該集合的所有超集也不能通過相同的測試

9、。Apriori性質通過減少搜索空間，來提高頻繁項集逐層產生的效率,,Apriori算法 (2),Apriori算法利用頻繁項集性質的先驗知識（prior knowledge），通過逐層搜索的迭代方法，即將k-項集用于探察(k+1)-項集，來窮盡數據集中的所有頻繁項集。先找到頻繁1-項集集合L1,然后用L1找到頻繁2-項集集合L2，接著用L2找L3，直到找不到頻繁k-項集，找每個Lk需要一次數據庫掃描。,Apriori算法步驟,Ap

10、riori算法由連接和剪枝兩個步驟組成。連接：為了找Lk，通過Lk-1與自己連接產生候選k-項集的集合，該候選k項集記為Ck。Lk-1中的兩個元素L1和L2可以執(zhí)行連接操作 的條件是Ck是Lk的超集，即它的成員可能不是頻繁的，但是所有頻繁的k-項集都在Ck中（為什么？）。因此可以通過掃描數據庫，通過計算每個k-項集的支持度來得到Lk 。為了減少計算量，可以使用Apriori性質，即如果一個k-項集的(k

11、-1)-子集不在Lk-1中，則該候選不可能是頻繁的，可以直接從Ck刪除。,,,Apriori算法——示例,Database TDB,1st scan,,C1,L1,L2,C2,C2,,2nd scan,,,C3,L3,3rd scan,,,,最小支持計數：2,使用Apiori性質由L2產生C3,1 ．連接：C3=L2 L2= {{A,C},{B,C},{B,E}{C,E}} {{A,C},{B,C},{B,E}{

12、C,E}} = {{A,B,C},{A,C,E},{B,C,E}}2．使用Apriori性質剪枝：頻繁項集的所有子集必須是頻繁的，對候選項C3，我們可以刪除其子集為非頻繁的選項：{A,B,C}的2項子集是{A,B},{A,C},{B,C}，其中{A,B}不是L2的元素，所以刪除這個選項；{A,C,E}的2項子集是{A,C},{A,E},{C,E}，其中{A,E} 不是L2的元素，所以刪除這個選項；{B,C,E}的2項子集是{B,

13、C},{B,E},{C,E}，它的所有2－項子集都是L2的元素，因此保留這個選項。3．這樣，剪枝后得到C3={{B,C,E}},,由頻繁項集產生關聯規(guī)則,同時滿足最小支持度和最小置信度的才是強關聯規(guī)則，從頻繁項集產生的規(guī)則都滿足支持度要求，而其置信度則可由一下公式計算：每個關聯規(guī)則可由如下過程產生：對于每個頻繁項集l，產生l的所有非空子集；對于每個非空子集s，如果 則輸出規(guī)則“

14、 ”,,,,,多層關聯規(guī)則 (1),數據項中經常會形成概念分層底層的數據項，其支持度往往也較低這意味著挖掘底層數據項之間的關聯規(guī)則必須定義不同的支持度,All,Computeraccessory,software,laptop,financial,,,,,,mouse,color,,,printer,computer,,,desktop,,IBM,edu.,,,Microsoft,b/w,,,HP,,Son

15、y,wristpad,,,Logitech,,TID,Items,,,,,,,,,,,,T1,{IBM D/C, Sony b/w},,,,,,,,,T2,{Ms. edu. Sw., Ms. fin. Sw.},,,,,,,,,T3,{Logi. mouse, Ergoway wrist pad},,,,,,,,,T4,{IBM D/C, Ms. Fin. Sw.},,,,,,,,,T5,{IBM D/C},,,,,,,,,,,,,

16、,,,,Ergoway,多層關聯規(guī)則 (2),在適當的等級挖掘出來的數據項間的關聯規(guī)則可能是非常有用的通常，事務數據庫中的數據也是根據維和概念分層來進行儲存的這為從事務數據庫中挖掘不同層次的關聯規(guī)則提供了可能。在多個抽象層挖掘關聯規(guī)則，并在不同的抽象層進行轉化，是數據挖掘系統(tǒng)應該提供的能力,挖掘多層關聯規(guī)則的方法,通常，多層關聯規(guī)則的挖掘還是使用置信度－支持度框架，可以采用自頂向下策略請注意：概念分層中，一個節(jié)點的支持度肯定不小

17、于該節(jié)點的任何子節(jié)點的支持度由概念層1開始向下，到較低的更特定的概念層，對每個概念層的頻繁項計算累加計數每一層的關聯規(guī)則挖掘可以使用Apriori等多種方法例如：先找高層的關聯規(guī)則：computer -> printer [20%, 60%]再找較低層的關聯規(guī)則：laptop -> color printer [10%, 50%],多層關聯——一致支持度,一致支持度：對所有層都使用一致的最小支持度優(yōu)點：搜索時容易

18、采用優(yōu)化策略，即一個項如果不滿足最小支持度，它的所有子項都可以不用搜索缺點：最小支持度值設置困難太高：將丟掉出現在較低抽象層中有意義的關聯規(guī)則太低：會在較高層產生太多的無興趣的規(guī)則,多層關聯——遞減支持度,使用遞減支持度，可以解決使用一致支持度時在最小支持度值上設定的困難遞減支持度：在較低層使用遞減的最小支持度每一層都有自己的一個獨立的最小支持度抽象層越低，對應的最小支持度越小,min_sup = 5%,min_sup =

19、5%,min_sup = 3%,多層關聯——搜索策略 (1),具有遞減支持度的多層關聯規(guī)則的搜索策略逐層獨立：完全的寬度搜索，沒有頻繁項集的背景知識用于剪枝層交叉單項過濾：一個第i層的項被考察，當且僅當它在第（i-1）層的父節(jié)點是頻繁的（P165, 圖6-14）(computer)?( laptop computer, desktop computer)層交叉k項集過濾：一個第i層的k項集被考察，當且僅當它在第(i-1)層的對應

20、父節(jié)點k-項集是頻繁的（P165, 圖6-15）(computer, printer)?(( laptop computer, color printer), (desktop computer, b/w printer) …),多層關聯——搜索策略 (2),搜索策略比較逐層獨立策略條件松，可能導致底層考察大量非頻繁項層交叉k項集過濾策略限制太強，僅允許考察頻繁k-項集的子女層交叉單項過濾策略是上述兩者的折中，但仍可能丟失低層頻

21、繁項（圖6-14),受控的層交叉單項過濾策略,層交叉單項過濾策略的改進版本設置一個層傳遞臨界值，用于向較低層傳遞相對頻繁的項。即如果滿足層傳遞臨界值，則允許考察不滿足最小支持度臨界值的項的子女用戶對進一步控制多概念層上的挖掘過程有了更多的靈活性，同時減少無意義關聯的考察和產生,min_sup = 12%level_passage_support = 8%,min_sup = 3%,檢查冗余的多層關聯規(guī)則,挖掘多層關聯規(guī)則時，由于

22、項間的“祖先”關系，有些發(fā)現的規(guī)則將是冗余的例如：desktop computer => b/w printer [sup=8%, con=70%] (1)IBM desktop computer => b/w printer [sup=2%, con=72%] (2)上例中，我們說第一個規(guī)則是第二個規(guī)則的“祖先”如果規(guī)則(2)中的項用它在概念分層中的“祖先”代替，能得到(1)，而且(1)的支持度和置信度都接近“

23、期望”值，則(1)是冗余的。,多維關聯規(guī)則——概念,單維關聯規(guī)則：buys(X, “milk”) ＝ buys(X, “bread”)多維關聯規(guī)則：涉及兩個或多個維或謂詞的關聯規(guī)則維間關聯規(guī)則：不包含重復的謂詞age(X,”19-25”) ∧occupation(X,“student”) => buys(X,“coke”)混合維關聯規(guī)則：包含某些謂詞的多次出現age(X,”19-25”) ∧buys(X, “popco

24、rn”) => buys(X, “coke”)在多維關聯規(guī)則挖掘中，我們搜索的不是頻繁項集，而是頻繁謂詞集。k-謂詞集是包含k個合取謂詞的集合。例如：{age, occupation, buys}是一個3-謂詞集,挖掘多維關聯規(guī)則的技術,數據屬性可以分為分類屬性和量化屬性分類屬性具有有限個不同值，值之間無序量化屬性數值類型的值，并且值之間有一個隱含的序挖掘多維關聯規(guī)則的技術可以根據量化屬性的處理分為三種基本方法：1

25、. 量化屬性的靜態(tài)離散化使用預定義的概念分層對量化屬性進行靜態(tài)地離散化2. 量化關聯規(guī)則根據數據的分布，將量化屬性離散化到“箱”3. 基于距離的關聯規(guī)則考慮數據點之間的距離，動態(tài)地離散化量化屬性,多維關聯規(guī)則挖掘——使用量化屬性的靜態(tài)離散化,量化屬性使用預定義的概念分層，在挖掘前進行離散化數值屬性的值用區(qū)間代替如果任務相關數據存在關系數據庫中，則找出所有頻繁的k-謂詞集將需要k或k+1次表掃描數據立方體技術非常適合挖掘多

26、維關聯規(guī)則n-維方體的單元用于存放對應n-謂詞集的計數或支持度，0-D方體用于存放任務相關數據的事務總數如果包含感興趣的維的數據立方體已經存在并物化，挖掘將會很快，同時可以利用Apriori性質：頻繁謂詞集的每個子集也必須是頻繁的,挖掘量化關聯規(guī)則 (1),量化關聯規(guī)則中，數值屬性將根據某種挖掘標準，進行動態(tài)的離散化例如：最大化挖掘規(guī)則的置信度和緊湊性為了簡化量化關聯規(guī)則挖掘的討論，我們將聚焦于類似以下形式的2-維量化關聯規(guī)則：

27、Aquan1 ? Aquan2 ? Acat（兩個量化屬性和一個分類屬性間的關聯）例如： age(X,”30-39”) ? income(X,”42K - 48K”) ? buys(X,”high resolution TV”),挖掘量化關聯規(guī)則 (2),找出這類2-維量化關聯規(guī)則的方法：關聯規(guī)則聚類系統(tǒng)(ARCS)一種源于圖像處理的技術，該技術將量化屬性對映射到滿足給定分類屬性條件的2-D柵格上，然后通過搜索柵格點的聚類而產生關

28、聯規(guī)則,關聯規(guī)則聚類系統(tǒng)(ARCS) (1),ARCS過程中的步驟包括1. 分箱（根據不同分箱方法創(chuàng)建一個2-D數組），本步驟的目的在于減少量化屬性相對應的巨大的值個數，使得2-D柵格的大小可控等寬分箱等深分箱基于同質的分箱（每個箱中元組一致分布）2. 找出頻繁謂詞集掃描分箱后形成的2-D數組，找出滿足最小支持度和置信度的頻繁謂詞集,關聯規(guī)則聚類系統(tǒng)(ARCS) (2),3. 關聯規(guī)則聚類將上一步得到的強關聯規(guī)則映射到2-

29、D柵格上，使用聚類算法，掃描柵格，搜索規(guī)則的矩形聚類,,,,,,,,,ARCS的局限性,所挖掘的關聯規(guī)則左手邊只能是量化屬性規(guī)則的左手邊只能有兩個量化屬性（2-D柵格的限制）一種不基于柵格的，可以發(fā)現更一般關聯規(guī)則的技術，其中任意個數的量化屬性和分類屬性可以出現在規(guī)則的兩端等深分箱動態(tài)劃分根據部分完全性的度量進行聚類,挖掘基于距離的關聯規(guī)則,等寬劃分將很近的值分開，并創(chuàng)建沒有數據的區(qū)間等深劃分將很遠的值放在一組基于距離的關聯

30、規(guī)則挖掘考慮屬性值的接近性，緊扣區(qū)間數據的語義，并允許值的類似基于距離的關聯規(guī)則挖掘的兩遍算法：1. 使用聚類找出區(qū)間或簇2. 搜索頻繁的一起出現的簇組，得到基于距離的關聯規(guī)則,因為未考慮數據點之間或區(qū)間的相對距離，分箱方法不是總能緊扣區(qū)間數據的語義,關聯規(guī)則的興趣度度量,客觀度量兩個流行的度量指標支持度置信度主觀度量最終，只有用戶才能確定一個規(guī)則是否有趣的，而且這種判斷是主觀的，因不同的用戶而異；通常認為一個規(guī)則（模式

31、）是有趣的，如果：它是出人意料的可行動的（用戶可以使用該規(guī)則做某些事情）挖掘了關聯規(guī)則后，哪些規(guī)則是用戶感興趣的？強關聯規(guī)則是否就是有趣的？,對強關聯規(guī)則的批評（1）,例1：(Aggarwal & Yu, PODS98)在5000個學生中3000個打籃球3750個喝麥片粥2000個學生既打籃球又喝麥片粥然而，打籃球 => 喝麥片粥 [40%, 66.7%]是錯誤的，因為全部學生中喝麥片粥的比率是75%，比打

32、籃球學生的66.7%要高打籃球 => 不喝麥片粥 [20%, 33.3%]這個規(guī)則遠比上面那個要精確，盡管支持度和置信度都要低的多,對強關聯規(guī)則的批評（2）,例1：(書P172，表6-4)上述數據可以得出buys(X, “computer games”) => buys(X, “videos”) [40%, 60%]但其實全部人中購買錄像帶的人數是75%，比60%多；事實上錄像帶和游戲是負相關的。由此可見A =&g

33、t; B的置信度有欺騙性，它只是給出A,B條件概率的估計，而不度量A,B間蘊涵的實際強度。,由關聯分析到相關分析,我們需要一種度量事件間的相關性或者是依賴性的指標當項集A的出現獨立于項集B的出現時，P(A∪B)=P(A)P(B)，即corrA,B＝1，表明A與B無關， corrA,B >1表明A與B正相關， corrA,B <1表明A與B負相關將相關性指標用于前面的例子，可以得出錄像帶和游戲將的相關性為：P({g