微信公眾號層次模糊元關聯規則聚類預警

宋 華，羅興宇，劉 亮

(1.重慶警察學院 信息安全系， 重慶 401331； 2.重慶郵電大學 移通學院， 重慶 400065)

0 引 言

當前，隨著網絡技術的發展，網絡環境紛繁復雜，網絡輿情監測變得非常重要，是很多政府、企業和社會關注的焦點。而微信公眾號[1-3]是當前社會上適用最為廣泛的網絡工具，因此對網絡輿情進行有效的監測具有非常重要的意義。國內外在微信公眾號主題數據挖掘方面的研究成果較少，對此考慮采用關聯規則方式進行數據主題的挖掘，在關聯規則研究方面，國內外已有許多成熟研究。傳統意義的關聯規則算法可獲得一切滿足符合條件的最小置信度和支持度閾值的規則。為了獲得上述目標，有學者提出了Apriori挖掘算法[4]，其將關聯規則算法分成兩組不同的子問題進行處理：①利用置信度指標，獲得強關聯屬性的規則；②按照支持度規則算法，獲得算法的頻繁項集。但是對數據庫進行反復掃描和算法產生的大量的候選集嚴重影響算法的性能。同時，關聯規則計算過程中頻繁項集處理速度嚴重影響著算法的計算效率，因此提高Apriori算法的計算效率是當前的研究熱點。為了降低算法執行中I/O操作復雜度，在對數據庫進行一次掃描中會獲得多組大小各異的頻繁項集[5]是主要的改進措施，同時采取的措施有利用位操作實現集合操作的提速[6]；為降低算法的內存占用，一般可將數據按照垂直和水平向進行壓縮，獲得進位表處理方式[7]。此外，還有算法提出利用并行方法實現Apriori數據處理速度提升[8]，以及頻繁項集邏輯規則改進[9]等方式。

當前，對于關聯規則的研究大多集中在規則提取和數量降低上，但存在的問題主要有：①冗余規則具有過于嚴格的定義，因此規則降低能力有限；②頻繁項集所含項數過多會導致關聯規則形式過于復雜，導致信息的重復和冗余度過高，不方便使用。為此，提出一種基于層次理論的模糊元關聯規則方法，進行微信公眾號主題知識的元規則二進制融合提取，允許從單個數據庫中獲得結果/模式，減少規則挖掘過程中所需的時間。

1 微信公眾號服務網絡

在微信公眾號中標簽信息服務、網絡API以及網絡服務之間存在一定的關聯，其構建了微信公眾號網絡的運作基礎。微信公眾號網絡通常情況下可由下列4部分因素構建：①微信公眾號網絡社區劃分；②微信公眾號網絡主題標簽定義；③微信公眾號服務的數據采集；④微信公眾號網絡的主題用戶查詢，具體如圖1(a)所示。

圖1 微信公眾號服務網絡模型

定義1 (M-M網)：構建微信公眾號服務與微信公眾號服務間網絡關系，如圖1(b)所示。圖中，方框表示微信公眾號服務，服務之間的連線是指微信公眾號網絡中服務間存在的關系。那么M-M網形式為

M-M=(N,E)

(1)

式中：E表示微信公眾號網路中服務之間的相互關系集合，N表示網路內微信公眾號所包含的服務集合。

定義2 (A-M網)：構建微信公眾號服務與API服務之間存在的二模關聯網絡，如圖1(b)所示。圓圈或方框表示的是API或者微信公眾號服務，圖中連線是網絡模型中API服務與微信公眾號服務之間存在的調用聯系。可看出微信公眾號一般是與多組API服務之間構成關聯。

按照以上定義形式，微信公眾號服務推薦過程即為通過聚類策略使得相同類別的服務進行分類并向用戶進行推薦，并且希望這種服務的推薦足夠準確，可以滿足用戶對于精度和實時性的需要。

2 基于層次理論的模糊元關聯規則

2.1 有關定義

(2)

(3)

式中：必須至少有一個原像α∈Λ，通過設定Λ=1可對其進行清晰化

(4)

(5)

(6)

當|ρA(αi)|=0時，置信度計算可能具有不確定形式0/0，這種情況是不允許存在的。因此，為了確保模糊規則的定義，對于上述不確定情形，設定其為1。

2.2 元規則提取

元關聯規則的目的是從數據庫中獲得數據的位置分布或橫向分區存儲，在這兩種情況下，希望從每個主要數據集的一組關聯規則中提取可能的關聯。對于大規模、復雜和異構的微信主題數據集，這種處理方式是有效的[14,15]。

這里利用示例進行說明，假設一個多分支機構，例如微信主題標簽，有許多的分支遍布網絡。在這種情況下，每個單獨微信分支存儲的數據將具有相似的結構。利用元規則融合提取的知識具有一定的優勢：①處理完整數據集是沒有必要的，這會降低算法計算效率。②它允許從單個數據庫中獲得結果/模式，減少規則挖掘過程中所需的時間。

圖2 從原始數據集到最終的元關聯規則

然后，我們可以區分模糊或清晰的元關聯規則，步驟如下：

步驟1 令{D1,D2,…,Dk}是一組屬性共享的數據庫。應用規則提取程序，每個數據庫中可為每個Di提取一組不同的關聯規則Ri。關于發現的關聯規則及其評估值可表示成集合R1,R2,…,Rk，其中有很多重復規則，不失一般性，假設采取相同的閾值最小支持和確定性因子用于數據集處理。

表1 布爾(上)和模糊(下)元數據庫

2.3 模糊層次元關聯規則融合

元關聯規則挖掘過程如算法1所示。所謂的頻繁項集或候選集的項計算過程見算法1中第(6)～(12)行代碼所示。這些規則利用高于用戶定義的閾值進行提取，見算法(13)～(15)行代碼所示。第一步計算所需計算最為復雜，并提出了不同的啟發式策略，以減少在規則挖掘過程中花費的時間。在所提算法中，使用二進制位串對項進行表示，加快連詞的計算速度，此外使用二進制表示的內存占用不高，降低了系統的內存需求。

算法1： 元關聯規則

輸入：D2,…,Dk,at1,at2,…,atm,minsupp,minCF;

輸出：R1,R2,…,Rk；

(1)forallDido

(2) #Di預處理

(3) 讀取Di， 并存儲項I；

(4) 將Di轉換成布爾數據庫；

(5) #關聯規則的挖掘

(6)ifSupp(X)≥minsuppthen

(7)X∈C#C為候選集

(8)endif

(9)forallX,Y∈C；X∩Y=?do

(10)ifSupp(X→Y)≥minsuppthen

(11)X∧Y∈CandX→Y是頻繁的；

(12)endif

(13)ifCF(X→Y)≥minCFthen

(14)X→Y∈RiandX→Y為確定的；

(15)endif

(16)endfor

(17)endfor

(19)編譯所有不同的規則R1,R2,…,Rk；

(21) #元規則挖掘

(22)利用D反復執行步驟(2)～步驟(16)；

那么基于層次理論的元關聯規則融合算法可見算法2所示。在并行水平集上利用式(4)和式(9)的FSupp和FCF進行模糊評估。特別是在步驟(9)中，對于每個α∈Λ，可對確定性因素和清晰度支持進行獨立計算，并對式(4)和式(6)的計算結果進行權重和計算。

算法2： 模糊關聯規則挖掘

輸出：FR,#模糊關聯規則集

(2) 讀取Di， 并存儲項I；

(4) 將數據庫編碼成二進制的p向量；

(5) #關聯規則的挖掘

(6)forallαi∈Λdo

(7) 反復執行算法1的步驟(6)～步驟(16)， 在每一級獲得清晰規則集；

(8) 讀取層級αi中所有被發現的規則；

(9) 利用式(4)和式(6)計算FSupp和FCF；

(10)endfor

(11)收集滿足FSupp和FCF要求的規則；

2.4 計算復雜度分析

如前所述，關聯規則挖掘算法通常有兩個步驟。該算法的計算復雜度為O(|D|2|I|)。在我們所提方法中，因為原始Di可實現并行化處理，算法1中(1)～(17)行的第一階段，具有與標準算法相同的計算復雜度，O(|D|2|I|)，取決于每種情況下的交易數量|Di|和項的數量。算法1中(18)～(22)行的第二階段，計算復雜度與初始數據庫規模k、附加屬性的數目m、以及第一步中獲得不同規則數目相關。由此可得，其計算復雜度為O(k2m+r)，因為算法2所示計算過程對于α∈Λ是并行執行的。

3 實驗分析

3.1 性能測試

為直觀表現算法性能優勢，這里利用Matlab聚類算法分析工具箱對所提關聯規則算法進行實驗對比，對比算法選取標準Apriori算法。硬件設置CPU：i3-6500K，內存大小為8GRAM，系統為Win10旗艦版。測試集選取Matlab聚類算法分析工具箱中的nDexample數據集，人造數據集的具體參數：data.X=nDexample(5,250,2,0)，并利用工具箱中自帶的clusteval函數對算法聚類效果進行評價，該評價函數采用了等值線評價方式，能夠更加直觀獲得算法聚類數據效果，如圖3所示。

圖3 nDexample聚類效果對比

根據圖3所示本文算法與標準Apriori算法聚類效果對比情況?？煽闯鲈趎Dexample測試集上結果，圖3(b)所示的數據點中有8個數據點未被正確的進行識別，而在圖3(a)中沒有正確識別的數據點的數量比8個更少。這表明本文算法在聚類效果上要優于標準Apriori算法。

為了對算法分類結果進行量化對比，這里選取統計指標CF對規則的獲取概率進行測度，測試數據集選取matlab聚類工具箱MotorCycle數據集，統計指標CF具體形式為

(7)

式中：mValue是相應的度量均值。圖4(a)、圖4(b)分別給出本文算法和對比算法在MotorCycle數據集上的數據分類效果的盒狀圖測度。

圖4 盒狀圖測度對比

圖4(a)、圖4(b)所示結果顯示，在規則的獲取概率上，圖4(b)所示的本文算法獲得的規則可獲取概率的分布更為集中，而原始關聯規則挖掘算法的規則可獲取概率的分布更加分散，這表明本文算法獲得的規則的冗余度更低，而對比算法的規則的冗余度較高，存在較多的重復規則和無效規則。

3.2 微信公眾號主題關聯規則挖掘效果

為驗證本文所提微信公眾號主題推薦算法有效性，利用本文網扒數據獲得的微信公眾號主題數據集進行推薦效果對比，所采用的微信公眾號主題推薦算法評價指標如下[12,13]

推薦精度對比

(8)

式中：參數mispl(ci)與succ(ci)分別表示微信公眾號主題被錯誤或正確推薦到分類ci的數量。

主題評價指標

(9)

式中：reli是微信公眾號服務和主題對應等級：無關、一般、相關。

對比主題推薦策略選取文獻[14]所提的DAT-kmeans分類算法和文獻[15]所提的DTV-kmeans推薦算法。仿真結果見表2以及圖5。

表2所示為微信公眾號主題的DCG均值，根據表2結果可知，在k=2取值情況下，微信公眾號主題的DCG均值最大，這表明微信公眾號中主題數為2的對應服務數最大。

表2 DCG均值

圖5 微信公眾號主題推薦結果對比

在微信服務器上網扒獲取的7260組微信公眾號服務可分成6種類別，分別為：①地圖類微信公眾號服務；②數據傳輸類微信公眾號服務；③藝術類微信公眾號服務；④搜索類微信公眾號服務；⑤插件類微信公眾號服務；⑥網購類微信公眾號服務。圖5(a)所示為選取的對比推薦方法的微信公眾號主題推薦數量對比情況，圖5(b)所示為選取的對比推薦方法的微信公眾號主題推薦精度對比情況，圖5(a)結果也顯示主題數為2的對應服務數最大。圖5(b)顯示本文算法在第1、第2、第3和第6類微信公眾號主題服務上的推薦精度相對于選取的推薦策略精度更高。本文策略在第4類微信公眾號主題的推薦精度要比DAT-kmeans略低，但是仍然高于DTV-kmeans微信公眾號主題的推薦精度，而算法在第5類主題的推薦精度比DTV-kmeans主題推薦精度略低，比DAT-kmeans主題推薦精度高，總體上本文算法要優于選取的對比策略。

為了對比算法在計算復雜度上的性能對比，這里仍然選擇DAT-kmeans和DTV-kmeans兩種算法作為對比，多3種算法的計算時間進行對比，結果見表3。

表3 算法計算時間對比

根據表3實驗結果可知，在選取的對比算法中，本文算法的計算時間為9.5 s，DAT-kmeans和DTV-kmeans兩種算法的計算時間分別為21.3 s和15.6 s，本文算法相對于上述兩種算法的計算效率分別提升39.1%和55.4%，體現了較高的算法計算效率。

4 結束語

本文提出一種微信公眾號主題層次模糊元關聯規則聚類預警方法，對于微信公眾號的網絡主題模型進行研究，獲得其服務本體和AM、MM模型定義，利用每個單獨微信分支存儲的數據所具有的相似結構，進行微信公眾號主題知識的元規則二進制融合提取，無需對整個數據集進行處理，減少規則挖掘過程中所需的時間。下一步研究方向：①算法應用系統開發；②建立更大規模數據庫對算法進行驗證；③考慮利用中文算法直接進行關聯規則構建。