基于影響函數的k-近鄰分類

職為梅 張 婷 范 明

（鄭州大學信息工程學院 鄭州 450052）

基于影響函數的k-近鄰分類

職為梅*張 婷 范 明

（鄭州大學信息工程學院 鄭州 450052）

分類是一種監督學習方法，通過在訓練數據集學習模型判定未知樣本的類標號。與傳統的分類思想不同，該文從影響函數的角度理解分類，即從訓練樣本集對未知樣本的影響來判定未知樣本的類標號。首先介紹基于影響函數分類的思想；其次給出影響函數的定義，設計3種影響函數；最后基于這3種影響函數，提出基于影響函數的k-近鄰（kNN）分類方法。并將該方法應用到非平衡數據集分類中。在18個UCI數據集上的實驗結果表明，基于影響函數的k-近鄰分類方法的分類性能好于傳統的k-近鄰分類方法，且對非平衡數據集分類有效。

數據挖掘；監督學習；非平衡數據集分類；影響函數；k-近鄰

1 引言

分類是一種監督學習方法［1］，已有的研究提出很多經典的分類方法，例如，決策樹歸納［2］、樸素貝葉斯法［3］、神經網絡［4］、支持向量機［5］、k-近鄰（k-Nearest Neighbor，kNN）［6］、基于案例的推理［7］等。這些分類方法的做法相似，即，給定一個訓練集 D，學習一個模型M，對于未知樣本x，由M給出x的類標號。如果沒有類標號已知的樣本和其他先驗知識，則除了隨機猜測之外，沒有更好的方法確定x的類標號。如果沒有類標號已知的樣本，但有某種先驗知識，例如知道每個類出現的概率，則推斷x屬于出現概率最大的類的出錯可能性更小。換句話說，利用先驗知識推斷勝過隨機猜測。如果有已知類標號的訓練樣本集D，則可以在D上訓練一個分類模型M（如決策樹歸納、樸素貝葉斯、神經網絡、支持向量機等）并用M對x分類，或者保留D并直接利用D推斷x所屬的類（如k -近鄰、基于案例的推理等）。借助于訓練樣本集，合理的分類算法遠比隨機猜測和僅利用簡單的先驗知識好得多。

一般的分類算法都是基于訓練數據集學習得到分類器分類未知樣本，因此它們都受到訓練數據集的影響。假設訓練集為空集，不管一個分類算法多么優秀，對于未知樣本，也只能采用隨機猜測的方法分類未知樣本；如果訓練集無限大，包含了所有可能的實例，不管一個分類算法多么糟糕，分類準確率很容易達到百分之百；如果訓練集D非空也沒有包含所有的樣本，那么分類算法基于訓練集學習分類器分類未知樣本?；诖?，可以換個角度理解分類，即分類的過程也就是考察訓練樣本對未知樣本x的影響。訓練集為空，D對x的影響為0，只能隨機猜測未知樣本的類標號；訓練集無限大，一定存在某一個類對x的影響為1，這個類的標號即為x的類標號；如果訓練集為有限集合，假設D只包含了兩個類C1和C2，如果C1類所有訓練樣本對x的影響大于C2類樣本對x的影響，則x的類標號就為C1類。反之亦然。

基于以上分析，和傳統的分類方法不同，從另一個角度看待分類問題，即，從訓練數據集對未知樣本的影響［8］角度出發看待分類。本文從新的角度闡述分類，提出基于影響函數的分類思想，也即，每個訓練實例都對未知樣本有一定的影響，綜合所有訓練樣本對未知樣本的影響，即可判定未知樣本的類標號。嚴格地說，基于影響函數的分類不是一種分類算法，而是一種分類范型。定義不同的影響函數導致不同的分類算法。本文給出了3種影響函數的定義，基于這3種影響函數，提出了基于影響函數的k-近鄰分類方法，UCI數據集上的實驗結果表明，相對于普通的k-近鄰分類方法，該方法可以提高分類的性能。

論文剩余部分組織如下：第2節介紹影響函數的定義，設計3種影響函數，并提出基于影響函數的k-近鄰分類；第3節給出實驗結果及相關評述；第4節給出基于影響函數的k-近鄰分類方法在非平衡數據集上的分類效果；第5節總結全文。

2 基于影響函數的k-近鄰分類

設訓練數據集D包含L個類C1，C2，…，CL，Dl為第l類訓練樣本的集合，x為待分類實例?；谟绊懞瘮捣诸惖幕舅枷胧牵憾x L個實型函數fl（x），l= 1，2，…， L。其中，fl（x）計算Dl中樣本對x的影響。將待分類實例x分配到對x影響最大的類：如果，則把x分配到Cj類。

當只有兩個類（L = 2）時，問題可以簡化為：定義一個實型影響函數f（x）=f1（x）-f2（x），計算D中樣本對x的影響。如果 f（ x ）≥ 0，則把x分配到C1類，否則把x分配到C2類。

k-近鄰分類是一個經典的分類方法［6］，從影響函數的角度更容易理解k-近鄰分類?？紤]未知樣本x的某個領域，比如距離它最近的k個近鄰，定義影響函數，計算這k個近鄰對x的影響，將x劃歸為對它影響最大的那個類。下面就通過定義不同的影響函數，分析基于影響函數的k-近鄰分類方法的性能。

2.1 影響函數的定義

影響函數的定義范圍可以是全局的，也可以是局部的［8］。全局影響函數指每個訓練實例都對 x有影響；局部影響函數指只有x的那些近鄰才對x有影響。全局影響函數也很容易變換成局部影響函數，下面以全局影響函數為例介紹影響函數的定義方法：

（1）定義單個訓練實例 'x對x的影響g（'x，x）；

（2）數據集D對x的影響 fD（x）可以定義為數據集中訓練實例對x的影響的加權和：

其中wi是實例 'x的權重，它反映 'x的重要性。在最簡單的情況下，所有實例都取相等權重。當數據集D為第i類訓練樣本時，fD（x）簡記為fi（x）。

訓練實例 'x對 x的影響 g（'x，x）的定義也有很多種方式，最簡單的，0/1影響：如果 'x和x滿足某個謂詞，則 'x對x的影響為1，否則為0。這里，簡單的“謂詞”可以是“ 'x是x的k個最近鄰之一”，“ 'x在 x的 -ε鄰域內”。更復雜的謂詞可以是，例如，分類規則的前件。除了0/1影響外，本文還設計了3種影響：

（1）線性影響：'x對x的影響隨 'x與x的距離增加而線性減小。

其中，d（'x，x）是 'x與x之間的距離，而dmax是訓練實例之間的最大距離。

（2）平方影響：'x對x的影響隨 'x與x的距離增加而平方減小。

（3）指數影響：'x對x的影響隨 'x與x的距離增加而指數衰減。

其中，α是一個待定常數，用于控制衰減速度。

2.2 算法描述

有了訓練實例對未知樣本的影響函數，可以對傳統的k-近鄰分類方法加以改進，得到基于影響函數的 k-近鄰分類方法，其算法的具體過程見表 1。首先遍歷D得到x的k個近鄰Dz，對于Dz中每個實例 'x，根據影響函數的定義，計算它對x的影響，得到Dz每個類對x的影響函數值fl（x），將x的類標號設為fl（x）最大的那個類。

3 實驗

3.1 數據集和實驗設置

18個數據集從UCI機器學習庫中隨機選?。?］。對于每個數據集，采用5×2折交叉驗證分析算法的性能。數據集的詳細情況如表2所示。所有實驗均基于weka平臺。

表1 算法描述

3.2 實驗結果

實驗時，本文對比了樸素貝葉斯算法［3］（Navie Bayes，NB）、支持向量機算法［5］（Support Vector Machine，SVM）、判定樹算法［2］（Decision Tree，常用的判定樹算法是 C4.5）、神經網絡算法［4］（Neural Network，NN），k-近鄰分類（k-Nearest Neighbor，kNN）、基于線性影響的 k-近鄰分類（Linear Effect kNN，LE-kNN）、基于平方影響的 k-近鄰分類（Square Effect kNN，SE-kNN）和基于指數影響的k-近鄰分類（Exponential Effect kNN，EE-kNN）。kNN，LE-kNN，SE-kNN以及EE-kNN 4四個算法都存在確定k值的問題，傳統的k-近鄰算法，k的值一般為3，因此在實驗中，首先給出k值為3時，kNN，LE-kNN，SE-kNN以及EE-kNN在準確率上的結果，結果如表3所示。基于影響函數的分類中，如果考慮的實例少，效果不太好，為了對比實例多少對算法性能的影響，實驗時改變k值的大小，分別取k為10，25，50，實驗結果分別如表4～表6所示。

由表3可以發現，當k值取3的時候，神經網絡的平均效果最好，支持向量機和神經網絡比kNN的效果都好。而LE-kNN，SE-kNN，EE-kNN和kNN相比，kNN的效果最好，在15個數據集上的準確率值都超過了其他3三個算法，kNN在這18個數據集上的平均準確率值也最高，為80.05，LE-kNN，SE-kNN和EE-kNN的分別為73.84，73.51和79.88。這個結果不難理解，kNN算法通常取值為3，而基于影響函數的kNN算法，如果考慮的實例少時，效果不好。隨著k值的增加，基于影響函數的kNN算法性能變好。

如表4所示，當k取值為10時，仍舊是神經網絡的效果最好，但是LE-kNN和SE-kNN的平均準確率有明顯提高，LE-kNN由 73.84提高到79.97，SE-kNN由73.51提高到79.46。相比于LE-kNN，SE-kNN，EE-kNN的還是性能最好，LE-kNN在這18個數據集上的平均準確率值也最高?？梢钥闯觯琇E-kNN和kNN的性能相差無幾。對比表3和表4可以發現，LE-kNN的性能在上升，而kNN的性能在下降。當k取值為25時，結果如表5所示，SE-kNN的性能最好，在這18個數據集上的平均準確率值也最高，為81.67，LE-kNN，EE-kNN，kNN，NB，SVM，C4.5和 NN的分別為 81.55，76.19，77.07，75.24，80.77，78.29和81.33，很明顯LE-kNN的結果要比kNN，NB，SVM，C4.5和NN都好。對比表3，表4，表5發現，LE-kNN和SE-kNN的性能仍舊上升，kNN的性能仍舊下降。并且LE-kNN和SE-kNN的平均準確率同時超過神經網絡。當k取值為50時，結果如表6所示，SE-kNN的性能仍舊最好，在這18個數據集上的平均準確率值也最高，為 81.54，LE-kNN，EE-kNN，kNN，NB，SVM，C4.5和NN的分別為79.91，73.81，74.33，75.24，80.77，78.29和81.33。

表2 實驗數據集信息

表3～表6的結果表明，隨著k值的增加，LE-kNN和SE-kNN的分類準確率增加，當k值增加到一定大小時，準確率的值也趨于穩定。對于k的取值，本文做了大量的實驗，發現當k的值在20～50時，LE-kNN和SE-kNN的性能最好。達到相同的準確率值時，LE-kNN比SE-kNN取的k值要小一些。同時，還發現了一個有趣的現象，在大多數數據集上，EE-kNN在k值較小時達到最優性能，并且，EE-kNN在大多數數據集上的結果和kNN的結果相似，如表3所示。仔細觀察表3～表6可以發現，當k值很小的時候，LE-kNN，SE-kNN在某些數據集上準確率值很差，比如tic-tac-toe，隨著k值的增加，效果越來越好，當k達到一個特定值后，準確率值不再升高。而EE-kNN正好相反，當k值小的時候它在tic-tac-toe上的準確率值很高，隨著k值的增加，準確率不升反降，這是一個有趣的現象。本文發現，在另外的一些數據集上也存在這樣的現象。

表3 LE-kNN，SE-kNN，EE-kNN及kNN分類準確率的結果（k=3）

表4 LE-kNN，SE-kNN，EE-kNN及kNN分類準確率的結果（k=10）

表5 LE-kNN，SE-kNN，EE-kNN及kNN分類準確率的結果（k=25）

表6 LE-kNN，SE-kNN，EE-kNN及kNN分類準確率的結果（k=50）

表3～表6的實驗結果表明，當影響函數設置得當時，基于影響函數的kNN分類可以提高分類的效果，并且正如所預測的那樣，基于影響函數的kNN，需要一定數目的近鄰來計算影響函數的值，如果考慮的近鄰數目過少，效果不明顯，考慮了足夠多的近鄰時，往往可以極大提高基于影響函數的kNN的分類性能。

3.3 局部性確定

傳統的k-近鄰學習算法通常將其設置為3，但是基于影響函數的k-近鄰算法中，如果k的值很小，意味著影響未知樣本x的訓練樣本少，效果非常差，應該為k選擇一個適當的值。本小節中，本文設計了一組實驗，學習最佳k值，論文隨機選擇兩個數據集作為代表數據集學習最佳k值，分別是breastcancer和cleve。實驗結果如圖1和圖2所示。

圖1和圖2分別給出 3種影響函數在 breastcancer和cleve上的結果。這兩個圖有一個共同特點，即線性影響和平方影響隨著k值的增加性能變好，當k達到一定時（對于線性影響來說通常為25，平方影響為50），準確率趨于穩定。對于指數影響來說，隨著k值的增加性能往往下降，k值在3～10之間性能最好。對于線性影響k值取15～50，對于平方影響k值取20～50。

4 影響函數分類用于非平衡數據集

基于影響函數的k近鄰分類方法通過考察未知樣本x的近鄰對x的影響確定它的類標號，對它影響大的樣本的類標號就是它的類標號，這種分類的思想也適合于非平衡數據集分類，非平衡數據集分類是數據挖掘中的一個難點問題，也是數據挖掘中的一個熱點問題［10-16］。為了驗證基于影響函數的分類對非平衡數據集分類有效，本文選擇了兩個常用的非平衡數據集：breast-cancer和sick（sick數據集的不平衡程度高，故在實驗部分沒有選擇它作為數據集），對比了kNN，LE-kNN，SE-kNN在這些數據集上的分類效果（由3.2節知EE-kNN性能和kNN相似，故在此不再對比EE-kNN），使用非平衡數據集分類常用的衡量標準 f-度量、召回率來衡量分類效果的好壞，并且只給出了少數類上的 f-度量和召回率。結果如圖3和圖4所示。

Breast-cancer數據集有9個屬性，286條實例，包含復發事件（recurrence-events）和非復發事件（no-recurrence-events）兩個類，其中復發事件類為少數類，有85條實例，非復發事件類為多數類，有201條實例。由圖4可以發現，LE-kNN和SE-kNN在復發事件類上的召回率和 f-度量都明顯好于kNN。

sick數據集有 30個屬性，3772條實例，包含negative和sick兩個類，其中sick類為少數類，有231條實例，0類為多數類，有3541條實例。由圖4可以發現，LE-kNN和SE-kNN在sick類上的召回率和f-度量都明顯好于kNN，并且隨著k值的增加，這3個算法的性能都下降。

在這2個數據集上的實驗結果表明基于影響函數的分類方法的確對非平衡數據集分類有效。在此，本文只是簡單的將LE-kNN和SE-kNN算法應用于二元的非平衡數據集分類中（實驗中使用的2個數據集都是二元數據集），我們工作的下一步是設計更好的影響函數，并推廣到多元的非平衡數據集分類中去。

5 總結

圖1 LE-kNN，SE-kNN，EE-kNN在breast-cancer 上的準確率值

圖2 LE-kNN，SE-kNN，EE-kNN在cleve 上的準確率值

圖3 kNN，LE-kNN，SE-kNN 在breast-cancer上的召回率和f-度量

圖4 kNN，LE-kNN，SE-kNN 在sick上的召回率和f-度量

本文從一個新的角度理解分類問題，即，從訓練數據集對未知樣本的影響角度出發看待分類。本文給出了幾種影響函數的定義方法，并將這些影響函數的定義運用到k-近鄰算法中，介紹了基于影響函數的k-近鄰分類方法。通過實驗對比，發現基于影響函數的k-近鄰分類方法的確比普通的k-近鄰分類方法性能好，當選定合適的k值時，基于影響函數的k-近鄰算法并常用的分類算法性能還好。但是基于影響函數的k-近鄰分類算法往往比普通的k-近鄰分類方法需要考慮更多的近鄰。本文中，將基于影響函數的分類方法應用與非平衡數據集分類中，發現該方法對于非平衡數據集分類也有效，我們工作的下一步是設計更復雜的影響函數，并推廣至多元的非平衡數據集分類中去。考慮將基于影響函數分類和支持向量機和神經網絡方法結合起來，進一步提高分類的性能。

［1］ Tan P N and Steinbach M著，范明，范宏建，譯. 數據挖掘入門［M］. 第2版，北京：人民郵電出版社，2011：127-187.

［2］ Quinlan J S. Induction of decision trees［J］. Machine Learning，1986，1（1）：81-106.

［3］ Domingos P and Pazzani M J. Beyond independence：conditions for the optimality of the simple bayesian classifier［C］. Proceedings of the International Conference on Machine Learning，Bari，Italy，1996：105-112.

［4］ Rumelhart D E，Hinton G E，and Williams R J. Learning representations by back-propagating errors［J］. Nature，1986，323（9）：533-536.

［5］ Boser B E，Guyon I M，and Vapnik V N. A training algorithm for optimal margin classifiers［C］. Proceedings of the Conference on Learning Theory，Pittsburgh，USA，1992：144-152.

［6］ Dasarathy B V. Nearest Neighbor （NN） norms：NN Pattern Classification Techniques［M］. Michigan：IEEE Computer Society Press，1991：64-85.

［7］ Leake D B. Experience，introspection and expertise：learning to refine the case-based reasoning process［J］. Journal of Experimental & Theoretical Artificial Intelligent，1996，8（3/4）：319-339.

［8］ Hinneburg A and Keim D A. An efficient approach to clustering in large multimedia databases with noise［C］. Proceedings of the Knowledge Discovery and Data Mining，New York，USA，1998：58-65.

［9］ Bache K and Lichman M. UCI repository of machine learning databases［OL］. http：//www.ics.uci.edu/～mlearn/MLRepository. html. 2014.5.

［10］ Liu X Y，Li Q Q，and Zhou Z H. Learning imbalanced multi-class data with optimal dichotomy weights［C］. Proceedings of the 13th IEEE International Conference on Data Mining，Dallas，USA，2013：478-487.

［11］ He H B and Edwardo A G. Learning from imbalanced Data［J］. IEEE Transactions on Knowledge and Data Engineering，2009，21（9）：1263-1284.

［12］ Maratea A，Petrosino A，and Manzo M. Adjusted F-measure and kernel scaling for imbalanced data learning［J］. Information Sciences，2014（257）：331-341.

［13］ Wang S and Yao X. Multiclass imbalance problems：analysis and potential solutions［J］. IEEE Transactions on Systems，Man and Cybernetics， Part B，2012，42（4）：1119-1130.

［14］ Lin M，Tang K，and Yao X. Dynamic sampling approach to training neural networks for multiclass imbalance classification［J］. IEEE Transactions on Neural Networks and Learning Systems，2013，24（4）：647-660.

［15］ Peng L Z，Zhang H L，Yang B，et al.. A new approach for imbalanced data classification based on data gravitation［J］. Information Sciences，2014（288）：347-373.

［16］ Menardi G and Torelli N. Training and assessing classification rules with imbalanced data［J］. Data Mining and Knowledge Discovery，2014，28（1）：92-122.

職為梅： 女，1977年生，博士生，講師，研究方向為數據挖掘、機器學習、人工智能.

張 婷： 女，1988年生，碩士，研究方向為數據挖掘、機器學習、人工智能.

范 明： 男，1948年生，教授，博士生導師，研究方向為數據挖掘、模式識別、人工智能.

k-nearest Neighbor Classification Based on Influence Function

Zhi Wei-mei Zhang Ting Fan Ming

（College of Information Engineering， Zhengzhou University， Zhengzhou 450052，China）

Classification is a supervised learning. It determines the class label of an unlabeled instance by learning model based on the training dataset. Unlike traditional classification，this paper views classification problem from another perspective，that is influential function. That is，the class label of an unlabeled instance is determined by the influence of the training data set. Firstly，the idea of classification is introduced based on influence function. Secondly，the definition of influence function is given and three influence functions are designed. Finally，this paper proposes k-nearest neighbor classification method based on these three influence functions and applies it to the classification of imbalanced data sets. The experimental results on 18 UCI data sets show that the proposed method improves effectively the k-nearest neighbor generalization ability. Besides，the proposed method is effective for imbalanced classification.

Data mining；Supervised learning；Classification of imbalanced data sets；Influence function；k-Nearest Neighbor （kNN）

TP181

A

1009-5896（2015）07-1626-07

10.11999/JEIT141433

2014-11-13收到，2015-04-03改回，2015-06-01網絡優先出版

國家自然科學基金（61170223）和河南省教育廳科學技術研究重點項目（14A520016）資助課題

*通信作者：職為梅 iewmzhi@zzu.edu.cn