Data discretization algorithm based on adaptive improved particle swarm optimization

doi:10.11772/j.issn.1001-9081.2016.01.0188

Abstract

Abstract: Focusing on the issue that the classical rough set can only deal with discrete attributes, a discretization algorithm based on Adaptive Hybrid Particle Swarm Optimization (AHPSO) was proposed. Firstly, the adaptive adjustment strategy was introduced, which could not only overcome the shortage that the particle swarm was easy to fall into local extremum but also improve the ability of seeking the global excellent result. Secondly, the Tabu Search (TS) method was introduced to deal with the global optimal particle of each generation and to get the best global optimal particle, which enhanced the local search ability of particle swarm. Finally, the attribute discretization points were initialized to the particle group when the classification ability of the decision table had been kept. The optimal discretization points were sought through the interaction between particles. By using the classification method of J48 decision tree based on WEKA (Waikato Environment for Knowledge Analysis) platform, compared with the discretization algorithms based on importance of attribute and information entropy, the classification accuracy of the proposed algorithm improved by about 10% to 20%.Compared with the discretization algorithms based on Niche Discrete PSO (NDPSO) and linearly decreasing weight PSO, the classification accuracy of the proposed algorithm improved by about 2% to 5%. The experimental results show that the proposed algorithm significantly enhances the accuracy of classification by J48 decision tree, and it has better validity for discretization of continuous attributes.

Key words: classical rough set, self-adaption, Particle Swarm Optimization (PSO), discretization, Tabu Search (TS)

摘要： 针对经典粗糙集只能处理离散型属性的问题,提出一种基于自适应混合粒子群优化(AHPSO)的离散化算法。首先,引入自适应调整策略,以克服粒子群易陷入局部解的缺点,提高了粒子群全局寻优能力;然后对每一代全局最优粒子进行禁忌搜索(TS),得到当代最佳全局最优粒子,增强了粒子群局部搜索能力;最后,在保持决策表分类能力不变的情况下,将属性离散化分割点初始化为粒子群体,通过粒子间的相互作用得到最佳的离散化分割点。使用WEKA平台上的J48决策树分类方法,与基于属性重要度、信息熵的离散化算法相比,该算法的分类精度提升了10%~20%;与基于小生境离散粒子群优化(NDPSO)、参数线性递减粒子群的离散化算法相比,该算法的分类精度提升了2%~5%。实验结果表明,该算法显著地提高了J48决策树的分类学习精度,在对数据离散化时也有较好的性能。

关键词: 经典粗糙集, 自适应, 粒子群优化, 离散化, 禁忌搜索

CLC Number:

TP311
TP18

DONG Yuehua, LIU Li. Data discretization algorithm based on adaptive improved particle swarm optimization[J]. Journal of Computer Applications, 2016, 36(1): 188-193.

董跃华, 刘力. 基于自适应改进粒子群优化的数据离散化算法[J]. 计算机应用, 2016, 36(1): 188-193.

References

[1] GARCIA S, LUENGO J, SAEZ J A, et al. A survey of discretization techniques: taxonomy and empirical analysis in supervised learning [J]. IEEE transactions on knowledge & data engineering, 2013, 25(4): 734-750.
[2] KOTSIANTIS S, KANELLOPOULOS D. Discretization techniques: a recent survey [J]. GESTS international transactions on computer science and engineering, 2006, 32(1): 47-58.
[3] 李慧,闫德勤,韩丽.一种基于粗糙集理论的连续属性离散化新算法[J].计算机应用研究,2010,27(1):77-78.(LI H, YAN D Q, HAN L. Novel algorithm for discretization of continuous attributes based on rough sets theory [J]. Application research of computers, 2010, 27(1): 77-78.)
[4] JIN R, BREITBART Y, MUOH C. Data discretization unification [J]. Knowledge & information systems, 2008, 19(1): 1-29.
[5] TIAN D, ZENG X J, KEANE J. Core-generating approximate minimum entropy discretization for rough set feature selection in pattern classification [J]. International journal of approximate reasoning, 2011, 52(6): 863-880.
[6] 侯利娟,王国胤,聂能,等.粗糙集理论中的离散化问题[J].计算机科学,2000,27(12):89-94.(HOU L J,WANG G Y, NIE N, et al. Discretization in rough set theory [J]. Computer science, 2000, 27(12): 89-94.)
[7] 谢宏,程浩忠,牛东晓.基于信息熵的粗糙集连续属性离散化算法[J].计算机学报,2005,28(9):1570-1574.(XIE H, CHENG H Z, NIU D X. Discretization of continuous attributes in rough set theory based on information entropy [J]. Chinese journal of computers, 2005, 28(9): 1570-1574.)
[8] 许磊,张凤鸣,靳小超.基于小生境离散粒子群优化的连续属性离散化算法[J].数据采集与处理,2008,23(5):584-588.(XU L, ZHANG F M, JIN X C. Discretization algorithm for continuous attributes based on niche discrete particle swarm optimization [J]. Journal of data acquisition & processing, 2008, 23(5):584-588.)
[9] 汪凌.一种基于改进粒子群的连续属性离散化算法[J].计算机工程与应用,2013,49(21):33-36.(WANG L. Algorithm of continuous attribute discretization based on improved particle swarm [J]. Computer engineering and applications, 2013, 49(21): 33- 36.)
[10] 史哲文,白雪石,郭禾.基于改进小生境粒子群算法的多模函数优化[J].计算机应用研究,2012,29(2):465-468.(SHI Z W, BAI X S, GUO H. Multimodal function optimization based on modified niching particle swarm optimization [J]. Application research of computers, 2012, 29(2): 465-468.)
[11] SHI Y, EBERHART R. A modified particle swarm optimizer [C] // Proceedings of the 1998 IEEE International Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence. Piscataway, NJ: IEEE, 1998: 69-73.
[12] 张腾飞,王锡淮,肖健梅.基于微粒群优化的连续属性离散化算法[J].计算机工程,2006,32(3):44-46.(ZHANG T F, WANG X H, XIAO J M. Algorithm for discretization of continuous attributes based on particle swarm optimization [J]. Computer engineering, 2006, 32(3): 44-46.)
[13] GLOVER F, KELLY J P, LAGUNA M. Genetic algorithms and tabu search: hybrids for optimization [J]. Computers & operations research, 1995, 22(1): 111-134.
[14] RATNAWEERA A, HALGAMUGE S, WATSON H C. Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients [J]. IEEE transactions on evolutionary computation, 2004, 8(3): 240-255.
[15] 吕振肃,侯志荣.自适应变异的粒子群优化算法[J].电子学报,2004,32(3):416-420.(LYU Z S, HOU Z R. Particle swarm optimization with adaptive mutation [J]. Acta electronica sinica, 2004, 32(3): 416-420.)
[16] 朱小明,张慧斌.PSO算法的稳定性分析及算法改进[J].计算机科学,2013,40(3):275-278.(ZHU X M, ZHANG H B. Stability analysis of particle swarm optimization algorithm and its improved algorithm [J]. Computer science, 2013, 40(3): 275-278.)
[17] SHI Y, EBERHART R C. Empirical study of particle swarm optimization [C]// Proceedings of the 2004 IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2004: 1945-1950.
[18] CHATTERJEE A, SIARRY P. Nonlinear inertia weight variation for dynamic adaptation in particle swarm optimization [J]. Computers & operations research, 2006, 33(3): 859-871.