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

提出了基于分明矩阵的启发式知识约简算法.该算法以分明矩阵中属性出现的频率作为启发信息,通过构造新的决策表,每次选取出现个数最多的属性,直到选取的属性能够保持原决策表的分类能力,此时得到的集合即是一个约简.试验结果表明,该算法在大多数情况下都能够找到最小约简或令人满意的次优解.     

一种属性与值约简及规则提取算法

本文提出了一种属性与值约简及规则提取算法。该算法无需求出分明矩阵,而是从决策表中直接提出关于属性值分明的属性构造分明函数,并且可以同时求出属性约简和属性值约简。在此基础上提取规则不仅节约了空间,而且提高了效率,并通过实例进行了验证。     

基于信息观差别矩阵的属性约简算法

提出一种信息观下的差别矩阵,并基于该矩阵设计了一种信息观下决策表的属性约简算法,该算法以信息观下属性核为起点,通过计算信息观下差别矩阵中各属性出现的频率确定属性的重要度,进而根据各个属性的重要度来计算属性约简。实验结果表明,该算法可以求出更有效的信息观下属性约简,且计算约简耗时更少。     

基于相对可辨识矩阵的决策表属性约简算法

针对现有属性约简算法存在的问题,利用信息论和粗糙集理论,提出一种基于相对可辨识矩阵的决策表属性约简算法.该算法以核属性为基础,通过建立相对可辨识矩阵,利用条件信息熵作为启发式信息,减少属性约简过程中的搜索空间,逐个添加条件信息熵最大的属性,直到找出最小约简为止,并分析了该算法的时间复杂度.实例分析结果表明,该算法能有效地对决策表属性进行约简.     

不相容决策表中一种新的属性约简算法

针对不相容决策表中一些属性约简算法的不足,结合粗糙集的代数观与信息观的优点,对差别矩阵加以改进,提出了一种新的属性约简算法,该算法在保证约简后决策表的正域和条件信息熵不变的情况下,降低了时间复杂度。通过实例说明了该算法的有效性和可行性。     

不相容决策表的属性约简算法

对Skowron可辨识矩阵方法进行分析,并应用反例说明基于Skowron可辨识矩阵的属性约简算法对不相容决策表的属性约简,可能会导致错误的结果。针对这一问题,提出了一种基于改进可辨识矩阵的属性频率约简算法。该算法以改进的可辨识矩阵为基础,以属性频率作为启发信息,同时在算法中加入消除冗余属性二次约简过程。提供了实例分析,验证了该算法能够有效地对相容与不相容的决策表进行属性约简。     

基于决策表的区分矩阵增量属性约简算法

对于决策表中存在对象动态变化的现象,当利用静态的属性约简算法处理这类决策表时算法效率并不理想,为了有效提高增量属性约简算法的效率,对决策表进行了简化,并证明了基于简化区分矩阵的属性约简与基于区分矩阵的属性约简是一致的,在利用原的属性约简的基础上,提出了一种基于决策表的区分矩阵增量属性约简算法,通过实例分析说明算法的有效性和可行性。     

Discernibility Matrix Algorithm of Attribute Reduction Based on Knowledge Granulaion in Incomplete Decision Table

基于不完备决策表的属性约简定义有多种,现研究基于知识粒度的属性约简.研究发现,差别矩阵是一种较好的设计属性约简算法的方法.为此,定义了一种粒度差别矩阵和基于该差别矩阵的属性约简,并证明了该差别矩阵的属性约简定义与基于知识粒度的属性约简定义等价.在此基础上,设计了一个新的基于信息量的不完备决策表的属性约简算法,其时间复杂度得以降低.     

基于区分能力的HU差别矩阵属性约简算法

将决策表属性区分能力大小与HU差别矩阵结合起来,建立起属性区别能力与该属性在HU差别矩阵中出现次数之间的关系.提出与HU差别矩阵属性约简相适应,只依赖于等价类基数计算的属性区分能力计算公式,得到HU差别矩阵约简的属性区分能力判定定理.定义了以属性区分能力为基础的属性相对重要性概念,提出以相对重要性为启发式信息的HU属性约简算法.由于该算法不必构造差别矩阵,只依赖于等价类基数的计算,从而大大提高了算法效率.数值算例和实验结果表明,该算法更有利于最优或次优约简结果的搜索.     

属性与属性值合一的数据约简算法

提出一种数据约简算法.该算法从决策表中条件属性的等价类族考虑,分析决策值的等价类族,在约简过程中,可同时进行属性约简与属性值约简.与基于分析法或区分矩阵的传统约简等算法相比,本文算法可省略属性值约简中繁琐的比较过程,减少比较次数,提高约简效率.     

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

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

不完备决策表中基于对象矩阵属性约简算法

基于差别矩阵的属性约简是粗糙集属性约简中最常用的方法。对通常给出的以存储条件属性为基础差别矩阵进行比较后,给出一种对象矩阵的定义。对象矩阵从相容类内对象的决策值与条件属性的关系出发,存储的是对象集。给出对象矩阵的属性约简定义,证明了属性约简与基于正区域的属性约简的等价性。给出一个启发式的属性约简算法,其时间复杂度为max(O(|C|2|Upos||U|),O(|C||U|2)),空间复杂度为O(|C||U|2);通过实例说明方法的可行性。     

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

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

基于加权浓缩树的粗糙集属性约简算法

针对基于分辨矩阵约简算法中存在冗余元素,从而导致空间存储代价高的问题,提出一种基于加权浓缩树的属性约简算法。该算法可以进一步剔除冗余元素,压缩存储分辨矩阵中的信息,并且在构建树结构的过程当中考虑了属性重要度的影响。实验结果与C-Tree及差别信息树算法进行比较,提出的算法可以获得更优的属性约简结果,有效地降低了空间复杂度。     

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

指出支天云的二进制可分辨矩阵约简算法存在的不足,给出简化的决策表定义和基于二进制可分辨矩阵的属性频率函数的定义。在此基础上,以核属性为初始约简集,以属性频率为启发式信息,提出了一种改进的基于二进制可分辨矩阵的属性约简算法,其最终可以获得一个最优约简,并且算法时间复杂度和空间复杂度分别为max{O（｜C｜ ｜U｜）,O（｜C｜^2｜ ｜U｜^2）}和0（｜C｜ ｜U｜^2）。通过实例验证,表明该算法是有效的。     

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

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

基于差别矩阵的完备属性约简算法

基于差别矩阵思想的属性约简算法需要求出决策表的差别矩阵,然而差别矩阵的求取不但费时而且占用大量的存储空间。为此,提出一种基于差别矩阵中非空对象个数的改进属性约简算法。在利用差别矩阵思想的同时不生成差别矩阵,并给出属性重要度的定义及其快速计算公式,只需要 和 就能计算出属性重要度。实例分析证明,该算法能节省计算时间,求出最小属性约简。     

改进的基于差别矩阵的属性约简算法

指出现有差别矩阵属性约简算法的不足,对原有差别矩阵和属性重要性度量方法进行改进,运用差别矩阵元素项的重要性质,提出一种新的启发式约简完备算法,有效地降低差别矩阵约筒算法的空间复杂度。仿真实验结果显示,新算法产生的约筒与分辨函数思想产生的最优约简一致,表明了新算法的有效性与完备性。     

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

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