3.2 Кластерный анализ

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

Кластерный анализ – это способ группировки многомерных объектов, основанный на представлении результатов отдельных наблюдений точками подходящего геометрического пространства с последующим выделением групп как «сгустков» этих точек (кластеров, таксонов). «Кластер» (cluster) в английском языке означает «сгусток», «гроздь винограда», «скопление звезд» и т.д. Данный метод исследования получил развитие в последние годы в связи с возможностью компьютерной обработки больших баз данных.[26]

Кластерный анализ предполагает выделение компактных, удаленных друг от друга групп объектов, отыскивает «естественное» разбиение совокупности на области скопления объектов.[14] Он используется, когда исходные данные представлены в виде матриц близости или расстояний между объектами либо в виде точек в многомерном пространстве. Наиболее распространены данные второго вида, для которых кластерный анализ ориентирован на выделение некоторых геометрически удаленных групп, внутри которых объекты близки.

Задача кластерного анализа:

Пусть множество обозначает объектов. Результат измерения i-й характеристики объекта обозначают символом , а вектор

отвечает каждому ряду измерений (для j-го объекта). Таким образом, для множества I объектов исследователь располагает множеством векторов измерений , которые описывают множество . Множество X может быть представлено как n точек в p-мерном евклидовом пространстве .

Пусть m – целое число, меньшее чем n. Задача кластерного анализа заключается в том, чтобы на основании данных, содержащихся во множестве Х, разбить множество объектов I на m кластеров (подмножеств) так, чтобы каждый объект принадлежал одному и только одному подмножеству разбиения и чтобы объекты, принадлежащие разным кластерам, были разнородными (несходными). [28]

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

Основные понятия

N измерений могут быть представлены в виде матрицы

(3.31)

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

(3.32)

для

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

, , , . (3.33)

Понятием, противоположным понятию расстояния между объектами и , является понятие близости (сходства) между и . Точнее, мера близости между объектами и – это вещественная функция со свойствами:

Пары значений мер близости можно объединить в матрицу близости:

, (3.34)

Величину называют коэффициентом близости. Примером линейной близости является коэффициент корреляции. Рассмотрим основные способы определения расстояний между объектами.

Метрики для количественных шкал (расстояние).

а) Линейное расстояние

(3.35)

б) евклидово расстояние

(3.36)

в) обобщенное степенное расстояние Минковского (универсальная

метрика)

(3.37)

Метрики для качественных шкал (мера близости).[27]

К качественным шкалам относят:

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

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

Расстояние для номинальных шкал вводится следующим образом. Пусть имеются два объекта X и Y с N признаками. Введем координаты и

как логические переменные, принимающие значение 1, если объект обладает i-м признаком, и 0, если признак с номером i у объекта отсутствует. Выбор конкретного измерителя близости объектов X и Y должен осуществляться из содержательных соображений: если предполагается значимость совпадения единичных и нулевых свойств, то применяют расстояние Хемминга – отношение количества совпадающих значений к числу всех значений N. Если же важно наличие свойства, а не его отсутствие, то применяют коэффициенты Рао или Роджерса-Танимото, в которых учитываются только совпадающие единичные значения, а совпадающие нулевые игнорируются.

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