張昭琴,徐泰華,鞠恒榮,劉克宇,4,王平心

(江蘇科技大學(xué) 1.計(jì)算機(jī)學(xué)院;2.理學(xué)院,江蘇 鎮(zhèn)江 212100;3.南通大學(xué) 信息科學(xué)技術(shù)學(xué)院,江蘇 南通 226019;4.西南交通大學(xué) 計(jì)算機(jī)與人工智能學(xué)院,四川 成都 611756)

屬性約簡[1,2]是粗糙集[3,4]理論研究中的一項(xiàng)核心內(nèi)容。作為一種有效的特征選擇技術(shù)[5,6],近年來屬性約簡已然成為了眾多學(xué)者關(guān)注的焦點(diǎn),其主要思想是依據(jù)不確定性度量評估候選屬性,篩選并移除部分屬性,最終得到滿足給定約束條件的最小屬性子集。作為一種數(shù)據(jù)預(yù)處理技術(shù),屬性約簡既可以對數(shù)據(jù)進(jìn)行降維,從而降低后續(xù)學(xué)習(xí)任務(wù)的復(fù)雜性,又能在一定程度上提升學(xué)習(xí)器的泛化性能。

目前,大量學(xué)者除了根據(jù)實(shí)際應(yīng)用需求,對屬性約簡的結(jié)構(gòu)及形式進(jìn)行廣泛探索,還著眼于設(shè)計(jì)一些搜索算法,以期能夠快速地得到有效的約簡結(jié)果。一般來說,在兼顧考慮約簡求解效率與約簡結(jié)果有效性的同時(shí),眾多學(xué)者傾向于使用前向貪心搜索策略。然而需指出的是,該策略需依據(jù)給定的度量標(biāo)準(zhǔn)對所有候選屬性進(jìn)行逐一評估,直至滿足算法終止條件。這一進(jìn)程需要迭代地遍歷所有的候選屬性,才能得出最終的約簡結(jié)果,因而在屬性數(shù)量急劇增加的情況下,利用前向貪心搜索進(jìn)行約簡求解將顯式地帶來較大的時(shí)間消耗。

根據(jù)上述分析,利用前向貪心搜索求解約簡時(shí),時(shí)間效率依然可以進(jìn)一步提升,例如采用一些選擇性的策略[7],來達(dá)到減少候選屬性數(shù)量的目的。鑒于此,本文在前向貪心搜索進(jìn)程中,引入了粒度[8,9]的概念,用以度量各個(gè)候選屬性對應(yīng)的?；痆10]結(jié)果的粗細(xì)程度,使其能夠在進(jìn)行候選屬性評估之前,剔除部分對應(yīng)著較粗?；Y(jié)果的屬性,從而減少需被評估的侯選屬性的個(gè)數(shù)。這主要是因?yàn)榭紤]到如果某一屬性對應(yīng)著較粗的?；Y(jié)果,那么該屬性對于降低粗糙集方法中的不確定性度量值的貢獻(xiàn)度較弱,若將其加入到約簡結(jié)果中,則對于約束條件的逼近作用不顯著。利用這一選擇性策略,通過比較不同屬性上所對應(yīng)的粒度的值,可以顯式地減少每次迭代進(jìn)程中候選屬性的數(shù)量,從而達(dá)到壓縮屬性搜索空間,提升約簡求解效率的目的。

1 基礎(chǔ)知識

1.1 鄰域粗糙集

(1)

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

(2)

(3)

式中:Xp∈U/IND(d)。

1.2 粒度

以粒計(jì)算的視角來看,粒度這一概念常被用來表征信息?；某潭取Ｒ罁?jù)不同的信息?；绞?粒度可以具有不同的語義解釋[14]如下所示。

(1)基于屬性的粒度。若利用基于屬性集合的二元關(guān)系、聚類等方式進(jìn)行信息粒化,則此時(shí)粒度就可以反映樣本在這些屬性上的區(qū)分程度。相應(yīng)地,根據(jù)不同屬性子集所具備的區(qū)分程度的差異,可以計(jì)算出不同的粒度值。

(2)基于參數(shù)的粒度。若利用基于參數(shù)的二元關(guān)系來進(jìn)行信息?；?則此時(shí)粒度就可以反映在該參數(shù)下樣本的區(qū)分程度。類似地,使用不同的參數(shù)也可能得到不同的粒度值。

實(shí)際上,第1.1節(jié)所示的鄰域關(guān)系本質(zhì)上就是一種信息?；募夹g(shù)手段,這種鄰域關(guān)系既體現(xiàn)了基于屬性的粒度,也體現(xiàn)了基于參數(shù)的粒度。鑒于此,利用鄰域關(guān)系,可以定義如下所示的粒度求解方法。

(4)

式中:|X|表示集合X的基數(shù)。

1.3 屬性約簡

屬性約簡[18]是一種有效的特征選擇方法,依據(jù)不同的約簡求解目標(biāo),已有學(xué)者提出了數(shù)十種屬性約簡的定義。然而,這些定義大都具有類似的結(jié)構(gòu),因此Yao等[19]總結(jié)了屬性約簡的一般表現(xiàn)形式,并給出的形式化定義如下。

(1)A滿足約束條件Cρ,

其中ρ是一個(gè)函數(shù),形如ρ:2U×2AT→R,R是所有實(shí)數(shù)的合集。

由定義4可知屬性約簡的一般表現(xiàn)形式,此時(shí)如何依據(jù)該定義求解約簡就可被視作一個(gè)搜索問題。為此,學(xué)者們采用了諸多不同類型或結(jié)構(gòu)的搜索算法,如完全搜索[20]、隨機(jī)搜索[21]、貪心搜索[22]等。在這些策略中,前向貪心搜索因較低的時(shí)間復(fù)雜度,受到眾多學(xué)者的青睞,此搜索策略的詳細(xì)過程如算法1所示。

算法1前向貪心約簡求解算法

輸入:決策系統(tǒng)DS=〈U,AT∪syggg00〉,約束條件Cρ;

輸出:red;

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

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

(2)依據(jù)(1),找出當(dāng)前迭代過程中一個(gè)合適的屬性b∈AT-red;

(3)red=red∪;

End

步驟3 輸出red。

在算法1迭代求解約簡的過程中,最壞的情況下,條件屬性集AT中的每個(gè)屬性都需要被評估。因此,評估屬性所需要的次數(shù)為(|AT|+1)·|AT|/2,此時(shí)該算法的時(shí)間復(fù)雜度為O(|U|2·(|AT|+1)·|AT|/2),即O(|U|2·|AT|2)。

2 基于粒度的約簡加速求解算法

在粒計(jì)算領(lǐng)域中,粒度這一概念可以量化地描述屬性所具備的分辨能力。一般來說,較細(xì)的粒度,即粒度值較小,表示屬性具有較強(qiáng)的分辨能力,而較粗的粒度,即粒度值較大,表明屬性具有較弱的分辨能力。

通過觀察算法1,不難發(fā)現(xiàn)屬性約簡的過程實(shí)際上是與粒度的變化密切相關(guān)的,這主要是因?yàn)樗惴?是一個(gè)迭代地增加屬性的過程,而隨著屬性不斷地被評估并加入到約簡池中,粒度將逐漸變細(xì),即粒度的值將逐漸變小。由此可以得知:(1)在每次迭代過程中,所有候選池中的屬性都需被評估;(2)候選池中的部分屬性可能對應(yīng)著較粗的粒度,這類屬性往往具備較弱的區(qū)分能力,因而具有較粗粒度的候選屬性可能會(huì)對屬性評估以及計(jì)算約簡的時(shí)間消耗產(chǎn)生不利影響。綜合考慮以上兩點(diǎn),如何利用屬性約簡過程和粒度變化的關(guān)聯(lián),進(jìn)一步提升評估屬性及計(jì)算約簡的效率,是一個(gè)突破口。

根據(jù)上述分析,在候選池中刪除一些對應(yīng)著較粗粒度的侯選屬性,可以達(dá)到減少屬性約簡過程中侯選屬性搜索范圍的目的。因此,本文提出了一種基于粒度的加速求解約簡策略,詳細(xì)算法如算法2所示。

算法2基于粒度的加速求解約簡算法

輸入:決策系統(tǒng)DS=〈U,AT∪syggg00〉,約束條件Cρ;

輸出:red;

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

步驟4 根據(jù)步驟3,找到合適的屬性b∈AT-red;

步驟5red=red∪;

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

(3)依據(jù)(2),找到合適的屬性b∈T,red=

red∪;

End

步驟7 輸出red。

相較于算法1,算法2在最壞情況下,評估屬性所需的次數(shù)為(|AT|+1)·|AT|/2,則算法求解約簡的時(shí)間復(fù)雜度為O(|U|2·(|AT|+1)·|AT|/2),即O(|U|2·|AT|2)。算法1和算法2兩者就時(shí)間復(fù)雜度來看是一致的,但此僅局限于兩種算法在最壞的情況下所得出的時(shí)間復(fù)雜度。大量前期測試結(jié)果表明,在求解屬性約簡的過程中,通過剔除部分對應(yīng)著較粗?；Y(jié)果的屬性,可以減少侯選屬性的個(gè)數(shù)。這意味著可以減少評估屬性所需要的次數(shù),算法迭代次數(shù)會(huì)減少,進(jìn)而可以達(dá)到快速約簡求解的目的,具體的實(shí)驗(yàn)結(jié)果將在第3節(jié)中進(jìn)行展示。

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

為了驗(yàn)證所提算法的有效性,本文從UCI數(shù)據(jù)集中選取了12組數(shù)據(jù)集,數(shù)據(jù)集的基本描述如表1所示。實(shí)驗(yàn)均采用MATLAB R2018a實(shí)現(xiàn),操作系統(tǒng)為Windows 10,CPU為Intel?Core(TM)i5-4210U,內(nèi)存為8.00 GB。

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

本節(jié)實(shí)驗(yàn)分別采用了3種不確定性度量準(zhǔn)則,來構(gòu)造定義4中所示的約束Cρ,從而實(shí)現(xiàn)算法1和算法2,這3種不確定性度量分別是近似質(zhì)量[23]、條件熵[24,25]和鄰域鑒別指數(shù)[26]。此外,因?yàn)楸疚牟捎玫氖青徲虼植诩鳛槟Ｐ?因此,對于每一組實(shí)驗(yàn),都分別選取了0.01、0.02、…、0.20等20個(gè)半徑[27],并利用交叉驗(yàn)證[28]的方法進(jìn)行約簡求解。

3.1 時(shí)間消耗比對

圖1展示了利用兩種算法和3種不確定性度量,在12個(gè)數(shù)據(jù)集上計(jì)算約簡的時(shí)間消耗。

圖1 求解約簡的時(shí)間消耗

由圖1,可得出如下結(jié)論:

(1)無論采用哪一種不確定性度量,相較于算法1,所提出的算法2確實(shí)可以對約簡的求解過程進(jìn)行加速,從而使得時(shí)間消耗顯著降低。以數(shù)據(jù)集“Australian sign language signs”為例,若采用近似質(zhì)量度量構(gòu)造約束,算法1在半徑設(shè)置為0.08時(shí),求解約簡需耗時(shí)16.135 8 s,而算法2僅需耗時(shí)9.839 3 s;若以鄰域鑒別指數(shù)為度量標(biāo)準(zhǔn)構(gòu)造約束,算法1在半徑設(shè)置為0.12時(shí)求解約簡需耗時(shí)2.788 8 s,而算法2僅需耗時(shí)2.308 3 s。由此可見,相較于傳統(tǒng)前向貪心約簡求解算法,基于粒度的加速求解約簡算法在獲取約簡的效率上具有顯著優(yōu)勢,這與算法的設(shè)計(jì)初衷是保持一致的。在每一輪迭代選擇屬性的過程中,剔除了一些對應(yīng)著較粗?；Y(jié)果的屬性,減少了侯選屬性的個(gè)數(shù),從而使得評估屬性時(shí)計(jì)算次數(shù)減少。

(2)本文提出的算法在不同類型的樣本數(shù)據(jù)集上,都體現(xiàn)出了較好的加速效果。以數(shù)據(jù)集“LSVT voice rehabilitation”和“Cardiotocography”為例,前者樣本數(shù)是126,屬性個(gè)數(shù)為256;后者樣本數(shù)是2 126,屬性數(shù)目為21。從求解約簡所需時(shí)間消耗的角度來看,在利用近似質(zhì)量為度量來構(gòu)造約束的情形下,前者在算法1且半徑為0.09的情況下求解約簡需耗時(shí)3.108 7 s,而算法2僅需耗時(shí)1.692 3 s;后者在算法1且半徑設(shè)置為0.09的情況下求解約簡需耗時(shí)71.121 7 s,而算法2僅需耗時(shí)43.466 3 s。由此可見,盡管兩組數(shù)據(jù)就樣本和屬性的比例來看,存在顯著的差異,但是從求解約簡所需時(shí)間消耗的角度來看,本文提出的算法在這兩組數(shù)據(jù)上都表現(xiàn)出了良好的性能。

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

在本組實(shí)驗(yàn)中,采用了常用的K最近鄰分類器(K-nearest neighbor,KNN,K=3)和支持向量機(jī)[29](Support vector machine,SVM,libSVM默認(rèn)參數(shù))兩種分類器分別對所求得的約簡的分類性能進(jìn)行測試。因?yàn)樵谇蠼饧s簡時(shí)采用了五折交叉驗(yàn)證,因此在每一輪使用四折樣本求得約簡結(jié)果后,都可以使用剩下的那一折樣本進(jìn)行分類測試,最終求得平均分類準(zhǔn)確率。其詳細(xì)結(jié)果分別如表2和表3所示。

表3 SVM分類器的分類準(zhǔn)確率

通過對比表2和表3展示的結(jié)果,不難發(fā)現(xiàn),本文所提出的算法2在大多數(shù)情況下都能得到令人滿意的分類準(zhǔn)確率。舉例來說,在表2中,以數(shù)據(jù)集“QSAR biodegradation”為例,采用3種不同的不確定性度量分別構(gòu)造約束,算法1求得的約簡結(jié)果所對應(yīng)的分類準(zhǔn)確率分別為0.841 7、0.840 4和0.841 5,而算法2求得的約簡結(jié)果所對應(yīng)的分類準(zhǔn)確率分別為0.842 6、0.841 3和0.843 2;在表3中,以數(shù)據(jù)集“Waveform database generator”為例,采用3種不同的不確定性度量分別構(gòu)造約束,算法1求得的約簡結(jié)果所對應(yīng)的分類準(zhǔn)確率分別為0.787 1、0.805 9和0.813 1,而算法2求得的約簡結(jié)果所對應(yīng)的分類準(zhǔn)確率分別為0.807 6、0.823 6和0.828 9。由此可見,相較于傳統(tǒng)的前向貪心策略所求得的約簡,基于粒度的加速求解約簡策略能夠使得所求約簡具備相似的分類能力。

綜合3.1節(jié)和3.2節(jié)所述內(nèi)容,不難發(fā)現(xiàn),相較于算法1而言,算法2可以在保證縮短求解約簡時(shí)間消耗的同時(shí),提供滿意的分類準(zhǔn)確率。

4 結(jié)束語

考慮到基于前向貪心搜索策略求解約簡時(shí),需評估所有的候選屬性,導(dǎo)致時(shí)間消耗過多的問題。本文依據(jù)屬性約簡過程和粒度變化的關(guān)聯(lián),提出了一種基于粒度的加速求解約簡策略。該策略通過在屬性約簡進(jìn)程中,剔除對應(yīng)著較粗粒度的屬性,壓縮候選屬性的搜索空間,進(jìn)行快速約簡求取。實(shí)驗(yàn)結(jié)果表明所提出的算法在多種度量下,能夠有效地降低求解約簡所需的時(shí)間消耗,同時(shí)也保證了所求得的約簡具備令人滿意的泛化能力。

在此基礎(chǔ)上,今后將進(jìn)一步探討如下問題。

(1)所提算法是一個(gè)框架性的結(jié)構(gòu),文中只使用了鄰域粗糙集及相關(guān)度量進(jìn)行討論,也可以采用其他諸如不具備單調(diào)性的粗糙集模型和度量進(jìn)行算法的進(jìn)一步提升。

(2)將約簡結(jié)果的穩(wěn)定性納入討論范圍,可以進(jìn)一步考慮如何在提升約簡穩(wěn)定性的同時(shí),確保求解約簡的效率。

(3)本文所提算法是基于粒度的角度,在屬性選擇的過程中壓縮候選屬性的搜索空間。為了進(jìn)一步提升算法的性能,可以考慮增加樣本層面的加速策略,與基于樣例選取的屬性約簡算法[30]進(jìn)行結(jié)合,以期更進(jìn)一步地提升約簡求解的效率。