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

(重慶郵電大學(xué)計(jì)算智能重慶市重點(diǎn)實(shí)驗(yàn)室 重慶 400065)

1 引言

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

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

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

2 基礎(chǔ)知識(shí)

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

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

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

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

定義3[10]給定決策信息系統(tǒng)S=(U,C ∪D,V,f)，假定A1,A2,...,An表示一組條件屬性集，且滿足A1?A2?...?An ?C。對(duì)于?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ǔ)，從多粒度的角度來看，隨著屬性的增加，等價(jià)類會(huì)被進(jìn)一步的細(xì)分。依據(jù)條件屬性集構(gòu)建的多粒度空間可以用樹形結(jié)構(gòu)來表示，最頂層表示論域的信息，即最粗粒層，隨著屬性的逐步加入，信息粒度逐步變細(xì)。因此，序貫三支決策的決策過程能夠構(gòu)成一個(gè)多粒度空間。圖1簡要介紹了多粒度的構(gòu)造過程示意圖。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)對(duì)比及分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

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

圖2 算法框架

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

4.2 實(shí)驗(yàn)結(jié)果分析

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

表3 代價(jià)參數(shù)

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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