METHOD OF CLUSTERIZATION, BASED ON SERIAL LAUNCHING OF K-MEANS WITH IMPROVED SELECTION OF THE CANDIDATE FOR NEW POSITION OF INSERTION

Authors

  • Oleksandr Tkachenko Vinnytsia National Technical University
  • Oksana Grijo Tukalo Vinnytsia National Technical University
  • Olexiy Dzys Vinnytsia National Technical University
  • Sergiy Lakhovets Vinnytsia National Technical University

Keywords:

code books, clusterization, k-means, centroides, kd-trees

Abstract

The paper suggests improved method of K-means clusterization, which, unlike the conventional method, allows to obtain the solution, close to global minimum of distortion by means of serial launching of k-means for 1, 2, ..., k .centroides. Decrease of distortion is achieved at the expense of improvement of the procedure of vectors-candidates definition on the selection of insertion position of new centroide without considerable slowing down of operation time.

 

REFERENCES

1. Fayyad U. M. Advances in Knowledge Discovery and Data Mining / U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, R. Uthurusamy // AAAI/MIT Press. – 1996. – 611 p.

2. Gersho A. Vector Quantization and Signal Compression. / A. Gersho, R. M. Gray // Boston: Kluwer Academic. – 1992. – 760 p.

3. Duda R. O. Pattern Classification and Scene Analysis / R. O. Duda, P. E. Hart // New York: John Wiley & Sons. – 1973. – 512 p.

4. Jain A. K. Algorithms for Clustering Data / A. K. Jain, R. C. Dubes // Englewood Cliffs, N.J.: Prentice Hall. – 1988. – 334 p.

5. Arthur D. k-means++: The advantages of careful seeding / D. Arthur, S. Vassilvitskii // ACM-SIAM Symposium on Discrete Algorithms (SODA 2007) Astor Crowne Plaza – New Orleans, Louisiana. – 2007. – P. 1027 – 1035.

6. Lai Jim Z. C. Fast k-means clustering algorithm using cluster center displacement / Jim Z. C. Lai, Tsung-Jen Huang, Yi-Ching Liaw // Pattern Recognition. – 2009. – No 11, vol. 42. – P. 2551 – 2556.

7. Kanungo T. An Efficient k-means clustering algorithm: analysis and implementation / T. Kanungo, D. M. Mount, N. S. Netanyahu, C. Piatko, R. Silverman and A.Y. Wu // IEEE Transactions On Pattern Analysis And Machine Intelligence. – 2002. – No. 7, vol. 24. – P. 881 – 892.

8. Likas A. The global k-means clustering algorithm / Aristidis Likas, Nikos Vlassis, Jacob J. Verbeek // Pattern Recognition. – 2002. – No 2, vol. 36. – P. 451 – 461.

9. Refining initial points for KMeans clustering : (Conference on Machine Learning) [Електронний ресурс] / P. S. Bradley, U. M. Fayyad // Proceedings of Fifteenth Intl. – 1998. – P. 91 – 99. / Режим доступу: ftp://ftp.research.microsoft.com/pub/tr/tr-98-36.pdf.

10. Hussein N. A Fast Greedy K-Means Algorithm / Master’s Thesis Nr:9668098 N. Hussein. – University of Amsterdam Faculty of Mathematics, Computer Sciences, Physics and Astronomy Euclides Building Plantage muidergracht 24. – 2002. – p. 62.

11. Moore Andrew William Efficient memory based learning for robot control / Moore Andrew William. – PhD thesis Nr: UCAM-CL-TR-209. – 1990. – p. 248.

12. Kanungo T. A Local Search Approximation Algorithm for k-Means Clustering / T. Kanungo, D. M. Mount, N. S. Netanyahu, C. Piatko, R. Silverman, A. Y. Wu // Computational Geometry: Theory and Applications. – 2004. – No 2. – P. 89 – 112.

13. Ткаченко О. М. Ефективне векторне квантування LSF-параметрів при ущільненні мовних сигналів / О. М. Ткаченко, О. Д. Феферман, С. В. Хрущак // Інформаційні технології та комп’ютерна інженерія. – 2007. – № 1. – С. 124 – 129

Author Biographies

Oleksandr Tkachenko, Vinnytsia National Technical University

Cand. Sc. (Eng.), Assistant Professor, Department of Computer Engineering

Oksana Grijo Tukalo, Vinnytsia National Technical University

Student

Olexiy Dzys, Vinnytsia National Technical University

Student

Sergiy Lakhovets, Vinnytsia National Technical University

Student

Downloads

Abstract views: 136

Published

2015-11-27

How to Cite

[1]
O. Tkachenko, O. Grijo Tukalo, O. Dzys, and S. Lakhovets, “METHOD OF CLUSTERIZATION, BASED ON SERIAL LAUNCHING OF K-MEANS WITH IMPROVED SELECTION OF THE CANDIDATE FOR NEW POSITION OF INSERTION”, Works of VNTU, no. 2, Nov. 2015.

Issue

Section

Information Technologies and Computer Engineering

Metrics

Downloads

Download data is not yet available.