半監(jiān)督Relief-F特征選擇算法

靳炳燁, 王 鋒, 魏 巍

(山西大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,山西 太原 030006)

隨著互聯(lián)網(wǎng)技術(shù)和信息產(chǎn)業(yè)的快速發(fā)展,數(shù)據(jù)獲取和采集的能力飛速提高,數(shù)據(jù)規(guī)模呈現(xiàn)了前所未有的增長(zhǎng)和龐大.如何從海量的大數(shù)據(jù)中抓取重點(diǎn),挖掘出最有用的信息一直以來(lái)便是智能信息領(lǐng)域中的研究重點(diǎn)和熱點(diǎn)[1].特征選擇是數(shù)據(jù)挖掘領(lǐng)域中一種常見(jiàn)的數(shù)據(jù)降維技術(shù),主要通過(guò)一定的度量來(lái)選擇優(yōu)的特征,移除不相關(guān)或冗余特征,進(jìn)而提高學(xué)習(xí)模型的性能,降低過(guò)擬合等[2-6].目前,依照數(shù)據(jù)樣本是否具有類(lèi)別信息,現(xiàn)有特征選擇方法可分為有監(jiān)督特征選擇、無(wú)監(jiān)督特征選擇和半監(jiān)督特征選擇[7-8].其中,半監(jiān)督特征選擇算法便是將半監(jiān)督學(xué)習(xí)機(jī)制引入到了處理少數(shù)標(biāo)記數(shù)據(jù)的特征選擇中.

針對(duì)半監(jiān)督特征選擇的探索,一些研究者也已經(jīng)取得了可觀的研究成果[9-13].文獻(xiàn)[14]提出了一種新穎的基于空間覆蓋的半監(jiān)督特征選擇算法,該算法同時(shí)利用已標(biāo)簽數(shù)據(jù)和未標(biāo)簽數(shù)據(jù)進(jìn)行特征選擇.文獻(xiàn)[15]基于粗糙集理論和信息熵的概念,提出了一種基于信息熵的粗糙特征選擇算法.文獻(xiàn)[16]基于集合間相關(guān)度和自相關(guān)度的定義提出了一種基于類(lèi)標(biāo)號(hào)擴(kuò)展的半監(jiān)督特征選擇算法.此外,文獻(xiàn)[17-18]通過(guò)引入面向部分標(biāo)記數(shù)據(jù)的特征重要度,設(shè)計(jì)了基于粗糙集理論的半監(jiān)督粗糙特征選擇算法.在此基礎(chǔ)上,為進(jìn)一步提高大數(shù)據(jù)背景下半監(jiān)督特征選擇的算法性能和可移植性,并充分利用大量無(wú)標(biāo)記樣本.本文中,筆者通過(guò)重新定義數(shù)據(jù)樣本近鄰的求解和搜索策略,以符號(hào)數(shù)據(jù)為研究對(duì)象,設(shè)計(jì)了一種基于Relief-F的半監(jiān)督特征選擇算法.

Relief-F算法是較為常用的一種特征選擇算法,由于其簡(jiǎn)單、易于實(shí)現(xiàn)已經(jīng)被廣泛應(yīng)用于多個(gè)領(lǐng)域.經(jīng)典的Relief-F算法僅適用于有標(biāo)記數(shù)據(jù)集[19],為有效處理少數(shù)標(biāo)記數(shù)據(jù)集,劉吉超等[20]在Relief-F算法上進(jìn)行擴(kuò)展,把無(wú)標(biāo)簽數(shù)據(jù)和有標(biāo)簽數(shù)據(jù)綜合來(lái)考慮,從而提出了一種基于Relief-F的半監(jiān)督特征選擇算法.該算法主要通過(guò)使用無(wú)標(biāo)記樣本輔助有標(biāo)記樣本來(lái)確定樣本的近鄰,進(jìn)而更新特征的權(quán)重.但是該算法求解過(guò)程中只使用了少部分無(wú)標(biāo)記樣本,大量的無(wú)標(biāo)記樣本中蘊(yùn)含的信息仍被忽略掉.

為此,在文獻(xiàn)[20]算法的基礎(chǔ)上,筆者對(duì)于有標(biāo)記樣本的近鄰求解機(jī)制進(jìn)行了優(yōu)化,提出了一種優(yōu)化的基于Relief-F的半監(jiān)督特征選擇算法.為進(jìn)一步驗(yàn)證新算法的有效性,仿真實(shí)驗(yàn)中選取了5組UCI數(shù)據(jù)集,并引入機(jī)器學(xué)習(xí)中3個(gè)常用分類(lèi)器對(duì)新算法和對(duì)比算法的特征選擇結(jié)果的分類(lèi)性能作了分析和比較,實(shí)驗(yàn)結(jié)果很好地驗(yàn)證了本文中提出的新算法的有效性和可行性.

1 基本概念

為有效度量符號(hào)數(shù)據(jù)樣本的距離,進(jìn)而確定其近鄰樣本,算法中引入了一種基于粗糙集的面向符號(hào)數(shù)據(jù)的距離度量,為此,粗糙集理論以及該距離度量的相關(guān)概念介紹如下.

1.1 粗糙集相關(guān)概念

粗糙集理論中,一個(gè)含有類(lèi)信息的數(shù)據(jù)集通常被表示為一個(gè)四元組S=(U,A,V,f),其中U是數(shù)據(jù)樣本集,稱(chēng)為論域,A=C∪D,C是特征集,D是類(lèi)別信息,V=Ua∈AVa,Va是其值屬性a的值域.f:U×A→V是一個(gè)信息函數(shù).對(duì)于任意的a∈A,并且x∈U,f(x,a)∈Va.令B?C,x,y∈U有如下的等價(jià)關(guān)系:

RB={(x,y)∈U×U|f(x,a)=f(v,a),?a∈B}.

由等價(jià)關(guān)系RB形成的等價(jià)類(lèi)表示為[x]B={y|(x,y)∈RB}.對(duì)于每個(gè)數(shù)據(jù)集的子集X?U和B?A,X的下近似和上近似算子分別為

1.2 一種基于粗糙集的距離度量

基于上述粗糙集理論,為有效度量符號(hào)數(shù)據(jù)樣本的相似性,文獻(xiàn)[21]提出了一種基于粗糙集的距離度量.該度量方式不僅考慮了在同一特征下不同特征值的異同,還考慮了其他特征對(duì)特征值距離(或相似度)的影響,即同一特征下2個(gè)值之間的相似度不僅取決于它們本身還與它們所處的環(huán)境有關(guān).

定義1令S=(U,C∪D)是一個(gè)符號(hào)數(shù)據(jù)表,對(duì)于任意ai∈C,設(shè)p,q∈Vai,p和q相對(duì)于ai的內(nèi)部距離定義為

(1)

定義2令S=(U,C∪D)是一個(gè)符號(hào)數(shù)據(jù)表,對(duì)于任意ai∈C,設(shè)p,q∈Vai,p和q相對(duì)與屬性aj(j≠i)的外部距離定義為

(2)

其中X={x|f(x,ai)=p,x∈U},Y={x|f(x,ai)=q}.

定義3令S=(U,C∪D)是一個(gè)符號(hào)數(shù)據(jù)表,對(duì)于任意ai∈C,設(shè)p,q∈Vai,p和q關(guān)于屬性集A的定義為

定義4令S=(U,C∪D)是一個(gè)符號(hào)數(shù)據(jù)表,xi,xj∈U(1≤i,j≤n),xi和xj之間的距離定義為

(3)

2 一種基于Relief-F的半監(jiān)督特征選擇算法

2.1 算法思想

Relief-F算法是對(duì)經(jīng)典特征選擇算法Relief的拓展,可有效處理多分類(lèi)問(wèn)題,其核心思想是:屬于相同類(lèi)的數(shù)據(jù)樣本,那么它們之間的距離應(yīng)該更近;而對(duì)于不同類(lèi)的數(shù)據(jù)樣本,那么它們之間的距離應(yīng)該相對(duì)更遠(yuǎn).因此,一個(gè)好的特征應(yīng)該是讓同類(lèi)的數(shù)據(jù)樣本離的更近,不同類(lèi)的數(shù)據(jù)樣本離的更遠(yuǎn).Relief-F算法的特征權(quán)重更新公式的主要框架是:在每個(gè)特征權(quán)重值初始值的基礎(chǔ)上,不斷減少選定數(shù)據(jù)樣本及其同類(lèi)近鄰在該特征上的差異值,同時(shí)不斷增加選定數(shù)據(jù)樣本及其不同類(lèi)近鄰在該特征上的差異值.如果某特征的權(quán)重值較大,則說(shuō)明該特征可使選定數(shù)據(jù)樣本和同類(lèi)樣本近鄰之間差異更小,而和不同類(lèi)樣本近鄰之間差異更大,即可以更好的區(qū)分類(lèi)別.

為有效處理少數(shù)標(biāo)記數(shù)據(jù)集,劉吉超等[20]將半監(jiān)督學(xué)習(xí)思想引入經(jīng)典的Relief-F算法中,設(shè)計(jì)了一種基于Relief-F的半監(jiān)督特征選擇算法.該算法的核心思想是:所選取數(shù)據(jù)樣本的同類(lèi)近鄰和不同類(lèi)近鄰均是從無(wú)標(biāo)記數(shù)據(jù)樣本中選取,并依此來(lái)更新特征權(quán)重.但是由于經(jīng)典Relief-F算法并未求解所有樣本的近鄰,而且實(shí)際數(shù)據(jù)集中通常只有少數(shù)有標(biāo)記樣本,尤其大數(shù)據(jù)背景下,無(wú)標(biāo)記樣本的規(guī)模更加龐大,因此上述方法只利用了少量的無(wú)標(biāo)記樣本,而大量的無(wú)標(biāo)記樣本未被使用,其中蘊(yùn)含的大量信息也被忽略.為此,為更多地發(fā)現(xiàn)大量無(wú)標(biāo)記樣本中的有用信息,設(shè)計(jì)了一種新的基于Relief-F的半監(jiān)督特征選擇算法.新算法在求解樣本近鄰過(guò)程中擴(kuò)大了搜索范圍,充分利用了大量無(wú)標(biāo)記樣本,依此提高特征選擇的性能.

新算法的核心思想是:對(duì)給定數(shù)據(jù)樣本,基于多個(gè)不同類(lèi)樣本的近鄰來(lái)確定所選定樣本的不同類(lèi)近鄰,即對(duì)選定樣本不再基于單一的不同類(lèi)樣本來(lái)尋找其不同類(lèi)近鄰,而是從多個(gè)不同類(lèi)樣本的多組近鄰中確定不同類(lèi)近鄰.

2.2 算法步驟

新算法的創(chuàng)新主要是改進(jìn)了不同類(lèi)樣本近鄰的求解方式,對(duì)選定的每個(gè)樣本s(s∈Yi類(lèi)),首先求解類(lèi)Yj(i≠j)中所有對(duì)象的近鄰,即?x∈Yj,從無(wú)標(biāo)記樣本中求解x的k個(gè)最近鄰.假設(shè)Yj中有n個(gè)對(duì)象,則一共會(huì)找到nk個(gè)近鄰;然后在這nk個(gè)近鄰選取到s的k個(gè)無(wú)標(biāo)記樣本最近鄰,即Yj(i≠j)類(lèi)中s的k個(gè)近鄰.新算法對(duì)不同類(lèi)樣本最近鄰求解擴(kuò)充了原有的搜索范圍,更加充分利用了大量無(wú)標(biāo)記數(shù)據(jù)樣本.新算法的詳細(xì)步驟見(jiàn)算法1.

算法1一種基于Relief-F的半監(jiān)督特征選擇算法(A semi-supervised feature selection algorithm based on Relief-F, SRfFS).

輸入:數(shù)據(jù)集S=S1∪S2,其中S1為有標(biāo)記數(shù)據(jù)樣本集,S2為無(wú)標(biāo)記數(shù)據(jù)樣本集,特征個(gè)數(shù)m,類(lèi)別集C.

輸出:特征的權(quán)重值Wk=(1,2,…,m).

步驟1 初始化特征權(quán)重wk(k=1,2,…,m).

步驟2 循環(huán)執(zhí)行步驟2.1～2.4M次.

步驟2.1 從有標(biāo)記樣本S1中隨機(jī)抽取一個(gè)樣本s,樣本s的類(lèi)別為cq(cq∈C).

步驟2.3 在其余的每一類(lèi)cp∈C(p≠q)中循環(huán)執(zhí)行以下操作:

步驟2.3.1 對(duì)類(lèi)別cp中的每一個(gè)對(duì)象y∈cp在無(wú)標(biāo)記數(shù)據(jù)中基于定義4找y的d個(gè)近鄰;

步驟2.3.2 在類(lèi)別cp中所有對(duì)象的近鄰中基于定義4計(jì)算出離s最近的d個(gè)近鄰(假設(shè)cp類(lèi)有10個(gè)對(duì)象,那么要求解10d個(gè)近鄰,然后在10d個(gè)近鄰中找離s最近的10個(gè)近鄰).

步驟2.4 基于下面公式更新所有特征的權(quán)重:

(4)

步驟3 輸出特征權(quán)重值wk=k(1,2,…,m).

算法1對(duì)原先劉吉超等[20]提出的基于Relief-F的半監(jiān)督特征選擇算法的改進(jìn)主要有2點(diǎn)內(nèi)容:首先引入了一種基于粗糙集理論的距離度量方式;其次在為和目標(biāo)實(shí)例不同類(lèi)的樣本找最近鄰的時(shí)候綜合考慮每個(gè)類(lèi)下的所有對(duì)象的距離,在此基礎(chǔ)上確定所選樣本的最近鄰樣本。而在求解出最近鄰樣本后,算法1中使用了與經(jīng)典Relief-F算法相同的特征權(quán)重值更新公式.

3 實(shí)驗(yàn)分析

為有效驗(yàn)證本文第2節(jié)中提出算法1的可行性,本節(jié)中選取了5組UCI數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)分析.實(shí)驗(yàn)分析中使用的編程語(yǔ)言是Java1.8,程序的開(kāi)發(fā)平臺(tái)是IDEA.程序運(yùn)行的計(jì)算機(jī)配置是:CPU Inter(R) i5- 6300 HQ,2.80GHZ;內(nèi)存為16GB;操作系統(tǒng)為Windows 10,數(shù)據(jù)集的描述見(jiàn)表1.

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

由于實(shí)際應(yīng)用中,數(shù)據(jù)庫(kù)中只有少部分?jǐn)?shù)據(jù)樣本獲取到了類(lèi)標(biāo)簽,大量存在的仍是無(wú)標(biāo)記樣本,為此,實(shí)驗(yàn)中選取有標(biāo)記樣本占比30 %,即無(wú)標(biāo)記數(shù)據(jù)樣本占數(shù)據(jù)集70 %的情況.為進(jìn)一步驗(yàn)證新算法的有效性,與文獻(xiàn)[20]中的半監(jiān)督特征選擇算法(SFSR算法)以及文獻(xiàn)[15]中的基于信息熵的半監(jiān)督特征選擇算法(SEFS算法)作了比較.特征選擇結(jié)果的分類(lèi)性能由機(jī)器學(xué)習(xí)中常用的3個(gè)分類(lèi)器:logistic、支持向量機(jī)(SVM)、樸素貝葉斯(NBC)來(lái)驗(yàn)證.實(shí)驗(yàn)比較結(jié)果見(jiàn)表2～4.表2～4分別給出了在3個(gè)分類(lèi)器下SFSR算法、SEFS算法和ISFSR算法在表1中5組UCI數(shù)據(jù)集上的特征選擇結(jié)果及其分類(lèi)性能的對(duì)比結(jié)果。在表2-4中,N表示有效特征子集中特征的個(gè)數(shù);分類(lèi)性能是每組數(shù)據(jù)集的特征選擇結(jié)果在上述3個(gè)分類(lèi)器上的分類(lèi)精度,分類(lèi)精度值是通過(guò)十折交叉驗(yàn)證方法求解得到的最終值.實(shí)驗(yàn)過(guò)程中使用的分類(lèi)器集成在數(shù)據(jù)挖掘軟件weka中.此外,為更清晰地比較相同數(shù)據(jù)集由不同特征選擇算法求解得到的特征子集的分類(lèi)精度,表2～4中的最后一行列出了同一個(gè)算法在所有數(shù)據(jù)集上的分類(lèi)精度均值.

表2 在Logistic下算法性能的比較Tab.2 Comparison of Algorithm Performance Under Logistic

表3 在SVM下算法性能的比較Tab.3 Comparison of Algorithm Performance Under SVM

表4 在NBC下算法性能的比較Tab.4 Comparison of Algorithm Performance Under SVM

由表2～4的實(shí)驗(yàn)結(jié)果可以知道,所設(shè)計(jì)的基于Relief-F的半監(jiān)督特征選擇算法的改進(jìn)SRfFS在5個(gè)UCI數(shù)據(jù)集上選取的特征子集所得出分類(lèi)器精度高于算法SFSR和算法SEFS得出的特征子集的精度,尤其是基于SVM的分類(lèi)精度,筆者提出的新算法的分類(lèi)精度明顯高于另外2個(gè)算法.此外,在dermatology和backup-large數(shù)據(jù)集上,算法求解到的特征子集的特征個(gè)數(shù)較多,這樣的結(jié)果可能表明,如果在進(jìn)行特征選擇的時(shí)候,更多的利用到無(wú)標(biāo)簽數(shù)據(jù)信息,有可能會(huì)選擇到更多的特征,同時(shí)也得到了精度上的提升.上述實(shí)驗(yàn)進(jìn)一步驗(yàn)證了新算法的有效性.新算法的核心內(nèi)容是研究了如何尋找不同類(lèi)樣本的最近鄰,后續(xù)研究工作中將針對(duì)如何使用有標(biāo)記數(shù)據(jù)對(duì)無(wú)標(biāo)記數(shù)據(jù)進(jìn)行標(biāo)簽的傳播,盡可能為更多的無(wú)標(biāo)記數(shù)據(jù)確定類(lèi)信息.

4 結(jié) 論

為有效處理少數(shù)標(biāo)記數(shù)據(jù)的特征選擇問(wèn)題,本文針對(duì)符號(hào)數(shù)據(jù),基于Relief-F算法的特征權(quán)重更新機(jī)制,通過(guò)重新定義數(shù)據(jù)樣本近鄰的求解策略和搜索范圍,設(shè)計(jì)了一種新的半監(jiān)督粗糙特征選擇算法.新算法在近鄰樣本的確定過(guò)程中充分利用了大量無(wú)標(biāo)記樣本,可求解到更為準(zhǔn)確的近鄰樣本.實(shí)驗(yàn)分析結(jié)果進(jìn)一步驗(yàn)證了新算法的有效性.研究?jī)?nèi)容和方法為后續(xù)的半監(jiān)督數(shù)據(jù)挖掘技術(shù)提供了可以借鑒的新的思路.