Целочисленное программирование

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

11.2.4. Методы кластеризации

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

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

Метод максимального локального расстояния (Мак Нотон-Смит): объекты группируются последовательно по следующему правилу - два кластера объединяются, если максимальное расстояние между точками одного и другого минимально.

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

Центроидный метод (Сокал и Миченер) основан на определении расстояния между средними значениями кластеров.

Двухгрупповой метод (Сокал и Миченер) опирается на связь между объектом i и кластером I. Эта связь выражается в виде среднего коэффициента сходства между объектом i и всеми объектами, входящими в кластер I.

Метод групповых средних (Ланс, Уильямс) определяет среднее сходство между двумя кластерами I и J как среднее сходство между всеми парами объектов из I и J.

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

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

В процедуре Болла и Холла первоначальные К кластеров формируются случайным отбором k точек, к которым затем присоединяется каждая из оставшихся n – k точек (по минимальному расстоянию к той или иной из них).

Другие методы (Мак Квин, Себестьен, Дженсен, Форджи и др.) можно рассматривать как модификации вышеизложенных методов кластеризации.

11.2.5. Представление данных

Данные кластеризации можно наглядно представить в двумерном пространстве в виде дендрограмм или разветвленного (древовидного) графа. В том и другом случае в качестве исходных данных служат матрица сходства или расстояния между обектами.

Рассмотрим в качестве примера корреляционную матрицу (матрицу сходства) следующего вида (табл. 11.2):

Таблица 11.2

Объекты (признаки)	A	B	C	D	E	F
A	1,00	0,35	0,92	0,50	0,42	0,72
B		1,00	0,47	0,67	0,65	0,54
C			1,00	0,38	0,24	0,78
D				1,00	0,84	0,44
E					1,00	0,35
F						1,00

Каждая из шести переменных, фигурирующих в матрице, обозначена латинскими буквами от A до F. Заполнена только половина матрицы, поскольку верхняя правая и нижняя левая половины зеркально отражают друг друга (r_AB = r_BA, r_BF = r_FB и т.д.). По главной диагонали матрицы коэффициенты корреляции соответствуют единицам (r_xx = 1).

Объединение переменных в кластеры производится, начиная с максимального коэффициента корреляции. При этом для построения дендрограммы переменные связываются между собой на данном уровне коэффициента корреляции r или меры расстояния d = 1 – r². Для облегчения работы эти значения округляются до 1-го знака после запятой. Так, максимальный коэффициент корреляции – между переменными A и C (r = 0,92), следовательно, переменные связываются между собой на уровне ~ 0,9. Следующий за первым (по мере убывания) коэффициент корреляции между переменными D и E равен 0,84 (переменные связываются друг с другом на уровне ~ 0,8). Третий по убыванию коэффициент между переменными C и F соответствует 0,78; следовательно, на уровне ~ 0,8 мы можем «привязать» к переменным A и C (а они уже связаны друг с другом) еще и переменную F и т.д. Таким образом, мы последовательно связываем друг с другом все переменные, формируя дендрограмму (аналогично построению «родословного дерева» исследуемых признаков в биологии).

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

1,0_ F A C D E B

0,9 0,8 0,7 0,6 0,5 0,4

Рис. 11.1. Дендрограмма признаков, построенная на основе матрицы корреляций.

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

Рис. 11.2. Древовидный (разветвленный) граф:

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

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