Геометрия скоплений

Шаг 1

Разберём подробнее алгоритм k-means

Как он работает:

1. Алгоритм берёт k случайных точек и раскидывает их по пространству — это будущие центры скоплений (центроиды).
2. Считает расстояние от каждого центра до каждой точки данных.
3. Каждая точка отправляется в тот кластер, к центру которого она ближе всего.
4. Затем пересчитываются новые центры кластеров — так, чтобы сумма расстояний от центра до всех точек его кластера была минимальной.
5. Центры сдвинулись — значит, и расстояния до точек изменились. Алгоритм повторяет этот цикл (снова перераспределяет точки и снова двигает центры) до тех пор, пока центры не перестанут смещаться.

Шаг 2

Первое, что нужно понять - алгоритм в общем виде очень чувствителен к выбору осей

Если взять стандартную евклидову норму, то эта проблема частично решается (одна из главных причин, почему её чаще всего используют)

Главный плюс евклидовой норм - инвариантность к поворотам

Если все оси повернуть базис и запустить алгоритм, то он выдаст тот же результат

*Алгоритм редко выдаёт абсолютно одинаковые результаты из-за случайности изначально раскиданных точек, но если этим пренебречь, то поворот на результат не влияет

Остальные нормы такой привилегии не имеют

Если взять ту же норму манхэттена, то с повёрнутыми осями алгоритм выдаст другой результат

Поэтому, при использовании неевклидовых норм следует понимать, насколько вы уверены в своих осях

Шаг 3

Вторая важная особенность - неустойчивость к масштабированию

В теории, если в данных есть какие-то скопления, то этот факт не должен портиться, если мерить не условными метрами, а сантиметрами

Но k-means крайне неустойчив к этому и нужно за этим следить

Самый простой вариант решения этой проблемы - перед вставкой в алгоритм масштабировать все оси от -1 до 1 обычной линейной заменой координатНо в некоторых ситуациях и этого может быть недостаточно

Шаг 4

Представим датасет для магазина с двумя признаками:

1. Количество дней с момента регистрации

2. Сумма покупок

Задача - классифицировать покупателей

Возьмём условных четырёх клиентов:

Клиент	Дней на сайте	Сумма покупок (X)	Описание типажа
Анна	30	1 000 ₽	Новичок с маленькой покупкой
Борис	30	10 000 ₽	Новичок, сделавший ощутимый заказ
Виктор	200	100 000 ₽	Постоянный клиент со средним чеком
Галина	200	10 000 000 ₽	«Олигарх» (выброс)

С точки зрения бизнеса, Анна и Борис совсем разные клиенты и хорошо бы их различать

Но обычный k-means, скорее всего, засунет их в один кластер из-за малых различий в данных (учитывая, что Галина потратила вообще 100 000 раз больше, чем Анна)

И простое линейное масштабирование никак это не изменит:

• Анна  0.0001
• Борис 0.001
• Виктор 0.0099
• Галина 1.0000

Так даже лучше видно, насколько маленькая разница между Анной и Борисом, для k-means точки находятся практически вплотную

В данном случае для решения этой проблемы можно масштабировать не линейно, а логарифмически

Применим к данным обычный логарифм по основанию 10:

• Анна  1000 -> 3
• Борис  -> 10000 -> 4
• Виктор 100000 -> 5
• Галина 1000000 -> 7

Теперь данные для анализа становятся очень удобными и классифицировать клиентов будет сильно проще