基于粒化單調(diào)的不完備混合型數(shù)據(jù)增量式屬性約簡算法

張雨新 孫達(dá)明 李 飛

1(唐山工業(yè)職業(yè)技術(shù)學(xué)院信息工程系 河北 唐山 063299)

2(東北大學(xué)計(jì)算中心 河北 秦皇島 066004)

0 引 言

屬性約簡[1-2]又稱為特征選擇，目前在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等領(lǐng)域發(fā)揮了很重要的作用[3]。然而在實(shí)際工程應(yīng)用中，數(shù)據(jù)集往往是不斷動態(tài)增加的，而傳統(tǒng)的屬性約簡算法進(jìn)行運(yùn)用時會產(chǎn)生大量的重復(fù)計(jì)算和時間開銷，不利于實(shí)際的應(yīng)用。為了改善這一局限性，學(xué)者們將增量式學(xué)習(xí)應(yīng)用在傳統(tǒng)的屬性約簡中，提出了增量式的屬性約簡方法[4-5]，從而滿足了動態(tài)數(shù)據(jù)集屬性約簡的時效性。

不完備信息系統(tǒng)[6]是一種常見的信息系統(tǒng)類型，即數(shù)據(jù)集中的某些屬性值是缺失的。對于這類數(shù)據(jù)集，學(xué)者們不斷地進(jìn)行了增量式的屬性約簡研究。Meng等[7]基于不完備信息系統(tǒng)的正區(qū)域提出了一種快速的屬性約簡算法，用來提高對于動態(tài)數(shù)據(jù)的屬性約簡效率。Shu等[8]針對不完備信息系統(tǒng)屬性變化的情形，提出了正區(qū)域的增量式更新，進(jìn)而構(gòu)造出了相應(yīng)的增量式屬性約簡算法。針對這類問題，李成等[9]也提出了類似的算法，同時Shu等[10]針對不完備信息系統(tǒng)對象增加的情形，設(shè)計(jì)了一種新的增量式屬性約簡算法。進(jìn)一步地，Shu等[11]提出了一種改進(jìn)的增量式屬性約簡算法，優(yōu)化了原先算法的效率。根據(jù)一致性度量，Xie等[12]在對象增加、屬性增加、屬性值變化方面，提出了一種新的增量式屬性約簡算法。針對區(qū)分矩陣的方法，丁棉衛(wèi)等[13]提出了一種二進(jìn)制區(qū)分矩陣的不完備系統(tǒng)增量式屬性約簡算法。在其他類型的不完備信息系統(tǒng)中，Luo等[14]提出了一種不完備多尺度信息系統(tǒng)的增量式算法。

然而，實(shí)際數(shù)據(jù)環(huán)境下的很多不完備信息系統(tǒng)既包含了離散型的屬性也包含了連續(xù)型的屬性，稱這類信息系統(tǒng)為不完備混合型信息系統(tǒng)[15]，目前對這類信息系統(tǒng)的增量式屬性約簡研究甚少。本文針對這一問題，提出一種屬性增加時的增量式屬性約簡算法。

對于不完備混合型信息系統(tǒng)，Zhao等[15]將鄰域關(guān)系和容差關(guān)系進(jìn)行結(jié)合，提出了鄰域容差關(guān)系，并根據(jù)該二元關(guān)系，在不完備混合型信息系統(tǒng)下提出了鄰域容差條件熵，相應(yīng)的屬性約簡算法也被提出。本文在Zhao等的基礎(chǔ)上，證明鄰域容差關(guān)系隨屬性增加時的?；瘑握{(diào)性；然后基于這種?；瘑握{(diào)性，研究鄰域容差條件熵的增量式更新，并利用該更新機(jī)制設(shè)計(jì)出相應(yīng)的增量式屬性約簡算法；最后通過實(shí)驗(yàn)來驗(yàn)證算法的有效性。

1 基本理論

1.1 粗糙集模型與不完備混合型信息系統(tǒng)

在粗糙集理論[3]的研究范疇內(nèi)，數(shù)據(jù)集被格式化成信息系統(tǒng)的形式。通常一個信息系統(tǒng)可簡單表示為一個三元組IS=(U,AT,V)，其中：U稱為信息系統(tǒng)的論域，是數(shù)據(jù)集所有對象的集合；AT稱為信息系統(tǒng)的屬性集；V表示信息系統(tǒng)所有屬性值的集合，即對于?x∈U且?a∈AT，a(x)∈V，這里a(x)表示對象x在屬性a下的屬性值。在實(shí)際中，信息系統(tǒng)的屬性值可能是缺失的，并且連續(xù)型的屬性值和離散型的屬性值并存，對于這類信息系統(tǒng)，稱之為不完備混合型信息系統(tǒng)[15]。

對于不完備混合型信息系統(tǒng)，Zhao等[15]聯(lián)合鄰域關(guān)系和容差關(guān)系提出了一種鄰域容差粗糙集模型，該模型通過構(gòu)造鄰域容差關(guān)系來對論域進(jìn)行知識?；鳛樵撃Ｐ偷睦碚撚?jì)算基礎(chǔ)。

(a(y)=*)∪((a∈AD→a(x)=a(y))∩

(a∈AN→|a(x)-a(y)|≤δ))}

(1)

式中：δ為鄰域半徑，是一個非負(fù)常數(shù)；“*”表示缺失的屬性值。

式中：U={x1,x2,…,xn}。

1.2 不完備混合型信息系統(tǒng)的條件熵與屬性約簡

屬性約簡是粗糙集理論的研究重點(diǎn)[3]，屬性約簡的目的是對原信息系統(tǒng)中選擇一個極小的屬性子集，使得這個屬性子集與原屬性集具有相同的分類能力[16-17]。在不完備混合型信息系統(tǒng)中，Zhao等[15]基于條件熵的方式提出了一種屬性約簡方法。

定義1[15]對于不完備混合型信息系統(tǒng)IS=(U,AT,V),U={x1,x2,…,xn},鄰域半徑為δ。屬性子集A1,A2?AT誘導(dǎo)的鄰域容差粒化分別表示為：

那么A2關(guān)于A1的條件熵定義為：

(2)

(3)

式中：[xi]D表示對象xi在決策屬性集D下的等價類。

定義2[15]對于不完備混合型決策信息系統(tǒng)IS=(U,C∪D,V)，若red?C是該信息系統(tǒng)的條件熵屬性約簡，則同時滿足：

(1)E(D|C)=E(D|red)。

(2) ?a∈red,E(D|red)

基于定義2所示的屬性約簡定義，其對應(yīng)的屬性約簡算法如算法1所示。

算法1[15]不完備混合型信息系統(tǒng)的條件熵屬性約簡算法

輸入：不完備混合型決策信息系統(tǒng)IS=(U,C∪D,V)，鄰域半徑δ。

輸出：屬性約簡結(jié)果red。

步驟1初始化red←?。

步驟2令E(D|φ)=1。遍歷C-red中每個屬性a，計(jì)算屬性a的條件熵屬性重要度：

sig(a)=E(D|red)-E(D|red∪{a})

步驟3對于步驟2中C-red所有屬性，找出屬性重要度最大的屬性，記為amax。

步驟4若sig(amax)=0，則轉(zhuǎn)步驟5；若sig(amax)>0，則red←red∪{amax}，并返回步驟2。

步驟5返回屬性約簡結(jié)果red。

在算法1中，通過條件熵作為啟發(fā)式函數(shù)進(jìn)行屬性的選擇，直至達(dá)到條件E(D|C)=E(D|red)成立時算法終止，選擇出的red為最終的屬性約簡結(jié)果。算法1的時間復(fù)雜度為O(|C|2·|U|2)[15]。

2 屬性變化時條件熵的增量式學(xué)習(xí)

在實(shí)際應(yīng)用領(lǐng)域，信息系統(tǒng)時刻處于動態(tài)更新之中，此時傳統(tǒng)的屬性約簡算法不再有效[4]，對傳統(tǒng)的算法構(gòu)造增量式學(xué)習(xí)，設(shè)計(jì)出增量式的屬性約簡是目前的主要研究方向[8-14]。屬性集的動態(tài)增加是信息系統(tǒng)動態(tài)更新的一種常見情形，對于條件熵的屬性約簡算法，當(dāng)不完備混合型信息系統(tǒng)有新的屬性集加入時，計(jì)算新的約簡時需要重新進(jìn)行條件熵的計(jì)算，這無疑會增加時間開銷。本節(jié)針對不完備混合型信息系統(tǒng)中屬性集增加的情形，提出條件熵的增量更新方法。

對于完備型的信息系統(tǒng)，當(dāng)屬性增加時，由于論域的粒化滿足單調(diào)性，因此學(xué)者們通過等價類的變化進(jìn)行相關(guān)啟發(fā)式函數(shù)的增量式計(jì)算[8-9,12]。本節(jié)同樣采用這一思路，通過鄰域容差類的?；瘑握{(diào)性去更新條件熵，提出一種高效的條件熵增量式更新方法。

證明：由于P?Q，根據(jù)鄰域容差關(guān)系的定義有：

證畢。

性質(zhì)1表明，對于不完備混合型信息系統(tǒng)的鄰域容差關(guān)系，當(dāng)屬性集增加時，其中每個對象的鄰域容差類是逐漸減小的，即鄰域容差類滿足?；瘑握{(diào)性。

例1表1所示的是一個不完備混合型信息系統(tǒng)，其中：論域U={x1,x2,x3,x4,x5,x6}；屬性集AT={a,b,c}；屬性a為連續(xù)型屬性；屬性b和屬性c為離散型屬性；“*”表示缺失的屬性值；F、T、S、C代表了對應(yīng)的屬性值，無實(shí)際含義。

表1 不完備信息系統(tǒng)

令P={a,b}，Q={a,b,c}，鄰域半徑δ=0.1。根據(jù)鄰域容差類的定義，有:

令：

(4)

定義3表明，在不完備混合型信息系統(tǒng)中，當(dāng)屬性集發(fā)生增加時，一部分鄰域容差類會減小，一部分鄰域容差類可能保持不變。根據(jù)如上所述的變化規(guī)律，接下來可以推導(dǎo)出條件熵的增量式更新。

E(A2|A′1)=E(A2|A1)-Δ

(5)

證明：根據(jù)定義1有：

根據(jù)性質(zhì)1有:

根據(jù)集合的計(jì)算法則，可以得到：

又由于：

所以：

對于?x∈U，記：

那么

因此：

顯然?x∈U有Ψ(x)?Φ(x)，即:

|Φ(x)|-|Ψ(x)|=|Φ(x)-Ψ(x)|=

因此E(A2|A′1)=E(A2|A1)-Δ,其中：

根據(jù)定義3，其中：

即：

因此：

那么：

證畢。

E(D|A′)=E(D|A)-Δ

例2在例1的基礎(chǔ)上，假設(shè)不完備混合型信息系統(tǒng)增加屬性集ΔA=j5i0abt0b，新的信息系統(tǒng)如表2所示，此時AT′={a,b,c,d}。

表2 新的不完備信息系統(tǒng)

根據(jù)定義1有：

根據(jù)定理1有：

如果采用定義1的方法，得到的計(jì)算結(jié)果是一致的。

3 增量式屬性約簡算法

本節(jié)根據(jù)條件熵增量式更新，提出不完備混合型信息系統(tǒng)屬性增加時的條件熵增量式屬性約簡算法。

對于不完備混合型信息系統(tǒng)IS=(U,C∪D,V),約簡集為red。當(dāng)新的屬性集ΔC加入條件屬性集時，新的信息系統(tǒng)表示為IS′=(U,C′∪D,V′)，其中C′=C∪ΔC。算法2所示為基于屬性增加時的條件熵增量式屬性約簡算法。

算法2屬性增加時不完備混合型信息系統(tǒng)的條件熵增量式屬性約簡算法

輸入：增加屬性集ΔC后新的不完備混合型決策信息系統(tǒng)IS′=(U,C′∪D,V′)；鄰域半徑δ；舊信息系統(tǒng)IS的屬性約簡red；條件熵E(D|red)。

輸出：新的屬性約簡結(jié)果red′。

步驟1初始化red′←red。

步驟2根據(jù)條件熵E(D|red)按照定理1增量式計(jì)算新的條件熵E(D|C′),判斷E(D|C′)與E(D|red)之間的大小關(guān)系：若E(D|C′)=E(D|red)，那么跳轉(zhuǎn)入步驟5；若E(D|C′)

步驟3遍歷C′-red′中每個屬性a，計(jì)算屬性a的條件熵屬性重要度：

sig(a)=E(D|red′)-E(D|red′∪{a})

找出C′-red′中屬性重要度sig(a)最大的屬性，記為amax。

步驟4若sig(amax)=0，那么跳轉(zhuǎn)入步驟5，若sig(amax)>0，則red←red∪{amax}，并返回步驟3。

步驟5對于屬性集red′中的每個屬性a，若存在E(D|red′-{a})=E(D|red′)，那么red′←red′-{a}。重復(fù)進(jìn)行步驟5，直到不存在這樣的屬性。

步驟6返回屬性約簡結(jié)果red′。

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

表3所示為實(shí)驗(yàn)中所使用的數(shù)據(jù)集，其中所有的數(shù)據(jù)集均來源于UCI 標(biāo)準(zhǔn)數(shù)據(jù)集庫，在這6個數(shù)據(jù)集中，Cylinder、Sick和Annealing為連續(xù)型和離散型屬性混合的不完備數(shù)據(jù)集。整個實(shí)驗(yàn)環(huán)節(jié)采用Windows 7操作系統(tǒng)、Inter (R) Core (TM) i7-2700 CPU (3.5 GHz)和8.00 GB內(nèi)存的個人電腦，算法采用MATLAB 2015b進(jìn)行編程實(shí)現(xiàn)和運(yùn)行。

表3 實(shí)驗(yàn)數(shù)據(jù)集

4.1 實(shí)驗(yàn)設(shè)計(jì)與流程

本實(shí)驗(yàn)的流程如下，首先分別使用算法1和算法2對表3中的6個數(shù)據(jù)集分別進(jìn)行動態(tài)的屬性約簡，通過比較屬性約簡所需的時間開銷來證明所提出算法的增量式屬性約簡效率。在屬性約簡的過程中，通過比較每次數(shù)據(jù)集屬性約簡結(jié)果的分類精度，來驗(yàn)證所提算法屬性約簡的優(yōu)越性。

表3所示的是靜態(tài)的不完備數(shù)據(jù)集，為了模擬數(shù)據(jù)集屬性動態(tài)變化的情形，本實(shí)驗(yàn)采用原始數(shù)據(jù)集屬性遞增的方式進(jìn)行處理，即原始數(shù)據(jù)集按照屬性平均分成7個屬性子集，從屬性空集開始每次增加一個屬性子集來生成數(shù)據(jù)集屬性的一次動態(tài)更新，這樣便可以實(shí)現(xiàn)數(shù)據(jù)集屬性的7次更新。整個實(shí)驗(yàn)均采用這種方式進(jìn)行實(shí)驗(yàn)。

4.2 參數(shù)設(shè)置

在算法1和算法2中，鄰域半徑δ是算法的入?yún)?，它的取值不同對最終的屬性約簡結(jié)果將產(chǎn)生很重要的影響，本節(jié)將通過實(shí)驗(yàn)的方法對鄰域半徑δ選取合適的參數(shù)。對鄰域半徑在[0,0.3]中以0.02為間隔分別進(jìn)行取值，然后將對應(yīng)的鄰域半徑分別作為算法2的入?yún)⑦M(jìn)行增量式屬性約簡，每次增量式屬性約簡將會得到對應(yīng)的屬性約簡集，利用SVM分類器對約簡集進(jìn)行分類精度計(jì)算，從而得到該約簡集下的分類精度，所有數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果如圖1所示。

(a) Cylinder (b) Sick

觀察圖1可以發(fā)現(xiàn)，隨著數(shù)據(jù)集屬性增量次數(shù)的增加，屬性約簡結(jié)果的分類精度是逐漸增大的，對于不同的鄰域半徑δ，當(dāng)取值在0.12～0.16之間時得到的分類精度大致是最高的，本實(shí)驗(yàn)將鄰域半徑設(shè)定為δ=0.14進(jìn)行實(shí)驗(yàn)。其中數(shù)據(jù)集Mushroom的分類精度不隨鄰域半徑的變化而變化，這主要是由于該數(shù)據(jù)集為不包含連續(xù)型屬性的數(shù)據(jù)集，因此實(shí)驗(yàn)結(jié)果不受鄰域半徑影響。

4.3 屬性約簡效率的比較

圖2所示為算法1和算法2在6個數(shù)據(jù)集下動態(tài)屬性約簡的用時比較結(jié)果。

(a) Cylinder (b) Sick

數(shù)據(jù)集剛開始進(jìn)行增量式更新時，算法1和算法2的屬性約簡用時相近，當(dāng)數(shù)據(jù)集更新次數(shù)逐漸增多時，兩種算法的約簡用時出現(xiàn)明顯的差距，其中算法1的增加速率逐漸增大，而本文所提出的算法2，隨著屬性更新次數(shù)的增加，其約簡用時增長較為緩慢。出現(xiàn)這種現(xiàn)象的主要原因是由于算法2是一種增量式的屬性約簡算法，數(shù)據(jù)集每次更新后，算法會在之前屬性約簡結(jié)果的基礎(chǔ)上進(jìn)行計(jì)算，避免了對舊數(shù)據(jù)集的重復(fù)計(jì)算；同時對于屬性的逐漸增加，信息系統(tǒng)論域的?；泳?xì)，導(dǎo)致信息系統(tǒng)再增加屬性集時，對象的容差類很難發(fā)生很大的變化。因此算法2具有較高的動態(tài)屬性約簡效率。

4.4 屬性約簡結(jié)果的分類性能比較

屬性約簡旨在找到與原始屬性集具有相同區(qū)分能力的屬性子集，而具有相同區(qū)分能力的屬性子集可能具有不同的分類性能，因此具有更高分類性能的屬性子集則更加優(yōu)越。本節(jié)比較兩類算法屬性約簡結(jié)果的分類性能，其中屬性集的分類性能通過支持向量機(jī)分類器(SVM)進(jìn)行評估，即通過屬性子集十折交叉驗(yàn)證的分類精度去衡量。

在數(shù)據(jù)集屬性每次動態(tài)更新中，算法1和算法2都會得到當(dāng)時數(shù)據(jù)集的屬性約簡結(jié)果，然后利用SVM分類器對約簡結(jié)果進(jìn)行分類訓(xùn)練，便得到了對應(yīng)的分類精度，其結(jié)果如表4所示?？梢园l(fā)現(xiàn)本文所提出的算法2在大部分情形下具有較高的分類性能，例如：在數(shù)據(jù)集Sick中，算法2在第6次的更新結(jié)果中分類精度達(dá)到了86.42%，而算法1只有83.08%；在數(shù)據(jù)集Iono中，算法2第5次實(shí)驗(yàn)結(jié)果的分類精度為99.92%；在數(shù)據(jù)集Mushroom中，算法2第6次實(shí)驗(yàn)結(jié)果的分類精度為95.37%。在某些情形下，算法1的分類精度稍高于算法2，例如數(shù)據(jù)集Cylinder的第3次結(jié)果，數(shù)據(jù)集Annealing的第2次結(jié)果等。結(jié)果表明算法2的約簡結(jié)果具有較高的分類性能。

表4 增量式屬性約簡分類精度比較 %

4.5 實(shí)驗(yàn)總結(jié)

綜合整個實(shí)驗(yàn)部分的所有實(shí)驗(yàn)結(jié)果，可以看出本文提出的條件熵增量式屬性約簡算法比傳統(tǒng)的算法具有更高的增量式屬性約簡性能。同時所提出的增量式屬性約簡算法對于屬性增加的動態(tài)數(shù)據(jù)集，具有很高的屬性約簡效率，因此可以證明所提出的增量式算法的有效性。

5 結(jié) 語

本文通過鄰域容差關(guān)系隨屬性增加時的?；瘑握{(diào)性，研究了鄰域容差條件熵的增量式更新，并且根據(jù)這種更新機(jī)制提出一種不完備混合型信息系統(tǒng)屬性增加時的增量式屬性約簡算法。實(shí)驗(yàn)證明了所提出算法的有效性。接下來將進(jìn)一步探索不完備混合型信息系統(tǒng)對象增加時的增量式屬性約簡問題。