基于聚類?；痛亻g散度的屬性約簡算法

李 艷，范斌，郭劼

（1.河北大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，河北保定 071002；2.河北省機器學(xué)習(xí)與計算智能重點實驗室（河北大學(xué)），河北保定 071002；3.北京師范大學(xué)珠海校區(qū)應(yīng)用數(shù)學(xué)與交叉科學(xué)研究中心，廣東珠海 519087）

0 引言

粗糙集理論［1-2］在數(shù)據(jù)挖掘、決策分析、人工智能等領(lǐng)域受到廣泛關(guān)注，該理論基于等價關(guān)系建立了信息系統(tǒng)的屬性約簡策略，即利用兩個精確的集合（上下近似）對不確定概念進行刻畫，在保持信息系統(tǒng)分類能力的前提下盡可能地去除冗余特征，提取數(shù)據(jù)中最重要的信息，從而達到知識發(fā)現(xiàn)和進行決策支持的目的。

傳統(tǒng)粗糙集約簡方法是基于等價關(guān)系建立的，因此僅能處理符號值數(shù)據(jù)，但實際應(yīng)用問題中連續(xù)值數(shù)據(jù)是廣泛存在的，而將連續(xù)值數(shù)據(jù)離散化可能會導(dǎo)致信息丟失，且不同的離散化策略會影響屬性約簡效果。許多學(xué)者對Pawlak 粗糙集模型進行了改進：一方面利用模糊性，將數(shù)據(jù)集進行模糊化處理，提出相應(yīng)的模糊粗糙集模型。如Zhang 等［3］利用信息熵理論提出了一種特征選擇方法，此方法基于模糊粗糙集，對原粗糙集模型進行了改進；Yang 等［4］考慮了模糊粗糙集與三支決策的組合形式，從三支決策角度構(gòu)建了魯棒模糊粗糙集模型；Xiong 等［5］利用實例間相關(guān)性來挖掘隱藏的標簽相關(guān)性，提出了一種基于模糊互信息與標簽分布的特征選擇算法；Sang 等［6］利用模糊優(yōu)勢鄰域粗糙集對動態(tài)區(qū)間值有序數(shù)據(jù)進行了研究，提出了增量特征選擇方法；Yuan 等［7］針對無監(jiān)督混合數(shù)據(jù)集難以進行屬性約簡的問題，基于模糊粗糙集模型提出了一種屬性約簡算法。另一方面，從等價關(guān)系角度進行改進。對于有序關(guān)系的數(shù)據(jù)，Greco 等［8］首先提出用優(yōu)勢關(guān)系代替?zhèn)鹘y(tǒng)粗糙集中的等價關(guān)系處理帶有序關(guān)系的連續(xù)值數(shù)據(jù)集；Huang 等［9］對優(yōu)勢粗糙集模型進行了擴展，提出了處理復(fù)合有序數(shù)據(jù)的動態(tài)優(yōu)勢粗糙集方法；Ahmad等［10］優(yōu)化了計算基于優(yōu)勢的粗糙集近似的方法；Palangetic等［11］對基于優(yōu)勢度的粗糙集方法進行了模糊擴展。許多研究工作采用了優(yōu)勢關(guān)系粗糙集模型來處理連續(xù)值數(shù)據(jù)，但實際問題數(shù)據(jù)中，連續(xù)值屬性的取值是否具有序關(guān)系有時并不明顯，而使用優(yōu)勢關(guān)系來刻畫本身沒有序關(guān)系的連續(xù)值數(shù)據(jù)會一定程度歪曲數(shù)據(jù)本身的含義。Hu 等［12］基于鄰域關(guān)系提出了鄰域粗糙集模型，成為粗糙集框架下處理連續(xù)值數(shù)據(jù)的主要模型之一，該模型通過鄰域描述樣本的相似關(guān)系，并可通過調(diào)節(jié)鄰域半徑參數(shù)對論域形成不同?；潭鹊母采w。在Hu 等研究的基礎(chǔ)上發(fā)展出許多基于鄰域粗糙集的屬性約簡方法，如Wang 等［13］提出鄰域區(qū)分指數(shù)作為評估函數(shù)，用以代替鄰域粗糙集中的信息熵，設(shè)計了特征選擇算法；姚晟等［14］針對屬性約簡方法的單調(diào)性缺陷提出了基于鄰域粗糙互信息熵的非單調(diào)屬性約簡算法；鄭文彬等［15］設(shè)計了基于屬性重要度的變精度鄰域粗糙集屬性約簡算法；劉丹等［16］提出了不完備鄰域多粒度決策理論粗糙集與三支決策模型。雖然鄰域關(guān)系可以通過調(diào)整鄰域半徑在多粒度視角下建模，但是由于連續(xù)值數(shù)據(jù)各屬性值量綱不同導(dǎo)致半徑難以統(tǒng)一，并且半徑參數(shù)為連續(xù)值，理論上有無數(shù)種取值，整個參數(shù)?；^程計算量較大。針對參數(shù)粒化過程，吳將等［17］從連續(xù)參數(shù)區(qū)間視角下對多粒度屬性約簡進行了研究。

以上研究中，不同的二元關(guān)系下產(chǎn)生了不同種類的信息粒，如等價類、模糊等價類、優(yōu)勢類、鄰域類。在粒計算框架下，錢宇華［18］指出，聚類也是信息粒化的一種重要方式，聚類簇可形成對論域的劃分，而且類簇和鄰域本質(zhì)上都是樣本相似關(guān)系的體現(xiàn)，只是生成機制不同。在規(guī)模較大的連續(xù)值數(shù)據(jù)集上，相比要計算每個樣本的鄰域，類簇的數(shù)量一般會明顯小于鄰域的數(shù)量（即樣本的數(shù)量），可在一定程度上降低計算的耗費。目前基于聚類?；M行屬性約簡的工作尚不多見，主要困難在于難以確定基于類簇差異的辨識矩陣，此外，類簇的數(shù)目對?；潭扔兄匾挠绊憽１疚幕诰垲悂矶x約簡相關(guān)的一系列概念，進而建立一種新的約簡策略，不同于基于優(yōu)勢關(guān)系與鄰域關(guān)系的屬性約簡方法，聚類?；瘜傩约s簡方式不要求數(shù)據(jù)屬性具有序關(guān)系，且能夠在有限范圍內(nèi)離散地選取參數(shù)對論域形成粗細不同的多粒度劃分，進而對數(shù)據(jù)集進行多粒度屬性約簡。具體來說，首先，利用k均值（k-means）聚類算法［19-20］將數(shù)據(jù)集通過調(diào)節(jié)聚類參數(shù)k得到類簇，定義基于聚類的近似集和正域等概念；然后，用JS（Jensen-Shannon）散度理論［21-23］對不同類簇屬性的數(shù)據(jù)分布進行差異性度量，利用差異性結(jié)果挑選出區(qū)分兩類簇的核心屬性，由此定義了辨識矩陣［24］和屬性重要性度量；最后，在此基礎(chǔ)上設(shè)計了基于聚類粒化和簇間散度的屬性約簡算法。

1 基本概念

本章首先給出粗糙集理論［1-2］以及JS 散度［21-23］理論的一些相關(guān)概念。

1.1 基于等價關(guān)系的屬性約簡

定義1決策信息系統(tǒng)。決策信息系統(tǒng)也被稱作決策表，可由四元組表示：

其中：U={x1，x2，…，xn}是包含若干對象xi的非空有限集，稱為論域；C=A∪D是有限非空屬性集合，A與D分別是條件屬性集和決策屬性集；多決策屬性的決策信息系統(tǒng)可以轉(zhuǎn)化為單決策屬性決策信息系統(tǒng)，故本文僅以單決策屬性的決策信息系統(tǒng)作為研究對象，即D=j5i0abt0b；V是屬性集對應(yīng)的值域；f是一個信息函數(shù)，它指定U中每一個對象的屬性值，即對xi∈U，a∈A，fa(xi) ∈Va，Va為屬性a的值域。

定義2等價關(guān)系。定義S為決策信息系統(tǒng)，若條件屬性子集Q?A，滿足

稱RQ為決策信息系統(tǒng)S定義在屬性集Q上的等價關(guān)系?；谝陨隙x，記

為xi基于屬性Q的等價類；稱U/Q={[xi]Q|xi∈U}為論域U基于等價關(guān)系RQ的劃分。

定義3上下近似集。對于任意目標概念X?U，定義X關(guān)于等價關(guān)系RQ的上近似和下近似為：

上下近似集分別代表確定屬于和可能屬于X的對象集合。

定義4相對正域。決策信息系統(tǒng)中，條件屬性集A關(guān)于決策屬性集D的正域定義為：

若基于條件屬性集A所有等價類的對象均屬于同一個決策類，意味著所有樣本均屬于正域，此時稱該決策信息系統(tǒng)為一致的，否則稱該決策信息系統(tǒng)為不一致的。

定義5正域約簡。給定S為一個決策信息系統(tǒng)，對于?Q?A，若Q滿足以下兩個條件，則稱Q為A的正域約簡：

1）POSQ(D)=POSA(D)。

2）?a∈Q，(D) ≠POSA(D)。

定義6不一致決策信息系統(tǒng)及其可辨識矩陣。給定不一致決策信息系統(tǒng)S，U={x1，x2，…，xn}，D=j5i0abt0b，其可辨識矩陣定義為n×n的矩陣，記作M，矩陣元素mij定義為：

其中：w(xi，xj)={(xi，xj)|xi∈POSA(D) ∨xj∈POSA(D)}為正域約束集。

命題1 給定決策信息系統(tǒng)S，M是其可辨識矩陣，屬性子集Q?A是該決策信息系統(tǒng)的正域約簡當且僅當Q滿足：

1）對任意非空元素m∈M，有m∩Q≠?；

2）對?a∈Q，?m∈M使得m∩Q-{a}=?。

由以上概念可以了解到，對于給定的決策信息系統(tǒng)，正域約簡所保留的屬性是能夠維持正域不變的屬性子集，可以在保留樣本區(qū)分性的前提下最大限度地約簡掉冗余屬性。但這種約簡建立在等價關(guān)系上，只能處理符號值數(shù)據(jù)。在連續(xù)值屬性上，用基于相似性得到的若干類簇對論域形成劃分后，如何衡量屬性對不同樣本的區(qū)分度是進行屬性約簡的關(guān)鍵問題。本文引入散度概念，提出利用散度理論定義不同類簇數(shù)據(jù)分布之間的差異性。

1.2 JS散度

JS 散度由KL（Kullback-Leibler）散度理論［25］衍生而來，KL 散度又被稱作相對熵或信息散度，是由Kullback 等［25］提出用來衡量兩個概率分布間差異的非對稱性度量，信息論中相對熵等價于兩個概率分布信息熵的差。相對熵常被應(yīng)用于優(yōu)化算法，通常表示使用理論分布擬合真實分布時產(chǎn)生的信息損耗。

定義7KL 散度。設(shè)P(x)、Q(x)分別是隨機變量x數(shù)據(jù)的真實概率分布和理論概率分布，KL 散度定義為：

離散值隨機變量：

連續(xù)值隨機變量：

有時會將KL 散度稱為KL 距離，但KL 散度并不滿足距離的性質(zhì)，其有兩個特性：

1）KL 散度的非對稱性：KL(A，B) ≠KL(B，A)；

2）不滿足三角不等式。

為解決KL 散度的非對稱問題，有學(xué)者提出了JS 散度概念，JS 散度是基于KL 散度的變體，度量了兩個概率分布的相似度，解決了KL 散度非對稱問題，更適用于衡量兩個數(shù)據(jù)分布的差異性。一般情況下JS 散度是對稱的，其取值在0～1，定義如下：

定義8JS 散度。P(x)，Q(x)分別是隨機變量x的真實概率分布和理論概率分布，則JS 散度定義為：

利用JS 散度衡量不同類簇間各屬性上的數(shù)據(jù)分布差異，以此差異定義可辨識矩陣，矩陣中元素為導(dǎo)致兩樣本分屬不同類簇的主要差異屬性。特殊情形下，當兩類簇數(shù)據(jù)完全沒有交疊時，會導(dǎo)致JS 散度成為常數(shù)。實際數(shù)據(jù)中多維樣本聚類后，生成類簇在所有屬性上毫無交疊情況較少，當所有類簇數(shù)據(jù)都無交疊時可以考慮使用Wasserstein 散度［26］方法來度量兩不同類簇數(shù)據(jù)的差異性。

2 基于聚類?；c簇間散度屬性約簡算法

本章中提出一種基于聚類粒化和簇間散度的屬性約簡算 法（Attribute Reduction algorithm based on Cluster granulation and Divergence among clusters，ARCD）。考慮分類問題的數(shù)據(jù)集，將其類別標簽看作決策屬性，條件屬性均為連續(xù)值，則此連續(xù)值數(shù)據(jù)集可被看作一個決策信息系統(tǒng)。

針對連續(xù)值數(shù)據(jù)集決策信息系統(tǒng)，首先利用k-means 聚類算法將其聚類。聚類本質(zhì)上是將相似的樣本聚成集合，若類簇內(nèi)的對象均屬于同一個決策類，意味著相似的樣本決策相同，則稱該決策信息系統(tǒng)為一致的，否則稱該決策信息系統(tǒng)為不一致的。然后基于傳統(tǒng)粗糙集理論用聚類得到的相似類替代等價類。在此基礎(chǔ)上定義基于聚類的上下近似、相對正域以及正域約簡概念。因為基于相似性且通過調(diào)整聚類參數(shù)k能對數(shù)據(jù)集形成不同?；潭鹊膭澐纸Y(jié)果，所以該算法不要求屬性具有序關(guān)系，并且能在較小范圍內(nèi)選擇離散的參數(shù)值k對連續(xù)值數(shù)據(jù)集進行多粒度屬性約簡。基于該思想定義以下相關(guān)概念。

2.1 相關(guān)概念

給定決策信息系統(tǒng)S，條件屬性子集Q?A。將由Q組成的數(shù)據(jù)子集經(jīng)k-means 算法聚類后生成的k個類簇記為LQ={C1，C2，…，Ck}，其中Ci為k-means 聚類形成的第i個類簇。以下給出基于聚類的屬性約簡定義。

定義9基于聚類的近似集。給定決策信息系統(tǒng)S，屬性子集Q?A，聚類后形成類簇集為LQ，給定目標概念X?U，定義X關(guān)于LQ的上下近似分別為：其中Cx即包含對象x的類簇。

定義10基于聚類的相對正域。在決策信息系統(tǒng)S中，給定目標概念X?U，條件屬性集A聚類得到的類簇集為LA。基于聚類，條件屬性集A關(guān)于決策屬性集D的正域為：

定義11基于聚類的正域約簡。給定決策信息系統(tǒng)S，對于?Q?A，若Q滿足以下兩個條件，則稱Q為A的正域約簡：

將類簇類比為傳統(tǒng)粗糙集中的等價類，基于可辨識矩陣中元素存儲的是不同決策類樣本的區(qū)分屬性（屬性值不相等），將基于聚類的非一致決策信息系統(tǒng)可辨識矩陣元素定義為：導(dǎo)致兩不同決策類樣本分屬不同類簇的主要差異屬性集。由此上述約簡也可方便地由以下定義求得。

定義12簇間屬性上的JS 散度。給定決策信息系統(tǒng)S，論域U聚類后形成類簇集LA。令C(a)表示類簇C中所有樣本在屬性a上的取值，令P(Ci(a))、Q(Cj(a))表示任意類簇Ci、Cj中樣本在屬性a上取值的數(shù)據(jù)分布。簇間屬性上的JS散度定義為：

定義13簇間屬性平均JS 散度。根據(jù)式（1），給定數(shù)據(jù)集中條件屬性集為A={a1，a2，…，al}，A中共有l(wèi)個屬性，Ci、Cj簇間屬性平均JS 散度定義為：

定義14簇間主要差異屬性。根據(jù)式（2），設(shè)JS 散度差異性閾值為γ，不同類簇Ci、Cj的主要差異屬性集定義為：

定義15基于聚類的非一致決策信息系統(tǒng)可辨識矩陣。根據(jù)式（3），給定非一致決策信息系統(tǒng)S，U={x1，x2，…，xn}，D=j5i0abt0b，論域U聚類后形成類簇集為LA。設(shè)樣本xi、xj分屬不同類簇Ck1、Ck2，JS 散度差異性閾值為γ，定義一個n×n的矩陣，記作M，第i行第j列矩陣元素mij定義為：

定義16基于聚類的變精度正域約簡。給定決策信息系統(tǒng)S，論域U聚類后形成類簇集LQ，對于Q?A和變精度約簡參數(shù)β∈[0，1]，若POS(D)=POS(D)且任何Q的真子集均不滿足此式。其中：

此時稱Q為A的β-正域約簡，變精度的引入使得模型對數(shù)據(jù)的不一致性具有一定程度的容忍性，增強了模型的容噪能力，(1 -β)即為可容忍誤分率。β越接近于1，所得到的約簡越接近嚴格正域約簡。特別地，當β=1 時即為定義11 基于聚類的正域約簡。

定義17基于聚類和信息增益的屬性重要度。給定決策信息系統(tǒng)S，U={x1，x2，…，xn}，D=j5i0abt0b，決策屬性集D等價劃分后類別數(shù)定義為|D|，假定論域U中依決策屬性第n類樣本所占比例為pn(n=1，2，…，|D|)，信息熵Ent(U) 定義如下：

一般而言，“信息增益”越大，意味著使用屬性a來進行劃分所獲得到的“純度提升”越大。

2.2 算法步驟

基于傳統(tǒng)粗糙集理論和以上概念，可以建立基于聚類粒化和簇間散度的屬性約簡算法，具體步驟說明如下。

算法1 基于聚類?；痛亻g散度的屬性約簡算法。

輸 入S=(U，C=A∪D，V，f)；聚類數(shù)目k；變精度參數(shù)β。

輸出 屬性約簡REDUCT。

步驟2）中使用k-means++聚類將數(shù)據(jù)聚類。這是由于k-means 算法在選擇初始聚類中心存在不足，而k-means++算法能夠選擇盡可能分散的初始聚類中心點。由于采用可辨識矩陣來確定兩樣本分屬不同類簇的差異屬性，對于數(shù)據(jù)集U當聚類參數(shù)為k時算法時間復(fù)雜度為O(k2|U|2)。

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

為檢驗此約簡算法的有效性，從UCI 數(shù)據(jù)庫［27］與Kent Ridge 數(shù)據(jù)庫［28］中選取了14 個連續(xù)值數(shù)據(jù)集進行實驗，表1列出了數(shù)據(jù)集的詳細信息，其中條件屬性個數(shù)最多達7 129，樣例數(shù)最多為10 000。

表1 實驗數(shù)據(jù)集Tab.1 Experimental datasets

表1 實驗數(shù)據(jù)均為連續(xù)值數(shù)據(jù)集，為消除各屬性量綱對約簡結(jié)果的影響，在實驗之前對數(shù)據(jù)集進行了歸一化處理。由第2 章中定義，得到實驗數(shù)據(jù)集基于本文算法ARCD 的屬性約簡集，并與基于優(yōu)勢關(guān)系與鄰域關(guān)系的屬性約簡算法結(jié)果進行對比。選取的4 種代表性對比算法為：1）基于優(yōu)勢關(guān)系的多準則決策分析粗糙集（Dominance-based Rough Sets theory for multicriteria decision analysis，DRS）算法［8］；2）基于鄰域粗糙集的特征選擇（Neighborhood Rough Set based heterogeneous feature subset selection，NRS）算法［12］；3）基于鄰域粗糙互信息熵的非單調(diào)屬性約簡（non-monotonic attribute reduction based on Neighborhood Rough Mutual Information Entropy，NRMIE）算法［14］；4）基于鄰域區(qū)分指數(shù)的特征選擇（Heuristic Algorithm based on Neighborhood Discrimination Index，HANDI）算法［13］。

實驗過程中所有算法均通過python3.7 編程實現(xiàn)，實驗運行的硬件環(huán)境為Intel Core i7-9750H CPU 和32 GB RAM。本實驗共分為5 部分：第1 部分為上述5 種算法的約簡結(jié)果比較；第2 部分對比了5 種算法所得最佳特征子集的約簡率；第3 部分比較分析了5 種算法所得約簡結(jié)果的分類精度；第4 部分比較了各算法計算約簡結(jié)果的時間；最后將ARCD 中聚類參數(shù)k與散度閾值γ對約簡結(jié)果的影響進行了分析與探討。

3.1 約簡結(jié)果比較

實驗設(shè)置：NRS、NRMIE 和HANDI 三種算法都涉及鄰域半徑參數(shù)的選取，本文ARCD ?；瘏?shù)k為離散整數(shù)值。為權(quán)衡參數(shù)優(yōu)化和計算量，體現(xiàn)ARCD 在較低代價下選取參數(shù)的高效性，實驗中定義鄰域半徑δ=Δmin+h(Δmax-Δmin)，其中h∈[0，1]，Δmin表示數(shù)據(jù)集所有對象之間距離的最小值，Δmax表示數(shù)據(jù)集所有對象間的距離最大值；h初始值定義為0.01，其余取值以0.05 的整數(shù)倍變化。對于本文算法ARCD，聚類參數(shù)k∈[2，20]以步長為1 進行變化。通過調(diào)節(jié)?；瘏?shù)對數(shù)據(jù)集進行實驗，得到了各參數(shù)對應(yīng)的屬性約簡結(jié)果。每種算法統(tǒng)一以在4 種分類器上分類精度都較高時的約簡集作為最佳約簡結(jié)果。

表2、3 分別展示了ARCD 和其他4 種對比算法的最終約簡結(jié)果，約簡集中的序號表示相應(yīng)數(shù)據(jù)集中屬性所對應(yīng)的標號。表2 中最后一列表示最佳約簡結(jié)果的聚類參數(shù)k。

表2 ARCD屬性約簡結(jié)果Tab.2 ARCD attribute reduction results

對比表2、3 看出，ARCD 在iris 與banknote 數(shù)據(jù)集上約簡結(jié)果與NRS 算法約簡結(jié)果相同，在banknote、electrical 數(shù)據(jù)集上與HANDI 算法約簡結(jié)果相同。當條件屬性較少時ARCD在個別數(shù)據(jù)集上所選擇的特征實際上是DRS 或NRS 算法約簡結(jié)果的子集，例如glass 與electrical 數(shù)據(jù)集。這說明在某些低維數(shù)據(jù)集上相較于DRS 與NRS 算法，ARCD 有能力去除更多的冗余特征。另外可以發(fā)現(xiàn)在其他低維數(shù)據(jù)集上ARCD所選特征大多為DRS、NRS、NRMIE、HANDI 算法約簡結(jié)果子集的并集。例如wine、breast、wireless、wine quality 數(shù)據(jù)集。原因可能在于ARCD 基于聚類?；绞?，通過k調(diào)節(jié)粒度粗細對數(shù)據(jù)集進行劃分，具有獲得更多特征組合的可能性。隨著條件屬性增多ARCD 約簡結(jié)果的規(guī)模也在逐漸增大。特別地，在數(shù)據(jù)集DLBCL 上，由于該數(shù)據(jù)集屬性維度為7 129，可能存在較多數(shù)量的約簡集可以選擇，因此ARCD 與其他算法的約簡結(jié)果中沒有出現(xiàn)共同屬性。除DLBCL 數(shù)據(jù)集外在iono、sonar、libras 數(shù)據(jù)集上與其他4 種算法對比，雖然獲得的約簡集不同，但約簡結(jié)果中始終存在著共同特征。所選特征子集之間的差異性表明：對于給定的分類任務(wù)，有多種特征組合具有可接受的分類能力。

3.2 約簡率比較

本節(jié)中比較了ARCD 與對比算法的約簡率，計算公式為：約簡率=[(|A| -|REDUCT|)/|A|]× 100%。約簡率越高表示去除冗余屬性的能力越好，約簡后需要的存儲空間也越小。各個數(shù)據(jù)集在5 種算法中的最優(yōu)約簡率以黑體標注。從表4 所列出的結(jié)果可以看出，在14 個數(shù)據(jù)集上ARCD 的平均約簡率明顯高于其他4 種對比算法，達到了67.70%；其次是NRS，為60.02%。從約簡集中平均屬性個數(shù)上看，ARCD略高于NRS（相差0.72），基本持平，但明顯少于DRS、NRMIE、HANDI 所得約簡集中屬性的數(shù)目。具體到每個數(shù)據(jù)，ARCD 在7 個數(shù)據(jù)集上獲得了最高的約簡率，其次是NRS和HANDI 分別在5 個數(shù)據(jù)集上有最高約簡率。顯示出所提出的ARCD 有較強的屬性約簡能力。

表3 各算法的屬性約簡結(jié)果對比Tab.3 Attribute reduction results comparision of different algorithms

表4 各算法約簡結(jié)果的屬性個數(shù)與約簡率對比Tab.4 Comparison of attribute number and reduction rate of reduction results by different algorithms

3.3 分類精度對比

本節(jié)比較了5 種算法在各數(shù)據(jù)集上約簡結(jié)果的分類精度，即對約簡后的數(shù)據(jù)集進行分類，分類精度可以用來體現(xiàn)約簡效果。實驗中采用了4 種常見分類器分別為：決策樹（Decision Tree）、K近鄰（K-Nearest Neighbors，KNN）、支持向量 機（Support Vector Machine，SVM）、神經(jīng)網(wǎng)絡(luò)（Neural Network），其中神經(jīng)網(wǎng)絡(luò)分類器為多層感知機。以上分類器均通過交叉驗證的網(wǎng)格搜索方式擬合參數(shù)。各數(shù)據(jù)集獲得最終特征子集后用上述4 種分類器通過設(shè)置訓(xùn)練數(shù)據(jù)與測試數(shù)據(jù)進行10 次十折交叉驗證計算得到分類精度，如表5～8所示。每個表記錄了各約簡算法所得最佳特征子集使用同一種分類器計算出的分類精度結(jié)果，最后一行是平均值，其中“原始屬性”指沒有經(jīng)過屬性約簡的原始數(shù)據(jù)集。在每個表中，分類精度都以“均值±標準差”的形式表示；各數(shù)據(jù)集在不同約簡算法上獲得的最優(yōu)分類精度用黑體標注；表頭各算法名稱后面括號中的數(shù)字表示該算法在幾個數(shù)據(jù)集上得到最佳分類精度，如使用KNN 分類器時，ARCD 在9 個數(shù)據(jù)集上取得了最好的精度。

表5 基于KNN的約簡分類精度比較 單位：%Tab.5 Comparison of classification accuracy of KNN based attribute reduction unit：%

從表5～8 可以看出，在4 種分類器的結(jié)果中都顯示ARCD 在14 個數(shù)據(jù)集上的平均精度均優(yōu)于其他對比約簡算法。而且，從取得最優(yōu)精度的數(shù)據(jù)集個數(shù)上看，ARCD 是最多的，除了在Decision Tree 分類器結(jié)果中有7 個數(shù)據(jù)集外，其余3 種分類算法上都是在9 個數(shù)據(jù)集上取得最優(yōu)分類精度?？梢?，在多數(shù)連續(xù)值數(shù)據(jù)集上利用ARCD 能夠保持甚至提高分類精度的前提下去除冗余屬性，具有較好的約簡效果。更詳細地，具體到每個數(shù)據(jù)集來看，相比其他4 種對比約簡算法，ARCD 在數(shù)據(jù)集banknote 和electrical 上所選特征子集在4種不同分類算法上均取得了最高分類精度；在iris、wine、glass、forest、sonar、DLBCL 這6 個數(shù)據(jù)集上所得特征子集在3種分類器上取得最高分類精度?？梢姰敂?shù)據(jù)集樣本數(shù)較多（如electrical 數(shù)據(jù)）和維數(shù)較高（如DLBCL 數(shù)據(jù)）時，ARCD 仍可以取得較好的約簡效果。

表6 基于Decision Tree的約簡分類精度比較 單位：%Tab.6 Comparison of classification accuracy of Decision Tree based attribute reduction unit：%

表7 基于SVM的約簡分類精度比較 單位：%Tab.7 Comparison of classification accuracy of SVM based attribute reduction unit：%

在平均精度和獲得最優(yōu)精度次數(shù)方面，表現(xiàn)次優(yōu)的是NRS 和HANDI。當然，不同分類器也會影響具體的分類結(jié)果。在KNN、Decision Tree、Neural Network 分類器上，ARCD平均分類精度比NRS、HANDI 略高，最高提升了約2.0 個百分點；但在SVM 分類器上明顯優(yōu)于其他約簡算法，精度比NRS 提升了約2.6 個百分點，比HANDI 提升了約5.3 個百分點。基于優(yōu)勢關(guān)系的DRS 約簡算法表現(xiàn)排在NRS 和HANDI之后，分析其原因可能在于大部分連續(xù)值的條件屬性相較于決策屬性并不具有優(yōu)勢關(guān)系，即不一定有“某個條件屬性值越大/小，則決策屬性越大/小”這樣的單調(diào)關(guān)系，這時如果基于優(yōu)勢關(guān)系去進行屬性約簡會引入不必要的序信息。而聚類算法本質(zhì)上是基于相似性將特征空間中相似的對象歸類，同一決策類中的樣例大多具有較高的相似度，這對于大多數(shù)分類問題是合理的假設(shè)。另一方面，通過類簇數(shù)目k可以調(diào)節(jié)對論域劃分的粗細，形成多個粒度空間，可以選擇在合適的粒度下進行屬性約簡；而且，整數(shù)k的離散化擇優(yōu)相比連續(xù)值的鄰域半徑擇優(yōu)更加簡單易行。通過對比可以發(fā)現(xiàn)NRMIE 算法表現(xiàn)不佳，可能因為該算法對參數(shù)取值較為敏感，在低代價下選擇部分離散參數(shù)沒有得到較好約簡結(jié)果。

以上結(jié)果說明基于聚類粒化和簇間散度的屬性約簡算法能夠直接處理不具有序關(guān)系的連續(xù)值數(shù)據(jù)集，用較低代價離散地調(diào)節(jié)參數(shù)便能在保持甚至提高分類精度的前提下去除數(shù)據(jù)集中的冗余特征，具有比較理想的效果。

3.4 運行時間比較

本節(jié)中將ARCD 與另外4 種對比算法運行時間進行了比較。最終運行時間結(jié)果由多次計算約簡用時的平均值表示。由于在14 個數(shù)據(jù)集中更關(guān)注算法在規(guī)模與維度較高的數(shù)據(jù)集上的運行效率，因此從中選取了6 個數(shù)據(jù)集進行實驗對比，結(jié)果用柱狀圖展示。因時間差異將其分為兩組展示，其中圖1 為libras、wireless、QSAR 數(shù)據(jù)集上的實驗結(jié)果；圖2 為wine quality、DLBCL、electrical 數(shù)據(jù)集上的實驗結(jié)果；圖3 為各算法在所選數(shù)據(jù)集上的平均運行時間對比。

圖1 不同算法在libras、wireless、QSAR數(shù)據(jù)集上的運行時間對比Fig.1 Running time comparison of different algorithms on libras，wireless，QSAR datasets

圖2 不同算法在wine quality、DLBCL、electrical數(shù)據(jù)集上的運行時間對比Fig.2 Running time comparison of different algorithms on wine quality，DLBCL，electrical datasets

圖3 不同算法的平均運行時間對比Fig.3 Average running time comparison of different algorithms

表8 基于Neural Network的約簡分類精度比較 單位：%Tab.8 Comparison of classification accuracy of Neural Network based attribute reduction unit：%

由圖1、2 可以看出，基于優(yōu)勢關(guān)系粗糙集的約簡算法隨樣本規(guī)模增大其運行時間也越來越長，在wine quality 和electrical 兩個數(shù)據(jù)集上尤其明顯。這是由于基于優(yōu)勢關(guān)系粗糙集不僅要遍歷樣本比較各屬性上的取值并排序，計算樣本所屬優(yōu)勢類，還要計算優(yōu)勢關(guān)系下的可辨識矩陣。ARCD的運行時間與NRS、NRMIE、HANDI 在wireless、wine quality數(shù)據(jù)集上的運行時間基本持平；ARCD 與NRS、HANDI 運行時間在electrical 數(shù)據(jù)集上相近。這是由于在決策信息系統(tǒng)S中，NRS、NRMIE 與HANDI 算法時間復(fù)雜度為O(|A|2|U|2)，聚類參數(shù)為k時ARCD 時間復(fù)雜度為O(k2|U|2)。當數(shù)據(jù)集屬性數(shù)量較小時ARCD 運行時間與NRS、NRMIE、HANDI 算法差距不大，隨著數(shù)據(jù)集屬性數(shù)增多，ARCD 的運行時間相較于其中某些算法會更具優(yōu)勢。如ARCD 在QSAR 數(shù)據(jù)上遠遠低于NRS 和HANDI 所需時間；在libras 上與NRS、NRMIE相近但運行速度明顯快于HANDI；在DLBCL 上所需時間與NRS 和HANDI 相近，但明顯低于NRMIE，由圖3 各算法平均運行時間對比結(jié)果可以看出ARCD 更具優(yōu)勢，相較于NRS 和HANDI 分別縮減了25.4%與32.3%?？梢园l(fā)現(xiàn)即使同為基于鄰域關(guān)系的屬性約簡算法，在同一數(shù)據(jù)集上的約簡時間也不盡相同，主要是由于各算法評估函數(shù)不同，基于熵與正域等方式獲得不同長度的特征子集都會影響計算約簡的時間。

3.5 聚類參數(shù)k的探究與分析

根據(jù)定義可知聚類參數(shù)k對本文算法有重要的影響，調(diào)節(jié)參數(shù)k能對論域形成不同?；潭鹊膭澐郑时竟?jié)將參數(shù)k與約簡集的大小和分類精度之間的關(guān)系進行了探究與分析。參數(shù)k∈[2，20]，并以步長為1 進行變化，調(diào)節(jié)k值得到多種粒度劃分下的約簡結(jié)果，在4 種分類器上對約簡后的數(shù)據(jù)集分別計算分類精度。圖4～9 所示的是部分數(shù)據(jù)集隨k值變化所得的約簡集大?。ㄓ肧ize 表示）和各分類器上的分類精度變化曲線。各數(shù)據(jù)集的最佳約簡結(jié)果（4 種分類器計算精度都高）用紅色虛線框標注。圖10 為不同數(shù)據(jù)集上各k值對應(yīng)所得約簡集平均大小與各分類器平均分類精度變化曲線。

圖4 k對結(jié)果的影響（wine數(shù)據(jù)集）Fig.4 Influence of k on results（wine dataset）

圖5 k對結(jié)果的影響（forest數(shù)據(jù)集）Fig.5 Influence of k on results（forest dataset）

圖6 k對結(jié)果的影響（QSAR數(shù)據(jù)集）Fig.6 Influence of k on results（QSAR dataset）

圖7 k對結(jié)果的影響（wireless數(shù)據(jù)集）Fig.7 Influence of k on results（wireless dataset）

根據(jù)圖4～10 數(shù)據(jù)集的實驗結(jié)果可以看出：聚類參數(shù)k的取值從2～20 逐漸增大的過程中，約簡集的大小總體上呈逐漸增大的趨勢，這是由于聚類簇越多，對數(shù)據(jù)集的劃分越細致，樣本有更大可能被分到不同類簇中，從而導(dǎo)致最終結(jié)果可以吸收到更多的屬性。綜合圖4～9 數(shù)據(jù)集的實驗結(jié)果可以注意到在k∈[2，20]范圍內(nèi)，在不同數(shù)據(jù)集上運行ARCD都可以計算得出一個約簡集小并且在多個分類器上分類精度較高的約簡結(jié)果。另外，通過圖10 可以看出KNN、Decision Tree 與Neural Network 分類器的分類精度結(jié)果隨k值增大一開始逐漸上升隨后變得穩(wěn)定，而SVM 分類器所得分類精度隨k值增大而升高后在小范圍區(qū)間內(nèi)波動。在k為10之前各分類器已經(jīng)能夠獲得較高的分類精度，且分類精度不會隨著k值增大而出現(xiàn)較大的增幅。這是因為在k值較小時ARCD 所計算的約簡屬性便具有較好的分類能力，隨著聚類簇的增多，算法所計算的簇間區(qū)分屬性逐漸飽和，分類精度不會出現(xiàn)明顯提升。對于ARCD，在樣本規(guī)模10 000 以內(nèi)的數(shù)據(jù)集上，如果注重運行時間效率與約簡率時可以將k值選定在[2，10]的范圍內(nèi)，可以有效降低調(diào)參的代價的同時獲得可接受的分類效果；如果更關(guān)注分類精度結(jié)果則可以適當擴大范圍來選擇k值，通過調(diào)整參數(shù)k取得較優(yōu)分類性能。

圖8 k對結(jié)果的影響（electrical數(shù)據(jù)集）Fig.8 Influence of k on results（electrical dataset）

圖9 k對結(jié)果的影響（libras數(shù)據(jù)集）Fig.9 Influence of k on results（libras dataset）

圖10 平均分類精度、平均約簡集大小隨k值的變化Fig.10 Average classification accuracy and reduction set size varying with k value

3.6 閾值參數(shù)γ的探究與分析

除?；瘏?shù)k外，散度閾值參數(shù)γ的取值會決定一個屬性是否具有足夠的辨識能力，因此也是一個重要的參數(shù)。類似于3.5 節(jié)，本節(jié)選取了部分數(shù)據(jù)集，詳細分析了不同參數(shù)值γ對約簡集的大小和分類精度的影響?？紤]到γ=1 所代表的含義是選擇大于平均簇間散度的屬性，故將γ設(shè)置在1左右范圍內(nèi)進行調(diào)整，觀察對約簡結(jié)果的影響。定義參數(shù)γ∈[0.8，1.4]，以步長為0.05 進行變化，將k固定為各數(shù)據(jù)集對應(yīng)的最佳值，對部分數(shù)據(jù)集繪制了隨γ值變化所得的約簡集大小和各分類器上的分類精度變化曲線，如圖11～14。

圖11 γ對結(jié)果的影響（wine數(shù)據(jù)集）Fig.11 Influence of γ on wine dataset

圖12 γ對結(jié)果的影響（iono數(shù)據(jù)集）Fig.12 Influence of γ on iono dataset

圖13 γ對結(jié)果的影響（sonar數(shù)據(jù)集）Fig.13 Influence of γ on sonar dataset

從圖11～14 可以看出，隨著γ取值的變化，KNN 與Decision Tree 分類器分類精度都處在高位且較為穩(wěn)定，而SVM 與Neural Network 分類器對γ較為敏感，其分類精度會隨γ值的變化在一定范圍內(nèi)波動。另外，不同于鄰域粗糙集中屬性重要度參數(shù)，γ值不直接決定約簡集的大小，因為γ值僅決定獲得兩簇差異屬性的比例，而這些差異屬性是否普遍存在于任意兩簇間才是影響最終約簡結(jié)果的關(guān)鍵因素?？梢宰⒁獾疆敠弥等〉絒1.1，1.3]區(qū)間內(nèi)時會得到較為理想的約簡結(jié)果，數(shù)據(jù)集約簡后在4 種分類器上可達到較高精度且約簡中屬性個數(shù)可取到相對較低點，當然分類精度和約簡率之間一般需要進行權(quán)衡。

圖14 γ對結(jié)果的影響（libras數(shù)據(jù)集）Fig.14 Influence of γon libras dataset

4 結(jié)語

在粗糙集框架下，基于聚類?；绞綄⒕垲愃惴ㄉ傻念惔乜醋骰谙嗨脐P(guān)系的信息粒，用聚類類簇代替等價類定義了基于聚類的近似集、相對正域、正域約簡、可辨識矩陣等概念，利用散度理論定義了不同類簇的主要差異屬性等概念。由主要差異屬性構(gòu)造出可辨識矩陣，為處理連續(xù)值數(shù)據(jù)提出了一種基于聚類的屬性約簡算法，可通過調(diào)節(jié)?；瘏?shù)k在有限范圍內(nèi)離散地選取參數(shù)對論域形成多粒度劃分，進而對數(shù)據(jù)集進行多粒度屬性約簡。本文算法ARCD 不要求連續(xù)值數(shù)據(jù)集屬性具有序關(guān)系，同在較低代價下選取?；瘏?shù)時，相較于基于鄰域關(guān)系的屬性約簡算法，ARCD 約簡率與運行時間均具有優(yōu)勢，且所選特征子集在各分類器上平均分類精度都更高。在UCI 和Kent Ridge 數(shù)據(jù)庫的14 個數(shù)據(jù)集上與基于優(yōu)勢關(guān)系和鄰域關(guān)系的4 種代表性屬性約簡算法進行了實驗對比，實驗結(jié)果驗證了本文算法的可行性與有效性，在多數(shù)數(shù)據(jù)集上的分類結(jié)果表明本文算法可以在維持原始分類能力的前提下，去除冗余屬性，擁有較好的約簡效果，將會對后續(xù)生成高質(zhì)量的決策規(guī)則以及降低存儲和算法運行時間耗費起到重要的作用。但注意到不同于等價類、優(yōu)勢類或鄰域類，當屬性由少增多時，類簇不能自然地由粗變細，而是通過控制k來生成不同大小的類簇。因為冗余屬性的存在，可能會導(dǎo)致利用所有原始屬性進行聚類不能完全反映對象之間的相似性，未來的工作將會考慮用更多聚類方法如（基于密度的聚類）研究不同屬性子集上條件屬性與決策之間的依賴度變化，從而進一步改善屬性約簡的效果。