1、第六章 挖掘頻繁模式、關(guān)聯(lián)和相關(guān)性：基本概念和方法,報(bào)告人：唐忠任,數(shù)據(jù)挖掘概念與技術(shù),哪些模式是有趣的：模式評(píng)估方法,哪些模式是有趣的？,本節(jié)學(xué)習(xí)目標(biāo),本節(jié)首先考察為何關(guān)聯(lián)規(guī)則也可能是無(wú)趣的并且可能是誤導(dǎo)。 然后討論如何用基于相關(guān)分析的附加度量加強(qiáng)支持度置信度框架。,強(qiáng)規(guī)則不一定是有趣的,規(guī)則是否有趣可以主觀(guān)或客觀(guān)地評(píng)估。最終，只有用戶(hù)能夠評(píng)判一個(gè)給定的規(guī)則是否是有趣的，并且這種判斷是主觀(guān)的，可能因用戶(hù)而異。然而，根據(jù)數(shù)據(jù)“背后”的統(tǒng)計(jì)量，客觀(guān)興趣度度量可以用來(lái)清除無(wú)趣的規(guī)則，而不用用戶(hù)提供。 “我們?nèi)绾巫R(shí)別哪些強(qiáng)關(guān)聯(lián)規(guī)則是真正有趣的？”讓我們考查下面的例子。,一個(gè)誤導(dǎo)的“強(qiáng)”關(guān)聯(lián)規(guī)則,假設(shè)

2、我們對(duì)分析涉及購(gòu)買(mǎi)計(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%。將發(fā)現(xiàn)下面的關(guān)聯(lián)規(guī)則：,從關(guān)聯(lián)分析到相關(guān)分析,正如我們?cè)谏厦嬉呀?jīng)看到的，支持度和置信度不足以過(guò)濾掉無(wú)趣的關(guān)聯(lián)規(guī)則。為了處理這個(gè)問(wèn)題，可以使用相關(guān)性度量來(lái)擴(kuò)充關(guān)聯(lián)規(guī)則的支持度置信度框架。這導(dǎo)致如下形式的相關(guān)規(guī)則（correlation rule） A=Bsup

3、port, confidence, correlation 也就是說(shuō)，相關(guān)規(guī)則不僅用支持度和置信度度量，而且還用項(xiàng)集A和B之間的相關(guān)性度量有許多不同的相關(guān)性度量可供選擇。本節(jié)研究各種相關(guān)性度量，確定哪些度量適合挖掘大型數(shù)據(jù)集。,提升度,提升度（lift）是一種簡(jiǎn)單的相關(guān)性度量，定義如下。項(xiàng)集A的出現(xiàn)獨(dú)立于項(xiàng)集B的出現(xiàn)，如果P(AB)=P(A)P(B);否則，作為事件，項(xiàng)集A和B是依賴(lài)的（dependent） 和相關(guān)的（correlated）。這個(gè)定義容易推廣到兩個(gè)以上的項(xiàng)集。A和B出現(xiàn)之間的提升度可以通過(guò)計(jì)算正式得到,讓我們回到例6.7的計(jì)算機(jī)游戲和錄像數(shù)據(jù) 例6.8 使用提升度的相關(guān)分析 為

4、了幫助過(guò)濾掉從例6.7的數(shù)據(jù)得到的形如A=B的誤導(dǎo)“強(qiáng)”關(guān)聯(lián)，需要研究?jī)蓚€(gè)項(xiàng)集A和B如何相關(guān)的。設(shè) 表示例6.7中不包含計(jì)算機(jī)游戲的事務(wù)， 表示不包含錄像的事務(wù)。這些事務(wù)可以匯總在一個(gè)相依表（contingency）中。,小結(jié),大量數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系的發(fā)現(xiàn)在選擇購(gòu)物、決策分析和商務(wù)管理方面是有用的。一個(gè)流行的應(yīng)用領(lǐng)域是購(gòu)物籃分析，通過(guò)搜索經(jīng)常一塊（或依次）購(gòu)物的商品的集合，研究顧客的購(gòu)物習(xí)慣。關(guān)聯(lián)規(guī)則首先找出頻繁項(xiàng)集（項(xiàng)的集合，如A和B，滿(mǎn)足最小支持度閾值，或相關(guān)任務(wù)的百分比），然后，由它們產(chǎn)生形如AB的強(qiáng)關(guān)聯(lián)規(guī)則。這些規(guī)則也滿(mǎn)足最小置信度閾值（預(yù)定義的在滿(mǎn)足A的條件下滿(mǎn)足B的概率）。,根據(jù)不

5、同的標(biāo)準(zhǔn)，關(guān)聯(lián)規(guī)則可以分成若干類(lèi)型，如：,根據(jù)規(guī)則所處理的值的類(lèi)型，關(guān)聯(lián)規(guī)則可以分為布爾的和量化的。布爾規(guī)則表現(xiàn)離散（分類(lèi)）對(duì)象之間的聯(lián)系。量化關(guān)聯(lián)規(guī)則是多維關(guān)聯(lián)規(guī)則，涉及動(dòng)態(tài)離散化的數(shù)值屬性。它可能涉及分類(lèi)屬性。 根據(jù)規(guī)則中數(shù)據(jù)涉及的維，關(guān)聯(lián)規(guī)則可以分為單維和多維的。單維關(guān)聯(lián)規(guī)則涉及單個(gè)謂詞或維，如buys；而多維關(guān)聯(lián)規(guī)則涉及多個(gè)（不同的）謂詞或維。單維關(guān)聯(lián)規(guī)則涉及的是屬性?xún)?nèi)聯(lián)系（即同一屬性或維內(nèi)的關(guān)聯(lián)）；多維關(guān)聯(lián)規(guī)則展示的是屬性間的聯(lián)系（即屬性/維之間的關(guān)聯(lián)）。 根據(jù)規(guī)則涉及的抽象層，關(guān)聯(lián)規(guī)則可以分為單層和多層。在單層關(guān)聯(lián)規(guī)則中，項(xiàng)或謂詞的挖掘不考慮不同的抽象層；而多層關(guān)聯(lián)規(guī)則考慮多個(gè)抽象

6、層。 根據(jù)對(duì)關(guān)聯(lián)挖掘的不同擴(kuò)充，關(guān)聯(lián)挖掘可以擴(kuò)充為相關(guān)分析和最大頻繁模式（“最大模式”）與頻繁閉項(xiàng)集挖掘。相關(guān)分析指出相關(guān)項(xiàng)的存在與否。,2020/7/8,Apriori算法,Apriori算法是一種有效的關(guān)聯(lián)規(guī)則挖掘算法，它探查逐級(jí)挖掘Aprior性質(zhì)：頻繁項(xiàng)的所有非空子集都必須是頻繁的。在第K次（k1），它根據(jù)頻繁k-項(xiàng)集，形成頻繁（k+1）-項(xiàng)集候選，并掃描數(shù)據(jù)庫(kù)一次，找出完整的頻繁（k+1）-項(xiàng)集L。 涉及散列和事務(wù)壓縮的變形可以用來(lái)使得過(guò)程更有效。其他變形涉及劃分?jǐn)?shù)據(jù)（在每一部分挖掘，然后合并結(jié)果）和數(shù)據(jù)選樣（在數(shù)據(jù)子集上挖掘）。這些變形可以將數(shù)據(jù)掃描次數(shù)減少到兩次或一次。,2020

7、/7/8,頻繁模式增長(zhǎng)（FP-增長(zhǎng)）,是一種不產(chǎn)生候選的挖掘頻繁項(xiàng)的集方法。它構(gòu)造一個(gè)高度壓縮的數(shù)據(jù)結(jié)構(gòu)（FP-樹(shù)），壓縮原來(lái)的數(shù)據(jù)庫(kù)。不使用類(lèi)Apriori方法的產(chǎn)生-測(cè)試策略，它聚焦于頻繁模式（段）增長(zhǎng)，避免了高代價(jià)的候選產(chǎn)生，獲得更好的效率。,2020/7/8,多層關(guān)聯(lián)規(guī)則,多層關(guān)聯(lián)規(guī)則可以根據(jù)每個(gè)抽象層上的最小支持閾值如何定義，使用多種策略挖掘。當(dāng)在多層使用遞減的支持度時(shí)，剪枝方法包括層交叉按單項(xiàng)過(guò)濾，層交叉按k-項(xiàng)集過(guò)濾。冗余的多層（后代）關(guān)聯(lián)規(guī)則可以刪除，不向用戶(hù)提供，如果根據(jù)其對(duì)應(yīng)得祖先規(guī)則，它們的支持度和置信度接近于期望的話(huà)。,2020/7/8,多層關(guān)聯(lián)規(guī)則,挖掘多維關(guān)聯(lián)規(guī)則可以根據(jù)對(duì)量化屬性處理分為若干類(lèi)。第一，量化屬性可以根據(jù)預(yù)定義的概念分層靜態(tài)離散化。數(shù)據(jù)立方體非常適合這種方法，因?yàn)閿?shù)據(jù)立方體和量化屬性都可以利用概念分層。第二，可以挖掘量化關(guān)聯(lián)規(guī)則，其量化屬性根據(jù)分箱動(dòng)態(tài)離散化，其中”臨近的“關(guān)聯(lián)規(guī)則可以用聚類(lèi)組合。第三，可以挖掘基于距離的關(guān)聯(lián)規(guī)則，其中區(qū)間根據(jù)聚類(lèi)的定義。,2020/7/8,并非所有的強(qiáng)關(guān)聯(lián)規(guī)則都是有趣的。對(duì)統(tǒng)計(jì)相關(guān)項(xiàng)，可以挖掘相關(guān)規(guī)則。 基于約束的挖掘允許用戶(hù)聚焦，按提供的元規(guī)則（即模式模板）和其它挖掘約束搜索規(guī)則。這種挖掘促進(jìn)了