基于一致性和知識粒度的半監(jiān)督特征選擇方法

萬麗娟，錢文彬*，曾武序

（1.江西農(nóng)業(yè)大學(xué) 軟件學(xué)院，江西 南昌 330045；2.江西農(nóng)業(yè)大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，江西 南昌 330045）

0 引言

數(shù)據(jù)挖掘旨在從數(shù)據(jù)信息中獲取規(guī)則和知識，已被應(yīng)用到多個領(lǐng)域。但隨著數(shù)據(jù)信息量的爆發(fā)式增長，“維度災(zāi)難”給高維的數(shù)據(jù)挖掘分析帶來了嚴(yán)峻的挑戰(zhàn)［1-2］。當(dāng)前，特征選擇是對高維數(shù)據(jù)進(jìn)行數(shù)據(jù)預(yù)處理的重要技術(shù)之一［3-4］，并根據(jù)數(shù)據(jù)是否存在類別標(biāo)記可分為監(jiān)督特征選擇、半監(jiān)督特征選擇和無監(jiān)督特征選擇。監(jiān)督特征選擇的數(shù)據(jù)為正確且非空標(biāo)記數(shù)據(jù)［5-6］；無標(biāo)記特征選擇的數(shù)據(jù)都為無標(biāo)記的樣本［7-8］。由于標(biāo)注樣本類別的成本非常昂貴，因此實(shí)際數(shù)據(jù)集中往往含有少量的標(biāo)記數(shù)據(jù)和大量的未標(biāo)記數(shù)據(jù)［9-10］。目前，半監(jiān)督數(shù)據(jù)中僅利用標(biāo)記信息較難精確地完成分類學(xué)習(xí)任務(wù)，此類問題引起了研究者的廣泛關(guān)注［11-12］。

目前，針對半監(jiān)督學(xué)習(xí)的特征選擇方法研究，Razieh等［13］通過拉普拉斯算法結(jié)合正則化和損失函數(shù)方法，提出一種半監(jiān)督特征選擇方法；Shi等［14］結(jié)合自訓(xùn)練和拉普拉斯權(quán)重提出了半監(jiān)督特征選擇方法，其利用多視圖提高分類性能并預(yù)測未標(biāo)記數(shù)據(jù)，從而獲得特征子集；Pang等［15］基于標(biāo)記和特征之間的關(guān)系預(yù)測未標(biāo)記數(shù)據(jù)的標(biāo)記信息，從中選擇滿足條件的特征子集；Lü等［16］結(jié)合自適應(yīng)全局結(jié)構(gòu)學(xué)習(xí)和流行學(xué)習(xí)提出學(xué)習(xí)框架，選取更具有代表性的特征作為特征選擇結(jié)果；Wang等［17］結(jié)合標(biāo)記傳播和半結(jié)構(gòu)化圖學(xué)習(xí)進(jìn)行半監(jiān)督降維，其語義信息從標(biāo)記傳播到學(xué)習(xí)結(jié)構(gòu)圖上的未標(biāo)記樣本，獲取未標(biāo)記數(shù)據(jù)的標(biāo)記信息從而進(jìn)行特征選擇。上述半監(jiān)督特征選擇方法主要是根據(jù)已有標(biāo)記的數(shù)據(jù)訓(xùn)練分類模型，再根據(jù)分類模型預(yù)測未標(biāo)記數(shù)據(jù)的標(biāo)記信息進(jìn)行特征選擇。但是，在現(xiàn)實(shí)生活中因?yàn)榇嬖谥倭康臉?biāo)記數(shù)據(jù)，通過標(biāo)記數(shù)據(jù)訓(xùn)練模型得到的偽標(biāo)記信息往往存在一定的偏差。

粗糙集理論是一種新的處理不確定、不精確、不完備和信息的數(shù)學(xué)工具［18］，目前已成為特征選擇的重要手段之一。在粗糙集中，正域約簡的思想是利用正域下的依賴度獲取分類性能較高的特征子集。Xie等［19］提出基于局部搜索的k-size正域約簡方法，利用局部搜索和正域約簡之間的關(guān)系設(shè)計(jì)的最優(yōu)歸約和局部歸約；Yuan等［20］結(jié)合模糊粗糙集提出了無監(jiān)督學(xué)習(xí)的正域約簡方法，主要考慮是在沒有標(biāo)記信息情況下的混合特征選擇模型。同時(shí)，知識粒度是利用數(shù)據(jù)?；乃枷敕治鎏卣鞯闹匾浴ing等［21］引用增量機(jī)制和知識粒度來處理動態(tài)特征選擇的學(xué)習(xí)任務(wù)；Li等［22］利用知識粒度覆蓋處理無法定義的粒度問題。在上述的方法中，主要處理監(jiān)督數(shù)據(jù)或無監(jiān)督數(shù)據(jù)，較少考慮數(shù)據(jù)中同時(shí)含有標(biāo)記和無標(biāo)記樣本的情況，因此如何使用粒計(jì)算方法處理半監(jiān)督數(shù)據(jù)學(xué)習(xí)任務(wù)并進(jìn)行特征選擇具有重要的研究意義。

為此，本文提出基于一致性和知識粒度的半監(jiān)督特征選擇方法。針對半監(jiān)督數(shù)據(jù)中含有標(biāo)記數(shù)據(jù)和未標(biāo)記數(shù)據(jù)，對于有標(biāo)記的數(shù)據(jù)，為了更好地衡量特征相對于樣本標(biāo)記的重要度，利用正域下的依賴度去度量樣本的一致類；同對于未標(biāo)記數(shù)據(jù)，采用知識粒度對未標(biāo)記樣本進(jìn)行數(shù)據(jù)?；ズ饬刻卣鲗颖究臻g的可區(qū)分性，因此結(jié)合數(shù)據(jù)分布情況提出一種新型的半監(jiān)督特征選擇方法。為了驗(yàn)證該方法的可行性，在公共數(shù)據(jù)集UCI上八個數(shù)據(jù)集上與當(dāng)前四種半監(jiān)督特征選擇對比方法進(jìn)行實(shí)驗(yàn)分析，實(shí)驗(yàn)結(jié)果表明，提出的方法分類性能得到提高，并獲取較為合理的特征選擇結(jié)果。

1 基礎(chǔ)知識

定義1［22］設(shè) DS=(U，A，V，f)為一個決策表。其中，論域?yàn)閁={UL∪UU}，其中UL={x1，x2，…，xl} 為 有 標(biāo) 記 數(shù) 據(jù) ， UU={xl+1，…，xm} 為 未 標(biāo) 記 數(shù) 據(jù) ； 特 征A={C∪D}，其C是條件特征，D是決策特征；V是特征值的集合，在半監(jiān)督學(xué)習(xí)中，存在大量缺少標(biāo)記信息的樣本，因此VD可取空值；f是分類映射函數(shù)，即f：U×C∪D→V。

定義2［23］設(shè) DS=(U，A，V，f)是一個決策表，?x，y∈U。任意特征集B?A，其等價(jià)關(guān)系IND(B)為：

在等價(jià)關(guān)系IND(B)中，將論域U劃分為等價(jià)類，可表示為 U/IND(B)={X1，X2，…，Xn}，其中Xn為在等價(jià)關(guān)系下劃分的等價(jià)類。

定義3［24］設(shè) DS=(U，A，V，f)是一個決策表，?x，y∈U。任意特征集B?A，[x]B表示在等價(jià)關(guān)系IND(B)下包含元素x的等價(jià)類。對于根據(jù)決策特征D劃分的等價(jià)關(guān)系可表示為：U/D= {D1，D2，…，Dq}，其 上 、下近似集定義為：

在決策表DS中，其決策特征的下近似集可以得到條件特征集B的正域：POSB(D)=∪X∈U/D-BX。

定義4［25］設(shè) DS=(U，A，V，f)是一個決策表，?x，y∈U。A={C∪D}，C表示條件特征，D表示決策特征。?B?C，決策特征D對于條件特征B的依賴度定義為：

其中|·|表示集合的樣本個數(shù)，由于POSB(D)為論域的子集，γB(D)的值域?yàn)閇0，1]，當(dāng) γB(D)=1時(shí)，表示特征集B為該論域的特征選擇結(jié)果。

2 基于一致性和知識粒度的半監(jiān)督特征選擇

在本節(jié)中，將會詳細(xì)介紹基于一致性和知識粒度的半監(jiān)督特征選擇的具體實(shí)現(xiàn)方法。對于半監(jiān)督數(shù)據(jù)集，采用依賴度去度量有標(biāo)記樣本特征與標(biāo)記的相關(guān)性，以及使用知識粒度方法去衡量無標(biāo)記樣本的特征相對于整個樣本空間的可區(qū)分性。其具體定義如下。

定義5 設(shè) DS=(U，A，V，f)是一個 決策表，?x，y∈U。A={C∪D}，C表示條件特征，D表示決策特征。?B?C和?c∈(C?B)，則針對于特征集B下條件特征c相對于決策特征D的重要度為：

由于 γB(D)的值域?yàn)?[0，1]，條件特征 c相對于決策特征D的重要度的值域?yàn)閇0，1]，若重要度的值為0則表示該特征為冗余特征，否則該特征為不可缺少特征。當(dāng)增加一個特征時(shí)，相應(yīng)的重要度表示增加特征后的依賴度的變化。

定義 6 設(shè) DS=(U，A，V，f)是一個決策表，?x，y∈U。A={C∪D}，C表示條件特征，D表示決策特征。?B?C，若B為特征選擇后的特征子集，則滿足：

（1）γB(D)= γC(D)；

（2）?b ∈ B，γB?(D)≠ γB(D)。

根據(jù)以上定義和性質(zhì)，利用正域下的依賴度可用于分析有標(biāo)記一致類樣本，從而進(jìn)行特征選擇的過程，但是，半監(jiān)督數(shù)據(jù)中存在大部分無標(biāo)記樣本［26］，為了充分利用無標(biāo)記樣本的特征信息進(jìn)行特征選擇，因此，引入了知識粒度方法來處理此類學(xué)習(xí)任務(wù)。

定義7［22］設(shè) DS=(U，A，V，f)是一個決策表，A={C∪D}，C表示條件特征，D表示決策特征。?B?C，基于條件特征B劃分的等價(jià)類為 U/IND(B)={X1，X2，…，Xn}，則條件特征B的知識粒度定義GD(B)為：

其中|·|表示集合的樣本個數(shù)，基于該公式，知識粒度是對在該粒度下的等價(jià)類進(jìn)行類內(nèi)的不確定性度量。

性質(zhì)2 給定一個決策表DS=(U，A，V，f)，?x，y∈U。A={C∪D}，C 表示條件特征，D表示決策特征 。 若B，E?C， 且 B?E 則GD(B)> GD(E)。其中，? 表示一種偏好關(guān)系。為了更好表示知識粒度對于決策表的可區(qū)分性，其表示為知識粒度的辨識度，定義如下。

定義 8 設(shè) DS=(U，A，V，f)是一個決策表，A={C∪D}，?B?C。知識 B的辨識度Dis(B)為：

定義 9 設(shè) DS=(U，A，V，f)是一個決策表 ，A={C∪D}， ?B?C 和 ?b∈(C?B)，則條件特征b相對于特征子集B的重要度為：

定理 1 設(shè) DS=(U，A，V，f)是一個決策表 。 A={C∪D}， ?B?C，若 GD(B)=GD(C)且對于任意條件特征b∈B，并Siggk(b，B?|b|)>0，則B為A的一個特征子集。

由于半監(jiān)督數(shù)據(jù)中存在有標(biāo)記數(shù)據(jù)和無標(biāo)記數(shù)據(jù)，其特征的重要度需要充分考慮該兩部分?jǐn)?shù)據(jù)中特征的重要度，為此考慮數(shù)據(jù)分布情況，構(gòu)造了基于一致性和知識粒度的半監(jiān)督特征選擇方法，其特征的重要度計(jì)算定義給出如下。

定義10 設(shè) DS=(U，A，V，f)是一個決策表，A={C∪D}，C表示條件特征，D表示決策特 征 。 ?B?C，?c∈(C?B)和 b∈(C?B?c)，則特征重要度為：

其中α為有標(biāo)記數(shù)據(jù)在半監(jiān)督數(shù)據(jù)中占有比例，有標(biāo)記數(shù)據(jù)部分中條件特征c的重要度為Sigpos(c，B，D)，無標(biāo)記數(shù)據(jù)部分中條件特征 c的重要度為Siggk(c，B)。在計(jì)算有標(biāo)記數(shù)據(jù)和無標(biāo)記數(shù)據(jù)條件特征重要度的基礎(chǔ)上，將其兩者在同一量綱下進(jìn)行融合計(jì)算最終該條件特征在半監(jiān)督數(shù)據(jù)中重要度值，在此基礎(chǔ)上，與該條件特征之外的其他特征中最大重要度值進(jìn)行歸約，保證算法的可行性。其算法如算法1所示。

算法中步驟一是對數(shù)據(jù)預(yù)處理；步驟二是初始化變量；在步驟三中，針對每個特征進(jìn)行計(jì)算其重要度，在步驟3.1中是根據(jù)該特征在正域下的依賴度去衡量樣本的一致類，步驟3.2中利用知識粒度對數(shù)據(jù)?；攘吭撎卣鲗颖究臻g的可區(qū)分性，步驟3.3根據(jù)數(shù)據(jù)分布情況計(jì)算該特征的重要度，步驟3.4對所計(jì)算出的特征重要度進(jìn)行排序；步驟4根據(jù)排序結(jié)果選取特征選擇結(jié)果。

3 實(shí)例分析

為進(jìn)一步詳細(xì)介紹算法的詳細(xì)流程。以表1的半監(jiān)督數(shù)據(jù)為例進(jìn)行分析說明算法流程。其 中 U={x1，x2，x3，x4，x5，x6，x7，x8，x9，x10}，前 5個樣本為有標(biāo)記樣本，后5個樣本為無標(biāo)記樣本 ，C={c1，c2，c3，c4，c5}為 條 件特征集 ，D 為 決策特征集，在半監(jiān)督數(shù)據(jù)中，無標(biāo)記信息的決策特征表示為“*”。

將半監(jiān)督數(shù)據(jù)集劃分為有標(biāo)記數(shù)據(jù)部分和無標(biāo)記數(shù)據(jù)部分，對于有標(biāo)記數(shù)據(jù)部分，首先，根據(jù)標(biāo)記進(jìn)行等價(jià)類劃分，得到U/IND(D)={{x1，x4，x5}， {x2，x3}}={X1，X2}，并令γ?(D)=0；之后對單個特征進(jìn)行劃分等價(jià)類，比如對于c1特征，我們可以得到U/IND(c1)={{x1，x3，x5}，{x2，x4}}= {C1，C2}，其一致性為0，因此其依賴度γci(D)=0，其重要 度 也 為 0。 依 次 ，計(jì) 算 出Sigl(c2，Redl，D)=2/5 ，Sigl(c3，Redl，D)=1/5 ，Sigl(c4，Redl，D)=0，Sigl(c5，Redl，D) =0，之后選取重要度最大值的特征加入候選特征集Red中，并保存相應(yīng)特征的重要度，此時(shí)Redl={c2}；之后從其他特征中選擇重要度最大值的特征，比如特征c1，對條件特征集合c1∪c2進(jìn)行劃分等價(jià)類，得U/IND(c1∪c2)={{x1，x5}，{x2，x4}，{x3}}={C1，C2，C3}，其依賴度為 γ(c1∪c2)(D)=3/5，重要度為 Sigl(c1，c2，D)=3/5?2/5=1/5。依次計(jì)算得出特征的重要度為1/5、1/5、1/5。選其中一個特征加入候選子集并記錄其重要度，此時(shí)候選子集Redl={c1∪c2}；依次步驟計(jì)算相應(yīng)特征的重要度并獲取候選子集。

對于無標(biāo)記數(shù)據(jù)部分，采用知識粒度方法進(jìn)行數(shù)據(jù)?；瘉硖幚碓擃悓W(xué)習(xí)任務(wù)。首先，令GD(?)=1，對于單個特征進(jìn)行劃分等價(jià)類，比如c1特征，我們可以得到等價(jià)類為U/IND(c1)={{x6，x8，x10}，{x7， x9}}，根據(jù)知識粒度公式，可得辨識度為GD(c1)=(32+22)/(5)2=13/25，重要度為Sigu(c1，?)=12/25。依次可計(jì)算出其他特征的重要度為12/25、12/25、8/25、12/25。此時(shí)的候選子集為Redu={c1}，并記錄該特征的重要度；之后計(jì)算除了候選子集的特征重要度，比如特征c2，通過對條件特征集合c1∪c2進(jìn)行等價(jià)類劃分，得到U/IND(c1∪ c2)={{x6，x10}，{x7，x9}，{x8}}，其 辨 識 度為 9/25，其重要度為4/25，依次算出其他特征的重要度為6/25、4/25、4/25。選擇 c3特征加入候選子集中，并記錄該特征的重要度，此候選子集為Redu={c1∪c3}；依次計(jì)算相應(yīng)特征對應(yīng)的重要度，并獲取候選子集。

在獲得有標(biāo)記數(shù)據(jù)部分中特征對應(yīng)的重要度以及無標(biāo)記數(shù)據(jù)部分中特征的重要度后，根據(jù)定義10進(jìn)行融合計(jì)算特征在半監(jiān)督數(shù)據(jù)下的重要度，并獲取在半監(jiān)督數(shù)據(jù)下的候選特征子集。

4 實(shí)驗(yàn)對比與分析

4.1 數(shù)據(jù)集和數(shù)據(jù)預(yù)處理

為驗(yàn)證本文提出的半監(jiān)督特征選擇算法的可行性，從UCI數(shù)據(jù)集中選取了8個公共數(shù)據(jù)集進(jìn)行測試和分析，數(shù)據(jù)集的詳細(xì)信息如表2所示。實(shí)驗(yàn)的測試環(huán)境為：CPU為i5-4590S CPU @ 3.00 GHz，內(nèi)存為8.0 GB，操作系統(tǒng)為Window 10， 采 用 Pycharm 和 MATLAB 平 臺 進(jìn)行編程。

數(shù)據(jù)預(yù)處理實(shí)驗(yàn)進(jìn)行測試和分析的過程中，將UCI數(shù)據(jù)集根據(jù)標(biāo)記比例α進(jìn)行劃分為有標(biāo)記數(shù)據(jù)和無標(biāo)記數(shù)據(jù)［27-28］。在本文中，α的取值為0.2，即有標(biāo)記數(shù)據(jù)的比例的取值為20%；并將數(shù)據(jù)集劃分為無標(biāo)記樣本的標(biāo)記信息設(shè)為空值構(gòu)成半監(jiān)督數(shù)據(jù)。

4.2 評估標(biāo)準(zhǔn)和算法比較

本文選用分類準(zhǔn)確率作為評估標(biāo)準(zhǔn)。為了保證對比實(shí)驗(yàn)的公平性，本文選取了3種不同的分類器進(jìn)行測試，即K近鄰分類器（KNN）、SVM分類器和決策樹分類器（DT）［29］。本文算法以及對比方法均基于十倍交叉驗(yàn)證方法對數(shù)據(jù)集進(jìn)行特征選擇，根據(jù)特征選擇結(jié)果在此三種分類器上的分類性能驗(yàn)證算法的可行性。本文實(shí)驗(yàn)選取了4種半監(jiān)督特征選擇對比算法 ，分 別 為 Semi-JMI［30］、Semi-MIM［30］、Semi-P［31］和 Semi-D［31］方法。

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

為了驗(yàn)證算法的有效性，與當(dāng)前四種半監(jiān)督特征選擇方法Semi-JMI、Semi-MIM、Semi-P和Semi-D在有標(biāo)記數(shù)據(jù)比例為20%的情況下進(jìn)行對比，并采用KNN、SVM和CT三種不同分類器下的分類精度作為約簡結(jié)果如表3—5所示，粗體表示分類精度最高值。其中Rank（↓）為在實(shí)驗(yàn)方法中精度值排名序號值的平均值，該值越小表示該實(shí)驗(yàn)方法的性能更好，Win/Tie/Loss表示實(shí)驗(yàn)方法與其他對比方法表現(xiàn)性能“更好/相等/更低”的數(shù)量對比。

由表3—5的實(shí)驗(yàn)數(shù)據(jù)可得，采用Semi-CG半監(jiān)督特征選擇方法在八個真實(shí)數(shù)據(jù)集的標(biāo)記數(shù)據(jù)比例為20%的特征選擇結(jié)果在三種不同分類器下的分類性能有較明顯的優(yōu)勢。實(shí)驗(yàn)結(jié)果表明Semi-CG方法可以有效充分利用未標(biāo)記數(shù)據(jù)的信息，選擇出對分類性能較好的特征子集。另外在處理未標(biāo)記數(shù)據(jù)時(shí)，采用知識粒度方法考慮特征對整個樣本空間的可區(qū)分性可以充分利用未標(biāo)記數(shù)據(jù)特征信息進(jìn)而獲取更為可靠的特征子集。

為了進(jìn)一步詳細(xì)分析特征子集對分類性能的影響，本文以有標(biāo)記數(shù)據(jù)比例為20%的情況為例，在Optdits和Letter這兩個數(shù)據(jù)集上，計(jì)算并記錄特征選擇結(jié)果在KNN、SVM和DT分類器上的分類精度隨特征個數(shù)的增加變化的趨勢結(jié)果，如圖1?3所示。

由圖1?3可以看出，Semi-CG方法較比其他四種半監(jiān)督特征選擇方法，在大部分的情況下，分類精度相對較高。在分類器KNN上，數(shù)據(jù)集Optdits在隨著特征個數(shù)的增加，其分類精度也隨之增加，增加的幅度也隨之趨于穩(wěn)定，KNN分類器在Semi-CG方法下訓(xùn)練的分類模型較好，在Letter數(shù)據(jù)集上的趨勢也是顯示增加的趨勢，在大部分情況下，Semi-CG方法的分類性能較優(yōu)。在其他分類器下的情況也呈現(xiàn)相同趨勢，但在分類器SVM，數(shù)據(jù)集Letter下，其分類精度的增加趨勢與其他方法性能較為接近。

綜上，隨著數(shù)據(jù)的特征數(shù)目的增加，Semi-CG算法的分類性能也隨之增加，并在大部分的情況下優(yōu)于其他半監(jiān)督特征選擇方法。本文算法可以更有效地利用無標(biāo)記數(shù)據(jù)中的信息，提高特征選擇結(jié)果的分類性能。

5 結(jié)論

粗糙集和粒計(jì)算是數(shù)據(jù)挖掘的強(qiáng)有力工具。針對數(shù)據(jù)的標(biāo)注代價(jià)過高，本文采用粒計(jì)算更有效的獲取無標(biāo)記數(shù)據(jù)的信息進(jìn)行特征選擇，本文利用知識粒度方法詳細(xì)分析特征空間中特征的相關(guān)性獲取更多未標(biāo)記數(shù)據(jù)的信息，并結(jié)合依賴度分析有標(biāo)記數(shù)據(jù)中特征與標(biāo)記的相關(guān)性進(jìn)行特征選擇，提高了分類精度。實(shí)驗(yàn)分析表明，Semi-CG半監(jiān)督特征選擇方法8個UCI數(shù)據(jù)集以及三個不同分類器上能夠獲得分類性能較好的特征約簡結(jié)果。目前，本文主要是針對單標(biāo)記數(shù)據(jù)進(jìn)行半監(jiān)督特征選擇，下一步工作將研究在多標(biāo)記數(shù)據(jù)情況下半監(jiān)督特征選擇工作。