基于鄰域區(qū)分度的不完備混合數(shù)據(jù)屬性約簡方法

孫 林，李夢夢，徐久成

(河南師范大學(xué) 計算機與信息工程學(xué)院，新鄉(xiāng) 453007)

隨著大數(shù)據(jù)處理技術(shù)的發(fā)展，屬性約簡在數(shù)據(jù)挖掘、機器學(xué)習(xí)等領(lǐng)域中發(fā)揮著非常重要的作用[1].在日常生產(chǎn)生活中，由于數(shù)據(jù)采集過程中存在測量誤差、設(shè)備故障、人為遺漏等意外因素，導(dǎo)致出現(xiàn)大量的屬性值缺失的不完備數(shù)據(jù)[2].在實際應(yīng)用中，符號型和數(shù)值型混合的不完備決策系統(tǒng)也是一種常見的信息系統(tǒng)類型[3-4].鄰域粗糙集理論[5]是一種處理混合型不完備決策系統(tǒng)的常用有效模型[6-7].文獻(xiàn)[8]針對不完備混合型決策表，提出了一種基于鄰域容差條件熵的鄰域粗糙集特征選擇算法.文獻(xiàn)[3]結(jié)合Lebesgue測度和熵度量，提出了不完備混合鄰域決策系統(tǒng)的特征選擇算法.但是，上述處理不完備數(shù)據(jù)的屬性約簡模型仍存在沒有實施更有效的度量機制，未能精準(zhǔn)評估屬性集之間的依賴關(guān)系，以及算法效率偏低等問題.

信息系統(tǒng)的區(qū)分度是一種非常有效的屬性集度量函數(shù).文獻(xiàn)[9]定義可區(qū)分度來度量信息系統(tǒng)中屬性重要性，設(shè)計了一種啟發(fā)式約簡算法，并通過實驗證明了基于區(qū)分度屬性約簡算法的高效性.文獻(xiàn)[10]基于矩陣構(gòu)造區(qū)分度，提出了一種增量式屬性約簡算法.文獻(xiàn)[11]針對混合數(shù)據(jù)提出了基于鄰域區(qū)分度的增量式屬性約簡算法.因此，區(qū)分度是構(gòu)造屬性約簡的一種重要度量方法，不僅可以更加準(zhǔn)確地度量屬性集之間的依賴關(guān)系，而且具有計算時間復(fù)雜度低的優(yōu)勢[11].但是，目前還未有利用區(qū)分度進(jìn)行不完備混合數(shù)據(jù)屬性約簡的研究，因此，將文獻(xiàn)[9]的符號型信息系統(tǒng)中的區(qū)分度概念推廣到不完備混合型信息系統(tǒng)中.

首先利用鄰域粗糙集模型既能分析數(shù)值型數(shù)據(jù)，又能處理符號型與數(shù)值型的混合數(shù)據(jù)的優(yōu)勢，針對不完備混合數(shù)據(jù)，構(gòu)建不完備混合鄰域決策系統(tǒng)；基于Relief 算法的diff函數(shù)定義新的距離函數(shù)，分別處理離散型屬性、數(shù)值型屬性和屬性值缺失情況；并給出鄰域、鄰域容差關(guān)系、鄰域上下近似集等概念，進(jìn)而構(gòu)建不完備混合數(shù)據(jù)的鄰域粗糙集模型.然后，在不完備混合鄰域決策系統(tǒng)中，基于不完備混合數(shù)據(jù)的鄰域粗糙集模型定義區(qū)分關(guān)系、鄰域區(qū)分度和相對鄰域區(qū)分度概念，理論證明了相關(guān)性質(zhì)及單調(diào)性定理.最后，基于相對鄰域區(qū)分度給出屬性約簡集、內(nèi)部與外部屬性重要度以及核屬性等定義，設(shè)計基于鄰域區(qū)分度的不完備混合數(shù)據(jù)屬性約簡算法.5個低維UCI數(shù)據(jù)集和3個高維基因數(shù)據(jù)集上的仿真實驗結(jié)果表明，所提出的屬性約簡算法在處理不完備混和數(shù)據(jù)集上具有較好的分類性能.

1 不完備混合數(shù)據(jù)的屬性約簡方法

1.1 不完備混合數(shù)據(jù)的鄰域粗糙集

假設(shè)不完備混合鄰域決策系統(tǒng)表示為IMNDS=，其中U={x1,x2,…,xm}；C=C1∪C2為條件屬性集，其中C1為符號型屬性子集，C2為數(shù)值型屬性子集；D為決策屬性集，并且C∩D= ?；V代表各個屬性的值域；f是U×A→V的映射函數(shù)，并且存在f(a,x)=*，即屬性存在缺失值；Δ→[0, ∞]是距離函數(shù)；δ是鄰域半徑參數(shù)且0 ≤δ≤ 1.

傳統(tǒng)的歐氏距離忽略了不同屬性之間的差別，而Relief算法[12]可以通過特征對近距離樣本的區(qū)分能力進(jìn)行評價，原因在于diff函數(shù)能有效地找到最近鄰的樣本集.因此，使用Relief算法中的diff函數(shù)定義一種新的距離函數(shù)作為鄰域粗糙集的距離函數(shù).

定義1在IMNDS= 中，對于xi,xj∈U，a∈C，使用diff函數(shù)計算兩個樣本在屬性上的差異程度，分3種情況描述：

(1)在處理離散型屬性時，距離函數(shù)為：

(1)

(2)在處理數(shù)值型屬性時，距離函數(shù)為：

(2)

(3)在處理屬性值缺失時，距離函數(shù)為：

(3)

定義2在IMNDS=中，B?C，a∈B，對于xi,xj∈U，那么δB(xi)表示xi關(guān)于B的鄰域為：

δB(xi)={xj|xj∈U,diff(a,xi,xj)=

ΔB(f(a,xi),f(a,xj))≤δ}

(4)

定義3在IMNDS=中，B?C，a∈B，那么關(guān)于B的鄰域容差關(guān)系和xi關(guān)于B鄰域容差類分別為：

f(a,xj)∨f(a,xi)=*∨f(a,xj)=

*∨Δ(f(a,xi),f(a,xj))≤δ}

(5)

(6)

定義4在IMNDS= 中，B?C，xi∈X?U，那么B關(guān)于X的鄰域上近似與下近似集分別為：

(7)

(8)

1.2 不完備混合數(shù)據(jù)的鄰域區(qū)分度

定義5在IMNDS=中，B?C，那么B確定的區(qū)分關(guān)系表示為：

DIS(B)={(xi,xj)∈U2|?a∈B,f(a,xi)≠f(a,xj)}

(9)

依據(jù)文獻(xiàn)[11]定義2的原理，從上述定義5可知，在不完備混合鄰域決策系統(tǒng)中，區(qū)分關(guān)系與不可區(qū)分關(guān)系是相反的且是互補的，在此基礎(chǔ)上構(gòu)建鄰域區(qū)分度的概念.

定義6在IMNDS=中，B?C，a∈B，xi∈U，那么a在該系統(tǒng)下的鄰域區(qū)分度為：

(10)

性質(zhì)1在IMNDS= 中，B?C并且B為符號型屬性集，a∈B，那么該鄰域區(qū)分度為：

(11)

證明：由定義7可以直接得到

所以，可知

即NDDB(D)≤NDDC(D).

1.3 基于鄰域區(qū)分度的屬性約簡算法

定義8在IMNDS=中，若R?C是屬性約簡集，那么下式一定成立：

NDDC(D)=NDDR(D)

(12)

NDDC(D)

(13)

定義9在IMNDS=中，a∈B?C，那么a相對于D的內(nèi)部屬性重要度為：

Siginner(a,B,D)=NDDB(D)-NDDB-{a}(D)

(14)

定義10在IMNDS= 中，B?C且存在a∈C-B，那么a相對于D的外部屬性重要度為：

Sigouter(a,C,D)=NDDR∪{a}(D)-NDDR(D)

(15)

定義11在IMNDS=中，B?C，a∈B，如果Sigouter(a,B,D)>0，那么a是B相對于D的一個核屬性，且為必要屬性；否則a為不必要屬性.如果B中每一個屬性a都為必要屬性，那么屬性子集B是獨立的；否則B是不獨立的.

文中采用前向貪心式搜索方法，設(shè)計基于鄰域區(qū)分度的屬性約簡算法(attribute reduction algorithm based on neighborhood discernibility degree, ARNDD)，偽代碼描述如下：

算法1 ARNDD算法輸入:不完備混合鄰域決策系統(tǒng)IMNDS=,給定鄰域半徑δ和距離函數(shù)Δ;輸出:屬性約簡集B.Step1:初始化屬性約簡集B=?;Step2:對于任意xi∈U和a∈C,得到xi的決策類[xi]D;Step3:根據(jù)式(6)計算ΔB(f(a,xi),f(a,xj))?δ,得到xi的鄰域容差類NTδB(xi);Step4:對于屬性a計算出任意樣本xi的|NTBδ(xi)∩[xi]D|,并對其結(jié)果求和;Step5:根據(jù)式(12)計算決策屬性D關(guān)于a的相對鄰域區(qū)分度NDD{a}(D);Step6:根據(jù)式(17)計算屬性a的屬性重要度Sigouter(a,B,D);Step7:搜索屬性重要度最大的屬性,記為a';Step8:如果Sigouter(a',B,D)>0,則B=B∪{a'},并轉(zhuǎn)入Step2;否則轉(zhuǎn)入Step3;Step9:返回屬性約簡集B.

2 實驗結(jié)果與分析

通過仿真實驗測試與分析所提出的屬性約簡算法的分類性能，實驗硬件環(huán)境為Win10、CPU Intel i5-6500 3.20GHz和8G RAM，軟件環(huán)境為MATLAB R2016b和WEKA 3.8.使用的8個公共數(shù)據(jù)集，如表1，所有分類實驗均采用十折交叉驗證.后續(xù)實驗結(jié)果中粗體表示最優(yōu)值.

表1 數(shù)據(jù)集信息描述

2.1 鄰域參數(shù)的選擇

采用Fisher評分方法[13]對3個高維基因數(shù)據(jù)集進(jìn)行初步降維，分別計算不同維度下的分類精度，并選擇合適的維度方便進(jìn)行下一步的屬性約簡.圖1顯示了3個基因數(shù)據(jù)集的分類精度與基因數(shù)量的變化趨勢.依據(jù)圖1結(jié)果，將Colon、Breast和Mll這3個數(shù)據(jù)集的合適的維度分別設(shè)置為50維、100維和200維.

圖1 3個基因數(shù)據(jù)集的基因個數(shù)與分類精度

針對混合數(shù)據(jù)集進(jìn)行歸一化處理，以減少屬性量綱影響[5].鄰域半徑參數(shù)選擇的重要標(biāo)準(zhǔn)是最大限度地平衡分類精度和選擇的屬性個數(shù).在不同分類器下，以0.05為間隔設(shè)置鄰域參數(shù)且δ∈[0.05,1]，選擇的屬性個數(shù)并計算分類精度，通過評估選擇出最佳鄰域參數(shù)值[3].表2為在CART分類器和SVM分類器下5個UCI數(shù)據(jù)集的最佳分類結(jié)果，表3為在KNN分類器和C4.5分類器下3個基因數(shù)據(jù)集的最佳分類結(jié)果.

表2 5個UCI數(shù)據(jù)集在2個分類器下的最佳鄰域參數(shù)和分類精度

表3 3個基因數(shù)據(jù)集在2個分類器下的最佳鄰域參數(shù)和分類精度

2.2 低維 UCI 數(shù)據(jù)集的分類結(jié)果

(1)CART分類器上的實驗結(jié)果與分析

依據(jù)表2選擇的鄰域半徑，對每個數(shù)據(jù)集實施不同程度的隨機缺失處理.圖2展示了不同不完備率下分類精度和約簡個數(shù)的具體變化情況.表4給出了選擇的最優(yōu)分類結(jié)果.

圖2 CART分類器上不同不完備率下5個UCI數(shù)據(jù)集的分類結(jié)果

表4 CART分類器上5個UCI數(shù)據(jù)集的不完備率與分類結(jié)果

根據(jù)表4可知，在5個UCI數(shù)據(jù)集上，ARNDD算法的屬性約簡子集大小均遠(yuǎn)小于原始屬性個數(shù)；在分類精度方面，除了Soy數(shù)據(jù)集，其它4個數(shù)據(jù)集上ARNDD算法均高于0.91.與文獻(xiàn)[16]中的FNPME-FS算法進(jìn)行比較，結(jié)果如表5.

表5 2種算法選擇的屬性個數(shù)的比較

從表5可知，在4個數(shù)據(jù)集上，ARNDD算法的約簡子集個數(shù)比FNPME-FS算法少.因此，在選擇的屬性個數(shù)方面，ARNDD算法得到較小的屬性子集，具備較好的約簡性能.

將ARNDD算法與4種算法(FNCE[14]、IFPR[15]、FSNTDJE[3]和FNPME-FS[16])進(jìn)行對比，結(jié)果如表6.

表6 5種屬性約簡算法在4個UCI數(shù)據(jù)集上的分類精度

從表6可知，在Wdbc和Inno這2個數(shù)據(jù)集上，ARNDD算法的分類精度均優(yōu)于其它4種算法；在Wine數(shù)據(jù)集上，ARNDD算法優(yōu)于FNCE、IFPR和FSNTDJE這3種算法；在Sonar數(shù)據(jù)集上，ARNDD算法優(yōu)于IFPR和FSNTDJE算法.

(2)SVM分類器上的實驗結(jié)果與分析

與CART分類器下的實驗結(jié)果類似，對每個數(shù)據(jù)集進(jìn)行不同程度的隨機缺失處理.圖3為不同不完備率下分類精度和約簡的情況.表7給出了選擇的最優(yōu)分類結(jié)果.根據(jù)表7的結(jié)果可知，ARNDD算法的約簡結(jié)果的大小均遠(yuǎn)小于原始屬性個數(shù)；在分類精度方面，在4個數(shù)據(jù)集上，ARNDD算法均高于0.84.與文獻(xiàn)[17]中的K2NCRS算法進(jìn)行比較，結(jié)果如表8.

圖3 SVM分類器上不同不完備率下5個UCI數(shù)據(jù)集的分類結(jié)果

表7 SVM分類器上5個UCI數(shù)據(jù)集的不完備率與分類結(jié)果

表8 2種屬性約簡算法在3個UCI數(shù)據(jù)集上的分類結(jié)果

根據(jù)表8可知，ARNDD算法在選擇的屬性個數(shù)方面具有較好的效果，并且在分類精度方面是比較接近的.將ARNDD算法與這4種算法(FSIE[18]、HANDI[19]、NCMAR[20]和NMIE[21])進(jìn)行比較，結(jié)果如表9.

表9 5種屬性約簡算法在3個UCI數(shù)據(jù)集上的分類精度

根據(jù)表9的結(jié)果可知，在選擇的屬性個數(shù)方面，ARNDD算法比其它4種算法選擇的屬性個數(shù)都少.在分類精度方面，在Wdbc數(shù)據(jù)集上，ARNDD算法優(yōu)于其他4種算法.從選擇的屬性個數(shù)和分類精度2個指標(biāo)綜合考慮，ARNDD算法的分類能力均優(yōu)于其它4種算法.

根據(jù)上述實驗結(jié)果，可以說明ARNDD算法對低維UCI數(shù)據(jù)集進(jìn)行分類是有效的，文中算法不僅能夠刪除冗余屬性，而且在分類精度方面也具有較好的分類效果.

2.3 高維基因數(shù)據(jù)集的分類結(jié)果

依據(jù)表2選擇合適的鄰域半徑，對每個數(shù)據(jù)集實施不同程度的隨機缺失處理.針對3個高維基因數(shù)據(jù)集，圖4為不同不完備率下選擇的屬性個數(shù)和分類精度結(jié)果.在此基礎(chǔ)上，表10、11分別給出了2個分類器下選擇的最優(yōu)分類結(jié)果.

圖4 2個分類器上不同不完備率下3個基因數(shù)據(jù)集的分類結(jié)果

表10 KNN分類器上3個基因數(shù)據(jù)集的不完備率與分類結(jié)果

表11 C4.5分類器上3個基因數(shù)據(jù)集不完備率與分類結(jié)果

從表10、11可以看出，在選擇的基因個數(shù)方面，在KNN和C4.5分類器上，ARNDD算法選擇的基因個數(shù)均遠(yuǎn)遠(yuǎn)小于原始基因個數(shù).在分類精度方面，在Breast和Mll數(shù)據(jù)集上，ARNDD算法的分類精度還是較好的.

與文獻(xiàn)[3]中的FSNTDJE算法進(jìn)行實驗比較，結(jié)果如表12.針對這3個基因數(shù)據(jù)集，繼續(xù)與FPRA[22]、FRFS[23]、FSNTDJE[3]和IFGAS[15]這5種算法進(jìn)行不同指標(biāo)的比較，實驗結(jié)果如表13.

表12 2個分類器上2種算法在3個基因數(shù)據(jù)集上選擇的基因個數(shù)

從表13可知，在Breast和Mll這2個數(shù)據(jù)集上，ARNDD算法的分類精度均高于其它4種算法；在Colon數(shù)據(jù)集上，ARNDD算法比IFGAS算法高.總之，根據(jù)高維基因數(shù)據(jù)集的分類實驗結(jié)果，ARNDD算法在KNN和C4.5分類器上均能夠取得了良好的分類效果.

表13 KNN分類器上5種算法的特征選擇分類精度比較

3 結(jié)論

針對不完備混合鄰域決策系統(tǒng)，提出了基于鄰域區(qū)分度的屬性約簡方法.首先，根據(jù)不完備混合數(shù)據(jù)之間的關(guān)系定義新的距離函數(shù)，建立了鄰域容差關(guān)系、鄰域上下近似集，構(gòu)建了不完備混合數(shù)據(jù)的鄰域粗糙集模型.在此基礎(chǔ)上，為了更加準(zhǔn)確地度量屬性集之間的依賴關(guān)系，基于鄰域粗糙集定義鄰域區(qū)分度、相對鄰域區(qū)分度概念.最后，基于相對鄰域區(qū)分度設(shè)計一種啟發(fā)式的屬性約簡算法.8個公共數(shù)據(jù)集上的實驗結(jié)果表明，所提出的屬性約簡算法是有效的.