測試代價受限下數據的屬性和粒度選擇方法

廖淑嬌，朱清新，梁 銳

(1.電子科技大學信息與軟件工程學院，四川 成都 610054;2.閩南師范大學數學與統計學院，福建 漳州 363000)

1 引言

代價敏感學習是數據挖掘領域的一個重要研究方向[1]。迄今為止，不少學者已對其理論和應用進行了較為深入的研究[2 - 11]。一般來說，相比主要追求高分類精度的非代價敏感學習方法，代價敏感學習技術由于考慮了現實的代價因素，因此更有實際意義。測試代價和誤分類代價是最常考慮的兩種代價[12]。其中，測試代價(也稱獲取代價)是指人們為了獲得樣本(也稱對象)某個數據項的值而對該樣本進行測試所付出的代價，例如醫療檢查中抽血檢驗所花費的金錢就是該檢查項目的測試代價。當一個樣本具有多個數據項，即具有多個屬性時，所檢測的所有屬性的測試代價之和稱為總測試代價。而誤分類代價則是由錯誤分類所導致的代價，不同的分類錯誤經常造成不同大小的代價。例如，在銀行發放貸款的風險評估中，將低信用等級的客戶誤評為高信用等級一般比將高信用等級的客戶誤評為低信用等級具有更高的誤分類代價。

在數據值的獲取/測試過程中，由于觀測者的水平不同或者觀測工具的條件有限，觀測誤差廣泛存在。對于同一個量來說，不同人或不同工具得到的觀測誤差一般服從正態分布。數據的誤差范圍越大，它的粒度就越粗，反之則越細。以往的代價敏感學習經常假設測試代價和誤分類代價是固定不變的，事實上這兩類代價往往都是可變的。一方面，測試代價與數據粒度有密切的關系，要得到越精確的數據值，即希望數據粒度越細時，需要的測試代價往往越高。另一方面，誤分類代價又常受總測試代價大小的影響，對于同樣的錯誤分類，當已付出的總測試代價越高時，誤分類代價也常常跟著增多。此外，現實中還存在測試代價受限，即總測試代價受到一定約束的情況。

在當今的大數據時代，一個數據集經常含有很多個屬性，這導致了數據分類處理的復雜性。作為一種常用的數據預處理技術，屬性選擇著力于去除數據集中冗余或不相關的屬性，從而提高數據后續處理的效率。此外，粒度也是數據處理中經常考慮的一個問題。雖然已經有學者分別研究了測試代價受限情況下的屬性選擇[13]和不受限情況下的粒化問題[14]，但并沒有考慮到測試代價受限下屬性和粒度的同步選擇。基于這種情況，本文著眼于研究在測試代價受限的情形下，基于誤差和可變代價的屬性和粒度選擇方法，其中粒度選擇指的是選擇數據合適的誤差范圍。

本文以最小化數據集在測試與分類過程中所付出的平均總代價(總代價的平均值)為目標，提出了一種測試代價受限的屬性和粒度同步選擇的方法，其中數據的粒度用觀測誤差的置信水平來衡量。誤差置信水平越高，數據粒度越粗。本文首先建立了包含誤差置信水平、誤差區間、鄰域模型和可變的代價函數等內容的理論模型；接著提出了一個高效的屬性和粒度選擇的算法，其中運用了三個剪枝技術以提高算法的效率；最后，在多個UCI數據集的實驗結果表明，所提算法能針對不同大小的總測試代價約束進行有效的屬性和粒度選擇，并且揭示了算法所得的最優屬性子集和最優數據粒度隨著總測試代價上限的大小變化的規律。

2 理論模型

本節建立理論模型，從而為下一節的算法設計提供理論依據。首先根據置信水平和置信區間的關系給出了屬性的誤差邊界和誤差區間的計算方法；接著建立了基于誤差置信水平的鄰域模型，然后結合現實情況分別設計了可變的測試代價函數和誤分類代價函數；最后給出了數據集中對象測試與分類的平均總代價的計算方法。

2.1 誤差置信水平與誤差區間

根據數據觀測誤差的特點，假設誤差服從均值為0的正態分布，而數據粒度的大小用誤差置信水平來衡量。如前文所述，一個數據集經常含有多個屬性，令σa表示數據集中所有對象關于屬性a的觀測誤差所服從的正態分布的標準差，e(a,p)表示這些對象關于屬性a和置信水平p的觀測值的誤差邊界，則有:

e(a,p)=σa·zp

(1)

(2)

其中，λ>0為調節系數。結合式(1)和式(2)，可以計算得到數據集中對象關于屬性a和置信水平p的誤差邊界e(a,p),從而得到誤差區間[-e(a,p),+e(a,p)]。顯然，誤差邊界和誤差區間隨著置信水平的增大而增大，這時數據精度下降，數據粒度變粗。

2.2 基于誤差置信水平的鄰域模型

決策系統和鄰域是數據挖掘中的常用概念。本節分別給出基于誤差置信水平的決策系統和鄰域的定義如下。

定義1稱六元組S=(U,C,D,V,I,p)為基于誤差置信水平的決策系統ECLDS(Error-Confidence-Level-based Decision System)，其中，U為對象的集合，稱為論域；C為條件屬性的集合;D為決策屬性的集合；V={Va|a∈C∪D}，Va為屬性a的值域；I={Ia|a∈C∪D},Ia:U→Va為信息函數；p∈(0,0.997]為誤差置信水平。

定義2設S=(U,C,D,V,I,p)為一個ECLDS，則對于任意的x∈U,a∈C,對象x的基于屬性a和誤差置信水平p的鄰域為：

N(a,p)(x)={y∈U‖a(y)-a(x)|≤2e(a,p)}

(3)

這里分析選擇2e(a,p)而不是e(a,p)作為鄰域中對象的最大距離的原因。在誤差環境中a(x)是對象x關于屬性a的觀測值，設x關于屬性a的真實值為a′(x),則有a′(x)-e(a,p)≤a(x)≤a′(x)+e(a,p),即a′(x)-e(a,p)和a′(x)+e(a,p)可能為同一個對象的觀測值，這時|(a′(x)+e(a,p))-(a′(x)-e(a,p))|=2e(a,p),所以對象x的鄰域N(a,p)(x)必須包含所有觀測值跟a(x)的距離不超過2e(a,p)的對象。

由式(3)可知，對于任意的x∈U,B?C,x基于屬性子集B和誤差置信水平p的鄰域為：

N(B,p)(x)=∩a∈BN(a,p)(x)

(4)

即對象關于屬性子集的鄰域是關于單個屬性的鄰域的交集。由以上鄰域的定義及分析可知，一個對象的鄰域中的所有元素跟這個對象本身是不可區分的。

由式(3)和式(4)，可得到鄰域N(B,p)(x)分別關于屬性子集B和誤差置信水平p的單調性，如以下兩個定理所示。

定理1(關于屬性子集的單調性) 設S=(U,C,D,V,I,p)為一個ECLDS，B1?B2?C,則對于任意的x∈U,有：

N(B1,p)(x)?N(B2,p)(x)

定理2(關于置信水平的單調性) 設S=(U,C,D,V,I,p)為一個ECLDS，B?C,p1

N(B,p1)(x)?N(B,p2)(x)

由以上兩個定理可知，同一個對象的鄰域隨著屬性子集的增大而縮小，隨著誤差置信水平的增大而擴大。

2.3 可變的代價函數

本小節根據現實中測試代價和誤分類代價變化的特點來設計這兩類代價函數。

首先討論屬性的測試代價。如前面所述，一個屬性的測試代價一般隨著數據粒度的變細而增加，而數據粒度用誤差置信水平來衡量；當置信水平增加時，數據精度下降，數據粒度變粗，所以測試代價是誤差置信水平的單調遞減函數。用tc(a,p)表示屬性a基于置信水平p的測試代價，設：

(5)

tc(B,p)=∑a∈Btc(a,p)

(6)

即總測試代價是屬性集中每個屬性測試代價的和。

接著討論對象的誤分類代價。如前所述，誤分類代價經常隨著總測試代價的增加而增大。令二元組(h,k)表示把屬于第h類的對象誤分到第k類，簡稱為一個誤分類別對，mc(h,k)(B,p)表示誤分類別對(h,k)在屬性子集為B和置信水平為p的條件下的誤分類代價。顯然，當h=k即正確分類時，mc(h,k)(B,p)=0。當h≠k時，令：

tc(B,p)∈[TTCj-1,TTCj],j=1,2,…,n

(7)

值得注意的是，由于篇幅所限，本文僅給出分段常值函數形式的測試代價和誤分類代價函數，研究者也可根據實際情況設計其他類型的代價函數。

2.4 平均總代價的計算方法

如前所述，本文以最小化論域中對象測試與分類的平均總代價為目標，尋找最優的屬性子集和數據粒度。平均總代價由兩部分組成：論域中對象的平均測試代價和平均誤分類代價。為了簡便起見，本文假設論域中每個對象的測試屬性集和誤差置信水平都分別一樣，顯然這些對象基于屬性子集B和置信水平p的平均測試代價等于每個對象分別的總測試代價，即為tc(B,p)。

接下來分析平均誤分類代價的計算方法。第一步也是關鍵的步驟是，對于論域中的每個對象，根據其鄰域的情況對其進行分類，得到該對象的誤分類代價，分類依據是一個鄰域中對象的不可區分性以及最小化鄰域中對象的總誤分類代價這兩個原則。具體地，用mc(x,B,p)表示對象x基于屬性子集B和誤差置信水平p的誤分類代價，則根據鄰域N(B,p)(x)的情況有兩種可能：(1)當N(B,p)(x)中所有對象的決策屬性值一樣時，則可以將這些對象包括x分到正確的類別，這時mc(x,B,p)=0;(2)當N(B,p)(x)中對象的決策屬性值不完全一樣時，則根據使N(B,p)(x)中所有對象的誤分類代價總和最小的原則將x分到相應的類別，這時即可得到mc(x,B,p)。接著，計算論域U中對象的總誤分類代價和平均誤分類代價，分別為：

TMC(U,B,p)=∑x∈Umc(x,B,p)

(8)

和

AMC(U,B,p)=TMC(U,B,p)/|U|

(9)

綜上，可得平均總代價為：

ATC(U,B,p)=tc(B,p)+AMC(U,B,p)

(10)

3 算法設計

本節設計了測試代價受限情形下數據的屬性和粒度同步選擇的算法。該算法由算法1和算法2組成。

算法1測試代價受限的屬性和粒度同步選擇算法

輸入：決策系統S=(U,C,D,V,I,p), 總測試代價的上限值w,最小置信水平p0,置信水平的遞增步長r,每個屬性的測試代價函數，每個誤分類別對相應的誤分類代價函數。

輸出：全局的最小平均總代價gmtc和最優屬性子集R*以及最優誤差置信水平p*。/*它們都是全局變量*/

(1)gmtc=+∞;//gmtc表示全局最小平均總代價

(2) for (p=p0;p≤0.997;p=p+r) do

(3) 得到置信水平p下每個屬性a的測試代價tc(a,p);

(4)cmtc=+∞;/*cmtc表示當前置信水平下最小平均總代價*/

(5)B=?;//當前測試屬性集

(6)cttc=0;//當前的總測試代價

(7)backtracking(B,cttc,1);/*調用算法2，得到cmtc和R*/

(8) if (cmtc

(9)gmtc=cmtc;//更新全局最小平均總代價

(10)R*=R;//更新全局最優屬性子集

(11)p*=p;//更新最優置信水平

(12) end if

(13) end for

算法2回溯算法backtracking(B,cttc,l)

輸入：當前的測試屬性集B和總測試代價cttc，以及當前搜索路徑下屬性指標的起始值l。

輸出：當前置信水平下的最小平均總代價cmtc和最優屬性子集R。/*它們都是全局變量*/

(1) for (i=l;i≤|C|;i++) do

(2) if (tc(ai,p)≥cmtc||tc(ai,p)>w) then

(3) continue;//剪枝，摒棄測試代價過高的屬性

(4) end if

(5)B=R∪{ai};

(6)tc(B,p)=cttc+tc(ai,p);

(7) if (tc(B,p)≥cmtc||tc(B,p)>w) then

(8) continue;/*剪枝，摒棄總測試代價過高的屬性子集*/

(9) end if

(10) 得到每個誤分類別對(h,k)相應的誤分類代價mc(h,k)(B,p);

(11) 計算每個對象的鄰域和誤分類代價；

(12) 計算平均誤分類代價AMC(U,B,p);

(13)ATC(U,B,p)=tc(B,p)+AMC(U,B,p);

(14) if (ATC(U,B,p)

(15)cmtc=ATC(U,B,p);/*更新當前最小平均總代價*/

(16)cttc=tc(B,p);//更新當前總測試代價

(17)R=B;//更新當前最優屬性子集

(18) end if

(19)backtracking(B,cttc,i+1);//再下一層搜索

(20) end for

算法1中，誤差置信水平由最小值p0(p0>0,可由用戶根據具體情況給定)逐步遞增到最大值0.997。對于每個置信水平，其相應的最小平均總代價和最優屬性子集由算法1調用算法2得到，再將該平均總代價與現有的全局最小平均總代價進行比較，從而得到全局最優的屬性子集和誤差置信水平。特別地，當總測試代價不受限時，可設算法1中的輸入量w=+∞,所以測試代價不受限可看成有受限的特殊情形。

算法2是一個回溯算法，它使用了三個剪枝技術以提高效率。

首先，如第1行所示，回溯算法的搜索路徑中屬性指標的起始值l不是都從1開始，而是隨著算法的進行在遞增的，這樣減少了搜索工作量；其次，如第2行～第4行所示，當單個屬性的測試代價過高時，則進行剪枝；最后，如第7行～第9行所示，當屬性子集的總測試代價過高時，也進行剪枝。后面兩個剪枝主要是基于平均誤分類代價不小于0的特點而提出的。這三個剪枝技術能較大程度地提高算法的效率。

4 實驗與分析

為了驗證所提出的屬性和粒度選擇算法的性能，本文使用了7個常用的UCI數據集進行實驗。如表1所示，這些數據集分別涉及到醫療、金融、物理和圖形學等領域，因此具有較強的代表性和現實意義。在實驗中，令誤差置信水平的最小值p0和遞增步長r都為0.1，式(2)中正態分布的標準差的調節系數λ=0.05;令每個屬性的測試代價為其值介于10和100之間的分段常值函數，它們隨著誤差置信水平的增高而遞減；令每個誤分類別對的代價為其值介于500和10 000之間的分段常值函數，它們隨著總測試代價的增大而遞增。

Table 1 Dataset information

通過實驗發現，運用算法可以得到不同大小的總測試代價上限下最優的屬性子集和數據粒度；算法的運行時間較短，并且總測試代價的上限越低，算法的運行時間越短，這是因為剪枝技術在起作用。此外，不同數據集在屬性和粒度的選擇結果隨總測試代價上限的大小變化方面服從類似的規律。表2～表4和圖1給出了每個數據集的一組代表性實驗結果，其中的最大總測試代價指的是測試代價不受限情況下最優的屬性和粒度選擇結果相應的總測試代價值。具體地，表2～表4分別列出了Diab、Liver和Wpbc三個數據集的最優置信水平和最優屬性子集以及相應的三種代價值；而為了直觀起見，對于其他四個數據集，則畫出了平均測試代價和平均總代價的變化趨勢圖，如圖1所示，顯然每個子圖中同一橫坐標對應的平均總代價和平均測試代價的差值就是平均誤分類代價(事實上，如2.4節所述，數據集中對象的平均測試代價等于單個對象的總測試代價)。

Table 2 Representative experimental results of Diab dataset,where the maximum total test cost is 128.746

Table 3 Representative experimental results of Liver dataset,where the maximum total test cost is 154.034 4

Table 4 Representative experimental results of Wpbc dataset,where the maximum total test cost is 77.518 1

Figure 1 Cost comparison under different sizes of constraint圖1 不同大小的約束下的代價對比圖

從這些圖表中可以發現，隨著測試代價受限程度的增強，即隨著總測試代價的上限占最大總測試代價比例的減少，所得最優誤差置信水平可能不變也可能改變，但當所得最優屬性子集不變時，最優置信水平一般會增加(如表3中第4～6行)，表示放寬對相同屬性的數據精度要求；最優屬性子集的維度呈現減少的趨勢，具體地，維度可能逐漸減少(如表3和表4所示)，也可能先增加后減少(如表2所示)；平均測試代價遞減，平均誤分類代價遞增，平均總代價除極個別外也遞增。而當總測試代價的上限相當低時，所得屬性子集為空集，如表2～表4的最后一行所示，以及圖1中四個子圖的橫坐標有的只到20%，有的只到30%，即當上限值占最大總測試代價的比例為10% 或20% 時，沒辦法得到非空的屬性子集。

從以上實驗結果發現的規律和現實情況是吻合的。以醫療為例，當看病的人能承擔的費用越有限時，他/她不得不更多地減少必須檢查的項目，或降低對這些項目的精度要求，或替換成測試代價較低但分類能力較差的項目(如表2中第4～6行所示)，從而導致誤分類(誤診)可能性較大程度地增大，所以平均誤分類代價增高，平均總代價一般也增高。而當病人能承擔的費用實在低時，即使他/她再降低對檢查結果精度的要求，即誤差置信水平再高，也沒有合適的檢查項目滿足要求。

5 結束語

考慮到數據值獲取過程中經常存在誤差，并且屬性的測試代價和樣本的誤分類代價經常隨著誤差范圍的大小而變化，還有樣本的總測試代價大小有可能受到約束等因素，本文提出了測試代價受限情況下的一種屬性和粒度同步選擇的方法，充分討論了相關的理論知識，并設計了一個較為高效的算法。實驗結果驗證了所設計算法的有效性，并分析了屬性和粒度選擇結果隨總測試代價上限的大小變化的規律。本文為代價敏感學習的實際應用提供了理論和技術支持。接下來擬進一步改進算法以高效求解大型數據集的相關問題。