Привет, Хабр! В этой части мы опишем вам алгоритм, с помощью которого были получены цвета на графах из первой части. В основе алгоритма лежит k-medoids — довольно простой и прозрачный метод. Он представляет собой вариант популярного k-means, про который наверняка большинство из вас уже имеет представление.

В отличие от k-means, в k-medoids в качестве центроидов может выступать не любая точка, а только какие-то из имеющихся наблюдений. Так как в графе между вершинами расстояние определить можно, k-medoids годится для кластеризации графа. Главная проблема этого метода — необходимость явного задания числа кластеров, то есть это не выделение сообществ (сommunity detection), а оптимальное разбиение на заданное количество частей (graph partitioning).

С этим можно бороться двумя путями:

В этом блоге мы уже много о чём поговорили: были краткие описания основных рекомендательных алгоритмов (постановка задачи, user-based и item-based, SVD: 1, 2, 3, 4), о нескольких моделях для работы с контентом (наивный Байес, LDA, обзор методов анализа текстов), был цикл статей о холодном старте (постановка задачи, текстмайнинг, теги), была мини-серия о многоруких бандитах (часть 1, часть 2).

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