代 琪，李 敏 ，2，3，劉 洋，李麗紅，2，3

1.華北理工大學(xué) 理學(xué)院，河北 唐山 063210

2.河北省數(shù)據(jù)科學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，河北 唐山 063210

3.唐山市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室，河北 唐山 063210

屬性約簡(jiǎn)是粗糙集理論的重要研究?jī)?nèi)容，通過(guò)確定信息表達(dá)系統(tǒng)中條件屬性的重要性，在保證信息系統(tǒng)性能不變的前提下，刪除冗余屬性，簡(jiǎn)化知識(shí)表達(dá)空間[1]。高媛等[2]針對(duì)較大樣本集，提出了一種一致性樣本約簡(jiǎn)策略，在滿足一致性原則前提下，選擇部分樣本組成新的決策系統(tǒng)，提高算法的運(yùn)算速度。孫妍等[3]通過(guò)構(gòu)造極大相容塊的辨識(shí)矩陣縮小矩陣的規(guī)模，簡(jiǎn)化計(jì)算屬性約簡(jiǎn)過(guò)程，有效地節(jié)省計(jì)算時(shí)間和存儲(chǔ)空間。米據(jù)生等[4]為了高效處理高維數(shù)據(jù)集，將圖論與區(qū)分矩陣相結(jié)合，提出基于圖論的粗糙集約簡(jiǎn)算法，有效地提高了運(yùn)算速度及分類精度。Yu 等[5]提出兩種基于最小元素選擇樹(shù)結(jié)構(gòu)的屬性約簡(jiǎn)算法，利用多種策略消除可分辨矩陣中的冗余元素，從而提高約簡(jiǎn)速度，降低運(yùn)算成本。高陽(yáng)等[6]為了減少算法時(shí)間成本，改進(jìn)FHARA（Fast Hash Attribute Reduct Algorithm）算法，利用矩陣保留度量計(jì)算值的平方，將原本n維上的計(jì)算改進(jìn)為1 維上的計(jì)算，從而降低了算法運(yùn)算時(shí)間。Fan等[7]提出廣義屬性約簡(jiǎn)算法和廣義正域計(jì)算算法，利用廣義的不可辨性減少模型的粒度結(jié)構(gòu)，構(gòu)建多個(gè)不可分辨關(guān)系引起的定量度量，用于減少模型的計(jì)算成本。Fang 等[8]提出了在定性和定量標(biāo)準(zhǔn)下，基于三支決策和可辨矩陣的代價(jià)敏感近似屬性約簡(jiǎn)算法，該算法將原始數(shù)據(jù)空間近似為一個(gè)低維空間，在低維空間上建模，提升了模型的運(yùn)算時(shí)間。

傳統(tǒng)屬性約簡(jiǎn)算法的計(jì)算時(shí)間較長(zhǎng)，難以應(yīng)用于高維數(shù)據(jù)集，分析以上研究成果，學(xué)者們主要從兩個(gè)角度對(duì)屬性約簡(jiǎn)算法進(jìn)行研究：一是，選擇部分樣本進(jìn)行約簡(jiǎn)。文獻(xiàn)[2-5]通過(guò)制定數(shù)據(jù)集提取規(guī)則，選取部分?jǐn)?shù)據(jù)進(jìn)行約簡(jiǎn)，在特定條件下提高了算法約簡(jiǎn)速度。二是，近似表示原始屬性集。文獻(xiàn)[6-8]通過(guò)設(shè)計(jì)定性或定量的計(jì)算標(biāo)準(zhǔn)，近似表示原始數(shù)據(jù)的屬性特征。上述約簡(jiǎn)算法計(jì)算過(guò)程損失了部分?jǐn)?shù)據(jù)或影響數(shù)據(jù)集分布特征，導(dǎo)致約簡(jiǎn)結(jié)果不能準(zhǔn)確地表示屬性間的重要程度，約簡(jiǎn)結(jié)果存在偏差。因此本文在不改變數(shù)據(jù)集結(jié)構(gòu)的前提下，提出一種基于模糊層次商空間的快速屬性約簡(jiǎn)算法（Fuzzy Euclidean Distance-Based Reduction Algorithm，F(xiàn)ED-RA），縮短約簡(jiǎn)時(shí)間，提高算法計(jì)算精度。首先，結(jié)合隸屬函數(shù)與歐氏距離，定義模糊歐氏距離；其次，利用模糊歐氏距離計(jì)算屬性之間的相似程度，并應(yīng)用層次商空間結(jié)構(gòu)構(gòu)建約簡(jiǎn)粒層空間；最后，以粒層空間聚類結(jié)果作為約簡(jiǎn)基礎(chǔ)，實(shí)現(xiàn)樣本集屬性約簡(jiǎn)，并以KEEL 數(shù)據(jù)庫(kù)中的公開(kāi)數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)，驗(yàn)證算法的可行性及有效性。

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

1.1 模糊歐氏距離

經(jīng)典歐式距離主要是通過(guò)計(jì)算樣本間的距離，度量樣本的相似程度。

模糊集用于表示界限或邊界不分明且具有特定性質(zhì)事物的集合。模糊等價(jià)關(guān)系考慮的不是有無(wú)關(guān)系，而是關(guān)系的深淺程度。目前模糊集已被廣泛應(yīng)用到數(shù)據(jù)預(yù)處理中[9-11]。

定義1（模糊集）[12]設(shè)X是論域，X上的一個(gè)模糊集A是指 ?x∈X，有一個(gè)指定的數(shù)μA∈[0,1]，稱為x對(duì)A的隸屬程度，映射μA:X→[0,1],x→μA(x)稱為A的隸屬函數(shù)。

令T(X)表示X上一切模糊子集的集合，則T(X)實(shí)際上是μ:X→[0,1]這個(gè)函數(shù)組成的函數(shù)空間。

定義2（模糊歐氏距離）設(shè)一個(gè)數(shù)據(jù)集中有n個(gè)樣本，μi(m)表示第m個(gè)樣本在屬性i上對(duì)應(yīng)的隸屬度，則定義屬性i、j間的模糊歐氏距離為：

1.2 模糊等價(jià)關(guān)系的層次商空間結(jié)構(gòu)

商空間理論是關(guān)于復(fù)雜問(wèn)題求解的空間關(guān)系理論，其主要內(nèi)容包括復(fù)雜問(wèn)題的商空間描述、商空間的粒度計(jì)算、粒度空間關(guān)系的推理等[13-15]。

定義3[16]設(shè)U是一個(gè)有限域，是U上的一個(gè)模糊等價(jià)關(guān)系，D是的值域。集合稱為的層次商空間結(jié)構(gòu)。

推論1[16]在層次商空間結(jié)構(gòu)中，關(guān)于U上的模糊等價(jià)關(guān)系，如果λ1＞λ2，有

當(dāng)λ增大時(shí)，層次商空間結(jié)構(gòu)中的粒層空間逐漸細(xì)化，因此，以λ為基礎(chǔ)實(shí)現(xiàn)樣本聚類，當(dāng)所有樣本自成一類時(shí)，聚類結(jié)束。

2 模糊層次商空間的快速屬性約簡(jiǎn)算法

2.1 學(xué)術(shù)思想

層次商空間是基于模糊集和商空間的多層知識(shí)空間表示。層次商空間的本質(zhì)是采用模糊集思想將數(shù)據(jù)模糊化處理后，在不同的粒層空間上構(gòu)建層次商空間結(jié)構(gòu)，通過(guò)自底向上的方式描述屬性或樣本之間的等價(jià)關(guān)系，因此，利用層次商空間理論可以對(duì)論域進(jìn)行不同劃分，建立具有層次結(jié)構(gòu)的商空間。然后通過(guò)分析空間中等價(jià)關(guān)系的結(jié)構(gòu)或相關(guān)性，獲取論域中的知識(shí)表示，從而實(shí)現(xiàn)知識(shí)與粒層結(jié)構(gòu)之間的轉(zhuǎn)化。

基于上述分析，層次商空間結(jié)構(gòu)有利于從不同的粒層空間中分析屬性之間的相關(guān)程度。本文提出的快速屬性約簡(jiǎn)算法，采用模糊歐氏距離度量屬性之間的相關(guān)程度，距離越小，屬性相關(guān)程度越高。在層次商空間中，依次從相關(guān)程度較低的粒層空間中剔除屬性，實(shí)現(xiàn)數(shù)據(jù)集的屬性快速約簡(jiǎn)。但目前仍然是依靠專家經(jīng)驗(yàn)選擇隸屬函數(shù)，根據(jù)數(shù)據(jù)結(jié)構(gòu)或分布選取隸屬函數(shù)有利于數(shù)據(jù)模糊化處理及屬性快速約簡(jiǎn)，但也限制了模型的泛化性能。

2.2 算法流程

該算法的流程圖如圖1所示。

圖1 算法流程圖

算法具體計(jì)算步驟如下：

步驟1由于樣本原始屬性值存在量綱不同、取值范圍不同等問(wèn)題，選取柯西分布函數(shù)作為算法的隸屬函數(shù)，對(duì)樣本屬性值模糊化處理。

其中，a是樣本集中各屬性的最小屬性值。

步驟2利用模糊歐氏距離公式（1）計(jì)算屬性間的模糊距離，根據(jù)粒層空間上各屬性的等價(jià)關(guān)系，構(gòu)建模糊關(guān)系矩陣。

步驟3構(gòu)建屬性間的層次商空間結(jié)構(gòu)，根據(jù)層次商空間結(jié)構(gòu)獲得不同等價(jià)屬性的粒層空間Ω1,Ω2,…,Ωn。λ值越小，商空間粒度越細(xì)，空間中包含的屬性等價(jià)類個(gè)數(shù)越多[17]。

步驟4以層次商空間形成的粒層空間作為計(jì)算基礎(chǔ)，選取λ值實(shí)現(xiàn)樣本集的屬性約簡(jiǎn)。

2.3 模型構(gòu)建

在不同粒層空間上，應(yīng)用CART（Classification And Regression Trees）決策樹(shù)建模，分析分類結(jié)果，獲得最佳粒層空間上的屬性約簡(jiǎn)。

步驟1研究不同粒層空間中屬性之間的等價(jià)關(guān)系，選擇λ值獲得不同的粒層空間。

步驟2在不同粒層上，屬性總數(shù)是相同的，但空間中存在不同的屬性等價(jià)類，因此，根據(jù)粒層空間中不同的等價(jià)類實(shí)現(xiàn)屬性快速約簡(jiǎn)。

步驟3用屬性約簡(jiǎn)后的樣本集構(gòu)建CART決策樹(shù)，構(gòu)造過(guò)程如下：

以約簡(jiǎn)后的數(shù)據(jù)子集Di作為模型的數(shù)據(jù)集，構(gòu)建CART 決策樹(shù)，如果樣本個(gè)數(shù)小于閾值或沒(méi)有特征，則返回決策子樹(shù)，當(dāng)前節(jié)點(diǎn)停止遞歸。

根據(jù)式（4）計(jì)算數(shù)據(jù)子集Di的基尼系數(shù)，如果基尼系數(shù)小于閾值，則返回決策子樹(shù)，當(dāng)前節(jié)點(diǎn)停止遞歸。

在分類問(wèn)題中，數(shù)據(jù)集中類別數(shù)目為m，樣本屬于第i類的概率為pi，則該樣本的基尼系數(shù)為[18]：

樣本集S的基尼系數(shù)值為：

其中，|S|表示集合S的總樣本數(shù)，|Di|表示集合S中屬于第i類的樣本數(shù)，基尼指數(shù)表示集合S的不確定性。

如果集合S中，屬性A的值等于a的所有樣本所形成的子集為S1，余下的為S2，則集合S在屬性A的條件下得到的基尼指數(shù)為：

基尼指數(shù)Gini(S,A)表示集合S的不確定性，基尼指數(shù)越大，樣本集的不確定性也越大[19]。

計(jì)算當(dāng)前節(jié)點(diǎn)各特征值對(duì)數(shù)據(jù)子集Di的基尼系數(shù)。

選擇基尼系數(shù)最小的特征A和對(duì)應(yīng)的特征值a，根據(jù)最優(yōu)特征和最優(yōu)特征值，將數(shù)據(jù)子集劃分為兩部分，同時(shí)建立當(dāng)前節(jié)點(diǎn)的左右節(jié)點(diǎn)，對(duì)左右的子節(jié)點(diǎn)遞歸生成決策樹(shù)。

3 實(shí)驗(yàn)仿真與性能分析

3.1 算例示例

本文選取UCI 數(shù)據(jù)集中混凝土抗壓強(qiáng)度的部分?jǐn)?shù)據(jù)進(jìn)行計(jì)算，共選取20個(gè)樣本，原始數(shù)據(jù)表如表1所示，表中決策屬性為壓強(qiáng)，單位為MPa。

表1 樣本原始數(shù)據(jù)表

（1）利用式（1）計(jì)算各屬性間的模糊歐氏距離，建立所有屬性的模糊相似矩陣。

（2）根據(jù)模糊相似矩陣分層遞階結(jié)構(gòu)的聚類算法，得到一個(gè)有序樣本的層次商空間{D(λ) |0 ≤λ≤1} ，不同粒層上的商空間對(duì)應(yīng)不同的屬性聚類結(jié)果，如表2所示。

表2 有序樣本的層次商空間

（3）選取λ值，實(shí)現(xiàn)樣本集屬性約簡(jiǎn)，由于篇幅原因，僅列出選取部分閾值的約簡(jiǎn)結(jié)果。

當(dāng)閾值λ=0.134 時(shí)，冗余屬性是A2、A3，約簡(jiǎn)結(jié)果是A1、A4、A5、A6、A7、A8、A9；

當(dāng)閾值λ=0.132 時(shí)，冗余屬性是A2、A3、A7，約簡(jiǎn)結(jié)果是A1、A4、A5、A6、A8、A9；

當(dāng)閾值λ=0.117 時(shí)，冗余屬性是A1、A6、A2、A3、A7、A8，約簡(jiǎn)結(jié)果是A4、A5、A9。

3.2 仿真系統(tǒng)與數(shù)據(jù)集

基于Python 實(shí)現(xiàn)算法仿真。本文使用來(lái)源于KEEL 數(shù)據(jù)集的15 組具有代表性的數(shù)據(jù)集進(jìn)行對(duì)比仿真實(shí)驗(yàn)，以CART決策樹(shù)為分類工具，構(gòu)建分類模型，驗(yàn)證算法的可行性，數(shù)據(jù)集信息如表3所示。

硬件環(huán)境：CPU，i5-6500；RAM，8 GB。

軟件環(huán)境：操作系統(tǒng)，Windows 10專業(yè)版；解釋器，Python 3.7。

3.3 性能分析

所有數(shù)據(jù)集均按照訓(xùn)練集80%，測(cè)試集20%隨機(jī)劃分。該約簡(jiǎn)算法主要以各粒層空間上屬性的近似程度作為聚類基礎(chǔ)，實(shí)現(xiàn)數(shù)據(jù)集屬性約簡(jiǎn)。由于傳統(tǒng)約簡(jiǎn)算法主要是通過(guò)計(jì)算樣本間的等價(jià)關(guān)系約簡(jiǎn)屬性，當(dāng)數(shù)據(jù)集樣本數(shù)量較大時(shí)，計(jì)算量明顯增大，不利于屬性快速約簡(jiǎn)。與傳統(tǒng)約簡(jiǎn)算法相比，該算法約簡(jiǎn)速度明顯提升，且不受數(shù)據(jù)集中樣本數(shù)量影響，能夠?qū)崿F(xiàn)數(shù)據(jù)集快速約簡(jiǎn)，運(yùn)算時(shí)間優(yōu)勢(shì)明顯。因此在對(duì)比實(shí)驗(yàn)中，以不平衡數(shù)據(jù)集作為實(shí)驗(yàn)樣本集，以SMOTE+TL、ADASYN、XGBOOST 三種算法作為模型框架分別在各約簡(jiǎn)數(shù)據(jù)子集上構(gòu)建分類模型，并分析分類結(jié)果，驗(yàn)證約簡(jiǎn)算法的可行性與準(zhǔn)確性。實(shí)驗(yàn)結(jié)果如圖2 所示。圖中縱坐標(biāo)表示分類模型的G-mean值，橫坐標(biāo)的K表示約簡(jiǎn)輪數(shù)。

表3 數(shù)據(jù)集基本信息

圖2 屬性約簡(jiǎn)后分類模型G-mean值

圖2 （續(xù)）

分析圖2 中各分類模型在約簡(jiǎn)粒層空間上的G-mean值可以看出，在SMOTE+TL、ADASYN、XGBOOST三種學(xué)習(xí)框架下，ecoli3、pima、wisconsin、yeast4、yeast5、yeast6六個(gè)數(shù)據(jù)集的約簡(jiǎn)過(guò)程中，主要剔除的是零值較多或?qū)δＰ头诸愑绊戄^小的屬性，隨著約簡(jiǎn)次數(shù)增多，分類模型精度提升明顯，呈現(xiàn)出明顯的上升趨勢(shì)。在segment0、yeast1、yeast3三個(gè)數(shù)據(jù)集約簡(jiǎn)過(guò)程中，分類模型精度穩(wěn)定，當(dāng)約簡(jiǎn)至核屬性時(shí)，分類模型精度下降明顯，在此類數(shù)據(jù)集中，對(duì)決策屬性影響較大的條件屬性與影響較小的條件屬性之間差異明顯。通過(guò)計(jì)算屬性之間相似程度有利于屬性約簡(jiǎn)，且在約簡(jiǎn)數(shù)據(jù)子集與原數(shù)據(jù)集上分別構(gòu)建分類模型，精度變化較小。因此，對(duì)于此類數(shù)據(jù)更應(yīng)該約簡(jiǎn)后再構(gòu)建分類模型，有利于提升模型精度及運(yùn)算速度。當(dāng)約簡(jiǎn)次數(shù)達(dá)到一定程度時(shí)，分類模型分類精度下降明顯，因此，該點(diǎn)約簡(jiǎn)的剩余屬性即為核屬性。

在 new-thyroid1、page-blocks0、vehicle0、vehicle1、vehicle2、vehicle3六個(gè)數(shù)據(jù)集上，隨著約簡(jiǎn)次數(shù)的增加，分類模型運(yùn)算速度明顯提高，精度有所下降，但精度下降并不明顯，每次約簡(jiǎn)后精度下降2%左右，如果在精度較高的數(shù)據(jù)集上，可以犧牲一部分精度提升分類模型運(yùn)算速度。這些數(shù)據(jù)有一個(gè)共同點(diǎn)，各屬性之間的聯(lián)系密切，條件屬性權(quán)重相差較小，單純使用模糊歐氏距離度量屬性之間的相似程度，不能有效地區(qū)分影響力大小。因此，對(duì)于屬性重要程度相近的數(shù)據(jù)集，可以通過(guò)樣本計(jì)算屬性間的近似程度，從而提升模型分類精度。

4 結(jié)束語(yǔ)

使用屬性作為約簡(jiǎn)基礎(chǔ)可以有效降低約簡(jiǎn)時(shí)間，降低樣本數(shù)量變化對(duì)屬性約簡(jiǎn)結(jié)果的影響。本文結(jié)合模糊歐氏距離及層次商空間理論，通過(guò)構(gòu)建層次粒層空間，在各粒層空間上實(shí)現(xiàn)屬性約簡(jiǎn)。仿真結(jié)果表明，基于模糊層次商空間的快速屬性約簡(jiǎn)算法在保證數(shù)據(jù)完整的前提下，具有更快的約簡(jiǎn)速度，且不受樣本集樣本數(shù)量的影響，具有更高的穩(wěn)定性。該算法在建模過(guò)程中，需要通過(guò)分析數(shù)據(jù)分類結(jié)果才能發(fā)現(xiàn)核屬性，因此，如何自動(dòng)獲取最優(yōu)核屬性并建模是未來(lái)的研究方向。