周志洪，馬 進(jìn)，夏正敏，陳秀真

(1.上海交通大學(xué)網(wǎng)絡(luò)安全技術(shù)研究院，上海 200240；2.上海市信息安全綜合管理技術(shù)研究重點(diǎn)實(shí)驗(yàn)室，上海 200240)

1 引言

高頻數(shù)據(jù)就是大數(shù)據(jù)的簡化形式。在高頻數(shù)據(jù)集內(nèi)存在大量雜亂無章的信息，也存在一些具有規(guī)律的信息，準(zhǔn)確存儲(chǔ)與分析這些高頻數(shù)據(jù)可促進(jìn)經(jīng)濟(jì)發(fā)展[1-3]。

離群點(diǎn)檢測屬于數(shù)據(jù)挖掘的主要方法，離群點(diǎn)檢測負(fù)責(zé)分析目標(biāo)數(shù)據(jù)集，主要找到數(shù)據(jù)集內(nèi)異常數(shù)據(jù)或具有特征的數(shù)據(jù)信息[4]。葉福蘭研究基于離群點(diǎn)檢測的不確定數(shù)據(jù)流聚類算法，提升聚類算法的伸縮性[5]；趙建龍等研究一種基于仿射傳播的增強(qiáng)型流聚類算法，提升聚類效率[6]。

通過對高頻數(shù)據(jù)研究發(fā)現(xiàn)，當(dāng)高頻數(shù)據(jù)中存在相同或類似數(shù)據(jù)信息時(shí)，通常存在很多和數(shù)據(jù)信息有關(guān)的數(shù)據(jù)標(biāo)簽同時(shí)出現(xiàn)，且出現(xiàn)概率較高，這些數(shù)據(jù)標(biāo)簽即為高頻數(shù)據(jù)共現(xiàn)。針對高頻數(shù)據(jù)共現(xiàn)，研究基于局部離群點(diǎn)檢測的高頻數(shù)據(jù)共現(xiàn)聚類算法，提升高頻數(shù)據(jù)聚類的執(zhí)行效率與準(zhǔn)確性。

2 基于局部離群點(diǎn)檢測的高頻數(shù)據(jù)共現(xiàn)聚類算法

2.1 局部離群點(diǎn)檢測算法

2.1.1 相關(guān)定義

局部離群檢測算法是利用一種模糊方式判斷高頻數(shù)據(jù)集中是否存在異常高頻數(shù)據(jù)對象，并對其實(shí)施挖掘[7]。

定義1：對象x的k距離。在高頻數(shù)據(jù)集D內(nèi)的任意一個(gè)正整數(shù)k，對象x的k距離由k-distance(x)代表，對象x與對象o(o∈D)間的距離由e(x，o)代表。若k-distance(x)=e(x，o)，那么需要符合的條件如下：

1)最少存在k個(gè)對象o′∈D/{x}，該對象到對象x的距離e(x，o′)≤e(x，o)；

2)最多存在k-1個(gè)對象o′∈D/{x}，該對象到對象x的距離e(x，o′)

定義2：對象x的k-distance(x)鄰域。對象x的k-distance(x)是已知的，高頻數(shù)據(jù)集D內(nèi)的對象y與對象x間的距離小于k-distance(x)的全部對象集合，公式如下

Ndistan ce(x)(x)

={y∈D/{x}|e(x，y)≤k-distance(x)}

(1)

定義3：對象x與對象o間的可達(dá)距離。假設(shè)k屬于一個(gè)自然數(shù)，定義對象x與對象o間的可達(dá)距離公式如下

reach-distk(x，o)

=max{k-distance(o)，e(x，o)}

(2)

根據(jù)可達(dá)距離定義可知，若x偏離o，那么x與o間的可達(dá)距離和x與o間的實(shí)際距離一致；若x與o非常接近，那么x與o間的可達(dá)距離和o的k-distance(o)一致。

定義4：對象x的局部可達(dá)密度。定義對象x的局部可達(dá)密度公式如下

(3)

式中，高頻數(shù)據(jù)集內(nèi)高頻數(shù)據(jù)對象的總數(shù)是N。根據(jù)式(3)可知，x的MinPts個(gè)最近鄰居的平均可達(dá)距離的倒數(shù)是x的局部可達(dá)密度。

定義5：對象x的局部離群因子。定義對象x的局部離群因子公式如下

(4)

x的離群程度由x的局部離群因子表示。按照式(4)可知，x越偏離MinPts個(gè)鄰居以及離群因子越大，那么x的局部可達(dá)密度越小以及MinPts個(gè)最近鄰居的局部可達(dá)密度越大。

局部離群檢測算法的輸入的是高頻數(shù)據(jù)集D與離群點(diǎn)數(shù)目n；輸出的是指定的N個(gè)離群點(diǎn)集合。具體執(zhí)行步驟如下：

步驟1：利用上述公式分別計(jì)算已給的高頻數(shù)據(jù)集內(nèi)的隨機(jī)記錄x的局部離群因子值；

2.1.2 基于可變網(wǎng)格劃分的局部離群點(diǎn)檢測算法

在局部離群點(diǎn)檢測算法中引入可變網(wǎng)格劃分，通過劃分網(wǎng)格空間確定聚類區(qū)域，不需浪費(fèi)時(shí)間搜索聚類區(qū)域，提升局部離群點(diǎn)檢測算法的執(zhí)行效率[8]。可變網(wǎng)格劃分方法首先等間距劃分高頻數(shù)據(jù)空間的各維度，再合并與該維相似的區(qū)間段，最后形成網(wǎng)格空間。

步驟2：獲取相鄰區(qū)間段的相似性。等間距劃分各維度后，兩個(gè)相鄰區(qū)間段的相似性εr由這兩個(gè)相鄰區(qū)間段的全部高頻數(shù)據(jù)點(diǎn)數(shù)量比值代表，其中r=(1，2，…，k-1)。兩個(gè)相鄰區(qū)間段的相似性εr計(jì)算公式如下：

(5)

步驟3：按照順序?qū)Ρ鹊趇維內(nèi)相鄰區(qū)間段的相似性εr。若閾值Ti(0≤Ti≤1)小于εr，那么代表這兩個(gè)相鄰區(qū)間段屬于相似的；若閾值Ti(0≤Ti≤1)大于εr，那么代表這兩個(gè)相鄰區(qū)間段屬于不相似的；完成對比后，合并相似的區(qū)間段。

步驟4：從步驟1到步驟3循環(huán)計(jì)算高頻數(shù)據(jù)集各維的相似區(qū)間段，并合并相似區(qū)間段，輸出網(wǎng)格空間。

2.1.3 設(shè)置參數(shù)

在構(gòu)建網(wǎng)格空間過程中，各維度等間隔劃分的區(qū)間段數(shù)量是k。假設(shè)d維度中存在N個(gè)高頻數(shù)據(jù)對象的高頻數(shù)據(jù)集，按照式(6)設(shè)置參數(shù)k，可防止網(wǎng)格數(shù)量跟隨維度與網(wǎng)格劃分粒度出現(xiàn)提升的情況，參數(shù)k設(shè)置公式如下

(6)

針對任意維度，其維度上需合并的區(qū)間段數(shù)量由Ti值確定。若采用一個(gè)固定的相似性閾值實(shí)施合并操作，便不能準(zhǔn)確描繪高頻數(shù)據(jù)集在空間的分布情況[9]。因此，對于第i維，需按照高頻數(shù)據(jù)的實(shí)際分布狀況決定Ti的取值，參數(shù)Ti的取值公式如下

(7)

根據(jù)式(7)可知，通過任意維度的全部相鄰區(qū)間段相似性的平均值獲取Ti，利用式(7)設(shè)置相似性閾值，提升合并區(qū)間段的合理性。

2.1.4 算法執(zhí)行步驟

基于可變網(wǎng)格劃分的局部離群檢測算法輸入的是目標(biāo)高頻數(shù)據(jù)集D、密度閾值MinP與離群點(diǎn)數(shù)量n；輸出的是前n個(gè)比較大的離群因子值對象。具體執(zhí)行步驟如下：

2.2 高頻數(shù)據(jù)共現(xiàn)聚類算法

在實(shí)施局部離群點(diǎn)檢測后的高頻數(shù)據(jù)集中，經(jīng)常出現(xiàn)不一樣的數(shù)據(jù)標(biāo)簽記錄同一個(gè)數(shù)據(jù)集的現(xiàn)象[11]。如果數(shù)據(jù)標(biāo)簽t1與數(shù)據(jù)標(biāo)簽t2記錄同一個(gè)數(shù)據(jù)集，那么這種情況叫作t1與t2共現(xiàn)。若兩個(gè)數(shù)據(jù)標(biāo)簽經(jīng)常記錄同一個(gè)數(shù)據(jù)集，則這兩個(gè)數(shù)據(jù)標(biāo)簽可能存在相似的語義。利用兩個(gè)數(shù)據(jù)標(biāo)簽一起標(biāo)記同一個(gè)數(shù)據(jù)集的次數(shù)表示這兩個(gè)數(shù)據(jù)標(biāo)簽間的相似度。兩個(gè)數(shù)據(jù)標(biāo)簽記錄同一個(gè)數(shù)據(jù)集次數(shù)與這兩個(gè)數(shù)據(jù)標(biāo)簽的相似度成正比。

數(shù)據(jù)標(biāo)簽ta與數(shù)據(jù)標(biāo)簽tb的相似度計(jì)算公式如下

sim(ta，tb)=

(8)

式中，數(shù)據(jù)標(biāo)簽ta與數(shù)據(jù)標(biāo)簽tb的相似度是sim(ta，tb)；數(shù)據(jù)標(biāo)簽ta記錄數(shù)據(jù)集ww的次數(shù)是fw，a；通過式(8)能夠計(jì)算s個(gè)數(shù)據(jù)標(biāo)簽兩兩間的相似度，便能獲取數(shù)據(jù)標(biāo)簽相似度矩陣Ts×s，Ts×s矩陣內(nèi)元素的值就是式(8)內(nèi)的sim(ta，tb)。

數(shù)據(jù)標(biāo)簽ta和通過s個(gè)數(shù)據(jù)標(biāo)簽聚類成的類cs的相似度計(jì)算公式如下

(9)

通過式(9)能夠獲取數(shù)據(jù)標(biāo)簽和類間的相似度，然后獲取數(shù)據(jù)標(biāo)簽和類的相似度矩陣H1，H1矩陣內(nèi)的元素就是式(9)內(nèi)的sim(ta，cs)。

通過v個(gè)數(shù)據(jù)標(biāo)簽聚類形成的類cv與通過s個(gè)數(shù)據(jù)標(biāo)簽聚類形成的類cs的相似度計(jì)算公式如下

(10)

通過式(10)能夠獲取類和類間的相似度，然后獲取類和類的相似度矩陣H2，矩陣內(nèi)的元素就是式(10)內(nèi)的sim(cv，cs)。

高頻數(shù)據(jù)共現(xiàn)聚類算法的基本思想是：對高頻數(shù)據(jù)集D實(shí)施局部離群點(diǎn)檢測挖掘高頻數(shù)據(jù)對象，計(jì)算挖掘后高頻數(shù)據(jù)對象內(nèi)數(shù)據(jù)標(biāo)簽t間的高頻數(shù)據(jù)共現(xiàn)相似度sim(ta，cs)，再結(jié)合層次聚類算法完成高頻數(shù)據(jù)共現(xiàn)聚類。

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

為驗(yàn)證本文算法實(shí)施高頻數(shù)據(jù)共現(xiàn)聚類的執(zhí)行效率與準(zhǔn)確性，以某大學(xué)的高頻數(shù)據(jù)集為實(shí)驗(yàn)對象，從中選取6組高頻數(shù)據(jù)集，共分為人工數(shù)據(jù)集與UCI(University of Californialrvine，標(biāo)準(zhǔn)測試數(shù)據(jù)集)數(shù)據(jù)集兩種類型，其中數(shù)據(jù)集1-3屬于人工數(shù)據(jù)集，數(shù)據(jù)集4-6屬于UCI標(biāo)準(zhǔn)數(shù)據(jù)集。通過Matlab工具箱內(nèi)自帶的函數(shù)生成人工數(shù)據(jù)集；在http:∥archive.ics.uci.edu/ml/內(nèi)獲取UCI標(biāo)準(zhǔn)數(shù)據(jù)集。6組數(shù)據(jù)集的具體信息如表1所示。

表1 6組數(shù)據(jù)集的信息

3.1 離群點(diǎn)檢測性能分析

利用本文算法與文獻(xiàn)[5]算法、文獻(xiàn)[6]算法檢測6組數(shù)據(jù)集中離群點(diǎn)數(shù)量，文獻(xiàn)[5]算法是基于離群點(diǎn)檢測的不確定數(shù)據(jù)流聚類算法研究，文獻(xiàn)[6]算法是一種基于仿射傳播的增強(qiáng)型流聚類算法。三種算法的離群點(diǎn)數(shù)量檢測結(jié)果如表2所示。

表2 三種算法的離群點(diǎn)數(shù)量檢測結(jié)果

根據(jù)表2可知，在不同數(shù)據(jù)集中，本文算法對6組數(shù)據(jù)集離群點(diǎn)檢測的數(shù)量和實(shí)際數(shù)量最大差值是2，其余兩種算法檢測的離群點(diǎn)數(shù)量與實(shí)際數(shù)量差距較大。實(shí)驗(yàn)證明：本文算法檢測離群點(diǎn)數(shù)量的準(zhǔn)確性更高。

3.2 聚類的執(zhí)行效率分析

利用本文算法與文獻(xiàn)[5]算法、文獻(xiàn)[6]算法對6組數(shù)據(jù)集實(shí)施高頻數(shù)據(jù)共現(xiàn)聚類，三種算法分別用a、b、c表示，三種算法分別實(shí)施3次實(shí)驗(yàn)，避免隨機(jī)初始化導(dǎo)致的誤差，執(zhí)行時(shí)間測試結(jié)果如表3所示。

表3 三種算法高頻數(shù)據(jù)共現(xiàn)聚類處理的執(zhí)行時(shí)間

根據(jù)表3可知，本文算法與文獻(xiàn)[5]算法、文獻(xiàn)[6]算法相比，本文算法對6組數(shù)據(jù)集實(shí)施3次高頻數(shù)據(jù)共現(xiàn)聚類處理的執(zhí)行時(shí)間均高于其余兩種算法，原因是本文算法加入可變網(wǎng)格劃分方法可對原始數(shù)據(jù)集實(shí)施一定程度上的約簡，提升高頻數(shù)據(jù)共現(xiàn)聚類處理的執(zhí)行效率。實(shí)驗(yàn)證明：本文算法高頻數(shù)據(jù)共現(xiàn)聚類的執(zhí)行效率更快。

3.3 聚類的準(zhǔn)確性分析

利用F-measure評價(jià)高頻數(shù)據(jù)共現(xiàn)聚類的準(zhǔn)確性，F(xiàn)-measure綜合了準(zhǔn)確率P與召回率R。F-measure的計(jì)算公式如下

(11)

其中，高頻數(shù)據(jù)共現(xiàn)聚類是c，類標(biāo)記是u。

高頻數(shù)據(jù)共現(xiàn)聚類的總體評價(jià)指標(biāo)F-measure通過加權(quán)求和所有聚類結(jié)果得到，F(xiàn)-measure值與高頻數(shù)據(jù)共現(xiàn)聚類效果成正比，即F-measure值越高，聚類準(zhǔn)確性越高，L為矩陣行數(shù)，計(jì)算公式如下

(12)

利用本文算法與與文獻(xiàn)[5]算法、文獻(xiàn)[6]算法對6組高頻數(shù)據(jù)集實(shí)施高頻數(shù)據(jù)共現(xiàn)聚類，三種算法分別實(shí)施3次實(shí)驗(yàn)，避免隨機(jī)初始化導(dǎo)致的誤差，三種算法實(shí)施高頻數(shù)據(jù)共現(xiàn)聚類的F-measure值測試結(jié)果如表4所示。

表4 三種算法F-measure值測試結(jié)果

根據(jù)表4可知，對于6組不同數(shù)據(jù)集本文算法實(shí)施高頻數(shù)據(jù)共現(xiàn)聚類的準(zhǔn)確性明顯高于其余兩種算法。實(shí)驗(yàn)證明：本文算法的高頻數(shù)據(jù)共現(xiàn)聚類效果更好。

3.4 在不同k值作用下的聚類精度與執(zhí)行效率分析

為進(jìn)一步驗(yàn)證本文算法的準(zhǔn)確性，以數(shù)據(jù)集1為例，測試本文算法與文獻(xiàn)[5]算法、文獻(xiàn)[6]算法在不同k值與top-n作用下高頻數(shù)據(jù)共現(xiàn)聚類的聚類精度(聚類精度=聚類到的高頻數(shù)據(jù)共現(xiàn)數(shù)量/全部高頻數(shù)據(jù)共現(xiàn)數(shù)量)。三種方法在不同k值作用下高頻數(shù)據(jù)共現(xiàn)聚類的聚類精度與執(zhí)行時(shí)間分別如圖1與表5所示。

圖1 在不同k值作用下三種方法的聚類精度

根據(jù)圖1可知，隨著k值的不斷提升，三種算法的聚類精度均有所提高。在k值為30個(gè)時(shí)，三種算法的聚類精度均處于最高值，在k值逐漸增加時(shí)，本文算法的聚類精度明顯高于其余兩種算法，本文算法的聚類精度變化比較平穩(wěn)，在k值大于30個(gè)后，聚類精度趨于穩(wěn)定；其余兩種算法的聚類精度變化幅度較大，表示文獻(xiàn)[5]算法與文獻(xiàn)[6]算法對k值非常敏感，聚類精度受k值影響較大。表明本文算法加入的可變網(wǎng)格劃分方法可有效降低k值對聚類精度的影響，提升高頻數(shù)據(jù)共現(xiàn)聚類的準(zhǔn)確性。實(shí)驗(yàn)證明：在不同k值作用下，本文算法高頻數(shù)據(jù)共現(xiàn)聚類的準(zhǔn)確性更高。

表5 不同k值作用下三種算法的執(zhí)行時(shí)間

根據(jù)表5可知，隨著k值的逐漸增加，三種算法的執(zhí)行時(shí)間均不斷提升，本文算法的執(zhí)行時(shí)間明顯低于其余兩種算法，原因是本文算法中加入了可變網(wǎng)格劃分方法，能夠降低時(shí)間復(fù)雜度，提升高頻數(shù)據(jù)共現(xiàn)聚類的執(zhí)行效率。實(shí)驗(yàn)證明：在不同k值作用下，本文算法的高頻數(shù)據(jù)共現(xiàn)聚類的執(zhí)行時(shí)間更短，有效提升高頻數(shù)據(jù)共現(xiàn)聚類的執(zhí)行效率。

4 結(jié)論

研究基于局部離群點(diǎn)檢測的高頻數(shù)據(jù)共現(xiàn)聚類算法，利用可變網(wǎng)格劃分的局部離群點(diǎn)檢測算法挖掘高頻數(shù)據(jù)共現(xiàn)對象，提升高頻數(shù)據(jù)共現(xiàn)聚類的執(zhí)行效率。該算法雖在實(shí)驗(yàn)中取得了很好的實(shí)驗(yàn)結(jié)果，但還需不斷完善該算法。例如實(shí)施可變網(wǎng)格劃分時(shí)需要計(jì)算高頻數(shù)據(jù)集內(nèi)的各個(gè)維度，在維度較高的情況下，該算法的計(jì)算量也相對較大，以后可以在該算法中加入降維等技術(shù)，進(jìn)一步加快算法的執(zhí)行效率。