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

姚鵬，古平（重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶　400044）

?

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

姚鵬，古平
（重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶400044）

摘要：

關(guān)鍵詞：

0　引言

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

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

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

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

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

1.1基本定義

1.2譜聚類

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

1.3HSIC

HSIC是一種基于核的獨(dú)立性度量方法，是在再生核希爾伯特空間上定義互協(xié)方差算子，在互協(xié)方差算子中找出可度量獨(dú)立性的統(tǒng)計(jì)量，從而來獲得獨(dú)立性的大小。HSIC使用Hilbert-Schmidt互協(xié)方差算子，通過對該算子范數(shù)的經(jīng)驗(yàn)估計(jì)來評估獨(dú)立性[11]。

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

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

1.4多視角生成算法

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

公式（3）中的第一項(xiàng)HSIC（XW，U）用譜聚類準(zhǔn)則公式（1）表示：

上述優(yōu)化問題的最優(yōu)解在HSIC（XW，U）較大并且HSIC（XW，Y）較小時(shí)獲得。HSIC（XW，U）大表示聚類劃分U是在XW中的一個(gè)高質(zhì)量聚類，HSIC（XW，Y）小表示W(wǎng)空間中的聚類與已知聚類結(jié)果Y關(guān)聯(lián)度較低，W是一個(gè)新奇的聚類子空間。

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

②假設(shè)U是固定的，優(yōu)化W。當(dāng)U固定時(shí)，公式（4）可轉(zhuǎn)化為：

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

輸入：數(shù)據(jù)X，已獲得劃分矩陣Y，子空間維數(shù)q，簇個(gè)數(shù)c。

輸出：轉(zhuǎn)換矩陣W，離群度LOF。

1.初始化W=I。

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

4.重復(fù)步驟2，3直到收斂。

5.對U進(jìn)行k均值聚類，劃分結(jié)果Yi合并到Y(jié)。

6.計(jì)算XW中各數(shù)據(jù)點(diǎn)的LOF。

2　實(shí)驗(yàn)結(jié)果及分析

為了測試KDAC算法的有效性，選取LOF和LDOF作為對比算法，驗(yàn)正top-n離群點(diǎn)的精確度。算法使用Python編寫，實(shí)驗(yàn)環(huán)境：Intel Core i3，2.4GHz，內(nèi)存4GB，Windows 10操作系統(tǒng)。

2.1Yeast data set

酵母數(shù)據(jù)集（yeast data set）包含1484個(gè)樣本，每個(gè)樣本有9個(gè)屬性，有一個(gè)屬性是類標(biāo)屬性。實(shí)驗(yàn)中從樣本中選擇1299條記錄作為正常數(shù)據(jù)，加入20個(gè)離群點(diǎn)。KDAC算法中取c=4，q=6。實(shí)驗(yàn)結(jié)果如圖1所示。

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

2.2KDD-Cup 1999數(shù)據(jù)集

KDD-Cup 1999是一個(gè)網(wǎng)絡(luò)入侵檢測的數(shù)據(jù)集，它有五種數(shù)據(jù)對象，包括正常的連接，各種入侵和攻擊等。實(shí)驗(yàn)時(shí)對數(shù)據(jù)集進(jìn)行修改，在原來41維屬性中選取32維連續(xù)屬性，并使入侵?jǐn)?shù)據(jù)（50個(gè)離群點(diǎn)）占2％。實(shí)驗(yàn)結(jié)果如圖2所示。

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

圖1　yeast數(shù)據(jù)集

圖2　KDD-Cup 1999數(shù)據(jù)集

3　結(jié)語

本文基于多視角聚類進(jìn)行離群檢測，該算法一方面采用譜聚類，以確保高質(zhì)量的聚類結(jié)果；另一方面通過希爾伯特-施密特獨(dú)立性準(zhǔn)則，以確保新的聚類結(jié)果相對于已知?jiǎng)澐帜Ｊ绞菬o冗余的。從得到的多個(gè)不同的視角，獲得對數(shù)據(jù)集更全面的認(rèn)識。實(shí)驗(yàn)結(jié)果表明，該方法能有效解決離群檢測問題，對高維數(shù)據(jù)集有更好的效果。

參考文獻(xiàn)：

[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]薛安榮，姚林，鞠時(shí)光，等.離群點(diǎn)挖掘方法綜述[J].計(jì)算機(jī)科學(xué)，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].計(jì)算機(jī)研究與發(fā)展，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-），男，河南許昌人，研究生，研究方向?yàn)殡x群檢測

古平（1976-），男，重慶人，副教授，研究方向?yàn)閿?shù)據(jù)挖掘與機(jī)器學(xué)習(xí)

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：

復(fù)雜數(shù)據(jù)集通常包含不同的組織模式，傳統(tǒng)的離群檢測算法從單一視角尋找離群點(diǎn)，不能充分利用多視角信息，造成信息遺漏。提出一種基于多視角聚類的離群檢測算法，該算法一方面采用譜聚類，以確保高質(zhì)量的聚類結(jié)果；另一方面通過希爾伯特-施密特獨(dú)立性準(zhǔn)則，以確保新的聚類結(jié)果相對于已知?jiǎng)澐帜Ｊ绞菬o冗余的。對得到多個(gè)視角進(jìn)行離群分析，從而得到更準(zhǔn)確的離群集。研究結(jié)果表明，該算法能夠提高離群檢測精度。

離群檢測；多視角；譜聚類；希爾伯特-施密特獨(dú)立性準(zhǔn)則

文章編號：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