基于粒化單調的不完備混合型數據增量式屬性約簡算法

張雨新 孫達明 李 飛

1(唐山工業職業技術學院信息工程系 河北 唐山 063299)

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

0 引 言

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

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

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

對于不完備混合型信息系統，Zhao等[15]將鄰域關系和容差關系進行結合，提出了鄰域容差關系，并根據該二元關系，在不完備混合型信息系統下提出了鄰域容差條件熵，相應的屬性約簡算法也被提出。本文在Zhao等的基礎上，證明鄰域容差關系隨屬性增加時的?；瘑握{性；然后基于這種粒化單調性，研究鄰域容差條件熵的增量式更新，并利用該更新機制設計出相應的增量式屬性約簡算法；最后通過實驗來驗證算法的有效性。

1 基本理論

1.1 粗糙集模型與不完備混合型信息系統

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

對于不完備混合型信息系統，Zhao等[15]聯合鄰域關系和容差關系提出了一種鄰域容差粗糙集模型，該模型通過構造鄰域容差關系來對論域進行知識粒化，作為該模型的理論計算基礎。

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

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

(1)

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

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

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

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

定義1[15]對于不完備混合型信息系統IS=(U,AT,V),U={x1,x2,…,xn},鄰域半徑為δ。屬性子集A1,A2?AT誘導的鄰域容差?；謩e表示為：

那么A2關于A1的條件熵定義為：

(2)

(3)

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

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

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

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

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

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

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

輸出：屬性約簡結果red。

步驟1初始化red←?。

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

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

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

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

步驟5返回屬性約簡結果red。

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

2 屬性變化時條件熵的增量式學習

在實際應用領域，信息系統時刻處于動態更新之中，此時傳統的屬性約簡算法不再有效[4]，對傳統的算法構造增量式學習，設計出增量式的屬性約簡是目前的主要研究方向[8-14]。屬性集的動態增加是信息系統動態更新的一種常見情形，對于條件熵的屬性約簡算法，當不完備混合型信息系統有新的屬性集加入時，計算新的約簡時需要重新進行條件熵的計算，這無疑會增加時間開銷。本節針對不完備混合型信息系統中屬性集增加的情形，提出條件熵的增量更新方法。

對于完備型的信息系統，當屬性增加時，由于論域的?；瘽M足單調性，因此學者們通過等價類的變化進行相關啟發式函數的增量式計算[8-9,12]。本節同樣采用這一思路，通過鄰域容差類的?；瘑握{性去更新條件熵，提出一種高效的條件熵增量式更新方法。

證明：由于P?Q，根據鄰域容差關系的定義有：

證畢。

性質1表明，對于不完備混合型信息系統的鄰域容差關系，當屬性集增加時，其中每個對象的鄰域容差類是逐漸減小的，即鄰域容差類滿足粒化單調性。

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

表1 不完備信息系統

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

令：

(4)

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

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

(5)

證明：根據定義1有：

根據性質1有:

根據集合的計算法則，可以得到：

又由于：

所以：

對于?x∈U，記：

那么

因此：

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

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

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

根據定義3，其中：

即：

因此：

那么：

證畢。

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

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

表2 新的不完備信息系統

根據定義1有：

根據定理1有：

如果采用定義1的方法，得到的計算結果是一致的。

3 增量式屬性約簡算法

本節根據條件熵增量式更新，提出不完備混合型信息系統屬性增加時的條件熵增量式屬性約簡算法。

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

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

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

輸出：新的屬性約簡結果red′。

步驟1初始化red′←red。

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

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

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

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

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

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

步驟6返回屬性約簡結果red′。

4 實驗分析

表3所示為實驗中所使用的數據集，其中所有的數據集均來源于UCI 標準數據集庫，在這6個數據集中，Cylinder、Sick和Annealing為連續型和離散型屬性混合的不完備數據集。整個實驗環節采用Windows 7操作系統、Inter (R) Core (TM) i7-2700 CPU (3.5 GHz)和8.00 GB內存的個人電腦，算法采用MATLAB 2015b進行編程實現和運行。

表3 實驗數據集

4.1 實驗設計與流程

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

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

4.2 參數設置

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

(a) Cylinder (b) Sick

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

4.3 屬性約簡效率的比較

圖2所示為算法1和算法2在6個數據集下動態屬性約簡的用時比較結果。

(a) Cylinder (b) Sick

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

4.4 屬性約簡結果的分類性能比較

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

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

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

4.5 實驗總結

綜合整個實驗部分的所有實驗結果，可以看出本文提出的條件熵增量式屬性約簡算法比傳統的算法具有更高的增量式屬性約簡性能。同時所提出的增量式屬性約簡算法對于屬性增加的動態數據集，具有很高的屬性約簡效率，因此可以證明所提出的增量式算法的有效性。

5 結 語

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