数据挖掘与知识发现(讲稿6粗糙集挖掘技术).doc

第6章 基于粗糙集（Rough Set）理论的数据挖掘技术 粗糙集理论是由波兰华沙理工大学数学家Z.Pawlak于1982年提出的一种数据分析理论，该理论在分类意义下定义了模糊性和不确定性两个概念。是一种处理不完整数据、不精确知识的表达、学习、归纳等的一种新型数学工具。 粗集理论的重要特点是：不需要任何附加信息或先验知识，直接从所需处理的数据本身所提供的信息出发找出问题的内在规律。 目前，大多数数据挖掘工具软件（如：AQ系统、IDS系统等）都是基于集合论开发的，其中粗糙集（RS）理论使用最广，也最有发展前途。 由于RS是研究不精确和不确定知识的一种数据工具，如，知识的含糊性，主要包括：①术语的模糊性，如高矮；②数据的不确定性，如噪声；③知识自身的不确定性，如规则的前后件间的依赖关系不完全可靠等。所以，它同其它不确定问题理论，如，概率统计理论中的概率分布、模糊理论不能处理不完整数据且需提供隶属函数这种先验知识、D-S证据理论中的基本概率赋值等相比，更具实用性。 粗集理论的主要思想：是在保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。 目前，RS理论已成功地应用于机器学习、过程控制、模式识别、数据挖掘、预测、故障诊断、决策分析和人工神经网络等领域，成为其它不确定理论的一种补充，有着不可替代的优越性。 1. 粗糙集理论的基本概念 （1） 知识和知识库 设为论域，任何子集，称为中的一个概念或范畴。规定空集也是一个概念。中的一个概念族称为关于的抽象知识，简称知识。 这里，主要对上能形成划分的那些知识感兴趣。 一个划分F定义为：F，其中， （显然，一个划分就是一条知识） 上的一族划分称为关于的一个知识库（knowledge base）。 设是上的一个等价关系，表示R的所有等价类构成的集合，即。表示包含元素的R等价类。 【例如】考虑一组儿童的集合，A={（张，9），（王，9），（李，9），（赵，9），（刘，7），（洪，7），（梁，7），（黄，5），（陈，5），（段，8）}。则具有“相同年龄”关系的等价类如下： ={（张，9），（王，9），（李，9），（赵，9）} ={（刘，7），（洪，7），（梁，7）} ={（黄，5），（陈，5）} ={（段，8）} 即 一个知识库就是一个关系系统，R是上的一族等价关系。 若等价关系族，且，则也是一个等价关系（即P中所有等价关系的交集），称为P上的不可区分关系（indiscernibility）,记为ind(P)，且有 （1） 则表示与等价关系族P相关的知识，称为K中关于的P基本知识（P基本集）。为简单起见，用代替。不可分辩关系概念是RS理论的基础，它揭示出论域知识的颗粒状结构。 的等价类称为知识P的基本概念或基本范畴。 特别的，如果，则称为K中关于的初等知识。的等价类为知识R的初等概念或初等范畴。 当为一知识库，定义为K中所有等价关系的族，记作 （说明K是由所有基本知识组成的集合） 【例如】一玩具积木的知识表达系统 论域，如果根据某一属性描述这些积木情况，就可按颜色、形状和体积分类。换言之，可以定义三个等价关系（即属性）：颜色、形状、体积。 按分：---红；---蓝；---黄 按分：---圆；---方；---三角型 按分：---大；---小。 由此得三个等价类： 这三个等价类均是由知识库中的初等概念（初等范畴）构成的。它的基本范畴是初等范畴的交集构成的，如 ------红色三角形 ------蓝色方形 ------黄色三角形 上面是的基本范畴。 ------红色大三角形 这是的基本范畴。 ----红色或蓝色，为的范畴。 注：（1）有些范畴在这个知识库是无法得到的，如 ---说明知识库中不存在蓝色圆形，为空范畴。 ---说明知识库中不存在红色方形，为空范畴。 （2）上例容易求出、、和 =={} =={} =={} =={} （3）若一个知识系统，，给定一个等价关系簇，且有下列等价类： 试求：，，， 《自己思考》 定义： 设和为两个知识库，若，即，则称和（P和Q）是等价的，记作（）。（说明和有同样的基本范畴） 设和为两个知识库，当时，称知识P（知识库）比知识Q（知识库）更精细，或Q比P更粗糙。当P比Q更精细时