基于K最近鄰的代價敏感三支決策邊界域處理模型

王剛，張燕平，陳潔*，趙姝

?

基于K最近鄰的代價敏感三支決策邊界域處理模型

王剛1,2，張燕平1,2，陳潔1,2*，趙姝1,2

(1.安徽大學計算機科學與技術學院，合肥 230601 2.安徽大學計算智能與信號處理教育部重點實驗室，合肥 230601)

三支決策理論是Yao在研究粗糙集和決策粗糙集時提出的，其主要目的是為粗糙集三個域提供合理的語義解釋，即正域POS(X)、負域NEG(X)和邊界域BND(X)。目前，如何有效地處理邊界域已成為三支決策理論研究的熱點問題。例如，基于CCA的三支決策模型提出了三種方法對邊界域樣本進行處理，分別是距中心最近原則、距邊界最近原則和萬有引力原則，但是這三種方法都沒有考慮到分類問題的代價敏感性。本文在基于CCA的三支決策模型的基礎上，針對邊界域的處理問題，提出了一種基于K最近鄰的代價敏感三支決策邊界域處理模型。該模型首先根據樣本分布特征尋找最優K值，然后根據與樣本邊界距離最小的K個覆蓋的類別和代價敏感損失函數對邊界域樣本進行劃分。實驗結果表明，與基于CCA的三支決策模型中的處理方法相比，本文模型在最優K值下的分類結果的高代價樣本的誤分類數顯著減少，分類損失更小，而且總分類錯誤率較低。

三支決策；覆蓋算法；K最近鄰；代價敏感；邊界域處理

引言

Yao在粗糙集和決策粗糙集研究中提出了三支決策理論，該理論將傳統的正域、負域的二支決策語義拓展為正域、邊界域和負域的三支決策語義[1-2]。目前的三支決策理論的研究主要是基于粗糙集的三支決策理論，而其中最具有代表性的是決策粗糙集理論模型（Decision Theoretic Rough Set Model, DTRSM）[3]，由Yao等在1990年提出。近年來許多學者也對其進行了大量的研究，于洪等人研究了基于DTRS的聚類[4-6]。賈修一等人研究了決策風險最小化情形下的屬性約簡和基于三支決策的屬性約簡[7]。李文和苗奪謙等人提出了基于決策粗糙集的文本分類方法[8]。李華雄等人研究了決策粗糙集的三支決策語義，并提出了三支決策粗糙集模型[9-11]。近十多年來，DTRSM被引入到不完備系統和多智能體系統中，應用于投資決策[12]、信息過濾[13]、垃圾郵件等方向[14-15]，取得了很大成效。但是，基于決策粗糙集的三支決策模型仍存在兩個需要解決的問題：一、在該模型中，三個域的形成由一對閾值、來決定，閾值、由損失函數計算得到，而損失函數由專家根據自己的經驗給定，具有很大的主觀不確定性；二、形成三個域后，邊界域中樣本的處理問題還有待進一步解決。

構造性覆蓋算法（Constructive Covering Algorithm, CCA）[16-17]由中國學者張鈴、張鈸提出?；跇嬙煨愿采w算法的三支決策模型[19]可以根據樣本的分布特征自動形成三個域，不必人為確定相關參數，使得損失函數和閾值、的取值問題得以解決。該模型還提出了三種處理全部邊界域樣本的原則，分別是距中心最近原則、距邊界最近原則和萬有引力原則[18]。但是這三種方法只是根據樣本與覆蓋之間的距離或者覆蓋的樣本數對邊界域中樣本進行簡單分類，并沒有考慮到分類的代價敏感問題。

分類問題往往具有代價敏感性，本文針對三支決策模型中的邊界域處理問題，在基于CCA的三支決策模型的基礎上提出了基于K最近鄰的代價敏感的邊界域處理模型。該模型根據樣本的K個最近鄰覆蓋及樣本的分類損失函數來計算比較每種決策損失的大小，然后選擇損失代價最小的決策對樣本進行劃分。由于KNN算法的局限性，K取值太小時分類誤差較大，取值太大又沒有意義。依據經驗，一般K的最優取值在[7,37]之間，在最優K值下，本文的分類模型可以有效降低高代價樣本的誤分類數，使分類損失最小化，而且分類的總錯誤率較低。

1 基于CCA的三支決策模型及邊界域處理方法

1.1 基于CCA的三支決策模型

基于構造性覆蓋算法（CCA）的三支決策模型[19]可以根據數據集自身特性自動形成三個域，即正域POS(X)、負域NEG(X)和邊界域BND(X)，不需要討論任何參數。

通常構造覆蓋的方法有三種，分別是最小半徑法、最大半徑法和折中半徑法。最小半徑法將距覆蓋中心最近的異類樣本的歐式距離作為覆蓋的半徑，而最大半徑法選擇在該距離以內最遠的同類樣本到覆蓋中心的歐式距離作為覆蓋的半徑，折中半徑法則取二者的平均值作為覆蓋的半徑。如圖1所示：

圖1 覆蓋半徑（）

（2）

本文在構造覆蓋的過程中采用最大半徑法。相比于折中半徑法和最小半徑法，最大半徑法構造的覆蓋雖然包含的樣本數雖然較少，但是覆蓋中不包含異類樣本，有利于降低分類損失。

1.2 邊界域樣本的處理方法

在邊界域樣本的處理問題上，基于CCA的三支決策模型給出了三種對全部邊界域樣本進行處理的方法，分別是距中心最近原則、距邊界最近原則和萬有引力原則。

1、距中心最近原則

2、距邊界最近原則

（4）

3、萬有引力原則

圖2 處理邊界域的三原則

三種處理方法的原理都比較簡單，時間效率較高，但是都沒有考慮分類的代價敏感性，因此分類的代價損失會比較大。

2 基于K最近鄰的代價敏感三支決策邊界域處理模型

K 最近鄰分類算法（KNN）是基于類比學習的非參數的分類技術，在基于統計的模式識別中非常有效。其分類基本原理為：首先將待分類樣本表達成和訓練樣本庫的樣本一致的特征向量；然后據距離函數計算待分類樣本 x 和每個訓練樣本的距離，選擇與待分類樣本距離最小的 K 個樣本作為 x 的 K 個最近鄰；最后根據 x 的K 個最近鄰判斷 x 的類別。

當分類問題中不同的分類錯誤會引起不同的分類代價時，這個分類問題就稱為代價敏感分類問題。例如郵件分類問題，如果將一封垃圾郵件誤分為合法郵件可能只是花費用戶一些時間來檢查整理郵件。而如果當把一封合法郵件誤分為垃圾郵件，可能會使某個用戶錯過一個重要的應聘而失去工作機會，給用戶帶來巨大的損失。因此，郵件分類問題就是一個代價敏感的分類問題。而基于CCA的三支決策模型所提出的處理邊界域樣本的方法都沒有考慮到這一點。本文在基于CCA的三支決策模型基礎之上，提出了基于K最近鄰的代價敏感三支決策邊界域處理模型（Cost-sensitive Three-way decision model for processing boundary region based on K nearest neighbor，CTK）。該模型將K最近鄰分類與代價敏感分類相結合，相比于原來的處理方法，它可以有效降低高代價樣本的誤分類數，使分類損失最小化，同時分類的總錯誤率也較小。

在KNN算法中，測試樣本的標簽由距離它最近的K個鄰居決定。假設x為邊界域中一個樣本，找出與x邊界距離最小的K個覆蓋，中正域覆蓋數為N，負域覆蓋數為（K-N）。本文中使用，分別代表樣本x屬于正域和負域的概率。為了減小分類損失，本文在分類過程中進一步引入代價敏感的分類原則，樣本x被劃分到正域和負域的決策損失和可以通過公式（6）、（7）進行計算：

（7）

算法具體過程如下

算法1：基于K最近鄰的代價敏感三支決策邊界域處理模型（CTK） 輸入：樣本數據集，樣本屬性集。輸出：正域POS(X)和負域NEG(X)。Step1：根據CCA算法中的最大半徑原則對樣本集進行訓練，得到一個覆蓋集合和邊界域BND。Step2：確定最優 K 值和損失函數值。Step3：從BND中任取一樣本x，根據公式（6）（7）計算出樣本被劃分到正域和負域的損失和。Step4：對于滿足的數據集，如果，則將x劃分到正域，否則x被劃分到負域；對于滿足的數據集，如果，則將x劃分到負域，否則x被劃分到正域。Step5：若邊界域中所有樣本都被成功劃分到正域或負域中，結束，否則，轉step2。

當K=1時，CTK算法等價于距邊界最近原則（NBP）。

3 實驗

在本文中實驗所使用的四個數據集均來自UCI Machine Learning Repository (http://archive.ics.uci.edu/ml/datasets.html)。在這四個數據集Spambase，Ads，Chess和Wpdc上將本文的分類模型（CTK）與距中心最近原則（NCP）、距邊界最近原則（NBP）和萬有引力原則（GP）的結果進行了對比和分析。實驗中采用的驗證方法均是十交叉驗證法，所有對比實驗均是四種分類模型在處理相同邊界域樣本的條件下進行。表1是兩個數據集的基本信息。

表1 實驗數據集基本信息表

由算法1可以看出影響CTK算法性能的主要有兩個參數，一個是與樣本最近鄰的覆蓋數K，另一個是損失函數。下面假設每個數據集的損失函數取值如表 2 所示，其中，對于Spambase數據集，滿足，對于其他三個數據集，損失函數值的大小沒有實際意義，在不影響預期效果的情況下假設Ads滿足，Chess和Wpdc滿足，兩個數據集一組形成對比參照，正確分類的樣本損失為0：

表2 損失函數值

圖3是四種分類算法在Spambase、Ads、Chess和Wpdc四個數據集進行分類后的分類損失對比圖，由于NCP、NBP和GP的實驗結果不受K值的影響，因此都用一條水平直線來表示。一般情況下，CTK算法在每個數據集都會有一個最優K值使分類損失最小，由于K取值太小時分類誤差較大，取值太大又沒有意義，本文只需在區間[7,43]上找到最優K值對應的分類結果作為最終CTK算法的分類結果即可。

（a）

（b）

（c）

（d）

圖3 分類損失對比圖

Fig.3 The comparison charts of loss of classification

從圖3可以看出，在 Spmbase 上最優K值為7，此時 CTK 算法的分類損失在四種算法中最小；在 Ads 上最優K值為7，此時CTK算法的分類損失在四種算法中最??；在 Chess上最優K值為 7，此時CTK 算法的分類損失在四種算法中最??；在Wpdc上最優K值為31，此時CTK算法的分類損失雖然并不是最小，但是與分類損失最小的NBP算法相差僅為1。圖4中給出了CTK算法在上述最優K值下與另外三種算法的高代價樣本誤分類數和總錯誤率（TER）對比圖。

假設邊界域中樣本數為N，全部處理完后高代價樣本的誤分類數為NHC，低代價樣本的誤分類數為NLC。則總錯誤率（TER）可以用下列公式表示：

在K取最優值的條件下，從圖4可以得出以下結論：（1）如圖4（a）所示，與其他三種非代價敏感分類算法相比，CTK算法可以有效降低高代價樣本的誤分類數，除了在Wpdc上由于高代價樣本數太小效果不明顯外，在其他三個數據集上CTK算法的高代價樣本誤分類數都是最小的，這也是分類損失降低的一個重要原因；（2）如圖4（b）所示，在高代價樣本分類錯誤數得到降低的同時，CTK算法的總分類錯誤率也相對較低，基本與其他三種非代價敏感分類算法中最低的相近甚至更低，如在數據集Chess和Wpdc上CTK算法的總分類錯誤率都是四種算法中最低的。

（a）

（b）

（a）

（b）

圖5 高代價樣本誤分類數和分類總錯誤率對比圖

Fig.5 The comparison charts of number of misclassification of high cost sample and total error rate

下面固定取值K=13，來觀察損失函數值變化對實驗結果的影響。由于損失函數值在變化，無法對比分類損失。圖5（a）給出了CTK算法在不同損失函數值下對邊界域進行處理后的高代價樣本誤分類數變化圖，圖5（b）給出了CTK算法在不同損失函數值下對邊界域進行處理后的總分類錯誤率變化圖。鑒于損失函數值的大小關系，對于Spambase和Ads數據集，取，；對于Chess和Wpdc數據集，取，。

在K取值固定的條件下，從圖5可以得出以下結論：（1）隨著高代價樣本誤分類損失函數值越來越大，高代價樣本的誤分類數也隨著越來越小，甚至降為零。（2）隨著高代價樣本誤分類損失函數值越來越大，雖然高代價樣本的誤分類數越來越小，但是低代價樣本誤分類數越來越大，導致分類的錯誤率卻越來越高。因此，選取合理的損失函數值對CTK算法的分類性能也有著重要的影響。一般情況下，損失函數取值在[1,20]之間，高代價樣本誤分類損失與低代價樣本誤分類損失相差在10以內時CTK算法的分類損失、總錯誤率相對較低。

4 總結與展望

分類問題往往具有代價敏感性，而傳統的邊界域處理算法很少考慮到這一點。本文在基于構造性覆蓋算法的三支決策模型的基礎上，針對邊界域的處理問題，提出了一種基于K最近鄰的代價敏感邊界域處理模型。該模型首先采用CCA算法中的最大半徑法來形成覆蓋，這樣可以保證所得到覆蓋中沒有任何異類樣本，減小分類的總損失；然后根據基于K最近鄰的代價敏感處理方法對所有邊界域樣本進行劃分。該方法首先根據數據集分布特征尋找出最優K值，然后選取合理的損失函數值，最后通過比較計算得到的劃分損失對邊界域樣本一一進行分類。實驗結果表明，相比較于基于CCA的三支決策模型中邊界域的處理方法，本文的代價敏感分類模型在最優K值條件下，可以有效減小高代價樣本的誤分類數，降低分類損失，同時分類總錯誤率較低。

[1] YAO Y Y, WONG S K M. A decision theoretic framework for approximating concepts[J]. International Journal of Man-Machine Studies, 1992, 37(6): 793-809.

[2] YAO Y Y. Two semantic issues in a probabilistic rough set model[J]. Fundamental Informatics, 2011, 108(3): 249-265.

[3] YAO Y Y, WONG. SKM, Lingras. P. A decision-theoretic rough set model[C]//Proceeding of ISMIS. 1990: 17-25.

[4] YU H, WANG X. Three-wax decisions method for overlapping clustering[C]//Rough Sets and Current Trends in Computing. Springer Berlin Heidelberg, 2012: 277-286.

[5] YU H, CHU S, XANG D. A semiautonomous clustering algorithm based on decision-theoretic rough set theory[C]//Cognitive Informatics(ICCI), 2010 9th IEEE International Conference on. IEEE, 2010: 477-483.

[6] YU H, LIU Z, WANG G. Automatically determining the number of clusters using decision-theoretic rough set[M]//Rough Sets and Knowledge Technology. Springer Berlin Heidelberg, 2011: 504-513.

[7] JIA X, LI W, SHANG L, et al. An optimization viewpoint of decision-theoretic rough set model[M]//Rough Sets and Knowledge Technology. Springer Berlin Heidelberg, 2011: 457-465.

[8] LI W, MIAO D, WANG W, et al. Hierarchical rough decision theoretic framework for text classification[C]//Cognitive Informatics (ICCI), 2010 9th IEEE International Conference on. IEEE, 2010: 484-489.

[9] LI H X, LIU D, ZHOU X Z. The summary of research on decision- theoretic rough set[J]. Journal of Chongqing University of Posts and Telecommunications: Science and Technology, 2010, 22(5): 624-630.

[10] LI H X, ZHOU X Z, LI T R, et al. Decision-theoretic rough set and its research progress[M]. Beijing:Science Press, 2011.

[11] LIU D, XAO X X, LI T R. Three-wax decision of rough set[J]. Computer Science, 2011, 38(1): 245-250.

[12] LIU D, XAO X X, LI T R. Three-wax investment decisions with decision-theoretic rough sets[J]. International Journal of Computational Intelligence Systems, 2011, 4(1): 66-74.

[13] Lingras P, CHEN M, MIAO D. Rough cluster quality index based on decision theory[J]. Knowledge and Data Engineering, IEEE Transactions on, 2009, 21(7): 1014-1026.

[14] ZHOU B, XIAO X, LUO J. A three-wax decision approach to email spam filtering[M]//Advances in Artificial Intelligence. Springer Berlin Heidelberg, 2010: 28-39.

[15] JIA X, ZHENG K, LI W, et al. Three-wax decisions solution to filter spam email: an empirical study[C]//Rough Sets and Current Trends in Computing. Springer Berlin Heidelberg, 2012: 287-296.

[16] 張鈴, 張鈸. M—P 神經元模型的幾何意義及其應用[J]. 軟件學報, 1998, 9(5): 334-338.

[17] ZHANG L, ZHANG B. A geometrical representation of McCulloch-Pitts neural model and its applications[J]. IEEE transactions on neural networks/a publication of the IEEE Neural Networks Council, 1998, 10(4): 925-929.

[18] 張燕平, 鄒慧錦, 邢航, 等. CCA 三支決策模型的邊界域樣本處理[J]. 計算機科學與探索, 2014, 8(5): 593-600.

[19] ZHANG X, XING H, ZOU H, et al. A Three-Way Decisions Model Based on Constructive Covering Algorithm[M]//Rough Sets and Knowledge Technology. Springer Berlin Heidelberg, 2013: 346-353.

Cost-Sensitive Three-Way Decision Model for Boundary Region Processing with K-Nearest Neighbors

WANG Gang1,2, ZHANG Yanping1,2, CHEN Jie1,2*, ZHAO shu1,2

(1.School of Computer Science and Technology, Anhui University, Hefei 230601, China 2.Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, Anhui University, Hefei, 230601, China)

Three-way decision is proposed by Yao in the study of rough sets and decision-theoretic rough sets. It is constructed based on the notions of acceptance, rejection and non-commitment, which can be directly generated by the three regions: positive region POS(X), negative region NEG(X) and boundary region BND(X). In recent years, how to process the boundary region has become a hot topic in the field of three-way decision theory. For example, the three-way decision model based on CCA includes three methods to process boundary region. These methods include the nearest to the center principle, the nearest to the boundary principle and the gravity principle. Unfortunately, none of them consider cost-sensitive classification. On the basis of the three-way decision model based on constructive covering algorithm, we propose a cost-sensitive method to process the boundary region based on K nearest neighbors. This method takes fully cost-sensitive classification into account to minimize cost. Results show that our method can reduce the number of misclassification of high cost samples and the loss of classification. The classification error rate is also low.

the three-way decision; constructive covering algorithm; k-nearest neighbor; cost-sensitive; process boundary region.

1672-9129(2016)02-0015-06

TP3911

A

2016-09-10；

2016-10-02。

國家自然科學基金項目（61673020、61602003）資助。

王剛(1991-)，男，湖北黃岡人，安徽大學計算機科學與技術學院研究生，主要研究領域為三支決策和機器學習。

E-mail:chenjie200398@163.com

(*通信作者電子郵箱：chenjie200398@163.com)