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

劉吉超，王 鋒

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

0 引言

大數(shù)據(jù)背景下，隨著數(shù)據(jù)獲取工具的迅速發(fā)展和數(shù)據(jù)存儲(chǔ)技術(shù)的不斷進(jìn)步，數(shù)據(jù)庫中存儲(chǔ)的數(shù)據(jù)集的規(guī)模也越來越龐大，這給傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)帶來了嚴(yán)峻而全新的挑戰(zhàn)。 眾所周知，為數(shù)據(jù)樣本確定類標(biāo)簽需要耗費(fèi)一定的時(shí)間以及相應(yīng)的技術(shù)支撐。而隨著數(shù)據(jù)規(guī)模的日趨龐大，為所有數(shù)據(jù)樣本確定類標(biāo)簽的代價(jià)也隨之變得異常昂貴。 這顯然也是目前大數(shù)據(jù)背景下分類問題中面臨的挑戰(zhàn)之一。 面對(duì)規(guī)模異常龐大的數(shù)據(jù)集，通常只能為其中一小部分確定類標(biāo)簽，而大量存在的是無標(biāo)記的數(shù)據(jù)樣本。 為有效處理這類數(shù)據(jù)集，眾多研究者引入了半監(jiān)督學(xué)習(xí)機(jī)制來處理部分標(biāo)記數(shù)據(jù)的學(xué)習(xí)任務(wù)[1-6]。

特征選擇是數(shù)據(jù)挖掘技術(shù)中一種常用的數(shù)據(jù)預(yù)處理技術(shù)，對(duì)給定數(shù)據(jù)集進(jìn)行有效特征子集的選取，只保留對(duì)學(xué)習(xí)任務(wù)貢獻(xiàn)較大的特征，可有效提高學(xué)習(xí)模型的泛化能力，降低過擬合以及計(jì)算耗時(shí)[7-13]。 面對(duì)部分標(biāo)記數(shù)據(jù)集，半監(jiān)督特征選擇算法也引起了眾多研究者的廣泛關(guān)注，并取得了一定的研究成果。文獻(xiàn)[14]將有標(biāo)記樣本和無標(biāo)記樣本相結(jié)合度量特征的相關(guān)性，設(shè)計(jì)了基于圖論的半監(jiān)督處理機(jī)制。 文獻(xiàn)[15]同時(shí)基于無標(biāo)記樣本和有標(biāo)記樣本來構(gòu)造基于數(shù)據(jù)的圖結(jié)構(gòu)，進(jìn)行特征選擇。文獻(xiàn)[16]設(shè)計(jì)了基于多目標(biāo)優(yōu)化理論的半監(jiān)督特征子集選取機(jī)制。文獻(xiàn)[17]通過計(jì)算特征間相關(guān)性來構(gòu)造特征的近鄰，進(jìn)行有效特征子集的選取。文獻(xiàn)[18]將流形學(xué)習(xí)引入特征選擇中，提出了基于流形正則化的半監(jiān)督特征選擇方法。此外，文獻(xiàn)[19-20]基于粗糙集理論，定義了半監(jiān)督意義下新的特征重要度的度量，并給出了相應(yīng)的特征選擇算法。文獻(xiàn)[21]基于最大相關(guān)最小冗余的特征選擇求解策略，分別基于有標(biāo)記數(shù)據(jù)和無標(biāo)記數(shù)據(jù)給出了相關(guān)性和冗余性的計(jì)算公式，并給出了相應(yīng)的半監(jiān)督特征選擇求解過程。 在此基礎(chǔ)上，為進(jìn)一步充分利用數(shù)據(jù)庫中大量無標(biāo)記數(shù)據(jù)集，本文基于Relief-F算法設(shè)計(jì)一種面向符號(hào)數(shù)據(jù)的半監(jiān)督特征選擇算法。

Relief-F系列算法的主要特點(diǎn)是基于分析近鄰樣本對(duì)類別的區(qū)分能力來確定特征的權(quán)重，即特征重要度。 其核心思想是：一個(gè)優(yōu)秀的特征應(yīng)該使得同類的樣本更加靠近，而使得不同類的樣本更加分散。 Relief-F系列算法提出以來已經(jīng)在許多算法和應(yīng)用中被廣泛使用。 針對(duì)部分標(biāo)記的符號(hào)數(shù)據(jù)，本文中首先引入了一種基于耦合學(xué)習(xí)的樣本相似度度量，可更有效地度量符號(hào)型數(shù)據(jù)樣本的相似性[22-23]。 在此基礎(chǔ)上，將Relief-F算法進(jìn)行拓展用于處理部分標(biāo)記數(shù)據(jù)。

本文首先介紹了基于耦合學(xué)習(xí)的數(shù)據(jù)樣本相似度，然后提出了基于Relief-F的半監(jiān)督特征選擇算法，最后為實(shí)驗(yàn)結(jié)果及分析。

1 對(duì)象的耦合相似度

數(shù)據(jù)樣本間的相似度依賴于樣本對(duì)各個(gè)特征取值之間的相似度。 對(duì)于符號(hào)型數(shù)據(jù)，由于數(shù)據(jù)取值的無序性，顯然不能通過計(jì)算距離直接比較。一些研究者通過分析數(shù)據(jù)取值間的耦合特性，提出了基于耦合學(xué)習(xí)的符號(hào)取值相似度度量(coupled attribute similarity for objects，CASO)[20]。 基于耦合的數(shù)據(jù)取值相似度既考慮了同一特征內(nèi)部特征取值之間的相似性 (intra-coupled attribute value similarity，IaASV)，同時(shí)又考慮了其余特征對(duì)當(dāng)前特征取值相似性的貢獻(xiàn)(inter-coupled attribute value similarity，IeASV)。 該相似度主要通過分析屬性值的頻率分布和特征間的依賴聚合度來確定最終的相似度度量[23], 具體介紹如下。

定義1給定一個(gè)信息表Sn×m,則數(shù)據(jù)表中的對(duì)象ux、uy之間的對(duì)象耦合相似度CASO(ux,uy)為

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

經(jīng)典Relief-F特征選擇算法的核心思想是，首先從數(shù)據(jù)集中隨機(jī)選擇一個(gè)樣本，然后分別從該樣本的同類和不同類中均選擇出k個(gè)最近鄰樣本，通過分析該樣本同其近鄰間的距離(或相似度)來更新特征的權(quán)重。 其更新權(quán)重的意義在于減去選定樣本與其同類近鄰在該特征上的差異，增加選定樣本與其不同類近鄰在該特征上的差異。 在此基礎(chǔ)上重復(fù)抽取多個(gè)樣本，上述過程重復(fù)迭代多次，最終每個(gè)特征得到一個(gè)平均權(quán)重。 最后根據(jù)權(quán)重值的大小可對(duì)特征進(jìn)行排序。

為更好地度量符號(hào)數(shù)據(jù)樣本間的相似度，本節(jié)中引入定義1～3的耦合相似度(CASO)來求解給定樣本的近鄰，并在此基礎(chǔ)上，將半監(jiān)督學(xué)習(xí)機(jī)制引入經(jīng)典Relief-F算法中，對(duì)其進(jìn)行拓展。 具體的算法思想為：先從有標(biāo)記數(shù)據(jù)中隨機(jī)抽取數(shù)據(jù)樣本s(假設(shè)s的類別為yi)，然后從其余每一類yj(i≠j)中選擇一個(gè)s的最近鄰xj；在所有未標(biāo)記數(shù)據(jù)中計(jì)算并選取出s和所有xj的k個(gè)最近鄰樣本；基于在無標(biāo)記數(shù)據(jù)集中求解到的所有近鄰并結(jié)合Relief-F算法更新特征的權(quán)重。該算法的具體算法流程介紹如下。

算法1基于Relief-F的半監(jiān)督特征選擇算法(semi-supervised feature selection based on Relief-F，SFSR)。

輸入: 訓(xùn)練集S=S1∪S2，其中S1為有標(biāo)記數(shù)據(jù)，S2為無標(biāo)記數(shù)據(jù)，特征個(gè)數(shù)m，類別集C。

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

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

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

步驟2.1 從有標(biāo)記樣本集S1中隨機(jī)選擇一個(gè)樣本s，s的類別為cq(cq∈C)。

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

(1)

步驟3 返回結(jié)果wk(k=1,2,…,m)。

算法1對(duì)經(jīng)典Relief-F算法的拓展主要有兩個(gè)方面：1) 引入基于耦合學(xué)習(xí)的相似度度量來計(jì)算給定樣本的近鄰；2) 從無標(biāo)記樣本中尋找給定樣本的近鄰，充分利用了無標(biāo)記樣本信息。而基于樣本近鄰來更新特征權(quán)重的公式(步驟2.4)仍是使用的經(jīng)典 Relief-F算法中的更新公式。

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

為驗(yàn)證上述提出的基于Relief-F的半監(jiān)督特征選擇算法,選取了 5組UCI數(shù)據(jù)集。實(shí)驗(yàn)程序所用語言為Python 3.6，程序開發(fā)平臺(tái)為Anaconda Spyder。程序所運(yùn)行的計(jì)算機(jī)配置為：CPU Inter(R)CoreTMi5-3230,2.60 GHz；內(nèi)存為8 GB；操作系統(tǒng)為Windows 7。 數(shù)據(jù)集的描述見表1。

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

在實(shí)際情況中，大部分?jǐn)?shù)據(jù)集中已標(biāo)記的數(shù)據(jù)占比都比較小，因此在本實(shí)驗(yàn)中考慮了數(shù)據(jù)集中無標(biāo)記數(shù)據(jù)占總數(shù)據(jù)集70%、80%、90%這三種情況。由于針對(duì)面向符號(hào)數(shù)據(jù)的半監(jiān)督特征選擇算法的研究還相對(duì)較少，實(shí)驗(yàn)中所選取的對(duì)比試驗(yàn)為前向半監(jiān)督算法(FSFS)[24]。在此基礎(chǔ)上，本節(jié)中選取了機(jī)器學(xué)習(xí)中常用的三個(gè)分類器logistic、支持向量機(jī)(SVM)、樸素貝葉斯 (NBC)來進(jìn)一步驗(yàn)證特征選擇結(jié)果的有效性。表2～4分別給出了三種情況下由特征選擇算法SFSR和FSFS對(duì)表1中5個(gè)數(shù)據(jù)集選擇得到的特征個(gè)數(shù)和由選擇結(jié)果誘導(dǎo)的分類精度的比較。其中N表示特征選擇結(jié)果中特征的個(gè)數(shù)，分類精度表示由特征選擇結(jié)果分別在上述三個(gè)分類器上通過十折交叉驗(yàn)證得到分類精度，表中數(shù)值的前面部分表示十次分類正確率的均值，后面部分表示平均絕對(duì)誤差。本節(jié)中使用的分類器和精度計(jì)算方法均集成在數(shù)據(jù)挖掘軟件weka中。另外，表2～4中加粗的內(nèi)容表示由不同特征選擇算法得到的特征選擇結(jié)果在相同分類器上得到的分類精度較高的值，例如表2數(shù)據(jù)集backup-large由本文算法得到的選擇結(jié)果在分類器logistics和SVM上分類精度高于由算法FSFS的結(jié)果在這兩個(gè)分類器上的精度，而在分類器NBC上的分類精度則低于算法FSFS的選擇結(jié)果在該分類器上的精度。

表2 無標(biāo)記數(shù)據(jù)為70%的情況下特征選擇結(jié)果的分類精度比較Table 2 The experimental results of classification accuracy on feature subsets with 70% unlabeled objects

表3 無標(biāo)記數(shù)據(jù)為80%的情況下特征選擇結(jié)果的分類精度比較Table 3 The experimental results of classification accuracy on feature subsets with 80% unlabeled objects

表4 無標(biāo)記數(shù)據(jù)為90%的情況下特征選擇結(jié)果的分類精度比較Table 4 The experimental results of classification accuracy on feature subsets with 90% unlabeled objects

由表2～4的實(shí)驗(yàn)結(jié)果可得，本文所設(shè)計(jì)的基于Relief-F的SFSR算法在5個(gè)UCI數(shù)據(jù)集上選擇出的特征子集所得出的分類精度結(jié)果大部分都高于或持平于FSFS算法所得出的結(jié)果。 上述實(shí)驗(yàn)結(jié)果進(jìn)一步驗(yàn)證了本文提出的基于Relief-F的SFSR算法的有效性。 但是由于本文新算法在求解樣本近鄰過程中使用的相似度度量需要綜合考慮特征取值在所有特征下的相似度，因此新算法的計(jì)算效率還有待進(jìn)一步提高。下一步的研究工作會(huì)包括對(duì)算法效率的探索和分析。

4 結(jié)論

針對(duì)符號(hào)型部分標(biāo)記數(shù)據(jù)集，本文通過引入一種基于耦合學(xué)習(xí)的數(shù)據(jù)樣本相似度，設(shè)計(jì)了一種基于Relief-F算法的半監(jiān)督特征選擇算法，算法中綜合考慮了有標(biāo)記數(shù)據(jù)和無標(biāo)記數(shù)據(jù)來求解選定樣本的近鄰，進(jìn)而更新特征的權(quán)重值。 為有效驗(yàn)證提出新算法的可行性，實(shí)驗(yàn)分析中選取了5組UCI數(shù)據(jù)集和3種常用機(jī)器學(xué)習(xí)分類器來對(duì)新算法的性能進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果進(jìn)一步驗(yàn)證了算法的有效性。 該算法可以充分利用無標(biāo)記數(shù)據(jù)信息來更新特征權(quán)重值，所得出的特征子集也有效提高了分類器的分類精度。 為后續(xù)的半監(jiān)督數(shù)據(jù)挖掘技術(shù)提供了可以借鑒的新思路。