Кластеризация информации. 
Методы подготовки персонализированного контента

Кластеризация (или кластерный анализ) — это задача разбиения множества объектов на группы, называемые кластерами[2]. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных групп должны быть как можно более отличны. Главное отличие кластеризации от классификации состоит в том, что перечень групп четко не задан и определяется в процессе работы алгоритма.

Формально задача кластеризации звучит следующим образом[5]. Пусть — множество объектов, — множество номеров (имён, меток) кластеров. Задана функция расстояния между объектами. Имеется конечная обучающая выборка объектов. Требуется разбить выборку на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из объектов, близких по метрике, а объекты разных кластеров существенно отличались. При этом каждому объекту приписывается номер кластера .

Применение кластерного анализа в общем виде сводится к следующим этапам:

• 1. Определение множества переменных, по которым будут оцениваться объекты в выборке. При необходимости — нормализация значений переменных.
• 2. Вычисление значений меры сходства между объектами.
• 3. Применение метода кластерного анализа для создания групп сходных объектов (кластеров).

Алгоритмы кластеризации можно классифицировать по методам следующим образом[5]:

• — Иерархический подход (направление «снизу-вверх» или «сверху-вниз»). Результатом работы иерархического алгоритма является дендограмма (иерархия), позволяющая разбить исходное множество объектов на любое число кластеров. Два наиболее популярных алгоритма строят разбиение «снизу-вверх»: Single-link на каждом шаге объединяет два кластера с наименьшим расстоянием между двумя любыми представителями, а Complete-link — между двумя наиболее удалёнными представителями. Самым популярным иерархическим алгоритмом с направлением «сверху-вниз» является алгоритм минимального покрывающего дерева, который в свою очередь является представителем семейства алгоритмов поиска кратчайшего пути в графе.
• — Вероятностный подход. Предполагается, что каждый рассматриваемый объект относится к одному из k классов. Наиболее известным представителем является алгоритм k-means.
• — Подходы на основе систем искусственного интеллекта. Наиболее известным представителем является алгоритм C-means.

Всего существует девять наиболее распространённых алгоритмов кластеризации информации[6]: CURE, BIRCH, MST, k-means, PAM, CLOPE, HCM, Fuzzy C-means, WaveCluster. Достоинства и недостатки этих алгоритмов приведены в таблице 1.

Таблица 1.

Так как в настоящее время наиболее востребованными являются вероятностные подходы и подходы на основе нейронных сетей[7][8], далее будут рассмотрены алгоритмы k-means и C-means.