區(qū)間型符號數(shù)據(jù)的特征選擇方法

郭崇慧, 劉永超

(大連理工大學(xué) 系統(tǒng)工程研究所，遼寧 大連 116024)

?

區(qū)間型符號數(shù)據(jù)的特征選擇方法

郭崇慧, 劉永超

(大連理工大學(xué) 系統(tǒng)工程研究所，遼寧 大連 116024)

對區(qū)間型符號數(shù)據(jù)進(jìn)行特征選擇，可以降低數(shù)據(jù)的維數(shù)，提取數(shù)據(jù)的關(guān)鍵特征。針對區(qū)間型符號數(shù)據(jù)的特征選擇問題，本文提出了一種新的特征選擇方法。首先，該方法使用區(qū)間數(shù)Hausdorff距離和區(qū)間數(shù)歐氏距離度量區(qū)間數(shù)的相似性，通過建立使得樣本點(diǎn)與樣本類中心相似性最大的優(yōu)化模型來估計區(qū)間型符號數(shù)據(jù)的特征權(quán)重。其次，基于特征權(quán)重構(gòu)建相應(yīng)的分類器來評價所估計特征權(quán)重的優(yōu)劣。最后，為了驗(yàn)證本文方法的有效性，分別在人工生成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行了數(shù)值實(shí)驗(yàn)，數(shù)值實(shí)驗(yàn)結(jié)果表明，本文方法可以有效地去除無關(guān)特征，識別出與類標(biāo)號有關(guān)的特征。

符號數(shù)據(jù)分析；特征選擇；最近鄰分類器；區(qū)間型數(shù)據(jù)

0 引言

隨著數(shù)據(jù)收集和存儲技術(shù)的不斷進(jìn)步，越來越多的數(shù)據(jù)出現(xiàn)在各個領(lǐng)域當(dāng)中。數(shù)據(jù)的不斷豐富也加大了對海量數(shù)據(jù)分析方法和技術(shù)的需求。傳統(tǒng)的數(shù)據(jù)分析方法在處理海量數(shù)據(jù)時，往往計算量很大，且難以從整體上掌握樣本的性質(zhì)。針對此類問題，Edwin Diday于1988年在國際分類協(xié)會聯(lián)合會(CFCS) 的第一次大會上首次提出了符號數(shù)據(jù)分析( Symbolic Data Analysis, SDA) 技術(shù)[1]。

所謂符號數(shù)據(jù)，是指通過對大的數(shù)據(jù)樣本空間進(jìn)行降維處理，實(shí)現(xiàn)“數(shù)據(jù)合并”而形成的一個“數(shù)據(jù)包”，這個“數(shù)據(jù)包”就被定義為符號數(shù)據(jù)。常用的符號變量類型有區(qū)間型、多值型和分布型[2]。區(qū)間型符號數(shù)據(jù)描述的是一個變量的上下限區(qū)間，通常情況下，它是從一組定量數(shù)據(jù)中找出上限和下限，并利用上下限描述這組定量數(shù)據(jù)的符號數(shù)據(jù)。例如，收集某支股票某日的價格數(shù)據(jù)，用該日該支股票價格的最低值和最高值組成的區(qū)間表示此股票在一天內(nèi)的價格。多值型符號數(shù)據(jù)描述的是有多個取值的變量，一個樣本的值是這個多個取值集合的子集。例如，一個宿舍學(xué)生的生源地變量X={河南，遼寧，吉林}。分布型符號數(shù)據(jù)描述的是一個變量中的各種取值以及各個取值的分布比例或者權(quán)重。例如，一個辦公室內(nèi)的性別變量S=[男性 (0.7)，女性 (0.3)]，其中圓括號中的小數(shù)就描述的是各個性別所占的比例。SDA技術(shù)運(yùn)用“數(shù)據(jù)打包”思想，使得數(shù)據(jù)降維在樣本空間中得以實(shí)現(xiàn)[3]。相較于傳統(tǒng)方法，因?yàn)镾DA技術(shù)能使原始數(shù)據(jù)樣本的個數(shù)大大縮小，所以能夠高效地處理海量數(shù)據(jù)，甚至發(fā)現(xiàn)傳統(tǒng)分析方法所不能發(fā)現(xiàn)的知識。

區(qū)間型符號數(shù)據(jù)作為最常見的一種符號數(shù)據(jù)，具有重要的研究意義。目前針對區(qū)間型符號數(shù)據(jù)的研究主要集中在主成分分析、回歸分析和聚類分析等方面。文[4～6]將主成分分析法應(yīng)用到區(qū)間型符號數(shù)據(jù)。文[7～9]針對區(qū)間型符號數(shù)據(jù)進(jìn)行了回歸分析。文[10～14]對區(qū)間型符號數(shù)據(jù)進(jìn)行聚類分析。然而，針對區(qū)間型符號數(shù)據(jù)的特征選擇問題，卻很少有學(xué)者研究。

特征選擇也叫特征子集選擇，它的目的是從樣本的所有特征中選擇出對描述目標(biāo)概念比較重要的一組特征子集。對區(qū)間型符號數(shù)據(jù)進(jìn)行特征選擇，不僅能夠降低數(shù)據(jù)的復(fù)雜程度和處理時間，而且通常能夠提高預(yù)測器的性能。

文[15]基于相似性邊界，建立了優(yōu)化模型，通過模型求解，得出了一種針對區(qū)間型符號數(shù)據(jù)的特征選擇方法InterSym。然而，InterSym也有一些不足之處。第一，相似性度量標(biāo)準(zhǔn)忽略了區(qū)間中心之間距離對相似性的影響，導(dǎo)致其并不適用于樣本點(diǎn)集中在中心位置的區(qū)間型符號數(shù)據(jù)；第二，InterSym中計算特征權(quán)重的方法，并不適用于在某些特征下，數(shù)據(jù)的多個類中心分別相互靠近的情形。

本文首先基于區(qū)間數(shù)Hausdorff距離和區(qū)間數(shù)歐氏距離給出了更符合現(xiàn)實(shí)意義的區(qū)間數(shù)相似性度量。然后，本文充分地考慮了區(qū)間型數(shù)據(jù)的多個類中心分別相互靠近的情形，并建立了新的優(yōu)化模型估計特征權(quán)重，得到了模型的解析解。本文的第1節(jié)，給出了一些基本概念和定義，包括區(qū)間數(shù)的Hausdorff距離和歐氏距離，以及樣本類中心的表示，并對區(qū)間數(shù)的幾種相似性度量進(jìn)行了比較分析。在第2節(jié)，建立了優(yōu)化模型，得到了模型的解析解。第3節(jié)給出了一種新的區(qū)間型符號數(shù)據(jù)特征選擇方法。第4節(jié)是數(shù)值實(shí)驗(yàn)，將所提出的特征選擇方法應(yīng)用到三個區(qū)間型數(shù)據(jù)集(包括一組人工生成數(shù)據(jù)和兩組真實(shí)數(shù)據(jù))，在分類精度上驗(yàn)證了方法的有效性。第5節(jié)結(jié)束語部分對全文進(jìn)行了總結(jié)。

1 基本概念

1.1 區(qū)間數(shù)相似性度量

相似性度量是分類和聚類的基礎(chǔ)，本文分別應(yīng)用Hausdorff距離和歐氏距離作為區(qū)間型符號數(shù)據(jù)相似性度量的標(biāo)準(zhǔn)，以有效地處理數(shù)據(jù)分布集中在區(qū)間中心位置的區(qū)間型符號數(shù)據(jù)。Hausdorff距離由德國數(shù)學(xué)家Hausdorff于20世紀(jì)初提出，用來定義Rp空間上兩個緊集之間的距離。區(qū)間數(shù)是緊集，因此可以用Hausdorff距離來度量。歐氏距離是n維空間中點(diǎn)與點(diǎn)之間最常用的一種距離度量方法，目前已經(jīng)將其推廣到度量區(qū)間數(shù)的情形。下面給出區(qū)間數(shù)Hausdorff距離[13]和歐氏距離[16]的定義。

定義1 令A(yù)=[A-,A+]和B=[B-,B+]為兩個區(qū)間數(shù)，則A與B之間的Hausdorff距離為：

H(A,B)=|C(A)-C(B)|+|r(A)-r(B)|

(1)

區(qū)間數(shù)的Hausdorff距離綜合了兩個區(qū)間數(shù)中心之間的距離和半徑之間的差異，其中|C(A)-C(B)|為區(qū)間中心之間的距離，|r(A)-r(B)|為半徑之間的差異。令U=[Xmin,Xmax]為整個區(qū)間樣本的域，其中Xmin為所有區(qū)間左側(cè)的下限，Xmax為所有區(qū)間右側(cè)的上限。那么，即可得到兩個區(qū)間數(shù)之間的相似性：

(2)

定義2 令A(yù)=[A-,A+]和B=[B-,B+]為兩個區(qū)間數(shù)。則A與B之間的歐氏距離為：

(3)

不難驗(yàn)證，式(3)可以改寫為:

(4)

上式由兩部分組成，第一部分為區(qū)間中心之間的距離，第二部分為半徑之間的差異。在歐氏距離的基礎(chǔ)上，即可得到兩個區(qū)間數(shù)之間的相似性，

(5)

基于歐氏距離和Hausdorff距離的相似性度量方法均能夠有效地處理集中在區(qū)間中心位置的區(qū)間型符號數(shù)據(jù)，由式(1)和式(4)可以看出，它們本質(zhì)上并無差異，都是基于區(qū)間中心之間的距離和半徑之間的差異。

文[15]提出的相似性標(biāo)準(zhǔn)如下:

(6)

與文[15]的相似性度量方法相比，基于Hausdorff距離和歐氏距離的相似性度量克服了其忽視區(qū)間中心對區(qū)間數(shù)相似性影響的缺點(diǎn)。例如服從高斯分布的區(qū)間型符號數(shù)據(jù)A1=[0,7]，A2=[1,2] ，A3=[3,4]。取U=[0,7]，在文[15]的相似性度量方法下，S(A1,A2)=S(A1,A3)=0.5714，A1與A2，A1與A3之間的相似性是相同的，而實(shí)際情況應(yīng)該是A1與A3的相似性要比A1與A2的相似性更大一些。在Hausdorff距離下，S(A1,A2)=0.2857，S(A1,A3)=0.5714。在歐氏距離下，S(A1,A2)=0.4849，S(A1,A3)=0.5714。本文分別應(yīng)用Hausdorff距離和歐氏距離來度量兩個區(qū)間數(shù)的相似性，能夠有效地處理集中在區(qū)間中心位置的區(qū)間型符號數(shù)據(jù)。

1.2 樣本類中心

假設(shè)類Ck內(nèi)有Nk個樣本點(diǎn)xn,n=1,2,…,Nk.令

(7)

對各個類中心進(jìn)行表示后，可以計算每個樣本點(diǎn)與各個類中心之間的相似性向量。第n個樣本點(diǎn)xn和第k個類Ck的中心之間的相似性可用下面的向量表示：

(8)

2 模型建立與求解

為了更合理地度量兩個區(qū)間樣本點(diǎn)之間的相似性，需要知道特征的權(quán)重。設(shè)第i個特征的權(quán)重為wi,i=1,2,…,n。由式(7)，可以得到第n個樣本點(diǎn)和第k個類Ck的中心之間的整體相似性為：

(9)

(10)

令

(11)

可以看出，ai為在第i個特征下，所有樣本屬于其所在類的可能性之和。由式(11)，式(10)可以寫為：

(12)

在式(10)和式(12)中的歸一化約束之所以取平方和是為了得到更合理的解，因?yàn)槿羧1+w2+…+wm=1，則其為線性優(yōu)化問題，所得的解在邊界的交點(diǎn)處取到，即w=[0,…,1,…,0]，取1的項(xiàng)為目標(biāo)函數(shù)變量系數(shù)最大的項(xiàng)，即最大的ai，這樣僅僅得到了權(quán)重最大的特征，其他特征全被忽略，這顯然不是想要的結(jié)果。

為求約束優(yōu)化模型(12)的解，本文采用懲罰函數(shù)法，先將(12)化成僅含等式約束的情形。令M為足夠大的正數(shù)，則優(yōu)化問題(12)可以化為下面的形式：

(13)

式(13)的Lagrange函數(shù)為：

(14)

目標(biāo)函數(shù)取得最大值的必要條件為：

(15)

整理式(15)，可得：

(16)

令M→+∞，則有：

(17)

(18)

3 區(qū)間型符號數(shù)據(jù)特征選擇算法

上一節(jié)基于所有樣本點(diǎn)與其所在類中心的相似性與其他類中心的相似性差值最大化的想法，建立了優(yōu)化模型，通過模型求解，得到了每個特征的權(quán)重。然后計算每個樣本點(diǎn)與各個類中心之間的加權(quán)相似性。本節(jié)選用最近鄰分類器，特征搜索時采用帶驗(yàn)證集的前向選擇方法，得到了一種區(qū)間型符號數(shù)據(jù)特征選擇方法FSMSID (Feature Selection Method for Symbolic Interval Data)。最近鄰分類器，即每個樣本被劃分到與自身距離最近的類(也是相似度最大的類中心)，簡單高效，易于理解，已經(jīng)被廣泛應(yīng)用于人工智能的各個問題。FSMSID在選擇特征時采用的是帶驗(yàn)證集的前向選擇方法，即每次從剩余特征中加入一個新特征來訓(xùn)練新的模型，依據(jù)模型得到的分類器的精度來評估模型，然后從中選出分類精度最優(yōu)的模型，將其對應(yīng)的新特征加入所選擇的特征集合中。前向選擇避免了組合優(yōu)化的維數(shù)災(zāi)難問題，且能夠有效地去除一些無關(guān)特征和冗余特征。

具體算法如下：

Step 2 依據(jù)式(2)或式(5)計算訓(xùn)練集XT中每個樣本點(diǎn)與各個類中心ρCk之間的相似性向量(8)。

Step 3 依據(jù)式(11)計算ai,i=1,2,…,m。

Step 4 依據(jù)式(18)計算特征權(quán)重wi,i=1,2,…,m。

Step 5 對t=1,2,…,m

(1)令Wt表示第t次已選出的特征集合，W-Wt表示剩余的特征集合。對wj∈W-Wt,j=1,2,…,m-mt，其中mt表示W(wǎng)t中特征的個數(shù)。

(a)將W-Wt-wj中的特征權(quán)重全部賦值為零。

(b)用驗(yàn)證集XV中的數(shù)據(jù)檢驗(yàn)分類器的精度：

(2)若Rt+1≤Rt，結(jié)束。

4 數(shù)值實(shí)驗(yàn)

為了驗(yàn)證本文方法的有效性，將其應(yīng)用于三組數(shù)據(jù)集。然后分別應(yīng)用文[15]中的方法InterSym和本文方法FSMSID(分別基于Hausdorff距離和歐氏距離)處理這三組數(shù)據(jù)，以分類器的精度作為方法有效性的評價標(biāo)準(zhǔn)。其中，第一個數(shù)據(jù)集為人工生成，包含2000個樣本點(diǎn)，采用的驗(yàn)證方法為10折交叉驗(yàn)證，第二個數(shù)據(jù)集和第三個數(shù)據(jù)集為真實(shí)數(shù)據(jù)集，它們來源于http://lhedjazi.jimdo.com/usef-ullinks，因樣本個數(shù)較少，故采用留一法交叉驗(yàn)證。

第一個數(shù)據(jù)集具體模擬生成方法如下：

(1) 生成區(qū)間中點(diǎn)的隨機(jī)點(diǎn)數(shù)據(jù)集

首先生成4組數(shù)據(jù)，每組500個樣本，每個樣本4個特征(x,y,z,v)，每一個點(diǎn)作為所要生成的區(qū)間樣本集的一個區(qū)間中心。z為隨機(jī)生成的[-2,2]上服從均勻分布的無關(guān)特征。x,y,v服從正態(tài)分布，具體生成規(guī)則如下：

第一組：μx=-1,σx=0.4,μy=-1,σy=0.8,μv=-1,σv=0.4;

第二組：μx=-1,σx=0.4,μy=1,σy=0.8,μv=-0.4,σv=0.4;

第三組：μx=1,σx=0.4,μy=-1,σy=0.8,μv=0.3,σv=0.4;

第四組：μx=1,σx=0.4,μy=1,σy=0.8,μv=1,σv=0.4;

其中μ為期望，σ為標(biāo)準(zhǔn)差。

數(shù)據(jù)集中的每一個樣本有四個變量(x,y,z,v)確定。每個點(diǎn)的類別標(biāo)號由該點(diǎn)在x,y的坐標(biāo)符號所決定。具體如下：

第一類：x>0,y>0; 第二類：x>0,y<0; 第三類：x<0,y>0; 第四類：x<0,y<0

每個樣本的區(qū)間中心點(diǎn)的特征x,y決定了該樣本的類別，特征z為無關(guān)特征，特征v為生成的與類別標(biāo)號具有一定相關(guān)性的特征。

(2) 產(chǎn)生隨機(jī)區(qū)間數(shù)據(jù)集

隨機(jī)生成[0,0.5]上服從均勻分布的點(diǎn)數(shù)據(jù)(2000×4的矩陣)，與(1)中的點(diǎn)數(shù)據(jù)相對應(yīng)，作為區(qū)間樣本集的半徑。對點(diǎn)(x,y,z,v)，若對應(yīng)生成的半徑為r1,r2,r3,r4，則得到一個區(qū)間型樣本([x-r1,x+r1],[y-r2,y+r2],[z-r3,z+r3],[v-r4,v+r4])，它的類標(biāo)號由x,y的符號決定。這樣就得到了一個隨機(jī)區(qū)間數(shù)據(jù)集(rand data)。

將本文算法FSMSID(分別基于Hausdorff距離和歐氏距離)和文[15]的InterSym在rand data上運(yùn)行5次，得到了特征權(quán)重平均值和分類錯誤率平均值，如表1和表2所示，其中FSMSID(H)表示基于Hausdorff距離的FSMSID，F(xiàn)SMSID(E)表示基于歐氏距離的FSMSID。

表1 兩種方法在rand data上的特征權(quán)重比較

表2 兩種方法在rand data上的分類錯誤率比較

特征1特征1、2特征1、2、3特征1、2、3、4InterSym0．3204(v)0．3131(v，y)0．3125(v，y，x)0．3195(v，y，x，z)FSMSID(H)0．3552(v)0．1164(v，y)0．0636(v，y，x)0．0636(v，y，x，z)FSMSID(E)0．3618(v)0．1072(v，y)0．0539(v，y，x)0．0539(v，y，x，z)

表2中的特征1、2表示依據(jù)前兩個特征產(chǎn)生的分類器的分類錯誤率。如：0.3131(v,y)表示選出的前兩個特征是v和y，并依據(jù)這兩個特征產(chǎn)生分類器，得到的分類器的分類錯誤率為0.3131。

從表2可以看到，在對rand data數(shù)據(jù)集進(jìn)行特征選擇后，F(xiàn)SMSID得到的分類器的錯誤率要遠(yuǎn)遠(yuǎn)低于InterSym，這也說明了FSMSID所選特征權(quán)重的合理性。

圖1 區(qū)間型符號數(shù)據(jù)集

第二個數(shù)據(jù)集為Car Data，該數(shù)據(jù)集中一共包含33個汽車樣本，每個樣本有8個區(qū)間型特征(Price, Engine, Capacity, Top Speed, Acceleration, Step, Length, Width, Height)和三個類別變量，它們共分為4個類：實(shí)用型(Utilitarian)、貝琳娜(Berlina)、運(yùn)動型(Sporting)、豪華型(Luxury)。在這里，僅考慮8個區(qū)間型的特征。

表3是兩種方法在Car Data上的特征權(quán)重比較。從表3可以看到，InterSym所得的特征權(quán)重排序從大到小依次為3、8、1、4、2、6、5、7，F(xiàn)SMSID(H)所得的特征權(quán)重排序從大到小依次為2、5、8、6、4、1、3、7，F(xiàn)SMSID(E)所得的特征權(quán)重排序從大到小依次為2、8、5、6、4、1、7、3。由此可以看出，F(xiàn)SMSID(H)和FSMSID(E)所得到的權(quán)重大小及排序基本相同，但與InterSym相差較大。圖2是FSMSID與InterSym在Car Data上的分類精度對比，在InterSym下，選4個特征(Height, Top Speed, Price, Acceleration)時產(chǎn)生分類效果最好的分類器，其分類錯誤率為21.21%。FSMSID(H)選5個特征(Engine Capacity, Step, Height, Length, Acceleration) 得到的分類器分類精度最好，其分類錯誤率為15.15%。FSMSID(E)選4個特征(Engine Capacity, Height, Step, Length) 得到分類精度最好的分類器，其分類錯誤率為15.15%。從圖2可以看出，在分類精度上，F(xiàn)SMSID優(yōu)于InterSym。

表3 兩種方法在Car Data上的特征權(quán)重比較

圖2 兩種方法在Car Data上的分類錯誤率比較

第三個數(shù)據(jù)集是Fish Dataset，該數(shù)據(jù)集包括12個淡水魚樣本，每一個有13個區(qū)間特征(Length，Weight，Muscle，Intestine，Stomach，Gills，Liver，Kidneys，Liver/muscle，Kidneys/muscle，Gills/muscle，Intestine/muscle，Stomach/muscle)，依據(jù)它們的飲食共分為4個類別，肉食類(Carnivorous)，糞食類(Detritivorous)，雜食類(Omnivorous)，草食類(Herbivorous)。

表4是兩種算法在Fish Dataset上的特征權(quán)重比較。從表4可以看到，InterSym所得的特征權(quán)重排序從大到小依次為1、3、11、6、4、2、5、7、8、9、10、12、13，且特征2(包括特征2)之后的特征權(quán)重均為0。FSMSID(H)所得的特征權(quán)重排序從大到小依次為12、13、1、5、7、9、10、11、2、3、4、6、8，F(xiàn)SMSID(E)所得的特征權(quán)重排序從大到小依次為12、13、1、5、7、9、10、11、2、3、4、6、8?？梢钥闯?，F(xiàn)SMSID(H)和IFSMSID(E)所得到的權(quán)重大小基本相同，排序完全一致，但與InterSym相差較遠(yuǎn)。圖3為是FSMSID與InterSym在Fish Dataset上的分類精度對比。從圖3可以看到，在InterSym下，選前4個特征(Length，Muscle，Intestine/muscle，Gills)時產(chǎn)生分類效果最好的分類器，其分類錯誤率為25%。FSMSID(H)和FSMSID(E)只需選2個特征(Intestine/muscle，Stomach/muscle) 就可得到分類精度最好的分類器，其分類錯誤率為8.33%。

表4 兩種方法在Fish Dataset上的特征權(quán)重比較

5 結(jié)束語

圖3 兩種方法在Fish Dataset上的分類錯誤率比較

本文首先比較分析了區(qū)間數(shù)的相似性度量標(biāo)準(zhǔn)，指出基于區(qū)間數(shù)歐氏距離和區(qū)間數(shù)Hausdorff距離的相似性度量方法更適用于現(xiàn)實(shí)中普遍存在的分布集中在中心的區(qū)間型符號數(shù)據(jù)。然后，本文建立了新的優(yōu)化模型來估計區(qū)間型符號數(shù)據(jù)的特征權(quán)重，該優(yōu)化模型能夠有效地處理在某些特征下，樣本多個類中心相互接近的區(qū)間型符號數(shù)據(jù)。其次，本文方法在搜索特征子集時采取前向選擇方法，能夠避免維數(shù)災(zāi)難，且有效去除一些冗余特征。最后，本文做了3組對比實(shí)驗(yàn)，結(jié)果顯示本文方法在分類精度上要優(yōu)于InterSym方法。

本文算法只是針對類標(biāo)號已知的區(qū)間型符號數(shù)據(jù)，但現(xiàn)實(shí)中存在很多類標(biāo)號未知的區(qū)間型符號數(shù)據(jù)。針對類標(biāo)號未知或部分未知的區(qū)間型符號數(shù)據(jù)的特征選擇問題，目前尚無研究工作，將來的進(jìn)一步工作可在這方面展開。

[1] Bock H H, Diday E. Analysis of symbolic data: exploratory methods for extracting statistical information from complex data[M]. Springer, 1999.

[2] 李汶華,郭均鵬.區(qū)間型符號數(shù)據(jù)回歸分析及其應(yīng)用[J].管理科學(xué)學(xué)報,2010,13(4):38-43.

[3] 胡艷,王惠文.一種海量數(shù)據(jù)分析技術(shù)-符號數(shù)據(jù)分析及應(yīng)用[J].北京航空航天大學(xué)學(xué)報,2004,17(2):40-44.

[4] Douzal-Chouakria A, Billard L, Diday E. Principal component analysis for interval-valued observations[J]. Statistical Analysis and Data Mining, 2011, 4(2): 229-246.

[5] Lauro C N, Palumbo F. Principal componment analysis of interval data: a symbolic data analysis approach[J]. Computational Statisics, 2000, 15(1): 73-87.

[6] Gioia F, Lauro C N. Principal component analysis on interval data[J]. Computational Statistics, 2006, 21(2): 343-363.

[7] Lima Neto E A, de Carvalho F A T. Centre and range method for fitting a linear regression model to symbolic interval data[J]. Computational Statistics & Data Analysis, 2008, 52(3): 1500-1515.

[8] Domingues M A O, de Souza R M C R, Cysneiros F J A. A robust method for linear regression of symbolic interval data[J]. Pattern Recognition Letters, 2010, 31(13): 1991-1996.

[9] Lima Neto E A, de Carvalho F A T. Constrained linear regression models for symbolic interval-valued variables[J]. Computational Statistics & Data Analysis, 2010, 54(2): 333-347.

[10] 張偉斌,劉文江.區(qū)間型數(shù)據(jù)的模糊c均值聚類算法[J].計算機(jī)工程,2008,34(11):26-28.

[11] De Souza R M C R, de Carvalho F A T. Clustering of interval data based on city-block distances[J]. Pattern Recognition Letters, 2004, 25(3): 353-365.

[12] Chavent M, de Carvalho F A T, Lechevallier Y, et al. New clustering methods for interval data[J]. Computational statistics, 2006, 21(2): 211-229.

[13] De Carvalho F D A T, de Souza R M C R, Chavent M, et al. Adaptive Hausdorff distances and dynamic clustering of symbolic interval data[J]. Pattern Recognition Letters, 2006, 27(3): 167-179.

[14] De Carvalho F A T, Lechevallier Y. Partitional clustering algorithms for symbolic interval data based on single adaptive distances[J]. Pattern Recognition, 2009, 42: 1223-1236.

[15] Hedjazi L, Aguilar-Martin J, Lann M L. Similarity-margin based feature selection for symbolic interval data[J]. Pattern Recognition Letters , 2011, 32(4): 578-585.

[16] 謝信喜,王士同.適用于區(qū)間數(shù)據(jù)的基于相互距離的相似性傳播聚類[J].計算機(jī)應(yīng)用,2008,28(6):1441-1443.

A Feature Selection Method for Symbolic Interval Data

GUO Chong-hui, LIU Yong-chao

(InstituteofSystemsEngineering,DalianUniversityofTechnology,Dalian116024,China)

Feature selection for symbolic interval data can reduce the dimension of data and extract the key features of data.In order to deal with the feature selection problem, a new method is proposed in this paper. Firstly, Hausdorff distance and Euclidean distance are utilized to measure the similarity between two interval numbers, and an optimization model, which aims to maximize the similarity between each sample and its class center, is established to estimate the feature weights for symbolic interval data. Next, based on the estimated feature selection weights, a classifier is constructed to evaluate the goodness of the weights. Finally, in order to verify the effectiveness of the proposed method, numerical experiments are done in artificially generated data sets and real data sets, respectively. The numerical experiments results show that the proposed algrithm can eliminate irrelevant features and identify features which are relevant to the class labels.

symbolic data analysis; feature selection; nearest neighbor classifier；interval data

2013- 08-27

國家自然科學(xué)基金資助項(xiàng)目(71171030，71031002)；教育部新世紀(jì)優(yōu)秀人才支持計劃(NCET-11- 0050)

郭崇慧(1973-)，男，博士，教授，博士生導(dǎo)師，主要研究方向：數(shù)據(jù)挖掘與知識發(fā)現(xiàn)， 決策理論與方法等。劉永超(1989-)，男，碩士研究生，研究方向：符號數(shù)據(jù)挖掘。

O235

A

1007-3221(2015)01- 0067- 08