李凱，張可心

1 引言

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

為此，本文通過擴(kuò)展信息熵，研究了結(jié)構(gòu)α-熵的加權(quán)高斯混合模型的子空間聚類.

2 相關(guān)工作

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

3 結(jié)構(gòu)α-熵的加權(quán)高斯混合子空間聚類模型

假設(shè)樣本集為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)是模糊隸屬值組成的向量. 為了便于表達(dá)，下面給出了簇結(jié)構(gòu)α-熵與聚類結(jié)構(gòu)α-熵的定義.

定義1 設(shè)簇i的權(quán)向量為wi=(wi1,wi2,…,wip)，則簇結(jié)構(gòu)α-熵由式（5）計算.

其中α≥0,α≠1.

定義2 聚類結(jié)構(gòu)α-熵定義為所有簇結(jié)構(gòu)α-熵的加權(quán)和，并由式（6）計算.

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

可以看到，當(dāng)α→1 時，則簇結(jié)構(gòu)α-熵即為模糊熵，聚類結(jié)構(gòu)α-熵為聚類模糊熵.

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

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

4 結(jié)構(gòu)α-熵的加權(quán)高斯混合模型子空間聚類算法

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

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

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

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

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

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

下面給出結(jié)構(gòu)α-熵的加權(quán)高斯混合模型的子空間聚類算法SEWMM，如算法1.

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

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

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

由以上結(jié)果可知，對于第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))關(guān)于變量t是一個非增函數(shù)，從而可知算法是收斂的. 假設(shè)算法迭代T次收斂，由算法可知，其時間復(fù)雜性為O（npTc）.

5 實驗研究

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

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

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

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

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

5.2.1 BSDS500圖像

針對BSDS500 圖像數(shù)據(jù)集［27］，選取其中的16 幅圖像對提出的算法SEWMM 進(jìn)行了圖像分割實驗，比較算法分別為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 指標(biāo)值進(jìn)行了平均，實驗結(jié)果如圖1 所示. 可以看到，對于選取的所有圖像，在聚類指標(biāo)Acc 和RI 上，算法SEWMM 均優(yōu)于比較的算法，而在NMI指標(biāo)上，算法SEWMM 略低于NCust2；另外，我們也看到，在所有三個聚類指標(biāo)上，提出的算法SEWMM 的指標(biāo)值都高于算法EWMM.

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

本小節(jié)選取CIFAR10［32］、CIFAR100［32］、MNIST［33］、Fashion-MNIST［34］和USPS［35］圖像測試集對提出的算法進(jìn)行了實驗；同時，選取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］算法與提出的算法進(jìn)行了實驗比較. 使用PCA 方法對灰度圖像進(jìn)行特征提取，其中CIFAR-10、CIFAR-100、MNIST 與Fashion-MNIST 圖像數(shù)據(jù)的特征數(shù)均置為500；對于USPS 圖像數(shù)據(jù)直接使用所有的灰度值，實驗結(jié)果如表2所示，其中每個數(shù)據(jù)集所對應(yīng)的三行數(shù)值分別為Acc、NMI和RI指標(biāo).

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

圖1 圖像分割實驗結(jié)果

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

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

6 結(jié)論

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