«上一篇 下一篇»
  山东大学学报(工学版)  2016, Vol. 46 Issue (1): 1-9  DOI: 10.6040/j.issn.1672-3961.2.2015.033
0

引用本文 

景运革, 李天瑞. 基于知识粒度的增量约简算法[J]. 山东大学学报(工学版), 2016, 46(1): 1-9. DOI: 10.6040/j.issn.1672-3961.2.2015.033.
JING Yunge, LI Tianrui. An incremental approach for reduction based on knowledge granularity[J]. Journal of Shandong University(Engineering Science), 2016, 46(1): 1-9. DOI: 10.6040/j.issn.1672-3961.2.2015.033.

基金项目

国家自然科学基金资助项目(61175047);国家自然科学基金委员会-中国工程物理研究院NSAF联合基金资助项目(U1230117)

作者简介

景运革(1970-),男,山西运城人,副教授,博士研究生,主要研究方向为粒计算与粗糙集,数据挖掘与知识发现.E-mail:jyg701022@163.com

通讯作者

李天瑞(1969- ),男,福建莆田人,教授,博士生导师,主要研究方向为粒计算与粗糙集,数据挖掘与知识发现,云计算与大数据.E-mail:trli@swjtu.edu.cn

文章历史

收稿日期：2015-05-18
网络出版时间：2015-12-18 15:15:37
Contents              Abstract              Full text              Figures/Tables              PDF
基于知识粒度的增量约简算法
景运革1, 2, 李天瑞1     
1. 西南交通大学信息科学与技术学院, 四川 成都 611756;
2.运城学院公共计算机教学部, 山西 运城 044000
收稿日期：2015-05-18; 网络出版时间：2015-12-18 15:15:37
基金项目：国家自然科学基金资助项目(61175047);国家自然科学基金委员会-中国工程物理研究院NSAF联合基金资助项目(U1230117)
作者简介：景运革(1970-),男,山西运城人,副教授,博士研究生,主要研究方向为粒计算与粗糙集,数据挖掘与知识发现.E-mail:jyg701022@163.com
通讯作者：李天瑞(1969- ),男,福建莆田人,教授,博士生导师,主要研究方向为粒计算与粗糙集,数据挖掘与知识发现,云计算与大数据.E-mail:trli@swjtu.edu.cn
摘要: 在现实中,许多数据库都是动态变化的,非增量约简方法处理这些数据需要花费大量的时间和空间。增量技术是处理动态数据的有效方法。首先介绍了计算知识粒度的增量机制,然后提出了基于知识粒度的增量约简算法,当一些对象增加到决策表时,能够利用原有决策表的知识粒度和约简,快速计算出增加对象后的知识粒度和约简,并通过理论分析验证了增量方法可以减少计算属性约简的时间复杂度,最后用增量方法和非增量方法对UCI数据集进行一系列试验。试验结果表明,所提增量算法在处理动态数据时能够节省大量的计算时间。
关键词: 知识粒度    属性约简    增量学习    粗糙集理论    决策表    
An incremental approach for reduction based on knowledge granularity
JING Yunge1, 2, LI Tianrui1     
1.School of Information Science and Technology, Southwest Jiaotong University, Chengdu 611756, Sichuan, China;
2.Department of Public Computer Teaching, Yuncheng University, Yuncheng 044000, Shanxi, China
Abstract: The object set in a decision table varied dynamically nowadays. It cost a lot of time for non-incremental algorithms solving reduction of dynamical data set. Incremental technique supplied an efficient and effective soluation to such dynamic data. An incremental mechanism for updating knowledge granularity was introduced and then an incremental approach for attribute reduction based on knowledge granularity was developed. With the existing knowledge granularity and reduction, the new reduction could be obtained by the proposed method when multiple objects were added to the decision table. Theoretical analysis validated that incremental approach could reduce complexity of time for computing attribute reduction. Experiments conducted on different data sets from UCI showed that the proposed incremental algorithm could achieve better performance than the non-incremental approach.
Key words: knowledge granularity    attribute reduction    incremental method    rough set theory    decision table    
0 引言

粒计算是用来处理不确定、不精确数据的数学工具,已广泛应用到数据挖掘[1, 2]、模式识别[3]、机器学习[4]和专家系统[5]等领域,并取得了大量研究成果。知识约简就是在决策系统分类能力不变的情况下,删除冗余和不重要属性。最近几年来,许多学者对属性约简方法进行了深入研究。王磊等从矩阵的视角重新给出知识粒度分辨度和属性重要度等计算方法,提出了属性重要度矩阵计算的知识约简方法[6];翟俊海等受决策树划分子集思想的启发,提出了一种基于划分子集的属性约简算法[7];邱桃荣等在多值信息系统下利用粒度计算方法设计多级概念获取算法[8];钟珞等定义了粒矩阵相,建立了基于粒矩阵的知识粒化方法,提出了基于粒矩阵的知识粒化方法,以及一种新的信息系统属性约简方法[9]。但上述大多数约简方法都是针对静态数据库,在现实中许多数据库都是动态变化的,静态约简方法需要重复计算,造成大量时间和空间的耗费,所以这些静态约简的方法在实际应用中受到极大的限制。

为了有效处理动态数据,许多学者提出了增量属性约简方法,并将其成功运用到动态知识挖掘领域中。ZENG Anping等人在模糊决策信息系统中研究了混合信息系统中属性集添加或删除时,近似空间中知识粒度的变化规律,给出粒度变化前后的模糊粗糙集模型中近似集、约简集之间的数学关系以及隶属度变化规律,提出了属性集动态变化时基于模糊粗糙集理论的动态特征提取方法[10];LIANG Jiye等人利用增量机制计算决策表的3种信息熵,当多个对象增加到决策表时,利用粗糙集技术提出了一种群增量特征选择的方法[11];QIAN Yuhua等人根据决策系统的粒度变化,设计了正向和逆向近似,并将其成功应用到启发式约简算法中,当属性动态变化时,能够快速找到新的属性约简[12];刘洋等在对象集增加的基础上,分析了差别矩阵的增量机制,提出了差别矩阵的增量式属性约简完备算法,并通过试验验证了该方法的有效性[13];CHEN Hongmei等人在不完备信息系统中,为提高属性约简的效率,定义了最小辨识属性集。在属性值粗化细化时,分析了最小辨识属性集以及规则的变化性质,提出了不协调决策系统中基于粗糙集的规则增量更新算法[14];杨明分析了对象增加情况下差别矩阵更新的增量机制,提出了基于改进差别矩阵的属性约简增量式更新算法,在原有的约简的基础上可以快速找到更新后决策表的属性约简[15],对于不完备系统,SHU Wenhao等人提出了正域增量约简算法,可以有效处理属性集动态变化的数据[16];LI Shaoyong等人提出了一种新的复合粗糙集模型,讨论了当增加或删除对象时,增量更新复合粗糙集的策略,并设计了相应的增量算法[17]。许多学者已在增量约简和近似集方面做了大量的研究工作,并取得一定的成效,但关于知识粒度增量约简方法的报道却不多。为了进一步扩展知识粒度的粗糙集模型,本研究提出了一种基于知识粒度的增量约简算法,首先介绍了计算知识粒度的增量机制,然后给出了相关定理和定义,最后通过算例和试验证明所提出算法的有效性。

1 粗糙集的相关知识

定义1[18] 决策表是一个四元组S=(U,A=C∪D,V,f),U={x1,x2,…,xn}表示非空有限的对象集合,也称论域;其中C为条件属性集,D为决策属性集,$V{\rm{=}}\mathop \cup \limits_{a \in C \cup D} {V_a}$,其中Va是属性a的值域,f: U×C∪D→V是一个信息函数,即a∈C∪D,x∈U有f(x,a)∈Va。

定义2[19] 决策表S=(U,A=C∪D,V,f),U为论域,π为U上的一个划分,且π={X1,X2,…,Xm},则π的知识粒度GD(π)定义为$GD\left(\pi \right)=\sum\limits_{i=1}^m {\frac{{\left| {{{\rm{x}}_i}} \right|}}{{\left| U \right|}}} \log \left| {{{\rm{x}}_i}} \right|$。

定义为π={{x}|x∈U},π的粒度达到最小值0;π={U},π的粒度达到最大值log|U|。

2 知识粒度约简算法 2.1 知识粒度基本知识

定义3[20] S=(U,A=C∪D,V,f),U为论域，P、Q为定义在U上的两个等价关系族，则知识Q关于知识P的相对知识粒度定义为GD(Q|P)=GD(P)-GD(P∪Q)。

例1 表 1为决策表,条件属性的划分为:U/C={{1},{2,4},{3,5},{6,7},{8,9}},条件属性和决策属性的划分为: U/C∪D={{1},{2,4},{3,5},{6,7},{8,9}}。

表1 决策系统 Table 1 A decision system

则GD(D|C)=GD(C)-GD(C∪D)=$\frac{8}{9}$log 2-$\frac{6}{9}$log 2=$\frac{2}{9}$log 2。

相对粒度GD(Q|P)反映了知识Q相对于知识P在论域U上的分辨能力,即GD(Q|P)越小,表明Q相对于P对U中对象的分辨能力就越弱;反之,若GD(Q|P)越大,表明Q相对于P对U中对象的分辨能力就越强。

定义4[20] (属性重要度1)决策表S=(U,A=C∪D,V,f),∀a∈C,定义属性a在C相对于决策属性集D的重要性为SigUinner(a,C,D)=GD(D|C-｛a｝)-GD(D|C)。

定义5[20] (属性重要度2)决策表S=(U,A=C∪D,V,f),令C0C,a∈C-C0关于属性集C0对决策属性集D的重要性为: SigouterU(a,C,D)=GD(D|C0)-GD(D|C0∪｛a｝)。

定义6[20] 决策表S=(U,A=C∪D,V,f),a∈C,若GD(D|C)=GD(D|C-{a}),则称a是C相对于决策属性集D所不必要的,否则称a是必要的。

性质1[20] 决策表S=(U,A=C∪D,V,f),属性a为C中相对于决策属性集D所必要的属性,当且仅当Sig(a,C,D)＞0。

定义7[20] 决策表S=(U,A=C∪D,V,f), 信息系统的核为CoreC(D)={a∈C|Sig(a,C,D)＞0}。

定义8[18, 19] 决策表s=(u,a=c∪d,v,f),red⊆c,red为知识粒度模型下的属性约简,则red必须满足条件:(1)gd(d|c)=gd(d|red);(2)∀ci∈red,使得gd(d|red-｛ci｝)≠gd(d|c)。

2.2 经典知识粒度约简算法

基于上述定理,算法1给出了一种经典的知识粒度属性约简算法[11, 18]。

算法1 经典的知识粒度属性约简算法

输入: 决策表S=(U,A=C∪D,V,f),其中C为条件属性集,D为决策属性集;

输出: 决策表的属性约简RedU。

Step 1: 计算条件属性C相对于决策属性D的核Core,令RedU←Core;

Step 2: If(GD(D|RedU)=GD(D|C))then

       go to Step 5;

    else

       go to Step 3;

    End if

Step 3: P←RedU,while(GD(D|RedU)≠GD(D|C)) do

       ｛对每个ai∈C-P,计算属性重要度2,即SigUouter(ai,P,D),选择SigUouter(ai,P,D)最大的属性ai作为扩展属性,

       RedU←RedU∪｛ai｝｝;

Step 4: For(a∈RedU)

        If(GD(D|P)=GD(D|C))then

        RedU←P-｛a｝;

       End if

      End

Step 5: 输出属性约简RedU,算法结束。

3 知识粒度增量约简算法

当有新对象添加到决策表时,重复计算知识粒度需要耗费大量的时间和空间,为了提高约简效率,快速找到增加对象后的约简,提出了基于知识粒度的增量约简算法。

3.1 知识粒度增量机制

决策表S=(U,A=C∪D,V,f),B⊆C,U/B={X1,X2,…,Xm｝,假设U+是新增的对象集,U+／B=｛Y1,Y2,…,Ym′｝,由于等价类U/B和U+／B之间可能存在相同的对象,所以假设U∪U+／B=｛X′1,X′2,…,X′k,Xk+1,Xk+2,…,Xm,Yk+1,Yk+2,…,Ym′｝,在U∪U+／B中,X′i=Xi∪Yi(i=1,2,…,k)表示可能联合的等价类,也就是说Xi∈U/B和Yi∈U+／B的属性值是相同的,且Xi∈U/B(i=k,k+1,k+2,…,m)和Yi∈U+／B(i=k+1,k+2,…,m)表示不能联合的等价类。

例2 假设U={x1,x2,…,x7},U／B=｛｛x1,x2｝,｛x3,x4｝,｛x5｝,｛x6,x7｝｝,增加的对象集U+=｛y1,y2,y3｝,U+／B=｛｛y1,y2｝,｛y3｝｝,假设{x5}与{y3}关于属性集B有相同的属性值,则:

$ U \cup {U^+}/B - \left\{ {\left\{ {{x_5},{x_3}} \right\},\left\{ {{x_1},{x_2}} \right\},\left\{ {{x_3},{x_4}} \right\},\left\{ {{x_6},{x_7}} \right\},\left\{ {{y_1},{y_2}} \right\}} \right\}. $

而X′1={x5,y3},X2={x1,x2},X3={x3,x4},x4={x3,x4}和Y2={y1,y2},显然m=4,m′=2,k=1。

定理1 假设S=(U,A=C∪D,V,f)是一个决策表,U/C={X1,X2,…,Xm},U+是新增加的对象集,U+／C=｛Y1,Y2,…,Ym′｝,可得U∪U+／C=｛X′1,X′2,…,X′k,Xk+1,Xk+2,…,Xm,Yk+1,Yk+2,…,Ym′｝,则增加对象后新的知识粒度

$\begin{array}{l} G{D_{U \cup {U^+}}}\left(C \right)=\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left| U \right|G{D_U}\left(C \right)+\left| {{U^+}} \right|G{D_{{U^+}}}\left(C \right)+\left| {{X_i}} \right|\sum\limits_{i=1}^k {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{X_i}} \right|}}} } \right.+\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left.{\left| {{Y_i}} \right|\sum\limits_{i=1}^k {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{Y_i}} \right|}}} } \right). \end{array}$

证明 根据已知条件

X′i=Xi∪Yi(i=1,2,…,k),则:

$\begin{array}{l} G{D_{U \cup {U^+}}}\left(C \right)=\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left({\left| {{X_i}} \right|+\left| {{Y_i}} \right|} \right)\sum\limits_{i=1}^k {\log \left({\left| {{X_i}} \right|+\left| {{Y_i}} \right|} \right)+\left| {{X_i}} \right|\sum\limits_{i=k+1}^m {\log \left| {{X_i}} \right|+\left| {{Y_i}} \right|\sum\limits_{i=k+1}^m {\log \left| {{Y_i}} \right|} } } } \right)=\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left| {{X_i}} \right|\sum\limits_{i=1}^k {\log \left| {{X_i}} \right|+\left| {{X_i}} \right|\sum\limits_{i=1}^k {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{X_i}} \right|}}+\left| {{Y_i}} \right|\sum\limits_{i=1}^k {\log \left| {{Y_i}} \right|} } }+} \right.\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left.{\left| {{Y_i}} \right|\sum\limits_{i=1}^k {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{Y_i}} \right|}}+\left| {{X_i}} \right|\sum\limits_{i=k+1}^m {\log \left| {{X_i}} \right|+\left| {{Y_i}} \right|\sum\limits_{i=k+1}^m {\log \left| {{Y_i}} \right|} } } } \right)=\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left| U \right|\left({\frac{{\left| {{X_i}} \right|}}{{\left| U \right|}}\sum\limits_{i=1}^k {\log \left| {{X_i}} \right|+\frac{{\left| {{X_i}} \right|}}{{\left| U \right|}}\sum\limits_{i=k+1}^m {\log \left| {{X_i}} \right|} } } \right)} \right.+\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left| {{U^+}} \right|\left({\frac{{\left| {{Y_i}} \right|}}{{\left| {{U^+}} \right|}}\sum\limits_{i=1}^k {\log \left| {{Y_i}} \right|+\frac{{\left| {{Y_i}} \right|}}{{\left| {{U^+}} \right|}}\sum\limits_{i=k+1}^m {\log \left| {{Y_i}} \right|} } } \right)+\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left.{\left| {{X_i}} \right|\sum\limits_{i=1}^k {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{Y_i}} \right|}}+\left| {{Y_i}} \right|+\sum\limits_{i=1}^K {\log \left| {{Y_i}} \right|} } \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{Y_i}} \right|}}} \right) \end{array}$

因为: $G{D_U}\left(C \right)=\frac{{\left| {{X_i}} \right|}}{{\left| U \right|}}\sum\limits_{i=1}^K {\log \left| {{X_i}} \right|,} G{D_{{U^+}}}\left(C \right)=\frac{{\left| {{Y_i}} \right|}}{{\left| U \right|}}\sum\limits_{i=1}^K {\log \left| {{Y_i}} \right|}$,则

$\begin{array}{l} G{D_{U \cup {U^+}}}\left(C \right)=\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left| U \right|G{D_U}\left(C \right)+} \right.\left| {{U^+}} \right|G{D_{{U^+}}}\left(C \right)+\left| {{X_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{X_i}} \right|}}}+\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left.{\;\left| {{Y_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{X_i}} \right|}}} } \right). \end{array}$

定理2 假设S=(U,A=C∪D,V,f)是一个决策表,U/C∪D={M1,M2,…,Mm},U+是新增加的对象集,U+／C∪D=｛N1,N2,…,Nm′｝,可得U∪U+／C∪D=｛M′1,M′2,…,M′k,Mk+1,Mk+2,…,Mm,Nk+1,Nk+2,…,Nm′｝,则

$\begin{array}{l} G{D_{U \cup {U^+}}}\left({C \cup D} \right)=\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left| U \right|G{D_U}\left({C \cup D} \right)+} \right.\left| {{U^+}} \right|G{D_{{U^+}}}\left({C \cup D} \right)+\left| {{M_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}}+\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left.{\;\left| {{N_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}} } \right). \end{array}$

定理3 假设S=(U,A=C∪D,V,f)是一个决策表,U/C={X1,X2,…,Xm},U/C∪D={M1,M2,…,Mm},U+是新增加的对象集,U+／C=｛Y1,Y2,…,Ym′｝,U+／C∪D=｛N1,N2,…,Nm′｝,可得U∪U+／C=｛X′1,X′2,…,X′k,Xk+1,Xk+2,…,Xm,Yk+1,Yk+2,…,Ym′｝,U∪U+／C∪D=｛M′1,M′2,…,M′k,Mk+1,Mk+2,…,Mm,Nk+1,Nk+2,…,Nm′｝,则

$\begin{array}{l} G{D_{U \cup {U^+}}}\left({D \cup C} \right)=\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left| U \right|G{D_U}\left({D \cup C} \right)+} \right.\left| {{U^+}} \right|G{D_{{U^+}}}\left({D \cup C} \right)+\left| {{X_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{X_i}} \right|}}}+\\ \;\left.{\;\;\;\;\;\;\;\;\;\;\;\;\;\left| {{Y_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{Y_i}} \right|}} - \left({\left| {{M_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}+\left| {{N_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}} } } \right)} } \right) \end{array}$

证明:

$ \begin{array}{l} G{D_{U \cup {U^+}}}\left({D\left| C \right.} \right)=G{D_{U \cup {U^+}}}\left(C \right)- G{D_{U \cup {U^+}}}\left({C \cup D} \right)=\\ \;\;\;\;\;\;\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left({\left| U \right|G{D_U}\left(C \right)+} \right.\left| {{U^+}} \right|G{D_{{U^+}}}\left(C \right)+\left| {{X_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{X_i}} \right|}}+\left| {{Y_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{Y_i}} \right|}}} } } \right)- \\ \;\;\;\;\;\;\;\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left| U \right|G{D_U}\left({C \cup D} \right)+\left| {{U^+}} \right|G{D_{{U^+}}}\left({C \cup D} \right)+} \right.\\ \;\;\;\;\;\;\;\;\left.{\left| {{M_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}+\left| {{N_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}} } } \right)=\\ \;\;\;\;\;\;\;\;\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left({\left| U \right|G{D_U}\left(C \right)- \left| U \right|G{D_U}\left({C \cup D} \right)+\left| {{U^+}} \right|G{D_{{U^+}}}\left(C \right)- } \right.\left| {{U^+}} \right|G{D_{{U^+}}}\left({C \cup D} \right)} \right)+\\ \;\;\;\;\;\;\;\;\;\left| {{X_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{X_i}} \right|}}+\left| {{Y_i}} \right|} \sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{Y_i}} \right|}} - } \\ \;\;\;\;\;\;\;\;\;\left.{\left({\left| {{M_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}+\left| {{N_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}} } } \right)} \right)=\\ \;\;\;\;\;\;\;\;\;\;\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left| U \right|G{D_U}\left({D\left| C \right.} \right)+\left| {{U^+}} \right|G{D_{{U^+}}}\left({D\left| C \right.} \right)+} \right.\\ \;\;\;\;\;\;\;\;\;\;\;\left| {{X_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{X_i}} \right|}}+\left| {{Y_i}} \right|} \sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{Y_i}} \right|}} - } \\ \;\;\;\;\;\;\;\;\;\;\;\left.{\left({\left| {{M_i}} \right|} \right)\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}+\left| {{N_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}} } } \right). \end{array} $

定理4 假设S=(U,A=C∪D,V,f)是一个决策表,U/C={X1,X2,…,Xm},U／C∪D=｛M1,M2,…,Mn｝,U／C-｛a｝=｛E1,E2,…,Eb｝,U／C-｛a｝∪D=｛Z1,Z2,…,Zb′｝,U+是新增加的对象集,U+／C=｛Y1,Y2,…,Ym′｝,U+／C∪D=｛N1,N2,…,Nn′｝,U+／C-｛a｝=｛F1,F2,…,Fc｝,U+／C-｛a｝∪D=｛L1,L2,…,Lc′｝,可得U∪U+／C=｛X′1,X′2,…,X′k,Xk+1,Xk+2,…,Xm,Yk+1,…,Ym′,｝,U∪U+／C∪D=｛M′1,M′2,…,M′k,Mk+1,Mk+2,…,Mn,Nk+1,Nk+2,…,Nn′,｝,U∪U+／C-｛a｝=｛E′1,E′2…,E′k,Ek+1,Ek+2,…,Eb,Fk+1,Fk+2,…,FC,｝,U∪U+／C-｛a｝∪D=｛Z′1,Z′2,…,Z′k,Zk+1,Zk+2,…,Zb′,Lk+1,Lk+2,…,LC′｝,则增加对象后,a∈C,属性a在C相对于决策属性集D的重要性变为

$ \begin{array}{l} {\rm{S}}ig_{U \cup {U^+}}^{{\rm{inner}}}\left({a,C,D} \right)=\;\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left| U \right|} \right.{\rm{Sig}}_U^{{\rm{inner}}}\left({a,C,D} \right)+\left| {{U^+}} \right|{\rm{Sig}}_U^{{\rm{inner}}}\left({a,C,D} \right)+\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left| {{E_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{E_i}} \right|+\left| {{F_i}} \right|}}{{\left| {{E_i}} \right|}}+\left| {{F_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{E_i}} \right|+\left| {{F_i}} \right|}}{{\left| {{F_i}} \right|}}} } - \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left({\left| {{Z_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{Z_i}} \right|+\left| {{L_i}} \right|}}{{\left| {{Z_i}} \right|}}+\left| {{L_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{Z_i}} \right|+\left| {{L_i}} \right|}}{{\left| {{L_i}} \right|}}} } } \right)- \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left({\left| {{X_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{X_i}} \right|}}+\left| {{Y_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{X_i}} \right|+\left| {{Y_i}} \right|}}{{\left| {{Y_i}} \right|}}} } } \right)+\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left.{\left.{\left| {{M_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{M_i}} \right|}}+\left| {{N_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{M_i}} \right|+\left| {{N_i}} \right|}}{{\left| {{N_i}} \right|}}} } } \right)} \right). \end{array} $

定理5 决策表S=(U,A=C∪D,V,f),C0∈C,U／C0=｛Q1,Q2,…,Qd｝,U／C0∪D=｛G1,G2,…,Gd′｝,U／C0∪｛a｝=｛H1,H2,…,Hz｝,U／C0∪｛a｝∪D=｛P1,P2,…,Pz′｝。U+是新增加的对象集,U+／C0=｛O1,O2,…,Ow｝,U+／C0∪D=｛T1,T2,…,Tw′｝,U+／C0∪｛a｝=｛W1,W2,…,Wi｝,U+／C0∪｛a｝∪D=｛I1,I2,…,Ii′｝,可得U∪U+／C0=｛Q′1,Q′2,…,Q′k,Qk+1,Qk+2,…,Qd,Ok+1,…,Ow,｝,U∪U+／C0∪D=｛G′1,G′2,…,G′k,Gk+1,Gk+2,…,Gd′,Tk+1,Tk+2,…,Tw′｝,U∪U+／C0∪｛a｝=｛H′1,H′2,…,H′k,Hk+1,Hk+2,…,Hz,Wk+1,Wk+2,…,Wi｝,U∪U+／C0∪｛a｝∪D=｛P′1,P′2,…,P′k,Pk+1,Pk+2,…,Pz′,Ik+1,Ik+2,…,Ii′｝,则增加对象后,a∈C-C0,关于属性集C0对决策属性集D的重要性变为

$\begin{array}{l} {\rm{S}}ig_{U \cup {U^+}}^{{\rm{outer}}}\left({a,{C_0},D} \right)=\;\frac{1}{{\left| {U \cup {U^+}} \right|}}\left({\left| U \right|} \right.{\rm{Sig}}_U^{{\rm{outer}}}\left({a,{C_0},D} \right)+\left| {{U^+}} \right|{\rm{Sig}}_U^{{\rm{outer}}}\left({a,{C_0},D} \right)+\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left| {{Q_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{Q_i}} \right|+\left| {{O_i}} \right|}}{{\left| {{Q_i}} \right|}}+\left| {{O_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{Q_i}} \right|+\left| {{O_i}} \right|}}{{\left| {{O_i}} \right|}}} } - \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left({\left| {{G_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{G_i}} \right|+\left| {{T_i}} \right|}}{{\left| {{G_i}} \right|}}+\left| {{T_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{G_i}} \right|+\left| {{T_i}} \right|}}{{\left| {{T_i}} \right|}}} } } \right)- \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left({\left| {{H_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{H_i}} \right|+\left| {{W_i}} \right|}}{{\left| {{H_i}} \right|}}+\left| {{W_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{H_i}} \right|+\left| {{W_i}} \right|}}{{\left| {{W_i}} \right|}}} } } \right)+\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left.{\left.{\left| {{P_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{P_i}} \right|+\left| {{I_i}} \right|}}{{\left| {{P_i}} \right|}}+\left| {{I_i}} \right|\sum\limits_{i=1}^K {\log \frac{{\left| {{P_i}} \right|+\left| {{I_i}} \right|}}{{\left| {{I_i}} \right|}}} } } \right)} \right). \end{array}$
3.2 知识粒度增量约简算法

基于知识粒度的增量机制,下面介绍一种基于知识粒度的增量约简算法。

算法2 一种基于知识粒度的增量约简算法

输入: 信息系统S=(U,A=C∪D,V,f),增加对象前的属性约简RedU,其中U+是新增加的对象集;

输出: 增加对象后的属性约简RedU∪U+。

Step 1: P←RedU,计算U／P=｛X1B,X2B,…,XjB｝,U+／P=｛M1B,M2B,…,Xj′B｝,U／C=｛X1C,X2C,…,XmC｝,U+／C=｛Y1C,Y2C,…,Ym′C｝;

Step 2: 计算U∪U+／P=｛X′1B,X′2B,…,X′kB,Xk+1B,Xk+2B,…,XjB,Mk+1B,Mk+2B,…,Mj′B｝和U∪U+／C=｛X′1C,X′2C,…,X′KC,XK+1C,,XK+2C,…,XmC,,YK+1C,YK+2C,…,YCm′｝;

Step 3: 计算GDU+(D|P)和GDU+(D|C),if(GDU+(D|P)=GDU+(D|C)),then

        go to Step 6;

       else

        go to Step 4;

Step 4: While(GDU∪U+(D|P)≠GDU∪U+(D|C))do

｛对每个ai∈C-P,按照定理5计算属性重要度2,即SigU∪U+outer(ai,P,D),选择SigU∪U+outer(ai,P,D)最大的属性ai作为扩展属性,

    RedU←RedU∪｛ai｝｝;

Step 5: For(a∈P)

        If(GDU∪U+(D|P-｛a｝)=GDU∪U+(D|C)then

        P←P-{a};

        End if

        End

Step 6: RedU∪U+←P,输出增加对象后的约简RedU∪U+,算法结束。

下面分析算法1和算法2的时间复杂度,当多个对象增加到决策表,徐章艳等在[21]给出知识粒度的复杂度为O(|C||U|+|C||U+|),算法1中Step 3-Step 5的时间复杂度为O(|C||U||U+|+|C||U|2+|C||U+|2),故算法1总的时间复杂度为O(|C||U|+|C||U+|+|C||U||U+|+|C||U|2+|C||U+|2);算法2中Step 3-Step 5的时间复杂度为O(|C||U||U+|+|C||U+|2),算法2总的时间复杂度为O(|C||U|+|C||U+|+|C||U||U+|+|C||U+|2)。算法1和算法2的时间复杂度比较结果如表 2所示。

表2 算法1和算法2时间复杂度比较 Table 2 A comparison of time complexity of incremental reduction Algorithm 1 and Algorithm 2
4 算例

例3 表 1是决策表,论域U={1,2,…,9},条件属性集C={a,b,c,e,f},决策属性集D={d},按照算法1计算约简是RedU=｛a,f｝,假设新增加的对象集U+=｛10,11,12｝,且10=｛1,0,0,1,1,0｝,11={0,0,1,0,1,1},12={0,1,1,1,1,1},计算增加对象集后决策表的属性约简。

(1)P←RedU,根据Step 2可得,U∪U+／P=｛｛1,10｝,｛2,4,11,12,8,9｝,｛3,5｝,｛6,7｝｝,U∪U+／C=｛｛1｝,｛2,4,11｝,｛3,5｝,｛6,7｝,｛8,9｝,｛10｝,｛12｝｝;

(2)根据Step 3可得,GDU∪U+(D|P)≠GDU∪U+(D|C),所以需要从C-P中选取属性增加到P=｛a,f｝中直到他们相等为止;

(3)根据Step 4我们增加属性｛b,e｝到P=｛a,f｝中,可到GDU∪U+(D|P)=GDU∪U+(D|C),然后执行Step 5;

(4)最后得到增加后的属性约简为RedU∪U+=｛a,f,b,e｝。

5 仿真分析 5.1 数据集和仿真环境

为了验证所提出增量方法的有效性,从UCI机器学习数据库下载了6个数据集,数据描述如表 3所示。仿真所用的软件和硬件环境是:Windows 8操作系统,32-bits(JDK1.6.0-20),CPU Pentium(R)Dual-Core E5800 3.20GHz,内存为Samsung DDR3 SDRAM 4.0GB。

表3 数据集描述 Table 3 Description of data sets
5.2 运行时间

在仿真过程中,分别用算法1和算法2运行表 3中的每个数据集,首先把每个数据集分成均匀两部分,第一部分作为基础数据集,剩余的50％数据作为增量数据集添加到基本数据集,增量和非增量算法的试验结果如表 4所示。从表 4可以清晰看到,约简属性数和约简的结果基本一致,甚至在某些数据集下是完全一样的,但是增量算法的运行时间却远远小于非增量算法。特别是对于较大数据集,算法的效果越明显。试验结果表明,所提的增量算法在数量动态数据是有效的。

表4 比较算法1和算法2的运行时间 Table 4 Comparison of Algorithm 1 and Algorithm 2 on computation time
6 结束语

通过分析决策表中对象动态增加时决策属性关于条件属性知识粒度的变化规律,给出了知识粒度增量变化的定量关系,提出了一种基于知识粒度的增量约简算法。当多个对象增加到决策表后,算法通过增量机制计算出新的知识粒度,进而可得到新决策表的属性约简。本研究提出的算法可用于决策表增量约简更新,为粗糙集的拓展提供了一种新思路。由于决策表不仅存在对象的变化,而且也存在属性的变化,所以后续工作重点在于研究属性变化时的知识粒度增量约简算法。

参考文献
[1] SUN Lin, XU Jiucheng, TIAN Yun. Feature selection using rough entropy-based uncertainty measures in incomplete decision systems[J].Knowledge-Based Systems, 2013(36):206-216.(1)
[2] YAO Yiyu, ZHONG Ning. Potential applications of granular computing in knowledge discovery and data mining[C]// Proceedings of the World Multi-conference on Systemics, Cybernetics and Informatics.[S.l.]: Betascript Publishing, 1999:573-580.(1)
[3] ROMAN W, SWINIARSKI, ANDRZEJ Skowron A. Rough set methods in feature selection and recognition[J].Pattern Recognition Letters, 2003, 24(6):833-849.(1)
[4] ANANTHANARAYANA V S, NARASIMHA Murty M, SUBRAMANIAN D K. Tree structure for efficient data mining using rough sets[J].Pattern Recognition Letter, 2003, 24(6):851-862.(1)
[5] SHUSAKU Tsumoto. Automated extraction of medical expert system rules from clinical databases based on RST[J]. Information Sciences,1998,112(1-4):67-84.(1)
[6] 王磊,叶军. 知识粒度计算的矩阵方法及其在属性约简中的应用[J].计算机工程与科学, 2013,35(3):98-102.
WANG Lei, YE Jun. Matrix-based approach for calculating knowledge granulation and its application in attribute reduction[J]. Computer Engineering ＆ Science, 2013, 35(3):98-102.(1)
[7] 翟俊海,高原原,王熙照,等. 基于划分子集的属性约简算法[J].山东大学学报(工学版),2011,41(4):25-28.
ZHAI Junhai, GAO Yuanyuan, WANG Xizhao,et al. An attribute reduction algorithm based on a partition subset[J]. Journal of Shandong University(Engineering Science), 2011, 41(4):25-28.(1)
[8] 邱桃荣,刘清,黄厚宽. 多值信息系统中基于粒计算的多级概念获取算法[J].模式识别与人工智能,2009,22(1):22-27.
QIU Taorong, LIU Qing, HUANG Houkuan. Granular computing based hierarchical concept capture algorithm in multi-valued information system[J].Pattern Recognition and Artificial Intelligence, 2009, 22(1):22-27.(1)
[9] 钟珞,梅磊,郭翠翠,等. 粒矩阵属性约简启发式算法[J].小型微型计算机系统,2011,2(3):516-520.
ZHONG Lu, MEI Lei, GUO Cuicui,et al. Heuristic algorithm for attribute reduction on granular matrix[J]. Journal of Chinese Computer Systems, 2011, 2(3):516-520.(1)
[10] 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.(1)
[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):1-31.(2)
[12] QIAN Yuhua, LIANG Jiye, PEDRYCZB W. et al. Positive approximation: An accelerator for attribute reduction in rough set theory[J]. Artificial Intelligence, 2010, 174(9-10):597-618.(1)
[13] 刘洋,冯博琴,周江卫. 基于差别矩阵的增量式属性约简完备算法[J].西安交通大学学报,2007,41(2):158-161.
LIU Yang, FENG Boqin, ZHOU Jiangwei. Complete algorithm of increment for attribute reduction based on discernibility matrix[J]. Journal of Xi′an Jiaotong University, 2007, 41(2):158-161.(1)
[14] 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.(1)
[15] 杨明.一种基于改进差别矩阵的属性约简增量式更新算法[J].计算机学报,2007,30(5):815-822.
YANG Ming. An incremental updating algorithm for attribute reduction based on improved discernibility matrix[J]. Chinese Journal of Computer, 2007, 30(5):815-822.(1)
[16] 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.(1)
[17] LI Shaoyong, LI Tianrui, HU Jie. Update of approximations in composite information systems[J]. Knowledge-Based Systems, 2015(83):138-148.(1)
[18] 刘清.Rough set及Rough推理[M].北京:科学出版社,2001:7-16.(3)
[19] YAO Yiyu. Probabilistic approaches to rough sets[J]. Expert Systems, 2003, 20(5):287-297.(2)
[20] 苗夺谦,范世栋.知识粒度的计算及其应用[J].系统工程理论与实践,2002,22(1):48-56.
MIAO Duoqian, FAN Shidong. The calculation of knowledge granulation and its application[J]. Systems Engineer-Theory & Practice, 2002, 22(1):48-56.(6)
[21] 徐章艳,刘作鹏,杨炳儒,等.一个复杂度max(O(|C||U|,O(|C|2|U／C|))的快速约简算法[J].计算机学报,2006,29(3):391-398.
XU Zhangyan, LIU Zuopeng, YANG Bingru, et al. A quickly attribute reduction algorithm with complexity of max(O(|C||U|,O(|C|2|U／C|))[J]. Chines Journal of Computer, 2006, 29(3):391-398.(1)