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

知识约简是祖糙集理论处理信息系统的重要手段,本文首先给出了不完备信息系统的相关概念和定义,提出了不完备决策表的一种知识约简算法．实例计算结果证明了算法的可行性。     

不完备决策表的一种知识约简算法

知识约简是粗糙集理论的核心内容之一。介绍了不完备信息系统下的粗糙集模型,提出了一个在不完备决策表中利用属性的重要性进行知识约简的算法,并给出实例计算结果,证明了算法的可行性。     

不一致决策表的知识约简方法研究

日前计算不一致决策表的分布约筒、最大分布约筒和分配约筒的方法均基于可辨识属性矩阵,在大数据集下耗时较多.为此,提出转化算法,将计算原不一致决策表的上述3种约简转化为计算3种一致决策表的Pawlak约筒,通过应用针对后者的高效启发式算法,有效地减少了计算时间．此外,引入λ-约筒的概念,通过调节A的值,能得到一族反映决策矢量不同水平相似程度的知识约筒．该方法降低了分布约筒对决策表区分能力的过高要求,较上述3种约筒更为灵活。     

一种不完备决策表的属性约简算法

对于不完备决策表,给出了区分对象对集和基于区分对象对集约简的定义,并证明出基于区分对象对集的属性约简定义等价于基于广义决策的属性约简定义。在此基础上,提出一种基于区分对象对集的新算法。新算法以区分度[K(ci)]和完备度[P(ci)]为启发信息,结合基数排序,使得算法最终时间复杂度为[O(|C||U|2)],相比传统的算法时间复杂度[O(|C|3|U|2)]和[O(|C|2|U|2)],时间复杂度有效降低。通过实例说明了新算法的正确性和有效性。     

高效的不完备信息系统知识约简算法研究

文章基于粒度和粒度计算的方法,对不完备信息系统的属性重要度和相对于决策属性的重要度做了定义,在此基础上形成了基于粒度方法的不完备信息系统知识约简算法,通过实例证明了这种方法的有效性。文章分析了算法的时间复杂度,并同粗糙集算法进行了对比。     

不完备决策表属性约简的CIEARAWCC算法

不完备信息系统中的属性约简是粗集理论应用的难点。通过引入信息熵和条件信息熵,对信息系统中属性的必要性进行了定义,提出了一种基于条件信息熵的属性约简启发式算法。通过引入相对正域,有效地解决了不一致系统属性约简过程中产生的冗余属性问题,并分析了该算法的时间复杂度。最后,通过实例说明该算法能得到不完备决策表的最小相对约简。     

不完备决策表的差别矩阵属性约简算法

给出一个差别矩阵的属性约简定义,证明该属性约简的定义与广义决策属性约简的定义是等价的,对差别矩阵进行了有效的压缩。在此基础上,为求出不完备决策表的属性约简,设计了一个基于该差别矩阵的不完备决策表属性约简算法,其时间复杂度为O(|C|2|U|2),最后用实例说明了该算法的有效性。     

一种基于冲突域的不完备决策表属性约简算法

以不完备决策表为研究对象,通过对冲突域的概念进行研究,给出在不完备决策表下的基于冲突域的属性约简的定义。证明该属性约简的定义与基于正区域的属性约简定义是等价的,同时设计一个在不完备决策表中的新的属性约简算法。该算法的时间复杂度为O(|K||C|2|U|),其中K=max{|TC(xi)|,xi∈U}。最后用实例说明该算法是有效的。     

不完备决策表中基于相对知识量的属性约简

在不完备决策表中,引入基于相容关系的相对知识量,定义属性的重要度,提出一种启发式属性约简算法。该算法通过在约简过程中不断缩小样本空间的方法,降低算法计算时间。采用UCI数据集进行实验,结果表明该算法可提高不完备决策表的约简效率,适用于大规模数据集的属性约简。     

基于条件信息熵的决策表约简

Rough集理论是近年来发展起来的一种有效地处理不精确、不确定、含糊信息的数学理论方法，在机器学习、数据挖掘、智能数据分析、控制算法获取等领域取得了很大的成功。研究者从不同的角度对这个理论进行研究。本文将从信息论观点出发对Rough集理论的基本概念和主要运算进行分析讨论，通过与Rough集理论的代数观点进行比较分析，得到这两种观点下的一些等价性质和不同的特性，并基于条件信息熵提出决策表的约简算法。     

不完全决策表的一种信息熵属性约简算法

属性约简是粗糙集理论的核心问题之一，也是粗糙集有效算法研究的焦点。为获得最简明的规则集，通常希望能找出最小的属性约简集，但得到最优解NP-hard的问题，通常采取启发式的算法得到近似最优解。文中研究了不完全决策表的属性约简，提出了对不完全决策表的一种基于信息熵的属性约简算法，并通过例子说明算法的具体过程和验证了算法的可行性。对寻找对象的相似类的步骤则在排序和二分查找的基础上提出了一种高效的算法，这样就相应地提高了属性约简算法的效率。     

基于差别矩阵启发式决策表属性约简算法

属性约简是粗糙集理论研究的核心内容之一,足知识获取的关键步骤.针对大规模数据集,基于决策表差别矩阵属性约简不具备可操作性缺点;以及基于差别矩阵属性频度的约简算法没有考虑到差别矩阵元素中属性个数多少的缺陷.基于差别矩阵元素的基数越小,其属性越重要的思想,按照基数由小到大的顺序,利用矩阵中具有相同基数的矩阵元素的簇集中属性出现的频度,确定属性的重要度,提出一种快速搜索属性约简算法,能快速搜索到属性的最优或次优约简.实验结果表明算法是可行、有效的.     

一种基于重构相容决策表的属性约简算法

基于正区域的属性约简是目前最常用的一类约简算法。现实中的决策表有可能存在不一致的对象。另外,在约简过程中随着属性个数的减少,也有可能产生新的不一致对象。对于基于正区域的约简算法来说,不一致的对象并没有提供任何有用的信息,删除不一致的对象不会改变正区域的计算结果以及最终的约简结果,而且可以显著提高算法的效率。然而现有的基于正区域的约简算法并没有考虑到这个问题,它们采用论域中的所有对象来计算正区域并得出约简结果。针对这一问题,定义了重构相容决策表和重构相容决策子表的概念。引入这两个概念的目的是在约简过程中删除初始决策表中的不一致对象,从而获得一个相容决策表。借助于这两个概念,提出了一种新的基于正区域的属性约简算法。在真实数据集上的实验表明,与传统的算法相比,该算法能够获得较小的约简结果和较高的分类精度,并且具有相对较低的时间复杂度。     

一种新的完全决策表属性约简的高效算法

属性约简是粗糙集理论的核心问题之一,也是粗糙集有效算法研究的焦点。为获得最简明的规则集,通常希望能找出最小的属性约简集,但得到最优解是NP-hard的问题,通常采取启发式的算法得到近似最优解。文中研究了不完全决策表的属性约简,提出一种衡量不完全决策表属性重要性的标准,依此给出了一种新的进行属性约简启发式算法。对寻找对象的相似类的步骤则在排序和二分查找的基础上提出了一种新的高效的算法,这样就相应地使得属性约简的效率得到提高。此算法较好地解决了不完全决策表的属性约简问题。     

一种快速的不完备决策表属性约简算法

目前,关于不完备决策表的属性约简算法已有不少,其中在很多算法中,其时间复杂度为O( |C|3|U|2).为有效地降低算法的时间复杂度,给出一个差别矩阵的定义和基于差别矩阵属性约简的定义,并证明了该属性约简与基于正区域的属性约简是等价的.生成的差别矩阵无需比较Umeg之间的对象,使差别矩阵得到有效地简化,进一步降低算法的存储空间.在此基础上,利用简化的差别矩阵设计一个快速计算不完备决策表的属性约简的算法,其时间复杂度降为maX{O( |C|2|Upos,||U|),O(K|C||U|)}.(其中K=max{ |Tc(xi)|,xi∈U}).最后用实例仿真说明了新算法的有效性.     

不完备决策表中基于相似关系的属性约简

在基于相似关系的不完备决策表中,条件属性值为“*”的属性不参与相似关系的确定,由此定义属性的相对重要度和属性重要度。根据属性重要度,提出寻找不完备决策表的分配协调集和分配约简的启发式算法。通过实例证明该方法能找到不完备决策表的分配协调集和分配约简,并减少约简的搜索空间。     

新简化决策表的研究

针对简化决策表的定义和建立算法只能处理一致对象的问题,提出新简化决策表定义和建立算法,采用对不一致对象单独处理的方法,有效地解决简化决策表不能处理不一致对象的问题。通过实验验证新简化决策表可以处理不一致对象,简化决策表不能处理不一致对象。     

不完备联系度粗糙集模型的知识约简

知识约简是粗糙集理论的重要研究内容之一。在不完备信息系统中,对联系度粗糙集模型的研究比较深入,但极少涉及知识约简问题。该文在进一步改进联系度粗糙集模型的基础上,研究该模型的知识约简。针对改进模型,提出多种知识约简定义,给出了这些约简之间的关系。通过定义初等分辨矩阵和属性重要度,介绍一种分配约简算法。实例分析说明了算法的有效性。