區(qū)間值數(shù)據(jù)的代價敏感特征選擇

劉 瓊 ,代建華* ,陳姣龍

（1.智能計算與語言信息處理湖南省重點實驗室，湖南師范大學(xué)，長沙，410081；2.湖南師范大學(xué)信息科學(xué)與工程學(xué)院，長沙，410081）

隨著社會的快速發(fā)展，存在的數(shù)據(jù)也越來越多，數(shù)據(jù)中往往包含有不確定性，而區(qū)間數(shù)據(jù)是一個重要的類型.一方面，客觀上由于測量、計算所帶來的數(shù)據(jù)誤差往往不是一個確定的數(shù)，而是一個區(qū)間范圍；另一方面，主觀上人們在描述和理解某些數(shù)據(jù)時，也更傾向一個區(qū)間范圍，而不是一個確定的值，比如身高、體重、收入等.高維的區(qū)間值數(shù)據(jù)在現(xiàn)實生活中廣泛存在，因此研究區(qū)間值數(shù)據(jù)的特征選擇具有重要的意義.針對區(qū)間值數(shù)據(jù)的特征選擇問題，學(xué)者已進行了相關(guān)研究.例如，Du and Hu［1］提出區(qū)間值有序決策表的近似分布約簡.Yang et al［2］提出基于α 序關(guān)系區(qū)間值信息系統(tǒng)屬性約簡.Dai et al［3］在區(qū)間值決策系統(tǒng)中利用概率方法建立優(yōu)勢度的模糊粗糙集模型，并利用該模型進行近似分布約簡.Li［4］提出基于區(qū)間值信息系統(tǒng)的模糊概念格的特征選擇方法.Dai et al［5］提出基于不完備區(qū)間值決策系統(tǒng)的特征選擇.尹繼亮等［6］提出區(qū)間值決策系統(tǒng)的局部屬性約簡.Shu et al［7］提出基于不確定度量的區(qū)間值缺失屬性約簡.閆岳君和代建華［8］提出區(qū)間序信息系統(tǒng)的無監(jiān)督特征選擇.

值得注意的是，上述針對區(qū)間數(shù)據(jù)的特征選擇方法沒有考慮數(shù)據(jù)自身的測試代價和誤分類代價.代價敏感在數(shù)據(jù)挖掘和機器學(xué)習(xí)中得到了廣泛的關(guān)注［9-14］.在代價敏感的應(yīng)用中，代價可以用許多不同的單位來度量，例如在醫(yī)學(xué)領(lǐng)域里，代價可以是非癌癥患者被誤判為癌癥患者的可能.在圖像識別中，代價可以是被錯誤分類的損失.本文考慮到測試代價和誤分類代價，研究代價敏感區(qū)間數(shù)據(jù)特征選擇.首先，利用鄰域粗糙集給出區(qū)間值鄰域的概念，并通過區(qū)間值鄰域進行分類，進而重定義基于區(qū)間值鄰域的熵結(jié)構(gòu)；其次，構(gòu)造了區(qū)間值系統(tǒng)下的代價敏感函數(shù)，引入測試代價和誤分類代價，并提出基于代價敏感的區(qū)間值特征選擇方法；最后，通過實驗驗證了本文方法的有效性.本文的主要貢獻有：

（1）利用KL 散度度量兩個區(qū)間值之間的關(guān)聯(lián)，并構(gòu)造了區(qū)間值鄰域，進而重新定義了區(qū)間值鄰域的熵結(jié)構(gòu)；

（2）構(gòu)造區(qū)間值系統(tǒng)下的代價敏感函數(shù)，代價敏感函數(shù)有效地考慮了區(qū)間值數(shù)據(jù)自身的測試代價和誤分類代價；

（3）提出基于代價敏感的區(qū)間值特征選擇方法，該方法可以選擇代價較小但擁有較多有效信息量的特征.

1 預(yù)備知識

本節(jié)重點回顧一些相關(guān)概念.

顯然，IND(C)具有自反性、對稱性和傳遞性.U/IND(C)表示所有等價類IND(C)的族，可以簡寫為U/C.

定義1是一個決策信息系統(tǒng)，其中U是非空有限對象集合，稱為論域；C為條件特征集合，D為決策特征集合；V是所有特征域的并集，B?C，關(guān)于特征集B的信息熵定義如下：

定義2是一個決策信息系統(tǒng)，其中U是非空有限對象集合，C為條件特征集合，D為決策特征集合；V是所有特征域的并集，B，Y2，…，Ym} .特征集B和K的聯(lián)合熵定義為：

定義3是一個決策信息系統(tǒng)，其中U是非空有限對象集合，C為條件特征集合，D表示決策特征，V是所有特征域的并集，…，Ym} .條件特征集P關(guān)于決策特征D的條件熵定義為：

定義4是一個決策信息系統(tǒng)，其中U是非空有限對象集合，C為條件特征集合，D表示決策特征，V是所有特征域的并集，…，Ym} .特征集合P和決策特征D的互信息定義為：

對于一個正態(tài)分布，μ是數(shù)學(xué)期望，σ是標準差，x位于區(qū)間(μ-3σ，μ+3σ)外的概率小于0.3%.在實際問題中，往往認為當(dāng)置信水平達到95%時，已具備統(tǒng)計學(xué)意義.考慮到區(qū)間值數(shù)據(jù)為一段有限區(qū)間，而分布是無限的，因此本文通過使用合適的參數(shù)，使得區(qū)間盡可能落在95%的置信區(qū)間內(nèi).任意給定一個區(qū)間[a，b]，本文取區(qū)間中值作為期望值作為標準差，這樣就構(gòu)成一個正態(tài)分布S～N(μ，σ2)，以滿足該區(qū)間[a，b]具備統(tǒng)計學(xué)意義［15］.

定義5設(shè)P～N是兩個正態(tài)分布，則關(guān)于P，Q兩個分布之間的距離可利用KL 散度定義：

考慮到KL 散度不滿足對稱性，因此對于兩個分布之間的距離度量可重定義為如下形式：

2 基于區(qū)間分類誤差的鄰域粗糙集

本節(jié)提出基于區(qū)間分類誤差的鄰域粗糙集模型（Interval-Classification-Error-Based Neighborhood Rough Set Model）并證明一些相關(guān)性質(zhì).是一個鄰域決策信息系統(tǒng)，其中U={x1，x2，…，xn}是n維對象集合，稱為論域；C為所有條件特征集合；D表示決策特征，N為樣本關(guān)于特征的鄰域映射函數(shù)，其中?x∈U，a∈C，Na(x)={y∈U|da(x，y)≤δ} .

定義6是一個鄰域決策信息系統(tǒng)，其中U={x1，x2，…，xn}為n維對象集合，C為所有條件特征集合；D表示決策特征，N為樣本關(guān)于特征的鄰域映射函數(shù).設(shè)a∈C，x∈U.對于任意對象區(qū)間值[n，m]，首先取區(qū)間中值作為期望值作為標準差，這樣就構(gòu)成一個滿足統(tǒng)計學(xué)意義的正態(tài)分布，然后基于式（6）和式（7）定義對象x在特征a下的鄰域：

da(x'，x)表示對象x'和x在特征a下的兩個分布之間的距離，max(σa)表示特征a下所有對象的最大標準差，也稱為上邊界域.

設(shè)特征a的測量誤差值都在區(qū)間[-b，b]之間，對特征a來說，對象x的真實值是a'(x).但是由于測量誤差的原因，其測量值a(x)會在一個區(qū)間范圍內(nèi)，即a'(x)-b≤a(x) ≤a'(x)+b.特別地，在極端情況下，同一對象的觀測值可能是從端點取得的，即a-b或a+b.則有(a'(x)+b)-(a'(x)-b)=2b，所以觀測值不應(yīng)超過2b，故本文的鄰域差設(shè)計為2max(σa).

定義7是一個鄰域決策信息系統(tǒng)，其中U={x1，x2，…，xn}為n維對象集合，C為所有條件特征集合，D表示決策特征，N為樣本關(guān)于特征的鄰域映射函數(shù).設(shè)B?C，?x∈U，對象x關(guān)于特征集合B的鄰域定義為：

根據(jù)定義7 得出以下性質(zhì)：

性質(zhì)1是一個鄰域決策信息系統(tǒng)，P?C，?x∈U，EP(x) 滿足以下性質(zhì)：

（1）自反性：?x∈U,x∈EP(x)；

（2）對稱性：?xi，xj∈U，如果xj∈EP(xi)則xi∈EP(xj).

證 明

（1）根據(jù)式（8）和式（9），?a∈P，x∈U，有da(x'，x) ≤2 max (σa)，而da(x，x)=0 且max (σa)≥0，則?x∈U,x∈Ea(x)，然后根據(jù)式（9）可得?x∈U,x∈EP(x).

（2）因為?xi，xj∈U，xj∈EP(xi)，根據(jù)式（9）可知，?a∈P，xi，xj∈U有xj∈Ea(xi)，從式（8）可以明顯看出Ea(x)具有對稱性，故?a∈P，xi，xj∈U有xi∈Ea(xj)，從而有xi∈EP(xj).

給定一個非空特征集合P，RP是定義在特征P上的鄰域等價關(guān)系，用關(guān)系矩陣?M(RP)表示：

其中，rij是xi和xj的關(guān)系值，也可以寫作RP(xi，xj)，n=|U|，?xi，xj∈U，若xj∈EP(xi)或xi∈EP(xj)則rij=1，否則rij=0.

根據(jù)性質(zhì)1 可以得到RP滿足自反性rii=1 和對稱性rij=rji.

任意給定一個非空特征集合P1，P2，RP1，RP2是分別定義在特征集合P1，P2上的鄰域等價關(guān)系.?x，y∈U，幾種關(guān)系矩陣的運算方式定義如下：

定義8[xi]R基數(shù)定義如下：

定義9給定一個鄰域決策信息系統(tǒng)NS=，其中U={x1，x2，…，xn}為n維對象集合，C為所有條件特征集合，D表示決策特征，N為樣本關(guān)于特征的鄰域映射函數(shù).設(shè)A?C，R為特征集A上的鄰域等價關(guān)系.關(guān)于特征集A的信息熵可以定義為如下形式：

定義10給定一個鄰域決策信息系統(tǒng)NS=其中U={x1，x2，…，xn}為n維對象集合，C為所有條件屬性集合；D表示決策屬性，N為樣本關(guān)于屬性的鄰域映射函數(shù).設(shè)B，K?C，[xi]B和[xi]K分別是屬性集B，K上的等價類.關(guān)于屬性集B和K的聯(lián)合熵的定義如下所示：

RB，RK分別表示定義在屬性集B，K上的鄰域等價關(guān)系.

定義11給定一個鄰域信息系統(tǒng)NS=，其中U={x1，x2，…，xn}為n維對象集合，C為所有條件屬性集合；D表示決策屬性，N為樣本關(guān)于屬性的鄰域映射函數(shù).設(shè)P?C，[xi]P和[xi]D分別是屬性集P，D上的等價類.條件屬性集P關(guān)于決策屬性D的條件熵定義如下：

為了便于理解式（8）的鄰域Ea(x)和最大標準差max (σa)，下面用例子來說明.

例1一個區(qū)間決策信息系統(tǒng)由表1 構(gòu)成.U={x1，x2，…，x6}，C={a1，a2，a3} 且決策屬性d在論域U上的劃分為U/d={{x1，x2，x3}，{x4，x5，x6} }.設(shè)X1={x1，x2，x3}，X2={x4，x5，x6} .首先基于表1 給出屬性下的最大標準差max(σa1)=9.375，ma x(σa2)=3.675，max(σa3)=0.0575.根據(jù)式（8）可以計算出所有屬性的鄰域，結(jié)果如表2所示.設(shè)B1={a1，a2}，B2={a1，a3}，B3={a2，a3} .根據(jù)表2 和式（9）可以計算出B1，B2，B3鄰域EB1(x)，EB2(x)，EB3(x)分別為：

表1 區(qū)間決策系統(tǒng)一個實例Table 1 An example of interval decision system

表2 鄰 域Table 2 The neighborhoods

3 基于代價敏感的特征選擇問題

通常數(shù)據(jù)本身有測試代價，即獲得數(shù)據(jù)精度所付出的代價，并且現(xiàn)實生活中的數(shù)據(jù)因為一系列原因可能導(dǎo)致一定的誤分類代價.因此，本節(jié)提出基于區(qū)間值數(shù)據(jù)的測試代價和誤分類結(jié)構(gòu).

3.1 代價函數(shù)對于一個鄰域決策信息系統(tǒng)其中U={x1，x2，…，xn}為n維對象集合，C為所有條件屬性集合；D表示決策屬性，N為樣本關(guān)于屬性的鄰域映射函數(shù).設(shè)a∈C，tc為測試代價函數(shù)，tc(a)max是屬性a下所有對象的最高測試代價，即屬性a獲得最高數(shù)據(jù)精度所付出的測試代價，則每個對象的最高總測試代價為tc本文給定屬性a，測試代價函數(shù)根據(jù)應(yīng)用背景以不同的形式表示，本文的線性函數(shù)的測試代價函數(shù)設(shè)計為：

其中，λa∈[0，1 ]是測試代價的一個調(diào)節(jié)因子，調(diào)節(jié)所有對象的測試代價，使每個對象的總測試代價趨于平衡.

對任意B?C，每個對象總測試代價（Total Test Cost，TTC）定義為：

設(shè)mc為誤分類代價函數(shù)，(n，m)為從類n到類m的誤分類.誤分類代價函數(shù)定義如下：

其中，β(n，m)＞0 是一個懲罰因子，用于懲罰從類n到類m?誤分類的對象x.另一種誤分類代價常數(shù)函數(shù)定義如下：

MC(n，m)為從類n分類到類m的誤分類代價，是一個常數(shù).

3.2 平均總代價的計算考慮到一個對象往往屬于多個鄰域粒，可能導(dǎo)致誤分類代價被重復(fù)計算.本文使用文獻［16］中新的誤分類代價計算方法，可以避免過多的重復(fù)計算.

（1）如果?y∈EB(x)且d(y)=d(x)，則把對象x分類到本身所在類，所以mc(x，B)=0.

（2）如果?y∈EB(x)且d(y)≠d(x)，考慮到同一鄰域粒的對象是不可區(qū)分的，假設(shè)它們在分類時具有相同的決策值，那么可以對x進行分類，使EB(x)中所有對象的誤分類總代價最小化，從而得到相應(yīng)的mc(x，B).

則平均誤分類代價（Average Mis-classification Cost，AMC）定義如下：

因為對象的總測試代價是相同的且等于TTC(B)，所以平均總代價（Average Total Cost，ATC）定義如下：

例2（續(xù)例1）給定：tc(a1)max=20，tc(a2)max=63，tc(a3)max=15，λa1=0.3，λa2=0.4，λa3=0.2，則tc(C)max==98.設(shè)B={a1，a3}，因為tc(a1)=20×0.3=6和tc(a3)=15×0.2=3，則有TTC(B)=6+3=9.那么設(shè)β(1，2)=40 和β(2，1)=10，有mc(B)(1，2)=40×9=360，mc(B)(2，1)=10×9=90.

根據(jù)例1 所計算的鄰域，有：

EB(x1)={x1，x6}，EB(x2)={x2，x6}

EB(x3)={x3}，EB(x4)={x4，x6}

EB(x5)={x5，x6}，EB(x6)={x1，x2，x4，x5，x6}

結(jié)合表1，將每個對象按照其鄰域進行分類，得到誤分類代價.具體來說，對于對象x1，假設(shè)鄰域EB(x1)中所有對象都被分類到類“1”，則鄰域EB(x1)中所有對象的誤分類總代價為90.相反，如果將鄰域EB(x1)中所有對象分類到類“2”，則相應(yīng)的誤分類總代價為360.因此將鄰域EB(x1)中所有對象分類到類“1”以獲得較少的誤分類總代價.根據(jù)表1，對象x1本身決策屬性為類“1”，所以對象x1被正確分類，mc(x1，B)=0.對于對象x6，如果把鄰域EB(x6)中所有對象分類到類“1”，則鄰域EB(x6)中所有對象的誤分類總代價為90×3=270.相反，如果將鄰域EB(x6)中所有對象分類到類“2”，則相應(yīng)的誤分類總代價為360×2=720.因此，選擇將鄰域EB(x6)中所有對象分類到類“1”，在這種情況下，x6本身決策屬性為類“2”，但被誤分類到類“1”，所以mc(x6，B)=90.同理可得mc(x2，B)=mc(x3，B)=mc(x4，B)=mc(x5，B)=0.

根據(jù)式（19），AMC(U，B)=90 ∕6=15，然后根據(jù)式（20）得到ATC(U，B)=9+15=24.

代價敏感屬性約簡的目的是找到一個屬性子集，并使得總代價最小化［17-21］，盡可能多地保留原始數(shù)據(jù)中的信息.基于代價敏感區(qū)間值屬性約簡的問題形式定義如下：

4 基于代價敏感區(qū)間值特征選擇算法

本節(jié)提出基于代價敏感的區(qū)間值屬性約簡算法，算法具體步驟展示在算法1 中.

算法1 遵循Liao et al［16］討論的添加-刪除策略，主要包含三個步驟：第一步，初始化全局變量；第二步，選擇出相應(yīng)的屬性子集B；第三步是刪除階段，根據(jù)屬性B中的平均總代價來刪除冗余的屬性.

分析時間復(fù)雜度.對于選擇屬性階段，最壞的情況下，while 循環(huán)m次，即所有條件屬性都被選擇；while 循環(huán)體內(nèi)部最壞的情況下for 循環(huán)將執(zhí)行次，for 循環(huán)體內(nèi)部計算條件熵的時間復(fù)雜度為O(nm)，其中n為對象個數(shù).故在選擇屬性階段時間復(fù)雜度為O(nm3).對于刪除階段，最壞的情況下屬性全部被刪除，這種情況while 循環(huán)執(zhí)行|B|次，相應(yīng)的for 循環(huán)將執(zhí)行次，for 循環(huán)體內(nèi)部平均總代價的時間復(fù)雜度，根據(jù)式（20）可知為O(max(n，m))，故刪除階段時間的復(fù)雜度為故在最壞的情況下算法1的時間復(fù)雜度為O(nm3).

5 實驗與結(jié)果

為了驗證提出算法的有效性，在11 個真實數(shù)據(jù)集上進行了實驗.數(shù)據(jù)集都是從UCI 數(shù)據(jù)庫中獲得，其中Face，F(xiàn)ish，Water 條件屬性值都是原始區(qū)間值數(shù)據(jù)，其他數(shù)據(jù)集的原始屬性值為實值.表3 展示了實驗數(shù)據(jù)的詳細信息.

5.1 實驗準備在進行實驗之前，首先將實值數(shù)據(jù)進行區(qū)間化預(yù)處理，根據(jù)3.1 節(jié)對實驗數(shù)據(jù)進行代價函數(shù)預(yù)處理，先對實驗數(shù)據(jù)的屬性集設(shè)置測試代價.對于屬性數(shù)目小于15 的數(shù)據(jù)集，設(shè)最高測試代價tc(a)max為分布在[20，100 ]內(nèi)的均勻分布的隨機整數(shù)，而其他數(shù)據(jù)集則設(shè)置在[20，200 ]內(nèi)，測試代價調(diào)節(jié)因子λa∈[0，1 ]，設(shè)置誤分類代價懲罰因子β(n，m)為[10，100 ]內(nèi)的整數(shù)，誤分類代價常數(shù)函數(shù)MC(n，m)設(shè)為[5000，50000]內(nèi)的整數(shù).例如Water 數(shù)據(jù)集中有兩個類，分別為類1 和類2，設(shè)置懲罰因子β(1，2)=20 和β(2，1)=50；Face 數(shù)據(jù)集中有九個類，設(shè)置誤分類代價常數(shù)函數(shù)MC(n，m)=10000.

表3 數(shù)據(jù)集介紹Table 3 The introduction of datasets

本文所有實驗都在相同的軟硬件環(huán)境下進行.CPU：Intel（R）Core（TM）i5-9300H CPU @2.40 GHz；RAM：16.0 GB；操作系統(tǒng)：Windows 10；Matlab 版本：Matlab 2019b.

5.2 實驗結(jié)果實驗的結(jié)果展示于表4 中.如表4 所示，TTC，AMC，ATC每列下面劃分為三列，第一列為未經(jīng)屬性約簡的結(jié)果（NFSR），第二列為Dai et al［22］的方法（ARCE）經(jīng)過屬性約簡后的結(jié)果，第三列為本文方法經(jīng)過屬性約簡后的結(jié)果（CSIVARA）.每一行中最小平均總代價（ATC）用黑體字突出顯示.

表4 中Sonar 數(shù)據(jù)集上CSIVARA 的平均總代價高于ARCE；Libras 和Waveform 數(shù)據(jù)集上CSIVARA 的最小平均總代價接近最低平均總代價；其他八個數(shù)據(jù)中CSIVARA 的最小平均總代價都遠低于未約簡前的和對比方法ARCE 的最小平均總代價.總體來說，CSIVARA 表現(xiàn)最好.

5.3 比較與分析為了進一步分析實驗結(jié)果，將CSIVARA 和ARCE 的分類精度進行對比.

為了比較區(qū)間值決策信息系統(tǒng)上屬性約簡的分類性能，利用擴展的KNN 分類器進行分類性能的實驗.

表4 三種方法的平均總代價的比較Table 4 The average total cost of the three methods

設(shè)X和Y是兩個在區(qū)間值信息系統(tǒng)下的對象，是兩個在第k個屬性下的區(qū)間值.X和Y之間距離定義如下［23］：

其中m為條件屬性數(shù)量，是兩個區(qū)間值之間的相似度.

考慮Fish 和Face 數(shù)據(jù)集的樣本數(shù)太少，采用留一交叉驗證的方式驗證分類精度，而對于其他數(shù)據(jù)則采用十折交叉驗證的方式.另外，由于隨機性的問題，所有的實驗結(jié)果都運行20 次，并取20 次平均值作為最終的分類精度，本文使用KNN（k=3）分類器進行實驗.分類精度結(jié)果如圖1 所示，可見兩種方法在Face 數(shù)據(jù)集中的分類精度持平；在Lung 數(shù)據(jù)集中，CSIVARA 分類精度略低于ARCE；在Spectf 和Water 數(shù)據(jù)集中，兩種方法分類精度結(jié)果非常接近；在其他七個數(shù)據(jù)集中，CSIVARA 的分類精度都優(yōu)于ARCE，特別是在Libras 數(shù)據(jù)集中，CSIVARA 分類精度顯著高于ARCE.

圖1 在KNN (k=3)分類器上的平均分類精度結(jié)果Fig.1 Results of average classification accuracy on KNN (k=3)classifier

實驗分析結(jié)果表明，CSIVARA 分類精度高于ARCE，同時還保證了平均總代價最小化.

6 結(jié)論

本文提出基于代價敏感的區(qū)間值屬性約簡方法，該方法根據(jù)原始數(shù)據(jù)的分布構(gòu)建了基于區(qū)間值數(shù)據(jù)的代價敏感函數(shù)，充分考慮了測試代價和誤分類代價對于數(shù)據(jù)的影響.最終實驗表明，本文提出的方法可以在平均總代價較小的情況下有效地選擇重要的候選屬性.未來的工作將繼續(xù)探討區(qū)間鄰域決策系統(tǒng)存在缺失值的情況.