3.3.8. Кластеризация, основанная на теории графов

Алгоритмы построения кластеров, рассмотренные в предыдущих разделах, используют меры сходства, в основу которых положено понятие расстояния. Эти алгоритмы оказались полезными

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

Другой возможный подход к отысканию кластеров связан с использованием ряда фундаментальных понятий теории графов. Этот подход предусматривает построение в первую очередь графа образов по заданной выборке. Образы, вошедшие в предъявленную для классификации выборку, представляются вершинами графа, причем вершины и связываются ребром, если соответствующие им образы сходны или между ними существует некоторое отношение. Считается, что образы сходны, если значение соответствующей меры сходства оказывается больше величины заданного порога Т. Меру сходства можно использовать для построения матрицы сходства элементами которой являются 0 и 1. Матрица сходства обеспечивает возможность применять при построении графа образа систематическую процедуру. Поскольку клики графа образа соответствуют кластерам, для отыскания последних можно воспользоваться процедурой выделения клик графа образов. В литературе описано несколько алгоритмов и программ поиска клик графа. Читателю можно рекомендовать обратиться к работам Боннера [1969], Джардина и Сибсона [1968], Харари [1973], Огастсона и Минкера [1970], Зана [1971] и Остина и Ту [1973]. Данный теоретико-графовый подход можно использовать и для выделения кластеров в тех случаях, когда классифицируемые образы характеризуются не числовыми оценками, а отношениями, что позволяет сделать вывод о его применимости для решения широкого спектра задач кластеризации.