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

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

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

1. Алгоритм берёт k случайных точек и раскидывает их по пространству — это будущие центры скоплений (центроиды).

2. Считает расстояние от каждого центра до каждой точки данных.

3. Каждая точка отправляется в тот кластер, к центру которого она ближе всего.

4. Затем пересчитываются новые центры кластеров — так, чтобы сумма расстояний от центра до всех точек его кластера была минимальной.

5. Центры сдвинулись — значит, и расстояния до точек изменились. Алгоритм повторяет этот цикл (снова перераспределяет точки и снова двигает центры) до тех пор, пока центры не перестанут смещаться.

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

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

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

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

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

Представим датасет для магазина с двумя признаками:
1. Количество дней с момента регистрации
2. Сумма покупок

Задача - классифицировать покупателей 
Возьмём условных четырёх клиентов:

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

• Анна  0.0001

• Борис 0.001

• Виктор 0.0099

• Галина 1.0000

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

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

• Анна  1000 -> 3

• Борис  -> 10000 -> 4

• Виктор 100000 -> 5

• Галина 1000000 -> 7

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