2.4. Алгоритм KOLAPS.

Взглянув на рис. 7, мы скорее всего отметим следующие его особенности: здесь выделяются три разных по диаметру сгустка точек на равномерном сером фоне. Хотелось бы, чтобы алгоритм таксономии мог выделить эти три сгустка, каждый со своим диаметром, отделив их от точек фона, т. е. мог бы решать задачу выделения ярких созвездий на звездном небе. Для решения таких задач предназначен один из алгоритмов семейства FOREL — алгоритм KOLAPS. Его можно разделить на два этапа.

Рис. 7.

На первом этапе ищутся потенциальные центры будущих таксонов, а на втором — делается проверка, действительно ли выбранная точка является центром устойчивого таксона.

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

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

максимизации функционала .