李 丹

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

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

李 丹

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

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

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

1 概述

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

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

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

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

定義1[15]假設(shè)一個信息系統(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)是一個決策表，U 為論域且U/C={X1,X2,…,Xm}，條件屬性C的知識粒度被定義為

3 知識粒度約簡算法

3.1 知識粒度基本知識

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

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

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

定義9[1]假設(shè)S=(U,A=C?D,V,f)是一個決策表，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計算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)，計算屬性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中的每一個屬性a，計算知識粒度GDU(D|P-{a})，如果GDU(D|P-{a})=GDU(D|C)，則 P←P-{a}。

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

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

4.1 知識粒度的增量機制

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

定義10[5]S=(U,A=C?D,V,f)是一個決策表，B?A,B≠?,al∈B ，其中屬性 al的值域為 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)是一個決策表，是U 的關(guān)系矩陣。假設(shè)屬性ai的屬性值發(fā)生細(xì)化，U′表示新的論域，則細(xì)化后的關(guān)系矩陣的元素被定義為：

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

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

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

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

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

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

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

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

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

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

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

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

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

5 實驗分析

為了測試本文提出算法2的性能，把算法2的約簡時間和算法1的約簡時間作比較，并從UCI數(shù)據(jù)集選取Lung Cancer和 ticdata2000作為實驗仿真數(shù)據(jù)集，數(shù)據(jù)集描述如表1，實驗仿真的環(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ù)據(jù)集均分成兩部分，其中有一部分作為基本數(shù)據(jù)集，分別對另一部分?jǐn)?shù)據(jù)集的10%、20%、30%、40%、50%數(shù)據(jù)的屬性值進行細(xì)化，分別用增量約簡算法和非增量約簡算法運行每個數(shù)據(jù)集，實驗結(jié)果如圖1所示，縱軸表示算法的計算時間，橫軸表示數(shù)據(jù)集對象屬性值細(xì)化的百分?jǐn)?shù)。

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

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

6 結(jié)論

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

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

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

[3]梁吉業(yè)，曲開社，徐宗本.信息系統(tǒng)的屬性約簡[J].系統(tǒng)工程理論與實踐，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]王磊，洪志全，萬旎.屬性值變化時變精度粗糙集模型中近似集動態(tài)更新的矩陣方法研究[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é)報，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]王磊，葉軍.知識粒度計算的矩陣方法及其在屬性約簡中的應(yīng)用[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)合項目（No.U1230117）。

李丹（1973—），男，講師，研究方向：粒計算，云計算，移動應(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