基于粗糙集理论的不完备信息系统中知识约简的研究

2019-08-08袁鸿燕

电脑知识与技术 2019年18期

摘要：本文基于不完备信息系统，以知识获取为目标，数学研究工具选择粗糙集理论，对不完备信息系统中的各种拓展粗糙集模型进行了研讨，重点是其中的知识约简算法。

关键词：不完备信息系统;粗糙集;知識约简

中图分类号：TP393 文献标识码：A

文章编号：1009-3044（2019）18-0295-02

Abstract： In this paper， for the purpose of knowledge acquisition in incomplete information systems， various extended rough set models in incomplete information systems are studied with rough set theory as a mathematical tool， with emphasis on the knowledge reduction algorithm.

Key words： Incomplete Information System; Rough Set; Knowledge Reduction

随着大数据时代的悄然而至，各行各业，各个领域，调查数据表明：决策的形成，相比较于经验和直觉，更依赖于数据与分析。数据挖掘技术是数理统计分析应用的延伸和发展，假如人们利用数据库的方式从被动的查询变成主动发现知识的话，概率论和数理统计这一古老的学科可以从数据中归纳知识，而数据挖掘技术提供理论基础[2]。数据挖掘（Data Mining），又称数据库中的知识发现（KDD），是目前最先进的数据资源分析技术，它可以从大量的数据中及时有效地提取隐含其中未知的、有用的、不一般的信息和知识，用以对决策活动进行支持[14]。粗糙集是数据挖掘中统计方法的一种，分类的意义是在已有数据集的基础上学会一个分类函数或构造出一个分类模型，该模型或函数能够把训练集中的数据记录映射到给定类别中的某一个，从而可以应用于数据预测。粗糙集（Rough Sets）理论是波兰Pawlak Z教授在1982年提出的一种可以能够有效定量分析并处理不精确、不一致、不完备信息在复杂系统中对象相似性约简办法，能比较客观地形容和处理事件的不确定性[1]。粗糙集理论为空间数据的属性剖析和知识发现开拓了一条新途径，可用于空间数据库属性表的一致性分析、属性的重要性、属性依赖、属性表简化、最小决策和分类算法生成等。粗糙集理论与其他知识发现算法相结合可以在空间数据库中数据不确定的情况下获取多种知识[15]。

1 不完备信息系统

定义1 一个知识表达系统[3]，即信息系统S，可表达为二元组，即S=（U，AT）。当中，U表示对象的非空有限集合，称之为论域;AT则表示所有属性的集合。[?]a[∈]AT，Va表示属性a的值域，即有a（x） [∈]Va（[?]x[∈]U），此处a（x）表示对象x在属性a上的取值。在信息系统S中，若[?]x[∈]U，x在属性a（a[∈]AT）上的取值未知，则称信息系统S为一个不完备信息系统[10]。

在不完备信息系统中，根据粗糙集理论的研究成果来看，可将未知属性值分为两种，即遗漏型和缺席型。此处仅思考遗漏型未知属性值，表明未知属性值实际上是确实存在的，只是因为各种缘由，目前未能监测到该值，这种遗漏型未知属性值可被记为a（x）=*。[9]

当数据集存在缺失值时，建模过程中就容易出现报错的情况，缺失值分析是数据分析过程中重要的一步，包括缺失值检测和缺失值处理。在R语言中，常用的缺失值分析函数如表1所示。

现在通过一个简单的实例来演示这几个函数的应用，要求检验出数据集score中的缺失值，并删除score中含有缺失值的行。

2 算法思路描述

知识约简是粗糙集重要研究内容，表示在原信息系统分类或决策能力保证不变条件下，将条件属性中的冗余属性和不相关的属性删除掉，使得决策表中知识表示可简化而又不丢失决策表中重要信息。[15]通过属性约简能取得比原始属性少得多的约简集，产生更加简洁知识的规则[3]。针对含有属性空值的不完备信息系统，汪凌[5，10]等人提出：引入相容属性矩阵与决策属性矩阵[10]的概念，提出在相容关系下基于矩阵的不完备信息系统规则获取算法，为大规模数据集的规则获取提供了一种新的思路[5，10]。

图1 不完备信息决策系统大数据集的规则获取方法

不完备信息决策系统DS=，条件属性集合是C，决策属性集合是D，相容属性矩阵与决策矩阵的生成是执行整个算法的基础[10，13]。首先，生成属性的|U|×|U|阶相容属性矩阵或决策属性矩阵，需要比较|U|×（|U|-1）/2次，时间复杂度为O（|U|2）。然后，从这两个属性矩阵中提取一阶决策规则时，需要按位去比较两个矩阵相应位置上的元素值，时间复杂度为O（|U|2）。最后，从一阶相容矩阵两两相交求二阶相容矩阵，需要计算次数为2|C|-1，二阶相容矩阵的时间复杂度是O（2|C|）[10，13]，每个条件属性相容矩阵都要跟决策属性矩阵进行两两相交的运算，时间复杂度为O（|U|2）。计算量的增长相对于对象个数是多项式级的，相对于属性个数是指数级模式[10，13]。本算法的优势是将复杂的提取过程转变成对简单0，1矩阵的操作，而不是对象集的处理，减少了矩阵计算量，大大提高了算法的效率。

3 结束语

此算法通过计算相容属性矩阵与决策属性矩阵，在提取规则时减少了矩阵生成的比较次数，降低了矩阵的占用空间，通过比较向量大小可快速求出全部决策规则集，大大提高了规则获取效率。[10]

参考文献：

[1] Pawlak Z. Rough sets[J]. International Journal of Computer and Information Sciences，1982，11（5）：341-356.

[2] 罗森林，马俊，潘丽敏.数据挖掘理论与技术[M].北京：电子工业出版社，2013.

[3] 董威.粗糙集理论及其数据挖掘应用[M].沈阳：东北大学出版社，2009.

[4] 张良均，谢佳标，杨坦，肖刚.R语言与数据挖掘[M].北京：机械工业出版社，2016.

[5] 汪凌.基于粗糙集的不确定信息知识发现及在城市交通管理中的应用研究[D].西南交通大学博士论文，2011.6.

[6] Pang-Ning Tan，Michael Steinbach，Vipin Kumar.Introduction to Data Mining[M].北京：人民邮电出版社，2006.

[7] 王添，姜麟，米允龙.海量数据下不完备信息系统的知识约简算法[J].计算机技术与发展，2015 （1）：137-142.

[8] 李长清，张燕兰.不完备信息系统下基于分辨率的属性约简算法[J].海南师范大学学报（自然科学版），2015（12）：359-361.

[9] 马兴斌，鞠恒荣，杨习贝，宋晶晶.不完备信息系统中多重代价决策粗糙集[J].南京大学学报（自然科学），2015 （3）：335-342.