基于代價敏感的序貫三支決策最優粒度選擇方法

張清華 龐國弘 李新太 張雪秋

(重慶郵電大學計算智能重慶市重點實驗室 重慶 400065)

1 引言

在實際決策中，如何處理代價敏感問題一直是研究的熱點之一。代價通常分為決策代價(誤分類代價和延遲代價)和測試代價(測試成本)。一般地，決策代價隨著信息逐步增加而降低，而測試代價隨著信息增加而增加，兩者呈負相關關系且量綱不同。例如，在醫療診斷中，若患者偏好高精度的診斷，會選擇成本較高的檢查項目；相反，若患者偏好普通的診斷，往往會選擇成本低的檢查項目。這兩種情況都廣泛發生在實際應用中，因此如何實現代價最小的決策是值得研究的。

現階段許多專家學者將代價敏感研究運用于機器學習理論中，并取得了重要的研究成果[1,2]。目前，代價敏感方面的研究方法主要分為以下3個方面：從決策代價敏感的角度來看，Li等人[3]結合序貫三支決策提出了一種最小化代價的決策模型；Zhang等人[4]基于鄰域覆蓋方法，根據損失函數改變覆蓋半徑，來減小分類損失；Jia等人[5]通過定義一種新的屬性約簡方法使模型的決策代價最小。同時，在降低測試代價方面，Yang等人[6]提出了一種測試代價最優的粒度結構選擇回溯算法。Min等人[7]在測試代價中引入代價敏感決策系統的層次結構。另外，在同時考慮決策代價和測試代價的研究中，廣大學者也進行了相應的工作[8,9]。

序貫三支決策[10]是近年發展起來的一種處理不確定性決策的方法。作為粒計算[11–13]概念下的具體模型，其目標是提供一種靈活的機制和方法，幫助用戶在信息粒化過程中做出合適的決策。目前在圖像分析、屬性約簡、語音識別等方面均已取得了較大的成果[14–17]。代價敏感的序貫三支決策從粒計算的角度提高了三支決策的有效性，實現了粗粒度到細粒度漸進式的決策過程。但在最優粒度選擇方面，仍存在一些問題需要改進。首先，在構建多粒度空間過程中，從屬性重要度選擇方法上來看，存在沒有充分考慮數據中有冗余屬性或不相關屬性的問題，這樣可能會增加額外的測試代價或有損模型的性能。其次，隨著獲取信息的增多，針對兩類錯誤分類和兩類不確定性分類[18]的代價參數是保持不變的，使得代價參數在序貫三支決策漸進計算過程中缺乏一定的自適應性，導致在粗粒層產生較低的分類精度，從而影響模型的最優粒度選擇。此外，在現有計算總代價的方法中，未能考慮測試代價與決策代價測量尺度或量綱不統一所帶來的影響，從而丟失部分關鍵因素，導致直接進行計算得到的結果不準確。針對這些問題，本文首先利用卡方檢驗剔除高相關性的條件屬性，再借助信息增益計算屬性重要度并根據得到的屬性重要度序列進行多粒度空間的構建。其次，針對兩類錯誤分類和兩類不確定性分類[18]的代價參數缺乏自適應性，結合漸進計算的思想，借助懲罰函數來對代價參數設置相應的懲罰規則，有效提升了模型的分類精度。最后，利用變異系數構建了一種合理的代價結構，實現了同量綱下的代價計算，從而可以有效利用測試代價和決策代價的信息。實驗表明所提出的模型在不同的代價場景下能夠產生合理的多粒度空間結構，同時所得到的代價最小的粒度空間也更符合實際應用場景代價最小的需求。

2 基礎知識

定義1[19,20]給定決策信息系統S=(U,C ∪D,V,f)，其中U表示非空有限論域；C和D分別表示條件屬性集和決策屬性集，且C ∩D=? ；V表示屬性值的集合；f:U×C →V表示一個信息函數，用于指定U中每一個對象x的屬性值。

定義2[19,20]給定決策信息系統S=(U,C ∪D,V,f)，對于任意屬性子集A ?C，等價關系EA定義為

等價關系可形成論域U上的一個劃分，記為U/EA，簡記為U/A。給定對象x∈U，表示在屬性子集A所形成的等價關系下的等價類，簡記為[x]A或 [x]。

相比于二支決策，三支決策理論的關鍵在于引入了延遲決策，即當決策對象的信息不足時采用延遲決策，等待收集更多有用信息后再重新進行決策。這種對決策對象的認識從粗粒度向細粒度轉化，使邊界域中的對象逐漸被正確決策，進而形成一種序貫決策方法。下面介紹序貫三支決策的一些基本概念。

定義3[10]給定決策信息系統S=(U,C ∪D,V,f)，假定A1,A2,...,An表示一組條件屬性集，且滿足A1?A2?...?An ?C。對于?x∈U，有

定義4[10]給定決策信息系統S=(U,C ∪D,V,f)，設A1,A2,...,An表示一組條件屬性集，且滿足A1?A2?...?An ?C。在這種條件屬性集的序貫情形下多粒度空間記為GS，在第i(i=1,2,...,n)層，GS的粒度結構記為GLi,，GLi和GS定義為

在多粒度空間中，給定第i層的閾值(αi,βi)，則第i層的接受域、延遲域和拒絕域可以表示為

粗糙集理論為序貫三支決策奠定了理論基礎，從多粒度的角度來看，隨著屬性的增加，等價類會被進一步的細分。依據條件屬性集構建的多粒度空間可以用樹形結構來表示，最頂層表示論域的信息，即最粗粒層，隨著屬性的逐步加入，信息粒度逐步變細。因此，序貫三支決策的決策過程能夠構成一個多粒度空間。圖1簡要介紹了多粒度的構造過程示意圖。

圖1 多粒度空間的構造過程

3 代價敏感的序貫三支決策最優粒度選擇模型

3.1 基于信息增益和卡方檢驗的屬性重要度選擇方法

多粒度空間的構建與屬性重要度的選擇是緊密相連的，如果充分考慮條件屬性內在的關系和條件屬性與決策屬性之間的關系來進行屬性重要度選擇，所得到的多粒度空間往往會更優。因為數據集中有些條件屬性是冗余甚至是不相關的。冗余屬性的存在會增加額外的測試代價，而不相關的屬性會有損模型的性能。因此，對條件屬性進行相關性分析是有必要的，從而使模型泛化能力更強。

卡方檢驗是一種用途很廣的計數資料的假設檢驗方法，屬于非參數檢驗，主要是比較兩個及兩個以上樣本率(構成比)以及兩個分類變量的關聯程度。其主要思想在于比較理論頻數和實際頻數的吻合程度或者擬合優度，用來描述兩個事件的獨立性。卡方值χ2越大，說明兩個事件的相互獨立性越弱。

定義5(卡方分布[21])設s個相互獨立的隨機變量Y1,Y2,...,Ys，且符合標準正態分布N(0,1)，則這s個隨機變量的平方和為服從自由度為s的卡方分布，記為Q～χ2(s)。

定義6(卡方檢驗[21])給定數據的實際值A和理論值T，則卡方檢驗的公式為

理論上，如果卡方值越大，二者偏差程度越大；反之，二者偏差越小；若兩個值完全相等時，卡方值為0，表明理論值與數據的實際值完全符合。因此，通過卡方檢驗可以更好地剔除條件屬性集中的冗余屬性，減小測試代價。

同時，多粒度空間的構建與條件屬性的劃分能力是緊密相連的，如果充分考慮條件屬性的劃分能力來進行論域的劃分，所得到的多粒度空間往往會更優。目前，屬性重要度選擇的方法大多基于熵。熵是用來描述論域中不確定性的一種度量方法。熵越大，論域的不確定性就越大。因此可以使用信息增益(論域集合劃分前后熵的差值)來衡量使用當前屬性對于論域劃分效果的好壞。

定義7(信息增益[22,23])給定決策信息系統S=(U,C ∪D,V,f),B ?C。假設論域U在等價關系EB和ED下的劃分分別為U/B={B1,B2,...,Bm}和U/D={D1,D2,...,Dp}，信息增益Gain(D,B)可定義為

基于信息增益的屬性重要度做出選擇的規則是：對于待劃分的論域，在劃分前的熵是一定的，而劃分后的熵是不定的，且劃分后的熵越小說明使用此屬性劃分所得到的子集的不確定性越小，即純度越高，因此劃分前后熵值差異越大，說明使用當前屬性劃分論域，其不確定性越小。以信息增益作為劃分論域的屬性選擇的標準，在屬性選擇上更傾向于選擇取值較多的屬性，這樣在多粒度空間構建的過程中粒度空間往往能夠朝著最快到達最細粒度空間的方向發展，因此可以選擇使得信息增益最大的屬性來劃分當前論域。

3.2 懲罰規則下代價參數和閾值的變化規律

因為基于決策粗糙集的三支決策存在一定的容錯能力，所以3個域中都可能存在不確定性進而產生相應的代價。在序貫三支決策中，隨著屬性的增加，等價類被進一步細分，信息粒度逐步變細，對象之間的區分也越明顯，邊界域中的對象可能會被重新分類，分類精度會進一步的提升，所以針對錯誤分類和不確定性分類應該給予更高的代價懲罰。本文借助文獻[24]中的思想，考慮損失函數在隨著粒度變化的情況下，利用懲罰函數對其進行相應的修改。因為在實際應用中，通常可以通過加大懲罰力度的方式來獲取“優秀”的目標對象。同時，懲罰力度會隨著懲罰次數的增加而增加，因此，懲罰函數必定是一個單調遞增函數。進一步地，在序貫三支決策中，通過懲罰規則對代價參數進行修改，進而調整決策閾值(即α值的增大或β值的減小)，這樣可以使等價類得到更準確的分類。同時，代價參數的值增大，即錯分代價和延遲代價也會增高。所以，通過引入懲罰規則，利用代價參數值的增大進而提高決策精度。

考慮到采取不同行動會產生不同的損失，記和表示在第k層，x屬于X時采取行動aB和aN下的損失；相似地，記和表示在第k層，x不屬于X時采取行動aP和aB下的損失；另外，代價參數λPP和λNN表示正確劃分下的代價，不產生代價損失。代價參數矩陣可以描述為表1。

表1 代價參數矩陣

根據貝葉斯決策理論，將屬于目標集合的對象分類到接受域的代價要小于等于將其分類到延遲域和拒絕域中的代價。相似地，將不屬于目標集合的對象分類到拒絕域的代價要小于等于將其分類到延遲域和接受域中的代價。基于這兩種規則，可以得到代價參數之間存在以下規律，。因此決策閾值可以表示為

一般地，隨著屬性的增加，粒度變細，形成的等價類將發生變化，代價參數值增大，閾值也會相應地發生改變。

定理1與定理2同理可證。

因此，通過引入懲罰函數來處理實際決策過程中的代價參數變化，使得多粒度空間具有更好的適應性，能夠動態地進行決策。

3.3 序貫三支決策模型的代價結構設計

在序貫三支決策中主要存在兩種代價，第1種是因對象誤分類或者需要延遲決策而產生的決策代價，第2種是因獲得新的屬性而產生的測試代價，即獲取某些屬性值的成本。在實際應用場景中，這兩種代價都應該被考慮。因此，如何合理地結合決策代價和測試代價來解決問題具有重要意義。為了尋求決策代價和測試代價的最優平衡點，本文設計了一個啟發式函數用來綜合決策代價和測試代價。

因為產生測試代價的因素(時間、金錢、復雜度等)的維度不同，很難將各因素綜合起來考慮。一般地，屬性重要度越高的屬性，它所擁有的分類能力越強，測試成本越高。

定義8給定決策信息系統S=(U,C∪D,V,f)，條件屬性c(c∈C)對決策結果的影響度可以定義為

其中，I(c)的 值越大，該決策屬性對屬性c的依賴程度越高，說明屬性c的影響度越大。屬性影響度作為啟發式信息來度量某一屬性的分類能力，區分能力越大，帶來的測試代價越高。因此，測試代價與屬性重要度呈現正相關關系，所以條件屬性c的測試代價可以定義為

其中，η是一個常數。

一般地，若兩個條件屬性對決策屬性的影響度一致(即劃分能力一致)，那么這兩個條件屬性具有一樣的測試代價。

定義9在多粒度空間GS=(GL1,GL2,...,GLn)中，第i層的決策代價可以定義為

其中，GLi表示GS的 第i粒層，COST(POS(αi,βi)(Xi))表示產生第1 類分類錯誤帶來的代價，COST(NEG(αi,βi)(Xi))表示產生第2類分類錯誤帶來的代價，C OST(BND(αi,βi)(Xi))表示產生不確定性分類帶來的代價。

因為測試代價和決策代價呈現負相關關系且量綱不相同，所以不能將其直接進行計算。為了更好地計算總代價，本文引入變異系數的概念，并基于變異系數定義一種綜合客觀的評價函數進行總代價計算的方式

C.V表示變異系數。

變異系數是衡量各組數據變異程度的一種統計量。在統計學中，如果兩組數據的測量尺度相差太大，或者數據量綱不同，直接使用標準差來進行綜合計算不合適，此時就應當消除測量尺度和量綱的影響，而變異系數可以做到這一點，它是原始數據標準差與原始數據平均數的比。因為變異系數沒有量綱，因此得到結果是一個標量，可以客觀地將決策代價與測試代價相結合。

4 實驗對比及分析

4.1 實驗設計

為了更好地說明所提模型的有效性和實用性，本文選取美國加州大學歐文分校(University of California Irvine,UCI)數據庫的6個標準數據集進行了對比實驗，并且每個數據集在兩種不同的代價環境下進行實驗。數據集的詳細信息如表2所示。實驗環境為8GB RAM,3.2 GHz CPU,Windows 10 system，編程語言是Python。

表2 數據集的描述

本文算法的框架如圖2所示，可以分為3個過程：屬性重要度選擇、多粒度空間構建和最優粒度選擇。其中屬性重要度選擇部分由信息增益和卡方檢驗構成；在多粒度空間構建時，為代價參數設置了懲罰規則；最后利用變異系數消除測試代價與決策代價量綱的差異。

圖2 算法框架

在計算算法的時間復雜度時，往往以最壞情況計算。根據上述實驗步驟，算法的時間復雜度主要取決于多粒度空間構建，從圖1中可知，多粒度空間是一個自頂向下且具有偏序關系的層級結構，層數是由條件屬性集的基數(屬性個數)所決定的。因屬性重要度的選擇方法是由卡方檢驗和信息增益所構成，因此需要對所有的屬性進行計算：第1步屬性重要度選擇過程的時間復雜度為O(n)；多粒度空間的構建是基于經過屬性重要度方法計算后條件屬性集的屬性個數的，所以構建多粒度空間的時間復雜度為O(n)，同時在每一粒層上借助懲罰規則對代價參數進行修改的時間復雜度為O(1)，因此第2步構建多粒度空間的時間復雜度為O(n)；第3步在最優粒度選擇過程中，需要對全部粒層進行遍歷計算，同樣時間復雜度為O(n)。因為算法中3個步驟是遞進關系，所以該算法整體的時間復雜度為O(n)，其中n表示序貫三支決策的條件屬性集中屬性的個數。

4.2 實驗結果分析

本節對4.1節所選的UCI數據集進行了實驗，為了方便研究，首先將數據集中的字符型數據轉化為整數型數據；其次給出2組代價參數，其數值均滿足第4節中定義并通過代價參數計算決策閾值對(α,β)，如表3所示；此外，為了體現最優化的思想，設計懲罰函數對代價參數進行懲罰。本文所選的懲罰函數是φ(x)=log2(1+0.1×k)×λσ，其中σ={NP,BP,PN,BN}。

表3 代價參數

通過實驗發現，運用上述的算法均可以得到不同數據集的代價最小的最優粒層，驗證了算法的實用性。圖3和圖4給出了不同代價參數下的各數據集的代價變化以及最優粒層。另外，表4和表5分別列出了各數據集最優粒層的詳細數據。從圖3、圖4和表4、表5中清楚地看出，所選的最優粒度較符合人類的認知。同時，所提出的代價結構利用標準化和變異系數進行處理能夠消除因測試代價和決策代價尺度和量綱不同所帶來的影響。

表4 第1組代價參數下各個數據集最優粒層信息

表5 第2組代價參數下每個數據集最優粒層信息

圖3 第1組代價參數下各數據集最優粒層的代價變化

圖4 第2組代價參數下各數據集最優粒層的代價變化

具體地，針對Breast Cancer Wisconsin數據集，通過使用最優粒度選擇算法，將在不同代價參數環境下尋找一個總代價最小的粒度空間。從實驗結果可以看出，在第1組代價參數下，代價最小的最優粒度空間由{c2,c3,c6,c7,c5,c8,c4,c9}誘導而得到并且構造多粒度空間的順序是c2→c3→c6→c7→c5→c8→c4→c9。此時構建的粒度空間總代價最小，為0.3684(標準化后)；在第2組代價參數下，代價最小的最優粒度空間{c2,c3,c6,c7,c5}由誘導而得到，并且構造多粒度空間的順序是c2→c3→c6→c7→c5。此時構建的粒度空間總代價最小，為0.4459(標準化后)。

從以上6個數據集的實驗結果可以看出，選取不同的代價參數時，所得到的最優粒層不一定是相同的，即便是改變一個代價參數也可能引起整個序貫三支決策粒層結構的改變，進而得到代價最小的最優粒層可能也是不一樣的。相比于第1組代價參數，第2組代價參數值更大，所得到的最優屬性子集中屬性個數更少，這種所得到的代價最小的最優粒層是較為符合人類認知的。同時，兩組代價參數通過定理1可以得到αk+1＞αk,βk+1＜βk，隨著粒度空間的細化，每一粒層上的決策標準更為嚴格，分類到接受域(或延遲域)中對象的準確率更高，這與現實生產中的實際情況也是相吻合的。

此外，為了說明懲罰規則的有效性，將所提模型(模型1)與不加懲罰規則的最優粒層選擇模型(模型2)在第1組代價參數下進行對比，實驗結果如表6所示。從表中可以發現，模型1和模型2均可以得到代價最小的粒層。相比于模型2，模型1所得到的粒層比模型2所得到的最優屬性子集中屬性個數更多，即當前模型1所得的粒層能夠獲取的信息更多。通過實驗說明，利用懲罰函數對代價參數進行合理的修改，在選取最優粒層的時候逐步提高了閾值要求，能夠有效地防止選擇測試代價較小同時精度較差的粒層。因此，所提出的模型具有更好的實用性。

表6 最優粒層比較

在一定程度上，本文所提模型在實驗過程中給定的代價參數需要在滿足一定約束條件下進行隨機選擇，不同的代價參數組合得到的結果可能不一致。一般地，所給出的代價參數滿足λPN-λBN＞λBP和λBN＜λNP-λBP等條件較為合理，在懲罰規則下，閾值α會逐漸增大，閾值β會逐漸減小，每一粒層上分類時的標準更為嚴格，接受域或拒絕域中的對象精度越大。

5 結論

序貫三支決策作為粒計算概念下的產物，其目標是提供一個靈活的機制和方法，使得用戶在信息粒化過程中做出合適的決策，因此如何通過合理的粒度選擇，來對復雜問題進行求解是值得研究的。本文介紹了一種新的序貫三支決策中最優粒度選擇的方法，其思想是首先通過信息增益對屬性的分類能力進行排序，再利用卡方檢驗進行屬性之間的相似度檢驗，去除冗余屬性。其次，設計懲罰函數對代價參數進行處理，使其能夠隨著粒度自適應變化。進一步地，通過測試代價和決策代價的變異系數建立了一種客觀的綜合度量代價的方法，消除兩種代價量綱不一致帶來的影響，實現同量綱下的評價。最后，通過UCI上的標準數據集對本文所提方法進行了驗證，實驗結果表明了所提方法選取的最優粒度空間具有一定的實用性。