基于粗糙集的不完备情报信息系统的完备化

基于粗糙集的不完备情报信息系统的完备化（精选2篇）

篇1：基于粗糙集的不完备情报信息系统的完备化

基于粗糙集的不完备情报信息系统的完备化

在现有的基于粗糙集的不完备数据分析方法-ROUSTIDA算法的基础上,扩充了相似对象集的概念,提出了一种新的改进算法,并利用该算法对一不完备的情报信息系统实施完备化,填补的.效率高、速度快.

作 者：周业明 林秀芹 曹之新 文学义 ZHOU Ye-ming LIN Xiu-qin CAO Zhi-xin WEN Xue-yi  作者单位：海军兵种指挥学院,广东,广州,510430 刊 名：军事运筹与系统工程 英文刊名：MILITARY OPERATIONS RESEARCH AND SYSTEMS ENGINEERING 年，卷(期)： 21(2) 分类号：N99 关键词：粗糙集   信息系统   完备化  

篇2：基于粗糙集的不完备情报信息系统的完备化

在事务数据库中挖掘数据间的关联性已经引发学界日益广泛的高度关注, 该研究是由Agrawal等人首度创立并提出有关描述的[1]。在事务数据库中不存在值丢失的问题, 但却会有缺失值广泛存在于日常数据库中。针对这样的不完备系统进行关联规则挖掘, 最常见的方法就是通过各种方法手段将数据集实现完备化, 但在此之后却会使知识发生不同程度的失真。本文研究力图在保持原始信息不发生变化的前提下对信息系统进行处理。而经过研究可知, 粗糙集却恰是处理不精确、不确定与不完全数据的相应数学理论[2]。并且, 粗糙集理论最显著的优点即在于处理过程中并不需要待处理数据集合外的任何先验信息。

基于此, 本文提出了一种基于粗糙集的不完备系统关联规则挖掘模型, 并利用粗糙集理论中的等价关系, 重新定义了关联规则的支持度和置信度等概念, 而利用此模型即可以不处理缺失数据, 直接提取带结论域的关联规则。

1 关联规则

1.1 关联规则基本概念

关联规则挖掘作为一种重要的数据挖掘技术, 其目的是从大型数据中发现隐藏的、具有偏好性的以及属性间存在的规律。关联规则挖掘的基本概念如下[3]:

设I={I1, I2, …, Im}是项的集合, 事务集记为D={t1, t2, …, tn}, 其中每个事务ti={Ii1, Ii2, …, Iik}是项的集合, 使得ti∈I, 关联规则是形如XY的蕴含式, 而X, YI是两个项目集合, 且X∩Y=。规则XY在事务集D中成立, 具有支持度s和置信度c, 并且s是D中事务同时包含X、Y的百分比, c是D中在包含X的事务中同时包含Y的百分比。

支持度s反映了规则的频度, 置信度c则表明了整个规则的正确度。一个关联规则必须满足用户指定最小支持度 (min_sup) 和最小置信度 (min_conf) 阈值。对规则XY, 若s≧min_sup且c≧min_conf, 则称XY为强关联规则。关联规则挖掘的任务就是挖掘事务集中所有的强关联规则。

1.2 带结论域的关联规则

一般的关联分析是不设结论域的, 如此才能够尽量发现各个属性间的关联性和依赖性。对决策者而言, 往往只是关注条件属性与决策属性之间的关联性, 而对其他关联规则却不具兴趣。针对这一点, 文中只对带结论域的关联规则进行挖掘, 将属性集分为决策属性集和条件属性集。即关联规则XY中, X和Y均由多项属性组成, 可分别将其称为条件属性集和决策属性集, 为此关联规则即可表示为x1∧x2∧…∧xmy1∧y2∧…∧yn。其中, xi∈X, yj∈Y分别称为条件属性和决策属性。

2 不完备信息系统及粗糙集理论

2.1 不完备信息系统

不完备系统大量存于现实生活中, 对象信息的不完备性是从实例中学习的难点和障碍所在, 因此, 如何从这些不完备信息系统获取有用的知识随之而具备了重要的理论和现实意义。如下即给出不完备信息系统的定义。

定义1[4]四元组S= (U, A, V, f) 称为一个信息系统。其中, U表示对象的非空有限集合, 称为论域;A表示属性的非空有限集合, 包含条件属性集合C和决策属性集合D, A=C∪D, C∩D=, x∈U, a∈D, f (x, a) ≠*, 即决策属性中不含空值;V=Ua∈AVa, Va表示属性a的值域;f:U×A→V是一个信息函数, 可为每个对象的任一个体属性赋予一个信息值, 即a∈A, x∈U, f (x, a) ∈Va。若存在一个x∈U, a∈C, f (x, a) =*, 则称信息系统是不完备的;否则将称该信息系统是完备的。

2.2 不完备信息系统的处理方法

目前, 对不完备信息系统的处理主要有两种策略:

其一, 通过对不完备对象进行处理, 使系统达到完备化。如删除带有空值的对象、通过数据补齐将不完备信息系统转化为完备信息系统等[5]。但删除空值却有可能造成错误的结果, 而对空值不正确的填充又可能会将新的噪声引入数据中。补齐处理在将未知值补以主观估计值时则未必会符合客观事实, 此时就可能改变了原始的信息系统, 从而使挖掘任务产生错误的结果。

其二, 直接从初始的不完备信息系统中获取规则[6]。常见的方法是基于粗糙集理论的规则获取, 该方法已知则具有着不改变初始不完备系统的结构、且所获得的规则也不受缺省值的影响等显著优点。

2.3 粗糙集理论

粗糙集理论作为一种研究不完整、不确定知识和数据的表达、学习及归纳的理论方法, 是由波兰学者Z Pawlak首创提出的[7], 是一种特殊形式下的关联规则系统。该理论可直接从给定问题描述集合出发, 通过不可分辨关系和不可分辨类确定问题的近似域, 从而找到该问题的内在规律。

定义2[8]给定信息系统IS= (U, A, V, f) , 设A={a1, a2, …, am}, 称为一个关系项目, 其中v∈Vai。设R是所有关系项目的集合, 称为总项目集, 若且X中每个属性最多只出现一次, 则称X为关系项目集。

定义3给定信息系统IS={U, A, V, f}, 基于项目集X的等价类记为RX:

定义中, RX表示U中匹配项目集X的元组集合。

如上已给出了项目集的等价类的定义, 由此即可提出不完备系统中项目集的上下近似集及边界域的定义。

定义4给定不完备信息系统S= (U, A, V, f) , 对于y∈U, 一定匹配项目集X的最大元组集为:

可能匹配项目集X的最大元组集为为:

项目集X的边界域定义为:

由定义4可知, 表示一定不能匹配项目集X的集合;表示可能不匹配项目集X的集合。

3 不完备信息系统中关联规则挖掘

3.1 支持度和置信度的估计值

在不完备信息系统中, 精确地计算得到关联规则的支持度和置信度多具有一定难度, 但却可将最小可能值和最大可能值定义为实际支持度、置信度的估计值。

定义5项目集X的最小可能支持度为:

最大可能支持度为:

定义6关联规则的最小可能置信度为:

最大可能置信度为:

综合以上内容可得:

3.2 支持度和置信度的预测值

粗糙集理论中, 粗糙集的边界不确定性将引起粗糙集的不确定性[9,10]。粗糙集的边界越大, 确定性程度就会越小。因而, 可根据其边界域来缩小最小可能支持度和最大可能支持度的差距, 当最小可能支持度和最大可能支持度的值差别较小时, 即可预测出接近实际值的支持度。

定义7设项目集X的预测支持度为Presup (X) :

可得出性质2。

性质2若X是一个项目集, 则

相应地, 定义7则可变为:

定义8设关联规则的预测置信度为, 其计算公式即可描述为:

由定义7可知, 最小可能支持度和最大可能支持度的距离增大时, 粗糙边界即随之增大, 而若在最保守的估计值Minsup (X) 的基础上增大支持度, 并减小最大、最小可能支持度的距离, 即可预测得到更接近实际值的支持度。根据定义8则可预测出更接近实际值的置信度, 此时将可重新定义强关联规则。

4 数据实例

不完备信息系统S= (U, C∪D) 如表1所示, 其中C={a, b, c}, D={d}。给定min_sup=2/8, min_conf=3/5。

由表3可知, 其中就可筛选出满足Preconfmin_conf的强关联规则, 如此即可得出规则1, 2, 4均为强关联规则。

5 结束语

本文提出了一种基于粗糙集的不完备系统关联规则挖掘模型。该模型的优点是:

(1) 保持初始不完备信息系统结构, 使原始信息不发生失真;

(2) 提出了规则的预测支持度和预测置信度, 可以利用预测值在不完备信息系统中进行有效的强关联规则挖掘;

(3) 用户可根据实际情况确定使用支持度和置信度的可能值或预测值, 以此而提高关联规则的灵活性。

参考文献

[1]AGRAWAL R, IMIELINSKI T, SWAMI A.Mining association rules between sets of items in large databases[C]//Proc.1993 ACM SIGMOD Conference on Management of Data.Washington, D.C., 1993:207-216.

[2]Z.Pawlak.Rough sets:theoretical aspects of reasoning about data[M].Boston:kluwer academic publishers, 1991.

[3]J.Han, M.Kamber.Data mining:concepts and techniques[M].San Francisco:Morgan Kaufmann Publishers, 2001.

[4]KRYSZKIEWICZ M.Probabilistic approach to association rules in incomplete databases[J].Web-Age Information Management, 2000:133-138.

[5]QUINLAN J R.Unknown attributes values in induction[C]//Proceeding of the Sixth int’Workshop on Machine Learning.New York:IEEE Press, 1989.

[6]RAMONI M, SEBASTIANI P.Robust learning with missing data[J].Machine Learning, 2001, 45 (2) :147-170.

[7]GIUDICI P, CASTELO R.Improving Markov chain Monte Carlo model search for data mining[J].Machine Learning, 2003, 50 (1) :127-158.

[8]瞿彬彬, 卢炎生.不完备信息系统规则获取的矩阵算法[J].计算机科学, 2007, 34 (8) :193-195.

[9]孙成敏, 刘大有, 孙舒杨.面向不完备信息系统的粗糙集方法研究[J].小型微型计算机系统, 2007, 28 (10) :1869-1873.