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

趙星輝+龍藝璇

摘要摘要：針對低維多流形非相似結構數據，提出一種基于變化率聚類的算法。首先觀察數據，按結構對數據進行分類，然后在同構的數據點之間按變化率進行劃分，最終實現數據聚類。實驗結果證明，該算法能夠有效對低維多流形非相似結構數據進行聚類分析，聚類效果明顯優于LRR、SSC等傳統算法，且時間復雜度較低，有較強的適用性。

關鍵詞關鍵詞：流形學習；子空間聚類；低秩表示法（LRR）；稀疏子空間聚類（SSC）；變化率

DOIDOI：10.11907/rjdk.162181

中圖分類號：TP312文獻標識碼：A文章編號文章編號：16727800（2017）001002903

引言

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

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

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

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

1.1算法描述

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

輸入：數據集D，簇數k。

輸出：k個簇。

Step1：按一定的準則選擇重要屬性。

Step2：根據重要屬性將不同結構的數據劃分開，形成m個中間簇。

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

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

Step5：輸出k個簇。

1.2對比算法選取

在子空間聚類算法中，應用比較多的是基于譜聚類的方法，首先根據樣本點之間的關系構造圖譜，然后利用NCut[4]等譜聚類方法得到分割結果。基于譜聚類的子空間分割方法中比較有代表性的是低秩表示法（LRR）[5]和稀疏子空間聚類（SSC）[6]算法。

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

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

2實驗結果與分析

為了驗證基于變化率的子空間聚類算法的有效性與實用性，本文選取三幅變化率較為明顯的低維多流行結構圖進行聚類分析實驗。

2.1實驗一結果與分析

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

3結語

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

參考文獻：

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

圖4實驗三結果

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

[3]鄭媛媛.基于非負矩陣分解的數據表示算法研究及其應用[D].南京：南京理工大學，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]王衛衛，李小平，馮象初，等.稀疏子空間聚類綜述[J].自動化學報，2015，41（8）：13731384.

[8]周愛武，于亞飛.KMeans聚類算法的研究[J].計算機技術與發展，2011，21（2）：6265.