差别矩阵浓缩及其属性约简求解方法

属性约简是粗糙集理论的重要研究内容之一,已出现大量的属性约简算法,其中基于差别矩阵的属性约简算法是高效属性约简算法之一,但这些算法主要针对一致决策表,而对于不一致决策表,某些情况下不能得到属性约简。为此,本文提出改进的差别矩阵及其属性约简求解方法,统一考虑决策表一致和不一致情况两种情况下的属性约简,有效改进经典的基于差别矩阵求解属性约简的不足。同时,为适应大数据集属性约简需要,提出一种新的差别矩阵浓缩策略,以此提高属性约简的效率。     

基于元素约简的决策表属性约简算法

Skowron差别矩阵广泛应用于属性约简及求核运算,但它只适用于相容决策表,对于不相容决策表有时会得到错误的结果。虽然国内多位学者对它进行了改进,但一方面它们仍只适用于相容或部分相容决策表的属性约简,对完全不相容决策表仍得不到正确的结果。另一方面须通过额外的函数来约束差别矩阵的构造过程,增加计算负担。利用等价差别矩阵具有相同属性约简的思想,将元素对象分割成相容对象与矛盾对象,通过对参与构造差别矩阵的行与列元素进行约简,减少了某些重复计算过程,提高了计算效率。以此为基础,给出了一种改进的属性约简算法。数值算例验证了该算法是有效可行的。     

基于改进的Wap算法的Web序列模式的研究

基于不完备决策表的属性约简定义有多种,现研究基于知识粒度的属性约简。研究发现,差别矩阵是一种较好的设计属性约简算法的方法。为此,定义了一种粒度差别矩阵和基于该差别矩阵的属性约简,并证明了该差别矩阵的属性约简定义与基于知识粒度的属性约简定义等价。在此基础上,设计了一个新的基于信息量的不完备决策表的属性约简算法,其时间复杂度得以降低。     

Discernibility Matrix Algorithm of Attribute Reduction Based on Knowledge Granulaion in Incomplete Decision Table

基于不完备决策表的属性约简定义有多种,现研究基于知识粒度的属性约简.研究发现,差别矩阵是一种较好的设计属性约简算法的方法.为此,定义了一种粒度差别矩阵和基于该差别矩阵的属性约简,并证明了该差别矩阵的属性约简定义与基于知识粒度的属性约简定义等价.在此基础上,设计了一个新的基于信息量的不完备决策表的属性约简算法,其时间复杂度得以降低.     

一个新的差别矩阵及其在决策表中的应用

在利用差别矩阵求解决策表的相对核方法中,针对HU方法的错误,人们提出了各种各样新的差别矩阵及求相对核的方法,但计算代价高.把决策属性与条件属性放在一起构造出一个新的差别矩阵,得到了差别矩阵的若干性质和定理.在此基础上提出了求决策表的正区域、相对核、相对约简和最小约简的新算法,分析了该算法的时间复杂性.理论分析和实例表明,与现有的属性约简算法相比,该算法的时间复杂性较低.     

基于粗糙属性向量树的属性约简新方法

在对区分能力大小研究的基础上建立了一个用于指导信息表的绝对属性约简的粗糙集模型, 同时在对区分能力和分类能力二者关系深入研究的基础上提出了决策依赖区分精度新概念,该概念是用于指导决策表的、相对属性约简的一个新的判据.借助粗糙属性向量树提出了新的求全部属性约简的算法, 通过理论分析说明了新算法的最坏时间复杂度低于经典的"基于差别矩阵求全部属性约简算法"以及它的改进算法.对比实验结果验证了该算法在运算效率上明显高于"基于差别矩阵求全部属性约简算法"的改进算法.     

基于数组的增量式属性约简研究*

为了在动态变化的决策表中,快速方便地获得新的属性约简,利用数组元素对差别矩阵中的属性组合进行计数,提出一种基于数组的增量式属性约简更新算法。当决策表动态变化时,根据数组元素的取值变化,获得差别矩阵中增加和减少的元素,依据这些元素更新原属性约简,快速得到新的最小属性约简。理论分析及实例验证了提出的算法是有效的。     

决策表化简及其属性约简方法

给出一种求不一致决策表的核和所有属性约简的新方法,首先利用U/C对决策表进行化简,然后在简化的决策表上定义新的差别矩阵,最后利用差别函数求出所有属性约简.该方法可有效降低生成差别矩阵时所需的存储空间和时间,理论分析和例子表明,该属性约简方法在效率上比现有的基于差别矩阵和差别函数的方法有显著提高.     

不完备决策表的差别矩阵属性约简算法

给出一个差别矩阵的属性约简定义,证明该属性约简的定义与广义决策属性约简的定义是等价的,对差别矩阵进行了有效的压缩。在此基础上,为求出不完备决策表的属性约简,设计了一个基于该差别矩阵的不完备决策表属性约简算法,其时间复杂度为O(|C|2|U|2),最后用实例说明了该算法的有效性。     

相容矩阵的高效属性约简算法

给出完备决策表和不完备决策表的定义并说明相容关系.给出了相容矩阵及其属性约简的定义,同时也给出差别矩阵及其属性约简的定义,证明了基于相容矩阵的属性约简与关于差别矩阵的属性约简定义是等价的,给出了一个计算条件属性的频率的公式,该公式不必计算差别矩阵,而是直接从决策表中计算出各条件属性在差别矩阵中出现的频率.设计一个快速计算条件属性频率的快速算法,在此基础上,设计了一个高效求基于相容矩阵的属性约简算法,并通过实例对该算法进行了验证.实践证明:算法的复杂度都得以降低,该算法的时间复杂度为O(|C|2|U|),空间复杂度为O(|U|).该方法为计算其他的属性约简算法提供了一条新思路.     

信息观下基于不一致邻域矩阵的属性约简

信息观下研究邻域决策系统的属性约简是一种新颖的思路. 通过分析论域下某样本邻域中其他样本与该样本决策属性值的异同, 定义不一致邻域矩阵. 在计算属性重要度时, 利用不一致邻域减少在原条件属性基础上增加一个属性后条件熵的计算时间. 分析得到邻域系统下条件熵与正域的关系, 提出一种信息观下基于不一致邻域矩阵的属性约简算法, 并分析该算法与其他算法的内在联系. 实验结果验证了所提出算法的有效性.

     

基于粒度决策熵的属性约简

近年来,人们越来越关注粗糙集中的属性约简算法,尤其是启发式的约简算法。为了度量属性重要度,人们把各种不同的信息熵模型应用到粗糙集中,同时在信息熵这一理论的基础上得出了许多约简算法,用来解决粗糙集中属性约简的问题。然而,现有的基于信息熵的方法还存在一系列问题。针对这些问题,本文首先将知识粒度与相对决策熵这2个概念结合在一起,从而引入一种新的信息熵模型--粒度决策熵;然后,利用粒度决策熵来度量属性的重要性,并由此得出新的约简算法--ARGDE约简算法;最后,用不同的UCI数据集来做实验,通过与已有的约简算法比较,该算法能够得到更好的实验结果。     

基于相对可辨识矩阵的决策表属性约简算法

针对现有属性约简算法存在的问题,利用信息论和粗糙集理论,提出一种基于相对可辨识矩阵的决策表属性约简算法.该算法以核属性为基础,通过建立相对可辨识矩阵,利用条件信息熵作为启发式信息,减少属性约简过程中的搜索空间,逐个添加条件信息熵最大的属性,直到找出最小约简为止,并分析了该算法的时间复杂度.实例分析结果表明,该算法能有效地对决策表属性进行约简.     

基于辨识集的属性约简算法

为了过滤掉不相关或相关程度较低的属性,就必须使用属性约简算法,从而使得属性约简成为粗糙集中一个核心的研究课题。基于差别矩阵的属性约简算法求解时总是先要求出差别矩阵,当问题规模增大时,将导致存放差别矩阵的空间过大和算法执行时间过长。针对这一问题,本文提出辨识集的定义,并利用辨识集设计一个新的属性约简算法。新算法在属性约简过程中不生成差别矩阵和大量的无用元素,大大减少存储量和计算量,从而提高算法的效率。实验验证了新算法的高效性。     

连续型数据的辨识矩阵属性约简方法

属性约简是粗糙集理论在数据处理方面的重要应用,已有的针对连续型数据的属性约简算法主要集中在基于正域的贪心算法,该方法只考虑了一致样本和其他样本的可辨识性,而忽略了边界样本点间可区分性。为了克服基于正域算法的缺点,提出了连续型数据的辨识矩阵属性约简模型,该模型不但考虑了正域样本的一致性,同时考虑了边界样本的可分性。基于该模型,分析了属性约简结构,定义了辨识矩阵来刻画特征子集的分类能力,构造了实值型数据的属性约简启发式算法,并利用UCI标准数据集进行了验证。理论分析和实验结果表明,提出的算法能够有效地处理连续型数据,提高了数据的分类精度。     

An incremental algorithm for attribute reduction with variable precision rough sets

Attribute reduction with variable precision rough sets (VPRS) attempts to select the most information-rich attributes from a dataset by incorporating a controlled degree of misclassification into approximations of rough sets. However, the existing attribute reduction algorithms with VPRS have no incremental mechanisms of handling dynamic datasets with increasing samples, so that they are computationally time-consuming for such datasets. Therefore, this paper presents an incremental algorithm for attribute reduction with VPRS, in order to address the time complexity of current algorithms. First, two Boolean row vectors are introduced to characterize the discernibility matrix and reduct in VPRS. Then, an incremental manner is employed to update minimal elements in the discernibility matrix at the arrival of an incremental sample. Based on this, a deep insight into the attribute reduction process is gained to reveal which attributes to be added into and/or deleted from a current reduct, and our incremental algorithm is designed by this adoption of the attribute reduction process. Finally, experimental comparisons validate the effectiveness of our proposed incremental algorithm.     

面向一致性样本的属性约简

作为粗糙集理论的一个核心内容,属性约简致力于根据给定的约束条件删除数据中的冗余属性。基于贪心策略的启发式算法是求解约简的一种有效手段,这一手段通常使用数据中的全部样本来度量属性的重要度从而进一步得到约简子集。但实际上,不同样本对于属性重要度计算的贡献是不同的,有些样本对重要度贡献不高甚至几乎没有贡献,且当数据中的样本数过大时,利用全部样本进行约简求解会使得时间消耗过大而难以接受。为了解决这一问题,提出了一种基于一致性样本的属性约简策略。具体算法大致由3个步骤组成,首先,将满足一致性原则的样本挑选出来;其次,将这些选中的样本组成新的决策系统;最后,利用启发式框架在新的决策系统中求解约简。实验结果表明:与基于聚类采样的属性约简算法相比,所提方法能够提供更高的分类精度。     

粒计算中基于属性分类的形式概念属性约简

针对目前已有的形式概念属性约简算法的不足(如属性约简的时间复杂度偏高、属性及属性值比较过程中存在冗余计算、存储开销大等问题),结合粒计算思想,提出基于属性分类的形式概念属性约简模型.首先,通过定义两个算子来划分属性之间分类关系;然后,由属性分类关系制定约简规则,并在此基础上提出基于属性分类的形式概念约简算法,该算法在保持目前最低时间复杂度不变的情况下,减少了冗余计算和存储开销,提高了属性约简的计算效率;最后,通过实例和仿真实验对基于属性分类关系的形式概念属性约简算法的有效性进行了验证.     

决策表分解及其最小属性约简研究

现有的很多属性约简算法都是由构造决策表的差别矩阵出发,将矩阵中非空元素的合取范式转化为极小析取范式。为提高对大规模数据的决策表进行约简的效率,文中指出基于U/{a}划分的最小约简算法存在的缺陷,给出以划分粒度为启发式信息,利用单个条件属性把论域划分成多个等价类,将计算整个全域上的属性约简问题转化为计算在相应划分的子区域上属性约简问题,提出了一种基于决策表分解的最小属性约简算法。理论分析和实例表明该约简算法是有效的。     

基于优化可辨识矩阵和改进差别信息树的属性约简算法

运用可辨识矩阵表示信息系统中所有对象的区分信息,为研究属性约简提供了新方向。然而,传统的可辨识矩阵在构造结束后才利用核属性消除冗余元素项,忽略了核属性在矩阵构建过程中的作用。针对这一问题,文中做了以下研究:1)优化可辨识矩阵的构造方式,在计算任意两个对象的区分信息之前,先判断核属性上的取值是否相等,如果不相等,则直接将对应元素项记为Φ,忽略对其他条件属性的判断;2)提出属性加权重要度的概念,综合考虑每个条件属性占可辨识矩阵中非空元素项的比率(称为宏观重要度)与每个属性对区分对象的贡献程度(称为微观重要度),并通过例子说明了该度量方法的合理性;3)针对优化后的矩阵仍然存在大量冗余元素和空集这一缺陷,结合差别信息树的概念提出基于优化可辨识矩阵和属性加权重要度的差别信息树。按照属性加权重要度对优化可辨识矩阵中所有非空元素项进行排序,使得重要度高的属性被更多的节点共享;且在构建过程中将不包含核属性的元素项映射到树中的一条路径上,而包含核属性的元素项则被直接忽略。最后,提出基于优化可辨识矩阵和改进差别信息树的约简算法HSDI-tree。在UCI的5个数据集上分别比较了HSDI-tree算法与CDI-tree,DI-tree和IDI-tree算法的约简结果和节点个数,实验结果表明HSDI-tree算法能有效找到最小属性约简且空间压缩能力更好。