基于類間區(qū)分度的屬性約簡方法*

饒 亞，賈修一,,+，李同軍，商 琳

1.南京理工大學 計算機科學與工程學院，南京 210094

2.浙江海洋大學 浙江省海洋大數(shù)據(jù)挖掘與應用重點實驗室，浙江 舟山 316022

3.南京大學 計算機軟件新技術國家重點實驗室，南京 210093

1 引言

粗糙集理論[1-2]是一種有效地處理模糊及不確定知識的數(shù)學工具，在數(shù)據(jù)挖掘、知識發(fā)現(xiàn)等方面均有著重要作用。屬性約簡是粗糙集模型中一個關鍵性問題，所謂屬性約簡，就是尋找滿足某種特定標準的屬性最小子集的過程[3-4]。利用屬性約簡，能夠有效地消除無關和冗余信息，減少屬性數(shù)目，提高數(shù)據(jù)挖掘任務的效率，簡化分析數(shù)據(jù)并提取數(shù)據(jù)中的關鍵信息[5-6]。

近年來，粗糙集理論模型中的屬性約簡問題引發(fā)了學者們廣泛的關注與研究。許多學者提出了基于熵（包括信息熵[7]、互信息[8]、條件熵[9]等）、一致性[10-11]以及決策域[12-13]（包括正域、負域、邊界域）等的屬性約簡定義。然而，這些屬性約簡定義大部分都是基于不可分辨或可分辨關系[14]所提出的，通過對具有等價關系的類簇對象的計算，來判定當前約簡子集的表現(xiàn)性能的好壞，卻忽略了不具有等價關系的不同類簇對象間關系的變化情況，而這些被忽略的類簇對象間的關系同樣是影響約簡子集表現(xiàn)性能的關鍵性因素之一。

針對該問題，本文提出了一種類間區(qū)分度的概念，用于衡量不同類簇對象間的區(qū)分關系，在其值的計算過程中需要考慮不同類簇對象間的關系及分布情況。相較于等價類和上下近似集而言，類間區(qū)分度考慮到了上述所忽略的不存在不可分辨關系的各類簇對象的區(qū)分關系情況，且其值的變化能夠反映隨著屬性集的變化不同類簇間區(qū)分情況的變化。

本文基于類間區(qū)分度，定義了一種屬性約簡，并提出了相應的屬性約簡算法。在該方法中，將類間區(qū)分度的概念引入到屬性約簡中，在約簡過程中充分考慮到該區(qū)分度值的變化情況，并給出類間重合度和類間區(qū)分度的概念以求解當前對象集各類簇間可分性大小。之后，基于所提出的屬性約簡定義并結(jié)合啟發(fā)式搜索策略[15]提出了一種保持類間區(qū)分度值不變的屬性約簡方法，并通過一系列實驗驗證了所提約簡方法的有效性。

2 類間區(qū)分度

本章將對類間區(qū)分度的相關概念進行介紹。

2.1 決策信息系統(tǒng)

粗糙集理論模型主要針對決策信息系統(tǒng)進行研究，一個決策信息系統(tǒng)可以定義為一個四元組DS=(U,A=C?D,V={Va|a∈A},f={fa|a∈A})且C?D=?。其中，U表示一個有限非空對象集，A是一個有限非空屬性集，C是條件屬性集，D是決策屬性集。V是非空值集且Va表示屬性a的取值范圍。f是一個信息函數(shù)，fa(x)表示對象x在屬性a上的取值。且該決策信息系統(tǒng)可以簡寫為DS=(U,C?D)。對于給定的決策信息系統(tǒng)，對象集U能由決策屬性集D劃分為多個類簇，其表示為：U D={D1,D2,…,DM}(M＞0)，其中Di(1≤i≤M)表示對象集U的第i個類簇。此外，設條件屬性子集R?C。

2.2 重合度

類間重合度是評價對象集U由決策屬性集D劃分的多個類簇中任意兩類簇間對象重合程度的指標。

定義1（類間重合度）在決策信息系統(tǒng)DS=(U,C?D)中，對于由決策屬性集D劃分的任意兩個類簇Di和Dj，設兩類簇在屬性子集R?C下的類間重合度值為InterCR(Di,Dj)，則其計算如下：

其中，Dik表示類簇Di的第k個對象，表示集合的基（即集合中元素的數(shù)目）。IR(x,Di)是與對象x和類簇Di有關的指示函數(shù)，定義如下：

其中，fR(x)={ }fa(x)|a∈R是決策信息系統(tǒng)中與對象x有關的信息函數(shù)。

例1如表1，DS=(U,C?D)是一個決策信息系統(tǒng)，U={o1,o2,…,o9},C={c1,c2,…,c5}且U D={D1,D2,D3}，其中D1={o1,o2},D2={o3,o4,o5},D3={o6,o7,o8,o9}。根據(jù)定義1，對于類簇D1、D2和D3，存在重合度值計算如下：InterCC(D1,D2)=0，InterCC(D1,D3)=1/3，即在條件屬性集C下，類簇D1與D3的類間重合度大于類簇D1與D2的重合度。

Table 1 Decision information table表1 一個決策信息表

2.3 區(qū)分度

與類間重合度相反，類間區(qū)分度是衡量對象集由決策屬性集劃分的多個類簇中任意兩類簇間能被有效區(qū)分的程度值，也是兩類簇間對象不重合的程度指標。在本節(jié)中，將對類間區(qū)分度的相關概念進行介紹。

定義2（類間區(qū)分度）在決策信息系統(tǒng)DS=(U,C?D)中，設InterSR(Di,Dj)是類簇Di和Dj間的區(qū)分度，基于類間區(qū)分度定義，則有：

其中，隨著InterSR(Di,Dj)值的增大，類簇Di和Dj間的區(qū)分度值越高，當前屬性子集R下對類簇Di和Dj進行分簇操作時所產(chǎn)生的劃分誤差越小。

在本文中，提出全局類間區(qū)分度的概念，用以衡量當前對象集各類簇間區(qū)分度總值，以確定當前對象集分簇能力的大小。

定義3（全局類間區(qū)分度）在決策信息系統(tǒng)DS=(U,C?D)中，InterSR(Di,Dj)是對象集由決策屬性集D劃分的多個類簇中任意兩類簇Di和Dj在條件屬性子集R下的類間區(qū)分度。設InterSU(R,D)是對象集的全局類間區(qū)分度，則：

其中，InterSU(R,D)的值越大，表示在屬性子集R下由決策屬性集D劃分的多個類間區(qū)分度的全局均值越大，對當前數(shù)據(jù)集進行分簇操作時的效果越好（劃分錯誤率越低）。

定義4（基于全局類間區(qū)分度的屬性重要度）R?C，在決策信息系統(tǒng)DS=(U,C?D)中，對于任意一個條件屬性a∈R，條件屬性a在屬性子集R下基于全局類間區(qū)分度的屬性重要度計算如下：

其中，Siginner(a,R,D)值越大表示該值所對應的屬性a對類間區(qū)分度的影響越顯著。

性質(zhì)1在決策信息系統(tǒng)DS=(U,C?D)中，R?C且R≠?，則有InterSU(C,D)≥InterSU(R,D)。

證明假設C={c1,c2,…,cn}且R={c1,c2,…,cn-1}，其中C?R=R，C-R={cn}。據(jù)上述定義，條件屬性集C和R下對象集的全局類間區(qū)分度值計算如下：

（1）假設fcn(Dik)=fcn(Djk)，則在刪除屬性cn時，對象Dik和Djk間關系不會改變，即IR(Dik,Dj)-IC(Dik,Dj)=0。

（2）假設fcn(Dik)≠fcn(Djk)，則Dik≠Djk（即IC(Dik,Djk)=0）。若刪除屬性cn，則有Dik=Djk或Dik≠Djk（即IR(Dik,Dj)=1或IR(Dik,Dj)=0），則IR(Dik,Dj)-IC(Dik,Dj)≥0。

3 一種基于類間區(qū)分度的屬性約簡方法

作為影響對象集類簇劃分能力的關鍵因素，應在屬性約簡過程中充分考慮到類間區(qū)分度值的變化情況。在本章中，基于類間區(qū)分度的定義和性質(zhì)，定義了相應的屬性約簡，并提出了一種屬性約簡方法。

3.1 基于類間區(qū)分度的屬性約簡定義

通常來講，使用屬性約簡的一個目的是期望能在更低劃分錯誤的情況下進行類簇劃分，而類間區(qū)分度就是影響各類簇間劃分表現(xiàn)性能的關鍵因素。由前文可知，對象集各類簇的類間區(qū)分度值越大，對該對象集進行分簇操作時可能產(chǎn)生的分簇錯誤越少，且隨著屬性子集R中屬性的減少，對象集U的全局類間區(qū)分度值會單調(diào)減小。在本節(jié)中，基于類間區(qū)分度的定義及其性質(zhì)提出了保持類間區(qū)分度值不變的屬性約簡定義。

定義5在決策信息系統(tǒng)DS=(U,C?D)中，當且僅當條件屬性子集R?C滿足以下條件時，R是基于類間區(qū)分度不變的一個屬性約簡：

（1）InterSU(C,D)=InterSU(R,D)

（2）?a∈R,InterSU(R-{a},D)＜InterSU(R,D)

在上述定義中，本文的目的是尋找一個屬性子集R以在減少屬性數(shù)目的條件下保持對象集U全局類間區(qū)分度的值不變。其中，條件（1）用以保證所獲得的條件屬性子集能夠保持類間區(qū)分度值大小不變；條件（2）是確保所獲得的約簡是滿足條件（1）的不含冗余屬性的最小屬性子集。

3.2 一種基于類間區(qū)分度的屬性約簡方法

根據(jù)上述基于類間區(qū)分度值不變的屬性約簡定義，提出了一種基于啟發(fā)式搜索策略的屬性約簡方法。

首先，基于類間區(qū)分度和屬性重要度定義，對條件屬性集中各屬性的重要度進行計算并排序。之后，基于屬性重要度序列以及保持類間區(qū)分度值不變的約簡定義，結(jié)合啟發(fā)式搜索刪除策略逐個刪除屬性重要度為零的屬性，并利用區(qū)分度不變策略刪除約簡子集中的冗余屬性，其具體操作流程見算法1。

算法1基于類間區(qū)分度不變的屬性約簡方法

輸入：決策信息系統(tǒng)DS=(U,C?D)。

輸出：約簡子集R。

1.初始化：C→R。

2.對于屬性子集R中的每一個屬性ai計算其屬性重要度：Siginner(ai,R,D)。

3.據(jù)屬性重要度對R中屬性進行排序。

4.刪除屬性重要度為零的屬性：

約簡循環(huán)1，選擇R中屬性重要度為零的屬性ak：

①若InterSU(R-ak,D)=InterSU(R,D)，則{R-ak}→R；返回步驟4重復循環(huán)；

②若InterSU(R-ak,D)≠InterSU(R,D)，則跳至步驟5結(jié)束循環(huán)1。

5.刪除約簡集中的冗余屬性ak：

for eachk=1 tok=|R|：

①計算InterSU(R-ak,D)；

②若InterSU(R-ak,D)=InterSU(R,D)，則{R-ak}→R。

6.返回R即為所求屬性約簡。

4 實驗

為驗證本文所提方法的有效性，在UCI數(shù)據(jù)庫中的一些數(shù)據(jù)集進行實驗。其數(shù)據(jù)集基本信息在表2中列出，其中列“Number of attributes”指條件屬性集所包含的屬性數(shù)目，“Size”指對象集所包含的對象數(shù)目，“Classes”表示決策屬性所包含的不同取值數(shù)目。

在實驗過程中，對每個數(shù)據(jù)集均使用10次10折交叉驗證，實驗結(jié)果保留4位小數(shù)，且均使用“均值±標準差”的記錄形式。使用WEKA[16]環(huán)境下4種常見分類算法以評價各約簡算法的分類準確率，其中包括：支持向量機、樸素貝葉斯、決策樹以及隨機森林。

Table 2 Brief description of data sets表2 數(shù)據(jù)集簡要描述

實驗結(jié)果見表3～表7，在這些表中，PRER（positive region expanded reduction）、MIR（maximum information based reduction）、COR（consistency based reduction）分別表示基于正域擴展、基于最大互信息以及基于一致性的約簡方法。同樣的，ICSR（inter-classseparability based reduction）代表的是本文基于類間區(qū)分度不變準則所提出的屬性約簡方法。在上述結(jié)果比較表中，每行表現(xiàn)最好的約簡方法結(jié)果均使用加粗處理。進一步的，使用5%顯著度的雙尾t-檢驗去檢測本文所提出方法的約簡結(jié)果與其他方法結(jié)果之間的差異性。其中使用標志“?”標記劣于本文所提出的方法且與其有顯著差異的方法結(jié)果值。使用標志“?”標記優(yōu)于本文中的方法且與其有顯著差異的方法結(jié)果值。此外，在以下各表中，對與本文實驗結(jié)果無顯著差異的實驗方法結(jié)果值均不做任何標記處理。需要補充的是，為更好地對各約簡方法的表現(xiàn)性能進行比較，表中使用“Score”行以計數(shù)各列所代表方法中出現(xiàn)最好實驗結(jié)果值的次數(shù)。

Table 3 Length of reduction of different reduction algorithms表3 不同約簡方法約簡長度比較

Table 4 Classification accuracy comparison of different reduction algorithms with naive Bayesian表4 樸素貝葉斯分類器下不同約簡方法分類精度比較

Table 5 Classification accuracy comparison of different reduction algorithms with decision trees表5 決策樹分類器下不同約簡方法分類精度比較

表3是不同約簡方法的約簡長度的比較。表4～表7是基于本文所提出的約簡方法與其他3種有效的約簡方法所求得的約簡結(jié)果基礎上，應用4種不同分類器對各分類精度值的比較。

Table 6 Classification accuracy comparison of different reduction algorithms with random forests表6 隨機森林分類器下不同約簡方法分類精度比較

Table 7 Classification accuracy comparison of different reduction algorithms with support vector machine表7 支持向量機分類器下不同約簡方法分類精度比較

從表中可以發(fā)現(xiàn)：4種約簡方法均可在一定程度上有效地減少各數(shù)據(jù)集的屬性數(shù)目。在上述各表中，ICSR約簡方法在所有分類器上均實現(xiàn)了很好的約簡結(jié)果，其在大多數(shù)數(shù)據(jù)集上實現(xiàn)了最優(yōu)分類結(jié)果，其中分別包括12、10、11、10次最優(yōu)分類精度值。相較于ICSR約簡方法，PRER約簡方法雖實現(xiàn)了最多次最小長度的約簡結(jié)果，但其僅在4種分類器13個數(shù)據(jù)集上實現(xiàn)了3次最優(yōu)分類精度結(jié)果。同樣的，對于MIR約簡方法和COR約簡方法而言，二者雖比ICSR約簡方法實現(xiàn)了較多次的更短約簡長度結(jié)果，但其在各分類器上實現(xiàn)最優(yōu)分類精度結(jié)果的次數(shù)卻遠遠小于本文所提出的約簡方法所實現(xiàn)最優(yōu)分類結(jié)果的次數(shù)。

從上述各表實驗結(jié)果來看，盡管本文所提出的約簡方法并未實現(xiàn)最短的約簡長度結(jié)果值，但其在4個分類器13個數(shù)據(jù)集的分類精度比較實驗中實現(xiàn)最優(yōu)分類精度值的次數(shù)遠多于其他3種屬性約簡方法，且其實驗結(jié)果值與其他3種方法的實驗結(jié)果相比具有顯著的差異性。此外，上述分類精度及差異性比較實驗也表明了本文所提出的約簡方法的有效性。

5 結(jié)論

屬性約簡是分類學習中一個重要的問題。針對當前的屬性約簡方法中較少考慮到各類簇間區(qū)分度值的問題，本文將類間區(qū)分度的相關概念引入到粗糙集屬性約簡模型中，提出了一種保持類間區(qū)分度不變的屬性約簡方法。首先，解釋并定義了類間重合度，基于重合度概念分析并定義了類間區(qū)分度。之后，考慮到類間區(qū)分度的相關性質(zhì)，定義了一種保持類間區(qū)分度值不變的屬性約簡，并基于該約簡定義以及啟發(fā)式搜索策略獲得滿足相關標準的最小條件屬性子集。最后，通過與其他約簡方法的對比實驗表明本文所提出的方法能夠獲得具有更高分類準確率的屬性約簡結(jié)果。