Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика (1027378), страница 57
Текст из файла (страница 57)
Это решение использот =! вано в описанном (см. п. 7.5.2) алгоритме Беждека. 10.3.7. Модель алгоритма (Л (й) — «)-средних. Модель 10.3.5 описывает ядерный алгоритм нечеткой классификации, поэтому точно так же, как был осуществлен подъем алгоритма А-средних до алгоритма (й — «)-средних, можно от алгоритма Л (й)-средних перейти вверх по нашей иерархии до алгоритма (Л (А) — «)-средних. Таким образом получается модель а.чгоритма, отстоящая от модели 10.3.1 уже на два уровня. 10.3.8.
Модель алгоритма (Л (!) — «)-средних для весовых функций Беждека. Спускаясь вниз по уровням иерархии от модели 10.3.7, получаем: Ло = Л (2) = (2 =- гтЛ, + гзЛ,, ге ~» О, г'+ г' = 1); 5о = (э; О-+. Л (2)); Уо = (!у+ (1 — 1) У (з): 0 ~ Г ~; ( 1, У'Е )г«) и У" (~) — изолированная точка, т. е. !'о— конус над гт«с вершиной К ( ). Далее, Ь вЂ” часть множества линейных отображений Л (2) в !', состоящая из всех отображений, при которых вершина Л, переходит в точку У (*). Классификатор К и дескриптор 0 задаются формулами: ,„+,(Х) =(з„егл(Х), з„,+,,(Х)), где 3 ) 1 з +к1(Х) = 1+ ~ 7! ~, з„+ьз —— г !! х — !'„!! ~ "— ' 1 « ~т+ьм ч', 1,„+ь, (Х) )а Х (Л хе о ~ш+1 1 (Х) хео В заключение отметим, что при а-~ 1 от модели 10.3.8 переходим (спускаемся по иерархии) к модели !0.3.3, а, полагая от модели 10.3.4 — к модели 10.3.8.
10.4. Исследование сходнмости алгоритмов АК О п р ед ел е н и е !0.7. Модель ААК называется коррекгпной, если 1) для данных зЕ Яо, ! Е Е и р Е Р оператор К меняет состояние только подмножества р Е О, причем это изменение полностью определяется описанием 1.„ 2) существует интерпретирующий функционал Е, ограниченный снизу на данном движении алгоритма, такой, что для любого з ) 0 и т - т, существует 6) О, что, как только Р (з, 1„) — Р (з +ы ! е,) ( 6, то р (1, 1,)~ з (см. определение 10.5).
Далее, говоря об ннтерпретирующем функционале Р корректной модели, все~да будем подразумевать, что он удовлетворяет условию 2 определения 10.7. Л е м м а 10.1. Пусть Р— интерпретирующий функционал корректной модели ААК. Тогда из равенства Г (з ) =- Г (з з„( +,! следует, что ! = ! +, для всех т » «що. Оказывается, что для болыпого класса ААК верно и обратное утверждение.
Л ем м а 10.2. Если множество значений ннтерпретирующего функционала Г конечно, то в модели ААК условие 2 определения ! 0,7 выполняется тогда и только тогда, когда из Р (з, ! ) = Р (з,„+„! .„) для т )~ т„следует, что 1 = 1„+,. Т е о р е м а 10.1. Если множество значений интерпретирующего функционала Р корректной модели ААК конечно, то в движении этого алгоритма последовательность описаний 1„..., ! стабилизируется, т. е. существует такое т„что ! = 1 +, для всех т л глз. Доказательство предыдущих результатов использует только свойство 2 определения 10.7. Следующий результат показывает роль свойства 1.
Т е о р ем а 10.2. Если в движении алгоритма, описываемого корректной моделью, последовательность опи- саний 1„..., 1 стабилизируется начиная с номера т„то соответствующая последовательность состояний зо ..., з задает стабилизирующуюся классификацию выборки О, т. е. как только Хс р„с: О для т ) т,, то з ~> (Х) = = зщ~.„к (Х) для всех и ~ 1. В случае когда оператор О не зависит от первого аргумента, т. е.
задается отображением Зо — Е (это имеет место во многих алгоритмах, например во всех алгоритмах МДС (см. 5 7.4)), то из конечности множества 5о и теорем 10.1 н 10.2 следует стабилизируемость движений алгоритмов, описываемых такими корректными моделями. Следующий результат лежит в основе исследования сходимости алгоритмов последовательного типа, описываемых корректной моделью для бесконечных выборок (ср. (139)). Л е м м а 10,3.
Пусть (з„1,), ..., (з, 1 ) — движение алгоритма, описываемого некоторой корректной моделью. Тогда для любого з '- 0 и натурального У существует номер т„ такой, что р (1„„ 1„,+,) < а для всех 1 ( й и т~т,. 0 п р ед ел е н и е 10.8. Модель ААК называется усиленно корректной, если: 1) оператор К удовлетворяет условию 1 определения 10.7; 2) существует интерпретирующий на данном движении алгоритма ограниченный снизу функционал Р и строго монотонно возрастающая функция ф, причем ф (0) = О, такие, что как только т ~ тм то Р( „, 1„) - Р(з,„,„„1„,,)+ф(р(1„, 1„„)).
(10.22) Нетрудно проверить, что усиленно корректная модель является корректной. Доказательство усиленной корректности моделей многих ядерных алгоритмов, использующих в качестве меры близости г (О (д), )') между классом О (д) и ядром У статистический разброс класса О (д) относительно ядра г, вытекает из классического тождества Гюйгенса: Ъ'. г(Х)))Х вЂ” У1*= ~~', г(Х) 1(Х вЂ” Х(('+ хео хео + ~ у(Х))Х вЂ” У!', (10.23) хео где ~ т(х)х хео =;: т(х) хе о П р и м е р !0.10.
Рассмотрим интерпретирующий функционал Р (з, 1) .= ~ч~~ ~к~~ [[ Х вЂ” У (а) [1' а=! хео па в модели алгоритма й-средних. Тогда из (10.23) получаем Р(з, 1 )=»!'(з„„,, 1 )=Р( +и 1„.ы)+ + ч", л (и) [[)' (1) — )' +, (и) [[', р =.! л (д) =[0„(д)[, з =(О„(1), ..., О (а)), 1 =(1 (!), ..., К„(й)). Так как р (1, 1„,+,) = ~; [[1',„(д) — 1' +, (4)[[' и з=! п (д) 1 для всех д, то получаем, что модель алгоритма л-средних является усиленно корректной. Аналогично проверяется, что и модель алгоритма (л — г)- средних является корректной для любого г. Применяя теперь теорему 10.1, получаем, что движение алгоритма (й — г)-средннх стабилизируется.
П р и м е р ! О.!! . Пусть у: А" — ~ [О, 1) — невозрастающая функция, являющаяся параметром модели алгоритма выделения размытого кластера (см. п. 10.3.4). Для каждого натурального числа У введем новую функцию 7н (г) =- — где [ ) — символ операции взятия целой части [жт ОЛ Ж числа. Из свойств операции [.1 следует, что 0 < у (1)— 1 — "гн (1) < — для всех М. Ф Т ео р ем а 10.3. Допустим, чтоу (1)= Вщ у (К) для с г — о всех 1 с [О, оо). Тогда движение алгоритма выделения размытого кластера с параметром ун (1) стабилизируется для всех АГ [42!. В заключение приведем результат, который служит основой для построения новых усиленно корректных моделей ААК.
Л е м м а 10.4. Пусть заданы следующие компоненты структуры модели ААК: (Яо, 1., Р; К, 6) и некоторый ограниченный снизу функционал Р: Яо'сЕ- й', такой, что Р (з, 1) > Р (К (з, 1, р), 1). Тогда для любой строго монотонной функции <р существует оператор Т1: ЗохЬ-э Ь, вместе с которым данные компоненты образуют усиленно корректную модель ААК. Требуемый оператор 0 (з, 1) действует по формуле: О(з, 1) =- агпш1п(Р(з, 1')+ ~р(р(1', 1))). пес выводы 1.
Многообразие алгоритмов автоматической классификации (ААК) представляется в виде некоторой иерархической структуры. На самом верхнем уровне находится математическая модель ААК, компонен гы которой образуют средства, облегчающие переход от содержательной постановки задачи классификации к ее математической формализации.
На самом нижнем уровне располагаются конкретные алгоритмы АК. Переход с высших уровней на низшие происходит за счет конкретизаций, наполняющих компоненты структуры ААК информацией о характере данных, конечной цели классификации, априорных гипотезах и сведениях о свойствах исследуемых объектов, результатах предварительной обработки и т. п. 2. Описанная теория имеет следующие три аспекта. А.
Сопоставление различных известных алгоритмов и разработка методов целенаправленного конструирования новых алгоритмов, основанных на переходах снизу вверх и сверху вниз по уровням иерархической структуры в многообразии алгоритмов. Б. Получение параметрических семейств алгоритмов с целью реализации их в виде комплексов программ, предназначенных для автоматизации процедур проверки сложных иерархических гипотез.
В, Исследование модели АК как математической структуры с целью получения условий сходимости алгоритмов и описания класса функционалов, оптимизируемых имн. Гл аз а 11. ВЫБОР МЕТРИКИ И СОКРАЩЕНИЕ РАЗМЕРНОСТЕЙ В ЗАДАЧАХ КЛАСТЕР-АНАЛИЗА Проблема выбора метрики и тесно связанная с ней проблема сокращения размерности задачи кластер-анализа возникает, ко~да исходная информация задана в виде матрицы данных Х.
Выбор метрики, т. е. функции для вычисления расстояния между объектами, является одним из основных управляющих факторов, влияющих на результаты кластер-анализа, В данной главе рассмотрим несколько подходов, позволяющих в некоторых случаях удовлетворительно решать обе проблемы — выбора метрики и сокращения размерности в тех случаях, когда у исследователя отсутствует априорная информация, позволяющая сделать выбор метрики более обоснованно. Что касается выделения переменных, то для решения этой задачи в настоящее время не имеется эффективных вычислительных алгоритмов. Частично эта задача решается с помощью процедур адаптивной настройки, менее информативным переменным скорее всего будет присвоен и меньший вес.
11.1. Целенаправленное проецирование данных в пространство небольшой размерности с сохранением кластерной структуры Этот подход пригоден, когда все переменные измерены в количественной шкале. Будем искать последовательность из д (д( р) линейных комбинаций исходных переменных вида (У,'Х), таких, что векторы Уо ..., У, попарно $-ортогональны и являются решениями оптимизационной задачи У = агя гпах Я (К Х) (!1. 1) и при условии (У;Яl,) =- 0 (! = 1, ..., 1 — 1); $ — матрица ковариаций или ее оценка. В качестве функционала Я~ (У, Х) используется величина (см. гл.
19) ()з (У, Х) = зз Ег )з (г), () ) О, где ) ( ) и эз (у) — соответственно оценки плотности и дисперсии для одномерной случайной величины г = У'Х, оцененной по совокупности одномерных проекций г,- = (и'Х,)(! — 1, ..., и). Смысл использования критерия (!!.!) состоит в том, что чем больше его величина, тем более неоднородным можно считать распределение одномерной проекции г = (У' Х), например, в рамках модели смеси нормальных распределений. Перейдем сначала к махаланобнсовой метрике, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
