基于鄰域關系矩陣的屬性約簡算法

徐 波，馮 山

(四川師范大學數學科學學院，成都610068)

E-mail:xuboxbox@163.com

1 引言

粗糙集理論［1］已被廣泛應用于機器學習、規則挖掘、模式識別等領域［2，3］.屬性約簡是其核心研究內容之一，在智能信息處理研究中占有重要地位.對給定任務數據集，不是所有屬性都同等重要.例如，能夠由其他屬性導出的屬性是冗余的，其存在會帶來時空浪費，且干擾決策.屬性約簡正好是在保持或改善數據決策能力下刪除不重要或冗余屬性.

含有決策屬性的數據集稱為決策表，其屬性約簡并不一定唯一.找到具有最少條件屬性子集的約簡是人們的期望.但文獻［4］表明，由于屬性的組合爆炸，決策系統中基于粗糙集的最小屬性約簡是一個NP-hard問題.因此，在決策系統的約簡算法中，融入啟發信息以加快屬性約簡算法的收斂速度成為一個主流的研究方向［5］.

根據啟發信息的不同，啟發式約簡算法有關聯差別矩陣［6］、信息度量(包括信息熵、互信息熵、條件信息熵、近似決策熵)［7-9］、三支決策［10］和屬性重要度(正域)［11］等.在基于屬性重要度的約簡算法中，一般以等價關系區分對象，故只能直接處理離散型屬性對象.實際上，離散型、連續型和混合型屬性數據都大量存在，直接采用現有算法有局限.為此，Lin［12］提出了基于拓撲學中內點和閉包的鄰域關系及鄰域模型相關的概念.Yao［13］研究了1-step鄰域系統與粗糙集近似的關系.基于此，胡清華等［14］研究了鄰域系統的粗糙計算及屬性約簡，以鄰域關系代替等價關系提出了基于鄰域粗糙集模型的特征選擇算法NRS，它可直接處理混合型屬性數據集，是傳統基于屬性重要度的約簡算法的直接拓展.因NRS的正域啟發只考慮某類樣本鄰域信息粒的決策信息，忽略了鄰域信息粒中多類樣本的情形，導致約簡效果不理想.于是文獻［15］提出基于鄰域決策誤差最小化的特征選擇算法NDEM，它將一致性指標引入鄰域粗糙集中，由樣本鄰域信息粒的內部類分布和多數決策原則重新給各樣本分配類別，進而統計實際類別與重分類別的差異率.但它只考慮各類分布不均勻時樣本鄰域信息粒中決策信息，無法準確反映各類分布均勻時樣本鄰域信息粒中的決策信息.目前，對鄰域粗糙集中條件屬性子集與決策屬性間的不確定性度量研究已有一些成果，如文獻［1http://archive.ics.uci.edu/ml，2013.6］的鄰域精度、鄰域信息熵等.

在文獻［14-16］基礎上，通過分析鄰域決策系統的鄰域信息粒中類分布，結合樣本鄰域信息粒的決策分布，本文提出一種能反映條件屬性子集與決策屬性間相關性的度量.以鄰域關系矩陣表示鄰域關系，將鄰域關系間的集合運算轉化為矩陣運算，探究了鄰域關系矩陣的基本性質.證明了相關性度量的?；瘑握{性，結合排序思想與鄰域關系矩陣對稱性，改進了文獻［17］計算單屬性關系矩陣算法(Single Attribute Neighborhood Relation Matrix algorithm，SANRM)，將其時間復雜度降低至對數級，并設計了基于鄰域關系矩陣的啟發式約簡算法(heuristic Neighborhood Relation Matrix Attribute Reduction algotirhm，NRMAR).UCI1http://archive.ics.uci.edu/ml，2013.數據集實驗的比較分析表明，NRMAR比NDEM選擇更少的屬性，且可以保持或改善數據集的分類能力.

2 鄰域決策系統的概念與性質

一個信息系統是一個形如IS=(U，A，V，f)的四元組.U={x1，x2，…，xn}是論域;A 是屬性集;V=∪Va( a∈A)是屬性值域的并，Va是屬性a的值域;f:U×A→V是映射，對 xi∈U，a∈A，有f(xi，a)∈Va.A=C∪D，C∩D= 時，C 為條件屬性集，D為決策屬性集.此時稱為決策信息系統或決策系統，記 DIS=(U，C∪D，V，f).特別地，本文 D=g0gggggg.

對鄰域決策系統 NDIS=(U，C∪D，V，f，δ)，要引入距離函數與鄰域半徑δ來度量樣本在屬性集上的區分性.

對任意非空條件屬性子集 BC，B={b1，b2，…，bm}， xi，xj，xk∈U(1≤i，j，k≤n)，距離函數 ΔB(xi，xj)要滿足:

1)ΔB(xi，xj)≥0，ΔB(xi，xi)=0(非負性);

2)ΔB(xi，xj)=ΔB(xj，xi)(對稱性);

3)ΔB(xi，xk)≤ΔB(xi，xj)+ ΔB(xj，xk)(傳遞性).

ΔB(xi，xj)計算xi與xj在屬性子集B下的距離.本文采取文［14］的歐氏距離函數，即:

其中，f(xi，bl)與 f(xj，bl)分別表示樣本 xi與 xj在屬性 bl下的屬性值.

定義 1［14］.NDIS=(U，C∪D，V，f，δ)中， xi∈U，給定 δ≥0，定義在B上的δ-鄰域為:

其中 1≤i，j≤n.δ-鄰域又稱為鄰域信息粒或樣本鄰域類，表示樣本在屬性集B下的不可區分樣本集.它不僅蘊含樣本間的不可區分性，也含有決策信息.

性質1［14］.鄰域nB(xi)具有如下基本性質:

性質2是條件屬性子集與決策屬性相關性度量的單調性理論基礎.

定義 2［14］.在 NDIS=(U，C∪D，V，f，δ)中，BC 可以確定鄰域關系nr(B):

鄰域關系是基于距離度量的一種相似關系，拓展了等價關系的適用范圍.B為離散屬性集時鄰域半徑δ=0，此時關系退化為等價關系;B為連續屬性集時δ＞0，此時可以直接處理混合型屬性數據集.

3 基于鄰域決策誤差率最小化準則的分析

可引入0－1判別函數如下:

其中，ω(xi)為樣本xi的真實類別.則鄰域決策誤差率可以定義為:

公式(2)只考慮了樣本鄰域信息粒中各類分布不均勻情況，在多數決策原則下只能反映多數樣本信息粒的類別信息.當樣本鄰域信息粒中各類分布均勻時會出現錯誤決策.

圖1 二維空間上的樣本分布實例Fig.1 Sample distribution on two-dimensional space

如果論域樣本的二維空間分布如圖1.類為d1和d2.x1～x4的類為 ω(x1)=ω(x2)=ω(x4)=d1和 ω(x3)=d2，λ(ω(x1)，d1)=0、λ(ω(x2)，d2)=1、λ(ω(x3)，d2)=0.對 x4，P(d1|nB(x4))=P(d2|nB(x4))=，由多數決策原則，它可以被判定為 d1或 d2類，故 λ(ω(x4)，d.)=1 或0.顯然，此時的鄰域決策誤差率無法正確反映各類均勻分布的樣本鄰域信息粒中的決策信息.為此，需要提出能夠反映條件屬性子集與決策屬性相關性的度量，它依賴于每個樣本在決策屬性上的鄰域信息粒與條件屬性集上的鄰域信息粒的融合所提供的信息量，以避免無法刻畫各類均勻分布時樣本鄰域信息粒中決策信息的情況.

其中nD(xi)與樣本xi真實類一致;nB(xi)是B下不能與xi區分的樣本集，其每個樣本類不盡相同.與公式(2)相比，公式(3)可以準確反映nB(xi)中各類不同分布時的類信息量，具體體現在n(B，D)(xi)中元素個數.當與xi不同的類中樣本數居多時n(B，D)(xi)中元素多;當xi同類與xi不同的類中樣本數相同時n(B，D)(xi)中元素相對減少;當只有 xi一類時 n(B，D)(xi)中元素最少，即nD(xi).綜上，n(B，D)(xi)中的元素都可唯一確定.故基于融合信息?？山o出B和D的相關性度量定義.

定義4.NDIS=(U，C∪D，V，f，δ)中， xi∈U，D 關于 B的融合鄰域信息粒n(B，D)(xi)，B與D的相關性度量為:

顯然，公式(4)可以有效反映B與D的相關性，克服公式(2)無法準確反映鄰域信息粒的決策信息不足，避免鄰域信息粒的各類分布均勻時的錯誤決策，還具備?；瘑握{性.為證明公式(4)的相關性質，可引入鄰域關系矩陣將鄰域關系的集合運算轉化為矩陣運算.

4 基于鄰域關系矩陣的屬性約簡

4.1 鄰域關系矩陣相關概念與性質

定義5.(鄰域關系矩陣)NDIS=(U，C∪D，V，f，δ)中，U={x1，x2，…，xn}，BA 有鄰域關系 nr(B)，則鄰域關系矩陣為 MB=(mij)n×n，其中 n=|U|

命題1.(鄰域關系矩陣與δ-鄰域關系) xi∈U，若有B上 δ-鄰域 nB(xi)，如果 NDIS=(U，C∪D，V，f，δ)中的鄰域關系矩陣 MB=(mij)n×n，n=|U|，則有:

證明:δ-鄰域nB(xi)是樣本集，將其與n維0－1向量建立一一對應關系，對應論域中所有樣本，則有:

性質 3［17］.鄰域關系矩陣 MB=(rij)n×n具有如下性質:

1)對 i=1，2，…，n，有 rii=1(自反性).

2)MB是對稱矩陣(對稱性).

3) i，j，k∈{1，2，…，n}，rij=rjk=1 時 rik=1(傳遞性).

由此，可以構建計算單屬性下鄰域關系矩陣的快速算法(SANRM).由于鄰域關系矩陣是布爾矩陣，元素只有0和1，鄰域關系矩陣的∧運算與∨運算可定義如下.

為了證明基于鄰域關系矩陣的屬性相關性度量的粒化單調性，可以定義矩陣間的如下偏序關系.

由命題1的鄰域關系矩陣與δ-鄰域的關系可知，MP中每一行的第j列取值1時，MQ中對應行列位置處取1或0;MP中每一行的第j列取值0時，MQ中對應行列位置的取值必為0.由定義7 可知，MPMQ.

4.2 基于鄰域關系矩陣的屬性約簡的相關概念

其中，sum(M)表示矩陣M中元素為1的個數.

性質1.

1)規定 M=(1)n×n，若 B= ，則 mrB(D)=0;

2)當且僅當 MB=MD=diag(1)n×n，則 mrB(D)=1其中diag(1)n×n是元素值為1的n×n階對角矩陣.

證明:

性質1說明，B= 時條件屬性子集與決策屬性無關，相關度達到最小值0;性質2說明，能夠找到一個條件屬性子集B與決策屬性D的具有相近的決策能力.此時，兩者的相關度達到最大值1

由定義4，rB(D)依賴于融合鄰域信息粒n(B，D)(xi)中元素的個數.由命題1中集合與矩陣間的一一對應關系，定義8中mrB(D)=rB(D)，在表示與計算上，前者基于鄰域關系矩陣，后者基于集合.下面證明mrB(D)具有?；瘑握{性.

命題3表明，mrB(D)具有?；瘑握{遞增性.條件屬性子集B越大(即隨著新條件屬性的加入)，mrB(D)值越大，所以mrB(D)能夠作為啟發信息構建啟發式約簡算法.

定義9.NDIS=(U，C∪D，V，f，δ)中， b∈BC，若 mrB(D)=mrB－(D)，稱b為B基于鄰域關系矩陣屬性相關性度量的冗余屬性;否則，mrB－(D)＜mrB(D)時稱b為B基于鄰域關系矩陣屬性相關性度量的必要屬性.

定義10.(基于鄰域關系矩陣的屬性約簡)在 NDIS=(U，C∪D，V，f，ε)中，非空屬性子集 BC 稱為基于鄰域關系矩陣的屬性約簡，如果其滿足:

1) b∈B有mrB－(D)＜mrB(D)，即B中屬性都必要;

2)mrC(D)=mrB(D).

為加快約簡算法收斂速度，減少不同屬性集樣本間距離計算，單屬性集與多屬性集下鄰域關系矩陣有如下關系.

證明:令MB=(mij)n×n，由命題1中鄰域關系矩陣與鄰域的關系知mij=1xj∈nB(xi); B，由性質2的 nB(xi)單調性有xj∈nB(xi)n(xi)，故

由命題4，多屬性鄰域關系矩陣計算可轉為單屬性鄰域關系矩陣運算以減少樣本間距離的計算次數，減少約簡的時間.文獻［17］的單屬性關系矩陣計算主要基于樣本間的依次比對，時間復雜度為O(|U|2).將有序性和鄰域關系矩陣對稱性融合，改進的計算單屬性鄰域關系矩陣算法(SANRM)時間復雜度為O(|U|log(|U|)).定義11是決策系統的矩陣表示.

定義11.對 DIS=(U，C∪D，V，f)，|C∪D|=m，|U|=n，有信息矩陣Wn×m(記W)，W中每一列描述樣本的一種屬性，每一行由樣本的各屬性值構成，最后一列是決策屬性.

算法1.計算單屬性下鄰域關系矩陣(SANRM)

輸出:鄰域關系矩陣M{ai}.

算法1對論域樣本進行給定屬性的升序排列并一一記錄對應的原始樣本標號，排序后從第一個樣本開始依次向下比對屬性值，將滿足鄰域定義的其他樣本記錄在臨時矩陣的兩處位置(其一，對應第一個樣本原始樣本標號所在的行和其他樣本原始樣本標號所在的列;其二，將位置一中行和列對應臨時矩陣的列和行的位置)，直到不滿足鄰域定義，進入下一個樣本，循環上述過程，直到最后一個樣本處理結束，得到該屬性下的臨時鄰域關系矩陣.步驟2的排序時間復雜度為O(|U|log(|U|)).假設論域樣本的鄰域平均對象數為q(q|U|)，則步驟7-步驟20的時間復雜度為O(q)，故步驟3-步驟21的時間復雜度為O(q|U|).因此，該算法的平均時間復雜度為O(|U|log(|U|)).

以鄰域關系矩陣的屬性相關性度量為基礎，利用其粒化單調性，以算法1計算單屬性下的鄰域關系矩陣.進而可考慮條件屬性的增加策略以構建啟發式約簡算法［18］.為此，下面給出單條件屬性重要度概念.

定義 12.NDIS=(U，C∪D，V，f，δ)中，對 BC，定義屬性a∈C－B相對B關于D的基于鄰域關系矩陣的屬性相關性度量的屬性重要度為:

基于mrB(D)的?；瘑握{遞增性，(6)式刻畫了單屬性加入前后B與D相關度變化，由此可挑選出變化最大的屬性，直到新屬性加入時mrB(D)不再增加為止.因此，基于鄰域關系矩陣的啟發式約簡算法可描述如下.

算法2.基于鄰域關系矩陣的啟發式約簡算法(NRMAR)

輸出:約簡屬性子集reduct.

算法2先算各屬性的鄰域關系矩陣.再依次加條件屬性計算屬性相關度，由屬性重要度挑選屬性到約簡子集.重復直到重要度不再變化.其計算單屬性鄰域關系矩陣的復雜度為O(|C∪D||U|log(|U|)).步驟7按矩陣行并行計算，復雜度O(|

5 UCI數據集實驗驗證及分析

為驗證NRMAR的有效性，我們先通過實驗選取合理的鄰域半徑δ，再對NRMAR與NDEM的約簡屬性數量、質量和運行時間對比.如表1，實驗從UCI機器學習數據庫挑選6個數據集(3個連續型數據集Wine、Wdbc和Sonar，1個離散型數據集Tic，2個混合型數據集 Heart和 Thoraric).算法在MATLAB R2010b上實現.配置為:Intel(R)Core(TM)i5-2400、主頻 3.10GHz、內存 2G、Windows 7.

表1 實驗數據集的基本描述Table 1 Basic description of experiment data set

5.1 鄰域半徑選取分析

實驗前要對連續屬性數據歸一化［19］，它并不影響樣本分布，只是消除不同取值的量級與量綱影響.假定采用最小-最大規范化，公式如下:

其中，f(xi，bj)為 xi在屬性 bj下的取值，maxbj和 minbj為全部樣本在屬性bj下的最大和最小值.規范化后，xi在屬性bj下的取值范圍 f*(xi，bj)為［0，1］.

由定義1，鄰域信息粒生成的關鍵在鄰域半徑δ的選取.δ直接影響鄰域信息粒中各個類的分布，從而影響著約簡屬性數量和約簡屬性子集質量.實驗用表1的Wine、Heart和Thoraric確定 δ.δ∈［0，1］，變化步長 0.01.δ對約簡屬性子集數量及分類準確率的影響如圖2和圖3所示.

圖2 條件屬性數量與δ取值關系Fig.2 Relationship of conditional attribute number and theδvalue

圖3 分類準確率與δ取值關系Fig.3 Relationship of classification accuracy and theδvalue

圖2 表明，用NRMAR約簡時，不同δ對條件屬性數影響明顯.δ∈［0，0.1］及接近1 時屬性數較少;δ∈［0.1，0.3］時屬性數適中;δ∈［0.3，0.4］時屬性數達到最大值并保持.

圖3表明，NRMAR用于3個數據集時，約簡后的屬性子集在CART方法下的分類準確率與δ的取值變化關系.δ在0和1附近時準確率偏低;δ∈［0.05，0.15］時準確率較高，但Wine和Thoraric的分類準確率波動較大;δ∈［0.15，0.25］時準確率達到最大并保持.故δ的合理取值范圍為［0.15，0.25］.為使試驗更客觀，處理連續屬性時取δ=0.15，否則δ=0.

5.2 約簡屬性子集數目與分類準確率

表1數據集在NRMAR和文［15］NDEM算法下的約簡屬性子集的結果如表2所示.

表2 NRMAR和NDEM算法下的約簡屬性子集Table 2 Subset of reduction attributes under NRMAR and NDEM

表2表明，算法能有效約簡數據集.對連續型的Wine和Sonar，約簡后的屬性數明顯減少，說明連續型數據集有大量冗余屬性，其約簡算法更加值得研究.兩種算法對單個數據集的約簡都有相同條件屬性，但又不盡相同.差異源于約簡算法的屬性重要度差異.由此印證了基于鄰域關系矩陣的屬性相關性度量與文［15］的鄰域決策誤差率最小化準則度量的差異.對表2的約簡質量，以CART分類［18］為準，以10次交叉驗證算出分類準確率，結果如表3所示.

表3 基于CART分類器的分類準確率Table 3 Classification accuracies based on CART classification

表3表明，兩種算法在連續型數據集Wine、Wdbc和Sonar上的約簡屬性子集屬性數和分類準確度都較好.它源于:(1)數據采集的人為和儀器測量因素引起的誤差，以及針對具體決策任務而言的屬性冗余.(2)鄰域關系是等價關系拓展來的相似關系，能一定程度上容忍數據誤差，有效處理連續型數據集.其中，NRMAR比NDEM的結果更好.比如，Sonar的初始60個屬性的準確率為71.15%，NRMAR選出5個屬性的準確率為78.85%，而NDEM選出的11個屬性的準確率為74.52%.它得益于NRMAR考慮了每個樣本信息粒中各個類的均勻分布和融合其決策分布，強化了條件屬性與決策屬性間的相關性.另外，兩種算法在離散型Tic上的優化不明顯.原因是鄰域關系退化成了等價關系，此時，樣本鄰域信息粒中各類分布因δ=0而不會發生改變.雖然表2中兩種算法在Tic上的約簡屬性子集的屬性及其被選順序不盡相同，但最終準確率不低于初始準確率，表明兩種算法都能直接有效處理離散型數據集.最后，對混合型Heart和Thoraric，算法結果都較好.其中 NRMAR比 NDEM 更優.比如，在 Heart上NRMAR只需6個屬性即可達82.21%的準確率.兩種算法對Thoraric約簡優化效果不明顯的主要原因是，Thoraric中的屬性絕大部分是離散型.從均值看，約簡后屬性數都顯著減少且準確率都有所提高，而NRMAR效果更好.

5.3 運行時間比較

將鄰域關系間的集合運算轉化為矩陣運算，同時，改進計算單屬性鄰域關系矩陣法及利用命題4中單屬性與多屬性的鄰域關系矩陣，可得NRMAR時間復雜度為:

基于集合表示與運算的NDEM的時間復雜度為:

兩種算法在6個數據集上的運行時間對比如圖4所示.可見，NRMAR的用時更少，且與理論分析一致.

6 結論與展望

提出了基于鄰域關系矩陣的屬性約簡算法(NRMAR)，解決了NDEM無法準確反映各類分布均勻時的樣本信息粒的決策信息問題.主要工作如下:

1)通過融合樣本鄰域信息粒與其決策分布提出了條件屬性集與決策屬性的相關性度量，用鄰域關系矩陣表示鄰域關系，并用基于鄰域關系矩陣的屬性相關性度量表示，證明了其?；膯卧鲂?

2)改進了單屬性鄰域關系矩陣計算方法，將時間復雜度控制在對數級，給出了單屬性與多屬性鄰域關系矩陣的內在聯系;

3)設計、實現了NRMAR算法，UCI數據集實驗分析驗證了NRMAR相比NDEM更能選擇較少條件屬性，且可保持或改善數據的分類能力.

NRMAR中的鄰域半徑直接影響著鄰域信息粒中各個類的分布，從而影響屬性約簡的結果.下一步工作將考慮如何合理選擇鄰域半徑.