Цель кластеризации методом k-средних – выбрать несколько точек в пространстве и превратить их в k группы (где k – любое выбранное вами число). Каждая группа определена точкой в центре вроде флага, воткнутого в Луну и сигнализирующего: «Эй, вот центр моей группы! Присоединяйтесь, если к этому флагу вы ближе, чем к остальным!» Этот центр группы (с официальным названием кластерный центроид) – то самое среднее из названия метода k-средних.

Вспомним для примера школьные танцы. Если вы сумели стереть ужас этого «развлечения» из своей памяти, я очень извиняюсь за возвращение таких болезненных воспоминаний.

Герои нашего примера – ученики средней школы Макакне, пришедшие на танцевальный вечер под романтическим названием «Бал на дне морском», – рассеяны по актовому залу, как показано на рис. 2–1. Я даже подрисовал в Photoshop паркет, чтобы было легче представить ситуацию.

А вот примеры песен, под которые эти юные лидеры свободного мира будут неуклюже танцевать (если вдруг вам захочется музыкального сопровождения, к примеру, на Spotify):

• Styx: Come Sail Away

• Everything But the Girl: Missing

• Ace of Base: All that She Wants

• Soft Cell: Tainted Love

• Montell Jordan: This is How We Do It

• Eiffel 65: Blue

Теперь кластеризация по k-средним зависит от количества кластеров, на которое вы желаете поделить присутствующих. Давайте остановимся для начала на трех кластерах (далее в этой главе мы рассмотрим вопрос выбора k). Алгоритм размещает три флажка на полу актового зала некоторым допустимым образом, как показано на рис. 2–2, где вы видите 3 начальных флажка, распределенных по полу и отмеченных черными кружками.

В кластеризации методом k-средних танцоры привязаны к ближайшему для них кластерному центру, так что между двумя любыми центрами на полу можно нарисовать демаркационную линию. Таким образом, если танцор находится на одной стороне линии, он принадлежит к одной группе, если по другую сторону – то уже к другой (как на рис. 2–3).

Используя эти демаркационные линии, разделим танцоров на группы и раскрасим соответствующим образом, как на рис. 2–4. Эта диаграмма, разделяющая пространство на многоугольники, определенные близостью к тому или иному кластерному центру, называется диаграммой Вороного.

Посмотрим на наше первоначальное разделение. Что-то не так, не правда ли? Пространство разделено довольно странным образом: нижняя левая группа осталась пустой, а на границе верхней правой группы, напротив, много людей.

Алгоритм кластеризации методом k-средних перемещает кластерные центры по полу, пока не достигнет наилучшего результата.

Как определить «наилучший результат»? Каждый присутствующий отстоит на сколько-то от своего кластерного центра. Чем меньше среднее расстояние от участников до центра их группы, тем лучше результат.

Теперь, как я и обещал в главе 1, вводим слово «минимизация» – оно вам очень пригодится в оптимизации модели для лучшего расположения кластерных центров. В данной главе вы будете заставлять «Поиск решения» передвигать кластерные центры бессчетное количество раз. Способ, который использует «Поиск решения» для нахождения наилучшего расположения кластерных центров, – это медленное итеративное перемещение их по поверхности с фиксацией лучших найденных результатов и комбинированием их (буквально спариванием, как скаковых лошадей) для нахождения наилучшего положения.

Так что если диаграмма на рис. 2–4 выглядит довольно бледно, «Поиск решения» может внезапно расположить центры как на рис. 2–5. Таким образом среднее расстояние между каждым танцором и его центром немного уменьшится.

Очевидно, что рано или поздно «Поиск решения» поймет, что центры должны быть размещены в середине каждой группы танцоров, как показано на рис. 2–6.

Отлично! Вот так выглядит идеальная кластеризация. Кластерные центры находятся в центре каждой группы танцоров, минимизируя среднее расстояние между танцором и ближайшим центром. Теперь, когда кластеризация закончена, время перейти к развлекательной части, а именно: попытке понять, что же эти кластеры означают.

Если вы узнали цвет волос танцоров, их политические предпочтения или время преодоления ими стометровки, то кластеризация не имеет особого смысла. Но решив определить возраст и пол присутствующих, вы начнете видеть некоторые общие тенденции. Небольшая группа внизу – это пожилые люди, скорее всего сопровождающие. Группа слева вся состоит из мальчиков, а группа справа – из девочек. И все очень боятся танцевать друг с другом.

Таким образом, метод k-средних позволил вам разделить множество посетителей танцев на группы и скоррелировать характеристики каждого посетителя с принадлежностью к определенному кластеру, чтобы понять причину разделения.

Теперь вы наверняка говорите себе: «Да ладно, что за глупости. Я уже до начала знал ответ». Вы правы. В этом примере – да. Я специально привел такой «игрушечный» пример, будучи уверенным, что вы можете решить его, просто взглянув на точки. Действие происходит в двумерном пространстве, в котором кластеризация производится элементарно с помощью глаз.

Но что, если вы держите магазин, реализующий тысячи товаров? Некоторые покупатели совершили одну или две покупки за последние два года. Другие – десятки. И каждый покупал что-то свое.

Как вы кластеризируете их на таком «танцполе»? Начнем с того, что этот танцпол не двумерный, и даже не трехмерный. Это тысячемерное пространство реализации товара, в котором покупатель приобрел или не приобрел товар в каждом измерении. Видите, как быстро проблема кластеризации начинает выходить за пределы способностей «глазного яблока первого разряда», как любят говорить мои друзья-военные.