Unsupervised classification and particle swarm optimization

• Autorzy: Truszkowski A. , Topczewska M.

Warianty tytułu

PL

Klasyfikacja nienadzorowana i optymalizacja rojem cząstek

• Języki publikacji: EN

Abstrakty

EN

This article considers three algorithms of unsupervised classification -K-means, Gbest and the Hybrid method, the last two have been proposed in [14]. All three algorithms belong to the class of non-hierarchical methods. At first, the initial split of objects into known in advance number of classes is performed. If it is necessary, some objects are then moved into other clusters to achieve better split - between cluster variation should be much larger than within cluster variation. The first algorithm described in this paper (K-means) is wellknown classical method. The second one (Gbest) is based on the particle swarm intelligence idea. While the third is a hybrid of two mentioned algorithms. Several indices assessing the quality of obtained clusters are calculated.

PL

W niniejszym artykule porównywane są trzy algorytmy analizy skupień - metoda k-średnich, algorytm gbest oraz metoda hybrydowa. Algorytmy gbest oraz hybrydowy zostały zaproponowane w publikacji [14]. Wszystkie trzy metody nalezą a do rodziny metod niehierarchicznych, w których na początku tworzony jest podział obiektów na znaną z góry liczbę klastrów. Następnie, niektóre obiekty przenoszone są pomiędzy klastrami, by uzyskać jak najlepszy podział - wariancja pomiędzy skupieniami powinna być znacznie większa niż wariancja wewnątrz skupień. Pierwszy algorytm (k-means) jest znaną, klasyczną metodą. Drugi oparty jest na idei inteligencji roju cząstek. Natomiast trzeci jest metodą hybrydową łączącą dwa wymienione wcześniej algorytmy. Do porównania uzyskanych skupień wykorzystano kilka różnych indeksów szacujących jakość otrzymanych skupień.

Słowa kluczowe

EN

unsupervised classification; clustering; particle swarm optimization (PSO)

PL

klasyfikacja nienadzorowana; analiza skupień; optymalizacja rojem cząstek

• Wydawca: Oficyna Wydawnicza Politechniki Białostockiej
• Czasopismo: Zeszyty Naukowe Politechniki Białostockiej. Informatyka
• Rocznik: 2012
• Tom: Z. 9
• Strony: 119--132
• Opis fizyczny: Bibliogr. 15 poz., tab., wykr.

Twórcy

autor

Truszkowski A.

autor

Topczewska M.

• Bialystok University of Technology, Faculty of Computer Science, Białystok, Poland

Bibliografia

• [1] X. Cui, T.E. Potok and P. Palathingal, Document Clustering using Particle Swarm Optimization IEEE Swarm Intelligence Symposium, The Westin , 2005.
• [2] K. Fukunaga, Introduction to Statistical Pattern Recognition, Morgan Kaufmann, San Francisco, 1990.
• [3] T. Hardin, X. Cui, R.K. Ragade, J.H. Graham and A.S. Elmaghraby, A Modified Particle Swarm Algorithm for Robotic Mapping of Hazardous Environments, The 2004 World Automation Congress, Seville, Spain, 2004.
• [4] L. Hubert and P. Arabie, Comparing partitions., Journal of Classification, 193-218, 1985.
• [5] R.A. Johnson, D.W. Wichern, Applied Multivariate Statistical Analysis, Prentice-Hall International, Inc., 1992.
• [6] J. Kennedy and R. Eberhart, Particle swarm optimization., Proceedings of IEEE International Conference on Neural Networks, IEEE Press, Piscataway, NJ, USA, 1942-1948, 1995.
• [7] R.J. Kuo, L.M. Ho and C.M. Hu, Integration of self-organizing feature map and K-means algorithm for market segmentation, Computers & Operations Research, Vol. 29, Issue 11, 1475–1493, 2002.
• [8] H. Liu and X. Yu, Application Research of k-means Clustering Algorithm in Image Retrieval System, Proceedings of the Second Symposium International Computer Science and Computational Technology(ISCSCT ’09), Huangshan, P.R. China, 274-277, 2009
• [9] J.B. McQueen, Some methods for classification and analysis of multivariate observations, Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, 1, Berkeley, Calif.: University of California Press, 281-297, 1967.
• [10] M. Omran, A. Salman and A.P. Engelbrecht, Image classification using particle swarm optimization, Proceedings of the 4th Asia-Pacific Conference on Simulated Evolution and Learning (SEAL 2002), Singapore, 370-374, 2002.
• [11] O.J. Oyelade, O.O. Oladipupo, I.C. Obagbuwa, Application of k-Means Clustering algorithm for prediction of Students’ Academic Performance, International Journal of Computer Science and Information Security, Vol. 7, No. 1, pp. 292-295, 2010
• [12] R. Pietrzykowski and W. Zielinski and D. Kozioł, Application of k-means method for a portfolio of shares taxonomy (in Polish), Wyd. Wyzszej Szkoły Ekonomiczno–Informatycznej, Warszawa, s.3, 74-76, 2005.
• [13] W.M. Rand, Objective criteria for the evaluation of clustering methods, Journal of the American Statistical Association, 66, 846-850, 1971.
• [14] D.W. van der Merwe and A.P. Engelbrecht, Data clustering using particle swarm optimization, The 2003 Congress on Evolutionary Computation (CEC’03), vol. 1, 215- 220, Canbella, Australia, 2003.
• [15] http:/ /aragorn.pb.bialystok.pl/~magda/data/dane.zip