分治策略下的代價敏感屬性選擇回溯算法*

黃偉婷，趙　紅，祝　峰

1.閩南師范大學 計算機學院，福建 漳州 363000

2.閩南師范大學 粒計算及其應用重點實驗室，福建 漳州 363000

分治策略下的代價敏感屬性選擇回溯算法*

黃偉婷1+，趙紅2，祝峰2

1.閩南師范大學 計算機學院，福建 漳州 363000

2.閩南師范大學 粒計算及其應用重點實驗室，福建 漳州 363000

代價敏感屬性選擇是數據挖掘的一個重要研究領域，其目的在于通過權衡測試代價和誤分類代價，獲得總代價最小的屬性子集。針對經典回溯算法運行時間較長的缺點，結合分治思想，提出了一種改進的回溯算法。改進算法引入了兩個相關參數，根據數據集規模自適應調整參數，并按參數大小拆分數據集，降低問題規模，以提高經典回溯算法的執行效率。針對較大規模數據集的實驗結果表明，與經典的回溯算法相比，改進算法在保證效果的同時至少提高20%的運算效率；與啟發式算法相比，改進算法在保證效率的同時取得了具有更小總代價的屬性集合，可應用于實際問題。

粗糙集；粒計算；代價敏感；屬性選擇；自適應分治

1　引言

代價敏感學習是機器學習和數據挖掘領域的十大最具挑戰性問題之一[1]。近十年來，代價敏感學習的研究工作受到越來越多學者的關注。賈修一等人[2]基于決策成本的最小化問題，提出了決策粗糙集模型的一種優化表示。閔帆等人[3]基于公共測試代價和屬性測試順序問題，構建了測試代價敏感決策系統的層次模型。周志華等人[4]將代價敏感學習和人工神經網絡相結合，給出了決策類不平衡問題的解決方案。文獻[5]將代價敏感學習引入到人臉識別領域，提出了基于代價敏感學習的人臉識別方法。

屬性選擇是數據挖掘的重要問題。代價敏感屬性選擇問題是經典屬性選擇問題的自然擴展。代價敏感屬性選擇的目的是通過測試代價[6]和誤分類代價[7]之間的權衡，得到總代價最小的最優屬性子集。在現實應用中，測試代價和誤分類代價是普遍存在的兩類重要代價。測試代價是指為獲取數據而付出的代價，可以是金錢和時間等。誤分類代價則是指把一個類的數據誤分為另一個類而受到的懲罰，也可以用金錢等來表示。

代價敏感屬性選擇問題經過多年的研究發展，已經建立了一系列的理論與方法，流行的方法包括粗糙集[8]、決策樹[9]、人工神經網絡[4]和貝葉斯網絡[10]等。Yael等人[11]基于直方圖比較方法，設計了一個代價敏感適應度函數，很好地解決了代價敏感屬性選擇問題。楊習貝等人[12]在多粒度粗糙集基礎上，建立了測試代價敏感多粒度粗糙集模型，并基于該模型提出了一個新的最小代價選擇算法。文獻[13]構建了一個基于置信水平的覆蓋粗糙集模型，針對不同粒度的數據，動態生成測試代價和誤分類代價，并給出了一種最優代價敏感粒計算方法。

目前，代價敏感屬性選擇問題的研究方法主要有窮舉算法和啟發式算法[14]。通常，啟發式算法的效率高于窮舉算法，而窮舉算法的效果優于啟發式算法。回溯法[15]是典型的窮舉算法，它一般能求得最優解，但是其運行時間較長，特別是當數據集規模較大時，其效率并不理想，不能滿足實際需求。本文在回溯法基礎上，結合分治思想，將較大規模的數據集拆分成多個獨立的、規模較小的子數據集，然后逐一求解子數據集。這樣，將一個大問題分為小問題，在不影響執行效果的前提下，縮小問題規模，從而減少運行時間，提高算法效率。因此，與經典回溯法相比，本文算法能在短時間內獲得理想的結果。本文采用6個UCI數據集進行實驗，驗證了所提算法對提高經典回溯法運行速度的有效性。

2　代價敏感屬性選擇問題

代價敏感屬性選擇問題是基于代價敏感決策系統，在權衡測試代價和誤分類代價的同時，求解最小總代價屬性子集。下面主要介紹代價敏感屬性選擇問題的相關定義。

定義1代價敏感決策系統是一個七元組[15]S=。其中U是對象的集合；C是條件屬性集合；D是決策屬性集合；Va是屬性a的值集合；Ia:U→Va是一個信息函數；tc:C→R+∪{0}是一個測試代價函數，可以用一個代價向量tc=[tc(a1),tc(a2),…,tc(a|c|)]來表示。對任意屬性子集B?C，屬性子集B的測試代價為。mc:k×k→R+∪{0}是一個誤分類代價函數，其中，可以用一個k×k矩陣來表示。mc(i,j)表示將類別i誤分為類別j所導致的代價，一般情況下，mc(i,i)=$0。

Table 1　An example of decision system表1　一個決策系統

Table 2　An example of test cost vector表2　測試代價向量

為了評價所選的屬性子集是否最優，引入平均總代價的概念。設B為一個屬性子集，IND(B)為U的一個劃分，對象集合U′∈IND(B)，U′的誤分類代價記為mc(U′,B)。對于任意的x,y∈U′，當且僅當D(x)= D(y)時，mc(U′,B)=0。而當x,y∈U′且D(x)≠D(y)時，可以將U′中的所有對象歸為某一類。而在選擇所屬類別時，人們總是遵循最小化總誤分類代價的原則，即所選的類別應使得總誤分類代價最小。這里，平均誤分類代價（average misclassification cost，AMC）表示為：

平均總代價（average total cost，ATC）表示為：

定義2設S是一個代價敏感決策系統，對于任意B?C，當且僅當滿足，則稱B為最小平均總代價屬性子集。

3　分治策略下的代價敏感屬性選擇回溯算法

經典回溯算法通常能獲得代價敏感屬性選擇問題的最優解，但算法效率低，特別是當處理較大規模數據集時。為此，本文引入分治策略，設計兩個相關參數，提出了分治策略下的代價敏感屬性選擇回溯算法。本文算法的主要思想是：根據數據集規模，按條件屬性拆分數據集，然后調用回溯法處理各子數據集。這樣，減少了回溯算法處理的數據集規模，在保證獲得最優解的同時，縮短處理時間，有效地提高了算法的效率。分治策略下的代價敏感屬性選擇回溯算法的主要步驟如下：

步驟1拆分數據集，每個子數據集的條件屬性個數為size，子數據集總個數為Blocks=|C|/size。

步驟2調用回溯法對各子數據集求最小約簡。

步驟3每次合并相鄰的每k個子數據集的最小約簡。

步驟4Blocks=Blocks/k。若Blocks>1，返回步驟2；否則繼續執行。

步驟5對最后得到的子數據集中的每一個屬性逐一進行判斷：由式（2）計算每一屬性刪除前后的ATC，若屬性去掉后ATC減小，則刪除；否則保留。

下面給出分治策略下的代價敏感屬性選擇回溯算法（簡稱分治回溯算法）的偽代碼。

算法1分治策略下的代價敏感屬性選擇回溯算法

在分治回溯算法中，S表示代價敏感決策系統；參數k表示每次參與合并的子數據集個數，即合并的路數；參數size表示初始每個子數據集所包含的條件屬性個數，為了控制每個子數據集的大小，并保證多路合并時有足夠多的子數據集，其值根據各個數據集條件屬性總數的不同而變化，設置為size=ceil(|C|/k)－1。若參數k=1，即參數size=|C|時，分治回溯算法退化為經典回溯算法。為了提高算法的效果，在對各子數據集求解時，采用了競爭策略。

4　實驗結果與分析

為了驗證分治策略下的代價敏感屬性選擇回溯算法的有效性，本文從UCI數據庫中選取6個數據集，描述如表3所示，與文獻[15]中的經典回溯算法和文獻[16]中的啟發式算法進行實驗對比。

Table 3　Dataset information表3　數據集信息

4.1實驗參數設置

本文采用均勻分布方式隨機產生測試代價，測試代價為[1，10]區間內的整數，誤分類代價設置為mc(0,1)=4mc(1,0)。另外，考慮到運行效率，根據數據集規模動態調整合并的路數k。對于前4個中小規模的數據集，設置參數k=2，參數size=ceil(|C|/k)－1；而對于最后兩個較大規模的數據集，設置參數k=3，參數size=4。算法運行5次。

4.2實驗結果分析

為了分析在不同誤分類代價設置下，測試代價和最小平均總代價（minimal average total cost，MATC）的變化情況，設置mc(1,0)值范圍為$0～$200，步長為$20。在6個數據集上，按不同參數設置執行分治回溯算法，運行結果如圖1所示。

圖1中，橫坐標均表示mc(1,0)值，縱坐標表示代價，從圖1中可以看出：

（1）MATC整體上都隨著誤分類代價的增長而增長。

（2）圖1（b）～（d）中，當測試代價不變時，MATC隨誤分類代價的增加呈線性增長。

（3）圖1（a）、（d）和（f）中，隨著誤分類代價的增大，測試代價慢慢逼近MATC。當誤分類代價足夠大時，測試代價等于MATC。此時，平均誤分類代價為$0，表示所選的屬性子集為一個約簡。

（4）圖1（e）中，當mc(1,0)=$20時，測試代價為$0，表示此時未進行任何測試。

Fig.1　Test cost and minimal average total cost with different misclassification costs圖1　不同誤分類代價下的測試代價和最小平均總代價

為了直觀地顯示不同誤分類代價設置下的最優屬性子集及分治回溯算法的處理能力，選擇較大規模數據集Promoters進行實驗，設置mc(1,0)值范圍為$0～$1 000，步長為$200，執行10次，運行結果如表4所示。從表4中可以看出：

（1）當mc(1,0)=$0時，平均總代價為$0，表示此時不存在懲罰代價，屬性子集為空集。

（2）當mc(1,0)≠$0時，測試代價和MATC保持不變，值均為$7，屬性子集的大小也不變。可見，所選最優屬性子集均為約簡。

為驗證分治回溯算法的執行能力，選取中大規模數據集Mushroom和Kr-vs-kp進行實驗。對于數據集Mushroom，分別執行分治回溯算法、文獻[15]中的回溯算法和文獻[16]中的啟發式算法。對于數據集Kr-vs-kp，當mc(1,0)=$300時，回溯算法獲得的MATC值為$48.622，略高于其他兩個算法；其運行時間為1.24×107ms，而其他兩個算法的運行時間僅為幾百毫秒，并且誤分類代價越大，必須花費更多的時間測試更多的屬性，運行時間也越長。因此，為便于畫圖，并能更好地做對比，在數據集Kr-vs-kp中，只比較分治回溯算法和啟發式算法的實驗結果。實驗結果對比如圖2和圖3所示。

Table 4　Optimal feature subset with different misclassification costs表4　不同誤分類代價下的最優屬性子集

Fig.2　Comparison of minimal average total cost with different misclassification costs圖2　不同誤分類代價下的最小平均總代價對比

Fig.3　Comparison of runtime with different misclassification costs圖3　不同誤分類代價下的運行時間對比

圖2和圖3中，橫坐標均表示mc(1,0)值，圖2的縱坐標表示最小平均總代價，圖3的縱坐標表示運行時間。這里，設置mc(1,0)值范圍為$100～$800，步長為$100，啟發式算法參數λ=－1。數據集Mushroom中，參數k=2，參數size=6；數據集Kr-vs-kp中，參數k=3，參數size=4。

從圖2中可以看出：

（1）圖2（a）中，回溯算法的效果最好，MATC隨誤分類代價的增加而緩慢增大。啟發式算法和分治回溯算法的實驗結果較為接近，兩個算法在mc(1,0)值為$400和$700時，MATC均為$18，所求得的屬性子集均為一個約簡。

（2）圖2（b）中，啟發式算法和分治回溯算法的MATC隨誤分類代價的增加而增大，啟發式算法的增長較快，而分治回溯算法的變化較小。從整體上看，分治回溯算法的運行效果好于啟發式算法。

從圖3中可以看出：

（1）圖3（a）中，回溯算法的效率最差，運行時間隨著誤分類代價的增加基本呈線性增長。啟發式算法和分治回溯算法的運行時間隨誤分類代價的不同并無太大變化，啟發式算法結果較好。

（2）圖3（b）中，啟發式算法和分治回溯算法的運行時間基本保持穩定，不受誤分類代價的影響。啟發式算法的運行時間約為630 ms，分治回溯算法的運行時間基本為150 ms左右。可見，分治回溯算法的執行效率高于啟發式算法。

5　結束語

本文提出了分治策略下的代價敏感屬性選擇回溯算法，根據數據集規模動態設置參數size和參數k，將問題分而治之，有效改進了經典回溯算法的效率。通過與文獻[15]中的回溯算法和文獻[16]中的啟發式算法的實驗對比，驗證了本文算法的有效性。對于數據集Kr-vs-kp，設置參數k=3，參數size=4時，本文算法的效果最好。可見，將此參數設置應用到規模較大的數據集時，本文算法能獲得令人滿意的解。在將來的工作中，可以考慮是否有其他拆分數據集的方式，不同拆分方式下的性能是否有所區別。顯然，如何快速求解多代價下的代價敏感屬性選擇問題是一個重點研究的課題。

[1]Yang Qiang,Wu Xindong.10 challenging problems in data mining research[J].International Journal of Information Technology&Decision Making,2006,5(4):597-604.

[2]Jia Xiuyi,Tang Zhenmin,Liao Wenhe,et al.On an optimization representation of decision-theoretic rough set models [J].International Journal of Approximate Reasoning,2014, 55(1):156-166.

[3]Min Fan,Liu Qihe.Ahierarchical model for test-cost-sensitive decision systems[J].Information Sciences,2009,179(14): 2442-2452.

[4]Zhou Zhihua,Liu Xuying.Training cost-sensitive neural networks with methods addressing the class imbalance problem[J].IEEE Transactions on Knowledge and Data Engineering,2006,18(1):63-77.

[5]Zhang Yin,Zhou Zhihua.Cost-sensitive face recognition[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(10):1758-1769.

[6]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,San Diego,USA,Aug 15-18,1999.New York:ACM, 1999:155-164.

[7]Lin Ziqiong,Zhao Hong.Cost-sensitive optimal error bound selection[J].Journal of Frontiers of Computer Science and Technology,2013,7(12):1146-1152.

[8]Yao Yiyu,Zhao Yan.Attribute reduction in decision-theoretic rough set models[J].Information Sciences,2008,178(17): 3356-3373.

[9]Wang Xizhao,Dong Lingcai,Yan Jianhui.Maximum ambiguitybased sample selection in fuzzy decision tree induction[J]. IEEE Transactions on Knowledge&Data Engineering, 2012,24(8):1491-1505.

[10]Friedman N,Geiger D,Goldszmidt M.Bayesian network classifiers[J].Machine Learning,1997,29(2/3):131-163.

[11]Weiss Y,Elovici Y,Rokach L.The CASH algorithm—costsensitive attribute selection using histograms[J].Information Sciences,2013,222:247-268.

[12]Yang Xibei,Qi Yunsong,Song Xiaoning,et al.Test cost sensitive multigranulation rough set:model and minimal cost selection[J].Information Sciences,2013,250:184-199.

[13]Zhao Hong,Zhu W.Optimal cost-sensitive granularization based on rough sets for variable costs[J].Knowledge-Based Systems,2014,65:72-82.

[14]Li Huaxiong,Zhou Xianzhong,Huang Bing,et al.Decision-theoretic rough det and cost-sensitive classification[J].Journal of Frontiers of Computer Science and Technology,2013, 7(2):126-135.

[15]Min Fan,Zhu W.Minimal cost attribute reduction through backtracking[J].Communications in Computer&Information Science,2011,258:100-107.

[16]Li Xiangju,Zhao Hong,Zhu W.An exponent weighted algorithm for minimal cost feature selection[J].International Journal of Machine Learning and Cybernetics,2014:1-10. doi:10.1007/s13042-014-0279-4.

附中文參考文獻：

[7]林姿瓊,趙紅.代價敏感最優誤差邊界選擇[J].計算機科學與探索,2013,7(12):1146-1152.

[14]李華雄,周獻中,黃兵,等.決策粗糙集與代價敏感分類[J].計算機科學與探索,2013,7(2):126-135.

HUANG Weiting was born in 1977.She received the M.S.degree in computer application from Fuzhou University in 2008.Now she is a lecturer at Minnan Normal University.Her research interests include granular computing and the study of cost-sensitive.

黃偉婷（1977—），女，福建漳州人，2008年于福州大學計算機應用專業獲得碩士學位，現為閩南師范大學講師，主要研究領域為粒計算，代價敏感學習。

ZHAO Hong was born in 1979.She received the M.S.degree in computer application from Liaoning Normal University in 2006.Now she is an associate professor at Minnan Normal University.Her research interests include granular computing and the study of cost-sensitive.

趙紅（1979—），女，黑龍江哈爾濱人，2006年于遼寧師范大學計算機應用專業獲得碩士學位，現為閩南師范大學副教授，主要研究領域為粒計算，代價敏感學習。

ZHU William was born in 1962.He received the Ph.D.degree in computer science from University of Auckland in 2007.Now he is a professor at Minnan Normal University.His research interests include artificial intelligence, rough sets,software watermarking and software security.

祝峰（1962—），男，江西玉山人，2007年于奧克蘭大學計算機科學專業獲得博士學位，現為閩南師范大學教授，主要研究領域為人工智能，粗糙集，軟件水印，軟件安全。

Backtracking Algorithm for Cost-Sensitive Feature Selection Based on Divide and Conquer Strategy?

HUANG Weiting1+,ZHAO Hong2,ZHU William2
1.School of Computer,Minnan Normal University,Zhangzhou,Fujian 363000,China
2.Lab of Granular Computer,Minnan Normal University,Zhangzhou,Fujian 363000,China

E-mail:weitinghuang92@163.com

Cost-sensitive feature selection is an important research field in the process of data mining.It aims at obtaining an attribute subset of the lowest total cost,through balancing test cost and misclassification cost.According to the shortcoming of the classical backtracking algorithm with longer running time,combining divide and conquer thought, this paper proposes an improved backtracking algorithm.Introducing two related parameters,this algorithm computes adaptively parameters according to the dataset scale,and splits the dataset with these parameters.It can enhance the efficiency of the classical backtracking algorithm by reducing the problem size.The experiments on the datasets with large scale show that this improved algorithm is effective and meets the need of practical problems.At the same time guaranteeing the effect,this improved algorithm promotes the efficiency of 20%at least than the classical backtracking algorithm.Compared with heuristic algorithm,this improved algorithm obtains an attribute set with a smaller total costand ensures the efficiency.

rough sets;granular computing;cost-sensitive;feature selection;adaptive divide and conquer

2015-09,Accepted 2015-12.

10.3778/j.issn.1673-9418.1509042

A

TP18

*The National Natural Science Foundation of China under Grant Nos.61379049,61379089,61170128(國家自然科學基金);the Key Science and Technology Project of Fujian Province under Grant No.2012H0043(福建省科技計劃重點項目);the Natural Science Foundation of Zhangzhou under Grant No.ZZ2016J35(漳州市自然科學基金).

CNKI網絡優先出版:2015-12-09,http://www.cnki.net/kcms/detail/11.5602.TP.20151209.1103.004.html

HUANG Weiting,ZHAO Hong,ZHU William.Backtracking algorithm for cost-sensitive feature selection based on divide and conquer strategy.Journal of Frontiers of Computer Science and Technology,2016,10(10)：1451-1458.