基於概率圖模型的頻繁模式關聯分類方法
2023-09-18 15:40:00 2
專利名稱：基於概率圖模型的頻繁模式關聯分類方法
技術領域：
本發明公開了一種基於概率圖模型(Probabilistic Graphical Model)的頻繁模式關聯分類方法，涉及一種基於概率圖模型的頻繁模式之間相互關係的表示、並在不同抽象層次上進行關聯分類的方法。屬於數據挖掘及信息處理技術領域。
背景技術：
實際中的數據對象，除了本身的屬性外，對象的行為、以及由於行為而產生的相互關係，也是對其進行分類的重要依據。利用頻繁模式挖掘算法得到頻繁出現在數據集中的模式，利用關聯規則表達頻繁模式之間的相互關係，經典分類算法以對象本身的屬性為基礎、未考慮由於對象之間行為而產生的相互關係，為此，將表示對象間相互關係的關聯規則用於數據的分類中，公知的關聯分類方法基於關聯規則進行數據對象的分類分析。董傑 (大連理工大學博士論文，2009)提出了一種基於位表的關聯規則挖掘及關聯分類算法；陳國青等(〈信息資源管理學報〉，2011(2))介紹了基於信息熵的關聯分類方法；霍緯綱等(〈 計算機研究與發展〉，2011，48(4) =567-575)提出了一種基於多目標進化算法的模糊關聯分類方法。作為關聯分類的基礎性技術手段，頻繁模式的關聯規則表示方法不能從全局的角度有效表達頻繁模式間較複雜的相互關係，不能描述所涉及頻繁模式的全局概率分布及相互關係的不確定性，為此，公知的方法利用圖模型擴展頻繁模式和關聯規則的挖掘算法。耿汝年等(〈計算機集成製造系統〉，2008，14 (6) =1220-1229)提出了一種基於全局圖遍歷的頻繁模式挖掘算法；陳文等(〈計算機工程〉，2010，36 (13) 9-6)提出了一種基於關聯圖的加權關聯規則模型，並利用關聯圖存儲頻繁模式集；胡春玲等(〈軟體學報〉，2011，22 (12) 2934-2950)提出了一種基於貝葉斯網這一概率圖模型的頻繁模式興趣度計算和剪枝策略， 並有效利用貝葉斯網的推理算法來計算關聯規則的支持度。相對公知的頻繁模式表示方法，基於概率圖模型可以表示頻繁模式之間任意形式的全局相互關係、以及相互關係的不確定性，基於概率圖模型分析頻繁模式間相互關係的緊密程度、並進行結點的合併，可以在不同抽象層次進行頻繁模式分類。以頻繁模式之間的因果關係為出發點，提出了頻繁模式的概率圖模型表示方法，建立了從頻繁模式到概率圖模型的等價轉換機制，給出了基於概率圖模型性質的頻繁模式層次聚集方法，將其用於學術論文和論文作者聯繫的自動分類的問題中，具有較高的效率和分類準確率。此方法能以一個統一的模型方便高效地實現頻繁模式之間相互依賴關係的全局表示，可滿足不同抽象層次用戶的關聯分類需求，具有較好的伸縮性，為後續研發提供理論依據和技術基礎。
發明內容
本發明提供一種基於概率圖模型的頻繁模式關聯分類方法。在Apriori頻繁模式挖掘算法的執行結果之上，提供一種基於概率圖模型的頻繁模式間相互關係的表示及頻繁模式的關聯分類方法。以馬爾可夫網(Markov network)這一重要概率圖模型作為知識表示的基本框架，建立頻繁模式與概率圖模型的內在聯繫，構建頻繁模式中蘊含的馬爾可夫網，通過結點自底向上的聚集對頻繁模式進行不同抽象層次上的關聯分類。可以從全局的角度方便高效地表示頻繁模式間任意形式的相互關係，不同抽象層次用戶的關聯分類具有較好的伸縮性，為後續研發提供理論依據和技術基礎。本發明按以下步聚完成本發明工藝流程為首先，基於Apriori頻繁模式挖掘算法、設置支持度，獲得極大頻繁項目集；接著，對每個極大頻繁項目集分別構建初始無向圖，並根據它們之間的公共項目集進行初始無向圖的合併，進而測試圖中結點之間的條件獨立性，刪除條件獨立的邊， 得到頻繁項目集中蘊含的馬爾可夫網；然後，對得到的馬爾可夫網進行弦化處理，將弦化的馬爾可夫網表示為連接樹，以一個弦化子圖作為連接樹的一個頂點，從而得到頻繁模式的初始分類；進一步以自底向上的方式，對連接樹的頂點進行聚集合併，得到反映更高抽象層次的分類，直到滿足用戶需求為止。(I)獲得頻繁模式基於Apriori頻繁模式挖掘算法，並設置支持度閾值，得到 I-頻繁項集，2-頻繁項集，……，直到不能得到更大的頻繁項集為止，從而獲得極大頻繁項集。基於Apriori頻繁模式挖掘算法,針對項集I = U1,…，in},設置支持度閾值ε (O < ε < I)，若I的子集X滿足概率P(X)彡ε，則X為頻繁項集。首先得到含有I個項的 I-頻繁項目集，再得到含有2個項的2-頻繁項目集，……，依次執行，直到不能得到更大的頻繁項集為止。從而獲得極大頻繁項目集；(2)構建頻繁模式中蘊含的馬爾可夫網針對每個極大頻繁項目集，首先構建以其中各頻繁項目作為結點的全連通無向圖，再將各極大頻繁項目集所對應的完全子圖進行合併，然後根據頻繁項目之間是否條件獨立來確定邊的刪除與保留，從而得到反應頻繁項目之間全局相互關聯的馬爾可夫網。①對每個極大頻繁項目集分別構建無向圖對極大頻繁項集Ai,以其中的項作為圖的結點，用無向邊連接Ai中任意兩個不同的項，得到Ai對應的全連通無向圖G(Ai),如圖
2、圖3和圖4所示；②合併所有頻繁項集對應的無向圖對於存在公共項的任意兩個Ai和Ap將Ai中的每個項與 中的其他項用無向邊相連，從而將每個極大頻繁項集對應的無向圖進行合併，得到全局無向圖G，如圖5所示；③刪去條件獨立結點對應的邊，得到馬爾可夫網用 表示「 α 與 β 條件獨立於 Ζ」，若 P ( α，Ζ，β) =Ρλ (α，Ζ) ·Ρ λ (β，
ο P(X) < λ
Ζ)/Ρλ⑵，其中= j, X為頻繁項集，λ為給定的概率閾值。
L屍(Ji ) γ(Λ ) > Λ若X為極大頻繁項集，α，β e X，有〈α I χ- α - β I β >總成立。對於所有頻繁項集對應的無向圖，考查G(Ai)中的任意無向邊(ail; aik),若〈ajAi-aifaiklaik〉成立(即an 與aik條件獨立於G(Ai)中其他結點)，則從G中刪除邊(ail; aik);若an和aik又是Aj中的頻繁項且〈a^Ai-aifaiklaik〉成立(即an與aik條件獨立於G (Aj)中其他結點)，則也從G 中刪除邊(ail; aik)。從而建立了頻繁模式與條件獨立性之間的關係，得到了表示頻繁項之間相互依賴關係的無向圖結構，該圖結構滿足概率圖模型的必要條件、為有效的頻繁項馬爾可夫網，將其稱為項關聯馬爾可夫網(Item Association Markov Network),如圖6所不。(3)頻繁模式的層次聚集根據弦化的定義，(一個無向圖稱為弦圖，當圖中任一長度大於3的環都至少有一個弦)，將構建的馬爾可夫網弦化處理，同時建立馬爾可夫網中各結點極大完全子圖的無環序，進而得到以極大完全子圖為結點的聯接樹，根據聯接樹中極大完全子圖的無環序進行聯接樹中結點的聚集合併，自底向上的方式重複此過程，直到滿足用戶所需抽象程度為止。①用弦化(Chordal)作為頻繁項聯繫緊密的衡量標準，得到弦化的項關聯馬爾可夫網及弦化子圖的序基於無向圖弦化的概念，對每個長度不少於4的環都進行弦化(即三角化，使得每個環的長度不大於3)，每個長度不超過3的環中的結點構成一個弦化子圖Xi，每個弦化子圖包含聯繫緊密的頻繁項且對應一個初始的類，如圖7所示；進一步基於以下標準得到弦化子圖的序(Xl，…，xm)，為得到更高抽象層次的類奠定基礎
其中 I 彡 j 彡 i ;②將弦化無向圖表示為連接樹(Join Tree):弦化的馬爾可夫網可以用樹結構來描述，稱為連接樹；而連接樹本身是弦化的，包括了聯繫緊密的頻繁項。將弦化子圖作為頂點，若Ci與有公共頻繁項，則Ci與之間有一條無向邊，得到連接樹Τ，如圖8所示；③連接樹結點聚集合併，實現不同抽象層次的頻繁模式關聯分類按照弦化子圖的序，將連接樹T中各無向邊末端的頂點與頭端結點合併，得到新的連接樹Τ,，其中每個結點對應更高抽象層次的一個類，如圖9和圖10所示。以自底向上的方式重複此過程，得到越來越大的類，直到滿足用戶所需抽象程度為止。與公知技術相比本發明具有的優點及積極效果(I)通過構建概率圖模型，以一個統一的模型、從全局的角度描述了頻繁模式之間的相互關係，是頻繁模式及關聯規則挖掘方法的擴展，更容易地實現了頻繁模式間任意形式相互關係的建模，彌補了基於關聯規則的頻繁模式間相互關係表示機制的不足。(2)以頻繁模式間的因果關係為出發點，建立了從頻繁模式到概率圖模型的等價轉換機制、頻繁模式聯合概率分布的表示機制，定量地反映了頻繁模式間相互依賴的不確定性。(3)基於概率圖模型的結點聚集來實現關聯分類，避免了基於關聯規則進行關聯分類時由於僅考慮局部相關性帶來的分類或聚類結果的片面性和不準確性，提高了關聯分類的易實現性和結果的正確性；實現了頻繁模式不同抽象層次的關聯分類，具有更好的可伸縮性，能滿足用戶的不同需求。(4)成熟的概率圖模型推理方法可為關聯分類提供定量的分析和計算的支撐技術，為解決自動關聯分類及基於關聯分類的社會計算等目前亟待解決的熱點問題提供了有力的技術支持。
四
圖I本發明的技術路線圖。包括以下三個主要部分獲得頻繁模式(預處理)、構建概率圖模型和層次關聯分類；圖2、圖3和圖4分別為三個頻繁項目集對應的初始無向圖圖2全連通無向子圖①。結點為極大頻繁項集(Α，B, C)中的頻繁項；
圖3全連通無向子圖②。結點為極大頻繁項集(C，D)中的頻繁項；圖4全連通無向子圖③。結點為極大頻繁項集(D，E，F)中的頻繁項；圖5所有頻繁項的無向圖。合併圖2、圖3和圖4得到圖5，結點為所有頻繁項集 U = (A，B, C，D，E，F)中的頻繁項，合併全連通無向子圖時添加的邊用雙線表示；圖6關鍵詞頻繁項目集U的項關聯馬爾可夫網。對圖5進行條件獨立測試後得到；圖7弦化的項關聯馬爾可夫網G。對圖6進行弦化處理得到，其中X1 =「頻繁項」， x2 = 「Apriori」，X3 = 「剪枝」，X4 = 「分類」，X5 = 「貝葉斯網」，X6 = 「團樹」;圖8弦化的項關聯馬爾可夫網G的連接樹1\。其中C1 = (x1；x2,X3)代表「關聯規則」，C2 = (x2, x3, x5)代表「圖模型挖掘」，C3 = (x2, X4)代表「分類分析」，C4 = (x5, x6)代表「概率圖模型」；圖9新的連接樹圖T2。對圖8中T1的頂點聚集合併得到，其中CflC1, C2)代表「關
聯規則挖掘」，C21HC2, C4)代表「不確定性知識發現」，C3tHCu C3)代表「關聯分類」；圖10新的連接樹T3和最高抽象層次的連接樹Τ4。分別對T2和T3的頂點聚集合
並得到，其中cYUc/, 代表「人工智慧」，fV=(r/,c/)代表「數據挖掘」；C24) 表示「數據與知識工程」。
五具體實施例方式實施例I :學術論文關鍵詞關聯分類(I)項目集從發表的學術論文中抽取關鍵詞(Keywords)並對各詞出現的頻繁度分別進行統計，若兩個關鍵詞出現在同一篇論文中，則表示兩個關鍵字同時出現的支持度計算加I ;(2)極大頻繁項目集設置最小支持度閾值，使用Apriori算法，掃描關鍵詞並計數，得到I-頻繁項目集的集合，進一步得到2-頻繁項目集的集合，……，不斷執行直到不能再找到k-頻繁項目集為止；(3)針對每個關鍵詞極大頻繁項目集，首先構建以其中各頻繁項目作為結點的全連通無向圖，然後根據頻繁項之間是否條件獨立來確定邊的刪除與保留，從而得到各極大頻繁項目集的子圖，再將各極大頻繁項目集所對應子圖進行合併，得到反映頻繁項目之間全局相互關係的馬爾可夫網，U= (A，B，C，D，E，F)為關鍵詞的I-頻繁項目集，首先得到分別如圖2、圖3和圖4所示的3個全連通無向子圖，再根據各子圖的公共結點將這3個子圖合併，得到對應於U中所有頻繁項的無向圖，如圖5所示，對關鍵詞頻繁項目進行條件獨立測試，若條件獨立，則刪去相應的邊，(A，E)、(A，F)、(B，E)和(B，F)這4對結點間的邊不存在，對於圖5中的無向圖，(即E和F條件獨立於C和D)，則刪去E和F之間的邊，得到關鍵詞頻繁項目集U的項關聯馬爾可夫網，如圖6所示；(4)若弦化的項關聯馬爾可夫網如圖7所示，按照弦化子圖的序(C1, C2，C3，C4)，得到連接樹T1，如圖8所示，圖8中連接樹頂點極大完全子圖的無環序為(C/，c2'，C3,)， 則對T1中的頂點進行聚集合併，得到新的、描述更高抽象層次關鍵詞頻繁項目分類的連接樹1~2，如圖9所示。對T2中的頂點進行聚集合併，得到新的連接樹T3，進而得到C1"，=(C1"，C2")，即得到最高抽象層次類的連接樹T4，如圖10所示。性能選擇ScienceDirect資料庫中5個「主題(Subject) 」中的學術論文400 篇，選取其中的1500個關鍵詞，記錄這些論文的主題及其下的子主題信息，執行以上步驟
(1) (4)，從1000個頻繁項構建項關聯馬爾可夫網只需15毫秒，獲得論文所述子主題和上一級主題分類信息，在這兩個分類的抽象層次分別與論文本身所述類相比，本研究所得結果的誤差分別為2. 5%和I. 2%。
權利要求
1.一種基於概率圖模型的頻繁模式關聯分類方法，其特徵在於其按以下步驟完成，(1)獲得頻繁模式基於Apriori頻繁模式挖掘算法，並設置支持度閾值，得到1_頻繁項集，2-頻繁項集，……，直到不能得到更大的頻繁項集為止，從而獲得極大頻繁項集；(2)構建頻繁模式中蘊含的馬爾可夫網針對每個極大頻繁項目集，首先構建以其中各頻繁項目作為結點的全連通無向圖，再將各極大頻繁項目集所對應的完全子圖進行合併，然後根據頻繁項目之間是否條件獨立來確定邊的刪除與保留，從而得到反應頻繁項目之間全局相互關聯的馬爾可夫網；(3)頻繁模式的層次聚集根據弦化的定義，將構建的馬爾可夫網弦化處理，同時建立馬爾可夫網中各結點極大完全子圖的無環序，進而得到以極大完全子圖為結點的聯接樹， 根據聯接樹中極大完全子圖的無環序進行聯接樹中結點的聚集合併，自底向上的方式重複此過程，直到滿足用戶所需抽象程度為止。
2.根據權利要求I所述的基於概率圖模型的頻繁模式關聯分類方法，其特徵在於一種學術論文關鍵詞關聯分類法按以下步驟完成，(1)項目集從發表的學術論文中抽取關鍵詞(Keywords)並對各詞出現的頻繁度分別進行統計，若兩個關鍵詞出現在同一篇論文中，則表示兩個關鍵字同時出現的支持度計算加I ;(2)極大頻繁項目集設置最小支持度閾值，使用Apriori算法，掃描關鍵詞並計數，得到I-頻繁項目集的集合，進一步得到2-頻繁項目集的集合，……，不斷執行直到不能再找到k-頻繁項目集為止；(3)針對每個關鍵詞極大頻繁項目集，首先構建以其中各頻繁項目作為結點的全連通無向圖，然後根據頻繁項之間是否條件獨立來確定邊的刪除與保留，從而得到各極大頻繁項目集的子圖，再將各極大頻繁項目集所對應子圖進行合併，得到反映頻繁項目之間全局相互關係的馬爾可夫網，U = A，B, C，D，E，F為關鍵詞的I-頻繁項目集，首先得到3個全連通無向子圖，再根據各子圖的公共結點將這3個子圖合併，得到對應於U中所有頻繁項的無向圖，對關鍵詞頻繁項目進行條件獨立測試，若條件獨立，則刪去相應的邊，(A，E)、(A，F)、 (B，E)和(B，F)這4對結點間的邊不存在，對於圖5中的無向圖，，則刪去E和F 之間的邊，得到關鍵詞頻繁項目集U的項關聯馬爾可夫網；(4)按照弦化子圖的序C1,C2, C3, C4，得到連接樹T1，圖8中連接樹頂點極大完全子圖的無環序為C/, C21, Cl則對T1中的頂點進行聚集合併，得到新的、描述更高抽象層次關鍵詞頻繁項目分類的連接樹T2，對T2中的頂點進行聚集合併，得到新的連接樹T3，進而得到 C1" ' =C1" ,C2"，即得到最高抽象層次類的連接樹T4。
全文摘要
本發明涉及一種基於概率圖模型的頻繁模式關聯分類方法。在Apriori頻繁模式挖掘算法的執行結果之上，提供一種基於概率圖模型的頻繁模式間相互關係的表示及頻繁模式的關聯分類方法。以馬爾可夫網這一重要概率圖模型作為知識表示的基本框架，建立頻繁模式與概率圖模型的內在聯繫，構建頻繁模式中蘊含的馬爾可夫網，通過結點自底向上的聚集對頻繁模式進行不同抽象層次上的關聯分類，可以從全局的角度方便高效地表示頻繁模式間任意形式的相互關係，不同抽象層次用戶的關聯分類具有較好的伸縮性，為後續研發提供理論依據和技術基礎。
文檔編號G06F17/30GK102609528SQ20121003166
公開日2012年7月25日 申請日期2012年2月14日 優先權日2012年2月14日
發明者劉惟一, 嶽昆 申請人:雲南大學