Дюран Б._ Оделл П. - Кластерный анализ (1977) (1185343), страница 3
Текст из файла (страница 3)
Наблюдаемые характеристики могут быть как количественными, так н качественными; однако основная часть нашего рассмотрения будет поу священа количественным данным, которые иногда будем называть измерениями. Результат измерения 1-й характеристики 11 объекта будем обозначать символом хгь а вектор Х;=(х4 размерности рХ! будет отвечать каждому ряду измерений (для 1-го индивида). Таким образом, для множества индивидов 1 исследователь располагает множеством векторов измерений Х= (Хь Хз,...,Х ), которые описывают множество 1.
Отметим, что множество Х может быть представлено как л точек в р-мерном евклидовам пространстве Е„. ' ЗдесЬ и — знак трансионирования, который в русской литературе обычно обозначается штрихом. — Примеч. ред. И $.2. Задача кластерного анализа Пусть т — целое число, меньшее, чем а. Задача кластерного анализа заключается в том, чтобы на основании данных, содержащихся в множестве Х, разбить множество объектов 1 на т кластеров (подмножеств) пь тгз,..., н так, чтобы каждый объект !г принадлежал одному н только одному подмножеству разбиения и чтобы объекты, принадлежащие одному н тому же кластеру, были сходными, в то время как объекты, принадлежащие разным кластерай, были разнородными (несходными) *. Решением задачи кластерного анализа является разбиение, удовлетворяющее некоторому критерию оптимальности.
Этот критерий может представлять собой некоторый функционал, выражающий уровни желательности различных разбиений и группировок. Этот функционал часто называют целевой функцией. Например, в качество целевой функции может быть взята внутри- групповая сумма квадратов отклонений (см.
параграф 1.5). В качестве примера рассмотрим п=8 объектов, обладающих одной характеристикой (т. е. р=1); ре. зультаты измерения пусть представляют собой множество Х= (3, 4, 7, 4, 3, 3, 4, 4). Сумма квадратов отклонений вычисляется по формуле — з ) )(у= ~"', (хг-х)а= ~ ',хг — — (2„'ха)а л э= 1 з 1 г=з где хг представляет собой измерение (-го объекта. Для нашего примера, содержащего 8 объектов, получим: з а ) з ~ ,'хч — — (~',хг)а=140 — 128=12. 8 г 1 г з Если множество Х разбить на трн группы: 61=(3, 3, 3), Оз=(4, 4, 4, 4) и ба= (7), то все внутригрупповые суммы квадратов отклонений будут равны нулю: ((Уг+ ((' 3+ (( 3 0+0+0 Оэ е Приведем следующий прямер задачи кластерного анализа.
В качестве ( рассмотрим л стран, каждую из которых характеризуем валовым национальным продуктом на душу населения (С,), личным потреблением на душу населения (Сз), душевым погреб. пением электроэнергии (Сз) и т. п. Тогда Х~ (вектор измерений) гредставляет собой набор указанных характеристик для первой страны; Хз — для второй и т. д. Задача ааключается в'том, чтобы разбить страны по уровню развития. — Примеч. лер. .15 где и»» обозначает сумму квадратов, соответствующую группе 6».
Оптимальное значение для этого примера равно нулю при условии, что ведется .разбиение натри группы. В общем случае следует рассматривать значение целевой функции в сочетании с желаемым числом групп. Далее будут определены различные виды целевых функций, многие из которых могут быть записаны в универсальной и общей форме.
Очевидно, для того чтобы «решить» задачу кластерного анализа, необходимо количественно определить понятия сходства и разнородности. Что означает «два объекта 1; и 1» различны»? Задача была бы решена, если бы »-й и 1-й объекты попадали в один н тот же кластер всякий раз, когда расстояние (отдаленность) между соответствующими точками Х» и Х» было бы «достаточно малым», и, наоборот, попадали в разные кластеры, если бы расстояние между точкамн Х< и Х; было бы, «достаточно большим». Таким образом, для нашей цели следует рассмотреть понятие расстояния между точками Х» и Х; из Ер с абстрактных позиций. 1.3.
Функции расстояния Определение 1.1. -Неотрицательная вещественнозначная функция»((Х», Х;) называется функцией расстояния (метрикой), если: а)»(»Х», Х») =»б для всех Х» и Х; из Ер, б)»((Х», Х;) =О тогда и только тогда, когда Х»=Х»1 в)»1(Х;, Х;) =И(Хь Х»); г) Ы(Х», Х;)(»((Х», Хь)+И(Хм Х,), где Хь Х» и Х« — любые три вектора из Ер. Значение д(Х», Х;) для заданных Х» и Х» называется расстоянием между Х» и Х» и эквивалентно расстоянию между 1» и 1; соответственно выбранным характеристикам (С<, Са,..., Ср)г В таблице 1.1 приводятся примеры некоторых наиболее употребительных функций расстояния.
Евклидова метрика очень популярна и наиболее употребительна. Метрика 1< абсолютных значений наиболее простая с вычислительной точки зрения'. Сюпремум-норма также легко вычисляется и включает в себя процедуру упорядочивания. 1р-норма охватывает функции расстояния 1, 2 и 3, соответственно р=2,1 иоо. Расстояние Махаланобиса часто называют обобщенным евклидовым расстоянием.
(р-» обычно обозначает рз Т а б л к к а 1Л. Некоторые фуяккяя рееетокяяя матрицу, обратную к матрице рассеяния (см. параграф 1.5). Расстояние Махаланобиса 'инвариантно относительно невырождекных линейных преобразований. Рассмотрим преобразование У=ВХ. Тогда И (Уо У,)=(У,-У1)тйук (У,— У,)= =(ВХ,— ВХ,) Я7„'(ВХ,-ВХ1) = -(Х; — Х,)тВт У„'В(Х,-Х1) = - (Х,— Х;) т Вт(ВЧР„Вт)-з В(Х,— Х,)- - (Х, — Х,) т 97а ' (Х вЂ” Х,) =0а(Хз Х,) Существуют другие, эвристические, меры отдаленности, не являющиеся расстояниями с точки зрения определения 1.1, которые, однако, также применяются на практике.
Например, мера Джеффриса — Матуситы [81], [82], [259], которая определяется по формуле У ч .1/3 тИ= ~ ~ (1'хд;,— тхк1)а ~ (1. 1) к=1 и другая мера, известная под названием «коэффициент дивергенция» [55] т заказ ат93 '17 Мера Джеффриса — Матуситы первоначально была введена в качестве расстояния между двумя функциями плотностей вероятности„однако в форме (1.1) она может быть применена и как мера расстояния междупарой векторов. В первоначальном применении коэффициента дивергенции х были действительными средними х н рассматривались как расстояние между выборочными средними двух выборок.- Следующая теорема позволяет упорядочить функции расстояния, определяемые по 1р-норме.
Теорема 1.1. Неравенство А,(Хо Х;) «о( (Хо Х;) выполняется для всех Хе и Х» из Ер тогда и только тогда, когда И~те. Напомним, что из определения расстояния следует, что для Хе Хь п»р(Хь Х~) =О. 1.4. Меры сходства и измерений Хь Ха,..., Х могут быть представлены в виде матрицы данных размером р Хин ХМ Хра ... Хсп Хр1 Хр2 . Хрп Аналогичным образом расстояния между парами векторов е((Хо Х») могут быть представлены в виде симметричной матрицы расстояний: О г ... а е(21 О ... Аа 1»= Пп2 Ппа ° го О Заметим, что диагональные элементы е(м=О для 1=1, 2, ..., п. Понятием, противоположным расстоянию между Хе и Хь является понятие сходства между двумя объекта* ми 1е и 1ь и Ср.
мажорантносгь средних в применении и степенным средним. — Лримее. ред. 18 Определение 1.2. Неотрицательная вещественная функция з(Хь Х») =зм называется мерой сходства, если: 1) 0~2(Х», Х;) с! для Х»ФХ~', 2) 2(Хь Х») =1; 3) з(ХА Х»)=з(Хь Х;). .Пары значений мер сходства можно объединить в матрицу сходства: 1 512. ° ..
21» — 521 1 . ° ° 22» 2»1 з»2 .. 1 Величину зц будем. просто называть коэффициентом сходства. Если каждый вектор измерения Х» состоит из нулей и единиц, эту величину называют коэффициентом ассоциации, илн парным коэффициентом сопряженности. Существует несколько видов коэффициентов ассоциации, значения которых лежат в пределах от — 1 до +1. К этой группе принадлежит фи-коэффицнент, известный также под названием «четырехпольный коэффициент корреляции».
В дальнейшем мы остановимся только на коэффициентах, удовлетворяющих определению 1.2. Предположим, что каждый вектор наблюдений содержит только нули и единицы, т. е. бинарные данные. Для заданных векторов Х» и Х» обозначим через п»2 число характеристик, которые соответствуют единицам в векторах Х» и Х1, через и»» — число характеристик, соответствующих'нулям в этих векторах; через аы — число характеристик, дающих нуль в Х» и единицу в Х2; сходным образом определяется л„.. Таким образом, и,= =л»1+вы есть число единиц в Хь а и;=г»»»+и»» — число нулей в Хь В табл. 1.2 приводятся примеры коэффициентов сходства, выраженных в терминах определенных выше величин. Обсуждение коэффициентов сходства табл.
1.2, а также другие коэффициенты читатель найдет в работе 13361. Статистики постоянно пользуются мерой линейного сходства, называемой коэффициентом корреляции, который обычно обозначается гц и вычисляется но формуле Р 2 Р 2 г»»= [~хА» хаД/( ~ лА» ~'.,хА» )1»2 ° (1 2) А 1 А 1 А 1 Гаоляна ! 2, Коаффннненты сходства длв аннаэных данных Ковэфиквевт С«нвкв [173], [328] лтт+лтт+лы лтт+лы [334] лтт Р 2лтр [303] [82], [338] 2птт+птт+л!т 2(лтт+лы) р+лтт+по лат+2(пт!+л!т) лтт+л!! [294] р+пт!+лы е, (].З) где Π— угол между этими двумя векторами.
Поэтому, как следует из уравнения (1.3), — 1<с!3<1. Будем говорить, что объекты 1, и 1! сходны положительным об. разом (положительно), если гм «близок» к 1, отрицательно сходны, если г!! «близок» к — 1, не сходны, если го «близок» к нулю. Заметим, что гм не является функцией сходства с точки зрения определения 1.2«. ' Не выполняется вкснона 1.— Прил««. лер. Ф Р Р В формуле (1.2) предполагается, что Ххат= Ххат=О. в=! . в-! Коэффициент гц занимает важное место в статистике и употребляется, зачастую ошибочно, почти каждым. Важно подчеркнуть, что если Х! и Х) рассматривать как координаты двух точек в пространстве Ев, являющиеся концами двух векторов с началом в начале координат, то 17] Лемма гЛ.' Коэффициент корреляции гц=1 тогда и только тогда, когда Х<=йХь где й — неотрицательное число.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
