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

黃偉婷，趙　紅，?！》?/p>

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

2.閩南師范大學(xué) 粒計算及其應(yīng)用重點實驗室，福建 漳州 363000

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

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

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

2.閩南師范大學(xué) 粒計算及其應(yīng)用重點實驗室，福建 漳州 363000

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

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

1　引言

代價敏感學(xué)習(xí)是機器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域的十大最具挑戰(zhàn)性問題之一[1]。近十年來，代價敏感學(xué)習(xí)的研究工作受到越來越多學(xué)者的關(guān)注。賈修一等人[2]基于決策成本的最小化問題，提出了決策粗糙集模型的一種優(yōu)化表示。閔帆等人[3]基于公共測試代價和屬性測試順序問題，構(gòu)建了測試代價敏感決策系統(tǒng)的層次模型。周志華等人[4]將代價敏感學(xué)習(xí)和人工神經(jīng)網(wǎng)絡(luò)相結(jié)合，給出了決策類不平衡問題的解決方案。文獻(xiàn)[5]將代價敏感學(xué)習(xí)引入到人臉識別領(lǐng)域，提出了基于代價敏感學(xué)習(xí)的人臉識別方法。

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

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

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

2　代價敏感屬性選擇問題

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

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

Table 1　An example of decision system表1　一個決策系統(tǒng)

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

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

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

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

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

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

步驟1拆分?jǐn)?shù)據(jù)集，每個子數(shù)據(jù)集的條件屬性個數(shù)為size，子數(shù)據(jù)集總個數(shù)為Blocks=|C|/size。

步驟2調(diào)用回溯法對各子數(shù)據(jù)集求最小約簡。

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

步驟4Blocks=Blocks/k。若Blocks>1，返回步驟2；否則繼續(xù)執(zhí)行。

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

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

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

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

4　實驗結(jié)果與分析

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

Table 3　Dataset information表3　數(shù)據(jù)集信息

4.1實驗參數(shù)設(shè)置

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

4.2實驗結(jié)果分析

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

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

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

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

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

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

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

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

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

（2）當(dāng)mc(1,0)≠$0時，測試代價和MATC保持不變，值均為$7，屬性子集的大小也不變?？梢姡x最優(yōu)屬性子集均為約簡。

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

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

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

從圖2中可以看出：

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

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

從圖3中可以看出：

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

（2）圖3（b）中，啟發(fā)式算法和分治回溯算法的運行時間基本保持穩(wěn)定，不受誤分類代價的影響。啟發(fā)式算法的運行時間約為630 ms，分治回溯算法的運行時間基本為150 ms左右?？梢?，分治回溯算法的執(zhí)行效率高于啟發(fā)式算法。

5　結(jié)束語

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

[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.

附中文參考文獻(xiàn)：

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

[14]李華雄,周獻(xiàn)中,黃兵,等.決策粗糙集與代價敏感分類[J].計算機科學(xué)與探索,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年于福州大學(xué)計算機應(yīng)用專業(yè)獲得碩士學(xué)位，現(xiàn)為閩南師范大學(xué)講師，主要研究領(lǐng)域為粒計算，代價敏感學(xué)習(xí)。

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年于遼寧師范大學(xué)計算機應(yīng)用專業(yè)獲得碩士學(xué)位，現(xiàn)為閩南師范大學(xué)副教授，主要研究領(lǐng)域為粒計算，代價敏感學(xué)習(xí)。

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年于奧克蘭大學(xué)計算機科學(xué)專業(yè)獲得博士學(xué)位，現(xiàn)為閩南師范大學(xué)教授，主要研究領(lǐng)域為人工智能，粗糙集，軟件水印，軟件安全。

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(國家自然科學(xué)基金);the Key Science and Technology Project of Fujian Province under Grant No.2012H0043(福建省科技計劃重點項目);the Natural Science Foundation of Zhangzhou under Grant No.ZZ2016J35(漳州市自然科學(xué)基金).

CNKI網(wǎng)絡(luò)優(yōu)先出版: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.