АЛГОРИТМЫ АНАЛИЗА ДАННЫХ. КЛАСТЕРИЗАЦИЯ

Одним из наиболее распространенных и простых алгоритмов кластеризации является алгоритм k-means.

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

Алгоритм состоит из двух этапов.

1. Первоначальное распределение объектов по кластерам. Задается число k, и на первом шаге эти точки считаются «центрами» кластеров. Каждому кластеру соответствует один центр. Выбор начальных центров осуществляется случайным образом. В результате каждый объект назначен определенному кластеру.

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

В качестве функции расстояния k-means в Deductor использует:

– для непрерывных числовых полей, а также упорядоченных категориальных признаков – евклидово расстояние. Использует для вычисления расстояний следующее правило:

𝑑𝑑𝐸𝐸(𝑥𝑥, 𝑦𝑦) = ��(𝑥𝑥𝑖𝑖− 𝑦𝑦𝑖𝑖)2;

𝑖𝑖

где х = (x1, x2,..., xm), y = (y1, y2,..., ym) – наборы (векторы) значений признаков двух записей.

Поскольку множество точек, равноудаленных от некоторого центра при использовании евклидовой метрики будет образовывать сферу (или круг в двумерном случае), то и кластеры, полученные с использованием евклидова расстояния, также будут иметь форму, близкую к сферической;

– для неупорядоченных категориальных признаков – функцию отличия:

𝑑𝑑(𝑥𝑥, 𝑦𝑦) = �0, 𝑥𝑥= 𝑦𝑦�.

1, 𝑥𝑥 ≠ 𝑦𝑦

В Deductor Studio для автоматизации этого процесса есть

соответствующий инструмент – Кластеризация.

1) Рассмотрим механизм кластеризации реализованный на алгоритме

k-means, основываясь на данных роста численности населения по регионам.

Исходная таблица находится в файле Polution.txt.Задача состоит в распределении регионов на функциональные группы по демографической картине в них и выявлении скрытых закономерностей.

Вначале необходимо осуществить импорт рассматриваемых данных из файла.

2) После этого выбираем и запускаем Мастер обработки

Кластеризация.

При запуске Мастеранеобходимо настроить назначения столбцов, т.е. выбрать свойства по которым будет происходить группировка объектов (рис. 8.1).

Укажем столбцам назначение соответственно рисунку.

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

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

Рисунок 8.1 – Настройка назначения столбцов

Рисунок 8.2 – Разбиение исходного набора данных на подмножества

Рисунок 8.3 – Настройка параметров кластеризации

5) Для отображения полученных групп кластеров выберем в обработчике Кластеризация из списка визуализаторов способы отображения данных: Что-если для решения задачи классификации, отнесение региона к одному из кластеров, Профили кластеров – для определения структуры формирования группы кластеров и Куб – для наглядного просмотра полученных результатов (рис. 8.4).

Для настройки визуализатора Куб необходимо выбрать рассматриваемые свойства как факты, а Номер кластера – как измерение и Регионы –информационное.

Наиболее правильно в дальнейших настройках задать отображение всех фактов как среднее по рассматриваемое группе (рис. 8.5).

6) Общую структуру сформированных алгоритмом кластеров можно просмотреть в визуализаторе Профили кластеров. Отсортировав кластеры по убыванию, получаем следующие профили кластеров (рис. 8.6).

Рисунок 8.4 – Настройка полей визуализатора Куб

Рисунок 8.5 – Настройка отображаемых фактов

Рисунок 8.6 – Результат сортировки кластеров по убыванию

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

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

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

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

Кластеры поменялись местами в зависимости от значимости среднедушевого дохода в рассматриваемом наборе. Наиболее отличающиеся кластеры по среднедушевому годовому отчету будут иметь максимальную значимость (рис. 8.8).

8) Результаты п сформированным кластерам наиболее удобно рассматриваются с помощью визуализатора Куб, в котором встроена кросс- диаграмма, изображающая полученные кластеры в графическом виде, что существенно упрощает анализ (рис. 8.9).

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

Рисунок 8.7 – Настройка сортировки

Рисунок 8.8 – Результат сортировки кластеров

Рисунок 8.9 – Кластеризация отображена визуализатором Куб

Сохраните результат в файле L8_1.ded.

Рассмотренный пример проиллюстрировал, применение кластеризации для группового анализа данных. С помощью задачи кластеризации все регионы сгруппировались на кластеры по параметрам входных значений, интерпретация которых осуществляется с помощью кросс-диаграммы и куба. Но кажущаяся простота задачи кластеризации обманчива, она требует полной собранности аналитика при анализе полученных результатов и наличии чувства интуиции. Именно аналитик решает, на сколько кластеров необходимо разбить исследуемый набор данных и какие свойства будут основными при построении кластера, т.е. аналитик закладывает фундамент решения задачи. Но это не все проблемы, связанные с задачей кластеризации – одной из особенностей применения k-means алгоритма, а также и многих других. Например, то что при повторном построении задачи кластеризации можно не получить одинакового результата, это связано с тем что данные очень разрозненные и алгоритм выбирает случайным образом центры кластеров.