汪志遠(yuǎn)，降愛(ài)蓮，奧斯曼·穆罕默德

（太原理工大學(xué)信息與計(jì)算機(jī)學(xué)院，山西晉中 030600）

（*通信作者電子郵箱ailianjiang@126.com）

0 引言

各種智能電子設(shè)備和信息系統(tǒng)的廣泛使用產(chǎn)生和收集了大量的高維無(wú)標(biāo)簽數(shù)據(jù)。利用相應(yīng)的機(jī)器學(xué)習(xí)算法對(duì)這些數(shù)據(jù)進(jìn)行處理和分析，可以發(fā)掘數(shù)據(jù)的潛在價(jià)值。在模式識(shí)別與機(jī)器學(xué)習(xí)研究領(lǐng)域中，對(duì)于機(jī)器學(xué)習(xí)算法而言，樣本數(shù)據(jù)集是訓(xùn)練模型的重要前提，但是收集到的原始數(shù)據(jù)通常含有大量的冗余特征，導(dǎo)致其并不適合直接被使用。冗余特征不必要地增加了數(shù)據(jù)的維數(shù)，降低了訓(xùn)練性能［1］。如果不剔除數(shù)據(jù)中的冗余特征，將會(huì)導(dǎo)致機(jī)器學(xué)習(xí)模型的訓(xùn)練時(shí)間變長(zhǎng)，訓(xùn)練后得到的預(yù)測(cè)模型泛化能力差，甚至因遭遇維數(shù)災(zāi)難而使訓(xùn)練無(wú)法進(jìn)行。文獻(xiàn)［2］表明，去除冗余特征可以明顯地提升訓(xùn)練效率。

特征選擇是一種有效的數(shù)據(jù)降維方法［3］，它可以選出數(shù)據(jù)中的重要特征，剔除不重要的冗余特征，從而得到更加低維的數(shù)據(jù)。數(shù)據(jù)維數(shù)降低，可以減少機(jī)器學(xué)習(xí)模型的訓(xùn)練時(shí)間，提高模型訓(xùn)練效率［4］。根據(jù)學(xué)習(xí)任務(wù)類(lèi)型的不同，特征選擇方法分為有監(jiān)督特征選擇方法和無(wú)監(jiān)督特征選擇方法兩大類(lèi)［5］。有監(jiān)督特征選擇方法依據(jù)特征與標(biāo)簽之間的相關(guān)性來(lái)選出重要的特征子集，因?yàn)橹匾卣髋c標(biāo)簽之間的相關(guān)性更強(qiáng)。然而，并非所有的數(shù)據(jù)集都帶有類(lèi)別標(biāo)簽信息，數(shù)據(jù)無(wú)標(biāo)簽使得有監(jiān)督特征選擇方法不再適用，也使得特征選擇變得更加困難［6-7］。

較早提出的無(wú)監(jiān)督特征選擇方法，如最小化方差法［8］和Trace Ratio 方法［9］，這些方法單獨(dú)計(jì)算每個(gè)特征的分?jǐn)?shù)，按分?jǐn)?shù)排名選出特征，此類(lèi)方法評(píng)價(jià)標(biāo)準(zhǔn)單一，對(duì)數(shù)據(jù)的解釋能力較差。之后發(fā)展出基于譜分析技術(shù)［10］的無(wú)監(jiān)督特征選擇方法，此類(lèi)方法通過(guò)對(duì)鄰接圖拉普拉斯矩陣進(jìn)行譜分解，利用關(guān)聯(lián)矩陣的特征值度量各個(gè)特征的重要性，但是該方法在處理高維數(shù)據(jù)時(shí)面臨計(jì)算量過(guò)大的問(wèn)題。目前，正則回歸也被應(yīng)用到特征選擇，Zheng 等［11］提出的自步正則化無(wú)監(jiān)督特征選擇方法（Unsupervised Feature Selection by Self-Paced Learning Regularization，UFS_SP）和劉艷芳等［12］提出的鄰域保持學(xué)習(xí)特征選擇方法（Neighborhood Preserving Learning Feature Selection，NPLFS）將特征選擇問(wèn)題建模為損失函數(shù)最小化問(wèn)題，對(duì)權(quán)重矩陣施加正則約束，表現(xiàn)出較好的魯棒性，但是現(xiàn)有的正則特征選擇方法優(yōu)化困難，計(jì)算復(fù)雜度較高。

正則自表示（Regularized Self-Representation，RSR）方法［13］首次提出特征自表示性質(zhì)，即高維數(shù)據(jù)的每個(gè)特征可由全部特征線(xiàn)性近似表示，該性質(zhì)考慮了特征間的相關(guān)性，具有較強(qiáng)的數(shù)據(jù)解釋能力，但該理論也存在不足之處，在目標(biāo)函數(shù)優(yōu)化時(shí)，特征權(quán)重容易向自身傾斜，導(dǎo)致無(wú)法合理地為特征分配權(quán)重。其他的基于自表示性質(zhì)的特征選擇方法均無(wú)法避免自表示性質(zhì)的缺陷。為此，本文提出特征互表示性質(zhì)，即高維數(shù)據(jù)中的每個(gè)特征可由除該特征之外的其他特征線(xiàn)性近似表示，而不是由全體特征線(xiàn)性近似表示，這克服了特征權(quán)重容易向自身傾斜的缺點(diǎn)。然后，基于特征互表示性質(zhì)，提出一種新的正則化無(wú)監(jiān)督特征選擇方法，該方法能夠有效提升數(shù)據(jù)聚類(lèi)準(zhǔn)確率，降低數(shù)據(jù)冗余率，并且計(jì)算復(fù)雜度較低。

1 特征互表示性質(zhì)

假定X是數(shù)據(jù)矩陣，X∈Rm×n，m是樣本數(shù)量，n是特征數(shù)量，fi代表X的第i個(gè)特征，則X可以表示為特征的集合：X={f1，f2，…，fn}。

高維數(shù)據(jù)中的每個(gè)特征可以由數(shù)據(jù)中的其他特征線(xiàn)性近似表示，特征之間存在相關(guān)性，因此可以很好地互相近似表示，把高維數(shù)據(jù)所滿(mǎn)足的這一數(shù)學(xué)性質(zhì)稱(chēng)為特征互表示性質(zhì)。利用特征互表示性質(zhì)，數(shù)據(jù)矩陣X中的每一個(gè)特征fi可形式化表示為：

式中：wj是第j個(gè)特征的權(quán)重系數(shù)；ei為殘差向量，代表特征fi重構(gòu)前后的殘差。本文期望重構(gòu)后的特征可以很好地近似表示原特征，所以殘差應(yīng)當(dāng)盡可能小，使用向量的l2-范數(shù)的平方度量殘差大小，將損失函數(shù)定義為：

2 特征選擇模型及其優(yōu)化算法

2.1 正則互表示無(wú)監(jiān)督特征選擇模型

通過(guò)將X={f1，f2，…，fn}中的每一個(gè)特征進(jìn)行重構(gòu)，可得如下結(jié)果：

式中：Wo為權(quán)重矩陣，上標(biāo)o是指權(quán)重矩陣W的對(duì)角線(xiàn)元素都為0，這是因?yàn)樘卣鞑粎⑴c自身的線(xiàn)性近似表示，所以權(quán)重系數(shù)為0；E為殘差矩陣，表示原始數(shù)據(jù)X重構(gòu)前后的殘差。

從向量的角度分析，殘差矩陣E由殘差向量的有序集合{e1，e2，e3，…，en}組成，每個(gè)特征重構(gòu)前后的殘差使用度量。將殘差度量標(biāo)準(zhǔn)由向量推廣到矩陣時(shí)，可以使用度量原始數(shù)據(jù)X重構(gòu)前后的殘差大小。本文期望重構(gòu)后的數(shù)據(jù)XWo能夠很好地近似表示原始數(shù)據(jù)X，因此殘差越小越好，對(duì)應(yīng)的目標(biāo)函數(shù)為：

目標(biāo)函數(shù)式（3）的優(yōu)化問(wèn)題屬于無(wú)偏估計(jì)回歸問(wèn)題，在無(wú)偏估計(jì)回歸問(wèn)題中，當(dāng)數(shù)據(jù)矩陣X不是列滿(mǎn)秩的，或者某些列之間線(xiàn)性相關(guān)性比較強(qiáng)時(shí)，得到的最優(yōu)解將會(huì)不穩(wěn)定。為了解決這個(gè)問(wèn)題，在目標(biāo)函數(shù)中加入一個(gè)正則項(xiàng)對(duì)權(quán)重矩陣的解空間進(jìn)行約束，使計(jì)算出的最優(yōu)解更穩(wěn)定?；谏鲜龇治?，改進(jìn)后的目標(biāo)函數(shù)為：

本文把包含權(quán)重矩陣正則項(xiàng)的目標(biāo)函數(shù)式（4）稱(chēng)為正則互表示（Regularized Mutual Representation，RMR）無(wú)監(jiān)督特征選擇模型。

2.2 分治-嶺回歸優(yōu)化算法

針對(duì)提出的RMR 特征選擇模型，為之設(shè)計(jì)一種高效的優(yōu)化算法，該算法結(jié)合了分治算法［14］和嶺回歸［15］優(yōu)化算法，本文稱(chēng)之為分治-嶺回歸優(yōu)化算法。本節(jié)首先證明以下定理。

定理1給定如下兩個(gè)優(yōu)化問(wèn)題的目標(biāo)函數(shù)：

其中：fi是X的第i列；是Wo的第i列。則整體優(yōu)化問(wèn)題的最優(yōu)解可通過(guò)計(jì)算所有嶺回歸子優(yōu)化問(wèn)題的最優(yōu)解得到。

證明 將數(shù)據(jù)矩陣X按列數(shù)分解為特征的有序集合{f1，f2，…，fn}，將權(quán)重矩陣按列數(shù)分解為權(quán)重向量的有序集合{ω1，ω2，…，ωn}，則有：

因?yàn)榫仃嚨腇robenius 范數(shù)的平方等于矩陣中所有列向量l2-范數(shù)平方的和，因此上式中可繼續(xù)變形為：

至此可知，只要使得分解后的每個(gè)嶺回歸子優(yōu)化問(wèn)題都取得最優(yōu)解，即可保證整體優(yōu)化問(wèn)題取得最優(yōu)解。

定理1證畢

分治-嶺回歸優(yōu)化算法首先利用分治算法的思想，將整體優(yōu)化問(wèn)題分解為若干個(gè)子優(yōu)化問(wèn)題；然后針對(duì)每個(gè)子優(yōu)化問(wèn)題利用嶺回歸優(yōu)化算法計(jì)算最優(yōu)解；最后將各個(gè)子優(yōu)化問(wèn)題的最優(yōu)解進(jìn)行整合，得到整體優(yōu)化問(wèn)題的最優(yōu)解。

分治-嶺回歸優(yōu)化算法的具體計(jì)算步驟如下。

首先，將RMR 模型的整體優(yōu)化問(wèn)題按照數(shù)據(jù)矩陣X的每個(gè)特征，分解為如下的n個(gè)嶺回歸子優(yōu)化問(wèn)題：

式中：i=1，2，…，n。第i個(gè)子優(yōu)化問(wèn)題的最優(yōu)解用于重構(gòu)特征fi，使得重構(gòu)前后的誤差最小的第i個(gè)元素為0，因?yàn)樘卣鱢i不參與自身的線(xiàn)性近似表示。

式（6）中的Xi是由X去掉特征fi得到，式（6）中的由式（5）中的ωi刪除第i個(gè)元素得到。目標(biāo)函數(shù)式（6）的優(yōu)化問(wèn)題是嶺回歸優(yōu)化問(wèn)題，該優(yōu)化問(wèn)題的損失函數(shù)以及推導(dǎo)過(guò)程如下：

由于嶺回歸優(yōu)化問(wèn)題的損失函數(shù)是一個(gè)光滑的凸函數(shù)，因此可以在導(dǎo)數(shù)為0 處求得損失函數(shù)的最優(yōu)解，即能夠使殘差L(ei)最小的解析解。最優(yōu)解的推導(dǎo)過(guò)程如下：

令L(ei)對(duì)求偏導(dǎo)，得：

式中：I是單位矩陣；λ是正則項(xiàng)參數(shù)，且λ＞0。

總結(jié)上述分治-嶺回歸優(yōu)化算法的具體計(jì)算步驟，得到RMR特征選擇方法的計(jì)算框架1。

輸入 數(shù)據(jù)集X，正則項(xiàng)參數(shù)λ，特征選擇數(shù)量k；

輸出 特征子集S。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)中使用的數(shù)據(jù)集來(lái)源于UCI 標(biāo)準(zhǔn)數(shù)據(jù)集，共5 個(gè)數(shù)據(jù)集，關(guān)于這些數(shù)據(jù)集的詳細(xì)描述信息請(qǐng)參考表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集Tab.1 Experimental Datasets

表1中的Iris20 數(shù)據(jù)集為合成數(shù)據(jù)集，它是由UCI 標(biāo)準(zhǔn)數(shù)據(jù)集Iris 擴(kuò)展而成，前4 列是Iris 數(shù)據(jù)集初始數(shù)據(jù)，后16 列數(shù)據(jù)是由前4 列進(jìn)行隨機(jī)線(xiàn)性組合得到，線(xiàn)性組合系數(shù)和為1，并在后16列數(shù)據(jù)中加入高斯白噪聲。

3.2 評(píng)價(jià)指標(biāo)

3.2.1 聚類(lèi)準(zhǔn)確率

使用K-Means 算法［16］對(duì)數(shù)據(jù)進(jìn)行聚類(lèi)，并計(jì)算數(shù)據(jù)樣本聚類(lèi)之后的準(zhǔn)確率，聚類(lèi)準(zhǔn)確率（ACCuracy of clustering，ACC）的值越大說(shuō)明聚類(lèi)結(jié)果越好。ACC計(jì)算公式如下：

式中：m是樣本個(gè)數(shù)；li是第i個(gè)樣本的實(shí)際標(biāo)簽；map(ri)是第i個(gè)樣本的聚簇標(biāo)簽，該函數(shù)使用Kuhn-Munkres 算法計(jì)算樣本的聚簇標(biāo)簽；函數(shù)f(a，b)用于判斷標(biāo)簽a和標(biāo)簽b的值是否相等，若相等則函數(shù)值為1，不相等則函數(shù)值為0。

3.2.2 歸一化互信息

歸一化互信息（Normalized Mutual Information，NMI）是評(píng)價(jià)聚類(lèi)結(jié)果好壞的常用指標(biāo)之一，用于度量聚簇標(biāo)簽向量與實(shí)際標(biāo)簽向量的一致程度，NMI 值越大說(shuō)明聚類(lèi)結(jié)果越好。NMI計(jì)算公式如下：

式中：p是聚簇標(biāo)簽向量；q是實(shí)際標(biāo)簽向量；I(p，q)是向量p與q之間的互信息；H(p)和H(q)分別是p和q的信息熵。

3.2.3 冗余率

冗余率（Redundancy rate，Rr）用于度量數(shù)據(jù)的特征之間是否具有較強(qiáng)的相關(guān)性，相關(guān)性越強(qiáng)說(shuō)明數(shù)據(jù)冗余程度越高，因此冗余率越小越好。Rr計(jì)算公式如下：

式中：S是特征子集；n是特征子集的特征數(shù)量；βi，j是特征fi和特征fj的皮爾遜相關(guān)系數(shù)。

3.3 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證所提出的RMR 無(wú)監(jiān)督特征選擇方法的有效性和高效性，實(shí)驗(yàn)中使用另外四種無(wú)監(jiān)督特征選擇方法用于對(duì)比，對(duì)比方法分別為經(jīng)典的Laplacian 特征選擇方法［17］、使用了譜分析技術(shù)的非負(fù)判別特征選擇（Nonnegative Discriminative Feature Selection，NDFS）方法［18］、引入了正則約束的RSR 方法和自表示特征選擇（Self-Representation Feature Selection，SR_FS）方法［19］。

每種特征選擇方法從每個(gè)數(shù)據(jù)集中選出9 個(gè)不同維數(shù)的特征子集，選出特征數(shù)量依次是特征總數(shù)量的1/10，2/10，…，9/10，然后取這9 個(gè)不同維數(shù)的特征子集的聚類(lèi)準(zhǔn)確率平均值、歸一化互信息平均值以及冗余率平均值，作為評(píng)價(jià)該特征選擇方法效果優(yōu)劣的三項(xiàng)指標(biāo)。對(duì)于目標(biāo)函數(shù)中有正則項(xiàng)的特征選擇方法，將正則項(xiàng)參數(shù)的值域設(shè)置為｛0.01，0.1，1，10，100｝，對(duì)每個(gè)正則項(xiàng)參數(shù)均進(jìn)行實(shí)驗(yàn)并選取最佳結(jié)果。

另外，針對(duì)聚類(lèi)準(zhǔn)確率這一評(píng)價(jià)指標(biāo)，由于K-Means 聚類(lèi)算法得出的聚類(lèi)準(zhǔn)確率會(huì)受初始質(zhì)心選取的影響，為減少隨機(jī)誤差的影響，提升結(jié)果準(zhǔn)確度，對(duì)每個(gè)特征子集進(jìn)行100 次聚類(lèi)，然后取100 次聚類(lèi)準(zhǔn)確率的平均值作為該特征子集的聚類(lèi)準(zhǔn)確率。

3.4 結(jié)果分析

首先，將本文提出的RMR 方法應(yīng)用在Iris20 合成數(shù)據(jù)集上，因?yàn)镮ris20 數(shù)據(jù)集的后16 列數(shù)據(jù)是由前4 列數(shù)據(jù)組合得到，且加入了一定的噪聲，因此后16 列數(shù)據(jù)是應(yīng)當(dāng)剔除的冗余特征，而前4 列數(shù)據(jù)為特征選擇方法應(yīng)當(dāng)識(shí)別出的重要特征。

圖1 是RMR 方法計(jì)算出的Iris20 特征權(quán)重直方圖，橫軸代表Iris20 數(shù)據(jù)集的20 個(gè)特征，縱軸代表計(jì)算出的各個(gè)特征的權(quán)重。權(quán)重越大，特征越重要，越具有代表性。從圖1 可以直觀地看出，前4個(gè)特征的權(quán)重明顯大于后16個(gè)特征的權(quán)重，這說(shuō)明RMR 方法可以有效地識(shí)別出數(shù)據(jù)集中具有代表性的特征。從表2 的實(shí)驗(yàn)結(jié)果數(shù)據(jù)可以得知，RMR 特征選擇方法與其他四種特征選擇方法相比，其在5 個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上選出的特征子集的平均聚類(lèi)準(zhǔn)確率最大，說(shuō)明RMR 方法對(duì)聚類(lèi)準(zhǔn)確率的提升能力更強(qiáng)。從表3 的實(shí)驗(yàn)結(jié)果數(shù)據(jù)可以看出，RMR 方法選出的特征子集的歸一化互信息NMI 值最大，說(shuō)明RMR 方法選出的特征子集的聚類(lèi)效果更好。無(wú)論是聚類(lèi)準(zhǔn)確率還是歸一化互信息，都是度量聚類(lèi)結(jié)果好壞的常用指標(biāo)，值越大越好。因此從表2 和表3 可以得出相同的結(jié)論，使用RMR 方法對(duì)原始數(shù)據(jù)集進(jìn)行特征選擇，可以選出數(shù)據(jù)中的具有代表性的特征，有效地改善數(shù)據(jù)在聚類(lèi)時(shí)的表現(xiàn)，并且同其他四種對(duì)比方法相比效果更好。

圖1 Iris20特征權(quán)重直方圖Fig.1 Histogram of feature weights of Iris20

表2 聚類(lèi)準(zhǔn)確率對(duì)比 單位：%Tab.2 Comparison of clustering accuracy unit：%

表3 歸一化互信息對(duì)比 單位：%Tab.3 Comparison of normalized mutual information unit：%

從表4中的實(shí)驗(yàn)結(jié)果可知，RMR 方法與另外四種特征選擇方法相比，其所選出的特征子集的冗余率最低，說(shuō)明RMR方法從原始數(shù)據(jù)中選出的特征相關(guān)性較弱，數(shù)據(jù)冗余程度更低。

表4 冗余率對(duì)比 單位：%Tab.4 Comparison of redundancy rate unit：%

RMR 方法選出的特征子集之所以具有較好的聚類(lèi)表現(xiàn)和較低的冗余程度，是因?yàn)镽MR 模型是基于正則互表示性質(zhì)，利用了特征間的相關(guān)性，同時(shí)克服了特征權(quán)重容易向自身傾斜的缺點(diǎn)。RSR方法和SR_FS方法雖然利用了特征間的相關(guān)性，但是忽視了特征權(quán)重容易向自身傾斜的問(wèn)題。NDFS方法結(jié)合譜聚類(lèi)技術(shù)進(jìn)行特征選擇，該方法的效果依賴(lài)于樣本相似性矩陣，容易受其影響。Laplacian 方法沒(méi)有考慮特征間的相關(guān)性，因此無(wú)法有效識(shí)別冗余特征。

在計(jì)算復(fù)雜度方面，RMR 數(shù)學(xué)模型中的誤差項(xiàng)和正則項(xiàng)都是使用矩陣Frobenius 范數(shù)進(jìn)行約束，使用分治算法將矩陣優(yōu)化問(wèn)題轉(zhuǎn)換為若干個(gè)向量?jī)?yōu)化問(wèn)題，如式（5）所示。此時(shí)的向量?jī)?yōu)化問(wèn)題是嶺回歸優(yōu)化問(wèn)題，目標(biāo)函數(shù)中的誤差項(xiàng)和正則項(xiàng)均由向量l2-范數(shù)約束，l2-正則是凸形正則，可以在導(dǎo)數(shù)為0處直接取得使殘差最小的解析解，如式（7）所示，式中：的計(jì)算復(fù)雜度是O(mn2)；求逆運(yùn)算的復(fù)雜度是O(n3)；的復(fù)雜度是O(mn)；矩 陣與向量相乘的復(fù)雜度是O(n2)。考慮到樣本數(shù)量大于特征數(shù)量（即m＞n），所以單個(gè)嶺回歸優(yōu)化的總體漸進(jìn)復(fù)雜度為O(mn2)。因?yàn)檎w優(yōu)化問(wèn)題被分解為n個(gè)嶺回歸子優(yōu)化問(wèn)題，所以RMR 方法的整體優(yōu)化問(wèn)題的漸進(jìn)計(jì)算復(fù)雜度為O(mn3)。RMR 方法計(jì)算特征選擇模型最優(yōu)解的過(guò)程僅相當(dāng)于一次矩陣迭代運(yùn)算，而非多次迭代，而NDFS 方法、RSR 方法以及SR_FS 方法都是采用矩陣多次迭代的方式逼近最優(yōu)解，每一次迭代都會(huì)涉及大量的矩陣運(yùn)算，計(jì)算復(fù)雜度與迭代次數(shù)成正比。因此，RMR 方法具有更低的計(jì)算復(fù)雜度，在計(jì)算性能上更具優(yōu)勢(shì)。

4 結(jié)語(yǔ)

本文研究利用高維無(wú)標(biāo)簽數(shù)據(jù)特征之間的相關(guān)性進(jìn)行特征選擇，通過(guò)在特征選擇時(shí)對(duì)特征權(quán)重施加正則約束，提升了特征選擇結(jié)果的魯棒性，解決了特征權(quán)重分配不合理導(dǎo)致無(wú)法有效識(shí)別冗余特征的問(wèn)題。實(shí)驗(yàn)結(jié)果表明，RMR 方法能夠選出重要特征，減少數(shù)據(jù)冗余，提升聚類(lèi)精度。算法理論復(fù)雜度分析表明，所提方法因使用分治-嶺回歸優(yōu)化而具有較低的計(jì)算復(fù)雜度。RMR 方法也存在不足之處，其未考慮數(shù)據(jù)集的樣本數(shù)量少于特征數(shù)量的情況，未來(lái)研究可考慮高維小樣本數(shù)據(jù)情況下如何改進(jìn)。