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

Есть несколько алгоритмов разделения множества исходных данных на кластеры. В большинстве из этих алгоритмов при выполнении кластеризации в качестве меры близости объектов используются различные способы определения расстояний. Использование расстояния в качестве меры близости является естественным, если учесть, что исследуемые объекты изображаются точками в евклидовом пространстве. Однако критерии, основанные на том или ином способе определения расстояния, являются только одним из возможных способов определения кластеров. Хартиган [18] указал шесть типов алгоритмов кластеризации, отличающихся друг от друга способами выделения кластеров.

1.Сортировка

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

2.Перегруппировка

Задается некоторое начальное распределение объектов по кластерам. Далее объекты перемещают из одного кластера в другой в соответствии с каким-либо критерием, например величиной стандартного отклонения для данного кластера. Алгоритмы перегруппировки отличаются высокой скоростью, однако конечный результат иногда зависит от вида начального распределения.

3. Объединение

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

4. Разбиение

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

5. Добавление

Эти алгоритмы работают путем добавления элементов выборки в уже существующие кластеры. Ограниченность этих алгоритмов очевидна.

6. Поиск

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

Существует много различных алгоритмов, однако ни один из них не приспособлен для решения любой из возникающих задач. Некоторые алгоритмы, например алгоритм ISODATA Болла и Холла [19,20] может осуществлять процедуры добавления, поиска, объединения и разбиения. Такие алгоритмы имеют более широкую область применения, однако ни один из них не является универсальным. К тому же многие алгоритмы являются эвристическими по своей природе, и поэтому успех их реализации, в конечном счете, зависит от мастерства исследователя. И наконец, последний недостаток методов кластеризации заключается в том, что иногда возникают трудности с отнесением неизвестного объекта к одному из уже имеющихся классов.

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