Дюран Б._ Оделл П. - Кластерный анализ (1977) (1185343), страница 4
Текст из файла (страница 4)
Доказательство этой леммы следует непосредственно из формулы (1.2). Заметим, что две точки Х~ и Ха могут быть сравнительно далекими друг от друга и в то же время сходство, измеряемое гп, может оказаться равным 1. Рассмотрим, в частности, следующий пример (графнк с числовыми значениями представлен на рис. 1). лл хп Рис. 1. Две точки в Еа Пользуясь метриками (1), (2) и (3) табл. 1.1 и гм (уравнение (1.2) ), найдем: с(х(Х1 Ха) = [(10 — 1)'+ (10 — 1)')"=9)(21 Ию(ХьХт) = И10-1~+ /10 — 1Ц =181 . И (ХьХа)=зпр И10 — 1~, ~10 — 1Ц=9; гм=1.
Заметим, что хотя Х1ФХх, гм=1, т. е. объекты г1 и )я с точки зрения такого критерия будут считаться сходными. Заметим также, что 4 (Х1 Хв) (с(т (Хь Хт) <А (Хь Хт), что лишний раз иллюстрирует теорему 1.1 из параграфа 1.3. Важно заметить, что, выбирая соответствующеепреобразование,.можно исходя нз различных мер расстояния, приведенных в параграфе 1.3, построить соответствующие меры сходства*.
Поэтому если предпочтитель- Например, можно положить ат(Х» Хг) =1/(1+с(г(Хь Хг))', где от в евклидово расстояние. Легко проверить, что все свойства меры сходства для гт выполняются (определение !.2). — Примеч. иер. 21 нее работать с мерами сходства, то необходим соответ. ствуюший переход. Воспользуемся теперь введенным понятием расстояния для вычисления меры рассеяния или разнородности множества объектов 1= (»»,..., 1„), Определение 1.3. Пусть Х=(Хь Хь..., Х ) обозначает множество наблюдений, произведенных над множеством объектов 1= (1ь 1ь..., 1 ). Величина и л зл= 1/2 ~;,'~ д(Х,, Х») (1.4) называется общим рассеянием, соответствующим данной функции расстояния д(Хь Х»). Определечие 1.4. Величина ел=ел//»/,ь где Л»л=(пав -и)/2 называется средним рассеянием множества 1.
Обоснование определений 1.3 и 1.4 следует из рассмотрения матрицы расстояний Р=(д»»=»1(Х», Х»)) с учетом того, что, во-первых, для всех» д»»=д(Х», Х,) -О, а, во-вторых, из Н(Хь Х») =»1(х», Х»)' следует д»»=»/»» для всех»~/=1, 2,..., и. Отсюда величина зл представляет собой сумму и' расстояний, из которых п равны нулю, и (и' — и)/2, вообще говоря, различны и неотрицательны. Поэтому зл есть арифметическое среднее ненулевых расстояний между парами элементов из Х, илн, что то же, из 1. Матрица Р является компактной записью расстояний всех пар элементов из множества 1. Статистики применяют аналогичную меру рассеяния (см., например, Уилкс (391 с.
591 — 6141)'. Определение 15. Матрица рХр Б,= Е (Х» — Х) (Х» — Х)т (1.5) »=» называется матрицей рассеяния множества Х, причем Х= 2", Х»/и (1.6) »» есть вектор рХ1 арифметических средних. Матрицу Я также иногда называют матрыцей сул»- мы каадратое. "з Определение 1.6. След матрицы 5„называется статистическим рассеянием множества Х и обозначается з»-— (г5„= ~., '~.', (Х»м — Ха)а=,'Г', (Х» — Х)т(Х» — Х) Мера з» равна сумме квадратов расстояний л точек от средних по группе Х и представляет собой сумму (внут- реннюю по группе) квадратов отклонений. Можно по- казать, что п о Е Е (Х» Хт) т (Х Х») и »-» ь=» »<» н о У.. ~б (Х»,Х»).
(1.7) »=» з=» »<» Таким образом, когда оперируют следом 1г5„, имеют в виду расстояние в евклидовом смысле. Определение 1.7. Определитель ~5„~ матрицы 5„на- зывается статистическим рассеянием, соответствующим опРеделителю, и обозначаетсЯ зв = [5„~ е. Матрица коэффициентов корреляций )г=(г»») может бйть получена из матрицы 5,=(з»»), определенной уравнением (1.5).
Найдем диагональную матрицу (О(а 5„]=(зп, зав,..., зрн) и (О(а 5„)"=(з»», з,",,..., зч ). Тогда Д=(О)а5„]ь5„1О(а 5,]Ч (1.8) Лемма 1.2. 5„=0 (нулевой матрице) тогда и только тогда, когда Х~=Ха=...=Ха и Ха+~ —— ...=Х =0 для некоторого й~л, 1.э. Расстояние между кластерами н нх сходство Как мы увидим позднее, многие процедуры прн кластеризации совершаются ступенчато. Это означает, что два наиболее близко расположенных объекта 1, н 1а объединяются н рассматриваются как один кластер.
Это приводит к тому, что число объектов уменьшается н становится равным и — 1, причем один кластер будет содержать два объекта, а п — 2 остальных по одному. Процесс можно повторять до тех пор, пока все объекты не сгруппируются в один кластер. В рассмотренной по- * В статнстнке ~5 ~ также называют оаобн»анной ннснерсней.— Примеч. нер. 23 следовательной процедуре тюльзуются интуитивным представлением о расстоянии между объектом и класте- ром и расстоянии между двумя кластерами. Неотъемлемой частью задачи кластерного анализа является понятие оптимального критерия (целевой функции), которое позволяет установить, когда достига. ется желательное разбиение.
Для введения подобного критерия необходимо найти меру внутренней однород- ности кластера и меру разнородности кластеров между собой. Пусть 1=(1ь 1»ь °, 1„) и 1=(Хь Хъ", Х„,) обо- значают два кластера объектов, принадлежащих неко- торой популяции и. Пусть С=(Сь С,,..., Ср)т будет множеством характеристик, которые генерируют два множества измерений Х=(Х», Хз,...,Х,) и У=(Уь Уь..., Уиз), соответствующие 1 и Х.
Определение 1.8.. Обозначим через 0=(й(Х», У!), »=2,..., и», 1=1, 2,..., пз) множество всех расстоя- ний. Величину 0»(1,1) = »п(пй(Х;, У»), »'=1,..., и„ 1 1. 1~ ° ° п2 будем называть минимальнь»м локальным расстоянием (пеагез( пе(нЬЬог д(з(апсе) [395) между кластерами 1 и Х, соответствующим данной функции расстояния й. Определение 1.9. Пусть 0 = (й(Х», У») ) определено так же, как и в определении 1.8. Тогда Рз — — гаахй(Х», У») 1=1,...,и» 1=1,..., пз назовем максимальным локальным расстоянием (1пг(Ьез( пе(дЬЬог б(з(апсе) [234) между 1 и 1. Определение !.1О. Величина п, я~ Рз= ~, 'лч'., й(Х; У )/п»пз з-»» есть среднее расстояние 1225) между 1 н 1, соответст. вующее данной функции расстояния И.
Прн оперировании понятием статистического рассея- ния иногда пользуются следующей мерой расстояния между кластерами 1 и Х. .Определемие 1.11. Величину В,= "'"* (Х-У)т(х-у), л,+ла где л» ла Х= ~х»/и», У= ~ у»/па, »» называют статистическим расстоянием между кластера- ми 1 и 1'. Меру 11», очевидно, можно обосновать следующим образом. Рассмотрим два кластера 1 и 1, которые в свою очередь составляют кластер К, где К=1()1 (зна- чок () означает объединение); тогда по формуле (1.5) лг .ла Зк Е (Х» М) (Х» М)т+,Е (У» М) (У» М)т »=» »=1 л, где М= (Е Х»+У, У»)/(п»+па). .»-1»=» Поэтому 5к= ~ (Х»-Х+Х вЂ” М) (Х» — Х+Х-М)т+ »=» ~.~ (У У+У М) (У У+У М)т л» л~ ,1"', (Х» — Х) (Х» — Х) т+ ~ (Х-М) (Х-М) т+, »=» "а + и.
(у, у) (у у)т+ ч. (у М) (у М)т, .»=» »=» л, л, поскольку У(Х; — Х) (Х вЂ” М)т=Х (У» — У) (У вЂ” М)т=О. »-» »-1 Заметим, что М = (п»Х+и, У) /(п, +па), поэтому й л~ л« (Х вЂ” и) (Х вЂ” М) т = —, (Х- У) (Х- У) т (в~+ ля) ' « Легко видеть, что Ю» пропорциональна квадоату расстояния между «центрами» рассеяния множеств Х и У. — Примеч, лер, 25 ~ (У вЂ” М) (У-М) т=, (Х вЂ” У) (Х- У) ° ! 1 Окончательно и! яз ~'(Х М)(Х М)т 1. Ч'(У М)(У М)т з=! з ! л! лз л! лз - ~ — +.— 1(Х-у)(Х вЂ” у)т(лз+лз)з ' (лз+лз)з л! лз ( Х У ) ( Х У ) и лз+ля Последнее выражение будем называть гзатрицей межгруппового рассеяния. В результате получим: 5 +5 +, "'"з (Х у) (Х у)т ' (1 д)' ' лз+лз где 5! и 5з обозначают внутрнгрупповое рассеяние 1 и з.' Матрицу — (Х вЂ” У) (Х- У)т (1.10) я!+ля назовем матрицей межгруппового рассеяния, а следэтой матрицы 1Г (Х вЂ” у) (Х- у) = — (Х вЂ” у) (Х вЂ” у) я!+из лз+лз — статистическим расстоянием между кластерами 1 иХ.
След матрицы (1.10) называют внутригрупповой суммой квадратов (ВСК). При объединении 1 и з в один кластер К, очевидно, ВСК возрастает. Уравнение (1.9) статистики интерпретируют следующим образом: «оби(ая сумма квадратов равна внутригрупповой сумме квадратов плюс иежгрупповая сумма квадратов». Сумма 5з+5х есть «внутригрупповая сумма квадратов», а выражение (1.10) представляет «межгрупповую сумму квадратов», записанную в матричной форме. Подобным образом можно было бы построить новые меры расстояния между кластерами, воспользовавшись другими функциями расстояния, рассмотренными в параграфе 1.3«. з Напомним, что введенные здесь расстояния между кластерами опираются иа енклидоеу метрику. — Прямее лер.
26 Рассмотрим теперь несколько иной подход к проба . ме измерения расстояния между кластерами, Предпо ложим, что каждый кластер представляет собой выборку из некоторой генеральной совокупности (популяции). Обозначим через 1 и л функции плотности вероятности, соответствующие кластерам 1 и Х. Уоккер и Лангриб (3831 рассматривают различные многомерные формы мер расстояния и их метрические свойства. Их результаты сведены в табл, 1.3, где С обозначает класс всех р-мерных абсолютно непрерывных функций расцреде. лепна, л1У)У вЂ” класс многомерных нормальных распределений, л1УУх — класс многомерных нормальных распределений с одинаковыми матрицами ковариаций.
В таблице также приводятся метрические. свойства мер расстояния соответственно для трех классов функций распределения. Этн меры межкластерного расстояния могут оказаться весьма полезными в случае нормального распределения. В этом случае оценкам и и Х служат соответственно Х и 5', и меры табл. 1.3 могут быть легко вы« числены. Коэффициент дивергенции применяется в приложениях дискриминантного (классификационного), анализа 12261.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
