巴 婧,陳 妍,楊習(xí)貝

(江蘇科技大學(xué) 計(jì)算機(jī)學(xué)院,江蘇 鎮(zhèn)江 212100)

作為處理連續(xù)型和混合型等復(fù)雜數(shù)據(jù)的一種拓展粗糙集方法[1,2],胡清華等[3]提出的鄰域粗糙集因其靈活的粒度表現(xiàn)形式,受到了眾多研究學(xué)者的青睞。然而,在使用鄰域粗糙集進(jìn)行屬性約簡[4-6]這一問題的研究時(shí),往往需要通過大量的嘗試或采用一定的參數(shù)搜索策略來設(shè)置鄰域半徑的大小[7-9],這勢必會(huì)帶來極大的時(shí)間消耗。

為了克服鄰域粗糙集中半徑選取這一困難,已有相關(guān)學(xué)者借助自適應(yīng)的理念,提出了一些能夠自主確定半徑大小的策略。例如,Zhou等[10]面向在線特征選擇問題,提出了Gap鄰域的概念,其使用樣本間距離的差值確定鄰域的大小,從而生成較為緊湊的Gap鄰域粒結(jié)構(gòu);Xia等[11]為提升大規(guī)模數(shù)據(jù)中分類任務(wù)的效率,提出了粒球的概念,其過程是迭代使用2-means聚類,從數(shù)據(jù)自身的分布出發(fā),生成大小不一的粒球,直至粒球的純度達(dá)到預(yù)期目標(biāo)。

粒球的純度實(shí)際上是粒球中樣本的標(biāo)簽與粒球標(biāo)簽相吻合的樣本的比重,采用這一概念,Xia等[12]進(jìn)一步地進(jìn)行了基于粒球純度的屬性約簡問題的研究。然而,若采用貪心搜索策略對基于粒球純度的約簡進(jìn)行求解,依然會(huì)存在候選屬性空間較大的問題,從而致使搜索效率不高。例如,采用后向貪心搜索時(shí),對于每一個(gè)候選屬性都要進(jìn)行逐步的評估與嘗試,以判斷該屬性是否可以被刪除;而采用前向貪心搜索時(shí),依然需要對每一個(gè)候選屬性進(jìn)行逐步的評估與嘗試,以判斷該屬性是否可以被加入到約簡集合中。

綜上所述,如果從壓縮候選屬性數(shù)量的層面出發(fā),基于粒球純度的約簡求解效率依然存在提升空間。因此,本文在前向貪心搜索約簡的進(jìn)程中,引入了屬性劃分策略。屬性劃分方法的本質(zhì)是在搜索時(shí),將所有屬性劃分成不同的組,從而以屬性的分組為基準(zhǔn)進(jìn)行候選屬性的篩選,僅評估那些與約簡池中的屬性不屬于同一組的屬性,以達(dá)到減少候選屬性數(shù)量,提升約簡求解效率的目的。其具體步驟為:(1)使用K-means方法對所有屬性進(jìn)行劃分;(2)僅對所有未加入約簡池且與約簡池中任一屬性不在同一劃分中的侯選屬性進(jìn)行評估;(3)根據(jù)評估結(jié)果,挑選出最重要屬性并將其加入到約簡池中。這些步驟能夠壓縮候選屬性的搜索空間,有望降低計(jì)算約簡的時(shí)間消耗,實(shí)現(xiàn)約簡的快速求解。本文所提出的基于粒球粗糙集的屬性劃分快速約簡求解算法,不僅利用粒球粗糙集,從樣本的角度對樣本集進(jìn)行分簇,而且通過引入屬性劃分的方法,從屬性層面對約簡過程進(jìn)行加速。

1 基礎(chǔ)知識

1.1 鄰域粗糙集

(1)

式中:ΔA(xi,xj)表示依據(jù)條件屬性集合A,樣本xi與xj間的距離;δ為給定的半徑。

(2)

(3)

式中:Xp∈U/IND(d)表示具有相同標(biāo)記的樣本所構(gòu)成的第p(1≤p≤n)個(gè)決策類。

1.2 粒球

鄰域關(guān)系因其半徑的存在,所以能夠靈活地以不同的尺度刻畫兩個(gè)樣本間是否相似。但在使用鄰域時(shí),半徑的選擇是一個(gè)難題。雖然目前可以采用諸如優(yōu)化等方式挑選符合問題求解的合適的半徑,但往往搜索效率較低。鑒于此,Xia等[11]依據(jù)數(shù)據(jù)自適應(yīng)理念,提出了粒球的概念。與鄰域不同的是,粒球能夠根據(jù)數(shù)據(jù)自身的分布,自適應(yīng)地刻畫不同樣本之間的相似性。在Xia等[11]的粒球理論中,粒球的結(jié)構(gòu)主要包含兩個(gè)指標(biāo):中心點(diǎn)以及半徑。詳細(xì)定義如下所示。

(4)

(5)

(6)

在Xia等[11]提出的粒球中,粒球的產(chǎn)生采用2-means算法,其主要步驟如下:

(1)將論域U視為一個(gè)類簇;

(2)利用2-means算法分別對每個(gè)類簇進(jìn)行聚類;

(3)求得每一個(gè)類簇的中心點(diǎn)以及類簇中所有樣本至中心點(diǎn)的平均距離;

(4)根據(jù)中心點(diǎn)及平均距離得到粒球,且求得粒球的純度;

(5)遍歷所有粒球,若粒球的純度不低于給定閾值,則不再生成新的粒球,算法結(jié)束;否則返回步驟(2)。

1.3 粒球粗糙集

在求得粒球的基礎(chǔ)上,Xia等[12]進(jìn)一步提出了粒球粗糙集的概念如下所示。

GBs∩Xp≠?}

(7)

(8)

1.4 屬性約簡

在使用粗糙集進(jìn)行數(shù)據(jù)分析時(shí),屬性約簡是一個(gè)關(guān)鍵科學(xué)問題。屬性約簡能夠在某種給定的度量準(zhǔn)則下,通過刪除冗余或者不相關(guān)屬性,以達(dá)到數(shù)據(jù)降維及提升學(xué)習(xí)器性能的目的,近年來受到了諸多學(xué)者的廣泛關(guān)注。一般來說,屬性約簡的形式化定義如下所示。

(1)Abs(ε(A)-ε(AT))≤ζ;

式中:Abs(ε(A)-ε(AT))表示根據(jù)不同屬性集合所得到的度量值之差的絕對值,ζ表示對給定度量的包容度。

包容度ζ的設(shè)置會(huì)使得約簡條件不必過于嚴(yán)苛,文中取值設(shè)置為0.95。因此,在定義7中,條件(1)保證相較于原有屬性集合,所選擇出的屬性子集在給定的度量上不會(huì)帶來較大的偏差;條件(2)保證所選擇出的屬性子集中沒有冗余屬性的存在。

在很多已有的研究成果中,ε可采用近似質(zhì)量(下近似集中樣本占所有樣本的比重)進(jìn)行計(jì)算;在粒球粗糙集方法中,Xia等[12]則采用粒球中獨(dú)有的純度作為ε的計(jì)算方式。

2 基于粒球粗糙集的約簡快速算法

2.1 后向貪心約簡求解

在粒球粗糙集理論中,Xia等[12]以粒球的純度為度量標(biāo)準(zhǔn),不僅給出了相應(yīng)的屬性約簡概念,而且利用后向貪心刪除策略,設(shè)計(jì)了求解約簡的算法,具體描述如算法1所示。

算法1基于粒球粗糙集的后向貪心約簡求解算法

輸入:決策系統(tǒng)DS=〈U,AT∪bzbprpj〉;

輸出:red;

步驟1初始化,令red=AT;

(3)red=red-;

End

red=red∪;

End

步驟5輸出red。

2.2 前向貪心約簡求解

在利用貪心策略求解約簡這一問題中,Yao等[14]將貪心搜索劃分為兩大類:減法控制策略和加法控制策略。實(shí)際上,算法1所描述的后向貪心算法體現(xiàn)了減法控制策略的基本思想。為進(jìn)一步豐富粒球粗糙集中屬性約簡問題的研究,算法2將根據(jù)加法控制策略的基本思想,設(shè)計(jì)出前向貪心搜索算法以求解約簡。

算法2基于粒球粗糙集的前向貪心約簡求解算法

輸入:決策系統(tǒng)DS=〈U,AT∪j5fhrnh〉;

輸出:red;

步驟1初始化,令red=?;

(3)red=red∪;

End

步驟4輸出red。

2.3 基于屬性劃分的約簡快速求解

根據(jù)2.1和2.2節(jié),不難發(fā)現(xiàn)算法1和算法2的時(shí)間復(fù)雜度相同。由于算法1和算法2的時(shí)間消耗均極大地依賴于粒球的個(gè)數(shù),而粒球的個(gè)數(shù)又極大地依賴于數(shù)據(jù)本身的分布,故當(dāng)粒球個(gè)數(shù)較多時(shí),對每個(gè)粒球進(jìn)行遍歷以求解平均純度,會(huì)致使約簡求解的時(shí)間消耗較高。鑒于此,下文將提出一種新的約簡求解策略,即基于屬性劃分的粒球約簡求解方法。

在屬性劃分方法中,優(yōu)先選取對提高平均純度有較大幫助的屬性且這些屬性需與約簡池中的屬性具有較高的不相似度,這樣可以在一定程度上壓縮候選屬性的搜索空間,以達(dá)到減少時(shí)間消耗的目的。此處采用K-means聚類的方法來判定兩個(gè)屬性之間是否具有較高的不相似度,若兩屬性處于不同劃分中,則認(rèn)為這兩個(gè)屬性間的不相似度較高。基于上述思想,算法3構(gòu)建了一個(gè)基于粒球粗糙集的屬性劃分快速約簡求解算法,該算法在對全部屬性集合進(jìn)行劃分后,將侯選屬性中與已在約簡池中屬性屬于不同劃分的屬性加入到約簡集合中,直至滿足約簡所需約束。

算法3基于粒球粗糙集的屬性劃分快速約簡求解算法

輸入:決策系統(tǒng)DS=〈U,AT∪dbnlnf5〉;

輸出:red;

步驟1利用K-means聚類算法對屬性集合AT進(jìn)行分組,以求得屬性劃分;

步驟2初始化,令red=?,T′=?;

(1)令T=AT-red;

(3)若T=?,轉(zhuǎn)(4),否則轉(zhuǎn)(5);

(4)T=AT-red,T′=?;

(5)在T中找到屬性b,使得b=

(6)red=red∪,T′=T′∪;

End

步驟5輸出red。

為了便于理解本文所提算法的主要原理,以下給出一個(gè)簡單的示例。

例1對于表1所示的決策系統(tǒng)DS=〈U,AT∪vrfdrdr〉,其中U={x1,x2,x3,x4},AT={a1,a2,a3,a4}。

表1 決策系統(tǒng)示例

根據(jù)算法3所示步驟,具體計(jì)算過程如下所示:

(1)利用K-means聚類算法對屬性集合AT進(jìn)行分組,得到屬性劃分為{a1,a2}和{a3,a4};

(2)將屬性a1加入到約簡集合中,計(jì)算得到在約簡集合下粒球純度為1,即red=red∪{a1};

(3)由于屬性a2與a1在同一屬性劃分中,故將a3加入到約簡集合中,計(jì)算得到在約簡集合下粒球純度為1,即red=red∪{a3};

(4)循環(huán)步驟(2)和步驟(3),直至滿足約簡條件。

3 實(shí)驗(yàn)分析

為了測試所提算法的有效性,本節(jié)進(jìn)行了相關(guān)的實(shí)驗(yàn)對比。所有實(shí)驗(yàn)均采用MATLAB R2018a實(shí)現(xiàn),操作系統(tǒng)為Windows 10,CPU為Intel?Core(TM)i5-4210U,內(nèi)存為8.00 GB。本節(jié)實(shí)驗(yàn)從UCI標(biāo)準(zhǔn)數(shù)據(jù)集中選取了10組數(shù)據(jù),這些數(shù)據(jù)的基本信息如表2所示。

表2 數(shù)據(jù)集描述

本節(jié)實(shí)驗(yàn)除了實(shí)現(xiàn)文中所示的算法1、算法2和算法3外,還將這些算法與基于鄰域粗糙集的前向貪心約簡求解方法(簡稱鄰域)進(jìn)行了比對。由于鄰域粗糙集涉及半徑選取的問題,故本組實(shí)驗(yàn)以步長為0.02,選取了0.02、0.04、…、0.40等20個(gè)不同半徑,并在這20個(gè)不同半徑下,求取進(jìn)行約簡求解所需時(shí)間消耗的均值。需注意,上述所示的4種算法均采用十折交叉驗(yàn)證進(jìn)行測試。

此外,通過大量的前期測試,對于算法3所涉及的K-means聚類,筆者發(fā)現(xiàn)K取值為「|AT|/3?時(shí),可以使得所提算法展現(xiàn)出較好的性能。

3.1 時(shí)間消耗比對

在本組實(shí)驗(yàn)中,對算法1、算法2、算法3和鄰域粗糙集約簡求解的時(shí)間消耗進(jìn)行統(tǒng)計(jì),具體時(shí)間消耗如表3所示。

表3 不同算法求解約簡的時(shí)間消耗對比 s

觀察表3,不難得出以下結(jié)論。

(1)利用鄰域粗糙集求解約簡,其所需要的時(shí)間遠(yuǎn)超過算法1和2所需的時(shí)間,說明在使用粒球粗糙集進(jìn)行約簡求解時(shí),能夠大大提高約簡求解的效率。以數(shù)據(jù)Breast cancer wisconsin(Diagnostic)為例,在利用鄰域粗糙集求解約簡時(shí),平均時(shí)間消耗為3.011 0 s時(shí),而算法1和2所需的時(shí)間分別為0.068 3 s和0.014 4 s。由此可見,相較于基于鄰域粗糙集的約簡求解,基于粒球粗糙集的算法1和算法2,效率較高。

(2)相較于算法1和2,算法3所需的時(shí)間消耗較低,說明從屬性間相似度出發(fā),將屬性進(jìn)行劃分并求取約簡,確實(shí)能夠進(jìn)一步地降低所需的時(shí)間。以數(shù)據(jù)Ionosphere為例,算法1和2所消耗的時(shí)間分別為0.453 6 s和0.435 7 s,而算法3所消耗的時(shí)間僅為0.329 3 s。由此可知,引入屬性劃分方法后確實(shí)能夠加速約簡求解的進(jìn)程。

表4進(jìn)一步地展現(xiàn)了不同算法之間的加速比,其中,加速比為相應(yīng)的對比算法所需時(shí)間與所提的算法3所需時(shí)間的比值。觀察表4,可以清晰地發(fā)現(xiàn)相較于鄰域粗糙集的約簡求解、算法1和算法2,算法3能夠提供較好的加速比,從而進(jìn)一步地展現(xiàn)了算法3在時(shí)間效率上的優(yōu)越性。

表4 求解約簡所需時(shí)間的加速比

3.2 分類準(zhǔn)確率對比

在本組實(shí)驗(yàn)中,采用K最鄰近(K-nearest neighbor,KNN;K=3)和支持向量機(jī)(Support vector machine,SVM)(libSVM默認(rèn)參數(shù))兩種分類器,對約簡的分類性能進(jìn)行展示。表5展現(xiàn)了不同算法所求得的約簡在測試集上所得到的分類準(zhǔn)確率的均值。

表5 KNN和 SVM 分類器的分類準(zhǔn)確率

觀察表5,不難發(fā)現(xiàn)無論是采用KNN還是SVM分類器,利用4種算法求得約簡在分類性能上相差不大,這說明基于粒球粗糙集的屬性劃分約簡算法能夠產(chǎn)生較為滿意的約簡。但綜合考慮時(shí)間消耗,算法1和2的時(shí)間消耗低于鄰域粗糙集約簡求解的時(shí)間消耗,算法3的時(shí)間消耗又低于算法1和2的時(shí)間消耗?？梢?基于粒球粗糙集的屬性劃分快速約簡求解算法不僅能夠減少約簡求解的時(shí)間,而且相較于其他算法來說,也能夠提供具有相當(dāng)分類能力的約簡。

4 結(jié)束語

為了降低利用貪心搜索算法求解約簡所帶來的時(shí)間消耗,本文在粒球粗糙集的基礎(chǔ)上,利用屬性間的相似度對屬性進(jìn)行劃分,從而能夠切實(shí)減少約簡進(jìn)程中在屬性搜尋層面上的時(shí)間消耗。實(shí)驗(yàn)結(jié)果驗(yàn)證了所提算法的有效性。在此基礎(chǔ)上,今后將就以下問題進(jìn)行深入探索:

(1)所提屬性劃分方法實(shí)際上是在屬性層面上針對快速約簡問題進(jìn)行了探討,今后可以進(jìn)一步地同時(shí)從屬性和樣本兩個(gè)層面對快速約簡問題進(jìn)行研究;

(2)除了采用粒球的純度以外,還可以采用諸如粒球的生成正域、條件熵[15]等度量對粒球粗糙集的屬性約簡問題進(jìn)行深入研究。