數(shù)據(jù)挖掘?qū)д?ch7

關(guān)聯(lián)分析:高級(jí)概念第7章關(guān)聯(lián)分析:高級(jí)概念關(guān)聯(lián)分析處理事務(wù)數(shù)據(jù)RulesDiscovered:

{Diaper}-->{Beer}處理分類(lèi)屬性我們可能發(fā)現(xiàn)關(guān)于因特網(wǎng)用戶(hù)特征的有趣信息:{網(wǎng)上購(gòu)物=是}{關(guān)注隱私=是}許多應(yīng)用包含對(duì)稱(chēng)二元屬性和標(biāo)稱(chēng)屬性。表7-1顯示的因特網(wǎng)調(diào)查數(shù)據(jù)包含對(duì)稱(chēng)二元屬性，如：性別、家庭計(jì)算機(jī)、網(wǎng)上聊天、網(wǎng)上購(gòu)物和關(guān)注隱私；還包括標(biāo)稱(chēng)屬性，如文化程度和州。處理分類(lèi)屬性為了提取這樣的模式，我們需要將標(biāo)稱(chēng)屬性和對(duì)稱(chēng)二元屬性轉(zhuǎn)換成“項(xiàng)”，使得已有的關(guān)聯(lián)規(guī)則挖掘算法可以使用。這種類(lèi)型的變化可以通過(guò)為每個(gè)不同的屬性-值對(duì)創(chuàng)建一個(gè)新的項(xiàng)來(lái)實(shí)現(xiàn)。例如:標(biāo)稱(chēng)屬性文化程度可以用三個(gè)二元項(xiàng)取代

文化程度=大學(xué)

文化程度=研究生

文化程度=高中類(lèi)似的，對(duì)稱(chēng)二元屬性性別可以轉(zhuǎn)換成一對(duì)二元項(xiàng)：性別=男、性別=女。處理分類(lèi)屬性將關(guān)聯(lián)分析用于二元化后的數(shù)據(jù)時(shí)，需要考慮如下問(wèn)題。(1)有些屬性值可能不夠頻繁，不能成為頻繁模式的一部分。如：州名。解決辦法：將相關(guān)的屬性值分組，形成少數(shù)類(lèi)別。例如，每個(gè)州名都可以用對(duì)應(yīng)的地理區(qū)域取代。例如：分別用中西部、太平洋西北部、西南部和東海岸取代。處理分類(lèi)屬性將關(guān)聯(lián)分析用于二元化后的數(shù)據(jù)時(shí)，需要考慮如下問(wèn)題。(2)某些屬性值的頻率可能比其他屬性高很多。如：假定85%的被調(diào)查人都有家庭計(jì)算機(jī)，如果為每個(gè)頻繁出現(xiàn)在數(shù)據(jù)中的屬性值創(chuàng)建一個(gè)二元項(xiàng)，我們可能產(chǎn)生許多冗余模式。{家庭計(jì)算機(jī)=是，網(wǎng)上購(gòu)物=是}{關(guān)注隱私=是}解決辦法：使用處理具有寬支持度的極差數(shù)據(jù)集的技術(shù)。處理分類(lèi)屬性將關(guān)聯(lián)分析用于二元化后的數(shù)據(jù)時(shí)，需要考慮如下問(wèn)題。(3)計(jì)算時(shí)間可能增加，特別是當(dāng)新創(chuàng)建的項(xiàng)變成頻繁項(xiàng)時(shí)。因?yàn)闀?huì)產(chǎn)生更多的候選項(xiàng)集。解決辦法：避免產(chǎn)生包含多個(gè)來(lái)自同一個(gè)屬性的項(xiàng)的候選項(xiàng)集。例如：不必產(chǎn)生諸如{州=X，州=Y，…}的候選項(xiàng)集，因?yàn)樵擁?xiàng)集支持度為零。處理連續(xù)屬性因特網(wǎng)調(diào)查數(shù)據(jù)可能還包含連續(xù)屬性，如表7-3所示。挖掘連續(xù)屬性可能揭示數(shù)據(jù)的內(nèi)在聯(lián)系，如“年收入超過(guò)120k的用戶(hù)屬于45-60年齡組”或“擁有超過(guò)3個(gè)email帳號(hào)并且每周上網(wǎng)超過(guò)15小時(shí)的用戶(hù)通常關(guān)注個(gè)人隱私”:包含連續(xù)屬性的關(guān)聯(lián)規(guī)則通常稱(chēng)作量化關(guān)聯(lián)規(guī)則（quantiativeassociationrule）。對(duì)連續(xù)數(shù)據(jù)進(jìn)行關(guān)聯(lián)分析的方法:基于離散化的方法非離散化方法基于統(tǒng)計(jì)學(xué)的方法基于離散化的方法離散化是處理連續(xù)屬性最常用的方法。這種方法將連續(xù)屬性的鄰近值分組，形成有限個(gè)區(qū)間。例如：年齡屬性可以劃分為如下區(qū)間：

[12,16),[16,20),[20,24),…,[56,60)離散化技術(shù)：等寬、等頻、聚類(lèi)表7-4顯示了離散化和二元化后的因特網(wǎng)調(diào)查數(shù)據(jù)。屬性離散化的一個(gè)關(guān)鍵在于劃分每個(gè)屬性的區(qū)間個(gè)數(shù)和寬度。然而，確定正確的區(qū)間是困難的。如果支持度閾值=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%）區(qū)間寬度對(duì)關(guān)聯(lián)分析結(jié)果的影響。（1）如果區(qū)間太寬，則可能因?yàn)槿狈χ眯哦榷ツ承┮?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%）區(qū)間寬度對(duì)關(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=9.2%，60.5%）

[20,28)網(wǎng)上聊天=是（s=9.2%，60.0%）非離散化方法有一些應(yīng)用，分析者更感興趣的是發(fā)現(xiàn)連續(xù)屬性之間的關(guān)系。例如，找出表7-6所示文本文檔中詞的關(guān)聯(lián)。在文本挖掘中，分析者更感興趣的是發(fā)現(xiàn)詞之間的關(guān)聯(lián)（例如：數(shù)據(jù)和挖掘）。而不是詞頻區(qū)間（例如,數(shù)據(jù)：[1,4]，挖掘：[2,3]）之間的關(guān)聯(lián)。一種方法是將數(shù)據(jù)變換成0/1矩陣；其中，如果規(guī)范化詞頻超過(guò)某個(gè)閾值t，則值為1，否則為0。該方法缺點(diǎn)是閾值難確定。另一種方法是采用min-apriori方法。S({word1,word2})=min(0.3,0.6)+min(0.1,0.2)+min(0.4,0.2)+min(0.2,0)=0.6Min-apriori中支持度s隨著詞的規(guī)范化頻率增加而增大。隨包含該詞的文檔個(gè)數(shù)增加而單調(diào)遞增。處理概念分層概念分層是定義在一個(gè)特定的域中的各種實(shí)體或概念的多層組織。概念分層可以用有向無(wú)環(huán)圖表示。概念分層主要優(yōu)點(diǎn)（1）位于層次結(jié)構(gòu)較下層的項(xiàng)（如：AC適配器）可能沒(méi)有足夠的支持度，但是，作為概念分層結(jié)構(gòu)中它們的父母結(jié)點(diǎn)（如：便攜機(jī)配件）具有較高支持度。（2）在較低層發(fā)現(xiàn)的規(guī)則傾向于過(guò)于特殊，可能不如較高層的規(guī)則令人感興趣。（如：脫脂牛奶普通面包，脫脂牛奶白面包，等過(guò)于特殊）實(shí)現(xiàn)概念分層的方法每個(gè)事務(wù)t用它的擴(kuò)展事務(wù)t’取代，其中，t’包含t中所有項(xiàng)和它們的對(duì)應(yīng)祖先。如：事務(wù){(diào)DVD，普通面包}可以擴(kuò)展為{DVD，普通面包，家電，電子產(chǎn)品，面包，食品}然后對(duì)擴(kuò)展的數(shù)據(jù)庫(kù)使用如Apriori等已有的算法來(lái)發(fā)現(xiàn)跨越多個(gè)概念層的規(guī)則。概念分層主要缺點(diǎn)（1）處于較高層的項(xiàng)比處于較低層的項(xiàng)趨向于具有較高的支持度計(jì)數(shù)。（2）概念分層的引入增加了關(guān)聯(lián)分析的計(jì)算時(shí)間。（3）概念分層的引入可能產(chǎn)生冗余規(guī)則。規(guī)則XY是冗余的，如果存在一個(gè)更一般的規(guī)則X’Y’，其中X‘是X的祖先，Y’是Y的祖先，并且兩個(gè)規(guī)則具有非常相似的置信度。例如：{面包}{牛奶}，{白面包}{脫脂牛奶}序列模式購(gòu)物籃數(shù)據(jù)常常包含關(guān)于商品何時(shí)被顧客購(gòu)買(mǎi)的時(shí)間信息?？梢允褂眠@種信息，將顧客在一段時(shí)間內(nèi)的購(gòu)物拼接成事務(wù)序列。然而，迄今為止所討論的關(guān)聯(lián)模式概念都只強(qiáng)調(diào)同時(shí)出現(xiàn)關(guān)系，而忽略數(shù)據(jù)中的序列信息。對(duì)于識(shí)別動(dòng)態(tài)系統(tǒng)的重現(xiàn)特征，或預(yù)測(cè)特定事件的未來(lái)發(fā)生，序列信息可能是非常有價(jià)值的。序列模式將與對(duì)象A有關(guān)的所有事件按時(shí)間增序排列，就得到A的一個(gè)序列（sequence）ObjectTimestampEventsA102,3,5A206,1A231B114,5,6B172B217,8,1,2B281,6C141,8,7SequenceDatabase:一般地，序列是元素（element）的有序列表，可以記作s=<e1e2e3,…,en>,其中每個(gè)ej是一個(gè)或多個(gè)事件的集族，即ej={i1，i2，…，ik}。SequenceE1

E2E1

E3E2E3

E4E2Element(Transaction)Event

(Item)序列數(shù)據(jù)的例子子序列（

Subsequence）序列t是另一個(gè)序列s的子序列（subsequence），如果t中每個(gè)有序元素都是s中一個(gè)有序元素的子集。DatasequenceSubsequenceContain?<{2,4}{3,5,6}{8}><{2}{3,5}>Yes<{1,2}{3,4}><{1}{2}>No<{2,4}{2,4}{2,5}><{2}{4}>Yes序列模式發(fā)現(xiàn)（SequentialPatternMining）設(shè)D是包含一個(gè)或多個(gè)數(shù)據(jù)序列的數(shù)據(jù)集:序列s的支持度是包含s的所有數(shù)據(jù)序列所占的比例。如果序列s的支持度大于或等于用戶(hù)指定的閾值minsup，則稱(chēng)s是一個(gè)序列模式（或頻繁序列）。定義7.1序列模式發(fā)現(xiàn):給定序列數(shù)據(jù)庫(kù)D和用戶(hù)指定的最小支持度閾值minsup，序列模式發(fā)現(xiàn)的任務(wù)是找出支持度大于或等于minsup的所有序列。例子Minsup

=50%ExamplesofFrequentSubsequences:<{1,2}> s=60%<{2,3}> s=60%<{2,4}> s=80%<{3}{5}> s=80%<{1}{2}> s=80%<{2}{2}> s=60%<{1}{2,3}> s=60%<{2}{2,3}> s=60%<{1,2}{2,3}> s=60%提取序列模式：蠻力方法給定n個(gè)事件的集族:i1,i2,i3,…,in候選1-序列:<{i1}>,<{i2}>,<{i3}>,…,<{in}>候選2-序列:<{i1,i2}>,<{i1,i3}>,…,<{in-1}{in}>,<{i1}{i1}>,<{i1}{i2}>,…,<{in-1}{in}>候選3-序列:<{i1,i2,i3}>,<{i1,i2,i4}>,…,<{i1,i2}{i1}>,<{i1,i2}{i2}>,…,<{i1}{i1,i2}>,<{i1}{i1,i3}>,…,<{i1}{i1}{i1}>,<{i1}{i1}{i2}>,…候選序列的個(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-序列，如<{i1,i2}>,<{i1}{i2}>,<{i2,i2}>,<{i1,i1}>。次序在序列中是重要的，但在項(xiàng)集中不重要。例如，{1,2}和{2,1}表示同一個(gè)項(xiàng)集，而<{i1}{i2}>和<{i2}{i1}>對(duì)應(yīng)于不同的序列，因此必須分別產(chǎn)生。先驗(yàn)原理對(duì)序列數(shù)據(jù)成立。包含特定k-序列的任何數(shù)據(jù)序列必然包含該k-序列的所有(k-1)-序列。序列模式發(fā)現(xiàn)的類(lèi)Apriori算法候選產(chǎn)生一對(duì)頻繁(k-1)-序列合并，產(chǎn)生候選k-序列。為了避免重復(fù)產(chǎn)生候選，傳統(tǒng)的Apriori算法僅當(dāng)前k-1項(xiàng)相同時(shí)才合并一對(duì)頻繁k-項(xiàng)集。類(lèi)似的方法可以用于序列。例子<{1}{2}{3}{4}>通過(guò)合并<{1}{2}{3}>和<{2}{3}{4}>得到。由于事件3和事件4屬于第二個(gè)序列的不同元素，它們?cè)诤喜⒑笮蛄兄幸矊儆诓煌脑亍?lt;{1}{5}{3,4}>通過(guò)合并<{1}{5}{3}>和<{5}{3,4}>得到。由于事件3和事件4屬于第二個(gè)序列的相同元素，4被合并到第一個(gè)序列的最后一個(gè)元素中。候選剪枝一個(gè)候選k-序列被剪枝，如果它的(k-1)-序列最少有一個(gè)是非頻繁的。例如，假設(shè)<{1}{2}{3}{4}>是一個(gè)候選4-序列。我們需要檢查<{1}{2}{4}>和<{1}{3}{4}>是否是頻繁3-序列。由于它們都不是頻繁的，因此可以刪除候選<{1}{2}{3}{4}>。支持度計(jì)數(shù)在支持度計(jì)數(shù)期間，算法將枚舉屬于一個(gè)特定數(shù)據(jù)序列的所有候選k-序列。計(jì)數(shù)之后，算法將識(shí)別出頻繁k-序列，并可以丟棄其支持度計(jì)數(shù)小于最小支持度閾值minsup的候選。圖7-6時(shí)限約束模式的事件和元素都施加時(shí)限約束。例子：學(xué)生A：<{統(tǒng)計(jì)學(xué)}{數(shù)據(jù)庫(kù)系統(tǒng)}{數(shù)據(jù)挖掘}>學(xué)生B：<{數(shù)據(jù)庫(kù)系統(tǒng)}{統(tǒng)計(jì)學(xué)}{數(shù)據(jù)挖掘}>感興趣的模式是<{統(tǒng)計(jì)學(xué)，數(shù)據(jù)庫(kù)系統(tǒng)}{數(shù)據(jù)挖掘}>，意思是說(shuō)注冊(cè)數(shù)據(jù)挖掘課程的學(xué)生必須先選修數(shù)據(jù)庫(kù)系統(tǒng)和統(tǒng)計(jì)學(xué)方面的課程。顯然，該模式被這兩個(gè)學(xué)生支持，盡管他們都沒(méi)有同時(shí)選修統(tǒng)計(jì)學(xué)和數(shù)據(jù)庫(kù)系統(tǒng)。相比之下，一個(gè)10年之前選修了統(tǒng)計(jì)學(xué)課程的學(xué)生不能認(rèn)為支持該模式，因?yàn)檫@些課程的時(shí)間間隔太長(zhǎng)了。圖7-7解釋了可以施加在模式上的某些時(shí)限約束。最大跨度約束最大跨度約束指定整個(gè)序列中所允許的事件的最晚和最早發(fā)生時(shí)間的最大時(shí)間差。假定最大時(shí)間跨度maxspan=3，下面的表包含了給定的數(shù)據(jù)序列支持和不支持的序列模式。數(shù)據(jù)序列s序列模式tS支持t?<{1,3}{3,4}{4}{5}{6,7}{8}><{3}{4}>是<{1,3}{3,4}{4}{5}{6,7}{8}><{3}{6}>是<{1,3}{3,4}{4}{5}{6,7}{8}><{1,3}{6}>否一般，maxspan越長(zhǎng)，在數(shù)據(jù)序列中檢測(cè)到模式的可能性就越大。然而，較長(zhǎng)的maxspan也可能捕獲不真實(shí)的模式可能涉及陳舊事件。最大跨度約束影響序列模式發(fā)現(xiàn)算法的支持度計(jì)數(shù)。施加最大時(shí)間跨度約束之后，有些數(shù)據(jù)序列就不再支持候選模式。最小間隔和最大間隔約束時(shí)限約束也可以通過(guò)限制序列中兩個(gè)相繼元素之間的時(shí)間差來(lái)指定。如果最大時(shí)間差（maxgap）是一周，則元素中的事件必須在前一個(gè)元素的事件出現(xiàn)后的一周之內(nèi)出現(xiàn)。如果最小時(shí)間差（mingap）是0，則元素中的事件必須在前一個(gè)元素的事件出現(xiàn)之后出現(xiàn)。假定maxgap=3，mingap=1，下表給出了模式通過(guò)或未通過(guò)最大間隔和最小間隔約束的例子。數(shù)據(jù)序列s序列模式tmaxgapmingap<{1,3}{3,4}{4}{5}{6,7}{8}><{3}{6}>通過(guò)通過(guò)<{1,3}{3,4}{4}{5}{6,7}{8}><{6}{8}>通過(guò)未通過(guò)<{1,3}{3,4}{4}{5}{6,7}{8}><{1,3}{6}>未通過(guò)通過(guò)<{1,3}{3,4}{4}{5}{6,7}{8}><{1}{3}{8}>未通過(guò)未通過(guò)與最大跨度一樣，這些約束也影響序列模式發(fā)現(xiàn)算法的支持度計(jì)數(shù)，因?yàn)楫?dāng)最小間隔和最大間隔約束存在時(shí)，有些數(shù)據(jù)序列就不再支持候選模式。使用最大間隔約束可能違反先驗(yàn)原理。為了解釋這一點(diǎn)，考慮圖7-5中的數(shù)據(jù)集。如果沒(méi)有最小間隔或最大間隔約束，<{2},{5}>和<{2}{3}{5}>的支持度都是60%。然而，如果mingap=0，maxgap=1，則<{2}{5}>的支持度下降至40%，而<{2}{3}{5}>的支持度仍然是60%。這與先驗(yàn)原理相違背。例子Minsup

=50%ExamplesofFrequentSubsequences:<{1,2}> s=60%<{2,3}> s=60%<{2,4}> s=80%<{3}{5}> s=80%<{1}{2}> s=80%<{2}{2}> s=60%<{1}{2,3}> s=60%<{2}{2,3}> s=60%<{1,2}{2,3}> s=60%定義7.2鄰接子序列序列s是序列w=<e1e2…ek>的鄰接子序列(contiguoussubsequence)，如果下列條件之一成立：（1）s是從e1或ek中刪除一個(gè)事件后由w得到。（2）s是從至少包含兩個(gè)事件的任意ei∈w中刪除一個(gè)事件后由w得到。（3）s是t的鄰接子序列，而t是w的鄰接子序列。數(shù)據(jù)序列s序列模式tt是s的鄰接子序列<{1}{2,3}

><{1}{2}>是<{1,2}{2}{3}><{1}{2}>是<{3,4}{1,2}{2,3}{4}><{1}{2}>是<{1}{3}{2}><{1}{2}>否<{1,2}{1}{3}{2}><{1}{2}>否定義7.3修訂的先驗(yàn)原理如果一個(gè)k-序列是頻繁的，則它的所有鄰接(k-1)-子序列也一定是頻繁的。在候選剪枝階段，并非所有的k-序列都需要檢查，因?yàn)樗鼈冎械囊恍┛赡苓`反最大間隔約束。例如，如果maxgap=1，則不必檢查候選<{1}{2,3}{4}{5}>的子序列<{1}{2,3}{5}>是否是頻繁的，因?yàn)樵貃2,3}和{5}之間的時(shí)間差大于一個(gè)時(shí)間單位。我們只需要考察<{1}{2,3}{4}{5}>的鄰接子序列，包括<{1}{2,3}{4}>，<{2,3}{4}{5}>，<{1}{2}{4}{5}>和<{1}{3}{4}{5}>。窗口大小約束最后，元素sj中的事件不必同時(shí)出現(xiàn)?？梢远x一個(gè)窗口大小閾值（ws）來(lái)指定序列模式的任意元素中事件最晚和最早出現(xiàn)之間的最大允許時(shí)間差。窗口大小為0表明模式同一元素中的所有事件必須同時(shí)出現(xiàn)。下面的例子使用ws=2，mingap=0，maxgap=3，maxspan=∞數(shù)據(jù)序列s序列模式tS支持t？<{1,3}{3,4}{4}{5}{6,7}{8}><{3,4}{5}>是<{1,3}{3,4}{4}{5}{6,7}{8}><{4,6}{8}>是<{1,3}{3,4}{4}{5}{6,7}{8}><{3,4,6}{8}>否<{1,3}{3,4}{4}{5}{6,7}{8}><{1,3,4}

{6,7,8}>否子圖模式關(guān)聯(lián)分析方法應(yīng)用到遠(yuǎn)比項(xiàng)集和序列更復(fù)雜實(shí)體。例子包括化學(xué)化合物、3-D蛋白質(zhì)結(jié)構(gòu)、網(wǎng)絡(luò)拓?fù)浜蜆?shù)結(jié)構(gòu)的XML文檔。這些實(shí)體可以用圖形表示建模。在這種類(lèi)型的數(shù)據(jù)上進(jìn)行數(shù)據(jù)挖掘的任務(wù)是，在圖的集合中發(fā)現(xiàn)一組公共子結(jié)構(gòu)。這樣的任務(wù)稱(chēng)作頻繁子圖挖掘圖與子圖定義7.5支持度給定一個(gè)圖的集族ζ,子圖g的支持度定義為包含它的所有圖所占的百分比，即例7.2考慮5個(gè)圖G1到G5，如圖7-10所示。右上角的圖g1是G1，G3，G4，G5的子圖，因此s(g1)=4/5=80%。類(lèi)似地，我們由s(g2)=60%，因?yàn)間2是G1、G2和G3的子圖；而s(g3)=40%，因?yàn)間3是G1和G3的子圖。頻繁子圖挖掘定義7.6頻繁子圖挖掘給定圖的集合和支持度閾值minsup，頻繁子圖挖掘的目標(biāo)是找出所有使得s(g)>=minsup的子圖g。本章的討論主要關(guān)注無(wú)向連通圖（undirected，connectedgraph）。挖掘頻繁子圖是一項(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ù)。在頻繁子圖挖掘中，每個(gè)實(shí)體是一個(gè)頂點(diǎn)，并且最多可以有d-1條到其他頂點(diǎn)的邊。假定頂點(diǎn)的標(biāo)號(hào)是唯一的，則子圖的總數(shù)是其中，是選擇i個(gè)頂點(diǎn)形成子圖的方法數(shù)，而是子圖的頂點(diǎn)之間邊的最大值。表7-8對(duì)不同的d比較了項(xiàng)集和子圖的個(gè)數(shù)。挖掘頻繁子圖的一種蠻力方法是，產(chǎn)生所有的連通子圖作為候選，并計(jì)算它們各自的支持度?？紤]圖7-11a中顯示的圖，假定頂點(diǎn)標(biāo)號(hào)選自集合{a，b}，而邊的標(biāo)號(hào)選自集合{p，q}，則具有一個(gè)到三個(gè)頂點(diǎn)的連通子圖列在圖7-11b中。候選子圖的個(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è)圖中出現(xiàn)多次。相同的頂點(diǎn)標(biāo)號(hào)對(duì)可以有多種邊標(biāo)號(hào)選擇。把事務(wù)轉(zhuǎn)化為圖把圖轉(zhuǎn)化為事務(wù)頻繁子圖挖掘算法的一般結(jié)構(gòu)一種挖掘頻繁子圖的類(lèi)Apriori算法由以下步驟組成候選產(chǎn)生：合并頻繁(k-1)-子圖對(duì)，得到候選k-子圖。候選剪枝：丟棄包含非頻繁的(k-1)-子圖的所有候選k-子圖。支持度計(jì)數(shù)：統(tǒng)計(jì)ζ中包含每個(gè)候選的圖的個(gè)數(shù)。候選刪除：丟棄支持度小于minsup的所有候選子圖。候選產(chǎn)生在候選產(chǎn)生階段，一對(duì)頻繁(k-1)-子圖合并成一個(gè)候選k-子圖。如何定義子圖的大小k？在圖7-11顯示的例子中，k是圖中的頂點(diǎn)個(gè)數(shù)。通過(guò)添加一個(gè)頂點(diǎn)，迭代的擴(kuò)展子圖的方法稱(chēng)作頂點(diǎn)增長(zhǎng)（vertexgrowing）。K也可以是圖中邊的個(gè)數(shù)。添加一條邊到已有的子圖中來(lái)擴(kuò)展子圖的方法稱(chēng)作邊增長(zhǎng)（edgegrowing）。為了避免產(chǎn)生重復(fù)的候選，可以對(duì)合并施加附加的條件：兩個(gè)(k-1)-子圖必須共享一個(gè)共同的(k-2)-子圖。共同的(k-2)-子圖稱(chēng)作核(core)。通過(guò)頂點(diǎn)增長(zhǎng)產(chǎn)生候選用鄰接矩陣表示圖。頂點(diǎn)增長(zhǎng)方法可以看成合并一對(duì)(k-1)×(k-1)的鄰接矩陣，產(chǎn)生k×k鄰接矩陣的過(guò)程。通過(guò)頂點(diǎn)增長(zhǎng)合并子圖的過(guò)程：鄰接矩陣M1與另一個(gè)鄰接矩陣M2合并，如果刪除M1和M2的最后一行和最后一列得到的子矩陣相同。結(jié)果矩陣是M1，添加上M2的最后一行和最后一列。新矩陣的其余項(xiàng)或者為0，或者用連接頂點(diǎn)對(duì)的合法的邊標(biāo)號(hào)替換。VertexGrowingarar結(jié)果圖包含的邊比原來(lái)的圖多一條或兩條。(d,e)可以相連或不相連。由于該邊的標(biāo)號(hào)未知，我們需要對(duì)(d,e)考慮所有可能的邊標(biāo)號(hào)，從而大大增加了候選子圖的個(gè)數(shù)。通過(guò)邊增長(zhǎng)產(chǎn)生候選在候選產(chǎn)生期間，邊增長(zhǎng)將一個(gè)新的邊插入一個(gè)已經(jīng)存在的頻繁子圖中。與頂點(diǎn)增長(zhǎng)不同，結(jié)果子圖的頂點(diǎn)個(gè)數(shù)不一定增加。通過(guò)邊增長(zhǎng)產(chǎn)生候選子圖的過(guò)程概括如下：一個(gè)頻繁子圖g1與另一個(gè)頻繁子圖g2合并，僅當(dāng)從g1刪除一條邊得到的子圖與從g2刪除一條邊得到的子圖拓?fù)涞葍r(jià)。合并后，結(jié)果子圖是g1，添加g2的那條額外的邊。a頂點(diǎn)拓?fù)涞葍r(jià)（topologicallyequivalent）：加入一條新邊到v1與加入該邊到v2產(chǎn)生的圖相同，則v1和v2兩頂點(diǎn)拓?fù)涞葍r(jià)。頂點(diǎn)拓?fù)涞葍r(jià)的概念能夠幫助我們理解，在邊增長(zhǎng)時(shí)為什么能夠產(chǎn)生多個(gè)候選子圖。如果a和c拓?fù)涞葍r(jià)，我們將它們記作a=c。對(duì)于核外邊的點(diǎn)，如果它們的標(biāo)號(hào)相同，我們將它們記作b=d。當(dāng)與一對(duì)(k-1)-子圖相關(guān)聯(lián)的核有多個(gè)時(shí)，還可能產(chǎn)生多個(gè)候選子圖。候選剪枝產(chǎn)生候選k-子圖后，需要剪去(k-1)-子圖非頻繁的候選。候選剪枝可以通過(guò)如下步驟實(shí)現(xiàn)：相繼從k-子圖刪除一條邊，并檢查對(duì)應(yīng)的(k-1)-子圖是否連通且頻繁。如果不是，則該候選k-子圖可以丟棄。為了檢查(k-1)-子圖是否頻繁，需要將它與其他頻繁(k-1)-子圖匹配。判定兩個(gè)圖是否拓?fù)涞葍r(jià)稱(chēng)為圖同構(gòu)（graphisomorphism）問(wèn)題。為了解釋圖同構(gòu)問(wèn)題的困難性，考慮圖7-19中的兩個(gè)圖。同構(gòu)圖處理圖同構(gòu)處理圖同構(gòu)問(wèn)題的標(biāo)準(zhǔn)方法是，將每一個(gè)圖都映射到一個(gè)唯一的串表達(dá)式，稱(chēng)作代碼（code）或規(guī)范標(biāo)號(hào)（canonicallabel）。規(guī)范標(biāo)號(hào)具有如下性質(zhì)：如果兩個(gè)圖是同構(gòu)的，則它們的代號(hào)一定相同。這個(gè)性質(zhì)使得我們可以通過(guò)比較圖的規(guī)范標(biāo)號(hào)來(lái)檢查圖同構(gòu)。構(gòu)造圖的規(guī)范標(biāo)號(hào)的第一步是找出圖的鄰接矩陣表示。一個(gè)圖可以有多種鄰接矩陣表示，因?yàn)榇嬖诙喾N確定頂點(diǎn)次序的方法。數(shù)學(xué)上講，每個(gè)排列都對(duì)應(yīng)于初始鄰接矩陣與一個(gè)對(duì)應(yīng)的排列矩陣的乘積，如下面的例子所示。例子：考慮下面的矩陣：其中，P13是通過(guò)交換單位矩陣的第一行和第三行得到的。為了交換M的第一和第三行（和列），排列矩陣與M相乘M右乘P13交換M的第一列和第三列，而M左乘P’13交換M的第一行和第三行。第二步是確定每個(gè)鄰接矩陣的串表示。由于鄰接矩陣是對(duì)稱(chēng)的，因此只需要根據(jù)矩陣的上三角部分構(gòu)造串表示就足夠了。在圖7-21所示的例子中，代碼是通過(guò)逐列連接矩陣的上三角元素得到的。最后一步是比較圖的所有串表達(dá)式，并選出具有最?。ㄗ畲螅┳值浯涡蛑档拇ＶС侄扔?jì)數(shù)支持度計(jì)數(shù)一般是開(kāi)銷(xiāo)很大的操作，因?yàn)閷?duì)于每個(gè)G∈ζ，必須確定包含在G中的所有候選子圖。加快該操作的一種方法是，維護(hù)一個(gè)與每個(gè)頻繁(k-1)-子圖相關(guān)聯(lián)的圖ID表。一旦一個(gè)新的候選k-子圖通過(guò)合并一對(duì)頻繁(k-1)-子圖而產(chǎn)生，就對(duì)它們的對(duì)應(yīng)圖ID表求交集。最后，子圖同構(gòu)檢查就在表中的圖上進(jìn)行，確定它們是否包含特定的子圖。非頻繁模式迄今為止，關(guān)聯(lián)分析都基于這樣的前提：項(xiàng)在事務(wù)中出現(xiàn)比不出現(xiàn)更重要。因此，數(shù)據(jù)庫(kù)中很少出現(xiàn)的模式不是令人感興趣的，并使用支持度度量將其刪除。這種模式稱(chēng)為非頻繁模式。定義7.7非頻繁模式非頻繁模式是一個(gè)項(xiàng)集或規(guī)則，其支持度小于閾值minsup。盡管絕大部分非頻繁模式都是讓人不感興趣的，但是其中的一些可能對(duì)于分析是有用的，特別是涉及到數(shù)據(jù)中的負(fù)相關(guān)性。例如：DVD和VCR一起銷(xiāo)售的情況很少，因?yàn)橘?gòu)買(mǎi)DVD的人多半不會(huì)購(gòu)買(mǎi)VCR，反之亦然。這種負(fù)相關(guān)模式有助于識(shí)別競(jìng)爭(zhēng)項(xiàng)（competingitem）。競(jìng)爭(zhēng)項(xiàng)的例子包括茶與咖啡、黃油與人造黃油、普通與節(jié)食蘇打、臺(tái)式機(jī)與便攜式計(jì)算機(jī)。某些非頻繁模式也可能暗示數(shù)據(jù)中出現(xiàn)了某些有趣的罕見(jiàn)事件或例外情況。例如：如果{火災(zāi)=yes}是頻繁的，但{火災(zāi)=yes，報(bào)警=on}是非頻繁的。而后者是一個(gè)有趣的非頻繁模式，因?yàn)樗赡苤赋鼍瘓?bào)系統(tǒng)的故障。為了檢測(cè)這種不尋常情況，必須確定模式的期望支持度，使得如果一個(gè)模式的支持度明顯低于期望支持度，則可以聲明它是一個(gè)有趣的非頻繁模式。負(fù)模式設(shè)I={i1,i2,…,id}是項(xiàng)的集合。負(fù)項(xiàng)ik表示項(xiàng)ik不在給定的事務(wù)中出現(xiàn)。例如，如果事務(wù)中不包含咖啡，則咖啡是一個(gè)值為1的負(fù)項(xiàng)。定義7.8負(fù)項(xiàng)集負(fù)項(xiàng)集X是一個(gè)具有如下性質(zhì)的項(xiàng)集：（1）X=A∪B，其中A是正項(xiàng)的集合，而B(niǎo)是負(fù)項(xiàng)的集合，|B|≥1;（2）s(X)≥

minsup。定義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ī)則的置信度大于或等于minconf本章中，負(fù)項(xiàng)集和負(fù)關(guān)聯(lián)規(guī)則統(tǒng)稱(chēng)負(fù)模式負(fù)相關(guān)模式定義7.10負(fù)相關(guān)項(xiàng)集項(xiàng)集X={x1,x2,…,xk}是負(fù)相關(guān)的，如果定義7.11負(fù)相關(guān)關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則XY是負(fù)相關(guān)的，如果s(X∪Y)<s(X)s(Y)，其中，X和Y是不相交的項(xiàng)集，即X∩Y=￠。負(fù)相關(guān)的完全條件可以表述如下：負(fù)相關(guān)條件也可以用正項(xiàng)集和負(fù)項(xiàng)集的支持度表示。設(shè)和分別表示X和Y的對(duì)應(yīng)負(fù)項(xiàng)集，由于負(fù)相關(guān)條件可以表述如下：負(fù)相關(guān)項(xiàng)集和負(fù)相關(guān)關(guān)聯(lián)規(guī)則統(tǒng)稱(chēng)負(fù)相關(guān)模式（negativelycorrelatedpattern）非頻繁模式、負(fù)模式和負(fù)相關(guān)模式比較非頻繁模式、負(fù)模式和負(fù)相關(guān)模式是三個(gè)密切相關(guān)的概念。盡管非頻繁模式和負(fù)相關(guān)模式只涉及包含正項(xiàng)的項(xiàng)集或模式，而負(fù)模式涉及包含正項(xiàng)和負(fù)項(xiàng)的項(xiàng)集或模式，但是這三個(gè)概念之間存在一定的共性，如圖7-22所示首先，許多非頻繁模式有對(duì)應(yīng)的負(fù)模式。如果x∪y是非頻繁的，則除非minsup太高，否則它很可能有對(duì)應(yīng)的負(fù)項(xiàng)集。例如：假定minsup<0.25，如果x∪y是非頻繁的，則表中的其它幾種組合至少有一種是頻繁的。yyxS(x∪y)S(x∪y)S(x)xS(x∪y)S(x∪y)S(x)S(y)S(y)1挖掘有趣的非頻繁模式的技術(shù)原則上講，非頻繁項(xiàng)集是未被標(biāo)準(zhǔn)的頻繁項(xiàng)集產(chǎn)生算法（如Apriori和FP增長(zhǎng)）提取的所有項(xiàng)集。這些項(xiàng)集對(duì)應(yīng)于圖7-23所示的頻繁項(xiàng)集邊界之下的那些項(xiàng)集。由于非頻繁模式的數(shù)量可能是指數(shù)級(jí)的，特別是對(duì)于稀疏的、高維的數(shù)據(jù)。因此，為挖掘非頻繁模式而開(kāi)發(fā)的技術(shù)著力于發(fā)現(xiàn)有趣的非頻繁模式。例如：負(fù)相關(guān)模式基于挖掘負(fù)模式的技術(shù)一種方法是將每個(gè)項(xiàng)看作對(duì)稱(chēng)的二元變量。通過(guò)用負(fù)項(xiàng)