Кластеризация k-means с расстоянием Евклида и Махаланобиса

[egens]

А каким образом выбиралась матрица ковариации для метрики махаланобиса?

[mephistopheies]

просто по определению матрицы ковариации, почитать можно тут www.machinelearning.ru/wiki/index.php?title=Ковариационная_матрица ну или в википедии, там все на самом деле просто. элементы матрицы это попарная ковариация величин

код простой, если интересно могу выложить в коммент

[DenXX]

Т.е. для всей выборки целиком? А если кластеры под разными углами? И наверняка какой-нибудь spectral clustering дал бы сразу хороший результат.
И это у вас не бинарный ли признак разделил выборку на два кластера?

[mephistopheies]

Т.е. для всей выборки целиком?

ага

А если кластеры под разными углами?

ничего страшного, все сработает. я тут вот описывал природу каминса и предположения которые лежат в его основе. так что просто будет построен гауссиан для кластера.

И наверняка какой-нибудь spectral clustering дал бы сразу хороший результат.

наверняка, я не пробовал. я обычно иду от простого к сложному.

И это у вас не бинарный ли признак разделил выборку на два кластера?

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

[DenXX]

Наверное, если кластеры под разными углами, а ковариационная матрица оценивается по всей выборке, то она уже не будет так хорошо описывать эллипсы самих кластеров и возможно та же проблема, как с классическим k-means в вашем случае.
Кластеры выглядят настолько похоже, что кажется, что один — это сдвинутая версия другого. Ясно, что в исходном пространестве они тоже разделялись. Так вот может быть среди 12 ваших исходных признаков есть бинарный, который и разделяет данные на два кластера?..

[egens]

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

+1, задавая вопрос, думал именно об этом.
Будет косяк даже если например в приведенном примере расстояние между кластерами будет больше, чем 'длина' кластеров.

[egens]

И еще — если я правильно понимаю, классический k-means с евклидовой метрикой должен в половине случаев — когда начальные точки выбираются из разных кластеров, — выдавать верный результат. В остальной половине скатываться к локальному минимуму — типа приведенного вами. Для любой метрики можно придумать 'неуиноуные' наборы данных. По-моему лучше раз десять прогнать на данных обычный евклидовый k-means и выбрать превалирующий вариант кластеризации.

[mephistopheies]

ага с каминсом есть смысл прогонять различные инициализации и по функции стоимости разбиения смотреть более лучшее. ну и конечно инициализировать можно по разному.

[mephistopheies]

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

на счет повернутого кластера вопрос интересный, на днях попробую протестить это, а то самому стало сильно интересно =)

про бинарный признак отвечу завтра

[xiWera]

мда… повернул по оси, и вот тебе четкая кластеризация данной двухмерной выборки…

[mephistopheies]

а?

[xiWera]

Еще разжевывать надо?! :-O
Поворот данной двухмерной выборки в удобную сторону, например против часовой на 30 градусов (на глазок) упростит разбиение на две группы до простого
if ( x< C ) { group = 0 }else{ group= 1 };
Геометрический поворот то надеюсь трудности не составит?

[mephistopheies]

лол, ок

[xiWera]

Мдас… А меж тем если есть такие простые способы отобразить пространство выборки на другое более удобное пространство, лучше и проще использовать их. При таких-то данных у вас с большой вероятностью и оставшиеся 10 размерностей тоже отображаются легко.

[egens]

Вы забываете, что при вашем способе отображать в новое пространство придется каждую новую точку — таким образом ничего в скорости вы не выйграете, а может быть даже и проиграете.

[xiWera]

А вы не забываете что к-средних вообщето гораздо медленнее простого поворота всего набора, так как делает кучу сравнений?

[egens]

Я говорю не про обучение классификатора, а про его дальнейшее использование.

[xiWera]

А в дальнейшем использовании :)
что предлагает автор — проверить попадание в эллипс, что предлагаю я — вычислить ОДНУ из координат точки после поворота. Вычисление одной координаты — два умножения и сложение :)

[egens]

к-средние будут проверять не попадание в эллипс, а сравнивать два расстояния до центральных точек кластеров. не все так очевидно.

[xiWera]

В данной статье предложенное «расстояние» суть попадание в эллипс

[xiWera]

ru.wikipedia.org/wiki/%D0%E0%F1%F1%F2%EE%FF%ED%E8%E5_%CC%E0%F5%E0%EB%E0%ED%EE%E1%E8%F1%E0

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

Суть того что сделал автор в данном посте — поехал в париж через Владивосток. Всю плоскость повернули — и вуаля: сделали тоже самое. При этом 1) не было никакого к-средних (лишнего шага, для миллионной выборки он довольно затратен) 2) не было никаких громоздких вычислений расстояний

Мне вообще непонятно зачем было визуализировать данные (то есть сделать что-то, чтобы человеку было проще понять как они сгруппированы), а потом эту понятую человеком группировку взять и попытаться решить не человеком а подгонкой параметров к уже имеющемуся алгоритму…

[ererer]

Такие очевидно линейно разделимые выборки логичней делить чем-то линейным, специально для этого придуманным. Персептроном, например, логистической регрессией или, для эстетов, support vector machine.
Ну а про Густафсона-Кесселя для эллипсов мы, кажется, говорили уже.

[ererer]

Да, и на случай, если вы подумали, что я целенаправленно злобно критикую ваши статьи, заверяю, что каждую из них плюсанул =) Потому что методы методами, но успешно и наглядно решённую задачу всегда приятно видеть.
Однако, о хорошем говорить скучно =)

[mephistopheies]

критика это самое збс -) в споре рождается истина -)

[bazzilic]

Да, первое что приходит в голову при взгляде на картинку — SVM, как-то k-means выглядит здесь не к месту.

[DenXX]

SVM — это алгоритм обучения по размеченой выборке. У автора классы и эти два облака практически не связаны (классы, как я понял, синие и красные точки). Так что, чтобы SVM разделил их, надо сначала разметить какую-нить выборку.
Но автор так и не ответил, эта кластеризация не есть ли результат наличия бинарного признака?