Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика (1027378), страница 44
Текст из файла (страница 44)
и 3. Критерием сходимости алгоритма й-средних является получение набора центров е' = (е,, ..., е„)„для которого минимальное дистанционное разбиение последовательности, порождаемо~ набором е', является несмещенным. В связи с этим алгоритм останавливается, если в течение У ша! ов подряд практическине происходит пересчет центров.
Например, если последовательность точек получена зацикливанием выборки объема и, то в качестве Л! достаточно взять 224 и. В общем случае число гу' задается априори илиоценивается в ходе работы алгоритма исходя из модели всей совокупности точек Пусть е' = (е„ , ез) — набор центров, полученный на последнем шаге алгоритма. Ито!ом классификации является минимальное дистанционное разбиение последовательности, порождаемое набором е' Баме подробный анализ этого алгоритма можно найти в !91 Модификация этого алгоритма, в которой число классов А является параметром, настраиваемым в ходе классификации, приведена в п 7 3.2.
Алгоритмы с управляющими параметрами, настраиваемыми в ходе классификации 7.3.1. Параллельные процедуры. Рассматриваемые ниже алгоритмы ИСОМАД и Пульсар являются модификациями соответственно алгоритмов А-сроднил параллельного типа и Форель Алгоритм ИСОМАД (1зог(а!а) '.
Основной процедурой в этом ал! оритме, как и в алгоритме н-средних, является минимальное дистанционное разбиение, порожденное набором центров. Число классов заранее не фиксируется, а определяется в ходе классификации Для этого используется ряд вспомогательных эвристических процедур, параметрами которых регулируются характеристики межклассовои н внутриклассовой структуры выборки на этапах классификации Конфигурация (схема) ИСОМАД не является фиксированной, ее развитие отражает богатый опыт практического применения этого алгоритма Опишем наиболее распространенный вариант (ср. с (21, 1561). Параметры, определяющие процедуру классификации: й — предполагаемое число классов; йз — начальное (разведочное) число классов; 0„— минимально допустимое число элементов в классе (функция от и, где п — число элементов во всей выборке); 9, — порог внутриклассового разброса; О, — порог межклассового разброса; () — максимально допустимое количество пар центров классов, которые можно объединить; 7 — допустимое число циклов итерации.
' !зооз!з — Иегинте Зе!1-Огйзп!з!пя Озгз Апз!уз!и Тесно!. янез (ИСОМАД вЂ” Итеритинннй СзиоОргинизующийеи Метод Ани. лиза Данник). 8 Заказ № 29! Конкретные значения параметров задаются на основе априорной информации либо на этапе разведочного анализа выбираются из общих соображений, а затем корректируются от итерации к итерации. Пусть на классификацию поступила выборка Х = (Х„ ..., Х„), где Х! Е гга.
Выберем начальный набор центров Схема алгоритма !. Выбираются значения параметров. 2. Строится минимальное дистанционное разбиение 5 — (5,, ..., 5а,) выборки Х, порожденное набором центров. 3. Пусть и! — число элементов в классе 5ь Составляется 5= (5„..., 5а ) из классов 5, разбиения 5, у которых п~ > 0„, где Й вЂ” полученное (текущее) число классов.
5 присваивается обозначение 5 = (5„..., 5а ). 4, Вычисляется набор центров е = (е„..., еа ) из средних векторов классов, нходящих в разбиение 5. б. Вычисляется вектор Р = (Р,, ..., Рх ), где Рс= — "5 ЦХ вЂ” есП, 1= 1, „й~. "' хез, б. Вычисляется ~т — 1 Р- — Ч~Р~ а~Ро 1=- ! 7. а) Если текущий цикл итерации последний, то переход к 11; б) если А„, ( й!2, то переход к 8; в) если текущий цикл итерации имеет четный порядковый номер или л =- 2 й, то переход к 11; в противном случае переход к 8.
8. Для каждого класса 5, вычисляется вектор о, = = (о/, ..., оР), где о(~ — — ~ )'„(Хбч — е</>)' 1= 1» " Р Г ! хез, 9. В каждом векторе а, отыскивается координата от~= гпах а1, 1<1<й . г<гмо 10. Если <ф ) О, для некоторого 1, причем а) Р, ~ б и п~ ~ 2 (О„ + 1) или б) Й„< й/2, то класс 5, с центром с, расщепляется на два новых класса 5р', 5~ с центрами е,' ие,, где соответственно е,+=а,-+.е, а~ --= (а,',..., еЯ и в~ =- О, если /~ !ь в" =- уа", О<.
у < 1. Если расщепление класса на этом шаге происходит, то пере- ход к 2с набоРом центРов (еп ..., е~-~ е~ еГ ° е~+~ "' еь ) в противном случае переход к 11. 11. Вычисляется матрица (Ыо) взаимных расстояний между центрами классов 4, = )!е, — ез(!. !2. Расстояния йы, где ! < !. сравниваются с порогом усть с~~ ! ~< г(~ ! <~ ...
~ ~(~о го -. упорядоченная по следовательность тех из них, которые меньше О,. Вычеркон последовательности г(; г, если н т в наборе (!и !м ..., !о,,) встречается индекс (дч либо в наборе (1,, 1„..., )о,,) встречается индекс (со Проде- лаем аналогичную операцию с 4о, э „и так далее до г(,„,. Пусть 4... < а!„„< ... < Н..., — полученная в ре- зультате последовательность. Заметим, что по построению 1, = 1„), = г,. Положим д = пцп (9, (;>,). !3. Слияние классов. Лля каждой нары (!и (;), 1 < ! <д классы 50 и 5,, сливаются в класс 5,, () 5,, Непосредст- венно из 12 следует, что, если на предыдущем шаге было й,„ классон, то теперь остается й — д классов совокупности, которым переиндексацией присваивается обозначение 5 = = (5„..., 5ь,, ). Вычисляется набор центров е =- (е„..., ..., ех „) средних векторов классов, входящих в 5.
14. Если текущий цикл итерации последний, то алго- ритм заканчивает работу. В противном случае переход к 1, если пользователь решил изменить какой-либо из пара- метров алгоритма, либо переход к 2, если в очередном цикле итерации параметры не меняются. Завершением цикла ите- рации считается каждый переход к 1 либо к 2. Алгоритм Пульсар. Этот алгоритм, как и алгоритм Фо- рель, состоит из последовательности одинаковых этапов, иа каждом из которых выделяется один компактный класс (сгусток). Но радиус шара (величина окна просмотра) не фиксируется, а меняется (пульсирует) в ходе класси- фикации.
Для этого в алгоритм включены управляющие параметры„позволяющие поиск окончательного радиуса 227 реализовать в виде процедуры стохастической аппроксимации. Опишем этап выделения одного сгустка 142]. Параметры, определяющие процедуру классификации; г„„„, г""'" — минимальный и максимальный радиусы; и,„,„, и"' — минимальное и максимальное число элементов в классе; тд, — допустимое число колебаний радиуса. (Говорят, что произошло колебание радиуса„ если Лг х х Лг +, О, где Аг = г — г „ г — значение радиуса на гп-м шаге); 6 - порог, регулирующий скорость изменения радиуса.
Схема алгоритма !. Выберем начальный центр е' и значения параметров. гам + „тах 2. Для радиуса го— построим класс 5' = (Х Е Х:!(Х вЂ” е~)) ( гз), вычислим число элементов и„ в классе 5' и присвоим т (числу колебании радиуса) значение т„= О. 3. Пусть на и-м шаге для центра е~ выбран радиус г построен класс 5"' = (Х Е Х:ЦХ вЂ” е Ц ~ г ), подсчитано число егоэлементов и и значение т =- т Положим е"ч '= — у Х; 1 т~ а~а кезм гп!п(г+уб, г '"), если и„, < и„„„; гпах(г — уб, г,„), если а и ", причем т ~та, или е"'+' чье'"; г — в остальных случаях. Здесь у = (1 + т„)-'.
Порог т„,„учитывается при выборе радиуса г +, только тогда, когда е +, — — е и одновременно и ) и '". Далее положим тз=э„=О и для т)~ 1 т , Лг„.Лг +, О; тих+1 +1, Ьг Ьг +,(О. 228 4. Если е +, — — е, г +, — — г, то алгоритм заканчивает работу, в противном случае переходим к 3, заменив и на т -~- 1.
7.3.2. Последовательные процедуры. В качестве основного примера, следуя !53), опишем вариант последовательного алгоритма й-средних (см. п. 7.2.2), в котором число классов не фиксироваьо, а меняется от итерации к итерации, настраиваясь под влиянием управляющих параметров на структуру выборки. Параметры, определяющие процедуру классификации: й — начальное число классов; ф — минимально допустимое расстояние между центрами разных классов; ф — максимально допустимое удаление элемента от центра его класса; 7 — допустимое число циклов итерации. Пусть иа классификацию поступает последовательность точек (Х,, ..., Х„, ...).
Первые й, точек возьмем в качестве начального набора центров е' = (е"„..., е~1.), присвоим центрам веса ы,' = 1. схема алгоритма 1. Выберем значения параметров <р и ф. 2. Проведем огрубление центров е'. Расстояние между двумя ближайшими центрами сравнивается с ~р. Если оно меньше ~р, то эта пара центров заменяется их взвешенным центром, которому присваивается вес, равный сумме соответствующих двух весов. К полученному набору из Йэ — 1) центров опять применяется процедура огрубления и так далее до тех пор, пока расстояние между любыми двумя центрами будет не меньше, чем ~р. Пусть в результате получается набор центров еэ = — (е"„ е-,), А„~ А, с набором весов й =- (ы(, ..., о4,). 3. Для вновь поступившей точки Х„,+, вычислим минимальное расстояние до центра: И,= пип Н(Х„+ ы е,').
~мп<сь, Если И, ~ ф, то Х ~,.„объявляется центром еь,э, с весом а, э, = 1 Если 4 < р, то самый близкий к Хх„э, центр заменяется взвешенным центром этого старого центра и точки Х~,~,. Вес нового центра считается равным сумме соответствующих весов. Все остальные центры и их веса не пере- считываются. Полученные в итоге наборы центров я весов обозначаются через Е' =- (е,',, е„',) и 1«' = («»',, ..., «з,'„). Заметим, что й«< й, < й«+ 1. 4. Цикл итерации состоит из шагов и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
