Кластеризация.
Продолжение
Сегментация
Алгоритм k-средних (k-means)
Выборка начальных центроидов может быть как рандомной так и по определенному алгоритму.
1.Входим в цикл, который продолжается до тех пор, пока центроиды кластеров не перестанут изменять свое положение.
2. Для каждого объекта смотрим, к какому центроиду какого кластера он является близлежащим. 3.Присваиваем объект к кластеру этого центроида. 4.Перебрали все объекты? Пересчитываем новые координаты центроидов k кластеров.
5. Проверяем координаты новых центроидов. Если они соответственно равны предыдущим центроидам — выходим из цикла, если нет возвращаемся к пункту 3.
Пути повышения точности алгоритма k- means
1.При выборе первоначального положения кластеров необходимо максимально разнести их.
2.Провести процесс кластеризации несколько раз.
3.Выбрать оптимальное число кластеров.
Определение оптимального числа кластеров. Критерий Elbow Метод «локтя»
Классический метод для оценки числа кластеров методом k-means.
Проводится кластеризация с увеличением числа кластеров.
Рассчитывается коэффициент, отражающий степень «гетерогенности» кластеров.
Выбираем первую точку перегиба как оптимальное число кластеров.
Определение оптимального числа кластеров. «Силуэт»
Проводится кластеризация с увеличением числа кластеров.
Рассчитывается значение «силуэта».
Выбираем первую точку максимума как оптимальное число кластеров.
Более надежен (например, при наложении кластеров).
Коэффициент:
(b - a) / max(a, b)
a – среднее внутрикластерное расстояние;
b – среднее расстояние до ближайшего кластера.
Методы расчета межкласторных расстояний
Метод DBSCAN
DBSCAN (Density-based spatial clustering of applications with noise, плотностной алгоритм пространственной кластеризации с присутствием шума) оперирует плотностью данных.
Работа алгоритма DBSCAN
Сравнение алгоритмов кластеризации