14.9. Автоматическое формирование кластера

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

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