屬性值細(xì)化的矩陣增量約簡算法

李 丹

成都東軟學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，四川 青城山 611844

屬性值細(xì)化的矩陣增量約簡算法

李 丹

成都東軟學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，四川 青城山 611844

現(xiàn)實(shí)生活中許多數(shù)據(jù)庫都是動(dòng)態(tài)變化的，為了獲取新的知識，傳統(tǒng)的方法需要重復(fù)計(jì)算，耗時(shí)巨大。為了克服這個(gè)缺陷，有效處理動(dòng)態(tài)數(shù)據(jù)，許多學(xué)者提出了增量學(xué)習(xí)方法。針對決策表屬性值動(dòng)態(tài)變化，提出了基于屬性值細(xì)化的矩陣增量約簡算法，當(dāng)一部分屬性值被細(xì)化時(shí)，同非增量約簡方法相比，增量方法能快速找到新的約簡，最后通過UCI數(shù)據(jù)進(jìn)行性能測試，實(shí)驗(yàn)仿真結(jié)果表明所提增量約簡算法是有效的。

屬性值細(xì)化；增量學(xué)習(xí)；屬性約簡；粗糙集；知識粒度

1 概述

在現(xiàn)實(shí)生活中，許多領(lǐng)域的數(shù)據(jù)如經(jīng)濟(jì)研究、社會(huì)調(diào)研和醫(yī)藥研究的數(shù)據(jù)都是動(dòng)態(tài)變化的，使用傳統(tǒng)獲取知識的方法處理這些數(shù)據(jù)需要重復(fù)操作才能獲得新知識，重復(fù)操作造成時(shí)間消耗巨大，故傳統(tǒng)獲取知識的方法處理動(dòng)態(tài)數(shù)據(jù)效果不好。為了克服這些缺陷，有效處理動(dòng)態(tài)數(shù)據(jù)，許多研究者提出了增量學(xué)習(xí)方法，該方法能夠有效利用以前的知識，不需要對全部數(shù)據(jù)重新學(xué)習(xí)，這在一定程度上更能滿足實(shí)際需要。屬性約簡也稱為特征選擇，它是數(shù)據(jù)處理的一種有效技術(shù)，已經(jīng)被廣泛應(yīng)用到模式識別、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)領(lǐng)域，研究者提出了很多屬性約簡的方法[1-3]，但是這些方法都是處理靜態(tài)數(shù)據(jù)集的，對于動(dòng)態(tài)變化的數(shù)據(jù)需要重復(fù)計(jì)算，造成時(shí)間和空間的浪費(fèi)。

增量約簡算法可以有效處理動(dòng)態(tài)數(shù)據(jù)，科學(xué)研究者對動(dòng)態(tài)約簡方法已做了大量的工作。Zeng等在模糊決策信息系統(tǒng)中，研究了屬性集添加或刪除時(shí)，近似空間中知識粒度的變化規(guī)律，提出了屬性集動(dòng)態(tài)變化時(shí)動(dòng)態(tài)特征提取方法[4]；王磊等從矩陣的視角探討信息系統(tǒng)動(dòng)態(tài)知識更新的有效方法和途徑，提出了信息系統(tǒng)的屬性值發(fā)生變化時(shí)變精度粗糙集模型中概念上、下近似集增量式更新的矩陣方法并構(gòu)造出相應(yīng)的算法[5]；Wang等根據(jù)三種信息熵概念，定義了信息熵增量機(jī)制，針對屬性值動(dòng)態(tài)變化情況，提出了一種有效特征選擇方法[6]；劉洋等構(gòu)造了差別矩陣的增量機(jī)制，在對象動(dòng)態(tài)增加下，提出了一種基于差別矩陣的增量約簡完備算法[7]；Luo等在集值有序決策系統(tǒng)中，構(gòu)造了基于矩陣的上、下近似集計(jì)算方法，并提出了屬性泛化時(shí)近似集的動(dòng)態(tài)更新算法，利用UCI公共數(shù)據(jù)集測試了算法的性能[8]；Chen等在不完備信息系統(tǒng)中，定義了最小辨識屬性集，并在屬性值粗化細(xì)化時(shí)，分析了最小辨識屬性集及規(guī)則的演化性質(zhì)，提出了不協(xié)調(diào)決策系統(tǒng)中基于粗糙集的規(guī)則增量更新算法[9]。Jing等分析了屬性增加時(shí)知識粒度的增量機(jī)制，提出了增量屬性約簡算法[10]；針對決策粗糙集模型，Luo等提出了矩陣計(jì)算近似集的增量算法[11]；Jing等分析了對象增加時(shí)知識粒度的增量機(jī)制，提出了基于知識粒度的增量約簡方法[12]；Shu等針對不完備信息系統(tǒng)，提出了基于正區(qū)域的增量約簡算法[13]；針對對象變化時(shí)，Liang等提出了基于信息熵的增量約簡算法[14]。根據(jù)上面分析，基于屬性值細(xì)化的矩陣增量式約簡算法研究較少。

矩陣是一種非常強(qiáng)大的數(shù)學(xué)工具，它的特點(diǎn)是直觀和簡明，在工程和科學(xué)研究領(lǐng)域應(yīng)用比較廣泛。知識粒度在粗糙集中用來表示信息的不確定程度，許多研究者已經(jīng)把它應(yīng)用到啟發(fā)式屬性約簡中，在現(xiàn)實(shí)生活中，許多數(shù)據(jù)庫的數(shù)據(jù)都是動(dòng)態(tài)變化的，靜態(tài)約簡算法在處理這些數(shù)據(jù)會(huì)消耗巨大的時(shí)間和空間，為了提高計(jì)算速度，本文提出了一種屬性值細(xì)化的矩陣增量式約簡算法，當(dāng)決策表的某些屬性發(fā)生細(xì)化時(shí)，給出了知識粒度的增量機(jī)制，使用UCI數(shù)據(jù)集對該算法進(jìn)行了測試，實(shí)驗(yàn)結(jié)果表明所提的增量算法是有效的。

2 粗糙集的相關(guān)知識

定義1[15]假設(shè)一個(gè)信息系統(tǒng)S=(U,A=C?D,V,f)是四元組，U為論域，C為條件屬性集且D為決策屬性集，，其中Va為屬性a的值，f:U×C?D→V 是信息函數(shù)，且a∈C?D，x∈U有 f(x,a)∈Va。

定義2[1]假設(shè)S=(U,A=C?D,V,f)是一個(gè)決策表，U 為論域且U/C={X1,X2,…,Xm}，條件屬性C的知識粒度被定義為

3 知識粒度約簡算法

3.1 知識粒度基本知識

定義3[5]假設(shè)S=(U,A=C?D,V,f)是一個(gè)決策表，且U/C={X1,X2,…,Xm}，RC是U 的一個(gè)等價(jià)關(guān)系，則關(guān)系矩陣的元素被定義為：

定義4[16]假設(shè)S=(U,A=C?D,V,f)是一個(gè)決策表，且U/C={X1,X2,…,Xm}，條件屬性C的知識粒度被定義為是關(guān)系矩陣的平均值。

定義8[1]假設(shè)S=(U,A=C?D,V,f)是一個(gè)決策表，決策表S的核被定義為C,D)＞ 0}。

定義9[1]假設(shè)S=(U,A=C?D,V,f)是一個(gè)決策表，B?C，B為決策表S的屬性約簡當(dāng)且僅當(dāng)：

（1）GD(D|B)=GD(D|C)；

（2）對于?a∈B，使得GD(D|B-{a})≠GD(D|C)。

3.2 基于知識粒度的啟發(fā)式約簡算法

根據(jù)上面定義的矩陣表示形式，構(gòu)造了一種基于知識粒度的啟發(fā)式約簡算法1描述如下：

算法1基于矩陣的啟發(fā)式約簡算法

輸入 決策表S=(U,A=C?D,V,f)；

輸出 屬性約簡REDU。

步驟1根據(jù)定義8計(jì)算S的核CoreC(D)，REDU←CoreC(D)。

步驟2如果GDU(D|REDU)=GDU(D|C)，轉(zhuǎn)跳到步驟5，否則轉(zhuǎn)跳到步驟3。

步驟3P←REDU，當(dāng)GDU(D|P)≠GDU(D|C)，計(jì)算屬性a(a∈C-P)相對于屬性P的重要性（符合定義7），依次循環(huán)選取重要性最大的屬性a0=max(SigoutterU(a,P,D))添加到P中，即P←P?{a0}，直到GDU(D|P)=GDU(D|C)為止。

步驟4從后向前依次遍歷P中的每一個(gè)屬性a，計(jì)算知識粒度GDU(D|P-{a})，如果GDU(D|P-{a})=GDU(D|C)，則 P←P-{a}。

步驟5REDU←P，輸出S屬性約簡REDU，算法結(jié)束。

4 基于屬性值細(xì)化的矩陣增量式約簡算法

4.1 知識粒度的增量機(jī)制

當(dāng)信息系統(tǒng)的屬性值發(fā)生細(xì)化時(shí)，用算法1計(jì)算新決策表的屬性約簡需要重復(fù)計(jì)算知識粒度，造成時(shí)間和空間消耗巨大。為了提高計(jì)算速度，在較短的時(shí)間內(nèi)快速找到新決策表的屬性約簡，提出了一種基于屬性值細(xì)化的矩陣增量式約簡算法。

定義10[5]S=(U,A=C?D,V,f)是一個(gè)決策表，B?A,B≠?,al∈B ，其中屬性 al的值域?yàn)?Vl，若有 f(xk,al)=v，且v?Vl，則稱屬性值 f(xi,al)=v細(xì)化為v。

記 IX-Y={i|ui∈X-Y}，IY={i|ui∈Y}，其中 IX-Y表示集合X-Y中元素下標(biāo)組成的集合，IY表示集合Y中元素下標(biāo)組成的集合。

定義11[5]S=(U,A=C?D,V,f)是一個(gè)決策表，是U 的關(guān)系矩陣。假設(shè)屬性ai的屬性值發(fā)生細(xì)化，U′表示新的論域，則細(xì)化后的關(guān)系矩陣的元素被定義為：

定理1S=(U,A=C?D,V,f)是一個(gè)決策表，GDU(C)是決策表?xiàng)l件屬性C的知識粒度。假設(shè)屬性ai的屬性值發(fā)生細(xì)化，U′表示新的論域，增量關(guān)系矩陣為則決策表的知識粒度為：

定理2S=(U,A=C?D,V,f)是一個(gè)決策表，GDU(C?D)是決策表?xiàng)l件和決策屬性C?D的知識粒度。假設(shè)屬性ai的屬性值發(fā)生細(xì)化，U′表示新的論域，增量關(guān)系矩陣為則決策表的知識粒度為：

定理3S=(U,A=C?D,V,f)是一個(gè)決策表，GDU(D?C)是條件屬性C關(guān)于決策屬性D的相對知識粒度。假設(shè)屬性ai的屬性值發(fā)生細(xì)化，U′表示新的論域，增量關(guān)系矩陣為，則屬性C關(guān)于D的相對知識粒度為：

4.2 屬性值細(xì)化的矩陣增量約簡算法

根據(jù)上面所提的知識粒度的增量機(jī)制，提出了一種基于屬性值細(xì)化的矩陣增量式約簡算法2，假設(shè)有一個(gè)動(dòng)態(tài)決策表，當(dāng)某些屬性的值發(fā)生了細(xì)化，首先利用知識粒度增量機(jī)制計(jì)算變化后新決策表的知識粒度，然后在原來決策表約簡的基礎(chǔ)上，可以快速找到細(xì)化后決策表的約簡，算法2描述如下：

算法2一種屬性值細(xì)化的矩陣增量約簡算法

輸入 決策表S=(U,A=C?D,V,f)，屬性P細(xì)化前的約簡REDU，屬性P的值發(fā)生了細(xì)化。

輸出 屬性P的值細(xì)化后的約簡REDU′。

步驟1B←REDC，計(jì)算增量關(guān)系矩陣

步驟2計(jì)算屬性P的值發(fā)生了細(xì)化后的知識粒度GDU′(D|B)，GDU′(D|C)（根據(jù)定理1～3）。

步驟 3 如果 GDU′(D|B)=GDU′(D|C)，轉(zhuǎn)跳到步驟6，否則轉(zhuǎn)跳到步驟4。

步驟4 當(dāng) GDU′(D|B)≠GDU′(D|C)，計(jì)算屬性 a(a∈C-B)相對于屬性B的重要性（符合定義7），依次循環(huán)選取重要性最大的屬性添加到 B 中，即 B←B?{a0}，直到 GDU′(D|B)=GDU′(D|C)為止。

步驟5從后向前依次遍歷B中的每個(gè)屬性a，計(jì)算 知 識 粒 度 GDU′(D|B-{a}) ，如 果 GDU′(D|B-{a})=GDU′(D|C)，則 B ←B-{a}。

步驟6REDU′←B，輸出屬性 P細(xì)化后的約簡REDU，算法結(jié)束。

下面對算法1（非增量算法）和算法2（增量算法）的時(shí)間復(fù)雜度進(jìn)行分析，當(dāng)決策表的某個(gè)屬性被細(xì)化后，非增量約簡算法的時(shí)間復(fù)雜度近似為O(|C||U|2)，而增量約簡算法的時(shí)間復(fù)雜度近似為O(|C||X-Y||Y|)，因?yàn)閨X-Y||Y|＜|U|2，所提的矩陣增量約簡算法計(jì)算時(shí)間小于非增量約簡算法所花費(fèi)的時(shí)間。

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

為了測試本文提出算法2的性能，把算法2的約簡時(shí)間和算法1的約簡時(shí)間作比較，并從UCI數(shù)據(jù)集選取Lung Cancer和 ticdata2000作為實(shí)驗(yàn)仿真數(shù)據(jù)集，數(shù)據(jù)集描述如表1，實(shí)驗(yàn)仿真的環(huán)境：CPU Pentium?Dual-Core E5800 3.20 GHz，內(nèi)存：Samsung DDR3 SDRAM，4.0 GB Windows7操作系統(tǒng)，32 bit(JDK1.6.0_20)。

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

在實(shí)驗(yàn)仿真過程中，把每個(gè)數(shù)據(jù)集均分成兩部分，其中有一部分作為基本數(shù)據(jù)集，分別對另一部分?jǐn)?shù)據(jù)集的10%、20%、30%、40%、50%數(shù)據(jù)的屬性值進(jìn)行細(xì)化，分別用增量約簡算法和非增量約簡算法運(yùn)行每個(gè)數(shù)據(jù)集，實(shí)驗(yàn)結(jié)果如圖1所示，縱軸表示算法的計(jì)算時(shí)間，橫軸表示數(shù)據(jù)集對象屬性值細(xì)化的百分?jǐn)?shù)。

通過實(shí)驗(yàn)仿真結(jié)果可以得出，所提屬性值細(xì)化的矩陣增量約簡算法的計(jì)算時(shí)間遠(yuǎn)遠(yuǎn)小于非增量約簡算法的計(jì)算時(shí)間，從而說明本文所提的屬性值細(xì)化的矩陣增量約簡方法是有效的。

圖1 插入多個(gè)屬性集增量和非增量約簡算法消耗時(shí)間的比較

6 結(jié)論

動(dòng)態(tài)數(shù)據(jù)約簡算法研究是人工智能領(lǐng)域中的一個(gè)研究熱點(diǎn)，本文根據(jù)知識粒度的矩陣表示方法，提出了一種屬性值細(xì)化的矩陣增量約簡算法，當(dāng)決策表的屬性值發(fā)生細(xì)化時(shí)，首先通過增量機(jī)制來更新屬性值細(xì)化后決策表的知識粒度，然后在原有約簡的基礎(chǔ)上，可以快速找到新的約簡，通過與非增量約簡算法的比較，實(shí)驗(yàn)結(jié)果表明增量屬性約簡的方法是可行的。下一步研究將考慮在云計(jì)算環(huán)境平臺下如何實(shí)現(xiàn)并行增量的屬性約簡算法。

[1]苖奪謙，范世棟.知識粒度的計(jì)算及其應(yīng)用[J].系統(tǒng)工程理論與實(shí)踐，2002，22（1）：48-56.

[2]王國胤，于洪，楊大春.基于條件信息熵的決策表約簡[J].計(jì)算機(jī)學(xué)報(bào)，2002，25（7）：760-765.

[3]梁吉業(yè)，曲開社，徐宗本.信息系統(tǒng)的屬性約簡[J].系統(tǒng)工程理論與實(shí)踐，2001，21（12）：76-80.

[4]Zeng Anping，Li Tianrui，Liu Dun，et al.A fuzzy rough set approach for incremental feature selection on hybrid information systems[J].Fuzzy Sets and Systems，2014，258：39-60.

[5]王磊，洪志全，萬旎.屬性值變化時(shí)變精度粗糙集模型中近似集動(dòng)態(tài)更新的矩陣方法研究[J].計(jì)算機(jī)應(yīng)用研究，2013，30（7）：2011-2013.

[6]Wang Feng，Liang Jiye，Dang Chuangyin.Attribute reduction for dynamic data sets[J].Applied Soft Computing，2012，18：1-18.

[7]劉洋，馮博琴，周江衛(wèi).基于差別矩陣的增量式屬性約簡完備算法[J].西安交通大學(xué)學(xué)報(bào)，2007，41（2）：158-161.

[8]Luo Chuan，Li Tianrui，Chen Hongmei.Dynamic maintenance of approximations in set-valued ordered decision systems under the attribute generalization[J].Information Sciences，2014，257：210-228.

[9]Chen Hongmei，Li Tianrui，Luo Chuan，et al.A rough set-based method for updating decision rules on attribute values coarsening and refining[J].IEEE Transactions on Knowledge and Data Engineering，2014，26（12）：2886-2899.

[10]Jing Yunge，Li Tianrui，Huang Junfu，et al.An incremental attribute reduction approach based on knowledge granularity under the attribute generalization[J].International Journal of Approximate Reasoning，2016，76：80-95.

[11]Luo Chuan，Li Tianrui，Zhang Yi，et al.Matrix approach to decision-theoretic rough sets for evolving data[J].Knowledge-Based Systems，2016，99：123-134.

[12]Jing Yunge，Li T R，Luo C，et al.An incremental approach for attribute reduction based on knowledge granularity[J].Knowledge-Based Systems，2016，104（C）：24-38.

[13]Shu Wenhao，Shen Hong.Updating attribute reduct in incomplete decision systems with the variation of attribute set[J].International Journal of Approximate Reasoning，2014，55：867-884.

[14]Liang Jiye，Wang Feng，Dang Chuangyin，et al.A group incremental approach to feature selection applying rough set technique[J].IEEE Transactions on Knowledge and Data Engineering，2014，26（2）：1-31.

[15]劉清.Rough set及Rough理論[M].北京：科學(xué)出版社，2001：7-16.

[16]王磊，葉軍.知識粒度計(jì)算的矩陣方法及其在屬性約簡中的應(yīng)用[J].計(jì)算機(jī)工程與科學(xué)，2013，35（3）：98-102.

LI Dan

Department of Computer Science and Technology,Chengdu Neusoft University,Qingchengshan,Sichuan 611844,China

Matrix-based incremental reduction approach with attribute values refining.Computer Engineering and Applications,2017,53（21）：68-71.

In practices,many real data in databases may vary dynamically.One has to run a knowledge acquisition method repeatedly in order to acquire new knowledge.This is very time-consuming.To overcome this deficiency,incremental approaches have been presented to deal with dynamic data set.This paper proposes a matrix-based incremental reduction approach with attribute values refining.When a part of data in a given data set is replaced by some new data,compared with the non-incremental reduction approach,the developed incremental reduction approach can find a new reduct in a much shorter time.Finally,experiments on two data sets downloaded from UCI show that the developed algorithm is effective.

attribute values refining;incremental learning;attribute reduction;rough set;knowledge granularity

A

TP18

10.3778/j.issn.1002-8331.1605-0246

國家自然科學(xué)基金聯(lián)合項(xiàng)目（No.U1230117）。

李丹（1973—），男，講師，研究方向：粒計(jì)算，云計(jì)算，移動(dòng)應(yīng)用開發(fā)，E-mail：lidan@nsu.edu.cn。

2016-05-18

2016-06-28

1002-8331（2017）21-0068-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2016-11-21,http://www.cnki.net/kcms/detail/11.2127.TP.20161121.1652.020.html