3.4. Многомерные статистические группировки

Для проведения многомерной классификации необходимо:

1) сформулировать цель классификации;

2) выделить комплекс ее признаков;

3) определить меру сходства объектов;

4) выбрать алгоритм и программу классификации;

5) распределить объекты по группам;

6) оценить результаты.

Первые 4 этапа – это постановка задачи классификации. Исходные данные для задачи многомерной классификации обычно представляют в виде матрицы «объект-признак». Строками являются значения признаков, характеризующих соответствующий объект, а столбцами – значения каждого отдельного признака для всей рассматриваемой совокупности объектов.

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

Для измерения степени близости между парами объектов (i и j), когда каждый из признаков принимает значение 0 или 1, используются коэффициенты подобия S. Наиболее простой коэффициент подобия рассчитывается по формуле двух сравниваемых объектов –

,

где – число совпадающих признаков по объектам i и j; m – общее число признаков, по которым осуществляется сравнение.

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

.

Расстояния между объектами i и j определяют одной из следующих метрик:

1) расстояние по Хеммингу (особенно для признаков, не требующих стандартизации и обладающих только двумя значениями – 0 и 1) –

;

(Расстояние по Хэммингу иногда называют манхэттенским расстоянием).

2) расстояние Евклида– для количественных признаков –

,

где x_il – значение (стандартизованное) l–го признака у объекта i; х_jl – то же, для объекта j.

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

3) расстояние Махаланобиса –

,

где x_i – строка значений всех признаков по объекту i, x_j – то же для объекта j.

Σ^-1 – матрица, обратная матрице Σ ковариации признаков (размерности m×m). На главной диагонали ковариационной матрицы располагаются дисперсии признаков. Если признаки стандартизованы, то Σ это матрица парных линейных коэффициентов корреляции.

4) расстояние Чебышева –

Наиболее известными и простыми приемами многомерных классификаций наблюдений (объектов) являются:

• метод дендритов;

• метод шаров;

• метод многомерной средней.

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

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

На первом этапе находят повторяющиеся связи (например, 1–3 и 3–1), одно из двух повторяющихся сочетаний всегда исключается. Наличие общих элементов (объектов, общих узлов) в отдельных дугах позволяет их объединить в несколько дендритов (скоплений) первого порядка (например, дуга 1–3 и 3–5 объединяется в общий дендрит 1–3–5, каждый из дендритов первого порядка может разветвляться и иметь более сложный вид). В редких случаях дендрит первого порядка может включить в себя сразу все объекты совокупности, тогда процесс построения дендрита заканчивается. Но обычно дендриты первого порядка не удовлетворяют основному условию, поскольку не связывают все объекты в единое целое, требуется переход ко второму этапу.

На втором этапе определяются два наиболее близких скопления первого порядка и дуга, связывающая их. Данная дуга становится связью между двумя соответствующими скоплениями. Так образуются дендриты (скопления) 2-го порядка. Второй этап повторяют столько раз, сколько необходимо, чтобы любые два объекта исследуемого множества оказались связанными друг с другом, т.е. пока не сформируется единый общий дендрит.

На основе полученного дендрита выполняется разбиение множества на однородные совокупности. Оптимальное разбиение дендрита предполагает два варианта. Если заранее известно n – число групп, на которые следует разделить изучаемое множество объектов, то из построенного дендрита удаляется (n-1) самых длинных дуг, т.е. дендрит разбивается на n частей.

Если число групп неизвестно, то либо подбирается пороговая величина h, и убираются дуги с длиной, большей h, (изменяя величину порога, так поступают несколько раз, останавливаясь, когда разбиение может быть сочтено оптимальным), либо применяется «естественный» способ разбиения. Для этого все связи полученного дендрита упорядочиваются по убыванию расстояний. Затем рассчитываются отношения соседних расстояний:

…,

где – упорядоченные длины связей;

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

.

Если таких соотношений несколько, выбирается минимальное значение; Если, например, это соотношение i_m , из дендрита удаляют m-1 самых длинных дуг и получают, естественно, разбиение на m классов.

Пример. Матрица расстояний между объектами (V_i) представлена таблицей

	V1	V2	V3	V4	V5	V6	V7	V8	V9
V1	0	6	11	14	18	23	26	32	38
V2	6	0	5	8	12	17	20	26	32
V3	11	5	0	3*	9	12	15	21	27
V4	14	8	3	0*	4	9	12	18	24
V5	18	12	9	4*	0	5	8	14	20
V6	23	17	12	9	5	0	3	9	15
V7	26	20	15	12	8	3	0	7	12
V8	32	26	21	18	14	9	7	0	8
V9	38	32	27	24	20	15	12	8	0

Выполним построение дендрита.

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

V₁–V₂, расстояние равно 6;

V₂–V₃, расстояние равно 5;

V₃–V₄, расстояние равно 3, (расстояние V₄-V₃ не включаем, как повторное);

V₅–V₄, расстояние равно 4;

V₆–V₇, расстояние равно 3; (расстояние V₇-V₆ не включаем, как повторное);

V₈–V₇, расстояние равно 7;

V₉–V₈, расстояние равно 8.

2. Простое объединение этих дуг дает 2 скопления (дендрита) 1-го порядка:

V₁ –(6)– V₂ – (5) – V₃ – (3) – V₄ – (4) – V₅;

V₆ – (3) – V₇ – (7) – V₈ – (8) – V₉.

3. Находим наименьшее расстояние между всеми полученными дендритами первого порядка. Обнаруживаем, что наиболее близкими являются объект V₅ из первого дендрита и объект V₆ из второго дендрита (расстояние равно 5). В общем случае полезно составить матрицу оставшихся расстояний.

	V1	V2	V3	V4	V5
V6	23	17	12	9	5^*
V7	26	20	15	12	8
V8	32	26	21	18	14
V9	38	32	27	24	20

В результате объединения получаем полный дендрит. Как видно, в данном случае этот дендрит имеет очень простую структуру:

V₁ –(6)– V₂ – (5) – V₃ – (3) – V₄ – (4) – V₅ –(5) – V₆ – (3) – V₇ – (7) – V₈ – (8) – V₉.

Для определения числа классов упорядочиваем длины дуг дендрита по уменьшению:

(8) – (7) – (6) – (5) – (5) – (4) – (3) – (3)

и находим отношения соседних длин:

i₂=8/7=1,143; i₃=7/6=1,167; i₄=6/5=1,20; i₅=5/5=1,0; i₆=5/4=1,25; i₇=4/3=1,333; i₈ = 3/3 = 1,0 .

Соотношение встречается четыре раза:

i₂ < i₃ ;

i₃ < i₄ ;

i₅ < i₆ ;

i₆ < i₇.

Минимальное соотношение в неравенстве при k=5 ; (i₅=1,0 < i₆=1,25). Следовательно, удаляем (k–1)=4 самые большие расстояния дендрита. (В неопределенных ситуациях удаляем в первую очередь дуги, связывающие дендриты меньшего порядка). Получаем 5 групп объектов⁵:

{V₁}, {V₂-V₃-V₄-V₅}, {V₆-V₇}, {V₈}, {V₉}.

Метод шаров. Пусть для множества объектов получена {С_ij} – матрица расстояний между точками (i,j = 1, … , n).

Для каждой точки строится шар радиуса ρ. Радиус шара может быть вычислен двумя способами:

1) ;

2) , причем ; , , где m – действительное неотрицательное число.

Затем для каждого элемента (объекта) подсчитывается число точек, находящихся внутри данного шара:

,

где Ω_i означает подмножество i множества . Его образуют элементы i и , удовлетворяющие условию (иногда рекомендуется: ).

Если обозначить через l_i объем подмножества Ω_i, то – величина, определяющая первое выделяемое подмножество. Если существует несколько подмножеств с равными максимальными объемами, исчисляют расстояние до центров выбранных шаров от начала системы координат. Первое подмножество образуют единицы, которые содержатся в шаре, ближе всего находящемся от начала системы координат. Это подмножество обозначается символом Ω_i. Если первичных данных нет, то ограничиваются суммированием расстояний от центра шара до включенных в него элементов.

Дальнейшие действия аналогичны, только относятся не ко всем объектам, а лишь к тем, которые остались после исключения первого подмножества. Это значит, что при дальнейшем выделении подмножеств рассматривается множество Ω\Ω_i. Процедура заканчивается при исчерпании множества Ω.

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

	V1	V2	V3	V4	V5	V6	V7	V8	V9
Min по столбцу	6	5	3	3	4	3	3	7	8
l	2	3	3	3	3	3	3	2	1
∑	-	11	8	7*	9	8	10	-	-

Максимальное значение этих минимальных элементов равно 8. Таким образом, ρ = 8.

Теперь для каждого объекта V_j определяется l –число объектов, входящих в его шар таким образом, что . Элементы того объекта, где больше число l и образуют первое подмножество. В нашем примере шесть столбцов имеют l_max = 3. В этом случае мы выбираем столбец, в котором сумма расстояний (∑) между элементами, удовлетворяющими условию , является минимальной. Это столбец V₄, и тогда первое подмножество образуют элементы V₃, V₄ и V_5.

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

	V1	V2	V6	V7	V8	V9
V1	0	6	23	26	32	38
V2	6	0	17	20	26	32
V6	23	17	0	3*	9	15
V7	26	20	3	0*	7	12
V8	32	26	9	7*	0	8
V9	38	32	15	12	8	0
Min по столбцу	6	6	3	3	7	8^*
l	2	2	2	3*	2	1

Определяем элементы второго множества. Радиус шара равен 8. Так как столбец (V₇) имеет l_max = 3, то второе подмножество включает {V₆, V₇, V₈}.

Элементы выявленного подмножества опять исключаются из матрицы расстояний. В результате новой итерации будем иметь два подмножества {V₁, V₂,},{ V₉}:

	V1	V2	V9
V1	0	6*	38
V2	6	0*	32
V9	38	32	0
Min по столбцу	6	6	32
Max min ρ	32
l	2	2	1
∑	6	6	-

Таким образом, применив метод шаров, мы распределили объекты по 4 группам: {V₃, V₄, V₅}, {V₆, V₇, V₈}, {V₁, V₂}, {V₉}.

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

либо .

По нормированным значениям для каждого объекта (или наблюдения) рассчитывается средняя арифметическая величина:

.

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

Имеется совокупность из 10 объектов, каждый из которых характеризуется признаками X₁, X₂, X₃. Значения признаков для каждого объекта нормируются по их среднему уровню, после чего подсчитывается среднее значение нормированных признаков –

, где k = 3 – число признаков.

Номер объекта	X1	X2	X3	Нормированные уровни Pij			Обобщенный признак
1	8	7	62	2,29	0,65	0,98	1,31
2	3	5	53	0,86	0,46	0,83	0,72
3	2	15	78	0,57	1,39	1,23	1,06
4	1	9	95	0,29	0,83	1,50	0,87
5	6	20	62	1,71	1,85	0,98	1,51
6	2	9	46	0,57	0,83	0,72	0,71
7	1	18	84	0,29	1,67	1,32	1,10
8	5	1	72	1,42	0,10	1,13	0,88
9	6	15	40	1,71	1,39	0,63	1,24
10	1	9	43	0,29	0,83	0,68	0,60
Итого	35	108	635	10,00	10,00	10,00	10,00
	3,5	10,8	63,5	1,0	1,0	1,0	1,0

Полученные значения многомерной средней следует разделить на n=1+3,322·lg10 = 4 группы. Величина интервала определяется по формуле

.

Обобщенный признак (многомерная средняя) группируется по интервалам: 0,6–0,83; 0,84–1,07; 1,08–1,31; 1,32–1,55. Получаем следующее распределение объектов по группам:

Группировка объектов по величине многомерной средней	Количество объектов	Номера объектов	Средние значения по признакам
			X1	X2	X3
0,60 – 0,83	3	2, 6, 10	2,00	7,67	47,33
0,84 – 1,07	3	3, 4, 8	2,67	8,33	81,67
1,08 – 1,31	3	1, 7, 9	5,00	13,33	62,00
1,32 – 1,55	1	5	6,00	20,00	62,00