Дюран Б._ Оделл П. - Кластерный анализ (1977) (1185343), страница 14
Текст из файла (страница 14)
При оперировании на деревьях семейство (т)с) итеративно преобразуется в с.-оптимальное семейство. Семейство деревьев (т)) назовем локально оптимальным на множестве локальных операций 1., если это семей- ство является Ь-оптимальным для каждого Ь~(.. Желаемыми свойствами локальных операций являются: 1) легкость вычислений, 2) возможность.р-сокращений. Оценить операцию в терминах свойства (2) довольно трудно, за исключением некоторых экспериментальных способов, поэтому свойство,(1) является решающим при выборе того или иного семейства операций. Можно показать, что если коэффициенты. сходства узлов' приближения, вычисленных по формуле (4.8), не удовлетворяют неравенству о(а) ~о(6) для любых а(Ь, то можно найти дерево с количеством узлов, меньших на единицу,.
и которое приближает 5 так же хорошо, т. е. оба дерева приводят к одному и тому же значению р. Это означает, что поиск локально оптимальных деревьев можно ограничить классом деревьев сходства. Аргументацию этого предложения читатель найдет в работе Хартигена [162, параграф 8). Локальная операция Ь на т приводит к новому дереву Ьт с подогнанными весами и коэффициентами сходств узлов, которые обозначим соответственно Ьв и Ьо. Полу.чаемое улучшение (если таковое будет) представляет собой разность р(5, Ьт) —.р(5, т).
Значение р(5, Ьт) может быть вычислено на основе Ьга и 1,о. Если через т~(Ь) обозначить число а и о, изменяющихся Ьт при операции Ь, то гп,(Ь) можно исйользовать как показатель «трудоемкости» вычисления р(5, Ьг). После того как локальная операция выполнена, основная корректировка заключается в изменении некоторых значений расширенных матриц ИУ, 5. Бее другие величины, связанные с деревом, должны быть изменены одинаковым образом. Процедура заключается втом, чтобы оценить данную серию операций на дереве т и выполнить ту, которая приводит к наибольшему уменьшению р. Результат локальной операции Ь, расстояние р(5, Ьт), сравнивается с р(5,т*) или р(5,5*), где т*— оптимальное дерево с 1ь узлами, 5* — соответствующая матрица сходства. Следующей вычислительной задачей является определение матрицы сходства, 5ь с точной структурой дерева т*, для которой р(5, 5*) минимально.
Три локальные операции, выполняемые на деревьях: 1) операция разветвления. Операция разветвления из а в о обозначается Ь(п, Ь); это операция, которая соединяет некоторый узел а из семейства Та и некоторый другой узел дерева Ь, причем о< а. Функция Т из- меняется на функцию ЬТ так, что (ЬТ)а'=Та' для а'чьа и (ЬТ)а=Ь. Операция разветвления не меняет числа узлов дерева; 2) операция исключения К(а) исключает узел а из дерева и переводит семейство а в Т(а) Эта операция определена для любых узлов за исключением корня и начальных узлов. В терминах отображения Т это означает (КТ)а'=Та' для а'Фа, Та'~"а и (КТ)а'=Та для Та'= а; 3) операция включения М(а) включает новый узел а* в дерево т между а и Та.
Если а — корень, то а*— новый корень. В терминах Т имеем: (МТ)а'=Та' для а'Фа,а'; . (МТ)а=а"', (МТ)аэ=Та для аФа, и (МТ)а"=аэ для а=ао. Операция включения и исключения изменяет число узлов дерева т. Иллюстрации этих операций читатель найдет в статье Хартигена. Он также дает примеры применения этой процедуры для отыскания локально оптимального дерева и показывает, как Р-критерий может быть использо. ван для определения приемлемого размера дерева.Там же рассматриваются другие определения точной структуры дерева н другие, отличные от деревьев, структуры сходства.
ГЛАВА 5 КЛАСТЕРИЗАЦИЯ НА ОСНОВЕ ОЦЕНИВАНИЯ ФУНКЦИИ ПЛОТНОСТИ 5Л. Модальный анализ Один из методов кластеризации, рассмотренных в главе 1,— метод по минимальному локальному расстоянию — приводит к удлинению кластеров. Этот метод яе принадлежит к классу методов с минимальной дисперсией, которые рассматривались в параграфе 1.6.
Применение для кластеризации метода минимального локального расстояния благодаря цепной тенденции может привести к ряду «плотных» кластеров, которые перемежаются, соединяются «редкими, неплотными» кластерами. В случае одной характеристики гистограмма будет иметь вид мультимодального распределения. Желательно пользоваться методами, которые бы определяли моды етого распределения и соответствуюшие им отдельные кластеры. Для массивов среднего объема Уишарт [396) предложил метод кластеризации, который он назвал модальным анализом. Этот метод им же был обобшен на случай большого числа наблюдений.
Его процедура начинается с выяснения вопроса о мультнмодальностн данных. В случае одной характеристики необходимо построить гистограмму и вычеркнуть данные с малой частотой (седловые области). Тогда соответствующий кластер можно установить для каждой модальной области. Данные, принадлежащие седловой области, относятся к ближайшей моде. В случае Р-характеристик этот метод становится неудобным. Если каждая ось измерения разбита на й классов, то мы получим Рь Р-мерных прямоугольников. Для определения, в какой из классов необходимо отнести то или иное наблюдение, зт требуется ответить на ряд вопросов, одним из которых является выбор оси измерения. Эту проблему можно обойти, если пользоваться сферическими областями.
Однауровневый алгоРитм Уншарта может быть записан следующим образом: а) выбираем значения порогового расстояния г и пороговой частоты (; б) вычисляем: матрицу сходства 5; в) для каждой точки находим частоту попадания точек )ь лежащих на расстоянии меньшем г; 'г) точку с частотой меньшей чем ~» удаляем; д) кластеризуем оставшиеся точки концентрации по методу 'минимального локального расстояния; е) распределяем точки, исключенные на шаге (г), по' кластерам, полученным в (д), соответственно некоторому'критерию. (Например, каждую точку, не являющуюся точкой концентрации, приписываем к кластеру, для которого расстояние между данной точкой и соответствующей точкой концентрации минимально.) Далее, Уишарт предложил ступенчатый алгоритм, который выполнял только задачу модального анализа, Для этого необходимо было задать лишь пороговое значение для частоты (.
На первом и последнем цикле алгоритма определяется один кластер. На некотором. промежуточном цикле получается-максимальное число кластеров. Для унимодальных данных анализ приводит к одному кластеру. За полным описанием зтого ступенчатого алгоритма отсылаем читателя к работе [3961. Заде,(407] ввел понятие «размытого» множества, его процедура имеет много общего с модальным анализом Уишарта. По' Заде, если Š— пространство точек, размытое множество А в Е характеризуется функцией семейства (характеристической функцией) ~,~(х)., которая каждой 'точке в Е ставит в соответствие число в интервале (О, Ц, причем величина ~л(х) представляет собой- степень «принадлежности» х к множеству 'А.
Смысл )л(х) аналогичен пороговому значению 1 Уишарта. Гитман и Левин (Г291 предлагают алгоритм, который разбивает выборку из мультимодального размытого мньжества на унимодальиые размытые множества; а. затем применяется алгоритм кластеризации многомерных наблюдений, в результате которого получаются однородные группы. Эта процедура тдкже аналогична модальиому анализу Уишарта.
88 ' Результат кластеризации, основанный на. модальном . анализе, сильно зависит .от оцеиивания положения моды, поэтому различные методы оценивания мультимодальных многомерных функций плотностей приведут и к'новым методам кластеризации. Этой проблеме мы н посвятим оставшуюся часть этой главы. 5.2. Оцениваиие функции плотности вероятности По вопросу оцеиивания функции плотности вероят- ности имеется много работ.
Мы не ставим себе цели дать обзор методов оценивания функций плотности. За корот- ким обзором существующих методов отсылаем читате- ля к' Брайену [40]. Брайен предлагает один метод оце- нивання многомерных функций плотности вероятности, который называет методом ядра; он также строит метод, кластеризации, который основывается на оценке функ- . ции плотности. Метод ядра оценивании функции плотности, связан с линейным интегральным преобразованием, 6(х) = ~,К(х — у)д(у)Ыу. Это преобразование устанавливает соответствие между' функциями 6(х) и л(у). Функция К(х — у) называется ядром преобразования (см.
[209]). Метод ядра также' иногда. называют оцениванием с 'езеешенным средним (см. [95], [283], [298]). В методе ядра функция плотности вероятности 1(х) оценивается яо формуле л и '1(х) = ~ К(х — и)г(7 (и) — 2; К(х-х~), Зс е где К(х — у) — ядро, а г„(и) — эмпирическая функция распределения. Розенблат [298] предложил само ядро рассматривать как некоторую функцию плотности, т. е. К(х) )О, ~К(х)Их=1. Сейчас мы рассмотрим основные моменты процедуры оцениваиия плотности вероятности, предложенной Брай- еном [401 Пусть Хь Хм ..., Х обозначает случайную выборку. объема и из.некоторой функции плотности 1(х), имею- .
щей невырождеиную матрицу ковариаций Е. С помо- 89 щью рассматриваемого метода, который аналогичен методу Какоулоса 1421, оценивается функция плотности в виде: 1(х) = — ', Х К ~ — ""' ), 3= где К вЂ” ядро. В качестве ядра выбирается функция плотности многомерного нормального распределения с математическим ожиданием, равным нулю, а ковариа- 'цнонной матрнцей 5, т. е, (2н) ив )а ) Чи Оценкой тогда будет: и (х-х ) 3 (х-х)) л 1 х чар ) (*) — н (5.2) иаи (2и) и)и ) Я ра 1=) где Хь Хм ..., Х обозначают векторы наблюдений, а х 5= (1/а)Х(х; — х) (х; — х)' — выборочная матрица кова- 1 ! риаций, которая предполагается невырожденной, откуда следует, что п)р и 5 положительно определена. л Легко показать, что 1(х) из (5.2) является функцией плотности вероятности, другими словами, л л ~(х) )О и ~ ~ (х)((х=1.
Квадратичная форма х'5-'х и зкспоненте К(х) в (5.1) является расстоянием Махаланобиса между х и О. Вместо матрицы 5 можно привлечь матрицу Р; это приведет к квадрату евклидова расстояния между х и О, т. е. 4е(х, О) =хтх. Выбор 5 и 1 эквивалентен выбору между расстоянием Махаланобиса и евклидовым рас- стоянием: Евклидово расстояние проще н легче вычисляется. Однако расстояние Махаланобиса имеет много преиму- ществ.
Например, как показано в параграфе 1,3, это расстояние инвариантно по отношению ко всем невыл р и р ир м-.э, ы)а) р — .* ° -., ° .х — и, . р. и' Линейным.— Примеч. иер. Л совпадает-с ((Ах), -где А — невырождено. Таким обра- Л зом, выбор масштаба не влияет на 1(х).
Это перестает быть верным для евклидова расстояния. Другим свойством расстояния Махаланобиса является то, что оно делает некоторые критерии кластеризации эквивалентными. Следующие три критерия кластеризации при пользовании раостоянием Макалаиобиса эквивалентны: 1) (г )(У; 2) ! Т(7 (Ч71; 3) (г ))7-'В, где Т, В н В' — соответственно матрицы полного, межгруппового и внутригруппового расстояния, которые обсуждались в параграфе 1А. Критерии (2) и (3) были предложены Фрндманом и Рубиным [1221, ими же были исследованы свойства этих критериев.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
