Я читаю Бишопа об алгоритме EM для GMM и взаимосвязи между GMM и k-means.
В этой книге говорится, что k-means - это жестко заданная версия GMM. Мне интересно, означает ли это, что если данные, которые я пытаюсь кластеризовать, не являются гауссовыми, я не могу использовать k-means (или, по крайней мере, они не подходят для использования)? Например, что если данные являются изображениями рукописных цифр, состоящих из 8 * 8 пикселей каждое со значением 0 или 1 (и предположить, что они независимы, то это должна быть смесь Бернулли)?
Я немного запутался в этом и буду благодарен за любые мысли.
clustering
data-mining
k-means
gaussian-mixture
eddie.xie
источник
источник
Ответы:
В типичных ситуациях EM GMM учитывают дисперсию и ковариацию. Это не сделано в k-средних.
Но действительно, одна из популярных эвристик для k-средних (примечание: k-means - это проблема, а не алгоритм) - алгоритм Ллойда - по сути является EM-алгоритмом, использующим модель центроида (без дисперсии) и жесткие назначения.
Выполняя кластеризацию в стиле k-средних (т.е. минимизацию дисперсии), вы
Обычно говорят, что к-среднее предполагает сферические кластеры. Также общепризнанно, что кластеры k-средних являются клетками Вороного, т.е. не сферическими. Оба верны, и оба неправы. Прежде всего, кластеры - это не полные клетки Вороного, а только известные в них объекты. Нет необходимости рассматривать мертвое пространство между кластерами как часть любого кластера, так как наличие там объекта повлияет на результат алгоритма. Но не намного лучше назвать это «сферическим», просто потому, что евклидово расстояние сферическое. K-means не заботится о евклидовом расстоянии. Все, что есть, - это эвристика для минимизации дисперсий . И это на самом деле то, что вы должны рассматривать k-означает: минимизация дисперсии.
источник
minimize squared euclidean distance
илиminimize the variances
? Должны быть слова «сумма» или «объединено» или что-то подобное, потому что у нас есть 2+ кластера, не так ли?coincidentally minimize Euclidean distance, because the sqrt function is monotone
, если быть точным, не верна.minimize squared Euclidean distance, because WCSS variance contribution = squared euclidean distance
означает , ? Вы говорите «квадраты d между объектами в кластерах минимизируются, потому что WCSS отклонений минимизируется», или просто «WCSS отклонений минимизируется, которые - отклонения - являются евклидовыми расстояниями по природе»? Или что-то еще?GMM использует перекрывающиеся холмы, которые простираются до бесконечности (но практически учитывают только 3 сигмы). Каждая точка получает все оценки вероятности холмов. Кроме того, холмы имеют «яйцевидную форму» [хорошо, это симметричные эллипсы ] и, используя полную ковариационную матрицу, могут быть наклонены .
K-означает жесткое назначение точки одному кластеру, поэтому оценки других центров кластеров игнорируются (неявно сбрасываются в ноль / не волнует). На холмах сферические мыльные пузыри. При соприкосновении двух мыльных пузырей граница между ними становится плоской (гипер) плоскостью. Точно так же, как когда вы пускаете пену из множества мыльных пузырей, пузыри внутри не плоские, а квадратные, поэтому границы между многими (гипер-) сферами фактически образуют вороное разделение пространства. В 2D это имеет тенденцию выглядеть неопределенно как гексагональная плотная упаковка, например, улей (хотя, конечно, ячейки Вороного не гарантированно будут шестиугольниками). Холм с K-средним является круглым и не наклоняется, поэтому у него меньше представительная сила; но это гораздо быстрее для вычисления, особенно в более высоких измерениях.
Поскольку K-means использует евклидову метрику расстояния, предполагается, что размеры сопоставимы и имеют одинаковый вес. Таким образом, если измерение X имеет единицы миль в час, варьируясь от 0 до 80, а измерение Y имеет единицы фунтов, варьирующиеся от 0 до 400, и вы помещаете окружности в это пространство XY, то одно измерение (и его разброс) будет более мощным, чем другое измерение, и затмит результаты. Вот почему принято нормализовать данные при приеме К-средних.
И GMM, и K-средства моделируют данные, подбирая наилучшие приближения к тому, что дано. GMM подходит для опрокинутых яиц, а K-средство подходит для сферических шариков. Но лежащие в основе данные могут иметь форму чего угодно, это может быть спираль или картина Пикассо, и каждый алгоритм все равно будет работать и делать свой лучший снимок. Насколько итоговая модель будет похожа на фактические данные, зависит от базового физического процесса, генерирующего данные. (Например, измерения задержки являются односторонними; хорошо ли подходит гауссиан? Возможно.)
Таким образом, ваше двоичное изображение 8x8 будет рассматриваться как 64-мерный гиперкуб в первом гиперквадранте. Затем алгоритмы используют геометрические аналогии для поиска кластеров. Расстояние с К-средним показывается как евклидово расстояние в 64-мерном пространстве. Это один из способов сделать это.
источник