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

Авторы

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

Ключевые слова:

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

Аннотация

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

Биографии авторов

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

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

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

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

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

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

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

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

Библиографические ссылки

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.

Загрузки

Просмотров анотаций: 183

Как цитировать

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

Выпуск

Раздел

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

Метрики

Скачивания

Данные скачивания пока недоступны.