基于相似和差異雙視角的高維數(shù)據(jù)屬性約簡(jiǎn)

李元江，權(quán)金升，譚陽(yáng)奕，楊 田

（智能計(jì)算與語(yǔ)言信息處理湖南省重點(diǎn)實(shí)驗(yàn)室（湖南師范大學(xué)），長(zhǎng)沙 410081）

0 引言

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

粗糙集［3］為屬性約簡(jiǎn)提供了理論框架，在沒(méi)有先驗(yàn)知識(shí)的情況下［4-6］，通過(guò)知識(shí)粒和近似算子計(jì)算上下逼近，篩選重要特征，進(jìn)而制定推理規(guī)則。基于粗糙集理論，學(xué)者們?cè)O(shè)計(jì)了一系列屬性約簡(jiǎn)算法［7-11］。其中，區(qū)分矩陣［12］是粗糙集理論中的一種屬性約簡(jiǎn)方法，它關(guān)于特征的復(fù)雜度為線性級(jí)別，能夠?qū)Ω呔S數(shù)據(jù)進(jìn)行快速降維［13］。

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

1 相關(guān)工作

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

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

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

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

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

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

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

2 基本概念

2.1 粗糙集

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

定義2［3］上近似與下近似。給定知識(shí)庫(kù)K=(U，R)，對(duì)于任意子集X?U和一個(gè)等價(jià)關(guān)系R∈ind(K)，則

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

2.2 區(qū)分矩陣

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

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

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

定義3 中的區(qū)分矩陣存在兩個(gè)問(wèn)題：1）對(duì)于同類樣本可能依然會(huì)進(jìn)行區(qū)分，實(shí)際上與決策相關(guān)性更強(qiáng)的特征應(yīng)該較少地區(qū)分同類樣本對(duì)；2）在處理連續(xù)型數(shù)據(jù)時(shí)，將兩個(gè)樣本值是否相等作為區(qū)分標(biāo)準(zhǔn)太過(guò)嚴(yán)苛，相當(dāng)于粒化水平太細(xì)，會(huì)導(dǎo)致模型出現(xiàn)過(guò)擬合的情況。

3 異同矩陣及屬性約簡(jiǎn)

3.1 異同矩陣的基本概念

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

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

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

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

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

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

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

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

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

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

3.2 基于異同矩陣的屬性約簡(jiǎn)算法

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

算法1 異同矩陣約簡(jiǎn)算法。

第一步：建立異同矩陣。

4 實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)置

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

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

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

表2 時(shí)間/空間復(fù)雜度對(duì)比Tab.2 Comparison of time/space complexity

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

4.2 結(jié)果分析

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

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

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

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

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

表5 四個(gè)算法的約簡(jiǎn)時(shí)間對(duì)比 單位：sTable 5 Comparison of reduction time of four algorithms unit：s

5 結(jié)語(yǔ)

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

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