Какова связь между кластеризацией k-средних и PCA?

61

Обычной практикой является применение PCA (анализ главных компонентов) перед алгоритмом кластеризации (таким как k-средних). Считается, что это улучшает результаты кластеризации на практике (снижение шума).

Однако я заинтересован в сравнительном и углубленном изучении взаимосвязи между PCA и k-средних. Например, Крис Дин и Сяофэн Хе, 2004, Кластеризация K-средних с помощью анализа главных компонентов, показали, что «главными компонентами являются непрерывные решения индикаторов дискретного членства в кластере для кластеризации K-средних». Однако мне трудно понять эту статью, и Википедия фактически утверждает, что это неправильно .

Кроме того, результаты двух методов несколько различаются в том смысле, что PCA помогает уменьшить количество «функций» при сохранении дисперсии, тогда как кластеризация уменьшает количество «точек данных», суммируя несколько точек по их ожиданиям / средствам. (в случае k-средних). Таким образом, если набор данных состоит из точек, каждый из которых содержит объектов, PCA стремится к сжатию объектов тогда как кластеризация стремится к сжатию точек данных.Т Т НNTTN

Я ищу непрофессиональное объяснение отношений между этими двумя методами + еще несколько технических документов, касающихся этих двух методов.

микрофон
источник
2
Кластеризация также может рассматриваться как сокращение возможностей. Где вы выражаете каждую выборку по назначению кластера, или разреженно кодируете их (поэтому уменьшите до ). Оба этих подхода поддерживают постоянное количество точек данных, уменьшая при этом измерения «характеристик». кTk
Джефф

Ответы:

74

Это правда, что кластеризация K-средних и PCA, по-видимому, имеют совершенно разные цели и на первый взгляд, похоже, не связаны между собой. Однако, как объяснено в статье D-& He 2004 г. Кластеризация K-средних с помощью анализа основных компонентов , между ними существует глубокая связь.

Интуиция заключается в том, что PCA стремится представить все векторов данных в виде линейных комбинаций небольшого числа собственных векторов и делает это для минимизации среднеквадратичной ошибки восстановления. Напротив, K-среднее стремится представлять все векторов данных через небольшое количество центроидов кластеров, то есть представлять их как линейные комбинации небольшого числа векторов центроидов кластеров, где веса линейных комбинаций должны быть равны нулю, за исключением одного . Это также сделано, чтобы минимизировать среднеквадратичную ошибку реконструкции.n 1nn1

Таким образом, K-средних можно рассматривать как супер разреженный PCA.

То, что делает бумага Ding & He, это сделать эту связь более точной.


К сожалению, статья Ding & He содержит неаккуратные формулировки (в лучшем случае) и может быть легко понята неправильно. Например, может показаться, что Ding & He утверждают, что доказали, что центроиды кластеров решения кластеризации K-средних лежат в -мерном подпространстве PCA:(K1)

Теорема 3.3. Подпространство центроида кластера охватывает первые основные направления [...].K1

Для это будет означать, что проекции на оси PC1 обязательно будут отрицательными для одного кластера и положительными для другого кластера, то есть ось PC2 будет идеально разделять кластеры.K=2

Это либо ошибка, либо неаккуратное написание; в любом случае, буквально это конкретное утверждение является ложным.

Давайте начнем с рассмотрения некоторых игрушечных примеров в 2D для . Я сгенерировал несколько выборок из двух нормальных распределений с одной и той же ковариационной матрицей, но разными способами. Я тогда управлял и K-means и PCA. На следующем рисунке показан график разброса данных выше и те же данные, окрашенные в соответствии с решением K-средних, приведенным ниже. Я также показываю первое основное направление в виде черной линии и центроидов классов, найденных с помощью K-средних с черными крестами. Ось PC2 показана пунктирной черной линией. К-среднее было повторено раз со случайными семенами, чтобы обеспечить сходимость к глобальному оптимуму.100K=2100

PCA против K-средних

Хорошо видно, что, хотя центроиды классов, как правило, довольно близки к первому направлению ПК, они точно не падают на него. Более того, даже несмотря на то, что ось PC2 прекрасно разделяет кластеры на участках 1 и 4, на участках 2 и 3 есть пара точек с обратной стороны.

Таким образом, соглашение между K-means и PCA довольно хорошее, но не точное.

Так что же доказали Дин и Он? Для простоты я рассмотрю только случай . Пусть количество точек, назначенных каждому кластеру, равно и а общее количество точек . Следуя Ding & He, давайте определим вектор индикатора кластера следующим образом: если точки принадлежат кластеру 1, и если он принадлежит кластеру 2. Вектор индикатора кластера имеет единичную длину и является "центрированным", то есть его элементы sum to zero .n 1 n 2 n = n 1 + n 2 qR n q i = K=2n1n2n=n1+n2 qRn iqi=-qi=n2/nn1iqi=n1/nn2q=1qi=0

Ding & He показывают, что функция потерь K-средних (этот алгоритм K-средних минимизирует) может быть эквивалентно переписана как , где - матрица Грама скалярных произведений между всеми точками: , где - матрица данных и - центрированная матрица данных.ki(xiμk)2qGqGn×nG=XcXcXn×2Xc

(Примечание: я использую обозначения и терминологию, которые немного отличаются от их статьи, но которые я нахожу более понятными).

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

Другими словами, K-средних и PCA максимизируют одну и ту же целевую функцию , с той лишь разницей, что у K-средних есть дополнительное «категориальное» ограничение.

Само собой разумеется, что в большинстве случаев решения K-средних (с ограничениями) и PCA (без ограничений) будут довольно близки друг к другу, как мы видели выше при моделировании, но не следует ожидать, что они будут идентичными. Принятие и установка всех его отрицательных элементов равными и всех его положительных элементов в обычно не дают точно .pn1/nn2n2/nn1q

Дин и Он, кажется, хорошо это понимают, потому что они формулируют свою теорему следующим образом:

Теорема 2.2. Для кластеризации K-средних, где , непрерывное решение вектора индикатора кластера является [первым] главным компонентомK=2

Обратите внимание, что слова «непрерывное решение». После доказательства этой теоремы они дополнительно комментируют, что PCA может использоваться для инициализации итераций K-средних, что имеет полный смысл, учитывая, что мы ожидаем, что будет близко к . Но все же нужно выполнять итерации, потому что они не идентичны.qp

Тем не менее, Дин и Хэ продолжили разработку более общего подхода к и в итоге сформулировали теорему 3.3 какK>2

Теорема 3.3. Подпространство центроида кластера охватывает первые основные направления [...].K1

Я не проходил математику в разделе 3, но я полагаю, что эта теорема на самом деле также относится к «непрерывному решению» K-средних, то есть его утверждение должно читаться как «кластерное центроидное пространство непрерывного решения K-средних. натянутый [...] ".

Ding & He, однако, не делают эту важную квалификацию, и, кроме того, напишите в своем резюме, что

Здесь мы доказываем, что главными компонентами являются непрерывные решения индикаторов дискретности кластеров для K-средних. Эквивалентно, мы показываем, что подпространство, охватываемое центроидами кластера, задается спектральным расширением ковариационной матрицы данных, усеченной в терминах .K1

Первое предложение абсолютно правильно, а второе - нет. Мне не ясно, является ли это (очень) неаккуратным письмом или подлинной ошибкой. Я очень вежливо послал по электронной почте обоим авторам, просящим разъяснения. (Обновление два месяца спустя: я никогда не получал ответ от них.)


Matlab симуляционный код

figure('Position', [100 100 1200 600])

n = 50;
Sigma = [2 1.8; 1.8 2];

for i=1:4
    means = [0 0; i*2 0];

    rng(42)
    X = [bsxfun(@plus, means(1,:), randn(n,2) * chol(Sigma)); ...
         bsxfun(@plus, means(2,:), randn(n,2) * chol(Sigma))];
    X = bsxfun(@minus, X, mean(X));
    [U,S,V] = svd(X,0);
    [ind, centroids] = kmeans(X,2, 'Replicates', 100);

    subplot(2,4,i)
    scatter(X(:,1), X(:,2), [], [0 0 0])

    subplot(2,4,i+4)
    hold on
    scatter(X(ind==1,1), X(ind==1,2), [], [1 0 0])
    scatter(X(ind==2,1), X(ind==2,2), [], [0 0 1])
    plot([-1 1]*10*V(1,1), [-1 1]*10*V(2,1), 'k', 'LineWidth', 2)
    plot(centroids(1,1), centroids(1,2), 'w+', 'MarkerSize', 15, 'LineWidth', 4)
    plot(centroids(1,1), centroids(1,2), 'k+', 'MarkerSize', 10, 'LineWidth', 2)
    plot(centroids(2,1), centroids(2,2), 'w+', 'MarkerSize', 15, 'LineWidth', 4)
    plot(centroids(2,1), centroids(2,2), 'k+', 'MarkerSize', 10, 'LineWidth', 2)

    plot([-1 1]*5*V(1,2), [-1 1]*5*V(2,2), 'k--')
end

for i=1:8
    subplot(2,4,i)
    axis([-8 8 -8 8])
    axis square
    set(gca,'xtick',[],'ytick',[])
end    
амеба говорит восстановить монику
источник
2
Я только что заглянул в газету Ding & He. В теореме 2.2 они утверждают, что если вы выполните k-среднее (с k = 2) некоторого p-мерного облака данных, а также выполните PCA (на основе ковариаций) данных, то все точки, принадлежащие кластеру A, будут отрицательными, и все баллы, относящиеся к кластеру B, будут положительными, на баллах ПК1. Интересное утверждение, - оно должно быть проверено в симуляциях. Проблема, однако, в том, что она предполагает глобально оптимальное решение K-средних, я думаю; но как мы узнаем, была ли достигнутая кластеризация оптимальной?
ttnphns
1
@ttnphns, я обновил симуляцию и фигуру, чтобы проверить это утверждение более явно. Если проекции на PC1 должны быть положительными и отрицательными для классов A и B, это означает, что ось PC2 должна служить границей между ними. Это очень близко к случаю в моих 4 игрушечных симуляциях, но в примерах 2 и 3 есть пара моментов на обратной стороне PC2. Что касается конвергенции, я запустил kmeansфункцию с 100 повторениями: она каждый раз выбирает различную случайную инициализацию, а затем выбирает лучшее решение, поэтому следует надеяться, что будет достигнут глобальный оптимум.
говорит амеба: восстанови Монику
1
@ttnphns: Думаю, я понял, что происходит, пожалуйста, смотрите мое обновление.
говорит амеба: восстанови монику
амеба, спасибо, что усвоили обсуждаемую статью для всех нас и за то, что сделали свои выводы (+2); и за то, что дали мне знать лично! Я вернусь через пару дней, чтобы прочитать и изучить ваш ответ. Но оцениваю это уже сейчас.
ttnphns
1
Выдающийся пост. Есть ли причина, по которой вы использовали Matlab, а не R? Просто любопытно, потому что я беру курс ML Coursera, а Эндрю Нг также использует Matlab, в отличие от R или Python. Это общий выбор ОД?
Антони Пареллада
10

PCA и K-средства делают разные вещи.

PCA используется для уменьшения размерности / выбора признаков / обучения представлению, например, когда пространство признаков содержит слишком много ненужных или избыточных функций. Цель состоит в том, чтобы найти внутреннюю размерность данных.

Вот двумерный пример, который можно обобщить на пространства более высоких измерений. Набор данных имеет две особенности: и , каждый кружок является точкой данных.xy

введите описание изображения здесь

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

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

На изображении ниже набор данных имеет три измерения. Из трехмерного графика слева видно, что размер можно «отбросить» без потери большого количества информации. PCA используется для проецирования данных в два измерения. На рисунке слева также показана проекционная плоскость. Затем можно использовать K-средства на проецируемых данных для маркировки различных групп, на рисунке справа, закодированных разными цветами.X

введите описание изображения здесь

PCA или другие методы уменьшения размерности используются до как неконтролируемых, так и контролируемых методов в машинном обучении. В дополнение к причинам, изложенным вами и тем, что я упомянул выше, он также используется для целей визуализации (проекция в 2D или 3D из более высоких измерений).

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

«PCA нацелена на сжатие функций T, тогда как кластеризация нацелена на сжатие N точек данных».

Действительно, сжатие - это интуитивно понятный способ думать о PCA. Однако в K-означает, что для описания каждой точки относительно ее кластера вам все равно нужно по крайней мере такое же количество информации (например, размеры) , где - это расстояние, а хранится вместо . И вам также нужно сохранить чтобы знать, к чему относится дельта. Вы можете, конечно , магазин и , однако , вы не сможете получить актуальную информацию в данных.xi=d(μi,δi)dδixiμidi

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

сюрикен х синий
источник
3
То, как ваши ПК помечены на графике, кажется несовместимым с соответствующим обсуждением в тексте. Обратите внимание, что, хотя PCA обычно применяется к столбцам, & k-означает для строк, оба могут применяться к любому из них. Я не читал газету, но держу пари, об этом они и говорят.
gung - Восстановить Монику
Извините, я имел в виду верхнюю цифру: v1 и v2 для ПК.
gung - Восстановить Монику
Хорошая мысль, может быть полезно (не могу понять зачем) сжимать группы точек данных. Найти группы, используя k-means, сжимать записи в меньшее количество, используя pca. Что касается группировки функций, это может быть полезно.
сюрикен х синий
2
Так вы говорите, что газета не права? В нем четко говорится (см. 3-е и 4-е предложения в аннотации) и утверждается, что математически доказано, что существует определенная связь, тогда как вы говорите, что связи нет.
говорит амеба, восстанови Монику
Что я получил от этого: PCA улучшает кластерные решения K-средних. Связь заключается в том, что структура кластера встроена в первые K - 1 главных компонентов. Это вклад.
сюрикен х синий
7

Обычно отбеливают данные перед использованием k-средних. Причина в том, что k-means чрезвычайно чувствителен к масштабу, а когда у вас смешанные атрибуты, «истинного» масштаба больше нет. Затем вы должны нормализовать, стандартизировать или отбелить ваши данные. Ни один из них не идеален, но отбеливание устранит глобальную корреляцию, которая иногда может дать лучшие результаты. PCA / отбеливание - так как вы работаете с ковариационной матрицей.O(nd2+d3)

Насколько я понимаю, отношение k-средних к PCA не соответствует исходным данным . Он заключается в использовании PCA на матрице расстояний (которая имеет записей, и, таким образом, полное PCA составляет - то есть непомерно дорого, в частности по сравнению с k-средних, которые где - единственный большой член), и, возможно, только для . K-среднее - это задача оптимизации методом наименьших квадратов, как и PCA. k-means пытается найти раздел наименьших квадратов данных. PCA находит вектор принадлежности кластера наименьших квадратов.n2O(n2d+n3)O(knid)nk=2

Первый собственный вектор имеет наибольшую дисперсию, поэтому расщепление по этому вектору (которое напоминает принадлежность кластера, а не координаты входных данных!) Означает максимизацию дисперсии кластера . Максимизируя дисперсию кластера, вы также минимизируете дисперсию внутри кластера.

Но для реальных проблем это бесполезно. Это только теоретический интерес.

Anony-Мус
источник
2
Было бы здорово увидеть более подробное объяснение / обзор статьи Ding & He (с которой связан OP). Я сам не знаком с ним (пока), но видел, что он упоминал достаточно раз, чтобы быть довольно любопытным.
говорит амеба, восстанови Монику
3
Вы имеете в виду это ? Да, я тоже сталкивался с этим; Я думаю, что это только добавляет моей путаницы. Я надеялся, что это будет та нить, которая могла бы прояснить это для меня ... Теперь, когда я думаю об этом, возможно, я должен вознаградить за это. Я не думаю, что у меня будет время в следующие дни, чтобы изучить эту тему самостоятельно.
говорит амеба: восстанови Монику
3
Этот абзац вики очень странный. В нем говорится, что Ding & He (2001/2004) был не прав, и это не новый результат! Чтобы продемонстрировать, что это не ново, он приводит статью 2004 года (?!). Чтобы продемонстрировать, что это было неправильно, он приводит новую статью 2014 года, в которой даже не упоминается Ding & He. Подозрительное.
говорит амеба, восстанови Монику
3
Может быть, цитата спама снова. Википедия полна саморекламы.
Anony-Mousse
1
Я думаю, я понял, что происходит в Дин и Хэ, пожалуйста, посмотрите мой ответ. Кроме того, ваш аргумент об алгоритмической сложности не совсем корректен, потому что вы сравниваете полное разложение по собственным векторам матрицы с извлечением только K-средних «компонентов». Это не честное сравнение. Если вы используете какой-то итерационный алгоритм для PCA и извлекаете только компонентов, то я ожидаю, что он будет работать так же быстро, как K-means. Так что я не уверен, что правильно говорить, что это бесполезно для реальных задач и имеет только теоретический интерес. n×nkk
говорит амеба: восстанови монику
4

Решение k-средних в приближении O (k / epsilon) низкого ранга (т. Е. Проекция на диапазон первых по величине сингулярных векторов, как в PCA) даст (1 + эпсилон) приближение в терминах мультипликативной ошибки.

В частности, проецирование на k-самый большой вектор даст 2-аппроксимацию.

Фактически, сумма квадратов расстояний для ЛЮБОГО множества k центров может быть аппроксимирована этой проекцией. Затем мы можем вычислить базовый набор на сокращенных данных, чтобы уменьшить входные данные до поли (k / eps) точек, которые приближаются к этой сумме.

См .: Дэн Фельдман, Мелани Шмидт, Кристиан Солер: Превращение больших данных в крошечные данные: наборы ядер постоянного размера для k-средних, PCA и проективной кластеризации. СОДА 2013: 1434-1453

Дэн Фельдман
источник
3

Интуитивные отношения PCA и KMeans

  1. Теоретически анализ измерений PCA (первое измерение K сохраняет, скажем, 90% дисперсии ... не обязательно иметь прямую связь с кластером K Means), однако ценность использования PCA пришла из а) практического рассмотрения, учитывая природу объектов, которые мы анализируем тенденцию естественным образом объединяться вокруг (или сегмента) их основных компонентов (возраст, пол и т. д.) b / эволюционировать b) PCA устраняет эти низкие дисперсионные измерения (шум), поэтому сама добавляет ценность (и формирует ощущение, подобное кластеризации ) сосредоточив внимание на этом ключевом измерении. Проще говоря, это то же самое, что ось XY - это то, что помогает нам овладеть любой абстрактной математической концепцией, но более продвинутым образом.

  2. K означает попытку минимизировать общее расстояние внутри кластера для данного K

  3. Для набора объектов с N параметрами измерения по умолчанию аналогичные объекты будут иметь параметры MOST «схожими», за исключением нескольких ключевых отличий (например, группа молодых ИТ-студентов, молодых танцоров, людей… будет иметь некоторые очень похожие функции (низкая дисперсия) но некоторые ключевые характеристики все еще довольно разнообразны, и захват этих «ключевых основных компонентов», по существу, отражает большинство различий, например, цвет, область проживания…. Отсюда низкий уровень искажений, если мы пренебрегаем этими признаками незначительных различий или преобразованием в нижние ПК не потеряют много информации
  4. Таким образом, «очень вероятно» и «очень естественно», что их объединение для анализа различий (вариаций) имеет смысл для оценки данных (например, если вы проводите 1000 опросов в неделю на главной улице, группируя их по этническим группам). , возраст или уровень образования в качестве ПК имеют смысл) В рамках миссии K Means мы пытаемся установить достаточное количество K, чтобы эти элементы группы (в кластере) имели наименьшее общее расстояние (минимизированное) между Centroid и в то же время стоимостью установка и запуск K-кластеров оптимальны (каждый член кластера не имеет смысла, так как это слишком дорого для обслуживания и не имеет никакой ценности)
  5. K Означает, что группировка может быть легко «визуально проверена», чтобы быть оптимальной, если такая K относится к основным компонентам (например, если для людей разного возраста, этнических / религиозных групп они склонны выражать сходные мнения, поэтому, если вы группируете эти опросы на основе те ПК, которые достигают цели минимизации (ссылка 1). Также эти ПК (этнические, возрастные, религиозные ...) довольно часто являются ортогональными, следовательно, визуально различимы при просмотре PCA.
  6. Однако этот интуитивный вывод приводит к достаточному, но не обязательному условию. (Ссылка 2: Тем не менее, то, что PCA представляет собой полезное ослабление кластеризации k-средних, не было новым результатом (см., Например, [35]), и довольно просто обнаружить контрпримеры к утверждению о том, что подпространство центроида кластера охватывает по основным направлениям. [36])

Выбор кластеров на основе / вдоль CP может удобно привести к удобному механизму распределения

Этот пример может быть примером, если x - первый ПК вдоль оси X: (........... CC1 ............... CC2 ..... ....... CC3 X ось), где ось X, скажем, захватить более 9X% дисперсии и, скажем, единственный компьютер

6. Наконец, PCA также используется для визуализации после того, как сделано K-средство (ссылка 4).

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

(* поскольку по определению PCA обнаруживает / отображает эти основные измерения (от 1D до 3D), такие, что, скажем, K (PCA) будет охватывать, вероятно, подавляющее большинство дисперсии.

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

Ссылка:

  1. https://msdn.microsoft.com/en-us/library/azure/dn905944.aspx
  2. https://en.wikipedia.org/wiki/Principal_component_analysis
  3. КЛАСТЕРИЗАЦИЯ С ИСПОЛЬЗОВАНИЕМ ОСНОВНОГО АНАЛИЗА КОМПОНЕНТОВ: ПРИМЕНЕНИЕ ПОЖИЛЫХ ЛЮДЕЙ С АВТОНОМНОЙ ИНВАЛИДНОСТЬЮ (Combes & Azema)
  4. http://cs229.stanford.edu/notes/cs229-notes10.pdf Эндрю Нг
г пун
источник