宋 華，羅興宇，劉 亮

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

0 引 言

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

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

1 微信公眾號服務網(wǎng)絡

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

圖1 微信公眾號服務網(wǎng)絡模型

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

M-M=(N,E)

(1)

式中：E表示微信公眾號網(wǎng)路中服務之間的相互關(guān)系集合，N表示網(wǎng)路內(nèi)微信公眾號所包含的服務集合。

定義2 (A-M網(wǎng))：構(gòu)建微信公眾號服務與API服務之間存在的二模關(guān)聯(lián)網(wǎng)絡，如圖1(b)所示。圓圈或方框表示的是API或者微信公眾號服務，圖中連線是網(wǎng)絡模型中API服務與微信公眾號服務之間存在的調(diào)用聯(lián)系?？煽闯鑫⑿殴娞栆话闶桥c多組API服務之間構(gòu)成關(guān)聯(lián)。

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

2 基于層次理論的模糊元關(guān)聯(lián)規(guī)則

2.1 有關(guān)定義

(2)

(3)

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

(4)

(5)

(6)

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

2.2 元規(guī)則提取

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

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

圖2 從原始數(shù)據(jù)集到最終的元關(guān)聯(lián)規(guī)則

然后，我們可以區(qū)分模糊或清晰的元關(guān)聯(lián)規(guī)則，步驟如下：

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

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

2.3 模糊層次元關(guān)聯(lián)規(guī)則融合

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

算法1： 元關(guān)聯(lián)規(guī)則

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

輸出：R1,R2,…,Rk；

(1)forallDido

(2) #Di預處理

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

(4) 將Di轉(zhuǎn)換成布爾數(shù)據(jù)庫；

(5) #關(guān)聯(lián)規(guī)則的挖掘

(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)編譯所有不同的規(guī)則R1,R2,…,Rk；

(21) #元規(guī)則挖掘

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

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

算法2： 模糊關(guān)聯(lián)規(guī)則挖掘

輸出：FR,#模糊關(guān)聯(lián)規(guī)則集

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

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

(5) #關(guān)聯(lián)規(guī)則的挖掘

(6)forallαi∈Λdo

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

(8) 讀取層級αi中所有被發(fā)現(xiàn)的規(guī)則；

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

(10)endfor

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

2.4 計算復雜度分析

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

3 實驗分析

3.1 性能測試

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

圖3 nDexample聚類效果對比

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

為了對算法分類結(jié)果進行量化對比，這里選取統(tǒng)計指標CF對規(guī)則的獲取概率進行測度，測試數(shù)據(jù)集選取matlab聚類工具箱MotorCycle數(shù)據(jù)集，統(tǒng)計指標CF具體形式為

(7)

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

圖4 盒狀圖測度對比

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

3.2 微信公眾號主題關(guān)聯(lián)規(guī)則挖掘效果

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

推薦精度對比

(8)

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

主題評價指標

(9)

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

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

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

表2 DCG均值

圖5 微信公眾號主題推薦結(jié)果對比

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

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

表3 算法計算時間對比

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

4 結(jié)束語

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