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.     

一种基于rough集的属性约简的改进算法

目前粗糙集属性约简基本上是通过差别矩阵先求出属性核,然后在属性核的基础上再求出属性约简。这种计算方法具有较高的复杂度。因此提出并分析了属性的加权平均重要性的属性约简算法,该算法可以确保得到决策表的一个约简,且不需要计算核,减少计算量,提高计算速度。以实例验证了算法的正确性。     

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.     

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.     

Parameterized attribute reduction with Gaussian kernel based fuzzy rough sets

Fuzzy rough sets are considered as an effective tool to deal with uncertainty in data analysis, and fuzzy similarity relations are used in fuzzy rough sets to calculate similarity between objects. On the other hand in kernel tricks, a kernel maps data into a higher dimensional feature space where the resulting structure of the learning task is linearly separable, while the kernel is the inner product of this feature space and can also be viewed as a similarity function. It has been reported there is an overlap between family of kernels and collection of fuzzy similarity relations. This fact motivates the idea in this paper to use some kernels as fuzzy similarity relations and develop kernel based fuzzy rough sets. First, we consider Gaussian kernel and propose Gaussian kernel based fuzzy rough sets. Second we introduce parameterized attribute reduction with the derived model of fuzzy rough sets. Structures of attribute reduction are investigated and an algorithm with discernibility matrix to find all reducts is developed. Finally, a heuristic algorithm is designed to compute reducts with Gaussian kernel fuzzy rough sets. Several experiments are provided to demonstrate the effectiveness of the idea.     

一种实域粗糙集模型及属性约简方法

通过对实域区间和决策值的重新划分,对已经存在的属性广义重要度度量准则进行了扩展,构建了对象空间上的广义邻域关系及广义邻域关系下的实域粗糙集模型,并在此基础上提出了实域决策系统中属性约简方法(ARRDDS).对不同数据集的实验测试结果表明,与其他相关方法相比,ARRDDS方法能够较好地处理决策表中实数域属性约简问题.     

基于粗糙集的属性约简方法研究综述*

针对经典粗糙集理论的属性约简,从三个方面对属性约简方法进行综述。最后对属性约简中存在的问题进行了分析,并提出了进一步研究的方向。     

基于粗糙集和信息增益的属性约简改进方法

针对属性过多对于有效的数据挖掘很不利以及约简中差别矩阵的产生会占用较大存储空间的问题,提出了一种基于粗糙集和信息增益的属性约简改进算法.该算法首先采用信息增益技术对决策表属性进行相关分析,删除部分冗余属性,减小属性约简的复杂度,然后直接从决策表中提取出分明函数,求出属性约简.由于避免了分明矩阵的生成,因此该算法不仅节约了时间和空间,而且提高了效率.     

一种粗糙集属性约简的伪粒子群算法

针对高维数据集的属性约简问题,通过改变经典粒子群算法的运动方程,并用属性依赖性和属性子集特征数构造适应度函数,提出以决策表核属性为基础的最小属性子集搜寻策略。实验结果表明,与其他类型的最小属性约简算法相比,该算法不仅能有效提高获得最小属性约简的机率,同时还大大降低了计算时间。     

一种基于粗集理论的属性约简改进算法

利用粗集理论中属性的依赖度和重要度性质,提出一种对数据属性进行约简的改进算法,对该算法进行分析,并运用一个简单的例子对该算法的有效性进行验证。     

置换矩阵算法在粗糙集属性约简中的应用

介绍了粗糙集的布尔矩阵表示和置换矩阵的概念,导出了属性约简与置换矩阵之间的关系,讨论了逻辑关系方程组解的理论,提出了基于置换矩阵的粗糙集属性约简的新算法,通过实例分析证明了该方法的有效性,表明该算法在粗糙集属性约简中具有参考价值,对粗糙集理论的应用具有一定的实际意义。     

基于可辨识矩阵的快速粗糙集属性约简算法

Karno Bozi提出的Core Searching算法在向约简中插入候选属性的时候,根据属性出现次数需要循环查找可辨识矩阵中的所有剩余项,直至矩阵为空,导致计算量较大和结果中冗余属性存在的可能.基于Core Searching算法提出通过给属性设立计数器的基于可辨识矩阵的快速属性约简算法,实例分析表明,该算法与Core Searching算法相比,在计算量减少和循环次数减少的同时能得到更简约的结果,是一种快速、高效的属性约简算法.     

一种基于改进区分矩阵的属性约简算法

现有的很多约简算法都是由构造决策表的区分矩阵出发,将矩阵中非空元素的合取范式转化为极小析取范式。但是,基于Skowron提出的区分矩阵约简算法对不相容决策表会产生错误的结果。为此,提出一种改进的区分矩阵的定义,以及基于此区分矩阵的属性约简算法,该算法对相容或不相容决策表都是适用的,特别对不相容决策表会得到更加稀疏的区分矩阵,可大大节省计算时间和存储空间,该算法是一种简单、有效、普遍适用的求解属性约简方法。     

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

属性约简是粗糙集理论的重要研究内容之一,目前已有许多属性约简算法。但这些算法中主要针对一致决策表,当决策表是不相容的情况下,常用的计算全部属性约简的差别矩阵算法会产生错误的结果。为了解决这个问题,引入了一个改进的二进制分辨矩阵,提出了一种基于改进的二进制分辨矩阵的属性约简算法。并利用上述算法结合实例进行属性约简,证明了算法的正确性和有效性。     

An enhancement for heuristic attribute reduction algorithm in rough set

Attribute reduction is one of the most important issues in the research of rough set theory. Numerous significance measure based heuristic attribute reduction algorithms have been presented to achieve the optimal reduct. However, how to handle the situation that multiple attributes have equally largest significances is still largely unknown. In this regard, an enhancement for heuristic attribute reduction (EHAR) in rough set is proposed. In some rounds of the process of adding attributes, those that have the same largest significance are not randomly selected, but build attribute combinations and compare their significances. Then the most significant combination rather than a randomly selected single attribute is added into the reduct. With the application of EHAR, two representative heuristic attribute reduction algorithms are improved. Several experiments are used to illustrate the proposed EHAR. The experimental results show that the enhanced algorithms with EHAR have a superior performance in achieving the optimal reduct.     

基于GA-PSO的粗糙集属性约简算法

属性约简是粗糙集合研究的重要内容之一。为了能够有效地获取决策表中属性最小相对约简,提出了一种基于GA-PSO的属性约简算法。该算法以条件属性对决策属性的支持度为基础,求解核属性,把所有的条件属性(除去核属性)加入粒子群算法的初始种群中,并用遗传算法对不满足适应度条件的粒子进行交叉变异操作。实验结果表明,该算法在加强局部搜索能力的同时保持了该算法全局寻优的特性,能够快速有效地获得最小相对属性集。     

粗糙集属性约简的方法

传统粗糙集分类方法过于严格,对噪音过分敏感。针对带不确定因子决策系统,提出一种基于属性依赖度的约简算法,使含不确定信息及数据噪音的系统中的属性得以简化,找到一种具有广泛表达能力的数据隐含格式,删去冗余的规则,并保持系统的原有用途和性能。通过一个例子实现了该算法。     

一种基于粗糙集属性约简的多分类器集成方法

为提高多分类器系统的分类精度,提出了一种基于粗糙集属性约简的分类器集成方法 MCS_ARS。该方法利用粗糙集属性约简和数据子集划分方法获得若干个特征约简子集和数据子集,并据此训练基分类器;然后利用分类结果相似性得到验证集的若干个预测类别;最后利用多数投票法得到验证集的最终类别。利用UCI标准数据集对方法 MCS_ARS的性能进行测试。实验结果表明,相较于经典的集成方法,方法 MCS_ARS可以获得更高的分类准确率和稳定性。     

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.     

一种基于区分矩阵的属性约简算法

属性约简是粗糙集理论研究的关键问题之一。文章以属性在区分矩阵中出现的频率作为启发,对HORAFA算法做了一些改进。它是以核为基础,加入属性重要性最大的属性,直到不能再加。为了能找到信息系统的最优约简,在此基础上加了一个反向消除过程,直到不能再删为止。最后通过一个实例完整演示了该方法,证实其有效性。