連續(xù)值屬性約簡算法改進

唐寅 閔涼宇

【摘要】目前存在的基于粗糙集理論的屬性約簡算法多數(shù)只適用于離散型數(shù)據(jù)。而在現(xiàn)實工作中，不僅有符號、類別等離散型數(shù)據(jù)，更有大量的連續(xù)型或?qū)嵭蛿?shù)據(jù)，甚至二者的混合。傳統(tǒng)的離散化過程并不能保存屬性在數(shù)值上的差異，造成了一定程度的信息損失。本文提出一種將模糊聚類和粗糙集相結(jié)合的屬性約簡算法，從而避免了實型數(shù)據(jù)的離散化。

【關(guān)鍵詞】數(shù)據(jù) 粗糙集 屬性約簡算法

一、連續(xù)值決策表的屬性約簡

連續(xù)值決策表的屬性約簡主要分為兩部分：一，將模糊聚類引入到對象劃分中，解決粗糙集在連續(xù)數(shù)值屬性處理上的局限性，同時獲得滿足一定依賴度要求的Q型模糊聚類最佳參數(shù)λQ及對應(yīng)實例序?qū)Γ▁i，xj）λ，本文將這部分稱之為基于模糊聚類和粗糙集的連續(xù)型決策表對象離散化；二，對條件屬性進行R型模糊聚類，獲得期望數(shù)目的聚類，并從中選出符合依賴度要求的屬性子集即為一個可接受的屬性約簡。

（一）連續(xù)型決策表對象離散化

通過Q型模糊聚類，我們將實型屬性的模糊性轉(zhuǎn)化為實例對象的模糊性，依據(jù)對象間的模糊近似程度，實現(xiàn)對象的離散化。Q型模糊聚類的最終結(jié)果取決于決策類對全部條件屬性的依賴度，在數(shù)據(jù)充分的情況下，可認為這一依賴度的值為1。我們可以獲得Q型模糊聚類的最佳參數(shù)λQ，及其對應(yīng)的實例序?qū)Γ▁i，xj）λ。如果屬性子集P是條件屬性C相對于D的一個合理約簡，屬性子集P表達的對象模糊相似關(guān)系應(yīng)最大程度地保持條件屬性C表達的對象間模糊相似關(guān)系。那么序?qū)Γ▁i，xj）λ？劬（i，j）在屬性子集P的模糊相似矩陣FMP中，同樣具有劃分對象的作用。FMP（i，j）是模糊相似關(guān)系FMP中，使得分類滿足依賴度要求的對象間相似度最低要求。算法如下：

輸入：一個實型決策表S=（U，CUD，V，f）。輸出：Q型模糊聚類最佳參數(shù)λQ及其序?qū)Γ▁i，xj）λ。Step1.決策表數(shù)據(jù)預處理：補缺、去重等；Step2.計算實例對象間的模糊相似矩陣FMC；Step3.運用直接聚類法進行對象劃分，聚類參數(shù)λ，得到劃分類Uλ；Step4.計算決策類對劃分類的依賴度γλ（D），若γλ（D）=θ，轉(zhuǎn)至Step5；否則，調(diào)整參數(shù)λ，轉(zhuǎn)至Step3；Step5.得到最佳聚類參數(shù)λQ，計算其相應(yīng)序?qū)Γ▁i，xj）λ；對序?qū)Γ▁i，xj）λ的數(shù)據(jù)行進行再次噪聲檢查，如果存在多組不受噪聲干擾的序?qū)Γ瑒t從中任選一組；Step6.本部分算法結(jié)束，輸出最佳聚類參數(shù)λQ和相應(yīng)序?qū)Γ▁i，xj）λ。

（二）連續(xù)值屬性約簡

本文用R型模糊聚類將相似度貼近的屬性聚為一類，并從每一類中選擇代表性的屬性構(gòu)成屬性子集，并以該子集的依賴度是否接近決策屬性對全部條件屬性的依賴度為標準判斷該屬性子集是否合理。定義1 設(shè)實型決策表S=（U，CUD），條件屬性C滿足依賴度閾值的最佳聚類參數(shù)為λQ，對應(yīng)序?qū)椋▁i，xj）λ，則屬性子集P是C相對于D的屬性約簡：

FMP為基于屬性子集P的對象間模糊相似矩陣。

在基于粗糙集的啟發(fā)式屬性約簡算法中，往往約簡的結(jié)果無法由預期控制。而在實際屬性約簡的工作中，人們通常對約簡屬性的數(shù)目有一個心理預期。同樣地，在連續(xù)值決策表中也可以運用這種思路求得一個符合預期的可接受屬性約簡。具體分為以下三個步驟：一，以預期屬性數(shù)目為主導，對條件屬性進行聚類。二，對聚類結(jié)果進行屬性組合。應(yīng)當優(yōu)先選擇每一類中平均相似度最大的屬性進入屬性子集。可以獲得一個由最具代表性的屬性構(gòu)成的屬性子集P。三，計算屬性子集依賴度。基于屬性子集計算對象間模糊相似關(guān)系FMP，以FMP（i，j）（其中，（i，j）=（xi，xj）λ）為聚類的閾值，得到論域?qū)ο蟮膭澐郑瑥亩@得依賴度γp（D，F(xiàn)MP（i，j））。如果其依賴度滿足：

其中，ρ為一接近0的正數(shù)，則說明屬性子集P為C的一個可接受約簡。如果>ρ，說明算法不能滿足預期屬性規(guī)模的屬性約簡，此時應(yīng)當調(diào)整屬性規(guī)模預期或選擇其它算法。

二、實證

以數(shù)據(jù)集A（見附錄A）的數(shù)據(jù)為例，說明本部分屬性約簡過程。在A的決策表S=（U，SUD）中，條件屬性集C={c1，c2，…，c7}，設(shè)定期望屬性數(shù)目為z=3。Step1.計算條件屬性的模糊相似矩陣FMR7×7。由于案例數(shù)據(jù)為時間序列，因此選擇模糊相似關(guān)系為：

Step2.基于FMR，應(yīng)用直接聚類法對條件屬性進行劃分，記為Rλ；并以|Rλ=z|為聚類終止條件。Step3.計算每一類中，屬性之間的平均相似度：

Step4.構(gòu)建屬性子集，R0.73{1}中的最佳代表屬性為c2，R0.73{2}中的最佳代表屬性為c4，R0.73{3}中的最佳代表屬性為c5。所以，屬性子集P={c2，c4，c5}

Step5.計算決策屬性對屬性子集P的依賴度：γp（D，F(xiàn)MP（（xi，xj）λ））。我們得到（xi，xj）λ=（x14，x15），γc（D，λQ）=0.35。計算基于P的實例對象間的模糊相似關(guān)系FMP20×20，ρ的設(shè)置不應(yīng)太小。依賴接近度為0.1，說明約簡前后的正域波動為兩個對象，是可以接受的。因此，P={c2，c4，c5}是全部條件屬性C相對于D的一個可接受約簡。事實上，基于全部條件屬性C的實例對象的聚類結(jié)果：

在兩組分類中，只有{6，18}在U_P中發(fā)生了合并。這說明，屬性子集P不僅較好地繼承了條件屬性C的劃分能力，對其中相對于決策屬性的分類能力，更是很好地保留。該種算法可以適用于連續(xù)型、離散型以及二者混合的數(shù)據(jù)類型。

參考文獻

[1]Chen Y，Zhu Q，Xu H.Finding rough set reducts with fish swarm algorithm[J].Knowledge-Based Systems，2015，81：22-29.

[2]唐孝，舒蘭.基于粒計算的屬性約簡改進算法[J].計算機科學，2014（32）.

[3]張吉洋，馮長煥.加權(quán)模糊相似矩陣的構(gòu)造[J].統(tǒng)計與決策，2014（20）.

作者簡介：唐寅（1991-），男，漢族，貴州金沙人，首都經(jīng)濟貿(mào)易大學學生，碩士學位，研究方向：電子商務(wù)。