關聯分析高級概念第一頁，共一百零一頁，編輯于2023年，星期五關聯分析處理事務數據RulesDiscovered:

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

{家庭計算機=是，網上購物=是}{關注隱私=是}解決辦法：使用處理具有寬支持度的極差數據集的技術。第七頁，共一百零一頁，編輯于2023年，星期五處理分類屬性將關聯分析用于二元化后的數據時，需要考慮如下問題。(3)計算時間可能增加，特別是當新創建的項變成頻繁項時。因為會產生更多的候選項集。解決辦法：避免產生包含多個來自同一個屬性的項的候選項集。例如：不必產生諸如{州=X，州=Y，…}的候選項集，因為該項集支持度為零。第八頁，共一百零一頁，編輯于2023年，星期五處理連續屬性因特網調查數據可能還包含連續屬性，如表7-3所示。挖掘連續屬性可能揭示數據的內在聯系，如“年收入超過120k的用戶屬于45-60年齡組”或“擁有超過3個email帳號并且每周上網超過15小時的用戶通常關注個人隱私”:包含連續屬性的關聯規則通常稱作量化關聯規則（quantiativeassociationrule）。對連續數據進行關聯分析的方法:基于離散化的方法非離散化方法基于統計學的方法第九頁，共一百零一頁，編輯于2023年，星期五第十頁，共一百零一頁，編輯于2023年，星期五基于離散化的方法離散化是處理連續屬性最常用的方法。這種方法將連續屬性的鄰近值分組，形成有限個區間。例如：年齡屬性可以劃分為如下區間：

[12,16),[16,20),[20,24),…,[56,60)離散化技術：等寬、等頻、聚類表7-4顯示了離散化和二元化后的因特網調查數據。第十一頁，共一百零一頁，編輯于2023年，星期五第十二頁，共一百零一頁，編輯于2023年，星期五屬性離散化的一個關鍵在于劃分每個屬性的區間個數和寬度。然而，確定正確的區間是困難的。第十三頁，共一百零一頁，編輯于2023年，星期五如果支持度閾值=5%，置信度閾值=65%。我們可以從表中推出年齡和網上聊天隱含強規則：

[16,24)網上聊天=是（s=8.8%，c=81.5%）[44,60)網上聊天=否（s=16.8%，c=70%）區間寬度對關聯分析結果的影響。（1）如果區間太寬，則可能因為缺乏置信度而失去某些規則例如：當區間寬度為24歲時，上面的兩個規則變為

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

[36,60)網上聊天=否（s=28%，58.3%）第十四頁，共一百零一頁，編輯于2023年，星期五區間寬度對關聯分析結果的影響。（2）如果區間太窄，則可能因為缺乏支持度而失去某些規則例如：當區間寬度為4歲時，上面的兩個規則變為

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

[20,24)網上聊天=是（s=4.4%，78.6%）（3）當區間寬度為8歲時，上面的兩個規則變為

[44,52)網上聊天=否（s=8.4%，70%）

[52,60)網上聊天=否（s=8.4%，70%）

[12,20)網上聊天=是（s=9.2%，60.5%）

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

E2E1

E3E2E3

E4E2Element(Transaction)Event

(Item)第二十五頁，共一百零一頁，編輯于2023年，星期五序列數據的例子第二十六頁，共一百零一頁，編輯于2023年，星期五子序列（

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