李元江，權金升，譚陽奕，楊 田

（智能計算與語言信息處理湖南省重點實驗室（湖南師范大學），長沙 410081）

0 引言

隨著數(shù)據(jù)規(guī)模的不斷擴大，尤其是特征數(shù)量的急劇增長，維度災難成為數(shù)據(jù)挖掘和人工智能的共性問題［1］。作為主要的數(shù)據(jù)壓縮方法，屬性約簡能夠根據(jù)某種評估規(guī)則篩選有效的特征，去除冗余特征，從而達到降維數(shù)據(jù)、簡化計算、提高數(shù)據(jù)質(zhì)量和模型泛化能力的目的［2］。

粗糙集［3］為屬性約簡提供了理論框架，在沒有先驗知識的情況下［4-6］，通過知識粒和近似算子計算上下逼近，篩選重要特征，進而制定推理規(guī)則?；诖植诩碚摚瑢W者們設計了一系列屬性約簡算法［7-11］。其中，區(qū)分矩陣［12］是粗糙集理論中的一種屬性約簡方法，它關于特征的復雜度為線性級別，能夠?qū)Ω呔S數(shù)據(jù)進行快速降維［13］。

經(jīng)典的區(qū)分矩陣模型聚焦于異類的樣本，將能否區(qū)分異類的樣本作為評估屬性的標準，好的屬性往往能夠區(qū)分更多的異類樣本對。但是在以往區(qū)分矩陣的研究中，沒有基于同類樣本對屬性形成評價，導致同類樣本的信息沒有得到充分利用。針對這一問題，本文提出了異同矩陣，通過樣本對相似性和差異性的兩方面對屬性形成綜合評估，以充分利用原始數(shù)據(jù)表的信息，使屬性約簡結果更加合理可靠。

1 相關工作

維度災難會降低機器學習模型的性能，導致學習算法失效，降維能將高維的原始數(shù)據(jù)轉(zhuǎn)換為低維數(shù)據(jù)，同時盡可能保留數(shù)據(jù)的原始含義，從而使機器學習模型能夠有效使用這些數(shù)據(jù)。

屬性約簡是降維中的重要方法，在粒計算領域，當前研究主要集中于粗糙集理論及其推廣理論。由Pawlak［3］提出的粗糙集理論是重要的知識?；Ｐ?。粗糙集以等價關系形成知識粒，通過上下逼近劃分正域和邊界，正域為能準確分類的樣本的集合，基于正域的大小制定規(guī)則就能挑選出有效特征，這些規(guī)則包括依賴度［14-15］、信息熵［16-17］、相關族［18］、區(qū)分矩陣［12，19］等。這些方法在知識推理，機器學習，數(shù)據(jù)挖掘等鄰域發(fā)揮著重要的作用［20-23］。

另外，有一些較新穎的屬性約簡思想被提出，包括：Armanfard 等［24］提出了一種局部特征選擇的方法，區(qū)別于經(jīng)典屬性約簡方法為所有樣本生成一個約簡子集，該方法為每個樣本區(qū)域生成一個約簡，從而對后續(xù)的學習更有針對性；Wang 等［25］提出了鄰域自信息的概念，將粗糙集模型中的上近似納入特征的衡量標準，能更加全面地考量特征子集；Zhu等［26］提出了一種多粒度的鄰域粗糙集模型，在此基礎上得到一種自適應特征選擇方法；Yamada 等［27］針對高維生物數(shù)據(jù)提出了一種非線性特征選擇方法；Hu 等［28］將屬性的重疊度引入到k-最近鄰粗糙集中，提高了約簡數(shù)據(jù)的計算效率和分類性能。

以上方法都是基于不同的考量，形成新的屬性約簡的標準，但它們都面臨共同的問題，即對于屬性維度的時間復雜度或空間復雜度較高，算法效率較低。而區(qū)分矩陣算法對于屬性維度的復雜度是線性級別的，因此能夠處理更高維度的數(shù)據(jù)。

當前基于經(jīng)典區(qū)分矩陣模型，結合其他模型，衍生出了一系列新的算法：Hu 等［14］用鄰域關系替換等價關系，以樣本為中心，固定半徑形成鄰域，進而形成上下逼近；Wang 等［29］在鄰域關系的基礎上進行改進，提出了鄰域區(qū)分指數(shù)來衡量特征子集的區(qū)分能力。另一個方面研究則是對經(jīng)典集合進行改變：Dubois 等［30］引入模糊集，形成了模糊粗糙集；Jensen等［31］首次把依賴度應用于模糊粗糙集，提出了新的屬性約簡算法；Chen 等［32］將區(qū)分矩陣的概念應用于模糊粗糙集中。

相較于原始模型，這些新的區(qū)分矩陣模型作出了基于鄰域形成覆蓋關系替代劃分關系以及用模糊關系替代經(jīng)典集合關系等改進，旨在更加充分地利用數(shù)據(jù)信息，其中覆蓋關系能夠處理連續(xù)數(shù)據(jù)，模糊關系生成的信息粒能包含更多信息。但經(jīng)典區(qū)分矩陣及其衍生模型都沒有完全充分利用樣本信息，均只使用不同類別的樣本信息對屬性進行評價，并沒有使用到大量的同類樣本信息。

因此，為了更加充分地挖掘數(shù)據(jù)信息，異同矩陣的概念被提出。異同矩陣將同類樣本相似度納入對屬性的衡量，形成同類相似度和異類差異度兩個方面的評價?；跇颖緦υ诿總€屬性下的距離以及類別標簽計算同類相似度和異類差異度，進而將所有樣本對的信息形成異同矩陣，并提出相應的屬性重要度對屬性進行評價，通過啟發(fā)式屬性約簡算法挑選出重要屬性，去除冗余屬性，完成屬性約簡。

2 基本概念

2.1 粗糙集

定義1［3］不可區(qū)分關系。設R是U上的一個等價關系，U/R表示R的所有等價類構成的集合，[x]R表示包含元素x∈U的R等價類。一個知識庫就是一個關系系統(tǒng)K=(U，R)，其中U為非空有限集，稱為論域，R是U上的一族等價關系。若P?R，且∩P也是一個等價關系，稱為P上的不可區(qū)分（indiscernibility）關系，記為ind(P)。

定義2［3］上近似與下近似。給定知識庫K=(U，R)，對于任意子集X?U和一個等價關系R∈ind(K)，則

基于依賴度和信息熵等方法的屬性約簡方法關于特征的復雜度高，難以處理高維數(shù)據(jù)。區(qū)分矩陣對于特征的復雜度較低，可快速約簡高維數(shù)據(jù)。

2.2 區(qū)分矩陣

定義3［12］設I=(U，A，V，f)是一個知識表達系統(tǒng)，|U|=n，則I的區(qū)分矩陣為：

其中βij={a∈A|f(xi，a) ≠f(xj，a)}。

區(qū)分矩陣是一個n×n的對稱矩陣，矩陣的每個元素記錄了能夠區(qū)分兩個樣本的屬性集合。

定義3 中的區(qū)分矩陣存在兩個問題：1）對于同類樣本可能依然會進行區(qū)分，實際上與決策相關性更強的特征應該較少地區(qū)分同類樣本對；2）在處理連續(xù)型數(shù)據(jù)時，將兩個樣本值是否相等作為區(qū)分標準太過嚴苛，相當于?；教?，會導致模型出現(xiàn)過擬合的情況。

3 異同矩陣及屬性約簡

3.1 異同矩陣的基本概念

對于上述問題，文獻［33］中提出了針對連續(xù)型數(shù)據(jù)的區(qū)分矩陣方法，將連續(xù)值的差值是否超過一個閾值作為區(qū)分標準，使第2）個問題得到了合理解決，但并沒有解決第1）個問題。不考慮同類樣本的情況，使這部分數(shù)據(jù)信息沒有被利用，極有可能影響最終的分類效果。本文從樣本對的相似性和差異性兩方面對屬性形成綜合評估，提出異同矩陣以解決第1）個問題。

定義4異同矩陣。設I=(U，A，V，f)是一個知識表達系統(tǒng)，|U|=n，|A|=m，ak(xi)表示xi在屬性ak下的屬性值。則I的異同矩陣為：

其中：(xi，xj)為不同類別的樣本差異度；Sak(xi，xj)為相同類別樣本的同類相似度；|·|表示取絕對值；γ1、γ2分別為差異度和相似度閾值。

從定義4 可以看出異同矩陣是一個對稱矩陣，因此計算矩陣時只需要計算一半即可。該異同矩陣的每個元素是一個1 ×m的列表，列表的每個數(shù)值相當于對屬性進行評價，對于不同類別的樣本，某屬性下的樣本值差距大于閾值，說明該屬性能很好地區(qū)分它們，則記為1；否則不能區(qū)分，記為0。對于相同類別的樣本，某屬性下的樣本值差距小于閾值，說明該屬性不會錯誤地區(qū)分它們，因此記為1；否則記為0。

定理1對于定義4 中的異同矩陣，當同類相似度閾值取值為0，異類差異度閾值取值為0 時，異同矩陣變化為區(qū)分矩陣。

證 明 當γ1=0，γ2=0 時，對于任 意xi，xj，ak，如 果d(xi)=d(xj)，則(xi，xj)=0。如 果d(xi) ≠d(xj)，當ak(xi)=ak(xj) 時，(xi，xj)=0；當ak(xi) ≠ak(xj) 時，(xi，xj)=1。將定義4 中αij值為1 的位置對應的屬性形成集合，即為定義3 中βij，此時，異同矩陣變換為區(qū)分矩陣。

根據(jù)定理1 可知，異同矩陣是對區(qū)分矩陣的推廣，因此異同矩陣在優(yōu)化區(qū)分矩陣的基礎上保留了區(qū)分矩陣的良好性質(zhì)。

基于異同矩陣，定義5 給出了屬性重要度評估方法。

定義5屬性重要度。設I=(U，A，V，f)是一個知識表達系統(tǒng)，|U|=n，|A|=m，ak(xi)表示xi在屬性ak下的屬性值。SDM為S的異同矩陣，則屬性ak的屬性重要度為：SIG(ak)=(ak)，其中αij(ak)表示αij的第k個值。

根據(jù)屬性重要度，本文在3.2 節(jié)中設計了啟發(fā)式屬性約簡算法。

3.2 基于異同矩陣的屬性約簡算法

基于異同矩陣的約簡算法可以分為兩步：第一步為建立異同矩陣，根據(jù)給定的閾值和定義4 遍歷一半的樣本對，建立異同矩陣；第二步為約簡，根據(jù)第一步建立的異同矩陣，計算每個屬性的屬性重要度，選取屬性重要度最大的特征ak進入約簡，并將αij(ak)=1 的αij設置為(0，0，…，0)，每輪選擇當前未被選擇的屬性直到所有αij都為(0，0，…，0)。對于算法的時間復雜度，假設樣本數(shù)為n，特征數(shù)為m，算法的第一步要遍歷一半的樣本對，因此要進行(n(n-1))m次計算，時間復雜度為O(n2m)；第二步基于矩陣的運算復雜度是常數(shù)級別。因此，ARSDM 算法的時間度為O(n2m)。由于要基于每個屬性存儲樣本對的信息，因此空間復雜度為O(mn2)。具體算法如下：

算法1 異同矩陣約簡算法。

第一步：建立異同矩陣。

4 實驗與結果分析

4.1 實驗設置

實驗數(shù)據(jù)集來自UCI 和scikit-feature 數(shù)據(jù)庫，具體信息如表1 所示。對Fitting Fuzzy Rough Sets（FFRS）［34］、Granular Ball Neighborhood Rough Sets（GBNRS）［35］和Discernibility Matrix based on Graph theory（DMG）［36］三種屬性約簡算法進行對比，其中DMG 算法是區(qū)分矩陣算法的最新改進版本。對于屬性約簡結果，通過分類回歸樹（Classification And Regression Tree，CART）分類器和支持向量機（Support Vector Machine，SVM）分類器進行十折交叉驗證，得到的結果為10次結果的平均值。

表1 數(shù)據(jù)集信息Tab.1 Dataset information

對于FFRS 和DMG，為了得到更好的結果，本文將δ設置為從0 到0.5 并以0.02 為步長進行遍歷，因此會得到26 個結果，最終選取分類準確率最高的結果。GBNRS 算法運行不需要設置參數(shù)，但是GBNRS 的結果具有較大隨機性，因此本文設置運行5 次，取最大準確率。同時，ARSDM 也對閾值γ1從0 到0.5 以0.02 為步長進行遍歷，對閾值γ2=0.2γ1從0到0.1 以0.004 為步長進行遍歷。ARSDM 也會得到26 個結果，選取分類準確率最高的結果作為最終約簡。4 個對比算法的時間復雜度與空間復雜度如表2 所示。

表2 時間/空間復雜度對比Tab.2 Comparison of time/space complexity

本文實驗均在同一環(huán)境下進行，使用Matlab R2018b 進行代碼編寫，在個人電腦上運行。個人電腦的系統(tǒng)為Windows 10，處理器是Intel Core i5-8250U CPU @ 1.60 GHz，內(nèi)存是32.0 GB。

4.2 結果分析

原始數(shù)據(jù)（RAW）和4 個算法（DMG、FFRS、GBNRS 和ARSDM）在CART 和SVM 分類器上的約簡數(shù)據(jù)的分類準確率分別如表3 和表4 所示，每個數(shù)據(jù)集的最大分類準確率用加粗字體表示。圖1 和圖2 分別展示了CART 和SVM 在不同數(shù)據(jù)集上的準確率變化。

表3 CART分類器上約簡數(shù)據(jù)的分類準確率比較 單位：%Tab.3 Comparison of classification accuracy on reduction data under CART classifier unit：%

表4 SVM分類器下約簡數(shù)據(jù)的分類準確率比較 單位：%Tab.4 Comparison of classification accuracy on reduction data under SVM classifier unit：%

表3、4 的結果表明，經(jīng)過ARSDM 算法約簡的數(shù)據(jù)分類準確率比原始數(shù)據(jù)高，說明ARSDM 在減小數(shù)據(jù)規(guī)模的同時，保證了約簡數(shù)據(jù)的質(zhì)量。對比另外三個算法的約簡結果，在CART 分類器的評估下，ARSDM 對于數(shù)據(jù)集SCADI、Allaml、Lung、Biodeg、Pageblock、Cane 的分類準確率更高；在SVM 分類器的 評估下，對于數(shù)據(jù)集Sonar、SCADI、Heart、Lung、GLI85、Biodeg、ORL、Messidor、Cane 的分類 準確率更高。ARSDM 在兩個分類器下的平均分類準確率均最高，其中，對比DMG、FFRS 以及GBNRS，在CART 分類器下的平均分類準確率分別提高1.07，6.48，8.92 個百分點；在SVM 分類器下的平均分類準確率分別提高1.96，11.96，12.39 個百分點。這說明對比只考慮樣本差異度的DMG，加入樣本相似度后的ARSDM 能夠篩選出質(zhì)量更高的屬性進而提高分類準確率。而且對比經(jīng)典的屬性約簡方法，ARSDM 對數(shù)據(jù)集的考察更全面，能夠利用更多的信息，分類準確率較為穩(wěn)定，有良好的魯棒性。

表5 展示了4 個算法對不同數(shù)據(jù)集的約簡時間，由于DMG、FFRS、ARSDM 需要針對26 個鄰域參數(shù)計算26 次，以選擇最好的結果，因此，約簡時間是26 次計算的總時間。GBNRS 需要運行5 次選取最好結果，所以約簡時間是5 次約簡時間總和。從表5 中可以看出，對比DMG，ARSDM 平均運行時間更長，因為ARSDM 要額外計算樣本相似度；對比FFRS 和GBNRS，ARSDM 平均運行時間更短；此外，對于高維數(shù)據(jù)，ARSDM 運行效率更有優(yōu)勢，例如GLI85；而對于樣本數(shù)量大維度低的數(shù)據(jù)，ARSDM 運行效率較低，例如Pageblock。結合分類準確率結果，這說明ARSDM 更適合處理高維數(shù)據(jù)，能在對高維數(shù)據(jù)有效較低維度的同時保證較高效率。

表5 四個算法的約簡時間對比 單位：sTable 5 Comparison of reduction time of four algorithms unit：s

5 結語

本文基于粗糙集理論對區(qū)分矩陣模型進行了優(yōu)化，由于以往研究只考慮了不同類別的樣本，形成的評價不夠全面，因此，本文從相似和差異兩個方面，加入了對同類樣本相似性的衡量，提出了異同矩陣。在異同矩陣的基礎上，提出了屬性約簡啟發(fā)式算法ARSDM。在數(shù)值實驗中，將ARSDM 算法與FFRS、DMG、GBNRS 約簡結果對比，用CART 和SVM 分類器對結果進行評估。結果表明，ARSDM 能在原始數(shù)據(jù)上有效去除冗余屬性，對比其他約簡算法的結果，在多數(shù)數(shù)據(jù)集上分類準確率有明顯提高。

ARSDM 算法在樣本數(shù)量較多時的約簡速度較慢。因此，后續(xù)的研究工作主要是兩個方面：1）對ARSDM 算法進行優(yōu)化，提高運行速度，處理維度更高的數(shù)據(jù)；2）將ARSDM 算法應用到增量學習中，使其能夠處理動態(tài)數(shù)據(jù)。