7.2. Алгоритмы, использующие понятие центра тяжести

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

Пусть исходная информация о классифицируемых объектах представлена матрицей «объект—свойство», столбцы которой задают точки -мерного евклидова пространства.

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

Опишем один из наиболее известных алгоритмов, модификациями которого являются многие важнейшие алгоритмы, приведенные далее (общая схема таких модификаций дана в гл. 10).

Алгоритм -средних. Единственным управляющим параметром является число классов, на которые проводится разбиение выборки X. В результате получается несмещенное разбиение (см. п. 5.4.5)

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

1. Выберем начальное разбиение где

2. Пусть построено разбиение Вычислим набор средних где

3. Построим минимальное дистанционное разбиение, порождаемое набором и возьмем его в качестве п. 5.4.5):

где — расстояние в

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

Введем расстояние от точки до множества где по формуле

Тогда можно рассмотреть статистический разброс выборки X относительно множества

Определим статистический разброс разбиения выборки X как разброс этой выборки относительно множества где — средний вектор класса т. е. положим

Непосредственно из построения минимального дистанционного разбиения следует формула

Так как на последовательности разбиений которая строится в алгоритме -средних, функционал не возрастает, причем только если то для любого начального разбиения алгоритм через конечное число шагов заканчивает работу (см. гл. 10).

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

В ряде случаев начальное разбиение задается как минимальное дистанционное разбиение, порожденное некоторым набором точек Результат классификации зависит от выбора Обычно для проверки устойчивости результата рекомендуется варьировать выбор В тех случаях, когда из априорных соображений нельзя сразу выбрать число классов k, его находят либо перебором, либо вместо алгоритма средних используется алгоритм ИСОМАД (Isodata), в котором k является параметром, настраиваемым в ходе классификации (см. §. 7.4).

Алгоритм Форель. Единственным управляющим параметром является порог — радиус шаров, которыми покрывается выборка X. Пусть — шар радиуса с центром в точке е. Подвыборка называется несмещенной в , если ее средний вектор совпадает с е. Классификация при помощи алгоритма Форель разбивается на несколько последовательных этапов. На первом в выборке X выделяется несмещенная подвыборка X, в некотором которая объявляется первым таксоном. На втором этапе та же процедура применяется к выборке . Таким образом, достаточно описать алгоритм только для первого этапа.

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

1. Выберем начальное разбиение выборки X.

2. Пусть построено разбиение Вычислим средний вектор класса

3. Построим разбиение где

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

Пополним пространство «точкой» такой, что d для всех Тогда статистический разброс выборки X относительно множества где запишется в виде

где — число элементов в множестве При помощи функционала (7.2) в гл. 10 показано, что последовательность разбиений которая строится на первом этапе алгоритма Форель, стабилизируется и алгоритм через конечное число шагов заканчивает работу.

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

На основе алгоритма первого этапа Форели строится целое семейство алгоритмов, целью которых является разбиение выборки на заданное число классов, покрытие выборки X областями более сложной формы, чем шары, и т. п. Подробное описание этого семейства см. в [75]. Имеется модификация алгоритма первого этапа Форели, в которой порог является параметром, настраиваемым в ходе поиска первого сгустка (см. алгоритм Пульсар в п. 7.3.1)