基于可辨识矩阵的启发式属性约简方法及其应用

在基于可辨识矩阵的属性约简算法的基础上，提出了基于可辨识矩阵的计算属性重要性的方法，并以此作为启发式知识来约简决策表中的冗余属性。这种方法直接源于评审数据，思路清晰，拟合结果表明本约简算法合理、可靠。     

基于差别矩阵启发式决策表属性约简算法

属性约简是粗糙集理论研究的核心内容之一,足知识获取的关键步骤.针对大规模数据集,基于决策表差别矩阵属性约简不具备可操作性缺点;以及基于差别矩阵属性频度的约简算法没有考虑到差别矩阵元素中属性个数多少的缺陷.基于差别矩阵元素的基数越小,其属性越重要的思想,按照基数由小到大的顺序,利用矩阵中具有相同基数的矩阵元素的簇集中属性出现的频度,确定属性的重要度,提出一种快速搜索属性约简算法,能快速搜索到属性的最优或次优约简.实验结果表明算法是可行、有效的.     

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

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

基于改进分辨矩阵的属性约简方法

在分辨矩阵的属性约简算法的研究中,需比较决策系统中各对象生成矩阵元素,导致所得分辨矩阵过于庞大,且造成较大的时间开销.为降低利用分辨矩阵求取属性约简算法的复杂度,依据条件等价类将原决策系统分解为一相容对象集与一非相容对象集,给出条件相对于决策的可辨识关系定义与改进的分辨矩阵定义,将条件相对于决策的可辨识关系变化作为属性约简的判定标准,结果证明改进分辨矩阵的属性约简与保持正域不变的属性约简等价.推理证明与仿真实例说明,改进方法的高效性与完备性.     

基于改进差别矩阵的属性约简增量式更新算法

针对目前基于差别矩阵的属性约简算法需要耗费大量的时间和空间,粗糙集中求属性核和属性约简更新效率低以及有关属性约简的增量式更新算法目前还比较少等问题,提出了一种基于改进差别矩阵的属性约简增量式更新算法.该算法在更新差别矩阵时,仅须插入某一行及某一列,或删除某一行并修改相应的列,因而可有效地提高核和属性约简的更新效率.然后在分析新增对象x与原决策系统对象的关系的基础上,给出了属性约简增量更新算法.理论与实验分析表明,提出的算法提高了属性约简的更新效率,明显降低了时间和空间复杂度.     

概率差别矩阵与不完备信息系统属性约简

差别矩阵的概念是基于粗糙集理论对信息系统进行属性约简的一个重要内容。针对不完备信息系统的属性约简本文提出了一种概率差别矩阵的概念与构造方法，给出了相关的定理。在此基础上提出了一种利用概率差别矩阵对不完备信息系统属性约简的方法，并给出了应用举例。     

新的可分辨矩阵及其约简方法

为了解决因决策表存在不相容性造成求核和属性约简的错误,首先通过增加一个属性列,将原始决策表相容化;然后创建可分辨矩阵,并给出核属性和属性约简的性质,同时证明了由该性质获得的核和属性约简与正区域的核和属性约简是等价的;最后设计属性约简算法及其改进算法,并通过实例验证了该方法的正确性.     

Approximations and reducts with covering generalized rough sets

The covering generalized rough sets are an improvement of traditional rough set model to deal with more complex practical problems which the traditional one cannot handle. It is well known that any generalization of traditional rough set theory should first have practical applied background and two important theoretical issues must be addressed. The first one is to present reasonable definitions of set approximations, and the second one is to develop reasonable algorithms for attributes reduct. The existing covering generalized rough sets, however, mainly pay attention to constructing approximation operators. The ideas of constructing lower approximations are similar but the ideas of constructing upper approximations are different and they all seem to be unreasonable. Furthermore, less effort has been put on the discussion of the applied background and the attributes reduct of covering generalized rough sets. In this paper we concentrate our discussion on the above two issues. We first discuss the applied background of covering generalized rough sets by proposing three kinds of datasets which the traditional rough sets cannot handle and improve the definition of upper approximation for covering generalized rough sets to make it more reasonable than the existing ones. Then we study the attributes reduct with covering generalized rough sets and present an algorithm by using discernibility matrix to compute all the attributes reducts with covering generalized rough sets. With these discussions we can set up a basic foundation of the covering generalized rough set theory and broaden its applications.     

广义约简、核与分辨矩阵

针对粗糙集理论中计算决策表核属性时出现的若干问题,讨论并分析了这些问题产生的原因.在此基础上,给出了不同目标下的广义约简定义,提出了必要区分关系和非必要区分关系等概念,由此给出了一般意义下的分辨矩阵定义.根据广义约简的定义,将已有的改进差别矩阵求核方法与早期Skowron等人提出的经典分辨矩阵求核方法作了对比,证明了两种方法完全相I司.     

基于区分矩阵的启发式属性约简算法

由于大量等价类元素的存在,同一等价类中的记录与其他非该等价类中的记录相比较将会产生大量空元素及重复元素,使得构造区分矩阵需要耗费大量的时间与空间。因此以信息向量为工具处理等价类,改进了区分矩阵的构造过程,有效地提高了构造区分矩阵的时空间效率;其次,利用属性频度为启发信息,给出了一种基于区分矩阵的启发式属性约简算法;最后,利用恒星天体光谱数据集,实验验证了算法的有效性。     

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

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

一种基于扩展差别矩阵的规则获取方法

本文对Skowron差别矩阵[1]进行扩展,提出了一种不求决策表属性约简,直接获取决策规则的方法.此外,该方法只需根据同一决策类中扩展差别矩阵元素来提取规则,且不会造成规则冲突,适合于分布规则提取.     

决策系统基于不可区分关系及区分关系的约简

信息系统中的知识约简和知识发现是粗糙集理论的重要研究方向。针对决策系统中的不可区分关系及区分关系,给出相应的协调集判定定理,进而借助区分矩阵及区分函数给出属性约简方法,并借助实例将其与已有的相关研究工作进行了对比分析。     

决策系统属性约简优化算法研究

属性约简是粗糙集理论研究的关键问题,针对求取决策系统所有约简的NP问题,基于差别矩阵提出一种决策系统属性约简优化算法.通过改进差别矩阵得到差别集,在获得核与约简候选信息基础上,以属性频度作为启发式信息,快速有效地求取决策系统的所有约简.分析表明了该算法的可行性与有效性.     

A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets

Traditional rough set theory is mainly used to extract rules from and reduce attributes in databases in which attributes are characterized by partitions, while the covering rough set theory, a generalization of traditional rough set theory, does the same yet characterizes attributes by covers. In this paper, we propose a way to reduce the attributes of covering decision systems, which are databases characterized by covers. First, we define consistent and inconsistent covering decision systems and their attribute reductions. Then, we state the sufficient and the necessary conditions for reduction. Finally, we use a discernibility matrix to design algorithms that compute all the reducts of consistent and inconsistent covering decision systems. Numerical tests on four public data sets show that the proposed attribute reductions of covering decision systems accomplish better classification performance than those of traditional rough sets.     

A systematic study on attribute reduction with rough sets based on general binary relations

Attribute reduction is considered as an important preprocessing step for pattern recognition, machine learning, and data mining. This paper provides a systematic study on attribute reduction with rough sets based on general binary relations. We define a relation information system, a consistent relation decision system, and a relation decision system and their attribute reductions. Furthermore, we present a judgment theorem and a discernibility matrix associated with attribute reduction in each type of system; based on the discernibility matrix, we can compute all the reducts. Finally, the experimental results with UCI data sets show that the proposed reduction methods are an effective technique to deal with complex data sets.     

基于改进差别矩阵和专家知识的态势指标提取算法

针对常规粗糙集约简算法在应用中的样本指标提取困难和效率低下等问题,将粗糙集理论引入到态势指标提取中,基于差别矩阵压缩和分类选择实现态势指标决策表的信息约简,结合专家知识的指标重要性度量调整态势指标的选择,提出一种基于改进差别矩阵和专家知识的态势指标提取算法.在态势指标体系实例中进行分析和验证,实验表明该算法具有较好的态势指标约简效果,提取后的指标在网络安全评估中是合理的,因此该研究为态势指标的有效提取提供一种可行的解决途径.     

一种基于区分矩阵的属性组合权重构造方法

详细分析了以基于Pawlak的属性重要度来构造属性权重的方法存在的问题,给出了一种基于区分矩阵的属性重要度的定义方法,并且得到了该定义方法的一些重要性质。在此基础上提出了一种新的信息系统属性权重构造方法,新方法是以条件属性在整个信息系统中的贡献度来确定属性权重,不仅反映了属性自身区分对象的能力,而且体现了各属性在整个条件属性中的分类能力。通过算例分析表明,该方法得到的属性权重更加贴近事实,因此它能提高属性权重的准确度。     

云计算环境下差别矩阵知识约简算法研究

知识约简是粗糙集理论的重要研究内容之一。经典的差别矩阵知识约简算法只能处理小数据集,而已有的任务并行的知识约简算法是假设所有数据一次性装入内存中,这显然不适合处理海量数据。为此,剖析了差别矩阵元素的特性,根据属性(集)的不可辨识性和云计算技术MapRcducc设计了适合数据并行的差别矩阵,并首次提出了面向大规模数据的差别矩阵知识约简算法。实验结果表明该知识约简算法是有效可行的,且具有较好的可扩展性。     

基于等价类矩阵的属性约简

由于不完备信息系统不能完全适用于粗糙集等价类模型,其合理的属性约简方法的研究在当前是一个备受关注的研究热点。文章给出不完备信息系统等价关系的矩阵表示,同时给出了关于等价类矩阵以及核属性的相关定理,给出了应用等价类矩阵进行属性约简的方法和应用举例,为不完备信息系统的属性约简提供了一种新的方法。