29.07.2019 10:23
vladshow 24 2900 Источник

В работе предлагается новый метод кластерного анализа. Его преимущество в менее сложном с вычислительной точки зрения алгоритме. Метод основан на расчете голосов за то, что пара объектов находится в одном классе из информации о значении отдельных координат.

Введение


Большой потребностью анализа данных является разработка эффективных методов классификации. В таких методах требуется разделить все множество объектов на оптимальное число классов, основываясь только на информации о значении отдельных показателей [Загоруйко 1999].

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

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

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

Метод k-средних


Метод k-средних является одним из наиболее популярных методов кластеризации. Его целью является получение таких центров данных, которые бы соответствовали бы гипотезе компактности классов данных при их симметричном радиальном распределении. Одним из способов определить положения таких центров, при заданном их количестве \textit{k}, является EM подход.

В данном методе выполняется последовательно две процедуры.

  1. Определение для каждого объекта данных $inline$X_{i}$inline$ ближайшего центра $inline$C_{j}$inline$, и назначение данному объекту метки класса $inline$X_{i}^{j} $inline$. Далее для всех объектов становится определена их принадлежность различным классам.
  2. Вычисление нового положения центров всех классов.

Итеративно повторяя эти две процедуры из начального случайного положения центров \textit{k} классов, можно добиться разделения объектов на классы, которые бы максимально бы соответствовали гипотезе радиальной компактности классов.

С методом k-средних будет сравниваться новый авторский алгоритм классификации.

Новый метод


Новый алгоритм кластерного анализа построен на базе голосов за принадлежность различным кластерам из информации о значений отдельных координат точек данных.

  1. Задается величина d, характеризующая длину интервала показателей, в пределах которого два объекта считаются принадлежащими одному классу.
  2. Выбирается показатель $inline$x_{i}$inline$ и рассматриваются все пары объектов $inline$\left\{O_{l} ,O_{k} \right\}$inline$, где $inline$l,k=1\ldots N$inline$.
  3. Если $inline$\left|x_{i}^{l} -x_{i}^{k} \right|\le d$inline$, то величине $inline$r_{lk} :=r_{lk} +1$inline$ (прибавляется голос).
  4. Действия 2) и 3) повторяются для всех показателей $inline$i=1\ldots M$inline$.
  5. Задается величина p, характеризующая минимальное количество голосов, за принадлежность одинаковым классам.
  6. Методом ключей пар значений определяются все классы объектов, таких что в пределах одного класса голоса за пары объектов из этих классов >=p.
  7. Перебираются все значения d и p и повторяются пункты 1) — 6) для получения количества классов ближайшее к заданному числу классов g.

Чтобы снизить сложность алгоритма до N, можно использовать T интервалов для отдельных показателей и пункт 2) и 3) в алгоритме заменить на следующие:

1. Выбирается показатель $inline$x_{i}$inline$ и рассматриваются все интервалы $inline$\left[u_{l} ,w_{l} \right]$inline$, где $inline$l=1\ldots T$inline$:

$$display$$u_{0} =\min (x_{i} );u_{0} =\min (x_{i} );$$display$$


$$display$$w_{T} =\max (x_{i} );$$display$$


$$display$$s_{i} =w_{T} -u_{0} ;$$display$$


$$display$$u_{l} =u_{0} +l\cdot s_{i} ;$$display$$


$$display$$w_{l} =u_{l} +d;$$display$$



2. Если $inline$x_{i}^{k} \in \left[u_{j} ,w_{j} \right]$inline$ и $inline$x_{i}^{l} \in \left[u_{j} ,w_{j} \right]$inline$, где $inline$j=1\ldots T$inline$, то величине $inline$r_{lk} :=r_{lk} +1$inline$ (прибавляется голос при уникальном ключе l, k для i-го показателя).

Численный эксперимент


В качестве исходных данных были взяты данные, с интуитивно понятной человеку классификацией.

На рисунках 1 и 2 приведены результаты классификации метода k-средних и нового метода классификации.


Рис. 1. Проекция 1-2 и классификация данных.

Слева метод k-средних, справа авторский метод.


Рис. 2. Проекция 2-3 и классификация данных.

Слева метод k-средних, справа авторский метод.

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

Программная реализация


Метод кластеризации k-средних был реализован программно как web приложение. Вычислительная часть приложения вынесена на сервер написанном на языке PHP c использованием фреймворка Zend. Интерфейс приложения написан с использованием HTML, CSS, JavaScript, JQuery. Приложение доступно по адресу http://svlaboratory.org/application/klaster2 после регистрации нового пользователя. Приложение позволяет визуализировать принадлежность объектов различным кластерам в заданной плоскости координат.

Заключение


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

Список литературы (References)

  1. Загоруйко Н.Г. Прикладные методы анализа данных и знаний. Новосибирск: Изд-во Ин-та математики, 1999. 270 с.
  2. Загоруйко Н.Г., Борисова И.А., Кутненко О.А., Леванов Д.А. Обнаружение закономерностей в массивах экспериментальных данных // Вычислительные технологии. ? 2013. Т. 18. № S1. С. 12-20.
  3. Shen Furaoa, Tomotaka Ogurab, Osamu Hasegawab An enhanced self-organizing incremental neural network for online unsupervised learning. Hasegawa Lab, 2007.

Комментарии (24)


  1. prostofilya
    29.07.2019 14:01
    #20447311
    +9

    1. Алгоритм подозрительно похож на DBSCAN (sklearn)
    2. Алгоритмов кластеризации гораздо больше, чем один упомянутый k-средних, сравнение слабое.
    3. Не уподобляйтесь этим Загоруйковским оборотам, глаза вытекают при чтении:

    на информации о значении отдельных показателей [Загоруйко 1999]

    Вообще был опыт чтения его статей >5 лет назад. Есть статья, придуман там новый сверхсупер метод кластеризации, в n раз круче любого другого. Сжато описан алгоритм, реализация нигде не описана, результата реализации зачастую тоже. Пытался реализовать, но с его терминологией это нереально. Закралось подозрение что там просто клепают статьи.


    1. vladshow Автор
      29.07.2019 17:04
      #20448359

      Этот алгоритм далеко не DBSCAN.
      Спасибо за комментарий.


  1. aamonster
    29.07.2019 15:18
    #20447791
    +1

    Проверьте на устойчивость. На ваших же данных — прибавьте к координатам каждой точки случайные числа.


    Ну и для ваших данных, понятное дело, не подходит k-means — тут нужен какой-то из методов, объединяющих кластеры "по ближайшему соседу", с ними и следовало сравнивать.


    1. vladshow Автор
      29.07.2019 17:06
      #20448369

      Спасибо за комментарий.
      Думаю очевидно что помехи и шум не повлияют на результат.


    1. vladshow Автор
      29.07.2019 18:06
      #20448737

      «По ближайшему соседу» — можете подсказать название и описание такого метода (ссылку) по принципу «обучения без учителя». Т.к. мне известны только такие методы для «обучения с учителем». Когда представлены хотя бы несколько объектов с известными классами.


      1. Bas1l
        30.07.2019 12:30
        #20451863

        Вот тут уже что-то пишут: https://scikit-learn.org/stable/modules/neighbors.html


        1. vladshow Автор
          30.07.2019 22:27
          #20454759

          Спасибо за ссылку. Действительно метод соседей там представлен для данных «без учителя». Но структура алгоритма там другая.


      1. DaylightIsBurning
        31.07.2019 17:12
        #20458337

        Классические примеры — это DBSCAN и OPTICS.


  1. roryorangepants
    29.07.2019 16:24
    #20448145
    +2

    На рисунках 1 и 2 приведены результаты классификации метода k-средних и нового метода классификации.

    Здесь (и везде в других местах) говорить «классификация» некорректно.

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

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

    Нет, не очевидно. Дайте метрики какие-нибудь на пачке стандартных датасетов. Дайте результаты на реальных данных.
    В конце концов, дайте реализацию с каким-нибудь стандартным интерфейсом (похожим на sklearn-овский, например), чтобы люди могли сравнить.

    А то пока звучит как очередное изобретение вечного двигателя.


    1. vladshow Автор
      29.07.2019 17:09
      #20448387
      -5

      Дайте, дайте — попробуйте реализовать сами.


      1. roryorangepants
        29.07.2019 20:02
        #20449209

        Если алгоритм реализован и работает, а не «работает на бумаге», как часто бывает, то в чем проблема поделиться реализацией?
        Отсутствие метрик в статье и сравнение на синтетических данных с сомнительной SotA (k-means для данных такого вида и правда сомнительный, уж простите) выглядит неубедительно.


        1. kommie2050
          29.07.2019 21:23
          #20449517
          +1

          это вроде манхеттенская метрика с трешхолдом

          np.abs(arr_x-arr_y) < d

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

          нихрена. сам метрика примитивна.
          Реализациея на коленке:
          import numpy as np
          import pprint as pp

          arr = np.array([[1,2,3] , [1,3,5] , [1,1,1] , [2,2,2] , [7,7,7]])

          def clasterize_woting(arr,d ):

          objects_amount = len (arr)
          input_dim = len(arr[0])
          #woting_mx = np.zeros((objects_amount,objects_amount))
          woting_mx = {}

          for x in range(objects_amount-1):
          arr_x = arr[x]
          for y in range(x+1,objects_amount):
          arr_y = arr[y]
          wotes = np.sum(np.abs(arr_x-arr_y) < d)
          woting_mx[(x,y)] = wotes
          return woting_mx

          w = clasterize_woting(arr,2)

          pp.pprint(w)
          с результатом:
          {(0, 1): 2,
          (0, 2): 2,
          (0, 3): 3,
          (0, 4): 0,
          (1, 2): 1,
          (1, 3): 2,
          (1, 4): 0,
          (2, 3): 3,
          (2, 4): 0,
          (3, 4): 0}

          объединил сильно ([1,1,1], [2,2,2],[1,2,3]), слабее ([1,3,5]), вообще в стороне [7,7,7]

          почему проблема в метрике, потому что никогда не додумается, что ([1,1,1], [2,2,2], [7,7,7]) могут быть в одном кластере а ([1,2,3], [1,3,5]) в другом


          1. vladshow Автор
            30.07.2019 22:33
            #20454791

            Действительно, этот алгоритм использует гипотезу компактности и не относится к алгоритмам определяющих закономерности.


  1. Rumyantsev
    29.07.2019 20:30
    #20449299

    Посмотрите пожалуйста тут -раздел 2 и тут. Или соотв. оригинальную документацию sklearn описание, но по логике описания похоже на замену схемой голосования параметра d в DBSCAN — должно быть более гибко, но надо проверять т.к. п. 7. алгоритма выглядит вычислительно сложным.


    1. vladshow Автор
      30.07.2019 22:43
      #20454823

      Посмотрел, DBSCAN — это другой алгоритм.


  1. kommie2050
    29.07.2019 21:02
    #20449413

    попробую реализовать подозреваю результаты будут похожие на KNN или коннохена так как основной момент в метрике.
    и кстати количество кластеров может быть (и это имхо лучше) неизвестным


  1. S_A
    30.07.2019 13:02
    #20452071

    Не affinity ли propagation это часом? https://habr.com/ru/post/321216/


    1. vladshow Автор
      30.07.2019 22:55
      #20454875

      Нет, это другой алгоритм.


      1. S_A
        31.07.2019 05:50
        #20455385
        +2

        Джентльмены верят другу другу на слово? У вас какой-то его частный случай походу, так что да… Другой....


        И вообще, заявлений много, а анализа толкового нет. Мне особенно понравилось про сложные топологии :)


        Кстати у задачи кластеризации существуют конкретные метрики, silhoutte score например, а не только "интуитивная отличимость" (на игрушечных датасетах).


        Так что у вас один выход. Сделать python-библиотеку и собрать на гитхабе звёзд больше чем hdbscan (1300+ на данный момент).


        1. vladshow Автор
          31.07.2019 08:16
          #20455529

          «Сделать python-библиотеку» возможно в будущем кто нибудь сделает реализацию на python в качестве библиотеки


  1. CrazyElf
    30.07.2019 13:19
    #20452157

    Не бывает универсально лучших методов кластеризации (по крайней мере сейчас картина такова), иначе их не было бы столько разных вариантов в том же sklearn-е, лучший бы всех заборол, а про остальные бы забыли. ML очень динамичная область, тут всё быстро. Сегодня в регрессии/классификации рулит Ranfom Forest, а завтра уже XGBoost. Но для кластеризации такой «монополизации рынка» мы пока не видим. Для каких-то наборов данных лучше одни методы работают, для каких-то другие. Поэтому, как уже указывали выше, надо сравнивать с другими алгоритмами кластеризации на пачке разных данных, как это опять же сделано в sklearn. Кстати, если визуализировать результаты на одних и тех же данных, сразу будет заодно чисто визуально видно — не является ли предлагаемый метод копией какого-то другого метода, уже реализованного в sklearn. Если он будет давать в точности те же результаты, что и какой-то другой метод, то выводы можно сделать довольно легко.


    1. vladshow Автор
      30.07.2019 23:03
      #20454895
      -2

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


      1. CrazyElf
        31.07.2019 12:00
        #20456523

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


        1. vladshow Автор
          31.07.2019 13:03
          #20456885

          Спасибо за комментарий.