基于ReliefF的層次分類在線流特征選擇算法

張小清，王晨曦*，呂彥，林耀進(jìn)

（1.閩南師范大學(xué)計(jì)算機(jī)學(xué)院，福建漳州 363000；2.數(shù)據(jù)科學(xué)與智能應(yīng)用福建省高校重點(diǎn)實(shí)驗(yàn)室，福建漳州 363000）

0 引言

在人工智能蓬勃發(fā)展的時(shí)代，數(shù)據(jù)信息的產(chǎn)生速度呈指數(shù)式急劇上升，分類任務(wù)面臨著規(guī)模越來(lái)越大，如樣本數(shù)目多、特征維度高、類別數(shù)量大的挑戰(zhàn)。與此同時(shí)，數(shù)據(jù)的類標(biāo)記空間往往存在層次化結(jié)構(gòu)。如圖1 所示，胃腫瘤（gastric tumors）是消化系統(tǒng)常見(jiàn)疾病，可分為惡性和良性。惡性腫瘤包括胃癌、惡性淋巴瘤和惡性間質(zhì)瘤等。良性腫瘤可分兩大類：一類來(lái)源于黏膜的良性上皮細(xì)胞瘤，如胃腺瘤、腺瘤性息肉等；另一類是良性間葉組織腫瘤，如間質(zhì)瘤、脂肪瘤和神經(jīng)纖維瘤等。顯然，胃腫瘤的組織關(guān)系存在層次結(jié)構(gòu)化。間質(zhì)瘤是1983 年被首次提出，以DOG1、CDll7、CD34 陽(yáng)性為主，c-kit 或PDGFRA 基因功能獲得性突變是重要的分子特征，未定義之前易與其他常見(jiàn)的良性間葉組織腫瘤相混淆。由此可見(jiàn)，研究層次化結(jié)構(gòu)分類學(xué)習(xí)具有重要意義。

圖1 胃腫瘤層次結(jié)構(gòu)Fig.1 Hierarchical structure of gastric tumor

在層次化分類學(xué)習(xí)建模過(guò)程中，該類數(shù)據(jù)的特征空間表現(xiàn)出超高維和演化性［1］的特點(diǎn)。為減少特征高維度帶來(lái)的計(jì)算和存儲(chǔ)開(kāi)銷，特征選擇能夠?qū)?shù)據(jù)特征進(jìn)行篩選，有效地降低數(shù)據(jù)特征空間的高維性，降低樣本被誤分的概率。Relief 算法是一種高效的過(guò)濾式特征選擇方法，1992 年由Kira 等［2］提出并用于解決單標(biāo)記問(wèn)題。為能夠處理多標(biāo)記問(wèn)題，2013 年Spola?r 等［3］在Relief 算法的基礎(chǔ)上進(jìn)行改進(jìn)得到ReliefF 算法。學(xué)者們結(jié)合標(biāo)記相關(guān)性對(duì)ReliefF 算法進(jìn)行擴(kuò)展。Kong 等［4］提出MReliefF 算法，然而，這些特征選擇算法忽略了類別空間層次結(jié)構(gòu)關(guān)系。目前，已有許多面對(duì)層次化結(jié)構(gòu)數(shù)據(jù)的特征選擇算法被提出：Grauman 等［5］提出了一種新的視覺(jué)識(shí)別度量學(xué)習(xí)方法，集成了關(guān)于對(duì)象層次結(jié)構(gòu)的外部語(yǔ)義；Hwang 等［6］提出了一種語(yǔ)義核林方法，使用多個(gè)層次分類來(lái)表示對(duì)象類別的不同語(yǔ)義視圖；Zhao 等［7］提出了一種新的具有遞歸正則化的分層分類特征選擇框架，同時(shí)考慮類別之間的父子、兄弟關(guān)系。

這些已有的分層特征選擇算法假設(shè)特征空間是靜態(tài)的、先前已知的，未考慮建模任務(wù)中特征的動(dòng)態(tài)性和不確定性，因此把動(dòng)態(tài)的、未知條件下的特征選擇問(wèn)題轉(zhuǎn)換成流特征概念下的在線特征選擇問(wèn)題的研究十分重要。針對(duì)傳統(tǒng)的二分類學(xué)習(xí)問(wèn)題，Wu 等［8］提出了一種在線流特征選擇框架；陳祥焰等［9］提出了基于鄰域粗糙集的高維類不平衡數(shù)據(jù)的在線流特征選擇算法，用于選擇在大類和小類之間具有高可分離性的特征。針對(duì)多分類學(xué)習(xí)問(wèn)題［10］，Lin 等［11］提出了基于模糊互信息的多標(biāo)記在線流特征選擇算法；Liu 等［12］提出了基于鄰域粗糙集的多標(biāo)記在線流特征選擇算法。

這些已有的層次特征選擇算法未考慮在線流特征的表現(xiàn)形式，而傳統(tǒng)的在線流特征選擇算法能夠?qū)崿F(xiàn)動(dòng)態(tài)特征的在線處理，但忽略了類別之間的層次關(guān)系。為此，本文基于ReliefF 算法［3］提出層次分類學(xué)習(xí)在線流特征選擇算法OH_ReliefF（Online Hierarchical streaming feature selection based on ReliefF algorithm）：利用標(biāo)記之間的層次關(guān)系對(duì)ReliefF 算法進(jìn)行改進(jìn)，使ReliefF 算法能夠處理層次化結(jié)構(gòu)數(shù)據(jù)，將新的特征權(quán)值計(jì)算方法與在線重要性分析和在線冗余性分析策略相結(jié)合，設(shè)計(jì)相關(guān)算法來(lái)構(gòu)建層次分類學(xué)習(xí)的在線流特征選擇框架。本文的主要工作如下：

1）在ReliefF 算法的基礎(chǔ)上，將排斥策略與兄弟策略結(jié)合作為劃分標(biāo)記異類的標(biāo)準(zhǔn)，定義一種能夠處理分層數(shù)據(jù)的特征權(quán)重計(jì)算方法HF_ReliefF（Hierarchical Feature weights calculated based on ReliefF algorithm）。

2）提出OH_ReliefF，將特征的層次關(guān)系與流特征選擇框架相結(jié)合，為層次數(shù)據(jù)集在線選擇一個(gè)較優(yōu)的特征子集。

3）與傳統(tǒng)的在線特征選擇算法相比，本文算法在6 個(gè)數(shù)據(jù)集上的平均預(yù)測(cè)精度值與次優(yōu)算法相比提高了10%，在LCA-F1（Lowest Common Ancestor-F1）分層指標(biāo)上相較于次優(yōu)算法提高了5%，并且TIE（Tree Induced Error）值降低了25%，說(shuō)明本文算法可以很好地應(yīng)對(duì)分層流特征選擇問(wèn)題。

1 相關(guān)基礎(chǔ)

1.1 類別的層次結(jié)構(gòu)

在層次分類學(xué)習(xí)中，一般把類別的層次結(jié)構(gòu)分成樹(shù)結(jié)構(gòu)和有向無(wú)環(huán)圖結(jié)構(gòu)兩種［13］，本文只考慮類別的樹(shù)結(jié)構(gòu)關(guān)系。樹(shù)結(jié)構(gòu)的“從屬”可以用序?qū)?D，?)來(lái)表示，具有不可逆性、反自反性和傳遞性［14］等特性，其中D表示樣本的標(biāo)記空間，?表示從屬關(guān)系。對(duì)于?di，dj，dk∈D，樹(shù)結(jié)構(gòu)的從屬關(guān)系的特性描述如下：

1）不可逆性：若di?dj，則dj?di。

2）反自反性：di?di。

3）傳遞性：若di?dk且dk?dj，則di?dj。

利用樹(shù)結(jié)構(gòu)中的從屬關(guān)系來(lái)表達(dá)層次結(jié)構(gòu)中節(jié)點(diǎn)之間的父子關(guān)系和兄弟關(guān)系，描述如下：

1）父子關(guān)系：若di?dj，則稱節(jié)點(diǎn)dj是節(jié)點(diǎn)di的父節(jié)點(diǎn)；

2）兄弟關(guān)系：若di?dk且dj?dk，則稱節(jié)點(diǎn)dj是節(jié)點(diǎn)di的兄弟節(jié)點(diǎn)，并且節(jié)點(diǎn)dk是點(diǎn)節(jié)點(diǎn)di、dj的父節(jié)點(diǎn)。

1.2 ReliefF算法

定義1［3］設(shè)U表示樣本的集合，對(duì)?xi，xj，xk∈U，Δf(xi，xj)表示樣本xi和xj在特征f(f?F)下的歐氏距離，并且Δ 函數(shù)滿足以下定義：

1）Δf(xi，xj)≥0，當(dāng)且僅當(dāng)xi=xj時(shí)，Δf(xi，xj)=0。

2）Δf(xi，xj)=Δf(xj，xi)。

3）Δf(xi，xj)≤Δf(xi，xk)+Δf(xk，xj)。

定義2［3］對(duì)?xi∈U，決策屬性D在特征f?F將U劃分為樣本xi的同類近鄰樣本集合Hi和異類近鄰樣本集合Mi。具體表示如下所示：

其中Label(xi)表示樣本xi的類別。

定義3［3］?xi∈U(i≥1)，在樣本xi下，特征f?F衡量對(duì)決策屬性D的劃分能力用權(quán)重Wi來(lái)表示。權(quán)重Wi計(jì)算公式如下所示：

其中：分別取前k個(gè)樣本作為樣本xi的最近同類近鄰和最近異類近鄰；表示樣本xi的第j個(gè)同類近鄰樣本，表示xi的第j個(gè)異類近鄰樣本；C表示樣本xi類別的異類。

2 基于ReliefF的層次分類在線流特征選擇

本章將排斥策略與兄弟策略相結(jié)合應(yīng)用到ReliefF 算法中，并將改進(jìn)的ReliefF 算法拓展到層次分類學(xué)習(xí)的在線流特征選擇問(wèn)題，基于ReliefF 算法提出層次分類學(xué)習(xí)模型的兩種在線特征評(píng)估準(zhǔn)則。

2.1 層次類別的劃分策略

傳統(tǒng)的ReliefF 特征選擇算法在劃分樣本同類、異類時(shí)往往沒(méi)有將類別之間的關(guān)系考慮進(jìn)去，通常采用排斥策略［15］來(lái)劃分類別。排斥策略描述如下：如果樣本的類別為di(di∈D)，則所有不同于di的類別都作為異類。針對(duì)的ReliefF 算法存在的不足，若樣本的類別具有層次結(jié)構(gòu)，利用樹(shù)結(jié)構(gòu)的層次關(guān)系可以更好地衡量類別之間的劃分：利用父子關(guān)系來(lái)劃分同類和異類稱為包含策略，即若樣本的類別為di，則di與該節(jié)點(diǎn)所有的孩子節(jié)點(diǎn)均視為同類，除此之外的類別均為異類節(jié)點(diǎn)。利用節(jié)點(diǎn)之間的兄弟關(guān)系來(lái)劃分同類異類的策略稱為兄弟策略，兄弟策略認(rèn)為節(jié)點(diǎn)di的同類為自身，節(jié)點(diǎn)di所有兄弟節(jié)點(diǎn)稱為異類。

2.2 面向?qū)哟位瘮?shù)據(jù)的ReliefF算法

定義4矩陣S∈Rl×l用于描述節(jié)點(diǎn)之間的兄弟關(guān)系，l表示層次樹(shù)中葉子節(jié)點(diǎn)個(gè)數(shù)。Si表示與節(jié)點(diǎn)di有兄弟關(guān)系的集合，Sij的值用來(lái)區(qū)分節(jié)點(diǎn)di和節(jié)點(diǎn)dj是否存在兄弟關(guān)系。兄弟矩陣S用形式化描述如下：

對(duì)于1≤j≤l，若?Sij=1，表示節(jié)點(diǎn)dj是節(jié)點(diǎn)di的兄弟節(jié)點(diǎn)，節(jié)點(diǎn)di的異類為dj。此時(shí)，節(jié)點(diǎn)di也是節(jié)點(diǎn)dj的兄弟，可以看出兄弟矩陣S是一個(gè)對(duì)稱矩陣。

定義5?di∈D，特征f?F衡量對(duì)類別di的劃分能力用權(quán)重Wdi來(lái)表示。權(quán)重Wdi如下所示：

其中：sim表示所有類別為di的樣本；若?Sij=1，類別di的兄弟節(jié)點(diǎn)為dj，dif表示所有類別為dj的樣本；否則采用排斥策略來(lái)劃分樣本，dif表示所有不同于類別為di的樣本。

面向?qū)哟位瘮?shù)據(jù)的特征權(quán)重計(jì)算算法HF_ReliefF 描述如算法1 所示：

算法1 HF_ReliefF。

輸入 特征矩陣data∈Rn×p，類別矩陣D∈R1×l，層次樹(shù)結(jié)構(gòu)tree，近鄰個(gè)數(shù)k；

輸出 預(yù)測(cè)特征權(quán)值向量W。

區(qū)別于傳統(tǒng)的ReliefF 算法，HF_ReliefF 算法考慮類別之間的層次關(guān)系，并且以每個(gè)類別作為單位來(lái)計(jì)算特征的權(quán)重，利用特征對(duì)近鄰樣本的劃分能力來(lái)評(píng)價(jià)特征的重要性。

2.3 OH_ReliefF算法

為解決層次分類學(xué)習(xí)中特征空間的動(dòng)態(tài)性和未知性問(wèn)題，選擇出對(duì)決策屬性具有高分離性并且低冗余性的特征，本節(jié)基于HF_ReliefF 算法介紹兩種在線評(píng)估準(zhǔn)則。

2.3.1 在線特征重要性分析

若同類樣本之間的距離越小，異類近鄰樣本之間的距離越大，則特征權(quán)值計(jì)算結(jié)果越大，表明所選特征對(duì)決策屬性劃分的能力越大。重要的特征應(yīng)該使得同類樣本的距離更加接近，而異類樣本之間的距離更遠(yuǎn)。

因此，如果新特征的加入可以提高候選子集的權(quán)重，即W{ft}∪st-1>Wst-1，說(shuō)明ft對(duì)候選子集是有意義的非冗余特征，能夠提高候選子集對(duì)決策屬的劃分能力；否則認(rèn)為候選子集St-1存在特征與ft相互冗余。

2.3.2 在線冗余分析

若新特征的加入不能提高候選子集的權(quán)重，即W{ft}∪st-1≤Wst-1，則對(duì)ft調(diào)用冗余分析。記S′=S∪{ft}，對(duì)集合S′中所有的特征利用式（3）分別計(jì)算與該集合中其他特征之間的協(xié)方差。

若特征fi與特征fj的協(xié)方差為Cov(fi，fj)=0，說(shuō)明特征fi與特征fj相互獨(dú)立，特征之間不存在冗余關(guān)系；否則，則認(rèn)為新特征ft的加入，使得特征集合S′中的特征fi與特征fj冗余，比較特征fi與fj之間的權(quán)重大小，若Wfi

根據(jù)式（2）與式（3），提出基于ReliefF 算法的層次分類在線流特征選擇算法OH_ReliefF，描述如算法2 所示。

算法2 OH_ReliefF 算法。

輸入特征矩陣data∈Rn×p，層次樹(shù)結(jié)構(gòu)tree，近鄰個(gè)數(shù)k；

輸出 特征序列S。

算法2 主要包含兩個(gè)階段：在線特征的選擇階段以及特征的冗余分析階段。在t時(shí)刻，新特征ft到達(dá)，執(zhí)行算法的第2）步計(jì)算特征的權(quán)重Wt。當(dāng)Wt<δ時(shí)，直接刪除特征ft；否則執(zhí)行第4）步，計(jì)算特征集合權(quán)重WS′，其中S′=S∪{ft}。當(dāng)WS′>WSt-1時(shí)，則執(zhí)行第6）步將特征加入特征子集中；否則需執(zhí)行第7）～16）步。在線冗余分析階段，對(duì)S′中每個(gè)特征執(zhí)行第9）～15）步。在第9）步中隨機(jī)選擇兩個(gè)特征fi、fj并計(jì)算特征之間的協(xié)方差，當(dāng)Cov(fi，fj)≠0 時(shí)，則可刪除冗余的特征。

假設(shè) |U|表示論域U的樣本個(gè)數(shù)，|F|表示條件屬性F的屬性個(gè)數(shù)，|l|是層次結(jié)構(gòu)中的葉子節(jié)點(diǎn)個(gè)數(shù)，當(dāng)前所選特征子集數(shù)量為|St|，則計(jì)算權(quán)重Wt的時(shí)間復(fù)雜度為；在在線特征重要性分析階段，遍歷所有類別所需時(shí)間復(fù)雜度是；當(dāng)執(zhí)行在線冗余更新階段，算法最差時(shí)間復(fù)雜度為。

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

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

本文使用6 個(gè)數(shù)據(jù)集來(lái)測(cè)試OH_ReliefF 算法的性能，其中包括2 個(gè)蛋白質(zhì)數(shù)據(jù)集和4 個(gè)圖像數(shù)據(jù)集，具體情況如表1 所示。

表1 數(shù)據(jù)集描述Tab.1 Description of datasets

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

在本文的實(shí)驗(yàn)中，基于K 最鄰近（K-Nearest Neighbor，KNN）分類器和拉格朗日支持向量機(jī)（Lagrangian Support Vector Machine，LSVM）分類器來(lái)評(píng)價(jià)算法的性能。為更好地對(duì)面向?qū)哟位瘮?shù)據(jù)的在線流特征選擇算法進(jìn)行評(píng)價(jià)，使用四種評(píng)價(jià)指標(biāo)對(duì)算法的性能進(jìn)行分析，分別是：預(yù)測(cè)精度（Accuracy）、TIE、H-F1（Hierarchical-F1）和LCA-F1。

令D、分別表示樣本真實(shí)類別和樣本預(yù)測(cè)類別，Anc(D)表示類別D的所有祖先節(jié)點(diǎn)，Lac(D，)表示類別D，的最近公共祖先節(jié)點(diǎn)。D，的層次分類擴(kuò)展標(biāo)記分別為：。最小公共祖先節(jié)點(diǎn)層次分類擴(kuò)展標(biāo)記表示為：。

1）Accuracy 表示樣本類別被正確劃分的程度。

2）TIE 表示在層次結(jié)構(gòu)中真實(shí)類別節(jié)點(diǎn)D和預(yù)測(cè)節(jié)點(diǎn)-D之間的總邊數(shù)：

3）H-F1 表示分層準(zhǔn)確率PH和召回率RH的調(diào)和平均：

4）LCA-F1 表示預(yù)測(cè)類別節(jié)點(diǎn)-D和真實(shí)標(biāo)記節(jié)點(diǎn)D最小公共祖先：

以上4 個(gè)性能評(píng)價(jià)指標(biāo)，TIE 指標(biāo)取值越小越好，而Accuracy、H-F1 以及LCA-F1 的取值越大表明算法性能越佳。

3.3 參數(shù)分析

為觀察參數(shù)k和δ在不同取值情況下對(duì)OH_ReliefF 算法的影響，令k=｛10，15，20，25，30｝，δ=｛0.000 1，0.001，0.01，0.1，1｝，在數(shù)據(jù)集AWA 和Bridges 上分別進(jìn)行實(shí)驗(yàn)，觀察OH_ReliefF 算法所篩選的特征子集在評(píng)價(jià)指標(biāo)Accuracy、HF1、LCA-F1 和TIE 的結(jié)果，并結(jié)合算法運(yùn)行的時(shí)間來(lái)選擇最佳參數(shù)。OH_ReliefF 算法在不同參數(shù)下的效果性能表現(xiàn)如圖2 所示。

對(duì)Accuracy、H-F1 和LCA-F1 這三個(gè)評(píng)價(jià)指標(biāo)，在使用KNN 分類器（K=10）和LSVM（C=1）分類器時(shí)，從圖2（a）、（b）可以看出，當(dāng)k=20，δ=0.1 時(shí)，OH_ReliefF 算法在數(shù)據(jù)集AWA 上表現(xiàn)出的效果最佳，三個(gè)評(píng)價(jià)指標(biāo)均略高于其他參數(shù)選項(xiàng)；當(dāng)k=25，δ=0.001 時(shí)，各指標(biāo)的結(jié)果為次優(yōu)。從圖2（c）、（d）可以看出，當(dāng)k=25，δ=0.001 時(shí)，在數(shù)據(jù)集Bridges上表現(xiàn)出的效果最佳。

圖2 參數(shù)k和δ的不同取值情況對(duì)OH_Relief算法的影響Fig.2 Influence of different values of parametersk andδ on OH_Relief algorithm

對(duì)TIE 這個(gè)評(píng)價(jià)指標(biāo)，在使用上述兩個(gè)分類器時(shí)，OH_ReliefF 算法在數(shù)據(jù)集AWA 上的結(jié)果相同，但當(dāng)參數(shù)k=25，δ=0.001 時(shí)，數(shù)據(jù)集Bridges 在兩個(gè)分類器上綜合表現(xiàn)低于其他參數(shù)選項(xiàng)。

綜合4 個(gè)評(píng)價(jià)指標(biāo)，參數(shù)k=20，δ=0.1 和參數(shù)k=25，δ=0.001 使得OH_ReliefF 算法能取得較優(yōu)的性能表現(xiàn)。而從圖3 可以看出，k=25，δ=0.001 時(shí)所消耗的時(shí)間要少于k=20，δ=0.1 的情況。

圖3 數(shù)據(jù)集AWA、Bridges在不同參數(shù)時(shí)的運(yùn)行時(shí)間Fig.3 Running times of AWA and Bridges datasets at different parameters

從以上分析結(jié)果可以看出，在不同分類器的情況下，結(jié)合4 個(gè)性能評(píng)價(jià)指標(biāo)和運(yùn)行時(shí)間，算法OH_ReliefF 的性能在取k=25，δ=0.001 時(shí)表現(xiàn)最佳，因此在3.4 節(jié)的實(shí)驗(yàn)中取k=25，δ=0.001 進(jìn)行實(shí)驗(yàn)。

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

為有效驗(yàn)證OH_ReliefF 算法的有效性，本節(jié)實(shí)驗(yàn)選擇5個(gè)當(dāng)前現(xiàn)有的在線流特征選擇算法作為對(duì)比算法，分別是：1）OSFS［8］，設(shè)置α=0.01，該算法此時(shí)達(dá)到最優(yōu)效果；2）Fast-OSFS（簡(jiǎn)稱FOSFS）［8］，設(shè)置α=0.01，該算法此時(shí)達(dá)到最優(yōu)效果；3）OFS-Density（簡(jiǎn)稱OFSD）［16］，設(shè)置α=0.05，該算法此時(shí)達(dá)到最優(yōu)效果；4）SAOLA［17］，設(shè)置α=0.01，該算法此時(shí)達(dá)到最優(yōu)效果；5）A3M［18］。

基于KNN 分類器(K=10)和LSVM 分類器(C=1)，本文在Accuracy、LCA-F1、TIE 比較本文算法與上述5 種算法，結(jié)果如表2～7 所示，加粗?jǐn)?shù)字表示在不同評(píng)價(jià)指標(biāo)中的最優(yōu)結(jié)果，下劃線表示次優(yōu)結(jié)果；“↑”表示數(shù)值越大越好，“↓”表示數(shù)值越小越好。

根據(jù)表2～7 的結(jié)果可以看出：OH_ReliefF 算法在6 個(gè)數(shù)據(jù)集的3 個(gè)評(píng)價(jià)指標(biāo)中的平均性能都排在第一。在KNN 分類器上，所提算法在3 個(gè)數(shù)據(jù)集（DD、F194、VOC）上表現(xiàn)出最優(yōu)的效果，在Bridges 和Cifar 數(shù)據(jù)集中表現(xiàn)次優(yōu)；在LSVM分類器上，數(shù)據(jù)集Cifar 表現(xiàn)出的結(jié)果為次優(yōu)，其他5 個(gè)數(shù)據(jù)集的所有指標(biāo)均是最優(yōu)，在每個(gè)數(shù)據(jù)集上的分類性能較為穩(wěn)定。

表2 基于KNN分類器的分類精度（↑）Tab.2 Classification accuracy based on KNN classifier（↑）

表3 基于KNN分類器的LCA-F1值（↑）Tab.3 LCA-F1 values based on KNN classifier（↑）

表4 基于KNN分類器的TIE值（↓）Tab.4 TIE values based on KNN classifier（↓）

表5 基于LSVM分類器的分類精度（↑）Tab.5 Classification accuracy based on LSVM classifier（↑）

表6 基于LSVM分類器的LCA-F1值（↑）Tab.6 LCA-F1 values based on LSVM classifier（↑）

選擇A3M、OFSD 和OH_ReliefF 這三個(gè)算法在Bridges、DD 和F194 數(shù)據(jù)集上運(yùn)行，算法在不同數(shù)據(jù)集上選擇特征的個(gè)數(shù)如表8 所示?？梢钥闯?，算法A3M 和OFSD 選擇的特征的個(gè)數(shù)過(guò)多或者過(guò)少，而算法OH_ReliefF 選擇出的特征個(gè)數(shù)較為適中，所以在整個(gè)實(shí)驗(yàn)中，OH_ReliefF 在很多方面的性能均優(yōu)于對(duì)比算法，在各個(gè)評(píng)價(jià)指標(biāo)上均表現(xiàn)優(yōu)異，相較于其他算法更加穩(wěn)定。

表7 基于LSVM分類器的TIE值（↓）Tab.7 TIE values based on LSVM classifier（↓）

表8 不同算法在3個(gè)數(shù)據(jù)集上選擇的特征個(gè)數(shù)Tab.8 Number of selected feature of different algorithms on three datasets

4 結(jié)語(yǔ)

本文基于ReliefF 算法提出了一個(gè)面向?qū)哟位瘮?shù)據(jù)的在線流特征選擇算法OH_ReliefF。首先，將兄弟策略與排斥策略相結(jié)合對(duì)ReliefF 算法進(jìn)行改進(jìn)，定義一種新的能夠處理層次化結(jié)構(gòu)數(shù)據(jù)的ReliefF 模型；其次，根據(jù)特征的權(quán)值定義層次分類在線流特征選擇模型框架，分為在線選擇重要特征和在線冗余分析兩個(gè)階段；最后，與五種先進(jìn)的在線流特征選擇算法作對(duì)比，大量的實(shí)驗(yàn)結(jié)果表明本文算法OH_ReliefF在KNN 分類器和LSVM 分類器的各個(gè)評(píng)價(jià)指標(biāo)中均取得了較優(yōu)的結(jié)果。在未來(lái)的工作中，將對(duì)基于圖結(jié)構(gòu)的在線流特征選擇算法進(jìn)行研究。