k means algorithm

алгоритм k-средних

Это реализация алгоритма k-средних на Python, включая метод локтя и метод силуэта для выбора оптимального K.

K-means — популярный алгоритм кластеризации, используемый для разделения данных на K-кластеры. Он работает путем итеративного присвоения каждой точки данных ближайшему центроиду кластера, а затем пересчета центроида каждого кластера на основе назначенных ему точек данных. Процесс повторяется до сходимости.

Алгоритм

• Случайным образом выберите K начальных центроидов кластера из точек данных.
• Назначьте каждую точку данных ближайшему центроиду кластера.
• Пересчитайте центроид каждого кластера на основе назначенных ему точек данных.
• Повторяйте шаги 2–3 до тех пор, пока не произойдет сходимость (т. е. когда назначения кластеров больше не будут меняться).

Целевая функция

Целью k-средних является минимизация суммы квадратов расстояний между каждой точкой данных и назначенным ей центроидом кластера. Целевую функцию можно записать как: $$J = sum_{j=1}^K sum_{i=1}^N||x_i^j - mu_j||^2$$ где $x_i^j$ — i-th точка данных в кластере j , μj — центроид кластера j , а N — общее количество точек данных.

Метод локтя

Метод Elbow — это эвристика, используемая для определения оптимального количества кластеров в кластеризации K-Means. Метод отображает сумму квадратов расстояний между каждым наблюдением и назначенным ему центроидом как функцию количества кластеров. Точка «локоть» на графике указывает количество кластеров, в которых добавление дополнительных кластеров не приводит к значительному уменьшению суммы квадратов расстояний.

Метод локтя можно резюмировать следующими этапами:

• Запустите кластеризацию K-Means для диапазона значений k.
• Вычислить сумму квадратов расстояний для каждого значения k
• Постройте сумму квадратов расстояний как функцию k
• Определите на графике точку «локтя».

Метод силуэта

Метод Silhouette — еще одна эвристика, используемая для определения оптимального количества кластеров в кластеризации K-Means. Метод измеряет качество назначения кластера каждого наблюдения путем расчета его коэффициента силуэта. Коэффициент силуэта варьируется от -1 до 1, где значение 1 указывает на то, что наблюдение хорошо кластеризовано, а значение -1 указывает на то, что наблюдение неправильно классифицировано. Формула для расчета коэффициента силуэта для точки данных i : $$s(i) = frac{(b(i) - a(i))}{max(a(i), b(i))}$$ где a(i) — среднее расстояние между i и всеми другими точками данных в его кластере, а b(i) — минимальное среднее расстояние между i и всеми остальными кластерами (т. е. кластером со следующим ближайшим центроидом). Коэффициент силуэта для всей кластеризации представляет собой среднее значение коэффициентов силуэта для всех точек данных.

Метод Silhouette можно резюмировать следующими этапами:

• Запустите кластеризацию K-Means для диапазона значений k.
• Для каждого наблюдения рассчитайте коэффициент силуэта
• Рассчитайте средний коэффициент силуэта для каждого значения k.
• Постройте средний коэффициент силуэта как функцию k
• Определите значение k с самым высоким средним коэффициентом силуэта.