Алгоритмы типа K-means: обобщённая теорема сходимости и характеристика локальной оптимальности

Алгоритм K-means является широко используемой методикой в кластерном анализе. В данной статье рассматриваются несколько вопросов, связанных с этим алгоритмом. Задача кластеризации сначала представлена как невыпуклая математическая программа. Затем приводится строгий доказательный вывод конечной сходимости алгоритма типа K-means для произвольной метрики. Показано, что при определённых условиях алгоритм может не сходиться к локальному минимуму, и что при условии дифференцируемости он сходится к точке Куна—Таккера. Наконец, приводится метод получения решения, соответствующего локальному минимуму.