Реализация k-средних с пользовательской матрицей расстояний на входе

14

Может кто-нибудь указать мне реализацию k-средних (было бы лучше, если бы в Matlab), который может принимать матрицу расстояний на входе? Для стандартной реализации Matlab требуется матрица наблюдения на входе, и пользовательское изменение меры подобия невозможно.

clustering matlab k-means Eugenio
источник
2
Вы можете попытаться сгенерировать необработанные данные, соответствующие вашей матрице евклидовых расстояний, и ввести их в K-средние. Альтернативным простым подходом может быть использование метода иерархической кластеризации матрицы Уорда: K-Means и Уорд разделяют схожую идеологию того, что такое кластер.
ttnphns
В дополнение к ttnphns и Not Durrett вы можете найти. Можно ли использовать расстояние Манхэттена с межкластерными связями Уорда в иерархической кластеризации? интересно
Штеффен
Не Matlab, но страница python в разделе « возможно, чтобы указать свою собственную функцию расстояния с помощью scikits-learn-k-means» может использовать любую из 20 с лишним метрик в scipy.spatial. расстояние.
Денис

Ответы:

13

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

Вместо этого вы можете попробовать k-medoids . Есть несколько доступных реализаций Matlab .

NF
источник
1
Привет, спасибо за ответ; вместо того, чтобы непосредственно давать матрицу расстояний, можно ли было бы ввести в качестве входных данных собственную метрику расстояния? Дело в том, что мне нужно сравнить два метода кластеризации, и, поскольку во втором я использую пользовательскую матрицу сходства, я хочу использовать тот же подход с kmeans, чтобы получить справедливое сравнение.
Эудженио
2
ELKI позволяет использовать произвольные функции расстояния с помощью k-средних. Обратите внимание, что алгоритм может не сойтись. K-means действительно рассчитан на квадрат евклидова расстояния (сумма квадратов). При других расстояниях среднее может больше не оптимизироваться, и бум, алгоритм в конечном итоге не будет сходиться. Серьезно, рассмотрите возможность использования k-medoids. На самом деле это было написано, чтобы позволить использовать идею k-средних с произвольными расстояниями.
ВЫЙТИ - Anony-Mousse
Существует также пикластеризация библиотеки python / C ++, которая позволяет вам предоставлять пользовательскую метрическую функцию: github.com/annoviko/pyclustering/issues/417
CpILL
7

Вы можете превратить свою матрицу расстояний в необработанные данные и ввести их в кластеризацию K-Means. Шаги будут следующими:

1) Расстояния между вашими N точками должны быть квадратами евклидова. Выполните « двойное центрирование » матрицы: вычтите среднее значение строки для каждого элемента; в результате столбец вычитания означает от каждого элемента; в результате добавьте среднее значение матрицы для каждого элемента; разделите на минус 2. Теперь у вас есть матрица SSCP (сумма квадратов и кросс-произведение) между вашими точками, в которой начало координат находится в геометрическом центре облака из N точек. (Прочитайте объяснение двойного центрирования здесь .)

2) Выполнить PCA (анализ главных компонентов) на этой матрице и получить матрицу загрузки компонентов NxN . Некоторые из последних столбцов могут быть равны 0, поэтому обрежьте их. То, с чем вы остаетесь сейчас, это на самом деле оценки главных компонентов, координаты ваших N точек на главных компонентах, которые проходят в виде осей через ваше облако. Эти данные могут рассматриваться как необработанные данные, подходящие для ввода K-средних.

PS Если ваши расстояния не являются геометрически правильными квадратами евклидова, вы можете столкнуться с проблемой: матрица SSCP может быть не положительной (полу) определенной. С этой проблемой можно справиться несколькими способами, но с потерей точности.

ttnphns
источник
Спасибо за Ваш ответ! На самом деле у меня нет реальной матрицы расстояний, но есть матрица сходства (0 ... 1) среди объектов, и сходства рассчитываются не точно с использованием евклидовых расстояний, а с помощью специального алгоритма, который учитывает необработанные данные, но не в стандартный способ. Я думаю, в этом случае я не могу применить вашу процедуру, я прав?
Эудженио
Вы все еще можете, после преобразования сходства в расстояния. Последнее, вероятно, не будет истинно евклидовым (и поэтому SSCP будет иметь некоторые отрицательные собственные значения); затем попробуйте добавить небольшую константу к расстояниям, пока SSCP не потеряет отрицание. ГЦОС. Существуют и другие способы обойти проблему. И, пожалуйста, помните, что у вас двойная центральная матрица квадратов расстояний.
ttnphns
PS И кстати. Если ваша матрица схожа, значит, еще лучше. Вы просто рассматриваете это как ту матрицу SSCP, о которой я говорил, и делаете PCA с этим. Тем не менее проблема возможных отрицательных собственных значений остается.
ttnphns
@ttnphns, извини я пропускаю ваше объяснение для шага 1. матрицу расстояний X(скажем , N * N) будет симметричными, так colMeans(X) =rowMeans(X) и как только вы вычитаете строки или Col средства: Y=X-rowMeans(X), mean(Y)0.
Zhubarb
1
@Zhubarb, когда я говорю You could turn your matrix of distances into raw data(пункты 1 и 2), я имею в виду, по существу, многомерное масштабирование (MDS) Торгерсона , в котором двойное центрирование является начальным шагом. Пожалуйста, поищите на этом сайте (и в Google тоже) об этой процедуре. «Двойное центрирование» - это преобразование (возведенных в квадрат) расстояний в соответствующую матрицу скалярных произведений, определенную для начала координат, помещенного в центроид облака точек.
ttnphns
3

Пожалуйста, смотрите эту статью, написанную одним из моих знакомых;)

http://arxiv.org/abs/1304.6899

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

Исходный код можно получить, перейдя по указанной выше ссылке, затем щелкнув «Другие форматы», а затем «Загрузить исходный код». Тогда вы получите .tar.gz, содержащий Program.cs. Кроме того, исходный код также можно скопировать из PDF.

szali
источник
3

Вы можете использовать библиотеку машинного обучения Java. У них есть реализация K-Means. Один из конструкторов принимает три аргумента

  1. К Значение.
  2. Объект этого является экземпляром DistanceMeasure .
  3. Количество итераций.

Можно легко расширить класс DistanceMeasure для достижения желаемого результата. Идея состоит в том, чтобы возвращать значения из пользовательской матрицы расстояний в методе меры (Instance x, Instance y) этого класса.

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

Чайтанья Шиваде
источник