基于K最近鄰樣本平均距離的代價敏感算法的集成

楊浩 王宇 張中原

摘 要：為了解決不均衡數據集的分類問題和一般的代價敏感學習算法無法擴展到多分類情況的問題，提出了一種基于K最近鄰（KNN）樣本平均距離的代價敏感算法的集成方法。首先，根據最大化最小間隔的思想提出一種降低決策邊界樣本密度的重采樣方法;接著，采用每類樣本的平均距離作為分類結果的判斷依據，并提出一種符合貝葉斯決策理論的學習算法，使得改進后的算法具備代價敏感性;最后，對改進后的代價敏感算法按K值進行集成，以代價最小為原則，調整各基學習器的權重，得到一個以總體誤分代價最低為目標的代價敏感AdaBoost算法。實驗結果表明，與傳統的KNN算法相比，改進后的算法在平均誤分代價上下降了31.4個百分點，并且代價敏感性能更好。

關鍵詞：代價敏感;最大化最小間隔;樣本間距離;貝葉斯決策理論;集成

Abstract： To solve the problem of classification of unbalanced data sets and the problem that the general cost-sensitive learning algorithm can not be applied to multi-classification condition， an integration method of cost-sensitive algorithm based on average distance of K-Nearest Neighbor （KNN） samples was proposed. Firstly， according to the idea of maximizing the minimum interval， a resampling method for reducing the density of decision boundary samples was proposed. Then， the average distance of each type of samples was used as the basis of judgment of classification results， and a learning algorithm based on Bayesian decision-making theory was proposed， which made the improved algorithm cost sensitive. Finally， the improved cost-sensitive algorithm was integrated according to the K value. The weight of each base learner was adjusted according to the principle of minimum cost， obtaining the cost-sensitive AdaBoost algorithm aiming at the minimum total misclassification cost. The experimental results show that compared with traditional KNN algorithm， the improved algorithm reduces the average misclassification cost by 31.4 percentage points and has better cost sensitivity.

Key words： cost-sensitive; maximization of minimum interval; distance between samples; Bayesian decision-making theory; integration

0 引言

在機器學習研究過程中，經常存在著樣本類別分布不均衡的情況，傳統的分類器注重于提高分類的準確率，對不均衡數據集的分類結果更傾向于多數類[1]，這種分類方式默認兩種分類錯誤的代價是相等的。然而在很多領域，比如入侵檢測、醫療診斷、欺詐檢測等，少數類的誤分類代價十分巨大，在此類情況中，人們主要關心少數類的分類準確率。傳統的算法無法滿足此類數據的分類需要，于是代價敏感學習的思想被提出并廣泛應用，代價敏感學習方法是解決不均衡數據集分類問題的一個重要方法[2]。代價敏感學習是指對不同的誤分類結果賦予不同的代價，得到一個在對未知樣本進行分類時誤分代價最小的分類器[3]。常見的誤分類代價包括基于類別的代價和基于樣本的代價。在基于類別的代價中，代價只與類別有關，而在基于樣本的代價中，誤分類代價與每一個樣本有關，在現實場景中，基于樣本的代價很難獲得，一般使用基于類別的代價。

一直以來，代價敏感學習算法在國際上都是機器學習和數據挖掘領域的研究熱點。現有的代價敏感學習方法分為兩種[4]：一是基于特定算法的代價敏感學習方法，將優化目標變為得到期望代價最小的假設。例如在決策樹算法中使用代價敏感的葉節點分裂準則以及代價敏感的剪枝策略[5]。二是代價敏感學習元方法，將使期望誤差率最小的學習算法轉變為得到期望代價最小的代價敏感學習算法，常見方法包括重采樣法[6]、閾值移動法[7]、集成學習法[8]。這種方法具備良好的通用性，文獻[9]基于貝葉斯風險最小化原理提出了一種可以將任意的分類器算法轉化為代價敏感算法的MetaCost算法，根據樣本屬于每個類的概率及誤分類代價之積選取出分類代價最小的類別作為樣本分類結果，達到最小誤分代價。目前，一些常見的分類算法，如支持向量機（Support Vector Machine， SVM）、決策樹、神經網絡和AdaBoost都有對應的代價敏感算法[10-13]。MetaCost算法可以將傳統的分類算法轉化為代價敏感學習算法，并且適用于任何數目的樣本類別和任意代價矩陣。

但是，目前的代價敏感學習算法主要針對二分類問題，對于代價敏感的多分類問題的研究不多，一些常見的算法無法擴展到多分類場景中。K最鄰近（K-Nearest Neighbor， KNN）分類算法作為一種成熟的算法，具有魯棒性、概念清晰等優點，算法以K個近鄰樣本的投票數來對未知樣本進行分類，可以直接擴展到多分類場景中。盡管KNN算法的優勢十分明顯，但是它的缺點也不容忽視。KNN算法基于空間向量模型（Vector Space Model， VSM請補充VSM的英文全稱）模型，利用歐氏距離或余弦距離度量樣本的距離，但權重不變，這與實際情況不符，一種改進的方法是加權KNN算法，根據樣本點之間的距離來分配權重，權重的大小隨距離的減小而增大[14]。同時KNN算法在K值的設定方面依賴于經驗，存在著K值單一的情況，而Boosting算法可以集成多個具備不同K值的KNN分類器，有效解決了這一問題[15]。

針對上述問題，本文提出了一種用于不平衡數據集上的近鄰樣本刪減策略以及基于近鄰樣本間距的代價敏感（Cost Sensitive based on average Distance of K-Nearest Neighbor， CSD-KNN）算法，并在此基礎上對此算法按一定策略進行集成。首先，針對多數類的邊界進行選擇性刪減，在新的數據集上算法得到樣本點與K個近鄰樣本的距離，并計算出每一個類中樣本與測試樣本點之間的平均距離，以此作為輸入進行代價敏感變換，得到期望代價最小的代價敏感分類器，最后在具備代價權重初值的AdaBoost算法上集成這種改進后的算法，使之誤分代價最小。在UCI數據集上的測試結果表明改進后算法的平均誤分代價更低。

1 近鄰樣本刪減策略

不均衡數據集會弱化分類器對少數類的分類效果，對樣本集的修改策略是重構數據集，調整樣本分布，使得多數類與少數類的樣本比例趨于1∶1。已有成果表明對分類結果有較大影響的樣本處于樣本邊界[16]，降低邊界處的多數類樣本密度比減少多數類的樣本數量更為切實有效。受支持向量機最大化最小間隔形式化目標的啟發，本文對多數類的邊界樣本進行篩選，減小邊界處多數類樣本的密度，加大多數類與少數類的樣本間隔，降低分類結果受少數類樣本稀疏性的影響。

定義樣本與自身的距離為∞。算法的思想是：確保少數類樣本的最近鄰樣本仍為少數類，即遍歷少數類中的所有樣本，判斷其最近鄰樣本點是否屬于少數類，若不是，則刪除此樣本的最近鄰點，并繼續對此樣本進行判斷，直到此樣本點的最近鄰樣本也屬于少數類。

2 代價敏感的改進算法——CSD-KNN

當樣本被錯分時會產生代價，分為兩種情況：多數類誤分為少數類的代價，以及少數類誤分為多數類的代價。當樣本正確分類時，代價值為0。傳統的學習算法默認兩種誤分類情況是等價的，但是在實際情況中，兩者必須區分開來。代價敏感思想基于期望代價最小的原則對分類器作出調整。MetaCost方法根據樣本屬于每一類的概率與其對應的誤分代價值之積，得到一個具有最小期望代價的分類結果。本文改進了傳統KNN算法中每個樣本權重相等的弊端，基于每一類中近鄰點與樣本之間的平均距離將樣本的誤分代價值以函數的形式表現出來。假設待測樣本Xi與鄰近樣本Xj（j=1，2，…，K）的距離為dij，為了便于說明，這里的dij取歸一化后的數值，屬性的歸一化方法為：

將每一類中近鄰樣本與測試樣本之間的平均距離作為具體的自變量因子，通過對數函數的形式表示基于距離的代價函數，距離越小，誤分代價值越大，并且隨著距離的縮小，樣本的誤分類代價值以指數形式上升。樣本屬性維度值w用來將對數函數的真數的值控制在0～1，避免出現負的代價值。通過樣本屬性維度值w樣本屬性維度值是希臘字母ω，還是英文字符w（式3中寫的是小寫w）？書寫需要統一。將對數函數的自變量取值范圍控制在0到1之間，避免函數值為負。樣本屬性維度值ω用來將對數函數的真數的值控制在0-1之間，避免出現負的代價值。現改為：通過樣本屬性維度值ω將對數函數的自變量取值范圍控制在0-1，避免函數值為負。在這種思想的指導下構造出基于距離的代價函數如下所示：

其中：m為某一類近鄰樣本點的個數;α值為距離對樣本分類的影響因子，值越小表明距離對樣本分類結果影響越大;c為少數類與多數類誤分類代價的比重。

基于最小風險的貝葉斯決策的形式化目標[17]為：

其中：R（yi|x）為樣本x分類到yi中的風險構造函數，F（yi，yj）為類別yi誤分為yj的代價，P（yi|x）為樣本x屬于類別yi的后驗概率。

定理1 在KNN算法中，若K為近鄰樣本的數量，m為樣本中某一類的總體數量，則樣本屬于該類的概率為m/K。

以樣本比例逼近概率：V為K個樣本點包圍的最小超球的體積，m為數據集中類別yi的個數，得到類條件概率密度：

其中N為樣本總數。

因此得到符合貝葉斯決策理論的代價敏感算法——CSD-KNN，表現形式為：

根據文中描述的分類器，具體的實現過程如算法1所示。

3 集成代價敏感的CSD-KNN算法

Boosting算法的基本思想是對每一輪迭代得到的分類器賦予不同的權重，使得分類器更注重分類難度大的樣本，最終得到一個基分類器ht（x）的線性集合H（x）。計算方式為Ht+1（x）=Ht（x）+α*t*ht（x），下標的書寫不規范，t和t+1是否應該為下標，請明確。回復：修改正確傳統的Boosting算法的最大特點是隨著迭代次數的增長，分類錯誤率以指數速度下降。將Boosting算法應用到代價敏感學習中，可以得到以錯分類代價最低為目標的代價敏感分類器，代價敏感的Boosting算法是代價敏感學習方法中的一個重要組成部分。目前人們已經提出了AdaCost、AdaC3[18-19]等代價敏感Boosting算法，但是這些算法通過啟發式策略向AdaBoost算法的加權投票因子中加入代價因子，有可能破壞算法的Boosting特性[20]。AdaBoost算法具備非對稱學習能力，在算法進行迭代之前，根據樣本類別賦予樣本代價權重：

根據式（8）可以實現代價敏感的Boosting算法。本文對此過程進行了改進，在賦予樣本初始化代價權重后，對代價敏感的基分類器進行訓練，實驗結果表明，集成改進后的代價敏感算法，減小了總體誤分代價，代價敏感性更好。

程序后

4 實驗結果與分析

實驗測試數據集為UCI官網上的公開數據集（http：//archive.ics.uci.edu/ml/index.php），在其中選取了5個典型的不均衡的分類數據集，實驗中將非數字型數據用數值表示，并對所有數據進行歸一化處理，使之成為能夠被KNN算法加載的數據集。對每個數據集進行了10折交叉法，每次取其中9個數據集作為樣本集，剩余1個數據集作為測試集，實驗結果取其平均值。

4.1 度量標準

代價敏感的學習過程中，提高高代價樣本的分類準確率顯得更為重要，通過對少數類的召回率（Recall）、平均誤分代價（AvgCost）和高代價錯誤率（記為High-rate）進行代價敏感性能比較，將多數類作為正例得到的混淆矩陣[21]如表1所示。

4.2 樣本重采樣實驗

第一個實驗是將數據集按照近鄰原則進行刪減，降低多數類樣本的邊界密度，使得樣本分布趨于平衡。表2為樣本集刪減前后少數類的比重對比，其中的rate為少數類在整個樣本中所占的比重，Before、Later為數據刪減前后的樣本數與維數的向量表示。

實驗過后，少數類的比重rate較原先的數據集提升了近17個百分點，表2中的結果表明，刪減過后的樣本分布更加均衡，少數類和多數類的比例接近1∶1，近鄰刪減法可以有效降低多數類的樣本密度。

4.3 算法性能對比

在第二個實驗中，將CSD-KNN算法與傳統的KNN和貝葉斯分類器進行代價敏感性能比較，并綜合分析算法的分類準確率。整個實驗中的數據是以K=5，α=0.5，誤分代價比重c=3得出的數據，其中CSD-KNN（new）表示在按近鄰策略刪減之后的樣本集上進行性能分析的結果。表4中的衡量指標為Recall值，少數類的召回率表示少數類的分類準確率，Recall值越大，表示算法對少數類的分類精確率越高。

相比KNN算法下降了12.33個百分點，對數據集應用近鄰刪減法和代價敏感改進，算法的平均誤分代價下降了37.87個百分點。實驗結果表明，與傳統的KNN算法和樸素貝葉斯算法相比，改進后算法的代價敏感性能明顯優于傳統算法。

從表4中可以直觀地看到，改進后的算法對少數類的正確分類更為注重，具備更強的代價敏感特性。改進后的算法是代價敏感的，并且根據KNN進行近鄰刪減后的數據集也可以提升算法的代價敏感性。

從圖1中可以發現，CSD-KNN算法是一種犧牲了部分分類準確率達到對少數類的高召回率的代價敏感分類算法。相比KNN算法：改進后的算法的分類準確率降低了約6.4個百分點，對于整體的分類效果影響不大;而對于少數類的召回率提高了約25.4個百分點，性能明顯優于傳統的KNN算法。同時，基于樣本刪減策略的CSD-KNN算法可以有效提高算法的分類準確率，相比KNN算法，改進后算法的分類準確率提升了約0.8個百分點，同時召回率也明顯提升。實驗證明，CSD-KNN算法具備代價敏感性，并且對于整體分類準確率的影響也較小，而樣本刪減策略可以有效地減少分類錯誤。基于樣本刪減策略的CSD-KNN算法在性能上明顯優于傳統的KNN算法。

4.4 CSD-KNN算法集成測試

在第3個實驗中，集成算法在調整權重之前，給每個樣本賦予代價初值使得集成后的算法具備代價敏感性，將KNN算法與集成的KNN算法以及集成代價敏感的CSD-KNN算法進行性能比較，分析對代價敏感的基學習器進行集成能否得到代價敏感性能更好的集成算法，實驗結果如圖2所示。

實驗結果表明，對權重賦代價初值可以得到代價敏感的集成算法，而相比集成KNN算法，對CSD-KNN算法進行集成的高代價錯誤率降低了4.01個百分點，證明對代價敏感的基分類器進行集成，對于降低平均誤分類代價效果更好。

在整個實驗中對于少數類的分類準確率，改進后的算法相比KNN算法提升了38.8個百分點，同時在整體性能上也優于原先的算法，而集成這種代價敏感的基分類算法使得算法的代價敏感性能更好，高代價錯誤率降低了14.01個百分點，平均誤分代價降低了31.35個百分點。

5 結語

在實際的應用中，針對不同的類別情況賦予不同的代價顯得更為可行，代價敏感學習算法在對不均衡數據集進行分類時性能實際意義明顯優于傳統的分類算法。本文提出的CSD-KNN集成算法不僅提出了一種應用于不均衡數據集的樣本刪減策略，同時還提出了一種代價敏感算法，通過不斷的迭代使得分類器的錯分代價降至最低，相比KNN算法，本文算法的高代價錯誤率和平均誤分代價都顯著降低了，同時整體分類性能更好。

需要指出，CSD-KNN算法在軟件缺陷預測、文本分類、聚類分析等諸多領域有著良好的效果，但是本文研究也存在不足之處，在進行樣本選擇時，壓縮樣本數量、選取典型樣本、大幅度減少樣本集數量將是下一階段的研究目標。

參考文獻 （References）

[1] 熊冰妍，王國胤，鄧維斌.基于樣本權重的不平衡數據欠抽樣方法[J].計算機研究與發展，2016，53（11）：2613-2622.（XIONG B Y， WANG G Y， DENG W B. Under-sampling method based on sample weight for imbalanced data [J]. Journal of Computer Research and Development， 2016， 53（11）： 2613-2622.）

[2] CHENG F， ZHANG J， WEN C. Cost-sensitive large margin distribution machine for imbalanced data classification [J]. Pattern Recognition Letters， 2016， 80： 107-112.

[3] CAO C J， WANG Z. IMCStacking： cost-sensitive stacking learning with feature inverse mapping for imbalanced problems [J]. Knowledge-Based Systems， 2018， 150： 27-37.

[4] PINAR T， LALE O， SINEM K， et al. A cost-sensitive classification algorithm： BEE-miner [J]. Knowledge-Based Systems， 2016， 95： 99-113.

[5] LOMAX S， VADERA S. A survey of cost-sensitive decision tree induction algorithms [J]. ACM Computing Surveys， 2013， 45（2）： 16-50.

[6] 陳永輝，岳麗華.特征敏感的點云重采樣算法[J].小型微型計算機系統，2017，38（5）：1086-1090.（CHEN Y H， YUE L H. Point cloud resampling algorithm of feature-sensitivity [J]. Journal of Chinese Computer Systems， 2017， 38（5）： 1086-1090.）

[7] 陳海鵬，申鉉京，龍建武.采用高斯擬合的全局閾值算法閾值優化框架[J].計算機研究與發展，2016，53（4）：892-903.（CHEN H P， SHEN X J， LONG J W. Threshold optimization framework of global thresholding algorithms using Gaussian fitting [J]. Journal of Computer Research and Development， 2016， 53（4）： 892-903.）

[8] 李勇，劉戰東，張海軍.不平衡數據的集成分類算法綜述[J].計算機應用研究，2014，31（5）：1287-1291.（LI Y， LIU Z D， ZHANG H J. A survey of integrated classification algorithms for unbalanced data [J]. Application Research of Computers， 2014， 31（5）： 1287-1291.）

[9] DOMINGOS P. MetaCost：a general method for making classifiers cost-sensitive[C]// Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 1999： 155-164.

[10] 周宇航，周志華.代價敏感大間隔分布學習機[J].計算機研究與發展，2016，53（9）：1964-1970.（ZHOU Y H， ZHOU Z H. Cost sensitive large interval distribution learning machine [J]. Journal of Computer Research and Development， 2016， 53（9）： 1964-1970.）

[11] BAHNSEN A C， AOUADA D， OTTERSTEN B. Example-dependent cost-sensitive decision trees [J]. Expert Systems with Applications， 2015， 42（19）： 6609-6619.

[12] GHAZIKHANI A， MONSEFI R， YAZDI H S. Online cost-sensitive neural network classifiers for non-stationary and imbalanced data streams [J]. Neural Computing and Applications， 2013， 23（5）： 1283-1295.

[13] 付忠良.多標簽代價敏感分類集成學習算法[J].自動化學報，2014，40（6）：1075-1085.（FU Z L. Multi-tag cost sensitive classification integrated learning algorithm [J]. Acta Automatica Sinica， 2014， 40（6）： 1075-1085.）

[14] 王茜，楊正寬.一種基于加權KNN的大數據集下離群檢測算法[J].計算機科學，2011，38（10）：177-180.（WANG Q， YANG Z K. An outlier detection algorithm for big data sets based on weighted KNN [J]. Computer Science， 2011， 38（10）： 177-180.）

[15] FREUND Y， IYER R， SCHAPIRE R， et al. An efficient boosting algorithm for combining preferences [J]. Journal of Machine Learning Research， 2003， 4 （6）： 170-178.

[16] 胡小生，鐘勇.基于邊界樣本選擇的支持向量機加速算法[J].計算機工程與應用，2017，53（3）：169-173.（HU X S， ZHONG Y. Support vector machine acceleration algorithm based on boundary sample selection [J]. Computer Engineering and Applications， 2017， 53（3）： 169-173.）

[17] 蔣盛益，謝照青，余雯.基于代價敏感的樸素貝葉斯不平衡數據分類研究[J].計算機研究與發展，2011，48（增刊I）：387-390.（JIANG S Y， XIE Z Q， YU W. Cost-sensitive naive Bayesian unbalanced data classification [J]. Journal of Computer Research and Development， 2011， 48（Suppl I）： 387-390.）

[18] SUN Y， KAMEL M S， WONG A K， et al. Cost-sensitive boosting for classification of imbalanced data [J]. Pattern Recognition， 2007， 40（12）： 3358-3378.

[19] SUN Y， WONG A K， WANG Y. Parameter inference of cost-sensitive boosting algorithms [C]// Proceedings of the 4th International Conference on Machine Learning and Data Mining in Pattern Recognition. Berlin： Springer， 2005： 21-30.

[20] 曹瑩，苗啟廣，劉家辰，等.具有Fisher一致性的代價敏感Boosting算法[J].軟件學報，2013，24（11）：2584-2596.（CAO Y， MIAO Q G， LIU J C， et al. Fisher consistent cost sensitive Boosting algorithm [J]. Journal of Software， 2013， 24（11）： 2584-2596.）

[21] 周志華.機器學習[M].北京：清華大學出版社，2018：30-33.（ZHOU Z H. Machine Learning [M]. Beijing： Tsinghua University Press， 2018： 30-33.）