程玉勝，陳 飛，王一賓,2

(1.安慶師范大學(xué) 計算機(jī)與信息學(xué)院，安徽 安慶 246011； 2.安徽省智能感知與計算重點實驗室, 安徽 安慶 246011; 3. 數(shù)據(jù)科學(xué)與智能應(yīng)用福建省高校重點實驗室，福建 漳州 363000)(*通信作者電子郵箱chengyshaq@163.com)

0 引言

多標(biāo)記學(xué)習(xí)作為機(jī)器學(xué)習(xí)研究熱點，對現(xiàn)實世界中多義性對象的研究具有重要意義[1]，并且多標(biāo)記學(xué)習(xí)對象在日常生活中廣泛存在。在多標(biāo)記學(xué)習(xí)框架之下，數(shù)據(jù)往往面臨多標(biāo)記性和高維性等多種問題，使得手工標(biāo)記一般費時費力。同時隨著數(shù)據(jù)維數(shù)的不斷增加，分類器的分類精度也在不斷下降，因此探究高效的分類算法就顯得尤為重要。近年來，相關(guān)學(xué)者在此問題上的研究已經(jīng)取得了卓越的成績,提出了多種算法[2-5]。在現(xiàn)有的多標(biāo)記分類算法中，與實例相關(guān)的標(biāo)記重要程度被視作相同，然而在現(xiàn)實世界中，不同的標(biāo)記對于同一個實例的描述程度并不都是相同的。例如在一幅自然風(fēng)景圖中，如果出現(xiàn)大量的“藍(lán)天”，那么出現(xiàn)大量“白云”的概率也就高，其他標(biāo)記的可能性也就比較低，這種現(xiàn)象被稱為標(biāo)記的不平衡性。針對這種標(biāo)記的不平衡性，Geng等[6]提出了一種標(biāo)記分布學(xué)習(xí)(Label Distribution Learning, LDL)范式，將傳統(tǒng)的邏輯標(biāo)記用概率分布的形式來進(jìn)行描述，更加準(zhǔn)確地反映了實例的相關(guān)內(nèi)容。目前也有很多學(xué)者在標(biāo)記分布學(xué)習(xí)范式下對人年齡[7-8]、人臉面部識別[9]、文本情感分類[10]等領(lǐng)域進(jìn)行研究。

然而，無論是傳統(tǒng)的多標(biāo)記學(xué)習(xí)還是標(biāo)記分布學(xué)習(xí)，其特征選擇方法都假定從一開始就可以獲得所有實例的特征數(shù)據(jù)。但是在許多情況下，往往無法一次性獲取實例的所有特征數(shù)據(jù)，更多呈現(xiàn)動態(tài)生成并記錄相應(yīng)特征數(shù)據(jù)，這種情況獲取的特征稱為流特征，相應(yīng)的特征選擇算法稱為流特征選擇算法[11]。例如，對一篇小說進(jìn)行分類并標(biāo)上標(biāo)記，需要提取小說里面所有的高頻詞特征。如果小說的篇幅比較長則提取所有特征就需要耗費大量的時間，等所有的特征全部提取完之后再進(jìn)行分類訓(xùn)練是不可能的，更可取的方法是一次一個地生成候選特征，從生成的候選特征中選擇特征集合較小并且分類效果也好的特征集合作為最后的特征，這種做法不僅會節(jié)省大量的資源，同時分類精度也得到了保證?；诖?，Wu等[11]提出了在線流特征選擇(Online Streaming Feature Selection, OSFS), 通過對特征的相關(guān)性和冗余性進(jìn)行分析，得到滿足條件的特征集合，并在文獻(xiàn)[12]中設(shè)計出了一系列的算法，取得了十分明顯的效果。但是，文獻(xiàn)[12]中所提到的算法主要適用于離散的數(shù)據(jù)，且為單個邏輯標(biāo)記的數(shù)據(jù)集，對于多個邏輯標(biāo)記及其標(biāo)記分布并不適用。

另外，上述算法無論是邏輯標(biāo)記還是標(biāo)記分布，在對特征進(jìn)行選擇時考慮更多的是特征與標(biāo)記之間的相關(guān)性，如：張振海等[13]利用信息熵進(jìn)行多標(biāo)記的特征選擇；Lee等[4]提出一種使用多變量互信息對特征進(jìn)行選擇，但對特征之間的冗余性考慮不充分，屬性約簡不夠充分。OSFS雖然考慮了特征間的冗余性，但計算過程較為復(fù)雜，算法效率較低，而粗糙集最大的貢獻(xiàn)就是進(jìn)行屬性約簡，去除冗余屬性。

粗糙集理論是Pawlak[14]提出的一種處理不精確、不確定的數(shù)學(xué)工具，自提出以來在人工智能、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域得到了成功應(yīng)用。相較于其他的特征選擇算法，粗糙集方法不需要先驗知識，僅僅利用數(shù)據(jù)本身所提供的信息發(fā)現(xiàn)問題的規(guī)律[15]，計算過程簡單高效。粗糙集理論通過構(gòu)建上下近似來對知識進(jìn)行描述，通過下近似與全體論域之間的比值來刻畫屬性的依賴度從而判斷屬性的冗余性。一般來說，下近似越大，屬性間的依賴度越大，冗余性也就越大。目前利用粗糙集進(jìn)行屬性約簡和特征選擇是多標(biāo)記學(xué)習(xí)的一個熱點，Yu等[16-17]將粗糙集的擴(kuò)展鄰域粗糙集應(yīng)用在多標(biāo)記分類問題上，取得了顯著的成績；段潔等[18]利用鄰域粗糙集實現(xiàn)了多標(biāo)記分類任務(wù)的特征選擇算法。但上述算法都應(yīng)用在邏輯標(biāo)記且特征數(shù)據(jù)是靜態(tài)的環(huán)境下，對現(xiàn)實世界中的數(shù)據(jù)流的情況并不適用。

目前，針對流特征數(shù)據(jù)的研究更加具有現(xiàn)實意義，同時，標(biāo)記分布比傳統(tǒng)的邏輯標(biāo)記更能反映樣本標(biāo)記的真實情況。由此，本文提出了基于粗糙集的數(shù)據(jù)流多標(biāo)記分布特征選擇(multi-label Distribution learning Feature Selection with Streaming Data Using Rough Set, FSSRS)算法。首先將在線特征選擇算法應(yīng)用在多標(biāo)記學(xué)習(xí)框架之下，其次將傳統(tǒng)的邏輯標(biāo)記轉(zhuǎn)換成標(biāo)記分布形式進(jìn)行學(xué)習(xí)，同時利用粗糙集中的依賴度來度量特征之間的相關(guān)性，從而去除冗余屬性，保證最終的特征子集的分類效果。實驗結(jié)果表明該方法是有效的。

1 相關(guān)工作

1.1 傳統(tǒng)多標(biāo)記學(xué)習(xí)

多標(biāo)記學(xué)習(xí)是針對現(xiàn)實生活中普遍存在的多義性對象而提出的一種學(xué)習(xí)框架，在這個框架之下，樣本由多個特征和多個標(biāo)記構(gòu)成，學(xué)習(xí)的目的是將未知的實例對應(yīng)上更多正確的標(biāo)記[19]。假設(shè)T是含有n個特征的特征集合T={t1,t2,…,tn}，L是由m個標(biāo)記組成的標(biāo)記集合L={l1,l2,…,lm}，其中1表示有該標(biāo)記，而-1表示沒有該標(biāo)記，則含有i個樣本的多標(biāo)記數(shù)據(jù)集可以表示為：

D={(Tj,Lj)|1≤j≤i,Tj∈T,Lj∈L}

(1)

1.2 標(biāo)記分布學(xué)習(xí)

1.3 數(shù)據(jù)流特征選擇

傳統(tǒng)的多標(biāo)記學(xué)習(xí)中，所有實例的特征數(shù)據(jù)都是完整的，并可以一次性獲得，從而進(jìn)行相應(yīng)的分類學(xué)習(xí)。但是，在一些情況下，同一實例的不同特征數(shù)據(jù)往往是實時生成并記錄的，并且這些特征的生成是無序的，有些特征數(shù)據(jù)甚至是無窮的。如果用傳統(tǒng)的多標(biāo)記特征選擇算法無疑會浪費大量的時間和精力，對于那些特征數(shù)據(jù)是無窮的實例，傳統(tǒng)方法更是無法進(jìn)行特征選擇。解決這個問題最好的方法就是從實時產(chǎn)生的特征數(shù)據(jù)中選擇符合一定條件的特征構(gòu)成候選特征子集，利用這個特征子集進(jìn)行相應(yīng)的訓(xùn)練和測試，這種方法被稱為在線流特征選擇(OSFS)[11]。在OSFS框架之下，對特征子集的選擇標(biāo)準(zhǔn)總共分成兩部分：1)特征與標(biāo)記之間相關(guān)性；2)特征與特征之間的冗余性。根據(jù)上述兩種情況，候選的特征集合又可以分為以下4個部分：1)不相關(guān)的特征；2)強相關(guān)的特征；3)弱相關(guān)非冗余特征；4)弱相關(guān)冗余特征。

通過計算特征與標(biāo)記之間的相關(guān)性舍棄不相關(guān)特征并保留強相關(guān)特征，對于弱相關(guān)的特征再進(jìn)行特征之間冗余性判斷，舍棄冗余屬性。由此，最終的特征子集應(yīng)包括強相關(guān)特征和弱相關(guān)但非冗余特征。

1.4 粗糙集理論

粗糙集理論是一種處理不精確、不確定的數(shù)學(xué)工具，自提出便廣泛應(yīng)用到人工智能、機(jī)器學(xué)習(xí)等領(lǐng)域。在粗糙集理論中，對于一個信息系統(tǒng)IS=〈U,Q,V,f〉，其中:U表示全體論域，即樣本集合;Q表示屬性集合(包括條件屬性C和決策屬性D);V表示屬性的值域;f表示一種映射。在分類過程中，差別不大的樣本被劃成一類，它們的關(guān)系被稱為相容關(guān)系或者等價關(guān)系。為方便問題描述，本文僅僅考慮了等價關(guān)系。對于任何一個屬性集合C，其等價關(guān)系可以用下面不可分辨關(guān)系IND來表示，定義如下：

IND(C)={(x,y)∈U×U:f(x,a)=f(y,a),a∈C}

(2)

不可分辨關(guān)系也就是U上的等價關(guān)系，可以用U/C來表示。粗糙集理論中，用上下近似來對知識進(jìn)行描述，假設(shè)B?C，X?U，則B的上近似與B的下近似定義如下：

?}

(3)

(4)

通過上下近似可以定義正域(POS)、負(fù)域(NEG)和邊界域(BNG)：

(5)

(6)

(7)

發(fā)現(xiàn)屬性之間的依賴關(guān)系也是數(shù)據(jù)分析中十分重要的一個問題。在粗糙集理論中，可以利用依賴度(Dep)來表示兩個屬性之間的依賴程度。假設(shè)B?C，則決策屬性D對條件屬性B的依賴程度用式(8)進(jìn)行計算:

(8)

表1 粗糙集示例

2 數(shù)據(jù)流多標(biāo)記分布特征選擇算法

2.1 特征與標(biāo)記的相關(guān)性

在多標(biāo)記學(xué)習(xí)框架之下，標(biāo)記的準(zhǔn)確性常常與特征的個數(shù)有著密切的聯(lián)系。在一定的范圍內(nèi)特征越多標(biāo)記準(zhǔn)確性也就越高，但隨著特征數(shù)目的不斷增加，次要特征和冗余特征也隨之增多，這就會導(dǎo)致分類器的精度下降，所以選擇與標(biāo)記相關(guān)的特征就顯得尤為重要。在目前的多標(biāo)記特征選擇中，大多數(shù)學(xué)者利用信息熵來度量特征與標(biāo)記之間的相關(guān)性，選擇信息熵較大的特征作為重要特征[20-22],但是，傳統(tǒng)的信息熵只能處理離散型數(shù)據(jù)，對于標(biāo)記分布中標(biāo)記空間的連續(xù)型概率分布數(shù)據(jù)并不適用。

在統(tǒng)計學(xué)中，皮爾遜相關(guān)系數(shù)(Pearson)常常用于度量兩個連續(xù)變量X和Y之間的相關(guān)性，其值為-1～1。其中正值表示正相關(guān)，反之則為負(fù)相關(guān)；皮爾遜相關(guān)系數(shù)絕對值越大則表示兩個變量的相關(guān)性越大。并且規(guī)定，若相關(guān)系數(shù)大于0.6則為強相關(guān)，相關(guān)系數(shù)小于0.2則為弱相關(guān)或不相關(guān)[23]。皮爾遜相關(guān)系數(shù)可以通過式(9)進(jìn)行計算:

(9)

其中:E表示數(shù)學(xué)期望，Cov表示協(xié)方差。

2.2 特征之間的冗余性

在傳統(tǒng)的OSFS框架[11]之下，往往是利用特征與標(biāo)記之間的條件概率對特征的冗余性進(jìn)行判斷，對于特征X、S和標(biāo)記T，如果P(T|X,S)=P(T|S)，則表示特征X對標(biāo)記T是冗余的。這種判斷方法需要知道特征空間、標(biāo)記空間和每個特征的先驗知識且計算復(fù)雜，而粗糙集方法可以很好地解決這個問題。在粗糙集理論中，條件屬性與決策屬性之間的依賴度可以很好地刻畫兩者之間的依賴程度。將依賴度引入到特征選擇中對兩個特征之間進(jìn)行冗余性判斷。計算流入特征與已確定特征之間的依賴度，若兩者依賴度越大，獨立性越小，冗余性也就越大。

2.3 基于粗糙集的數(shù)據(jù)流多標(biāo)記分布特征選擇

FSSRS算法對于實時產(chǎn)生的特征數(shù)據(jù)進(jìn)行十折離散化[24],利用皮爾遜相關(guān)系數(shù)對特征與標(biāo)記之間的相關(guān)性進(jìn)行判斷，對于強相關(guān)的特征直接保留進(jìn)入最終的特征子集中，不相關(guān)的特征則直接舍棄，弱相關(guān)的特征暫時保留在弱相關(guān)子集中，在下一個弱相關(guān)特征流入時進(jìn)行冗余性判斷。

對于流入的弱相關(guān)特征，與弱相關(guān)子集中的特征利用式(8)計算冗余性，將冗余的屬性直接舍棄，在保證分類器精度的同時也確保了最小的特征子集。

由于數(shù)據(jù)是實時產(chǎn)生并記錄的，需要提前設(shè)置好相關(guān)參數(shù)：α為強相關(guān)系數(shù),β為不相關(guān)系數(shù),γ為冗余性系數(shù)。

在線特征相關(guān)性 在t時刻獲取特征fti，利用皮爾遜相關(guān)系數(shù)進(jìn)行計算特征與標(biāo)記的相關(guān)性計算: 如果Pearsonti≥α則為強相關(guān)性特征，直接存到最終的特征子集中; 如果Pearsonti≤β則為不相關(guān)特征直接舍棄，如果α

在線特征冗余性 對于暫時保留的特征fti，利用式(8)計算與ti-1時刻確定的最終特征子集進(jìn)行依賴度計算，如果Depti≤γ則表示沒有冗余性，該特征存到最終特征子集中，否則舍棄該特征。

通過相關(guān)性與冗余性的判斷之后輸出最終的特征子集，并利用此特征子集進(jìn)行訓(xùn)練與測試。該算法的偽代碼如下所示：

算法 基于粗糙集的數(shù)據(jù)流多標(biāo)記分布特征選擇。

輸入fti為ti時刻的特征數(shù)據(jù)，α為強相關(guān)系數(shù)，β為不相關(guān)系數(shù)，γ為冗余性系數(shù)。

輸出 選擇后的特征子集FS。

1)

repeat

2)

在ti時刻得到一個新的特征數(shù)據(jù)fti；

3)

利用皮爾遜相關(guān)系數(shù)計算t時刻的相關(guān)性Pearsonti；

4)

IFPearsonti≥α

5)

將fti加入到FS中；

6)

跳轉(zhuǎn)到步驟17)；

7)

ELSE IFPearsonti≤β

8)

舍棄fti；

9)

ELSE

10)

利用式(8)計算特征間的依賴度Depti；

11)

IFDepti≤γ

12)

將fti加入到FS中；

13)

Else

14) 舍棄fti；

15) End IF并跳轉(zhuǎn)到步驟17)；

16)

End IF并跳轉(zhuǎn)到步驟17)；

17)

直到?jīng)]有新的特征流入；

18) 輸出特征子集FS

算法流程如圖1所示。

圖1 FSSRS算法流程

3 實驗結(jié)果及分析

3.1 評價指標(biāo)

1)Chebyshev距離(↓)：

2)Clark距離(↓)：

3)Canberra距離(↓)：

4)KL-div散度(↓)：

5)Cosine相似度(↑)：

6)Intersection相似度(↑):

3.2 實驗數(shù)據(jù)集

本文所有實驗均運行在3.4 GHz處理器，8.00 GB內(nèi)存及Matlab R2016a的實驗平臺上。實驗數(shù)據(jù)來源于標(biāo)記分布常用數(shù)據(jù)集(http://ldl.herokuapp.com/download)，選取其中12個數(shù)據(jù)集進(jìn)行對比實驗，其基本信息如表2所示。

3.3 實驗結(jié)果與分析

為驗證算法的有效性，與耿新提出的AA-kNN (Algorithm Adaptationk-Nearest Neighbors)、PT-SVM (Problem Transformation SVM)和SA-IIS(Specialized Algorithm Improved Iterative Scaling)進(jìn)行對比，對比實驗采用10折交叉驗證。表2中也列出了各數(shù)據(jù)集特征選擇的數(shù)量，表3～8則給出了11個數(shù)據(jù)集在三種不同算法上的實驗結(jié)果(平均值±標(biāo)準(zhǔn)差), 實驗中，α=0.8,β=0.3,γ=0.5。表9和表10是在Yeast-dtt數(shù)據(jù)集上，分類器選擇kNN，當(dāng)γ=0.5時，α、β不同取值時的結(jié)果(說明：表中黑色加粗的數(shù)字表示在該指標(biāo)上特征選擇后的數(shù)據(jù)優(yōu)于原始數(shù)據(jù)；數(shù)據(jù)括號中的數(shù)字為該值在評價指標(biāo)中的排名情況)。

表3 Chebyshev實驗結(jié)果

表4 Clark實驗結(jié)果

表5 Canberra實驗結(jié)果

表6 Kullback-Leibler實驗結(jié)果

表7 Cosine實驗結(jié)果

表8 Intersection實驗結(jié)果

表9 Yeast-dtt數(shù)據(jù)集不同參數(shù)實驗結(jié)果 (β=0.3，γ=0.5)

表10 Yeast-dtt數(shù)據(jù)集不同參數(shù)實驗結(jié)果 (β=0.2，γ=0.5)

從實驗結(jié)果來看，在11個數(shù)據(jù)集6個評價指標(biāo)共66個實驗結(jié)果上，AA-kNN有95.5%的結(jié)果優(yōu)于原始數(shù)據(jù)，PT-SVM有56.1%的結(jié)果優(yōu)于原始數(shù)據(jù)，SA-IIS有83.3%的結(jié)果優(yōu)于原始數(shù)據(jù)。

從表9和表10可知: 當(dāng)β=0.3時，α=0.7取得更多最優(yōu)結(jié)果; 當(dāng)β=0.2時，α=0.8取得更多最優(yōu)結(jié)果; 所有特征選擇的結(jié)果都優(yōu)于原始數(shù)據(jù)。

圖2～圖3是Yeast-cold數(shù)據(jù)集在不同參數(shù)下的實驗結(jié)果對比。由圖2可以看出，特征選擇數(shù)目與弱相關(guān)系數(shù)有著密切的關(guān)系；由圖3可以看出, 經(jīng)過特征選擇后的分類效果要優(yōu)于原始特征，結(jié)果也較為穩(wěn)定。

4 結(jié)語

針對傳統(tǒng)多標(biāo)記學(xué)習(xí)框架的邏輯標(biāo)記和靜態(tài)特征的情況，提出了基于粗糙集的數(shù)據(jù)流多標(biāo)記分布特征選擇算法，為了更加準(zhǔn)確地對樣本進(jìn)行描述，將傳統(tǒng)的邏輯標(biāo)記轉(zhuǎn)換成概率的形式。同時對實時產(chǎn)生的特征數(shù)據(jù)利用皮爾遜相關(guān)系數(shù)與粗糙集中的依賴度進(jìn)行處理，保留符合條件的特征構(gòu)成特征子集進(jìn)行訓(xùn)練，在節(jié)約資源的情況下又使得分類精度得到了保證，多組實驗證明了該算法的有效性。

圖2 不同參數(shù)特征選擇個數(shù)(Yeast-cold)

但是本文仍存在一些問題，如FSSRS算法在進(jìn)行冗余性判斷時，對于已經(jīng)是強相關(guān)性的特征沒有進(jìn)行冗余性檢查，以后將對此進(jìn)行改進(jìn)；同時本文的參數(shù)是人為設(shè)定，今后將繼續(xù)完善參數(shù)選擇，使得算法更加高效。

圖3 Yeast-cold數(shù)據(jù)集不同參數(shù)實驗結(jié)果