張 琦，鄭伯川，張 征，周歡歡

（1.西華師范大學數學與信息學院，四川南充 637009；2.西華師范大學計算機學院，四川南充 637009）

0 引言

聚類分析是數據挖掘領域的關鍵技術之一，是將一群不相關的對象劃分為相似對象的過程。

在許多實際應用中，高維數據通常漸進地存在于低維子空間，其中每個子空間對應一個類。子空間聚類是指將給定的取自于多個子空間并集中的數據點劃分到潛在子空間，在運動分割、圖像聚類、基因表達聚類等領域都有著重要應用。

無監(jiān)督數據的存在使得子空間聚類成為高維數據分析的有力工具。常見的子空間聚類方法主要分為四類：基于代數的方法、基于迭代的方法、基于統計的方法、基于譜聚類（Spectral Clustering，SC）的方法。近年來，基于SC 的稀疏子空間聚類（Sparse Subspace Clustering，SSC）算法基于稀疏表示理論，通過對系數矩陣施加

l

約束，獲得數據的稀疏表示，從而捕獲數據的全局結構。SSC 一經提出，就得到了廣泛關注和大量應用。所謂稀疏性就是指用盡量少的原子基來表示數據，即數據的非零系數的個數盡量少。近年來，研究者們在SSC 的基礎上進行了不同的拓展：Liu 等提出的低秩表示（Low-Rank Representation，LRR）模型，通過對數據施加低秩約束來獲取低秩表示，從而捕獲數據的全局結構；低秩SSC（Low-Rank SSC，LRSSC）將SSC 與LRR 相結合，不僅對系數進行稀疏約束，同時在模型中加入低秩約束，結合了稀疏性與低秩性的優(yōu)點；結構化的SSC（Structured SSC，SSSC）將每個數據點表示為其他數據點的結構化稀疏線性組合，設計了一個統一的優(yōu)化框架，可以同時學習親和矩陣和子空間的分割；為了解決SSC 時間復雜度與問題大小的立方成正比問題以及SSC 不處理未用于構造相似度圖的樣本外數據，可擴展的SSC 采用“采樣―聚類-編碼-分類”策略來解決可擴展性和樣本外問題；內核SSC（Kernel SSC，KSSC）利用核技巧，將SSC 擴展到非線性流形，在高維特征空間中利用非線性解析表示實現了更好的聚類；魯棒子空間聚類（Robust Subspace Clustering，RSC）提出了一種兩步

l

最小化算法，利用泛函分析的思想，解決噪聲數據的聚類問題；迭代重加權的SSC（Reweighted SSC，RSSC）算法，相對于傳統的

l

最小化框架，不僅提高了算法性能，而且更加逼近

l

最小化框架；基于正交匹配追蹤的SSC（scalable SSC by Orthogonal Matching Pursuit，SSCOMP）在廣義條件下既提高了計算效率，又保證了保持子空間的親和性；基于自表達和集群效應的算法，利用集群效應進行自表達，并且使用

l

范數誘導稀疏，解決了SSC 中關聯矩陣過于稀疏時忽略同一子空間數據的相似結構問題；基于低秩轉換的SSC（SSC with Low-Rank Transformation，SSC-LRT）算法提出了一種結合低秩轉換與SSC 相結合的兩階段迭代策略，解決了非獨立假設下的聚類問題、隨機SSC（Stochastic SSC via Orthogonal Matching Pursuit with Consensus，SCOMP-C）引入Dropout，解決了子空間聚類中的過度分割問題，提升了親和圖的連通性。

在SSC 方法中，如果數據集中數據點個數少，稀疏系數矩陣相對更容易求解，因此本文提出隨機分塊的SSC 方法，將原問題數據分成幾個數據量更少的問題求解。該方法的創(chuàng)新主要包括：

1）將原問題隨機劃分為

T

個子問題進行求解，將

T

個子問題的稀疏系數矩陣進行組合，然后采用SC 算法實現原問題的聚類；

2）提出了一種隨機分塊策略與擴充策略，利用該策略實現多個子問題分解和多個子問題系數矩陣的組合。

1 稀疏子空間聚類

稀疏子空間聚類主要包括兩個階段：1）使用稀疏或低秩最小化約束從數據中學習相似度矩陣；2）利用SC 對相似度矩陣進行分割。SC 是否成功很大程度上取決于構建一個信息豐富的相似度矩陣。

稀疏子空間聚類是一種基于自表示的方法?；舅枷胧牵簛碜?p>d

維子空間

S

中的任意數據點

y

都可以被表示成來自子空間

S

的其他數據點的一個線性組合。其中，因此，理想情況下，一個數據點的稀疏表示中非零系數的個數對應于潛在子空間的維數。

為了找到最稀疏的

c

的解，最小化目標函數為：

然而，

l

范數是非凸優(yōu)化問題和NP 難的，可用

l

范數來凸松弛

l

范數，原問題可轉化為

l

最小化問題：

矩陣形式的公式為：

考慮到噪聲和離群值：

其中：‖·‖表示Frobenius范數；

E

∈R表示離群點，

Z

∈R表示噪聲；

λ

、

λ

是平衡參數，用于平衡目標函數的三個項。

在一些實際問題中，數據位于仿射子空間而非線性子空間的并集。因此，為了將位于仿射子空間并集中的數據點進行聚類，稀疏優(yōu)化方程進一步改進為：

利用式（6）中的等式約束，消除

Z

：

引入輔助變量

A

∈R，加入參數

λ

，以及2個懲罰項，得

引入拉格朗日乘子

δ

∈R，

Δ

∈R，得到式（6）的拉格朗日函數：

通過交替方向乘子法（Alternating Direction Method of Multipliers，ADMM）求解式（9），可以獲得系數矩陣，則相似度矩陣定義為：

將相似度矩陣

W

輸入到SC 算法，即可獲得最終聚類結果。SSC 的框架如圖1 所示。

圖1 SSC框架Fig.1 Framework of SSC

SC 借助圖論的知識，將所有數據點看作空間中的點，點與點之間用邊相連，兩點之間的距離越遠，邊的權重越小，反之越大。通過對所有數據點組成的圖進行分割，使得不同子圖之間邊的權重盡可能低，子圖內邊的權重盡可能高，從而達到聚類的目的。將式（10）作為相似圖中點之間的權值矩陣，那么可以利用SC 來對稀疏子空間進行聚類。

算法1 SC 算法。

輸入 相似度矩陣

W

。輸出 數據集

Y

的

k

子集劃分

y

，

y

，…，

y

。步驟1 計算相似矩陣

W

的拉普拉斯矩陣

L

：

步驟3 把

k

個

n

維特征向量列成

n

×

k

的矩陣；步驟4 把生成的矩陣每一行看作

k

維空間的一個向量，使用

K-

Means 聚成

k

類。

2 基于隨機分塊的稀疏子空間聚類

2.1 算法思想和聚類求解框架

在深度網絡的訓練過程中，Dropout 技術將神經網絡中的每個神經元按照一定的概率使其暫時在神經網絡中失效。通過每次隨機地使某些神經元失效，減少神經元之間的相互作用，使得網絡模型不依賴于某些局部神經元，從而減輕過擬合現象。

受神經網絡中使用的Dropout 的啟發(fā)，本文提出在稀疏子空間稀疏系數矩陣求解過程中引入隨機分塊策略，將數據集隨機劃分成幾個子集，每個子集作為一個子問題分別求解出系數矩陣

C

，然后將所有子問題的系數矩陣通過擴充后累加成一個相似矩陣

W

，進而進行SC?；陔S機分塊的SSC 的框架如圖2 所示。

圖2 基于隨機分塊的SSC框架Fig.2 Framework of SSC based on random blocking

2.2 數學模型

基于隨機分塊的SSC 將原問題轉換為

T

個子問題，每個子問題的目標函數可以采取以下形式：

其中：

Y

表示第

t

（

t

=0，1，2，…，

T

）個子問題的數據集的矩陣形式；

C

表示第

t

個子問題的系數矩陣。

在現實世界中，大多數是噪聲數據集，所以子問題目標函數采用以下形式：

其中：

E

表示第

t

個子問題的離群點；

Z

表示第

t

個子問題的噪聲。

2.3 隨機分塊策略

基于隨機分塊的SSC 將原問題的數據集劃分成幾個子集分別求解稀疏系數矩陣。對原問題的數據集的劃分采用如下的隨機分塊策略進行：

設

idx

是1 到

N

的

N

個數構成的隨機序列，

idx

是指標集，表示每個數據點在數據集

Y

中所處的列指標；設

k

是每次從數據集中選擇的數據比例數。隨機分塊策略是每次從指標集

idx

中選擇連續(xù)的

k

*

N

個數據構成一個指標集子集，然后根據指標集子集從數據集中獲得子問題的子數據集。隨機分塊策略具體操作如下：

其中：

m

表示每次前進的步長；

Y

表示第

t

個子問題的數據集；

a

表示子集

Y

的指標集的開始位置；

b

表示子集

Y

的指標集的結束位置；函數mod(

i

，

N

)是求余函數。

2.4 子問題系數矩陣的擴充策略

求得每個子問題的系數矩陣后，需要將

T

個子問題的系數矩陣進行整合。首先將每個子問題的(

k

*

N

)*(

k

*

N

)維系數矩陣

C

擴充為

N

*

N

維的系數矩陣

C′

；然后將子問題系數矩陣進行疊加得到

C′′

；最后，將疊加后的系數矩陣的每個單元值除以該單元對應的兩個數據點被同時分配相同子集的次數，從而得到最終的系數矩陣

C

。

圖3 系數矩陣的擴充Fig.3 Expansion of coefficient matrix

圖4 系數矩陣整合Fig.4 Coefficient matrix integration

2.5 交替方向乘子算法求解子問題

使用交替方向乘子法（ADMM）可以求解拉格朗日函數式（9）的最小值，從而求得系數矩陣

C

。

算法2 交替方向乘子算法。

輸入 數據集

Y

。輸出 系數矩陣

C

。

步驟1 設置參數：

步驟2 初始化變量

i

=0，

A

=0，

C

=0，

δ

=0，

E

=0，

Δ

=0

步驟3 重復以下步驟直到算法收斂或迭代達到最大次數：

步驟3.1 固定(

C

)，

E

)，

δ

)，

Δ

))，通過更新

A

極小化

L

：

其中：

P

=[

Y

，

I

/

λ

]，

C

=[

C

；

λE

]步驟3.2 固定(

A

)，

E

)，

δ

)，

Δ

))，通過極小化

L

更新

C

：

其中：Γ=min(|

v

|-

η

，0)*sign(

v

)步驟3.3 固定(

A

)，

C

)，

δ

)，

Δ

))，通過極小化

L

更新

E

：

步驟3.4 固定(

C

)，

E

)，

A

))，更新(

δ

，

Δ

)：

步驟3.5

m

=

m

+1

2.6 完整算法

式（12）的求解分兩階段迭代進行：第一階段，對數據集進行2.2 節(jié)中的隨機分塊操作，將原問題轉化為

T

個子問題；第二階段，根據SSC 算法求出當前子問題的系數矩陣，然后將

T

個系數矩陣進行根據2.4 節(jié)的擴充策略進行整合，最后對整合后的系數矩陣進行聚類。具體算法如下：

算法3 基于隨機分塊的SSC。

輸入

D

×

N

的矩陣

Y

，參數

m

，

α

，

α

，

α

，

k

，

T

。

輸出 聚類結果。

步驟1 將原數據按照2.3 節(jié)的隨機分塊策略隨機劃分成

T

個子集

Y

，

Y

，…，

Y

，從而將原問題劃分為

T

個子問題；步驟2.1 針對每個子問題的數據矩陣

Y

，執(zhí)行算法2，獲得每個子問題的系數矩陣

C

；步驟2.2 將每個子問題的系數矩陣

C

按照2.4 節(jié)的擴充策略，擴充成

N

×

N

維的系數矩陣

C

′；步驟3 將

T

個系數矩陣

C

′進行疊加，疊加之后，每個單元值除以該單元對應的兩個數據點被同時分配相同子集的次數，從而得到原問題的系數矩陣

C

；步驟4 采用式（10）構建相似矩陣

W

；

步驟5 采用算法1，進行SC。

3 實驗與結果分析

實驗中，針對不同的聚類目標數量，首先，對不同的選點比例和子空間數進行實驗，探究選點比例與子空間數對聚類誤差的影響；然后選擇最優(yōu)的選點比例與子空間數，將本文提出的方法與稀疏子空間聚類（SSC）、隨機稀疏子空間聚類（SCOMP-C）、基于正交匹配追蹤的稀疏子空間聚類（SSCOMP）、譜聚類（SC）和

K

均值（

K

-Means）進行比較。

3.1 數據集

本文使用Extended Yale B 人臉數據集進行實驗。Extended Yale B 數據中每張圖像的像素均為192*168，總共有38 個人，每個人有64 張在不同光照條件下的正面人臉圖像。將所有人臉圖像的大小調整為16×14，并將每張圖像轉換成一個224 維向量。因此，被聚類的每個數據點有224 維，屬于高維聚類問題。圖5 展示了人臉數據集中10 個人在不同光照條件下的部分圖片。

圖5 人臉數據集的部分圖片Fig.5 Part images in face dataset

3.2 評價指標

為了評估聚類算法的性能，采用了4 個度量指標：子空間聚類誤差（Subspace clustering error）、互信息（Mutual information）、蘭德指數（Rand index）和熵（Entropy），它們的定義分別為式（13）～（16）：

其中：

X

是數據點的一種劃分；

Y

是數據點的另一個劃分；

n

為數據點的數量；

TP

為劃分正確的數據點數量；

TN

為劃分錯誤的數據點數量。

子空間聚類誤差用于衡量聚類準確率，聚類誤差越小越好；互信息、蘭德指數均用于衡量數據分布的吻合程度，取值范圍為[0，1]，其值越大越好；熵用于衡量變量的不確定程度，值越小越好。

3.3 實驗結果與分析

算法3 中的三個參數

α

、

α

、

α

均設置為20，

m

=150，

k

表示選點比例，

T

表示子問題數。為了探索算法針對不同目標數的性能，實驗分別對不同的聚類目標數：

Subjects

∈{2，3，4，5，6，7}進行實驗，此時，數據矩陣

Y

的大小分別為224 ×(64 ×

Subjects

)。表1 展示了當子問題中數據點的數量按照比例選擇時，選點的比例與子問題的數量對實驗結果中的聚類誤差的影響。其中，

T

∈{5，6，7，8，9} 表示子問題的個數，

k

∈{0.7，0.75，0.8，0.85，0.9}表示選點的比例，黑體字表示最優(yōu)項。在

Subjects

∈{2，3，4，5，6，7}的實驗中，無論

k

，

T

取何值時，效果均優(yōu)于SSC。當

k

=0.85 時的聚類誤差幾乎都小于其他選點比例的聚類誤差，且隨著

T

的增加，聚類誤差逐漸降低，而后趨于平穩(wěn)。故本文按照

k

=0.85 的比例選擇每個子問題的點數，子問題數為

T

=8。

表1 子問題數與選擇數據點的比例對聚類誤差的影響Tab 1 Influence of ratio of number of sub-questions to selected data points on clustering error

表2 展示了當

k

=0.85，

T

=8 時，本文方法在人臉數據集上與SSC、SCOMP-C、SSCOMP、SC 和

K

-Means 算法進行比較的實驗的結果，其中黑體字表示最優(yōu)項?？梢园l(fā)現：在

Subjects

∈{2，3，4，5，6，7}時，本文方法的聚類誤差和熵均比其他對比方法小，而互信息和蘭德指數相較于其他對比方法大。其中，相較于5 種對比方法中的最優(yōu)方法，聚類誤差平均降低了3.12 個百分點，熵平均降低了6 個百分點，互信息提升4 個百分點，蘭德指數提升2 個百分點。說明與其他算法相比，結合了隨機分塊策略與擴充的SSC 算法顯著優(yōu)于其他5 種方法。

表2 Extended Yale B數據集中不同數量對象的人臉圖像的5種聚類評估（k=0.85，T=8）Tab 2 Five clustering evaluations of face images with different numbers of objects in Extended Yale B dataset（k=0.85，T=8）

4 結語

本文提出了一種基于隨機分塊的SSC 方法，每次隨機選擇固定數量的點，將原問題轉換為

T

個子問題進行求解，將原優(yōu)化問題重新表述為一組小規(guī)模子問題上的聚類問題。還探索了選點比例以及子問題數對實驗結果的影響。在人臉數據集上的實驗結果表明，本文方法顯著優(yōu)于其他5 種方法。