混合不完備數(shù)據(jù)的新型雙鄰域粗糙集分類方法

黃恒秋，陳素霞，翁世洲

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

0 引言

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

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

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

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

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

1 鄰域粗糙集相關概念

1.1 鄰域關系

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

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

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

其中箭頭符號（→）表示關系滿足的條件，星號（*）表示屬性取值為缺失值。

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

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

定義4［15］記樣本xi的Tri-分割鄰域為

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

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

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

定義5閔氏距離［2］

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

定義6混合距離［17］

這里：

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

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

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

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

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

定義8 是對定義7 的拓展，該鄰域聯(lián)系度距離函數(shù)不帶參數(shù)，與定義7 相比還多了后面兩項，表示兩個樣本偏向對立面的程度，即差異度和對立度的轉化度量。

2.2 新型雙鄰域粗糙集模型

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

其中CDD 為無參數(shù)鄰域聯(lián)系度距離函數(shù)；β∈[ 0,1) 為異質度，即鄰域樣本中與xi不同類別的樣本數(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的鄰域異質度為r且鄰域樣本數(shù)量最大的樣本，r∈(0,1) ；η為調(diào)整系數(shù)，文中取η=0.0001,是對最近同類樣本與最近異類樣本距離相同時的調(diào)整。

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

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

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

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

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

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

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

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

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

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

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

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

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

Step2：?→R1和?→R2，并設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 獲得了新型雙鄰域粗糙集約簡后的下、上近似規(guī)則集R1和R2，下面基于最近鄰思想，給出新型雙鄰域粗糙集規(guī)則的最近鄰分類方法。

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

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

輸出：測試集對應的分類結果。

Step1：針對每個xi∈Test，計算它到下近似規(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ù)據(jù)集（簡稱UCI數(shù)據(jù)集）中下載7個數(shù)據(jù)集作為實驗數(shù)據(jù)，具體信息見表1。

表1 實驗數(shù)據(jù)集描述

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

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

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

表2 幾種距離函數(shù)分類精度對比實驗結果

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

6 結語

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