И.Д. Мандель - Кластерный анализ (1185344), страница 21
Текст из файла (страница 21)
Райтом (см. Ры). Похожие «корреляционные соображения», но в связи с признаками, а це расстояниями описаны в 2.2.4. 35, Под иг понимается такая точка пространства, которая минимизирует ~ д(хь и,*). Это обобщает понятие центра тяжести евклим5~ довых пространств (Р4). Для концепции «потери от замены» (гзз— — гзз) величина и» может быть хорошим кандидатом для сравнения» м,* является наилучшим из а,"'. 36 — 38. р~ — вероятность 1-го класса, 1ч — ненормированный момент г-го класса; р~=[й,(х) 1(р,), 1ч=[хИ(х)Й(р„), где ܄— характеристическая функция класса, Ф вЂ” пройзвольная выпуклая функция. Критерий представляет собой функционал общего вида. В такой форме под него подпадает множество конкретных функционалов [14) . Даже частные случаи Ею и гз» также имеют весьма общий вид. Пусть ~~Вц[~ матрица весовых коэффициентов, Ац — некоторая характеристика близости классов (расстояние, потенциальная функция и др.).
Тогда гм в разных случаях принимает форму средневзвешенной дисперии (см. Г~), общего разброса классов (см. гт), разницы расстояний (см. г») Построены специальные рекуррентные алгоритмы минимизации гзм также имеющие общее значение; доказана их сходимость в широких условиях, в том числе для потока наблюдений; установлен вид. разделяющих функций. 39. Если задан порог Н, то считается общее число нарушений условий правильной классификации Л; под правильной понимается такая, что внутри каждого класса «(п(с1, а межклассовые расстояния больше о. Ез» представляет относительную ошибку классификации (в [23] формулы не приводились, так что нами дан собственный вариант критерия).
В процессе оптимизации реализован синтез г-связывающих агломеративных процедур (см. 2.3) и алгоритмов типа «объединение», «перемещение» (см. 2.3.3), поэтому происходит настройка параметров Ы и г. В целом идея функционала является некоторой «вариацией на тему» критериев Р~м Рм, Р~м менее четкая 93 в формальном отношеннн, но, возможно, более гибкая практически. Работа идет в диалоговом режиме.
40. 5 — пространство всевозможных покрытий исходного множества объектов Е (например, множество непересекающихся разбиений); Š— пространство представительств (напрнмер, множество эталонных объектов нли центров классов); я — функция представительства, отображающая элемент хЕЕ в Е; 1 — функция назначения, относящая объект хЕХ в 5 (т. е. зачнсляющая объект в класс); 0(х, 1) — мера сходства между объектом н представителем. Общая формулировка критерия: отыскать такие 5 н Е чтобы они имелн наибольшую степень адекватности, соответствовали друг другу в и .определенном смысле: г„,=~ в(х,, ~,) В зависимости от выбора 5 н Е ~=! возникает множество конкретных функционалов качества.
Ограничимся случаем, когда 5 — множество разбиений (возможны иерархические структуры и т. д.), Š— множество единичных представителей класса. Тогда в схему Е4~ укладываются критерии Еь Е4, Ен, Ем, Еы, Езь Езз, Ем-м Ем, Еэз, Еы, а для квадратов евклндовых расстояний добавляются Ез — Еь Здесь под единичными представителями понимается либо некоторый реальный объект нз класса, либо искусственная точка класса (центр тяжести, экстремальная точка нз Езз н т.
д.). Возможны усложненные постановки двух видов: 1) расширение круга используемых расстояний 0(х, 1) (см. [29, с. 348], где приводится пример функционала, учитывающий нееднннчный вес каждого объекта, так называемые адаптивные расстояния [29, с. 38] и др.); 2) использование в качестве представителей не одного, а нескольких элементов класса [29, с. 35]. Почти любые задачи анализа данных могут быть сформулированы в терминах критериев описанного типа. Универсальным оказывается и способ нх оптимизации — метод динамических сгущений (ММ0), ориентированный на поиск некоторых заполненных окрестностей вокруг представителей.
41. Критерий представляет собой меру близости между результатдмн прямой и обратной классификации н подробно описан в 3.3. 42. Исходное множество объектов разбивается на два (нлн более) равных подмножества случайным образом, в каждом нз которых проводится каким-лнбо способом кластеризация (в [42] предполагалось минимизировать внутрикластерное расстояние). Близость результатов говорит о непротиворечивости кластеризации.
Эта идея восходит к нзвестным постановкам 60 — 70-х годов о случайных классификациях (алг. 13, 56 в табл. 2.3, см. также 2.2.3). Далее, поскольку непротиворечивым классификаций может быть несколько (для разного числа классов и набора признаков), вводится второй критерий волидносги — соответствия классификации некоторым экспертным представлениям. Два критерия сочетаются с общими принципами метода МГУА (группового учета аргументов) [20]. 94 43.
ап)0, ~ ««=~ — мера близости 1-го объекта 1-му классу; Ьи~)0, ~ ьл= ~ — вес прототипа, т. е. «степень прототипности» /=! 1-го объекта для прототипа Рго класса; 4; — расстояние между объектами. Функционал характеризует, видимо, наиболее сильное обобщение в теории размытой классификации: размыта степень принадлежности объекта к классу (см. Рм, Р»„Р»») и размыт сам представитель класса — каждый объект может быть в разной степени прототипом того или иного класса и одновременно «рядовым членом» этого и других классов. Результат классификации выдается в виде двух матриц А„„» и В„„», совместный анализ которых позволяет детально изучить структуру множества. Предложен специальный алгоритм минимизации р~».
44. l — множество всех номеров объектов мощностью )У; Ф'(!в множество представителей классов разбиения; а — соизмеряющий » коэффициент, который удобно принять в форме: =2~ л 1н(н — 0. !С/ Критерий отличается способом учета составляющих «вне и внутри»: рассчитывается не общая сумма расстояний внутри классов и между классами, как обычно, а расстояния до представителей классов, чем он напоминает Р„ Р»м и полностью вписываетсЯ в общую схему Р4» Однако для г«4 известен алгоритм точного решения задачи классификации, что существенно для критерия такого общего вида.
45. Точная постановка включает следующие ограничения для л кРитеРиЯ качества: ~~Р„«ч=~; «н~к,; '~~' 9 =ь; и, х«аЮ,0 9 =~, (=! ю 1 если Рй объект является представителем (фактически центром) класса. х„=1, если )чй объект ближе всего находится к /-му представителю. Таким образом, критерий реализует очень распространенное понимание кластера (множество объектов, ближайших к некоторому центральному), которое раньше часто встречалось. Отсюда и название метода — медиана в одномерном случае минимизирует сумму расстояний точек до нее, а среднее — сумму квадратов расстояний. Тем более важен для такого естественного критерия точный алгоритм, найденный методом ветвей и границ. Точный метод рекомендуется применять прн пк 30. 46. Здесь д;= 1, если Рй объект принадлежит множеству помеченных объектов (х~ ~Х), нулю — в обратном случае, 1»« — степень принадлежности 1-го объекта к 1-му классу, Ги — степень принадлежности помеченного объекта к классу, которая представляется самим 95 исследователем с соблюдением свойства,, " .
Теперь ясен смысл функционала: первое слагаемое (практически совпадает с Рьт) минимизирует размытую сумму квадратов расстояний до центра, а второе представляет собой взвешенную по квадратам расстояний сумму отклонений расчетных значений 1х от заданных априорно. Другие модификации критерия в )!45) связаны со взвешиванием двух этих слагаемых и с введением в расчет расстояния Махаланобиса. Численный эксперимент показал хорошие разделяющие способности метода, особенно заметные при использовании расстояния Махаланобиса. Успешно разделились кластеры, расположенные в форме креста — сложный для распознавания случай, на котором потерпели неудачу иерархические процедуры из )123], тоже выполнявшиеся с настройкой параметров по данным выборки (см.
2.2.4). 3.3.3. АЛГОРИТМЫ ОПТИМИЗАЦИИ В работах, ссылки на которые приводятся в табл. 2.3, предлагаются не только функционалы, но и алгоритмы их оптимизации, т. е. читатель при желании может подробно ознакомиться с теми конкретными особенностями вычислений, которые сопутствуют данному критерию. Здесь нет возможности описывать многочисленные алгоритмы, поэтому попробуем ограничиться некоторыми достаточно общими схемами оптимизации, пригодными практически для всех критериев качества. Естественным образом все алгоритмы классификации можно поделить на две неравные группы: в первую, большую, попадают методы, не гарантирующие глобальный экстремум функционала качества, во вторую, намного меньшую,— точные процедуры, приводящие к глобальному экстремуму. В первой группе можно выделить два наиболее важных типа процедур — рекуррентные алгоритмы оптимизации и алгоритмы, увеличивающие значения функционала на каждом шаге.
Рекуррентные алгоритмы оптимизации. Основная идея методов в том, что с учетом специфики функционала выбирается некоторый набор настроечных параметров, задающих разделяющие поверхности; параметры на каждом шаге работы рекуррентно пересчитываются. Для остановки процесса требуется стабилизация этих параметров. Такие алгоритмы нуждаются в специальных доказательствах сходимости и всегда определены для строго фиксированного круга критериев. Эти критерии, как показали специальные исследования, носят универсальный характер.
В первую очередь к ним относятся функционалы минимизации среднего риска Ри и связанные с ним Рт — Рм Рш, для которых обосновано использование типично рекуррентной процедуры метода стохастической аппроксимации. Уже этот широкий круг показателей характеризует важность алгоритмов такого рода. Новое продвижение в данной области сделано в 114), где разработаны рекуррентные процедуры для оптимизации функционалов общего вида Рм — Рм. 96 Существенной особенностью рекуррентных процедур является их последовательный характер, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
