Есть ли случаи, когда не существует оптимального k в k-средних?

Это было в моей голове, по крайней мере, несколько часов. Я пытался найти оптимальное k для вывода из алгоритма k-средних (с метрикой косинусного сходства ), поэтому в итоге я построил график искажения как функции от числа кластеров. Мой набор данных представляет собой коллекцию из 800 документов в 600-мерном пространстве.

Из того, что я понимаю, нахождение точки перегиба или точки колена на этой кривой должно сказать мне, по крайней мере, приблизительно количество кластеров, в которые я должен поместить свои данные. Я поставил график ниже. Точка, в которой была проведена красная вертикальная линия, была получена с использованием теста максимальной второй производной . После всего этого я застрял в чем-то гораздо более простом: что этот график говорит мне о наборе данных?

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

В большинстве ситуаций я бы подумал, что такой график в основном означает, что в данных нет кластерной структуры. Тем не менее, кластеризация в очень больших измерениях, таких как это сложно, так как для евклидовой метрики расстояния все расстояния стремятся к тому же с увеличением числа измерений. См. Эту страницу Википедии для ссылок на некоторые статьи по этой теме. Короче говоря, проблема может заключаться в высокой размерности набора данных.

По сути, это «проклятие размерности», см. Также эту страницу Википедии.

Документ, который может представлять интерес, - Sanguinetti, G., "Уменьшение размерности кластеризованных наборов данных", IEEE. Транзакции по шаблонному анализу и Machine Intelligence, vol. 30 № 3, стр. 535-540, март 2008 ( www ). Это немного похоже на неконтролируемую версию LDA, которая ищет низкоразмерное пространство, которое подчеркивает структуру кластера. Возможно, вы могли бы использовать это как метод извлечения признаков перед выполнением k-средних?

Как именно вы используете косинусное сходство? Это то, что называется сферическими К-средними? Ваш набор данных довольно мал, поэтому я постараюсь представить его как сеть. Для этого естественно использовать сходство (на самом деле, например, косинусное сходство или корреляцию Пирсона), применить отсечение (учитывайте только отношения выше определенного сходства) и просмотреть результат в виде сети, например, в Cytoscape или BioLayout. , Это может быть очень полезно, чтобы почувствовать данные. Во-вторых, я бы рассчитал единичные значения для вашей матрицы данных или собственные значения соответствующим образом преобразованной и нормализованной матрицы (матрица документ-документ, полученная в некоторой форме). Структура кластера должна (снова) отображаться как скачок в упорядоченном списке собственных значений или сингулярных значений.

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

Чтобы получить больше интуиции, вы также можете попробовать другой подход к визуализации: для k-средних вы можете визуализировать несколько прогонов с помощью k-средних с использованием Graphgrams (см. Пакет Graphgram WEKA - лучше всего его получить у менеджера пакетов или здесь . Введение и примеры также могут быть нашел здесь .

Если я правильно понимаю график, то это график количества кластеров, K на оси X и расстояние внутри кластеров на оси Y?

Поскольку вашей целевой функцией K-средних является минимизация WCSS, этот график всегда должен быть монотонно убывающим. Когда вы добавляете больше кластеров, расстояние между точками в кластере всегда будет уменьшаться. Это фундаментальная проблема выбора модели, поэтому вам нужно использовать немного больше изощренности.

Возможно, попробуйте статистику Gap: www-stat.stanford.edu/~tibs/ftp/gap.ps или другие подобные.

Кроме того, вы можете обнаружить, что K-means не является подходящим инструментом для работы. Сколько кластеров вы ожидаете найти? Использование правила дисперсии для уменьшения размерности для кластеризации не подходит. См. Этот документ, чтобы при проецировании на первые ПК K-1 была подходящей мерой предварительной обработки: http://people.csail.mit.edu/gjw/papers/jcss.ps

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