An efficient accelerator for attribute reduction from incomplete data in rough set framework

Feature selection (attribute reduction) from large-scale incomplete data is a challenging problem in areas such as pattern recognition, machine learning and data mining. In rough set theory, feature selection from incomplete data aims to retain the discriminatory power of original features. To address this issue, many feature selection algorithms have been proposed, however, these algorithms are often computationally time-consuming. To overcome this shortcoming, we introduce in this paper a theoretic framework based on rough set theory, which is called positive approximation and can be used to accelerate a heuristic process for feature selection from incomplete data. As an application of the proposed accelerator, a general feature selection algorithm is designed. By integrating the accelerator into a heuristic algorithm, we obtain several modified representative heuristic feature selection algorithms in rough set theory. Experiments show that these modified algorithms outperform their original counterparts. It is worth noting that the performance of the modified algorithms becomes more visible when dealing with larger data sets.     

Rough集之间的相似度量

Applications of rough set theory in incomplete information systems are a key of putting rough set into real applications. In this paper, after analyzing some basic concepts of classical rough set theory and extended rough set theory, the measure of similarity is developed between two rough sets in the classical rough set theory based on indiscernibility relation and between two rough sets in the extended rough set theory based on limited tolerance relation. Then,some properties of these two methods for measuring similarity are developed respectively. At last,these two measure methods of rough set theory are compared.     

量化容差关系的程度多粒度粗糙集模型

多粒度粗糙集是一种重要的多粒度数据挖掘模型。为了对不完备信息系统中等价类重叠部分的定量信息进行挖掘,提出一种多阈值的量化容差关系程度多粒度粗糙集模型。首先将描述等价类重叠信息的程度多粒度粗糙集模型与处理不完备信息系统的量化容差关系进行结合,提出量化容差关系的程度多粒度粗糙集模型,然后在该模型的基础上,为每个粒度设定与数据相适应的阈值,提高了量化容差关系程度多粒度粗糙集模型的灵活性,增加多粒度数据挖掘的性能。UCI数据集的实验结果表明,本文所提出的粗糙集模型具有较好的分类效果和理论的可行性。     

不完备数据中面向特征值更新的增量特征选择方法

实际应用中,数据常常表现出不完备性和动态性的特点.针对动态不完备数据中的特征选择问题,提出了一种基于相容粗糙集模型和信息熵理论的增量式特征选择方法.首先,建立了不完备信息系统中特征值动态更新时论域上条件划分与决策分类的动态更新模式,分析了作为特征重要度评价准则的不完备相容信息熵的增量计算机制,并将该机制引入到启发式最优...     

基于容差关系的不完备可变精度多粒度粗糙集

在不完备信息系统中, 为了融合可变精度粗糙集和多粒度粗糙集的各自优点, 提出一种基于容差关系的不完备可变精度多粒度粗糙集模型。研究了基于容差关系的可变精度乐观多粒度粗糙集和悲观多粒度粗糙集的相关性质。通过对可变精度多粒度粗糙集和经典多粒度粗糙集的对比分析, 结果表明, 基于容差关系的不完备可变精度多粒度粗糙集拥有更高的近似精度, 实例分析的结果也验证了该理论的可行性。     

基于改进模糊决策粗糙集的最小化决策代价特征选择算法

模糊决策粗糙集是决策粗糙集理论在模糊集环境下的重要延伸,然而该模型对含噪声的数据不具有很好的容忍性。为此在传统的模糊相似关系中引入一个限定阈值,提出一种改进的模糊相似关系。在其基础上对原始的模糊决策粗糙集进行重构,提出一种改进的模糊决策粗糙集模型。根据不同的特征选择方式,利用所提出的改进模型设计出两种搜索策略的最小化决策代价特征选择算法。实验分析表明,该算法比传统算法具有更高的优越性。     

基于相容关系的基因选择方法

有效的基因选择是对基因表达数据进行分析的重要内容。粗糙集作为一种软计算方法能够保持在数据集分类能力不变的基础上,对属性进行约简。由于基因表达数据的连续性,为了避免运用粗糙集方法所必需的离散化过程带来的信息丢失,将相容粗糙集应用于基因的特征选取,提出了基于相容关系的基因选择方法。首先,通过i检验对基因表达数据进行排列,选择评分靠前的若干基因;然后,通过相容粗糙集对这些基因进一步约简。在两个标准的基因表达数据上进行了实验,结果表明该方法是可行性和有效性的。     

一种不完备信息系统的直接约简方法

目前已有基于容差关系、相似关系、限制容差关系等的扩充rough集理论，但仅仅是提出了一些针对以上某种模型的属性约简算法，在此提出从离散化到规则匹配的一系列不完备信息系统的约简处理方法，该方法可以适用于各种rough集扩充模型，并且对完备信息系统和不完备信息系统是统一的．     

Incomplete Information Tables and Rough Classification

The rough set theory, based on the original definition of the indiscernibility relation, is not useful for analysing incomplete information tables where some values of attributes are unknown. In this paper we distinguish two different semantics for incomplete information: the "missing value" semantics and the "absent value" semantics. The already known approaches, e.g. based on the tolerance relations, deal with the missing value case. We introduce two generalisations of the rough sets theory to handle these situations. The first generalisation introduces the use of a non symmetric similarity relation in order to formalise the idea of absent value semantics. The second proposal is based on the use of valued tolerance relations. A logical analysis and the computational experiments show that for the valued tolerance approach it is possible to obtain more informative approximations and decision rules than using the approach based on the simple tolerance relation.     

基于邻域关系模糊粗糙集的分类新方法

针对目前模糊等价关系所诱导的模糊粗糙集模型不能准确地反映模糊概念范畴中数值属性描述的决策问题,提出一种基于邻域关系的模糊粗糙集模型NR-FRS,给出了该粗糙集模型的相关定义,在讨论模型性质的基础上进行模糊化邻域近似空间上的推理,并分析特征子空间下的属性依赖性;最后在NR-FRS的基础上提出特征选择算法,构建使得模糊正域增益优于具体阈值的特征子集,进而剔除冗余特征,保留分类能力强的属性.采用UCI标准数据集进行分类实验,使用径向基核函数(RBF)支持向量机作为分类器.实验结果表明,同基于邻域粗糙集的快速前向特征选择方法以及核主成分分析方法(KPCA)相比,NR-FRS模型特征选择算法所得特征子集中特征数量依据参数变化更加平缓、稳定.同时平均分类准确率提升最好可以达到5.2%,且随特征选择参数呈现更加平稳的变化.     

基于概率矩阵分解的不完整数据集特征选择方法

在机器学习理论与应用中,特征选择是降低高维数据特征维度的常用方法之一。传统的特征选择方法多数基于完整数据集,对实际应用中普遍存在缺失数据的情形研究较少。针对不完整数据中含有未被观察信息和存在异常值的特点,提出一种基于概率矩阵分解技术的鲁棒特征选择方法。使用基于分簇的概率矩阵分解模型对数据集中的缺失值进行近似估计,以有效测量相邻簇之间数据的相似性,缩小问题规模,同时降低填充误差。依据缺失数据值存在少量异常值的情形,利用基于l_2,1损失函数的方法进行特征选择,在此基础上给出不完整数据集的特征选择方法流程,并对其收敛性进行理论分析。该方法利用不完整数据集中的所有信息,有效应对不完整数据集中异常值带来的影响。实验结果表明,相比传统特征选择方法,该方法在合成数据集上选择更少的无关特征,可降低异常值带来的影响,在真实数据集上获得了较高的分类准确率,能够选择出更为准确的特征。     

基于多粒度决策粗糙集的云计算产品分类方法

粗糙集理论中一个重要的研究课题是残缺区间决策系统.针对现有决策系统存在分类精度和质量较低的问题,结合可能性相似度容差关系的优良特性,并运用粗糙集理论,设计出一种新的多粒度决策模型.基于属性的视角,重新定义容差关系,并基于此方法,借鉴多粒度决策粗糙集具有一定容错能力和能够多层次处理数据的优势,结合粗糙集的优良特征,提出一...     

基于改进的完备容差关系的扩充粗糙集模型

经典粗糙集理论不能直接处理不完备信息系统,而容差关系、相似关系限制容差关系和完备容差关系等扩充粗糙集模型在一定程度上解决了这个问题。分析了这些模型存在的局限性,并在完备容差关系的基础上,提出了基于改进的完备容差关系的扩充粗糙集模型,该模型既保留了已有模型的优点,又在一定程度上克服了它们的局限性。实例分析表明该模型对不完备信息系统的处理更符合实际情况。     

基于τ限制容差关系的不完备信息粗糙集模型

对经典粗糙集理论进行适当扩充使其适用于不完备信息系统,是把粗糙集理论进一步推向实用的关键。在分析已有的几个不完备信息系统的粗糙集扩充模型的基础上,提出了τ限制容差关系,并将上近似、下近似、广义决策函数、区分矩阵等概念在该关系下进行了定义,最后通过实例说明了新模型相较于已有模型的优越性。     

Rough集理论在不完备信息系统中的扩充

Pawlak教授所提出的经典Rough集理论主要是针对完备信息系统的，利用了不可分辨关系这种等价关系来对对象进行了近拟和下近似分类，对于不完备信息系统的处理，需要对经典Rough集理论进行扩充，主要是对不可分辨关系进行扩充，目前已经有了基于容差关系，相似关系和量化容差关系等的扩充Rough集理论，但是，这些扩充也还存在一些局限性，将提出一种基于限制容差关系的扩充Rough集模型，并比较分析这些扩充Rough集模型之间的性能。     

基于邻域量化容差关系粗糙集模型的特征选择算法*

数值型不完备信息系统的特征选择方法大多是以容差关系为基础,但是这种处理方式存在数据相似性刻画过于宽松的缺陷.文中提出邻域量化容差关系的粗糙集模型,在该模型的基础上定义邻域量化容差条件熵,分析相关性质,根据邻域量化容差条件熵的单调性构造相应的特征选择算法.实验表明,文中算法在特征选择结果、运行时间和分类精度方面具有优越性.     

改进的对象间差异度的限制容差关系模型

不完备信息系统不能直接用经典的粗糙集理论来处理,为此,容差关系、非对称相似关系、限制容差关系、限制非对称相似关系、对象间差异度的限制非对称相似关系等扩充的粗糙集模型被相继提出。通过分析这些模型的优点和不足之处,定义了新的对象间差异度,提出了一种改进的对象间差异度的限制容差关系模型,实例结果表明基于所提出模型的划分更精确,更符合实际。     

基于模糊粗集的不完备信息表属性约简新算法

模糊粗糙集结合了粗集和模糊集的优点,是一种有效的数据处理理论,尤其在不完备信息表数据处理中。论文对Krysckiewcz容差关系模型加以改进,充分考虑信息表中属性取值的规律,构造模糊的二元不可分辨关系,运用模糊粗糙集理论,推广属性依赖性度量概念,给出了属性约简算法,并通过一个实例验证了它的有效性,为不完备信息表的数据处理提供了一些解决问题的思路。     

一种粗糙集理论中量化容差关系的改进

量化容差关系是粗集理论中一个最重要的扩展模型,然而它却有自己的局限性:需要诸如不完备信息系统中的属性值的概率分布情况等相关领域的知识。本文提出了一个量化容差关系的改进模型,这个新的模型是建立在对不完备信息系统的属性值的统计数据基础上的,它有效地克服了普通量化容差关系的不足。实例分析表明,改进的量化容差关系比原来量化容差关系更符合实际,具有更强的分辨能力。在进行缺失数据补齐时,改进的量化容差关系更适合于作为寻找最相似对象的基础,获得更高的补齐率。     

On generalized fuzzy rough sets

In this paper, a class of generalized fuzzy rough sets based on two universes are studied. Some new set-valued mappings and fuzzy set-valued mappings are introduced to discuss properties of the known model, and a new model for fuzzy rough sets is proposed which provides a new selection of interval structure for uncertainty reasoning using rough set theory. Some properties of the new model are revealed. The new model seems to be more natural in the sense that fuzzy sets are approximated by fuzzy sets on the same universe.