模糊層次商空間的快速屬性約簡算法

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

1.華北理工大學 理學院，河北 唐山 063210

2.河北省數據科學與應用重點實驗室，河北 唐山 063210

3.唐山市數據科學重點實驗室，河北 唐山 063210

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

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

1 基礎知識

1.1 模糊歐氏距離

經典歐式距離主要是通過計算樣本間的距離，度量樣本的相似程度。

模糊集用于表示界限或邊界不分明且具有特定性質事物的集合。模糊等價關系考慮的不是有無關系，而是關系的深淺程度。目前模糊集已被廣泛應用到數據預處理中[9-11]。

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

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

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

1.2 模糊等價關系的層次商空間結構

商空間理論是關于復雜問題求解的空間關系理論，其主要內容包括復雜問題的商空間描述、商空間的粒度計算、粒度空間關系的推理等[13-15]。

定義3[16]設U是一個有限域，是U上的一個模糊等價關系，D是的值域。集合稱為的層次商空間結構。

推論1[16]在層次商空間結構中，關于U上的模糊等價關系，如果λ1＞λ2，有

當λ增大時，層次商空間結構中的粒層空間逐漸細化，因此，以λ為基礎實現樣本聚類，當所有樣本自成一類時，聚類結束。

2 模糊層次商空間的快速屬性約簡算法

2.1 學術思想

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

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

2.2 算法流程

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

圖1 算法流程圖

算法具體計算步驟如下：

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

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

步驟2利用模糊歐氏距離公式（1）計算屬性間的模糊距離，根據粒層空間上各屬性的等價關系，構建模糊關系矩陣。

步驟3構建屬性間的層次商空間結構，根據層次商空間結構獲得不同等價屬性的粒層空間Ω1,Ω2,…,Ωn。λ值越小，商空間粒度越細，空間中包含的屬性等價類個數越多[17]。

步驟4以層次商空間形成的粒層空間作為計算基礎，選取λ值實現樣本集的屬性約簡。

2.3 模型構建

在不同粒層空間上，應用CART（Classification And Regression Trees）決策樹建模，分析分類結果，獲得最佳粒層空間上的屬性約簡。

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

步驟2在不同粒層上，屬性總數是相同的，但空間中存在不同的屬性等價類，因此，根據粒層空間中不同的等價類實現屬性快速約簡。

步驟3用屬性約簡后的樣本集構建CART決策樹，構造過程如下：

以約簡后的數據子集Di作為模型的數據集，構建CART 決策樹，如果樣本個數小于閾值或沒有特征，則返回決策子樹，當前節點停止遞歸。

根據式（4）計算數據子集Di的基尼系數，如果基尼系數小于閾值，則返回決策子樹，當前節點停止遞歸。

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

樣本集S的基尼系數值為：

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

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

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

計算當前節點各特征值對數據子集Di的基尼系數。

選擇基尼系數最小的特征A和對應的特征值a，根據最優特征和最優特征值，將數據子集劃分為兩部分，同時建立當前節點的左右節點，對左右的子節點遞歸生成決策樹。

3 實驗仿真與性能分析

3.1 算例示例

本文選取UCI 數據集中混凝土抗壓強度的部分數據進行計算，共選取20個樣本，原始數據表如表1所示，表中決策屬性為壓強，單位為MPa。

表1 樣本原始數據表

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

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

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

（3）選取λ值，實現樣本集屬性約簡，由于篇幅原因，僅列出選取部分閾值的約簡結果。

當閾值λ=0.134 時，冗余屬性是A2、A3，約簡結果是A1、A4、A5、A6、A7、A8、A9；

當閾值λ=0.132 時，冗余屬性是A2、A3、A7，約簡結果是A1、A4、A5、A6、A8、A9；

當閾值λ=0.117 時，冗余屬性是A1、A6、A2、A3、A7、A8，約簡結果是A4、A5、A9。

3.2 仿真系統與數據集

基于Python 實現算法仿真。本文使用來源于KEEL 數據集的15 組具有代表性的數據集進行對比仿真實驗，以CART決策樹為分類工具，構建分類模型，驗證算法的可行性，數據集信息如表3所示。

硬件環境：CPU，i5-6500；RAM，8 GB。

軟件環境：操作系統，Windows 10專業版；解釋器，Python 3.7。

3.3 性能分析

所有數據集均按照訓練集80%，測試集20%隨機劃分。該約簡算法主要以各粒層空間上屬性的近似程度作為聚類基礎，實現數據集屬性約簡。由于傳統約簡算法主要是通過計算樣本間的等價關系約簡屬性，當數據集樣本數量較大時，計算量明顯增大，不利于屬性快速約簡。與傳統約簡算法相比，該算法約簡速度明顯提升，且不受數據集中樣本數量影響，能夠實現數據集快速約簡，運算時間優勢明顯。因此在對比實驗中，以不平衡數據集作為實驗樣本集，以SMOTE+TL、ADASYN、XGBOOST 三種算法作為模型框架分別在各約簡數據子集上構建分類模型，并分析分類結果，驗證約簡算法的可行性與準確性。實驗結果如圖2 所示。圖中縱坐標表示分類模型的G-mean值，橫坐標的K表示約簡輪數。

表3 數據集基本信息

圖2 屬性約簡后分類模型G-mean值

圖2 （續）

分析圖2 中各分類模型在約簡粒層空間上的G-mean值可以看出，在SMOTE+TL、ADASYN、XGBOOST三種學習框架下，ecoli3、pima、wisconsin、yeast4、yeast5、yeast6六個數據集的約簡過程中，主要剔除的是零值較多或對模型分類影響較小的屬性，隨著約簡次數增多，分類模型精度提升明顯，呈現出明顯的上升趨勢。在segment0、yeast1、yeast3三個數據集約簡過程中，分類模型精度穩定，當約簡至核屬性時，分類模型精度下降明顯，在此類數據集中，對決策屬性影響較大的條件屬性與影響較小的條件屬性之間差異明顯。通過計算屬性之間相似程度有利于屬性約簡，且在約簡數據子集與原數據集上分別構建分類模型，精度變化較小。因此，對于此類數據更應該約簡后再構建分類模型，有利于提升模型精度及運算速度。當約簡次數達到一定程度時，分類模型分類精度下降明顯，因此，該點約簡的剩余屬性即為核屬性。

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

4 結束語

使用屬性作為約簡基礎可以有效降低約簡時間，降低樣本數量變化對屬性約簡結果的影響。本文結合模糊歐氏距離及層次商空間理論，通過構建層次粒層空間，在各粒層空間上實現屬性約簡。仿真結果表明，基于模糊層次商空間的快速屬性約簡算法在保證數據完整的前提下，具有更快的約簡速度，且不受樣本集樣本數量的影響，具有更高的穩定性。該算法在建模過程中，需要通過分析數據分類結果才能發現核屬性，因此，如何自動獲取最優核屬性并建模是未來的研究方向。