Вопрос 37: Кластерный анализ. Алгоритмы кластерного анализа
(Шаги алгоритмов писались мной при написании доклада, поэтому они корявые)
Кластеризация или кластерный анализ – это задача разбиения заданной выборки объектов на группы, называемые кластерами. Объекты, находящиеся в одном кластере, должны иметь схожие свойства, а объекты из разных групп должны быть отличны друг от друга.
Типы кластеризации (по моделям):
Connectivity models (Модели, основанные на связности).
Анализируемое множество объектов характеризуется определенной степенью связности. За связность, в большинстве случаях, принимается расстояние между объектами.
Наиболее известый алгоритм данного типа - агломеративная иерархическая кластеризация.
Исходные данные:
- Х - множество из n объектов.
Алгоритм
- Выявляются два объекта или кластеры, расстояние между которыми является минимальным;
- Происходит объединение этих объектов;
- Если есть необъединенные кластеры, то возвращаемся на 1 шаг. Если все объекты слились в один кластер, то алгоритм заканчивает действие.
Centroid models (Модели, основанные на центроидах)
Действие алгоритмов данного типа такого, что стремится минимизировать суммарное квадратичное отклонение точек кластеров от центров этих кластеров. Центр масс или центроид кластера - точка в пространстве характеристических векторов со средними для данного кластера значениями характеристик.
Самый известный алгоритм данного типа - k-means.
Исходные данные:
- k – число кластеров;
- Х - множество из n объектов. Алгоритм
- Случайно выбрать k точек, являющихся начальными «центрами масс» кластеров (любые k из n объектов или случайные точки);
- Отнести каждый объект к кластеру с ближайшим центром масс;
- Пересчитать центры масс кластеров согласно текущему членству;
- Если критерий остановки алгоритма не удовлетворен, вернуться к шагу 2.
Distribution models (Модели, основанные на распределении)
Кластеризация данного вида напрямую связана с использованием моделей распределения. Кластеры определяются на основе вероятности того, что включенные объекты будут принадлежать одному распределению
Самый известный алгоритм данного типа - EM-алгоритм.
(Этот алгоритм - полная дичь, распишу только главные этапы, не думаю, что Новакова еще что-то требовать будет).
Алгоритм Итеративно выполняются следующие два шага:
- E-шаг: используя текущее значение вектора параметров, вычисляются значения скрытых переменных с помощью формулы Байеса;
- М-шаг: переоценка вектора параметров, используя текущие значения скрытых переменных; Итерации происходят до сходимости (норма разности векторов скрытых переменных или изменение логарифмического правдоподобия на каждой итерации не будет превышать заданную константу) или достижения максимального числа итераций.
Density models (Модели, основанные на плостности)
В этой группе анализа, кластеры определяются на основе определения областей с большей плотностью, чем в остальной части пространства.
Самый популярный алгоритм - DBSCAN. Дословно название переводится как плотностной алгоритм пространственной кластеризации с присутствием шума.
Исходные данные *множество объектов Х, для которых задана метрическая функция расстояния ρ. Также задаются параметры алгоритма:
- ε – максимальное расстояние между соседними объектами;
- minPts – минимальное количество соседних объектов, необходимых для образования кластера. Алгоритм
- Выбирается необработанный объект p;
- Находим соседние объекты в ε-окрестности объекта p;
- Сравниваем количество соседних объектов с minPts, определяя, является ли p ядровым объектом. Объект p называется ядровым, если в ε-окрестности точки p находятся minPts объектов (включая сам объект p).
- Если объект p является ядровым, то создаём новый кластер и запускаем поиск в ширину из данного объекта по другим необработанным объектам, находя все объекты кластера.
- Если объект p не является ядровым, то отмечаем его как шум. Алгоритм продолжается до тех пор, пока не будут обработаны все объекты.