Постановка задачи

Лекция 6 – Кластерный анализ данных

Что делать, если нет обучающего материала для построения классификатора? То есть нет учителя, который покажет, как следует классифицировать тот или иной объект?

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

Общий алгоритм кластеризации выглядит так:

1. Приведение исходных данных к нужному виду (подготовка данных);
2. Выбор меры близости;
3. Выбор алгоритма (метаалгоритма) кластеризации;
4. Выполнение алгоритма;
5. Представление полученных результатов;
6. Интерпретация полученных результатов.

Рассмотрим каждый из этапов более подробно.

На первом этапе происходит подготовка данных к кластеризации. Данные для кластеризации чаще всего представляют в виде таблиц, где каждый столбец - это один из атрибутов, строка - объект данных.

На втором этапе выбирают, как охарактеризовать сходство объектов. Для этого используются различные меры близости, то есть, фактически, оценки близости двух объектов друг к другу. Меры близости выбирают, исходя из свойств объектов. Так, популярной мерой близости является декартово расстояние (в двумерном случае): d²( < x₁,y₁ > , < x₂,y₂ > ) = sqrt((x₁ − x₂)² + (y₁ − y₂)²) или метрика Минковского в многомерном случае: dⁿ(x,y) = | | X,Y | | Это достаточно хорошие меры близости для представимых на координатной плоскости значений. Для нечисленных атрибутов подбирают такие меры близости, которые позволяют свести их к численным и сравнить. Так, основным расстоянием для строк является метрика Левенштейна, которая устанавливает расстояние между двумя строками равным количеству перестановок, которые необходимо совершить, чтобы превратить одну строку в другую. Мера близости подбирается индивидуально для конкретных типов данных. Иногда адекватной меры близости подобрать не удается, и приходится ее придумывать самим.

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

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

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

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