Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика (1027378), страница 43
Текст из файла (страница 43)
Схема алгоритма в предыдущих обозначениях алгоритма й эталонов: 2!8 1. Объекту О~ поставим в соответствие порог /(; ) О, называемый его радиусом влияния, т. е. объект О/ считается близким к О; (находится в сфере влияния объекта О;), если б(Х,, Х/) «А. 2. Объекту О; поставим в соответствие код е; = (е(П, ..., еью), где еп~ =1, если И (Хо Х,)</)ь ве',=Π— в противном случае. 3. Выделим в выборке классы, относя набор объектов О/, ..., О,, т «и, к одному классу, если у их кодов е;,, ..., е, все координаты сномерами1=1„...,1 равны!.
4. Выделим в выборке минимальное число классов, объединение которых дает всю выборку. Ясно, что алгоритм дает в общем случае нечеткую классификацию выборки. Геометрически каждому объекту О/ в признаковом пространстве Ла отвечает шар ~~ радиуса 4 с центром в точке Хо Классу (О,,, ..., О/ ) отвечает пересечение () ~~, шаров ъ/ и содержащее все центры Х~, ..., (=! Х; и называемое областью взаимного поглощения данного класса!58).
В ряде задач основной целью классификации является покрытие признакового пространства областями взаимного поглощения классов. Ясно, что настройка рассматриваемого алгоритма на специфику решаемой задачи осуществляется выбором порогов Ы„1 «1 «и. Приведем примеры такого выбора, взятые из!58): а) б; = тахй(Хн Х/) — Ь; / б) /(,= ш)п/1(Хп Х/)+8; / и// И (Хы Х/) в) /1,= и "ч аь/ /=.
1 Здесь б — некоторая константа; тц) 0 — весовые множители. Они задаются либо эвристически, либо на этапе разведочного анализа служат управляющими параметрами. 7.1.2. Последовательные процедуры. Процедуры, в которых элементы выборки поступают на классификацию по одному или малыми порциями, называются последовательными.
Приведем простой последовательный алгоритм классификации, в основе которого лежит предположение, что пред- 219 ставители одного класса не могут быть удалены друг от друга более чем на заданную пороговую величину. Пусть на классификацию объекты поступают последовательно, например по одному. Если исходная информация представлена в форме матрицы «объект — свойство», то параметрами алгоритма являются функция близости (расстояние) «((О;, 0,) между объектами и пороговое значение «(«; если исходная ин~)юрмация представлена матрицей взаимных расстояний, то единственным параметром является пороговое значение д».
Схема алгоритма 1. Первый объект О, объявляется ядром е, первого класса. 2. Пусть на гп-м шаге выделено й классов с ядрами е,,..., ..., Ею Зля поступившего объекта 0 если И (О, е,) -- =д„то 0 относим к первому классу; если и'(О, е~ »))«(«и«((0, е,) <«(„2<1<я, то 0 относим к 1-му классу; если «((О, е~) = «(„1 <1 <К то О объявляется ядром е„„, нового (й + 1)-го класса.
Если функция «( (О;, 0~) удовлетворяет неравенству треугольника, как, например, когда д (Оь Оз) — метрика, то объекты, отнесенные алгоритмом к одному классу, удалены друг от друга не более чем на 2 «(». Алгоритмы, использующие понятие центра тяжести При решении практических задач полезно иметь набор простых быстродействующих алгоритмов классификации для выработки первых представлений о структуре данных в признаковом пространстве.
Таким алгоритмам посвящен этот параграф. Модификации алгоритмов, приведшие к ряду важных многопараметрических семейств их, ориентированных на проверку более сложных гипотез, возникающих уже в ходе исследования, описаны ниже в этой главе и в гл. 10. Пусть исходная информация о классифицируемых объектах представлена матрицей «объект — свойство», столбцы которой задают точки р-мерного евклидова пространства. 7.2.1. Параллельные процедуры. Опишем один из наиболее известных алгоритмов, модификациями которого являются 220 многие важнейшие алгоритмы, приведенные далее (общая схема таких модификаций дана в гл.
10). Алгоритм а-средних. Единственным управляющим параметром является число классов, на которые проводится разбиение 5 = — (5„..., 5х) выборки Х. В результате получается несмещенное разбиение (см. п. 5.4.5) 5л = (5;,..., Я) Схема алгоритма 1. Выберем начальное разбиение 5'=(51, ., 5ь), где 5)=(Х,', ..., Хс.,(. й5с'=Х, 5;П5с =Я, 1~Р. 2. Пусть построено т-е разбиение 5"' = (5',", ..., 5|). Вычислим набор средних еы = (е",', ..., е ), где е,'" = ! лС вЂ” У Х5. лс /.=.
с 3. Построим минимальное дистанционное разбиение, порождаемое набором еы и возьмем его в качестве 5 +' = = (5',"+', ...„5,"'), т. е. (ср, п. 5.4.5): 5, +' =(ХЕХ:с((Х, е",')= ппп й(Х, е',")( !асах с с-с л;+ -(хсх'~ и лр~':аСх чС= с лсх. чс(, ~< ~ < л !<с'<Ф где й (Х, е) = 11Х вЂ” еЦ вЂ” расстояние в Яв. 4. Если 5 +' чь 5, то переходим к п. 2, заменив т на т + 1, если 5"'+' = 5"', то полагаем 5"' = 5л и заканчиваем работу алгоритма.
Введем расстояние сс (Х, е) от точки Х Е !св до множества е = — (е,, ..., еь), где ес 5 Кл по формуле й(Х, е) = ппп с((Х, ес). с<сиз Тогда можно рассмотреть статистический разброс выборки Х относительно множества е = (е„..., еь): Р(Х; е) = ~~~ с((Х, е)з. хек Определим спштистический разброс разбиенин 5 =(5„..., 5„) выборки Х как разброс этой выборки относительно множества е (5) =(е,(5), ..., е„(5)), где е, (5) — средний вектор класса 5ь т. е. положим Р (5) = Р (Х; е (5)). Непосредственнзт нз построения миннмальногп дистанцион- ного разбиения следует формула Р(5) = ~ ~э~~ ~~ Х вЂ” е,(5) '. хез (7.1) з Первоначальное название ФОРЭЛ вЂ” ФОРмальнма ЭЛенент.
Так как иа последовательности разбиений 5е, 5', ..., 5, ..., которая строится в алгоритме й-средних, функционал Р (5) не возрастает, причем Р (5'") = Р (5 "'), только если 5 — — 5 +', то для любого начального разбиения 5' алгоритм через конечное число шагов заканчивает работу (см. гл. 10). Содержательно процедура алгоритма Й-средних направлена на поиск разбиения 5* выборки Х с минимальным разбросом. В ряде случаев начальное разбиение 5' задается как минимальное дистанционное разбиение, порожденное некоторым набором точек е' =- (е|, ..., е1).
Результат классификации зависит от выбора ее. Обычно для проверки устойчивости результата рекомендуется варьировать выбор е'. В тех случаях, когда из априорных соображений нельзя сразу выбрать число классов й, его находят либо перебором, либо вместо алгоритма й-средних используется алгоритм ИСОМАД (1зоба1а), в котором а является параметром, настраиваемым в ходе классификации (см. й.
7.4). Алгоритм Форель '. Единственным управляющим параметром является порог г — радиус шаров, которыми покрывается выборка Х. Пусть 11» (е) с: )㻠— шар радиуса г с центром в точке е. Пвдвыбврка Х' =- Х П 17„(е) называется несмещенной в О, (е), если ее средний вектор совпадает с е.
Классификация при помощи алгоритма Форель разбивается на несколько последовательных этапов. На первом в выборке Х выделяется несмещенная подвыборка Х, в некотором 1~>, (е,), которая объявляется первым таксоном. На втором ртапе та же процедура применяется к выборке Х- Х,. Таким образом, достаточно описать алгоритм только для первого этапа. Схема алгоритма 1. Выберем начальное разбиение 5« = (5!, 5з) выборки Х. 2. Пусть построено и-е разбиение 5 = (5,, 5,). Вычислим средний вектор е" класса 5',".
3, Построим разбиение 5««+' = (5',"+', 5',"+'), где 5,+! =(Хб Х:«((Х, е") <г); 51"+! =Х 57+1. 4. Если 5"'+' ~ 5"', то переходим к п. 2, заменив т на гл + 1, если 5"«' — 5"', то полагаем 5"' = Х, и заканчиваем работу первого этапа алгоритма. Пополним пространство («» «точкой» в, такой, что «((Х, в) =: г для всех Х Е 0». Тогда статистический разброс выборки Х относительно множества е = = !е, в), где е Е (1», запишется в виде Р(Х; е) = ~'.
4(Х, е)*= ~', !(Х вЂ” е(!»-(-г«~ 5,~, (7.2) хе х хез, где 5, = (Х Е Х Н (Х, е) = ((Х вЂ” еЦ < г), (5,1 — число элементов в множестве Х'~5,. При помощи функционала (7.2) в гл. 10 показано, что последовательность разбиении 5«,..., 5"',, которая строится на первом этапе алгоритма Форель, стабилизируется и алгоритм через конечное число врагов заканчивает работу. Применение алгоритма Форель для ряда последовательг ных значений г, — 㫠— чб, где Л = — ', т = 1, 2, ..., 7»' — 1, позволяет оценить наиболее предпочтительное число классов для даннои выборки. При этом основанием для выбора числа классов может служить многократное повторение одного и того же числа классов для нескольких последовательных значений г, и его резкое возрастание для следующего шага по» На основе алгоритма первого этапа Форели строится целое семейство алгоритмов, целью которых является разбиение выборки на заданное число классов, покрытие выборки Х областями более сложной формы, чем шары, и т.
п. Подробное описание этого семеиства см. в 1751. Имеется модификация алгоритма первого этапа Форели, в которои порог г является параметром, настраиваемым в ходе поиска первого сгустка Х, (см. алгоритм Пульсар в п. 7.3 !) 7.2.2. Последовательные процедуры. Пусть Х„..., Х„...— последовательность точек пространства Й», описывающая последовательно поступающие на классификацию объ- екты О„..., О„, .... Предполагается, что последовательность сколь угодно длинная.
В тех случаях, когда число классифицируемых объектов конечно, применяется стандартный прием зацикливания конечной последовательности Х„, ..., Х, по правилу Х„„= Х„, д =-1, 2, .... л Положим Х (и) = - ~' Х!. Тождество Х (и + 1) = Х (и) + — (Х„+,— Х (и)) позволяет параллельные ! и+ ! процедуры, использующие понятие центра тяжести, модифицировать в последовательные процедуры. В качестве основного примера рассмотрим алгоритм й-средних.
Схема алгоритма 1. Выберем набор центров е' = (е',, ..., е!',), где е! с Я", и набор весов Яо =- (а! в~), где а!4 ~ О 2. Пусть на и-м шаге построены набор центров е"' = = (е,, ..., е ) и набор весов Й'" =- (в',", ..., в"'). Для вновь поступившей точки Х вычислим (,„= ппп И(Х, е™) !к!<а и построим новые наборы е е' и Й +': если !( (Х, еа) = г(, то положим .е, +' =- е",' — ' — (Х вЂ” е",'), в",'+ ' =в',"+ 1; ! аи с! е)"+! =е, в'"+'=в"' 1(1< 7г; ! 3 если !((Х, е',",) )1( и Ы (Х, е',") = е(, где 1«1 «, й, то положим: еа+ ! = е", ° + (Х„,— е,"'), в',"+ ' = а',"+ 1; 1 Ш+ ем+'=ер, ап+' =а"!, 1' чь1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
