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.     

基于分辨矩阵和属性重要度的规则提取算法

研究了Rough集理论中的属性约简和值约简问题,将分辨矩阵引入值约简中,从属性依赖度的角度重新定义了属性重要度,提出了基于分辨矩阵和属性重要度的分类规则提取算法。该算法在保持分类能力不变的前提下,得到最小属性约简,再经过值约简后得到精确的规则,与现有算法相比,能减少时间和空间耗费。实验结果验证了该算法的有效性。     

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

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

同可区分度属性约简的研究

通过具体算例指出基于同可区分度属性约简不是王国胤等提出的条件信息熵约简。理论上证明了基于同可区分度属性约简仅是基于差别矩阵的HU属性约简,它是一种基于梁吉业等提出的新条件信息熵属性约简。证明了同可区分度约简协调集一定是代数协调集和信息熵协调集,从而代数约简核属性和信息熵核属性一定是同可区分度约简核属性的子集。     

一种高效的增量式属性约简算法

针对粗糙集中求属性核和属性约简存在的问题,首先给出了改进的差别矩阵定义,进而提出一种基于改进差别矩阵的核增量式更新算法,用于解决对象动态增加情况下核的更新问题;同时,为了降低现有增量式属性约简算法的时间、空间复杂度,提出一种不存储差别矩阵的高效属性约简算法,用于处理对象动态增加情况下属性约简的更新问题.理论分析及实验结果均表明了所提出算法的有效性和可行性.     

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

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

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.     

基于幂图的属性约简

针对粗糙集理论中基于差别矩阵的属性约简方法存在的不足,提出一种基于幂图的属性约简算法.首先通过修改样本决策属性值将不相容决策表转化为简化的相容决策表;然后将样本对概念与幂图概念相结合,将基于修正差别矩阵的不相容决策表的属性约简转化为幂图的搜索问题;最后通过实例和实验验证了所提出算法的有效性.     

基于粗糙集的犹豫模糊多属性决策方法

针对属性值为犹豫模糊元的决策问题,提出一种基于粗糙集理论的多属性决策方法.首先,依据属性值与理想点的贴近度和给定的阀值得到判断矩阵;然后,根据判断矩阵对属性集进行约简,确定属性权重;最后,基于TOPSIS思想,计算各方案与理想点的综合贴近度,得到方案的优劣次序,并通过算例分析表明了该方法的有效性.     

Knowledge acquisition in vague objective information systems based on rough sets

Abstract: The growing volume of vague information poses interesting challenges and calls for new theories, techniques and tools for analysis of vague data sets. In this paper, we study how to extract knowledge from vague objective information systems (VOISs) based on rough sets theory. We first introduce the basic notion termed rough vague sets by combining rough sets theory and vague sets theory. By using the rough vague lower approximation distribution in the VOIS, the concept of attribute reduction is introduced. Then, we develop an algorithm based on a discernibility matrix to compute all the attribute reductions. Finally, a viable approach for extracting decision rules from the VOIS is proposed. An example is also presented to illustrate the application of the proposed theories and approaches in handling medical diagnosis problems.     

混合值不完备决策信息系统的粗糙分类方法

针对混合值不完备决策信息系统,提出一种将邻域联系度粗糙集与贝叶斯理论相结合的分类方法。定义了一种新的属性辨识矩阵——同异反辨识矩阵,给出了基于同异反辨识矩阵的t分配约简算法,以及对约简后的决策信息系统建立基于邻域联系度粗糙集的最小错误率贝叶斯决策准则,用于对含有混合属性值以及不完备数据的对象进行分类。实验表明所提出的方法是客观有效的。     

基于粗糙集的直觉模糊TOPSIS多属性决策方法

针对属性值为直觉模糊信息且属性权重完全未知的多属性决策问题,提出了一种基于粗糙集的直觉模糊TOPSIS多属性决策方法.首先给出了直觉模糊信息的正、负理想点的求法,根据属性值与理想点的贴近度和给定的阈值求得判断矩阵,再根据判断矩阵对属性约简,确定各属性的权重,最后依据TOPSIS思想计算各方案与理想点的加权贴近度,得到方案的排序,并通过算例的分析比较验证了此方法的有效性.     

基于二进制区分矩阵的约简算法研究

给出了一种基于二进制区分矩阵的约简方法.首先基于粗糙集理论定义了二进制区分矩阵及运算规则、基于二进制区分矩阵的最小约简的判别及属性重要性的计算方法.在定义的基础上,给出了基于二进制区分矩阵的求核算法、相对属性约简算法及值约简算法.该约简方法以位操作为主与传统的约简方法比较不包括复杂的逻辑化简和集合运算,在一定程度上简化了计算,提高了约简效率.将该算法应用于数字电路设计的开关电路综合中,得到最简数字电路的逻辑表达,从而说明了算法的有效性.     

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

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

Fuzzy rough set based attribute reduction for information systems with fuzzy decisions

Fuzzy rough set is a generalization of crisp rough set to deal with data sets with real value attributes. A primary use of fuzzy rough set theory is to perform attribute reduction for decision systems with numerical conditional attribute values and crisp (symbolic) decision attributes. In this paper we define inconsistent fuzzy decision system and their reductions, and develop discernibility matrix-based algorithms to find reducts. Finally, two heuristic algorithms are developed and comparison study is provided with the existing algorithms of attribute reduction with fuzzy rough sets. The proposed method in this paper can deal with decision systems with numerical conditional attribute values and fuzzy decision attributes rather than crisp ones. Experimental results imply that our algorithm of attribute reduction with general fuzzy rough sets is feasible and valid.     

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

在基于二进制分辨矩阵的属性约简方法中,删除法即从属性全集中依次删除冗余属性,直至剩余的属性集是一个最小约简.针对传统的基于二进制分辨矩阵的删除法效率较低且得不到最小约简的问题,提出一种改进的二进制分辨矩阵属性约简方法.首先对决策表进行简化,然后给出一种改进的简化二进制分辨矩阵方法;其次通过一个新的属性约简度量方法一次性删除多个属性,并从理论上分析了该方法的可行性;最后通过实验证明了得到的约简结果是最小约简.     

变精度极大相容块粗糙集模型及其属性约简

主要研究不完备信息系统的属性约简问题。首先基于极大相容块构造乐观和悲观两种广义变精度粗糙集模型,分析两种模型之间的关系并研究其主要性质。在此基础上,定义乐观(悲观)β-下分布约简和β-上分布约简并且给出相应的判定定理,进而得到一种保持决策类上(下)近似分布不变的属性约简方法--布尔计算方法。这种构造极大相容块间的辨识矩阵的方法缩小了矩阵的规模,进而简化了计算属性约简的过程,从而能够有效地节省计算时间和存储空间。然后对含有"丢失""不关心"值和只有"不关心"值的两种不完备信息系统进行实例分析,最后从UCI数据集中选取5组不完备信息数据集来验证方法的有效性。     

基于水平划分决策表的核属性求解算法

核属性求解是粗糙集理论的主要研究内容之一。针对现有差别矩阵求核算法的不足,给出决策差别矩阵定义和水平划分决策表方法。提出在子决策表上创建子决策差别矩阵,进行核属性求解的方法;并证明了由该方法获得核与正区域核是等价的,同时设计相应的串行和并行求核算法。实例分析和实验比较表明所提出的求核算法是正确的、高效的。     

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

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

基于粗糙集决策网络的故障诊断规则提取方法

针对故障诊断信息的不一致性,提出一种基于粗糙集决策网络的故障规则提取方法。将故障诊断决策系统通过分辨矩阵和分辨函数进行属性约简后,构造出一个不同简化层次的决策网络。将属性约简集作为网络初始节点,根据网络节点得到决策规则集;同时,为了有效滤除噪声,在置信度的基础上引入了规则覆盖度的概念,对提取的规则进一步评价,最终提取有效的诊断规则。旋转机械故障实例验证了该方法的有效性。