面向成組對象集的增量式屬性約簡算法

錢進，朱亞炎

(1.江蘇理工學院 計算機工程學院，江蘇 常州 213015； 2. 南京信息工程大學 江蘇省大數據分析技術重點實驗室，江蘇 南京 210044)

?

面向成組對象集的增量式屬性約簡算法

錢進1,2，朱亞炎1

(1.江蘇理工學院 計算機工程學院，江蘇 常州 213015； 2. 南京信息工程大學 江蘇省大數據分析技術重點實驗室，江蘇 南京 210044)

現實世界中數據集都是動態變化的，非增量式屬性約簡方法從頭重新計算原始數據集，而且未考慮先前約簡結果中的信息，將耗費大量的時間和空間。為此，討論了動態數據環境下約簡的不變性，提出了一種面向成組對象集的增量式屬性約簡算法，利用先前約簡中信息來快速獲取強傳承性的約簡，從而提高增量式學習算法效率。最后，將該算法與非增量式約簡方法和面向單個對象的增量式約簡方法在UCI數據集和人工數據集上進行了相關比較。實驗結果表明，面向成組對象的增量式屬性約簡算法能夠快速處理動態數據，具有較好的約簡傳承性。

粗糙集；屬性約簡；成組對象集；約簡傳承性；增量式學習

中文引用格式：錢進，朱亞炎. 面向成組對象集的增量式屬性約簡算法[J]. 智能系統學報， 2016, 11(4): 496-502.

英文引用格式：QIAN Jin， ZHU Yayan. An incremental attribute reduction algorithm for group objects[J]. CAAI Transactions on Intelligent Systems, 2016, 11(4): 496-502.

屬性約簡是Rough集理論中的核心問題之一，也是知識獲取的關鍵步驟。目前，許多學者已提出了一些有效的屬性約簡算法[1-4]，如基于正區域的屬性約簡算法、基于差別矩陣的屬性約簡算法、基于信息熵的屬性約簡算法等，但這些算法都是針對靜態的決策表，不適合處理動態的信息系統?，F實世界是不斷變化的，數據會源源不斷地添加到原始決策表中，一般不希望將原有的決策表和新產生的增量數據整合成一個新的決策表進行屬性約簡，因為這樣會對原有數據不斷地進行重復的計算。因此，如何利用原決策表中所含的信息并結合增量數據來進行屬性約簡成為粗糙集理論新的挑戰。

數據的動態變化主要有3種情況：1)屬性集保持不變而對象不斷增加[5-8]；2)對象集保持不變而屬性集不斷增加[9]；3)對象集和屬性集同時增加[10]。本文著重研究第1種情況的增量式屬性約簡問題，尤其研究適合大規模數據集的約簡問題。文獻[5]提出了基于正區域的屬性約簡增量式更新算法，提高了屬性約簡算法效率；文獻[6]提出了基于差別矩陣的屬性約簡增量式更新算法；文獻[7]提出了不使用可辨識矩陣的增量式核更新算法以及屬性約簡算法；文獻[8]針對現有增量式屬性約簡算法中存在的約簡傳承性差以及不完備現象，提出了基于標記可辨識矩陣的增量式屬性約簡算法。然而，這些算法不適宜解決每次增加批量對象的問題。文獻[11]提出了面向成組對象集的3種增量式信息熵屬性約簡算法；文獻[12]充分利用先前約簡中信息和計數排序算法快速更新批量對象的約簡，降低計算復雜度；文獻[13-14]探討了混合屬性約簡算法以及利用MapReduce進行面向大規模數據集的屬性約簡方法。

為提高增量式學習算法效率[15]和約簡傳承性，本文構建了面向成組對象的增量式屬性約簡算法，利用原始決策表的一個候選約簡來快速地更新新增決策表的約簡，這樣既提高了約簡的傳承性，又有效地利用了原有知識，提高了增量式學習算法效率。

1　粗糙集概念

下面簡要介紹本文主要用到的一些Rough集的基本概念[1,9,11,13-14]。

IND(R)=

關系IND(R)構成了U的一個劃分, 用U/IND(R)表示, 簡記為U/R。U/R中的任何元素[x]R= {y| ?a∈R,f(x,a)=f(y,a)}稱為等價類。不失一般性, 假設決策表S僅有一個決策屬性D=g0gggggg, 其決策屬性值映射為1, 2，…, k,由D導出的U上劃分記為U/ D={D1, D2, …,Dk}，其中，Di={x∈U| f(x,D)=i}，i = 1, 2, …, k。

U -POSA(D)

定義4 在決策表S中，一個屬性集Red?C是C的D-約簡，如果

1)POSRed(D)=POSC(D)；

2)?a∈Red，POSRed-{a}(D)≠POSRed(D)。

定義5 在決策表S中，A?C，?c∈A，在正區域下屬性c重要性定義為

定義6 在決策表S中，A?C，?c∈C-A，在正區域下屬性c重要性定義為

Sigouter(c,A,D)=γA∪{c}(D) -γA(D)

定義7 設Red為決策表S的候選屬性約簡，NewRed為新增樣本之后的新約簡，則單次增量式約簡的傳承率(inheritance rate, IR)定義為

假設進行了w次增量式約簡，則平均傳承率(inheritance rate average，IRA)定義為

在約簡過程中，傳承率越高則約簡集的變化越小，對原始規則集的影響將越小。如果傳承率為1，說明新增的對象不影響原始的規則集；如果傳承率為0，則新的約簡集與原來的約簡集完全不同，這時需全部更新所有規則。

2　面向成組對象集的增量式屬性約簡算法

給定決策表S=U，C∪D，V，f, 一個約簡Red?C。新對象y加入到決策表S中，U′=U∪{y},將此時的新決策表標記為S′。一種最簡單的屬性約簡增量式更新算法是直接計算S′的約簡。顯然，這種方法的屬性約簡效率比較低下，因為需要重復計算原始決策表S中的等價類。為此，如何在已有的約簡Red的基礎上快速更新約簡則成為本文主要研究內容。為此，如何在已有的約簡Red的基礎上快速更新約簡則成為本文主要研究內容。為方便討論，假設U/Red={X1，X2，…,}，用表示決策表S由約簡Red導出的正區域，用表示決策表S由約簡Red導出的邊界域，即。

當新對象y加入到S中，主要分為兩類情況：

1)y無法用Red區分，當且僅當?x∈U使得?a∈Red[f(x,a)=f(y,a)];

2)y可以用Red區分，當且僅當?x∈U使得?a∈Red[f(x,a)≠f(y,a)]。

根據上述分析，可以得出以下定理。

定理3給定決策表S和新增對象y，Red是決策表S的約簡，y?U/C∧y∈U/Red，若?z∈Xi[f(z,Red)=f(y,Red)]∧f(z,d)≠f(y,d)，則Red不是決策表S′的約簡。

下面給出面向單個對象的增量式屬性約簡算法，如算法1所示。

算法1面向單個對象的增量式屬性約簡算法

輸入一個決策表，S；一個新增對象，y；一個約簡，RedU；

輸出一個新的約簡，RedU∪{y}。

1)A= RedU；

{For each attributec∈C-A

A=A∪ {a}；

8)For each attributec∈A

9)RedU∪{y}=A，輸出RedU∪{y}。

復雜度分析算法的時間復雜度主要集中在2)、7)和8)。利用文獻[13]中計數排序算法和簡化決策表處理方式，2)的時間復雜度為O(|C||U|)，7)的時間復雜度為O(|C||U|)，8)的最壞時間復雜度為O(|C|2(|U/C|+1))，故整個算法時間復雜度為max(O(|C||U|),O(|C|2(|U/C|+1)))，空間復雜度為O(|U|)。

算法2面向成組對象集的增量式屬性約簡算法(GIAR)

輸入一個決策表，S；一個候選約簡，RedU；新增對象集，U△；

輸出一個新的約簡，RedU∪U△。

4)如果h=0 和h′=0，轉5；

//新增對象集中約簡不能區分的矛盾對象

7)fori=1 toh

//累加同一等價類中約簡不能區分的矛盾對象

{For each attributec∈C-A

//若這樣的屬性有多個，則任選一個；

A=A∪ {a}；}

10)For each attributec∈A

11)RedU∪U△=A, 輸出RedU∪U△。

例1表1給出一個決策表S和新增對象集U△，決策表S包含3個約簡{c2c1}、{c2c3}和{c3c4}，分別計算約簡的變化情況，如表2所示。

表2　原始決策表S和新增對象集U△

表2　約簡變化與約簡傳承性比較

3　實驗驗證

為了評價所提出的增量式約簡算法效率和約簡傳承性，使用Windows 7操作系統，2.4 GHz處理器和16 GB內存的計算機和Visual C#2012實現了相關實驗。由于所提出的約簡算法和經典的約簡算法僅能夠處理離散型屬性，先采用Rosetta軟件(http://www.lcb.uu.se/tools/rosetta)填充缺省值，并將數值型屬性連續值離散化；然后，分別在4個來自UCI Repository機器學習公共數據集和2個人工數據集進行實驗。每個數據集僅有1個決策屬性。人工數據集Dataset1每個屬性值為1～5；而人工數據集Dataset2每個屬性值為1～9。表3描述了6個數據集特性。原始數據集的50%作為基本數據集，剩下50%數據集的20%、40%、60%、80%和100%作為5個增量數據集，非增量式屬性約簡算法(NIAR)、面向單個屬性的增量式屬性約簡算法(SIAR)和面向成組數據集的屬性增量式約簡算法(GIAR)實驗結果如圖1所示。

圖1　增量式約簡算法和非增量式約簡算法運行時間比較Fig.1　Comparison of incremental and non-incremental Reduction algorithms on running time

由于面向單個屬性的增量式約簡算法(SIAR)對大規模數據集運行時間太長，圖1(e)-(f)未標出。從圖1可以看出，SIAR算法比GIAR算法運行時間更長，而GIAR算法的運行時間明顯少于NIAR算法，特別對于較大數據集，算法的效果越明顯。實驗結果表明，所提出的面向成組對象集的增量式約簡算法是可行的。

表3　6個數據集特性

下面比較約簡長度與約簡的傳承性。圖2給出了6個數據集在不同增長比例下的約簡長度。在4個數據集上，約簡不變，則只需要生成新增數據集的規則，原始規則集不必重新生成，而在另外兩個數據集上，約簡長度稍微增長，這主要因為新增對象與原始數據集引起沖突，需要另外的屬性集來細分原始對象，這時除了生成新規則集外，還需要修改部分原始規則。

圖2　約簡長度比較Fig.2　Comparison of Reduct length

表4給出了約簡的傳承性。從表4可以看出，利用先前約簡中信息所得到的新約簡結果變化不大，約簡傳承性較好。

表4　約簡傳承性比較

4　結論

在數據挖掘中, 屬性約簡僅僅是數據預處理中一個過程，挖掘規則才是最終的輸出。因此，充分利用先前約簡中信息不僅能夠快速得到約簡，而且更容易地利用已有知識進行規則更新。本文所提出的面向成組對象集的增量式約簡方法就是充分利用先前約簡中信息來快速更新約簡，不僅具有較高的約簡傳承率，而且可以快速進行增量式學習，具有良好的實用性。作者下一步將利用MapReduce進一步研究大規模數據集增量式屬性約簡方法。

[1]PAWLAK Z. Rough sets[J]. International journal of computer & information sciences, 1982, 11(5): 341-356.

[2]SKOWRON A, RAUSZER C. The discernibility matrices and functions in information systems[M]//SLOWINSKI R. Intelligent Decision Support, Handbook of Applications and Advances of the Rough Sets Theory. Netherlands: Springer, 1992: 311-362.

[3]苗奪謙, 胡桂榮. 知識約簡的一種啟發式算法[J]. 計算機研究與發展, 1999, 36(6): 681-684.

MIAO Duoqian, HU Guirong. A heuristic algorithm for reduction of knowledge [J]. Journal of computer research and development, 1999, 36(6): 681-684.

[4]王國胤, 于洪, 楊大春. 基于條件信息熵的決策表約簡[J]. 計算機學報, 2002, 25(7): 759-766.

WANG Guoyin, YU Hong, YANG Dachun. Decision table reduction based on conditional information entropy [J]. Chinese journal of computers, 2002, 25(7): 759-766.

[5]HU Feng, WANG Guoyin, HUANG Hai, et al. Incremental attribute reduction based on elementary sets[M]//SLEZAK D, WANG Guoyin, SZCZUKA M, et al. Proceedings of the 10th International Conference on Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing. Berlin Heidelberg: Springer, 2005: 185-193.

[6]楊明. 一種基于改進差別矩陣的屬性約簡增量式更新算法[J]. 計算機學報, 2007, 30(5): 815-822.

YANG Ming. An incremental updating algorithm for attribute reduction based on improved discernibility matrix[J]. Chinese journal of computers, 2007, 30(5) 815-822.

[7]馮少榮, 張東站. 一種高效的增量式屬性約簡算法[J]. 控制與決策, 2011, 26(4): 495-500.

FENG Shaorong, ZHANG Dongzhan. Effective incremental algorithm for attribute reduction[J]. Control and decision, 2011, 26(4): 495-500.

[8]尹林子, 陽春華, 王曉麗, 等. 基于標記可辨識矩陣的增量式屬性約簡算法[J]. 自動化學報, 2014, 40(3): 397-404.

YIN Linzi, YANG Chunhua, WANG Xiaoli, et al. An incremental algorithm for attribute reduction based on labeled discernibility matrix[J]. Acta automatica sinica, 2014, 40(3)： 397-404.

[9]SHU Wenhao, SHEN Hong. Updating attribute reduction in incomplete decision systems with the variation of attribute set[J]. International journal of approximate reasoning, 2014, 55(3): 867-884.

[10]CHEN Hongmei, LI Tianrui, LUO Chuan, et al. A Decision-theoretic rough set approach for dynamic data mining[J]. IEEE transactions on fuzzy systems, 2015, 23(6): 1958-1970.

[11]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)： 294-308.

[12]QIAN Jin, YE Feiyue, LV Ping. An incremental attribute reduction algorithm in decision table[C]//Proceedings of the 7th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD). Yantai, China: IEEE, 2010, 4: 1848-1852.

[13]QIAN Jin, MIAO Duoqian, ZHANG Zehua, et al. Hybrid approaches to attribute reduction based on indiscernibility and discernibility relations[J]. International journal of approximate reasoning, 2011, 52(2): 212-230.

[14] QIAN Jin, MIAO Duoqian, ZHANG Zehua, et al. Parallel attribute reduction algorithms using MapReduce [J]. Information sciences, 2014, 279: 671-690.

[15]康向平, 苗奪謙. 一種基于概念格的集值信息系統中的知識獲取方法[J]. 智能系統學報, 2016, 11(3): 287-293.

KANG Xiangping, MIAO Duoqian. A knowledge acquisition method based on concept latticein set-valued information systems[J]. CAAI transactions on intelligent systems, 2016, 11(3): 287-293.

錢進，男，1975年生，副教授，博士，主要研究方向為粗糙集、粒計算、云計算、大數據等。發表學術論文40余篇，其中被SCI、EI檢索20余篇。

朱亞炎，男，1994年生，主要研究方向為粗糙集、云計算等。

An incremental attribute reduction algorithm for group objects

QIAN Jin1,2， ZHU Yayan1

(1. School of Computer Engineering, Jiangsu University of Technology, Changzhou 213015, China; 2. Jiangsu Key Laboratory of Big Data Analysis Technology /B-DAT, Nanjing University of Information Science & Technology, Nanjing 210044, China)

Real-world datasets change in size dynamically. Non-incremental attribute reduction methods usually need to re-compute source data when obtaining a new reduction without considering the information in the existing reduction, which consumes a great deal of computational time and storage space. Therefore, in this paper, some reduction invariance properties for dynamic datasets are discussed. An incremental attribute reduction algorithm for group objects using the previous reduction is proposed to quickly update a reduction with high inheritance rate and thus improve the efficiency of incremental learning. Finally, the incremental approach proposed is compared with an existing incremental attribute reduction algorithm for a single object, the non-incremental attribute reduction algorithms on the UCI, and synthetic datasets. Experimental results show that this incremental attribute reduction algorithm for group objects can deal with dynamic data rapidly, as it has better inheritance of reduction.

rough set theory; attribute Reduction; group objects; inheritance rate of Reduct; incremental learning

10.11992/tis.201606005

網絡出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160808.0830.008.html

2014-06-02. 網絡出版日期：2014-08-08.

江蘇省自然科學基金項目(BK20141152);教育部人文社會科學研究青年基金項目(15YJCZH129);江蘇省青藍工程項目;江蘇省大數據分析技術重點實驗室開放基金項目 (KXK1402); 江蘇理工學院校級大學生創新項目(KYX15017).

錢進. E-mail：qjqjlqyf@163.com.

TP181

A

1673-4785(2016)04-0496-07