基于鄰域關(guān)系矩陣的屬性約簡算法

徐 波，馮 山

(四川師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，成都610068)

E-mail:xuboxbox@163.com

1 引言

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

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

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

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

2 鄰域決策系統(tǒng)的概念與性質(zhì)

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

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

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

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

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

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

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

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

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

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

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

性質(zhì)2是條件屬性子集與決策屬性相關(guān)性度量的單調(diào)性理論基礎(chǔ).

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

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

3 基于鄰域決策誤差率最小化準(zhǔn)則的分析

可引入0－1判別函數(shù)如下:

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

公式(2)只考慮了樣本鄰域信息粒中各類分布不均勻情況，在多數(shù)決策原則下只能反映多數(shù)樣本信息粒的類別信息.當(dāng)樣本鄰域信息粒中各類分布均勻時(shí)會(huì)出現(xiàn)錯(cuò)誤決策.

圖1 二維空間上的樣本分布實(shí)例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.對(duì) x4，P(d1|nB(x4))=P(d2|nB(x4))=，由多數(shù)決策原則，它可以被判定為 d1或 d2類，故 λ(ω(x4)，d.)=1 或0.顯然，此時(shí)的鄰域決策誤差率無法正確反映各類均勻分布的樣本鄰域信息粒中的決策信息.為此，需要提出能夠反映條件屬性子集與決策屬性相關(guān)性的度量，它依賴于每個(gè)樣本在決策屬性上的鄰域信息粒與條件屬性集上的鄰域信息粒的融合所提供的信息量，以避免無法刻畫各類均勻分布時(shí)樣本鄰域信息粒中決策信息的情況.

其中nD(xi)與樣本xi真實(shí)類一致;nB(xi)是B下不能與xi區(qū)分的樣本集，其每個(gè)樣本類不盡相同.與公式(2)相比，公式(3)可以準(zhǔn)確反映nB(xi)中各類不同分布時(shí)的類信息量，具體體現(xiàn)在n(B，D)(xi)中元素個(gè)數(shù).當(dāng)與xi不同的類中樣本數(shù)居多時(shí)n(B，D)(xi)中元素多;當(dāng)xi同類與xi不同的類中樣本數(shù)相同時(shí)n(B，D)(xi)中元素相對(duì)減少;當(dāng)只有 xi一類時(shí) n(B，D)(xi)中元素最少，即nD(xi).綜上，n(B，D)(xi)中的元素都可唯一確定.故基于融合信息粒可給出B和D的相關(guān)性度量定義.

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

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

4 基于鄰域關(guān)系矩陣的屬性約簡

4.1 鄰域關(guān)系矩陣相關(guān)概念與性質(zhì)

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

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

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

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

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

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

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

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

為了證明基于鄰域關(guān)系矩陣的屬性相關(guān)性度量的?；瘑握{(diào)性，可以定義矩陣間的如下偏序關(guān)系.

由命題1的鄰域關(guān)系矩陣與δ-鄰域的關(guān)系可知，MP中每一行的第j列取值1時(shí)，MQ中對(duì)應(yīng)行列位置處取1或0;MP中每一行的第j列取值0時(shí)，MQ中對(duì)應(yīng)行列位置的取值必為0.由定義7 可知，MPMQ.

4.2 基于鄰域關(guān)系矩陣的屬性約簡的相關(guān)概念

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

性質(zhì)1.

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

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

證明:

性質(zhì)1說明，B= 時(shí)條件屬性子集與決策屬性無關(guān)，相關(guān)度達(dá)到最小值0;性質(zhì)2說明，能夠找到一個(gè)條件屬性子集B與決策屬性D的具有相近的決策能力.此時(shí)，兩者的相關(guān)度達(dá)到最大值1

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

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

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

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

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

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

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

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

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

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

算法1.計(jì)算單屬性下鄰域關(guān)系矩陣(SANRM)

輸出:鄰域關(guān)系矩陣M{ai}.

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

以鄰域關(guān)系矩陣的屬性相關(guān)性度量為基礎(chǔ)，利用其?；瘑握{(diào)性，以算法1計(jì)算單屬性下的鄰域關(guān)系矩陣.進(jìn)而可考慮條件屬性的增加策略以構(gòu)建啟發(fā)式約簡算法［18］.為此，下面給出單條件屬性重要度概念.

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

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

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

輸出:約簡屬性子集reduct.

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

5 UCI數(shù)據(jù)集實(shí)驗(yàn)驗(yàn)證及分析

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

表1 實(shí)驗(yàn)數(shù)據(jù)集的基本描述Table 1 Basic description of experiment data set

5.1 鄰域半徑選取分析

實(shí)驗(yàn)前要對(duì)連續(xù)屬性數(shù)據(jù)歸一化［19］，它并不影響樣本分布，只是消除不同取值的量級(jí)與量綱影響.假定采用最小-最大規(guī)范化，公式如下:

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

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

圖2 條件屬性數(shù)量與δ取值關(guān)系Fig.2 Relationship of conditional attribute number and theδvalue

圖3 分類準(zhǔn)確率與δ取值關(guān)系Fig.3 Relationship of classification accuracy and theδvalue

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

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

5.2 約簡屬性子集數(shù)目與分類準(zhǔn)確率

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

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

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

表3 基于CART分類器的分類準(zhǔn)確率Table 3 Classification accuracies based on CART classification

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

5.3 運(yùn)行時(shí)間比較

將鄰域關(guān)系間的集合運(yùn)算轉(zhuǎn)化為矩陣運(yùn)算，同時(shí)，改進(jìn)計(jì)算單屬性鄰域關(guān)系矩陣法及利用命題4中單屬性與多屬性的鄰域關(guān)系矩陣，可得NRMAR時(shí)間復(fù)雜度為:

基于集合表示與運(yùn)算的NDEM的時(shí)間復(fù)雜度為:

兩種算法在6個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間對(duì)比如圖4所示.可見，NRMAR的用時(shí)更少，且與理論分析一致.

6 結(jié)論與展望

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

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

2)改進(jìn)了單屬性鄰域關(guān)系矩陣計(jì)算方法，將時(shí)間復(fù)雜度控制在對(duì)數(shù)級(jí)，給出了單屬性與多屬性鄰域關(guān)系矩陣的內(nèi)在聯(lián)系;

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

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