Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика (1027378), страница 52
Текст из файла (страница 52)
е. с, =- с, — бс„с, = с, + Ьс,. Таким образом, увеличиваются возможности классификации объектов и образования новых классов (принятые при реализации алгоритма значения бс, =- 0,01 и бс, = 0,001). Производится переход на шаг 2. Шаг 5. Проводится реклассификация исходной совокупности объектов Х так же, как на шаге 2, но при с, = 0 и без пересчета оценок статистических характеристик Хь Х. Полученная классификация считается окончательной. данными измерений, проб н т. п., при классификации часто необходимо учитывать качественную однородность этих объектов.
Приведем примеры построения матриц ограничений В= = (Ьгт), 1 < 1, 1 < и. Пример 9.1. Пусть Рс:0= (О,, ..., 0„) — подмножество объектов, объединенных общностью какого-либо показателя нь скажем, в задачах социологии, демографии и т. п. Допустим, что набор показателей и,, 1 < 1 < Т поэт воляет представить 0 в виде объединения () 0', вообще гас=~ зоря, пересекающихся подмножеств 0'. Тогда для пары объектов 0; и От положим Ьы —— О, если не существует ни одного показателя ао объединяющего их, и Ьгт =- 1, если (О;, 0 ) ~ 0' для некоторого й П р и м е р 9.2.
Пусть исследуемый обьект 0; описыва. ется точкой Х~ —— (хР', ..., х~"~) с Р~, причем набор признаков х;, ..., х<р~, таков, что для некоторого порогового ! значения с можно, априори, сделать вывод: если ЦХ,— — Х7Ц ) с, то объекты 0; и 07 не являются однородными. Тогда положим Ьгх — — О, если ЦХ, — Х;Ц ) е, и Ьгх = 1, если ЦХ; — Х;Ц < с. П р и м е р 9.3. Пусть объект 0; описывается парой (Х„Е;), где Х; = — (х~"', ..., х)ю) — вектор признаков, под. дающихся измерению, а Я~ — -- (г) ', ..., г)~') — вектор пригм знаков, для которых не существует обьективно обусловленной шкалы, скажем, г~~' — выраженное в баллах мнение д-го эксперта об 1-м объекте. Допустим, что существует мера близости р' (Ло 27), такая„что для некоторого порогового значения с из условия р' (Ео 27) ) с вытекает, что объекты О, и 0; заведомо не являются однородными.
Тогда положим Ьсх = О, если р' (Яь27);~ с, и Ьы= 1, если р' (Я;, Ег) < < с. Итак, пусть имеется совокупность объектов 0 = (О„ ..., 0,), исходная информация о которых представлена либо в форме матрицы обьект — свойство Х вЂ” - (х,~'), 1 ~ 1 ~ < п, 1 < 1 ~; р, и матрицы ограничений В = (Ьы), 1 < 1, 1 <и, где Ьы — — 0 или 1, либо в форме матрицы р = (ры), 1 < 1, 1 < и взаимных близостей между объектами, причем в этой матрице пропущены элементы р;ь где (1, 1) — пары индексов, для которых Ьы = О, Опишем схему соответствующего агломеративного алгоритма иерархической классификации. 271 Схема алгоритма 1. Выберем меру близости р (5„5,) между подмножествами исследуемой совокупности.
Подадим на вход алгоритма разбиение Бэ =- (51, ..., 5„') на одноточечные классы 5! =- (Хс) и матрицу ограничений В = (Ьы). 2. Допустим, что на т-м шаге имеется разбиение Б = (Бс, ..., 5, ~ь!), 1 < т < л — 1, и матрица ограничений В"-' =- (Ь,! '), 1 < с, у < а — т+ 1. Нацдем (у, у ) =агссш!и (р(5р — с, Б~-!);с !" у, Ьсс-! = 1) с!, и Объединим классы Бс, ' и Бу~ ' в один класс и получим разбиение Б = (5",', ..., 5„"' м), где 5", = 5,"- ', если у чь с„у„а — т+ 1; Бт =Бщ-с05щ — ! и Бщ Б" — 1 с, с. с, с л — щ+!' Далее, получим матрицу ограничений В'" =- (Ьсу), где Ьс'=Ь, — ', если (У, у) ()(У, у )= Я; ~0, если Ь вЂ” '+Ь вЂ” '=О; с, у у.
с (1, если Ь,"-'+Ь'"-.'=,АО, учту„; Ьыс = Ь,.т„— ! + с, если с Ф са. 3. Если В~ — единичная матрица, то объявляем разбиение 5 итоговой классификацией. Если вне диагонали матрицы В~ имеются ненулевые элементы, то возвращаемся к шагу 2, заменив т на т + 1. Результатом работы алгоритма является последовательность разбиений Ба ~...с: Б".
где 0 ~ й < и — 1, причем каждое разбиение 54 =- (51, ..., 5» с) согласовано с матрицей ограничений В в следующем смысле: если объекты О; и О; попадают в один класс, скажем 51, 1 < у < л — 1, то в этом классе обязательно содержится цепь объектов Ос, О;, ..., О,, Он т ) 1, такая, что Ьс, ... Ьс, с — — 1. Все результаты об агломеративных алгоритмах иерархической классификации (см. гл. 8) естественным образом распространяются на описанный выше алгоритм классификации при ограничениях на связи между объектами. 272 Классификация иа графах Опишем методы и алгоритмы классификации, основанные на представлении исходной информации о классифицируемых объектах в виде графа близости б = (У, Е), вершины и„..., оа Е 1' которого соответствуют объектам 0„..., 0„, а ребра ец Е Е, !' Ф 1', соединяющие вершины о, и от — неупорядоченным парам (О!, 0,), ! Ф 1, т.
е. ец — — е,, Длина ребра ец считается равной рц для выбранной мерй близости между объектами О, и О,. В изложении будем существенно опираться на работу Д. В. Матулы нз [83, с. 83 — 1111. 9.3.1. Основные понятия и определения. Предварительные сведения из теории графов приведены в 112, п. 4.2.1). Определение 9.1. Граф б= — (У, Е), где У= = (и„..., о„), Е = (гц), называется полным, если любые его две вершины п! и о! соединены ребром емб Е. Например, граф близости 6 = б (0) совокупности объектов 0 является полным.
В задачах классификации при наличии ограничений на связи между объектами (см. $ 9.2) используются неполные графы (В-графы близости, где В = =- (бц)), полученные из полного графа близости удалением ребер гц при условии, что Ьц = О. Определение 9.2. Пусть б= — (У, Е) — некоторый граф. Вектором инцидентности вершины о, называется вектор и!! = (и!„, ..., и!„), где и!ц = 1, если ец Р Е, и и!ц — — О, если ец- с Е'.
Степенью вершины п! в графе 6 называется число !(! (6) = а = !(! = ~", вц. Ясно, что граф 6 полный тогда и только тогда, ! =! когда степень любой его вершины равна и — 1. 0 п р едел ен не 9.3. Подграф 6' ~ б называется максимальным по отношению к некоторому свойству Р (Р-максимальным), если 6' обладает свойством Р и в 6 не существует подграфа 6", обладающего свойством Р, такого, что б' с: б" с б, б' чь б' чь б. П р и м е р 9.4. Пусть 0' с: 0 =- (О„ ..., О„) и 1" ~ ~ У вЂ” соответствующее подмножество вершин графа близости б (0) = (У, Е). Тогда среди всех подграфов с множеством вершин У' максимальным является граф близости б (О'). ! Обратим внимание, что ып = о длн всех !, т. е., как и в 1121, рассматриваем только простые графы, у которых ребра, соеднняюнхие вершину с собой. отсутствуют.
йуз Напомним, что граф 6 = (У, Е) называется связанным, если любые две его вершины оп п, можно соединить последовательностью ребер (е... д = О, ..., гп — 1, и» ) 1), где е,, = е;,„ае, ~ = е..., т. е. связать вершины о~ и о, путем, О п р е д е л е н и е 9.4. Максимальный связанный подграф б' = (У', Е') графа 0 = (У, Е) называется компоненгпой. Пусть б' = (У', Е') и б" = (У", Е") — две компоненты данного графа б = (1', Е). Тогда непосредственно из определений вытекает, что У' и У', как подмножества в У имеют пустое пересечение. 9.3.2. Алгоритм выделения компонент графа.
В рамках общего подхода, изложенного в (83, с. 83 †1), каждый метод классификации на графах опирается на процедуру выделения соответствующих Р-максимальных подграфов. Более подробно рассмотрим зто в п. 9.3.4. Здесь же опишем процедуру, лежащую в основе ряда известных методов, связанных с выделением компонент графа. Исходя из некоторой модели класса, описываемой в терминах теории графов (см.
п. 9.3.3 и 9.3.4), строится подграф 6' графа близости б (0) = (У, Е) с тем же множеством вершин У, т. е. 6' = (У, Е'), где Е' получается из Е удалением ребер, не отвечающих модели класса. Затем применяется алгоритм выделения компонент 61 = (У~, Е~), ..., 6» = = (У», Е») графа б' = (У, Е') н тем самым находится разбиение множества У на подмножества У„ ..., У„, т. е. классификация множества объектов О. Указанная процедура, примененная к В-графу близости, позволяет провести классификацию при наличии матрицы ограничений В на связи между объектами. Оп р е дел е н и е 9.5. Подграф 6' = (У', Е') некоторого графа 6 =- (У, Е) называется О-полным подграфом (короче, б-подграфом), если любое ребро нз 6, соединяющее какие-либо вершины из 6', принадлежит 6', т.
е. Е' =- (еы с Е Е: по пт Е 1"). Непосредственно из определения получаем: 1) существует взаимно-однозначное соответствие между подмножествами множества вершин У и б-подграфами графаб=(У, Е); 2) каждая компонента О' графа б является его б-подграфом. Опираясь на зти утверждения, опишем основной этап алгоритма. Шаг А. Пусть 0' = (У', Е')-связанный подграф графа 6 = (У, Е) и У» = (ип, ..., и, ) ~ У = (и„..., и„), т ~ ~ П. Положим У»=(цЕУгеп,ЕЕ, 1=1, ..., и), т.е.
введем множество вершин в 6, связанных с вершинами из 6' хотя бы одним ребром. Тогда 6-подграф 6' = (У», Е') графа 6, соответствующий множеству вершин У', будет связанным. Если У» = У», то получаем, что Ы является компонентой, содержащей данный граф 6'. Если У'~ У', то аналогично построим множество вершин У» и 6-подграф 6'= (Уз, Е'), соответствующий множеству вершин У». Так как У вЂ” конечное множество, то последовательность множеств У» с: У» с: У' с: ... стабилизируется, т.
е. У» =- =- У»+' для некоторого д и получим 6-подграф 6» = (У», Е»), являющийся компонентой графа 6, содержащей данный граф 0'. 3 а м е ч а н и е. Программную реализацию шага А можно провести, оперируя только векторами инцидентности вершин (см. определение 9.2). Итак, на вход алгоритма выделения компонент подается связанный граф, например граф близости (п„8) первой вершины. Применяя шаг А, получаем компоненту 6, =- (1'„ Е,) графа 6 =- (1', Е) и переходим к выделению компонент графа (У'; У„ Е Е,) и т.д, до тех пор, пока не исчерпаем все исходное множество вершин 1'.
9.3.3. Алгоритмы классификации, использующие процедуру выделения компонент графа. Рассмотрим матрицу взаимных близостей р = (р„= р (0„0,), 1 (1, 1 ~ л), между классифицируемыми объектами О,, ..., 0„. Без ограничения общности можно считать, что О < рп ~ 1, причем ры —— О тогда и только тогда, когда 1 = — 1.
Пусть О = с» ( с, ( ... ( с„-= 1 — некоторая последовательность пороговых значений. Тогда определена последовательность подграфов графа близости 6(0) = (У, Е): 6» ы 6' ~ ... ы 6, где 6' — — (У, Е') и Е' =- (е„Е Е: ры < с,). Заметим, что 6» — — (У, Я) и 6 =- 6. Граф 6~ называется графом близости на уровне сь Опишем сначала общую схему алгоритмов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
