И.Д. Мандель - Кластерный анализ (1185344), страница 19
Текст из файла (страница 19)
Р~). Этот функционал (и алгоритм его минимизации, предложенный в [106] ) оказал большое влияние на дальнейшие исследования в силу высокой общности заложенных в нем идей. Концепция минимизации потерь, родственная задаче минимизации среднего риска [19], носит универсальный характер и может служить основой ряда экстремальных постановок в распознавании. 4.
Если для конечного набора точек функцию потерь выбрать в виде: !!г!!=(х! — х;)х, то Рз примет конкретную форму Р~ и сведется к минимизации суммарных отклонений координат объектов от центров тяжести классов (см. обсуждение Р!). 5. В [6] предполагалось, что А! определяется как мера близости между объектами в смысле теории потенциальных функций: !!„= ~ь (х,, х,)+й (х! х!) — зь (", ' ) ° где ь(х, . )='~!' х',,р',р! — потенциаль! ная функция, имеющая, например, вид: й!!=1/(1+4;)". В случае !г(х)=х получаем взвешенное евклидово расстояние. Известен алгоритм, оптимизирующий Рм доказана его сходимость при )т'- со к оптимальным значениям (математическому ожиданию потерь).
В теории потенциальных функций рассматриваются и некоторые другие критерии [6, !6]. 85 6 — 8. Функционалы Р« — Рм пожалуй, в наибольшей степени отвечают интуитивному представлению о качестве разбиения. В одномерной ситуации Р«и Рг связаны между собой: для квадрата евклидова расстояния при фиксированном Й обозначим критерии как Р( и Р(, тогда получим правило сложения дисперсий (см. обсуждение Р~). В многомерном случае минимизация Р« еще не гарантирует максимизации Рг (хотя и доставляет близкие к экстремуму значения), поэтому возникает нужда в комбинированных критериях типа Рь Возможны и другие комбинации: Р»=~', Р»'=~-'+~-'и др.
Для Р«предложен алгоритм оптимизации. Эти функционалы, как и Рм предлагались для потенциальных функций, но здесь трактуются как универсальные. 9. В(5~) интерпретируется как потери от того, что все объекты класса (например, управляемые устройства) управляются одним органом управления, может измеряться дисперсией параметров. Яг(й) — потери от необходимости создавать й управляющих органов. Р» представляет собой интересный пример содержательно обоснованного функционала; в принципе каждому объекту можно придать свое управляющее устройство, но тогда Щй)=ИГ(М) будет очень велико, почему и нужна группировка. Здесь, в отличие от Рм своеобразно назначение второго слагаемого (первое аналогично Р«): (Г(й) зависит только от числа классов, а не от их удаленности, ибо независимо от нее надо делать новые управляющие устройства.
10. Функционалы такого вида (см. обсуждение Р~) являются очень распространенными, если вспомнить, как часто в табл. 2.3 встречалнсь пороги типа )г, то ясно, что идея «гравитационного окружения» некоторого центра в различных постановках остается одной из наиболее плодотворных в кластерном анализе. Распространенный вариант критерия Рм — сумма расстояний до центра класса. 1! — 13. Три критерия Фридмана и Рубина отражают традиционные статистические представления об однородности как о категории, связанной с дисперсией (см. 1.1, Р~), обобщая их для многомерной ситуации.
х~ — вектор средних значений признаков в классе; Яь х — вектор общих средних значений; в',= ~ч~Р (д-х,)(»-»,)г ме5~ ! матрица рассеяния (ковариации) 1-го класса; В'=~ Ф'~ — общая й 1 ! -т матрица внутриклассового рассеяния, в ~, в~(»~-»)(»~ — ") — ма[=! трица рассеяния между группами, Т=~ (х — х)(х — х) — общая ма- «64 трнца ковариаций.
Как известно, Т= Ф'+  — многомерный аналог правила сложения дисперсий. Из этого разложения и следуют есте- ственным образом критерии качества разбиения. Понятно, что ми- нимизация г!!=1гК эквивалентна максимизации гу!=1гВ, т. е, с ковариациями существует точная зависимость типа «внутрн клас- сов — вне классов», в отличие от расстояний (см.
гз). 14. Для каждого объекта определяется мера притяжения 'Ч М;= — ~~ !!!! и мера притяжения точки к остальным объектам: а! ь!65, ! М; — Н М; = 2; !(„. Определяется стабильность точки: Я, = ' + Л/ — л! ! — а с(ез + ', где !!: — задаваемый порог для расстояний. г"!~ является й — М, первым пороговым функционалом качества, которые в дальнейшем получили развитие.
15. Р!(х, и!) — функция потерь 1-го класса, и! — некоторые пара- метры (например, центр тяжести класса), р(х) — совместная плот- ность вероятностей распределения. Функционал подробно изучен и представляет собой конструкцию весьма общего вида. Если счи- тать, что потери являются функциями только эталонных точек п!=и!, то установлена связь Р!ь с несколькими критериями каче- ства.
Если Р!(х, п)=(х — и!)', то Р!з=Е~ [104], что, как показано в [5, с. 127], эквивалентно реализации алгоритма й-средних (алг. 37 в табл. 2.3) для евклидовых расстояний. Если перейти в так называемое спрямляющее пространство ме- тода потенциальных функций (см. пояснение к Р~), такое, что г! = =)!т р(х[) (в него же перейдут эталоны ог и!), то можно сформиро- вать функционалы (для й=2): при г!=(Е(х) — о!) + ~„'Йрп сводится к гв, ! ! при Р!=(Х(х) — и!)~Еп совпадает с Рз.
Оптимизация производится [104] последовательно с помощью рекуррентных пересчетов методом стохастической аппроксимации. Алгоритмы, как и функционалы, носят универсальный характер и обеспечивают сходимость процесса для любого, в том числе беско- нечного набора точек; их вычислительная трудоемкость по времени и памяти невелика. Дальнейшее обобщение подхода см: в описании Езх. 1б. Функционал является одним из наиболее просто устроенных (как и аналогичный ему Рз). Удобство его в том, что минимизация Р!з автоматически приводит к максимизации Р'!з — суммы межклас- совых расстояний, что не имеет места, скажем, для Рм Гъ Сущест- венный недостаток — тенденция к объединению многих объектов в один класс, что обычно искажает реальную структуру.
Для его преодоления вводится другой критерий — гз!. вт 17, Поясним значения параметров, имея в виду, что все первичные показатели измеряются только на отрезках КНП (см. алг. 54, 55): и — длина участка между соседними точками; ]1 — длина участков, непосредственно примыкающих к рассматриваемому; л!— х — ! 1 ч~ количество точек в классе; р! = — „1,~л ' — мера близости х точек внутри класса; ! с~ . — средйяя мера близости й !=! классов; г! — длина участка, по которому проходит граница между 1 классами, и=, ~ч~~ х! — средняя удаленность таксонов друг от друе !=! 1 11пна га;л= ! ~ч'„— — мера «одинаковости структуры» внутри таксо!=! нов [37, с. 93]; лучше эту величину назвать мерой изолированности таксонов или мерой резкости разделения, так как ри!!и — минимальный из отрезков КНП, примыкающий к граничному ребру; "=а Ц вЂ” — мера «одинаковости» числа точек, а точнее — мера Ц !г !=! У равномерности распределения объектов по классам (при п!= ~ 5=1).
Хотя параметры а, Ь, с, т, р, !р могут характеризовать вес каждого из измерителей качества классификации, они обычно принимаются равными 1 [37]. 18. а ~~~Р [р(5 /х,) — р(5 /х.)], с(Н;!)= ( лпах( — '!), если и' (3 ~ стах, если с1, )Ы. с! и Пусть для каждой точки определена некоторая функция плотности в ее 1с-окрестности (алг. 47 в 2.3), например, количество точек в гиперсфере пь Выбирается й наиболее плотных кластеров, и делается начальная оценка вероятной принадлежности объекта к некоторому классу р(5!/х!)= — ', где р, = — мера близости между Р« ХР« ' ' 1+А, объектами. Величина пн — измеритель общей близости объектов на всем множестве классов: эта величина равна единице, если объекты с единичной вероятностью попадают в два разных класса, и нулю, если с той же вероятностью они в одном классе, Поэтому и!! можно трактовать как своеобразную «контекстную» меру близости объектов (см.
88 1,3, алг. 66 в 2.3). г(А!) измеряет «обычную» близость объектов, причем в особом, штрафном порядке: чем ближе объекты по !1!!, тем они ближе по Р(!1!!). Тогда видно, что г"!! представляет собой весьма интересную конструкцию: хорошим считается то разбиение, которое минимизирует разницу между общей (контекстной) и прямой близостью объектов.
По своему содержанию функционал отличается от предыдущих критериев. Е. Руспини трактовал г"!» в терминах размытых множеств; это повторено и в [34, с. 62 — 63]. Однако из построения видно, что такая трактовка не является принципиальной. Величины р(5!/х!) не обязательно рассматривать как степени принадлежности; с равным успехом их можно назвать оценками вероятностей принадлежности к классам или просто мерами близости объекта и класса особого вида (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
