第7章 關(guān)聯(lián)分析 高級概念

1、關(guān)聯(lián)分析關(guān)聯(lián)分析: 高級概念高級概念第第7章章關(guān)聯(lián)分析關(guān)聯(lián)分析: 高級概念高級概念關(guān)聯(lián)分析處理事務(wù)數(shù)據(jù)關(guān)聯(lián)分析處理事務(wù)數(shù)據(jù)Rules Discovered: Diaper - Beer處理分類屬性處理分類屬性我們可能發(fā)現(xiàn)關(guān)于因特網(wǎng)用戶特征的有趣信息我們可能發(fā)現(xiàn)關(guān)于因特網(wǎng)用戶特征的有趣信息: 網(wǎng)上購物=是 關(guān)注隱私=是許多應(yīng)用包含對稱二元屬性和標(biāo)稱屬性。表許多應(yīng)用包含對稱二元屬性和標(biāo)稱屬性。表7-1顯示的因特網(wǎng)調(diào)查顯示的因特網(wǎng)調(diào)查數(shù)據(jù)包含對稱二元屬性，如：性別、家庭計(jì)算機(jī)、網(wǎng)上聊天、網(wǎng)上數(shù)據(jù)包含對稱二元屬性，如：性別、家庭計(jì)算機(jī)、網(wǎng)上聊天、網(wǎng)上購物和關(guān)注隱私；還包括標(biāo)稱屬性，如文化程度和州。購物

2、和關(guān)注隱私；還包括標(biāo)稱屬性，如文化程度和州。處理分類屬性處理分類屬性l為了提取這樣的模式，我們需要將標(biāo)稱屬性和對稱二元屬性轉(zhuǎn)換成“項(xiàng)”，使得已有的關(guān)聯(lián)規(guī)則挖掘算法可以使用。l這種類型的變化可以通過為每個(gè)不同的屬性-值對創(chuàng)建一個(gè)新的項(xiàng)來實(shí)現(xiàn)。 例如: 標(biāo)稱屬性文化程度可以用三個(gè)二元項(xiàng)取代u 文化程度=大學(xué)u 文化程度=研究生u 文化程度=高中l(wèi)類似的，對稱二元屬性性別可以轉(zhuǎn)換成一對二元項(xiàng)：性別=男、性別=女。處理分類屬性處理分類屬性l將關(guān)聯(lián)分析用于二元化后的數(shù)據(jù)時(shí)，需要考慮如下問題。 (1)有些屬性值可能不夠頻繁，不能成為頻繁模式的一部分。如：州名。 解決辦法：將相關(guān)的屬性值分組，形成少數(shù)類別。

3、例如，每個(gè)州名都可以用對應(yīng)的地理區(qū)域取代。例如：分別用中西部、太平洋西北部、西南部和東海岸取代。處理分類屬性處理分類屬性l將關(guān)聯(lián)分析用于二元化后的數(shù)據(jù)時(shí)，需要考慮如下問題。 (2)某些屬性值的頻率可能比其他屬性高很多。如：假定85%的被調(diào)查人都有家庭計(jì)算機(jī)，如果為每個(gè)頻繁出現(xiàn)在數(shù)據(jù)中的屬性值創(chuàng)建一個(gè)二元項(xiàng)，我們可能產(chǎn)生許多冗余模式。 家庭計(jì)算機(jī)=是，網(wǎng)上購物=是 關(guān)注隱私=是 解決辦法：使用處理具有寬支持度的極差數(shù)據(jù)集的技術(shù)。處理分類屬性處理分類屬性l將關(guān)聯(lián)分析用于二元化后的數(shù)據(jù)時(shí)，需要考慮如下問題。 (3)計(jì)算時(shí)間可能增加，特別是當(dāng)新創(chuàng)建的項(xiàng)變成頻繁項(xiàng)時(shí)。因?yàn)闀?huì)產(chǎn)生更多的候選項(xiàng)集。 解決辦法

4、：避免產(chǎn)生包含多個(gè)來自同一個(gè)屬性的項(xiàng)的候選項(xiàng)集。例如：不必產(chǎn)生諸如州=X，州=Y，的候選項(xiàng)集，因?yàn)樵擁?xiàng)集支持度為零。處理連續(xù)屬性處理連續(xù)屬性l因特網(wǎng)調(diào)查數(shù)據(jù)可能還包含連續(xù)屬性，如表7-3所示。l挖掘連續(xù)屬性可能揭示數(shù)據(jù)的內(nèi)在聯(lián)系，如“年收入超過120k的用戶屬于45-60年齡組”或“擁有超過3個(gè)email帳號(hào)并且每周上網(wǎng)超過15小時(shí)的用戶通常關(guān)注個(gè)人隱私”:l包含連續(xù)屬性的關(guān)聯(lián)規(guī)則通常稱作量化關(guān)聯(lián)規(guī)則（quantiative association rule）。l對連續(xù)數(shù)據(jù)進(jìn)行關(guān)聯(lián)分析的方法: 基于離散化的方法 非離散化方法 基于統(tǒng)計(jì)學(xué)的方法基于離散化的方法基于離散化的方法l離散化是處理連續(xù)屬

5、性最常用的方法。這種方法將連續(xù)屬性的鄰近值分組，形成有限個(gè)區(qū)間。例如：年齡屬性可以劃分為如下區(qū)間： 12,16),16,20),20,24),56,60)l離散化技術(shù)：等寬、等頻、聚類l表7-4顯示了離散化和二元化后的因特網(wǎng)調(diào)查數(shù)據(jù)。l屬性離散化的一個(gè)關(guān)鍵在于劃分每個(gè)屬性的區(qū)間個(gè)數(shù)和寬度。然而，確定正確的區(qū)間是困難的。l如果支持度閾值=5%，置信度閾值=65%。我們可以從表中推出年齡和網(wǎng)上聊天隱含強(qiáng)規(guī)則： 16,24) 網(wǎng)上聊天=是（s=8.8%，c=81.5%） 44,60) 網(wǎng)上聊天=否（s=16.8%，c=70%）l區(qū)間寬度對關(guān)聯(lián)分析結(jié)果的影響。 （1）如果區(qū)間太寬，則可能因?yàn)槿狈χ眯哦?/p>

6、而失去某些規(guī)則 例如：當(dāng)區(qū)間寬度為24歲時(shí)，上面的兩個(gè)規(guī)則變?yōu)?16,36) 網(wǎng)上聊天=是（s=30%，57.7%） 36,60) 網(wǎng)上聊天=否（s=28%，58.3%）l區(qū)間寬度對關(guān)聯(lián)分析結(jié)果的影響。 （2）如果區(qū)間太窄，則可能因?yàn)槿狈χС侄榷ツ承┮?guī)則 例如：當(dāng)區(qū)間寬度為4歲時(shí)，上面的兩個(gè)規(guī)則變?yōu)?16,20) 網(wǎng)上聊天=是（s=4.4%，84.6%） 20,24) 網(wǎng)上聊天=是（s=4.4%，78.6%） （3）當(dāng)區(qū)間寬度為8歲時(shí)，上面的兩個(gè)規(guī)則變?yōu)?44,52) 網(wǎng)上聊天=否（s=8.4%，70%） 52,60) 網(wǎng)上聊天=否（s=8.4%，70%） 12,20) 網(wǎng)上聊天=是（s=

7、9.2%，60.5%） 20,28) 網(wǎng)上聊天=是（s=9.2%，60.0%）非離散化方法非離散化方法l有一些應(yīng)用，分析者更感興趣的是發(fā)現(xiàn)連續(xù)屬性之間的關(guān)系。例如，找出表7-6所示文本文檔中詞的關(guān)聯(lián)。l在文本挖掘中，分析者更感興趣的是發(fā)現(xiàn)詞之間的關(guān)聯(lián)（例如：數(shù)據(jù)和挖掘）。而不是詞頻區(qū)間（例如,數(shù)據(jù)：1,4，挖掘：2,3）之間的關(guān)聯(lián)。l一種方法是將數(shù)據(jù)變換成0/1矩陣；其中，如果規(guī)范化詞頻超過某個(gè)閾值t，則值為1，否則為0。l該方法缺點(diǎn)是閾值難確定。l另一種方法是采用min-apriori方法。 S(word1, word2)=min(0.3, 0.6)+min(0.1 , 0.2)+ min(

8、0.4,0.2)+min(0.2, 0) =0.6lMin-apriori中支持度s隨著詞的規(guī)范化頻率增加而增大。隨包含該詞的文檔個(gè)數(shù)增加而單調(diào)遞增。處理概念分層處理概念分層l概念分層是定義在一個(gè)特定的域中的各種實(shí)體或概念的多層組織。l概念分層可以用有向無環(huán)圖表示。l概念分層主要優(yōu)點(diǎn) （1）位于層次結(jié)構(gòu)較下層的項(xiàng)（如：AC適配器）可能沒有足夠的支持度，但是，作為概念分層結(jié)構(gòu)中它們的父母結(jié)點(diǎn)（如：便攜機(jī)配件）具有較高支持度。 （2）在較低層發(fā)現(xiàn)的規(guī)則傾向于過于特殊，可能不如較高層的規(guī)則令人感興趣。（如：脫脂牛奶普通面包，脫脂牛奶白面包，等過于特殊）l實(shí)現(xiàn)概念分層的方法 每個(gè)事務(wù)t用它的擴(kuò)展事務(wù)t

9、取代，其中，t包含t中所有項(xiàng)和它們的對應(yīng)祖先。如：事務(wù)DVD，普通面包可以擴(kuò)展為DVD，普通面包，家電，電子產(chǎn)品，面包，食品 然后對擴(kuò)展的數(shù)據(jù)庫使用如Apriori等已有的算法來發(fā)現(xiàn)跨越多個(gè)概念層的規(guī)則。l概念分層主要缺點(diǎn) （1）處于較高層的項(xiàng)比處于較低層的項(xiàng)趨向于具有較高的支持度計(jì)數(shù)。 （2）概念分層的引入增加了關(guān)聯(lián)分析的計(jì)算時(shí)間。 （3）概念分層的引入可能產(chǎn)生冗余規(guī)則。規(guī)則X Y是冗余的，如果存在一個(gè)更一般的規(guī)則X Y，其中X是X的祖先，Y是Y的祖先，并且兩個(gè)規(guī)則具有非常相似的置信度。例如：面包 牛奶，白面包 脫脂牛奶序列模式序列模式l購物籃數(shù)據(jù)常常包含關(guān)于商品何時(shí)被顧客購買的時(shí)間信息?？?/p>

10、以使用這種信息，將顧客在一段時(shí)間內(nèi)的購物拼接成事務(wù)序列。l然而，迄今為止所討論的關(guān)聯(lián)模式概念都只強(qiáng)調(diào)同時(shí)出現(xiàn)關(guān)系，而忽略數(shù)據(jù)中的序列信息。l對于識(shí)別動(dòng)態(tài)系統(tǒng)的重現(xiàn)特征，或預(yù)測特定事件的未來發(fā)生，序列信息可能是非常有價(jià)值的。序列模式序列模式l將與對象A有關(guān)的所有事件按時(shí)間增序排列，就得到A的一個(gè)序列（sequence）ObjectTimestampEventsA102, 3, 5A206, 1A231B114, 5, 6B172B217, 8, 1, 2B281, 6C141, 8, 7Sequence Database:l一般地，序列是元素（element）的有序列表，可以記作s=, 其中每個(gè)

11、ej是一個(gè)或多個(gè)事件的集族，即ej=i1，i2，ik。SequenceE1E2E1E3E2E3E4E2Element (Transaction)Event (Item)序列數(shù)據(jù)的例子序列數(shù)據(jù)的例子子序列（子序列（ Subsequence）l序列t是另一個(gè)序列s的子序列（subsequence），如果t中每個(gè)有序元素都是s中一個(gè)有序元素的子集。Data sequenceSubsequenceContain?Yes NoYes序列模式發(fā)現(xiàn)（序列模式發(fā)現(xiàn)（Sequential Pattern Mining）l設(shè)D是包含一個(gè)或多個(gè)數(shù)據(jù)序列的數(shù)據(jù)集: 序列s的支持度是包含s的所有數(shù)據(jù)序列所占的比例。如果

12、序列s的支持度大于或等于用戶指定的閾值minsup，則稱s是一個(gè)序列模式（或頻繁序列）。 l定義7.1 序列模式發(fā)現(xiàn): 給定序列數(shù)據(jù)庫D和用戶指定的最小支持度閾值minsup，序列模式發(fā)現(xiàn)的任務(wù)是找出支持度大于或等于minsup的所有序列 。例子例子Minsup = 50%Examples of Frequent Subsequences: s=60% s=60%s=80%s=80%s=80%s=60% s=60% s=60%s=60%ObjectTimestampEventsA11,2,4A22,3A35B11,2B22,3,4C11, 2C22,3,4C32,4,5D12D23, 4D34

13、, 5E11, 3E22, 4, 5提取序列模式：蠻力方法提取序列模式：蠻力方法l給定n個(gè)事件的集族: i1, i2, i3, , inl候選 1-序列: , , , , l候選 2-序列: , , , , , , , l候選 3-序列:, , , , , , , , , , l候選序列的個(gè)數(shù)比候選項(xiàng)集的個(gè)數(shù)大得多。產(chǎn)生更多候選的原因有下面兩個(gè) 一個(gè)項(xiàng)在項(xiàng)集中最多出現(xiàn)一次，但一個(gè)事件可以在序列中出現(xiàn)多次。給定兩個(gè)項(xiàng)i1和i2，只能產(chǎn)生一個(gè)候選2-項(xiàng)集i1，i2，但卻可以產(chǎn)生許多候選2-序列，如, , , 。 次序在序列中是重要的，但在項(xiàng)集中不重要。例如，1,2和2,1表示同一個(gè)項(xiàng)集，而和對應(yīng)于

14、不同的序列，因此必須分別產(chǎn)生。l先驗(yàn)原理對序列數(shù)據(jù)成立。 包含特定k-序列的任何數(shù)據(jù)序列必然包含該k-序列的所有(k-1)-序列 。序列模式發(fā)現(xiàn)的類序列模式發(fā)現(xiàn)的類Apriori算法算法候選產(chǎn)生候選產(chǎn)生l一對頻繁(k-1)-序列合并，產(chǎn)生候選k-序列。l為了避免重復(fù)產(chǎn)生候選，傳統(tǒng)的Apriori算法僅當(dāng)前k-1項(xiàng)相同時(shí)才合并一對頻繁k-項(xiàng)集。類似的方法可以用于序列。l例子 通過合并和得到 。由于事件3和事件4屬于第二個(gè)序列的不同元素，它們在合并后序列中也屬于不同的元素。 通過合并和得到 。由于事件3和事件4屬于第二個(gè)序列的相同元素，4被合并到第一個(gè)序列的最后一個(gè)元素中。l候選剪枝 一個(gè)候選k-

15、序列被剪枝，如果它的(k-1)-序列最少有一個(gè)是非頻繁的。 例如，假設(shè)是一個(gè)候選4-序列。我們需要檢查和是否是頻繁3-序列。由于它們都不是頻繁的，因此可以刪除候選。l支持度計(jì)數(shù) 在支持度計(jì)數(shù)期間，算法將枚舉屬于一個(gè)特定數(shù)據(jù)序列的所有候選k-序列。 計(jì)數(shù)之后，算法將識(shí)別出頻繁k-序列，并可以丟棄其支持度計(jì)數(shù)小于最小支持度閾值minsup的候選。圖圖7-6時(shí)限約束時(shí)限約束l模式的事件和元素都施加時(shí)限約束。l例子：學(xué)生A： 學(xué)生B：l感興趣的模式是，意思是說注冊數(shù)據(jù)挖掘課程的學(xué)生必須先選修數(shù)據(jù)庫系統(tǒng)和統(tǒng)計(jì)學(xué)方面的課程。l顯然，該模式被這兩個(gè)學(xué)生支持，盡管他們都沒有同時(shí)選修統(tǒng)計(jì)學(xué)和數(shù)據(jù)庫系統(tǒng)。l相比之

16、下，一個(gè)10年之前選修了統(tǒng)計(jì)學(xué)課程的學(xué)生不能認(rèn)為支持該模式，因?yàn)檫@些課程的時(shí)間間隔太長了。l圖7-7解釋了可以施加在模式上的某些時(shí)限約束。最大跨度約束最大跨度約束l最大跨度約束指定整個(gè)序列中所允許的事件的最晚和最早發(fā)生時(shí)間的最大時(shí)間差。l假定最大時(shí)間跨度maxspan=3，下面的表包含了給定的數(shù)據(jù)序列支持和不支持的序列模式。數(shù)據(jù)序列數(shù)據(jù)序列s序列模式序列模式tS支持支持t?是是 否l一般，maxspan越長，在數(shù)據(jù)序列中 檢測到模式的可能性就越大。然而，較長的maxspan也可能捕獲不真實(shí)的模式可能涉及陳舊事件。l最大跨度約束影響序列模式發(fā)現(xiàn)算法的支持度計(jì)數(shù)。施加最大時(shí)間跨度約束之后，有些數(shù)據(jù)

17、序列就不再支持候選模式。最小間隔和最大間隔約束最小間隔和最大間隔約束l時(shí)限約束也可以通過限制序列中兩個(gè)相繼元素之間的時(shí)間差來指定。l如果最大時(shí)間差（maxgap）是一周，則元素中的事件必須在前一個(gè)元素的事件出現(xiàn)后的一周之內(nèi)出現(xiàn)。l如果最小時(shí)間差（mingap）是0，則元素中的事件必須在前一個(gè)元素的事件出現(xiàn)之后出現(xiàn)。l假定maxgap=3，mingap=1，下表給出了模式通過或未通過最大間隔和最小間隔約束的例子。數(shù)據(jù)序列數(shù)據(jù)序列s序列模式序列模式tmaxgapmingap通過通過通過未通過未通過通過 未通過未通過l與最大跨度一樣，這些約束也影響序列模式發(fā)現(xiàn)算法的支持度計(jì)數(shù)，因?yàn)楫?dāng)最小間隔和最大間

18、隔約束存在時(shí)，有些數(shù)據(jù)序列就不再支持候選模式。l使用最大間隔約束可能違反先驗(yàn)原理。l為了解釋這一點(diǎn)，考慮圖7-5中的數(shù)據(jù)集。如果沒有最小間隔或最大間隔約束，和的支持度都是60%。然而，如果mingap=0，maxgap=1，則的支持度下降至40%，而的支持度仍然是60%。這與先驗(yàn)原理相違背。例子例子Minsup = 50%Examples of Frequent Subsequences: s=60% s=60%s=80%s=80%s=80%s=60% s=60% s=60%s=60%ObjectTimestampEventsA11,2,4A22,3A35B11,2B22,3,4C11, 2C

19、22,3,4C32,4,5D12D23, 4D34, 5E11, 3E22, 4, 5l定義7.2 鄰接子序列 序列s是序列w=的鄰接子序列(contiguous subsequence)，如果下列條件之一成立： （1）s是從e1或ek中刪除一個(gè)事件后由w得到。 （2）s是從至少包含兩個(gè)事件的任意eiw中刪除一個(gè) 事件后由w得到。 （3）s是t的鄰接子序列，而t是w的鄰接子序列。數(shù)據(jù)序列數(shù)據(jù)序列s序列模式序列模式tt是是s的鄰接子序列的鄰接子序列是是是否 否l定義7.3 修訂的先驗(yàn)原理 如果一個(gè)k-序列是頻繁的，則它的所有鄰接(k-1)-子序列也一定是頻繁的。l在候選剪枝階段，并非所有的k-序

20、列都需要檢查，因?yàn)樗鼈冎械囊恍┛赡苓`反最大間隔約束。例如，如果maxgap=1，則不必檢查候選的子序列是否是頻繁的，因?yàn)樵?,3和5之間的時(shí)間差大于一個(gè)時(shí)間單位。l我們只需要考察的鄰接子序列，包括，和。窗口大小約束窗口大小約束l最后，元素sj中的事件不必同時(shí)出現(xiàn)?？梢远x一個(gè)窗口大小閾值（ws）來指定序列模式的任意元素中事件最晚和最早出現(xiàn)之間的最大允許時(shí)間差。窗口大小為0表明模式同一元素中的所有事件必須同時(shí)出現(xiàn)。l下面的例子使用ws=2，mingap=0，maxgap=3，maxspan=數(shù)據(jù)序列數(shù)據(jù)序列s序列模式序列模式tS支持支持t？是是否 否子圖模式子圖模式l關(guān)聯(lián)分析方法應(yīng)用到遠(yuǎn)比項(xiàng)集

21、和序列更復(fù)雜實(shí)體。例子包括化學(xué)化合物、3-D蛋白質(zhì)結(jié)構(gòu)、網(wǎng)絡(luò)拓?fù)浜蜆浣Y(jié)構(gòu)的XML文檔。這些實(shí)體可以用圖形表示建模。l在這種類型的數(shù)據(jù)上進(jìn)行數(shù)據(jù)挖掘的任務(wù)是，在圖的集合中發(fā)現(xiàn)一組公共子結(jié)構(gòu)。這樣的任務(wù)稱作頻繁子圖挖掘DatabasesHomepageResearchArtificialIntelligenceData Mining圖與子圖圖與子圖l定義7.5 支持度 給定一個(gè)圖的集族,子圖g的支持度定義為包含它的所有圖所占的百分比，即l例7.2 考慮5個(gè)圖G1到G5，如圖7-10所示。右上角的圖g1是G1，G3，G4，G5的子圖，因此s(g1)=4/5=80%。類似地，我們由s(g2)=60%，

22、因?yàn)間2是G1、G2和G3的子圖；而s(g3)=40%，因?yàn)間3是G1和G3的子圖。| ,| |)(iiiGsGgGgs頻繁子圖挖掘頻繁子圖挖掘l定義7.6 頻繁子圖挖掘 給定圖的集合和支持度閾值minsup，頻繁子圖挖掘的目標(biāo)是找出所有使得s(g)=minsup的子圖g。l本章的討論主要關(guān)注無向連通圖（undirected，connected graph）。l挖掘頻繁子圖是一項(xiàng)計(jì)算量很大的任務(wù)，因?yàn)樗阉骺臻g是指數(shù)的。為了解釋這項(xiàng)任務(wù)的復(fù)雜性，考慮一個(gè)包含d個(gè)實(shí)體的數(shù)據(jù)集。在頻繁項(xiàng)集挖掘中，每個(gè)實(shí)體是一個(gè)項(xiàng)，待考察的搜索空間是2d，這是可能產(chǎn)生的候選項(xiàng)集的個(gè)數(shù)。l在頻繁子圖挖掘中，每個(gè)實(shí)體是一

23、個(gè)頂點(diǎn)，并且最多可以有d-1條到其他頂點(diǎn)的邊。假定頂點(diǎn)的標(biāo)號(hào)是唯一的，則子圖的總數(shù)是 其中， 是選擇i個(gè)頂點(diǎn)形成子圖的方法數(shù)，而 是子圖的頂點(diǎn)之間邊的最大值。表7-8對不同的d比較了項(xiàng)集和子圖的個(gè)數(shù)。diiiidC12/ )1(2idC2/ )1(2iil挖掘頻繁子圖的一種蠻力方法是，產(chǎn)生所有的連通子圖作為候選，并計(jì)算它們各自的支持度。l考慮圖7-11a中顯示的圖，假定頂點(diǎn)標(biāo)號(hào)選自集合a，b，而邊的標(biāo)號(hào)選自集合p，q，則具有一個(gè)到三個(gè)頂點(diǎn)的連通子圖列在圖7-11b中。l候選子圖的個(gè)數(shù)比傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘中的候選項(xiàng)集的個(gè)數(shù)大得多，其原因： 一個(gè)項(xiàng)在一個(gè)項(xiàng)集中至多出現(xiàn)一次，而一個(gè)頂點(diǎn)標(biāo)號(hào)可能在一個(gè)

24、圖中出現(xiàn)多次。 相同的頂點(diǎn)標(biāo)號(hào)對可以有多種邊標(biāo)號(hào)選擇。把事務(wù)轉(zhuǎn)化為圖把事務(wù)轉(zhuǎn)化為圖Transaction IdItems1A,B,C,D2A,B,E3B,C4A,B,D,E5B,C,DABCDETID = 1:把圖轉(zhuǎn)化為事務(wù)把圖轉(zhuǎn)化為事務(wù)頻繁子圖挖掘算法的一般結(jié)構(gòu)頻繁子圖挖掘算法的一般結(jié)構(gòu)l一種挖掘頻繁子圖的類Apriori算法由以下步驟組成 候選產(chǎn)生：合并頻繁(k-1)-子圖對，得到候選k-子圖。 候選剪枝：丟棄包含非頻繁的(k-1)-子圖的所有候選k-子圖。 支持度計(jì)數(shù)：統(tǒng)計(jì)中包含每個(gè)候選的圖的個(gè)數(shù)。 候選刪除：丟棄支持度小于minsup的所有候選子圖。候選產(chǎn)生候選產(chǎn)生l在候選產(chǎn)生階段，一

25、對頻繁(k-1)-子圖合并成一個(gè)候選k-子圖。l如何定義子圖的大小k？l在圖7-11顯示的例子中，k是圖中的頂點(diǎn)個(gè)數(shù)。通過添加一個(gè)頂點(diǎn)，迭代的擴(kuò)展子圖的方法稱作頂點(diǎn)增長（vertex growing）。lK也可以是圖中邊的個(gè)數(shù)。添加一條邊到已有的子圖中來擴(kuò)展子圖的方法稱作邊增長（edge growing）。l為了避免產(chǎn)生重復(fù)的候選，可以對合并施加附加的條件：兩個(gè)(k-1)-子圖必須共享一個(gè)共同的(k-2)-子圖。共同的(k-2)-子圖稱作核(core)。通過頂點(diǎn)增長產(chǎn)生候選通過頂點(diǎn)增長產(chǎn)生候選l用鄰接矩陣表示圖。l頂點(diǎn)增長方法可以看成合并一對(k-1) (k-1)的鄰接矩陣，產(chǎn)生kk鄰接矩陣的

26、過程。l通過頂點(diǎn)增長合并子圖的過程： 鄰接矩陣M1與另一個(gè)鄰接矩陣M2合并，如果刪除M1和M2的最后一行和最后一列得到的子矩陣相同。 結(jié)果矩陣是M1，添加上M2的最后一行和最后一列。 新矩陣的其余項(xiàng)或者為0，或者用連接頂點(diǎn)對的合法的邊標(biāo)號(hào)替換。Vertex Growingararl結(jié)果圖包含的邊比原來的圖多一條或兩條。l(d,e)可以相連或不相連。l由于該邊的標(biāo)號(hào)未知，我們需要對(d,e)考慮所有可能的邊標(biāo)號(hào)，從而大大增加了候選子圖的個(gè)數(shù)。通過邊增長產(chǎn)生候選通過邊增長產(chǎn)生候選l在候選產(chǎn)生期間，邊增長將一個(gè)新的邊插入一個(gè)已經(jīng)存在的頻繁子圖中。l與頂點(diǎn)增長不同，結(jié)果子圖的頂點(diǎn)個(gè)數(shù)不一定增加。l通過

27、邊增長產(chǎn)生候選子圖的過程概括如下： 一個(gè)頻繁子圖g1與另一個(gè)頻繁子圖g2合并，僅當(dāng)從g1刪除一條邊得到的子圖與從g2刪除一條邊得到的子圖拓?fù)涞葍r(jià)。合并后，結(jié)果子圖是g1，添加g2的那條額外的邊。al頂點(diǎn)拓?fù)涞葍r(jià)（topologically equivalent）：加入一條新邊到v1與加入該邊到v2產(chǎn)生的圖相同，則v1和v2兩頂點(diǎn)拓?fù)涞葍r(jià)。l頂點(diǎn)拓?fù)涞葍r(jià)的概念能夠幫助我們理解，在邊增長時(shí)為什么能夠產(chǎn)生多個(gè)候選子圖。l如果a和c拓?fù)涞葍r(jià)，我們將它們記作a=c。對于核外邊的點(diǎn)，如果它們的標(biāo)號(hào)相同，我們將它們記作b=d。l當(dāng)與一對(k-1)-子圖相關(guān)聯(lián)的核有多個(gè)時(shí)，還可能產(chǎn)生多個(gè)候選子圖。候選剪枝候選

28、剪枝l產(chǎn)生候選k-子圖后，需要剪去(k-1)-子圖非頻繁的候選。l候選剪枝可以通過如下步驟實(shí)現(xiàn)： 相繼從k-子圖刪除一條邊，并檢查對應(yīng)的(k-1)-子圖是否連通且頻繁。 如果不是，則該候選k-子圖可以丟棄。l為了檢查(k-1)-子圖是否頻繁，需要將它與其他頻繁(k-1)-子圖匹配。判定兩個(gè)圖是否拓?fù)涞葍r(jià)稱為圖同構(gòu)（graph isomorphism）問題。l為了解釋圖同構(gòu)問題的困難性，考慮圖7-19中的兩個(gè)圖。同構(gòu)圖同構(gòu)圖處理圖同構(gòu)處理圖同構(gòu)l處理圖同構(gòu)問題的標(biāo)準(zhǔn)方法是，將每一個(gè)圖都映射到一個(gè)唯一的串表達(dá)式，稱作代碼（code）或規(guī)范標(biāo)號(hào)（canonical label）。l規(guī)范標(biāo)號(hào)具有如下性

29、質(zhì)：如果兩個(gè)圖是同構(gòu)的，則它們的代號(hào)一定相同。這個(gè)性質(zhì)使得我們可以通過比較圖的規(guī)范標(biāo)號(hào)來檢查圖同構(gòu)。l構(gòu)造圖的規(guī)范標(biāo)號(hào)的第一步是找出圖的鄰接矩陣表示。一個(gè)圖可以有多種鄰接矩陣表示，因?yàn)榇嬖诙喾N確定頂點(diǎn)次序的方法。l數(shù)學(xué)上講，每個(gè)排列都對應(yīng)于初始鄰接矩陣與一個(gè)對應(yīng)的排列矩陣的乘積，如下面的例子所示。l例子：考慮下面的矩陣：l其中，P13是通過交換單位矩陣的第一行和第三行得到的。為了交換M的第一和第三行（和列），排列矩陣與M相乘16151413121110987654321M100000010010010013PlM右乘P13交換M的第一列和第三列，而M左乘P13交換M的第一行和第三行。l第二步是

30、確定每個(gè)鄰接矩陣的串表示。由于鄰接矩陣是對稱的，因此只需要根據(jù)矩陣的上三角部分構(gòu)造串表示就足夠了。l在圖7-21所示的例子中，代碼是通過逐列連接矩陣的上三角元素得到的。l最后一步是比較圖的所有串表達(dá)式，并選出具有最小（最大）字典次序值的串。支持度計(jì)數(shù)支持度計(jì)數(shù)l支持度計(jì)數(shù)一般是開銷很大的操作，因?yàn)閷τ诿總€(gè)G，必須確定包含在G中的所有候選子圖。l加快該操作的一種方法是，維護(hù)一個(gè)與每個(gè)頻繁(k-1)-子圖相關(guān)聯(lián)的圖ID表。一旦一個(gè)新的候選k-子圖通過合并一對頻繁(k-1)-子圖而產(chǎn)生，就對它們的對應(yīng)圖ID表求交集。最后，子圖同構(gòu)檢查就在表中的圖上進(jìn)行，確定它們是否包含特定的子圖。非頻繁模式非頻繁模

31、式l迄今為止，關(guān)聯(lián)分析都基于這樣的前提：項(xiàng)在事務(wù)中出現(xiàn)比不出現(xiàn)更重要。l因此，數(shù)據(jù)庫中很少出現(xiàn)的模式不是令人感興趣的，并使用支持度度量將其刪除。這種模式稱為非頻繁模式。l定義7.7 非頻繁模式 非頻繁模式是一個(gè)項(xiàng)集或規(guī)則，其支持度小于閾值minsup。l盡管絕大部分非頻繁模式都是讓人不感興趣的，但是其中的一些可能對于分析是有用的，特別是涉及到數(shù)據(jù)中的負(fù)相關(guān)性。l例如：DVD和VCR一起銷售的情況很少，因?yàn)橘徺IDVD的人多半不會(huì)購買VCR，反之亦然。l這種負(fù)相關(guān)模式有助于識(shí)別競爭項(xiàng)（competing item）。l競爭項(xiàng)的例子包括茶與咖啡、黃油與人造黃油、普通與節(jié)食蘇打、臺(tái)式機(jī)與便攜式計(jì)算機(jī)。

32、l某些非頻繁模式也可能暗示數(shù)據(jù)中出現(xiàn)了某些有趣的罕見事件或例外情況。l例如：如果火災(zāi)=yes是頻繁的，但火災(zāi)=yes，報(bào)警=on是非頻繁的。而后者是一個(gè)有趣的非頻繁模式，因?yàn)樗赡苤赋鼍瘓?bào)系統(tǒng)的故障。l為了檢測這種不尋常情況，必須確定模式的期望支持度，使得如果一個(gè)模式的支持度明顯低于期望支持度，則可以聲明它是一個(gè)有趣的非頻繁模式。負(fù)模式負(fù)模式l設(shè)I=i1,i2,id是項(xiàng)的集合。負(fù)項(xiàng)ik表示項(xiàng)ik不在給定的事務(wù)中出現(xiàn)。例如，如果事務(wù)中不包含咖啡，則咖啡是一個(gè)值為1的負(fù)項(xiàng)。l定義 7.8 負(fù)項(xiàng)集 負(fù)項(xiàng)集X是一個(gè)具有如下性質(zhì)的項(xiàng)集：（1）X=AB，其中A是正項(xiàng)的集合，而B是負(fù)項(xiàng)的集合，|B|1; （

33、2）s(X) minsup。l定義 7.9 負(fù)關(guān)聯(lián)規(guī)則 負(fù)關(guān)聯(lián)規(guī)則是一個(gè)具有如下性質(zhì)的關(guān)聯(lián)規(guī)則：（1）規(guī)則是從一個(gè)負(fù)項(xiàng)集提取的，（2）規(guī)則的支持度大于或等于minsup，（3）規(guī)則的置信度大于或等于minconfl本章中，負(fù)項(xiàng)集和負(fù)關(guān)聯(lián)規(guī)則統(tǒng)稱負(fù)模式負(fù)相關(guān)模式負(fù)相關(guān)模式l定義7.10 負(fù)相關(guān)項(xiàng)集 項(xiàng)集X=x1,x2,xk是負(fù)相關(guān)的，如果l定義7.11 負(fù)相關(guān)關(guān)聯(lián)規(guī)則 關(guān)聯(lián)規(guī)則X Y是負(fù)相關(guān)的，如果s(XY)s(X)s(Y)，其中，X和Y是不相交的項(xiàng)集，即X Y=。 負(fù)相關(guān)的完全條件可以表述如下：)(.)()()()(211kkjjxsxsxsxsXsjjiiysxsYXs)()()(l負(fù)相關(guān)條

34、件也可以用正項(xiàng)集和負(fù)項(xiàng)集的支持度表示。設(shè) 和 分別表示X和Y的對應(yīng)負(fù)項(xiàng)集，由于 l負(fù)相關(guān)條件可以表述如下：l負(fù)相關(guān)項(xiàng)集和負(fù)相關(guān)關(guān)聯(lián)規(guī)則統(tǒng)稱負(fù)相關(guān)模式（negatively correlated pattern） Y()() ( )() ()() ()()()1()()() - () ()() ()() ()s XYs X s Ys XYs XYs XYs XYs XYs XYs XYs XYs XYs XY s XYs XY s XYs XY s XYX)()()()(YXsYXsYXsYXs非頻繁模式、負(fù)模式和負(fù)相關(guān)模式比較非頻繁模式、負(fù)模式和負(fù)相關(guān)模式比較l非頻繁模式、負(fù)模式和負(fù)相關(guān)模式是

35、三個(gè)密切相關(guān)的概念。l盡管非頻繁模式和負(fù)相關(guān)模式只涉及包含正項(xiàng)的項(xiàng)集或模式，而負(fù)模式涉及包含正項(xiàng)和負(fù)項(xiàng)的項(xiàng)集或模式，但是這三個(gè)概念之間存在一定的共性，如圖7-22所示l首先，許多非頻繁模式有對應(yīng)的負(fù)模式。l如果x y是非頻繁的，則除非minsup太高，否則它很可能有對應(yīng)的負(fù)項(xiàng)集。l例如：假定minsup0.25，如果x y是非頻繁的，則表中的其它幾種組合至少有一種是頻繁的。yyxS(xy)S(xy)S(x)xS(xy)S(xy)S(x)S(y)S(y)1挖掘有趣的非頻繁模式的技術(shù)挖掘有趣的非頻繁模式的技術(shù)l原則上講，非頻繁項(xiàng)集是未被標(biāo)準(zhǔn)的頻繁項(xiàng)集產(chǎn)生算法（如Apriori和FP增長）提取的所有

36、項(xiàng)集。這些項(xiàng)集對應(yīng)于圖7-23所示的頻繁項(xiàng)集邊界之下的那些項(xiàng)集。l由于非頻繁模式的數(shù)量可能是指數(shù)級的，特別是對于稀疏的、高維的數(shù)據(jù)。l因此，為挖掘非頻繁模式而開發(fā)的技術(shù)著力于發(fā)現(xiàn)有趣的非頻繁模式。l例如：負(fù)相關(guān)模式基于挖掘負(fù)模式的技術(shù)基于挖掘負(fù)模式的技術(shù)l一種方法是將每個(gè)項(xiàng)看作對稱的二元變量。通過用負(fù)項(xiàng)增廣，將事務(wù)數(shù)據(jù)二元化。然后使用Apriori算法等，可以導(dǎo)出所有的負(fù)項(xiàng)集。l僅當(dāng)只有少量變量被視為對稱的二元變量時(shí)，該方法才是可行的。如果每個(gè)項(xiàng)都必須視為對稱的二元變量，則可能導(dǎo)致計(jì)算復(fù)雜度增加。 (1)當(dāng)每個(gè)項(xiàng)都用對應(yīng)的負(fù)項(xiàng)增廣時(shí)，項(xiàng)的個(gè)數(shù)就加倍。待探測的項(xiàng)集格比2d大得多。 (2)當(dāng)增加進(jìn)負(fù)項(xiàng)后，基于支持度的剪枝不再有效。對于每個(gè)變量x，x或 的支持度大于等于50%.因此，即使支持度閾值達(dá)到50%，仍有一半的項(xiàng)是頻繁的。 (3)當(dāng)增加進(jìn)負(fù)項(xiàng)后，每個(gè)事務(wù)的寬度增加。當(dāng)包含負(fù)項(xiàng)后，事務(wù)的寬度增加到d。xl另一種方法不是用負(fù)項(xiàng)增廣數(shù)據(jù)，而是根據(jù)對應(yīng)的正項(xiàng)集計(jì)算負(fù)項(xiàng)集的支持度。例如， 的支持度可以用如下方法計(jì)算：l ,rqp),(),(),()(),(rqpsrpsqpspsrqpsniiZYZiZXs