共查询到18条相似文献,搜索用时 62 毫秒
1.
属性约简是粗糙集理论的核心问题之一,也是粗糙集有效算法研究的焦点.为获得最简明的规则集,通常希望能找出最小的属性约简集,但得到最优解NP-hard的问题,通常采取启发式的算法得到近似最优解.文中研究了不完全决策表的属性约简,提出了对不完全决策表的一种基于信息熵的属性约简算法,并通过例子说明算法的具体过程和验证了算法的可行性.对寻找对象的相似类的步骤则在排序和二分查找的基础上提出了一种高效的算法,这样就相应地提高了属性约简算法的效率. 相似文献
2.
属性约简是粗糙集理论的核心问题之一,也是粗糙集有效算法研究的焦点.为获得最简明的规则集,通常希望能找出最小的属性约简集,但得到最优解是NP-hard的问题,通常采取启发式的算法得到近似最优解.文中研究了不完全决策表的属性约简,提出一种衡量不完全决策表属性重要性的标准,依此给出了一种新的进行属性约简启发式算法.对寻找对象的相似类的步骤则在排序和二分查找的基础上提出了一种新的高效的算法,这样就相应地使得属性约简的效率得到提高.此算法较好地解决了不完全决策表的属性约简问题. 相似文献
3.
一种新的完全决策表属性约简的高效算法 总被引:2,自引:2,他引:2
属性约简是粗糙集理论的核心问题之一,也是粗糙集有效算法研究的焦点。为获得最简明的规则集,通常希望能找出最小的属性约简集,但得到最优解是NP-hard的问题,通常采取启发式的算法得到近似最优解。文中研究了不完全决策表的属性约简,提出一种衡量不完全决策表属性重要性的标准,依此给出了一种新的进行属性约简启发式算法。对寻找对象的相似类的步骤则在排序和二分查找的基础上提出了一种新的高效的算法,这样就相应地使得属性约简的效率得到提高。此算法较好地解决了不完全决策表的属性约简问题。 相似文献
4.
对于不完备决策表,给出了区分对象对集和基于区分对象对集约简的定义,并证明出基于区分对象对集的属性约简定义等价于基于广义决策的属性约简定义。在此基础上,提出一种基于区分对象对集的新算法。新算法以区分度[K(ci)]和完备度[P(ci)]为启发信息,结合基数排序,使得算法最终时间复杂度为[O(|C||U|2)],相比传统的算法时间复杂度[O(|C|3|U|2)]和[O(|C|2|U|2)],时间复杂度有效降低。通过实例说明了新算法的正确性和有效性。 相似文献
5.
针对目前求核方法存在的问题,提出一种基于分布函数的用于计算核属性的改进的二进制可辨矩阵。改进的二进制可辨矩阵不仅规模小,而且适用于任何决策表求核。在获取核属性的基础上,提出一种新的不一致决策表的属性约简算法,只要在用于计算核属性的改进的二进制可辨矩阵中简单增加相应的行,就可以利用逻辑运算来获取属性约简。并将吸收律应用于属性约简,较大提高了属性约简的效率。 相似文献
6.
以不完备决策表为研究对象,通过对冲突域的概念进行研究,给出在不完备决策表下的基于冲突域的属性约简的定义。证明该属性约简的定义与基于正区域的属性约简定义是等价的,同时设计一个在不完备决策表中的新的属性约简算法。该算法的时间复杂度为O(|K||C|2|U|),其中K=max{|TC(xi)|,xi∈U}。最后用实例说明该算法是有效的。 相似文献
7.
目前,基于不完备决策表的属性约简研究较少。基于信息量的不完备决策表属性约简是一种新的属性约简。由于在该属性约简中,计算相容关系是最主要的计算,也比计算等价关系要难得多。基于信息量的不完备决策表的属性约简算法的时间复杂度一般为O(|C|2|U|2)。为降低其时间复杂度,首先分析了老算法的不足,然后给出了一个效率较好的计算相容类的算法。最后设计了一个新的基于信息量的不完备决策表的属性约简算法,其时间复杂度为O(|C|2|U|2)。 相似文献
8.
目前,关于不完备决策表的属性约简算法已有不少,其中在很多算法中,其时间复杂度为O( |C|3|U|2).为有效地降低算法的时间复杂度,给出一个差别矩阵的定义和基于差别矩阵属性约简的定义,并证明了该属性约简与基于正区域的属性约简是等价的.生成的差别矩阵无需比较Umeg之间的对象,使差别矩阵得到有效地简化,进一步降低算法的存储空间.在此基础上,利用简化的差别矩阵设计一个快速计算不完备决策表的属性约简的算法,其时间复杂度降为maX{O( |C|2|Upos,||U|),O(K|C||U|)}.(其中K=max{ |Tc(xi)|,xi∈U}).最后用实例仿真说明了新算法的有效性. 相似文献
9.
粗糙集理论是一种新型的处理模糊和不确定知识的数学工具。对现有决策表的属性约简算法进行了比较研究,在此基础上设计了两个合理度量属性重要性的公式,并给出了该公式的递归计算方法,利用新公式作为启发式信息设计了一种新的基于决策表的高效属性约简算法。实例与实验表明,该约简算法在效率上较现有算法有显著的提高。 相似文献
10.
不完备信息系统中的属性约简是粗集理论应用的难点。通过引入信息熵和条件信息熵,对信息系统中属性的必要性进行了定义,提出了一种基于条件信息熵的属性约简启发式算法。通过引入相对正域,有效地解决了不一致系统属性约简过程中产生的冗余属性问题,并分析了该算法的时间复杂度。最后,通过实例说明该算法能得到不完备决策表的最小相对约简。 相似文献
11.
12.
给出容差关系下不完备决策系统中属性相对约简的定义,提出一种基于决策属性相对条件属性正域的求取属性约简算法。该算法以相对正域为迭代准则,以所有条件属性为初始约简集合,通过逐步缩减来求取约简,保证了所求取的约简对问题的分类能力不会减弱。同时给出该算法的时间复杂度分析,并举例验证了该算法的有效性和实用性。 相似文献
13.
14.
15.
属性约简是粗糙集理论的重要应用。考虑将决策表中的每行都作为一条决策规则时,若把表中出现相同决策规则的次数作为权,可得到带权决策表。提出了关于带权决策表的正域约简相应的辨识矩阵并给出了证明,从而得到了约简算法。相比于决策表中的正域约简时发现,通过将决策表转化为带权决策表后,再利用算法1进行约简时,其在一定程度上优于前者。提出了近似分类精度约简相应的辨识矩阵并给出了证明。对于2个算法,在选取的UCI数据集上进行了实验验证。通过实验进一步说明了所提出算法的可行性和有效性。 相似文献
16.
17.
首先简要介绍几种决策表的属性约简算法,分析各种算法的优缺点,然后在此基础上提出一种新的属性约简算法——基于分类质量的决策系统属性约简算法。该算法对完备信息系统和不完备信息系统都是通用的,从其得到满意的属性约简,最后通过实例验证该算法的正确性和有效性。 相似文献
18.
提出一种基于粗糙集属性重要性的属性约简算法。该算法以所有条件属性为初始约简集合,以属性重要性为迭代准则,通过逐步缩减来求取约简。同时给出了该算法的时间复杂度分析,并举例验证了所提出算法的有效性和实用性。 相似文献