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

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

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

1 引言

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

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

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

2 基礎(chǔ)知識

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

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

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

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

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

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

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

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

圖1 多粒度空間的構(gòu)造過程

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

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

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

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

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

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

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

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

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

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

3.2 懲罰規(guī)則下代價參數(shù)和閾值的變化規(guī)律

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

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

表1 代價參數(shù)矩陣

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

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

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

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

3.3 序貫三支決策模型的代價結(jié)構(gòu)設(shè)計

在序貫三支決策中主要存在兩種代價，第1種是因?qū)ο笳`分類或者需要延遲決策而產(chǎn)生的決策代價，第2種是因獲得新的屬性而產(chǎn)生的測試代價，即獲取某些屬性值的成本。在實際應(yīng)用場景中，這兩種代價都應(yīng)該被考慮。因此，如何合理地結(jié)合決策代價和測試代價來解決問題具有重要意義。為了尋求決策代價和測試代價的最優(yōu)平衡點，本文設(shè)計了一個啟發(fā)式函數(shù)用來綜合決策代價和測試代價。

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

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

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

其中，η是一個常數(shù)。

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

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

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

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

C.V表示變異系數(shù)。

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

4 實驗對比及分析

4.1 實驗設(shè)計

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

表2 數(shù)據(jù)集的描述

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

圖2 算法框架

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

4.2 實驗結(jié)果分析

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

表3 代價參數(shù)

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

表4 第1組代價參數(shù)下各個數(shù)據(jù)集最優(yōu)粒層信息

表5 第2組代價參數(shù)下每個數(shù)據(jù)集最優(yōu)粒層信息

圖3 第1組代價參數(shù)下各數(shù)據(jù)集最優(yōu)粒層的代價變化

圖4 第2組代價參數(shù)下各數(shù)據(jù)集最優(yōu)粒層的代價變化

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

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

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

表6 最優(yōu)粒層比較

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

5 結(jié)論

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