鄰域粗糙集屬性約簡方法研究

傅 凡，李京政，竇慧莉

（1.江蘇省光電子技術(shù)中心江蘇鎮(zhèn)江212000；2.江蘇科技大學(xué)計(jì)算機(jī)學(xué)院，江蘇鎮(zhèn)江212003）

經(jīng)典Pawlak粗糙集模型是建立在等價(jià)關(guān)系基礎(chǔ)上的，適用于處理離散型數(shù)據(jù)，不適用于直接處理現(xiàn)實(shí)中廣泛存在的數(shù)值型數(shù)據(jù)，而將數(shù)值型數(shù)據(jù)離散化會(huì)導(dǎo)致數(shù)據(jù)信息的丟失。鑒于此，眾多學(xué)者提出了多種粗糙集拓展模型[2-6]，例如模糊粗糙集，鄰域粗糙集等，其中，鄰域粗糙集從使用距離構(gòu)建鄰域的角度出發(fā)，其直觀簡潔的形式以及廣泛的應(yīng)用范圍得到了很多學(xué)者的關(guān)注。

在粗糙集的研究進(jìn)程中，屬性約簡[7-13]一直是重要研究內(nèi)容。所謂屬性約簡，就是依據(jù)粗糙集理論中的某種評(píng)價(jià)函數(shù)設(shè)置一個(gè)約束條件，使得刪除數(shù)據(jù)中的無關(guān)/冗余屬性后能夠滿足這一約束，其目的是簡化后續(xù)問題處理、加速問題求解或提升學(xué)習(xí)模型的泛化性能。目前在粗糙集理論中常用的評(píng)價(jià)函數(shù)有近似質(zhì)量[14]、條件熵、近似分布[15]等，約束條件一般有保持度量不變或使得度量指標(biāo)的變化在給定閾值范圍內(nèi)。可以知道，基于一種評(píng)價(jià)函數(shù)的屬性約簡求解出的屬性子集可以保證對(duì)應(yīng)的度量指標(biāo)在約束條件內(nèi)。從多準(zhǔn)則，多視角考慮，評(píng)價(jià)函數(shù)的多樣性會(huì)對(duì)約簡結(jié)果產(chǎn)生的影響也是研究的主要問題，基于一種評(píng)價(jià)函數(shù)的屬性約簡求解出的屬性子集是否能滿足其它度量指標(biāo)的約束條件，這也為考慮多個(gè)評(píng)價(jià)函數(shù)的屬性約簡提供一個(gè)新的方向。

1 鄰域粗糙集與鄰域分類器

在鄰域粗糙集中，一個(gè)決策系統(tǒng)可以表示為二元組DS=＜U，AT∪D＞，其中U是非空有限的樣本集合，AT是所有條件屬性集合，D=g0gggggg表示決策屬性的合集且AT∩D=?。?xi∈U，d（xi）是樣本xi的類別標(biāo)記。鄰域是通過給定半徑考察樣本的鄰居。不妨假設(shè)M=（rij）n×n為論域上的距離矩陣，rij表示樣本xi與xj之間的某一種距離度量，給定參數(shù)δ∈[0，1]，?xi∈U，xi的鄰域半徑為：

δA（xi）表示在樣本xi鄰域半徑內(nèi)的所有樣本。

定義1 令DS=＜U，AT∪g0gggggg＞為一決策系統(tǒng)，?A?AT，根據(jù)屬性集合A可以得到所有樣本之間的距離矩陣，?xi∈U，?X?U，X的鄰域下近似集與上近似集分別定義如下：

定義2給定一個(gè)決策系統(tǒng)DS，?A?AT，?X?U，X相對(duì)于A的近似質(zhì)量為：

其中|X|表示集合X的基數(shù)。

在鄰域粗糙集的基礎(chǔ)上，文獻(xiàn)[16]設(shè)計(jì)出鄰域分類器進(jìn)行分類學(xué)習(xí)研究，算法1給出了鄰域分類器的詳細(xì)流程。

算法1：鄰域分類器

輸入：決策系統(tǒng)DS，待預(yù)測(cè)樣本xi，鄰域半徑參數(shù)δ。

輸出：樣本的預(yù)測(cè)類別標(biāo)記PAT(xi)。

步驟1：?xj∈U，計(jì)算δAT(xi)；

步驟 2：?Xp?U/IND(g0gggggg)，計(jì)算Pr(Xp,δAT(xi))=；

步 驟 3：Xq=arg max{Pr(Xp,δAT(xi))| ?Xp∈U/IND(g0gggggg)}；

步驟4：PAT(xi)=q，輸出ρAT(xi)。

利用鄰域分類器，相應(yīng)的，文獻(xiàn)[16]進(jìn)一步給出了鄰域決策錯(cuò)誤率的概念，以下是鄰域決策錯(cuò)誤率的形式化定義。

定義3令DS為一決策系統(tǒng)，決策系統(tǒng)的鄰域決策錯(cuò)誤率為：

顯然，這是一種留一驗(yàn)證方法。從分類學(xué)習(xí)的視角來看，鄰域決策錯(cuò)誤率越低，表明分類性能越好。

2 屬性約簡

定義4給定一決策系統(tǒng)DS，?A?AT，A被當(dāng)作約簡當(dāng)且僅當(dāng)f（A，D）=f（AT，D）且?B?A，f（B，D）≠f（AT，D）。

定義4所示的屬性約簡定義是一個(gè)能夠保持決策系統(tǒng)中某種度量不發(fā)生變化的最小屬性子集，其中，f（A，D）表示利用屬性集合A的評(píng)價(jià)函數(shù)，以此求得在屬性子集上的某種度量指標(biāo)，這種度量指標(biāo)可以是近似質(zhì)量，鄰域決策錯(cuò)誤率等。進(jìn)一步考察屬性的重要度，?B∈AT且對(duì)于任意的a∈AT-B，如果f（B∪{a}，D）=f（B，D），那么就表明屬性a對(duì)于計(jì)算某種度量沒有帶來任何貢獻(xiàn)，a是冗余的；如果f（B∪{a}，D）≠f（B，D），那么就表示加入屬性a后對(duì)于計(jì)算這種度量產(chǎn)生了影響。可構(gòu)建如下所示的屬性重要度：

根據(jù)上述屬性重要度，算法2構(gòu)建了一個(gè)啟發(fā)式求解屬性約簡的過程，其目標(biāo)是獲得以定義4為依據(jù)的約簡。

算法2：啟發(fā)式算法

輸入：鄰域決策系統(tǒng)DS=＜U,AT∪D＞。

輸出：約簡red。

步驟1：令red←?；

步驟2：若f(red,D)≠f(AT,D)，則執(zhí)行以下循環(huán)，否則執(zhí)行步驟3；

(1)?ai∈AT-red，計(jì)算 Sig(ai,red,D)；

(2)選擇aj，滿足 Sig(aj,red,D)=max{Sig(ai,red,D)|?ai∈AT-red}，令red=red∪{aj}，返回步驟 2；

(3)計(jì)算f(red,D)；

步驟3輸出red。

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

利用算法2，在求解屬性約簡的過程中使用了近似質(zhì)量與鄰域決策錯(cuò)誤率兩種度量準(zhǔn)則，分別記為近似質(zhì)量約簡（AQR），鄰域決策錯(cuò)誤率約簡（NDERR）。實(shí)驗(yàn)中選取了6組UCI數(shù)據(jù)集，表1列出了它們的基本信息。使用歐氏距離構(gòu)造樣本之間的距離矩陣，鄰域半徑參數(shù)δ分別設(shè)定為0.1、0.2、0.3。在此基礎(chǔ)上進(jìn)行了2組實(shí)驗(yàn)，分別比較了利用算法AQR與NDERR求得的近似質(zhì)量和鄰域決策錯(cuò)誤率。

表1 實(shí)驗(yàn)數(shù)據(jù)的基本信息

表2列出了利用近似質(zhì)量約簡與鄰域決策錯(cuò)誤率約簡求得的近似質(zhì)量的對(duì)比；表3列出了利用近似質(zhì)量約簡與鄰域決策錯(cuò)誤率約簡求得的鄰域決策錯(cuò)誤率的對(duì)比。

表2 兩種約簡在近似質(zhì)量的對(duì)比

觀察表2與表3可以得到如下結(jié)論，在大多數(shù)數(shù)據(jù)集上，由近似質(zhì)量約簡求得的近似質(zhì)量都要高于由鄰域決策錯(cuò)誤率約簡求得的近似質(zhì)量，平均要高0.09左右。相應(yīng)的，由鄰域決策錯(cuò)誤率約簡求得的鄰域決策錯(cuò)誤率要低于由近似質(zhì)量約簡求得的鄰域決策錯(cuò)誤率，平均要低0.03左右，除了在數(shù)據(jù)Diabetic Retinopathy Debrecen上兩者相等以外。也就是說，近似質(zhì)量約簡并不能保證約簡結(jié)果在鄰域決策錯(cuò)誤率上能夠滿足約束條件，鄰域決策錯(cuò)誤率約簡也不能保證約簡結(jié)果在近似質(zhì)量上能夠滿足約束條件。

4 結(jié) 論

在鄰域粗糙集上考慮基于一種評(píng)價(jià)函數(shù)的屬性約簡結(jié)果可以滿足相應(yīng)度量指標(biāo)的約束條件，不能夠保證在其他度量指標(biāo)的約束條件。一方面，我們證實(shí)了傳統(tǒng)屬性約簡的有效性；另一方面，由于基于一種評(píng)價(jià)函數(shù)的屬性約簡在度量指標(biāo)的單一性，考慮多個(gè)評(píng)價(jià)函數(shù)的屬性約簡方法也成為一個(gè)新的研究方向。