§ П.2. Алгоритмы таксономии

Задача минимизации функционала на множестве возможных разделений I объектов на групп является задачей дискретного программирования: всего возможно

различных разбиений I объектов на групп так, чтобы ни одна из групп не была пустой. Необходимо среди разбиений выбрать то, которое минимизирует функционал

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

1) Вначале выбирается любой элемент из X, например и полагается Вектор исключается из множества X, образуя множество

2) Пусть к шагу из исходного множества отобрано векторов и построены последовательности

а оставшиеся векторы объединены в множество Тогда на шаге к последовательности добавляется ближайший из вектор, т. е. такой вектор на котором достигается минимум

Этот вектор добавляется к построенной последовательности, образуя последовательность а соответствующая величина добавляется к образуя новую последовательность Из множества исключается вектор образуя множество

Так продолжается до тех пор, пока все векторы из X не будут упорядочены.

3) Используя последовательность можно разбить последовательность на таксонов. Для этого выберем такое число чтобы только значений последовательности превосходили Пусть соответствующие значения последовательности

Тогда векторы из последовательности с номерами образуют первый таксон; векторы с номерами второй, и т. д. Всего таксонов.

Для того чтобы задать конкретный алгоритм, нужно определить понятие расстояния от точки х до множества Обычно используют следующую метрику : расстояние от х до X определяется величиной расстояния от х до ближайшего из X вектора.

Что же касается расстояния между двумя векторами элементами множества X, то наряду с обычной евклидовой метрикой в таксономии используются и специальные метрики.

В частности, используется метрика Танимото, определяющая близость двух множеств, множества X и множества

где — число объектов множества — число объектов множества число объектов, которые входят одновременно в оба множества.

С помощью метрики Танимото определяется близость множеств объектов из X, попадающих в -окрестность точки и множество объектов попадающих в -окрестность точки ( — заданный параметр).

Таким образом,

Такая метрика более соответствует исследованию «геометрии векторов в целом».