粗糙集多目标并行属性约简算法

粗糙集理论(RST)中,求解最小属性约简MAR (minimal attribute reduction)是一种NP-难(non-deterministic polynomialhard)组合优化问题.蚁群优化算法ACO(antcolonyoptimization)是进化算法中的一种启发式全局优化算法,粗糙集理论与ACO相结合,是求解属性约简的一种有效、可行的方式.针对蚁群优化算法易于陷入局部最优解、收敛速度慢等问题,首先以一种改进的信息增益率作为启发信息,提出了冗余检测机制,对每个被选属性和每代最优约简集合进行冗余检测,并提出了概率提前计算机制,可避免每只蚂蚁在搜索过程中相同路径上的信息反复计算;针对大数据集的属性约简问题,考虑到蚁群优化算法具有并行能力以及粗糙集中“等价类”计算的可并行性,提出一种将ACO与云计算相结合用于求解大数据集的属性约简算法,在此基础上,进一步提出一种多目标并行求解方案.该方案可以同时计算出其余属性相对于当前属性或约简集合的重要度.实验结果表明,该算法在处理大数据的情况下能够得到最小属性约简,计算属性重要度的时间复杂度由O(n2)降至O(|n|).     

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

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

基于信息熵与蚁群优化的属性约简算法

信息熵是粗糙集理论中度量不确定信息的重要工具之一。蚁群优化算法是一种新型的智能计算的方法,具有分布式、正反馈及启发性搜索等优良的性质,并且在优化计算中已得到了很多应用.最小属性约简问题也是一类优化问题,已有的属性约简算法主要采用Pawlak正域度量属性的重要度,而且求最小约简是NP-hard问题.为此,在分析信息熵度量不确定性数据的基础上,定义信息熵属性重要度概念,引入蚁群优化算法,提出基于信息熵与蚁群优化的最小属性约简算法.该算法发挥蚁群优化算法良好的寻优能力,大多数情况下能够找到最小约简.理论分析与实验结果表明该算法是有效可行的.     

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

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

基于蚁群优化的多个属性约简的求解方法

属性约简是粗糙集理论研究的一个核心问题,很多情况下多个最小属性约简被期望能帮助用户做出更好的决策。文中提出一种基于蚁群优化的获取多个属性约简的方法。首先,结合蚁群优化方法将属性约简问题转化为受限制满足问题,并提出新的模型R-Graph,进而最小属性约简问题转化为在R-Graph中寻找最低成本路径问题。然后,定义吸收算子删除可辨识矩阵中冗余数据的方法以达到简化搜索空间的目的,并提出一个求解多个属性约简的算法(R-ACO)。最后,对比实验说明该方法在大多数情况下能得到更多的最小属性约简结果,并且算法效率较高。     

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

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

基于量子精英蛙的最小属性自适应合作型协同约简算法

属性约简是粗糙集理论研究的重要内容之一,现已证明求决策表的最小属性约简是一个典型NP-Hard问题.提出一种基于量子精英蛙的最小属性自适应合作型协同约简算法.该算法首先将进化蛙群编码为多状态量子染色体形式,利用量子精英蛙快速引导进化蛙群进入最优化区域寻优,有效增强进化蛙群的收敛速度和全局搜索能力.然后构建一种自适应合作型协同进化的最小属性约简模型,融合蛙群最优执行经验和分配信任度自适应分割属性约简集,并以模因组内最优精英蛙优化各自选择的属性子集,提高属性约简的协同性和高效性,快速找到全局最小属性约简集.实验研究表明提出的算法在搜索最小属性约简解时具有较高的执行效率和精度.     

基于量子蚁群算法的粗糙集属性约简方法

针对蚁群算法求取属性约简中存在的迭代次数多、收敛较慢甚至得不到最小约简的问题,提出了基于量子蚁群算法的粗糙集属性约简的方法。每只蚂蚁携带一组表示蚂蚁当前位置信息的量子比特;采用量子旋转门完成蚂蚁的移动;采用量子非门实现蚂蚁所在位置的变异。实验证明,该算法能快速有效地求解属性约简,同时又能找到许多次最小约简。可以很好地解决这一难题,它不仅能得到最小约简属性集,而且可以得到很多的约简属性集。     

基于回溯搜索算法的决策粗糙集属性约简

属性约简是粗糙集理论的核心问题,为了获得更多更稳定的最小属性约简,根据决策粗糙集模型将最小属性约简问题转化为决策风险最小化问题,并给出了新的适应度函数计算方法;在此基础上利用回溯搜索算法较强的全局搜索性能,提出了基于回溯搜索算法的决策粗糙集属性约简算法;对UCI数据集的实验结果以及与其他约简算法的比较表明,该算法能够得到更多的最小属性约简,而且能够在多次运行中保持约简结果个数的稳定性。     

一种基于组合变换的粗糙集属性约简算法

粗糙集的核心问题是知识的约简和获取。该文提出一种基于组合变换的粗糙集属性约简算法,此算法基于数理逻辑的组合推理,采用核属性和单属性进行过滤,并用超集关系对候选约简进行消减。分析表明,算法具有较好的时间复杂度和空间复杂度。     

利用蚁群优化算法的粗糙集属性约简方法

随着高维数据的扩散,特征选择成为学习过程中不可或缺的一项任务。属性约简是特征选择的重要方法,为了寻找有效的属性约简方法,将粗糙集与蚁群算法相结合,提出了利用蚁群优化算法的粗糙集属性约简方法。首先从信息素的更新开始,限制其信息素值的上、下限范围,然后根据寻址方式改进候选解的构造方案。实验表明,该方法具有一定的优越性。     

基于可拓蚁群算法的粗糙集属性约简方法

蚁群算法是一种模拟进化算法,它有很多优点,且成功地解决了许多复杂的组合优化问题,然而它并不完美。受可拓学中关联函数的启发,提出基于关联函数的状态转换规则和局部信息素更新规则,并将其用于粗糙集的属性约简。实验结果证明该算法是有效的。     

基于可拓蚁群算法的粗糙集属性约简方法

蚁群算法是一种模拟进化算法,它有很多优点,且成功地解决了许多复杂的组合优化问题,然而它并不完美。受可拓学中关联函数的启发,提出基于关联函数的状态转换规则和局部信息素更新规则,并将其用于粗糙集的属性约简。实验结果证明该算法是有效的。     

基于属性桶的约简算法

基于粗糙集理论的属性约简算法是机器学习和数据挖掘领域的研究热点之一。粗糙集理论是一种新型的处理模糊和不确定信息的数学工具,在保证分类能力不变的前提下,通过知识的约简导出概念的分类规则。文中提出了一种基于属性桶的约简算法,其约简过程类似基于属性频度函数的约简算法。该算法首先构造一组与决策表决策属性个数相同的属性桶,不同的属性桶划分了不同长度的区分矩阵项,避免了约简前的排序过程。通过构造属性桶时对核属性进行特殊处理,在一定程度上简化了属性约简过程。     

连续值属性决策表中的可变精度粗糙集模型及属性约简

属性约简是粗糙集理论研究的一个核心问题.为了有效地处理决策表中连续值属性约简,提出了连续值属性决策表中的可变精度粗糙集模型以及基于此模型的连续值属性约简算法.仿真实验结果表明,该算法可以对连续值属性进行约简,而且比经典粗糙集相关方法在处理连续值属性约简方面更有效.     

基于GA-PSO的粗糙集属性约简算法

属性约简是粗糙集合研究的重要内容之一。为了能够有效地获取决策表中属性最小相对约简,提出了一种基于GA-PSO的属性约简算法。该算法以条件属性对决策属性的支持度为基础,求解核属性,把所有的条件属性(除去核属性)加入粒子群算法的初始种群中,并用遗传算法对不满足适应度条件的粒子进行交叉变异操作。实验结果表明,该算法在加强局部搜索能力的同时保持了该算法全局寻优的特性,能够快速有效地获得最小相对属性集。     

Fuzzy rough set based attribute reduction for information systems with fuzzy decisions

Fuzzy rough set is a generalization of crisp rough set to deal with data sets with real value attributes. A primary use of fuzzy rough set theory is to perform attribute reduction for decision systems with numerical conditional attribute values and crisp (symbolic) decision attributes. In this paper we define inconsistent fuzzy decision system and their reductions, and develop discernibility matrix-based algorithms to find reducts. Finally, two heuristic algorithms are developed and comparison study is provided with the existing algorithms of attribute reduction with fuzzy rough sets. The proposed method in this paper can deal with decision systems with numerical conditional attribute values and fuzzy decision attributes rather than crisp ones. Experimental results imply that our algorithm of attribute reduction with general fuzzy rough sets is feasible and valid.     

核属性蚁群算法的规则获取

蚁群算法是一种新型的模拟进化算法,研究已经表明该算法具有许多优良的性质,并且在优化计算中已得到了很多应用.粗糙集理论作为一种智能数据分析和数据挖掘的新的数学工具,其主要优点在于它不需要任何关于被处理数据的先验或额外知识.本文从规则获取和优化两方面研究基于粗糙集理论和蚁群算法的分类规则挖掘方法.通过研究决策表和决策规则系数,建立基于粗糙集表示和度量的知识理论,将粗糙集理论与蚁群算法融合,采用粗糙集理论进行属性约简,利用蚁群算法获取最优分类规则,优势互补.实验结果比较表明,算法获取的分类规则,具有良好的预测能力和更为简洁的表示形式.     

基于粒度决策熵的属性约简

近年来,人们越来越关注粗糙集中的属性约简算法,尤其是启发式的约简算法。为了度量属性重要度,人们把各种不同的信息熵模型应用到粗糙集中,同时在信息熵这一理论的基础上得出了许多约简算法,用来解决粗糙集中属性约简的问题。然而,现有的基于信息熵的方法还存在一系列问题。针对这些问题,本文首先将知识粒度与相对决策熵这2个概念结合在一起,从而引入一种新的信息熵模型--粒度决策熵;然后,利用粒度决策熵来度量属性的重要性,并由此得出新的约简算法--ARGDE约简算法;最后,用不同的UCI数据集来做实验,通过与已有的约简算法比较,该算法能够得到更好的实验结果。