第三章 覆盖粒计算在基于粗糙集的动态信息系统规则挖掘中的应用
和信息量随时间和场景的变化的状态，文献[84]中给出了信息变换函数f:T?S??的概念，函数的定义域是时间和场景的区域，其中时间序列集合为T?{t1,t2,...}，场景集合为S?{s1,s2,...}，状态序列集??{?ts,?ts,...}，每个?ts都是一个决策表且论
1122ii域、条件属性、决策属性均相同，属性值随着时间和场景的变化而变化。有： 定义3.1 动态信息系统为状态序列??{?ts,?ts,...}。
1122 抽取信息系统?ts和?ts（j?i），?Vca?Vca?ts?Vca?ts称为条件属性值差异，其
iijjjjii中Vca?ts表示对象个体c（c?U）关于属性a（a?CN）在ti时刻si场景下的属性值，
ii条件属性值差异描述了条件属性值的变化量。记CN'?{?a,?b,...}，其中?a是对条件属性a值的差异描述，?a的属性值为a的属性值差异。
而(Vce?ts?Vce?ts)?Ve?Ve称为决策变化趋势，其中e?D，描述了相同的对象个
iijj体的决策值从Vce?ts变化到Vce?ts。若两个不同个体k,h?U具有相同的变化趋势
iijj(Vke?tisi?Vke?tjsj)=(Vhe?tisi?Vhe?tjsj)，当且仅当Vke?ts?Vhe?ts和Vke?tjsj?Vhe?tjsj同时成立。记
iiiiD?{e,g,...}，e''''是对决策属性e变化趋势的描述，e'的属性值为e的决策变化趋势。
定义3.2 差异信息系统为???(U',A',V',f')，其中U'?U，A'?CN'?D'，
V?'?V，fa?A'''a':U?A?V'''，CN'、D'为差异信息系统的条件属性和决策属性。
由粗糙集理论可以得出，若信息系统?ts和?ts关于决策属性D的等价类记为：
iijj[u]D(i)和[u]D(j)，差异信息系统??ij中关于决策属性D'的等价类记为：[u]D(i?j)，则有
'[u]D'(i?j)=[u]D(i)?[u]D(j)。特殊的，当j?i?1时，此时的差异信息系统被称为相邻差
异信息系统。则有下面定义：
定义3.3 在差异信息系统??ij中，对任意的属性?a?CN'，?a的重要度Sig(?a)定义为Sig(?a)??CN(D')??CN??a(D')，式中：?P(Q)?''card(POSPQ)card(U)，POSPQ表示Q的
P正域[81]。重要度表明了属性对于决策分类能力的贡献程度。
定义3.4 设card(U')?m，card(A')?n，card(D')?d(d?n)（差异决策表有m行n列，决策属性d列），构造??上第p行的辨识矩阵M(p)?[wi,j](m?1?)n，其中如果
18
第三章 覆盖粒计算在基于粗糙集的动态信息系统规则挖掘中的应用
（xp?xi）则wi,j?1；否则wi,j?0。 f(xp,?aj)?f(xi,?aj)，
''定义3.5 设从差异信息系统??ij上获取的决策规则集为{r1,r2,...,rs}[86]，规则表示形式为?a????b???...?e'?(s1?s2)?...，定义决策规则的覆盖广度为
s?card(r)vv?1scard(U)，其中card(rv)为??i'j上满足该决策规则的记录数；决策规则的
s准确率为?bcard(rv)v?1?v?1fcard(rv)，其中fcard(rv)、bcard(rv)分别为??ij上满足该
决策规则前件和后件的记录数。
从中可以看出，通过某个挖掘算法得到的决策规则，其覆盖广度与准确率并不成正比，即在同样的时间复杂度下，一个改进的挖掘算法得到的挖掘规则，其覆盖广度和准确率都必须同时增大，因此决策规则更准确并且覆盖记录也就更广泛。
3.3规则挖掘
3.3.1动态信息系统中不一致性的辨识和消除
从粒计算的观点来看，如果我们将构成差异信息系统??ij的两个决策信息表看作是同一层次上的两个粒，那么差异信息系统??ij就直接为其上一层的粒，上层粒就会包含下层粒。因此，对于动态信息系统的状态序列?中决策表存在着一致或不一致这个问题，随着时间和场景的变化，就会有引起差异信息系统??ij中不一致的因素包含引起构成差异信息系统??ij的两个决策信息表中的不一致的因素的并，那么??ij中可能会产生新的不一致因素。对于这些新的不一致因素，我们将采取下面方法来消除：
由于不一致表现为在??ij中条件属性值均相同，而决策属性值存在不同，我们可以通过构造??ij上的覆盖，消除其上引起不一致的记录，使其成为一致差异决策表。设差异条件属性CN'构成的划分为X?{X1,X2,...,XM}，差异决策属性D'构成的划分按每个类所含记录多少降序排列为Y?{Y1,Y2,...,YN}（0 19 第三章 覆盖粒计算在基于粗糙集的动态信息系统规则挖掘中的应用 性构成的分类为基础，构造??ij上的覆盖Y'?{Y1',Y2',...,YN'}（由定义1.2可知）。其过程为：依次对每一个Yi?Y，满足若对?yik?Yi，?Xj?X，0?k?card(Yi)有yik?Xj，则Yi'?Yi'?Xj并且X?X?{Xi}；否则Yi'?Yi。 定理3.1 { ?Yi' | ?Yi'?Y', ?Yj'?Y',i?j且0?i,j?N,有Yi'?Yj'}为引起??ij上不一致原因的记录集合。 证明：根据以上算法描述，显然在差异决策属性D'构成的划分中，引起不一致原因的记录不会存在于card(Yi)?1的分类中，只会存在于card(Yi)?1的分类中。而在差异条件属性CN'构成的划分中，引起不一致原因的记录不会存在于card(Xj)=1的分类中，只会存在于card(Xj)?1的分类中。通过上述方法构造的??ij上的覆盖Y'，引起不一致原因的记录就会存在于card(Y'i)?1的Yi'中，同时card(Y'i)?1的Yi'中保留了引起不一致原因的记录，最终就有满足?Yi'?Y', ?Yk'?Y',有Yi'?Yk'的所有Yi'的并集 ?Yi 为引起??i'j上不一致原因的记录集，其中i?k且0?i,k?N。证毕！ 例3.1 U'?{1,2,3,4,5,6,7,8}，假设CN'构成的划分为X?{{1},{2,5},{3},{4,6}{7}{8}}， '那么D构成的划分按每个类所含记录多少降序排列为Y?{{1,6},{2,3}{4}{5}{7}{8}}， ''''''Y1?{1,4,6}，Y2?{2,3,5}，Y3?{4}，Y4?{5}，Y5?{7}Y8?{8}，按照Y'的构造过程有： 不一致因素为{4,5}。 3.2.2规则挖掘算法 输入：信息系统?ts与?ts； iijj输出：约简后的决策规则（表示形式为?a????b???...?e'?(s1?s2)?...）。 步骤1：根据定义3.2，构造相应的差异信息系统??ij?(U',CN'?D',V',f')； 步骤2：根据定理3.1，构造??ij上的覆盖，找出引起不一致的记录，并在??ij中设置对应记录所在行为空； 20 第三章 覆盖粒计算在基于粗糙集的动态信息系统规则挖掘中的应用 步骤3：根据定义3.3，对??ij对每个条件属性计算其重要性，得到属性重要性升序的序列，用数组Sig[card(CN')]保存，设置属性值不变的记录为空，用LN保存空行所在的行号； 步骤4：for i?1 to m { if(i?LN) { 根据定义3.4，构造第i行的辨识矩阵M(i); if(M(i)的后d列存在非零行) { 获取M(i)中所有非零行的前n?d列上的所有非零元素所在列号; 根据所获得的列号, 设置??ij第i行其他列号的条件属性值 为’*’; continue; } else for j?1 to card(CN') { 设置M(i)的第sig[j]列为1; if(M(i)中不存在某行前card(CN')列全为1，且后d列存在 0) 设置??ij第i行第sig[j]列的属性值为’*’; else break; } } else continue; 21 第三章 覆盖粒计算在基于粗糙集的动态信息系统规则挖掘中的应用 } 步骤5：整理合并相同规则，得到动态信息系统的最简决策规则。 算法的时间复杂度为o(n(n?d)m2)[87]，由于求信息系统的最优约简是NP问题 [88] ，所以算法试图生成的是最重要的尽可能全部的决策规则。 3.4实例分析 表3.1 ?ts?(U,CN?{e},V,f)ts iiii A U 1 2 3 4 5 6 7 8 a b c e 5 3 3 2 2 4 1 3 4 2 3 3 1 5 1 2 4 3 2 2 2 5 1 2 4 3 3 2 1 4 1 2 表3.2 ?t Ai?1si?1?(U,CN?{e},V,f)ti?1si?1 U 1 2 3 4 5 6 7 8 a b c e 4 4 3 1 3 3 2 4 2 3 4 3 2 5 1 3 1 5 5 2 4 5 2 5 3 4 4 1 3 3 2 4 对癌症病人的临床诊断的数据中，抽取部分数据并通过排序得到的状态集 ??{?ts,?t112s2,...}，选出在时刻ti与场景si的信息系统为?ts?(U,A,V,f)ts，其中U为 iiii全体病人，A?CN?D，CN?{a,b,c}为条件属性集，表示诊断项目，D?{e}为决策属性集，表示病人的状态，共分为4种状态。对属性值进行量化后，如表3.1所示；又选出在时刻ti?1与场景si?1的信息系统为?ti?1si?1?(U,A,V,f)ti?1si?1，如表3.2所示。 22