1 Свойства и структура алгоритма

По числу процессов — при увеличении числа процессов эффективность уменьшается на всей области рассматриваемых значений, причем темп убывания замедляется с ростом числа процессов.
По размеру задачи — при увеличении размера задачи эффективность вычислений вначале кратковременно возрастает, но затем начинает относительно равномерно убывать на всей рассматриваемой области.
По размеру задачи — при увеличении размера задачи эффективность вычислений в общем случае постепенно убывает. На малых данных она выходит на пик мощности, являющийся максимумом эффективности в исследуемых условиях, но затем возвращается к процессу убывания.

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

В однопоточном режиме на наборах данных, представляющих практический интерес (порядка нескольких десятков тысяч векторов и выше), время работы алгоритма неприемлемо велико. Благодаря свойству массового параллелизма должно наблюдаться значительное ускорение алгоритма на многоядерных архитектурах (Intel Xeon), а также на графических процессорах, даже на мобильных вычислительных системах (ноутбуках), оснащенных видеокартой. Алгоритм k-means также будет демонстрировать значительное ускорение на сверхмощных вычислительных комплексах (суперкомпьютерах, системах облачных вычислений^[18]).
На сегодняшний день существует множество реализаций алгоритма k-means, в частности, направленных на оптимизацию параллельной работы на различных архитектурах^[19][20][21]. Предлагается множество адаптаций алгоритма под конкретные архитектуры. Например, авторы работы^[22] производят перерасчет центров кластеров на этапе распределения векторов по кластерам.

2.7 Существующие реализации алгоритма

2.7.1 Открытое программное обеспечение

1. 
   CrimeStat
   

Программное обеспечение, созданное для операционных систем Windows, предоставляющее инструменты статистического и пространственного анализа для решения задачи картирования преступности.

2. 
   Julia
   

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

3. 
   Mahout
   

Apache Mahout - Java библиотека для работы с алгоритмами машинного обучения с использованием MapReduce. Содержит реализацию k-means.

4. 
   Octave
   

Написанная на C++ свободная система для математических вычислений, использующая совместимый с MATLAB язык высокого уровня, содержит реализацию k-means.

5. 
   Spark
   

Распределенная реализация k-means содержится в библиотеке Mlib для работы с алгоритмами машинного обучения, взаимодействующая с Python библиотекой NumPy и библиотека R.

6. 
   Torch
   

MATLAB-подобная библиотека для языка программирования Lua с открытым исходным кодом, предоставляет большое количество алгоритмов для глубинного обучения и научных расчётов. Ядро написано на Си, прикладная часть выполняется на LuaJIT, поддерживается распараллеливание вычислений средствами CUDA и OpenMP. Существуют реализации k-means.

7. 
   Weka
   

Cвободное программное обеспечение для анализа данных, написанное на Java. Содержит k-means и x-means.

8. 
   Accord.NET
   

C# реализация алгоритмов k-means, k-means++, k-modes.

9. 
   OpenCV
   

Написанная на С++ библиотека, направленная в основном на решение задач компьютерного зрения. Содержит реализацию k-means.

10. 
    MLPACK
    

Масштабируемая С++ библиотека для работы с алгоритмами машинного обучения, содержит реализацию k-means.

11. 
    SciPy
    

Библиотека Python, содержит множество реализаций k-means.

12. 
    scikit-learn
    

Библиотека Python, содержит множество реализаций k-means.

13. 
    R
    

Язык программирования для статистической обработки данных и работы с графикой, а также свободная программная среда вычислений с открытым исходным кодом в рамках проекта GNU, содержит три реализации k-means.

14. 
    ELKI
    

Java фреймворк, содержащий реализацию k-means, а также множество других алгоритмов кластеризации.