動態(tài)誤分類代價下代價敏感屬性選擇分治算法

黃偉婷，趙 紅

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

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

1 引言

代價敏感學習是數(shù)據(jù)挖掘的十大最具挑戰(zhàn)性問題之一[1]。代價是在數(shù)據(jù)的獲取或處理過程中產(chǎn)生的，是數(shù)據(jù)不可分割的一部分，將其引入數(shù)據(jù)挖掘是解決實際問題的必然趨勢?，F(xiàn)實中的代價有很多類，Turney[2]提出了代價分類法，常見的有測試代價和誤分類代價。近十年來，代價敏感學習的研究受到越來越多學者的關(guān)注，被廣泛應(yīng)用到醫(yī)學[3]、模式識別[4-5]、統(tǒng)計學[6]、經(jīng)濟[7]等各個研究領(lǐng)域。

屬性選擇是數(shù)據(jù)挖掘中最活躍和重要的研究問題之一。代價敏感屬性選擇問題是經(jīng)典屬性選擇問題的自然擴展。代價敏感屬性選擇的目的是通過權(quán)衡測試代價和誤分類代價，得到總代價最小的屬性子集。代價敏感屬性選擇問題經(jīng)過多年的研究，有了長足的進展。Min等[8]定義了代價敏感決策系統(tǒng)模型，并在回溯算法中引入三種有效的剪枝技術(shù)，以解決最小代價屬性選擇問題。文獻[9]提出了一種指數(shù)加權(quán)算法，通過對屬性重要度進行加權(quán)處理，來提高算法的效率。文獻[10]設(shè)計了新的代價敏感適應(yīng)度函數(shù)，并運用于遺傳搜索算法，解決了代價敏感屬性選擇問題。Zhao等[11]定義了基于置信水平的覆蓋粗糙集模型，研究了不同粒度下的代價敏感屬性選擇方法。文獻[12]定義了新的屬性重要度函數(shù)，并給出了缺失值數(shù)據(jù)下的多目標屬性選擇方法。文獻[13]提出了四種相對評價指標，并利用粒子群優(yōu)化方法來解決代價敏感屬性選擇問題。文獻[14]基于自適應(yīng)鄰域模型，對異構(gòu)數(shù)據(jù)進行了測試代價敏感屬性約簡研究。

目前，多數(shù)的代價敏感屬性選擇算法均采用靜態(tài)誤分類代價機制，即事先統(tǒng)一假定為某一固定值，與算法所選擇的屬性子集無關(guān)。而在現(xiàn)實問題中，為了減少誤分率，往往需要增加檢測。此時，若仍然錯分，則懲罰加重，誤分類代價會相應(yīng)地增大。如在金融詐欺中，識別過程越長，所遭受的損失越大。因此，如果采用固定的誤分類代價，就會忽略誤分類代價與所選屬性子集的相關(guān)性，這跟現(xiàn)實問題不太相符。另外，在實際應(yīng)用中，類別不平衡[15]的數(shù)據(jù)集往往存在著誤分類代價不等的問題。如在醫(yī)療診斷中，將正常人誤分類為病人，將影響其正常工作和生活，并付出治療費用；而將病人誤分類為正常人，則會延誤病情，甚至導致生命危險。顯然，后者所付出的代價遠大于前者。

為此，本文定義一種新的動態(tài)誤分類代價機制，考慮數(shù)據(jù)集類別不平衡的情況，根據(jù)所選屬性子集動態(tài)生成最優(yōu)誤分類代價，并提出了動態(tài)誤分類代價下的代價敏感屬性選擇分治算法。該算法結(jié)合分治法，將大規(guī)模數(shù)據(jù)集分解為多個獨立的、規(guī)模較小的子數(shù)據(jù)集，縮小了問題的規(guī)模，從而提高了算法的效率。實驗結(jié)果驗證了算法的有效性。

2 動態(tài)誤分類代價下的代價敏感決策系統(tǒng)

本章主要介紹代價敏感決策系統(tǒng)和動態(tài)誤分類代價機制，并在此基礎(chǔ)上給出動態(tài)誤分類代價下的代價敏感決策系統(tǒng)及其相關(guān)定義。

2.1 代價敏感決策系統(tǒng)

定義1代價敏感決策系統(tǒng)是一個七元組[8]：S=(U,C,D,V={Va|a∈C∪D},I={Ia|a∈C∪D},tc,smc),其中U是對象集合，C是條件屬性集合，D是決策屬性集合，Va是屬性a的值集合，Ia:U→Va是一個信息函數(shù)，tc:C→R+∪{0}是獨立測試代價函數(shù)，smc:k×k→R+∪{0}是靜態(tài)誤分類代價函數(shù)，k=|ID|。

獨立測試代價函數(shù)tc可以用一個代價向量tc=[tc(a1),tc(a2),…,tc(a|c|)]來表示。對任意屬性子集B?C,屬性子集B的測試代價為靜態(tài)誤分類代價函數(shù)smc可以用一個k×k矩陣來表示。smc(i,j)表示將類別i誤分為類別 j所導致的固定代價，通常smc(i,i)=$0。

一個代價敏感決策系統(tǒng)如表1和表2所示，靜態(tài)誤分類代價矩陣

表1 一個決策系統(tǒng)

表2 測試代價向量

2.2 動態(tài)誤分類代價機制

現(xiàn)有的大多數(shù)代價敏感屬性選擇算法，并未考慮所選屬性子集對誤分類代價的影響，而是對不同的數(shù)據(jù)集及其不同的屬性子集預(yù)先設(shè)置相同的誤分類代價。然而，在實際問題中，隨著檢測的屬性越多，錯分時所遭受的懲罰會越重?？梢?，誤分類代價與所選屬性子集之間具有一定的相關(guān)性。同時，在現(xiàn)實數(shù)據(jù)集中，類分布不均衡的情況是普遍存在的，錯分少數(shù)類所付出的代價往往大于錯分多數(shù)類所付出的代價。這里，假設(shè)類別i為少數(shù)類，類別j為多數(shù)類，對任意屬性子集B?C,定義動態(tài)誤分類代價dmc(B)為：

其中，當i≠j時，dmc(B)(i,j)為錯分少數(shù)類的誤分類代價，dmc(B)(j,i)為錯分多數(shù)類的誤分類代價，α和β為調(diào)整參數(shù)，以保證所得到的總代價最小。圖1給出了數(shù)據(jù)集Voting，在參數(shù)β值取1時，不同參數(shù)α值下總代價的變化情況。可見，dmc(B)(i,j)過大時，會使得總代價加大，通過參數(shù)α可以調(diào)整dmc(B)(i,j)的大小。同時，當數(shù)據(jù)集的規(guī)模增大時，所選屬性子集的大小會隨之變大，使得總代價增加。圖2給出了數(shù)據(jù)集Voting和Kr-vs-kp，在參數(shù)α值取0.1時，不同參數(shù)β值下總代價的對比情況。顯然，對于不同規(guī)模的數(shù)據(jù)集，為使得總代價最小，應(yīng)根據(jù)數(shù)據(jù)集的規(guī)模分別設(shè)置參數(shù)β的值。

圖1 不同參數(shù)α值下的總代價

圖2 不同參數(shù)β值下的總代價

以表1和表2為例，“d=0”為多數(shù)類，“d=1”為少數(shù)類，若B={a2,a5},α=0.5,β=1,由式（1）可得，dmc(B)(1,0)=

2.3 動態(tài)誤分類代價下代價敏感決策系統(tǒng)

定義2動態(tài)誤分類代價下的代價敏感決策系統(tǒng)是一個七元組：S=(U,C,D,V,I,tc,dmc),其中U、C、D、V、I和tc的定義與定義1中相同，dmc:k×k→R+∪{0}是動態(tài)誤分類代價函數(shù)，k=|ID|,可以用一個k×k矩陣來表示，矩陣元素值由式（1）計算得到。

為了評價所選屬性子集的優(yōu)劣，引入平均總代價概念。設(shè)B為一個屬性子集，IND(B)為U的一個劃分，對象集合U′∈IND(B),U′的動態(tài)誤分類代價記為dmc(U′,B),平均動態(tài)誤分類代價（Average Dynamic Misclassification Cost，ADMC）表示為：

平均總代價（Average Total Cost，ATC）表示為：

定義3設(shè)S是一個動態(tài)誤分類代價下的代價敏感決策系統(tǒng)，對于任意屬性子集B?C,當且僅當滿足ATC(U,B)=min{ATC(U,B′)|B′?C},則稱 B為最小平均總代價屬性子集。

3 動態(tài)誤分類代價下的代價敏感屬性選擇

本章將介紹分治法，并給出動態(tài)誤分類代價下的代價敏感屬性選擇分治算法。

3.1 分治法

目前，有些代價敏感屬性選擇算法存在效率低的問題，特別是對大規(guī)模數(shù)據(jù)集。分治法是一種簡單的粒計算方法，它將一個大的、難以直接解決的問題，分割成若干個問題相同且規(guī)模較小的子問題，以便逐一解決，分而治之。這將會節(jié)省時間，提高計算效率。顯然，分治法是一種處理大規(guī)模數(shù)據(jù)集的高效算法。

3.2 動態(tài)誤分類代價下代價敏感屬性選擇分治算法

代價敏感屬性選擇問題是在測試代價和誤分類代價之間權(quán)衡，使得所選屬性子集的總代價最小。為解決該問題，本文提出了動態(tài)誤分類代價下代價敏感屬性選擇分治算法（以下簡稱為算法1），算法思想以流程圖形式表示，如圖3所示。

圖3 算法1流程圖

在算法1中，參數(shù)size表示初始每個子數(shù)據(jù)集所包含的條件屬性個數(shù)，參數(shù)k表示每次參與合并的子數(shù)據(jù)集個數(shù)。為了控制每個子數(shù)據(jù)集的大小，并保證多路合并時有足夠多的子數(shù)據(jù)集，參數(shù)size值可根據(jù)各數(shù)據(jù)集規(guī)模的不同而變化。當參數(shù)size≤|C|/k時，能夠保證多路合并的有效性。若參數(shù)k=1，即參數(shù)size=|C|時，算法1退化為經(jīng)典的回溯算法。同時，為了提高算法的效果，在對各子數(shù)據(jù)集求解時，采用了競爭策略。

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

為驗證算法1的有效性，本文從UCI中選取六個不同規(guī)模的數(shù)據(jù)集進行實驗，并通過復(fù)制數(shù)據(jù)集Mushroom生成數(shù)據(jù)集DS。各數(shù)據(jù)集的描述如表3所示，其中|C|表示條件屬性的個數(shù)，|U|表示對象個數(shù)。因篇幅關(guān)系，本章的所有表中只列出各數(shù)據(jù)集的編號（No.），其編號和表3中的一致。另外，本章的所有圖中將“Housevotes-84”簡寫為“HV84”。

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

由于UCI數(shù)據(jù)集自身并不含測試代價，因此本文采用Uniform和Normal兩種分布方式[16]來生成測試代價，測試代價為[1，10]區(qū)間內(nèi)的整數(shù)。這兩種分布方式是日常生活中常見的概率分布，模擬了現(xiàn)實生活中不同的應(yīng)用，表明了算法能適用于不同的代價分布。為保證多路合并的有效性，本文根據(jù)數(shù)據(jù)集規(guī)模自適應(yīng)生成參數(shù)size的值，設(shè)置參數(shù)。另外，本文將參數(shù)α值設(shè)為0.1，參數(shù)β值根據(jù)數(shù)據(jù)集的規(guī)模分別設(shè)置：對前五個數(shù)據(jù)集，參數(shù)β值設(shè)為1；對后兩個數(shù)據(jù)集，參數(shù)β值設(shè)為0.3。本章的所有柱狀圖中，柱體的總高度均表示各數(shù)據(jù)集的平均總代價，而柱體空白部分的高度均表示各數(shù)據(jù)集的測試代價。

4.1 算法的效果

為了分析參數(shù)k對算法1的效果和效率的影響，這里，參數(shù)k值分別設(shè)為2、3和4進行對比實驗，實驗結(jié)果如圖4、表4和表5所示。

從圖4和表4可以看出：

（1）在前六個數(shù)據(jù)集中，隨著參數(shù)k值的增大，測試代價和平均總代價基本保持不變或減小。當參數(shù)k=2時，數(shù)據(jù)集Promoters的測試代價為$0。

（2）在各數(shù)據(jù)集上，隨著參數(shù)k值的增大，運行時間均減少，特別是對最后三個數(shù)據(jù)集。

圖4 不同參數(shù)k值下的平均總代價對比

表4 不同參數(shù)k值下的運行時間對比 ms

（3）從以上分析可見，當參數(shù)k值增大時，既保證了算法的效果，也提高了算法的效率，說明該分治算法是有效的。

表5列出了各數(shù)據(jù)集在不同參數(shù)k值下，由式（1）生成的動態(tài)誤分類代價。從表5可以看出：

（1）對于同一數(shù)據(jù)集，隨著參數(shù)k值的增大，各數(shù)據(jù)集的動態(tài)誤分類代價的變化不大，保證了該分治算法的穩(wěn)定性。

（2）對于不同規(guī)模的數(shù)據(jù)集，在參數(shù)β的調(diào)節(jié)作用下，動態(tài)誤分類代價未發(fā)生顯著變化，說明參數(shù)β的調(diào)節(jié)是有效的，其值應(yīng)根據(jù)數(shù)據(jù)集的規(guī)模分別設(shè)置。

準確率是平均誤分類代價的特例。當誤分類代價矩陣主對角線上的值均為0，且副對角線上的值均相等時，最小化平均誤分類代價等價于最大化準確率[8]。為了計算算法1下的準確率，設(shè)置dmc(0,1)=dmc(1,0)=280×|C|，并選取小規(guī)模數(shù)據(jù)集Voting、中等規(guī)模數(shù)據(jù)集Mushroom和大規(guī)模數(shù)據(jù)集DS進行實驗。實驗運行100次，統(tǒng)計平均總代價等于測試代價的概率，從而得到準確率，實驗結(jié)果如表6所示。從表6可以看出，隨著參數(shù)k值的增大，準確率更好。

表5 不同參數(shù)k值下的動態(tài)誤分類代價 美元

表6 不同參數(shù)k值下的準確率對比

4.2 算法的有效性

為了驗證動態(tài)誤分類代價機制的有效性，本文取參數(shù)k=3，分別在靜態(tài)誤分類代價機制和動態(tài)誤分類代價機制下進行算法1的對比實驗，實驗結(jié)果如圖5和表7所示。在靜態(tài)誤分類代價機制下，設(shè)置smc(0,1)=$800,smc(1,0)=$200；而動態(tài)誤分類代價則由式（1）生成。

表7 兩種誤分類代價機制下的運行時間對比 ms

從圖5和表7可以看出：

（1）動態(tài)誤分類代價下的平均總代價和測試代價均小于或等于靜態(tài)誤分類代價下的平均總代價和測試代價。

（2）在前四個數(shù)據(jù)集上，兩種誤分類代價機制下的運行時間基本相同；在后三個數(shù)據(jù)集上，動態(tài)誤分類代價下的運行時間較少，特別是數(shù)據(jù)集DS和Promoters上的運行時間差距明顯。

圖5 兩種誤分類代價機制下的平均總代價對比

（3）從以上分析可見，采用動態(tài)誤分類代價機制，可以在不影響算法效率的同時，提高算法的效果，說明該動態(tài)誤分類代價機制是有效的。

4.3 幾種算法的實驗對比

為進一步驗證算法1的有效性，本節(jié)選取了表3中的四個數(shù)據(jù)集House-votes-84、Voting、DS和Kr-vs-kp，在Uniform分布方式下，將算法1、文獻[8]的回溯算法和文獻[9]的啟發(fā)式算法進行對比實驗，實驗結(jié)果如圖6和表8所示。在算法1中，參數(shù)k值設(shè)為3，動態(tài)誤分類代價由式（1）生成；在另兩個算法中，設(shè)smc(0,1)=$1 200,smc(1,0)=$300。

圖6 Uniform分布下三種算法平均總代價對比

表8 Uniform分布下三種算法運行時間對比ms

從圖6和表8可以看出：

（1）在數(shù)據(jù)集House-votes-84、Voting和Kr-vs-kp上，算法1的測試代價和平均總代價均小于其他兩個算法。在數(shù)據(jù)集DS上，回溯算法的效果最好，算法1略好于啟發(fā)式算法。

（2）在這四個數(shù)據(jù)集上，算法1的運行時間均小于其他兩個算法，特別是在數(shù)據(jù)集DS和Kr-vs-kp上，算法1的運行時間明顯減少。

（3）從以上分析可見，算法1的整體性能優(yōu)于其他兩種算法，并且在較大規(guī)模數(shù)據(jù)集上的效率明顯高于其他兩種算法，說明動態(tài)誤分類代價下的代價敏感屬性選擇分治算法是有效的。

5 結(jié)束語

本文針對靜態(tài)誤分類代價機制的不足，考慮了誤分類代價與所選屬性子集之間的相關(guān)性，設(shè)計了動態(tài)誤分類代價函數(shù)，并結(jié)合分治思想，提出了動態(tài)誤分類代價下的代價敏感屬性選擇分治算法，最后從多方面進行了對比實驗。實驗結(jié)果表明，相對于靜態(tài)誤分類代價機制，本文所提出的算法能在提高計算效率的同時改善運行效果，驗證了該分治算法和動態(tài)誤分類代價機制的有效性。本文僅對動態(tài)誤分類代價機制進行了初步的探討，在今后的工作中：（1）除了用初等函數(shù)來表示動態(tài)誤分類代價，還可以采用復(fù)合函數(shù)來表示動態(tài)誤分類代價。（2）在復(fù)合函數(shù)中，除了考慮動態(tài)誤分類代價與屬性子集的相關(guān)性，是否還可以考慮與數(shù)據(jù)集樣本數(shù)的關(guān)系。動態(tài)誤分類代價是實際應(yīng)用中存在的客觀問題，有待進一步研究。

[1]Yang Qiang，Wu Xindong.10 challenging problems in data mining research[J].InternationalJournalofInformation Technology&Decision Making，2006，5（4）：597-604.

[2]Turney P D.Types of cost in inductive concept learning[C]//Proceedings of the Workshop on Cost-Sensitive Learning at the 17th ICML，California，2000：15-21.

[3]Hsu J L，Hung P C，Lin H Y，et al.Applying undersampling techniques and cost-sensitive learning methods on risk assessment of breast cancer[J].Journal of Medical Systems，2015，39（4）：1-13.

[4]Fan Jianping，Zhang Ji，Mei Kuizhi，et al.Cost-sensitive learning of hierarchical tree classifiers for large-scale image classification and novel category detection[J].Pattern Recognition，2015，48（5）：1673-1687.

[5]Li Huaxiong，Zhang Libo，Huang Bing，et al.Sequential three-way decision and granulation for cost-sensitive face recognition[J].Knowledge-Based Systems，2016，91：241-251.

[6]Lu J，Liong V E，Zhou J.Cost-sensitive local binary feature learning for facial age estimation[J].IEEE Transactions on Image Processing，2015，24（12）：5356-5368.

[7]Jahromi A T，Stakhovych S，Ewing M.Customer churn models：a comparison of probability and data mining approaches[M]//Looking forward，looking back：drawing on the past to shape the future of marketing.[S.l.]：Springer International Publishing，2016：144-148.

[8]Min F，Zhu W.Minimal cost attribute reduction through backtracking[M]//Database theory and application，bioscience and bio-technology.Berlin/Heidelberg：Springer，2011：100-107.

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

[10]Weiss Y，Elovici Y，Rokach L.The CASH algorithm-costsensitive attribute selection using histograms[J].Information Sciences，2013，222：247-268.

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

[12]Shu Wenhao，Shen Hong.Multi-criteria feature selection on cost-sensitive data with missing values[J].Pattern Recognition，2016，51：268-280.

[13]Dai Jianhua，Han Huifeng，Hu Qinghua，et al.Discrete particle swarm optimization approach for cost sensitive attribute reduction[J].Knowledge-Based Systems，2016.

[14]Fan Anjing，Zhao Hong，Zhu W.Test-cost-sensitive attribute reduction on heterogeneous data for adaptive neighborhood model[J].Soft Computing，2015：1-12.

[15]Krawczyk B，Wo?niak M，Schaefer G.Cost-sensitive decision tree ensembles for effective imbalanced classification[J].Applied Soft Computing，2014，14：554-562.

[16]Min Fan，He Huaping，Qian Yuhua，et al.Test-cost-sensitive attribute reduction[J].Information Sciences，2011，181（22）：4928-4942.