Основные идеи и методы кластерного анализа

История кластерного анализа

Классификация была издревле известна человечеству. Прообраз этого понятия можно найти в первых строках книги Бытия (Быт. 1:21). Известны классические примеры классификации у Платона и Аристотеля [Новая философская энциклопедия, 2001], однако систематизация процесса классификации долгое время не проводилась. В начале XIX века французский ботаник Огюстен Декандоль [Брокгауз, Ефрон 1907] предложил свою теорию классификации и систематизации, названную впоследствии таксономией. Декантоль стремился классифицировать все существующие растения, объединяя их в однородные группы разных уровней, образующих иерархическую структуру (вид, род, семейство, класс, отдел). Данный метод вскоре получил широкое распространение и за пределами биологии. Теперь он положен в основу иерархических методов кластеризации.

Немецким биологом Ф. Гейнке был предложен метод группировки объектов по нескольким признакам. Всякий новый объект принадлежал той группе, к центру которой он ближе всего — идея, легшая в основу метода k средних.

Пионером применения базовых принципов кластеризации считается польский антрополог К. Чекановский. В 1913 году он предложил идею «структурной классификации» [Плюта 1980]: выделять компактные группы объектов. Для этого он разработал и оригинальный метод, применяемый при диагонализации признаковой матрицы.

В 1925 году советским гидробиологом П. В. Терентьевым был разработан метод корреляционных плеяд [Терентьев 1959] - это по-видимому первый алгоритм, направленный на выявление групп тесно коррелирующих признаков. Идеи этого алгоритма легли в основу многих пороговых алгоритмов на графах, например метода связных компонент.

Термин кластерный анализ впервые применил английский ученый Р. Трион [Trion 1939].

В 50-х годах ситуация стала развиваться значительно быстрее. Появились ЭВМ, способные обрабатывать данные гораздо быстрее человека. Алгоритмы усложнялись и совершенствовались, объемы данных росли и вскоре кластерный анализ завоевал прочное место в ряду прикладных дисциплин. Появилась возможность обрабатывать такое количество информации, которое прежде было человеку не под силу.

Следующие два десятилетия считаются золотым веком кластерного анализа. Тогда были получены основные результаты, изучен метод k-средних, иерархические процедуры, диагонализация и пр. Важную роль в этом сыграли и советские ученые [Мандель 1988].

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