2.1. Алгоритм FOREL.

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

Для этого мы постепенно уменьшаем радиус сфер. Берем радиус  и помещаем центр сферы в любую из имеющихся точек. Находим точки, расстояние до которых меньше радиуса, и вычисляем координаты центра тяжести этих «внутренних» точек. Переносим центр сферы в этот центр тяжести и снова находим внутренние точки. Сфера как бы плывет в сторону локального сгущения точек. Такая процедура определения внутренних точек и переноса центра сферы продолжается до тех пор, пока сфера не остановится, т. е. пока на очередном шаге мы не обнаружим, что состав внутренних точек, а следовательно и их центр тяжести, не меняется. Это значит, что сфера остановилась в области локального максимума плотности точек в признаковом пространстве.

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

Рис. 5.

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