模糊粗糙集的LIFT數據分析

梁紹宸,徐蘇平,竇慧莉,李洪梅,楊習貝,2

1(江蘇科技大學 計算機學院,江蘇 鎮江 212003)2(南京理工大學 經濟管理學院,南京 210094)

1 引 言

多標記學習[1]是針對現實世界中普遍存在的多義性對象而提出的一種學習框架,其主要目標是預測未知對象的標記集合.多義性對象是指擁有多個語義信息的對象,例如:一個文本對象可以同時包含“經濟”和“新聞”兩種語義信息[2];類似地,一個圖像可以同時被標記為“天空”與“大海”[3,4].在多標記學習框架下,每一種語義信息都被刻畫為一個標記,所有對象的語義信息就構成了輸出空間(標記空間),同時,所有對象的特征構成了輸入空間(示例空間).以輸入空間作為分類依據,對一個對象在各個標記上的預測,都可被視作是一個二類分類問題.鑒于此,相關學者[5]針對每個標記,直接通過示例空間,分別構建分類器模型,從而可以得到未標記對象的標記集合[6].

然而,由直觀經驗可知每一個標記都有一些固有特性,而這些特性在幫助判斷對象是否屬于該標記時往往能夠提供更有利的信息[7].因此,Zhang等人提出了基于標記類屬屬性的多標記學習算法LIFT,并且已有的實驗結果表明,LIFT算法確實是有效的[8,9].但利用LIFT構建出的類屬屬性空間中存在冗余信息[10],這不僅增加了分類過程所消耗的時間,而且有可能對分類產生一定負面的影響.所以,尋找一種有效的方法來對類屬屬性空間進行特征選擇是有著客觀依據的[11,12].

自1990年Dubois提出模糊粗糙集[13]以來,國內外眾多學者開始致力于模糊粗糙集的理論與應用方法的研究[14,15].其中,有些學者提出,利用粗糙集中的約簡概念而產生的模糊粗糙集特征選擇方法,不僅能夠有效地處理各種類型的數據[16,17],而且可以最大限度地保持原始數據的分布信息[18-20].也正因為此,基于模糊粗糙集的特征選擇才在生物信息學、管理科學與工程等領域中得到了廣泛應用[21,22].

考慮到模糊粗糙集在實際應用中的有效性,筆者將借助模糊粗糙集模型,對由LIFT產生的類屬屬性空間進行特征選擇.在此基礎上,為進一步提升分類性能,采用了穩健模糊粗糙分類器[23,24].

本文主要內容安排如下:第二節介紹模糊粗糙集的基本知識,第三節給出多標記學習的算法LIFT,并針對LIFT算法存在的問題,設計了新算法FRS-LIFT,第四節通過實驗數據驗證了FRS-LIFT的有效性,第五節總結全文.

2 基礎知識

給定決策系統,其中,論域U={x1,x2,…,xn}是全部對象的集合,A={a1,a2,…,am}用來描述對象的各個特征,D刻畫了對象的所有決策.

不失一般性,若將B?A(B≠?)誘導的論域上的一個模糊二元關系記作RB,則當它至少滿足自反性與對稱性時,?x,y∈U,RB(x,y)∈[0,1]可用來表示對象x與y關于特征集B的相似度.如無特別說明,本文所探討的模糊二元關系都可用來刻畫對象間的相似度.

2.1 模糊粗糙集模型

(1)

(2)

2.2 穩健模糊粗糙集模型

由于上式中的最大值和最小值的統計對數據噪聲敏感,因此Hu等人定義了三種穩健的統計量代替上述的最大值和最小值.

定義2.[23]對于隨機變量X={x1,x2,…,xn},假定X的元素按照升序排列,定義X的k-mean最小值和最大值分別為(x1+x2+…+xk)/k和(xn-k+1+xn-k+2+…+xn)/k,X的k-median最小值和最大值分別為{x1,x2,…xk}的中位數和{xn-k+1,xn-k+2,…,xn}的中位數,X的k-trimmed最小值和最大值分別為xk+1和xn-k.基于此,三種穩健模糊粗糙集的隸屬函數分別為:

(3)

(4)

(5)

(6)

(7)

(8)

2.3 模糊粗糙分類器

決策系統的目標是利用已知決策的對象,構建上述模糊粗糙集模型,對未知對象的決策類進行預測.模糊粗糙分類器分類的方法如下:

給定決策系統,若D誘導的論域上的劃分為U/IND(D)={d1,…,dp},則未知對象x的決策類為:

(9)

其中,*為classical,k-mean,k-median,或者k-trimmed.

2.4 基于模糊粗糙集的特征選擇

現實世界中的數據往往存在冗余信息,利用特征重要度這一概念可以找到并刪除這些冗余信息,例如將特征重要度小的特征視作冗余信息.此外,一個特征的特征重要度由衡量指標分別在有無該特征時取到的值之差度量.近似質量作為重要的衡量指標之一,它刻畫了模糊粗糙集在現有知識水平下的確定性程度,其定義如下:

定義3.給定決策系統,?B?A,若D誘導的論域上的劃分為{d1,d2,…,dp},則在特征集合B下,模糊粗糙集的近似質量為:

(10)

根據如上定義,采用近似質量衡量特征重要度.?ai∈A,其特征重要度可以用如下兩種方式表示:

(11)

(12)

其中*為classical,k-mean,k-median,或者k-trimmed.在此基礎上,使用正向啟發式算法等可以進行特征選擇.

3 多標記學習

在多標記學習中,特征集合A= {a1,a2,…,am},標記集合L={l1,l2,…,lq}.與此同時,使用T= {(xi,Yi)|i=1,2,…,n}表示多標記對象的訓練集,其中xi=[fi(a1),fi(a2),…,fi(am)]刻畫了對象xi的各個特征,Yi=[gi(l1),gi(l2),…,gi(lq)]描述了對象xi的標記情況.當xi具備lk標記時,gi(lk)=1,否則gi(lk)=-1.

3.1 LIFT算法

由于不同的標記有不同的特性,而這些特性更傾向于判斷對象是否具有某個標記,因此已有學者[8]提出了LIFT算法來尋找各標記的類屬屬性,以期提高多標記學習的性能.LIFT首先分別按照是否具有標記lk∈L,把多標記對象分為正類樣本Pk和負類樣本Nk,形如:

Pk={xi|(xi,Yi)∈T,gi(lk)=1};

(13)

Nk={xi|(xi,Yi)∈T,gi(lk)=-1}.

(14)

然后分別在Pk和Nk上進行k-means聚類以獲取正、負兩類樣本的內在結構.由于Pk和Nk的聚類信息可被視為同等重要[9],為此聚類中心的數目均設為mk,即有:

mk=「δ·min(|Pk|,|Nk|)?.

(15)

在此基礎上,lk標記對應的類屬屬性空間按照如下方式構造:

(16)

其中,d(·,·)表示兩向量間的距離,本文采用了歐氏距離.實際上,φk是從特征集合A構成的m維空間到新的2mk維類屬屬性空間LIFTk的映射.

最后LIFT在構建出來的q個類屬屬性空間中分別訓練分類模型{h1,h2,…,hq}.參照形式化定義,?lk∈L,可得到如下二類訓練集BTk:

BTk={(φk(xi),gi(lk))|i=1,2,…n}.

(17)

進而使用任何一種二類分類算法都可以得到hk模型,對于未知對象x,其標記的預測集合為Y={lk|hk(φk(x))>0,1≤k≤q}.

3.2 FRS-LIFT算法

當類屬屬性維度較高時,分類模型構建較慢.為降低類屬屬性維度,筆者在保留了上述LIFT類屬屬性構建的方法基礎之上,對所有二類訓練集BTk分別進行基于模糊粗糙集的特征選擇得到BTk′,再分別使用對應的模糊粗糙分類器預測未知對象是否具備標記lk,最終得到未知對象的標記集合.無論采用哪種模糊粗糙集模型,筆者將這一完整過程統稱為FRS-LIFT算法,其具體流程如下:

算法1.FRS-LIFT

輸入: 多標記對象訓練集T,控制聚類個數的參數δ,近似質量變化的閾值ε,未知對象x;

輸出: 預測出的未知對象的標記集合Y.

步驟1.對于每一個標記lk,重復步驟2到步驟11;

步驟2.根據式(13)和(14)得到正類樣本集Pk與負類樣本集Nk;

步驟3.在Pk和Nk上分別使用k-means聚類,根據式(15)得到聚類個數mk;

步驟4.根據式(16),對于T中每個對象xi,創建映射φk(xi),進而得到lk標記下的類屬屬性空間LIFTk;

步驟5.根據式(10)計算γ*(Ak,lk),其中Ak為構成LIFTk空間的類屬屬性集;

步驟6.Bk←?;

步驟13.若class*(x)=Pk,則Y←Y∪{lk};

步驟14.輸出Y.

算法中,所有*都代表classical,k-mean,k-median,或者k-trimmed,它們全部取相同的值.步驟2到步驟4是原LIFT算法中構建類屬屬性的過程,步驟5到步驟10利用模糊粗糙集對類屬屬性空間進行了特征選擇,步驟12根據式(9)預測了未知對象的各個標記,最終得到其標記集合.

4 多標記學習

本文選取了5組多標記數據集進行了實驗,這些數據集涵蓋了音樂、文本、生物等多個實際應用領域,它們的基本信息如表1所示.

表1 數據集信息Table 1 Data sets description

注:URL1:http://sci2s.ugr.es/keel/multilabel.phpURL2:http://mulan.sourceforge.net/datasets-mlc.html

4.1 實驗設置

實驗選用高斯核函數計算多標記對象間的相似度,高斯核參數以0.1為步長在[0,1]內調節,最終設定為0.7,根據文獻[25]控制聚類個數的參數δ設為0.2,特征選擇中控制近似質量變化的閾值取0.05.另外,由三個穩健模糊粗糙集模型的定義可知,在一定范圍內,它們的參數越大,噪聲樣本對分類結果的影響越小,實驗效果越好.同時,當k-median參數取奇數時,會與k-trimmed取某個參數時實驗效果相同;當k-median的參數為2時,又會與k-mean的參數取2時的實驗效果相同,因此為了不失一般性并體現出三個穩健模糊粗糙集模型各自的特點,本實驗將三個穩健模糊粗糙集模型k-mean,k-median,k-trimmed的參數分別設置為3、4、2.

此外,所有實驗都使用MATLAB R2014a開發環境.由于Enron數據集較大,因此將此數據集運行在兩個2.13GHz的Intel處理器和16GB的內存空間中,其余實驗都運行在1.90GHz的AMD處理器和8GB的內存空間中.

在此基礎上,做了兩組實驗,第一組實驗對比特征選擇前后的類屬屬性空間的平均維度,第二組實驗對比四個模糊粗糙分類器在特征選擇前后的類屬屬性空間中的分類性能.

4.2 維度對比

分別采用四個模糊粗糙集模型對各標記構造出的類屬屬性空間LIFTk(1≤k≤q)特征選擇,特征選擇前后q個類屬屬性空間的平均維度,如表2所示.

4.3 分類效果對比

從表2中可以看出,在這5組數據集上,k-trimmed穩健模糊粗糙集模型降維效果始終最佳.同時可以看出有時類屬屬性空間維度較高,以Emotion數據集為例,它的特征選擇前的類屬屬性空間的平均維度比原始數據的特征維度要大.

為了考察多標記學習系統的分類性能,在每個數據集中,將數據集分成十份,輪流將其中9份樣本構成訓練集,1份構成測試集,分類過程重復10次并記錄10次實驗的均值與方差.顯然,精度、查準率等單標記指標不適用于度量多標記學習性能[6],因此,本文采用了5種多標記學習評價指標[2,26]來評價學習系統的性能,它們分別是Hamming Loss、Ranking Loss、One Error、Coverage、Average Precision.

值得注意的是,使用的四種模糊粗糙分類器,與特征選擇時所用的模糊粗糙集模型對應.它們對各數據集的分類效果分別如表3至表6所示.另外,表格中,↓表示對應指標的值越小,該指標下的性能越好,↑表示對應指標的值越大,該指標下的性能越好,性能好的數據以加粗體標出.

表2 特征選擇前后類屬屬性空間的平均維度對比Table 2 Comparison of average dimensionalities of label-specific feature spaces before and after feature selection

表3 傳統模糊粗糙集分類性能Table 3 Predictive performance of classical fuzzy rough set

表4 k-mean模糊粗糙集分類性能Table 4 Predictive performance of k-mean fuzzy rough set

表5 k-median模糊粗糙集分類性能Table 5 Predictive performance of k-median fuzzy rough set

表6 k-trimmed模糊粗糙集分類性能Table 6 Predictive performance of k-trimmed fuzzy rough set

觀察表3至表6所示結果,不難發現無論使用哪種模糊粗糙分類器,在特征選擇后的類屬屬性空間中,分類性能都有一定的提升.即使在少數情況下,在個別評價指標上特征選擇后的類屬屬性空間中分類性能不如原始的類屬屬性空間,但是差別不大.以Bird數據集為例,經過特征選擇后,k-trimmed分類器結果顯示Ranking Loss值僅下降0.9%左右.綜上所述,本文提出的FRS-LIFT算法是有效的.

5 結束語

LIFT試圖探尋各個標記所具有的特性,并在新的構造出的類屬屬性空間中進行多標記學習,這突破了一直以來在原始示例空間中采用各種算法進行多標記學習的做法.從相關學者已有的大量實驗數據可以看出,LIFT確實改進了多標記學習系統的性能.然而遺憾的是,LIFT忽略了類屬屬性空間中存在的冗余信息,沒有考慮到這些冗余信息對多標記學習系統的學習性能會造成一定負面影響.因此筆者在提出的新算法中,對LIFT構造出的類屬屬性進行了特征選擇.實驗結果表明,除去類屬屬性空間的冗余信息能夠使多標記學習系統性能得到進一步提升.

在本文工作的基礎上,筆者下一步的工作是:

1)改進對類屬屬性特征選擇的算法,減少特征選擇所需的時間.

2)LIFT和FRS-LIFT都沒有考慮各個標記之間的關系,能否將標記間的相關性考慮在內也是下一步的研究重點.

：

[1] Tsoumakas G,Katakis I.Multi-label classification:an overview [J].International Journal of Data Warehousing and Mining,2007,3(3):1-13.

[2] Schapire R E,Singer Y.BoosTexter:a boosting-based system for text categorization [J].Machine Learning,2000,39(2):135-168.

[3] Boutell M R,Luo Jie-bo,Shen Xi-peng,et al.Learning multi-label scene classification [J].Pattern Recognition,2004,37(9):1757-1771.

[4] Liang Xin-yan,Qian Yu-hua,Guo Qian,et al.Local rough sets for mutil-label learning [J].Journal of Nanjing University,2016,52(2):270-279.

[5] Yu Ying,Pedrycz W,Miao Duo-qian.Neighborhood rough sets based multi-label classification for automatic image annotation [J].International Journal of Approximate Reasoning,2013,54(9):1373-1387.

[6] Zhang Min-ling,Zhou Zhi-hua.A review on multi-label learning algorithms [J].IEEE Transactions on Knowledge and Data Engineering,2014,26(8):1819-1837.

[7] Wang Yu,Yang Zhi-rong,Yang Xi-bei.Local attribute reduction approach based on decision-theoretic rough set [J].Journal of Nanjing University of Sciences & Technology,2016,40(4):444-449.

[8] Wu Lei,Zhang Min-ling.Research of label-specific features on multi-label learning algorithm [J].Journal of Software,2014,25(9):1992-2001.

[9] Zhang Min-ling,Wu Lei.Lift:multi-label learning with label-specific features [J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2015,37(1):107-120.

[10] Xu Su-ping,Yang Xi-bei,Qi Yun-song.Multi-label learning with label-specific feature reduction [J].Journal of Computer Applications,2015,35(11):3218-3221.

[11] Li Hua,Li De-yu,Wang Su-ge,et al.Multi-label learning with label-specific features based on rough sets [J].Journal of Chinese Computer Systems,2015,36(12):2730-2734.

[12] Duan Jie,Hu Qing-hua,Zhang Ling-jun,et al.Feature selection for multi-label classification based on neighborhood rough sets [J].Journal of Computer Research & Development,2015,52(1):56-65.

[13] Dubois D,Prade H.Rough fuzzy sets and fuzzy rough sets [J].International Journal of General System,1990,17(2-3):191-209.

[14] Wu Wei-zhi,Mi Ju-sheng,Zhang Wen-xiu,et al.Generalized fuzzy rough sets [J].Information Sciences,2003,151(3):263-282.

[15] Hu Bao-qing,Xian Yan-xia.Level characteristics of rough fuzzy sets and fuzzy rough sets [J].Fuzzy Systems and Mathematics,2006,20(6):108-114.

[16] Zeng An-ping,Li Tian-rui,Liu Dun,et al.A fuzzy rough set approach for incremental feature selection on hybrid information systems [J].Fuzzy Sets & Systems,2015,258(1):39-60.

[17] Zhang Xiao,Mei Chang-lin,Chen De-gang,et al.Feature selection in mixed data:A method using a novel fuzzy rough set-based information entropy [J].Pattern Recognition,2016,56(1):1-15.

[18] Bhatt R B,Gopal M.On fuzzy-rough sets approach to feature selection [J].Pattern Recognition Letters,2005,26(7):965-975.

[19] Hu Qing-hua,An Shuang,Yu Da-ren.Soft fuzzy rough sets for robust feature evaluation and selection [J].Information Sciences,2010,180(22):4384-4400.

[20] Chen De-gang,Zhao Su-yun.Local reduction of decision system with fuzzy rough sets [J].Fuzzy Sets & Systems,2010,161(13):1871-1883.

[21] Zhou Jun-yi.Research on customer churn prediction in telecommunication based on attribute selection of rough set [D].Zhenjiang:Jiangsu University of Science and Technology,2014:1-86.

[22] Xu Fei-fei,Wei Lai,Du Hai-zhou,et al.Fast approach to mutual information based gene selection with fuzzy rough sets [J].Computer Science,2013,40(7):216-221+235.

[23] Hu Qing-hua,Zhang Lei,An Shuang,et al.On robust fuzzy rough set models [J].IEEE Transactions on Fuzzy Systems,2012,20(4):636-651.

[24] Zhang Jing,Li De-yu,Wang Su-ge,et al.Multi-label text classification based on robust fuzzy rough set model [J].Computer Science,2015,42(7):270-275.

[25] Xu Su-ping,Yang Xi-bei,Yu Hua-long,et al.Multi-label learning with label-specific feature reduction [J].Knowledge-Based Systems,2016,104(1):52-61.

[26] Schapire R E,Singer Y.Improved boosting algorithms using confidence-rated predictions [J].Machine Learning,1999,37(3):297-336.

附中文參考文獻：

[4] 梁新彥,錢宇華,郭 倩,等.面向多標記學習的局部粗糙集 [J].南京大學學報(自然科學),2016,52(2):270-279.

[7] 王 宇,楊志榮,楊習貝.決策粗糙集屬性約簡:一種局部視角方法 [J].南京理工大學學報(自然科學版),2016,40(4):444-449.

[8] 吳 磊,張敏靈.基于類屬屬性的多標記學習算法 [J].軟件學報,2014,25(9):1992-2001.

[10] 徐蘇平,楊習貝,祁云嵩.基于類屬屬性約簡的多標記學習 [J].計算機應用,2015,35(11):3218-3221.

[11] 李 華,李德玉,王素格,等.基于粗糙集的多標記專屬特征學習算法[J].小型微型計算機系統,2015,36(12):2730-2734.

[12] 段 潔,胡清華,張靈均,等.基于鄰域粗糙集的多標記分類特征選擇算法 [J].計算機研究與發展,2015,52(1):56-65.

[15] 胡寶清,咸艷霞.粗糙模糊集與模糊粗糙集的截集性質 [J].模糊系統與數學,2006,20(6):108-114.

[21] 周君儀.基于粗糙集特征選擇的電信客戶流失預測研究 [D].江蘇科技大學,2014:1-86.

[22] 徐菲菲,魏 萊,杜海洲,等.一種基于互信息的模糊粗糙分類特征基因快速選取方法 [J].計算機科學,2013,40(7):216-221,235.

[24] 張 晶,李德玉,王素格,等.基于穩健模糊粗糙集模型的多標記文本分類 [J].計算機科學,2015,42(7):270-275.