粗糙集多目标并行属性约简算法
作者:
作者单位:

作者简介:

通讯作者:

危前进,wei_qj@guet.edu.cn

中图分类号:

TP311

基金项目:

国家自然科学基金(U1811264,U1711263,61966009,61866007);广西自然科学基金(2018GXNSFDA281045);广西可信软件重点实验室研究课题(KX202024)


Multi-objective Parallel Attribute Reduction Algorithm in Rough set
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    Solving the minimal attribute reduction (MAR) in Rough set theory (RST) is an NP-hard combinatorial optimization problem. Ant Colony Optimization algorithm (ACO) is a globally heuristic optimization algorithm in evolutionary algorithms, so combining RST with ACO is an effective and feasible way to solve attribute reduction. The ACO algorithm often fall into local optimal solution, and the convergence speed is slow. This paper first uses an improved information gain rate as heuristic information, and then deduction test is performed on each selected attribute and the optimal reduction set of each generation. And the mechanism of calculating probability in advance is proposed to avoid repeated calculation of information on the same path in the search process for each ant. But the algorithm can only handle small-scale data sets. The ACO algorithm has good parallelism and the equivalent classes in rough set theory can be calculated by Cloud computing. In this paper, we propose a parallel attribute reduction algorithm based on ACO and Cloud Computing to solve massive data sets and further investigate a multi-objective parallel solution scheme, which can simultaneously calculate the importance of the remaining attributes relative to the current attribute or reduction set. Experiments show that the algorithm can obtain the MAR in the case of processing big data, and complexity of time on calculating the importance of attribute decreases from O(n2) to O(|n|).

    参考文献
    相似文献
    引证文献
引用本文

危前进,魏继鹏,古天龙,常亮,文益民.粗糙集多目标并行属性约简算法.软件学报,,():0

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2020-08-05
  • 最后修改日期:2020-11-17
  • 录用日期:
  • 在线发布日期: 2022-03-24
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号