基于粗糙集的分布式集值數(shù)據(jù)屬性約簡

胡 軍，黃思妤，邵 瑞

(重慶郵電大學(xué) 計算智能重慶市重點實驗室，重慶 400065)

0 引 言

實際獲取的數(shù)據(jù)中，往往存在大量的冗余數(shù)據(jù)。因此，為了提高知識獲取的效率，需要對這些原始數(shù)據(jù)進行約簡。粗糙集是屬性約簡的重要方法。經(jīng)典的粗糙集一般用來處理完備的數(shù)據(jù)，但在實際問題中，由于獲取手段的限制以及實際問題的需要，獲取到的數(shù)據(jù)很可能是不完備數(shù)據(jù)，區(qū)間值數(shù)據(jù)或是集值數(shù)據(jù)。目前針對集值數(shù)據(jù)已有許多研究成果。文獻[1-3]從不完備信息系統(tǒng)的角度討論了集值信息系統(tǒng)的處理。文獻[4-5]定義了一種容差關(guān)系和最大容差類來劃分論域，并給出了獲取決策規(guī)則的方法。文獻[6]針對集值信息系統(tǒng)提出了一種優(yōu)勢關(guān)系和相應(yīng)的屬性約簡算法。文獻[7]定義了一個模糊關(guān)系，可以用來衡量2個集值對象之間的相似程度。文獻[8]提出了一個δ優(yōu)勢關(guān)系和相應(yīng)的粗糙集定義，并基于分辨矩陣給出了屬性約簡算法。文獻[9]提出了2種類型的模糊粗糙近似，并針對所提出的2種近似分別給出了相應(yīng)的約簡方法。

分布存儲是目前數(shù)據(jù)存儲的一種普遍形式，即數(shù)據(jù)存儲在網(wǎng)絡(luò)中的多個數(shù)據(jù)站點上。針對分布式數(shù)據(jù)的屬性約簡問題已有一些研究。文獻[10-11]針對垂直分布的數(shù)據(jù)給出了一種利用不一致對象來求解全局屬性核的算法，并通過并行計算條件信息熵來獲得近似約簡。文獻[12]運用基于優(yōu)勢關(guān)系的鄰域粗糙集理論提出了MapReduce下基于分辨矩陣的屬性約簡算法，該方法可以有效地約簡混合型大數(shù)據(jù)集里的冗余屬性。文獻[13]針對符號型數(shù)據(jù)，定義了分布式?jīng)Q策信息系統(tǒng)下的粗糙集模型，并提出了一種基于正域的屬性約簡算法，文獻[14-15]在這一基礎(chǔ)之上，分別將該方法拓展到了連續(xù)值數(shù)據(jù)和不完備數(shù)據(jù)。但是，目前還沒有針對分布式集值數(shù)據(jù)的相關(guān)研究。

本文主要研究分布式環(huán)境下集值決策信息系統(tǒng)的屬性約簡問題，給出了分布式集值決策信息系統(tǒng)的粗糙集模型，并提出了分布式集值決策信息系統(tǒng)下的屬性約簡算法，最后用實驗證明了提出方法的有效性。

1 基本概念

集值信息系統(tǒng)是指在一個信息系統(tǒng)中，屬性的值不唯一并且以集合的形式存在。對于集值的理解一般有2種語義：一種是合取語義，另一種是析取語義。本文主要研究在析取語義背景下的情況。

定義1S=(U,C∪D,V,F)是一個集值決策信息系統(tǒng)，對于?b∈C，x,y∈U，x和y之間的相似度定義為

(1)

從概率的角度出發(fā)，μb(x,y)描述了x和y取相同值的概率。對于B?C，x和y在屬性B下的相似關(guān)系RB定義為

(2)

可以證明，RB具有自反性和對稱性。

定義2S=(U,C∪D,V,F)是一個集值決策信息系統(tǒng)，對于B?C，x∈U，x相對于B的δ-相似類定義為

δB(x)={y∈U|μRB(x,y)≥δ}(0≤δ≤1)

(3)

(3)式中，δ是一個閾值?？梢酝ㄟ^δ來調(diào)節(jié)通過屬性子集B所得到的信息粒度。具體地，δ越大，信息粒度越小；δ越小，信息粒度越大。

(4)

設(shè)U/D={d1,d2,…,dm}是論域上的劃分，那么D相對于B的正域為

(5)

根據(jù)此定義，正域是在給定的條件屬性下，論域里所有可以被確定分類的對象集合，它代表了系統(tǒng)的確定分類能力。

2 分布式集值決策信息系統(tǒng)下的粗糙集模型

設(shè)Δ={S1,S2,…,Sn}是一個分布式集值決策信息系統(tǒng)，其中，Si=(Ui,Ci∪D,V,F)表示1個子決策表，并且U1=U2=…=Un，Ci≠Cj(i≠j)。

(6)

D相對于B的正域為

POSB(D)={x∈U|?Si∈Δ∧dj∈U/D(δBi(x)?dj)}

3 分布式集值決策信息系統(tǒng)的屬性約簡

下面將基于前面提出的分布式集值決策信息系統(tǒng)下的粗糙集模型來研究分布式集值決策信息系統(tǒng)的屬性約簡。

定理2設(shè)Δ={S1,S2,…,Sn}是一個分布式集值決策信息系統(tǒng)，Φ和Ψ是Δ的2個子集。如果Φ?Ψ，則有POSΦ(D)?POSΨ(D)。

證明：可由定理1證得成立，故在此省略證明過程。

根據(jù)定理2可知，如果在一個分布式集值決策信息系統(tǒng)Δ中添加一個新的子決策信息表，那么Δ的正域?qū)龃蠡蛘呔S持不變。相應(yīng)地，如果在Δ中刪掉一個子決策信息表，這個時候正域則會減小或者維持不變。

定義5設(shè)Δ={S1,S2,…,Sn}是一個分布式集值決策信息系統(tǒng)，如果POSΔ-{Si}(D)=POSΔ(D)成立，那么在該分布式集值決策信息系統(tǒng)Δ中，子決策表Si相對于D是可約簡的。否則，子決策表Si是不可約簡的。

定理3設(shè)Δ={S1,S2,…,Sn}是一個分布式集值決策信息系統(tǒng)，如果POSCi(D)?POSΔ-{Si}(D)成立，那么子決策表Si是可約簡的。

證明：根據(jù)上述定理1可以很容易得出POSΔ(D)=POSCi(D)∪POSΔ-{Si}(D)，那么如果有POSCi(D)?POSΔ-{Si}(D)成立，則不難得出結(jié)論POSΔ(D)=POSΔ-{Si}(D)，因此由定義5可知，子決策表Si是可約的。證得定理3成立。

定理4設(shè)Δ={S1,S2,…,Sn}是一個分布式集值決策信息系統(tǒng)，當(dāng)且僅當(dāng)?x∈U(x∈POSCi(D)∧x?POSΔ-{Si}(D))成立，子決策表Si相對于Δ不可約簡。

定理5設(shè)Δ={S1,S2,…,Sn}是一個分布式集值決策信息系統(tǒng)，a是子決策表Si的一個屬性。如果在子決策表中a相對于D是可約的，那么在該分布式集值決策信息系統(tǒng)Δ中，屬性a相對于D也是可約的。如果在子決策表中屬性a相對于D是不可約的，在Δ中，屬性a不一定是不可約的。

證明：如果在子決策表Si中a相對于D是可約簡的，那么從子決策表Si中刪掉屬性a后其正域保持不變。根據(jù)定理1，Δ的正域也保持不變。即證得，在該分布式集值決策信息系統(tǒng)Δ中，屬性a相對于D是可約簡的。

定義7設(shè)Δ={S1,S2,…,Sn}是一個分布式集值決策信息系統(tǒng)，Θ={T1,T2,…,Tn}是Δ的一個子系統(tǒng)，其中?Ti∈Θ(?Si∈Δ(Ti?Si))。當(dāng)Θ是Δ相對于D的一個約簡時，需滿足的2個條件為

①POSΘ(D)=POSΔ(D)

根據(jù)上述定義6和定義7可知，一個分布式集值決策信息系統(tǒng)Δ與其約簡子系統(tǒng)Θ具有相同的全局正域。刪掉約簡子系統(tǒng)中的任意條件屬性都會導(dǎo)致Θ的正域減小。下面給出分布式集值決策信息系統(tǒng)的屬性約簡算法。

分布式集值決策信息系統(tǒng)屬性約簡算法

輸入：Δ={S1,S2,…,Sn}

輸出：約簡子系統(tǒng)Θ

1：Θ=Δ

2：for每一個子決策信息表Si∈Δdo

3： for每一個條件屬性a∈Sido

5： 從Θ刪掉屬性a

6： end if

7： end for

8：end for

對于一個給定的分布式集值決策信息系統(tǒng)，屬性約簡算法首先選取其中的一個子決策信息表，并對該子決策信息表中的每一個屬性根據(jù)定義6進行可約性判定，如果可約則去掉該屬性，否則保留該屬性直至子決策信息中的所有屬性都判定完畢。然后，算法繼續(xù)選取其他子決策信息表進行同樣的操作，直至所有子決策信息表都操作完畢。最后，可以得到一個約簡的子系統(tǒng)。接下來通過一個實例來說明算法的執(zhí)行過程。

例如表1，一個分布式集值決策信息系統(tǒng)Δ，該系統(tǒng)有2個子決策信息表，S1和S2。其中，S1有3個條件屬性，即C1={a1,a2,a3}，S2有2個條件屬性，即C2={a4,a5}。則使用上述屬性約簡算法得到Δ的約簡子系統(tǒng)的過程為

令δ=2/5：

對于S1，有

δC1(x1)={x1}，δC1(x2)={x2,x3,x8}，

δC1(x3)={x2,x3,x4,x6,x8}，

δC1(x4)={x3,x4,x6}，δC1(x5)={x5,x6}，

δC1(x6)={x3,x4,x5,x6}，

δC1(x7)={x7}，δC1(x8)={x2,x3,x8}，

U/D={(x1,x7),(x3,x4),(x2,x5,x6,x8)}，

POSC1(D)={x1,x5,x6,x7}。

對于S2，有

δC2(x1)={x1,x2,x4,x7}，

δC2(x2)={x1,x2,x3,x4,x8}，

δC2(x3)={x2,x3,x4,x8}，

δC2(x4)={x1,x2,x3,x4,x7}，

δC2(x5)={x5,x6}，

δC2(x6)={x5,x6,x8}，

δC2(x7)={x1,x4,x7}，

δC2(x8)={x2,x3,x6,x8}，

POSC2(D)={x5,x6,x8}。

表1 分布式集值決策信息系統(tǒng)

由定理1可得

POSC(D)=POSC1(D)∪POSC2(D)=

{x1,x5,x6,x7,x8}。

刪除屬性a1，對于S1，有

δC1-{a1}(x1)={x1,x5,x6}，

δC1-{a1}(x2)={x2,x3,x8}，

δC1-{a1}(x3)={x2,x3,x4,x5,x6,x8}，

δC1-{a1}(x4)={x3,x4,x5,x6}，

δC1-{a1}(x5)={x1,x3,x4,x5,x6}，

δC1-{a1}(x6)={x1,x3,x4,x5,x6}，

δC1-{a1}(x7)={x7}，

δC1-{a1}(x8)={x2,x3,x8}，

POSC1-{a1}(D)={x7}，POSC2(D)={x5,x6,x8}，

POSC-{a1}(D)=POSC1-{a1}(D)∪POSC2-{a1}(D)=

{x5,x6,x7,x8}。

由定理1可得

POSC-{a1}(D)=POSC1-{a1}(D)∪POSC2-{a1}(D)=

{x1,x2,x3,x5,x6,x7,x8}

由此發(fā)現(xiàn)，刪除屬性a1后全局正域發(fā)生了改變，因此可以推斷，屬性a1是不可約簡的。同理，依次對屬性a2，a3，a4和a5進行相應(yīng)的判斷，最終可以得出a2和a5是不可約的，a3和a4是可約的。因此，最終可以得到一個約簡，約簡結(jié)果為{a1,a2,a5}。

4 實驗結(jié)果與分析

為了驗證本文所提出方法的有效性，實驗中首先運用分布式集值決策信息系統(tǒng)屬性約簡算法對系統(tǒng)進行屬性約簡，接著利用約簡后的系統(tǒng)來訓(xùn)練分類器，最后通過集成來獲得分類的結(jié)果。所用的分類器是SVM(support vector machine), GBDT(gradient boosting decison tree), RF(random forest), NB(na?ve bayes)和LR(logistics regression)，分類集成的方法是將不同分類器上樣本的同類別概率加權(quán)求和，確定概率最大的類別為該樣本的最終類別。

實驗所用的5組數(shù)據(jù)集來自于UCI，數(shù)據(jù)集的具體信息如表2。為了模擬分布式集值決策信息系統(tǒng)且避免不同的屬性順序?qū)Y(jié)果的影響，實驗將每份數(shù)據(jù)集的條件屬性順序隨機打亂10次，并分別分割成2,3,4份來模擬具有2,3,4個數(shù)據(jù)站點的分布式集值決策信息系統(tǒng)，即每份數(shù)據(jù)集進行10次實驗，最后將分類結(jié)果取平均值。

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

圖1 約簡前后平均分類準(zhǔn)確率(2個站點)Fig.1 Average classification accuracy before and after reduction (two sites)

實驗中，數(shù)據(jù)集zoo, autism_adult_data, autistic_adolescent_data, cylinder_bands和extention_of_z_alizadeh_sani，對應(yīng)2，3，4個站點所選取的閾值分別為0.24/0.24/0.24, 0.26/0.24/0.24, 0.26/0.24/0.24,0.26/0.26/0.26,0.24/0.24/0.24。

1)2個站點。

約簡后每個數(shù)據(jù)集最終剩余的平均屬性個數(shù)(四舍五入取整)如表3，屬性約簡前后集成的平均分類準(zhǔn)確率如圖1。

2)3個站點。

約簡后每個數(shù)據(jù)集最終剩余的平均屬性個數(shù)(四舍五入取整)如表4，屬性約簡前后集成的平均分類準(zhǔn)確率如圖2。

表3 約簡后剩余平均屬性個數(shù)(2個站點)

3)4個站點。

約簡后每個數(shù)據(jù)集最終剩余的平均屬性個數(shù)(四舍五入取整)如表5，屬性約簡前后集成的平均分類準(zhǔn)確率如圖3。

表4 約簡后剩余平均屬性個數(shù)(3個站點)

表5 約簡后剩余平均屬性個數(shù)(4個站點)

從表3～表5可以看出，本文所提出的屬性約簡算法使得所有數(shù)據(jù)集都得到了一定程度的簡化。其中，對于分割成2個站點的數(shù)據(jù)集來說，extention_of_z_alizadeh_sani數(shù)據(jù)集約掉的屬性最多，相應(yīng)的簡化程度最高；分割成3個站點的數(shù)據(jù)集中，cylinder_bands數(shù)據(jù)集約掉的屬性最多，得到的簡化程度最高；分割成4個站點的數(shù)據(jù)集中，extention_of_z_alizadeh_sani數(shù)據(jù)集約掉的屬性最多，得到的簡化程度最高。由圖1—圖3可以看出，所有數(shù)據(jù)集在約簡后的分類準(zhǔn)確率相對于原始數(shù)據(jù)來說，其分類準(zhǔn)確率基本保持不變，有的約簡后的數(shù)據(jù)集的分類準(zhǔn)確率甚至更高。其中，數(shù)據(jù)集extention_of_z_alizadeh_sani的表現(xiàn)效果最好，該數(shù)據(jù)集在被分割成不同的站點時均能得到很高程度的簡化，且在所有分類器上幾乎都能得到比原始數(shù)據(jù)集更高的分類準(zhǔn)確率，說明約簡去掉了原始數(shù)據(jù)集中冗余的甚至是具有干擾作用的屬性，從而提高了分類的準(zhǔn)確率。總之，本文提出的針對分布式集值決策信息系統(tǒng)的屬性約簡算法，可以對系統(tǒng)進行一定程度的簡化，并且保持系統(tǒng)的分類能力基本不變。

5 結(jié) 論

為了簡化分布式集值決策信息系統(tǒng)，同時保持它的分類能力不改變，本文給出了分布式集值決策信息系統(tǒng)下的粗糙集模型，并基于該模型提出了相應(yīng)的屬性約簡算法。實驗結(jié)果表明，該方法可以有效地去除系統(tǒng)中的冗余屬性并且保持系統(tǒng)的分類能力基本不變，有效地解決了分布式集值數(shù)據(jù)的屬性約簡問題。該方法閾值的選取會對分類的準(zhǔn)確率產(chǎn)生一定的影響，如何選取合適的閾值將是本文未來的研究工作。