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

張小清，王晨曦*，呂彥，林耀進

（1.閩南師范大學計算機學院，福建漳州 363000；2.數據科學與智能應用福建省高校重點實驗室，福建漳州 363000）

0 引言

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

圖1 胃腫瘤層次結構Fig.1 Hierarchical structure of gastric tumor

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

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

這些已有的層次特征選擇算法未考慮在線流特征的表現形式，而傳統的在線流特征選擇算法能夠實現動態特征的在線處理，但忽略了類別之間的層次關系。為此，本文基于ReliefF 算法［3］提出層次分類學習在線流特征選擇算法OH_ReliefF（Online Hierarchical streaming feature selection based on ReliefF algorithm）：利用標記之間的層次關系對ReliefF 算法進行改進，使ReliefF 算法能夠處理層次化結構數據，將新的特征權值計算方法與在線重要性分析和在線冗余性分析策略相結合，設計相關算法來構建層次分類學習的在線流特征選擇框架。本文的主要工作如下：

1）在ReliefF 算法的基礎上，將排斥策略與兄弟策略結合作為劃分標記異類的標準，定義一種能夠處理分層數據的特征權重計算方法HF_ReliefF（Hierarchical Feature weights calculated based on ReliefF algorithm）。

2）提出OH_ReliefF，將特征的層次關系與流特征選擇框架相結合，為層次數據集在線選擇一個較優的特征子集。

3）與傳統的在線特征選擇算法相比，本文算法在6 個數據集上的平均預測精度值與次優算法相比提高了10%，在LCA-F1（Lowest Common Ancestor-F1）分層指標上相較于次優算法提高了5%，并且TIE（Tree Induced Error）值降低了25%，說明本文算法可以很好地應對分層流特征選擇問題。

1 相關基礎

1.1 類別的層次結構

在層次分類學習中，一般把類別的層次結構分成樹結構和有向無環圖結構兩種［13］，本文只考慮類別的樹結構關系。樹結構的“從屬”可以用序對(D，?)來表示，具有不可逆性、反自反性和傳遞性［14］等特性，其中D表示樣本的標記空間，?表示從屬關系。對于?di，dj，dk∈D，樹結構的從屬關系的特性描述如下：

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

2）反自反性：di?di。

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

利用樹結構中的從屬關系來表達層次結構中節點之間的父子關系和兄弟關系，描述如下：

1）父子關系：若di?dj，則稱節點dj是節點di的父節點；

2）兄弟關系：若di?dk且dj?dk，則稱節點dj是節點di的兄弟節點，并且節點dk是點節點di、dj的父節點。

1.2 ReliefF算法

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

1）Δf(xi，xj)≥0，當且僅當xi=xj時，Δf(xi，xj)=0。

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

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

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

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

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

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

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

本章將排斥策略與兄弟策略相結合應用到ReliefF 算法中，并將改進的ReliefF 算法拓展到層次分類學習的在線流特征選擇問題，基于ReliefF 算法提出層次分類學習模型的兩種在線特征評估準則。

2.1 層次類別的劃分策略

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

2.2 面向層次化數據的ReliefF算法

定義4矩陣S∈Rl×l用于描述節點之間的兄弟關系，l表示層次樹中葉子節點個數。Si表示與節點di有兄弟關系的集合，Sij的值用來區分節點di和節點dj是否存在兄弟關系。兄弟矩陣S用形式化描述如下：

對于1≤j≤l，若?Sij=1，表示節點dj是節點di的兄弟節點，節點di的異類為dj。此時，節點di也是節點dj的兄弟，可以看出兄弟矩陣S是一個對稱矩陣。

定義5?di∈D，特征f?F衡量對類別di的劃分能力用權重Wdi來表示。權重Wdi如下所示：

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

面向層次化數據的特征權重計算算法HF_ReliefF 描述如算法1 所示：

算法1 HF_ReliefF。

輸入 特征矩陣data∈Rn×p，類別矩陣D∈R1×l，層次樹結構tree，近鄰個數k；

輸出 預測特征權值向量W。

區別于傳統的ReliefF 算法，HF_ReliefF 算法考慮類別之間的層次關系，并且以每個類別作為單位來計算特征的權重，利用特征對近鄰樣本的劃分能力來評價特征的重要性。

2.3 OH_ReliefF算法

為解決層次分類學習中特征空間的動態性和未知性問題，選擇出對決策屬性具有高分離性并且低冗余性的特征，本節基于HF_ReliefF 算法介紹兩種在線評估準則。

2.3.1 在線特征重要性分析

若同類樣本之間的距離越小，異類近鄰樣本之間的距離越大，則特征權值計算結果越大，表明所選特征對決策屬性劃分的能力越大。重要的特征應該使得同類樣本的距離更加接近，而異類樣本之間的距離更遠。

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

2.3.2 在線冗余分析

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

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

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

算法2 OH_ReliefF 算法。

輸入特征矩陣data∈Rn×p，層次樹結構tree，近鄰個數k；

輸出 特征序列S。

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

假設 |U|表示論域U的樣本個數，|F|表示條件屬性F的屬性個數，|l|是層次結構中的葉子節點個數，當前所選特征子集數量為|St|，則計算權重Wt的時間復雜度為；在在線特征重要性分析階段，遍歷所有類別所需時間復雜度是；當執行在線冗余更新階段，算法最差時間復雜度為。

3 實驗與結果分析

3.1 實驗數據集

本文使用6 個數據集來測試OH_ReliefF 算法的性能，其中包括2 個蛋白質數據集和4 個圖像數據集，具體情況如表1 所示。

表1 數據集描述Tab.1 Description of datasets

3.2 評價指標

在本文的實驗中，基于K 最鄰近（K-Nearest Neighbor，KNN）分類器和拉格朗日支持向量機（Lagrangian Support Vector Machine，LSVM）分類器來評價算法的性能。為更好地對面向層次化數據的在線流特征選擇算法進行評價，使用四種評價指標對算法的性能進行分析，分別是：預測精度（Accuracy）、TIE、H-F1（Hierarchical-F1）和LCA-F1。

令D、分別表示樣本真實類別和樣本預測類別，Anc(D)表示類別D的所有祖先節點，Lac(D，)表示類別D，的最近公共祖先節點。D，的層次分類擴展標記分別為：。最小公共祖先節點層次分類擴展標記表示為：。

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

2）TIE 表示在層次結構中真實類別節點D和預測節點-D之間的總邊數：

3）H-F1 表示分層準確率PH和召回率RH的調和平均：

4）LCA-F1 表示預測類別節點-D和真實標記節點D最小公共祖先：

以上4 個性能評價指標，TIE 指標取值越小越好，而Accuracy、H-F1 以及LCA-F1 的取值越大表明算法性能越佳。

3.3 參數分析

為觀察參數k和δ在不同取值情況下對OH_ReliefF 算法的影響，令k=｛10，15，20，25，30｝，δ=｛0.000 1，0.001，0.01，0.1，1｝，在數據集AWA 和Bridges 上分別進行實驗，觀察OH_ReliefF 算法所篩選的特征子集在評價指標Accuracy、HF1、LCA-F1 和TIE 的結果，并結合算法運行的時間來選擇最佳參數。OH_ReliefF 算法在不同參數下的效果性能表現如圖2 所示。

對Accuracy、H-F1 和LCA-F1 這三個評價指標，在使用KNN 分類器（K=10）和LSVM（C=1）分類器時，從圖2（a）、（b）可以看出，當k=20，δ=0.1 時，OH_ReliefF 算法在數據集AWA 上表現出的效果最佳，三個評價指標均略高于其他參數選項；當k=25，δ=0.001 時，各指標的結果為次優。從圖2（c）、（d）可以看出，當k=25，δ=0.001 時，在數據集Bridges上表現出的效果最佳。

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

對TIE 這個評價指標，在使用上述兩個分類器時，OH_ReliefF 算法在數據集AWA 上的結果相同，但當參數k=25，δ=0.001 時，數據集Bridges 在兩個分類器上綜合表現低于其他參數選項。

綜合4 個評價指標，參數k=20，δ=0.1 和參數k=25，δ=0.001 使得OH_ReliefF 算法能取得較優的性能表現。而從圖3 可以看出，k=25，δ=0.001 時所消耗的時間要少于k=20，δ=0.1 的情況。

圖3 數據集AWA、Bridges在不同參數時的運行時間Fig.3 Running times of AWA and Bridges datasets at different parameters

從以上分析結果可以看出，在不同分類器的情況下，結合4 個性能評價指標和運行時間，算法OH_ReliefF 的性能在取k=25，δ=0.001 時表現最佳，因此在3.4 節的實驗中取k=25，δ=0.001 進行實驗。

3.4 實驗結果分析

為有效驗證OH_ReliefF 算法的有效性，本節實驗選擇5個當前現有的在線流特征選擇算法作為對比算法，分別是：1）OSFS［8］，設置α=0.01，該算法此時達到最優效果；2）Fast-OSFS（簡稱FOSFS）［8］，設置α=0.01，該算法此時達到最優效果；3）OFS-Density（簡稱OFSD）［16］，設置α=0.05，該算法此時達到最優效果；4）SAOLA［17］，設置α=0.01，該算法此時達到最優效果；5）A3M［18］。

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

根據表2～7 的結果可以看出：OH_ReliefF 算法在6 個數據集的3 個評價指標中的平均性能都排在第一。在KNN 分類器上，所提算法在3 個數據集（DD、F194、VOC）上表現出最優的效果，在Bridges 和Cifar 數據集中表現次優；在LSVM分類器上，數據集Cifar 表現出的結果為次優，其他5 個數據集的所有指標均是最優，在每個數據集上的分類性能較為穩定。

表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 這三個算法在Bridges、DD 和F194 數據集上運行，算法在不同數據集上選擇特征的個數如表8 所示。可以看出，算法A3M 和OFSD 選擇的特征的個數過多或者過少，而算法OH_ReliefF 選擇出的特征個數較為適中，所以在整個實驗中，OH_ReliefF 在很多方面的性能均優于對比算法，在各個評價指標上均表現優異，相較于其他算法更加穩定。

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

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

4 結語

本文基于ReliefF 算法提出了一個面向層次化數據的在線流特征選擇算法OH_ReliefF。首先，將兄弟策略與排斥策略相結合對ReliefF 算法進行改進，定義一種新的能夠處理層次化結構數據的ReliefF 模型；其次，根據特征的權值定義層次分類在線流特征選擇模型框架，分為在線選擇重要特征和在線冗余分析兩個階段；最后，與五種先進的在線流特征選擇算法作對比，大量的實驗結果表明本文算法OH_ReliefF在KNN 分類器和LSVM 分類器的各個評價指標中均取得了較優的結果。在未來的工作中，將對基于圖結構的在線流特征選擇算法進行研究。