Я хочу объединить массивный набор данных, для которого у меня есть только попарные расстояния. Я реализовал алгоритм k-medoids, но его запуск занимает слишком много времени, поэтому я хотел бы начать с уменьшения масштабов моей проблемы путем применения PCA. Тем не менее, единственный способ, которым я знаю, чтобы выполнить этот метод, это использовать ковариационную матрицу, которой у меня нет в моей ситуации.
Есть ли способ применить PCA, зная только парные расстояния?
pca
dimensionality-reduction
multidimensional-scaling
большое дерево
источник
источник
Ответы:
Обновление: я полностью удалил свой первоначальный ответ, потому что он был основан на путанице между евклидовыми расстояниями и скалярными произведениями. Это новая версия моего ответа. Извиняюсь.
Если под попарными расстояниями вы подразумеваете евклидовы расстояния, то да, есть способ выполнить PCA и найти основные компоненты. Я описываю алгоритм в своем ответе на следующий вопрос: в чем разница между анализом главных компонентов и многомерным масштабированием?
Очень кратко, матрица евклидовых расстояний может быть преобразована в центрированную матрицу Грама, которая может быть непосредственно использована для выполнения PCA посредством собственного разложения. Эта процедура известна как [классическое] многомерное масштабирование (MDS) .
Если ваши попарные расстояния не являются евклидовыми, то вы не можете выполнить PCA, но все равно можете выполнить MDS, который больше не будет эквивалентен PCA. Тем не менее, в этой ситуации MDS, вероятно, будет еще лучше для ваших целей.
источник
PCA с матрицей расстояний существует и называется многомерным масштабированием (MDS). Вы можете узнать больше в Википедии или в этой книге .
Вы можете сделать это
Rс помощью функции MDScmdscale. Для примераxвы можете проверить этоprcomp(x)иcmdscale(dist(x))дать тот же результат (гдеprcompPCA иdistпросто вычисляет евклидовы расстояния между элементами x)источник
Это похоже на проблему, к которой может быть применена спектральная кластеризация. Поскольку у вас есть матрица попарных расстояний, вы можете определить полностью связанный граф, в котором каждый узел имеет N соединений, что соответствует его расстоянию от любого другого узла в графе. Исходя из этого, вы можете вычислить лапласианский график (если это звучит страшно, не беспокойтесь - это простое вычисление), а затем взять собственные векторы наименьшегоСобственные значения (в этом отличие от PCA). Например, если вы возьмете 3 собственных вектора, у вас будет матрица Nx3. В этом пространстве точки (надеюсь) должны быть хорошо разделены из-за некоторой теории аккуратных графов, которая предполагает, что это оптимальный отрезок для максимизации потока (или расстояния, в данном случае) между кластерами. Оттуда вы можете использовать k-средних или аналогичный алгоритм для кластеризации в 3-пространстве. Я рекомендую проверить это удивительное прохождение для большего понимания:
http://arxiv.org/abs/0711.0189
источник
Попарные расстояния также образуют квадратную матрицу, как матрицу ковариации. PCA - это просто SVD ( http://en.wikipedia.org/wiki/Singular_value_decomposition ), применяемый к ковариационной матрице. Вы все еще должны быть в состоянии уменьшить размерность, используя SVD для ваших данных. Я не совсем уверен, как интерпретировать ваш вывод, но это определенно что-то попробовать. Вы можете использовать методы кластеризации, такие как k-means или иерархическая кластеризация. Также обратите внимание на другие методы уменьшения размеров, такие как многомерное масштабирование. Что вы пытаетесь выбраться из своих кластеров?
источник