宋 華，羅興宇，劉 亮

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

0 引 言

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

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

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

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

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

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

M-M=(N,E)

(1)

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

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

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

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

2.1 有關(guān)定義

(2)

(3)

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

(4)

(5)

(6)

當(dāng)|ρA(αi)|=0時，置信度計(jì)算可能具有不確定形式0/0，這種情況是不允許存在的。因此，為了確保模糊規(guī)則的定義，對于上述不確定情形，設(shè)定其為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ī)模、復(fù)雜和異構(gòu)的微信主題數(shù)據(jù)集，這種處理方式是有效的[14,15]。

這里利用示例進(jìn)行說明，假設(shè)一個多分支機(jī)構(gòu)，例如微信主題標(biāo)簽，有許多的分支遍布網(wǎng)絡(luò)。在這種情況下，每個單獨(dú)微信分支存儲的數(shù)據(jù)將具有相似的結(jié)構(gòu)。利用元規(guī)則融合提取的知識具有一定的優(yōu)勢：①處理完整數(shù)據(jù)集是沒有必要的，這會降低算法計(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ù)庫。應(yīng)用規(guī)則提取程序，每個數(shù)據(jù)庫中可為每個Di提取一組不同的關(guān)聯(lián)規(guī)則Ri。關(guān)于發(fā)現(xiàn)的關(guān)聯(lián)規(guī)則及其評估值可表示成集合R1,R2,…,Rk，其中有很多重復(fù)規(guī)則，不失一般性，假設(shè)采取相同的閾值最小支持和確定性因子用于數(shù)據(jù)集處理。

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

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

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

(3) 讀取Di， 并存儲項(xiàng)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反復(fù)執(zhí)行步驟(2)～步驟(16)；

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

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

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

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

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

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

(6)forallαi∈Λdo

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

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

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

(10)endfor

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

2.4 計(jì)算復(fù)雜度分析

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

3 實(shí)驗(yàn)分析

3.1 性能測試

為直觀表現(xiàn)算法性能優(yōu)勢，這里利用Matlab聚類算法分析工具箱對所提關(guān)聯(lián)規(guī)則算法進(jìn)行實(shí)驗(yàn)對比，對比算法選取標(biāo)準(zhǔn)Apriori算法。硬件設(shè)置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ù)對算法聚類效果進(jìn)行評價，該評價函數(shù)采用了等值線評價方式，能夠更加直觀獲得算法聚類數(shù)據(jù)效果，如圖3所示。

圖3 nDexample聚類效果對比

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

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

(7)

式中：mValue是相應(yīng)的度量均值。圖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ī)則的冗余度較高，存在較多的重復(fù)規(guī)則和無效規(guī)則。

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

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

推薦精度對比

(8)

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

主題評價指標(biāo)

(9)

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

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

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

表2 DCG均值

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

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

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

表3 算法計(jì)算時間對比

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

4 結(jié)束語

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