一種適宜于子空間聚類的離群點(diǎn)檢測(cè)算法

楊維永，何 軍，鄭生軍，張旭東

(1.南京南瑞集團(tuán)公司，江蘇 南京 210003;2.南京信息工程大學(xué)電子與信息工程學(xué)院，江蘇 南京 210044;3.北京國電通網(wǎng)絡(luò)技術(shù)有限公司，北京 100070;4.國網(wǎng)浙江省電力公司信息通信分公司，浙江 杭州 310007)

0 引言

隨著互聯(lián)網(wǎng)、社交媒體［1］和物聯(lián)網(wǎng)［2］的快速發(fā)展，人們所處的數(shù)字世界已經(jīng)邁入了大數(shù)據(jù)［3］的時(shí)代。然而數(shù)據(jù)的洪流給傳統(tǒng)的數(shù)據(jù)處理帶來了新的挑戰(zhàn):大數(shù)據(jù)的處理面臨數(shù)據(jù)的非結(jié)構(gòu)化［4］，收集到的數(shù)據(jù)存在信息缺失，甚至數(shù)據(jù)污染［5］等苛刻條件。因此，數(shù)據(jù)清理是大數(shù)據(jù)分析的一個(gè)首要的預(yù)處理過程。本文主要針對(duì)數(shù)據(jù)污染問題，即數(shù)據(jù)中存在離群點(diǎn)，在子空間聚類模型下討論并提出一個(gè)離群點(diǎn)檢測(cè)的有效算法。

1)離群點(diǎn)檢測(cè)。

在數(shù)據(jù)分析中，對(duì)于所分析的數(shù)據(jù)集D，通常假定D 服從某種概率分布D～P(θ)，而離群點(diǎn)指的則是數(shù)據(jù)集中那些明顯偏離數(shù)據(jù)分布P(θ)的數(shù)據(jù)點(diǎn)。離群點(diǎn)的檢測(cè)與去除是數(shù)據(jù)分析的一個(gè)重要預(yù)處理環(huán)節(jié)，因?yàn)殡x群點(diǎn)的存在會(huì)嚴(yán)重干擾傳統(tǒng)的數(shù)據(jù)分析的結(jié)果。學(xué)術(shù)界對(duì)于離群點(diǎn)的檢測(cè)做了許多深入的研究，例如針對(duì)經(jīng)典的主成分分析(PCA)受制于離群點(diǎn)的污染，性能嚴(yán)重下降的問題，近些年提出了若干優(yōu)秀的魯棒性主成分分析的理論與方法(Robust PCA)［6］;另一方面，在數(shù)據(jù)分析中的聚類分析方面，也出現(xiàn)了若干方法能夠有效克服離群點(diǎn)對(duì)于聚類的影響［7］。

2)子空間聚類。

經(jīng)典的主成分分析方法是假定數(shù)據(jù)來源于一個(gè)低維的線性子空間，進(jìn)而可以將高維數(shù)據(jù)投影到此低維子空間從而得到數(shù)據(jù)的緊湊表示形式，以便利于后續(xù)的分析。然而，在數(shù)據(jù)收集的過程中，數(shù)據(jù)通常來自于多個(gè)不同的數(shù)據(jù)源，因此一種更為恰當(dāng)?shù)臄?shù)據(jù)模型是假定每個(gè)數(shù)據(jù)源是一個(gè)低維動(dòng)力系統(tǒng)，則收集的數(shù)據(jù)可以歸集為該低維子空間的集合。從數(shù)據(jù)中辨識(shí)出子空間集合，并將數(shù)據(jù)分配至相應(yīng)子空間的方法稱之為子空間聚類。

近些年來在機(jī)器學(xué)習(xí)、計(jì)算機(jī)視覺等領(lǐng)域?qū)τ谧涌臻g聚類問題進(jìn)行了深入的研究，提出了諸如SSC［8］、LRR［9］、SCC［10］等優(yōu)秀的子空間聚類算法。另一方面，基于迭代方法的k-subspace 算法［11］及其變種，例如LBF［12］等由于其算法的效率和易于并行處理等優(yōu)勢(shì)，在子空間聚類方面也有較好的應(yīng)用前景。

在大數(shù)據(jù)處理中的子空間聚類問題，一個(gè)不可回避的問題是如何面對(duì)數(shù)據(jù)遭受離群點(diǎn)污染這樣的苛刻情況［13］。離群點(diǎn)的存在，破壞了經(jīng)典子空間聚類算法對(duì)于數(shù)據(jù)分布的假設(shè)，因此學(xué)者們也提出了若干魯棒性的子空間聚類算法，典型的方法是基于離群點(diǎn)稀疏性的先驗(yàn)知識(shí)，通過對(duì)子空間聚類的目標(biāo)函數(shù)增加?1范數(shù)的正則化項(xiàng)，進(jìn)而克服了離群點(diǎn)的影響。本文所提出的離群點(diǎn)檢測(cè)算法也遵循此思路，將?1范數(shù)的正則化引入k-subspace 此類迭代式子空間聚類算法中，以適應(yīng)于大規(guī)模的數(shù)據(jù)處理。

1 適宜于子空間聚類的離群點(diǎn)檢測(cè)模型

對(duì)于向量空間?n中的數(shù)據(jù)集X={x1，x2，…，xN}，假定數(shù)據(jù)來源于K 個(gè)低維線性子空間=1，為了簡(jiǎn)化討論，假定K 個(gè)子空間的維度均為d，則一個(gè)n×d 規(guī)范正交的矩陣Uk能夠張成子空間Sk。對(duì)于數(shù)據(jù)集X 中的任意數(shù)據(jù)xi，假定其必然能夠由某一個(gè)子空間Sj線性表示，即滿足xi=Ujw，其中w 是權(quán)重系數(shù)向量。另外，對(duì)于向量空間?n中的離群點(diǎn)集O={o1，o2，…，oM}，離群點(diǎn)均不能夠由此K 個(gè)低維子空間中的任意一個(gè)子空間線性表示。

對(duì)于子空間聚類中典型的k-subspace 模型，其優(yōu)化的目標(biāo)函數(shù)如公式(1)所示:

其中αik是分配因子，即:

表示數(shù)據(jù)xi適合歸類于子空間Uk。然而，由于離群點(diǎn)的出現(xiàn)，根據(jù)假定，任意一個(gè)離群點(diǎn)oj均無法由子空間線性表示，則離群點(diǎn)對(duì)于K 個(gè)子空間的線性回歸殘差值無法達(dá)到最優(yōu)。因此，在離群點(diǎn)的影響下，模型(1)無法進(jìn)行正確的子空間聚類。

根據(jù)離群點(diǎn)具有稀疏性的先驗(yàn)條件，對(duì)模型(1)增加?1范數(shù)正則化，即引入離群點(diǎn)殘差向量y 和動(dòng)態(tài)離群點(diǎn)判別閾值∈t，則離群點(diǎn)檢測(cè)的方法如公式(3)所示:

其中，向量y 的長(zhǎng)度與數(shù)據(jù)集大小一致，因此公式(3)表示如果對(duì)于某個(gè)數(shù)據(jù)xi，其投影到任意子空間的最小殘差ri超過給定判別閾值∈t，則將其檢測(cè)為離群點(diǎn)，并將最小的殘差ri記錄在向量y 的對(duì)應(yīng)分量。于是，離群點(diǎn)越稀疏，則向量y 的?1范數(shù)會(huì)越小。因此，得到適宜于離群點(diǎn)的子空間聚類模型(4):

需要指出的是，模型(4)與k-subspace 一致，是一類迭代更新的子空間聚類模型，離群點(diǎn)判別閾值在算法的迭代過程中會(huì)進(jìn)行相應(yīng)的改變。由于在迭代的初期，子空間剛剛初始化，模型還不能準(zhǔn)確地判定數(shù)據(jù)歸為哪一個(gè)子空間，自然也就無法準(zhǔn)確給出離群點(diǎn)的判定，因此，∈0設(shè)定為一個(gè)較大的數(shù)值。引入一個(gè)衰退因子η(0 ＜η ＜1)，在每次模型迭代更新后，更新判別閾值∈t=η∈t-1。于是，隨著模型的迭代，離群點(diǎn)判別閾值以指數(shù)級(jí)衰減，最終會(huì)將所有的離群點(diǎn)準(zhǔn)確地檢測(cè)出，并對(duì)子空間進(jìn)行合適的聚類。

2 離群點(diǎn)檢測(cè)與子空間聚類算法

根據(jù)離群點(diǎn)檢測(cè)公式(3)，可以列出偽碼如算法1 所示。

算法1 離群點(diǎn)檢測(cè)算法

從算法1 可以看出，確定一個(gè)數(shù)據(jù)是否是離群點(diǎn)，需要將該數(shù)據(jù)分別投影至K 個(gè)子空間，因此該算法本質(zhì)上是計(jì)算K 個(gè)最小二乘問題。又因?yàn)闃?gòu)成子空間的矩陣Uk規(guī)范正交，于是最小二乘算法被簡(jiǎn)化為僅需進(jìn)行一次矩陣和向量的相乘。

根據(jù)修改后的子空間聚類模型(4)，可以列出該算法的偽碼如算法2 所示。

算法2 適宜于離群點(diǎn)的子空間聚類算法

從算法2 可以看出，對(duì)于待判別的數(shù)據(jù)，首先確定其是否是離群點(diǎn)，如果是離群點(diǎn)則標(biāo)記對(duì)應(yīng)的離群點(diǎn)殘差向量，否則進(jìn)行子空間歸類，進(jìn)而更新該子空間。在算法迭代的過程中，逐步更新K 個(gè)子空間，由于算法是逐數(shù)據(jù)進(jìn)行處理，因此更新子空間的過程相當(dāng)于是隨機(jī)梯度下降算法(SGD)，對(duì)于內(nèi)存的要求相當(dāng)?shù)?，只需要維護(hù)k 個(gè)n×d 矩陣;同時(shí)算法的計(jì)算量也非常低，對(duì)于每個(gè)數(shù)據(jù)僅需計(jì)算k 次矩陣和向量乘法和進(jìn)行一次子空間的梯度下降更新。由此討論可以看出，算法2 滿足對(duì)于大數(shù)據(jù)處理的需求，即較低的計(jì)算復(fù)雜度和較少的內(nèi)存需求。

3 實(shí)驗(yàn)仿真驗(yàn)證

為了驗(yàn)證算法1 和算法2 在子空間聚類方面對(duì)于離群點(diǎn)的魯棒性，筆者設(shè)計(jì)了如下的仿真實(shí)驗(yàn)進(jìn)行驗(yàn)證。

根據(jù)上述討論，算法2 本質(zhì)上是一種隨機(jī)梯度下降算法，適宜于大數(shù)據(jù)處理［14］。這里考慮一種流式大數(shù)據(jù)情況，也就是數(shù)據(jù)以序列方式不斷地產(chǎn)生，數(shù)據(jù)來源于K=4 個(gè)低維線性子空間，子空間的秩d=1，并以隨機(jī)方式p(o)=0.1 加入離群點(diǎn)，為了方便可視化，本實(shí)驗(yàn)考慮數(shù)據(jù)的維度為n=3。圖1 展示了原始序列數(shù)據(jù)的空間分布情況。可以看出，對(duì)于秩為1 的子空間，其數(shù)據(jù)分別呈現(xiàn)出線性的形狀;而離群點(diǎn)的分布則完全隨機(jī)化。

圖1 原始序列數(shù)據(jù)

圖2 展示了子空間聚類算法2 的收斂速度?？梢钥闯?，盡管受到離群點(diǎn)的影響，算法2 依然顯示出了近似線性的快速收斂速度，成功地辨識(shí)出K=4 個(gè)子空間。

圖2 算法的收斂過程

最后，圖3 展示了最終對(duì)于序列數(shù)據(jù)的聚類結(jié)果，可以清晰地看出，數(shù)據(jù)流規(guī)整地來源于K=4 個(gè)子空間，而離群點(diǎn)被準(zhǔn)確地檢測(cè)出。其中圖中的橫坐標(biāo)表示數(shù)據(jù)流的標(biāo)號(hào)，縱坐標(biāo)的數(shù)值表示數(shù)據(jù)被歸為第幾個(gè)子空間，因?yàn)镵=4，所以縱坐標(biāo)的最大數(shù)值為4，離群點(diǎn)的標(biāo)記為-1。

圖3 子空間聚類的結(jié)果

4 結(jié)束語

針對(duì)大數(shù)據(jù)分析中不可避免的數(shù)據(jù)污染問題，本文以子空間聚類為研究對(duì)象，討論并提出了一種適合于子空間聚類的離群點(diǎn)檢測(cè)算法。本文所提出的算法能夠自適應(yīng)地確定離群點(diǎn)檢測(cè)閾值，并結(jié)合隨機(jī)梯度下降算法動(dòng)態(tài)更新子空間，算法復(fù)雜度低，內(nèi)存需求小，適合于大數(shù)據(jù)處理。通過數(shù)值仿真實(shí)驗(yàn)，驗(yàn)證了本算法的有效性和收斂性。對(duì)于未來的工作，筆者考慮將算法實(shí)現(xiàn)在目前流行的大數(shù)據(jù)處理平臺(tái)，諸如Spark［15］，并結(jié)合大數(shù)據(jù)流式計(jì)算技術(shù)［16］，在網(wǎng)絡(luò)日志安全檢測(cè)等方面進(jìn)行應(yīng)用和開發(fā)。

［1］LaValle Steve，Eric Lesser，Rebecca Shockley，et al.Big data，analytics and the path from insights to value［J］.MIT Sloan Management Review (Winter 2011)，2011，52(2).

［2］Gubbi Jayavardhana，Rajkumar Buyya，Slaven Marusic，et al.Internet of Things (IoT):A vision，architectural elements，and future directions［J］.Future Generation Computer Systems，2013，29(7):1645-1660.

［3］Manyika James，Michael Chui，Brad Brown，et al.Big data:The Next Frontier for Innovation，Competition，and Productivity［R］.McKinsey Global Institute，2011.

［4］Sagiroglu Seref，Duygu Sinanc.Big data:A review［C］//IEEE 2013 International Conference on Collaboration Technologies and Systems(CTS).2013:42-47.

［5］Wu Xindong，Zhu Xingquan，Wu Gongqing，et al.Data mining with big data［J］.IEEE Transactions on Knowledge and Data Engineering，2014，26(1):97-107.

［6］Emmanuel J Candès，Li Xiaodong，Ma Yi，et al.Robust principal component analysis?［J］.Journal of the ACM(JACM)，2011，58(3):11.

［7］Victoria J Hodge，Jim Austin.A survey of outlier detection methodologies［J］.Artificial Intelligence Review，2004，22(2):85-126.

［8］Elhamifar Ehsan，Rene Vidal.Sparse subspace clustering:Algorithm，theory，and applications［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35(11):2765-2781.

［9］Liu Guangcan，Lin Zhouchen，Yan Shuicheng，et al.Robust recovery of subspace structures by low-rank representation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35(1):171-184.

［10］Chen Guangliang，Gilad Lerman.Spectral curvature clustering (SCC)［J］.International Journal of Computer Vision，2009，81(3):317-330.

［11］Ho Jason，Yang Ming-Hsuan，Lim Jongwoo，et al.Clustering appearances of objects under varying illumination conditions［C］// Proceedings of 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.2003:1-11.

［12］Zhang Teng，Arthur Szlam，Yi Wang，et al.Hybrid linear modeling via local best-fit flats［J］.International Journal of Computer Vision，2012，100(3):217-240.

［13］Vidal René.A tutorial on subspace clustering［J］.IEEE Signal Processing Magazine，2010，28(2):52-68.

［14］Cevher Volkan，Steffen Becker，Martin Schmidt.Convex optimization for big data:Scalable，randomized，and parallel algorithms for big data analytics［J］.IEEE Signal Processing Magazine，2014，31(5):32-43.

［15］Zaharia Matei，Mosharaf Chowdhury，Michael J Franklin，et al.Spark:Cluster computing with working sets［C］//Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing.2010:10-10.

［16］Zaharia Matei，Tathagata Das，Li Haoyuan，et al.Discretized streams:Fault-tolerant streaming computation at scale［C］// Proceedings of the 24th ACM Symposium on Operating Systems Principles.2013:423-438.