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

周志洪，馬 進，夏正敏，陳秀真

(1.上海交通大學網(wǎng)絡安全技術研究院，上海 200240；2.上海市信息安全綜合管理技術研究重點實驗室，上海 200240)

1 引言

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

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

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

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

2.1 局部離群點檢測算法

2.1.1 相關定義

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

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

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

2)最多存在k-1個對象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間的可達距離。假設k屬于一個自然數(shù)，定義對象x與對象o間的可達距離公式如下

reach-distk(x，o)

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

(2)

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

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

(3)

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

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

(4)

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

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

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

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

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

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

(5)

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

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

2.1.3 設置參數(shù)

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

(6)

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

(7)

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

2.1.4 算法執(zhí)行步驟

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

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

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

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

sim(ta，tb)=

(8)

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

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

(9)

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

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

(10)

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

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

3 實驗分析

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

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

3.1 離群點檢測性能分析

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

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

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

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

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

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

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

3.3 聚類的準確性分析

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

(11)

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

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

(12)

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

表4 三種算法F-measure值測試結果

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

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

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

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

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

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

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

4 結論

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