7.3. Алгоритмы с управляющими параметрами, настраиваемыми в ходе классификации

7.3.1. Параллельные процедуры.

Рассматриваемые ниже алгоритмы ИСОМАД и Пульсар являются модификациями соответственно алгоритмов -средних параллельного типа и Форель

Алгоритм ИСОМАД (Isodata) . Основной процедурой в этом алюритме, как и в алгоритме -средних, является минимальное дистанционное разбиение, порожденное набором центров. Число классов заранее не фиксируется, а определяется в ходе классификации Для этого используется ряд вспомогательных эвристических процедур, параметрами которых регулируются характеристики межклассовой и внутриклассовой структуры выборки на этапах классификации Конфигурация (схема) ИСОМАД не является фиксированной, ее развитие отражает богатый опыт практического применения этого алгоритма

Опишем наиболее распространенный вариант с [21, 156]).

Параметры, определяющие процедуру классификации:

— предполагаемое число классов;

— начальное (разведочное) число классов;

— минимально допустимое число элементов в классе (функция от , где — число элементов во всей выборке);

— порог внутриклассового разброса;

— порог межклассового разброса;

— максимально допустимое количество пар центров классов, которые можно объединить;

— допустимое число циклов итерации.

Конкретные значения параметров задаются на основе априорной информации либо на этапе разведочного анализа выбираются из общих соображений, а затем корректируются от итерации к итерации.

Пусть на классификацию поступила выборка где Выберем начальный набор центров

Схема алгоритма

1. Выбираются значения параметров.

2. Строится минимальное дистанционное разбиение выборки X, порожденное набором центров.

3. Пусть — число элементов в классе Составляется из классов S; разбиения S, у которых где полученное (текущее) число классов. S присваивается обозначение

4. Вычисляется набор центров из средних векторов классов, входящих в разбиение

5. Вычисляется вектор , где

6. Вычисляется

7. а) Если текущий цикл итерации последний, то переход к 11; б) если то переход к ; в) если текущий цикл итерации имеет четный порядковый номер или то переход к 11; в противном случае переход к .

8. Для каждого класса вычисляется вектор где

9. В каждом векторе отыскивается координата

10. Если для некоторого I, причем

а)

или

б)

то класс с центром с, расщепляется на два новых класса с центрами где соответственно , если . Если расщепление класса на этом шаге происходит, то переход к 2 с набором центров в противном случае переход к 11.

11. Вычисляется матрица взаимных расстояний между центрами классов

12. Расстояния , где сравниваются с порогом . Пусть — упорядоченная последовательность тех из них, которые меньше Вычеркнем из этой последовательности если и только если в наборе встречается индекс либо в наборе встречается индекс Проделаем аналогичную операцию с и так далее

Пусть — полученная в результате последовательность. Заметим, что по построению Положим

13. Слияние классов. Для каждой пары классы сливаются в класс Непосредственно из 12 следует, что, если на предыдущем шаге было классов, то теперь остается классов совокупности, которым переиндексацией присваивается обозначение . Вычисляется набор центров средних векторов классов, входящих в

14. Если текущий цикл итерации последний, то алгоритм заканчивает работу. В противном случае переход к 1, если пользователь решил изменить какой-либо из параметров алгоритма, либо переход к 2, если в очередном цикле итерации параметры не меняются. Завершением цикла итерации считается каждый переход к 1 либо к 2.

Алгоритм Пульсар. Этот алгоритм, как и алгоритм Форель, состоит из последовательности одинаковых этапов, на каждом из которых выделяется один компактный класс (сгусток). Но радиус шара (величина окна просмотра) не фиксируется, а меняется (пульсирует) в ходе классификации. Для этого в алгоритм включены управляющие параметры, позволяющие поиск окончательного радиуса реализовать в виде процедуры стохастической аппроксимации.

Опишем этап выделения одного сгустка [42].

Параметры, определяющие процедуру классификации:

— минимальный и максимальный радиусы;

— минимальное и максимальное число элементов в классе;

— допустимое число колебаний радиуса. (Говорят, что произошло колебание радиуса, если где — значение радиуса на шаге);

- порог, регулирующий скорость изменения радиуса.

Схема алгоритма

1. Выберем начальный центр и значения параметров.

2. Для радиуса - построим класс вычислим число элементов в классе и присвоим v (числу колебаний радиуса) значение

3. Пусть на шаге для центра выбран радиус построен класс подсчитано число его элементов и значение

Положим

Здесь Порог учитывается при выборе радиуса только тогда, когда и одновременно .

Далее положим

4. Если то алгоритм заканчивает работу, в противном случае переходим к 3, заменив на .

7.3.2. Последовательные процедуры.

В качестве основного примера, следуя [58], опишем вариант последовательного алгоритма -средних (см. п. 7.2.2), в котором число классов не фиксировано, а меняется от итерации к итерации, настраиваясь под влиянием управляющих параметров на структуру выборки.

Параметры, определяющие процедуру классификации:

— начальное число классов;

— минимально допустимое расстояние между центрами разных классов;

— максимально допустимое удаление элемента от центра его класса;

— допустимое число циклов итерации.

Пусть на классификацию поступает последовательность точек Первые точек возьмем в качестве

начального набора центров присвоим

центрам веса

Схема алгоритма

1. Выберем значения параметров

2. Проведем огрубление центров

Расстояние между двумя ближайшими центрами сравнивается с Если оно меньше то эта пара центров заменяется их взвешенным центром, которому присваивается вес, равный сумме соответствующих двух весов. К полученному набору из центров опять применяется процедура огрубления и так далее до тех пор, пока расстояние между любыми двумя центрами будет не меньше, чем Пусть в результате получается набор центров с набором весов

3. Для вновь поступившей точки вычислим минимальное расстояние до центра:

Если то объявляется центром с весом Если то самый близкий к центр заменяется взвешенным центром этого старого центра и точки Вес нового центра считается равным сумме соответствующих весов.

Все остальные центры и их веса не пересчитываются. Полученные в итоге наборы центров я весов обозначаются через Заметим, что

4. Цикл итерации состоит из шагов п. 1—3. Если поль зователь решил изменить значение параметров или то переход к п. 1, если и не меняется, то переход к 2.

5. После прохождения циклов полученный набор центров объявляется набором эталонов классов и используется для классификации последующих наблюдений по методу минимального дистанционного разбиения.

Выбор значений параметров признается удачным (удовлетворительным), если получаемая в результате классификация оптимальна или с точки зрения экспертов, или в смысле принятых функционалов качества разбиения.