基于二元矩阵的启发式属性约简算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于二元矩阵的启发式属性约简算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

[摘 要]本文将基于分辨矩阵的二元矩阵和基于属性重要度的启发式属性约简算法结合起来,提出了一种新颖的针对不完备信息系统的属性约简算法。该算法用条件属性和决策属性之间的依赖度来度量属性重要度,进行启发式约简。该算法将属性约简问题转化为寻找能够覆盖决策属性的二元矩阵的二元矩阵集合问题。通过实例检验,该算法是有效的。

[关键词]粗糙集不完备信息系统约简二元矩阵启发式

[中图分类号]O15[文献标识码]A[文章编号]1007-9416(2010)03-0122-03

A Heuristic Reduction Algorithm Based on Binary Matrix

ZHU Meimei

(School of Management and Engineering,Nanjing University,Nanjing,Jiangsu,P.R.China,210093)

[Abstract]A novel attribute reduction algorithm in incomplete information (IIS) system is proposed, combining with binary matrix and attribute-oriented heuristic reduction.The significance of the conditional attributes is defined to measure the ability about determining the dependency relation between the conditional attributes and the decision attributes. The issue of finding an attribute reduction is converted to the issue of searching a set of binary matrices, in which the union of the binary matrices can cover the binary matrix of the decision attribute. Through the illustrative example of car relation, this algorithm is proved to be effective based on the tolerance relation.

[Key words]rough set,IIS,reduction,binary matrix,heuristic

1 引言

粗糙集理论是一种以决策表为形式,获取和优化不精确、不确定与不完全数据中的知识的理论,是由波兰数学家Z. Pawlak于1982年提出来的。在经典粗糙集理论中,论域上的等价关系起着非常重要的作用。在现实中,论域上的二元关系经常不是等价的,从而限制了Pawlak粗糙集模型在很多领域的应用。针对不完备信息系统,M. Kryszkiewicz提出了提出了相容关系。知识约简是粗糙集理论的重要研究内容,属性约简的目的是保持分类能力的前提下删除冗余的属性。作为经典的知识约简的算法之一,分辨矩阵法可求得信息系统的所有约简,但时间复杂度很高。基于属性重要度的启发式算法的时间复杂度较低,但该方法不能保证最后得到的就是最小约简。

本文在文献[1]介绍的分辨矩阵的基础上,结合相容关系,将分辨矩阵拆分为多个单属性的二元矩阵,并舴⑹皆技蛩惴ㄍ乒愕礁哺谴植诩P椭幸越档褪奔涓丛佣龋盟惴粜栽技蛭侍庾罢夷芄桓哺蔷霾呤粜缘亩卣蟮亩卣蠹衔侍猓唇粜栽技蛭侍庾卣蟮母哺俏侍狻?2 粗糙集的基本概念

在讨论基于二元矩阵的启发式属性约简算法前,首先来回顾一下粗糙集的一些基本概念。

定义1,四元组被称为一个信息系统。其中是表示对象的非空有限集合,称为论域;是表示属性的非空有限集合,称为条件属性集合,表示决策属性集合,且;,表示属性的值域;表示的一个信息函数,它为每个对象在每个属性上赋予一个信息值,即。若,则称信息系统为数据表,否则称为决策表。若存在一个,未知(记作:),则称信息系统是不完备的;否则称信息系统是完备的。[2]

粗糙集理论是建立在分类机制基础上的,将分类理解为在特定空间上的二元关系,而等价关系构成了对该空间的划分。在不完备信息系统中,针对属性值的缺失引入了多种二元关系。[3]其中,Kryszkiewicz M. 定义了如下相容关系。在相容关系中,空值被看做和任意值都是潜在相等的。

定义2给定不完备信息系统,对于具有空值的属性子集,记空值为“*”, Kryszkiewicz M. 定义了如下相容关系:定义3如果论域上的二元关系满足:自反性:对于所有,有成立;对称性;对于所有,若,则成立;传递性:对于所有,如果且那么必有,称是上的不分明关系。[5,6,7,8]

定义4对决策表,,记相对于的正域。

可见,的正域是中所有根据的信息划分到的等价关系中的对象集合。

定义5决策表的分辨矩阵是一个矩阵,对于,其任一元素为,满足或或。[2]

定义6每个单个的条件属性在决定条件属性和决策属性的依赖度上都有不同的重要度。根据约简集合和决策属性集之间的依赖度,表示为。将单个条件属性加入约简集合,增加的属性重要度可表示为。[9]

基于属性重要度的启发式算法以属性重要度作为启发原则,首先按照属性的重要程度从大到小逐个加入属性,直到该集合的分类能力与整个条件属性集合一致为止。

3 基于二元矩阵的启发式属性约简算法

本文提出的启发式属性约简算法,由基于分辨矩阵的二元矩阵表示了条件属性的属性重要度,按照属性的重要程度从大到小逐个加入到约简属性集合。下面的定义9给出了分辨矩阵基础上改进的二元矩阵,定义10则给出了属性重要度的定义。

定义6基于文献[7],定义了改进的分辨矩阵。被拆分为个矩阵(假设), 分别为所有单个条件属性和决策属性对应的二元矩阵,分别表示为,,,…,。

根据分辨矩阵的性质,下三角矩阵和上三角元素完全相同,而主对角线元素恒取值为0。该算法中的二元矩阵为了降低算法时间复杂度,去掉了二元矩阵的主对角线元素和下三角矩阵。

定义7函数定义为一个矩阵中元素取值为“1”的个数。从而,的属性重要度可定义为:

该算法的主要思想:从条件属性集相对于决策属性集的核开始,遍历条件属性集,并从中选择重要度最高的条件属性并将其赋值给约简属性集,并将其从条件属性集中剔除,并从决策属性的二元矩阵中去掉与条件属性的二元矩阵的交集,以便进入下面的循环。同时对于求得的进行判断,看其是否满足循环终止条件。

算法 1

输入:,其中为论域,、分别为条件和决策属性集

输出:该决策表的一个相对约简

第一步 令属性约简集

第二步

(1)判断,若成立,则输出,终止;否则进行(2);

(2)属性重要度取值最大的属性a,,,,转(1)。

下面分析算法的时间复杂度:

本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文

一.计算矩阵、共个矩阵的上三角元素,需要比较次,即

二.(2)的时间复杂度是,在最坏情形下需循环次,故时间复杂度是。

综上所述,该算法的最差时间复杂度为。

4 实例分析

为了考察算法的有效性,本节选择了一个已知最小相对约简的决策表进行对比分析。下面利用文献[4]给出的小汽车不完备决策表求属性约简。为了简化运算,采用了二元关系中的相容关系。表1中的行表示小汽车,包含了6个小汽车对象。表1中的列称为属性,,,and为条件属性,分别缩写为,,,,为决策属性。

下面展示属性约简的具体计算步骤,分别为约简算法执行的第一、二、三循环。

约简第一循环:

根据定义6,分别计算各单个属性对应的二元矩阵:

,,,,

根据定义7,分别计算各条件属性的属性那个重要度:

,,,。于是,条件属性被加入属性约简集。同时,将属性从条件属性集中删去,可得到:,。从中删去与的交集,。

约简第二循环:

,,,

,,。

条件属性被加进约简属性集。同时,从条件属性集中删除属性。,。从中删去与的交集,。

约简第三循环:

,,算法结束。

最终,该算法的约简结果为,与M.Kryszkiewicz在文献[4]得到的结果一致,通过该实例可以看出,基于分辨矩阵的覆盖式属性约简算法能够找到信息系统的最小约简。

5 结语

本文提出的基于二元矩阵的启发式属性约简算法,将分辨矩阵拆分为若干个单个属性的二元矩阵,将求属性约简问题转化为求矩阵覆盖的数学问题。并且通过实例证明该算法能够找到信息系统的最小约简。如何降低约简算法的算法复杂度是我们下一阶段的工作。

[参考文献]

[1] A. Skowron,and C.Rauszer. The Discernibility Matrices and Functions in Information Systems,in:R.Skowinski (Ed.),Intelligent Decision Support: Handbook of Applications and Advances of Rough Sets Theory.Kluwer Academic Publisher,Dordrench,1992, pp.331-362.

[2] 张文修,吴伟业,梁吉业,等.粗糙集理论与方法[M].北京:科学出版社,2001.pp.18-24.

[3] M.Kryszkiewicz, and H.Rybinski. Data mining in incomplete information systems from rough set perspective,Rough set methods and applications:new developments in knowledge discovery in information systems, 2000.

[4] M.Kryszkiewicz.Rough set approach to incomplete information systems [J].Information Sciences,1998,112:39-49.

[5] Z. Pawlak. Rough Sets: Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers,1991.

[6] Z.Pawlak. Rough Sets: International Journal of Information and Computer Sciences,11(1982),pp.341-356.

[7] Z. Pawlak. Rough Classification, International Journal of Man-Machine Studies, 20(1984), pp.469-483.

[8] Z.Pawlak,Grzymala-Busse,J. Slowinski, and R.Ziarko. Rough Sets, Communications of The ACM,38(1995), pp.89-95.

[9] X.Hu.Knowledge Discovery in Databases: An Attribute- Oriented Rough Set Approach.Doctoral dissertation,University of Regina,Canada,1995.

本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文