基于粗糙集的數據流多標記分布特征選擇

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

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

0 引言

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

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

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

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

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

1 相關工作

1.1 傳統多標記學習

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

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

(1)

1.2 標記分布學習

1.3 數據流特征選擇

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

通過計算特征與標記之間的相關性舍棄不相關特征并保留強相關特征，對于弱相關的特征再進行特征之間冗余性判斷，舍棄冗余屬性。由此，最終的特征子集應包括強相關特征和弱相關但非冗余特征。

1.4 粗糙集理論

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

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

(2)

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

?}

(3)

(4)

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

(5)

(6)

(7)

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

(8)

表1 粗糙集示例

2 數據流多標記分布特征選擇算法

2.1 特征與標記的相關性

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

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

(9)

其中:E表示數學期望，Cov表示協方差。

2.2 特征之間的冗余性

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

2.3 基于粗糙集的數據流多標記分布特征選擇

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

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

由于數據是實時產生并記錄的，需要提前設置好相關參數：α為強相關系數,β為不相關系數,γ為冗余性系數。

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

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

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

算法 基于粗糙集的數據流多標記分布特征選擇。

輸入fti為ti時刻的特征數據，α為強相關系數，β為不相關系數，γ為冗余性系數。

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

1)

repeat

2)

在ti時刻得到一個新的特征數據fti；

3)

利用皮爾遜相關系數計算t時刻的相關性Pearsonti；

4)

IFPearsonti≥α

5)

將fti加入到FS中；

6)

跳轉到步驟17)；

7)

ELSE IFPearsonti≤β

8)

舍棄fti；

9)

ELSE

10)

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

11)

IFDepti≤γ

12)

將fti加入到FS中；

13)

Else

14) 舍棄fti；

15) End IF并跳轉到步驟17)；

16)

End IF并跳轉到步驟17)；

17)

直到沒有新的特征流入；

18) 輸出特征子集FS

算法流程如圖1所示。

圖1 FSSRS算法流程

3 實驗結果及分析

3.1 評價指標

1)Chebyshev距離(↓)：

2)Clark距離(↓)：

3)Canberra距離(↓)：

4)KL-div散度(↓)：

5)Cosine相似度(↑)：

6)Intersection相似度(↑):

3.2 實驗數據集

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

3.3 實驗結果與分析

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

表3 Chebyshev實驗結果

表4 Clark實驗結果

表5 Canberra實驗結果

表6 Kullback-Leibler實驗結果

表7 Cosine實驗結果

表8 Intersection實驗結果

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

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

從實驗結果來看，在11個數據集6個評價指標共66個實驗結果上，AA-kNN有95.5%的結果優于原始數據，PT-SVM有56.1%的結果優于原始數據，SA-IIS有83.3%的結果優于原始數據。

從表9和表10可知: 當β=0.3時，α=0.7取得更多最優結果; 當β=0.2時，α=0.8取得更多最優結果; 所有特征選擇的結果都優于原始數據。

圖2～圖3是Yeast-cold數據集在不同參數下的實驗結果對比。由圖2可以看出，特征選擇數目與弱相關系數有著密切的關系；由圖3可以看出, 經過特征選擇后的分類效果要優于原始特征，結果也較為穩定。

4 結語

針對傳統多標記學習框架的邏輯標記和靜態特征的情況，提出了基于粗糙集的數據流多標記分布特征選擇算法，為了更加準確地對樣本進行描述，將傳統的邏輯標記轉換成概率的形式。同時對實時產生的特征數據利用皮爾遜相關系數與粗糙集中的依賴度進行處理，保留符合條件的特征構成特征子集進行訓練，在節約資源的情況下又使得分類精度得到了保證，多組實驗證明了該算法的有效性。

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

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

圖3 Yeast-cold數據集不同參數實驗結果