МЕТОД КЛАСТЕРИЗАЦІЇ НА ОСНОВІ ПОСЛІДОВНОГО ЗАПУСКУ 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.
Як цитувати
[1]
О. Ткаченко, О. Грійо Тукало, О. Дзісь, і С. Лаховець, МЕТОД КЛАСТЕРИЗАЦІЇ НА ОСНОВІ ПОСЛІДОВНОГО ЗАПУСКУ K-СЕРЕДНІХ З УДОСКОНАЛЕНИМ ВИБОРОМ КАНДИДАТА НА НОВУ ПОЗИЦІЮ ВСТАВКИ, НПВНТУ, № 2, 1.
Розділ
Інформаційні технології та комп'ютерна техніка

Найчитабильні статті цього ж автора(ів)

Цей плагін вимагає, щонайменше, один звіт статистики / плагін повинен бути включений. Якщо плагіни вашої статистики забезпечують більше однієї метрики, будь ласка, також виберіть основну метрику на сторінці налаштувань адміністратор сайту і / або на сторінках налаштувань менеджера журналу.