Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика (1027378), страница 53

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 53)

Параметром алгоритма является оператор К ставящий в соответствие последовательности графов 6» с= ... с: — 6 последовательность графов 6» : — ... с= 6 , где 6' -= (У, Е'), и Е' получается из Е' удалением некоторых связей в соответствии с выбранной моделью классов. Основные примеры операторов 0 рассмотрены в конце этого и в следую- 275 щем пункте. Ясно, что О" = 6~, а в тех случаях, когда нет априорных ограничений, на связи между объектами, то и 6 = 6"'. В общем случае граф 6 представляет собой В- граф близости, где В = (Ьы) — матрица ограничений на связи между объектами.

Схема алгоритма 1. На вход подается граф 6', множество его компонент задает разбиение совокупности обьектов О,, ..., О„ на одноточечные классы. 2. На вход г-го шага, 1 > 1, подается граф У-', разбитый на компоненты 6', ', ..., Оа,., и граф 6~. Так как 6'-' с: 6', то каждая компонента графа 6'-' является связанным подграфом графа 6'. Поэтому можно, начиная, например, с б',-~, при помощи алгоритма выделения компонент (см. и.

9.3.2) получить компоненту 6, 'графа (г и перейти к выделению компонент графа 6' 6',. Так как компоненты графа не пересекаются, то компонента графа 6'-' может входить только в одну компоненту графа 6'. Следовательно, выделение компонент в 6'~,0', можно начинать с одной из компонент графа 6' ~, не вошедших в 6'„и т. д. до тех пор, пока не будут выделены все компоненты графа 6'. Итогом г-го шага является разбиение графа 6' на компоненты 6'„..., ба~ и, следовательно, разбиение множества вершин У на непересекающиеся подмножества $"„..., У~,. Соответствующая классификация (5'„..., 5~,) множества объектов называется классификацией на уровне с,. Алгоритм заканчивает работу на т-м шаге. В результате получаем последовательность вложенных разбиений У с У с ...

с Б"', т. е. иерархию на множестве объектов О. Рассмотрим теперь наиболее известные примеры алгоритмов, основанные на простых моделях классов и соответственно простых операторах У. Построение операторов У для более сложных моделей классов требует привлечения результатов теории графов и изложено в следующем пункте. О п р е деле н не 9.б. Алгоритм классификации на графах с тождественным оператором У, т. е. 6' = 6' для всех г называется односвязывающим.

В случае когда последовательность пороговых значений 0 = с,~ с,( ... ( с = 1 совпадает с последовательностью рангов для последовательности ры, 1 с 1, 1 (и, иерархическая классификация при помощи односвязывающего алгоритма совпадает с иерархической классификацией, получаемой классической агломеративной процедурой по принципу «ближайшего соседа» (см.

$ 8.2). Алгоритм называется односвязывающим, так как он соответствует модели класса, в которой каждый объект из данного класса связан с остальными объектами из этого класса по крайней мере одной связью. О п р е деле н и е 9.7. Алгоритм классификации на графах с оператором У, удаляющим в графах 6' ребра (связи), идущие к вершинам степени, меньше й, к > 2, называется й-связывающим. Название алгоритма объясняется тем, что он соответствует модели класса, в которой представитель данного класса связан с остальными, по крайней мере, й связями. Определение 9.8. При данном й, й -.1 максимальный связанный подграф 6' графа 6 называется й-связкой, если степень каждой его вершины не меньше я.

Заметим, что каждая я-связка графа 6' является компонентой графа 6' для оператора У нз определения 9.7. Следовательно, й-связывающий алгоритм выделяет в исследуемом множестве объектов все й-связки на каждом уровне близости. г 9.3.4. Метод послойной классификации. Общий подход к построению алгоритмов классификзции на графах, Рассмотрим сначала, какие максимальные подграфы наряду с йсвязкой используются для описания структур классов. Определение 9.9. Приданном й, й)1, максимальный связанный подграф 6' =- (е", Е') графа 6 называется й-компонентой, если при любом разбиении множества вершин $~' на непересекаияциеся подмножества $'1, 'г'» существует, по крайней мере, й связей (ребер) в Е' между подмножествами р( и г'».

О п р е дел е н и е 9 !О. Связанный подграф 6'= = (У', Е) графа 6 называется й-сала»иным, я > 1, если ~ р" ( ) =вЙ + 1, и удаление любых (й — 1) вершин из )г' оставля- етегосвязанным, т. е. любой подграфу которого 1У"! => 1У'! — к + 1 явчяется связанным Определение 9.11. При данном 3, й>1, максимальный й -связанный подграф б' = (У', Е') ~ б называется к-блокол1. О п р еде л е н и е 9,12.

Кликой графа 6 называется максимальный полный подграф б' = (У', Е'). Клика графа, содержащая более к вершин, называется к-кликой, Й посредственно из определений 9.8 — 9,12 следует: 1) любого графа б каждая й-клика является подгр- е ) длял фом некоторого й-блока, каждый й-блок является подгр ф 8 Рнс. 9.1. Классификация на графе.

Компоненты (1, ..., 12), (13, ..., 16); 2-связкн (1... 1Ц, (14, 15, 16); 2.компоненты (1, ..., ); (, .„, ), ( 2-блоки. (1... 5); (5, 6, 7), (8, ..., 1Ц, (14, 15, 16); 2-клнкн (1, 2, 3, 4), (3, 4, 5), (5, 6, 7), (8..., 1Ц, (14, 15, !6) некоторо -ко й к- мпоненты, которая в свою очередь является .

9.1, г е к =- 2); подграфом некоторой к-связки (рис., где 2) любые две л-компоненты и, следовательно, любые две -связки й и одного графа б имеют пустое пересечение; ога амо- 3) пересечение любых двух й.блоков одног р ф жет содержать не более чем (к — 1) общих вершин. Д обства изложения будем считать, что каждая верДля уд фа б, не вошедшая ни в один подграф. максимальшина графа, не ный по отношению к выбранному свойству Е, фор мал ьно обладает этим сво йством. Например, будем говорить, что вер- ент г а а 6, сама шина, не вошедшая ни в одну к-компоненту графа, с является его к-компонентой. П итакомсоглашении можно сказать, что выделение в данном графе 6 = (У, Е) всех его подграфов бг = — ( „,), ..., ба — — (Уа, Еа), максимальных по отношению к выбранному свойству Е, задает покрытие множества вершин У подмножествами У,, ..., Ую () Уе — — У.

Есы 278 В случае й-компонент и й-связок получается разбиение множества У на непересекающиеся подмножества, а в случае й-блоков — покрытие, каждые два множества которого имеют не более чем (й — !) общую точку. Теперь можно описать общую схему алгоритма классификации на графах как естественное обобщение схемы из п, 9.3.2. Пусть, как и выше, Оч с=О'с=.:. ы Π— последова тельность подграфов графа О, где О' — граф близости на уровне сн Параметром алгоритма является процедура Аг выделения в графе 6' всех его подграфов, максимальных по отношению к выбранному свойству Р. Эти подграфы будем называть Р-компонентами графа 6.

Роль Р- компонент, в зависимости от Р, играют Й-компоненты, й-связки, й-блокн или й-клики. Схема алгоритма 1. На вход подается граф Оз, множество его Р-компонент задает покрытие совокупности объектов (О„ ..., 0„) одноточечными классами. 2. На вход бго шага, 1 > 1, подается граф О'-', покрытый Р-компонентами 6',— ', ..., Оз~,, и граф 6'. Так как О' ' с: О', то каждая Р-компонента графа О' ' является связным подграфом в 6'. На вход процедуры Ар подается граф О' . При помощи нее он достраивается до Р-компоненты О', графа О'. Затем среди Р-компонент графа 6' ~ берется та, которая не вошла в 6'„и при помощи той же процедуры достраивается до следующей Р-компоненты графа 6» н так далее, до тех пор, пока не будут выделены все Ркомпоненты О,', ..., 6~~ графа О~. Соответствующее покрытие (Я'„..., 3~,) совокупности объектов называется Р-классификацией ее на уровне с,.

Классы 5' д = 1, ..., йо могут пересекаться, как в случае классификации Й-блоками, но ни один класс не может целиком содержать другой. Алгоритм заканчивает работу на (7п — 1)-шаге, так как О является графом близости совокупности объектов, т. е. полным графом. (Это в случае, когда нет ограничений на связи между объектами, а если матрица априорных ограничений имеется, то алгоритм заканчивает работу на 7п-м шаге.) В результате получается последовательность вложенных покрытий У с: У с ...~ 5'", которая называется послойной Р-классификацией. В тех случаях, когда для каж- 279 дого г покрытие 5' состоит из непересекающихся классов, то Р-классификация является иерархической, т.

е. задает иерархию на множестве объектов (см. определение 8.1). Отмеченные выше взаимоотношения между Р-компонентами для различных свойств Р позволяют рассматривать в целом метод послойной классификации как последовательность уточняющих друг друга методов послойных Р-классификаций. Классификация Ькомпонентами уточняет классификацию й-связками и сама в свою очередь уточняется классификацией й-блоками и т. п. Эффективность алгоритмов послойных Р-классификаций определяется эффективностью реализации процедуры Ап выделения в графе всех его Р-компонент.

Как следует из п.9.3.3, в случае Ьсвязок существует достаточно эффективная процедура Аг благодаря тому, что каждая Й-связка графа 6' является компонентой графа 6', полученного из бт удалением некоторых связей. Непосредственные процедуры Ар для Р-классификаций, уточняющих классификацию й-связками, очень трудоемки, и реализация их затруднена даже для относительно небольших совокупностей обьектов. Но, привлекая результаты теории графов, удается существенно сократить наиболее трудоемкую часть процедур выделения Р-компонент, связанную с перебором вариантов разбиения множества вершин. Для построения алгоритмов классификации Й-компонентами и й-блоками большое значение имеют следующие результаты, полученные К.

Характеристики

Список файлов книги