Кластеризация данных
Данный узел или опция доступны, только если они включены в лицензии PolyAnalyst Server.

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

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

Кластеризация применяется для решения многих прикладных задач: от сегментации изображений до экономического прогнозирования и борьбы с электронным мошенничеством.

Для того, чтобы понять, что представляет собой такая близость, представьте себе простую диаграмму рассеяния X-Y с сотней случайно расположенных точек. Взглянув на график, вы можете сами выбрать точки на графике, которые расположены рядом и составляют большие группы. Таков один из возможных подходов к определению подобия – близость точек, минимальное расстояние между ними. Чем ближе точки, тем меньше расстояние (тем выше близость), следовательно, тем более похожи друг на друга эти точки. Конечно, такая диаграмма показывает отношения только в двух измерениях (в двух колонках в таблице). Данные, с которыми вы работаете при кластеризации, могут состоять из сотен колонок. Этот тип данных называют многомерным или n-мерным (n здесь означает "любое количество"). Поэтому, техники, используемые алгоритмами кластеризации, на самом деле являются более сложными для понимания и для визуализации (если, конечно, вы не работаете с двумя колонками).

Применение кластерного анализа в общем виде сводится к следующим этапам:

  1. Отбор выборки объектов для кластеризации.

  2. Определение множества переменных, по которым будут оцениваться объекты в выборке. При необходимости – нормализация значений переменных.

  3. Вычисление значений меры сходства между объектами.

  4. Применение метода кластерного анализа для создания групп сходных объектов (кластеров).

  5. Представление результатов анализа.

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

Главный вопрос для любого алгоритма кластеризации – как определять «похожесть» объектов? Для начала нужно составить вектор характеристик для каждого объекта — как правило, это набор числовых значений, например, рост-вес человека. Однако существуют также алгоритмы, работающие с качественными (т.н. категорийными) характеристиками.

После того, как вектор характеристик определен, можно провести нормализацию, чтобы все компоненты давали одинаковый вклад при расчете «расстояния». В процессе нормализации все значения приводятся к некоторому диапазону, например, [-1, -1] или [0, 1].

Наконец, для каждой пары объектов измеряется «расстояние» между ними — степень похожести. Существует множество метрик, вот лишь некоторые примеры: Евклидово расстояние, Манхэттенское расстояние, расстояние Чебышева и др.

В системе PolyAnalyst используются следующие инструменты кластерного анализа:

  • Кластеризация на основе расстояний основана на анализе расстояний между векторами. В отличие от кластеризации по методу k-средних, данный алгоритм не эффективен при поиске кластеров в случайных данных.

  • Максимизация ожидания – алгоритм, используемый для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных. Каждая итерация алгоритма состоит из двух шагов. На E-шаге (expectation) вычисляется ожидаемое значение функции правдоподобия, при этом скрытые переменные рассматриваются как наблюдаемые. На M-шаге (maximization) вычисляется оценка максимального правдоподобия, таким образом увеличивается ожидаемое правдоподобие, вычисляемое на E-шаге. Затем это значение используется для E-шага на следующей итерации.

  • Кластеризация по методу k-средних – один из наиболее часто используемых алгоритмов кластеризации данных, использующий быстрый эвристический метод на основе заданного количества кластеров (k). Данный метод очень чувствителен к аномальным значениям.

Более подробно каждый алгоритм описан в соответствующем разделе Руководства пользователя.