Кластеризация данных. 
Системы поддержки принятия решений

В результате изучения данной главы студент должен: знать

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

Ключевые слова Кластеризация данных, самоорганизующиеся карты Кохонена, нечеткая кластеризация, генетические алгоритмы.

Обзор методов кластеризации данных

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

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

Определение.

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

Необходимо различать понятия:

• кластеризации как процесса формирования групп объектов в соответствии со свойственными им характеристиками, реализуемого на основе обучения без учителя;

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

Общая схема проведения кластерного анализа, а также обзор наиболее распространенных методов кластеризации приведены ниже.

Основные этапы кластерного анализа:

• 1) формирование базы данных, в том числе выделение и отбор характеристик исследуемых объектов;
• 2) выбор метрик, т. е. определение критериев схожести объектов;
• 3) разбиение множества объектов на группы;
• 4) представление и интерпретация полученных результатов;
• 5) оценка результатов кластеризации¹.

Далее приведено более подробное описание каждого из этапов.

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

Характеристики объектов могут относиться к следующим типам:

• • количественные характеристики в виде непрерывных, дискретных или интервальных величин;
• • качественные характеристики, которые могут быть упорядоченными в соответствии с ординальной шкалой или быть неупорядоченными.

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

Обратите внимание!

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

'Jain А., МиПу М., Flynn Р. Data Clustering: A Review // ACM Computing Surveves. September 1999. Vol. 31. No 3. P. 264−323.

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

Метрикой называется вещественно-значная функция двух переменных d (x, у), имеющая следующие свойства:

• • свойство неотрицательности d (x, у) > 0, d (x, у) = 0 х = у;
• • свойство симметричности d (x, у) = d (y, х);
• • свойство, называемое неравенством треугольника d (x, у) < d (x, z) + + d (z, y).

Далее приведены наиболее распространенные метрики^[1]:

/V.

• евклидова метрика: d (x, y)₂ = * ?,(^xi ~У<)² !

т

• квадрат евклидовой метрики: d(х, у) =к X; -)²;

/=1.

т.

• манхэттенская метрика: d (x, y)_t = jT|x. -у, I;

i=i

• метрика Чебышева (максимум): d{x, у)" = шах |х, -уА;

/=1…т

Еч У,

• метрика косинус: d (гп)^ =^[2] :

I т т.

^Хч²-|>,²

• метрика Минковского: d (x, y)_r = У | х. -y_i |^г ;

'=> т

• • метрика Хэмминга: d (x, y)" = (Ч ⁼ У,)'<
• 1=1
• • метрика Махаланобиса: d (x, у)_м = (х — y)^rW '(х — у), где W ' — матрица, обратная матрице ковариаций.

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

Обратите внимание!

Квадрат евклидовой метрики удобен тем, что он всюду дифференцируем. При этом после дифференцирования мы получаем линейные двучлены, что обычно очень удобно с математической точки зрения в вычислительном плане. Тем не менее, если, к примеру, все элементы векторов х и у измерялись в рублях, то расстояние между ними будет уже рассчитываться в квадратных рублях, что сложнее поддается интерпретации. Данная метрика усиливает большие различия и, наоборот, нивелирует значимость незначительных отличий.

Тем не менее, в силу специфики реальных задач, часто использование других метрик может дать более «хорошее» разбиение, которое легче обосновать с экономической точки зрения, а для неколичественных шкал применение квадрата евклидовой метрики вообще трудно считать обоснованным.

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

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

Метрика Косинус представляет собой коэффициент корреляции между векторами х и у при условии, что они имеют нулевое среднее. Коэффициент корреляции, в свою очередь, является мерой линейной зависимости.

Расстояние Минковского интересно для изучения с математической точки зрения. Так, при г = 1 мы получим манхэттенское расстояние, при г = 2 — евклидово расстояние, при г —? оо — максимум.

Метрика Хэмминга, так же как метрика Рао и некоторые другие метрики, может успешно использоваться для переменных, оцененных в номинальных шкалах, для которых все вышеназванные метрики практически не применимы.

Метрика Махаланобиса. Если евклидово расстояние выделяет кластеры, которые имеют форму гиперсфер, то метрика Махаланобиса выделяет кластеры, которые будут иметь форму гиперэллипсоидов^[3]. Как частный случай она содержит в себе и квадрат евклидовой метрики.

Обратите внимание!

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

Существуют различные подходы к классификации наиболее распространенных методов кластеризации, некоторые из которых приведены ниже.

• [1] Фихтенгальц Г. М. Курс дифференциального и интегрального исчисления. Т. 1. М.:
• [2] Физматлит, 2001.
• [3] Фихтенгольц Г. М. Указ. соч.