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

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

一种基于浓缩树结构的属性约简算法

属性约筒是粗糙集理论的重要研究内容之一,以浓缩树结构存储区分矩阵中的非空数据项,对IReductBtree算法进行了一些改进.它是根据树结构特点结合特殊的启发式策略,删除树中结点,直到树空最后得到信息系统的一个约简.最后,通过一个实例完整演示了该方法证实其有效性.     

基于改进区分表的核属性约简算法

知识约简是一个NP难问题,在众多知识约简方法中,核属性基本上作为属性约简的初始解,这样就能有效地减小约简算法在属性空间中的搜索范围,在一定程度上加速了知识约简的进行.然而,核属性解基本上是利用Hu的分辨矩阵法求得的.结合Hu的分辨矩阵算法,讨论了Hu以及Wroblewaski区分表算法中存在的问题,改进了区分表的定义并结合Ye方法提出了基于区分表核属性约简算法,既克服了分辨矩阵方法的缺陷,又避免了区分表算法中存在的问题.实验结果表明该算法能有效求出决策系统的属性核.     

用差别矩阵思想设计的基于正区域的高效属性约简算法

近来一些学者用差别矩阵或差别矩阵的思想设计了基于正区域的属性约简算法.由于计算差别矩阵是一个既消耗时间又消耗空间的过程,故这些算法的效率并不好.为了降低这类属性约简算法的复杂度,文中利用基于区分对象对的属性约简的思想,在简化决策表的基础上,定义了一个函数,该函数能度量简化决策表中条件属性集产生的区分对象对的个数,并用该函数设计了一个启发函数,同时给出了计算该启发函数的快速算法,经分析其时间和空间复杂度均为O(|U/C|).最后用该启发函数设计了一个有效的基于正区域的属性约简算法,该算法的时间复杂度降为O(|C||U|),空间复杂度降为O(|U|).文中还用一个具体实例说明了新算法的有效性.经实验证明,新算法具有较高的效率.     

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

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

基于局部条件区分能力的高效属性约简算法

基于区分矩阵的传统属性约简方法具有直观易理解的优点,但时间和空间复杂度都很高,当数据规模较大或条件属性较多时,会无法快速得到约简结果.为解决该问题,在区分关系的基础上构造了条件区分能力来进行属性选择,提出一种基于条件区分能力的属性约简算法.而为了进一步加快属性重要性的计算、提高约简效率,依据大数定律中频率的稳定性,通过...     

区分对象对集的不完备决策表属性约简

通过利用粗糙集中差别矩阵的思想,引入不完备决策表的区分对象对集的概念。并给出不完备决策表基于区分对象对集的属性约简定义。同时,也证明了利用该定义得到的不完备决策表的属性约简与基于正区域的属性约简是等价的。相比较基于正区域的不完备决策表属性约简算法,基于区分对象对集的属性约简算法时间复杂度是降低的。最后,用一个实例说明了该算法的合理性。     

基于区分矩阵的增量式属性约简

定义了属性和属性集的区分矩阵以及区分矩阵的运算,表明了属性集的区分矩阵与论域按属性集的分类是1-1对应的,因此,区分矩阵代表了属性集的分类.以区分矩阵作为属性约简的标准,以属性对分类的贡献率作为贪心选择的次序,建立了一种针对无目标信息系统的属性约简以及增量式属性约简方法.该算法降低了处理增量式数据的复杂度,并且只涉及到矩阵的加法、非负矩阵转化为0-1矩阵、判断矩阵相等的运算,便于用计算机语言编程计算.     

粗糙集中求取所有最小属性约简快速算法

属性约简问题是粗糙集理论中一个核心的研究课题。本文基于区分矩阵存在大量冗余数据考虑,提出了一种利用吸收算子的快速算法,不用生成庞大的区分矩阵,与现有的属性约简算法相比,节约了大量时间和空间。对于UCI绝大部分数据,在P41.6G的PC机上都可以在1秒以内的时间求出所有的最小约简。实验数据说明了该算法的有效性。     

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

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

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

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

一种基于C-Tree的属性约简增量式更新算法

针对以往文献为克服基于差别矩阵的属性约简算法存储代价高的不足而提出的基于浓缩树(C-Tree)的高效属性约简算法仅考虑决策表不变的情况,提出了一种基于C-Tree的属性约简增量式更新算法,主要考虑对象动态增加情况下属性约简的更新问题.该算法可通过快速更新C-Tree,在动态求解核的基础上,利用原有的属性约简有效地进行属性约简的增量式更新.理论分析和实验结果表明,所提出的算法是有效可行的.     

分辨矩阵与它在一致性决策规则中的应用

属性约简是决策系统规则获取的基础,而Skowron分辨矩阵是粗集求核与约简的重要方法之一.本文以Skowron分辨矩阵讨论一致性决策系统的属性约简的结果为基础,提出基于分辨矩阵的一致性决策系统的规则获取算法和它的应用. 应用例子表明本文提出的方法的有效性     

一种新的不一致决策表属性约简算法

针对目前求核方法存在的问题,提出一种基于分布函数的用于计算核属性的改进的二进制可辨矩阵。改进的二进制可辨矩阵不仅规模小,而且适用于任何决策表求核。在获取核属性的基础上,提出一种新的不一致决策表的属性约简算法,只要在用于计算核属性的改进的二进制可辨矩阵中简单增加相应的行,就可以利用逻辑运算来获取属性约简。并将吸收律应用于属性约简,较大提高了属性约简的效率。     

属性约简的一种算法

根据可辨识矩阵和属性特征,建立可辨识链表,在建立过程中获得核集,并从可辨识链表中寻找必要属性集,从而得到信息系统的属性约简集,实例表明,该约简算法降低了空间和时间的复杂性。     

基于S-粗集的反辐射导弹识别算法研究

针对具有动态特征的信息系统,在S-粗集属性迁移理论基础上,给出了S-粗集上的区分矩阵,提出了一种基于S-粗集区分矩阵的属性约简算法.该算法弥补了Z.Pawlak粗集理论对于动态系统知识发现的局限,通过属性迁移对不完备的信息系统进行动态扩展.约简后生成的规则简单准确.本文的算法具有理论与应用的一般性、广泛性,对于现代战场中的删识别,更显示出了极强的优越性.     

一种基于零值原则的属性约简方法

根据Guan等提出的完备信息系统下矩阵约简算法,提出一种改进的属性约简计算方法。该方法根据矩阵的运算特点,通过引入唯一零值概念,使得计算过程更为简易。证明了它与区分矩阵下属性约简的等价性,最后将该方法运用到协调决策表中,并用实例对此进行了说明。     

变精度粗集模型的属性约简研究

针对大量存在的不一致决策表,研究了分配量函数和[β]分配量函数定义。依据Ziarko变精度粗糙集模型,提出利用计算条件属性组合的[β]重要度来选择属性的[β]重要度属性约简和利用[β]二进制可辨矩阵实现的[β]分配量属性约简,可有效解决不一致决策表属性约简问题。     

遗传算法与区分矩阵的属性约简算法

对于约简来说,其前提是保证知识库分类能力不变,由此引入弱约简的定义。利用区分矩阵能很容易计算出弱约简和遗传算法可以在全局寻优的优势,将染色体对区分函数的覆盖度作为适应度函数的参数,提出了一种基于遗传算法和区分矩阵的属性约简算法。算法中从粒计算的角度,重新度量粒度,对基于划分和覆盖的粗糙集决策表进行了研究。用k近邻算法通过准确率对弱约简效果进行评估。通过UCI数据集证明了该算法的有效性。该算法的时间复杂度是多项式的。     

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

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