И.Д. Мандель - Кластерный анализ (1185344), страница 18
Текст из файла (страница 18)
алг. 54 в табл. 2.3). Итеративное перераспределение объектов Р. Торндайка (1953) означало оптимизацию внутриклассового разброса [291. Эти работы, однако, не имели особого резонанса. В статье Дж. Уорда (1963) ' Мандель И. Д. Взвешенные средние и корреляции//Вестник статистики.— !986.— № 7.— С. 53 — 58.
76 фактически излагался оптимизационный иерархический алгоритм (алг. 8 в табл. 2 3), но акцентировка внимания иа оптимальности каждого шага, а не разбиения целом ставит эту часто цитируемую работу несколько в сторону от «чисто оптимизационного» направления. В 1965 г. вышла статья М. И. Шлезингера [106], в которой впервые точно сформулирована статистическая и оптимизационная задача обучения без учителя и предложен функционал качества классификации весьма общего вида.
Этн идеи, судя по всему, «носились в воздухею в 1965 †19 гг. появляется большое количество работ, в которых фактически закладываются основы важнейших теоретических конструкций распознавания вообще, распознавания без учителя — в частности. Для задачи кластеризации здесь наиболее важны два направления: теория потенциальных функций, развиваемая в трудах М.
А. Айзермана, А. Г. Аркадьева, Э М. Бравермана, А. А. Дорофеюка, И. Б. Мучника, Л. И. Розоиоэра и др. [6, 11], н теория стохастической аппроксимации в задачах распознавания, разрабатываемая Г. К, Кельмансом, Я. 3. ((ыпкиным и др. [104]. Кроме общих критериев качества, в этих н других работах предлагались достаточно универсальные алгоритмы оптимизации, ие потерявшие своего значения и по сегодняшний день. В последующие годы шло интенсивное развитие обеих сторон проблемы: разработка новых функционалов качества н новых алгоритмов их оптимизации. получили распространение естественные в статистическом отношении критерии Х Фридмана и Дж.
Рубина [32]; В. Н. Елкиной и Н. Г. Загоруйко был построен функционал, в котором авторы старались максимально учесть представления о качестве классификации [37]; в работах Е. Руспнни, У. Райта и др. разрабатывалнсь критерии качества для нечетких постановок оптимизационных задач кластеризации [34, 84, с. 208 — 247]; А. Н. Колмогоровым предложена весьма общая схема формирования критериев качества [5]. Во второй половине 70-х годов получили известность работы Е. Рольфа, Ф.
Бейкера н Дж. Хьюберта, Г. Маллигана по формированию критериев, ориентированных на некоторые корреляционные свойства разбиений; критерии для размытых множеств Дж. Беждека и Дж. Данна [39[; схемы оптимизации Э. Диде [29], М. Жамбю [135]; исследования В. Л. Купергнтоха, Б. Г. Миркина, В. А. Трофимова и др. по качественному факторному анализу, приводящему к теоретически обоснованным критериям классификации (см. 2.3.4), н другие исследования, частично отраженные ниже.
В последний период результаты общего характера получены В. В. Бауманом и А. А. Дорофеюком в [14], где предлагается алгоритм оптимизации функционала универсального вида и др. 2.2.2. КРИТЕРИИ КАЧЕСТВА КЛАССИФИКАЦИИ Практически во всех упомянутых и других работах приводятся не только сами критерии качества, но и соответствующие им алгоритмы, гарантирующие обычно локальный экстремум функционала. Имеется и небольшое число точных методов решения задачи классификации, где обеспечивается глобальный экстремум.
Методически удобнее разделить изложение материала на две части, хотя в оригинальных работах, они обычно сливаются: сначала рассказать о критериях качества классификации, а затем об алгоритмах их оптимизации. 8 табл. 2.5 приведено краткое описание отобранных нами функционалов, которые разбираются далее по тексту. Описание критериев качества классификации (' дано в соответствии с табл. 2.5. Обозначения сн. в табл. 2.2) 1. Критерий минимизации внутриклассовой дисперсии — один из наиболее распространенных в кластерном анализе. С одной сто- 77 6 н О ф а н л х Ц ф о х Н,т Х З н Ф ° 3 т н т т О.
т фо о нн з О Я ф 33 $ т и 3О ф .-О Х3 О. Ф н 9 ФБ т т О 6 63 ф О. 3О т 36 т » в н О 63 т х о. 1 ' 33 ! х" И И !! 78 л т » Ф 6 о ттн 6 тхт т т 63 х в т Ь" т т о»т ф ~ВОФ О ф 3. 3 ф т ф т т О. т от 3 Ф, фо ~ Р ФЯ ф от "тт т7 О.т т т н 63 н т н т 3 т 3 Ф ~ о й 6 И О. 3 » т Ф 6 ф т И т 8 О.
3 х -з н Ф х Ф1 ОХ Р' '33 х х О. х 'к 3т" Я Ь !1 й 3 '" ~л~ 3 Ф о и й о а т о о о 63 Я о жт 63Ф т у твф о:т атф а т 3 о н и ф 6 х В \6 "' о н н О. 3 » т Ф ы 63 3' 63. т т т о — Ь О. н и 36 о И'я а т 63 О. и Й 3 О х О, «с ОС3. „ х со Сс о 63, 6' х 3 й!66 63 О3 О3 о х х Ю х 63 й 3-,Х хох Ху 6 сх и Ь й Р О 6' и 3 о л 3 о х О 3" л О с ь + ос Сс р„~ аа 33. х о х О л х о о М Й э О.
о х з й сс О хх 33, С о О х О. 3 о о и '8 Ив !! о о о О О о сх н О.х Фр их о ф 6 ьо й ф О и $ О. ц 'О э 63 йо 3 О О О о о О Ф х Ю 3 ИО О 3 $ й о -и гЗ !! о. 63 ~С О 33 о х 3 с х й о 3- О. й О о а о — о — о 66 О о 63 сс й «У И 3 !! х Ь а й 3О О !! 6.
- о й Ф о Х И Х Х ой \" ФЗ Х й Х 6 » 66 в Х ф й* й О ~" й' бй ~ айй ~ н о ФХХ О 6 ффф Х Ф ФФХ ч н Ф о О. 6" Ф Ф ф О о и Х й 6 2 о Х Х » О о ф м Х Ф Х О ~с~ о о 6 Ф 6 О Ф й 6 и н ф Х 6 6 ф О Х о о Х .6 ф й Х Х н ф й 63 Х Ф н 'О Фо о ф '66 с 6Г 6. 6» ." ~6~ ~~ !! Х н н Й Х о Ф Ф ф Х О Р н Ф О О. 6 сф н х айф с х 66 й .6 6О й н о Р 6" й Х Ф й Ф а ай О ф 60 -Ж ф Х й Х Ф Р 6" а Х н Ф Ф и н И О. О. й й и Х О. Ф Х «о "о Р~, С Х ф Х й й Х е ъ ! О О.
66. Ф~„~И !! й ф $ о фф Фа н Ф ,о й 6 »'8 М Х Ф 6 й $ Фс Х 66 6 Ф 66 Х О. Ф н О н йй оД 6С О6 о + 1 И ь а Ф о ф 6 6 1О 6 О6 й ф но ХИ Х Х Ф о Х фс н О. О е В ~! Б Х й Ф' о о Ф х Ф Ф 3О -Й х х Ы аЕ 3Е= е о о 'Ф С о.
н с~ Ф Е Ф о Ф Ф о Е о. х ох И ФФ Ф Е е 3О х + И + о. Ъ ю о о Й 5 Е о + О3, Я' о Ф" Е й о Ф Й '8 Ф 3о Ф ) ,Ф ФО о До Ф" о ох Ф Е Е Ф 2Ж о Ф о + ' Ф 3 Ф 1~ й Ф Ф Е о о И" р о. о Ф О3 ъ Т ! й. х Е Е и й й. й й '2 ~с охй ф А о" й. й Е о э й о" О Х ф ~ц о х Е й й й. о х й. 2. С4 х о цр хф Я о1 й. М Е о о а 3 ы ф х й о х й л а о 3 Р5 й х ое н 2! Е х Е. ! хо Иш 2 Е о Е о. -Й пй й ~ о о Ей ах И 1 х 2 й Ы 2 + М й й Х х й Ф о и 3 » о й Е !! й.о ха а х о й а а й й о 2 д $ ФЕ <.~ ео Ь '-3 7~ х й 2 Йв ай й х % Е х 2 о 3 Д й Е х.хф й, о 1! ЕЕ Б8 ОЯ ох 2 Е Р х 2 6 8 й! лй $ а хо Е Е Е о Р В 'о 'к' х ~2 И ~а, ь й 5 й.
а й й о Д о. о о ~а. о ~ц З ж Р й~ й "'Ф оЯ со Ф " со ь ~„ м- х М о Ф ж И О Ф Й О й 63 ~ о рИ ! ,а Д $ -Л $' ~ Ф к е ~й П э к О. Р- ЗЬ й~ !! ~л~ ! !! вз ! о .4 с ~6 а~ "~~и ~ И Й Я Ф а Ж 2 ~~ ~ о Ю д Ю \ К".; фх о Й ~~~ л О Б 4~ $" ~- ~ 3 ~О с~ ~ а. М Ф йх ! о ~ к ~ Ю 6$ М о щ о О О. О $" Ю ж. с.' ~~ ~О СЬ | а~ ~ й Ю щ ~ я Ю Ф й о Ф 2 4ц ц ц~ Ю Я Ь эм~ $ й ~ й ы~ $ д, И в.
«~ н 3 й р о па ~ ~а й ЬЗ Я Ф иФ „й ~а )~ а ц Я й Ф о х о с » л н о З З й й й о й «З « 'с2 .с~ о ф о" ф х 2Й о" фф х~ ф ф ф СЧ ° оф < х а л н о х о о хо Мю и З З ф « а» ф 8 х й о х -в и ф ~З х 5« !! ф хо ф « й о н «« З З ЗЗ ф ф о о, й Ц ф й ф оо !!хх н и 8'8 й й а « фно Зфн «% ф ф ф а й о1 й хо « И« 8 й ~~ аъ ! + ой 'й8 ш И '- $ н й х О З й й й ф ф х о й ( о ой о ф ай н й Щ й Е 3 н н й а о $ х ф ф ф й оЗй О ой о. Ь фД Е= со ОО о.ф ф ~й й + Зй ф Й.
ф ( «~7~ о р~ М й й 1 х в н ф 1! х 7~ 8 й ф ф Е ф ф о 8,'8 роны, он примыкает к строгим задачам многомерного анализа (дискримннантного, дисперсионного и т. д.), с другой — к точным постановкам аппроксимационного типа (см. 2.3.4). Естественная сфера его применения — выделение кластеров в евклидовом пространстве, имеющих шарообразную форму. Точный алгоритм Р. Дженсена использует методы динамического программирования. Дисперсионный критерий тесно связан с квадратичными функционалами, использующими евклидово расстояние.
Известно, что — ~ч'', !!~ =~ч", !!~ [91, 54]. С учетом этого можно выписать 2 г х(Р~ — !) ч П ~(! I=! Ъ' Ь,— х!), следующие соотношения, обозначив через у! величину ~ ~-~ ' ' !=! ~~5 т. е. квадрат отклонения от центра тяжести класса: Р! = т!/л! ! Р! ~>О ~1!! ~~ 7!' лз= ~ ~ ) т! , 'Р~= !=! !=! ! ! ! Величину Р4 можно считать взвешенной внутриклассовой дисперсией. 2.)х[! — ребра кратчайшего незамкнутого пути, входящие в кластер '[см.
обсуждение алг. 54, 55 в 2.2). ! 3.))г!! — функция потерь от того, что объекты аь а; со значениями х! и к; отнесены к одному классу; фх!/х!) — условные плотности распределения вероятностей в классе Я!; р! — априорная вероятность класса. Минимизирует суммарные потери при классификации, для работы требуется конкретное задание функции потерь и способ определения вероятностей (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
