И.Д. Мандель - Кластерный анализ (1185344), страница 20
Текст из файла (страница 20)
алг. 49 в 2.3). 19. Хотя методы разделения смесей не являются предметом нашего рассмотрения, приведем этот функционал общего вида, поскольку он тесно связан с некоторыми ранее рассмотренными критериями. Предполагается, что каждый класс является выборкой из нормально распределенной генеральной совокупности с неизвестными параметрами х! и Х! (вектор средних и матрица ковариаций), которые требуется оценить. Р!» представляет собой функцию максимального правдоподобия для данной задачи.
Как можно показать [6, с. 97], в разных конкретных случаях г"!» сводится к известным функционалам: если ковариационные матрицы равны между собой и известны, то г!д=Е!», где !1 в Р!!! — расстояние Махаланобиса; если 2! равны между собой, но не известны, Р!» = г"! !, если У.. не равны между собой и не известны, е!»=Ц ~ Ф!~=л„(мы не рассматривали этот крите- Ы! рий в тексте в силу его некоторых неудобных свойств). Как видно, интуитивно хорошим критериям можно придать строгую вероятностную обоснованность. 20. Максимизация минимального межклассового расстояния, в отличие от предыдущих критериев, ориентирована на непараметрическую характеристику разбиения, связанную с порядком расстояний в матрице.
Критерий подкупает своей простотой и формальным изяществом. В зависимости от выбора способа измерения р!«возможны различные алгоритмы; в [67] предполагается наиболее «чистый» вариант: расстояние определяется по принципу ближнего соседа. Имеются локально-оптимальные алгоритмы минимизации г»м 21. Введем обозначения: ха=1, если а, Р5!, 0 — в обратном случае; у! = 1, если классификация ведется на д классов, д = !,й, !г= ~, и ~ч', ~ х;!д!!»„' г(Ф) — некоторая функция потерь от разлид=! ! ! !«! чия объектов внутри класса, заданная на всем множестве раз- зз биений множества (фактически при известном й !!т=г"!5); Ф вЂ” функция потерь от числа классов; 1)(5) — потери от разброса л! 2 численностей объектов в классах, !2(з)=~~~~ — [~ хт — — ), при этом ! / ЛГ~ 1=! =! Х К! =Л1(Л . В этом функционале объединяются требования к хорошей классификации из Рх (два первых слагаемых) и из Р2 — О(5).
В [1! 1] предложен точный алгоритм минимизации Р21, основанный на методе ветвей и границ, и обобщающий алгоритм Дж. Антонисса (см. г!5). 22. Отличается от г2! только членом О(5), но это позволяет точно (методом ветвей и границ) решать задачу при неизвестном числе классов. Балансировка двух критериев здесь происходит в силу монотонного убывания Ф' при росте числа классов д.
23. Характеристики критерия основаны на общей концепции сте- пенных средних, разработанной А. Н. Колмогоровым: Рл!= н — — и'." ° — средняя степенная мера внутриклассового рас=[ — ~ —,Х '] !, ! 1 ! к,е5, сеяния (при г=! совпадает с гл); 5; — кластер, содержащий точку л,~~ а,; и,— его мощность, г — показатель степени. 2 =[ — 'эх / — '1] ° 1=! средняя степенная мера концентрации точек: г,= 1 при объ- единении всех точек в один класс, 1/(М вЂ” 1) — при М клас! сах. Если г= — 1, г 1= —, где й — число классов разной мощи' и л, л, ности в разбиении; 2 =~' — ' !к — ' информационная мера кон! 2 и Л1х , л,, 2 ЦвитРаЦИИ! х = л!ах ~ — 1~; 2 = л!х! [ — ') ! 2,= — 22 л2.
1~,~и[,,Ч) -",м, и[, Ч)' ~=! Как видно, 1, есть функция внутриклассовых расстояний, а г,— функция только от относительных частот плотностей классон. Поэто- му аддитивное соизмерение двух разнотипных величин в едином критерии не оправдано, требуются некоторые веса. В Р22, в частно- сти, можно положить а=1, 8= ' (рекомендуемое в [5, с. 93] 22л,! У(1У вЂ” ! ) значении 8=! в силу указанного несоответствия вряд ли будет удоб- ным, см. также [69, с. 148] ); существует мультипликативная форма: г22=(' — [5]. Характеристики типа 1, и г, носят универсальный м характер и могут использоваться в задачах классификации в бо- лее широком контексте, чем описанный [5, с. 83]. 24.
ри — функции принадлежности 1-го объекта к 1-му классу (см. описание г!5), рл — расстояние точки до центра класса, р, — рас- 90 )1,2) И,З) )2,3) — о 9! стояние до общего центра совокупности (имеются в виду евклндовы расстояния). Величина 1— -Р24 представляет собой взве- 2 1 шенный вариант корреляционного отношения. В отличие от Рм, з 2 Рм и др. Ры сравнивает не внутриклассовые расстояния с межклассовыми, а внутриклассовые ))з) с общими, чем напоминает Р)1.
Установлены хорошие свойства, а Р„ относительно целого набора аксиом. ),З 25, 27, 28. Критерии устроены весьма своеобразно. Для уяснения смысла величин 5+, 5 1,4 о о рассмотрим пример. Пусть матрн- 24 ца расстояний имеет приведенный вид и разбита на два класса 24 (отмечены линиями). Требуется попарно сравнить все межклассовые и внутриклассовые расстояния. Для этого построим матрицу попарных сравнений расстояний (рис.
2.21), в которой сначала идут расстояния внутри кластера (1, 2) †(2, 3), затем расстояния между кластерами (1, 4) — '(3, 4) и, наконец, внутри следующего кластера и т. д. Выделим блок внутрикластерных расстояний; в нем никакие сравнения не проводятся (стоят нули); не сравниваются между собой и межкластерные расстояния (тоже стоят нули). Сравниваются только межклассовые расстояния с внутриклассовыми: если межклассовое расстояние больше внутриклассового, в матрице ставится единица; меньше или~анно — ставится минус единица.
Число единиц в матрице и есть 5, число отрицательных единиц — 5 и — сумма всех чисел, числитель Р24 и Рм. В примере 5+=3, 5 =6. Большая величина 5+ говорит о хорошем качестве разбиения— большинство межклассовых расстояний превышает внутриклассовые, рост 5 свидетельствует о плохом качестве (что видно из при- )))(Ф вЂ” ! ) веденного примера с неудачным разбиением). п4= — общее 2 число расстояний, т. е, число строк и столбцов в матрице сравнений; ИЮ(4~ — )) ! — число нулевых элементов в матрице.
Очевидно, 2 если все объекты объединяются в один класс (тогда значение Ры будет плохо определено), т. е. 1 введено в формулу для корректировки знаменателя: оно предотвращает выделение слишком больших кластеров. Данная нормировка не представляется особенно удачной даже в идеальном случае, когда 5 =О, Р24 не принимает изза нее критического значения, то же можно сказать о Р21. Наиболее удачной конструкцией является критерий «гамма» Бейкера — Хьюберта.
Его знаменатель представляет собой обшее число единиц любого знака в матрице, поэтому в случае идеального разбиения — гм=1, в случае самого плохого (5+=0) — Рм= — 1. Но зато критерий никак не реагирует на число классов и их заполненность, как Ргь. В целом критерии данного чипа весьма привлекательны. Их существенным достоинством является непараметрический характер, что важно в условиях неустойчивости расстояний к допустимым преобразованиям (см. 2.4). Другим преимуществом выступает наличие естественных границ изменения (особенно г„).
В зарубежной литературе критерии используются весьма широко. Недостатком является некоторая громоздкость в вычислении. 26, 30. дя —, сумма внутриклассовых расстояний, 4(з — сумма межклвссовых РасстоЯний, [„и 1в соответственно — количество внутриклассовых и межклассовых расстояний, ш)п(4(х), шах(4(я)— максимальное и минимальное значение расстояний. Как нетрудно видеть, оба показателя являются простой модификацией г«. 29. Критерий Р«» представляет собой, видимо, наиболее распространенный и изученный вариант экстремальной постановки задачи кластер-анализа в терминах размытых множеств (см.
описание Ры): 144(х) — функции принадлежности классов, о4 — некоторый типичный представитель (фактически центр) класса. Функционал является размытым обобщением г4 и отчасти Рм. В [39, с. 208 — 247] описан алгоритм типа й-средних оптимизации г»». 3!. Критерий подробно изучен [62 и др.]. Оптимальные по нему разбиения удовлетворяют естественным требованиям, предъявляемым к хорошей структуре (см. г«, Рп). Классы являются сгущениями в смысле 2.1. Существенно, что гм появляется в общей теории качественного факторного анализа, развиваемого авторами, как результат определения так называемого представлявшего фактора.
В рамках этой концепции можно найти оптимальное значение 4(, т. е. решить задачу в режиме свободной классификации. Подробнее обсуждение см. в 2.3.4. 32, 33., Функция г( °, ) характеризует некоторые потери, возникающие при замене одной точки класса а,' на другую этого же класса. Частным случаем функции может быть расстояние, тогда гз»=Ем (происходят замены каждой точки на каждую другую точку из класса); если г — квадрат расстояния, то Р««=Ем если замена происходит только иа центральные точки а,* и г — некоторая квадратичная функция, то гзз=г4 или Рзз=гш В [38] рассматриваются также модификации критериев: в г»» производится замена центрального объекта на самый далекий в классе: г»з=х4 (а,, «4~4 ' ' "4»=~ г4 замена объектов происходила 4=1 4 =! по цепи, из которой оставлено наибольшее звено 1; гэз минимизи- 92 рует сумму длиннейших ребер внутри таксонов в КНП (см.
Рь Г„). В целом идея «потери от замены», развивающая старую идею «потери от объединения» (см. Рм Рм), достаточно универсальна и использовалась впоследствии (см. гз»). 34. Обозначения показателей см. в гз~, .з« вЂ” среднее квадратическое отклонение всех расстояний. Функционал представляет собой коэффициент точечно-бисериальной корреляции между двумя признаками: один, дихотомический, задает разбиение расстояний на две группы — межклассовые и внутриклассовые; другой — сами расстояния (М'-мерный вектор действительных чисел). Очевидно, чем сильнее связь качественного и количественного признаков, тем лучше классификация. Впервые идея определения корреляций на множестве расстояний была выдвинута, видимо, Е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
