S2R2:基于相關(guān)性與冗余性分析的半監(jiān)督特征選擇

張東方,陳海燕,2,袁立罡

(1.南京航空航天大學計算機科學與技術(shù)學院，江蘇 南京 211106; 2.軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心,江蘇 南京 210093;3.南京航空航天大學民航學院,江蘇 南京 211106)

0 引 言

數(shù)據(jù)挖掘可以發(fā)現(xiàn)數(shù)據(jù)集中有意義的信息與模式,已經(jīng)被應(yīng)用在人臉識別[1]、圖像檢索[2]、醫(yī)療診斷[3-4]以及金融市場[5]等領(lǐng)域中。然而急劇增長的數(shù)據(jù)規(guī)模引發(fā)了“維度災難”，傳統(tǒng)的數(shù)據(jù)挖掘與學習算法無法快速有效地解決問題。盡管在理論上模型的判別力隨特征數(shù)量的增加而增強，但是當數(shù)據(jù)集內(nèi)在流形固定且增加的特征不相關(guān)或者冗余時，情況就不確定了[6]。另一方面，不相關(guān)與冗余特征也擴大了數(shù)據(jù)挖掘模型與算法的計算開銷。解決這一問題的關(guān)鍵方法是數(shù)據(jù)降維，即在進行進一步分析之前，通過識別和移除無意義的特征來降低數(shù)據(jù)集的維數(shù)。

數(shù)據(jù)降維可以在降低數(shù)據(jù)集計算復雜度的同時保持甚至提升其判別性能[7]。理論與實踐皆證明了數(shù)據(jù)降維可以提高學習效率、提升分類精度以及降低計算復雜度的作用。特征提取與特征選擇是數(shù)據(jù)降維的主要策略。前者通常將數(shù)據(jù)投影到一個低維度簡化子空間中，改變了特征的原有含義[8-9]。而后者致力于通過移除不相關(guān)與冗余特征，尋找原始特征集的最優(yōu)子集[10]。特征選擇方法保留了特征的原有含義，因而得到研究者的青睞。更進一步，特征選擇可以被分為4種類型：過濾型、封裝型、嵌入型以及混合型[11-14]。過濾型方法根據(jù)預先指定的評價標準探究數(shù)據(jù)集的內(nèi)在屬性，僅使用數(shù)據(jù)集自身來評估每個特征或子集的相關(guān)性，進而從原始特征空間種選擇一個特征子集。封裝型方法基于某種指定的學習算法，選擇能使預測結(jié)果最好的特征子集。相似地，嵌入型方法嘗試在訓練特定學習算法的過程中同時獲取最優(yōu)特征子集。而混合型方法兼具過濾型與封裝型的特點，通過獨立的評價準則與某種學習算法評估候選特征集。不同類型方法并無顯著優(yōu)劣之分，在本文中尤其關(guān)注可以提供更具泛化性結(jié)果以及計算效率更高的過濾型特征選擇方法。

基于標簽信息的可用性，特征選擇被劃分為有監(jiān)督、半監(jiān)督與無監(jiān)督方法。有監(jiān)督特征選擇方法對標記數(shù)據(jù)的數(shù)量與質(zhì)量有較高需求。如果缺乏足夠的標記數(shù)據(jù)，可能會導致在識別有類間判別力特征時失敗[15]。而無監(jiān)督特征選擇方法僅使用無標記數(shù)據(jù)，無視標簽信息，因而可能無法識別重要的或有判別力的特征[16]。實際上，在工程實踐中，標記工作通常是十分耗時且昂貴的，然而無標記數(shù)據(jù)卻可以輕易大量獲取。故在部分標記數(shù)據(jù)集上進行的半監(jiān)督特征選擇逐漸引起了研究者的興趣與重視。半監(jiān)督特征選擇研究如何更好地識別相關(guān)特征，通過挖掘有限標記數(shù)據(jù)與大量無標記數(shù)據(jù)背后的信息來為真實世界應(yīng)用尋找更具判別力的特征子集。在文獻[17]中，有標簽數(shù)據(jù)與無標簽數(shù)據(jù)被用于計算Pearson相關(guān)系數(shù)，進而度量特征相關(guān)性與冗余性并完成了特征排序。文獻[18]提出了挖掘有標記數(shù)據(jù)與無標記數(shù)據(jù)中包含的數(shù)據(jù)集空間分布結(jié)構(gòu)信息，通過在盡可能保持樣本空間分布結(jié)構(gòu)的同時最大化不同類別之間的邊界的思想評估特征。

從特征相關(guān)性與冗余性分析[15-16]以及信息論領(lǐng)域的最近相關(guān)工作[19-21]中得到啟發(fā)，結(jié)合最大相關(guān)最小冗余框架[10]，本文提出一種新半監(jiān)督特征選擇方法(Semi-supervised Feature Selection Based on Analysis of Relevance and Redundancy, S2R2)。首先基于信息論設(shè)計半監(jiān)督環(huán)境下用于度量特征之間信息以及特征與標簽之間信息的度量，其值是由無標記數(shù)據(jù)與有標記數(shù)據(jù)一齊參與計算給出；然后將這2種度量置入最大相關(guān)最小冗余特征選擇框架進行折中與組合；最后選用增量前向搜索方法貪婪地構(gòu)建特征子集，避免了子集搜索過程中的高計算復雜度。本文提出新的半監(jiān)督條件下的特征相關(guān)性與冗余性度量，并給出了相關(guān)理論分析。針對大規(guī)模數(shù)據(jù)集或計算復雜度敏感的應(yīng)用場景，還提出算法的加速版本FS2R2。實驗表明，本文提出的方法適用于在不同規(guī)模、不同標記比例的數(shù)據(jù)集上進行半監(jiān)督特征選擇，方法性能好且具有泛用性。

1 相關(guān)工作與理論基礎(chǔ)

本章介紹信息論的相關(guān)概念，同時討論特征信息度量以及最大相關(guān)最小冗余框架。首先簡述本文使用的標記與符號釋義。令F={F1,F2,…,Fd}表示特征全集,其中Fi(i=1,2,…,d)表示數(shù)據(jù)集第i個特征,特征子集S?F。數(shù)據(jù)集X={XL,XU}T，其中XL={x1,…,xn}T，XU={xn+1,…,xn+m}T,總大小為(n+m)×d，每個樣本xj∈Rd(j=1,2,…,n+m)有d個屬性，并且前n個樣本是有標記的，其標記為yj∈{1,2,…,c}，從類別標簽值集合C中取值，后m個樣本是無標記的。

1.1 特征信息度量

信息熵是信息論的基本概念。不同于其他只考慮特征間線性相關(guān)關(guān)系的度量，信息熵是一個非線性相關(guān)度量，同時也是無參的。由于理論上信息熵能夠在數(shù)據(jù)分布未知的情況下量化數(shù)據(jù)的信息量，信息熵與互信息被廣泛應(yīng)用于解決特征選擇問題[10,22]。

特征信息度量在特征選擇過程中量化了特征間或特征與標簽之間相關(guān)性?；谛畔㈧貙С龅幕バ畔⑴c條件熵就常被直接應(yīng)用到特征選擇方法中，由于不滿足于信息論概念的基本形式,研究者們進一步提出了多種擴展與改進。

定義1 對稱不確定性(Symmetrical Uncertainty)。在數(shù)據(jù)集X中，特征Fi與Fj的對稱不確定性SU(Fi,Fj)被定義為：

(1)

對稱不確定性又稱標準化互信息，是通過使用特征或特征與標簽的信息熵對互信息進行標準化后得到的，其值域為[0,1]。SU(Fi,C)度量了特征Fi與類別標簽C的相關(guān)性?？梢约俣ㄌ卣髋c類別標簽的對稱不確定性越大，特征含有的有關(guān)類別標簽的信息越多，即特征判別力越強。

定義2 相關(guān)度(Relevance)。在數(shù)據(jù)集X中，特征Fi的相關(guān)度UR(Fi)被定義為其與全體特征互信息的平均值：

(2)

特征Fi與全體特征的互信息平均值越高，其與數(shù)據(jù)集X的相關(guān)性越大。根據(jù)樸素貝葉斯假設(shè)，特征在給定類別標簽C的情況下是條件獨立的，特征Fi的相關(guān)度是Fi與潛在類C互信息的下界，即UR(Fi)≤I(Fi,C)[16]。故當數(shù)據(jù)集X的類別標簽在無監(jiān)督情境下無法獲取時，互信息I(Fi,C)在一定程度上可以通過最大化UR(Fi)進行估計。更進一步，特征Fi的相關(guān)度UR(Fi)可以被用于在無監(jiān)督情境中度量特征Fi與潛在類C之間的相關(guān)性。

1.2 最大相關(guān)最小冗余準則

增量前向搜索是大部分過濾型特征選擇方法常用的搜索策略。假設(shè)在增量前向搜索的第k步，已選特征集Sk-1由k-1個已經(jīng)決定的特征組成，根據(jù)“最大相關(guān)最小冗余”準則[10],第k個特征應(yīng)由式(3)從未選特征集U中選出：

(3)

式(3)中的第一項“最大相關(guān)”傾向于選擇那些與潛在類C相關(guān)性最大的特征。通常根據(jù)“最大相關(guān)”選擇的特征集具有很強的冗余性，即選擇的特征之間具有高相關(guān)性。當2個特征高度相關(guān)時，去除其中之一并不會導致整體判別能力產(chǎn)生較大變化。故式(3)中的第二項作為“最小冗余”條件，根據(jù)特征與已選特征相關(guān)性的平均水平，降低其整體度量結(jié)果數(shù)值。

“最大相關(guān)最小冗余”準則解決了有監(jiān)督特征選擇問題，并選用互信息作為特征與標簽間相關(guān)性以及特征間冗余性度量。Xu[16]首次提出了應(yīng)用于無監(jiān)督特征選擇問題的特征信息度量，應(yīng)用“最大相關(guān)最小冗余”準則解決無監(jiān)督特征選擇問題，繼而提出了“無監(jiān)督最大相關(guān)最小冗余”準則。而Xu等人[17]選取皮爾遜相關(guān)系數(shù)作為特征相關(guān)性度量，基于“最大相關(guān)最小冗余”，提出了半監(jiān)督特征選擇問題的解決方案。

2 S2R2特征選擇算法設(shè)計

本章介紹基于相關(guān)性與冗余性分析的半監(jiān)督特征選擇(S2R2)。S2R2的目標是挖掘半監(jiān)督數(shù)據(jù)集中的有標簽數(shù)據(jù)與無標簽數(shù)據(jù)以獲取特征間以及特征與標簽間的相關(guān)性，進而設(shè)計“半監(jiān)督最大相關(guān)最小冗余”準則，以增量前向搜索的方式構(gòu)建特征子集。

2.1 半監(jiān)督特征信息度量設(shè)計

設(shè)計半監(jiān)督特征信息度量的目的是實現(xiàn)在半監(jiān)督數(shù)據(jù)集中進行相關(guān)性與冗余性分析，量化特征與標簽信息之間的相關(guān)性以及特征彼此之間的冗余性。當可用有標記數(shù)據(jù)數(shù)量過少時，基于互信息等有監(jiān)督特征信息度量進行的有監(jiān)督特征選擇方法往往會得到過擬合的特征選擇結(jié)果。此時，挖掘無標記數(shù)據(jù)中含有的信息可以緩解這一問題。因而本文將有監(jiān)督與無監(jiān)督特征信息度量加以結(jié)合，設(shè)計用于半監(jiān)督相關(guān)性與冗余性分析的特征信息度量。

相關(guān)度(UR)作為典型的無監(jiān)督特征信息度量，在特征選擇問題上與“最大相關(guān)最小冗余”框架的結(jié)合取得了成功[16]。首先基于相關(guān)度，對無監(jiān)督特征信息度量進行進一步的發(fā)展與擴充。

定義3 聯(lián)合相關(guān)度(Joint Relevance)。在數(shù)據(jù)集X中,特征Fi與Fj的聯(lián)合相關(guān)度UR(Fi,Fj)被定義為：

(4)

定義4 條件相關(guān)度(Conditional Relevance)。在數(shù)據(jù)集X中,特征Fi與Fj的條件相關(guān)度UR(Fi|Fj)被定義為：

(5)

這樣的擴充是十分自然的。一方面，在樸素貝葉斯假設(shè)下，特征間在給定潛在類C的前提下是條件獨立的，標簽C并不改變特征Fi與Fj的聯(lián)合熵與特征Fi的信息熵的比值關(guān)系[21]。即：

(6)

在H(Fi,Fj)≠0且H(Fi)≠H(Fi|C)時,式(6)可以重寫為：

(7)

根據(jù)定義(2),自然地由式(7)將聯(lián)合相關(guān)度定義為式(4)。條件相關(guān)度的推導與聯(lián)合相關(guān)度一致。另一方面,如此定義的無監(jiān)督信息度量相關(guān)度、聯(lián)合相關(guān)度、條件相關(guān)度與常用的有監(jiān)督信息度量信息熵、聯(lián)合熵、條件熵呈對應(yīng)關(guān)系并繼承了其性質(zhì)與相關(guān)定理。

定理1 UR(Fi|Fj)=UR(Fi,Fj)-UR(Fj)≤UR(Fi)。

證明定理1

=UR(Fi|Fj)

由特征條件熵小于信息熵的性質(zhì)H(Fi|Fj)≤H(Fi),可得UR(Fi|Fj)-UR(Fi)≤0。故定理1成立。

更進一步，在相關(guān)度與條件相關(guān)度的基礎(chǔ)上，可以定義相關(guān)度增益以及無標簽對稱不確定性。

定義5 相關(guān)度增益(Relevance Gain)。在數(shù)據(jù)集X中，特征Fi與特征Fj的相關(guān)度增益UR(Fi;Fj)被定義為：

(8)

定義6 無監(jiān)督對稱不確定性(Unsupervised Symmetrical Uncertainty)。在數(shù)據(jù)集X中，特征Fi與特征Fj的無監(jiān)督對稱不確定性被定義為：

(9)

定理2 0≤USU(Fi,Fj)≤1。

無監(jiān)督對稱不確定性作為相關(guān)度增益的標準化，在特征選擇過程中克服了相關(guān)度增益傾向于支持更加離散特征的缺點。從相關(guān)度角度度量了無標記數(shù)據(jù)集上特征間的相關(guān)性。與有監(jiān)督對稱不確定性相同，其取值范圍為[0,1]。定理2重點說明USU(Fi,Fj)≤1。

證明USU(Fi,Fj)≤1

故USU(Fi,Fj)≤1。在這個證明中使用了相關(guān)度的性質(zhì)。

在完成無監(jiān)督特征信息度量之后，結(jié)合現(xiàn)有的有監(jiān)督特征信息度量，本文最終可以給出半監(jiān)督特征信息度量。

定義7 相關(guān)性(Relevance)。在數(shù)據(jù)集X中，特征Fi與類別標簽C的相關(guān)性為：

(10)

定義8 冗余性(Redundancy)。在數(shù)據(jù)集X中，特征Fi相對于特征Fj的冗余性為：

Red(Fi;Fj)=αUSU(Fi,Fj)+(1-α)SU(Fi,Fj)

(11)

定理3 0≤Rel(Fi;C)≤1。

定理4 0≤Red(Fi;Fj)≤1。

基于上述討論，結(jié)合定理2以及對稱不確定性(SU)、相關(guān)度的性質(zhì)[23]，定理3、定理4是比較顯然的。在本文實驗進一步證明相關(guān)性與冗余性2種度量的有效性之前，值得一提的是相關(guān)性與冗余性度量不僅不需要用戶進行參數(shù)調(diào)整(α由數(shù)據(jù)集性質(zhì)決定)，而且不需要進一步標準化，克服了諸多特征信息度量偏好自身信息熵較大特征的缺點。

2.2 半監(jiān)督最大相關(guān)最小冗余準則

在定義了半監(jiān)督相關(guān)性式(10)的前提下，半監(jiān)督“最大相關(guān)”準則可以表示為：

(12)

由“最大相關(guān)”準則獲取的特征集往往具有很強的冗余性，即特征間高度相關(guān)。這時一些冗余特征的移除不會引起較大的特征集判別力變化。故加入下述“最小冗余”準則來盡可能降低特征子集的冗余性：

(13)

上述2個準則的結(jié)合即是“半監(jiān)督最大相關(guān)最小冗余”準則?？紤]二者的簡單結(jié)合形式Φ(D,R)以同時達到“最大相關(guān)”與“最小冗余”的目標：

maxΦ(D,R),Φ=D-R

(14)

在實際求解過程中，本文采用增量前向搜索方法來避免搜索指數(shù)級大小的特征子集解空間。假設(shè)在增量前向搜索的第k步,已選特征集Sk由k-1個已經(jīng)決定的特征組成，根據(jù)“半監(jiān)督最大相關(guān)最小冗余”準則，第k個特征應(yīng)由下式從未選特征集U中選出：

(15)

2.3 算法及復雜性

基于以上設(shè)計與討論，本文提出一種基于相關(guān)性與冗余性分析的半監(jiān)督特征選擇方法(S2R2)。算法1給出了S2R2算法的具體步驟。

算法1 S2R2特征選擇算法

輸入：數(shù)據(jù)集X={XL,XU}T，全體特征集F，平衡參數(shù)α，目標特征數(shù)s

輸出：目標特征子集Sk

1：建立初始目標特征集S0=?，初始待選特征集U=F-S0

2：從k=1到s

2.1：在待選特征集U中根據(jù)以下準則搜索新特征Fk：

2.2：更新目標特征集Sk=Sk-1∪Fk，待選特征集U=U-Fk

S2R2方法的計算復雜度由2個部分組成，一部分是根據(jù)式(10)和式(11)進行的相關(guān)性與冗余性度量計算，另一部分是在算法1中的步驟2.1進行的特征排序。首先，考慮到s≤d，特征排序部分所需的計算復雜度不會超過O(d2)。

然后,考慮式(10)和式(11)中相關(guān)特征信息度量的計算復雜度。在已知全體特征相關(guān)度、信息熵以及任意2個特征間聯(lián)合熵的情況下，計算任一條件熵、信息增益、對稱不確定性、聯(lián)合相關(guān)度、條件相關(guān)度、相關(guān)度增益、無監(jiān)督對稱不確定性皆只需要O(1)次操作。在有標記數(shù)據(jù)集及無標記數(shù)據(jù)集上計算全體特征的信息熵以及任意一對特征的聯(lián)合熵所需的時間復雜度為O(d2n+d2m)，再加上在有標記數(shù)據(jù)集上進行的d次特征與標簽聯(lián)合熵計算，共需O(d2n+d2m+dn)次計算。在完成上述信息熵以及聯(lián)合熵計算的前提下，需要O(d2)次計算以得到每個特征的相關(guān)度。在此基礎(chǔ)上根據(jù)式(10)計算每個特征與標簽的半監(jiān)督相關(guān)性需要O(d)次操作，根據(jù)式(11)計算任2個特征間的半監(jiān)督冗余性需要O(d2)次操作。

綜上所述，可以確認S2R2方法的計算復雜度不會超過O(d2(n+m))。S2R2方法的主要計算開銷來自于在有標記及無標記數(shù)據(jù)集上進行的特征信息熵及特征間聯(lián)合熵計算。在獲取了上述信息后，其他指標、半監(jiān)督相關(guān)性冗余性的計算以及特征子集搜索工作則可以在較短時間內(nèi)完成。

2.4 快速特征過濾

在2.3節(jié)中討論了S2R2方法的計算復雜度。S2R2方法的主要計算開銷來自于特征自身信息熵以及特征之間聯(lián)合信息熵的計算。盡管S2R2方法的理論計算復雜度與當前流行的特征選擇方法如mRMR、LSDF等大致相同，但是日漸增大的數(shù)據(jù)規(guī)模以及無標記數(shù)據(jù)的易收集性意味著需要更加有效率的半監(jiān)督特征選擇方法。

另一方面，本文涉及的重要無監(jiān)督基本信息度量，即相關(guān)度，其本質(zhì)是使用特征與全體特征的互信息來近似估計特征與假想類的相關(guān)性。也就是說，無監(jiān)督情境中使用全體特征以均衡權(quán)重的方法擬合了假想類。但是在半監(jiān)督情境中，有標記部分的數(shù)據(jù)可以指導無標記部分數(shù)據(jù)上的假想類擬合方式。半監(jiān)督數(shù)據(jù)集中無標記部分數(shù)據(jù)的相關(guān)度計算可以不以均一權(quán)重或者不以全體特征參與的方式進行。

將2個方面考量結(jié)合，在S2R2算法中加入特征過濾步驟，設(shè)計新的特征相關(guān)度計算方案，進而提出基于相關(guān)性與冗余性分析的快速半監(jiān)督特征選擇方法(Fast Semi-supervised Feature Selection Based on Analysis of Relevance and Redundancy, FS2R2)。

相較于S2R2方法，F(xiàn)S2R2一方面通過特征過濾步驟，在移除不相關(guān)特征的同時快速縮小問題規(guī)模；另一方面在特征過濾結(jié)果而不是原始全體特征集上進行相關(guān)性與冗余性分析，大大減小了半監(jiān)督相關(guān)度與冗余度度量的單次計算資源消耗與計算總次數(shù)。

FS2R2方法特征過濾步驟的主要目的是去除不相關(guān)特征。在有標記數(shù)據(jù)集上，特征相關(guān)性可以通過互信息進行簡單度量。然而在無標記數(shù)據(jù)集上由于缺少標記信息，無法計算互信息進而度量特征與類別的相關(guān)性。考慮計算復雜度，采用最大熵原則作為互信息的替代，使用特征在無標記數(shù)據(jù)集上攜帶的信息量推測特征相關(guān)性。整合2個方面原則，就形成了FS2R2方法中使用的特征過濾準則，其將在有標記數(shù)據(jù)集上與標簽互信息熵大、在無標記數(shù)據(jù)集上信息熵較大的特征視為相關(guān)特征。FS2R2特征選擇步驟如算法2所示。

算法2 FS2R2特征選擇算法

輸入：數(shù)據(jù)集X={XL,XU}T，全體特征集F，平衡參數(shù)α，目標特征數(shù)s

輸出：目標特征子集Sk

1：建立初始目標特征集S0=?，初始待選特征集U=F-S0

2：從k=1到2s

2.1：在待選特征集U中根據(jù)以下準則搜索新特征Ff：

2.2：更新過濾特征集Uk=Uk-1∪Ff，待選特征集U=U-Uf

3：從k=1到s

3.1：在過濾特征集U2s中根據(jù)以下準則搜索新特征Fk：

3.2：更新目標特征集Sk=Sk-1∪Fk，過濾特征集U2s=U2s-Fk

特征過濾步驟的計算復雜度為O(d(n+m))，考慮到一般2s

3 實驗及分析

本章將基于相關(guān)性與冗余性分析的半監(jiān)督特征選擇方法(S2R2)與當前流行的不同種類的特征選擇方法相比較，并分析算法選擇特征的性能。

3.1 數(shù)據(jù)集

本次實驗共選擇了6個標準數(shù)據(jù)集進行實驗，包括5個普通數(shù)據(jù)集，分別為Vote、Letter、Musk1、Arrhythmia以及Madelon；1個圖片數(shù)據(jù)集,為AR10P。這些數(shù)據(jù)集可以從UCI機器學習庫[24]或者ASU特征選擇庫[25]中獲取。表1總結(jié)了這6個數(shù)據(jù)集的描述。

表1 數(shù)據(jù)集描述

實驗選用的數(shù)據(jù)集在樣本大小和特征數(shù)量上差別較大，涵蓋了一系列應(yīng)用領(lǐng)域。因此，它們可以提供較為全面的測試。在估計互信息時，通常很難根據(jù)有限實例在連續(xù)空間中計算積分。故本次實驗選用最小描述長度方法[26]對數(shù)據(jù)集中可能包含的連續(xù)特征進行離散化。

3.2 評估標準

本文選用領(lǐng)域內(nèi)通用的標準度量即分類準確率作為評估標準。為了保證對比實驗的公平性，本文選用2種不同類型的分類器，即K近鄰分類器(KNN)[27-28]與決策樹(DT)[29]，對測試樣本進行預測，并計算預測樣本的正確率，得出相應(yīng)的實驗分類結(jié)果。其中KNN分類器的參數(shù)K=1。另外，本文還采用十折交叉驗證框架。有標記數(shù)據(jù)被平均劃分為10份，在每輪運行中1份保留用于結(jié)果評估，其余9份用作訓練集。為了減輕隨機性對評估結(jié)果的影響，將每個實驗運行10次，并平均它們的結(jié)果。特征選擇評估框架如圖1所示。

圖1 特征選擇評估框架

3.3 算法比較

本次實驗選取5種對比算法，分別是1種有監(jiān)督特征選擇算法：mRMR[10]，3種半監(jiān)督特征選擇算法：RRPC[17]、LSDF[18]、TPFS[30]，1種無監(jiān)督特征選擇算法：UFS-MI[16]。為了保證算法在進行準確率比較時的公平性，TPFS的參數(shù)按照文獻[30]的建議確定最優(yōu)取值；另一方面mRMR、RRPC、UFS-MI以及S2R2與FS2R2的所選特征子集特征數(shù)量參數(shù)s需要在集合{「2d/log2d?,「d/log2d?,「d/2log2d?}中搜索確定最優(yōu)值。

首先選取基于最大相關(guān)最小冗余框架方法進行對比試驗，以驗證S2R2方法以及FS2R2方法的有效性。在3個數(shù)據(jù)集上，逐漸增加選擇的特征個數(shù)，計算并記錄特征選擇結(jié)果在KNN與DT分類器上的分類精度，得到的結(jié)果如圖2和圖3所示。

圖2 不同特征子集大小的KNN分類精度

圖3 不同特征子集大小的DT分類精度

從圖2和圖3可以看出，在實驗中本文提出的S2R2、FS2R2方法優(yōu)于所比較的特征選擇算法。一方面，隨著選擇的特征數(shù)量的增加，各方法的分類精度呈增速不斷放緩的上升態(tài)勢；另一方面，S2R2方法在絕大多數(shù)情況下的性能都優(yōu)于其他方法。這說明在最大相關(guān)最小冗余框架內(nèi)，半監(jiān)督特征選擇方法S2R2可以同時利用有標記數(shù)據(jù)與無標記數(shù)據(jù)攜帶的信息，提高了特征選擇方法的性能，驗證了半監(jiān)督特征選擇方法的有效性。

然后選取其他半監(jiān)督特征選擇方法進行對比實驗，進一步驗證S2R2方法以及FS2R2方法與常用半監(jiān)督特征選擇方法的性能。采用圖1所示的評估框架在多個標準數(shù)據(jù)集上進行實驗，實驗結(jié)果如表2和表3所示。

表2 KNN分類器平均準確率

表3 DT分類器平均準確率

表2展示了6個數(shù)據(jù)集經(jīng)由不同半監(jiān)督特征選擇方法處理后，在KNN分類器上的平均準確率。表3展示了6個數(shù)據(jù)集經(jīng)由不同半監(jiān)督特征選擇方法處理后，在DT分類器上的平均準確率。表2和表3中加粗的數(shù)值表示同一數(shù)據(jù)集中性能最好的特征選擇方法對應(yīng)的數(shù)值?？梢钥闯?，在實驗涉及的6個標準數(shù)據(jù)集上，S2R2方法相較于其他常用半監(jiān)督特征選擇具有較為顯著且一致的優(yōu)越性。而FS2R2方法的性能不穩(wěn)定，但其平均性能仍與其他對比算法相仿。

3.4 復雜性分析

本文2.3節(jié)和2.4節(jié)討論了S2R2方法以及FS2R2方法的理論復雜度，本節(jié)以數(shù)據(jù)集Musk1、Madelon以及AR10P為例，通過多次重復實驗比較各算法的平均時間消耗。對于需要設(shè)置子集大小參數(shù)s的方法,參數(shù)s設(shè)置為「d/log2d?。結(jié)果如表4所示。

表4 算法平均執(zhí)行時間消耗 單位:s

如表4所示，F(xiàn)S2R2表現(xiàn)出一致的較短耗時。LSDF方法屬于基于圖的半監(jiān)督特征選擇方法，在計算中需要構(gòu)造樣本集鄰接圖結(jié)構(gòu)，對樣本數(shù)量較為敏感。LSDF方法的耗時對目標特征子集大小是不敏感的。而TPFS方法包含一個特征相關(guān)性與冗余性排序階段，以及一個分別在有標記與無標記數(shù)據(jù)集上進行模糊聚類并探討聚類中心匹配程度的階段。其對樣本數(shù)量也較為敏感。

RRPC、S2R2、FS2R2方法作為最大相關(guān)最小冗余框架在半監(jiān)督特征選擇領(lǐng)域的應(yīng)用，需要進行大量特征間或特征與標簽間的相關(guān)性和冗余性計算，對特征數(shù)量更為敏感。其中由于RRPC整體設(shè)計較為簡單，不僅使用了只能探索線性相關(guān)關(guān)系的Pearson相關(guān)系數(shù)作為簡單度量，而且選擇特征不需要探索每對特征間的冗余性，故在執(zhí)行時間上具有一定優(yōu)勢。而FS2R2方法通過特征過濾步驟在算法執(zhí)行早期快速縮小了搜索空間大小，相較于無過濾步驟的S2R2，極大程度地減小了算法的計算消耗。特征數(shù)量越多，F(xiàn)S2R2方法的加速效果越明顯。

4 結(jié)束語

從相關(guān)性與冗余性分析以及信息論領(lǐng)域的最近相關(guān)工作中得到啟發(fā)，結(jié)合最大相關(guān)最小冗余框架，本文提出了一種新的半監(jiān)督特征選擇方法(S2R2)。S2R2方法作為過濾型特征選擇方法，在獨立于任何特定學習算法的條件下構(gòu)建了特征子集。首先基于信息論設(shè)計了半監(jiān)督環(huán)境下用于度量特征之間信息以及特征與標簽之間信息的度量，其值是由無標記數(shù)據(jù)與有標記數(shù)據(jù)一齊參與計算給出；然后將這2種度量置入最大相關(guān)最小冗余特征選擇框架進行折中與組合；最后選用增量前向搜索方法貪婪地構(gòu)建特征子集，避免了子集搜索過程中的高計算復雜度。在不同分類器上多個標準數(shù)據(jù)集的對比實驗驗證了S2R2的有效性與優(yōu)越性。

FS2R2方法在S2R2的基礎(chǔ)上加入了特征過濾步驟，提高了算法計算效率。實驗表明FS2R2的平均性能與經(jīng)典半監(jiān)督特征選擇方法相仿。理論上，F(xiàn)S2R2方法更適于在不相關(guān)特征較多的特征集上進行特征選擇，其泛化性與穩(wěn)定性仍待理論與實踐進一步驗證。

相關(guān)度與相關(guān)度增益測度是利用無標記數(shù)據(jù)進行特征選擇或者挖掘無標記數(shù)據(jù)信息的關(guān)鍵信息度量。在高維數(shù)據(jù)集中如何降低其計算復雜度，是進一步將其擴展與應(yīng)用的關(guān)鍵。