基于變化率的子空間聚類算法

趙星輝+龍藝璇

摘要摘要：針對低維多流形非相似結(jié)構(gòu)數(shù)據(jù)，提出一種基于變化率聚類的算法。首先觀察數(shù)據(jù)，按結(jié)構(gòu)對數(shù)據(jù)進(jìn)行分類，然后在同構(gòu)的數(shù)據(jù)點(diǎn)之間按變化率進(jìn)行劃分，最終實(shí)現(xiàn)數(shù)據(jù)聚類。實(shí)驗(yàn)結(jié)果證明，該算法能夠有效對低維多流形非相似結(jié)構(gòu)數(shù)據(jù)進(jìn)行聚類分析，聚類效果明顯優(yōu)于LRR、SSC等傳統(tǒng)算法，且時(shí)間復(fù)雜度較低，有較強(qiáng)的適用性。

關(guān)鍵詞關(guān)鍵詞：流形學(xué)習(xí)；子空間聚類；低秩表示法（LRR）；稀疏子空間聚類（SSC）；變化率

DOIDOI：10.11907/rjdk.162181

中圖分類號：TP312文獻(xiàn)標(biāo)識碼：A文章編號文章編號：16727800（2017）001002903

引言

隨著科學(xué)技術(shù)的發(fā)展，各類數(shù)據(jù)量迅猛增長。然而，并不是所有數(shù)據(jù)都是精煉且真實(shí)有效的，海量數(shù)據(jù)中存在著冗余與錯誤。如何對這些數(shù)據(jù)進(jìn)行快速、有效的處理，從而找到數(shù)據(jù)之間的內(nèi)在聯(lián)系成為解決很多問題的關(guān)鍵。因此對高維數(shù)據(jù)進(jìn)行相關(guān)性分析、聚類分析、結(jié)構(gòu)分析，挖掘數(shù)據(jù)背后的價(jià)值與意義尤為重要。

對高維數(shù)據(jù)進(jìn)行分析處理，當(dāng)前應(yīng)用比較廣泛的維數(shù)約減技術(shù)有流形學(xué)習(xí)[1]和子空間聚類[2]。流形學(xué)習(xí)的前提是假設(shè)在一個(gè)高維歐式空間均勻地對數(shù)據(jù)進(jìn)行采樣，然后將高維數(shù)據(jù)映射到低維，使得數(shù)據(jù)的低維表示能體現(xiàn)高維數(shù)據(jù)的本質(zhì)信息[3]；子空間聚類是假設(shè)一組數(shù)據(jù)屬于多個(gè)線性子空間的并集，將這組數(shù)據(jù)進(jìn)行分類，使得不同的類對應(yīng)不同的子空間。

高維數(shù)據(jù)的結(jié)構(gòu)一般為低維的，可以用位于相同子空間的低維數(shù)據(jù)對高維數(shù)據(jù)進(jìn)行稀疏表示，因此設(shè)計(jì)一種能分析低維多流形非相似結(jié)構(gòu)數(shù)據(jù)的算法更具有一般性和適用性。本文針對低維多流形非相似結(jié)構(gòu)數(shù)據(jù)，提出一種基于變化率聚類的算法，從而更有效進(jìn)行聚類分析。

1基于變化率的子空間聚類算法

1.1算法描述

為更好地對低維多流行非相似結(jié)構(gòu)的數(shù)據(jù)進(jìn)行聚類分析，本文提出一種基于變化率的子空間聚類算法。該算法的基本思想是：首先觀察數(shù)據(jù)，若數(shù)據(jù)來源于多個(gè)維數(shù)不等的數(shù)據(jù)結(jié)構(gòu)，則先根據(jù)按屬性重要性篩選出的維對不同結(jié)構(gòu)的數(shù)據(jù)進(jìn)行分類；然后在同構(gòu)數(shù)據(jù)點(diǎn)之間按其變化率進(jìn)行劃分，若變化率超過一定的閾值β，則分到不同的類中，若小于等于β則分到同一類；最終得到各個(gè)不同結(jié)構(gòu)的分類。任意兩點(diǎn)之間的變化率為：RC（X，Y） = Yi + 1 -Xi + 1 Yi -Xi （1）算法描述如下：

輸入：數(shù)據(jù)集D，簇?cái)?shù)k。

輸出：k個(gè)簇。

Step1：按一定的準(zhǔn)則選擇重要屬性。

Step2：根據(jù)重要屬性將不同結(jié)構(gòu)的數(shù)據(jù)劃分開，形成m個(gè)中間簇。

Step3：對中間簇中的數(shù)據(jù)按變化率RC進(jìn)行分類，如果兩點(diǎn)之間的變化率大于β，則劃分為不同的類；否則劃為一類。

Step4：重復(fù)Step3直到中間簇都被劃分完。

Step5：輸出k個(gè)簇。

1.2對比算法選取

在子空間聚類算法中，應(yīng)用比較多的是基于譜聚類的方法，首先根據(jù)樣本點(diǎn)之間的關(guān)系構(gòu)造圖譜，然后利用NCut[4]等譜聚類方法得到分割結(jié)果?；谧V聚類的子空間分割方法中比較有代表性的是低秩表示法（LRR）[5]和稀疏子空間聚類（SSC）[6]算法。

低秩表示法（LRR）算法是為了從包含錯誤的數(shù)據(jù)中恢復(fù)子空間結(jié)構(gòu)而提出的。在給定的一組數(shù)據(jù)樣本中，每一個(gè)都可以被表示為在一個(gè)字典中的一個(gè)基數(shù)線性組合，LRR旨在找到所有共同數(shù)據(jù)的低秩表示。通過選擇一個(gè)特定的字典，LRR可以很好解決子空間聚類問題。對于被任意錯誤污染的數(shù)據(jù)，LRR還可以近似的恢復(fù)行空間，LRR是一個(gè)有效的且具有魯棒性的子空間聚類算法。

稀疏子空間聚類（SSC）可以用來聚類位于低維子空間的并集的數(shù)據(jù)點(diǎn)。關(guān)鍵思想是，從其它點(diǎn)獲得無窮多的可以表示的數(shù)據(jù)點(diǎn)，并用一個(gè)稀疏表示來對應(yīng)從相同的子空間選擇的點(diǎn)。這促進(jìn)了譜聚類算法框架下用來推斷數(shù)據(jù)的聚類子空間的稀疏優(yōu)化程序。該算法處理接近于子空間交集的數(shù)據(jù)點(diǎn)是有效的，另一個(gè)關(guān)鍵優(yōu)勢在于它可以通過合并數(shù)據(jù)的模型到稀疏優(yōu)化程序來直接處理數(shù)據(jù)干擾，如噪音、稀疏的無關(guān)記錄和缺失記錄。在運(yùn)動分割和聚類方面，該算法都具有較高的實(shí)用性。

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

為了驗(yàn)證基于變化率的子空間聚類算法的有效性與實(shí)用性，本文選取三幅變化率較為明顯的低維多流行結(jié)構(gòu)圖進(jìn)行聚類分析實(shí)驗(yàn)。

2.1實(shí)驗(yàn)一結(jié)果與分析

從圖2可以看出，對分布在獨(dú)立子空間中的兩條直線上的數(shù)據(jù)進(jìn)行聚類，若每條直線上的數(shù)據(jù)為一類，則本文提出方法的聚類結(jié)果明顯要比LRR和SSC好。LRR和SSC算法聚類效果欠佳的原因在于對數(shù)據(jù)分解處理后用K-means算法[8]進(jìn)行聚類，K-means算法以距離度量為基礎(chǔ)，適合于發(fā)現(xiàn)球狀簇，對于線性數(shù)據(jù)的聚類效果并不理想。本文算法和LRR算法的主要誤差都在于圖像交叉相似的部分，但LRR算法的聚類誤差部分明顯大于本文算法的聚類誤差部分，而SSC算法基本無法聚類該圖數(shù)據(jù)。

3結(jié)語

本文提出一種基于變化率聚類的算法，首先觀察數(shù)據(jù)，按屬性重要性篩選出的維對不同結(jié)構(gòu)數(shù)據(jù)進(jìn)行分類，然后在同構(gòu)數(shù)據(jù)點(diǎn)之間按其變化率進(jìn)行分類，若變化率超過一定的閾值β，則分到不同的類中；若小于或等于β，則分到同一類，最終得到各個(gè)不同結(jié)構(gòu)的分類。此算法能夠有效對低維多流形非相似結(jié)構(gòu)的數(shù)據(jù)進(jìn)行聚類分析，聚類效果明顯優(yōu)于LRR、SSC等傳統(tǒng)算法，且時(shí)間復(fù)雜度較低，可以進(jìn)一步應(yīng)用到圖像分類、運(yùn)動識別等領(lǐng)域。

參考文獻(xiàn)：

[1]JB TENENBAUM，VD SILVA，JC LANGFORD.A global geometric framework for nonlinear dimensionality reduction[J].Science，2000，290（5500）：23192323.

圖4實(shí)驗(yàn)三結(jié)果

[2]E ELHAMIFAR，R VIDAL.Sparse subspace clustering[C].IEEE Conference on Computer Vision and Pattern Recognition，2009：27902797.

[3]鄭媛媛.基于非負(fù)矩陣分解的數(shù)據(jù)表示算法研究及其應(yīng)用[D].南京：南京理工大學(xué)，2013.

[4]J SHI，J MALIK.Normalized cuts and image segmentation[J].IEEE Transactions Pattern Analysis Machine Intelligence，2000，22（8）：888905.

[5]G LIU，Z LIN，S YAN，et al.Robust recovery of subspace structures by lowrank representation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35（1）：171184.

[6]E ELHAMIFAR，R VIDAL.Sparse subspace clustering：algorithm，theory，and applications[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35（11）：27652781.

[7]王衛(wèi)衛(wèi)，李小平，馮象初，等.稀疏子空間聚類綜述[J].自動化學(xué)報(bào)，2015，41（8）：13731384.

[8]周愛武，于亞飛.KMeans聚類算法的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2011，21（2）：6265.