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

錢進(jìn)，朱亞炎

(1.江蘇理工學(xué)院 計(jì)算機(jī)工程學(xué)院，江蘇 常州 213015； 2. 南京信息工程大學(xué) 江蘇省大數(shù)據(jù)分析技術(shù)重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210044)

?

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

錢進(jìn)1,2，朱亞炎1

(1.江蘇理工學(xué)院 計(jì)算機(jī)工程學(xué)院，江蘇 常州 213015； 2. 南京信息工程大學(xué) 江蘇省大數(shù)據(jù)分析技術(shù)重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210044)

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

粗糙集；屬性約簡；成組對象集；約簡傳承性；增量式學(xué)習(xí)

中文引用格式：錢進(jìn)，朱亞炎. 面向成組對象集的增量式屬性約簡算法[J]. 智能系統(tǒng)學(xué)報(bào)， 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集理論中的核心問題之一，也是知識獲取的關(guān)鍵步驟。目前，許多學(xué)者已提出了一些有效的屬性約簡算法[1-4]，如基于正區(qū)域的屬性約簡算法、基于差別矩陣的屬性約簡算法、基于信息熵的屬性約簡算法等，但這些算法都是針對靜態(tài)的決策表，不適合處理動態(tài)的信息系統(tǒng)?，F(xiàn)實(shí)世界是不斷變化的，數(shù)據(jù)會源源不斷地添加到原始決策表中，一般不希望將原有的決策表和新產(chǎn)生的增量數(shù)據(jù)整合成一個(gè)新的決策表進(jìn)行屬性約簡，因?yàn)檫@樣會對原有數(shù)據(jù)不斷地進(jìn)行重復(fù)的計(jì)算。因此，如何利用原決策表中所含的信息并結(jié)合增量數(shù)據(jù)來進(jìn)行屬性約簡成為粗糙集理論新的挑戰(zhàn)。

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

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

1　粗糙集概念

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

IND(R)=

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

U -POSA(D)

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

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

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

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

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

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

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

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

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

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

給定決策表S=U，C∪D，V，f, 一個(gè)約簡Red?C。新對象y加入到?jīng)Q策表S中，U′=U∪{y},將此時(shí)的新決策表標(biāo)記為S′。一種最簡單的屬性約簡增量式更新算法是直接計(jì)算S′的約簡。顯然，這種方法的屬性約簡效率比較低下，因?yàn)樾枰貜?fù)計(jì)算原始決策表S中的等價(jià)類。為此，如何在已有的約簡Red的基礎(chǔ)上快速更新約簡則成為本文主要研究內(nèi)容。為此，如何在已有的約簡Red的基礎(chǔ)上快速更新約簡則成為本文主要研究內(nèi)容。為方便討論，假設(shè)U/Red={X1，X2，…,}，用表示決策表S由約簡Red導(dǎo)出的正區(qū)域，用表示決策表S由約簡Red導(dǎo)出的邊界域，即。

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

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

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

根據(jù)上述分析，可以得出以下定理。

定理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′的約簡。

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

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

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

輸出一個(gè)新的約簡，RedU∪{y}。

1)A= RedU；

{For each attributec∈C-A

A=A∪ {a}；

8)For each attributec∈A

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

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

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

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

輸出一個(gè)新的約簡，RedU∪U△。

4)如果h=0 和h′=0，轉(zhuǎn)5；

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

7)fori=1 toh

//累加同一等價(jià)類中約簡不能區(qū)分的矛盾對象

{For each attributec∈C-A

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

A=A∪ {a}；}

10)For each attributec∈A

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

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

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

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

3　實(shí)驗(yàn)驗(yàn)證

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

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

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

表3　6個(gè)數(shù)據(jù)集特性

下面比較約簡長度與約簡的傳承性。圖2給出了6個(gè)數(shù)據(jù)集在不同增長比例下的約簡長度。在4個(gè)數(shù)據(jù)集上，約簡不變，則只需要生成新增數(shù)據(jù)集的規(guī)則，原始規(guī)則集不必重新生成，而在另外兩個(gè)數(shù)據(jù)集上，約簡長度稍微增長，這主要因?yàn)樾略鰧ο笈c原始數(shù)據(jù)集引起沖突，需要另外的屬性集來細(xì)分原始對象，這時(shí)除了生成新規(guī)則集外，還需要修改部分原始規(guī)則。

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

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

表4　約簡傳承性比較

4　結(jié)論

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

[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]苗奪謙, 胡桂榮. 知識約簡的一種啟發(fā)式算法[J]. 計(jì)算機(jī)研究與發(fā)展, 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]. 計(jì)算機(jī)學(xué)報(bào), 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ìn)差別矩陣的屬性約簡增量式更新算法[J]. 計(jì)算機(jī)學(xué)報(bào), 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]尹林子, 陽春華, 王曉麗, 等. 基于標(biāo)記可辨識矩陣的增量式屬性約簡算法[J]. 自動化學(xué)報(bào), 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]康向平, 苗奪謙. 一種基于概念格的集值信息系統(tǒng)中的知識獲取方法[J]. 智能系統(tǒng)學(xué)報(bào), 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.

錢進(jìn)，男，1975年生，副教授，博士，主要研究方向?yàn)榇植诩?、粒?jì)算、云計(jì)算、大數(shù)據(jù)等。發(fā)表學(xué)術(shù)論文40余篇，其中被SCI、EI檢索20余篇。

朱亞炎，男，1994年生，主要研究方向?yàn)榇植诩?、云?jì)算等。

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

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160808.0830.008.html

2014-06-02. 網(wǎng)絡(luò)出版日期：2014-08-08.

江蘇省自然科學(xué)基金項(xiàng)目(BK20141152);教育部人文社會科學(xué)研究青年基金項(xiàng)目(15YJCZH129);江蘇省青藍(lán)工程項(xiàng)目;江蘇省大數(shù)據(jù)分析技術(shù)重點(diǎn)實(shí)驗(yàn)室開放基金項(xiàng)目 (KXK1402); 江蘇理工學(xué)院校級大學(xué)生創(chuàng)新項(xiàng)目(KYX15017).

錢進(jìn). E-mail：qjqjlqyf@163.com.

TP181

A

1673-4785(2016)04-0496-07