9.3. Классификация на графах

Опишем методы и алгоритмы классификации, основанные на представлении исходной информации о классифицируемых объектах в виде графа близости , вершины которого соответствуют объектам а ребра соединяющие вершины и — неупорядоченным парам Длина ребра считается равной для выбранной меры близости между объектами

В изложении будем существенно опираться на работу Д. В. Матулы из [83, с. 83—111].

9.3.1. Основные понятия и определения.

Предварительные сведения из теории графов приведены в [12, п. 4.2.1].

Определение 9.1. Граф , где называется полным, если любые его две вершины и соединены ребром .

Например, граф близости совокупности объектов О является полным. В задачах классификации при наличии ограничений на связи между объектами (см. § 9.2) используются неполные графы (В-графы близости, где ), полученные из полного графа близости удалением ребер при условии, что

Определение 9.2. Пусть — некоторый граф. Вектором инцидентности вершины называется вектор где если если

Степенью вершины в графе G называется число Ясно, что граф G полный тогда и только тогда, когда степень любой его вершины равна

Определение 9.3. Подграф называется максимальным по отношению к некоторому свойству F (-максимальным), если G обладает свойством F и в G не существует подграфа обладающего свойством F, такого, что

Пример 9.4. Пусть — соответствующее подмножество вершин графа близости . Тогда среди всех подграфов с множеством вершин V максимальным является граф близости

Напомним, что граф называется связанным, если любые две его вершины можно соединить последовательностью ребер где - связать вершины путем»

Определение 9.4. Максимальный связанный подграф графа называется компонентой.

Пусть — две компоненты данного графа . Тогда непосредственно из определений вытекает, что как подмножества в У. имеют пустое пересечение.

9.3.2. Алгоритм выделения компонент графа.

В рамках общего подхода, изложенного в [83, с. 83—111], каждый метод классификации на графах опирается на процедуру выделения соответствующих -максимальных подграфов. Более подробно рассмотрим это в п. 9.3.4. Здесь же опишем процедуру, лежащую в основе ряда известных методов, связанных с выделением компонент графа.

Исходя из некоторой модели класса, описываемой в терминах теории графов (см. п. 9.3.3 и 9.3.4), строится подграф G графа близости с тем же множеством вершин V, т. е. , где Е получается из Е удалением ребер, не отвечающих модели класса. Затем применяется алгоритм выделения компонент графа и тем самым находится разбиение множества V на подмножества т. е. классификация множества объектов О.

Указанная процедура, примененная к В-графу близости, позволяет провести классификацию при наличии матрицы ограничений В на связи между объектами.

Определение 9.5. Подграф некоторого графа называется -полным подграфом (короче, -подграфом), если любое ребро из G, соединяющее какие-либо вершины из G, принадлежит G, т. е.

Непосредственно из определения получаем:

1) существует взаимно-однозначное соответствие между подмножествами множества вершин V и -подграфами графа

2) каждая компонента G графа G является его -подграфом.

Опираясь на эти утверждения, опишем основной этап алгоритма.

Шаг А. Пусть -связанный подграф графа

Положим , т. e. введем множество вершин в G, связанных с вершинами из G хотя бы одним ребром. Тогда -подграф графа G, соответствующий множеству вершин будет связанным. Если то получаем, что является компонентой, содержащей данный граф Если то аналогично построим множество вершин и -подграф соответствующий множеству вершин . Так как — конечное множество, то последовательность множеств стабилизируется, т. е. для некоторого q и получим -подграф являющийся компонентой графа G, содержащей данный граф

Замечание. Программную реализацию шага А можно провести, оперируя только векторами инцидентности вершин (см. определение 9.2).

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

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

Рассмотрим матрицу взаимных близостей между классифицируемыми объектами . Без ограничения общности можно считать, что причем тогда и только тогда, когда Пусть — некоторая последовательность пороговых значений. Тогда определена последовательность подграфов графа близости где . Заметим, что . Граф называется графом близости на уровне

Опишем сначала общую схему алгоритмов.

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

Ясно, что а в тех случаях, когда нет априорных ограничений, на связи между объектами, то и В общем случае граф представляет собой В-граф близости, где — матрица ограничений на связи между объектами.

Схема алгоритма

1. На вход подается граф множество его компонент задает разбиение совокупности объектов на одноточечные классы.

2. На вход шага, подается граф разбитый на компоненты и граф G. Так как то каждая компонента графа является связанным подграфом графа G. Поэтому можно, начиная, например, с при помощи алгоритма выделения компонент (см. п. 9.3.2) получить компоненту графа G и перейти к выделению компонент графа Так как компоненты графа не пересекаются, то компонента графа может входить только в одну компоненту графа . Следовательно, выделение компонент в можно начинать с одной из компонент графа не вошедших в и т. д. до тех пор, пока не будут выделены все компоненты графа Итогом шага является разбиение графа G на компоненты и, следовательно, разбиение множества вершин V на непересекающиеся подмножества

Соответствующая классификация множества объектов называется классификацией на уровне

Алгоритм заканчивает работу на шаге.

В результате получаем последовательность вложенных разбиений т. е. иерархию на множестве объектов О.

Рассмотрим теперь наиболее известные примеры алгоритмов, основанные на простых моделях классов и соответственно простых операторах U.

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

Определение 9.6. Алгоритм классификации на графах с тождественным оператором U, т. е. для всех t называется односвязывающим.

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

Определение 9.7. Алгоритм классификации на графах с оператором U, удаляющим в графах ребра (связи), идущие к вершинам степени, меньше к, называется -связывающим.

Название алгоритма объясняется тем, что он соответствует модели класса, в которой представитель данного класса связан с остальными, по крайней мере, к связями.

Определение 9.8. При данном максимальный связанный подграф G графа G называется -связкой, если степень каждой его вершины не меньше к.

Заметим, что каждая -связка графа является компонентой графа для оператора U из определения 9.7. Следовательно, А-связывающий алгоритм выделяет в исследуемом множестве объектов все -связки на каждом уровне близости.

9.3.4. Метод послойной классификации. Общий подход к построению алгоритмов классификации на графах.

Рассмотрим сначала, какие максимальные подграфы наряду с k-связкой используются для описания структур классов.

Определение 9.9. При данном к, k 1, максимальный связанный подграф графа G называется к-компонентой, если при любом разбиении множества вершин V на непересекающиеся подмножества существует, по крайней мере, k связей (ребер) в Е между подмножествами

Определение 9.10. Связанный подграф графа G называется -свяэанным, если и удаление любых вершин из V оставляет его связанным, т. е. любой подграф у которого является связанным.

Определение 9.11. При данном , максимальный -связанный подграф называется -блоком.

Определение 9.12. Кликой графа G называется максимальный полный подграф Клика графа, содержащая более 6 вершин, называется -кликой. Непосредственно из определений 9.8-9.12 следует:

1) для любого графа G каждая -клика является подграфом некоторого -блока, каждый -блок является подграфом некоторой -компоненты, которая в свою очередь является подграфом некоторой -связки (рис. 9.1, где );

Рис. 9.1. Классификация на графе. Компоненты ; 2-связки ; 2-компоненты ; 2-блоки ; 2-клики

2) любые две -компоненты и, следовательно, любые две -связки одного графа G имеют пустое пересечение;

3) пересечение любых двух -блоков одного графа может содержать не более чем общих вершин.

Для удобства изложения будем считать, что каждая вершина графа G, не вошедшая ни в один подграф, максимальный по отношению к выбранному свойству F, формально обладает этим свойством. Например, будем говорить, что вершина, не вошедшая ни в одну -компоненту графа G, сама является его -компонентой.

При таком соглашении можно сказать, что выделение в данном графе всех его подграфов , максимальных по отношению к выбранному свойству F, задает покрытие множества вершин У подмножествами

В случае -компонент и -связок получается разбиение множества V на непересекающиеся подмножества, а в случае -блоков — покрытие, каждые два множества которого имеют не более чем () общую точку.

Теперь можно описать общую схему алгоритма классификации на графах как естественное обобщение схемы из п. 9.3.2.

Пусть, как и выше, -последовательность подграфов графа G, где G — граф близости на уровне Параметром алгоритма является процедура выделения в графе G всех его подграфов, максимальных по отношению к выбранному свойству F. Эти подграфы будем называть -компонентами графа G. Роль компонент, в зависимости от F, играют -компоненты, -связки, -блоки или -клики.

Схема алгоритма

1. На вход подается граф множество его -компонент задает покрытие совокупности объектов одноточечными классами.

2. На вход шага, подается граф покрытый -компонентами и граф Так как то каждая -компонента графа является связным подграфом в G. На вход процедуры подается граф При помощи нее он достраивается до -компоненты графа Затем среди -компонент графа берется та, которая не вошла в и при помощи той же процедуры достраивается до следующей -компоненты графа G и так далее, до тех пор, пока не будут выделены все -компоненты графа Соответствующее покрытие совокупности объектов называется -классификацией ее на уровне Классы могут пересекаться, как в случае классификации -блоками, но ни один класс не может целиком содержать другой.

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

В результате получается последовательность вложенных покрытий которая называется послойной -классификацией.

В тех случаях, когда для каждого t покрытие S состоит из непересекающихся классов, то -классификация является иерархической, т. е. задает иерархию на множестве объектов (см. определение 8.1).

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

Эффективность алгоритмов послойных -классификаций определяется эффективностью реализации процедуры выделения в графе всех его -компонент. Как следует из п. 9.3.3, в случае -связок существует достаточно эффективная процедура благодаря тому, что каждая -связка графа является компонентой графа G, полученного из удалением некоторых связей.

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

Для построения алгоритмов классификации -компонентами и -блоками большое значение имеют следующие результаты, полученные К. Менгером [83, с. 102—106].

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

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

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

Опишем, например, как на основе следствия 9.1 построить процедуру выделения -компонент графа

Схема алгоритма

1. Применяя процедуру выделения -связок из п. 9.3.3, разобьем граф G на -связки

2. Пусть — некоторая -связка. Выделим все одноточечные -компоненты. Согласно следствию 9.1 вершина графа является одноточечной компонентой тогда и только тогда, когда существует хотя бы одна другая вершина этого графа, такая, что v, и соединяет меньше, чем k путей, не содержащих общих связей.

3. Пусть — подграф -связки у которой удалены все одноточечные компоненты. Так как любые две -компоненты одного графа не пересекаются, то представляет собой граф, связные компоненты которого являются -компонентами графа (Фактически здесь описана конструкция оператора удаления U (см. п. 9.3.3) для получения -компонент.) Применяя теперь алгоритм выделения компонент графа получаем, наконец, набор -компонент графа

Применяя шаги 2 и 3 последовательно к -связкам получаем набор всех -компонент графа