代价敏感属性约简的混合蚁群优化算法

发布时间：2018-01-12 02:31

本文关键词：代价敏感属性约简的混合蚁群优化算法　出处：《西南石油大学》2017年硕士论文　论文类型：学位论文

【摘要】：随着计算机应用领域的不断扩张,所采集数据的维度呈现爆炸性增长。属性约简的本质是在保持决策系统分类能力不变的前提下,降低数据维度,帮助人们高效地做出决策。代价敏感学习是数据挖掘中十大最具挑战性问题之一,其相关属性约简问题的目的是获得最小测试代价、时间代价或误分类代价等。针对代价敏感属性约简问题,很多仿生算法已被提出。蜂群算法速度快,但过早收敛导致局部最优解,即解的代价不是最低。蚁群算法寻优能力强,但运行效率较低。本文提出了一种混合蚁群优化算法的一般性框架(hybrid ant colony optimization general framework,HA),它由两种搜索策略混合而成,即部分搜索和完全搜索策略。在部分搜索策略中,每只先驱者蚂蚁选择出k个属性。其中,k是一个经验值,由一个初始约简的大小决定。部分搜索策略摈弃了频繁计算正区域、删除冗余属性等操作,使得HA具有高效性。在完全搜索策略中,每只收割者蚂蚁选择出一个可行解。在两种搜索策略中,人工蚂蚁均通过更新路径上的信息素来优化路径。对于最小测试代价和最小时间代价的属性约简问题,本文基于HA分别实现了相应具体的算法。实验采用了 UCI数据库中的四个真实数据集,每个数据集采取三种不同的代价分布。通过大量的参数调整以及与已有算法的对比,结果表明:1)参数配置对速度与解产生重要影响;2)当解的质量(比如找到最优因子)相当时,本文算法运行效率高于已有算法;3)当运行效率相近时,本文算法解的质量高于已有算法。
[Abstract]:With the continuous expansion of computer application field, the dimension of the collected data presents explosive growth. The essence of attribute reduction is to reduce the data dimension on the premise of keeping the ability of decision system classification unchanged. Cost-sensitive learning is one of the ten most challenging problems in data mining. For the cost sensitive attribute reduction problem, many bionic algorithms have been proposed. Bee colony algorithm is fast, but premature convergence leads to local optimal solution. The cost of the solution is not the lowest. However, the running efficiency is low. In this paper, a general framework of hybrid ant colony optimization algorithm is proposed. Hybrid ant colony optimization general framework. Hahe, which consists of two search strategies, partial search and complete search. In the partial search strategy, each pioneer ant selects k attributes, where k is an empirical value. Part of the search strategy abandons the frequent computation of positive areas and deletes redundant attributes, which makes HA efficient in the complete search strategy. Each reaper ant chooses a feasible solution. In both search strategies, the artificial ant optimizes the path by updating the information on the path. The attribute reduction problem of minimum test cost and minimum time cost is discussed. In this paper, the corresponding algorithm is implemented based on HA, and four real data sets in UCI database are used in the experiment. Each data set takes three different cost distributions. Through a large number of parameter adjustments and comparison with existing algorithms, the results show that the configuration of the parameters has an important effect on the speed and solution. 2) when the quality of the solution (such as finding the optimal factor) is equal, the efficiency of the algorithm is higher than that of the existing algorithm. 3) when the running efficiency is similar, the quality of the proposed algorithm is higher than that of the existing algorithm.
【学位授予单位】：西南石油大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【参考文献】