基于文本分類的Fisher Score 快速多標(biāo)記特征選擇算法

汪正凱，沈東升，王晨曦

（1.福建省粒計(jì)算及其應(yīng)用重點(diǎn)實(shí)驗(yàn)室，福建 漳州 363000；2.閩南師范大學(xué) 計(jì)算機(jī)學(xué)院，福建 漳州 363000）

0 概述

在傳統(tǒng)的單標(biāo)記監(jiān)督學(xué)習(xí)中，樣本僅由一個(gè)標(biāo)記屬性描述，這種假設(shè)常違背現(xiàn)實(shí)生活的真實(shí)情況。在一類非互斥屬性中，樣本的標(biāo)記屬性可能同時(shí)包含多個(gè)語義信息，例如，一部電影可能是喜劇電影的同時(shí)也是愛情電影，在這種情況下，單一屬性標(biāo)記無法有效地對(duì)樣本進(jìn)行類別劃分，因此一種多標(biāo)記學(xué)習(xí)框架［1-3］被提出。相對(duì)于單標(biāo)記學(xué)習(xí)，在多標(biāo)記學(xué)習(xí)中，每一個(gè)樣本具有多個(gè)以上的屬性標(biāo)記，在非分層任務(wù)中，樣本在屬性標(biāo)記下僅有二值取值，即為正或負(fù)，將樣本所有標(biāo)記中具有正值的標(biāo)記稱為標(biāo)記集合，樣本的標(biāo)記集合即構(gòu)成了對(duì)樣本屬性的完整描述。隨著數(shù)據(jù)挖掘技術(shù)與移動(dòng)互聯(lián)網(wǎng)技術(shù)的發(fā)展，數(shù)據(jù)的規(guī)模不斷增長，描述樣本屬性的標(biāo)記集合的規(guī)模也隨之增長，而豐富的標(biāo)記集合往往需要高維的特征空間描述［4］。但過高的特征維度會(huì)使得學(xué)習(xí)器的消耗提升，同時(shí)一些噪聲特征也會(huì)對(duì)分類結(jié)果產(chǎn)生影響，最終降低分類精度［5］。因此，高維特征帶來的維度災(zāi)難［6］已經(jīng)成為多標(biāo)記學(xué)習(xí)面臨的重要挑戰(zhàn)之一。

作為一種有效的特征降維技術(shù)，特征選擇［7］的目的是在保持學(xué)習(xí)器性能不改變太多的前提下能夠有效地約簡數(shù)據(jù)集的維度。目前，針對(duì)多標(biāo)記學(xué)習(xí)任務(wù)的特征選擇算法已有很多，這些算法按照與學(xué)習(xí)器的關(guān)系可以分為過濾式［7-9］、包裝式［10］和嵌入式3 種。其中過濾式不依賴于學(xué)習(xí)器，而是尋找獨(dú)立指標(biāo)來評(píng)價(jià)每個(gè)特征對(duì)分類能力的貢獻(xiàn)大小，以此過濾出含有更豐富信息的特征子集［11-12］，或以某個(gè)評(píng)價(jià)指標(biāo)結(jié)合搜索算法來搜索特征子集［13-14］，前者需要預(yù)設(shè)閾值，而后者可根據(jù)搜索策略自動(dòng)結(jié)束算法；相對(duì)于過濾式特征選擇算法，包裝式特征選擇算法以特征子集在分類器上的分類性能作為搜索指標(biāo)指導(dǎo)搜索方向，嵌入式特征選擇算法在進(jìn)行特征選擇的過程中即同時(shí)進(jìn)行了學(xué)習(xí)器的訓(xùn)練。因此，在算法運(yùn)行時(shí)間和計(jì)算資源的消耗以及模型的普適性上，過濾式特征選擇算法具有更大的優(yōu)勢(shì)。

Fisher Score（FS）作為一種基于距離度量的特征評(píng)價(jià)指標(biāo)，通過計(jì)算類間散度與類內(nèi)聚度的關(guān)系度量特征分類能力的強(qiáng)弱，在單標(biāo)記監(jiān)督學(xué)習(xí)中已有了較多的研究與應(yīng)用。XIE 等［15］提出一種基于改進(jìn)的F-score 和支持向量機(jī)的包裝式特征選擇方法，以SVM 分類器的分類結(jié)果指導(dǎo)搜索方向；SONG 等［16］提出了不均勻分布下的FS 特征選擇算法，以兩兩類別之間的距離代替類與總體中心的距離作為類間散度的計(jì)算方式；MUHAMMED［17］等提出一種結(jié)合FS評(píng)價(jià)準(zhǔn)則和貪心搜索的特征選擇算法，在阿爾茨海默病的分類上取得了較好的結(jié)果；SONG［16］等提出一種基于Fisher 判別分析（FDA）和F-score 的特征排序方法用以多類樣本分類，BEHESHTI［18］提出一種集合FS 評(píng)價(jià)準(zhǔn)則和T 檢驗(yàn)分?jǐn)?shù)來尋找最優(yōu)的特征集的特征選擇算法。

然而，以上的算法都忽略了樣本極值對(duì)類中心帶來的偏差影響，以距離度量的類中心的意義僅在統(tǒng)計(jì)學(xué)上得以體現(xiàn)，在實(shí)際應(yīng)用中很容易被異常值影響，當(dāng)方差很小的一類樣本中加入一個(gè)相對(duì)量綱較大的樣本時(shí)，會(huì)使得該類樣本的中心發(fā)生偏移，此時(shí)需要對(duì)該異常值進(jìn)行處理以避免最終FS 得分產(chǎn)生誤差。同時(shí)，上述算法都僅能應(yīng)用于單標(biāo)記特征選擇，而多標(biāo)記任務(wù)更能體現(xiàn)生活中的實(shí)際情況，因此將單標(biāo)記任務(wù)下的FS 算法應(yīng)用于多標(biāo)記任務(wù)具有一定的實(shí)際研究意義?；诖耍疚奶岢鲆环N多標(biāo)記FS 特征選擇算法，計(jì)算每個(gè)樣本在各個(gè)標(biāo)記下經(jīng)過去極值后的特征集合的FS 得分，若多標(biāo)記任務(wù)中標(biāo)記包含信息對(duì)分類的貢獻(xiàn)，則根據(jù)樣本具有的標(biāo)記數(shù)量可以得到該樣本標(biāo)記集合的標(biāo)記權(quán)值，以此更新樣本在特征空間下的FS 得分。

1 相關(guān)知識(shí)

FS 是一種經(jīng)典的評(píng)價(jià)特征對(duì)分類貢獻(xiàn)能力的指標(biāo)，特征的FS 得分越高，表明在該特征下類內(nèi)樣本間間距盡可能得小，類間樣本間距盡可能得大，即類間樣本間距與類內(nèi)樣本間距的比值越大。在傳統(tǒng)單標(biāo)記學(xué)習(xí)中FS 的相關(guān)描述如下：

disinner和disouter分別表示在特征fj下所有類別的類內(nèi)距離與所有類與樣本中心類間距離的和，可分別稱為特征fj下的類內(nèi)聚度與類間散度。當(dāng)類內(nèi)聚度越小時(shí)，樣本類內(nèi)分布越稠密，類間散度越大，樣本類間分布越稀疏，由于特征辨識(shí)類別的能力與該特征下的類間散度和類內(nèi)聚度比值成正相關(guān)，則定義特征fj對(duì)類別辨識(shí)的能力評(píng)價(jià)指標(biāo)FS 如下：

式（3）為單個(gè)特征下的FS 得分計(jì)算公式，若以單個(gè)特征的FS 得分作為評(píng)價(jià)指標(biāo)，則可計(jì)算出所有特征的FS 得分，通過設(shè)置閾值篩選出特征子集。若采用啟發(fā)式搜索的方式篩選特征子集，則需要設(shè)置合適的搜索策略，不斷迭代搜索當(dāng)前候選子集中的最優(yōu)特征，直至滿足搜索終止條件，得到最終的特征子集。相對(duì)于啟發(fā)式搜索，前者的時(shí)間復(fù)雜度更低，算法性能消耗更少。

2 基于多標(biāo)記FS 的特征選擇模型

式（3）給出了在單標(biāo)記學(xué)習(xí)下任意特征的FS 得分的計(jì)算公式，但都是直接對(duì)一類樣本計(jì)算其均值作為類中心，并沒考慮到極值帶來的方差增大的影響，假設(shè)某一特征下所有樣本的劃分情況如圖1 所示。其中，直線兩邊表示各自不同的一類樣本，圓圈選中的樣本代表多數(shù)真實(shí)樣本的分布，圓圈的圓心代表這些樣本的中心點(diǎn)，而圓圈外樣本會(huì)使得類樣本的中心點(diǎn)發(fā)生偏移，極端值樣本距離多數(shù)樣本越遠(yuǎn)，偏移程度越大，而在理想狀況下是同類樣本盡可能分布在一起，因此，需要根據(jù)類別樣本的分布情況對(duì)已劃分的樣本進(jìn)行處理，去除其中距離多數(shù)樣本較遠(yuǎn)的樣本，再對(duì)剩下的樣本進(jìn)行FS 得分計(jì)算。

圖1 類中心偏差示意圖Fig.1 Schematic diagram of class center deviation

同時(shí)式（3）僅能應(yīng)用于單標(biāo)記特征選擇，但在更復(fù)雜的多標(biāo)記學(xué)習(xí)中，式（3）無法直接應(yīng)用，若將多標(biāo)記任務(wù)簡單地分解為多個(gè)單標(biāo)記任務(wù)再應(yīng)用式（3），則會(huì)損失多標(biāo)記任務(wù)中標(biāo)記集合之間的關(guān)聯(lián)信息，基于此，考慮從樣本角度對(duì)標(biāo)記集合進(jìn)行遍歷，且針對(duì)各個(gè)標(biāo)記對(duì)整體標(biāo)記集合的貢獻(xiàn)值，將樣本的標(biāo)記集合下的全體特征的FS 得分與根據(jù)樣本本身具有的標(biāo)記集合所得出的標(biāo)記權(quán)值系數(shù)相乘，以此更新FS 的計(jì)算公式。

下文將給出相關(guān)定義來描述本文算法模型。假設(shè)存在一個(gè)決策系統(tǒng)其中論域U={x1，x2，…，xn}∈?n×m為全體樣 本組成的 非空有限 集合，xi∈U是維度為1×m的一維向量，表示論域U中的第i個(gè)樣本，A={f1，f2，…，fm}為全體特征組成的集合，fj∈A表示特征集合中第j個(gè)特征，為論域U中的一個(gè)實(shí)值，表示樣本xi在特征fj下的取值，D={y1，y2，…，yn}∈?n×l為樣本的標(biāo)記集合，yi∈D是維度為1×l的一維向量，表示標(biāo)記集合D中第i個(gè)樣本xi在全體決策屬性上的標(biāo)記結(jié)果為xi在第k個(gè)標(biāo)記上的標(biāo)記結(jié)果，在多標(biāo)記學(xué)習(xí)中，xi在標(biāo)記k下被標(biāo)記時(shí)，反之=0，且對(duì)任意 一個(gè)樣本xi，有≥1。綜合上述條件，有如下定義：

定義1假設(shè)存在一個(gè)隨機(jī)樣本xi∈U，xi的標(biāo)記集合為yi，定義xi在標(biāo)記空間上的真實(shí)標(biāo)記集合y_truei如下：

定義2假設(shè)存在一個(gè)隨機(jī)樣本xi∈U，xi的真實(shí)標(biāo)記集合為y_truei，對(duì)任意標(biāo)記k∈y_truei，則標(biāo)記k將論域U劃分如下：

其中：c表示樣本xr在標(biāo)記k下的值表示論域U中在標(biāo)記k下具有值為c的樣本組成的集合。

xi的真實(shí)標(biāo)記集合y_truei對(duì)論域U的劃分結(jié)果分布如下：

定義3假設(shè)存在一個(gè)隨機(jī)樣本xi∈U，有一個(gè)劃分情況Uk∈Ui，Uk中的任意一類樣本集合在特征fj下的均值如下：

定義4假設(shè)存在一個(gè)隨機(jī)樣本xi∈U，在標(biāo)記k劃分的論域空間中存在一個(gè)樣本類別集合，其中距離該類中心點(diǎn)最遠(yuǎn)的一個(gè)樣本為xmax，則定義該類中心點(diǎn)的有效樣本集合如下：

其中：dis_xmax表示xmax距離中心點(diǎn)的距離；δ∈(0，1]表示半徑系數(shù)，且δ和樣本數(shù)量正相關(guān)，當(dāng)δ=1 時(shí)，即相當(dāng)于不做中心偏移操作。

定義5假設(shè)存在一個(gè)隨機(jī)樣本xi∈U，有劃分情況Uk∈Ui，Uk中任一類樣本集合在特征fj上經(jīng)過中心偏移之后的樣本集合為，則特征fj在隨機(jī)樣本xi的標(biāo)記k劃分論域U加中心偏移處理之后的FS 得分如下：

其中：分子表示類間散度，相對(duì)于原始的每一類減去總體中心，在類別之間計(jì)算距離可以避免不均勻分布情況下的類間散度差異表示隨機(jī)樣本xi的標(biāo)記k的權(quán)值系數(shù)，為k與xi的真實(shí)標(biāo)記集合y_truei中的其余標(biāo)記的余弦系數(shù)的和再加1，如果樣本只具有1 個(gè)標(biāo)記，則為1，可以理解為標(biāo)記k與其余標(biāo)記的額外信息，顯然隨機(jī)樣本的真實(shí)標(biāo)記數(shù)量越多，任一標(biāo)記k的權(quán)值系數(shù)越大，因?yàn)闃?biāo)記數(shù)量越大，其中包含的分類信息應(yīng)當(dāng)更多，所以FS 分?jǐn)?shù)計(jì)算更加重視具有更多標(biāo)記的情況。

定義6假設(shè)存在一個(gè)隨機(jī)樣本xi∈U，xi的真實(shí)標(biāo)記集合為y_truei，根據(jù)式（11）得出特征fj在xi的標(biāo)記k上的FS 得分，則定義fj在整體標(biāo)記集合y_truei上的FS 得分如下：

根據(jù)式（12）可得出特征fj在全體樣本上的FS得分如下：

式（13）是單個(gè)特征的FS 得分，則最終全體特征集合A的FS 得分為：

式（14）為全體特征的FS 得分分布，對(duì)FS 進(jìn)行降序可以得到分類能力更強(qiáng)的特征，從而實(shí)現(xiàn)特征選擇的目標(biāo)。

上述定義中之所以采用全體采樣，是因?yàn)閷?duì)全體樣本的遍歷使得所提算法的結(jié)果具有較強(qiáng)的魯棒性，避免隨機(jī)采樣所導(dǎo)致結(jié)果產(chǎn)生不確定性。定義3和定義4 對(duì)一類樣本進(jìn)行了中心偏移操作，前提是該類樣本數(shù)量較多，因?yàn)閿?shù)量較少時(shí)，并不足以準(zhǔn)確地決定多數(shù)樣本的類中心，但并不是全部數(shù)據(jù)集中每個(gè)標(biāo)記下每類的樣本數(shù)量都足夠多，基于此在后續(xù)實(shí)驗(yàn)中進(jìn)行到中心偏移操作前都會(huì)對(duì)該類樣本數(shù)量進(jìn)行檢測(cè)，當(dāng)該類樣本數(shù)量占總體樣本數(shù)量比例小于0.05 時(shí)，即不進(jìn)行中心偏移操作。式（11）中類間散度計(jì)算沒有采用原始FS 計(jì)算類間散度的方式，而是改用了文獻(xiàn)［18］中提出的方式，該計(jì)算方式如式（15）所示：

其中：D(fi)表示特征fi的類間散度；p、q分別表示類別p和類別q；np表示類別p的數(shù)量；N為全體樣本數(shù)量；表示類別p在特征fi上的均值。可以看出，式（15）是采用類別間的序關(guān)系來實(shí)現(xiàn)類別間的兩兩距離計(jì)算，以避免類間重復(fù)計(jì)算。本文模型的算法流程如算法1 所示。

算法1MLFS 算法

在算法MLFS 中，主要的計(jì)算消耗在于對(duì)每個(gè)標(biāo)記k計(jì)算其FS 得分，若假設(shè)某數(shù)據(jù)集有n個(gè)樣本、m個(gè)特征和l個(gè)標(biāo)記，平均每個(gè)樣本在標(biāo)記空間上的標(biāo)記數(shù)量為LC，則計(jì)算全體特征的FS 得分的代價(jià)為O(m)，步驟3 計(jì)算全體標(biāo)記下的FS 得分的代價(jià)為O(m·l)，步驟4～步驟6 并沒有太多計(jì)算消耗，計(jì)算代價(jià)為O(n·LC)，步驟7 的排序代價(jià)為O(mlogam)，算法MLFS 的主要計(jì)算消耗在于計(jì)算每個(gè)標(biāo)記下的FS 得分，且并不依賴于任何分類器。

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

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

為驗(yàn)證本文算法的有效性，選取MuLan 庫中的8 個(gè)公開多標(biāo)記數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。由于數(shù)據(jù)集在MuLan 庫中已經(jīng)分好，訓(xùn)練集和測(cè)試集會(huì)直接采用已經(jīng)分好的結(jié)果，在訓(xùn)練集中對(duì)所提算法進(jìn)行特征選擇，再將特征選擇結(jié)果應(yīng)用于測(cè)試集進(jìn)行分類測(cè)試，數(shù)據(jù)集的詳細(xì)信息如表1 所示。

表1 多標(biāo)記數(shù)據(jù)集Table 1 Multi-label datasets

3.2 實(shí)驗(yàn)環(huán)境及評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)運(yùn)行環(huán)境為Pycharm Professional 2019.2.3+Python 3.7.1 64 位，硬件環(huán)境 為Inter?Xeon?CPU E5-26xx series 2.49 Hz，16 GB內(nèi)存，操作系統(tǒng) 為Windows10 64 位。實(shí)驗(yàn)采用5 種評(píng)價(jià)指標(biāo)［14］：Average Precision，Hamming Loss，One Error，Ranking Loss，Coverage，分別簡寫為AP、HL、OE、RL、Cov，其中，HL、OE 的計(jì)算基于標(biāo)記預(yù)測(cè)，AP、RL、Cov 基于標(biāo)記排序，AP 指標(biāo)表示數(shù)值越高，分類性能越好，其余指標(biāo)表示數(shù)值越低，分類性能越好。

3.3 相關(guān)參數(shù)設(shè)置及算法選擇

本文算法是通過設(shè)置半徑系數(shù)δ來選擇有效樣本集合的，因此不同大小的半徑系數(shù)會(huì)選取不同規(guī)模的樣本集合，實(shí)驗(yàn)會(huì)首先比較不同大小的半徑系數(shù)對(duì)實(shí)驗(yàn)結(jié)果產(chǎn)生的影響。

為比較本文算法的有效性，選擇了各類型的多標(biāo)記特征選擇算法作為對(duì)比算法，分別為基于蟻群優(yōu)化的多標(biāo)簽特征選擇算法（MLACO）［19］、多標(biāo)記ReliefF 特征選擇算法（MLRF）［8］、基于多變量互信息的多標(biāo)記特征選擇算法（PMU）［9］和多標(biāo)簽樸素貝葉斯分類的特征選擇算法（MLNB）［14］，其中MLACO為PANIRI 等提出的一種基于蟻群算法（ACO）的多標(biāo)記特征選擇算法，通過同時(shí)引入計(jì)算標(biāo)記相關(guān)性的有監(jiān)督啟發(fā)式函數(shù)與計(jì)算特征空間冗余性的無監(jiān)督啟發(fā)式函數(shù)在特征空間迭代搜索最優(yōu)子集，是一種最新的性能優(yōu)異的多標(biāo)記特征選擇算法；MLRF算法是基于距離度量的多標(biāo)記ReliefF 算法，通過引入漢明距離在標(biāo)記集合上尋找樣本的同類與異類近鄰；PMU 算法是LEE 等提出的基于互信息度量的特征選擇算法，通過三元互信息度量特征子集與標(biāo)記集合間的相關(guān)性；MLNB 是ZHOU 等提出的基于主成分提取PCA 和遺傳算法（GA）的混合型特征降維算法。

上述算法兼顧各種類型，便于本文所提算法與各類型算法進(jìn)行比較。在對(duì)比算法的參數(shù)設(shè)置上，MLACO 算法參數(shù)與原文保持不變；MLRF 采用全體采樣方式，近鄰個(gè)數(shù)設(shè)為5；PMU 算法需要先進(jìn)行離散化，以PMU 算法離散化方式為標(biāo)準(zhǔn)對(duì)實(shí)驗(yàn)數(shù)據(jù)預(yù)先進(jìn)行了兩折離散化；MLNB 設(shè)置一階段預(yù)留特征比例ratio 為0.7，平滑因子默認(rèn)為1。在特征數(shù)量的選擇上，由于MLNB 算法可以直接得到一個(gè)特征子集，而其他算法得到排序后的特征集，則按照MLNB算法得到的特征子集數(shù)量，在其他算法排序后的特征子集上取相同數(shù)量的特征子集進(jìn)行對(duì)比。

此外，實(shí)驗(yàn)所采用的分類器為MLKNN［20］分類器，默認(rèn)近鄰個(gè)數(shù)為10，平滑因子為1。

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

本文首先比較所提算法中參數(shù)δ對(duì)實(shí)驗(yàn)結(jié)果的影響，由于δ是一類樣本中心點(diǎn)選擇樣本的距離范圍占一類樣本中距離該類樣本中心點(diǎn)最遠(yuǎn)的樣本到中心點(diǎn)的距離的比例，實(shí)驗(yàn)設(shè)置3 個(gè)數(shù)據(jù)集在δ∈(0，]1 上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖2 所示。

圖2 各數(shù)據(jù)集上不同半徑系數(shù)隨著特征比例變化的情況Fig.2 Variation of different radius coefficients with feature proportion on each datasets

圖2 中選擇 了Computer、Health、Recreation 3 個(gè)數(shù)據(jù)集，在每一類數(shù)據(jù)集中，橫線表示不做中心偏移的算法取全部特征的分類結(jié)果?？梢钥闯?，在文本類數(shù)據(jù)集中，基本符合半徑系數(shù)越大分類性能越好的預(yù)期，這是由于文本類數(shù)據(jù)集中特征空間較為稀疏，在半徑系數(shù)較小時(shí)會(huì)損失多數(shù)樣本，而期望效果是僅去除小部分極端值樣本，因此分類結(jié)果較差。隨著半徑系數(shù)的增大，Computer 數(shù)據(jù)集中分類性能逐漸提升，而其余數(shù)據(jù)集中并沒有很明顯的變化，這是由于半徑系數(shù)是基于離類中心點(diǎn)最遠(yuǎn)樣本的比例確定的，可能存在一種情況，當(dāng)該樣本離類中心點(diǎn)足夠遠(yuǎn)時(shí)，此時(shí)半徑系數(shù)選擇0.5 或者0.9，而篩選的樣本數(shù)量是一樣的，對(duì)于這種情況，可以選擇加入數(shù)量判定，當(dāng)不同比例下半徑系數(shù)篩選的樣本數(shù)量不變時(shí)，選擇原有類別樣本數(shù)量的80%或者90%作為新的一類樣本。但所提的算法模型是基于全體樣本遍歷的，且在多標(biāo)記任務(wù)下每個(gè)標(biāo)記的劃分情況不同，盡管上述異常情況可能出現(xiàn)，但在全體樣本數(shù)量n×LC（LC 為每個(gè)樣本的平均標(biāo)記數(shù)量）個(gè)標(biāo)記的平均下，異常情況的影響會(huì)盡可能地被降低，因此所提算法沒有加入數(shù)量篩選這一步驟。

綜合以上分析可以得出，半徑系數(shù)的確定需要預(yù)先知道平均類樣本的分布情況，而在多數(shù)文本數(shù)據(jù)集中，特征空間是較為稀疏的，這使得在文本數(shù)據(jù)集中可以預(yù)先設(shè)定較大的半徑系數(shù)，基于此，在后續(xù)實(shí)驗(yàn)中，將所有實(shí)驗(yàn)數(shù)據(jù)集的半徑系數(shù)設(shè)定為0.9。

為了更加詳細(xì)地驗(yàn)證所提算法的有效性，將所提算法與4 種對(duì)比算法在所有數(shù)據(jù)集中進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表2～表7 所示，其中加粗字體為結(jié)果最優(yōu)。

表2 各數(shù)據(jù)集選擇特征數(shù)Table 2 Numbers of selected features of each datasets

表3 AP 評(píng)價(jià)指標(biāo)下各算法的性能比較Table 3 Performance comparison of each algorithms under AP evaluation index

表4 HL 評(píng)價(jià)指標(biāo)下各算法的性能比較Table 4 Performance comparison of each algorithms under HL evaluation index

表5 Cov 評(píng)價(jià)指標(biāo)下各算法的性能比較Table 5 Performance comparison of each algorithms under Cov evaluation index

表6 OE 評(píng)價(jià)指標(biāo)下各算法的性能比較Table 6 Performance comparison of each algorithms under OE evaluation index

表7 RL 評(píng)價(jià)指標(biāo)下各算法的性能比較Table 7 Performance comparison of each algorithms under RL evaluation index

由以上實(shí)驗(yàn)結(jié)果可以看出，本文MLFS 算法在Art、Business、Computer、Education、Enter、Health、Recreation、Reference 等8 個(gè)數(shù)據(jù)集中的各項(xiàng)指標(biāo)的平均值都為最優(yōu)，表明所提算法在整體上相對(duì)其余算法具有一定優(yōu)勢(shì)，對(duì)比各個(gè)指標(biāo)可以發(fā)現(xiàn)：

1）在AP 指標(biāo)上，MLFS算法僅在Reference 數(shù)據(jù)集中排名第2，在其余數(shù)據(jù)集中都是排名第1，且平均排序結(jié)果排名第1。綜合比較4 種對(duì)比算法，MLFS 算法選擇的特征子集分類性能達(dá)到最優(yōu)。

2）在HL 指標(biāo)上，MLFS 算法僅 在Computer 數(shù)據(jù)集中排名第2，在其余數(shù)據(jù)集中都是排名第1，且平均排序結(jié)果排名第1。綜合比較4 種對(duì)比算法，MLFS 算法選擇的特征子集分類性能達(dá)到最優(yōu)。

3）在Cov 指標(biāo)上，MLFS 算法僅在Art、Health 數(shù)據(jù)集中排名第2，在其余數(shù)據(jù)集中都是排名第1，且平均排序結(jié)果排名第1。綜合比較4 種對(duì)比算法，MLFS 算法選擇的特征子集分類性能達(dá)到最優(yōu)。

4）在OE 指標(biāo)上，MLFS 算法僅在Reference 數(shù)據(jù)集中排名第2，在其余數(shù)據(jù)集中都是排名第1，且平均排序結(jié)果排名第1。綜合比較4 種對(duì)比算法，MLFS 算法選擇的特征子集分類性能達(dá)到最優(yōu)。

5）在RL 指標(biāo)上，MLFS 算法在Art、Computer、Health 數(shù)據(jù)集中排名第2，在其余數(shù)據(jù)集中都是排名第1，且平均排序結(jié)果排名第1。綜合比較4 種對(duì)比算法，MLFS 算法選擇的特征子集分類性能達(dá)到最優(yōu)。

6）在約簡特征數(shù)量上，MLFS 算法相對(duì)于原始特征空間約簡了70%以上的特征比例仍具有較好的效果，表明所提算法實(shí)現(xiàn)了特征選擇的降維目標(biāo)。

7）綜合比較8 個(gè)數(shù)據(jù)集在5 個(gè)指標(biāo)上的40 種分類情況，所提算法MLFS 具有最優(yōu)結(jié)果的有32 種，占比80%，表明所提算法具有較好的穩(wěn)定性。

上述實(shí)驗(yàn)結(jié)果表明，所提算法選擇的特征子集在后續(xù)的分類結(jié)果的各個(gè)指標(biāo)上相比其余4 種算法具有領(lǐng)先優(yōu)勢(shì)，同時(shí)具有較高的約簡比例，驗(yàn)證了所提算法的有效性和魯棒性。

為避免出現(xiàn)局部優(yōu)勢(shì)帶來的誤差影響，下文將給出部分?jǐn)?shù)據(jù)集各特征選擇算法在不同特征比例下的分類情況，由于所選數(shù)據(jù)集較多，且針對(duì)每一種指標(biāo)共有40 種對(duì)比情況，限于篇幅，只選擇了其中6 個(gè)數(shù)據(jù)集在5 種指標(biāo)上的結(jié)果進(jìn)行展示，其中，MLNB算法因?yàn)橹荒艿玫揭粋€(gè)特征子集，并不能與其他算法一起比較特征比例上的分類性能，所以未給出變化情況。變化趨勢(shì)如圖3～圖7 所示。

圖3 AP 評(píng)價(jià)指標(biāo)下各算法分類性能的變化情況Fig.3 Change situation of classification performance of each algorithms under AP evaluation index

圖4 HL 評(píng)價(jià)指標(biāo)下各算法分類性能的變化情況Fig.4 Change situation of classification performance of each algorithms under HL evaluation index

圖5 Cov 評(píng)價(jià)指標(biāo)下各算法分類性能的變化情況Fig.5 Change situation of classification performance of each algorithms under Cov evaluation index

圖6 OE 評(píng)價(jià)指標(biāo)下各算法分類性能的變化情況Fig.6 Change situation of classification performance of each algorithms under OE evaluation index

圖7 RL 評(píng)價(jià)指標(biāo)下各算法分類性能的變化情況Fig.7 Change situation of classification performance of each algorithms under RL evaluation index

從圖3～圖7 的變化趨勢(shì)可以看出：本文算法MLFS在各個(gè)指標(biāo)上均優(yōu)于其余算法，且在AP、HL 指標(biāo)中的優(yōu)勢(shì)較為明顯，在其余指標(biāo)中除MLACO 算法外，均大幅優(yōu)于其余算法。在選取的特征比例上，本文算法在特征比例較小時(shí)即能達(dá)到較好的分類性能，表明本文算法基本能夠?qū)崿F(xiàn)特征選擇的目標(biāo)。

為從統(tǒng)計(jì)學(xué)意義上進(jìn)一步檢測(cè)所提算法與4種對(duì)比算法在各項(xiàng)指標(biāo)上是否存在顯著差異，將采用顯著 性水平為10% 的Nemenyi test［18］對(duì)所提算法和其余算法進(jìn)行比較。根據(jù)表3～表7 獲得各個(gè)算法在所有數(shù)據(jù)上的平均排序，排序結(jié)果如表8所示。

表8 各算法在不同評(píng)價(jià)指標(biāo)下的平均排序Table 8 Average ranking of each algorithm under different evaluation indexes

在表8 中，若2 個(gè)算法在所有數(shù)據(jù)集上的平均排序的差值小于臨界差值（Critical Difference，CD），則認(rèn)為2 個(gè)算法并沒有性能上的顯著性差異，由于實(shí)驗(yàn)所采用數(shù)據(jù)集個(gè)數(shù)為8，總算法個(gè)數(shù)為5，根據(jù)臨界差值計(jì)算公式可以得出CD 為1.944，則根據(jù)臨界差值給出各算法在不同指標(biāo)上的臨界差值圖，其中算法根據(jù)平均排名在坐標(biāo)軸中由左向右排列，且與所提算法沒有明顯性能差異的算法用一根加粗的實(shí)線相連，臨界差值如圖8 所示。從圖8 可以看出，本文算法在5 種評(píng)價(jià)指標(biāo)中性能均排名第1，在除RL指標(biāo)外的其余指標(biāo)中，本文算法與MLNB、PMU、MLRF 算法具有顯著的性能差異，與MLACO 算法沒有顯著差異，在RL 指標(biāo)中，本文算法與MLNB、MLRF 算法具有顯著的性能差異，與PMU、MLACO算法沒有顯著的性能差異。綜合上述情況，本文算法與4 種對(duì)比算法的統(tǒng)計(jì)結(jié)果中，性能處于最優(yōu)，表明所提算法的有效性和魯棒性。

圖8 各算法綜合性能比較Fig.8 Comprehensive performance comparison of each algorithms

此外，由于不同的特征選擇算法應(yīng)有其適用的學(xué)習(xí)任務(wù)，在實(shí)際應(yīng)用中應(yīng)根據(jù)不同的情況選擇適合的算法。在上述實(shí)驗(yàn)中，本文算法與其他算法均是在Yahoo網(wǎng)頁文本數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)類型較為單一，為驗(yàn)證所提算法的普適性，本文選擇2 個(gè)不同類型的數(shù)據(jù)集Scene 和Yeast 進(jìn)行實(shí)驗(yàn)。Scene 數(shù)據(jù)集是一類語義索引類圖像數(shù)據(jù)集，樣本數(shù)為2 407，特征數(shù)為294，標(biāo)記數(shù)為6，Yeast是一類關(guān)于酵母菌基因的生物數(shù)據(jù)集，樣本數(shù)量為2 417，特征數(shù)為103，標(biāo)記數(shù)為14。由于未知數(shù)據(jù)集特征空間的密集程度，因此無法事先確定所提算法中的半徑系數(shù)δ，基于此，測(cè)試3 個(gè)不同尺度的半徑系數(shù)，分別為0.1、0.5、0.9，將3 種不同的半徑系數(shù)作為算法的參數(shù)與4 種對(duì)比算法在Scene 和Yeast 數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖9 所示。從圖9 可以看出：并不是半徑系數(shù)越大越好，因?yàn)橄鄬?duì)于特征空間較為稀疏的文本類數(shù)據(jù)集，Scene 數(shù)據(jù)集上的樣本分布更為密集，較小的半徑系數(shù)已足以覆蓋類別中多數(shù)樣本。半徑系數(shù)越大，整體類別中心點(diǎn)產(chǎn)生的偏移越大，分類結(jié)果就越差，而Yeast 數(shù)據(jù)集上半徑系數(shù)為0.5 時(shí)分類性能相對(duì)最優(yōu)，這與數(shù)據(jù)集本身樣本的分布有關(guān)，當(dāng)半徑系數(shù)為0.5 時(shí)篩選的樣本集合的類中心與預(yù)期樣本的類中心距離最近，此時(shí)半徑系數(shù)過小或過大都會(huì)影響最終的分類性能。在與對(duì)比算法比較中可以發(fā)現(xiàn)，當(dāng)特征數(shù)量較少時(shí)，PMU 算法性能最優(yōu)，而在文本類數(shù)據(jù)集中表現(xiàn)優(yōu)異的MLFS 和MLACO 算法性能反而較差，這說明不同的特征算法應(yīng)該選擇其適用的學(xué)習(xí)任務(wù)，對(duì)于所提算法應(yīng)更適用于文本類數(shù)據(jù)集，而對(duì)于非文本類數(shù)據(jù)集，則需要預(yù)先分析其數(shù)據(jù)，獲取標(biāo)記劃分下樣本的分布情況，然后根據(jù)確定的半徑系數(shù)進(jìn)行特征選擇。

圖9 非文本數(shù)據(jù)集的AP 指標(biāo)比較Fig.9 Comparison of AP index in non text datasets

此外，對(duì)于非文本類數(shù)據(jù)集，可以使用基于距離排序的方式去除極值樣本，以此避免未知樣本分布情況下的半徑系數(shù)的確定問題。距離排序是指對(duì)某一類樣本中每一個(gè)樣本到該類樣本中心點(diǎn)的距離進(jìn)行排序，然后去除恒定數(shù)量的樣本。相對(duì)于半徑系數(shù)的方式，距離排序的計(jì)算復(fù)雜度較高。假設(shè)現(xiàn)在存在某一類樣本，該類樣本數(shù)量是n個(gè)，經(jīng)過計(jì)算存在一個(gè)極值點(diǎn)樣本距離該類樣本中心點(diǎn)最遠(yuǎn)，那么以該極值點(diǎn)到類樣本中心點(diǎn)的距離乘以某一比例δ得到距離r，并以類樣本中心點(diǎn)為圓心，以r為半徑去構(gòu)造圓，顯然在圓外的是需要去除的樣本，這里的計(jì)算復(fù)雜度主要在于找到最大距離的樣本以及遍歷該類樣本集合中的每個(gè)樣本，判斷每個(gè)樣本的距離與r的關(guān)系，前者最壞情況下的時(shí)間復(fù)雜度為O(n)，后者的時(shí)間復(fù)雜度也為O(n)，則總的時(shí)間復(fù)雜度為2O(n)。對(duì)于距離排序的方式，假設(shè)條件不變，則需要對(duì)樣本集合中所有樣本進(jìn)行距離排序，再根據(jù)給定的去除樣本的數(shù)量去除距離最大的一些樣本，則最壞情況下的時(shí)間復(fù)雜度為O(n2)，顯然半徑系數(shù)的方式在計(jì)算復(fù)雜度上要優(yōu)于距離排序的方式，所以在比較好確定半徑系數(shù)的稀疏類文本數(shù)據(jù)集中采用半徑系數(shù)的方式去去除極值樣本來減少計(jì)算消耗，而在不好確定半徑系數(shù)的非文本類數(shù)據(jù)集中采用距離排序的方式。為了驗(yàn)證距離排序的效果，選擇了兩個(gè)較小的非文本類數(shù)據(jù)集Birds、Emotion 數(shù)據(jù)集來進(jìn)行實(shí)驗(yàn)。其中Birds 數(shù)據(jù)集是記錄鳥的叫聲的數(shù)據(jù)集，有645 個(gè)樣本、260 個(gè)特征、20 個(gè)標(biāo)記；Emotion 數(shù)據(jù)集是音樂情感類數(shù)據(jù)集，有593 個(gè)樣本、72 個(gè)特征、6 個(gè)標(biāo)記。實(shí)驗(yàn)中設(shè)去除樣本的比例占該類樣本集合的10%，實(shí)驗(yàn)結(jié)果如圖10 所示。

圖10 基于距離排序的模型與對(duì)比算法的AP 指標(biāo)比較Fig.10 AP index comparison between model based on distance ranking and comparison algorithms

從圖10 可以看出，本文算法在特征比例較少時(shí)并沒有顯著優(yōu)勢(shì)，但是隨著特征比例逐漸提升，分類性能逐漸提高。在Birds 數(shù)據(jù)集中當(dāng)特征比例超過0.45 時(shí)即超過原始特征下的分類性能，且在特征比例為0.6 時(shí)達(dá)到最優(yōu)，同時(shí)領(lǐng)先其余算法；在Emotion數(shù)據(jù)集中當(dāng)特征比例超過0.35 時(shí)即超過原始特征下的分類性能，且在特征比例為0.9 時(shí)達(dá)到最優(yōu)，同時(shí)領(lǐng)先其余算法。這表明所提算法在使用距離排序去除極值樣本上具有一定效果，能夠一定程度應(yīng)用在非文本數(shù)據(jù)集上。

綜上實(shí)驗(yàn)可以得出，本文算法主要適用在樣本分布較為稀疏的文本類數(shù)據(jù)集上，在此類數(shù)據(jù)集上，每一維特征的重要度都較小，但是卻可能與標(biāo)記集合中某一個(gè)標(biāo)記有關(guān)聯(lián)信息，所以無法輕易去除特征。而本文算法能夠有效計(jì)算每一維特征下樣本被標(biāo)記劃分后的兩類樣本的區(qū)分程度，根據(jù)區(qū)分程度可以過濾出對(duì)整體分類貢獻(xiàn)能力弱的特征，但本文算法的局限性在于無法去除特征子集中的冗余特征，當(dāng)數(shù)據(jù)集中存在大量冗余特征時(shí)，本文算法將無法有效地應(yīng)對(duì)這種情況。

4 結(jié)束語

本文通過改進(jìn)單標(biāo)記下的FS 計(jì)算方式，去除一類樣本中的極端值，使得在統(tǒng)計(jì)意義上的樣本中心更符合實(shí)際生活中的樣本集合，即通過原始數(shù)據(jù)的中心偏移完成樣本的過濾，并結(jié)合標(biāo)記的權(quán)值系數(shù)，將其應(yīng)用于多標(biāo)記任務(wù)。實(shí)驗(yàn)結(jié)果證明了所提算法具有一定的有效性和魯棒性。但本文在實(shí)驗(yàn)過程中還存在算法難以適用較密集數(shù)據(jù)集，以及對(duì)于多標(biāo)記權(quán)值系數(shù)的確定較為簡單等問題，這將是下一步需要完善的工作。