Провалы и недостатки метода k-средних

Примеры провалов метода k-средних

Здравствуйте и вновь добро пожаловать на занятия по теме «Кластерный анализ и машинное обучение без учителя на языке Python».

В этой лекции мы рассмотрим некоторые случаи, в которых использование метода k-средних оказывается безуспешным. Если вы не хотите писать код самостоятельно, а лишь запустить уже созданный файл, перейдите по адресу https://github.com/lazyprogrammer/machine_learning_examples и найдите папку unsupervised_class. Соответствующий файл называется kmeans_fail.py.

Итак, начинаем с оболочки – импорта нужных библиотек и функций и функции main. Импортируем, среди прочего, функцию plot_k_means, написанную нами в прошлый раз.

import numpy as np

from kmeans import plot_k_means

Первый случай, который мы разберём, – «проблема пончика», при которой один кластер находится внутри другого. Создадим для этого соответствующую функцию. Если вы изучали мой курс по логистической регрессии, вы можете заметить, что данные взяты из него. Итак, у нас в качестве данных будет 1 000 точек, размерность равна 2, внутренний радиус установим равным 5, а внешний радиус – равным 10.

def donut():

    N = 1000

    D = 2

    R_inner = 5

    R_outer = 10

    R1 = np.random.randn(N/2) + R_inner

    theta = 2*np.pi*np.random.random(N/2)

    X_inner = np.concatenate([[R1 * np.cos(theta)], [R1 * np.sin(theta)]]).T

    R2 = np.random.randn(N/2) + R_outer

    theta = 2*np.pi*np.random.random(N/2)

    X_outer = np.concatenate([[R2 * np.cos(theta)], [R2 * np.sin(theta)]]).T

    X = np.concatenate([ X_inner, X_outer ])

    return X

В теле функции main в функции plot_k_means после X идёт 2 – ведь мы знаем, что у нас два кластера.

def main():

    X = donut()

    plot_k_means(X, 2)

if __name__ == ‘__main__’:

main()

Второй случай, который мы проверим, – это протяжённые кластеры. Создадим данные – 1 000 точек. Пусть первые 500 будут сгенерированы с помощью функции multivariate_normal со средним значением (0, 0) и ковариантностью (1, 0) и (0, 20), а следующие 500 – со средним значением (5, 0) и той же ковариантной матрицей – тогда получится, что вторые 500 будут находиться в отдалении от первых 500.

X = np.zeros((1000, 2))

X[:500,:] = np.random.multivariate_normal([0, 0], [[1, 0], [0, 20]], 500)

X[500:,:] = np.random.multivariate_normal([5, 0], [[1, 0], [0, 20]], 500)

plot_k_means(X, 2)

И третий случай – два кластера с разной плотностью. Вновь берём 1 000 точек, но теперь в первом кластере будет 950 точек, а во втором – только 50.

X = np.zeros((1000, 2))

X[:950,:] = np.array([0,0]) + np.random.randn(950, 2)

X[950:,:] = np.array([3,0]) + np.random.randn(50, 2)

plot_k_means(X, 2)

Итак, запустим программу.

Сначала видим функцию затрат и кластеры, которые метод k-средних вычислил для «проблемы пончика» – не совсем то, что ожидалось.

Далее – функция затрат для протяжённых гауссиан и найденные кластеры – вновь-таки, не совсем то, чего ожидалось.

Но поскольку Matplotlib любит выравнивать оси, мы вернём график в первоначальный вид, чтобы оси x и y имели один масштаб. Тогда мы увидим действительную форму.

Как видите, на самом деле получилось совсем не то, что предполагалось.

И третий случай – функция затрат для гауссиан с разной плотностью и найденные кластеры.

Как видите, гауссово облако справа, будучи значительно менее плотным, теперь включило в себя часть облака слева, пододвинув последнее.

Недостатки кластеризации методом k-средних

Итак, первый вопиющий недостаток заключается в том, что вы должны предварительно выбрать значение k. Перед этим я любезно сообщал, что наши данные состоят из трёх гауссиан, так что мы знали, что k нужно выбрать равным 3. А что, если бы вы не знали заранее, чему равно k, или размерность данных была бы чересчур велика, чтобы нарисовать диаграмму рассеяния? В таком случае высока вероятность того, что ваши кластеры получатся весьма неудачными.

Второй недостаток, о котором уже упоминалось, состоит в том, что метод k-средних сходится к локальным минимумам. С такой ситуацией мы постоянно сталкиваемся в глубоком обучении, и далеко не всегда это плохо. Но в случае метода k-средних – это, как мы уже убедились, действительно плохо. Один из способов исправить этот недостаток – запустить алгоритм несколько раз и выбрать ту кластеризацию, который даёт наилучшее значение целевой функции.

Но, к сожалению, это подводит нас к очередному недостатку метода k-средних. Он заключается в том, что метод крайне чувствителен к начальной конфигурации. Правда, каждый запуск алгоритма метода k-средних можно проводить независимо от остальных, так что и тут остаётся некоторая возможность устранения этой проблемы.

Ещё один недостаток – метод k-средних, как мы видели, не справляется с задачами, подобными «проблеме пончика». На самом деле метод k-средних не может справиться даже с правильными фигурами вроде эллипса. Это связано с тем, что в методе k-средних во внимание принимается только квадрат расстояния, а это значит, что метод стремится к обнаружению сферообразных кластеров. Если вы не понимаете, почему так получается, особо не беспокойтесь, поскольку мы раскроем эту тему подробнее чуть позже, когда будем обсуждать гауссовы смеси распределения.

Очередная проблема метода k-средних состоит в том, что он не учитывает плотность данных в кластере. Это более тонкая проблема. Заметьте, что из этого прямо следует, что если есть очень плотная область, где размещается много данных, то среднее значение будет находиться ближе к этой плотной области.

Андрей Никитенко
Андрей Никитенко
Задать вопрос эксперту
Понравилась статья? Поделить с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!:

Share via
Copy link