屬性值細化的矩陣增量約簡算法

李 丹

成都東軟學院 計算機科學與技術系，四川 青城山 611844

屬性值細化的矩陣增量約簡算法

李 丹

成都東軟學院 計算機科學與技術系，四川 青城山 611844

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

屬性值細化；增量學習；屬性約簡；粗糙集；知識粒度

1 概述

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

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

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

2 粗糙集的相關知識

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

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

3 知識粒度約簡算法

3.1 知識粒度基本知識

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

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

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

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

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

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

3.2 基于知識粒度的啟發式約簡算法

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

算法1基于矩陣的啟發式約簡算法

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

輸出 屬性約簡REDU。

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

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

步驟3P←REDU，當GDU(D|P)≠GDU(D|C)，計算屬性a(a∈C-P)相對于屬性P的重要性（符合定義7），依次循環選取重要性最大的屬性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，算法結束。

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

4.1 知識粒度的增量機制

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

定義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細化為v。

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

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

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

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

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

4.2 屬性值細化的矩陣增量約簡算法

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

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

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

輸出 屬性P的值細化后的約簡REDU′。

步驟1B←REDC，計算增量關系矩陣

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

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

步驟4 當 GDU′(D|B)≠GDU′(D|C)，計算屬性 a(a∈C-B)相對于屬性B的重要性（符合定義7），依次循環選取重要性最大的屬性添加到 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細化后的約簡REDU，算法結束。

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

5 實驗分析

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

表1 數據集描述

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

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

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

6 結論

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

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

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

[3]梁吉業，曲開社，徐宗本.信息系統的屬性約簡[J].系統工程理論與實踐，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]王磊，洪志全，萬旎.屬性值變化時變精度粗糙集模型中近似集動態更新的矩陣方法研究[J].計算機應用研究，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]劉洋，馮博琴，周江衛.基于差別矩陣的增量式屬性約簡完備算法[J].西安交通大學學報，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].北京：科學出版社，2001：7-16.

[16]王磊，葉軍.知識粒度計算的矩陣方法及其在屬性約簡中的應用[J].計算機工程與科學，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

國家自然科學基金聯合項目（No.U1230117）。

李丹（1973—），男，講師，研究方向：粒計算，云計算，移動應用開發，E-mail：lidan@nsu.edu.cn。

2016-05-18

2016-06-28

1002-8331（2017）21-0068-04

CNKI網絡優先出版：2016-11-21,http://www.cnki.net/kcms/detail/11.2127.TP.20161121.1652.020.html