5. Кластерный анализ, часть II: сетевые графы и определение сообществ

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

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

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

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

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

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

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

На высоком уровне модульная максимизация «награждает» вас каждый раз, когда вы помещаете в один кластер двоих хороших друзей, и «штрафует», когда вы помещаете вместе двоих незнакомцев. Собирая «награды» и избегая, по возможности, «штрафов», эта техника помогает вам добиться естественной кластеризации клиентов, причем, в отличие от кластеризации по k-средним вам не нужно выбирать k. Алгоритм делает это за вас! Таким образом, этот метод использует неконтролируемое машинное обучение на новом уровне знаний.

Кроме того, безусловно привлекательная с математической точки зрения кластеризация по k-средним служит нам уже полвека. А техника, использованная в этой главе, разработана всего пару лет назад. Настоящий пирожок с пылу с жару!