基于隸屬度的模糊加權k 近質心近鄰算法

劉利，張德生，肖燕婷

（西安理工大學 理學院，西安 710054）

0 概述

分類任務［1］是利用已知類別的樣本通過建立模型預測新樣本的類別［2］。分類是數據挖掘中最重要的任務之一，應用十分廣泛。目前，常用的分類算法主要有決策樹［3］、貝葉斯分類器［4］、人工神經網絡［5］、支持向量機［6］、k 近鄰（k-Nearest Neighbor，KNN）算法［7］等。這些已有的分類算法及其改進算法被廣泛地應用于各個領域，如統計學［8］、醫學［9］、模式識別［10］、決策理論［11］等。KNN 算法的基本思想［12］是通過已知類別的訓練樣本尋找待測樣本的k個近鄰，將k個近鄰中出現頻率最高的類別作為待測樣本的類別。由于KNN 算法具有理論簡單、易于操作等優點，被認為是數據挖掘中最簡單的方法之一［13］。但是，KNN 算法也存在不足：第1 個問題是它沒有考慮樣本的分布，當樣本分布不均勻或樣本中存在噪聲樣本時，分類精度會明顯下降；第2 個問題是所有訓練樣本具有同等重要性，判斷待分類樣本的類別時沒有考慮k個近鄰的區別；第3 個問題是使用單一的多數投票原則進行分類決策。以上3 個問題都會影響分類的準確率及效率。

針對KNN 算法存在的問題，很多研究者提出了不同的改進算法。文獻［14］提出了k 近質心近鄰（k-Nearest Centroid Neighbor，KNCN）算法，該算法的設計思想是近鄰點要盡可能地離待分類樣本近，而且近鄰點要均勻地分布在待分類樣本周圍，通過這些近鄰點所屬類別判斷待測樣本的類別。文獻［15］提出了一種基于局部權重的k 近質心近鄰算法LMKNCN，該算法的設計思想是為k個近質心近鄰賦予不同的權重，再通過決策函數對每個測試樣本進行分類。文獻［16］將模糊理論與KNN 相結合，提出了模糊k 近鄰（Fuzzy k-Nearest Neighbor，FKNN）算法，該算法的基本思想是為訓練樣本分配隸屬度，根據k個近鄰樣本的隸屬度和距離的權重，通過最大隸屬度原則確定待分類樣本的類別。文獻［17］提出了自適應k值的FKNN 算法，該算法的設計思想是通過改進的粒子群算法自適應優化k值和模糊強度參數m，從而提高算法性能。文獻［18］將KNCN 算法和FKNN 算法相結合，提出了模糊k 近質心近鄰（Fuzzy KNCN，FKNCN）算法，該算法的設計思想是使用近質心近鄰的概念來確定最近鄰，并使用模糊理論為每個類分配隸屬度，同時解決了樣本分布和權重問題。文獻［19］提出了基于Bonferroni 均值的FKNCN 算法，該算法的設計思想是運用均值算子和近質心近鄰概念，計算最近的局部Bonferroni 均值向量確定待分類樣本的類別標簽，該算法對異常值具有很好的魯棒性。

然而，上述FKNCN 算法及其改進算法在計算訓練樣本的隸屬度時沒有考慮訓練樣本中存在的噪聲點或離群點，這在小樣本數據集中會大幅降低分類精度。同時，算法忽略了訓練樣本特征的差異性，沒有進行特征選擇，影響了分類性能。針對這2 個問題，本文對FKNCN 算法進行改進，提出基于隸屬度的模糊加權k 近質心近鄰算法MRFKNCN。設計新的隸屬度函數計算訓練樣本的隸屬度，區分訓練樣本中存在的噪聲或離群樣本與有效樣本。在此基礎上，通過基于冗余分析的Relief-F 算法計算每個特征的權重，刪去較小權重所對應的特征和冗余特征，選出重要特征后根據加權歐氏距離選取k個有代表性的近質心近鄰，并確定待測樣本的類標號。

1 預備知識

1.1 符號說明

本文算法所使用的符號說明見表1。

表1 符號說明Table 1 Symbol description

1.2 FKNCN 算法

假定在p維特征空間中，訓練樣本集T=有M個類標簽c1,c2,…,cM，給定一個待測樣本點y，FKNCN 算法步驟如下：

步驟1利用式（1）計算待測樣本y與所有訓練樣本間的歐氏距離，進行升序排列，選擇最短距離所對應的訓練樣本作為第1 個近質心近鄰點

步驟2當r=2,3,…,k時，利用式（2）計算T（iTi表示除去被選為近質心近鄰的訓練樣本之外所有剩余的訓練樣本）中的訓練樣本與之前所選的r-1 個近質心近鄰的質心：

步驟3利用式（3）計算訓練樣本的質心與待測樣本間的最短距離，選取所對應的訓練樣本作為第r個近質心近鄰：

利用式（5）和式（6）均可計算訓練樣本的隸屬度。一般而言，優先選擇式（6）計算其隸屬度［18］，原因在于該計算方式引入了模糊理論，將訓練樣本的隸屬度模糊化，通過訓練樣本的k個近鄰確定其隸屬度，能夠確保訓練樣本在自己的類中被賦予較高的權重，而在其他類中被賦予較低的權重。

步驟5通過最大的模糊隸屬度值判斷待測樣本y的所屬類別，如式（7）所示：

步驟6對于一個新的待測樣本點，重復步驟1～步驟5。

1.3 特征的相關性度量

定義1皮爾遜相關系數［20］

設p維空間中的2 個樣本點e=(e1,e2,…,ep)，f=(f1,f2,…,fp)，兩者之間的皮爾遜相關系數的計算公式如式（8）所示：

ref表示特征之間的線性相關性，其取值范圍是[-1,1]，即0 ≤|ref| ≤1，相關系數的絕對值越大，相關性越強，相關系數的絕對值越接近于0，相關度越弱。

2 MRFKNCN 算法

隸屬度函數的設計是FKNCN 算法的關鍵，但FKNCN 算法在計算訓練樣本的隸屬度時，并沒有考慮噪聲點或離群點對分類的影響，同時該算法在計算待測樣本與訓練樣本間的歐氏距離時，把所有訓練樣本的各維特征等同對待，沒有區分它們的重要程度，這些都會影響分類的性能。為此，本文提出基于隸屬度的模糊加權k 近質心近鄰算法MRFKNCN。通過密度聚類思想為訓練樣本設計新的隸屬度函數、利用基于冗余分析的Relief-F 算法計算特征的權重、確定待測樣本的類別這3 個部分克服噪聲點、離群點的影響，同時解決相同特征權重的問題，提高分類的效率和準確率。

2.1 隸屬度函數構造

樣本集中經常會出現噪聲點或離群點，而FKNCN算法在計算訓練樣本的隸屬度時，沒有區分這些樣本與有效樣本，導致所有訓練樣本的隸屬度相同，這會在很大程度上影響分類的準確率。本文采用密度聚類的思想構造最小包圍球。首先計算最小包圍球的類中心和半徑；然后根據訓練樣本在最小包圍球的位置確定其隸屬度；最后根據隸屬度的大小判斷訓練樣本是離群或噪聲樣本還是有效樣本。計算最小包圍球類中心和半徑的具體步驟如下：

步驟1計算訓練樣本xj與訓練樣本集中其他樣本的歐氏距離，找到xj的第r個近鄰(xjr,r=1,2,…,k)。

步驟2根據樣本xj的k個近鄰構造n×k的密度矩陣D=(d(xj,xjr))n×k。

步驟3利用式（9）計算所有樣本的密度ρ(xj)：

步驟4選擇最大密度樣本點xmax，并找出離該點最近的樣本點xn_max，通過這2 個點確定最小包圍球的類中心O(T)：

步驟5利用式（10）計算最小包圍球的半徑：

其中：λ為自定義的懲罰因子；δ為半徑調整系數；a(T)為類中心到所有樣本點距離的平均值。

計算出樣本集中最小包圍球的類中心和半徑后，利用式（12）確定訓練樣本的隸屬度：

其中：d(xj)為訓練樣本xj與最小包圍球類中心O(T)的歐氏距離。從式（12）可以看出，訓練樣本離最小包圍球的類中心越遠，該訓練樣本的隸屬度就越小。如果訓練樣本位于最小包圍球之內，其隸屬度都大于0.3；反之，位于最小包圍球之外的訓練樣本，其隸屬度都小于等于0.3。位于最小包圍球之外的樣本一般都為離群或噪聲樣本。本文構造最小包圍球方法簡單有效，原因在于其只需計算最小包圍球的類中心和半徑，再通過式（12）為離群或噪聲樣本賦予較小的隸屬度，即可快速區分出離群或噪聲樣本與有效樣本。

2.2 基于冗余分析的Relief-F 算法

本節提出基于冗余分析的Relief-F 特征選擇算法計算每個特征的權重。首先將FKNCN 算法中的歐氏距離改為特征加權的歐氏距離；然后通過加權歐氏距離確定待測樣本的近質心近鄰；最后通過近質心近鄰的隸屬度和距離加權確定待測樣本的類隸屬度。

2.2.1 特征權重的計算

在分類過程中，并不是所有的特征都與分類強相關，也會存在一些不相關特征及冗余特征。如果在分類時不處理這些特征，會出現計算成本高、分類性能低等問題。為了得到最優特征子集，特征選擇是必不可少的。Relief-F 算法［21］是最成功的特征選擇方法之一，算法的具體步驟如下：

1）對所有特征歸一化處理：

2）從訓練集中隨機選擇樣本點xj，找出xj同類的k個最近鄰樣本集和不同類的k個樣本集。

3）通過式（14）計算每個特征的特征權重［22］：

其中：diff(Al,xj,Hr)表示樣本xj與Hr在第l個特征上的距離；diff(Al,xj,Mr(c))表示樣本xj與Mr(c) 在第l個特征上的距離；p(c)表示屬于類別c的樣本出現的概率。

雖然Relief-F 算法在處理多分類問題時效率高并且能夠很好地剔除不相關特征，但不能過濾冗余特征。為此，本文在Relief-F 算法的基礎上提出基于冗余分析的Relief-F 特征選擇算法計算所有特征的權重，算法描述如下：

算法1基于冗余分析的Relief-F 算法

輸入訓練集T，樣本抽樣次數α，最近鄰樣本個數k

輸出每個特征的特征權重w

步驟1所有特征歸一化處理。

步驟2將所有特征權重置0。

步驟3在T中隨機選擇樣本點xj。

步驟4找到與xj同類的k個最近鄰樣本集Hr。

步驟5每個類c≠class(xj)，找到與xj不同類的k個最近鄰樣本集Mr(c)。

步驟6更新每個特征的特征權重。

步驟7根據特征權重閾值，選擇分類權重最大的特征集合。

步驟8冗余分析。利用皮爾森相關系數計算特征之間的相關性。

以上步驟是在一次抽樣下計算每個特征的特征權重，經過α次抽樣后，將特征權重更新α次，并設置一個特征權重閾值Γ，將每個特征權重與總特征權重的比值累積，選擇累積特征權重比大于閾值Γ的特征作為新特征，并刪掉剩余的不相關特征，然后分析新特征之間的相關性，在特征相關性較大的情況下保留權重較高的特征，消除權重較低的特征，目的是消除冗余特征的干擾。通過基于冗余分析的Relief-F 算法計算特征權重，同時減少特征的數量、降低維數，從而完成特征選擇。

2.2.2 加權歐氏距離的計算

利用式（15）計算待測樣本y與訓練樣本xj的加權歐氏距離，從而確定待測樣本的k個近質心近鄰：

2.2.3 待分類樣本類別的確定

計算出每個特征的特征權重后，利用式（16）計算待測樣本y屬于每個類別的隸屬度值：

得到待測樣本y屬于每個類別的隸屬度后，通過最大隸屬度原則確定待測樣本y的類別。

2.3 算法描述

MRFKNCN 算法的設計思想為：首先計算訓練樣本的隸屬度；然后計算所有特征的權重，并找出k個近質心近鄰；最后計算待測樣本的模糊隸屬度，通過最大隸屬度原則確定待測樣本的類別。具體步驟如算法2 所示，算法流程如圖1 所示。

圖1 MRFKNCN 算法流程Fig.1 Procedure of MRFKNCN algorithm

算法2MRFKNCN 算法

輸入近質心近鄰個數k，待測樣本點y，訓練樣本集T，模糊強度參數m

輸出待測試樣本y的類別

步驟1利用式（9）計算訓練樣本的密度。

步驟2利用式（10）和式（11）計算最小包圍球的類中心和半徑。

步驟3利用式（12）計算訓練樣本隸屬度。

步驟4通過基于冗余分析的Relief-F 算法計算所有特征的權重。

步驟5利用式（15）計算待測樣本與訓練樣本之間的加權歐氏距離，找出k個近質心近鄰集合。

步驟6利用式（16）計算待測樣本的模糊隸屬度。

步驟7根據最大隸屬度原則確定待分類樣本的類別。

2.4 算法復雜度分析

假設n表示數據集的規模，p表示特征維數，k表示近鄰個數，M表示類別個數。基于隸屬度的模糊k 近質心近鄰算法的時間復雜度主要來源于以下5 個部分：1）通過密度聚類思想計算訓練樣本的隸屬度，時間復雜度為O(np)；2）計算每個特征的特征權重，時間復雜度為O(npμ)；3）計算訓練樣本的質心，時間復雜度為O(nk)；4）待測樣本到各個類的加權距離，時間復雜度為O(np)；5）通過最大隸屬度原則確定待測樣本的類別，時間復雜度為O(M)。因此，MRFKNCN 算法總的時間復雜度為O(2np+nk)。

3 仿真實驗與分析

3.1 數據集

為驗證本文MRFKNCN 算法的有效性，選用UCI 和KEEL 中的11 個標準數據集和4 個含噪數據集進行仿真實驗，所有實驗都在Matlab2014b 的環境下完成。表2、表3 列出了實驗中所用數據集的相關信息。

表2 標準數據集Table 2 Standard data sets

表3 含噪數據集Table 3 Datas sets with noise

3.2 算法參數設置

為了更好地測試各算法的分類效果，對本文算法所使用的相關參數進行調優。

參考文獻［23］，取λ=2，δ=0.14 計算最小包圍球的半徑。計算完特征權重后，需要設置一個閾值Γ?(0,1)［22］。對本文的數據集進行多次試驗可知，當Γ=0.8 時，選出的新特征最具有代表性，模糊強度參數m=2，當模糊隸屬度值與距離平方成反比時，在分類過程中會得到最優結果［18］。

3.3 實驗結果與分析

本節設計了4 個實驗來驗證MRFKNCN 算法的有效性，將分類的準確率作為評價標準，比較本文算法與其他算法的性能。準確率的計算方法如下：

其中：Nc為正確分類的樣本個數；Nt為實際分類的樣本個數。

對于樣本總數較小的數據集，通過10 次5 折交叉驗證進行實驗；對于樣本總數大的數據集，通過10 次10 折交叉驗證進行實驗，最后將所有實驗得到的準確率平均值作為測試結果。實驗1～實驗3 均采用交叉驗證法確定最優k值。

3.3.1 MRFKNCN 算法總體性能分析

實驗1為驗證本文所提的新的隸屬度函數在噪聲點或離群點影響下的有效性，將MRFKNCN 算法與利用式（5）計算隸屬度的FKNCN算法（命名為FKNCN1）及利用式（6）計算隸屬度的FKNCN 算法（命名為FKNCN2）進行比較，運用表3 含噪數據集。實驗結果如表4 所示。

表4 MRFKNCN 與FKNCN 算法的平均準確率Table 4 Average accuracy of MRFKNCN and FKNCN algorithms %

表4 結果表明，當訓練集中含有噪聲點或離群點時，MRFKNCN 算法的平均準確率明顯高于FKNCN1算法和FKNCN2 算法，在Iris、Vehicle、Wine、Letter 這4 個含噪數據集上，MRFKNCN 算法的平均準確率比FKNCN1 算法分別提高4.48、3.16、3.64、2.86個百分點，比FKNCN2算法分別提高3.26、3.92、2.69、2.33 個百分點，這表明本文所設計的新隸屬度函數可以很好地識別出訓練樣本集中的噪聲點或離群點，尤其是在Iris 小數據集中，MRFKNCN 算法獲得了較高的準確率。

實驗2為驗證基于冗余分析的Relief-F 算法計算特征權重方法的有效性，將MRFKNCN 算法與未加權歐氏距離的MRFKNCN 算法（命名為MRFKNCN_N）、確定統一特征權重的MRFKNCN 算法（命名為MRFKNCN_U）進行對 比，運用 表3 中Arrhythmia、Segment、Zoo、Balance、Thyroid 這5 個數據集，3 種算法的平均準確率結果如圖2 所示。

圖2 3 種算法平均準確率對比Fig.2 Comparison of average accuracy of three algorithms

圖2 結果表明，5 個數據集中MRFKNCN 的分類準確率都明顯優于MRFKNCN_N 算法和MRFKNCN_U算法，說明不同的特征有不同的貢獻率。因此，為了保證算法的準確率，應分別確定每個樣本特征的權重，區分其差異，從而提高分類的性能。

實驗3在最優k值下比較MRFKNCN、KNN［13］、KNCN［14］、LWKNCN［15］、FKNN［16］、FKNCN［18］和BMFKNCN［19］算法的分類平均準確率，所得結果如表5所示，其中加粗數字為最優值。

表5 最優k 值下MRFKNCN 與其他6 種算法的平均準確率Table 5 Average accuracy of MRFKNCN and other six algorithms under optimal k value %

表5 結果表明，雖然在Thyroid 數據集中，BMFKNCN算法取得了較高的準確率，但是MRFKNCN算法的準確率仍高于其他5 種對比算法。MRFKNCN算法在其余10 個數據集中的準確率都高于其他6 種對比算法的準確率，尤其是在Movement、Arrhythmia、Multivariate 這3 個高維數據集上的準確率大幅提升，說明MRFKNCN 算法不僅可以去除噪聲樣本對分類性能的影響，還可以選出有代表性的特征提高分類的準確率。同時，MRFKNCN 算法在11 個數據集中獲得了最高的平均準確率。

3.3.2 MRFKNCN 算法在不同k值下的性能分析

實驗4為了驗證MRFKNCN 算法在不同k值下的分類性能，將MRFKNCN 算法與6 個對比算法在k=1～15時進行比較。運用表3的Hayes-roth、Ecoli、Glass、Sends、Cleveland 這5 個數據集。圖3～圖7 給出了7 種算法的分類準確率對比折線圖。

圖3 在Hayes-roth 數據集上的實驗結果Fig.3 Experimental results on the Hayes-roth dataset

圖4 在Ecoli 數據集上的實驗結果Fig.4 Experimental results on the Ecoli dataset

圖5 在Glass 數據集上的實驗結果Fig.5 Experimental results on the Glass dataset

圖6 在Sends 數據集上的實驗結果Fig.6 Experimental results on the Sends dataset

圖7 在Movement 數據集上的實驗結果Fig.7 Experimental results on the Movement dataset

4 結束語

針對FKNCN 算法未區別樣本特征的不足，本文提出基于隸屬度的模糊加權k 近質心近鄰算法MRFKNCN。利用密度聚類思想設計新的隸屬度函數計算訓練樣本的隸屬度，通過基于冗余分析的Relief-F 算法計算每個特征的權重，刪去不相關特征和冗余特征，選出重要的特征，并利用加權歐氏距離選取k個近質心近鄰，最終根據最大隸屬度原則對待測樣本進行分類。該算法有效解決了訓練樣本中存在噪聲樣本或離群樣本的問題，而且還為每個特征賦予不同的權重，更符合分類的實際情況。實驗結果表明，MRFKNCN 算法在分類性能上明顯優于其他對比算法。由于FKNCN 算法對參數k和模糊強度因子m敏感也會影響分類性能，因此下一步將研究如何自適應地優化FKNCN 算法的參數k和模糊強度因子m，進一步提高算法準確率。