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

属性约简是Rough集理论的核心内容之一，计算所有的属性约简已经被证明是NP完全问题．在深入研究Rough集理论的基础上，仔细分析了对象集的增加与属性约简的关系，给出了增量式属性约简的判定定理，从而提供了计算所有属性约简的增量式算法，分析了算法的时间复杂度．理论分析和实验结果表明，该约简算法在效率上较现有的算法有显著提高．     

一种新的快速计算正区域的方法

Rough集理论是一种新型的处理模糊性和不确定性知识的数学工具，正区域是该理论的核心概念之一，如何有效地计算正区域对提高各相关算法的性能至关重要．在对比Rough集理论进行深入研究的基础上，提出且证明了一种新的快速计算正区域的方法，并进一步分析了正区域的渐增式计算，最后给出了详细的算法描述和时间复杂度分析．理论分析和实验结果表明，该方法能够有效地降低计算复杂度，在效率上较现有的方法有显著提高．     

关系决策系统中相对不可区分和区分关系的约简

针对相对不可区分和区分关系约简的问题提出相应的算法。首先，考虑等价关系中相对不可区分关系的约简，提出一种新的辨识矩阵，并在此基础上得到了一种约简算法，通过关系的补关系提出相对区分关系的约简算法。然后，将相对不可区分关系等概念推广到一般关系。对于关系决策系统的相对不可区分关系约简给出了相应的辨识矩阵，并利用关系的补关系得到了相对区分关系约简的辨识矩阵，从而得到了两者的约简算法。最后，在选取的UCI数据集上，对提出的算法进行验证。在等价关系上，基于绝对约简的相对不可区分关系的约简（EQIND）算法与相对不可区分一般关系的约简（BⅡND）算法所得约简相同，基于绝对约简的相对区分关系的约简（EQDIS）算法与相对区分一般关系的约简（BIDIS）算法所得约简相同；同时算法BⅡND、BIDIS可以对不完备决策表进行约简。实验结果验证了所提算法的可行性。     

一种基于Rough集的层次聚类算法

Rough集理论是一种新型的处理含糊和不确定性知识的数学工具，将Rough集理论应用于知识发现中的聚类分析，给出了局部不可区分关系、个体之间的局部不可区分度和总不可区分度、类之间的不可区分度、聚类结果的综合近似精度等定义，在此基础上提出了一种基于Rough集的层次聚类算法，该算法能够自动调整参数，以寻求更优的聚类结果。验结果验证了该算法的可行性，特别是在符号属性聚类方面有较好的聚类性能。     

一种属性与值约简简化算法

Rough Set理论是处理不确定性知识、不完整数据的重要工具，在Rough Set中属性最小约简与规则提取NP—hard的．本文针对现有属性约简与值约简算法的问题，分析了区分矩阵的特性，在此基础上，提出了属性与值约简的简化算法，并用实例作了验证．     

ROUGH集决策表约简二进制形式化方法

基于属性约简的分明矩阵方法的思想,本文提出Rough集不可分明关系和不可分明集概念,给出了基于二进制的条件属性约简和属性值约简方法,该方法在形式上更加简单,二进制参加运算,运算速度快,并通过示例说明了该方法比传统的Rough集理论中的方法更优越.     

基于二进制的Rough集决策表约简

基于属性约简的分明矩阵方法的思想，该文提出了Rough集不可分明属性模式和属性关系的概念，给出了基于二进制的条件属性约简和属性值约简方法，结果说明，该方法比传统的Rough集理论中的方法更简便、快捷。     

不完备决策表的启发式知识约简算法研究

经典Rough集理论是基于完备信息系统的。然而在实际应用中,由于数据存取或数据处理方面的原因,决策表经常是不完备的,即存在缺值。为了处理不完备信息系统,Kryszkiewicz提出了基于容差关系的Rough集模型。在该模型下进行知识约简时,现有的算法一般都采用构造区分矩阵和相应区分函数的方法。该方法虽然可以求得所有约简,然而业己证明这是一个NP-hard问题,因此实践中更为可行的方法是利用启发式搜索算法求出最优或次最优约简。在文中提出属性的重要性定义,并以此作为启发式信息,设计一种完备的知识约简算法。     

扩展正区域的属性约简方法

扩展了Rough集正区域和边界的定义,在得到信息系统最大正区域的前提下,给出了认知正区域、认知属性核和认知属性约简的定义,并给出了从经典属性约简到认知属性约简转换的高效算法。此外,在认知正区域的定义下,由于决策表的不相容性,在变精度模型下实现属性约简的增量处理是相当困难的,结合提出的高效算法,解决了这一问题。最后,仿真实验说明了算法的有效性。     

一种基于粗集的值约简方法

针对Rough Set理论中的值约简问题进行了研究，对基于决策间不可区分关系的值约简算法进行了改进，使其能够处理信息系统出现的各种情况。     

一种论域递减式计算正区域方法

正区域的计算在粗糙集的应用中十分重要。在深入研究粗糙集基本理论的基础上,围绕不可分辨关系,得到了一种计算正区域的等价方法,提出了一种论域递减式的计算正区域的算法。该算法对论域中的样本进行分步分类,同时判断其是否属于正区域,而后将其从论域中删除,从而减轻计算量。理论分析和实例结果验证了该算法的有效性和可行性。     

快速的属性约简算法

属性约简的效率是粗糙集等软计算理论的核心问题之一。为了提高约简效率,在分析不可分辨关系和基数排序特点的基础上,提出了一种时间复杂度为O(|C||U|)的求核算法。然后,运用改进的属性重要度作为启发信息,得到一种快速的属性约简算法,时间复杂度为O(|C|2|U)|。最后,通过UCI机器学习库中的一些数据集对算法进行测试,证明了算法对大型的数据集进行属性约简的高效性。     

快速求正区域的渐增式方法研究

正区域是粗糙集理论中的核心概念之一,提高计算正区域算法的效率对于其相关算法的效率有重要的影响。本文提出了一种求正区域的渐增式方法,它能有效地去掉求正区域算法中的一些冗余运算,其计算正区域的时间复杂度为,替换掉该算法的一部分将得到一个属性约简算法,它是高效而往往能满足用户需求的,比较适用于大型数据集。理论结果和实验表明,该方法确实能高效地计算出正区域。     

一种高效的核属性求解算法

求核算法主要存在以下不足：对不相容决策表无法获得与正区域一致的核,求核算法的效率不够理想。针对上述问题,首先给出决策表的新定义和求核性质,并证明由该性质获得的核与正区域的核是一致的。然后,设计快速求核算法,其时间复杂度和空间复杂度分别降低为O（|C|2|U|）和O（|U|）。最后,实验验证该算法的有效性和高效性。     

一种核属性快速求解算法

针对求核算法存在所求得的核与基于正区域的核不一致以及算法的时间和空间复杂度不理想的问题,提出一种新的求核方法,并证明了由该方法所获得的核与基于正区域的核是一致的.利用分布计数基数排序方法设计了一种高效的等价类求解算法,在此基础上给出了快速求核算法.实验表明,所提出的算法是正确而高效的.     

动态模糊粗糙特征选取算法

由于数据随时间和空间不断更新,很多基于粗糙集的增量方法被提出。然而,动态数据上基于模糊粗糙集的特征选取(也称属性约简)更新的研究较少,特别是连续型动态数据上的增量特征选取。为了解决这个问题,提出适用于连续型数据的基于模糊粗糙集的增量属性约简算法。首先提出模糊粗糙基本概念的增量机制,如模糊正域的增量机制。只有部分示例在已有属性约简上的辨识能力不足,即对于模糊正域来说,存在一个关键示例集。增量约简算法基于已有数据上的约简结果,仅需要更新关键示例集中的示例,而非全部的论域。因而该增量算法在动态数据上能快速获得约简的更新。通过数值对比实验可以看出,增量算法比非增量算法在运行时间上有明显的优势。特别是对于高维数据集,增量算法可以大大地节省计算时间。     

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

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

一种启发式知识约简算法

属性约简是Rough集理论中的核心问题之一,找出所有的约简或最小约简是一个NP难题.本文证明了正区域和边界域的一些性质,指出在考虑正区域作为启发信息的同时,还应该考虑在不一致决策表中边界域对约简的影响,综合这两种信息,提出了不一致决策表约简的启发信息.并在此基础上,设计了不一致决策表的启发式约简算法.实验证明,在多数情况下,该算法能够得到决策表的最小或次优约简.