ТЕХНОЛОГИИ КЛАСТЕРИЗАЦИИ

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

Таксономия, показанная на Рисунке 1 должна быть дополнена обсуждением межсекторальных методов кластеризации, которые могут (в принципе) влиять на все различные подходы независимо от их размещения в таксономии.

• Скопление против разделения: Этот аспект относится к алгоритмической структуре и эксплуатации. Агломерационый метод начинается с определения каждого элемента в отдельный кластер, и последовательно объединяет кластеры вместе, пока критерий останова не выполняется. Разделяющий метод начинается с определения всех элементов в одном кластере и выполняет его расщепление до выполнения критерия остановки.
• Монотетический против политетического: Этот аспект относится к последовательному или одновременному использованию функции кластеризации процесса. Большинство алгоритмов политетические, то есть, любым способом расчитать расстояния между элементами, и решения основанны на этих расстояниях. Простой монотетический метод рассматривает особенности последовательного разделения данного набора элементов. Это показано на Рисунке 2. Здесь, коллекция разделена на две группы с помощью функции x1; вертикальной ломаной V, разделяющей линии. Каждый из этих кластеров еще раз разделяется самостоятельно с помощью функции x2, о чем свидетельствуют разбитые линии H1 и H2. Основная проблема этого алгоритма в том, что он создает два кластера, где d — количество элементов. При больших значениях d, число кластеров порожденных этим алгоритмом является настолько большим, что набор данных делится на мелкие неинформативные и раздробленные кластеры.

Рисунок 2 — Монотентическая плоская кластеризация


• Жесткий против нечеткого: жесткий алгоритм кластеризации выделяет каждый элемент одного кластера в процессе его эксплуатации. Метод нечеткой кластеризации присваивает элементы членство в несколько кластерах. Нечеткая кластеризация может быть преобразована в жесткую кластеризациюи назначением каждого элемента в кластер с наибольшей мерой принадлежности.
• Детерминированный против стохастического: Этот метод в наибольшей степени соответствует плоским методам, направленным на оптимизацию квадрата функции ошибки. Эта оптимизация может быть выполнена с использованием традиционных методов или с помощью случайных поисков в пространстве состояний, состоящих из всех возможных маркировок.
• Инкрементное против декрементного: Эта проблема возникает тогда, когда набор элементов, расположены в большом диапазоне, и существует ограничение по времени исполнения или памяти. Ранняя история кластеризации не содержит много примеров того, как алгоритмы кластеризации были предназначены для работы с большими наборами данных, но появление интеллектуального анализа данных способствовала развитию алгоритмов кластеризации, которые минимизируют число сканирований через элемент, это сокращает число элементов рассмотреных во время исполнения алгоритма или уменьшает размер структур данных.

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

Иерархические алгоритмы кластеризации

Работа алгоритма иерархической кластеризации иллюстрируется с помощью двумерного набора данных на Рисунке 3. Этот рисунок описывает семь элементов: A, B, C, D, E, F, G и они находятся в трех кластерах. Иерархический алгоритм создает дендрограммы представляющие вложенные группы элементов и сходство уровней, на котором группы изменяются. Дендрограмма соответствующая семи точкам на Рисунке 3 показана на Рисунке 4. Дендрограммы можно разбить на различных уровнях для получения различных кластеризаций из данных.

Большинство алгоритмов иерархической кластеризации представляют собой варианты алгоритмов единой связи [Sneath and Sokal 1973], алгоритмов полной связи[King 1967], а также алгоритмов минимальной дисперсии [Ward, 1963; Murtagh 1984]. Из них алгоритмы единой и полной связи являются наиболее популярными. Эти два алгоритма отличаются тем, как они характеризуют сходство пары кластеров. В методе единой ссылки расстояние между двумя кластерами определяется минимальным расстоянием между парой элементов, каждый из которых находится в одном из кластеров. В методе полной связи расстояние между двумя кластерами определяется максимальным расстоянием между парой элементов в двух кластерах. В любом случае, две группы объединяются в больший кластер на основе критерия минимального расстояния. Алгоритм полной связи производит тесно связаные и компактные кластеры [Baeza–Yates 1992], алгоритм единой связи, напротив, подвержен эффекту цепочки [Nagy 1968]. Он имеет тенденцию производить кластеры, которые являются редкими или удлиненными. Так два кластера на Рисунках 6 и 7 отдалены друг от друга «мостом» шумных элементов. Алгоритм единой связи производит кластеры показанные на Рисунке 6, в то время как алгоритм полной связи получает кластеры показанные на Рисунке 7. Кластеры, полученные алгоритмом полной связи более компактны, чем, полученныме алгоритмом единой связи; кластер с номером 1 полученный алгоритмом единой связи вытянут из–за шумной модели помеченой «*». Хотя алгоритм единой связи более универсален, чем алгоритмполноя связи. Например, алгоритм единой связи может извлечь концентрические скопления показанные на Рисунке 5, а алгоритм полной связи не может этого сделать. Тем не менее, с прагматической точки зрения, было отмечено, что алгоритм полной связи производит более полезные иерархии в большинстве случаев, чем алгоритм единой связи.

(1) Поместите каждый элемент в отдельном кластере. Постройте список межэлементных расстояний для всех различных неупорядоченных пар моделей, и отсортируйте этот список в порядке возрастания.

(2) Для каждого отдельного несходства в отсортированном списке расстояний сформируйте значение dk, кластеры, для которых пары элементов ближе, чем значение dk, связаны. Если все пары элементов связны, алгоритм остановится. В противном случае, повторите этот шаг.

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

Агломерационный алгоритм полной связи

(1) Поместите каждый элемент в своем кластере. Постройте список межэлементных расстояний для всех различных неупорядоченных пар моделей, и отсортируйте этот список в порядке возрастания.

(2) Для каждого отдельного несходства в отсортированном списке расстояний сформируйте значение dk, кластеры, для которых пары элементов ближе, чем значение dk, связаны. Если все пары элементов связны, алгоритм остановится. В противном случае, повторите этот шаг.

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

Иерархические алгоритмы являются более универсальными чем плоские алгоритмы. Так, например, алгоритма кластеризации единой связи хорошо работает на наборах данных, содержащих неизотропные кластеры в том числе хорошо разделеные, цепные и концентрические кластеры, в то время как типичный плоский алгоритм, такой как метод К–средних хорошо работает только на наборах данных с изотропными кластерами [Nagy 1968]. С другой стороны, время и пространство сложности [Day 1992] в плоских алгоритмах, как правило, ниже чем в иерархических алгоритмах. Это позволило разработать гибридный алгоритм [Murty and Krishna 1980], который использует лучшие возможности каждого из алгоритмов.

Агломерационного алгоритм иерархической кластеризации

(1) Вычислить матрицы близости, содержащие расстояния между парами элементов. Обработка каждого элемента как кластера.

(2) Найти наиболее близкие пары кластеров, используя матрицы близости. Объединить эти два кластера в один кластер. Обновить матрицы близости чтобы отразить эту операцию слияния.

(3) Если все элементы окажутся в одном кластере, остановиться. В противном случае перейдите к шагу 2.

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