李凱，張可心

1 引言

近年來，隨著信息技術、計算機網(wǎng)絡與人工智能技術的不斷發(fā)展，在實際問題中產(chǎn)生了大量高維數(shù)據(jù)，如何對這些數(shù)據(jù)進行聚類卻遇到了很大的挑戰(zhàn). 盡管人們提出了一些不同的聚類算法，但由于高維數(shù)據(jù)的特殊性，使得傳統(tǒng)聚類算法并不能直接應用于這些數(shù)據(jù)，為此，人們對高維數(shù)據(jù)的聚類進行了研究，其中方法之一是維數(shù)約簡技術，該方法主要由降維和聚類兩個獨立的過程構成，且每個過程對聚類結果將會產(chǎn)生一定的影響，也就是說，利用該方法獲得的嵌入特征對于聚類來說并不一定是最優(yōu)的，且使得具有區(qū)分能力的信息丟失. 關于此問題，一些學者曾指出，若使用前幾個主成分對數(shù)據(jù)聚類，則將破壞原數(shù)據(jù)的聚類結構［1］. 之后，人們提出了變量選擇方法，較好地解決了降維和聚類過程獨立的問題. 最近，Zhao等人［2］提出了基于正則項的高斯混合模型子空間聚類，此方法將聚類和尋找簇的子空間同時進行處理，進一步提高了子空間聚類的性能. Peng 等人［3］為了獲取不同形狀與大小的子空間，將權向量的負信息熵引入到擴展的高斯混合模型中，提出了一種基于熵的高斯混合模型的子空間聚類方法，然而該方法只考慮了信息熵. 我們知道，信息熵是結構α-熵［4］的特例，特別是，對于結構α-熵中參數(shù)α的不同取值，則其對應于不同的熵，例如，當α趨近于1時，結構α-熵變?yōu)樾畔㈧?；當?2 時，則結構α-熵為平方熵. 另外，當α=2 時，基于結構α-熵的最小化準則等于最近鄰方法的錯誤概率. 以上表明，將基于權向量的信息熵作為懲罰項并不總是獲得較好的聚類結果. 針對結構α-熵，Li 等人［5］提出了最小熵的聚類方法，并將其應用于基因表達分析中，Nicholas 等人［6］提出了基于結構α-熵度量的點集配準，并且通過結構α-熵中參數(shù)控制求解的類型.

為此，本文通過擴展信息熵，研究了結構α-熵的加權高斯混合模型的子空間聚類.

2 相關工作

子空間聚類是指將數(shù)據(jù)劃分為不同的子空間或簇，并且尋求數(shù)據(jù)的多個簇結構. 通常，子空間聚類可以分為四種類型，下面對其進行簡介. 基于統(tǒng)計的方法將數(shù)據(jù)視為獨立抽取且服從高斯混合模型的樣本，子空間聚類問題被轉(zhuǎn)化為模型參數(shù)估計，可使用EM（Expectation Maximization）算法或最大似然方法估計相應的參數(shù)［3，7］. 由于高斯混合模型具有較強的概率解釋以及對噪聲魯棒性等優(yōu)點，因此，該方法獲得了較廣泛的應用［8］，然而，對于傳統(tǒng)的高斯混合模型，當面對高維數(shù)據(jù)的聚類時，由于需要估計大量參數(shù)，以及維數(shù)的逐漸增大，則極大似然估計問題很快成為不適用的方法. 為此，人們通過修改目標函數(shù)或?qū)f(xié)方差矩陣加以約束，提出了基于懲罰項的高斯混合模型的子空間聚類［2］. 基于代數(shù)的方法包括兩種形式，一種是矩陣分解方法［9，10］，通過對數(shù)據(jù)矩陣分解達到數(shù)據(jù)分割的目的，其缺陷是對數(shù)據(jù)噪聲和異常數(shù)據(jù)較為敏感；另一種是廣義主成分分析法［11］，它主要使用多項式擬合數(shù)據(jù)，但由于數(shù)據(jù)中存在噪聲，因此，該方法的實現(xiàn)較為困難，且對高維數(shù)據(jù)的處理代價較高. 基于迭代的方法將樣本分配給子空間，并利用迭代技術更新子空間的簇，從而實現(xiàn)對數(shù)據(jù)的劃分［13，14］. 此類方法可劃分為硬子空間聚類和軟子空間聚類. 硬子空間聚類通過使用啟發(fā)式準則，采取自頂向下或自底向上的搜索策略，從所有特征中尋找簇所在的子空間.軟子空間聚類通過分配特征權值確定簇所在的子空間，包括模糊加權子空間聚類［15~17］和熵加權子空間聚類［3，18，19］. 基于譜聚類的方法是將譜聚類算法作為框架，通過學習一個親和矩陣找到數(shù)據(jù)的低維嵌入，并使用傳統(tǒng)的聚類算法對低維數(shù)據(jù)聚類的一種方法. 親和矩陣可以使用高斯核、局部信息或全局信息進行構造［20，21］. 最近，一些學者提出了對角為分塊矩陣表示的子空間聚類以及復雜噪聲下的子空間聚類，統(tǒng)一了現(xiàn)有的一些子空間聚類方法［22，23］．

3 結構α-熵的加權高斯混合子空間聚類模型

假設樣本集為X={x1,x2,…,xn}，其中xk?Rp(k=1,2,…,n)，且xk是由c個高斯分量組成的混合密度中抽取的樣本，概率密度函數(shù)如式（1）所示.

其中βi、Vi和∑i分別為第i個分量的混合系數(shù)、均值向量和協(xié)方差矩陣；f(xk|Vi,Σi)為第i個分量的高斯密度函數(shù). 為了解決高維數(shù)據(jù)的子空間聚類，Peng等人［3］對高斯分量的協(xié)方差矩陣特例化，如式（2）所示.

為方便起見，令Θ={(βi,Vi,σi2,wi)|1 ≤i≤c}. 為了估計Θ中的 參數(shù)，通過 最小 化KL 散度［3］，從而 獲得式（4）：

其中uk=(u1k,u2k,…,uck)是模糊隸屬值組成的向量. 為了便于表達，下面給出了簇結構α-熵與聚類結構α-熵的定義.

定義1 設簇i的權向量為wi=(wi1,wi2,…,wip)，則簇結構α-熵由式（5）計算.

其中α≥0,α≠1.

定義2 聚類結構α-熵定義為所有簇結構α-熵的加權和，并由式（6）計算.

其中hi為加權系數(shù).

可以看到，當α→1 時，則簇結構α-熵即為模糊熵，聚類結構α-熵為聚類模糊熵.

將聚類結構α-熵引入式（4），并結合約束條件，從而獲得了結構α-熵的加權高斯混合子空間聚類模型，如式（7）所示.

由式（7）可知，通過引入結構α-熵，并利用最小化KL 散度以及最大化聚類結構α-熵，使得算法能夠獲取質(zhì)量較高的簇，權向量的聚類結構α-熵值越大，則越表明有更多的維度用于發(fā)現(xiàn)聚類中的簇，從而得到更好的子空間聚類結構．

4 結構α-熵的加權高斯混合模型子空間聚類算法

針對式（7），構造拉格朗日函數(shù)，如式（8）所示.

其中ξ為拉格朗日乘子，λ和η分別是由拉格朗日乘子λ1,λ2,…,λc和η1,η2,…,ηn構成的向量.

將式（8）分別對Vij、σi和βi求偏導，并令其等于0，從而得到式（9）~（11）.

對于隸屬度uik和特征權值wij的求解，下面以定理形式給出.

定理1 給定混合系數(shù)βi與權值向量wi=(wi1,wi2,…,wip)，則式（8）取極值時滿足的必要條件如式（12）所示.

定理2 給定混合系數(shù)βi以及隸屬度uik，則式（8）取極值時滿足的必要條件如式（13）所示.

下面給出結構α-熵的加權高斯混合模型的子空間聚類算法SEWMM，如算法1.

可以看到，算法SEWMM 包括兩種類型的參數(shù)，一種是具有約束的參數(shù)，例如wij、βi和uik，另一種是不具有約束的參數(shù)，例如σi和Vi．為了表明算法的收斂性，對于有約束參數(shù)，將式（8）關于wij、βi和uik求二階偏導數(shù)，分別得到式（14）~（16）.

由α>0 與α≠1 知，式（14）大于零，且式（15）與（16）也大于零.

對于無約束參數(shù)σi和Vi，它們?yōu)闃O小值的證明可參考EM算法收斂性證明方法.

由以上結果可知，對于第t次迭代，則有

J(uk(t),βi(t),Vi(t),σ2i(t),wij(t))≤

J(uk(t-1),βi(t-1),Vi(t-1),σ2i(t-1),wij(t-1))

此式表明函數(shù)J(uk(t),βi(t),Vi(t),σ2i(t),wij(t))關于變量t是一個非增函數(shù)，從而可知算法是收斂的. 假設算法迭代T次收斂，由算法可知，其時間復雜性為O（npTc）.

5 實驗研究

為了驗證算法SEWMM 的有效性，實驗選取了UCI標準數(shù)據(jù)集與圖像數(shù)據(jù)集，聚類評價指標分別為正確率（Accuracy，Acc）、蘭德指數(shù)（Rand Index，RI）和標準互信息（Normalized Mutual Information，NMI），它們的取值范圍均為［0，1］；參數(shù)α的取值范圍為［0.2，25］，δ=10，實驗結果為十次聚類的平均值.

5.1 UCI數(shù)據(jù)集

在UCI 標準數(shù)據(jù)集［24］中，選取了Sonar、WBCD、SPECT Heart、Vehicle、Semeion、Water Treatment Plant（WTP）、Ionosphere、Iris、Mfeat_zer（MFeat 的子數(shù)據(jù)集）和Liver 數(shù)據(jù)集進行了實驗，并與ESSC［25］、FWKM［15］、EWKM［18］、CKS-EWFC-F［26］、PFSCM［14］、kSDC［13］、MoG［23］、RGMM［22］和EWMM［3］算法進行了聚類性能比較，實驗結果如表1 所示，其中每個數(shù)據(jù)集所對應的三行數(shù)值分別為Acc、RI 和NMI 指標. 可以看出，算法SEWMM 在大部分數(shù)據(jù)集上獲得了較好的聚類結果.例如，對于數(shù)據(jù)集Ionosphere、Semeion、Iris、WBCD、Ve?hicle 與Liver ，在選取的三個指標上，提出的算法均獲得了較高值，而在Vehicle 和WBCD 數(shù)據(jù)集的Acc 指標略低于MoG 和EWKM 算法，但其值基本相當. 對于剩余的四個數(shù)據(jù)集，在選取的Acc、RI 和NMI 中的兩個指標都超過了比較的算法，而對于另一指標，提出的算法與獲得較好結果算法的性能也基本相當. 同時，提出的算法在十個數(shù)據(jù)集的聚類性能優(yōu)于EWMM. 以上表明，通過引入結構α-熵懲罰項，提出的算法在Acc、NMI 與RI上優(yōu)于比較的算法.

5.2 圖像數(shù)據(jù)集

本小節(jié)主要選取圖像數(shù)據(jù)集進行實驗和比較，包括BSDS500 圖像與較大規(guī)模圖像數(shù)據(jù)集，實驗中使用的圖像均為彩色圖像轉(zhuǎn)換后的灰度圖像.

5.2.1 BSDS500圖像

針對BSDS500 圖像數(shù)據(jù)集［27］，選取其中的16 幅圖像對提出的算法SEWMM 進行了圖像分割實驗，比較算法分別為NCuts［28］（記為NCuts1）、多尺度NCuts［29］（記為NCuts2）、FLICM［30］、DSFCM-N［31］、FSC［16］、kSDC［13］、CKS-EWFC-F［26］、PFSCM［14］和EWMM［3］. 為了衡量算法的總體性能，在實驗中，將不同算法分別在16幅圖像獲得的Acc、RI 和NMI 指標值進行了平均，實驗結果如圖1 所示. 可以看到，對于選取的所有圖像，在聚類指標Acc 和RI 上，算法SEWMM 均優(yōu)于比較的算法，而在NMI指標上，算法SEWMM 略低于NCust2；另外，我們也看到，在所有三個聚類指標上，提出的算法SEWMM 的指標值都高于算法EWMM.

5.2.2 圖像數(shù)據(jù)集的聚類

本小節(jié)選取CIFAR10［32］、CIFAR100［32］、MNIST［33］、Fashion-MNIST［34］和USPS［35］圖像測試集對提出的算法進行了實驗；同時，選取NMF［36］、SSC［20］、SSC-OMP［37］、LRR［21］、LSR［38］、LRSC［39］、EnSC［40］、CKS-EWFC-F［26］、PFSCM［14］、kSDC［13］、MoG［23］、RGMM［22］和EWMM［3］算法與提出的算法進行了實驗比較. 使用PCA 方法對灰度圖像進行特征提取，其中CIFAR-10、CIFAR-100、MNIST 與Fashion-MNIST 圖像數(shù)據(jù)的特征數(shù)均置為500；對于USPS 圖像數(shù)據(jù)直接使用所有的灰度值，實驗結果如表2所示，其中每個數(shù)據(jù)集所對應的三行數(shù)值分別為Acc、NMI和RI指標.

由表2 可知，對于選取的圖像數(shù)據(jù)集，算法SEWMM 的聚類指標值優(yōu)于EWMM 算法；與其他聚類算法相比，總體上來說，算法SEWMM 的聚類性能優(yōu)于所比較的算法，例如，對于Fashion-MNIST 數(shù)據(jù)集，算法SEWMM 的Acc、NMI與RI指標值分別為0.5880、0.6139和0.8836，而EnSC 算法的相應指標值分別為0.5777、0.6087 和0.8935，可以看到，提出的算法在Acc 和NMI兩個指標均獲得了較高值，而EnSC在RI指標上獲得了較高值，但SEWMM 與EnSC 兩種算法的RI 指標值相差幅度不大. 總之，在提出的算法中，通過引入結構α-熵，調(diào)整參數(shù)α的取值，提出的算法能夠獲得更好的聚類性能.

圖1 圖像分割實驗結果

表1 不同算法在UCI數(shù)據(jù)集上的聚類性能比較

表2 不同算法對圖像數(shù)據(jù)集的聚類性能比較

6 結論

本文在定義簇結構熵與聚類結構熵的基礎上，將權向量的負結構α-熵引入到高斯混合模型中，提出了結構α-熵的加權高斯混合模型的子空間聚類算法SEWMM. 通過選取聚類正確率Acc、蘭德指數(shù)RI 與標準互信息NMI 評價指標，在UCI 數(shù)據(jù)集與圖像數(shù)據(jù)集上，對提出的算法進行了實驗研究. 實驗結果表明，與已有的子空間聚類算法相比，算法SEWMM 對數(shù)據(jù)的聚類效果更好. 同時，算法SEWMM 的提出也為大數(shù)據(jù)背景下數(shù)據(jù)的聚類提供了一種新方法.