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

關(guān)聯(lián)分析高級概念第1頁，共101頁，2023年，2月20日，星期三關(guān)聯(lián)分析處理事務(wù)數(shù)據(jù)RulesDiscovered:

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

{家庭計算機=是，網(wǎng)上購物=是}{關(guān)注隱私=是}解決辦法：使用處理具有寬支持度的極差數(shù)據(jù)集的技術(shù)。第7頁，共101頁，2023年，2月20日，星期三處理分類屬性將關(guān)聯(lián)分析用于二元化后的數(shù)據(jù)時，需要考慮如下問題。(3)計算時間可能增加，特別是當新創(chuàng)建的項變成頻繁項時。因為會產(chǎn)生更多的候選項集。解決辦法：避免產(chǎn)生包含多個來自同一個屬性的項的候選項集。例如：不必產(chǎn)生諸如{州=X，州=Y，…}的候選項集，因為該項集支持度為零。第8頁，共101頁，2023年，2月20日，星期三處理連續(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ù)進行關(guān)聯(lián)分析的方法:基于離散化的方法非離散化方法基于統(tǒng)計學(xué)的方法第9頁，共101頁，2023年，2月20日，星期三第10頁，共101頁，2023年，2月20日，星期三基于離散化的方法離散化是處理連續(xù)屬性最常用的方法。這種方法將連續(xù)屬性的鄰近值分組，形成有限個區(qū)間。例如：年齡屬性可以劃分為如下區(qū)間：

[12,16),[16,20),[20,24),…,[56,60)離散化技術(shù)：等寬、等頻、聚類表7-4顯示了離散化和二元化后的因特網(wǎng)調(diào)查數(shù)據(jù)。第11頁，共101頁，2023年，2月20日，星期三第12頁，共101頁，2023年，2月20日，星期三屬性離散化的一個關(guān)鍵在于劃分每個屬性的區(qū)間個數(shù)和寬度。然而，確定正確的區(qū)間是困難的。第13頁，共101頁，2023年，2月20日，星期三如果支持度閾值=5%，置信度閾值=65%。我們可以從表中推出年齡和網(wǎ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ū)間太寬，則可能因為缺乏置信度而失去某些規(guī)則例如：當區(qū)間寬度為24歲時，上面的兩個規(guī)則變?yōu)?/p>

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

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

E2E1

E3E2E3

E4E2Element(Transaction)Event

(Item)第25頁，共101頁，2023年，2月20日，星期三序列數(shù)據(jù)的例子第26頁，共101頁，2023年，2月20日，星期三子序列（

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