基于粒度的加速求解約簡策略

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

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

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

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

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

1 基礎知識

1.1 鄰域粗糙集

(1)

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

(2)

(3)

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

1.2 粒度

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

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

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

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

(4)

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

1.3 屬性約簡

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

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

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

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

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

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

輸出:red;

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

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

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

(3)red=red∪;

End

步驟3 輸出red。

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

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

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

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

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

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

輸入:決策系統(tǒng)DS=〈U,AT∪j5i0abt0b〉,約束條件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,則算法求解約簡的時間復雜度為O(|U|2·(|AT|+1)·|AT|/2),即O(|U|2·|AT|2)。算法1和算法2兩者就時間復雜度來看是一致的,但此僅局限于兩種算法在最壞的情況下所得出的時間復雜度。大量前期測試結(jié)果表明,在求解屬性約簡的過程中,通過剔除部分對應著較粗?；Y(jié)果的屬性,可以減少侯選屬性的個數(shù)。這意味著可以減少評估屬性所需要的次數(shù),算法迭代次數(shù)會減少,進而可以達到快速約簡求解的目的,具體的實驗結(jié)果將在第3節(jié)中進行展示。

3 實驗分析

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

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

本節(jié)實驗分別采用了3種不確定性度量準則,來構造定義4中所示的約束Cρ,從而實現(xiàn)算法1和算法2,這3種不確定性度量分別是近似質(zhì)量[23]、條件熵[24,25]和鄰域鑒別指數(shù)[26]。此外,因為本文采用的是鄰域粗糙集作為模型,因此,對于每一組實驗,都分別選取了0.01、0.02、…、0.20等20個半徑[27],并利用交叉驗證[28]的方法進行約簡求解。

3.1 時間消耗比對

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

圖1 求解約簡的時間消耗

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

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

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

3.2 分類準確率對比

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

表3 SVM分類器的分類準確率

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

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

4 結(jié)束語

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

在此基礎上,今后將進一步探討如下問題。

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

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

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