一種基于多視角聚類的離群檢測算法

姚鵬，古平（重慶大學計算機學院，重慶　400044）

?

一種基于多視角聚類的離群檢測算法

姚鵬，古平
（重慶大學計算機學院，重慶400044）

摘要：

關鍵詞：

0　引言

離群檢測（Outlier Detection）是數據挖掘技術的一個研究方向，其目的是從大量數據中找到小部分異常的，與常規數據不同的數據。大多數算法使用Hawkins的離群點定義：“離群點的表現與其他點如此不同，以至于讓人懷疑它是由不同機制產生的”。目前，離群檢測在網絡入侵檢測、信用卡欺詐檢測、故障診斷、災害預測、圖像處理分析等領域都得到廣泛的應用[1-2]。現有的離群點檢測方法分類有基于分布的、基于距離的、基于密度的、基于聚類的、基于深度的[3-4]等。

以前的數據挖掘算法中，數據集的屬性是被認真挑選過的。但在大數據時代，數據的個數和維度都很多，數據的特征可能淹沒在高維的數據中，而只在特定的子空間有所體現，有些離群點也只能在子空間中觀察到。此時，離群檢測任務不僅僅為了找出離群點，同時要找出相關的子空間，從不同的視角去全面評估數據，而不是傳統的在全部屬性空間尋找離群點。聚類分析是根據數據集的特征，將數據劃分成有意義或者有用的簇，從而獲得數據集所包含的某種內部結構。傳統的聚類算法在做數據分析時，只挖掘數據中單個合理的模式，然而在實際應用中，數據往往蘊含著多個合理且有價值的特征模式。例如，在文檔數據中，既存在文檔主題模式，又存在文檔的寫作風格模式。因此，人們希望從數據中挖掘多個相異且有價值的聚類結果，以便給決策者提供更多的選擇空間。具體到離群檢測應用中，我們希望從多個視角對數據進行分析，獲得更全面的離群點集。

多視角聚類（multi-view clustering）是近年來新興的一種數據分析方法，有的文獻也稱為替代聚類（alternative clustering）[5，13]或無冗余聚類（non-redundant clustering）[6]。多視角聚類在進行數據分析時，一方面希望得到的高質量聚類結果，即捕捉到數據集本身所蘊含的某種合理內在結構；另一方面要求所得到的多個聚類之間無冗余，即希望從多角度全方位觀測分析數據。現有的多視角聚類算法可以分為同步學習和順序學習兩類。同步多視角聚類算法力圖從數據集中同時挖掘出多個相異且有價值的聚類模式；順序多視角聚類算法是在已知一個或多個聚類結果的情況下，再求一個與已知模式不同的高質量聚類結果。同步學習過程和順序學習過程均可挖掘出數據集中的多個劃分模式，不同的是順序多視角學習算法在學習一個新的聚類模式時，充分考慮已知的數據劃分模式，可將這些先驗知識融入到多視角學習的過程中[7]。

本文算法實現基于順序多視角聚類的離群檢測算法KDAC，采用譜聚類來獲得高質量聚類，同時使用希爾伯特-施密特獨立性準則HSIC保證新的聚類和前面的聚類無冗余，重復執行獲得多個視角，對多個視角進行離群分析，提高離群檢測的精確度。

1　基于多視角聚類的離群檢測算法

1.1基本定義

1.2譜聚類

譜聚類是一種基于譜圖理論的聚類算法，不同于傳統的k均值、EM算法，它不要求數據是凸形的，能夠在任意形狀的數據中進行聚類并得到全局最優的結果。譜聚類算法的基本思想是構造數據集的相似度矩陣，求出矩陣的特征值和特征向量，選擇合適的特征向量將原始數據點映射到低維空間中進行聚類。

1.3HSIC

HSIC是一種基于核的獨立性度量方法，是在再生核希爾伯特空間上定義互協方差算子，在互協方差算子中找出可度量獨立性的統計量，從而來獲得獨立性的大小。HSIC使用Hilbert-Schmidt互協方差算子，通過對該算子范數的經驗估計來評估獨立性[11]。

假設X，Y兩個空間，定義F為X的再生核希爾伯特空間，X到F的映射記為φ：MF，則兩點在核空間的內積可由核函數k1（x，x'）=＜φ（x），φ（x'）＞得到，類似的定義Y的核空間G，映射φ，核函數k2（.，.）。互協方差算子Cxy：GF定義為Cxy=Exy[（φ（x）-μy）（φ（y）-μy）]。Cxy可以看成Hilbert-Schmidt算子，而所謂的HSIC即定義為Cxy的Hilbert-Schmidt算子范數，即HSIC （pxy，F，G）=。對已知的數據Z=｛（x1，y1），…，（xn， yn）｝時可以得到HSIC的經驗估計：

其中K1，K2，H∈Rn×n，K1，K2是Gram矩陣，K1，ij=k1（xi，xj），K2，ij=k2（xi，xj），Hij=δij-n-1。公式（2）已被證明具有收斂速度快和運算簡單等優點，其HSIC值越大說明X，Y關聯性越強，若X和Y獨立，HSIC值為0。

1.4多視角生成算法

在譜聚類中，相似度矩陣K定義在全部數據屬性上，然而有些屬性可能是噪聲或無關的，因此需要對數據進行降維，在低維空間進行譜聚類。定義d×q（其中q＜d）的轉換矩陣W，則XW∈Rn×q表示降維后的數據矩陣。在算法每輪迭代中，給定Y，目標是發現一個替代聚類U以及U所在的子空間W。該問題可表示為優化問題：

公式（3）中的第一項HSIC（XW，U）用譜聚類準則公式（1）表示：

上述優化問題的最優解在HSIC（XW，U）較大并且HSIC（XW，Y）較小時獲得。HSIC（XW，U）大表示聚類劃分U是在XW中的一個高質量聚類，HSIC（XW，Y）小表示W空間中的聚類與已知聚類結果Y關聯度較低，W是一個新奇的聚類子空間。

通過交替的優化矩陣U和W來得到公式（4）的最優解，可分解為下面兩個步驟：

②假設U是固定的，優化W。當U固定時，公式（4）可轉化為：

交替執行步驟1，2直到數據收斂，對U進行k均值聚類可獲得一個新奇且高質量聚類劃分。之后對W空間進行離群檢測，如應用LOF算法[12]，LOF值大的數據為離群點，獲得在W視角下的離群點集。重復多次可獲得不同視角下的離群點集。整體算法KDAC步驟描述如下：

輸入：數據X，已獲得劃分矩陣Y，子空間維數q，簇個數c。

輸出：轉換矩陣W，離群度LOF。

1.初始化W=I。

3.有步驟2得到的U，根據1.4節的維度增加算法更新W。

4.重復步驟2，3直到收斂。

5.對U進行k均值聚類，劃分結果Yi合并到Y。

6.計算XW中各數據點的LOF。

2　實驗結果及分析

為了測試KDAC算法的有效性，選取LOF和LDOF作為對比算法，驗正top-n離群點的精確度。算法使用Python編寫，實驗環境：Intel Core i3，2.4GHz，內存4GB，Windows 10操作系統。

2.1Yeast data set

酵母數據集（yeast data set）包含1484個樣本，每個樣本有9個屬性，有一個屬性是類標屬性。實驗中從樣本中選擇1299條記錄作為正常數據，加入20個離群點。KDAC算法中取c=4，q=6。實驗結果如圖1所示。

由圖1看出，相比LOF和LDOF，KDAC能獲得較好的精確度。

2.2KDD-Cup 1999數據集

KDD-Cup 1999是一個網絡入侵檢測的數據集，它有五種數據對象，包括正常的連接，各種入侵和攻擊等。實驗時對數據集進行修改，在原來41維屬性中選取32維連續屬性，并使入侵數據（50個離群點）占2％。實驗結果如圖2所示。

如圖2所示在維度較高情況下，KDAC算法優于LOF和LDOF算法。在包含很多無關屬性的高維情況下，距離很難再作為樣本相似性的度量。而KDAC將數據映射到多個低維空間，因而更有效檢測離群點。

圖1　yeast數據集

圖2　KDD-Cup 1999數據集

3　結語

本文基于多視角聚類進行離群檢測，該算法一方面采用譜聚類，以確保高質量的聚類結果；另一方面通過希爾伯特-施密特獨立性準則，以確保新的聚類結果相對于已知劃分模式是無冗余的。從得到的多個不同的視角，獲得對數據集更全面的認識。實驗結果表明，該方法能有效解決離群檢測問題，對高維數據集有更好的效果。

參考文獻：

[1]Chandola V，Banerjee A，Kumar V.Anomaly Detection：A Survey[J].Acm Computing Surveys，2009，41（3）：75-79.

[2]Zimek A，Schubert E，Kriegel H P.A Survey on Unsupervised Outlier Detection in High-Dimensional Numerical Data[J].Statistical Analysis & Data Mining the Asa Data Science Journal，2012，66（1）：72-8.

[3]薛安榮，姚林，鞠時光，等.離群點挖掘方法綜述[J].計算機科學，2008，35（11）：13-18.

[4]Kriegel H P，Kr?ger P，Schubert E，et al.Interpreting and Unifying Outlier Scores[J].SDM，2011：13-24.

[5]Qi Z J，Davidson I.A Principled and Flexible Framework for Finding Alternative Clusterings[C].Acm Sigkdd International Conference on Knowledge Discovery & Data Mining.2009：717-726.

[6]Gondek D，Hofmann T.Non-Redundant Clustering with Conditional Ensembles[C].Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，Chicago，Illinois，USA，August 21-24，2005.2005：70-77.

[7]婁錚錚，葉陽東，劉瑞娜.基于IB方法的無冗余多視角聚類[J].計算機研究與發展，2013，50（9）：1865-1875.

[8]Luxburg U V.A Tutorial on Spectral Clustering[J].Statistics & Computing，2007，17（17）：395-416.

[9]Shi J，Malik J.Normalized Cuts and Image Segmentation[J].IEEE Trans.pattern Anal.mach.intell，2000，22（8）：888-905.

[10]Ng A Y，Jordan M I，Weiss Y.On Spectral Clustering：Analysis and an Algorithm[J].Proceedings of Advances in Neural Information Processing Systems，2001，14：849-856.

[11]Gretton A，Bousquet O，Smola A，et al.Measuring Statistical Dependence with Hilbert-Schmidt Norms[M].Algorithmic Learning Theory.Springer Berlin Heidelberg，2005：63-77.

[12]Breunig M M，Kriegel H P，Ng R T，et al.LOF：Identifying Density-Based Local Outliers[J].Acm Sigmod Record，2000，29（2）：93-104.

[13]Dy J G，Jordan M I.Iterative Discovery of Multiple Alternative Clustering Views[J].IEEE Transactions on Pattern Analysis & Machine Intelligence，2013，36（7）：1340-1353.

姚鵬（1990-），男，河南許昌人，研究生，研究方向為離群檢測

古平（1976-），男，重慶人，副教授，研究方向為數據挖掘與機器學習

Multi-View Clustering Based Outlier Detection Algorithm

YAO Peng，GU Ping
（College of Computer Science，Chongqing University，Chongqing 400030）

Abstract：

Complex data sets usually contain different organization patterns，traditional outlier detection algorithm cannot make full use of multi-view information and cause outlier missing from a single point of view.Proposes a multi-view clustering outlier detection algorithm，which on the one hand uses a spectral clustering algorithm to ensure high quality of clustering results；on the other hand，through Hilbert-Schmidt independence criterion to ensure that the new clustering result and the known partition model comparison are not redundant.And then gets more accurate outlier sets through the multi -view of the outlier analysis.The results show that the algorithm can improve the accuracy of outlier detection.

Keywords：

復雜數據集通常包含不同的組織模式，傳統的離群檢測算法從單一視角尋找離群點，不能充分利用多視角信息，造成信息遺漏。提出一種基于多視角聚類的離群檢測算法，該算法一方面采用譜聚類，以確保高質量的聚類結果；另一方面通過希爾伯特-施密特獨立性準則，以確保新的聚類結果相對于已知劃分模式是無冗余的。對得到多個視角進行離群分析，從而得到更準確的離群集。研究結果表明，該算法能夠提高離群檢測精度。

離群檢測；多視角；譜聚類；希爾伯特-施密特獨立性準則

文章編號：1007-1423（2016）14-0043-05

DOI：10.3969/j.issn.1007-1423.2016.14.009

作者簡介：book=47,ebook=48

收稿日期：2016-03-22修稿日期：2016-04-30

Outlier Detection；Multi-View；Spectral Clustering；Hilbert-Schmidt Independence Criterion