陳寶國(guó),陳 磊*,鄧 明,陳金林,2
(1.淮南師范學(xué)院 計(jì)算機(jī)學(xué)院,安徽淮南 232038;2.南京航空航天大學(xué)電子與信息工程學(xué)院,江蘇南京 211106)
屬性約簡(jiǎn)是粗糙集理論在模式識(shí)別下的最重要應(yīng)用之一[1–2]。粗糙集理論通過(guò)對(duì)數(shù)據(jù)集的屬性子集構(gòu)建二元關(guān)系,實(shí)現(xiàn)了屬性子集的不確定評(píng)估,從而可以刪除數(shù)據(jù)集中的無(wú)效屬性。針對(duì)不同的數(shù)據(jù)類型和數(shù)據(jù)環(huán)境,學(xué)者們基于粗糙集理論提出了大量的屬性約簡(jiǎn)算法,使得屬性約簡(jiǎn)成為粗糙集理論最為活躍的研究?jī)?nèi)容[1]。
當(dāng)今大數(shù)據(jù)環(huán)境下,數(shù)據(jù)常常呈現(xiàn)出快速更新變化的特性[3],一些傳統(tǒng)的屬性約簡(jiǎn)算法暴露出了計(jì)算效率低的缺陷。為了解決此問(wèn)題,增量式屬性約簡(jiǎn)的方法近幾年不斷地被研究和探索[4–15]。針對(duì)離散型的信息系統(tǒng),常用知識(shí)粒度[4]、區(qū)分矩陣[5–6]、依賴度[7]和遺傳算法[8]等方法;針對(duì)連續(xù)型的信息系統(tǒng),常用覆蓋粒度[9]、鄰域粗糙集[10]和模糊粗糙集[11]等方法;針對(duì)離散型和連續(xù)型混合類型的信息系統(tǒng),常用混合鄰域粗糙集[12]、鄰域知識(shí)粒度[13]、鄰域區(qū)分度[14]和鄰域正區(qū)域[15]等方法。目前為止,增量式屬性約簡(jiǎn)的研究已經(jīng)涵蓋了多種類型的數(shù)據(jù)。
然而,數(shù)據(jù)類型總是復(fù)雜多樣的,某些情形下信息系統(tǒng)的屬性值滿足一定的偏序關(guān)系,這類信息系統(tǒng)被稱為有序信息系統(tǒng),其中,優(yōu)勢(shì)粗糙集是處理該系統(tǒng)的常用模型[16]。有序信息系統(tǒng)的研究近年來(lái)受到了越來(lái)越多的關(guān)注[17–19],Sang等[20–22]學(xué)者分別在離散型和連續(xù)型有序信息系統(tǒng)下基于優(yōu)勢(shì)粗糙集提出了多種增量式屬性約簡(jiǎn)算法。然而,目前還未有不完備混合型有序信息系統(tǒng)增量式屬性約簡(jiǎn)的提出和設(shè)計(jì)。以此為研究動(dòng)機(jī),本文進(jìn)行了該類型信息系統(tǒng)的增量式屬性約簡(jiǎn)研究和探索。
首先,提出一種鄰域容差優(yōu)勢(shì)關(guān)系,實(shí)現(xiàn)不完備混合型有序信息系統(tǒng)的信息?;痛植诮?。其次,在所提出二元關(guān)系的框架下,建立了對(duì)應(yīng)的信息熵、聯(lián)合熵以及條件熵,利用條件熵的單調(diào)性設(shè)計(jì)了非增量式屬性約簡(jiǎn)算法。然后,當(dāng)不完備混合型有序信息系統(tǒng)的對(duì)象出現(xiàn)了動(dòng)態(tài)增加和減少,建立鄰域優(yōu)勢(shì)條件熵的增量式學(xué)習(xí)框架。最后,根據(jù)該框架提出了不完備混合型有序信息系統(tǒng)的增量式屬性約簡(jiǎn)算法,實(shí)驗(yàn)分析結(jié)果證明了本文增量式算法的有效性。
假設(shè)屬性子集B={a1,a2},圖1展示了對(duì)象xk在鄰域優(yōu)勢(shì)關(guān)系下優(yōu)勢(shì)集和劣勢(shì)集的示意圖,G1~G5代表了不同的區(qū)域,不同形狀的點(diǎn)隸屬于不同的區(qū)域,五角星形狀的點(diǎn)隸屬于G1區(qū)域,十字形狀的點(diǎn)隸屬于G2區(qū)域,三角形的點(diǎn)隸屬于G3區(qū)域,正方形的點(diǎn)隸屬于G4區(qū)域,圓形的點(diǎn)隸屬于G5區(qū)域。從圖1中可以看出,對(duì)象xk的優(yōu)勢(shì)集=G2,對(duì)象xk的劣勢(shì)集=G4。
圖1 對(duì)象優(yōu)勢(shì)集與劣勢(shì)集的示意圖Fig. 1 Schematic diagram of object dominating set and dominated set
由于實(shí)際環(huán)境下數(shù)據(jù)采集難易程度的不同及采集成本等方面的原因,信息系統(tǒng)存在著不完備的特性[7,15–16,23]??紤]到混合型有序信息系統(tǒng)的不完備性,本節(jié)將提出不完備混合型有序信息系統(tǒng)的概念,并提出對(duì)應(yīng)的鄰域優(yōu)勢(shì)粗糙集模型。
Zhao等[24]基于信息熵模型實(shí)現(xiàn)了不完備信息系統(tǒng)的不確定性度量與屬性約簡(jiǎn),本節(jié)針對(duì)此文所研究的信息系統(tǒng)類型,將該方法進(jìn)行推廣和擴(kuò)展。
對(duì)于?b∈(C-B)在B下的外部屬性重要度定義為
根據(jù)定義10和定義11,利用鄰域優(yōu)勢(shì)條件熵對(duì)不完備混合型有序信息系統(tǒng)進(jìn)行屬性約簡(jiǎn)的實(shí)現(xiàn)如算法1所示,由于算法1在進(jìn)行屬性約簡(jiǎn)時(shí)輸入的是靜態(tài)數(shù)據(jù)集,因此算法1也稱為非增量式屬性約簡(jiǎn)算法。
算法1基于鄰域優(yōu)勢(shì)條件熵的不完備混合型有序信息系統(tǒng)屬性約簡(jiǎn)算法。
信息系統(tǒng)不斷進(jìn)行更新,當(dāng)信息系統(tǒng)對(duì)象發(fā)生增刪時(shí),原有約簡(jiǎn)結(jié)果不再有效,因此,需要重新計(jì)算新信息系統(tǒng)的屬性約簡(jiǎn)。在已有各種基于信息熵的屬性約簡(jiǎn)算法中,學(xué)者們均通過(guò)增量式更新信息熵的方法來(lái)更新屬性約簡(jiǎn)結(jié)果[10,13,21–22],因此本文也采用類似的實(shí)現(xiàn)方案完成屬性約簡(jiǎn)的動(dòng)態(tài)更新。
在粗糙集理論中,矩陣是構(gòu)造模型和算法增量式學(xué)習(xí)的一種常用工具[3,5–6,18,21–22]。
第3.2節(jié)中實(shí)現(xiàn)了不完備混合有序信息系統(tǒng)對(duì)象增刪情形時(shí)鄰域優(yōu)勢(shì)條件熵的動(dòng)態(tài)更新,本節(jié)在其基礎(chǔ)上實(shí)現(xiàn)對(duì)應(yīng)的增量式屬性約簡(jiǎn)算法,分別如算法2和算法3所示。
算法2對(duì)象增加時(shí)基于鄰域優(yōu)勢(shì)條件熵的不完備混合型有序信息系統(tǒng)增量式屬性約簡(jiǎn)算法。
表1為加州大學(xué)歐文分校UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的8個(gè)常用分類學(xué)習(xí)數(shù)據(jù)集,其中,Chess為離散型屬性值的數(shù)據(jù)集,W ine、Wdbc和Parkinson’s Disease為連續(xù)型屬性值的數(shù)據(jù)集,AnuranCalls、DryBean、Magic和M usk為混合型屬性值的數(shù)據(jù)集,本節(jié)將在這8個(gè)數(shù)據(jù)集上進(jìn)行屬性約簡(jiǎn)實(shí)驗(yàn)來(lái)驗(yàn)證本文增量式算法的性能。所有的算法通過(guò)軟件Matlab2018b編程實(shí)現(xiàn),計(jì)算機(jī)型號(hào)為CPU Intel(R)Core(TM)i7–7700 4.20 GHz,內(nèi)存為16.0 GB DDR4,操作系統(tǒng)為W indows10。
表1 實(shí)驗(yàn)數(shù)據(jù)集Tab.1 Experimental data sets
在表1所示的數(shù)據(jù)集中,對(duì)于離散類型的屬性值(也包括決策屬性值),按照數(shù)據(jù)集樣本的序號(hào),將離散型屬性值替換成依次遞增的整數(shù)型數(shù)值,例如:對(duì)于屬性值v1、v2和v3,將其替換為1、2和3;對(duì)于連續(xù)型屬性值,為了消除屬性量綱帶來(lái)的影響,采用極差正規(guī)化的方法進(jìn)行數(shù)據(jù)標(biāo)準(zhǔn)化。整個(gè)實(shí)驗(yàn)中,統(tǒng)一按照屬性值的遞增來(lái)定義優(yōu)勢(shì)關(guān)系中的偏序關(guān)系,即屬性值大的對(duì)象優(yōu)勢(shì)于屬性值小的對(duì)象。此外,本文研究的是不完備信息系統(tǒng)下的屬性約簡(jiǎn)問(wèn)題,表1中的數(shù)據(jù)集均為完備型,本實(shí)驗(yàn)對(duì)決策屬性以外的屬性值隨機(jī)選擇3%進(jìn)行刪除,從而構(gòu)造數(shù)據(jù)集的不完備性。
在本文所提出的算法中,入?yún)⑧徲虬霃?δ取值的不同會(huì)影響到最終的屬性約簡(jiǎn)結(jié)果以及分類性能。因此,為了得到最優(yōu)的鄰域半徑值,將鄰域半徑 δ在區(qū)間[0.01,0.20]內(nèi)以0.01為間隔分別作為輸入?yún)?shù)輸入算法1,選擇出對(duì)應(yīng)的約簡(jiǎn)集結(jié)果,記錄屬性約簡(jiǎn)結(jié)果中屬性的個(gè)數(shù),同時(shí)利用兩種分類器(支持向量機(jī)(SVM)和鄰近點(diǎn)參數(shù)k設(shè)3的k鄰近(kNN))分類訓(xùn)練獲得約簡(jiǎn)集結(jié)果的分類精度。對(duì)所有鄰域半徑的結(jié)果進(jìn)行歸納確定最優(yōu)鄰域半徑 δ值。圖2為表1中部分?jǐn)?shù)據(jù)集的實(shí)驗(yàn)結(jié)果。由圖2可知,當(dāng)鄰域半徑增大,約簡(jiǎn)集長(zhǎng)度呈現(xiàn)出減小趨勢(shì),分類精度呈現(xiàn)出先穩(wěn)定后減小的趨勢(shì),鄰域半徑在[0.06,0.10]的范圍內(nèi)均具有較高的分類精度水平。屬性約簡(jiǎn)旨在找到屬性集較小且分類精度較高的屬性子集,因此,經(jīng)綜合比較,選擇鄰域半徑δ=0.10進(jìn)行實(shí)驗(yàn)較為合適。
4.2.1屬性約簡(jiǎn)結(jié)果有效性比較
對(duì)于表1中的各個(gè)數(shù)據(jù)集,從完整的論域選擇50%對(duì)象作為初始信息系統(tǒng),剩余50%的論域?qū)ο笞鳛閯?dòng)態(tài)增加的對(duì)象集。然后,利用增量式與非增量式算法分別進(jìn)行動(dòng)態(tài)屬性約簡(jiǎn),記錄兩種算法的詳細(xì)結(jié)果,并利用SVM和kNN(k為3)獲得約簡(jiǎn)結(jié)果的分類精度。所有實(shí)驗(yàn)結(jié)果如表2所示,其中,“{*}”為屬性集結(jié)果,“(*)”為屬性的數(shù)量。
由表2可知,兩種算法的約簡(jiǎn)結(jié)果非常接近。例如:數(shù)據(jù)集AnuranCalls有著相同的屬性約簡(jiǎn)結(jié)果;對(duì)于數(shù)據(jù)集W ine、Chess、M usk和Parkinson’s Disease,增量式屬性約簡(jiǎn)算法的約簡(jiǎn)結(jié)果更小一些,同時(shí)有著更高的分類精度;數(shù)據(jù)集Wdbc和DryBean有著屬性數(shù)量相同但屬性不完全一樣的約簡(jiǎn)集,其分類精度也很接近;對(duì)于數(shù)據(jù)集M agic,雖然增量式算法約簡(jiǎn)得到的屬性稍多一些,但是分類精度更高一些。表2的結(jié)果表明,兩種算法都是可行且有效的;相比非增量式算法,增量式算法的屬性約簡(jiǎn)結(jié)果更優(yōu)異。
表2 對(duì)象增加時(shí)兩類算法的屬性約簡(jiǎn)和分類精度比較Tab.2 Comparison of attribute reduction and classificatioaccuracy between the two algorithms when objects are added
4.2.2屬性約簡(jiǎn)算法的效率比較
從所有數(shù)據(jù)集中隨機(jī)選擇40%的對(duì)象作為初始數(shù)據(jù)集,然后,將剩余60%的對(duì)象集隨機(jī)平均分成6份,隨后依次將每份往初始數(shù)據(jù)集中添加,相當(dāng)于每次增加10%的對(duì)象,這樣便構(gòu)造出數(shù)據(jù)集6次數(shù)據(jù)量相同的增加更新。將本文的增量式屬性約簡(jiǎn)算法與非增量式算法分別基于這種數(shù)據(jù)更新方式進(jìn)行屬性約簡(jiǎn),統(tǒng)計(jì)每次屬性約簡(jiǎn)的計(jì)算時(shí)間,重復(fù)進(jìn)行30次實(shí)驗(yàn),其平均實(shí)驗(yàn)結(jié)果如圖3所示。在圖3中,隨著更新次數(shù)的增加,兩種算法的屬性約簡(jiǎn)運(yùn)行時(shí)間整體上呈逐步上升趨勢(shì),但增量式算法的運(yùn)行時(shí)間明顯更低,尤其對(duì)于大規(guī)模的數(shù)據(jù)集AnuranCalls、Dry-Bean和M agic,兩類算法的效率差異更加明顯。因此,對(duì)于信息系統(tǒng)數(shù)據(jù)量相同的增加更新,增量式的屬性約簡(jiǎn)要更加高效。
同時(shí),為了比較信息系統(tǒng)不同數(shù)據(jù)量增加時(shí)兩類算法的更新效率,同樣隨機(jī)選擇40%的對(duì)象作為初始數(shù)據(jù)集,剩余60%的對(duì)象集隨機(jī)平均分成6份;然后,每次分別往初始數(shù)據(jù)集添加不同量的剩余對(duì)象,其中,第1次隨機(jī)選擇1份對(duì)象集添加至初始數(shù)據(jù)集,第2次隨機(jī)選擇2份對(duì)象集進(jìn)行添加,依次類推,直至最后一次性添加6份對(duì)象集,這相當(dāng)于初始數(shù)據(jù)集分別添加了10%、20%、···、60%的對(duì)象,因此,構(gòu)造出了信息系統(tǒng)6次數(shù)據(jù)量不同的增加?;谶@種更新方式,讓兩類算法分別進(jìn)行屬性約簡(jiǎn)更新計(jì)算,重復(fù)進(jìn)行實(shí)驗(yàn)30次,其平均計(jì)算時(shí)間實(shí)驗(yàn)結(jié)果如圖4所示。在圖4中,同樣可以發(fā)現(xiàn)增量式算法的計(jì)算時(shí)間更低,因此,對(duì)于不同數(shù)據(jù)量的增加更新,增量式的屬性約簡(jiǎn)方法也更加高效。
圖3和4中兩類算法表現(xiàn)出的計(jì)算效率差異,主要是由于這兩類算法的計(jì)算架構(gòu)不同,算法1表明,非增量式算法每次對(duì)新的信息系統(tǒng)重新進(jìn)行屬性約簡(jiǎn)的搜索,其計(jì)算量與信息系統(tǒng)當(dāng)前的規(guī)模正相關(guān)。在算法2中,增量式算法以舊信息系統(tǒng)的屬性約簡(jiǎn)為基礎(chǔ),對(duì)變化的對(duì)象進(jìn)行增量式計(jì)算,即算法所產(chǎn)生的計(jì)算量大部分來(lái)源于屬性約簡(jiǎn)結(jié)果中變化的屬性,不必對(duì)原先屬性約簡(jiǎn)中的屬性進(jìn)行重復(fù)搜索計(jì)算,大幅提高了計(jì)算效率,因此,更新屬性約簡(jiǎn)的時(shí)間會(huì)更少。部分?jǐn)?shù)據(jù)集的增量式算法計(jì)算時(shí)間出現(xiàn)了一定波動(dòng),主要是由增量式算法的計(jì)算架構(gòu)決定的,當(dāng)舊的信息系統(tǒng)更新至新的信息系統(tǒng),如果舊的約簡(jiǎn)集能直接繼承作為新信息系統(tǒng)的約簡(jiǎn),那么增量式算法可以直接返回?zé)o需搜索新的屬性,此時(shí),增量式算法所需的耗時(shí)很短;如果舊的約簡(jiǎn)集不能作為新信息系統(tǒng)的約簡(jiǎn),那么需要選擇新屬性更新約簡(jiǎn)結(jié)果,此時(shí)增量式算法就會(huì)產(chǎn)生一定的運(yùn)行時(shí)間,所以,出現(xiàn)用時(shí)波動(dòng)的情況。
4.3.1屬性約簡(jiǎn)結(jié)果有效性比較
首先將表1中的各個(gè)完整數(shù)據(jù)集作為初始數(shù)據(jù)集,然后隨機(jī)選擇論域的50%作為動(dòng)態(tài)減少的對(duì)象,利用增量式算法與非增量式算法分別進(jìn)行動(dòng)態(tài)屬性約簡(jiǎn),并使用SVM和KNN(k為3)分別獲得屬性約簡(jiǎn)的分類精度,所有實(shí)驗(yàn)結(jié)果如表3所示,其中“{*}”為屬性集結(jié)果,“(*)”為屬性的數(shù)量。
在表3中,數(shù)據(jù)集DryBean下兩類算法的約簡(jiǎn)結(jié)果完全一致,而在數(shù)據(jù)集W ine和Chess中,增量式算法的約簡(jiǎn)集稍大一點(diǎn),數(shù)據(jù)集W dbc、AnuranCalls和Magic擁有相同的屬性約簡(jiǎn)集大小,但增量式算法分類精度更高。因此,對(duì)于信息系統(tǒng)對(duì)象減少的情形,增量式架構(gòu)的屬性約簡(jiǎn)算法在約簡(jiǎn)的分類精度方面更加占據(jù)優(yōu)勢(shì),這主要是由于增量式算法能夠保留舊信息系統(tǒng)中的有效屬性,提升新信息系統(tǒng)的分類性能。
4.3.2屬性約簡(jiǎn)算法的效率比較
表3 對(duì)象減少時(shí)兩類算法的屬性約簡(jiǎn)和分類精度比較Tab.3 Comparison of attribute reduction and classification accuracy between the two algorithms when objects are removed
首先將表1中的每個(gè)完整的實(shí)驗(yàn)數(shù)據(jù)集作為初始數(shù)據(jù)集,然后對(duì)每個(gè)數(shù)據(jù)集隨機(jī)選擇60%的對(duì)象集,并平均分成6份,隨后依次進(jìn)行移除操作,相當(dāng)于每次減少10%的對(duì)象,這樣便構(gòu)造出數(shù)據(jù)集6次相同數(shù)據(jù)量的減少。將本文的增量式屬性約簡(jiǎn)算法與非增量式算法分別基于這種數(shù)據(jù)更新方式進(jìn)行屬性約簡(jiǎn),統(tǒng)計(jì)每次屬性約簡(jiǎn)的計(jì)算時(shí)間,重復(fù)進(jìn)行30次實(shí)驗(yàn),其平均時(shí)間實(shí)驗(yàn)結(jié)果如圖5所示。在圖5中,隨著更新次數(shù)增加,兩種算法的屬性約簡(jiǎn)運(yùn)行時(shí)間均逐漸減小,但是增量式算法的運(yùn)行時(shí)間更短,尤其在數(shù)據(jù)集AnuranCalls、DryBean和Magic中,兩種算法的差異更加明顯。
同時(shí),為了比較信息系統(tǒng)不同數(shù)據(jù)量減少時(shí)兩種算法的更新效率,將完整的數(shù)據(jù)集作為初始數(shù)據(jù)集,隨機(jī)選擇60%的對(duì)象集平均分成6份,然后每次分別選擇不同量的對(duì)象集進(jìn)行移除,其中第一次移除1份對(duì)象集,第二次移除2份,依次類推,直至最后一次性移除6份對(duì)象集,這相當(dāng)于在初始數(shù)據(jù)集中分別移除10%、20%、···、60%的對(duì)象,因此構(gòu)造出了信息系統(tǒng)6次不同數(shù)據(jù)量的減少,基于這種更新方式,讓兩種算法分別進(jìn)行屬性約簡(jiǎn),重復(fù)進(jìn)行30次實(shí)驗(yàn),其平均計(jì)算時(shí)間實(shí)驗(yàn)結(jié)果如圖6所示。在圖6中,同樣可以發(fā)現(xiàn)增量式算法的計(jì)算時(shí)間更少,即增量式算法對(duì)動(dòng)態(tài)數(shù)據(jù)有著更高的屬性約簡(jiǎn)效率。
圖5和圖6表現(xiàn)出的效率差異同樣是由于增量式屬性約簡(jiǎn)算法的架構(gòu)決定的。在算法3中,當(dāng)信息對(duì)象減小時(shí),增量式算法在舊的約簡(jiǎn)集上更新屬性信息,避免對(duì)已選擇的屬性進(jìn)行重復(fù)計(jì)算,極大地提高了動(dòng)態(tài)數(shù)據(jù)環(huán)境下屬性約簡(jiǎn)的效率,由于非增量式算法重復(fù)地選擇屬性,使得屬性約簡(jiǎn)的耗時(shí)大幅高于增量式算法。
圖5 減少相同數(shù)據(jù)量時(shí)更新屬性約簡(jiǎn)的用時(shí)比較Fig. 5 Time comparison of updating attribute reduction when removing the same amount of data
圖6 減少不同數(shù)據(jù)量時(shí)更新屬性約簡(jiǎn)的用時(shí)比較Fig. 6 Time comparison of updating attribute reduction when removing the different amount of data
本小節(jié)所選擇的比較算法分別為:1)優(yōu)勢(shì)粗糙集模型的增量式屬性約簡(jiǎn)[20];2)混合型有序信息系統(tǒng)鄰域熵的增量式屬性約簡(jiǎn)[22];3)量化鄰域自信息熵的增量式屬性約簡(jiǎn)[25],這3種算法分別簡(jiǎn)記為對(duì)比算法1、2、3。其中,對(duì)比算法1是一種建立在離散型有序信息系統(tǒng)下的增量式屬性約簡(jiǎn),在進(jìn)行實(shí)驗(yàn)時(shí)需將表1的數(shù)據(jù)轉(zhuǎn)換成標(biāo)記型類型,同時(shí)這3種對(duì)比算法都只適用于完備型的有序信息系統(tǒng),而本實(shí)驗(yàn)選擇的數(shù)據(jù)集均為不完備類型,采用平均值的方法對(duì)這些數(shù)據(jù)集進(jìn)行缺失值填充,即對(duì)屬性下所有對(duì)象的屬性值求取平均值并用平均值對(duì)該屬性下的缺失值進(jìn)行填充。隨后,將所有增量式算法分別進(jìn)行信息系統(tǒng)動(dòng)態(tài)屬性約簡(jiǎn)實(shí)驗(yàn)。
4.4.1信息系統(tǒng)對(duì)象增加時(shí)增量式屬性約簡(jiǎn)比較
按照第4.2.2節(jié)對(duì)數(shù)據(jù)集構(gòu)建6次增加相同數(shù)據(jù)量的更新方式,將所有增量式算法分別進(jìn)行屬性約簡(jiǎn)實(shí)驗(yàn)。統(tǒng)計(jì)每次更新時(shí)所有算法的計(jì)算用時(shí),重復(fù)實(shí)驗(yàn)30次,其平均計(jì)算時(shí)間結(jié)果如圖7所示。當(dāng)數(shù)據(jù)集完成最后一次動(dòng)態(tài)增加,所有算法的約簡(jiǎn)集長(zhǎng)度比較結(jié)果見(jiàn)表4,約簡(jiǎn)集的分類精度比較結(jié)果見(jiàn)表5。
圖7 對(duì)象增加時(shí)增量式屬性約簡(jiǎn)算法的用時(shí)比較Fig. 7 Time comparison of the incremental attribute reduction algorithms when objects are added
表4 對(duì)象增加時(shí)增量式算法的屬性約簡(jiǎn)集長(zhǎng)度比較Tab.4 Length comparison of attribute reduction set for incremental algorithms when objects are increased
在表4中,除數(shù)據(jù)集Chess和M usk外,本文增量式算法有著更小的屬性約簡(jiǎn)集長(zhǎng)度。在表5中,除數(shù)據(jù)集W dbc和DryBean外,本文增量式算法的SVM分類精度高于其余算法;除數(shù)據(jù)集Chess、DryBean和M agic外,本文增量式算法的kNN分類精度高于其余算法。在圖7中,本文增量式算法的用時(shí)整體上低于其余算法。表4、5和圖7的實(shí)驗(yàn)結(jié)果表明,本文增量式算法有著更高的屬性約簡(jiǎn)性能。其原因?yàn)閷?duì)比算法1進(jìn)行實(shí)驗(yàn)時(shí)需將數(shù)據(jù)集進(jìn)行離散化,這一處理丟失了連續(xù)型屬性的數(shù)據(jù)結(jié)構(gòu)信息,因此,對(duì)最終的屬性約簡(jiǎn)結(jié)果造成了一定的偏差。對(duì)比算法2和3是兩種適用于完備型信息系統(tǒng)的增量式屬性約簡(jiǎn)方法,而本實(shí)驗(yàn)的數(shù)據(jù)集均為不完備類型,因此,對(duì)屬性約簡(jiǎn)的效果產(chǎn)生了一定影響。在增量式約簡(jiǎn)效率方面,本文增量式算法通過(guò)矩陣策略直接更新每個(gè)對(duì)象的鄰域優(yōu)勢(shì)類,并進(jìn)一步更新鄰域優(yōu)勢(shì)條件熵,跳過(guò)了對(duì)鄰域優(yōu)勢(shì)上下近似集的增量式更新,因此,所需的計(jì)算量最少,效率整體最高。
4.4.2信息系統(tǒng)對(duì)象減少時(shí)增量式屬性約簡(jiǎn)比較
按照第4.3.2節(jié)對(duì)數(shù)據(jù)集構(gòu)建6次減少相同數(shù)據(jù)量的更新方式,將所有增量式算法分別進(jìn)行屬性約簡(jiǎn),當(dāng)數(shù)據(jù)集完成最后一次動(dòng)態(tài)減少后,所有算法的約簡(jiǎn)集分類精度見(jiàn)表6,約簡(jiǎn)集長(zhǎng)度比較結(jié)果見(jiàn)表7。統(tǒng)計(jì)數(shù)據(jù)集每次更新時(shí)增量式屬性約簡(jiǎn)的計(jì)算用時(shí),重復(fù)進(jìn)行實(shí)驗(yàn)30次,其平均實(shí)驗(yàn)結(jié)果如圖8所示。
表5 對(duì)象增加時(shí)增量式算法的屬性約簡(jiǎn)集分類精度比較Tab.5 Comparison of classification accuracy of the attribute reduction set of the incremental algorithms when objects are increased
表6 對(duì)象減少時(shí)增量式算法的屬性約簡(jiǎn)集分類精度比較Tab.6 Comparison of classification accuracy of attribute reduction set of incremental algorithms when objects are reduced
表7 對(duì)象減少時(shí)增量式算法的屬性約簡(jiǎn)集長(zhǎng)度比較Tab.7 Length comparison of attribute reduction set for incremental algorithms when objects are reduced
在表7的實(shí)驗(yàn)結(jié)果中,除數(shù)據(jù)集W ine和M usk外,本文增量式算法有著更小的屬性約簡(jiǎn)集長(zhǎng)度。在表6的實(shí)驗(yàn)結(jié)果中:除數(shù)據(jù)集W ine外,本文增量式算法的SVM分類精度高于其余算法;除數(shù)據(jù)集Chess和Musk外,本文增量式算法的kNN分類精度高于其余算法。圖8的實(shí)驗(yàn)結(jié)果與圖7類似,本文增量式算法整體上有著最少的增量式屬性約簡(jiǎn)用時(shí)。表6、7和圖8的實(shí)驗(yàn)結(jié)果表明,在不完備混合型有序信息系統(tǒng)對(duì)象減少的情形下,本文增量式算法同樣有著更高的增量式屬性約簡(jiǎn)性能,其原因也與第4.4.1節(jié)類似。
圖8 對(duì)象減少時(shí)增量式屬性約簡(jiǎn)算法的用時(shí)比較Fig. 8 Time comparison of the incremental attribute reduction algorithms when objects are reduced
增量式屬性約簡(jiǎn)是當(dāng)前屬性約簡(jiǎn)研究的重點(diǎn)方向,針對(duì)有序信息系統(tǒng)的不完備性和混合性,通過(guò)鄰域優(yōu)勢(shì)條件熵作為啟發(fā)式函數(shù)提出一種增量式屬性約簡(jiǎn)算法。提出不完備混合型有序信息系統(tǒng)下的鄰域優(yōu)勢(shì)粗糙集模型,并設(shè)計(jì)出一種鄰域優(yōu)勢(shì)條件熵的非增量式屬性約簡(jiǎn)算法;分別研究了對(duì)象增加和減少情形下鄰域優(yōu)勢(shì)條件熵的增量式學(xué)習(xí)框架;提出了不完備混合型有序信息系統(tǒng)的增量式屬性約簡(jiǎn)算法。綜合不完備混合型有序信息系統(tǒng)下對(duì)象變化的動(dòng)態(tài)屬性約簡(jiǎn)實(shí)驗(yàn),證明了本文提出的增量式屬性約簡(jiǎn)算法具有更高的屬性約簡(jiǎn)性能。同時(shí),通過(guò)與同類型增量式屬性約簡(jiǎn)算法相比,證明了本文增量式屬性約簡(jiǎn)算法具有更高的優(yōu)越性。在未來(lái)的工作中,將嘗試對(duì)不完備混合型有序信息系統(tǒng)屬性的變化進(jìn)行增量式屬性約簡(jiǎn)的研究。
附錄見(jiàn)本刊網(wǎng)絡(luò)版(http://jsuese.ijournals.cn/jsuese_cn/ch/reader/view_abstract.aspx?file_no=202201214&flag=1),掃描標(biāo)題旁的二維碼可閱讀網(wǎng)絡(luò)全文。