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

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



    Обработка сырых данных



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

    Визуализация


    Визуализация позволяет наглядно оценить данные, например, можно увидеть, что данные образуют несколько групп, тогда возможно произвести кластеризацию, и обучить классификатор на каждый кластер. Получается простая двухступенчатая гибридная модель, по результату кластеризации строится первый классификатор на несколько классов (кластеров, которые обнаружены алгоритмом кластеризации), а затем для каждого класса/кластера используется свой классификатор для целевого поля. Как мы знаем, алгоритм k-means на вход принимает количество кластеров и разбивает данные на указанное число групп. Вместо того, чтобы перебирать количество кластеров и искать разбиение с наименьшей стоимостью, можно визуализировать данные и увидеть эти группы. Но есть и другая проблема, например, разбив данные по расстоянию Евклида, мы можем получить очень неявные границы кластеров, они будут очень близко друг к другу, и тем самым точность системы в целом уменьшается.

    Итак, я приступаю к визуализации, но, правда, визуализаировать 12-мерное пространство не очень просто, так что мне нужно уменьшить размерность до 3 или 2. Я для начала выбираю два, т.к. это проще. Для уменьшения размерности я использую метод главных компонент, кстати ту самую реализацию, описанную в позапрошлой статье.

    В итоге я получил такую картинку:



    Синие и красные точки — это как раз два класса, образованные целевым полем.

    Кластеризация


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

    Вот как выглядит кластеризация с Евклидовой метрикой:



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

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

    Вот результат такой кластеризации:



    Профит


    Пока не ясно профит или нет, но кластеризация дала мне две четкие группы данных, и теперь можно строить первую ступень модели. Или работать с каждым из кластеров, как с отдельной задачей. Далее, для каждой группы будет обучен классификатор по целевому полю, ну и так далее, но это уже не в рамках этой статьи -)
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 26

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

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

            ага

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

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

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

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

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

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

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

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

                  про бинарный признак отвечу завтра
          0
          мда… повернул по оси, и вот тебе четкая кластеризация данной двухмерной выборки…
            0
            а?
              –1
              Еще разжевывать надо?! :-O
              Поворот данной двухмерной выборки в удобную сторону, например против часовой на 30 градусов (на глазок) упростит разбиение на две группы до простого
              if ( x< C ) { group = 0 }else{ group= 1 };
              Геометрический поворот то надеюсь трудности не составит?
                0
                лол, ок
                  0
                  Мдас… А меж тем если есть такие простые способы отобразить пространство выборки на другое более удобное пространство, лучше и проще использовать их. При таких-то данных у вас с большой вероятностью и оставшиеся 10 размерностей тоже отображаются легко.
                    0
                    Вы забываете, что при вашем способе отображать в новое пространство придется каждую новую точку — таким образом ничего в скорости вы не выйграете, а может быть даже и проиграете.
                      0
                      А вы не забываете что к-средних вообщето гораздо медленнее простого поворота всего набора, так как делает кучу сравнений?
                        0
                        Я говорю не про обучение классификатора, а про его дальнейшее использование.
                          0
                          А в дальнейшем использовании :)
                          что предлагает автор — проверить попадание в эллипс, что предлагаю я — вычислить ОДНУ из координат точки после поворота. Вычисление одной координаты — два умножения и сложение :)
                            0
                            к-средние будут проверять не попадание в эллипс, а сравнивать два расстояния до центральных точек кластеров. не все так очевидно.
                              –1
                              В данной статье предложенное «расстояние» суть попадание в эллипс
                                0
                                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) не было никаких громоздких вычислений расстояний

                                Мне вообще непонятно зачем было визуализировать данные (то есть сделать что-то, чтобы человеку было проще понять как они сгруппированы), а потом эту понятую человеком группировку взять и попытаться решить не человеком а подгонкой параметров к уже имеющемуся алгоритму…
              0
              Такие очевидно линейно разделимые выборки логичней делить чем-то линейным, специально для этого придуманным. Персептроном, например, логистической регрессией или, для эстетов, support vector machine.
              Ну а про Густафсона-Кесселя для эллипсов мы, кажется, говорили уже.
                0
                Да, и на случай, если вы подумали, что я целенаправленно злобно критикую ваши статьи, заверяю, что каждую из них плюсанул =) Потому что методы методами, но успешно и наглядно решённую задачу всегда приятно видеть.
                Однако, о хорошем говорить скучно =)
                  +1
                  критика это самое збс -) в споре рождается истина -)
                  0
                  Да, первое что приходит в голову при взгляде на картинку — SVM, как-то k-means выглядит здесь не к месту.
                    0
                    SVM — это алгоритм обучения по размеченой выборке. У автора классы и эти два облака практически не связаны (классы, как я понял, синие и красные точки). Так что, чтобы SVM разделил их, надо сначала разметить какую-нить выборку.
                    Но автор так и не ответил, эта кластеризация не есть ли результат наличия бинарного признака?

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое