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

關(guān)聯(lián)分析高級概念第一頁，共一百零一頁，2022年，8月28日關(guān)聯(lián)分析處理事務(wù)數(shù)據(jù)RulesDiscovered:

{Diaper}-->{Beer}第二頁，共一百零一頁，2022年，8月28日處理分類屬性我們可能發(fā)現(xiàn)關(guān)于因特網(wǎng)用戶特征的有趣信息:{網(wǎng)上購物=是}{關(guān)注隱私=是}許多應(yīng)用包含對稱二元屬性和標(biāo)稱屬性。表7-1顯示的因特網(wǎng)調(diào)查數(shù)據(jù)包含對稱二元屬性，如：性別、家庭計(jì)算機(jī)、網(wǎng)上聊天、網(wǎng)上購物和關(guān)注隱私；還包括標(biāo)稱屬性，如文化程度和州。第三頁，共一百零一頁，2022年，8月28日處理分類屬性為了提取這樣的模式，我們需要將標(biāo)稱屬性和對稱二元屬性轉(zhuǎn)換成“項(xiàng)”，使得已有的關(guān)聯(lián)規(guī)則挖掘算法可以使用。這種類型的變化可以通過為每個不同的屬性-值對創(chuàng)建一個新的項(xiàng)來實(shí)現(xiàn)。例如:標(biāo)稱屬性文化程度可以用三個二元項(xiàng)取代文化程度=大學(xué)文化程度=研究生文化程度=高中類似的，對稱二元屬性性別可以轉(zhuǎn)換成一對二元項(xiàng)：性別=男、性別=女。第四頁，共一百零一頁，2022年，8月28日第五頁，共一百零一頁，2022年，8月28日處理分類屬性將關(guān)聯(lián)分析用于二元化后的數(shù)據(jù)時，需要考慮如下問題。(1)有些屬性值可能不夠頻繁，不能成為頻繁模式的一部分。如：州名。解決辦法：將相關(guān)的屬性值分組，形成少數(shù)類別。例如，每個州名都可以用對應(yīng)的地理區(qū)域取代。例如：分別用中西部、太平洋西北部、西南部和東海岸取代。第六頁，共一百零一頁，2022年，8月28日處理分類屬性將關(guān)聯(lián)分析用于二元化后的數(shù)據(jù)時，需要考慮如下問題。(2)某些屬性值的頻率可能比其他屬性高很多。如：假定85%的被調(diào)查人都有家庭計(jì)算機(jī)，如果為每個頻繁出現(xiàn)在數(shù)據(jù)中的屬性值創(chuàng)建一個二元項(xiàng)，我們可能產(chǎn)生許多冗余模式。

{家庭計(jì)算機(jī)=是，網(wǎng)上購物=是}{關(guān)注隱私=是}解決辦法：使用處理具有寬支持度的極差數(shù)據(jù)集的技術(shù)。第七頁，共一百零一頁，2022年，8月28日處理分類屬性將關(guān)聯(lián)分析用于二元化后的數(shù)據(jù)時，需要考慮如下問題。(3)計(jì)算時間可能增加，特別是當(dāng)新創(chuàng)建的項(xiàng)變成頻繁項(xiàng)時。因?yàn)闀a(chǎn)生更多的候選項(xiàng)集。解決辦法：避免產(chǎn)生包含多個來自同一個屬性的項(xiàng)的候選項(xiàng)集。例如：不必產(chǎn)生諸如{州=X，州=Y，…}的候選項(xiàng)集，因?yàn)樵擁?xiàng)集支持度為零。第八頁，共一百零一頁，2022年，8月28日處理連續(xù)屬性因特網(wǎng)調(diào)查數(shù)據(jù)可能還包含連續(xù)屬性，如表7-3所示。挖掘連續(xù)屬性可能揭示數(shù)據(jù)的內(nèi)在聯(lián)系，如“年收入超過120k的用戶屬于45-60年齡組”或“擁有超過3個email帳號并且每周上網(wǎng)超過15小時的用戶通常關(guān)注個人隱私”:包含連續(xù)屬性的關(guān)聯(lián)規(guī)則通常稱作量化關(guān)聯(lián)規(guī)則（quantiativeassociationrule）。對連續(xù)數(shù)據(jù)進(jìn)行關(guān)聯(lián)分析的方法:基于離散化的方法非離散化方法基于統(tǒng)計(jì)學(xué)的方法第九頁，共一百零一頁，2022年，8月28日第十頁，共一百零一頁，2022年，8月28日基于離散化的方法離散化是處理連續(xù)屬性最常用的方法。這種方法將連續(xù)屬性的鄰近值分組，形成有限個區(qū)間。例如：年齡屬性可以劃分為如下區(qū)間：

[12,16),[16,20),[20,24),…,[56,60)離散化技術(shù)：等寬、等頻、聚類表7-4顯示了離散化和二元化后的因特網(wǎng)調(diào)查數(shù)據(jù)。第十一頁，共一百零一頁，2022年，8月28日第十二頁，共一百零一頁，2022年，8月28日屬性離散化的一個關(guān)鍵在于劃分每個屬性的區(qū)間個數(shù)和寬度。然而，確定正確的區(qū)間是困難的。第十三頁，共一百零一頁，2022年，8月28日如果支持度閾值=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ū)間寬度對關(guān)聯(lián)分析結(jié)果的影響。（1）如果區(qū)間太寬，則可能因?yàn)槿狈χ眯哦榷ツ承┮?guī)則例如：當(dāng)區(qū)間寬度為24歲時，上面的兩個規(guī)則變?yōu)?/p>

[16,36)網(wǎng)上聊天=是（s=30%，57.7%）

[36,60)網(wǎng)上聊天=否（s=28%，58.3%）第十四頁，共一百零一頁，2022年，8月28日區(qū)間寬度對關(guān)聯(lián)分析結(jié)果的影響。（2）如果區(qū)間太窄，則可能因?yàn)槿狈χС侄榷ツ承┮?guī)則例如：當(dāng)區(qū)間寬度為4歲時，上面的兩個規(guī)則變?yōu)?/p>

[16,20)網(wǎng)上聊天=是（s=4.4%，84.6%）

[20,24)網(wǎng)上聊天=是（s=4.4%，78.6%）（3）當(dāng)區(qū)間寬度為8歲時，上面的兩個規(guī)則變?yōu)?/p>

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

E2E1

E3E2E3

E4E2Element(Transaction)Event

(Item)第二十五頁，共一百零一頁，2022年，8月28日序列數(shù)據(jù)的例子第二十六頁，共一百零一頁，2022年，8月28日子序列（

Subsequence）序列t是另一個序列s的子序列（subsequence），如果t中每個有序元素都是s中一個有序元素的子集。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第二十七頁，共一百零一頁，2022年，8月28日序列模式發(fā)現(xiàn)（SequentialPatternMining）設(shè)D是包含一個或多個數(shù)據(jù)序列的數(shù)據(jù)集:序列s的支持度是包含s的所有數(shù)據(jù)序列所占的比例。如果序列s的支持度大于或等于用戶指定的閾值minsup，則稱s是一個序列模式（或頻繁序列）。定義7.1序列模式發(fā)現(xiàn):給定序列數(shù)據(jù)庫D和用戶指定的最小支持度閾值minsup，序列模式發(fā)現(xiàn)的任務(wù)是找出支持度大于或等于minsup的所有序列。第二十八頁，共一百零一頁，2022年，8月28日例子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%第二十九頁，共一百零一頁，2022年，8月28日提取序列模式：蠻力方法給定n個事件的集族: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}>,…第三十頁，共一百零一頁，2022年，8月28日候選序列的個數(shù)比候選項(xiàng)集的個數(shù)大得多。產(chǎn)生更多候選的原因有下面兩個一個項(xiàng)在項(xiàng)集中最多出現(xiàn)一次，但一個事件可以在序列中出現(xiàn)多次。給定兩個項(xiàng)i1和i2，只能產(chǎn)生一個候選2-項(xiàng)集{i1，i2}，但卻可以產(chǎn)生許多候選2-序列，如<{i1,i2}>,<{i1}{i2}>,<{i2,i2}>,<{i1,i1}>。次序在序列中是重要的，但在項(xiàng)集中不重要。例如，{1,2}和{2,1}表示同一個項(xiàng)集，而<{i1}{i2}>和<{i2}{i1}>對應(yīng)于不同的序列，因此必須分別產(chǎn)生。先驗(yàn)原理對序列數(shù)據(jù)成立。包含特定k-序列的任何數(shù)據(jù)序列必然包含該k-序列的所有(k-1)-序列。第三十一頁，共一百零一頁，2022年，8月28日序列模式發(fā)現(xiàn)的類Apriori算法第三十二頁，共一百零一頁，2022年，8月28日候選產(chǎn)生一對頻繁(k-1)-序列合并，產(chǎn)生候選k-序列。為了避免重復(fù)產(chǎn)生候選，傳統(tǒng)的Apriori算法僅當(dāng)前k-1項(xiàng)相同時才合并一對頻繁k-項(xiàng)集。類似的方法可以用于序列。例子<{1}{2}{3}{4}>通過合并<{1}{2}{3}>和<{2}{3}{4}>得到。由于事件3和事件4屬于第二個序列的不同元素，它們在合并后序列中也屬于不同的元素。<{1}{5}{3,4}>通過合并<{1}{5}{3}>和<{5}{3,4}>得到。由于事件3和事件4屬于第二個序列的相同元素，4被合并到第一個序列的最后一個元素中。第三十三頁，共一百零一頁，2022年，8月28日第三十四頁，共一百零一頁，2022年，8月28日候選剪枝一個候選k-序列被剪枝，如果它的(k-1)-序列最少有一個是非頻繁的。例如，假設(shè)<{1}{2}{3}{4}>是一個候選4-序列。我們需要檢查<{1}{2}{4}>和<{1}{3}{4}>是否是頻繁3-序列。由于它們都不是頻繁的，因此可以刪除候選<{1}{2}{3}{4}>。支持度計(jì)數(shù)在支持度計(jì)數(shù)期間，算法將枚舉屬于一個特定數(shù)據(jù)序列的所有候選k-序列。計(jì)數(shù)之后，算法將識別出頻繁k-序列，并可以丟棄其支持度計(jì)數(shù)小于最小支持度閾值minsup的候選。第三十五頁，共一百零一頁，2022年，8月28日圖7-6第三十六頁，共一百零一頁，2022年，8月28日時限約束模式的事件和元素都施加時限約束。例子：學(xué)生A：<{統(tǒng)計(jì)學(xué)}{數(shù)據(jù)庫系統(tǒng)}{數(shù)據(jù)挖掘}>學(xué)生B：<{數(shù)據(jù)庫系統(tǒng)}{統(tǒng)計(jì)學(xué)}{數(shù)據(jù)挖掘}>感興趣的模式是<{統(tǒng)計(jì)學(xué)，數(shù)據(jù)庫系統(tǒng)}{數(shù)據(jù)挖掘}>，意思是說注冊數(shù)據(jù)挖掘課程的學(xué)生必須先選修數(shù)據(jù)庫系統(tǒng)和統(tǒng)計(jì)學(xué)方面的課程。顯然，該模式被這兩個學(xué)生支持，盡管他們都沒有同時選修統(tǒng)計(jì)學(xué)和數(shù)據(jù)庫系統(tǒng)。相比之下，一個10年之前選修了統(tǒng)計(jì)學(xué)課程的學(xué)生不能認(rèn)為支持該模式，因?yàn)檫@些課程的時間間隔太長了。第三十七頁，共一百零一頁，2022年，8月28日圖7-7解釋了可以施加在模式上的某些時限約束。第三十八頁，共一百零一頁，2022年，8月28日最大跨度約束最大跨度約束指定整個序列中所允許的事件的最晚和最早發(fā)生時間的最大時間差。假定最大時間跨度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}>否第三十九頁，共一百零一頁，2022年，8月28日一般，maxspan越長，在數(shù)據(jù)序列中檢測到模式的可能性就越大。然而，較長的maxspan也可能捕獲不真實(shí)的模式可能涉及陳舊事件。最大跨度約束影響序列模式發(fā)現(xiàn)算法的支持度計(jì)數(shù)。施加最大時間跨度約束之后，有些數(shù)據(jù)序列就不再支持候選模式。第四十頁，共一百零一頁，2022年，8月28日最小間隔和最大間隔約束時限約束也可以通過限制序列中兩個相繼元素之間的時間差來指定。如果最大時間差（maxgap）是一周，則元素中的事件必須在前一個元素的事件出現(xiàn)后的一周之內(nèi)出現(xiàn)。如果最小時間差（mingap）是0，則元素中的事件必須在前一個元素的事件出現(xiàn)之后出現(xiàn)。第四十一頁，共一百零一頁，2022年，8月28日假定maxgap=3，mingap=1，下表給出了模式通過或未通過最大間隔和最小間隔約束的例子。數(shù)據(jù)序列s序列模式tmaxgapmingap<{1,3}{3,4}{4}{5}{6,7}{8}><{3}{6}>通過通過<{1,3}{3,4}{4}{5}{6,7}{8}><{6}{8}>通過未通過<{1,3}{3,4}{4}{5}{6,7}{8}><{1,3}{6}>未通過通過<{1,3}{3,4}{4}{5}{6,7}{8}><{1}{3}{8}>未通過未通過第四十二頁，共一百零一頁，2022年，8月28日與最大跨度一樣，這些約束也影響序列模式發(fā)現(xiàn)算法的支持度計(jì)數(shù)，因?yàn)楫?dāng)最小間隔和最大間隔約束存在時，有些數(shù)據(jù)序列就不再支持候選模式。使用最大間隔約束可能違反先驗(yàn)原理。為了解釋這一點(diǎn)，考慮圖7-5中的數(shù)據(jù)集。如果沒有最小間隔或最大間隔約束，<{2},{5}>和<{2}{3}{5}>的支持度都是60%。然而，如果mingap=0，maxgap=1，則<{2}{5}>的支持度下降至40%，而<{2}{3}{5}>的支持度仍然是60%。這與先驗(yàn)原理相違背。第四十三頁，共一百零一頁，2022年，8月28日例子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%第四十四頁，共一百零一頁，2022年，8月28日定義7.2鄰接子序列序列s是序列w=<e1e2…ek>的鄰接子序列(contiguoussubsequence)，如果下列條件之一成立：（1）s是從e1或ek中刪除一個事件后由w得到。（2）s是從至少包含兩個事件的任意ei∈w中刪除一個事件后由w得到。（3）s是t的鄰接子序列，而t是w的鄰接子序列。第四十五頁，共一百零一頁，2022年，8月28日數(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}>否第四十六頁，共一百零一頁，2022年，8月28日定義7.3修訂的先驗(yàn)原理如果一個k-序列是頻繁的，則它的所有鄰接(k-1)-子序列也一定是頻繁的。在候選剪枝階段，并非所有的k-序列都需要檢查，因?yàn)樗鼈冎械囊恍┛赡苓`反最大間隔約束。例如，如果maxgap=1，則不必檢查候選<{1}{2,3}{4}{5}>的子序列<{1}{2,3}{5}>是否是頻繁的，因?yàn)樵貃2,3}和{5}之間的時間差大于一個時間單位。我們只需要考察<{1}{2,3}{4}{5}>的鄰接子序列，包括<{1}{2,3}{4}>，<{2,3}{4}{5}>，<{1}{2}{4}{5}>和<{1}{3}{4}{5}>。第四十七頁，共一百零一頁，2022年，8月28日窗口大小約束最后，元素sj中的事件不必同時出現(xiàn)。可以定義一個窗口大小閾值（ws）來指定序列模式的任意元素中事件最晚和最早出現(xiàn)之間的最大允許時間差。窗口大小為0表明模式同一元素中的所有事件必須同時出現(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}>否第四十八頁，共一百零一頁，2022年，8月28日子圖模式關(guān)聯(lián)分析方法應(yīng)用到遠(yuǎn)比項(xiàng)集和序列更復(fù)雜實(shí)體。例子包括化學(xué)化合物、3-D蛋白質(zhì)結(jié)構(gòu)、網(wǎng)絡(luò)拓?fù)浜蜆浣Y(jié)構(gòu)的XML文檔。這些實(shí)體可以用圖形表示建模。在這種類型的數(shù)據(jù)上進(jìn)行數(shù)據(jù)挖掘的任務(wù)是，在圖的集合中發(fā)現(xiàn)一組公共子結(jié)構(gòu)。這樣的任務(wù)稱作頻繁子圖挖掘第四十九頁，共一百零一頁，2022年，8月28日圖與子圖第五十頁，共一百零一頁，2022年，8月28日定義7.5支持度給定一個圖的集族ζ,子圖g的支持度定義為包含它的所有圖所占的百分比，即例7.2考慮5個圖G1到G5，如圖7-10所示。右上角的圖g1是G1，G3，G4，G5的子圖，因此s(g1)=4/5=80%。類似地，我們由s(g2)=60%，因?yàn)間2是G1、G2和G3的子圖；而s(g3)=40%，因?yàn)間3是G1和G3的子圖。第五十一頁，共一百零一頁，2022年，8月28日第五十二頁，共一百零一頁，2022年，8月28日頻繁子圖挖掘定義7.6頻繁子圖挖掘給定圖的集合和支持度閾值minsup，頻繁子圖挖掘的目標(biāo)是找出所有使得s(g)>=minsup的子圖g。本章的討論主要關(guān)注無向連通圖（undirected，connectedgraph）。挖掘頻繁子圖是一項(xiàng)計(jì)算量很大的任務(wù)，因?yàn)樗阉骺臻g是指數(shù)的。為了解釋這項(xiàng)任務(wù)的復(fù)雜性，考慮一個包含d個實(shí)體的數(shù)據(jù)集。在頻繁項(xiàng)集挖掘中，每個實(shí)體是一個項(xiàng)，待考察的搜索空間是2d，這是可能產(chǎn)生的候選項(xiàng)集的個數(shù)。第五十三頁，共一百零一頁，2022年，8月28日在頻繁子圖挖掘中，每個實(shí)體是一個頂點(diǎn)，并且最多可以有d-1條到其他頂點(diǎn)的邊。假定頂點(diǎn)的標(biāo)號是唯一的，則子圖的總數(shù)是其中，是選擇i個頂點(diǎn)形成子圖的方法數(shù)，而是子圖的頂點(diǎn)之間邊的最大值。表7-8對不同的d比較了項(xiàng)集和子圖的個數(shù)。第五十四頁，共一百零一頁，2022年，8月28日挖掘頻繁子圖的一種蠻力方法是，產(chǎn)生所有的連通子圖作為候選，并計(jì)算它們各自的支持度?？紤]圖7-11a中顯示的圖，假定頂點(diǎn)標(biāo)號選自集合{a，b}，而邊的標(biāo)號選自集合{p，q}，則具有一個到三個頂點(diǎn)的連通子圖列在圖7-11b中。候選子圖的個數(shù)比傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘中的候選項(xiàng)集的個數(shù)大得多，其原因：一個項(xiàng)在一個項(xiàng)集中至多出現(xiàn)一次，而一個頂點(diǎn)標(biāo)號可能在一個圖中出現(xiàn)多次。相同的頂點(diǎn)標(biāo)號對可以有多種邊標(biāo)號選擇。第五十五頁，共一百零一頁，2022年，8月28日第五十六頁，共一百零一頁，2022年，8月28日把事務(wù)轉(zhuǎn)化為圖第五十七頁，共一百零一頁，2022年，8月28日把圖轉(zhuǎn)化為事務(wù)第五十八頁，共一百零一頁，2022年，8月28日頻繁子圖挖掘算法的一般結(jié)構(gòu)一種挖掘頻繁子圖的類Apriori算法由以下步驟組成候選產(chǎn)生：合并頻繁(k-1)-子圖對，得到候選k-子圖。候選剪枝：丟棄包含非頻繁的(k-1)-子圖的所有候選k-子圖。支持度計(jì)數(shù)：統(tǒng)計(jì)ζ中包含每個候選的圖的個數(shù)。候選刪除：丟棄支持度小于minsup的所有候選子圖。第五十九頁，共一百零一頁，2022年，8月28日候選產(chǎn)生在候選產(chǎn)生階段，一對頻繁(k-1)-子圖合并成一個候選k-子圖。如何定義子圖的大小k？在圖7-11顯示的例子中，k是圖中的頂點(diǎn)個數(shù)。通過添加一個頂點(diǎn)，迭代的擴(kuò)展子圖的方法稱作頂點(diǎn)增長（vertexgrowing）。K也可以是圖中邊的個數(shù)。添加一條邊到已有的子圖中來擴(kuò)展子圖的方法稱作邊增長（edgegrowing）。為了避免產(chǎn)生重復(fù)的候選，可以對合并施加附加的條件：兩個(k-1)-子圖必須共享一個共同的(k-2)-子圖。共同的(k-2)-子圖稱作核(core)。第六十頁，共一百零一頁，2022年，8月28日通過頂點(diǎn)增長產(chǎn)生候選用鄰接矩陣表示圖。頂點(diǎn)增長方法可以看成合并一對(k-1)×(k-1)的鄰接矩陣，產(chǎn)生k×k鄰接矩陣的過程。通過頂點(diǎn)增長合并子圖的過程：鄰接矩陣M1與另一個鄰接矩陣M2合并，如果刪除M1和M2的最后一行和最后一列得到的子矩陣相同。結(jié)果矩陣是M1，添加上M2的最后一行和最后一列。新矩陣的其余項(xiàng)或者為0，或者用連接頂點(diǎn)對的合法的邊標(biāo)號替換。第六十一頁，共一百零一頁，2022年，8月28日VertexGrowingarar第六十二頁，共一百零一頁，2022年，8月28日結(jié)果圖包含的邊比原來的圖多一條或兩條。(d,e)可以相連或不相連。由于該邊的標(biāo)號未知，我們需要對(d,e)考慮所有可能的邊標(biāo)號，從而大大增加了候選子圖的個數(shù)。第六十三頁，共一百零一頁，2022年，8月28日通過邊增長產(chǎn)生候選在候選產(chǎn)生期間，邊增長將一個新的邊插入一個已經(jīng)存在的頻繁子圖中。與頂點(diǎn)增長不同，結(jié)果子圖的頂點(diǎn)個數(shù)不一定增加。通過邊增長產(chǎn)生候選子圖的過程概括如下：一個頻繁子圖g1與另一個頻繁子圖g2合并，僅當(dāng)從g1刪除一條邊得到的子圖與從g2刪除一條邊得到的子圖拓?fù)涞葍r。合并后，結(jié)果子圖是g1，添加g2的那條額外的邊。第六十四頁，共一百零一頁，2022年，8月28日a第六十五頁，共一百零一頁，2022年，8月28日頂點(diǎn)拓?fù)涞葍r（topologicallyequivalent）：加入一條新邊到v1與加入該邊到v2產(chǎn)生的圖相同，則v1和v2兩頂點(diǎn)拓?fù)涞葍r。第六十六頁，共一百零一頁，2022年，8月28日頂點(diǎn)拓?fù)涞葍r的概念能夠幫助我們理解，在邊增長時為什么能夠產(chǎn)生多個候選子圖。如果a和c拓?fù)涞葍r，我們將它們記作a=c。對于核外邊的點(diǎn)，如果它們的標(biāo)號相同，我們將它們記作b=d。第六十七頁，共一百零一頁，2022年，8月28日第六十八頁，共一百零一頁，2022年，8月28日當(dāng)與一對(k-1)-子圖相關(guān)聯(lián)的核有多個時，還可能產(chǎn)生多個候選子圖。第六十九頁，共一百零一頁，2022年，8月28日候選剪枝產(chǎn)生候選k-子圖后，需要剪去(k-1)-子圖非頻繁的候選。候選剪枝可以通過如下步驟實(shí)現(xiàn)：相繼從k-子圖刪除一條邊，并檢查對應(yīng)的(k-1)-子圖是否連通且頻繁。如果不是，則該候選k-子圖可以丟棄。為了檢查(k-1)-子圖是否頻繁，需要將它與其他頻繁(k-1)-子圖匹配。判定兩個圖是否拓?fù)涞葍r稱為圖同構(gòu)（graphisomorphism）問題。為了解釋圖同構(gòu)問題的困難性，考慮圖7-19中的兩個圖。第七十頁，共一百零一頁，2022年，8月28日同構(gòu)圖第七十一頁，共一百零一頁，2022年，8月28日處理圖同構(gòu)處理圖同構(gòu)問題的標(biāo)準(zhǔn)方法是，將每一個圖都映射到一個唯一的串表達(dá)式，稱作代碼（code）或規(guī)范標(biāo)號（canonicallabel）。規(guī)范標(biāo)號具有如下性質(zhì)：如果兩個圖是同構(gòu)的，則它們的代號一定相同。這個性質(zhì)使得我們可以通過比較圖的規(guī)范標(biāo)號來檢查圖同構(gòu)。構(gòu)造圖的規(guī)范標(biāo)號的第一步是找出圖的鄰接矩陣表示。一個圖可以有多種鄰接矩陣表示，因?yàn)榇嬖诙喾N確定頂點(diǎn)次序的方法。第七十二頁，共一百零一頁，2022年，8月28日第七十三頁，共一百零一頁，2022年，8月28日數(shù)學(xué)上講，每個排列都對應(yīng)于初始鄰接矩陣與一個對應(yīng)的排列矩陣的乘積，如下面的例子所示。例子：考慮下面的矩陣：其中，P13是通過交換單位矩陣的第一行和第三行得到的。為了交換M的第一和第三行（和列），排列矩陣與M相乘第七十四頁，共一百零一頁，2022年，8月28日M右乘P13交換M的第一列和第三列，而M左乘P’13交換M的第一行和第三行。第二步是確定每個鄰接矩陣的串表示。由于鄰接矩陣是對稱的，因此只需要根據(jù)矩陣的上三角部分構(gòu)造串表示就足夠了。在圖7-21所示的例子中，代碼是通過逐列連接矩陣的上三角元素得到的。最后一步是比較圖的所有串表達(dá)式，并選出具有最小（最大）字典次序值的串。第七十五頁，共一百零一頁，2022年，8月28日第七十六頁，共一百零一頁，2022年，8月28日支持度計(jì)數(shù)支持度計(jì)數(shù)一般是開銷很大的操作，因?yàn)閷τ诿總€G∈ζ，必須確定包含在G中的所有候選子圖。加快該操作的一種方法是，維護(hù)一個與每個頻繁(k-1)-子圖相關(guān)聯(lián)的圖ID表。一旦一個新的候選k-子圖通過合并一對頻繁(k-1)-子圖而產(chǎn)生，就對它們的對應(yīng)圖ID表求交集。最后，子圖同構(gòu)檢查就在表中的圖上進(jìn)行，確定它們是否包含特定的子圖。第七十七頁，共一百零一頁，2022年，8月28日非頻繁模式迄今為止，關(guān)聯(lián)分析都基于這樣的前提：項(xiàng)在事務(wù)中出現(xiàn)比不出現(xiàn)更重要。因此，數(shù)據(jù)庫中很少出現(xiàn)的模式不是令人感興趣的，并使用支持度度量將其刪除。這種模式稱為非頻繁模式。定義7.7非頻繁模式非頻繁模式是一個項(xiàng)集或規(guī)則，其支持度小于閾值minsup。第七十八頁，共一百零一頁，2022年，8月28日盡管絕大部分非頻繁模式都是讓人不感興趣的，但是其中的一些可能對于分析是有用的，特別是涉及到數(shù)據(jù)中的負(fù)相關(guān)性。例如：DVD和VCR一起銷售的情況很少，因?yàn)橘徺IDVD的人多半不會購買VCR，反之亦然。這種負(fù)相關(guān)模式有助于識別競爭項(xiàng)（competingitem）。競爭項(xiàng)的例子包括茶與咖啡、黃油與人造黃油、普通與節(jié)食蘇打、臺式機(jī)與便攜式計(jì)算機(jī)。第七十九頁，共一百零一頁，2022年，8月28日某些非頻繁模式也可能暗示數(shù)據(jù)中出現(xiàn)了某些有趣的罕見事件或例外情況。例如：如果{火災(zāi)=yes}是頻繁的，但{火災(zāi)=yes，報警=on}是非頻繁的。而后者是一個有趣的非頻繁模式，因?yàn)樗赡苤赋鼍瘓笙到y(tǒng)的故障。為了檢測這種不尋常情況，必須確定模式的期望支持度，使得如果一個模式的支持度明顯低于期望支持度，則可以聲明它是一個有趣的非頻繁模式。第八十頁，共一百零一頁，2022年，8月28日負(fù)模式設(shè)I={i1,i2,…,id}是項(xiàng)的集合。負(fù)項(xiàng)ik表示項(xiàng)ik不在給定的事務(wù)中出現(xiàn)。例如，如果事務(wù)中不包含咖啡，則咖啡是一個值為1的負(fù)項(xiàng)。定義7.8負(fù)項(xiàng)集負(fù)項(xiàng)集X是一個具有如下性質(zhì)的項(xiàng)集：（1）X=A∪B，其中A是正項(xiàng)的集合，而B是負(fù)項(xiàng)的集合，|B|≥1;（2）s(X)≥minsup。定義7.9負(fù)關(guān)聯(lián)規(guī)則負(fù)關(guān)聯(lián)規(guī)則是一個具有如下性質(zhì)的關(guān)聯(lián)規(guī)則：（1）規(guī)則是從一個負(fù)項(xiàng)集提取的，（2）規(guī)則的支持度大于或等于minsup，（3）規(guī)則的置信度大于或等于minconf本章中，負(fù)項(xiàng)集和負(fù)關(guān)聯(lián)規(guī)則統(tǒng)稱負(fù)模式第八十一頁，共一百零一頁，2022年，8月28日負(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)的完全條件可以表述如下：第八十二頁，共一百零一頁，2022年，8月28日負(fù)相關(guān)條件也可以用正項(xiàng)集和負(fù)項(xiàng)集的支持度表示。設(shè)和分別表示X和Y的對應(yīng)負(fù)項(xiàng)集，由于負(fù)相關(guān)條件可以表述如下：負(fù)相關(guān)項(xiàng)集和負(fù)相關(guān)關(guān)聯(lián)規(guī)則統(tǒng)稱負(fù)相關(guān)模式（negativelycorrelatedpattern）第八十三頁，共一百零一頁，2022年，8月28日非頻繁模式、負(fù)模式和負(fù)相關(guān)模式比較非頻繁模式、負(fù)模式和負(fù)相關(guān)模式是三個密切相關(guān)的概念。盡管非頻繁模式和負(fù)相關(guān)模式只涉及包含正項(xiàng)的項(xiàng)集或模式，而負(fù)模式涉及包含正項(xiàng)和負(fù)項(xiàng)的項(xiàng)集或模式，但是這三個概念之間存在一定的共性，如圖7-22所示第八十四頁，共一百零一頁，2022年，8月28日第八十五頁，共一百零一頁，2022年，8月28日首先，許多非頻繁模式有對應(yīng)的負(fù)模式。如果x∪y是非頻繁的，則除非minsup太高，否則它很可能有對應(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第八十六頁，共一百零一頁，2022年，8月28日挖掘有趣的非頻繁模式的技術(shù)原則上講，非頻繁項(xiàng)集是未被標(biāo)準(zhǔn)的頻繁項(xiàng)集產(chǎn)生算法（如Apriori和FP增長）提取的所有項(xiàng)集。這些項(xiàng)集對應(yīng)于圖7-23所示的頻繁項(xiàng)集邊界之下的那些項(xiàng)集。第八十七頁，共一百零一頁，2022年，8月28日由于非頻繁模式的數(shù)量可能是指數(shù)級的，特別是對于稀疏的、高維的數(shù)據(jù)。因此，為挖掘非頻繁模式而開發(fā)的技術(shù)著力于發(fā)現(xiàn)有趣的非頻繁模式。例如：負(fù)相關(guān)模式第八十八頁，共一百零一頁，2022年，8月28日基于挖掘負(fù)模式的技術(shù)一種方法是將每個項(xiàng)看作對稱的二元變量。通過用負(fù)項(xiàng)增廣，將事務(wù)數(shù)據(jù)二元化。然后使用Apriori算法等，可以導(dǎo)出所有的負(fù)項(xiàng)集。第八十九頁，共一百零一頁，2022年，8月28日僅當(dāng)只有少