基于沖突域的測試成本獨立決策系統(tǒng)屬性約簡

向恒月，楊思春，王小林，王 雷

（安徽工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，安徽馬鞍山243032）

基于沖突域的測試成本獨立決策系統(tǒng)屬性約簡

向恒月，楊思春，王小林，王 雷

（安徽工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，安徽馬鞍山243032）

針對決策系統(tǒng)存在沖突對象的情況，提出一個基于沖突域的λ-權(quán)重約簡的啟發(fā)式算法來降低屬性約簡的測試成本。首先對決策系統(tǒng)進(jìn)行簡化，將不一致對象的決策屬性值異類化，進(jìn)而刪除重復(fù)對象，然后對簡化后的決策系統(tǒng)根據(jù)沖突強(qiáng)弱計算出核屬性和屬性重要性,在此基礎(chǔ)上，利用啟發(fā)式函數(shù)來求解測試成本較低的屬性約簡，其中啟發(fā)式函數(shù)由屬性重要性和權(quán)重共同組成，權(quán)重由測試成本和非正參數(shù)λ決定。實驗結(jié)果表明該方法在保證降低測試成本的同時加快處理效率。

決策系統(tǒng)；測試成本獨立；沖突域；屬性約簡

在模式識別、數(shù)據(jù)挖掘中，屬性約簡是粗糙集領(lǐng)域特殊類型的特征選擇問題[1]。屬性約簡的目的是保留必要屬性，刪除冗余屬性，將隱含在數(shù)據(jù)中的知識用最簡決策規(guī)則表示出來，其核心步驟是分類。分類通常有兩個目標(biāo)：降低測試成本；提高分類的準(zhǔn)確性。在很多應(yīng)用中，數(shù)據(jù)庫中的數(shù)據(jù)免費(fèi)可用，故目前有很多文獻(xiàn)研究分類準(zhǔn)確性這個問題，較有效的方法有：人工神經(jīng)網(wǎng)絡(luò)[2]，貝葉斯網(wǎng)絡(luò)[3]，決策樹[4-5]，支持向量機(jī)[6]。另外一些應(yīng)用中的數(shù)據(jù)不免費(fèi)提供，每個數(shù)據(jù)項均有測試成本，因此需要用較低的測試成本獲得正確分類。然而現(xiàn)有對降低成本的研究較少，文獻(xiàn)[7]提出了一種以信息增益為基礎(chǔ)的λ-權(quán)重約簡算法，由測試成本和非正參數(shù)λ決定權(quán)重，研究結(jié)果表明利用競爭方法選擇一個合適的λ參數(shù)能顯著提高結(jié)果的質(zhì)量，但該研究沒有找到對任何數(shù)據(jù)庫均有效最優(yōu)的λ值。

在數(shù)據(jù)收集過程中，數(shù)據(jù)不一致（沖突）是常見現(xiàn)象。文獻(xiàn)[8]針對決策表中對象沖突的情況，設(shè)計基于沖突域的高效屬性約簡算法。文獻(xiàn)[9]針對非完全不一致決策表將原決策表中不一致對象的決策屬性值異類化，再消除重復(fù)對象得到簡化決策表，再利用沖突域求解屬性約簡以提高屬性約簡算法的效率。文獻(xiàn)[7]設(shè)計了基于信息增益的λ-權(quán)重約簡算法，求出測試成本獨立決策系統(tǒng)的一個相對測試成本較低的屬性約簡，算法的時間復(fù)雜度為O(|U|2|C|3)，空間復(fù)雜度為O(|U||C|)[7]。為進(jìn)一步提高測試成本獨立決策系統(tǒng)求屬性約簡的效率，本文對基于信息增益的λ-權(quán)重約簡方法進(jìn)行改進(jìn)，提出了基于沖突域的λ-權(quán)重約簡方法。

1 測試成本獨立決策系統(tǒng)

1.1 基本概念

定義1[10]一個決策系統(tǒng)S是一個5元組

其中，U為論域，是對象的集合，U={x1,x2,…,xn}；C為條件屬性集，D為決策屬性集；Va是屬性α∈C?D的值域；Ia為信息函數(shù) Ia∶U→Va,?α∈C?D,x∈U有Ia(x)∈Va不失一般性，也為了便于操作，假設(shè)D僅有一個決策屬性值。決策系統(tǒng)S中，若?xi,xj∈U(i≠j)，有IC(xi)=IC(xj)∧ID(xi)≠ID(xj)，則稱S為不一致決策系統(tǒng)，xi與xj稱為不一致對象（或稱沖突對象），否則稱S為一致決策系統(tǒng)。

定義2[10]一個測試成本獨立決策系統(tǒng)是一個6元組

其中c∶C→R+?{0}是屬性的成本函數(shù)。

通常測試成本是非負(fù)的(R+?{0})，條件屬性集的所有屬性的測試成本可以用一個向量表示c=[c(a1),c(a2),……,c(a|C|)]。由于λ-權(quán)重函數(shù)要求測試成本是非負(fù)值，不能取零，故文中規(guī)定：若有個別屬性的獲得不需要測試成本，仍然以一個很小的正值表示其測試成本。

性質(zhì)1[10]設(shè)c*表示屬性子集的成本函數(shù)，一個測試成本獨立決策系統(tǒng)有如下性質(zhì)：(1)c*(?)=0；(2)c*({a})=c(a)?a∈C；(3)

定義3在一個測試成本獨立決策系統(tǒng) S=(U,C,D,{Va|α∈C?D}，{Ia|α∈C?D},c)中，新的決策系統(tǒng)S'=(U,C,D,{V'a|α∈C?D}，{I'a|α∈C?D},c)，滿足：

其中Vξ表示不同于S中任何決策屬性的值。

由定義3可知，決策系統(tǒng)S’是將原決策系統(tǒng)S中不一致對象的決策屬性值均異類化為Vξ。

定義4在測試成本獨立決策系統(tǒng) S’=(U,C,D,{V’a|α∈C?D}，{I'a|α∈C?D},c)中，設(shè)U/C={[x1]C,[x2]C,…,[xn]C}，令U’={x1,x2,…,xn}；則稱S*=(U’,C,D,{V’a|α∈C?D}，{I’a|α∈C?D},c)為簡化決策系統(tǒng)。

由定義4可知，S*是將S’中重復(fù)對象刪除后得到的決策系統(tǒng)。

1.2 測試成本的設(shè)定

帕雷托分布(Pareto distribution)產(chǎn)生的一組隨機(jī)數(shù)中包含許多小數(shù)值和少量大數(shù)值[11]，所以用帕雷托分布來隨機(jī)產(chǎn)生測試成本更符合實際要求。

為了使實驗結(jié)果與文獻(xiàn)[7]具有可比性，本文將變量的取值設(shè)定與文獻(xiàn)[7]相同，變量?取2，p(M,N,x)的取值區(qū)間是(M,N+1)，cp(N,N,x)的取值區(qū)間是[M,N]，并設(shè)M=1,N=100。

1.3 評估標(biāo)準(zhǔn)

處理較低測試成本的屬性約簡問題有很多不同的算法，因此需要一個評估標(biāo)準(zhǔn)來比較不同算法的表現(xiàn)，本文用找到最優(yōu)約簡的概率來作為評估標(biāo)準(zhǔn)。設(shè)總實驗次數(shù)記為K，找到最優(yōu)約簡的次數(shù)記為k，找到最優(yōu)約簡的概率記為f=k/K。

在實驗部分，對同一個決策系統(tǒng)會產(chǎn)生不同的測試成本，也并非每次得到的約簡都是最優(yōu)約簡，因此用找到最優(yōu)約簡的概率既能定性又能定量的衡量一個算法的性能。

2 基于沖突域的λ-權(quán)重約簡

文獻(xiàn)[7]中是基于信息熵來獲得信息增益，在此基礎(chǔ)上給測試成本一個權(quán)重，共同構(gòu)成λ-權(quán)重函數(shù)，在文獻(xiàn)[7]中的時間復(fù)雜度為O(|U|2|C|3)，空間復(fù)雜度為O(|U||C|)，顯然這個時間復(fù)雜度比較高,且基于信息熵設(shè)計屬性約簡算法通常只要求H(D|R)=H(D|C),并不要求?r∈R均有H(D|R－{r})≠H(D|C),只有要求這一點而設(shè)計的屬性約簡算法才通常稱為完備的屬性約簡[12]。為了保證算法的完備性，文獻(xiàn)[7]中的算法在最后加上了消除冗余屬性的檢查，這樣無疑增加了算法的執(zhí)行時間。

2.1 啟發(fā)式函數(shù)的設(shè)計

文獻(xiàn)[7]當(dāng)中核屬性的計算采用正區(qū)域方法，對象之間頻繁的比較運(yùn)算難以避免，但是利用沖突域的方法求核屬性，既可以避免這個問題，同時也避免了采用可分辨矩陣所需的大量空間和時間開銷。

屬性集R關(guān)于決策屬性D的沖突域ConSet(R)的定義見文獻(xiàn)[8-9]，這里不再詳細(xì)介紹。

定義6|ConSet(R)|表示ConSet(R)中沖突對象的數(shù)目，如果|ConSet(R)|＞|ConSet(P)|,則稱R相對D的沖突強(qiáng)度大于P相對D的沖突強(qiáng)度。

定義7[8]屬性a的重要性sig(a,R,D)=|ConSet(R)|－|ConSet(R∪{a})|。

為了求出測試成本獨立決策系統(tǒng)的一個較低測試成本的屬性約簡，給測試成本一個權(quán)重，啟發(fā)式函數(shù)離不開屬性重要性和測試成本這兩方面，因此本文的啟發(fā)式函數(shù)定義如下：

定義8基于沖突域的λ-權(quán)重約簡的啟發(fā)式函數(shù)f(R,ai,ci)=(|ConSet(R)|－|ConSet(R∪{ai})|)ciλ。

2.2 約簡過程

求測試成本獨立決策系統(tǒng)的屬性約簡，其思路是先根據(jù)定義3和定義4將原決策系統(tǒng)進(jìn)行簡化，然后求出核屬性，再根據(jù)啟發(fā)式函數(shù)依次加入函數(shù)值大的屬性，直到得到較低測試成本的屬性約簡為止，最后對非核屬性進(jìn)行反向消除，以確保約簡的完備性。圖1是針對測試成本獨立決策系統(tǒng)求解測試成本較低的屬性約簡的流程圖。

3 實驗比較

采用本文算法和UCI數(shù)據(jù)庫中4個數(shù)據(jù)集為實驗數(shù)據(jù)，對文獻(xiàn)[7]中的約簡算法和本文的約簡算法進(jìn)行測試（實驗環(huán)境為T6600 2.2 GHz，內(nèi)存2 GB，eclipse3.6.1），通過f(R,ai,ci)=(|ConSet(R)|－|ConSet(R∪{ai})|)ciλ可知，當(dāng)λ=0時，本文算法就是基于沖突域漸減的屬性約簡算法，沒有考慮測試成本。Patient數(shù)據(jù)集有8個條件屬性，表1是帕雷托分布(Pareto distribution)產(chǎn)生的10組測試成本，其他數(shù)據(jù)集測試成本就不一一例舉。測試均是每個數(shù)據(jù)集設(shè)定100個不同的測試成本，也就是每個數(shù)據(jù)集都是試驗900次。文獻(xiàn)[7]中的約簡算法和本文的約簡算法的比較結(jié)果見表2。

表1 Pareto分布產(chǎn)生的測試成本Tab.1 Test cost settings of Pareto distribution

表2 兩個約簡算法的比較Tab.2 Comparison between the two reduction algorithms

由表2可知，本文算法的執(zhí)行時間要低于文獻(xiàn)[7]中的算法，雖然兩種算法采用的啟發(fā)式算法都是先求解核屬性，但是文獻(xiàn)[7]在計算核屬性的時候用的是正區(qū)域的方法，對象之間頻繁的比較運(yùn)算會增加算法執(zhí)行的時間。

本文設(shè)計的啟發(fā)式函數(shù)，其中λ是唯一可由用戶設(shè)定的參數(shù)，為了提高算法的性能，希望設(shè)置一個λ值，可以使得找到最優(yōu)約簡的概率最大。圖2是根據(jù)不同λ和找到最優(yōu)約簡的概率所畫出的折線圖。λ取0就是沒有權(quán)重函數(shù)，沒有考慮測試成本，因為Patient數(shù)據(jù)集僅有一個屬性約簡，所以不管λ取多少，這個僅有的約簡就是最優(yōu)約簡，所以找到最優(yōu)約簡的概率都是1.0，其他3個數(shù)據(jù)集會隨著λ的減小，找到最優(yōu)約簡的概率先上升后趨于平穩(wěn)。從圖2中可以看出當(dāng)λ取-1.25時，這四個數(shù)據(jù)集的找到最優(yōu)約簡的概率最大。

4 結(jié) 語

降低測試成本是屬性約簡的一個新的研究趨勢，也有其潛在的應(yīng)用領(lǐng)域。已有的求測試成本較低的屬性約簡問題因為使用正區(qū)域方法計算核屬性，使得算法的時間復(fù)雜度較高。為了降低時間復(fù)雜度，提高效率，本文對測試成本獨立決策系統(tǒng)的屬性約簡問題進(jìn)行了研究，針對決策系統(tǒng)存在沖突對象這一情況，先對決策表進(jìn)行簡化，然后提出一個基于沖突域的λ-權(quán)重約簡算法，根據(jù)沖突強(qiáng)弱計算核屬性和屬性重要性,避免正區(qū)域方法求核屬性時的頻繁比較運(yùn)算。最后，通過實驗驗證本文算法相對應(yīng)同類算法，有一定的優(yōu)越性。

[1]Min F,Hu Q,Zhu W.Feature selection with test cost constraint[J].International Journal of Approximate Reasoning,2014,55(1): 167-179.

[2]Hornik K,Stinchcombe M,White H.Multilayer feedforward networks are universal approximators[J].Neural Networks,1989, 2(5):359-366.

[3]Domingos P,Pazzani M.On the optimality of the simple Bayesian classifier under zero-one loss[J].Machine Learning,1997, 29(2):103-130.

[4]Quinlan J R.C4.5 Programs for Machine Learning[M].San Mateo,California:Morgan Kaufmann Publisher,1993:235-240.

[5]Yi W,Lu M,Liu Z.Multi-valued attribute and multi-labeled data decision tree algorithm[J].International Journal of Machine Learning and Cybernetics,2011,2(2):67-74.

[6]Vapnik V,Chervonenkis A.On the uniform convergence of relative frequencies of events to their probabilities[J].Theory of Probability and ItsApplication,1971,16(2):264-280.

[7]Min F,He H,Qian Y,et al.Test-cost-sensitive attribute reduction[J].Information Sciences,2011,181(2):4928-4942.

[8]葛浩，李龍澍，楊傳健.基于沖突域的高效屬性約簡算法[J].計算機(jī)學(xué)報,2012,35(2):342-350.

[9]葛浩，李龍澍，楊傳健.基于沖突域漸減的屬性約簡算法[J].系統(tǒng)工程理論與實踐,2013,33(9):2371-2380.

10]Yao Y.Apartition model of granular computing[M]//Transactions on Rough Sets I.Springer Berlin Heidelberg,2004:232-253.

[11]帕累托分布[Z/OL].(2013-03-09)[2014-09-20].http://site.douban.com/182577/widget/notes/10567181/note/265696846/.

[12]徐章艷，侯偉，宋威，等.一個有效的基于信息熵的啟發(fā)式屬性約簡算法[J].小型微型計算機(jī)系統(tǒng),2009,30(9):1805-1810.

責(zé)任編輯：丁吉海

Attribute Reduction in Test-cost-independent Decision System Based on Conflict Region

XIANG Hengyue,YANG Sichun,WANG Xiaolin,WANG Lei
(School of Computer Science and Technology,Anhui University of Technology,Ma'anshan 243032,China)

With pertinence to the conflict object existing in decision system,a heuristic algorithm based on conflict region λ-weighted reduction was proposed for the purpose of decreasing attribute reduction’s test cost.Firstly,decision system was simplified,decision attribute value of inconsistent object was paganized,and the duplicate objects were deleted.Then core attribute and attribution importance were calculated according to the conflict intensity on the simplified decision system,and based on these,using the heuristic function a lower test cost attribute reduction was solved,where the heuristic function was composed of attribution importance and weights,and weights were decided by test cost and a non-positive exponentλ.The experimental result shows that the method can reduce test cost and speed up processing efficiency.

decision system;test-cost-independent;conflict region;attribute reduction

TP391

A

10.3969/j.issn.1671-7872.2015.04.015

2015-02-28

安徽省高校自然科學(xué)研究重點項目(KJ2011A048)；安徽工業(yè)大學(xué)研究生創(chuàng)新研究基金項目(2013080)

向恒月(1990-)，女，安徽合肥人，碩士生，主要研究方向為粗糙集。

楊思春(1970-)，男，安徽六安人，博士，教授，主要研究方向為自然語言處理、粗糙集、信息檢索和概念格。

1671-7872(2015)-04-0378-05