李 華,王思宇,王雅茹

(石家莊鐵道大學(xué) 數(shù)理系,河北 石家莊 050043)

0 引 言

現(xiàn)實(shí)世界中，一個(gè)樣本可能同時(shí)與多個(gè)標(biāo)記相關(guān)聯(lián)，被稱為多標(biāo)記學(xué)習(xí)。例如，一幅圖片可以同時(shí)具有沙灘、山和天空等多個(gè)信息標(biāo)注[1]；一首音樂(lè)可以表達(dá)開(kāi)心、高興和放松等多種情感類[2]。由于多標(biāo)記學(xué)習(xí)框架更加準(zhǔn)確地刻畫(huà)了實(shí)際應(yīng)用中大量存在的多義性現(xiàn)象[3]，因而被廣泛應(yīng)用于文本分類[4]、圖像標(biāo)注[5]和社交網(wǎng)絡(luò)[6]等領(lǐng)域。

隨著信息技術(shù)的高速發(fā)展，視頻、文檔和音頻序列等多標(biāo)記數(shù)據(jù)的維數(shù)顯著增加，呈現(xiàn)出高維化的趨勢(shì)。多標(biāo)記數(shù)據(jù)的高維特征不僅增加了計(jì)算成本和存儲(chǔ)代價(jià)，而且還會(huì)導(dǎo)致所謂的“維數(shù)災(zāi)難”[7]問(wèn)題，因此對(duì)多標(biāo)記數(shù)據(jù)的高維特征進(jìn)行降維處理顯得尤為重要。

眾多的降維技術(shù)中，基于粗糙集理論[8]的特征選擇方法受到了廣泛關(guān)注。在粗糙集理論中，特征選擇也稱為屬性約簡(jiǎn)，其是在保持可識(shí)別能力不變的情況下，通過(guò)去除冗余特征來(lái)獲取知識(shí)的屬性約簡(jiǎn)。近年來(lái)，已有學(xué)者將粗糙集理論的屬性約簡(jiǎn)技術(shù)應(yīng)用于多標(biāo)記學(xué)習(xí)。段潔等人應(yīng)用前向貪心策略提出了基于鄰域粗糙集的多標(biāo)記特征選擇算法[9]；H.Li等人提出了基于粗糙集理論的互補(bǔ)決策約簡(jiǎn)啟發(fā)式算法，去除不必要屬性的同時(shí)保持了由標(biāo)記所傳遞的不確定性不變[10]；Y.Lin等人提出了多標(biāo)記模糊粗糙集理論并給出了相應(yīng)的屬性約簡(jiǎn)方法[11]；Y.Li等人提出了一種基于模糊粗糙集的多標(biāo)記特征選擇算法[12]；Z.Qiao等人利用標(biāo)記集正域進(jìn)行多標(biāo)記數(shù)據(jù)的屬性約簡(jiǎn)[13]；W.Qian等人基于特征依賴度和粗糙集理論，提出了標(biāo)記分布學(xué)習(xí)的特征選擇算法[14]。

上述針對(duì)于多標(biāo)記數(shù)據(jù)的屬性約簡(jiǎn)算法都能有效地減少冗余屬性，但對(duì)于大規(guī)模數(shù)據(jù)集而言，他們都不同程度地存在著計(jì)算耗時(shí)較大的問(wèn)題。因此，多標(biāo)記數(shù)據(jù)屬性約簡(jiǎn)算法的加速機(jī)制就成為了一個(gè)亟待解決的關(guān)鍵問(wèn)題。

在粗糙集理論中，基于集合的包含關(guān)系，當(dāng)屬性冪集中的屬性集由粗到細(xì)變化時(shí)，可以確定由粗到細(xì)的粒度序列，稱為正?；蛄衃15]。當(dāng)粒度由粗到細(xì)變化時(shí)，目標(biāo)概念的正域逐漸增大。如果逐步去掉正域，那么數(shù)據(jù)集的規(guī)模會(huì)逐漸縮小。本文首先研究了當(dāng)數(shù)據(jù)集規(guī)模逐步縮小時(shí)，互補(bǔ)決策約簡(jiǎn)中屬性外部重要度的保序性質(zhì)。特別地，當(dāng)粒度由粗到細(xì)變化時(shí)，在逐步去掉正域的數(shù)據(jù)集上，具有最大外部重要度的屬性是保持不變的?；诖?，本文提出互補(bǔ)決策約簡(jiǎn)啟發(fā)式算法的一種加速算法，該加速算法是在粒度由粗到細(xì)的變化過(guò)程中，通過(guò)逐步去掉正域來(lái)降低數(shù)據(jù)集的規(guī)模，縮短計(jì)算約簡(jiǎn)的時(shí)間；同時(shí)，雖然數(shù)據(jù)集的規(guī)模不斷縮小，但具有最大外部重要度的屬性是保持不變的，而約簡(jiǎn)是通過(guò)不斷在核屬性集上增加具有最大外部重要度的屬性得到的，因此加速算法可以得到與原算法相同的互補(bǔ)決策約簡(jiǎn)。

1 基本概念

1.1 多標(biāo)記決策表

多標(biāo)記數(shù)據(jù)可以用多標(biāo)記決策表[10]S=(U,A,L)來(lái)形式化表示，其中U={x1,x2,…,xn}是對(duì)象集合，稱為論域；A={a1,a2,…,am}是條件屬性集合，稱為條件屬性集；L={l1,l2,…,lq}是標(biāo)記的集合，稱為標(biāo)記集。每個(gè)條件屬性a∈A形成一個(gè)滿射a:U→Va，其中Va表示條件屬性a的值域。每個(gè)標(biāo)記l∈L形成一個(gè)滿射l:U→Vl，其中Vl={0,1}表示標(biāo)記l的值域。如果對(duì)象x和標(biāo)記l相關(guān)聯(lián)，那么l(x)=1，否則l(x)=0。

在多標(biāo)記決策表中，條件屬性集A與標(biāo)記集L互不相交，即A∩L=?；U中的每一個(gè)對(duì)象至少關(guān)聯(lián)于標(biāo)記集L中的一個(gè)標(biāo)記[16]；L中的每一個(gè)標(biāo)記至少與U中的一個(gè)對(duì)象相關(guān)聯(lián)[17]。本文不考慮無(wú)標(biāo)記的對(duì)象。

下面是多標(biāo)記決策表的一個(gè)實(shí)例。

例1多標(biāo)記決策表S=(U,A,L)是由中醫(yī)冠心病數(shù)據(jù)集[18]中部分?jǐn)?shù)據(jù)組成，如表1所示。論域U={x1,x2,x3,x4,x5}為患者集合。條件屬性集A={a,b,c}是由3個(gè)癥狀組成的條件屬性集，其中條件屬性a表示“胸痛特點(diǎn)”，其值域?yàn)閧1 隱痛 2 刺痛 3 脹痛}；條件屬性b表示“誘發(fā)因素”，其值域?yàn)閧1 勞累后加重 2 飲酒后加重 3 氣候驟冷加重}；條件屬性c表示“心悸”，其值域?yàn)閧1 出現(xiàn) 2 不出現(xiàn)}。L={l1,l2,l3}是由3個(gè)證型組成的標(biāo)記集，其中l(wèi)1表示“心氣虛”，l2表示“心陽(yáng)虛”，l3表示“氣滯”。顯然，U中的每個(gè)對(duì)象至少關(guān)聯(lián)于L中一個(gè)標(biāo)記，L中的每個(gè)標(biāo)記至少關(guān)聯(lián)于U中的一個(gè)對(duì)象。

表1 多標(biāo)記決策表S=(U,A,L)

1.2 互補(bǔ)決策約簡(jiǎn)

定義1[10]設(shè)S=(U,A,L)是多標(biāo)記決策表，其中A={a1,a2,…,am}，L={l1,l2,…,lq}。給定一個(gè)標(biāo)記li∈L，稱

Ei={x∈U:li(x)=1}

(1)

為對(duì)應(yīng)于標(biāo)記li的一個(gè)標(biāo)記信息集。

標(biāo)記信息集是所有與標(biāo)記li相關(guān)聯(lián)的對(duì)象集合，描述了多標(biāo)記數(shù)據(jù)中隱含的標(biāo)記信息。

(2)

(3)

定義3[10]設(shè)S=(U,A,L)是多標(biāo)記決策表，B?A。B稱為S的一個(gè)互補(bǔ)決策約簡(jiǎn)當(dāng)且僅當(dāng)B滿足下面的條件：

(1)對(duì)任意x∈U，

(4)

(2)對(duì)任意的B′?B，存在x∈U，使得

(5)

若B只滿足條件(1)，則稱B是一個(gè)互補(bǔ)決策協(xié)調(diào)集，否則稱B是不協(xié)調(diào)的。

2 動(dòng)態(tài)粒度下多標(biāo)記決策表的粗糙集近似

由等價(jià)關(guān)系所確定的分劃為描述目標(biāo)概念提供一個(gè)粒化世界[19]。用一組具有偏序關(guān)系的等價(jià)關(guān)系族來(lái)刻畫(huà)目標(biāo)概念被稱為動(dòng)態(tài)粒度下的粗糙集近似[15]。如果在這種粒度變化下，采用逐漸細(xì)化的思想，即粒度由粗變細(xì)，稱為正向近似。對(duì)于粒度計(jì)算和粗糙集理論，動(dòng)態(tài)粒度下的正向近似思想為其提供了一個(gè)新的研究方向，并且在屬性約簡(jiǎn)算法中得到了廣泛且有效的應(yīng)用[20-21]。本節(jié)主要探討動(dòng)態(tài)粒度下多標(biāo)記決策表的粗糙集近似及其相關(guān)性質(zhì)。

設(shè)S=(U,A,L)是多標(biāo)記決策表，在2A上定義偏序關(guān)系≤：設(shè)P≤Q(或者Q≥P)表示P比Q精細(xì)(或者Q比P粗糙)，當(dāng)且僅當(dāng)滿足對(duì)任意的Pi∈U/P，存在Qj∈U/Q使得Pi?Qj，其中U/P={P1,P2,…,Ps}和U/Q={Q1,Q2,…,Qt}分別是由P,Q?A所確定的劃分。如果P≤Q且U/P≠U/Q，稱P嚴(yán)格細(xì)于Q(或者Q嚴(yán)格粗于P)，用PP)來(lái)表示。

性質(zhì)1[10]設(shè)S=(U,A,L)是多標(biāo)記決策表，設(shè)B,C?A，那么

(1)如果B≥C，則

(6)

(2)對(duì)任意x∈U，

(7)

下面由粗決策函數(shù)和細(xì)決策函數(shù)來(lái)定義多標(biāo)記決策表的正域。

定義4設(shè)S=(U,A,L)是多標(biāo)記決策表，B?A，對(duì)于任意x∈U，標(biāo)記集L關(guān)于條件屬性集B的正域定義為：

(8)

下面基于動(dòng)態(tài)粒度下的正向近似思想表示正域。

定義5設(shè)S=(U,A,L)是多標(biāo)記決策表，B={R1,R2,…,Rn}是屬性集族，其中R1≥R2≥…≥Rn(Ri∈2A)，設(shè)Bi={R1,R2,…,Ri}，標(biāo)記集L關(guān)于Bi的正域可表示為：

(9)

性質(zhì)2設(shè)S=(U,A,L)是多標(biāo)記決策表，B={R1,R2,…,Rn}是屬性集族，其中R1≥R2≥…≥Rn(Ri∈2A)，設(shè)Bi={R1,R2,…,Ri}，則

(10)

i=1,2,…,n。

證明：根據(jù)定義5，可得

其中，U1=U，

性質(zhì)2表明標(biāo)記集L關(guān)于屬性集族Bk的正域可由屬性集族Bk-1的正域和在逐漸減少的論域上的屬性集Rk的正域來(lái)表示。

性質(zhì)3設(shè)S=(U,A,L)是多標(biāo)記決策表，B={R1,R2,…,Rn}是屬性集族，其中R1≥R2≥…≥Rn(Ri∈2A)，設(shè)Bi={R1,R2,…,Ri}，i=1,2,…,n，則

(11)

性質(zhì)3表明隨著屬性集族中屬性集數(shù)目的增加，標(biāo)記集L關(guān)于屬性集族的正域是單調(diào)遞增的。

3 多標(biāo)記數(shù)據(jù)互補(bǔ)決策約簡(jiǎn)加速算法

當(dāng)粒度由粗到細(xì)變化時(shí)，在逐步去掉正域的多標(biāo)記決策表上，互補(bǔ)決策約簡(jiǎn)中屬性外部重要度具有保序性質(zhì)，并基于此提出互補(bǔ)決策約簡(jiǎn)啟發(fā)式算法的加速算法。

3.1 屬性重要性的度量

定義6[10]設(shè)S=(U,A,L)是多標(biāo)記決策表，B?A，條件屬性集B的標(biāo)記依賴度為

(12)

這里λ∈(0,1)是常數(shù)。

標(biāo)記依賴度反映了條件屬性子集B對(duì)標(biāo)記集L的近似能力或依賴程度，由依賴度也可以定義每個(gè)條件屬性的重要度。

定義7[10]設(shè)S=(U,A,L)是多標(biāo)記決策表，B?A，a∈B的內(nèi)部重要度定義為：

(13)

定義8[10]設(shè)S=(U,A,L)是多標(biāo)記決策表，B?A，a∈A-B關(guān)于B的外部重要度定義為：

(14)

不同的條件屬性在保持標(biāo)記不確定性方面的作用是不同的，可將這些屬性分為兩類：不必要的和必要的。

定義9[10]設(shè)S=(U,A,L)是多標(biāo)記決策表，B?A，稱條件屬性a∈B是B中的不必要屬性，如果對(duì)于任意的x∈U，

(15)

否則稱a為B的必要屬性。

A中所有必要屬性組成的集合稱為A的核，記為CORE(A)。

下面性質(zhì)表明核可由內(nèi)部重要度定義。

性質(zhì)5[10]設(shè)S=(U,A,L)是多標(biāo)記決策表，則

CORE(A)={a∈A:Siginner(a,A,L,U)>0}

(16)

標(biāo)記依賴度和屬性的內(nèi)部重要度也可用于描述互補(bǔ)決策約簡(jiǎn)。

由性質(zhì)5可知，通過(guò)計(jì)算屬性的內(nèi)部重要度可得到多標(biāo)記決策表的核屬性集。然后，依次在核屬性集上添加具有最大外部重要度的屬性，可以得到一個(gè)互補(bǔ)決策協(xié)調(diào)集。由定理1，若該互補(bǔ)決策協(xié)調(diào)集中的每個(gè)屬性都是必要的，則該互補(bǔ)決策協(xié)調(diào)集為一個(gè)約簡(jiǎn)。基于上述理論，文獻(xiàn)[10]提出了互補(bǔ)決策約簡(jiǎn)啟發(fā)式算法，用來(lái)計(jì)算多標(biāo)記決策表的一個(gè)互補(bǔ)決策約簡(jiǎn)。

定理2表明在多標(biāo)記決策表中，在原始數(shù)據(jù)集和去掉正域的數(shù)據(jù)集上，屬性基于外部重要度的序是保持不變的。因此，在約簡(jiǎn)的啟發(fā)式算法中，在去掉正域的數(shù)據(jù)集上具有最大外部重要度的屬性也是原始數(shù)據(jù)集上具有最大外部重要度的屬性。所以，該定理保證了去掉正域的數(shù)據(jù)集的約簡(jiǎn)和原始數(shù)據(jù)集的約簡(jiǎn)是相同的，其為互補(bǔ)決策約簡(jiǎn)的加速算法提供了理論保證。

3.2 互補(bǔ)決策約簡(jiǎn)的加速算法

互補(bǔ)決策約簡(jiǎn)的加速算法，其主要思想為：首先計(jì)算屬性內(nèi)部重要度來(lái)尋找多標(biāo)記決策表的核屬性集RED。在核屬性集的基礎(chǔ)上，逐次從數(shù)據(jù)集中去掉已選屬性集對(duì)應(yīng)的正域，然后在剩下的數(shù)據(jù)集上選擇外部重要度最大的屬性，依次放入屬性集RED中，直到該特征子集滿足停止準(zhǔn)則，就得到了多標(biāo)記決策表中的一個(gè)互補(bǔ)決策約簡(jiǎn)RED。

算法1互補(bǔ)決策約簡(jiǎn)的加速算法(A-CDR)。

輸入：多標(biāo)記決策表S=(U,A,L)；

輸出：S的一個(gè)互補(bǔ)決策約簡(jiǎn)RED。

1.令RED=?；

2.for (k=1;k≤|A|;k++)

{計(jì)算Siginner(ak,A,L,U)；

如果Siginner(ak,A,L,U)>0，

則RED=RED∪{ak}；}

3.令i=1，R1=RED，B1={R1}，U1=U；

i=i+1；

依次計(jì)算并選取

Sigouter(a0,RED,L,Ui)=max{Sigouter(aj,RED,L,Ui),aj∈A-RED}

RED=RED∪{a0}；

Ri=Ri-1∪{a0}；

Bi={R1,R2,…,Ri}；}

5.輸出屬性約簡(jiǎn)結(jié)果RED。

4 實(shí)驗(yàn)及分析

本節(jié)在6組多標(biāo)記公開(kāi)測(cè)試集上比較互補(bǔ)約簡(jiǎn)啟發(fā)式算法(CDR)和加速算法(A-CDR)的計(jì)算性能。表2為數(shù)據(jù)集的詳細(xì)信息。

表2 數(shù)據(jù)集

本次實(shí)驗(yàn)在硬件配置為Intel(R) Core (TM) i5-5200U CPU @2.20 GHz，內(nèi)存4 GB的計(jì)算機(jī)上，用Matlab語(yǔ)言編程實(shí)現(xiàn)算法。依賴函數(shù)中的參數(shù)λ設(shè)置為0.1。

表3列出了兩種算法在6個(gè)數(shù)據(jù)集上屬性約簡(jiǎn)的結(jié)果和計(jì)算時(shí)間。

由表3可知，在同一個(gè)數(shù)據(jù)集上，加速算法可以得到和原始算法相同的約簡(jiǎn)，但加速算法的計(jì)算時(shí)間明顯減少。

表3 CDR算法和A-CDR算法的約簡(jiǎn)結(jié)果及計(jì)算時(shí)間

為了更好地比較兩種算法計(jì)算約簡(jiǎn)的時(shí)間，表2中的每個(gè)數(shù)據(jù)集都被平均分為20份，記為xi(i=1,2,…,20)，實(shí)驗(yàn)所使用的20份數(shù)據(jù)中的每一份記為Xi(i=1,2,…,20)，其中X1=x1，X2=x1∪x2，…，X20=x1∪x2…∪x20，最后一份數(shù)據(jù)即是數(shù)據(jù)集本身。

圖1是兩種算法分別在6組數(shù)據(jù)集上的約簡(jiǎn)計(jì)算時(shí)間，其中X軸表示上述20份樣本數(shù)目由少到多的數(shù)據(jù)集Xi(i=1,2,…,20)，Y軸表示算法在不同數(shù)據(jù)集上的計(jì)算時(shí)間(單位：秒)。

如圖1中(a)～(f)實(shí)驗(yàn)結(jié)果所示，隨著數(shù)據(jù)集規(guī)模的增加，原始算法和加速算法計(jì)算約簡(jiǎn)的時(shí)間也在增加。樣本的數(shù)據(jù)規(guī)模越大，兩種算法計(jì)算約簡(jiǎn)的時(shí)間消耗差值就越大。這表明加速算法有效地加速了屬性約簡(jiǎn)的過(guò)程，對(duì)于大規(guī)模的數(shù)據(jù)集來(lái)說(shuō)，加速算法的計(jì)算效率更高，更加高效。

圖1 CDR與A-CDR的計(jì)算時(shí)間

5 結(jié) 論

針對(duì)互補(bǔ)決策約簡(jiǎn)啟發(fā)式算法計(jì)算耗時(shí)過(guò)大的缺陷，本文首先研究了動(dòng)態(tài)粒度下互補(bǔ)決策約簡(jiǎn)的屬性外部重要度的保序性質(zhì)，并基于該性質(zhì)，提出了互補(bǔ)決策約簡(jiǎn)啟發(fā)式算法的加速算法。該加速算法通過(guò)逐步縮小數(shù)據(jù)規(guī)模來(lái)降低計(jì)算耗時(shí)，加速了屬性約簡(jiǎn)的過(guò)程，并且可以得到與原始算法相同的約簡(jiǎn)。最后，在多標(biāo)記數(shù)據(jù)集上有效地驗(yàn)證了加速算法的有效性。