Кластеризация. Алгоритм а-квазиэквивалентности

    Странно, но статей о извлечение знаний (data mining) и кластеризации (как одном из основных инструментом, которие используются для извлечения знаний) на Хабре совсем немного. А если говорить говорить о конкретных алгоритмах, то рассматривались только hard/soft k-means.

    В статье ниже описывается теория и реализация (Python + matplotlib) не очень известного, но крайне интересного иерархического метода который можно назвать алгоритмом а-квазиэквивалентности.


    Извлечения знаний и кластеризация


    К сожалению, чукча не писатель (тем более не русскоязычный), поэтому тем, кто не знаком с терминами в подзаголовке, рекомендую ознакомится с Обзор алгоритмов кластеризации данных и Извлечение данных или знаний? (статьи на родном Хабре) или посмотреть в Вики (1, 2).

    Задание


    Будем разделять и властвовать точки в двухмерном пространстве. Характеристиками точек будут только их координаты. Поскольку метод у нас иерархический, то результатом будет дерево\список возможных делений на кластера.
    Для затравки — пример. Хотим разделить на кластера точки на изображении:

    circle

    Как же должен поделить эти точки ИИ? Посмотрим, что придумает наш алгоритм.

    Теория


    Математика, изложенная ниже, взята из книги А. А. Барсегян, М. С. Куприянов, В. В. Степаненко, И. И. Холод — Методы и модели анализа данных OLAP и Data Mining (если быть точним — глава 7.4. Кластеризация данных при помощи нечетких отношений).

    Большинство алгоритмов кластеризации (будем рассматривать k-means как эталон) для оценки схожести образцов использует расстояние между ними. Довольно логично, но думаем шире — образцы так же похожи, если похожи оценки расстояния от каждого из них ко всем остальным образцам. Что нам это даст? — Мы сможем решить и поставленную задачу, и остальные примеры, с которыми справляется k-means.

    И так, как же реализованная описанная стратегия?
    • Имеем множество X, количество элементов в множестве — Q.
      Построим матрицу оценок расстояний между элементами (назовем эти оценки нормальными мерами сходства) с помощью формулы
      matrix1
      где d(x, y) — расстояние Евклида.
    • Построим относительные меры сходства с помощью формулы
      matrix2
      Полученная трехмерная матрица покажет, насколько похожа пара данных элементов относительно все остальных.

    • Построим матрицу мер сходства элементов множества по формуле
      image
      С трехмерной матрицы получили двухмерную, которая содержит худшие оценки мер сходства для каждой пары точек.
    • Для полученной матрицы R построим её замыкание, используя следующие формулы:
      closure1
      Определение для операции замыкания:
      closure2
      closure3
      В нашем случае S = max, T = min.

    В конце работы алгоритма для четырех точек мы получим матрицу типа
    1 2 3 4
    1 1 0.5 0.3 0.3
    2 0.5 1 0.3 0.3
    3 0.3 0.3 1 0.6
    4 0.3 0.3 0.6 1

    Числа в матрице показывают, принадлежит ли пара точек отношению R, их называют уровнями квазиэквивалентности. Выбор конкретного уровня (a) разбивает множество на классы эквивалентности, которые соответствуют отделенным кластерам. То есть, если мы выберем уровень a = 0.4, то пары (1,4), (2,4), (1,3) и (2,3) уже не будут принадлежать отношению (их уровень альфа меньше, чем заданный). По сути, данную матрицу можно представлять как матрицу графа, и в случае уровня a=0.4 начальный граф разобьется на два — (1, 2) и (3, 4).

    В некоторых научных работах вместе с описанием алгоритма также демонстрируют «блок-схемку»:

    schema

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

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

    Практика


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

    circle3

    Согласитесь, довольно неожиданно, но и в тоже время — логично.
    Ну и для случайных данных:

    rand1

    rand2

    rand3

    Исходный код: алгоритм, рисовалка.
    Код исключительно демонстрационный и не претендует ни на эффективность, ни на соответствие PEP8.

    Заключение


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

    Ссылки:
    — собственно книга, теория из которой использовалась — Методы и модели анализа данных OLAP и Data Mining;
    — еще одна книга по data mining от тех же авторов — Технологии анализа данных. Data Mining, Visual Mining, Text Mining, OLAP
    — интереснейшая статья, в которой на похожем примере решается задача классификации — Классификация данных методом опорных векторов.

    Буду признателен за замечания в личку.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

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

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

      –3
      Интересный алгоритм, спасибо.
        –6
        О, Господи! Меня один только заголовок повергает в транс, а сам статья вообще убивает. Понял только одно — это очень круто.
          0
          Крайне интересно.
          Мне приходилось столкнуться с задачей о классификации треков:
          в результате некоторого процесса был дан набор треков вида
          t=0 t=n
          ААBBCCCDDBBBCDDCC
          ABACCBBDDCCCCBBBC
          и т п
          Одни из этих треков описывали состояние процесса «нормального», а другие — испорченного.
          Требовалось найти по некоторому треку, процесс какого вида мог к нему привести.
          Задачу так удовлетворительно и не решили…
          Было бы интересно попробовать примениить для классификации такой или похожий алгоритм.
          В какую область математической статистики тут копать можно было бы?
            0
            Я не уверен, что правильно Вас понял, но при чем здесь матстатистика?

            > процесс какого вида мог к нему привести
            Похоже на предметную область теории конечных автоматов.
            0
            Чем-то похожим я сейчас занимаюсь, только вместо точек у меня фразы, и вычисление «расстояния» между ними — это самая заковыристая штука.
              0
              Делал такое. Вроде ж есть достаточно способов перевести фразу в вектор, а дальше уж сравнивать координаты, хотя бы и как в этой статье.
              +2
              > Построим матрицу оценок расстояний между элементами

              правильно ли я понимаю, что раз этот алгоритм строит матрицу расстояний между каждыми двумя элементами множества, то сложность такого алгоритма — квадратичная? Даже если сделать оптимизацию (матрица симметрична относительно диагонали), то получим (n^2)/2. Плюс вычислеие расстояния между объектами.
              Такой алгоритм годится для относительно небольших данных (ну, скажем, до 50 000 объектов)
                0
                Да, нужно посчитать n*n/2 расстояний. Кроме того, операция свертки может быть довольно дорогой для не дискретных данных.
                0
                Очень интересно. А не разъясните «физический смысл» и назначение в данном алгоритме операции замыкания?
                  0
                  Идея в построение отношения, которое обладает свойством эквивалентности. В книге есть определения теоремы, которая утверждает что отношение эквивалентности разбивает множество на попарно непересекающиеся классы эквивалентных элементов.

                  Я бы с удовольствием интерпретировал это определение, но мои познания с теории множеств не позволяют :)
                    0
                    А, я так и подумал. На мой взгляд, это недостаток — не так уж много реальных задач, в которых классы действительно не пересекаются. Интересно бы попробовать вместо замыкания прикрутить сюда что-нибудь из нечёткой логики, чтобы одна точка могла принадлежать нескольким кластерам одновременно.
                      +1
                      Есть довольно много наработок на тему Fuzzy Clustering'а i.e FLAME clustering
                        0
                        Благодарю покорно, прочёл с интересом. Видимо, наработок всё ещё недостаточно много, поскольку по нечёткой кластеризации у меня на подходе дисер =) Одна из идей, в частности, что на данный момент нет смысла разделять чёткую и нечёткую кластеризацию на уровне алгоритмов. Написать чёткий алгоритм и не обощить его до нечёткого — это сказать а и не сказать б.
                      +1
                      Это хороший пример того, что как некоторые российские математики умеют все запутать, чтобы выглядеть серьезней (я имею в виду авторов книги). Зачем, к примеру, переименовывать min и max в S и T?

                      На самом деле min и max — это нечеткое AND и OR соответственно, и судя по тому, что авторы опирались на теорию нечетких отношений, это скорее всего действительно так. Тогда смысл замыкания здесь в том, что вначале ищется для каждого элемента и подмножества — находится ли этот элемент в отношении R с подмножеством, то есть со всеми его элементами, и здесь используется MIN потому что это выражение "(x R a1) OR (x R a2) OR… (x R aN)"; затем, вычисляется — находится ли элемент в отношении R хотя бы с одним подмножеством, и здесь используется max потому что это OR.

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

                    Ну не знаю у кого он не очень известный, но в социологии и в маркетинговых исследованиях он используется очень часто (чаще чем k-means). Преимущество этого метода в том, что дерево кластеров очень наглядно показывает структуру данных. Только вот вы почему-то это дерево в статье не привели, а оно то как раз и есть самое главное в иерархических видах анализа.
                    Другое преимущество — нет необходимости заранее фиксировать число кластеров. В исследовательских задачах это очень важно, потому что число кластеров в массиве данных заранее неизвестно.
                      0
                      >он используется очень часто
                      Странно. До публикации статьи на гуглом находилось всего несколько научных статей-книг с упоминанием алгоритма.

                      > дерево кластеров
                      > нет необходимости заранее фиксировать число кластеров
                      Это всем известные преимущества иерархических методов. Не видел смысла о них упоминать еще раз.

                      > Только вот вы почему-то это дерево в статье не привели
                      Я бы с радостью, только здесь на порядок больше нужно было поработать над представлением результатов (дерево надо красиво нарисовать, точки на рисунках удобно пронумеровать) — а я пока так себе владею matplotlib.
                        0
                        >Странно. До публикации статьи на гуглом находилось всего несколько научных статей-книг с упоминанием алгоритма.

                        Ну я имел ввиду иерерхические методы вообще. А что касается конкретных алгоритмов, то социологи могут и не знать какой метод именно они используют:). Они же просто запускают какой-нибудь SPSS или R, и считают не вдаваясь особо в те алгоритмы, которые там используются.
                          0
                          Теперь понятно :) Фраза

                          >не очень известного, но крайне интересного иерархического метода

                          никак не имела ввиду редкость иерархических методов вообще, а только редкость конкретного метода.

                          п.с. у Вас отличные статьи о распознавание образов :)

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

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