Кластерный анализ на взвешенных гиперграфах

Гиперграф – это граф, ребра которого могут соединять более одного узла [5]. Задача кластерного анализа на таком графе сводится к нахождению его минимального разделения. Это разделение представляет собой удаление набора гиперребер (с минимальными весами), делящее гиперграф на k несвязных компонент.

Подходов к определению гиперграфа на семантическом пространстве документов и терминов несколько. В самом простом из них [5] каждому вектору x_j соответствует вершина v_j. Каждый термин, таким образом, является гиперребром, соединяющим все вершины. Весом такого гиперребра является общее количество употреблений данного термина во всем наборе документов. При разделении важность такого ребра определяется его весом. Достоинством данного подхода является отсутствие необходимости подсчета значения сходства для каждой пары документов. Недостатком же, очевидно, является неиспользование локальных частот встречаемости терминов в документах, что делает этот алгоритм совершенно неадекватным.

Остальные алгоритмы, основанные на гиперграфах значительно сложнее. Наиболее интересный, заслуживающий внимания алгоритм кластерного анализа, основанной на гиперграфе, построен с использованием ассоциативных правил.