МЕТОД КЛАСТЕРИЗАЦИИ НА ОСНОВЕ ПОСЛЕДОВАТЕЛЬНОГО ЗАПУСКА K-СРЕДНИХ С УСОВЕРШЕНСТВОВАННЫМ ВЫБОРОМ КАНДИДАТА НА НОВУЮ ПОЗИЦИЮ ВСТАВКИ

Authors

  • Александр Николаевич Ткаченко Винницкий национальный технический университет
  • Оксана Франсисковна Грийо Тукало Винницкий национальный технический университет
  • Алексей Викторович Дзись Винницкий национальный технический университет
  • Сергей Максимович Лаховец Винницкий национальный технический университет

Keywords:

кодовые книги, кластеризация, метод k-средних, центроиды, kd-деревья

Abstract

В работе предложен усовершенствованный метод кластеризации k-средних, который, в отличие от классического, позволяет получить решение, приближенное к глобальному минимуму искажения путем последовательного запуска k-средних для центроидов 1, 2, ..., k . Уменьшение искажения достигается за счет улучшенной процедуры определения векторов-кандидатов на выбор позиции вставки нового центроида без значительного замедления времени работы.

Author Biographies

Александр Николаевич Ткаченко, Винницкий национальный технический университет

к. т. н., доцент кафедры вычислительной техники

Оксана Франсисковна Грийо Тукало, Винницкий национальный технический университет

студентка института информационных технологий и компьютерной инженерии

Алексей Викторович Дзись, Винницкий национальный технический университет

студент института информационных технологий и компьютерной инженерии

Сергей Максимович Лаховец, Винницкий национальный технический университет

студент института информационных технологий и компьютерной инженерии

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.

Downloads

Abstract views: 175

How to Cite

Ткаченко, А. Н., О. Ф. Грийо Тукало, А. В. Дзись, and С. М. Лаховец. “МЕТОД КЛАСТЕРИЗАЦИИ НА ОСНОВЕ ПОСЛЕДОВАТЕЛЬНОГО ЗАПУСКА K-СРЕДНИХ С УСОВЕРШЕНСТВОВАННЫМ ВЫБОРОМ КАНДИДАТА НА НОВУЮ ПОЗИЦИЮ ВСТАВКИ”. Научные труды Винницкого национального технического университета, no. 2, Nov. 2012, https://trudy.vntu.edu.ua/index.php/trudy/article/view/341.

Issue

Section

Информационные технологии и компьютерная техника

Metrics

Downloads

Download data is not yet available.