Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика (1027378), страница 56
Текст из файла (страница 56)
1. Введение класса <джокер» (так называемый класс «не знаю», «отказ» н т. и.). Обычно класс «джокер» определяется следующим образом Задается порог 6, и если для классифицируемого объекта мера близости г" ч (Х, У ) превосходит 6 для всех д, 1 ( д ( й, где У, — ядро д-го класса на данном шаге алгоритма, то оператор К отказываегся от клас- сификации и относит элемент Х к символическому эталону * класса «джокер». На следующих шагах алгоритма, когда набор ядер (Кн ..., У») сменится, этот элемент может быть уже отнесен к некоторому классу. Для включения класса «джокер» в общую схему базисного ядерного алгоритма достаточно присвоить этому классу номер (й + !) и положить Р«+! (Х, )'»+Д = 6 для всех Х с О.
Тогда Р +, (О (й + 1), У„+!) = и „., 6, где и,+ —— — ~0 (й + 1) (— число элементов в (й + !) -м классе, т. е. число элементов, которые на данном шаге не классифицированы. 2. Следующая модификация применяется тогда, когда имеется дополнительнал информация о допустимой принадлежности элементов к классам, т. е. «р; 0-» 2х. В этом случае классификатор задается формулой д= агд щ!и г' ° (Х, 1(д')), ХЕ р. Х(в, 1, р)(Х) = ' ч<х> з (Х), Х ~ р Иерархическая структура многообразия алгоритмов АК 1О.З. 10» В данной модели алгоритма АК одни и те же множества 5о и Ь могут быть получены для различных конкретизаций множеств 2 и Уо соответственно. Таким образом, в рамках данной модели алгоритма АК элементы Л, Уо ее структуры являются варьируемыми параметрами. Покажем, как эти параметры позволяют восстанавливать иерархическую структуру многообразия алгоритмов.
10.3.1. Модель алгоритма й-средних параллельного типа. Пусть 0 =- (Х,, ..., Х„) ~ Р». Для простоты будем считать, что р-мерное евклидова пространство Я» наделено ц стандартной метрикой; ! ~Х вЂ” У'((' = 2 (х' — у!)', где 1=1 (х', ..., хР) и (у', ..., у») — координаты векторов Х и )е соответственно. В качестве первой конкретизации множества Я возьмем список номеров классов Л! = (1, ..., й). Положим 5о = = (гс 0 ~ Л!) и будем отождествлять каждое отображение з: 0-» Я, с разбиением множества 0 на классы (0(1), ..., 0(й)), где 0(д) =- в-' (д), Имеем: () 0 (д) =- 0 и 0 (д) П «=! Й 0(Ч) = Ы.
дчьд'. Каждый класс будем описывать его средним, т. е. в качестве Уо возьмем само пространство 1«» и положим Т. =- (1: Л«-» Уо) = Р'Х ... м Р», ,им образом 1 = (У„..., Уз) и потому в Е можно ввести ~етрику следующим образом: ((1» — Ц(»= ~ ((У» — У~ П», «=1 где 1, =- (Уго ..., У,«) и 1, = (Уьо ..., У„,). Так как строим модель алгоритма параллельного типа, то в качестве Р должны взять одноэлементное множество (выборка О вся участвует в классификации на каждом шаге), поэтому в дальнейших формулах компоненты Р и 6 модели можно не учитывать. Операторы К и 0 возьмем, следуя базисной модели ядерного алгоритма с Р (Х, У) = ((Х— « Я Ф вЂ” Ц .
Детальное описание этих операторов дано в п. 7.2.1. Непосредственно из конструкции этих операторов следует, что функционал Г(з, 1)= ~я~~ ~~Р ЦХ вЂ” У(д)1(», (10.17) «-~ хеои> где з = (О (1), ..., О (й)), 1 = (У (1), ..., У (й)), является интерпретирующим для этой модели (см. 5. 10.4). Итак, модель алгоритма л-средних параллельного типа описана. Начнем модификацию ее параметров. 10.3.2.
Модель алгоритма (й — г)-средних. Эта модельсвязана с введением класса «джокер» (см. 2 10.2). Задается «порог отказа» г, и если значение меры сходства объекта Х с каждым из Й ядер классов превосходит г, то такой объект относится к символическому классу ь.
Итак, 2, (*) = — (1, „й. /г + 1). В этом случае Яо точно такое же, как в алгоритме (й + 1)-средних. Лалее, Уо = У» (1 У» = 1«» () У («) — объединение пространства Р» и изолированной точки У («). В качестве 1. возьмем часть множества отображений Л, («) в Уо, состоящую из всех отображений, переводящих символ (й + 1) в У (*).
Тогда каждая точка 1Е 1. будет иметь вид (У(1), ..., У (я), У (*)). Операторы К и О зададим формулами (10.13) и (10.14) соответственно с Р,(Х, У01))=1Х вЂ” У()1, д=1, ..., й; Р'„««(Х, У(.»=,. Имеем: О(й+ 1)=О(«1=(ХЕ О: т(п ~~Х вЂ” У(д))»)г»); ~~«<» Г„+» (О (ь), У (»)) =! О (*Н г . ' Таким образом описана модель алгоритма (й — г)-средних и тем самым определено его движение. Теперь непосредственной проверкой можно убедиться, что функционал Р(з, !)= ~ У )Х вЂ” )'(в)]'+$0(ь)]гз (10.18) а=~ хео ни является интерпретирующим для этой модели.
Можно подвести первые итоги. Получение модели алгоритма (й — г)-средних иллюстрирует подъем снизу вверх в описываемой иерархии. Действительно, отправляясь от модели 10.3.1, получаем данную модель с дополнительным параметром г. Утверждение, что модель 10.3.2 лежит выше по иерархии, чем модель !0.3.1, обосновывается тем, что, отправляясь от модели 10.3.2 и устремляя г- со, очевидно, получим модель 10.3.1. !0.3.3. Модель алгоритма Форель. Для получения этой модели (см.
п. 7,2.1) достаточно, отправляясь от модели 10.3.2, спуститься вниз по иерархии, полагая й = 1. Этот результат иллюстрирует способность данной иерархической структуры устанавливать связи между известными алгоритмами, которые появились для решения разных задач классификации. Между моделями 10.3.1 и данной, лежащими на одном уровне иерархии, устанавливается связь через модель 10.3.2, лежащую выше. Применение алгоритма Форель опирается на гипотезу: выборка О представляет собой объединение О (1) () О (2), где О (1) — компактный кластер, ядро которого совпадает с его геометрическим центром, а точки из О (2) лежат на достаточном удалении от кластера О (1).
Следующая модель описывает алгоритмы, опирающиеся на аналогичную гипотезу в предпазожении, что ядро компактного кластера О (1) совпадает с взвешенным центром. !0.3,4. Модель алгоритма выделения размытого кластера. Параметром модели является неаозрастающая функция 7: !г'- ]О, 1], такая, что 7 (О) = 1 и у (!) = О, ! - йн В этой модели Е = ]О, !] и пространство допустимых классификаций имеет вид 5о =-- (з: О- [О, 1]: з (х) = — 7 (]] Х— — !']]) для некоторого !'Е !(~).
Согласно терминологии теории размытых множеств (см. п. 7.5. !) каждая такая классификация з с 3о задает размытый класс О (1) в О. Класс О (1) описывается точкой из 7(г (формальным элементом, как и в алгоритме Форель), т, е. г"о = — !сг и 1. = Р~. Разброс класса О (1) относительно ядра )' с мэ задается формулой Г(а(!), У) = ~ 7(!Х вЂ” УЦ)НХ вЂ” У]'. хео Для завершения описания модели осталось указать операторы К и 11. Пусть на т-м шаге алгоритма получен размытый класс О (1) и его ядро У .
Тогда К(з, У )(Х)=з +,— — у(!Х вЂ” У 1); В(з ~м У„,)=г' +,— — атаги)п ~~ у()Х вЂ” У )))Х вЂ” У)з, геляхео т. е. ~ тих — 1„й)х хео ~' тб)х — У„!!) хео Здесь з — описание класса 0 . Для получения из данно- го алгоритма алгоритма 10.3.3 надо спуститься вниз по иерархии, положив )1, (1(<г; (О, (!( г.
10.3.5. Модель алгоритма Л(~с)-средних. Опишем модель алгоритма, получение которой дает пример еще одного спо- соба подъема снизу вверх в исследуемой иерархии. Для это- го покажем сначала, как можно изменить параметры моде- ли !0.3.1, совершенно не меняя ее основные компоненты, а значит, и движение алгоритма. Обозначим через А (й) стандартный (й — 1)-мерный сим- плекс, т. е. множество точек ((г', ...,г"), гч )О, Хаю=11. Пронумеруем вершины Л„..., А„симплекса Л (/г) так, что- бы вершина Л „имела координаты (О, ..., О, 1, О, ..., 0), где 1 стоит на д-м месте.
Теперь в качестве второй конкретиза- ции множества 2 в модели !0.3.1 возьмем симплекс Л (Ф). Тогда 5о из этой модели можно отождествить с частью мно- жества отображений из О в Л (Ф), состоящего из всех ото- бражений, переводящих 0 в подмножество вершин (Лм ..., л,) с л (й), Каждую точку ЕЕ А (й) можно однозначно записать в виде Е= ~ г~бч, где ач ~ О, Хз~ = 1. Поэтому каждое ли— ! нейное отображение 1: А (й) -+- Р~, т.
е. такое отображение, что 1 (2) = ~ гз ! (Ат) однозначно определяется набором обр=~ разов вершин (! (Л,), ..., 1 (Лд). Следовательно, в новой кон- кретизации множества Я модели 10.3.1 множество А можно отождествить с множеством всех линейных отображений из А (й) в Нр. В новой интерпретации множеств Юо и 1. функционал (10.17) можно записать в виде Р(з, 1)= ~'„~ч'„Ч' (з(Х))1Х вЂ” г'(д)1', (10.19) ~=1 хео где Ч'ч (з (Х)) = 1, если з (Х) = Ач, и 0 — в противном случае, а У (д) = 1(Лэ). Тогда согласно общей схеме оп- тимизационного подхода к построению операторов К и 11 (см. формулы (10.6) и (10.7)), имеем: з +, — — К (з, 1 ) — отображение нз О в Л (й), такое, что з, (Х) = агд ш)п ч,; Ч' (з(Х)) ) Х вЂ” У (д) ))', (10.20) 5еЯ т.
е. минимум берется по всем возможным значениям клас- сификаций з для данного Х. Аргумент, в котором функция из (10.20) достигает минимума, может быть не единственным, поэтому необходимо фиксировать еще способ выбора требу- емого аргумента. В формуле для классификатора из алго- ритма Ьсредних (см. п. 7.2.1) заложен в явном виде способ выбора, наиболее употребительный на практике. Далее име- ем 1, = Э (1, з„,+,) — линейное отображение из Л (й) в КР, такое, что 1 „г(Лч) =агнш)п ~ч~~ Ч' (з „.,(Х))((Х вЂ” У()', геня хео т. е. ч; ч',(~ „(х)) х 1„.„(А,) = '" (10.2 Ц ~ч", ч'ч (л,„+,) (х)) ХЕ О Итак, требуемая модификация параметров модели !0.3.1 завершена. Она немедленно приводит к модели алгоритма нечеткой классификации, который назвали выше алгоритмом Л (к)-средних.
Для 2 = Л (й) возьмем в качестве Яо множество всех отображений из О в Л (й). Таким образом, классификация з с 5о ставит в соответствие объекту Х вектор (г', ..., гь), в котором координата г" имеетсмысл степени принадлежности объекта Х к д-му классу. Множество 1. возьмем таким же, как в модели 10.3.1. Иитерпретирующий функционал возьмем вида (10.19), но теперь будем считать, что функции Рч ( ), д = 1, ..., Й, являются параметрами модели. Операторы К и 11 зададим согласно формулам (10.20) и (10.21). 29б 10.3.6.
Модель алгоритма нечеткой классификации Беждека. Для того чтобы спуститься от модели 10.3.5 к модели 10.3.б, достаточно конкретизировать вид весовых функций Ч'~( ), рассматриваемых как функции на симплексе Л (Ф). В алгоритме Беждека (см. п. 7.5.2) В этом случае можно дать явное решение оптимизационной задачи (10.20): найти агягп!и ч,', (гт)'*!)Х вЂ” У(д))~,2= (гы), „., гь) г при условии, что гг > 0 и У гг = 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
