Новый метод кластерного анализа


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

Введение


Большой потребностью анализа данных является разработка эффективных методов классификации. В таких методах требуется разделить все множество объектов на оптимальное число классов, основываясь только на информации о значении отдельных показателей [Загоруйко 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.

Similar posts

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 24

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

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

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


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

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

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

              0
              Спасибо за ссылку. Действительно метод соседей там представлен для данных «без учителя». Но структура алгоритма там другая.
              0
              Классические примеры — это DBSCAN и OPTICS.
            +4
            На рисунках 1 и 2 приведены результаты классификации метода k-средних и нового метода классификации.

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

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

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

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

            А то пока звучит как очередное изобретение вечного двигателя.
              –9
              Дайте, дайте — попробуйте реализовать сами.
                0
                Если алгоритм реализован и работает, а не «работает на бумаге», как часто бывает, то в чем проблема поделиться реализацией?
                Отсутствие метрик в статье и сравнение на синтетических данных с сомнительной SotA (k-means для данных такого вида и правда сомнительный, уж простите) выглядит неубедительно.
                  +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]) в другом

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

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

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

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

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

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


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


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


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

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

                    Only users with full accounts can post comments. Log in, please.