程玉勝,陳 飛,王一賓,2
(1.安慶師范大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 安慶 246011; 2.安徽省智能感知與計(jì)算重點(diǎn)實(shí)驗(yàn)室, 安徽 安慶 246011; 3. 數(shù)據(jù)科學(xué)與智能應(yīng)用福建省高校重點(diǎn)實(shí)驗(yàn)室,福建 漳州 363000)(*通信作者電子郵箱chengyshaq@163.com)
多標(biāo)記學(xué)習(xí)作為機(jī)器學(xué)習(xí)研究熱點(diǎn),對(duì)現(xiàn)實(shí)世界中多義性對(duì)象的研究具有重要意義[1],并且多標(biāo)記學(xué)習(xí)對(duì)象在日常生活中廣泛存在。在多標(biāo)記學(xué)習(xí)框架之下,數(shù)據(jù)往往面臨多標(biāo)記性和高維性等多種問(wèn)題,使得手工標(biāo)記一般費(fèi)時(shí)費(fèi)力。同時(shí)隨著數(shù)據(jù)維數(shù)的不斷增加,分類(lèi)器的分類(lèi)精度也在不斷下降,因此探究高效的分類(lèi)算法就顯得尤為重要。近年來(lái),相關(guān)學(xué)者在此問(wèn)題上的研究已經(jīng)取得了卓越的成績(jī),提出了多種算法[2-5]。在現(xiàn)有的多標(biāo)記分類(lèi)算法中,與實(shí)例相關(guān)的標(biāo)記重要程度被視作相同,然而在現(xiàn)實(shí)世界中,不同的標(biāo)記對(duì)于同一個(gè)實(shí)例的描述程度并不都是相同的。例如在一幅自然風(fēng)景圖中,如果出現(xiàn)大量的“藍(lán)天”,那么出現(xiàn)大量“白云”的概率也就高,其他標(biāo)記的可能性也就比較低,這種現(xiàn)象被稱(chēng)為標(biāo)記的不平衡性。針對(duì)這種標(biāo)記的不平衡性,Geng等[6]提出了一種標(biāo)記分布學(xué)習(xí)(Label Distribution Learning, LDL)范式,將傳統(tǒng)的邏輯標(biāo)記用概率分布的形式來(lái)進(jìn)行描述,更加準(zhǔn)確地反映了實(shí)例的相關(guān)內(nèi)容。目前也有很多學(xué)者在標(biāo)記分布學(xué)習(xí)范式下對(duì)人年齡[7-8]、人臉面部識(shí)別[9]、文本情感分類(lèi)[10]等領(lǐng)域進(jìn)行研究。
然而,無(wú)論是傳統(tǒng)的多標(biāo)記學(xué)習(xí)還是標(biāo)記分布學(xué)習(xí),其特征選擇方法都假定從一開(kāi)始就可以獲得所有實(shí)例的特征數(shù)據(jù)。但是在許多情況下,往往無(wú)法一次性獲取實(shí)例的所有特征數(shù)據(jù),更多呈現(xiàn)動(dòng)態(tài)生成并記錄相應(yīng)特征數(shù)據(jù),這種情況獲取的特征稱(chēng)為流特征,相應(yīng)的特征選擇算法稱(chēng)為流特征選擇算法[11]。例如,對(duì)一篇小說(shuō)進(jìn)行分類(lèi)并標(biāo)上標(biāo)記,需要提取小說(shuō)里面所有的高頻詞特征。如果小說(shuō)的篇幅比較長(zhǎng)則提取所有特征就需要耗費(fèi)大量的時(shí)間,等所有的特征全部提取完之后再進(jìn)行分類(lèi)訓(xùn)練是不可能的,更可取的方法是一次一個(gè)地生成候選特征,從生成的候選特征中選擇特征集合較小并且分類(lèi)效果也好的特征集合作為最后的特征,這種做法不僅會(huì)節(jié)省大量的資源,同時(shí)分類(lèi)精度也得到了保證。基于此,Wu等[11]提出了在線流特征選擇(Online Streaming Feature Selection, OSFS), 通過(guò)對(duì)特征的相關(guān)性和冗余性進(jìn)行分析,得到滿(mǎn)足條件的特征集合,并在文獻(xiàn)[12]中設(shè)計(jì)出了一系列的算法,取得了十分明顯的效果。但是,文獻(xiàn)[12]中所提到的算法主要適用于離散的數(shù)據(jù),且為單個(gè)邏輯標(biāo)記的數(shù)據(jù)集,對(duì)于多個(gè)邏輯標(biāo)記及其標(biāo)記分布并不適用。
另外,上述算法無(wú)論是邏輯標(biāo)記還是標(biāo)記分布,在對(duì)特征進(jìn)行選擇時(shí)考慮更多的是特征與標(biāo)記之間的相關(guān)性,如:張振海等[13]利用信息熵進(jìn)行多標(biāo)記的特征選擇;Lee等[4]提出一種使用多變量互信息對(duì)特征進(jìn)行選擇,但對(duì)特征之間的冗余性考慮不充分,屬性約簡(jiǎn)不夠充分。OSFS雖然考慮了特征間的冗余性,但計(jì)算過(guò)程較為復(fù)雜,算法效率較低,而粗糙集最大的貢獻(xiàn)就是進(jìn)行屬性約簡(jiǎn),去除冗余屬性。
粗糙集理論是Pawlak[14]提出的一種處理不精確、不確定的數(shù)學(xué)工具,自提出以來(lái)在人工智能、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域得到了成功應(yīng)用。相較于其他的特征選擇算法,粗糙集方法不需要先驗(yàn)知識(shí),僅僅利用數(shù)據(jù)本身所提供的信息發(fā)現(xiàn)問(wèn)題的規(guī)律[15],計(jì)算過(guò)程簡(jiǎn)單高效。粗糙集理論通過(guò)構(gòu)建上下近似來(lái)對(duì)知識(shí)進(jìn)行描述,通過(guò)下近似與全體論域之間的比值來(lái)刻畫(huà)屬性的依賴(lài)度從而判斷屬性的冗余性。一般來(lái)說(shuō),下近似越大,屬性間的依賴(lài)度越大,冗余性也就越大。目前利用粗糙集進(jìn)行屬性約簡(jiǎn)和特征選擇是多標(biāo)記學(xué)習(xí)的一個(gè)熱點(diǎn),Yu等[16-17]將粗糙集的擴(kuò)展鄰域粗糙集應(yīng)用在多標(biāo)記分類(lèi)問(wèn)題上,取得了顯著的成績(jī);段潔等[18]利用鄰域粗糙集實(shí)現(xiàn)了多標(biāo)記分類(lèi)任務(wù)的特征選擇算法。但上述算法都應(yīng)用在邏輯標(biāo)記且特征數(shù)據(jù)是靜態(tài)的環(huán)境下,對(duì)現(xiàn)實(shí)世界中的數(shù)據(jù)流的情況并不適用。
目前,針對(duì)流特征數(shù)據(jù)的研究更加具有現(xiàn)實(shí)意義,同時(shí),標(biāo)記分布比傳統(tǒng)的邏輯標(biāo)記更能反映樣本標(biāo)記的真實(shí)情況。由此,本文提出了基于粗糙集的數(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í),同時(shí)利用粗糙集中的依賴(lài)度來(lái)度量特征之間的相關(guān)性,從而去除冗余屬性,保證最終的特征子集的分類(lèi)效果。實(shí)驗(yàn)結(jié)果表明該方法是有效的。
多標(biāo)記學(xué)習(xí)是針對(duì)現(xiàn)實(shí)生活中普遍存在的多義性對(duì)象而提出的一種學(xué)習(xí)框架,在這個(gè)框架之下,樣本由多個(gè)特征和多個(gè)標(biāo)記構(gòu)成,學(xué)習(xí)的目的是將未知的實(shí)例對(duì)應(yīng)上更多正確的標(biāo)記[19]。假設(shè)T是含有n個(gè)特征的特征集合T={t1,t2,…,tn},L是由m個(gè)標(biāo)記組成的標(biāo)記集合L={l1,l2,…,lm},其中1表示有該標(biāo)記,而-1表示沒(méi)有該標(biāo)記,則含有i個(gè)樣本的多標(biāo)記數(shù)據(jù)集可以表示為:
D={(Tj,Lj)|1≤j≤i,Tj∈T,Lj∈L}
(1)
傳統(tǒng)的多標(biāo)記學(xué)習(xí)中,所有實(shí)例的特征數(shù)據(jù)都是完整的,并可以一次性獲得,從而進(jìn)行相應(yīng)的分類(lèi)學(xué)習(xí)。但是,在一些情況下,同一實(shí)例的不同特征數(shù)據(jù)往往是實(shí)時(shí)生成并記錄的,并且這些特征的生成是無(wú)序的,有些特征數(shù)據(jù)甚至是無(wú)窮的。如果用傳統(tǒng)的多標(biāo)記特征選擇算法無(wú)疑會(huì)浪費(fèi)大量的時(shí)間和精力,對(duì)于那些特征數(shù)據(jù)是無(wú)窮的實(shí)例,傳統(tǒng)方法更是無(wú)法進(jìn)行特征選擇。解決這個(gè)問(wèn)題最好的方法就是從實(shí)時(shí)產(chǎn)生的特征數(shù)據(jù)中選擇符合一定條件的特征構(gòu)成候選特征子集,利用這個(gè)特征子集進(jìn)行相應(yīng)的訓(xùn)練和測(cè)試,這種方法被稱(chēng)為在線流特征選擇(OSFS)[11]。在OSFS框架之下,對(duì)特征子集的選擇標(biāo)準(zhǔn)總共分成兩部分:1)特征與標(biāo)記之間相關(guān)性;2)特征與特征之間的冗余性。根據(jù)上述兩種情況,候選的特征集合又可以分為以下4個(gè)部分:1)不相關(guān)的特征;2)強(qiáng)相關(guān)的特征;3)弱相關(guān)非冗余特征;4)弱相關(guān)冗余特征。
通過(guò)計(jì)算特征與標(biāo)記之間的相關(guān)性舍棄不相關(guān)特征并保留強(qiáng)相關(guān)特征,對(duì)于弱相關(guān)的特征再進(jìn)行特征之間冗余性判斷,舍棄冗余屬性。由此,最終的特征子集應(yīng)包括強(qiáng)相關(guān)特征和弱相關(guān)但非冗余特征。
粗糙集理論是一種處理不精確、不確定的數(shù)學(xué)工具,自提出便廣泛應(yīng)用到人工智能、機(jī)器學(xué)習(xí)等領(lǐng)域。在粗糙集理論中,對(duì)于一個(gè)信息系統(tǒng)IS=〈U,Q,V,f〉,其中:U表示全體論域,即樣本集合;Q表示屬性集合(包括條件屬性C和決策屬性D);V表示屬性的值域;f表示一種映射。在分類(lèi)過(guò)程中,差別不大的樣本被劃成一類(lèi),它們的關(guān)系被稱(chēng)為相容關(guān)系或者等價(jià)關(guān)系。為方便問(wèn)題描述,本文僅僅考慮了等價(jià)關(guān)系。對(duì)于任何一個(gè)屬性集合C,其等價(jià)關(guān)系可以用下面不可分辨關(guān)系IND來(lái)表示,定義如下:
IND(C)={(x,y)∈U×U:f(x,a)=f(y,a),a∈C}
(2)
不可分辨關(guān)系也就是U上的等價(jià)關(guān)系,可以用U/C來(lái)表示。粗糙集理論中,用上下近似來(lái)對(duì)知識(shí)進(jìn)行描述,假設(shè)B?C,X?U,則B的上近似與B的下近似定義如下:
?}
(3)
(4)
通過(guò)上下近似可以定義正域(POS)、負(fù)域(NEG)和邊界域(BNG):
(5)
(6)
(7)
發(fā)現(xiàn)屬性之間的依賴(lài)關(guān)系也是數(shù)據(jù)分析中十分重要的一個(gè)問(wèn)題。在粗糙集理論中,可以利用依賴(lài)度(Dep)來(lái)表示兩個(gè)屬性之間的依賴(lài)程度。假設(shè)B?C,則決策屬性D對(duì)條件屬性B的依賴(lài)程度用式(8)進(jìn)行計(jì)算:
(8)
表1 粗糙集示例
在多標(biāo)記學(xué)習(xí)框架之下,標(biāo)記的準(zhǔn)確性常常與特征的個(gè)數(shù)有著密切的聯(lián)系。在一定的范圍內(nèi)特征越多標(biāo)記準(zhǔn)確性也就越高,但隨著特征數(shù)目的不斷增加,次要特征和冗余特征也隨之增多,這就會(huì)導(dǎo)致分類(lèi)器的精度下降,所以選擇與標(biāo)記相關(guān)的特征就顯得尤為重要。在目前的多標(biāo)記特征選擇中,大多數(shù)學(xué)者利用信息熵來(lái)度量特征與標(biāo)記之間的相關(guān)性,選擇信息熵較大的特征作為重要特征[20-22],但是,傳統(tǒng)的信息熵只能處理離散型數(shù)據(jù),對(duì)于標(biāo)記分布中標(biāo)記空間的連續(xù)型概率分布數(shù)據(jù)并不適用。
在統(tǒng)計(jì)學(xué)中,皮爾遜相關(guān)系數(shù)(Pearson)常常用于度量?jī)蓚€(gè)連續(xù)變量X和Y之間的相關(guān)性,其值為-1~1。其中正值表示正相關(guān),反之則為負(fù)相關(guān);皮爾遜相關(guān)系數(shù)絕對(duì)值越大則表示兩個(gè)變量的相關(guān)性越大。并且規(guī)定,若相關(guān)系數(shù)大于0.6則為強(qiáng)相關(guān),相關(guān)系數(shù)小于0.2則為弱相關(guān)或不相關(guān)[23]。皮爾遜相關(guān)系數(shù)可以通過(guò)式(9)進(jìn)行計(jì)算:
(9)
其中:E表示數(shù)學(xué)期望,Cov表示協(xié)方差。
在傳統(tǒng)的OSFS框架[11]之下,往往是利用特征與標(biāo)記之間的條件概率對(duì)特征的冗余性進(jìn)行判斷,對(duì)于特征X、S和標(biāo)記T,如果P(T|X,S)=P(T|S),則表示特征X對(duì)標(biāo)記T是冗余的。這種判斷方法需要知道特征空間、標(biāo)記空間和每個(gè)特征的先驗(yàn)知識(shí)且計(jì)算復(fù)雜,而粗糙集方法可以很好地解決這個(gè)問(wèn)題。在粗糙集理論中,條件屬性與決策屬性之間的依賴(lài)度可以很好地刻畫(huà)兩者之間的依賴(lài)程度。將依賴(lài)度引入到特征選擇中對(duì)兩個(gè)特征之間進(jìn)行冗余性判斷。計(jì)算流入特征與已確定特征之間的依賴(lài)度,若兩者依賴(lài)度越大,獨(dú)立性越小,冗余性也就越大。
FSSRS算法對(duì)于實(shí)時(shí)產(chǎn)生的特征數(shù)據(jù)進(jìn)行十折離散化[24],利用皮爾遜相關(guān)系數(shù)對(duì)特征與標(biāo)記之間的相關(guān)性進(jìn)行判斷,對(duì)于強(qiáng)相關(guān)的特征直接保留進(jìn)入最終的特征子集中,不相關(guān)的特征則直接舍棄,弱相關(guān)的特征暫時(shí)保留在弱相關(guān)子集中,在下一個(gè)弱相關(guān)特征流入時(shí)進(jìn)行冗余性判斷。
對(duì)于流入的弱相關(guān)特征,與弱相關(guān)子集中的特征利用式(8)計(jì)算冗余性,將冗余的屬性直接舍棄,在保證分類(lèi)器精度的同時(shí)也確保了最小的特征子集。
由于數(shù)據(jù)是實(shí)時(shí)產(chǎn)生并記錄的,需要提前設(shè)置好相關(guān)參數(shù):α為強(qiáng)相關(guān)系數(shù),β為不相關(guān)系數(shù),γ為冗余性系數(shù)。
在線特征相關(guān)性 在t時(shí)刻獲取特征fti,利用皮爾遜相關(guān)系數(shù)進(jìn)行計(jì)算特征與標(biāo)記的相關(guān)性計(jì)算: 如果Pearsonti≥α則為強(qiáng)相關(guān)性特征,直接存到最終的特征子集中; 如果Pearsonti≤β則為不相關(guān)特征直接舍棄,如果α 在線特征冗余性 對(duì)于暫時(shí)保留的特征fti,利用式(8)計(jì)算與ti-1時(shí)刻確定的最終特征子集進(jìn)行依賴(lài)度計(jì)算,如果Depti≤γ則表示沒(méi)有冗余性,該特征存到最終特征子集中,否則舍棄該特征。 通過(guò)相關(guān)性與冗余性的判斷之后輸出最終的特征子集,并利用此特征子集進(jìn)行訓(xùn)練與測(cè)試。該算法的偽代碼如下所示: 算法 基于粗糙集的數(shù)據(jù)流多標(biāo)記分布特征選擇。 輸入fti為ti時(shí)刻的特征數(shù)據(jù),α為強(qiáng)相關(guān)系數(shù),β為不相關(guān)系數(shù),γ為冗余性系數(shù)。 輸出 選擇后的特征子集FS。 1) repeat 2) 在ti時(shí)刻得到一個(gè)新的特征數(shù)據(jù)fti; 3) 利用皮爾遜相關(guān)系數(shù)計(jì)算t時(shí)刻的相關(guān)性Pearsonti; 4) IFPearsonti≥α 5) 將fti加入到FS中; 6) 跳轉(zhuǎn)到步驟17); 7) ELSE IFPearsonti≤β 8) 舍棄fti; 9) ELSE 10) 利用式(8)計(jì)算特征間的依賴(lài)度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算法流程 1)Chebyshev距離(↓): 2)Clark距離(↓): 3)Canberra距離(↓): 4)KL-div散度(↓): 5)Cosine相似度(↑): 6)Intersection相似度(↑): 本文所有實(shí)驗(yàn)均運(yùn)行在3.4 GHz處理器,8.00 GB內(nèi)存及Matlab R2016a的實(shí)驗(yàn)平臺(tái)上。實(shí)驗(yàn)數(shù)據(jù)來(lái)源于標(biāo)記分布常用數(shù)據(jù)集(http://ldl.herokuapp.com/download),選取其中12個(gè)數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn),其基本信息如表2所示。 為驗(yàn)證算法的有效性,與耿新提出的AA-kNN (Algorithm Adaptationk-Nearest Neighbors)、PT-SVM (Problem Transformation SVM)和SA-IIS(Specialized Algorithm Improved Iterative Scaling)進(jìn)行對(duì)比,對(duì)比實(shí)驗(yàn)采用10折交叉驗(yàn)證。表2中也列出了各數(shù)據(jù)集特征選擇的數(shù)量,表3~8則給出了11個(gè)數(shù)據(jù)集在三種不同算法上的實(shí)驗(yàn)結(jié)果(平均值±標(biāo)準(zhǔn)差), 實(shí)驗(yàn)中,α=0.8,β=0.3,γ=0.5。表9和表10是在Yeast-dtt數(shù)據(jù)集上,分類(lèi)器選擇kNN,當(dāng)γ=0.5時(shí),α、β不同取值時(shí)的結(jié)果(說(shuō)明:表中黑色加粗的數(shù)字表示在該指標(biāo)上特征選擇后的數(shù)據(jù)優(yōu)于原始數(shù)據(jù);數(shù)據(jù)括號(hào)中的數(shù)字為該值在評(píng)價(jià)指標(biāo)中的排名情況)。 表3 Chebyshev實(shí)驗(yàn)結(jié)果 表4 Clark實(shí)驗(yàn)結(jié)果 表5 Canberra實(shí)驗(yàn)結(jié)果 表6 Kullback-Leibler實(shí)驗(yàn)結(jié)果 表7 Cosine實(shí)驗(yàn)結(jié)果 表8 Intersection實(shí)驗(yàn)結(jié)果 表9 Yeast-dtt數(shù)據(jù)集不同參數(shù)實(shí)驗(yàn)結(jié)果 (β=0.3,γ=0.5) 表10 Yeast-dtt數(shù)據(jù)集不同參數(shù)實(shí)驗(yàn)結(jié)果 (β=0.2,γ=0.5) 從實(shí)驗(yàn)結(jié)果來(lái)看,在11個(gè)數(shù)據(jù)集6個(gè)評(píng)價(jià)指標(biāo)共66個(gè)實(shí)驗(yàn)結(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時(shí),α=0.7取得更多最優(yōu)結(jié)果; 當(dāng)β=0.2時(shí),α=0.8取得更多最優(yōu)結(jié)果; 所有特征選擇的結(jié)果都優(yōu)于原始數(shù)據(jù)。 圖2~圖3是Yeast-cold數(shù)據(jù)集在不同參數(shù)下的實(shí)驗(yàn)結(jié)果對(duì)比。由圖2可以看出,特征選擇數(shù)目與弱相關(guān)系數(shù)有著密切的關(guān)系;由圖3可以看出, 經(jīng)過(guò)特征選擇后的分類(lèi)效果要優(yōu)于原始特征,結(jié)果也較為穩(wěn)定。 針對(duì)傳統(tǒng)多標(biāo)記學(xué)習(xí)框架的邏輯標(biāo)記和靜態(tài)特征的情況,提出了基于粗糙集的數(shù)據(jù)流多標(biāo)記分布特征選擇算法,為了更加準(zhǔn)確地對(duì)樣本進(jìn)行描述,將傳統(tǒng)的邏輯標(biāo)記轉(zhuǎn)換成概率的形式。同時(shí)對(duì)實(shí)時(shí)產(chǎn)生的特征數(shù)據(jù)利用皮爾遜相關(guān)系數(shù)與粗糙集中的依賴(lài)度進(jìn)行處理,保留符合條件的特征構(gòu)成特征子集進(jìn)行訓(xùn)練,在節(jié)約資源的情況下又使得分類(lèi)精度得到了保證,多組實(shí)驗(yàn)證明了該算法的有效性。 圖2 不同參數(shù)特征選擇個(gè)數(shù)(Yeast-cold) 但是本文仍存在一些問(wèn)題,如FSSRS算法在進(jìn)行冗余性判斷時(shí),對(duì)于已經(jīng)是強(qiáng)相關(guān)性的特征沒(méi)有進(jìn)行冗余性檢查,以后將對(duì)此進(jìn)行改進(jìn);同時(shí)本文的參數(shù)是人為設(shè)定,今后將繼續(xù)完善參數(shù)選擇,使得算法更加高效。 圖3 Yeast-cold數(shù)據(jù)集不同參數(shù)實(shí)驗(yàn)結(jié)果3 實(shí)驗(yàn)結(jié)果及分析
3.1 評(píng)價(jià)指標(biāo)
3.2 實(shí)驗(yàn)數(shù)據(jù)集
3.3 實(shí)驗(yàn)結(jié)果與分析
4 結(jié)語(yǔ)