Parallel Feature Selection Algorithm based on Rough Sets and Particle Swarm Optimization

• Autorzy: Mateusz Adamczyk
• Języki publikacji: EN

Abstrakty

EN

The aim of this paper is to propose a new method of solving feature selection problem. Foundations of presented algorithm lie in the theory of rough sets. Feature selection methods based on rough sets have been used with success in many data mining problems, but their weakness is their computational complexity. In order to overcome the above-mentioned problem, researches used diverse approximation techniques. This paper presents a new approach to approximation of reducts. Particle swarm optimization (PSO) is a stochastic meta-heuristic similar to genetic algorithms. The idea is to see each potential solution as a particle with certain velocity flying through the problem space. The PSO finds optimal solutions by interactions of individuals in population. The main advantage of the PSO over genetic algorithms, is that PSO does not require complex operators such as crossover or mutation. It only uses simple mathematical operators to update position and velocity of each particle, which makes PSO computationally inexpensive in terms of both memory and runtime. The presented feature selection algorithm treats each feature subset as separate particle. Optimal subset, in terms of selected measure, is discovered as particles fly within the problem space. In order to speed up calculations and balance usage of hardware resources (processors, memory), parallel asynchronous version of PSO is applied. It is based on scheduling calculations of complex fitness function on slave processors, while the main one is responsible for updating particles data and checking algorithm's convergence. Applied approach scales well and provides balanced usage of given resources even if it is not feasible to use the same computational power of every processor, for instance when used resources are not homogeneous. Proposed method was tested on selected set of data sets from the UCI repository and results were compared to some of the classical algorithms. (original abstract)

Słowa kluczowe

EN

Rough sets; Algorithms; Mathematical functions

PL

Zbiory przybliżone; Algorytmy; Funkcje matematyczne

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2014
• Tom: 2
• Strony: 43--50

Twórcy

autor

Mateusz Adamczyk

• University of Warsaw, Poland

Bibliografia

• Bache, K., Lichman, M.: UCI Machine Learning Repository, http: //archive.ics.uci.edu/ml, 2013, University of California, Irvine, School of Information and Computer Sciences
• Bazan, J. G., Szczuka, M.: RSES and RSESlib-a collection of tools for rough set computations, Rough Sets and Current Trends in Computing, 106?113, Springer Berlin Heidelberg, 2001, http://www.dx.doi.org/10.1007/3-540-45554-X_12
• Bazan, J. G.: A comparison of dynamic and non-dynamic rough set methods for extracting laws from decision tables, Rough sets in knowledge discovery, 1, 321?365, Citeseer, 1998
• Chu, S.-C., Roddick, J. F., Pan, J.-S.: Parallel particle swarm optimization algorithm with communication strategies, submitted to IEEE Transactions on Evolutionary Computation, 2003
• Das, S.: Filters, wrappers and a boosting-based hybrid for feature selection, ICML, 1, 74?81, Citeseer, 2001
• Eberhart, R., Kennedy, J.: Particle Swarm Optimization, Neural Networks, 1995., IEEE International Conference on, 1942-1948, IEEE, 1995, http://www.dx.doi.org/10.1109/ICNN.1995.488968
• Fleuret, F.: Fast binary feature selection with conditional mutual information, The Journal of Machine Learning Research, 5, 1531?1555, JMLR. org, 2004
• Goldberg, D.: Genetic algorithms in search, optimization, and machine learning, Addison-wesley Reading Menlo Park, 1989
• Guyon, I., Elisseeff, A.: An introduction to variable and feature selection, The Journal of Machine Learning Research, 3, 1157?1182, JMLR. org, 2003
• Koh, B., George, A. D., Haftka, R. T., Fregly, B.: Parallel asynchronous particle swarm optimization, International Journal for Numerical Methods in Engineering, 67, 4, 578?595, Wiley Online Library, 2006, http://www.dx.doi.org/10.1002/nme.1646
• Komorowski, J., Pawlak, Z., Polkowski, L., Skowron, A.: Rough sets: A tutorial, Rough fuzzy hybridization: A new trend in decision-making, 3?98, Springer Verlag, Singapore, 1999
• Pawlak, Z.: Information systems theoretical foundations, Information systems, 6, 3, 205?218, Elsevier, 1981 http://www.dx.doi.org/10.1016/0306-4379(81)90023-5
• Shi, Y., Eberhart, R.: A modified particle swarm optimizer, Evolutionary Computation Proceedings, 1998. IEEE World Congress on Computational Intelligence., The 1998 IEEE International Conference on, 69?73, IEEE, 1998, http://www.dx.doi.org/10.1109/ICEC.1998.699146
• Stefanowski, J.: On rough set based approaches to induction of decision rules, Rough sets in knowledge discovery, 1, 1, 500?529, Heidelberg, Germany: Physica-Verlag, 1998
• Wang, X., Yang, J., Teng, X., Xia, W., Jensen, R.: Feature selection based on rough sets and particle swarm optimization, Pattern Recognition Letters, 28, 4, 459?471, Elsevier, 2007, http://www.dx.doi.org/10.1016/j.patrec.2006.09.003
• Widz, S. and Slezak, D., Rough Set Based Decision Support ? Models Easy to Interpret, Selected Methods and Applications of Rough Sets in Management and Engineering, 95-112, Peters, G., Lingras, P., Slezak, D., Yao, Y., Advanced Information and Knowledge Processing, Springer, 2012, http://www.dx.doi.org/10.1007/978-1-4471-2760-4_6