一种新的不完备信息系统中极大相容块的构造算法

赵乃刚

(山西大同大学数学与计算机科学学院，山西大同037009)

一种新的不完备信息系统中极大相容块的构造算法

赵乃刚

(山西大同大学数学与计算机科学学院，山西大同037009)

在不完备信息系统中以分层递阶的方式求取极大相容块的构造算法，简化了不完备信息系统中极大相容块的求取过程.然而，该算法有一定不足之处，在求取极大相容块的中间过程中，没有进行非极大相容块的去除，从而增加了算法的空间复杂度，所以该算法仅适用于小规模不完备信息系统.基于这个缺点，提出了改进的极大相容块求取算法,从而可以在较大规模的不完备信息系统中进行极大相容块的求取.

粗糙集 非完备信息系统 极大相容块 空间复杂度

文献[1]提出的粗糙集理论模型对相容关系的结构进行深入分析，证明了极大相容块是不完备信息系统中的最小知识颗粒，这就意味着，它可以为知识获取提供更有效的计算，特别是对于大规模不完备信息系统而言.文献[2]提出了在不完备信息系统中以分层递阶的方式求取极大相容块的构造算法，从而简化了极大相容块的求取过程.然而，该算法有一定不足之处，在求取极大相容块的中间过程中，没有进行非极大相容块的去除，从而增加了算法的空间复杂度，所以该算法不适用于较大规模不完备信息系统中极大相容块的求取.基于这个缺点，本文提出了改进的极大相容块求取算法，实现了在较大规模不完备信息系统中进行极大相容块的求取.

1 相关基本概念

我们知道,一个信息系统是一个有序三元组S= (U,AT,f)，这里U是由对象组成的有限非空集，AT是由属性组成的有限非空集，对于任意的a∈AT，fa∶U→Va，其中，Va被称为属性a的值域.这里，假定一个对象x∈U在一个属性a下只取一个值，如果属性a的值缺失，则用“*”表示该缺失值.对于一个信息系统，如果对于任意的对象x∈U没有缺失的属性值，则称这个信息系统是完备的，否则它被称为是不完备的.

定义1[1]设S=(U,AT,f)是不完备信息系统，P⊆AT是一个属性子集，X⊆U是一个对象子集，称X关于P是相容的，如果对任意的x,y∈X有(x, y)∈SIM(P).如果不存在一个对象子集Y⊆U使得X⊂Y且Y关于P是相容的，则称X为一个极大相容子集或极大相容块.

为了方便起见，以C(P)记由属性集P⊆AT所决定的所有极大相容块构成的集合.

性质1[2]不完备信息系统S=(U,AT,f)中，a∈ AT，则

这条性质是针对不完备信息系统在单个属性作用下对极大相容块的求取.将原对象集合进行细化，细化后的集合内部，各个对象完全满足基本的容差关系.

性质2[2]不完备信息系统S=(U,AT,f)中，P⊆AT，任意的x∈C(P)，则存在Y∈C(P{a})，使得X∈CY({a}).其中X∈CY({a})表示Y为论域下属性集{a}决定的极大相容块集.

该性质为利用分层递阶方式求取极大相容块提供了方法.先求出属性集P{a}决定的极大相容块集C(P{a})={K1,K2,…,Km}，然后对于每个极大相容块Ki，用属性a提供的信息求更细的不可区分单元集C

Ki({a})，而且必有下式成立:.这样，我们可以结合性质1，在求由N个属性组成的属性集P决定的极大相容块时，完全可以利用分层递阶的思想进行.先求出由第一个属性a1决定的极大相容块，将这些相容块作为论域，再求由属性a2决定的极大相容块，如此反复，最后得到属性集P决定的极大相容块.

当然，在此迭代过程中，不可区分单元集({a})是相容块，但不一定是极大相容块，因为可能存在Xm∈CKi(a)，Xn∈CKj(a),有Xm⊆Xn，则Xm不符合定义1而不能是极大相容块.针对这种情况，我们可以这样处理：对前一步生成的极大相容块利用后面所加属性进一步分解后，所产生的相容块中，还要比较判断各块是否是当前属性下的极大相容块.如果在同一层次上，有集合X的超集存在，则不是极大相容块，应该去除之.

2 极大相容块的求取算法

给定不完备信息系统S=(U,AT)，若U′⊆U，AT′⊆AT,称S′=(U′,AT′)为原信息系统S的局部子系统.局部子系统中，在属性集P下的极大相容块是局部极大相容块，而在原系统下的极大相容块是全局极大相容块.

算法1：求属性集P决定的极大相容块C(P).

输入：不完备信息系统

输出：C(P).

说明：记Cb为中间过程所求单元素子论域集；Xi表示极大相容块集合C=({a1,a2,…,ar})；Xij表示C= ({a1,a2,…,ar})中的第j个局部极大相容块；Xi+1表示将极大相容块集合Xi在属性ai+1作用下求得的极大相容块集合；Yi+1表示生成Xi+1之前，未去除非极大相容块时的集合；Vai+1表示在属性Vi+1下，论域中各对象值的集合.

初始化：Cb=φ；CN=1；求极大相容块之前的初始数据集X01={1,2,…｜U｜}.

Step1：令i=0.

Step2：若i>r,则转Step14.

Step3：令CN2=CN，然后将CN清0.

Step4：将属性ai+1下论域中各对象值依次读到集合 Vai+1中.

Step5：令j=1.

Step8：令j=j+1转到步骤Step6.

Step9：判断集合Yi+1中每一个yk，得到C″= {M∈Yi+1｜∃N∈Yi+1且M∈N}.

Step10：判断集合Yi+1C″中每一个yk，若｜yk｜=1， 则Cb=Cb∪yk.

Step11：判断集合Yi+1中每一个yk，合成Xi+1= {yk∈Yi+1｜∉(Cb∪C″)}，且得到属性ai+1下的极大相容块个数CN3.

Step12：令CN=CN3.

Step13：令i=i+1，然后转到Step2.

Step14：去掉集合Cb中的重复值.

Step15：得到C(P)=X′∪Cb.

Step16：输出C(P)，算法结束.

Step1:利用属性ai+1对局部极大相容块Xij中的对象按其取值进行升序排列(将“*”当作无穷小的正则值).

Step3:判断若y1中对象值不为“*”,则令C′()，将当前CN值加上α，然后转步骤Step7.

Step4:若α>1，则转步骤Step5，否则转步骤Step6.

3 实验

我们从汽车评论网上下载了对某款汽车连续3个月的评论文本，共100篇.根据文本评论内容，我们选择了常用的65种特征，那些用来描述特征的词汇称为特征词.如描述特征“动力”时，可以用“强劲”、“不足”等.每个文本可由其在所有特征下的取值，即特征词所构成的向量来表示，如表1所示.由于并非所有特征均在每一个文本中出现，所以得到的是一个非完备信息系统，某个文本在某特征下取值为空时，用*表示.

表1 汽车评论文本的表示(100篇)

在表1中，由于特征词的种类太多，从而影响极大相容块的求取.所以，我们基于领域知识，利用文献[3]提供的情感词词表swt中规定的各特征词的情感极性,再利用文献[4]定义的条件属性值映射公式，可以将表1中出现的特征词映射成为两个符号a和c，其中符号a表示该特征词的情感倾向为正面，符号c表示该特征词的情感倾向为负面，这样表1便可以表示成表2的形式.

表2 将表1中情感词映射后的结果

再利用文献[4]提供的属性重要性度量公式计算出所有65个特征的重要度，为了在求取极大相容块时降低维度，选取前面最重要的25个特征进行计算.这样，我们就可以按照上面提到的算法进行极大相容块的求取，生成的极大相容块数为1 023，如表3所示.

表3 对100篇文本形成的不完备信息系统求取极大相容块的结果(部分)

4 结束语

本文首先将文本集表示成不完备信息系统的形式，然后对该系统进行特征词映射等一系列预处理，进而利用改进的算法求取极大相容块.实验表明，该算法适合于在较大规模的不完备系统中进行极大相容块的求取，然而，对于大规模的不完备信息系统，本算法还有待改进.

[1]Leung Y,Li D Y.Maximal consistent block technique for rule acquisition in incomplete information systems[J].Information Science, 2003,153:85-106.

[2]梁吉业,王宝丽,钱宇华,等.一种不完备信息系统中极大相容块的构造算法[J].计算机科学,2006,33(11A):79-82.

[3]王素格.基于Web的评论文本情感分类问题研究[D].上海:上海大学,2008.

[4]赵乃刚，李德玉，王素格，等.一种新的不完备信息系统中属性重要性度量及其应用[J].计算机科学,2008,35(8A):251-254.

Abstract:A hierarchical algorithm for constructing Maximal Consistent Block in Incomplete Information System is proposed in [2].As a result,the process for constructing Maximal Consistent Block is greatly simplified.However,There is a weak point in the algorithm,while computing the maximal consistent block,without dislodging the Non-Maximal Consistent Block.As a result,The Space-complexity of program is proved greatly,so the algorithm used only to a small Incomplete Information System.Based the fatal shortcoming,In the present paper,A better algorithm is provided,which would be used to the major Incomplete Information System.

Key words:rough set;Incomplete Information System;maximal consistent Block；space-complexity

〔编辑 高海〕

A New Algorithm of Constructing Maximal Consistent Block in Incomplete Information System

ZHAO Nai-gang
(School of Mathematics&Computer Science,Shanxi Datong University,Datong Shanxi,037009)

TP18

A

1674-0874(2010)04-0015-03

2010-03-25

赵乃刚（1975－），男，山西应县人，硕士，助教，研究方向：数据挖掘.