基于依赖度求解属性约简的方法

粗糙集的几种属性约简算法分析分类:默认栏目2006.6.16 10:32 作者：万富| 评论：0 | 阅读：1628陈淑珍，基于粗集的几种属性约简算法分析，武汉工业学院学报，Vol.2 4No.3，Sep .20 051.1 利用差别矩阵求最小约简差别矩阵(Discernibility Matrix)是由波兰华沙大学的著名数学家Skowron[21 提出来的，利用这个工具，可以将存在于复杂的信息系统中的全部不可区分关系表达出来。

利用差别矩阵求取最小约简的一个前提是:在数据表的预处理阶段要先对不相容的记录进行处理，即差别矩阵不处理不相容记录。

预处理的方法如将冲突的记录数除以记录总数，得到一个粗糙度的量度，该量度可以作为数据表的一个特征。

通过差别矩阵可以很方便地求取核属性，以核属性为出发点，再求取差别函数的最小析取范式，则求析取范式的运算就可以得到很大的简化。

而最后得到的每个析取分量对应着一个约简。

因此，一定可以得到最小约简。

但该算法的缺陷十分明显:首先，当论域的对象与属性的规模较大时，差别矩阵将占有大量的存储空间口(n的二次方);其次，差别函数的化简本身就是一个NP一hard问题，因此只要数据集稍大一点，就不具备可操作性。

1.2 基于属性依赖度约简算法求取所有约简是一个NP一hard问题，因此运用启发信息来简化计算以找出最优或次优约简显然是一种可取的方法。

许多启发式约简算法的基本步骤都是:由信息系统或决策表的核为起始点，然后根据属性重要性的某种测度，依次选择最重要的属性加人核中，直到满足终止条件。

便得到信息系统或决策表的一个约简(更确切的说，是包含约简的一个属性集)。

一个信息系统中的所有属性对于决策来说并不是同等重要的，在粗集理论中，属性重要性可通过相依度来体现。

决策属性D对于属性R(R属于C)的相依度y(R,D)定义为[3]:显然有，O <,y(R,D), l,y(R,D)给出了决策D对属性R之间相依性的一种测度。

属性约简方法概述属性约简又称维规约或特征选择，从数学的角度考虑，就是有p维数据x=(x1,x2……xp)，通过某种方法，得到新的数据x’=(x’1,x’2……x’k),k≤p,新的数据在某种评判标准下，最大限度地保留原始数据的特征。

属性约简主要是为了解决高维数据计算的复杂性和准确性问题。

目标是消除冗余和不相关属性对计算过程和最终结果造成的影响。

数据属性约简的意义主要从以下几个方面考虑：a)从机器学习的角度来看，通过属性约简去除噪音属性是非常有意义的；b)对一些学习算法来说，训练或分类时间随着数据维数的增加而增加，经过属性约简可以降低计算复杂度，减少计算时间；c）如果不进行属性约简，噪声或无关属性对分类的影响将与预期属性相同，这将对最终结果产生负面影响；d)当用较多的特征来描述数据时，数据均值表现得更加相似，难以区分。

为了描述属性约简方法，这里假设数据集合为d，d={x1,x2….xn},xi表示d中第i个实例，1≤i≤n，n为总的实例个数。

每个实例包含p个属性{|xi|=p}。

从机器学习的角度来看，属性约简方法可以分为监督的和非监督的两类。

下面是几种常用的方法。

（1）主成分分析主成分概念是karlparson于1901年最先引进。

1933年，hotelling把它推广到随机变量。

主成分分析把高维空间的问题转换到低维空间来处理，有效的降低了计算的复杂度。

通过主成分的提取，降低了部分冗余属性的影响，提高了计算的精度。

主成分分析的基本思想是通过正交变换将具有成分相关性的原始随机变量转换为具有成分不相关性的新变量。

从代数的角度，将原始变量的协方差矩阵变换为对角矩阵；从几何角度来看，将原始变量系统转换为一个新的正交系统，指向样本点分布最广的正交方向，然后降低多维变量系统的维数[43]。

定义4-1[44]：设x?(x1,x2,...,xp)'为p维随机向量，它的第i主成分分量可表示yi?ui'x，i=1,2,…,p。

粗糙集理论中的属性约简方法介绍粗糙集理论是一种用于处理不确定性和模糊性问题的数学工具，它在数据挖掘、机器学习和模式识别等领域得到了广泛应用。

属性约简是粗糙集理论中的一个重要概念，它能够帮助我们从大量的属性中找到最为重要的属性，减少数据处理的复杂性。

本文将介绍粗糙集理论中的一些常用属性约简方法。

1. 正域约简方法正域约简方法是粗糙集理论中最为常用的一种属性约简方法。

其基本思想是通过比较不同属性对决策类别的区分能力，来确定最为重要的属性。

具体步骤如下：首先，计算每个属性与决策类别之间的依赖度，依赖度越大表示属性对决策类别的区分能力越强。

然后，根据依赖度的大小进行排序，选择依赖度最大的属性作为初始约简。

接下来，逐步添加其他属性，并计算约简后的属性集对决策类别的依赖度。

如果添加属性后的依赖度没有显著提高，则停止添加，得到最终的约简属性集。

2. 相关属性约简方法相关属性约简方法是一种基于属性之间相关性的约简方法。

它通过计算属性之间的相关系数或互信息量来评估属性之间的相关性，并选择相关性较低的属性进行约简。

具体步骤如下：首先，计算属性之间的相关系数或互信息量。

然后，根据相关系数或互信息量的大小进行排序，选择相关性较低的属性作为初始约简。

接下来，逐步添加其他属性，并计算约简后的属性集的相关系数或互信息量。

如果添加属性后的相关性没有显著提高，则停止添加，得到最终的约简属性集。

3. 基于粒计算的约简方法基于粒计算的约简方法是一种基于粒度理论的属性约简方法。

它通过将属性集划分为不同的粒度，来减少属性的数量。

具体步骤如下：首先，将属性集划分为不同的粒度。

每个粒度包含一组相关性较高的属性。

然后，选择每个粒度中最为重要的属性作为初始约简。

接下来，逐步添加其他粒度，并计算约简后的属性集的重要性。

如果添加粒度后的重要性没有显著提高，则停止添加，得到最终的约简属性集。

4. 基于遗传算法的约简方法基于遗传算法的约简方法是一种基于进化计算的属性约简方法。

信息量的不完备信息系统属性约简方法信息量的不完备信息系统属性约简方法不完备信息系统是指存在一些未知或不可知的属性的系统。

约简是在保留系统重要特征的前提下，去除一些冗余的特征以降低系统的复杂性。

在不完备信息系统中，属性约简是一种重要的方法。

下面介绍一种基于信息量的不完备信息系统属性约简方法。

信息量是指某一事件的不确定性程度，用信息熵来表示。

对于一个不完备信息系统来说，我们可以通过已知的属性信息和属性取值进行估算和推测，然后计算出每个未知属性的信息熵。

如果一个属性在已知属性的条件下其信息熵较小，那这个属性就有更大的概率是有用的属性。

用这种方法求解属性约简，可以使得约简结果更具有实际意义和解释性。

具体步骤如下：1. 将不完备信息系统分为两类：已知属性集和未知属性集。

其中已知属性集包含在一些实例中已知的属性，未知属性集包含在这些实例中未知或不可知的属性。

2. 对于每个未知属性，计算在已知属性的条件下的信息熵。

假设一个未知属性 Ai，对于系统中任意的实例 X，已知属性集为 K，未知属性集为 U，该未知属性的取值为 Vi，那么该未知属性在已知属性集 K 的条件下的信息熵为：H(Ai|K) = -∑ (P(X|K) * log2 P(X|K))其中，P(X|K) 是在已知属性集 K 的条件下，未知属性 Ai 的取值为 Vi 的概率，根据贝叶斯定理可得P(X|K) = P(V1|K) * P(V2|K) * … * P(Vn|K)V1, V2, …, Vn 分别为未知属性集 U 中的属性取值。

3. 对于每个未知属性，计算其信息增益。

信息增益表示该属性对系统的分类能力，加入该属性后能够使得不完备信息系统的熵减少的程度。

信息增益的计算公式为：Gain(Ai|K) = H(U|K) - H(Ai|K)其中，H(U|K) 是在已知属性集 K 的条件下未知属性集 U 的信息熵。

4. 对于所有未知属性，按照信息增益从大到小排序，选择信息增益最大的属性加入已知属性集 K。

粗糙集理论的核心算法及其在实际问题中的应用粗糙集理论是一种用于处理不确定性和模糊性问题的数学工具，它能够在信息不完备或不准确的情况下进行决策和推理。

本文将介绍粗糙集理论的核心算法，并探讨其在实际问题中的应用。

一、粗糙集理论的核心算法粗糙集理论的核心算法主要包括粗糙集近似算法和粗糙集约简算法。

粗糙集近似算法是粗糙集理论最基本的算法之一，它用于将不完备或不准确的数据集划分为若干个等价类。

该算法基于属性重要性的概念，通过计算属性的正域和反域来确定属性的重要性，从而实现数据集的划分。

粗糙集约简算法是粗糙集理论中的关键算法，它用于从原始数据集中提取出最小的、具有相同决策规则的子集。

该算法通过计算属性的依赖度来确定属性的重要性，从而实现数据集的约简。

二、粗糙集理论在实际问题中的应用粗糙集理论在实际问题中有着广泛的应用，尤其在数据挖掘、模式识别和决策支持等领域。

在数据挖掘中，粗糙集理论可以用于特征选择和数据预处理。

通过粗糙集约简算法，可以从原始数据集中提取出最重要的特征，减少数据维度，提高数据挖掘的效率和准确性。

在模式识别中，粗糙集理论可以用于特征提取和模式分类。

通过粗糙集近似算法，可以对模式进行划分和分类，从而实现对复杂模式的识别和分析。

在决策支持中，粗糙集理论可以用于决策规则的生成和评估。

通过粗糙集约简算法，可以从原始数据集中提取出最简化的决策规则，为决策制定提供支持和指导。

除了以上应用，粗糙集理论还可以用于知识发现、智能推理和不确定性推理等领域。

它的优势在于能够处理不完备或不准确的信息，提供一种有效的决策和推理方法。

总结起来，粗糙集理论的核心算法包括粗糙集近似算法和粗糙集约简算法，它们在实际问题中有着广泛的应用。

通过粗糙集理论，可以处理不完备或不准确的信息，提高数据挖掘、模式识别和决策支持等领域的效率和准确性。

粗糙集理论为我们解决实际问题提供了一种有效的数学工具。

粗糙集属性约简的方法王培吉;赵玉琳;吕剑峰【期刊名称】《计算机工程与应用》【年(卷),期】2012(048)002【摘要】传统粗糙集分类方法过于严格,对噪音过分敏感.针对带不确定因子决策系统,提出一种基于属性依赖度的约简算法,使含不确定信息及数据噪音的系统中的属性得以简化,找到一种具有广泛表达能力的数据隐合格式,删去冗余的规则,并保持系统的原有用途和性能.通过一个例子实现了该算法.%Objects classification is strict excessively and too sensitive on noise. Aiming at decision system with uncertain factor, an al-gorithm of attribute reduction based on dependability is established. The attributes in the system with uncertain information and noise data are reduced, whereby finding a reducible implied pattern of the data, and deleting those redundant rules in the system. And it can keep the original properties and functions of the system. The implementation of algorithm is described by introducing an example.【总页数】4页(P113-115,129)【作者】王培吉;赵玉琳;吕剑峰【作者单位】内蒙古科技大学数理与生物工程学院,内蒙古包头014010;内蒙古第一机械集团公司二分公司,内蒙古包头014032;内蒙古科技大学数理与生物工程学院,内蒙古包头014010【正文语种】中文【中图分类】TP311【相关文献】1.利用蚁群优化算法的粗糙集属性约简方法 [J], 吴尚智;张文超;余志用;张霞;段超2.基于图的粗糙集属性约简方法 [J], MI Jusheng;CHEN Jinkun3.基于模糊粗糙集的辨识矩阵属性约简方法 [J], 赵晋欢; 王长忠4.改进粗糙集属性约简结合K‑means聚类的网络入侵检测方法 [J], 王磊5.基于k-原型聚类和粗糙集的属性约简方法 [J], 李艳;范斌;郭劼;林梓源;赵曌因版权原因，仅展示原文概要，查看原文内容请购买。

一种基于属性度量的快速属性约简算法属性约简是数据挖掘中非常重要的一项任务，是数据预处理的关键步骤之一。

属性约简的目的是去除冗余的属性，提高数据集的可处理性和可解释性。

在现实数据集中，经常存在大量的属性，且这些属性有一定的相关性，因此必须找到一个方法来减少属性数量和保留最重要的属性。

目前，基于属性度量的快速属性约简算法是一种被广泛研究和应用的方法。

本篇文章将讨论一种基于属性度量的快速属性约简算法。

1. 引言：对于实际问题，往往会涉及大量的属性，但这些属性可能会影响到我们最终得到的结论。

因此，属性约简就成为了一种非常重要的技术。

在属性约简的过程中，一个重要的概念是属性依赖。

属性依赖是指某个属性能否通过其他属性推出，而不需要利用所有的属性。

2. 基于属性度量的快速属性约简算法：基于属性度量的快速属性约简算法通过计算属性的不确定性和相关度来实现属性的筛选。

该算法主要有以下几个步骤：（1）初始化：将每个属性放入一个C和D中，其中C是原始属性集合，D是属性依赖集合。

（2）消除无用属性：对于一个属性a，如果其对于D中所有属性都是无用的，即对于任意X ⊂ C，a ⊈ (X)，则a是一个无用属性。

（3）计算属性相关度：对于一个属性a，其相关度的计算公式如下：相关度(A,B) = | supp(A,B) - supp(~A,B) - supp(A,~B) +supp(~A,~B) |其中supp(A,B)表示数据集中同时包含属性A和B的记录的个数，~A表示某个属性A的补集，即不包含A的集合。

（4）选择最优属性：在C中选择相关度最高的属性a，并将其添加到S中，S表示最终被选择的属性。

然后从D中删除与a相关的属性依赖，即将D中所有形如a -> y的依赖项删除。

（5）重复步骤（2）至（4）直到所有的属性都被计算完。

3. 算法优点：（1）时间复杂度低：该算法采用了计算属性相关度的方法，避免了对于所有子集的枚举，因此算法的时间复杂度较低。

函数依赖集闭包、属性集闭包、超键、候选键和最⼩函数依赖集的求法。

函数依赖集的闭包F：FD的集合称为函数依赖集。

F闭包：由F中的所有FD可以推导出所有FD的集合，记为F+。

例1，对于关系模式R(ABC)，F＝{A→B,B→C}，求F+。

根据FD的定义，可推出F+={φ→φ,A→φ,A→A,A→B,A→C,A→AB,A→BC,A→ABC,…}，共有43个FD。

其中，φ表⽰空属性集。

属性集闭包属性集闭包定义：对F，F+中所有X→A的A的集合称为X的闭包，记为X+。

可以理解为X+表⽰所有X可以决定的属性。

属性集闭包的算法：A+：将A置⼊A+。

对每⼀FD，若左部属于A+，则将右部置⼊A+，⼀直重复⾄A+不能扩⼤。

超键、候选键若X+包含R的所有属性，则X是超键。

当X不可约时则为候选键。

如上例：A+＝ABC，则A为超键，因为A不可约则为候选键。

设关系模式R中U=ABC.......等N个属性，U中的属性在FD中有四种范围：(1)左右出现;(2)只在左部出现;(3)只在右部出现;(4)不在左右出现;求候选键算法：1.R:只在FD右部出现的属性，不属于候选码;2.L:只在FD左部出现的属性，⼀定存在于某候选码当中;3.N:外部属性⼀定存在于任何候选码当中;4.其他属性逐个与2,3的属性组合，求属性闭包，直⾄X的闭包等于U,若等于U,则X为候选码。

例2，对于关系模式R(ABCD)，F＝{A→B,B→C,D→B}，求其候选键。

先按照属性集闭包的算法，求各个闭包,然后求得候选键。

(1) 求A+。

① A+＝A。

②由A→B，⽽A €A+可知，则A+＝AB。

③由B→C，⽽B A+可知，则A+＝ABC。

④ A+封闭，即A+＝ABC。

(2) 求B+、C+、D+。

按步骤(1)可得：B+＝BC，C+＝C，D+＝BCD。

(3) 求其候选键。

显然，R的候选键为AD。

例3，对于关系模式R(ABC)，F={A→BC,BC→A}，求其候选键。