Дюран Б._ Оделл П. - Кластерный анализ (1977) (Дюран Б._ Оделл П. - Кластерный анализ (1977).djvu), страница 13

Значение, соответствующее узлу, в котором кластеризу. ется пара ((, 1), равно з (ю', 1) =зп. Определение 4УЕ Расстояние между двуми матрицами сходства 5, и 5» определим как 78 Р(5ь5»)= Х Е йт(1 !)(з~(1 !) зз(1 !))»I2 а=37=1 где %7 (1,1) — весовая функция сходства з (1,!). Определение 4.4. Расстоянием между матрицей сходства 5 и деревом т называется р (5, т) = пп(п р (5, 5«), ЯФ где 5* — любая матрица сходства с точной структурой дерева т.

Расстоянием р (5,т) можно пользоваться для определения, насколько хорошо дерево т представляет свою матрицу сходства 5. Основная проблема заключается в том, чтобы найти семейство деревьев (т1), где 1 изменяется от п+1 до 2п — 1, такое, что р (5, т;) минимально среди деревьев с 1 узлами. Поставленную задачу для случая, когда и не очень мало, можно решить методами дискретного программирования 12921. Однако можно найти деревья, которые будут локально оптимальными в том смысле, что ии одно дерево нз семейства (т7) не может быть улучшена выполнением «локальных операций», с помощью которых деревья можно слегка изменять.

4.4. Деревья Дерево т определим как т= (аь, А, Т~1, где аь обозначает корень, А — множество (конечное) узлов, включая аы Т вЂ” отображение А в себя, такое, что для любого Ь) 1 Т" а= а тогда н только тогда, когда а=ам Для данной дендограммы аь соответствует кластеру (узлу), содержащему все и объектов. Для данного узла Ь отображение Т устанавливает, в какой узел переходит Ь после преобразования (группировки); зто отображение тесно связано с данной процедурой кластеризации. Узлы Т»а Ь объединяются и образуют новый кластер (узел Ь) и называются семейством Ь, а Ь называется образующим (рагеп1) узлов Т-' Ь.

Узел Ь называется тривиальным, если Т-' Ь состоит из одного узла. Узел Ь называется начальным (Ьаггеп), если множество Т-' Ь пусто. Множество начальных узлов обозначим буквой В. Число начальных узлов обозначим и (В), а общее число узлов— и (А), (Очевидно, и (В) =п, а и (А) принимают целые 79 СЕОдотВО то ао ов от 'об аб ои аг ог от Š— ноеольние узри 2 1б ронер 1~ Ойзонто О гв Вооенб Оо тг в то трибиорьньй уеер Сенейетйо убро ег В = 1т г,..... тг1 Оо~ гг ггт1тгг -1в,в,то1 Рис. 6 значения от и+1 до 2п — 1.) Отображение' Т, которое задает дерево, начинается с'начальных узлов н далее происходит в направлении корня. Таким образом, мы говорим, что основанием дерева т является В.

Этн идеи идут нз теории графов [1541, 12781. Введенные понятия иллюстрированы на рис. 6. Наше изложение можно связать с соответствующим изложением этих вопросов у Джонсона, Джардайна н Сибсона, рассматривая уровень, на котором происходит образование групп. Прн этом каждому узлу отвечает определенный уровень расстояния нли сходства а. В обычных схемах ступенчатой кластеризации.

дерево не имеет узлов, подобных 14 или 18 на рис. 6. Такие узлы можно рассматривать как результат «локальных операций», которые выполняются с целью модификации данного. дерева. Подобные операции 'будут обсуждаться в 'следующем параграфе. Если два узла таковы,, что для я~О Т"а=Ь, то будем писать а~Ь. Отношение ~ задает на А частичное упорядочение. Если а, ЬбнА, то существует элемент с=вор (а,Ь), такой, что а,Ь<с, и из а,Ь(с* следует с<с*, другими словами, с есть первый узел, который содержит а и Ь,.т. е. с=Т"а,с=Т Ь, а Ь+т минимально. В терминах этих понятий дерево т может быть определено как частичное упорядочение А, которое имеет единственный максимальный элемент (аб) и для которого множество (Ь)а(Ь) линейно упорядочено для всех а.

Дерево сходства, которое. обозначим как (т, о), состоит из дерева и вещественнозначной функции а на А, такой, что о(а) ='о(Ь) как только Ь(а. (4.4) Действительное число а(а) называется сходством узла а. Любое дерево сходства может быть -представлено дендограммой. В дендограмме узлам одного семейства присваивается порядок, соответствующий их узлам сходства, т.

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

На основе дендограммы может быть 'построено полное дерево сходства т. Действительно, дендограмма есть не что иное, как графическое представление абстрактного дерева т=(аб, А, Т). Матрица сходства 5 имеет точную структуру дерева т на В, т. е. Вант, если для некоторого а, (т, о) есть дерево сходства (4.5) з(1,/) =а(знр(й1)) для всех 1,)~В. Другими словами, величина сходства между двумя узлами й/~В равна сходству первого узла, в котором они кластеризуются с помощью Т-ото'- бражения. Это определение аналогично определению Джонсона [186) и Джардайна' и Сибсона 11Т9); рас- б Заказ бгбб стояние между двумя узлами ( н 1 полагается равным тому уровню расстояния, на котором происходит объединение 1 и /.

Если матрица сходства 5 имеет точную структуру дерева, то 1п(В)1". (т. е. п(п — 1)/2) элементов матрицы 5 могут быть определены по п(А) значениям о.' Расстояние между двумя матрицами сходства 5( и Вз определяетая как и и Р (5ь 5г) ~ 2. К((', /) ~з~ ((', /) -зз ((', /) Р/2, (4 6) 1 3=~ где яг — симметричная весовая функция. Расстояние между матрицей 5 и деревом т определяется как р(5,,) = (п1р(5, 5и), (4.7) Б* ее где 5*сит означает, что 5а имеет точную структуру дерева. Матрица сходства 5, которая минимизирует р(5, 5и), называется приближением 5 по т. Итак, е"(1,/) есть сходство первого узла, в котором ( и / группируют- ' ся впервые, т.

е. зь(й 1) =о(зпр(й /)), где и†некоторая вещественнозначная функция на А, такая, что а(а)Рь >о(Ь), если а~Ь. Отсюда следует, что р(5,т) ш1 ~.", ~ ЯГ(1,/) [з(1 1)-о(зпр(1/))1з/2, (=1 (=1 где о может быть выбрано произвольно и единственным ограничением является выполнение определенных неравенств. Такое определение р(5,т) приводит нас к задаче квадратичного программирования; при этом существует единственное решение, которое и приводит Томпсон 13681. Однако если единственным условием минимизации р(5, 5*) является 5*((,1) =о(зпр(й/) для произвольного о, то а(с) = 'Г', %'(1,1)з(й/)/ ~ йг(1,1). (48) ВОв((и~с вир((, п=с Если эта функция удовлетворяет неравенству о(а) Р-о(Ь) для а~Ь, то 5* является приближением 5 по дереву т.

В действительности наибольший интерес представляют такие деревья т, для которых это неравенство выполняется (см. 11621). Нахождение приближения 5 по т эквивалентно оты. 82 сканию таких деревьев т, для которых величина р(5, т) принимает минимальные значения. Определение расстояния р(5,т) позволяет нам выбрать «оптимальное» представление 5 деревом. Расстояние р(5,«) естьсредний квадрат ошибки при подстановке вместо 5 матрицы близости с точной структурой дерева т. Для любого дерева т на В обобщение (р, 5 на Ар',А производится следующим образом: Ят(а, Ь) = 2", ~ )ва(й у); (4.9) (<а )~Ь Я7(а, Ь)э(а, Ь)= 2., '~ В'(К,у)э(У,у). (4.10) (~а )~Ь Веса узлов приближения и их коэффициенты сходства определяются следующим образом: и((с) = %'(с, с) — ~", Я7(с', с') ' (4.11) т = ьр (с) о(с) = Я7(с, с) э (с, с) — ~ ', )уу(с', с ) э(с', с').

(4Л 2) тс'=в о, определенные из Уравнений (4.8) и (4.12), совпадают, поскольку Я7(с, с) = 2', 2", В'(у,у) = 2', 2 1()'(у,у)„ (~в )~в в ~в вар(( у) в Поэтому п)(с) = я7(с, с) -' ~ йт(с', с') = ~ Ж(у, у). вар(ья=в тв в Таким же образом ьр(с)а(с) = ~', )а'(У, у)э(У, у). вар(в,))=в Теперь средний квадрат ошибки р(5,«) может быть записан как р= (5 т) = Е и)'(у у)э'(у у) — 2.', и (а)в'(а), (4.13) (ВЕВ ааЛ поскольку р(5,т) = ~.", Я7(У, у) [з(У, у) — о(зпр(й у))1»= СУЕВ ~; яу(у, у) [з(у, у) — о(с)1»= вил вар(иу)=а — Е Х,' (%7(й!)22(й 1) — %7(й!) 02(с)) = сйА сир(С)) с %'(й /) 22(),.1) — 2.', ш(с) а'(с). с,ввэ свА ': Уравнения (4.9) — (4.13) применяются для приближения дерева к матрице сходства 5.

Лля данного 5 цель заключается в том, чтобы найти такие деревья т, для которых р(5,«) минимально, т. е. найти такие коэффициенты сходства узлов приближения о(с), которые минимизируют взвешенную сумму квадратов (среднее квадрата ошибки): 2 ~ Ж'(1,1) (з(й1') — о(с))2 .

с«А сиисз)=с 4.5. Локальные операции на деревьях Основная цель приближения т к 5 заключается в том, чтобы найти такие деревья т, которые обращают р(5, т) в 'минимум. Однако всегда существует такое дерево т;+ь что р(5,«)+))~р(5,2';). Поэтому целью яв'ляется отыскание семейства деревьев (ть а(В)« /( (2а(В)+1), таких, что р(5, т;) дает мйнимум для каждого 1с Единственный существующий метод отыскания оптимального семейства состоит в полном переборе всех возможных деревьев на В и вычислении для каждого дерева соответствующего значения р(5,т). Однако этот метод практически неосуществим нз-за того, что число деревьев очень быстро растет с ростом п(В).

Таким образом, мы приходим к понятию «локально оптимального» семейства. Процедура начинается с семейства (т)), над которым производятся некоторые итеративные преобразования, которые составляют так называемое множество «локальных операций» 1.. Локальной операцией' с.ен1с называется любая операция, которая изменяет дерево т и в результате которой получается другое дерево с, Семейство деревьев (т)) называется 2.соптимальным, если для каждого т;р(5,т,„) =р(5, Ит;), где /ь обозначает число узлов в йть Это означает, что семейство ие может быть улучшено с помощью операций 2,'.