陳中華，巴 婧，徐泰華 ，王平心，楊習(xí)貝

1(江蘇科技大學(xué) 計算機學(xué)院，江蘇 鎮(zhèn)江 212100) 2(江蘇科技大學(xué) 理學(xué)院，江蘇 鎮(zhèn)江 212100)

1 引 言

在粗糙集[1-3]研究領(lǐng)域內(nèi)，屬性約簡[4-8]一直是一個熱點話題.作為一種數(shù)據(jù)預(yù)處理技術(shù)，屬性約簡的核心思想是利用不確定性度量函數(shù)對屬性進行評估，篩選并刪除條件屬性集中的冗余屬性，從而達到降低數(shù)據(jù)維度并提升學(xué)習(xí)器泛化性能的目的.

正由于屬性約簡所具有的諸多優(yōu)勢，因此如何提升約簡求解的效率，已然受到眾多學(xué)者的廣泛關(guān)注[9-12].近年來，已有諸多學(xué)者對經(jīng)典粗糙集[13]進行了拓展和豐富[14-17]，提出了新的粗糙集模型，并對相關(guān)的約簡求解問題進行了研究.例如，Hu等人[14]設(shè)計了基于鄰域粗糙集的前向貪心約簡求解算法，受到了領(lǐng)域內(nèi)諸多學(xué)者的關(guān)注與認可.

傳統(tǒng)的鄰域粗糙集模型通過引入鄰域關(guān)系的概念，可以靈活地使用鄰域半徑判別論域中的兩個樣本相似與否.然而，傳統(tǒng)的鄰域粗糙集模型往往需要通過采用網(wǎng)格化搜索或嘗試策略，找尋出符合問題求解的鄰域半徑，這必然會導(dǎo)致與鄰域粗糙集相關(guān)的問題求解方法在時間效率上存在缺陷.

為了克服這一缺陷，已有學(xué)者借鑒自適應(yīng)理念，提出了一些能夠無參數(shù)地決定鄰域半徑大小的策略.例如，Zhou等人[18]針對在線流特征選擇問題，提出了Gap鄰域的概念，該鄰域的大小由數(shù)據(jù)中樣本間距離的差值自動地確定；Xia等人[19]為提升基于粒計算的分類器的性能，提出了粒球[19-21]的概念，其生成過程是迭代地使用2-means聚類，依據(jù)數(shù)據(jù)自身的分布自動地生成大小不一的粒球，直至粒球的純度達到給定的閾值，粒球的純度實際上就是粒球中那些樣本標簽與粒球標簽一致的樣本的比重.

基于粒球的概念，Xia等人[21]還提出了粒球粗糙集模型，并基于該模型探索了屬性約簡的相關(guān)問題.相較Hu[14]等人提出的鄰域粗糙集下的約簡求解算法，面向粒球粗糙集的約簡求解算法顯著地提升了時間效率.然而，在這一過程中，筆者發(fā)現(xiàn)粒球的生成過程占據(jù)了大部分的時間消耗，因此如若能提高粒球的生成效率，則可帶來約簡求解時間效率的總體提升.鑒于此，筆者將偽標簽策略引入到粒球的生成過程中，以期粒球的內(nèi)部更加聚集，減少真實標簽所帶來的不一致情形，從而達到提高粒球的產(chǎn)生效率及快速獲得約簡的目的.

2 基礎(chǔ)知識

2.1 粒球粗糙集

形式化地，決策系統(tǒng)可以表示為一個二元組DS=，其中U為非空有限的樣本集合，稱為論域；AT為非空有限的條件屬性集合，d為決策屬性.?xi∈U，d(xi)為樣本xi的標簽，因而U/IND(a0sqo0k)={X1，X2，…，Xn}表示根據(jù)決策屬性d在論域U上所誘導(dǎo)出的一個劃分.?Xp(U/IND(gqc00wo)，Xp表示具有相同標簽的樣本構(gòu)成的第p個決策類.

Xia等人[21]提出的粒球的概念，在信息?；倪M程中能夠依據(jù)球內(nèi)數(shù)據(jù)的分布，自適應(yīng)地生成信息粒.相較以往的鄰域粗糙集而言，粒球方法具有更高的靈活性，并且無需半徑尋優(yōu)這一耗時的過程.一般來說，粒球的主要結(jié)構(gòu)包括球心和半徑，其詳細定義如定義1所示.

定義1.給定一個決策系統(tǒng)DS，?A?AT，在論域U上依據(jù)條件屬性集A，可以誘導(dǎo)生成一個以C為球心，r為半徑的粒球GBs(GBs?U)，即：

(1)

(2)

其中，球心C為GBs中所有樣本點的重心，半徑r為GBs中所有樣本點到C的距離的均值，|GBs|表示GBs中樣本的個數(shù).

(3)

在Xia等人[21]所提出的粒球的生成過程中，初始時將論域U視作一個粒球，然后對每個粒球迭代地使用2-means聚類，用以對每個粒球進行分解，直至每個新生成的粒球的純度均達到給定閾值.其主要步驟如下所示：

1)假設(shè)n表示現(xiàn)有粒球的數(shù)量，將論域U視為一個初始粒球，此時n的值為1;

2)利用2-means算法分別對現(xiàn)有的每個粒球進行聚類，使得原來的每個粒球分別分裂成兩個更小的粒球，則現(xiàn)有的粒球數(shù)量為n·2;

3)求得現(xiàn)有每個粒球的純度；

4)遍歷所有現(xiàn)有的粒球，若每個粒球的純度均不低于給定的閾值，則算法結(jié)束；否則返回步驟2).

由上述粒球的概念，不難得到粒球粗糙集的定義，如定義4所示.

定義4.給定一個決策系統(tǒng)DS，?A?AT，?Xp∈U/IND(d)，根據(jù)條件屬性集A，Xp的粒球上、下近似集分別定義為：

(4)

(5)

2.2 屬性約簡

作為基于粗糙集理論的特征選擇方法，屬性約簡在諸多研究領(lǐng)域已然受到了相關(guān)學(xué)者的廣泛關(guān)注.一般來說，屬性約簡的目的是獲取滿足給定約束條件的極小屬性子集，并以此來降低數(shù)據(jù)維度、提高學(xué)習(xí)模型的泛化能力.形式化地，屬性約簡的一般定義如定義5所示.

定義5.給定一個決策系統(tǒng)DS，Cρ是與給定的一個度量ρ相關(guān)的約束條件，?red?AT，red為AT的一個約簡當且僅當：

1)red滿足Cρ.

2)?red′?red，red′不滿足Cρ.

其中度量ρ可被描述為一個函數(shù)，形如： 2U×2AT→R，R是所有實數(shù)的合集.

在定義5中，不難發(fā)現(xiàn)red實際是一個滿足給定約束條件的極小屬性子集，其中:1)能夠保證相較于原始屬性集，約簡中的屬性能夠滿足指定的約束條件；2)保證了約簡的極小性.

在粗糙集領(lǐng)域現(xiàn)有的諸多研究成果中，度量ρ可以使用不同的方式進行計算.例如，在經(jīng)典粗糙集方法中，度量ρ可以使用近似質(zhì)量來計算，約束條件Cρ就表示等價類的近似質(zhì)量；而在Xia等人[21]提出的粒球粗糙集方法中，此時可以采用粒球的純度作為度量ρ的計算方式，Cρ則表示原始數(shù)據(jù)上的粒球的純度.

3 屬性約簡加速方法

3.1 偽標簽粒球粗糙集

由2.1節(jié)可知，當粒球中存在較多與粒球標簽相異的樣本時，該粒球便不斷分裂以生成新的粒球，直至每個粒球的純度都達到給定的閾值，隨著迭代次數(shù)的增多，這個過程耗時巨大，因此勢必也會為約簡的求解帶來顯式的時間增長.為解決這一問題，本節(jié)將從提高粒球生成的效率這一層面出發(fā)，考慮粒球的新型生成方式，進而進行屬性約簡方面的探究.

在Xia等人[21]提出的粒球粗糙集中，粒球的生成過程是一個無監(jiān)督的進程，雖然樣本的標簽并未參與到生成粒球這一過程中，但樣本的標簽信息卻被用來計算粒球的純度，并依據(jù)計算結(jié)果來判定是否繼續(xù)分裂粒球.由此不難看出，當數(shù)據(jù)中存在較多不一致情形時，獲得高純度的粒球可能較為困難，這便直接影響到后續(xù)進行約簡求解的時間效率.

樣本的偽標簽也可以采用無監(jiān)督的模式進行獲取[15].偽標簽可以使得數(shù)據(jù)中樣本分布的刻畫更為聚集.考慮到這一優(yōu)勢，筆者在本節(jié)中將偽標簽策略引入粒球的生成過程中，旨在減少不一致情形，提高粒球的生成效率.

在數(shù)據(jù)中引入樣本的偽標簽后，需進一步對Xia等人[21]提出的粒球粗糙集中相關(guān)概念重新進行定義，詳細描述如定義6所示.

(6)

在偽標簽粒球的生成過程中，首先根據(jù)條件屬性集AT獲取樣本的偽標簽，偽標簽的數(shù)目與原始數(shù)據(jù)中原標簽的數(shù)目相等，并使用獲取的偽標簽對數(shù)據(jù)原標簽進行更新；其次，將論域U視作一個偽標簽粒球，然后對每個偽標簽粒球迭代地使用2-means聚類，用以對每個偽標簽粒球進行分解，直至每個新生成的偽標簽粒球的純度均達到給定的閾值.詳細的算法流程如算法1所示.

算法1.偽標簽粒球生成算法

輸入：DS=;

步驟1.根據(jù)條件屬性集AT獲取樣本的偽標簽，并使用獲取的偽標簽更新數(shù)據(jù)的原標簽;

步驟4.Repeat

1)使用2-means分解偽標簽粒球；

2)求得每個偽標簽粒球的純度；

Until每個偽標簽粒球的純度均不低于給定的閾值；

根據(jù)上述偽標簽粒球的概念，不難得到偽標簽粒球粗糙集的定義，如定義8所示.

(7)

(8)

3.2 快速約簡求解算法

在3.1節(jié)中，筆者給出了偽標簽粒球粗糙集的相關(guān)定義，本節(jié)中筆者將利用偽標簽粒球粗糙集，設(shè)計前向貪心搜索算法，用于求解基于偽標簽粒球粗糙集的約簡，具體的算法描述如算法2所示.

算法2.快速約簡求解算法

輸入：DS=，約束條件Cρ;

輸出：約簡red;

步驟2.令red=?;

步驟3.Whilered不滿足約束條件Cρdo

3)挑選出合適的屬性，形如b=arg

4)red=red∪;

End

步驟4.Repeat

2)Ifred滿足約束條件Cρ

red=red-{a};

End

Untilred不再發(fā)生變化或|red|=1;

步驟5.輸出red.

4 實驗分析

為了驗證所提算法的有效性，在本節(jié)中，筆者選取了12組基準數(shù)據(jù)集進行相關(guān)的實驗對比分析，數(shù)據(jù)的具體描述見表1.

表1 數(shù)據(jù)集描述Table 1 Data sets description

4.1 粒球生成的時間消耗對比

在本節(jié)實驗中，將針對Xia等人[21]提出的粒球生成算法及筆者提出的偽標簽粒球生成算法，進行時間消耗的對比分析，最終采集的時間消耗為兩種方法分別求解1000次粒球所需時間的均值，具體結(jié)果如表2所示.

表2 兩種算法生成粒球的時間消耗(秒)

觀察表2，不難得出如下結(jié)論：在多數(shù)數(shù)據(jù)上，使用偽標簽粒球生成算法所需的時間消耗要低于Xia等人[21]提出的粒球生成算法所需的時間消耗.這說明，在數(shù)據(jù)中引入偽標簽策略，可以有效地提升粒球生成的效率.

4.2 約簡求解的時間消耗對比

在文獻[21]中，Xia等人[21]不僅提出了粒球粗糙集模型，還針對屬性約簡的求解問題進行了研究，并設(shè)計了基于后向貪心的約簡求解算法.但文獻[22]指出，針對高維數(shù)據(jù)，采用該方法進行約簡求解時，在剔除屬性的過程中，將會產(chǎn)生巨大的時間消耗.鑒于此，文獻[22]提出了基于粒球粗糙集的前向貪心約簡求解方法.

此外，值得注意的是，粒球粗糙集是一種自適應(yīng)生成鄰域信息粒的技術(shù)，因此筆者還將粒球粗糙集的約簡求解與Gap鄰域粗糙集[18]的約簡求解進行了對比，這主要是因為Gap鄰域也是一種具有清晰語義解釋的自適應(yīng)生成信息粒的方法.

除此之外，筆者還挑選了傳統(tǒng)的基于半徑設(shè)置的鄰域信息粒生成方法，進行約簡求解.其中，對于鄰域粗糙集的半徑選擇問題，文中選取了0.02，0.04，…，0.40等20個不同半徑，步長為0.02.

在本節(jié)實驗中，對文獻[18]算法、文獻[22]算法、筆者在文中所提算法2以及鄰域粗糙集約簡求解的時間消耗進行統(tǒng)計，如表3所示.

表3 不同算法求解約簡的時間消耗對比(秒)Table 3 Time consumptions of different algorithms for deriving reducts(Seconds)

觀察表3，不難得出如下結(jié)論.

1)利用傳統(tǒng)鄰域粗糙集方法，進行約簡求解所需的時間消耗顯著高于其他3種算法所需的時間消耗.以數(shù)據(jù)Forest Fires為例，在運用鄰域粗糙集方法進行約簡求解時，所需的時間為1.5532秒，而利用文獻[18]算法、文獻[22]算法和筆者所提出的算法2進行約簡求解，所需的時間消耗分別為1.0903秒、0.7647秒和0.5979秒.由此可見，相較于設(shè)置半徑的方法來說，自適應(yīng)確定鄰域信息粒的方法的確能夠在約簡求解時帶來較大的時間優(yōu)勢.

2)在進行約簡求解時，文獻[22]算法所需的時間消耗要比文獻[18]算法的低，雖然它們都是數(shù)據(jù)自適應(yīng)的方法，但是Gap方法需要逐個求出樣本間距離，并對樣本間的距離從近到遠進行排序，而粒球迭代過程使用聚類算法，每次處理一簇樣本，所以文獻[22]算法具有更快的速度.但是在2個高維數(shù)據(jù)上，所提方法相較于Gap方法還存在一定的差距.

綜上所述，相較于Xia等人[21]所提出的粒球粗糙集約簡，文中所提方法在約簡效率上已經(jīng)有了很大程度的提升，但是在對高維數(shù)據(jù)進行約簡求解時，相較于Gap方法，仍具有可以進一步探索的空間.

表4展示了約簡求解所耗時間的加速比.

根據(jù)表4所示結(jié)果，可以清晰地看出，相較于鄰域粗糙集、文獻[18]算法、文獻[22]算法，筆者所提出的算法2提供了較為顯著的加速比.

表4 求解約簡所需時間的加速比Table 4 Speed-up ratios related to the elapsed time of deriving reducts

此外，為了進一步地展示文中所提算法2的優(yōu)越性，在文中的表5展示了約簡求解時得到的約簡率.

根據(jù)表5所示結(jié)果，可以明顯地看出，相較于文獻[18]算法，筆者所提算法2得到的約簡率仍有一定差距，但是相較于鄰域方法、文獻[22]算法，算法2具有更高的約簡率.

表5 求解約簡時得到的約簡率Table 5 Reduct ratios related to deriving reducts

4.3 分類準確率對比

在本節(jié)中，分別采取KNN(K取值為3)和SVM(libSVM[23]默認參數(shù))兩種分類器，利用約簡所求得的屬性，在測試集上進行分類.具體的分類準確率如表6所示.

表6 KNN和 SVM 分類器的分類準確率Table 6 Classification accuracies based on KNN and SVM classifiers

通過表6展示的結(jié)果并進行對比分析，可以得出如下結(jié)論：從分類準確率的均值來看，無論是采用KNN還是SVM分類器，4種算法求得的約簡均能提供相當?shù)姆诸惸芰?從分類準確率在單個數(shù)據(jù)上的表現(xiàn)來看，相較其他3種算法，利用筆者所提算法2產(chǎn)生的約簡，在某些數(shù)據(jù)上能夠提供較好的分類能力.這說明在粒球粗糙集中引入偽標簽策略并進行約簡求解并不會降低后續(xù)學(xué)習(xí)器的分類性能.

最后，綜合考慮時間消耗，相較于文中對比的其他3種算法，可以得知，利用偽標簽粒球粗糙集進行約簡求解，不僅在約簡效率上占據(jù)較大優(yōu)勢，還能得到較高的約簡率并維持較好的分類表現(xiàn)能力.

5 結(jié)束語

在利用粒球粗糙集進行約簡求解時，粒球的生成過程在很大程度上影響著約簡求解的時間效率.若數(shù)據(jù)中存在大量不一致樣本，則根據(jù)樣本自身提供的標簽信息生成高純度的粒球?qū)永щy，進而導(dǎo)致計算粒球的時間消耗急劇增加.

因此，筆者將偽標簽策略引入到粒球的計算過程中，使用偽標簽對數(shù)據(jù)中樣本的原始標簽進行更新，旨在減少不一致情形，從而使得粒球中的樣本分布更加聚集，降低計算粒球的時間消耗并以此來提升約簡求解的效率.實驗結(jié)果表明，所提出的偽標簽粒球方法可以顯著降低約簡求解的時間消耗，并且所獲取的約簡也具備相當?shù)姆诸惸芰?在本文的基礎(chǔ)上，可以就以下工作進行進一步探索.

1)在生成粒球的過程中，由于k-means算法固有的隨機性和不穩(wěn)定性，因而可以考慮其他無監(jiān)督策略以提升粒球及其粗糙集的穩(wěn)定性.

2)在對高維數(shù)據(jù)進行約簡求解時，基于粒球粗糙集的約簡求解耗時巨大，可以考慮在其中引入屬性簇[9]方法，進一步提升問題求解的效率.