В практике обычно реализуются агломеративные методы кластеризации.
Обычно перед началом классификации данные стандартизуются (вычитается среднее и производится деление на корень квадратный из дисперсии). Полученные в результате стандартизации переменные имеют нулевое среднее и единичную дисперсию.
Можно выбрать следующие правила иерархического объединения кластеров:
- метод одиночной связи,
- метод полной связи,
- невзвешенный метод «средней связи»,
- взвешенный метод «средней связи»,
- взвешенный центроидный метод,
- метод Уорда.
Данные алгоритмы различаются правилами объединения объектов в кластеры.
В методе одиночной связи на первом шаге объединяются два объекта, имеющие между собой максимальную меру сходства. На следующем шаге к ним присоединяется объект с максимальной мерой сходства с одним из объектов кластера. Таким образом, процесс продолжается далее. Итак, для включения объекта в кластер требуется максимальное сходство лишь с одним членом кластера. Отсюда и название метода одиночной связи, нужна только одна связь, чтобы присоединить объект к кластеру: связь нового элемента с кластером определяется только по одному из элементов кластера. Недостатком этого метода является образование слишком больших «продолговатых» кластеров.
Метод полных связей позволяет устранить указанный недостаток. Здесь мера сходства между объектом – кандидатом на включение в кластер и всеми членами кластера не может быть меньше некоторого порогового значения. В методе средней связи мера сходства между кандидатом и членами кластера усредняется, например, берется просто среднее арифметическое мер сходства.
Идея еще одного агломеративного метода – метода Уорда состоит в том, чтобы проводить объединение, дающее минимальное приращение внутригрупповой суммы квадратов отклонений. Замечено, что метод Уорда приводит к образованию кластеров примерно равных размеров и имеющих форму гиперсфер.
Рассмотрим еще итеративный метод группировки k -средних. Данный метод работает непосредственно с объектами, а не с матрицей сходства.
В методе k -среднихобъект относится к тому классу, расстояние до которого минимально. Расстояние понимается как евклидово расстояние, то есть объекты рассматриваются как точки евклидова пространства.
Как определить евклидово расстояние, мы уже знаем. Но как определить расстояние от объекта до совокупности объектов? Оказывается, это можно сделать следующим способом: каждый класс объектов имеет центр тяжести (рассмотрите, как и ранее, простейший случай – представьте, что объект имеет только два параметра, тогда его можно изобразить точкой на плоскости, а группа объектов – это просто группа точек).
Расстояние между объектом и классом есть расстояние между объектом и центром класса. Но как вычислить центр класса? Например, взять средние по каждому параметру. Тогда расстояние между объектом и группой объектов вполне определено и алгоритм может работать.
Представьте, что число объектов в группе равно 2. Соедините эти точки отрезком прямой и найдите его середину. Это и будет центр тяжести группы, состоящей из двух точек. Расстояние от этого центра до исходной точки будет искомым расстоянием.
Принципиально метод k -средних «работает» следующим образом:
1 вначале задается некоторое разбиение данных на кластеры (число кластеров определяется заранее); вычисляются центры тяжести кластеров;
2 происходит перемещение точек: каждая точка помещается в ближайший к ней кластер;
3 вычисляются центры тяжести новых кластеров;
4 шаги 2, 3 повторяются, пока не будет найдена стабильная конфигурация (то есть кластеры перестанут изменяться) или число итераций не превысит заданное пользователем. Итоговая конфигурация и является искомой.
