黃恒秋，陳素霞，翁世洲

（1.廣西民族師范學(xué)院數(shù)理與電子信息工程學(xué)院，崇左 532200；2.河南輕工職業(yè)學(xué)院計(jì)算機(jī)與藝術(shù)設(shè)計(jì)系，鄭州 450052；3.廣西民族師范學(xué)院經(jīng)濟(jì)管理學(xué)院，崇左 532200）

0 引言

經(jīng)典粗糙集模型以等價(jià)關(guān)系作為基本近似單元，要求數(shù)據(jù)集為離散型，然而現(xiàn)實(shí)中大部分?jǐn)?shù)據(jù)以數(shù)值型或者混合型存在。Lin［1］首次用鄰域關(guān)系代替經(jīng)典的等價(jià)關(guān)系，構(gòu)建了鄰域粗糙集模型。Hu 等［2］采用距離函數(shù)定義鄰域關(guān)系，使其能夠直接處理離散型和數(shù)值型數(shù)據(jù)，進(jìn)一步拓展了鄰域粗糙集模型的研究?jī)?nèi)容及應(yīng)用范圍。

鄰域粗糙集模型主要應(yīng)用于屬性約簡(jiǎn)和基于決策規(guī)則的分類［3］，目前已經(jīng)取得了豐碩的研究成果，比如基于鄰域粗糙集屬性約簡(jiǎn)和經(jīng)典分類方法融合的混合分類方法［4-9］；基于鄰域決策粗糙集和三支鄰域決策粗糙集的分類方法［10-11］；基于鄰域粗糙集約簡(jiǎn)規(guī)則的最近鄰分類方法［12-15］。

基于鄰域粗糙集約簡(jiǎn)規(guī)則的分類方法，由于容易理解和方便實(shí)現(xiàn)，同時(shí)能夠充分利用鄰域的局部最優(yōu)決策信息［8］，目前已獲得了廣泛應(yīng)用［7］，但是針對(duì)現(xiàn)實(shí)中廣泛存在的含離散屬性、數(shù)值屬性和缺失值的混合不完備數(shù)據(jù)集研究并不多見。目前，針對(duì)該類數(shù)據(jù)集主要有以下幾種處理方法：①使用能容忍缺失值的距離函數(shù)，比如混合距離HEOM［16］，該函數(shù)對(duì)屬性的缺失值用其最大值來代替，稱為最樂觀的情況。文獻(xiàn)［17］指出，如果屬性較多，同時(shí)缺失比例也較大時(shí)，HEOM 距離容易造成數(shù)據(jù)集失真。文獻(xiàn)［18］在使用HEOM 時(shí)，針對(duì)缺失值則是使用最小值來代替，即最悲觀的情況。②對(duì)鄰域關(guān)系進(jìn)行拓展定義，使其成為鄰域容差關(guān)系，比如視缺失值與其他非缺失值都相等的鄰域容差關(guān)系［19-20］，而文獻(xiàn)［21］則從兩個(gè)樣本之間的聯(lián)系度出發(fā)，通過定義三種聯(lián)系度指標(biāo)，給出鄰域聯(lián)系度容差關(guān)系。③將聯(lián)系度系數(shù)轉(zhuǎn)化為距離，從而方便計(jì)算和拓展應(yīng)用到其他模型［22-23］。該方法避免了對(duì)缺失值的填充，同時(shí)又較好地利用了聯(lián)系度信息，很好地對(duì)不確定樣本相似性進(jìn)行了有效度量。針對(duì)混合不完備數(shù)據(jù)集，文獻(xiàn)［24］給出了基于鄰域聯(lián)系度轉(zhuǎn)化為計(jì)算距離的雙鄰域粗糙集分類方法，也取得了優(yōu)異的分類效果，但是該距離函數(shù)（文獻(xiàn)中稱為鄰域聯(lián)系度距離）有三個(gè)參數(shù)需要通過大量實(shí)驗(yàn)來確定，限制了其拓展應(yīng)用。

本文在文獻(xiàn)［24］的基礎(chǔ)上，首先對(duì)其鄰域聯(lián)系度距離進(jìn)行拓展定義，提出一個(gè)不帶參數(shù)的鄰域聯(lián)系度距離函數(shù)；其次構(gòu)建基于鄰域聯(lián)系度距離的新型雙鄰域粗糙集模型；最后給出基于覆蓋約簡(jiǎn)的新型雙鄰域粗糙集規(guī)則學(xué)習(xí)與分類算法。

為了驗(yàn)證本文給出的分類方法的效果，選取7 個(gè)UCI 數(shù)據(jù)集進(jìn)行了對(duì)比實(shí)驗(yàn)，通過與HEOM 距離取最大值、HEOM 距離取最小值、文獻(xiàn)［24］的結(jié)果進(jìn)行對(duì)比，結(jié)果表明本文提出的分類方法仍然取得了優(yōu)異的分類效果。

1 鄰域粗糙集相關(guān)概念

1.1 鄰域關(guān)系

定義1［2］給定數(shù)據(jù)集構(gòu)成的決策系統(tǒng)I=(U,A?D,V,f),B?A,定義B上的δ-鄰域關(guān)系為

這里δ≥0，Δ是為距離函數(shù)。

定義2［19］設(shè)I=(U,A?D,V,f)為混合不完備系統(tǒng)，B?A,B=BC?BN,BC記為離散屬性，BN記為數(shù)值屬性，δ≥0。定義B的鄰域容差關(guān)系為

其中箭頭符號(hào)（→）表示關(guān)系滿足的條件，星號(hào)（*）表示屬性取值為缺失值。

定義3［21］對(duì)于混合不完備系統(tǒng)I=(U,A?D,V,f),|A|=N,Δ 表示絕對(duì)值距離，(xi,xj)∈U2為集對(duì)。記ε為相容鄰域半徑，M={a∈A|Δa(xi,xj)≤ε} 為集對(duì)取值在ε內(nèi)的屬性集；H={a∈A|Δa(xi,xj)＞ε} 為集對(duì)取值在ε外的屬性集合；G={a∈A|f(xi,a)=* ∨f(xj,a)=*} 為集對(duì)中屬性取值存在缺失值的屬性集。記m=|M|N,g=|G|N,h=|H|N，則集對(duì)(xi,xj)的鄰域聯(lián)系度為

這里m、g、h為同一度、差異度和對(duì)立度；i*、j*為用于區(qū)分差異度和對(duì)立度標(biāo)識(shí)。取0 ≤t≤1,B?A,則B上的鄰域聯(lián)系度容差關(guān)系為

定義4［15］記樣本xi的Tri-分割鄰域?yàn)?/p>

這里Δ 為距離函數(shù)；β為異質(zhì)度，即鄰域中與xi不同類別樣本數(shù)量的占比；δβ是異質(zhì)度為β時(shí)的鄰域半徑。則Tri-分割鄰域的下、上近似鄰域定義為

下近似鄰域要求β=0，上近似鄰域要求β=r，r∈(0,1) 。通過鄰域異質(zhì)度，可以控制鄰域樣本的類別純度，一般情況下純度越高，決策能力越強(qiáng)。區(qū)別于一般的鄰域粗糙集模型只用一個(gè)半徑來定義近似鄰域，這里的上、下近似鄰域半徑是不相同的，他們通過鄰域異質(zhì)度來控制，稱為雙鄰域近似。

1.2 鄰域系統(tǒng)中的距離度量

定義5閔氏距離［2］

這里m表示屬性維度。p=1 時(shí)表示閔可夫斯基距離；p=2時(shí)表示歐氏距離；p=∞時(shí)表示切比雪夫距離。

定義6混合距離［17］

這里：

定義7［24］給定兩個(gè)樣本構(gòu)成的集對(duì)(x,y)，其鄰域聯(lián)系度為μ(x,y)=m+gi*+hj*,則它們的鄰域聯(lián)系度距離定義為

這里w1,w2,w3為同一度、差異度和對(duì)立度的懲罰系數(shù)，且滿足w1+w2+w3=1。

2 基于無參數(shù)鄰域聯(lián)系度距離的新型雙鄰域粗糙集模型

2.1 無參數(shù)鄰域聯(lián)系度距離

定義8給定樣本(x,y)構(gòu)成的集對(duì)(x,y)，其鄰域聯(lián)系度μ(x,y)=m+gi*+hj*,則無參數(shù)鄰域聯(lián)系度距離定義為

定義8 是對(duì)定義7 的拓展，該鄰域聯(lián)系度距離函數(shù)不帶參數(shù)，與定義7 相比還多了后面兩項(xiàng)，表示兩個(gè)樣本偏向?qū)α⒚娴某潭龋床町惗群蛯?duì)立度的轉(zhuǎn)化度量。

2.2 新型雙鄰域粗糙集模型

定義9給定混合值不完備數(shù)據(jù)集構(gòu)成的決策系統(tǒng)I=(U,A?D,V,f),B?A，記B上關(guān)于樣本xi∈U的β-劃分鄰域?yàn)?/p>

其中CDD 為無參數(shù)鄰域聯(lián)系度距離函數(shù)；β∈[ 0,1) 為異質(zhì)度，即鄰域樣本中與xi不同類別的樣本數(shù)量占比；是異質(zhì)度為β時(shí)樣本xi的鄰域半徑，則xi基于β-劃分鄰域的上、下近似鄰域定義為

其中下近似鄰域半徑=CDD(xi,NM(xi))-(CDD(xi,HM(xi))+η),上近似鄰域半徑=CDD(xi,FM(xi)),NM(xi)為到xi的最近不同類樣本，HM(xi)為到xi的最近同類樣本，F(xiàn)M(xi)是使xi的鄰域異質(zhì)度為r且鄰域樣本數(shù)量最大的樣本，r∈(0,1) ；η為調(diào)整系數(shù)，文中取η=0.0001,是對(duì)最近同類樣本與最近異類樣本距離相同時(shí)的調(diào)整。

定義10給定混合不完備數(shù)據(jù)集樣本構(gòu)成的論域U,

分別稱為下近似鄰域粒度集和上近似鄰域粒度集，并記(U,N*)和(U,N*)為下、上近似鄰域空間。

定義11對(duì)X?U,則X的下近似和上近似分別定義為

定義12稱(N*X,N*X)為X的新型雙鄰域粗糙集。

3 基于無參數(shù)鄰域聯(lián)系度距離的新型雙鄰域粗糙集規(guī)則約簡(jiǎn)方法

定義13［14］記C={δ(x1),δ(x2),…,δ(xn)}為論域U的點(diǎn)覆蓋，則稱U,C為鄰域覆蓋空間，U,C,D則稱為鄰域覆蓋決策系統(tǒng)。

定義14［14］U,C,D為鄰域覆蓋決策系統(tǒng)，Xi為決策類，如果?δ(x'i)∈C,使得δ(x'i)?δ(xi)?Xi則稱δ(x'i)對(duì)于Xi是可約的，否則是不可約的。

定義15［14］給定U,C,D，對(duì)于任意決策類Xi，都不存在δ(x'i)∈C使得δ(x'i)?δ(xi)?Xi，則稱U,C,D是不可約的，否是可約的。

定義16［14］U,C,D為鄰域覆蓋決策系統(tǒng)，C'?C為去掉冗余覆蓋后得到的一個(gè)新的覆蓋，且U,C',D不可約，則稱C'是C的相對(duì)約簡(jiǎn)。

定義13—定義16 介紹了基于覆蓋約簡(jiǎn)的粗糙集規(guī)則約簡(jiǎn)理論，本文基于該理論給出新型雙鄰域粗糙集規(guī)則約簡(jiǎn)方法。

算法1新型雙鄰域粗糙集規(guī)則約簡(jiǎn)算法

輸入：I=(U,A?D,V,f);

輸出：約簡(jiǎn)后的下、上近似規(guī)則集R1和R2Step1: 對(duì)?xi∈U構(gòu)造{δ*(xi),δ*(xi)},計(jì)算和，同時(shí)計(jì)算上、下近似鄰域的樣本數(shù)量，并按降序排序。

Step2：?→R1和?→R2，并設(shè)C*=?{δ*(xi)}和C*=?{δ*(xi)}

Step3:執(zhí)行以下操作，獲得R1。

ifC*=?，則輸出R1

else 記

則R1?(xk,,dk)→R1，這里dk表示xk的類別。if?δ*(xp)∈C*使得δ*(xp)?δ*(xk)，則?→δ*(xp)，end，?→δ*(xk)

end

Step4：執(zhí)行以下操作，獲得R2。

ifC*=?，則輸出R2

else 記

則R2?(xk,,dk)→R2，這里dk表示xk的類別。if ?δ*(xp)∈C*使得δ*(xp)?δ*(xk)，則?→δ*(xp)，end,?→δ*(xk)

end

4 基于無參數(shù)鄰域聯(lián)系度距離的新型雙鄰域粗糙集規(guī)則最近鄰分類方法

算法1 獲得了新型雙鄰域粗糙集約簡(jiǎn)后的下、上近似規(guī)則集R1和R2，下面基于最近鄰思想，給出新型雙鄰域粗糙集規(guī)則的最近鄰分類方法。

算法2新型雙鄰域粗糙集規(guī)則最近鄰分類算法

輸入：測(cè)試集Test={x1,x2,…,xm}和R1,R2;

輸出：測(cè)試集對(duì)應(yīng)的分類結(jié)果。

Step1：針對(duì)每個(gè)xi∈Test，計(jì)算它到下近似規(guī)則集(xj,,dj)和上近似規(guī)則(xt,,dt)的無參數(shù)鄰域聯(lián)系度距離CDD(xi,xj)和CDD(xi,xt)

其中：j=1,2,…,|R1|,t=1,2,…,|R2|.

Step2：執(zhí)行以下步驟獲得xi的類別：

if ?k使得CDD(xi,xk)≤，則xi的類別為dk(1 ≤k≤|R1|)

else if ?l使得CDD(xi,xl)≤，則將所有的(xl,,dl)加入到候選集OC中。記OC中到xi的距離最小的規(guī)則是(xk,,dk)，則xi的類別為dk(1 ≤l≤|R2|)

else記

Δ(xk)=min{CDD(xi,xj)-}，則xi的類別為dk(1 ≤j≤|R1|)

end

5 實(shí)驗(yàn)分析

從美國(guó)加州大學(xué)公開的公共測(cè)試數(shù)據(jù)集（簡(jiǎn)稱UCI數(shù)據(jù)集）中下載7個(gè)數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)，具體信息見表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集描述

表1的7 個(gè)數(shù)據(jù)集中只有Heart 不含缺失值，其他6個(gè)數(shù)據(jù)集均存在不同程度的缺失。數(shù)據(jù)集的類別標(biāo)簽有兩類和多類，屬性類型有單純的數(shù)值屬性和離散屬性，也有同時(shí)存在數(shù)值和離散兩種類型的混合屬性。因此，實(shí)驗(yàn)選取的數(shù)據(jù)集具有廣泛性和代表性。

基于Matlab 2011B 進(jìn)行編程實(shí)驗(yàn)。針對(duì)數(shù)值屬性值，采用極差法標(biāo)準(zhǔn)化為［0，1］之間，離散屬性則不做標(biāo)準(zhǔn)化處理。通過10 次交叉檢驗(yàn)法計(jì)算實(shí)驗(yàn)分類精度。新型雙鄰域粗糙集模型近似鄰域半徑依據(jù)定義9的公式計(jì)算，并且鄰域異質(zhì)度r=0.05。

由于數(shù)值屬性值全部標(biāo)準(zhǔn)化為［0，1］之間，而離散屬性雖然屬于分類型變量，但是取值均為整數(shù)。數(shù)值型屬性值之間的差在［0，1］之間，離散型屬性值之間的差要么等于0，即相似的情形；要么大于等于1，即相異的情形。因此相容鄰域半徑ε的值在（0，1）區(qū)間內(nèi)選取，不管是離散屬性還是數(shù)值屬性都是適用的。本文中ε取值區(qū)間為［0.05，0.3］，間隔為0.05，取10次交叉檢驗(yàn)分類精度的最優(yōu)值進(jìn)行比較，相關(guān)實(shí)驗(yàn)對(duì)比結(jié)果如表2所示。

表2 幾種距離函數(shù)分類精度對(duì)比實(shí)驗(yàn)結(jié)果

其中HEOMA 和HEOMB 分別為混合距離HEOM 中缺失值用最悲觀值0 和最樂觀值1 來代替的兩種形式。文獻(xiàn)［24］的距離函數(shù)為帶參數(shù)的鄰域聯(lián)系度距離，本文的是不帶參數(shù)的鄰域聯(lián)系度距離。通過表2可以看出，缺失比例小于1%的4 個(gè)數(shù)據(jù)集，他們的分類效果相差不大。在缺失比例介于5.63%～9.78%的3個(gè)數(shù)據(jù)集中，文獻(xiàn)［24］的方法略優(yōu)于HEOMA 距離，相對(duì)于HEOMB 距離來說，則具有顯著優(yōu)勢(shì)。本文的方法，無論是缺失比例小于1%的數(shù)據(jù)集，還是缺失比例在5.63%～9.78%之間的數(shù)據(jù)集，總體上分類效果與文獻(xiàn)［24］的方法相當(dāng)。值得說明的是，文獻(xiàn)［24］定義的鄰域聯(lián)系度距離函數(shù)存在3個(gè)參數(shù)，需要通過大量的實(shí)驗(yàn)才能確定，在應(yīng)用中會(huì)受到相當(dāng)大的影響。本文方法對(duì)文獻(xiàn)［24］的函數(shù)進(jìn)行了拓展定義，給出了無參數(shù)的鄰域聯(lián)系度距離函數(shù)定義，其顯著的優(yōu)勢(shì)就是不再需要通過大量實(shí)驗(yàn)去確定這些參數(shù)取值，極大拓展了其應(yīng)用范圍。

6 結(jié)語

本文給出了一種新型的雙鄰域粗糙集分類方法。該方法的顯著特點(diǎn)是通過定義一個(gè)無參數(shù)的鄰域聯(lián)系度距離代替了原來帶參數(shù)的鄰域聯(lián)系度距離。在分類效果方面與原來帶參數(shù)的相當(dāng)，然而原來帶參數(shù)的鄰域聯(lián)系度距離需要通過大量實(shí)驗(yàn)來確定參數(shù)值，在實(shí)際應(yīng)用中受到極大限制，這也是本文分類方法的優(yōu)勢(shì)和創(chuàng)新所在。將無參數(shù)鄰域聯(lián)系度距離函數(shù)應(yīng)用于更多的數(shù)據(jù)挖掘與分析模型，拓展其應(yīng)用場(chǎng)景，將是一個(gè)非常有意義的工作，也是我們下一步計(jì)劃的研究和拓展方向。