多尺度鄰域決策信息系統(tǒng)的特征子集選擇

張廬婧 林國平 林藝東 寇 毅

ZHANG Lujing1,2, LIN Guoping1,2 , LIN Yidong1, KOU Yi1

粒計算[1-2]是知識發(fā)現(xiàn)和數(shù)據(jù)挖掘的重要方法之一,源自Zadeh[3]在模糊集理論背景下提出的“信息粒度”.而后Pawlak[4]提出經(jīng)典粗糙集理論,便于分析和處理語義型的數(shù)據(jù),尤其善于處理不確定問題.

然而經(jīng)典粗糙集僅適用于處理語義型數(shù)據(jù),并不適用于實際生活中廣泛存在的異構(gòu)數(shù)據(jù).因此,胡清華等[5]利用拓?fù)淇臻g中的球形鄰域概念構(gòu)造鄰域粗糙集,用于研究數(shù)值型數(shù)據(jù).此后,Hu等[6]通過鄰域粗糙集模型解決異構(gòu)特征選擇的問題.Chen等[7]提出基于優(yōu)勢關(guān)系的鄰域粗糙集模型,并設(shè)計并行的特征選擇算法.Hu等[8]為了挖掘特征與決策之間的相關(guān)性,在鄰域關(guān)系中引入權(quán)重的概念,構(gòu)造加權(quán)鄰域粗糙集模型.

上述研究均為單尺度決策表,即僅研究特征在單一尺度下的取值問題，而實際生活中存在的信息大多需要從多個尺度進行研究.針對該問題,Wu等[9]提出多尺度信息系統(tǒng)，描述不同尺度下信息粒之間的關(guān)系,并針對不一致的多尺度決策系統(tǒng)提出知識獲取算法[10],進一步分析多尺度決策系統(tǒng)的最優(yōu)尺度選擇問題[11].She等[12]研究局部規(guī)則歸納法.Wu等[13]提出不完備信息系統(tǒng)的規(guī)則獲取方法.Li等[14]以Wu-Leung研究的特殊案例為例,研究不同特征在不同尺度等級下的多尺度決策系統(tǒng),提出補模型和格模型.吳偉志團隊[15-20]利用D-S理論，提出一系列多尺度決策系統(tǒng)的擴展模型.牛東苒等[21]基于對偶概率粗糙集模型討論廣義多尺度決策系統(tǒng)中的最優(yōu)尺度組合選擇問題.Huang等[22-23]研究具有多尺度決策屬性的廣義多尺度決策系統(tǒng),將劃分?jǐn)U展到覆蓋,建立多尺度覆蓋數(shù)據(jù)分析模型.Li等[24]在多尺度覆蓋的基礎(chǔ)上研究鄰域算子和近似算子的一些性質(zhì),建立基于多尺度覆蓋的粗糙集模型.Zheng等[25]研究基于優(yōu)勢關(guān)系的多尺度序決策系統(tǒng).Wang等[26]構(gòu)造基于多粒度的多尺度決策系統(tǒng)擴展模型，用于知識發(fā)現(xiàn).

近年來,Li等[27-29]研究動態(tài)多尺度決策系統(tǒng)的最優(yōu)尺度選擇問題.陳應(yīng)生等[30]構(gòu)造多尺度集值信息系統(tǒng),討論協(xié)調(diào)和不協(xié)調(diào)情況下的最優(yōu)尺度選擇問題.陳應(yīng)生等[31]又采用布爾矩陣方法研究多尺度覆蓋決策信息系統(tǒng).Huang等[32-33]研究基于優(yōu)勢關(guān)系的多尺度IF決策表.之后Huang等[34]又提出多尺度模糊決策系統(tǒng),用于研究多尺度粗糙集的模糊泛化及其在數(shù)值數(shù)據(jù)特征選擇中的應(yīng)用.楊璇等[35]將模糊相似關(guān)系引入多尺度決策系統(tǒng),拓展模糊決策粗糙集模型的應(yīng)用.但是,目前針對適用于研究多源異構(gòu)多尺度數(shù)據(jù)的多尺度決策信息系統(tǒng)模型仍較少見.

隨著大數(shù)據(jù)時代的到來,數(shù)據(jù)表現(xiàn)形式多樣化.例如,同一部電影在不同平臺的評價體系擁有多個評價方式,評分可記錄為0～10之間的數(shù)值型數(shù)據(jù),也可用0～5顆星星數(shù)進行評價,再或是留言評價等.值得注意的是,數(shù)據(jù)來源于多個平臺,并且每個平臺的評分細(xì)則是多尺度的.與此同時,這類多源異構(gòu)多尺度數(shù)據(jù)集不僅包含語義型數(shù)據(jù),同時也包含數(shù)值型數(shù)據(jù).在此情況下,無法使用現(xiàn)有的一些模型進行有效處理.為此,本文針對這一類型數(shù)據(jù)集構(gòu)建多尺度鄰域決策信息系統(tǒng),便于實際生活中多源異構(gòu)多尺度數(shù)據(jù)集的研究,并討論模型的相關(guān)性質(zhì).

1 預(yù)備知識

1.1 鄰域決策系統(tǒng)

定義1[5]給定非空有限集合

U={x1,x2,…,xn},

A為描述U的特征集,D為決策特征,若A生成論域上的一族鄰域關(guān)系,則稱NDT=〈U,A,D〉為一個鄰域決策系統(tǒng).對于U上的任意對象xi,定義由xi生成的δ鄰域信息粒：

δ(xi)={x|x∈U,Δ(x,xi)≤δ},

其中，δ≥0，Δ為RN上的一個度量,滿足自反性、對稱性和三角不等性.

定義2[5]給定一個鄰域決策系統(tǒng)NDT=〈U,A,D〉,根據(jù)決策特征D可將U劃分為N個等價類{X1,X2,…,XN},?B?A,定義決策D關(guān)于B的下近似和上近似:

其中，

δB(xi)為樣本xi在特征子集B中的鄰域信息粒.

決策的邊界定義為

決策D的下近似也稱為決策正域,記為POSB(D).決策特征D對條件特征B的依賴度定義為

1.2 多尺度信息系統(tǒng)

定義3[11]多尺度信息系統(tǒng)可表示為

即

性質(zhì)1[11]給定一個多尺度信息系統(tǒng)

對于B?A,k∈{1,2,…,I},有

RBk={(x,y)∈U×U|ak(x)=ak(y)?a∈B},

[x]Bk={y∈U|(x,y)∈RBk}=

{y∈U|ak(x)=ak(y)?a∈B},

U/RBk={[x]Bk|x∈U}，

則

RB1?RB2?…?RBI,

[x]B1?[x]B2?…?[x]BI,

U/RB1U/RB2…U/RBI.

定義4[11]給定一個系統(tǒng)

為多尺度決策系統(tǒng),其中

為一個多尺度信息系統(tǒng),d∶U→Vd稱為決策.

定義5[11]給定一個多尺度決策系統(tǒng)

S稱為協(xié)調(diào)的決策系統(tǒng)當(dāng)且僅當(dāng)最細(xì)尺度等級下的決策系統(tǒng)S1為協(xié)調(diào)的.若Sk為協(xié)調(diào)的,但Sk+1為不協(xié)調(diào)的,則稱S的第k尺度等級為最優(yōu)尺度.

2 多尺度鄰域決策信息系統(tǒng)

在經(jīng)典的多尺度信息系統(tǒng)[9]中,每個特征在不同尺度下的特征值不一致,但約束每個特征的尺度等級個數(shù)相同,本文仍保持此假定.

定義7給定一個多尺度鄰域決策信息系統(tǒng)

對于鄰域半徑δ關(guān)于特征子集B的多尺度鄰域相似關(guān)系定義如下:

當(dāng)I=1時,多尺度鄰域相似關(guān)系退化為經(jīng)典的鄰域相似關(guān)系.因此,多尺度鄰域相似關(guān)系可視為鄰域相似關(guān)系的推廣.

鄰域半徑δ的選取是影響多尺度鄰域相似關(guān)系的關(guān)鍵因素之一,本文參考文獻[36]中利用標(biāo)準(zhǔn)差的方法,改進后得到更適用于本文的鄰域半徑δ的定義.

定義8給定一個多尺度鄰域決策信息系統(tǒng)

對于?B?A,定義鄰域半徑：

例1給定一個多尺度鄰域決策信息系統(tǒng),

其中U為對象集,表示不同的電影,

表示電影在不同平臺上對應(yīng)的不同評價標(biāo)準(zhǔn),第一尺度等級為每部電影在該平臺上評分的標(biāo)準(zhǔn)化數(shù)據(jù),第二尺度等級為觀眾在該平臺上的留言評價,即

V2={1,2,3}={不好看,一般,好看},

第三個尺度等級為該平臺上專業(yè)影評的評價,即

V3={1,2}={不喜歡,喜歡},

決策d為電影的最終評價分類.多尺度鄰域決策信息系統(tǒng)如表1所示.

表1 多尺度鄰域決策信息系統(tǒng)

根據(jù)定義8，α=1/3,μ=0.4,計算得到每個特征在不同尺度下的鄰域半徑分別為

性質(zhì)2給定一個多尺度鄰域決策信息系統(tǒng),

證明先證明1).若x∈U,對于(x,x),有

定義9給定一個多尺度鄰域決策信息系統(tǒng)

L={(l1,l2,…,lm)|lj∈{1,2,…,I},j={1,2,…,m}},

表示為多尺度組合全體.若

K1={l1,l2,…,lm},K2={k1,k2,…,km},

且

lj≤kj,j=1,2,…,m,

則表示K1細(xì)于K2,記為K1?K2;若

lj

則表示K1嚴(yán)格細(xì)于K2,記為K1K2.

定義10給定一個多尺度鄰域決策信息系統(tǒng)

性質(zhì)3對于

?K1=(k1,k2,…,km)∈L,K2=(l1,l2,…,lm)∈L,

x∈U,對應(yīng)的多尺度鄰域相似關(guān)系族及多尺度鄰域信息粒有如下性質(zhì):

證明先證明1).若δ1≤δ2,由于

再證明2).由于

設(shè)

K1=(k1,k2,…,km)∈L,K2=(l1,l2,…,lm)∈L,

對于K1?K2,?1≤j≤m,有kj≤lj,可得

可得

最后證明4).由2)可得:若K1?K2,有

(RK1)δ?(RK2)δ,

又

可得

定義11給定一個多尺度鄰域決策信息系統(tǒng)

對于

2)若δ1≤δ2,則POSRKδ1(d)?POSRKδ2(d);

證明先證明1).根據(jù)性質(zhì)3中3)可得,若δ1≤δ2,則

可得

再證明2).由1)根據(jù)性質(zhì)3中3)可得,若δ1≤δ2,則

對?y∈U,可得,若δ1≤δ2,則

又

可得

POSRKδ1(d)?POSRKδ2(d).

再證明3).根據(jù)性質(zhì)3中4)可得,若K1?K2,則

可得

最后證明4).根據(jù)3)可得,若K1?K2,則

又

可得

定義12給定一個多尺度鄰域決策信息系統(tǒng)

K=(k1,k2,…,km)∈L,

1)若δ1≤δ2,則γRKδ1(d)≥γRKδ2(d);

證明先證明1).由性質(zhì)4中2)可得,若δ1≤δ2,則

POSRKδ1(d)?POSRKδ2(d),

又

可得

γRKδ1(d)>γRKδ2(d).

再證明2).由性質(zhì)4中4)可得,若K1?K2,則

又

可得

3 多尺度鄰域決策信息系統(tǒng)的特征子集選擇算法

現(xiàn)有的關(guān)于多尺度決策信息系統(tǒng)特征子集選擇的研究多數(shù)采用首先選出最優(yōu)尺度再進行特征選擇的方式.與之不同的是,本文采用特征選擇和最優(yōu)尺度選擇結(jié)合的方式對多尺度鄰域決策信息系統(tǒng)進行特征子集選擇.面對多尺度模型中最優(yōu)尺度選擇時間復(fù)雜度過大的問題,文獻[37]中提出逐步最優(yōu)尺度算法,相比格模型[14],可有效減少最優(yōu)尺度選擇的時間成本.受逐步最優(yōu)尺度算法[37]啟發(fā),本文引入特征重要度閾值λ進行特征子集選擇.

定義13給定一個多尺度鄰域決策信息系統(tǒng)

K0=(1,1,…,1)∈L,K=(k1,k2,…,km)∈L,

定義14給定一個多尺度鄰域決策信息系統(tǒng)

K=(1,1,…,kj,…,1)∈L,

因此,根據(jù)定義14可得

并且對于特征aj的重要度采用加權(quán)和的方式進行定義,即

由此根據(jù)定義14給出的特征子集選擇算法.首先基于最細(xì)的尺度組合計算每個特征在不同尺度下特征的重要度,采用加權(quán)和的方式計算每個特征的重要度.由于重要度較小的特征對分類的影響較小,根據(jù)設(shè)定的閾值λ,刪除重要度小于閾值λ的特征,對于其余特征，根據(jù)特征的重要度由小到大排序,根據(jù)所得的排序依次對每個特征進行選擇最優(yōu)尺度,得到特征子集.具體算法步驟如下.

算法1多尺度鄰域決策信息系統(tǒng)的特征子集選擇

算法

輸入多尺度鄰域決策信息系統(tǒng)

S=(U,A∪j5i0abt0b,

閾值λ

輸出特征子集X

初始化X=[],S′=[]

Fork=1∶Im

//Im為每個特征的最粗尺度

令K←(1;1;…;k;…;1)

Foraj∈A(j=1,2,…,m)

令S′←S′∪{aj}

End

End

End

Forap∈S′(j=1,2,…,q)

特征進行排序,得到τ

Forapinτ

Fork=Ip∶1

令K′(p)←k∥K′(p)表示中的第p個元素

得到特征子集選擇后的最優(yōu)尺度組合K′

End

End

End

得到特征子集X

End

特征子集選擇算法的時間復(fù)雜度為

因此,本文算法同時進行最優(yōu)尺度選擇和特征選擇,減少搜索最優(yōu)尺度組合的遍歷次數(shù),有效提高特征子集選擇的效率.

例2(續(xù)例1) 根據(jù)定義14得到每個特征在每個尺度下的重要度：

進而得到每個特征的重要度:

由于每個特征的重要度一致,設(shè)λ=0.根據(jù)特征的重要度排序得到τ=123，

1)考慮特征a1.當(dāng)K1=(3,1,1)時,計算得到

2)考慮特征a2.當(dāng)K2=(3,3,1)時,計算得到

3)考慮特征a3.當(dāng)K4=(3,2,3)時,計算得到

K′=(3,2,1).

4 實驗及結(jié)果分析

對于本文提出的多尺度鄰域決策信息系統(tǒng)模型及對應(yīng)的特征子集選擇算法,本節(jié)通過實驗分析驗證其可行性和有效性.所有實驗硬件環(huán)境配置為Inter(R)Core(TM)i5-8250U CPU@1.60 GHz和4 GB內(nèi)存的個人計算機,算法運行的軟件環(huán)境為Matlab R2021a.

實驗數(shù)據(jù)集選擇UCI數(shù)據(jù)庫上的7個數(shù)據(jù)集,具體如表2所示.由于均為相應(yīng)的單尺度決策表，因此需要進行預(yù)處理,構(gòu)建相應(yīng)的多尺度鄰域決策表.

表2 實驗數(shù)據(jù)集

通過文獻[14]中方法類比得到多源異構(gòu)多尺度數(shù)據(jù)集.鑒于語義型數(shù)據(jù)需轉(zhuǎn)化為整數(shù)的數(shù)值型數(shù)據(jù)進行實驗,故后續(xù)數(shù)據(jù)獲取均用整數(shù)表示.

1)若對象的某一特征值缺失,刪除該對象.

2)設(shè)σa為標(biāo)準(zhǔn)差,ma為最小值,a(x)表示原始數(shù)據(jù)的特征值,則多尺度鄰域決策信息表中第一尺度的對象x的特征值為

根據(jù)特征值a1(x)得到相應(yīng)的特征值,若對象的某一特征值為0,刪除該對象,得到第一尺度的特征值.

3)利用定義8中的鄰域半徑定義求取第一尺度的鄰域相似類的平均值,并保留兩位小數(shù)作為第二尺度對應(yīng)的特征值a2(x),刪除特征值為0所在的對象,其中對應(yīng)δ中的a1的取值為決策類的個數(shù)d.以此類推,ak的取值遞減,直到k的取值為d/3-1,即

其中d為決策類的個數(shù).

4)從k=d/3開始,求取前一個尺度級別的鄰域相似類的平均值后取整.對于后續(xù)尺度等級的獲取,將在前一個尺度級別的基礎(chǔ)上,通過從上到下的方式合并某個值,直到某個特征的當(dāng)前尺度級別中的等價類數(shù)量不超過3個.

對于所得特征子集結(jié)果，采用十折交叉驗證法分別在SVM和KNN兩個分類器上進行分類性能評估.將本文算法得到的特征子集(簡記為Opt)分類精度與原始數(shù)據(jù)集(簡記為Raw)、最細(xì)尺度數(shù)據(jù)集(簡記為Fin)、最粗尺度數(shù)據(jù)集(簡記為Coa)在分類器上的分類精度進行對比,詳情如表3和表4所示，表中參數(shù)設(shè)置為α=0.1,μ=0.8.從實驗結(jié)果可知,通過本文的模型與算法,可獲得較好的特征子集,分類精度近似于原始數(shù)據(jù)集在分類器上的分類精度,且絕大多數(shù)分類精度優(yōu)于最細(xì)尺度數(shù)據(jù)集和最粗尺度數(shù)據(jù)集.由此說明本文的模型與算法是有效的.

表3 在分類器SVM上的分類精度對比

表4 在分類器KNN(K=2)上的分類精度

5 結(jié)束語

本文針對多源異構(gòu)多尺度數(shù)據(jù)進行研究,通過構(gòu)造多尺度鄰域信息粒,提出多尺度鄰域決策信息系統(tǒng)模型,給出多尺度鄰域半徑的形式化定義,對多尺度鄰域相似關(guān)系及上下近似的相關(guān)定義進行理論分析.最后,給出基于特征重要度的多尺度鄰域決策系統(tǒng)的特征子集選擇算法,并通過實驗驗證算法的有效性.今后將進一步探索多尺度信息系統(tǒng)在多源異構(gòu)多尺度數(shù)據(jù)上的研究,著重考慮大型數(shù)據(jù)集的多尺度鄰域決策信息系統(tǒng)的知識表示、規(guī)則提取等問題.