Дюран Б._ Оделл П. - Кластерный анализ (1977) (1185343), страница 15
Текст из файла (страница 15)
В следующем параграфе мы рассмотрим процедуру кластеризации, которая приводит к оптимальному, по меньшей мере в локальном смысле, разбиению иа группы относительно критериев (2) и (3). Метод, который был рассмотрен в параграфе 1.5, приводит к оптимальному разбиенйю с точки зрения критерия (1). Л Одной из проблем применения оценки ((х) в (5.2) является выбор значения а. Выбор того или иного значения очень важен, н в случае плохого выбора оценка будет неудовлетворительной. Выбор а основан на неравенстве теории информации~ Кульбак [2171 доказал, что равенство в (5.3) дости. Л гается тогда и только тогда, когда )(х) =1(х) для почти всех х.
Процедура заключается в том, чтобы минимизировать г. Неравенство (5.3) можно переписать еле. дующим образом: Л Л т=Е[1п)(х)1= 3((х) 1п[(х)дх( ~~[(х)1п((х)ох= =Е[1п ) (х) 1, причем равенство достигается в том и только в том слу- Л чае, когда ) (х) =1(х) для почти всех х. Как видим, минимизация г эквивалентна максимизации и.
Процедура выбора а заключается в максимизации не самого зна- '01 а чения <и, а его оценки. Если 1 построено на х<,х<ь ..., х„ и у<. уь ", уе — другая выборка объема й, то оценка и< равна: л ! «х и= в 2.", 1п ! (у»). а Если второй выборки не существует, то оценку для ! 'строят на основе х<, хм ..., х„; в этом случае она равна: «1 е л и<= — 2 ', 1п 1 (х<). (5.4) »=< Однако зта оценка будет смещена и может привести к отрицательным значениям а. Смещение оценки (5.4) может быть уменьшено методом складного ножа ()ас)<)<- н и!Ппд) (8Ц, (14Ц.
Пусть И;(х) — оценка !(х) (х;опущен).- Тогда х I х-х» И;(х)= — ' ~ К ( — ) (х — 1) ае а »=< и а и< определяется равенством: х 1 х х т= — ~",!пй;(х)). )=< л Производная т после преобразований равна: о»(х<, х») х ех» Х В<(х», х»)е «'<х 1 )< — — — Е ап й«3 В»!х<,х<) х За' Х е где бе(х», х ) (х< — х;) Б '(х;,— х;) а <)<х Оптимальное значение а находят из уравнения — „„=О. Для решения этого уравнения могут быть применены различные методы, например метод Ньютона — Рафсона. Эти методы рассматриваются в главе 3, Изаксона и Келлера [1721.
5.3. Кластеризация иа основе оцениваиия фупиции плотности: В предыдущем параграфе было указано, что одним л из преимуществ применения оценки плотности 1(х) (5.1) является то, что при этом три критерия группировки (1) Ф', (2) !Т!/!йГ! и (3) 1г Ф-'В становятся эквивалентными. Для этого векторы наблюдений уь ум ..., у» необходимо заменить'на х;=у~ — у, и так что новое семейство векторов будет иметь среднее, равное 0; а затем векторы х преобразовать по закону СХ, где С— невырожденная матрица, такая, что СТСт=1. Как следует из теоремы, доказанной в 1401, евклидово расстояние в преобразованном пространстве пропорционально расстоянию Махаланобиса первоначального пространства.
Отсюда можно сделать следующий вывод: алгоритмом кластеризации можно пользоваться в соответствии с одним из трех критериев без предварительного преобразования, если первоначально пользовались расстоянием Махаланобиса. Большинство из методов кластеризации, которые обсуждались в предыдущих главах, были сформулированы на эвристической и интуитивной основе и имели детерминированную природу. 'Методы, основанные иа оценивании функции плотности, составляют содержание статистического подхода и приводят к хорошо обоснованному понятию кластера (по крайней мере не хуже, чем в детерминированном случае). Один из основных моментов в статистическом подходе в оценивание моды. При этом имеются два способа: 1)' моды оцениваются непосредственно из наблюдений; 2) сначала оцениваетл ся многомерная функция плотности )(х), на основе которой затем вычисляются моды.
При эвристических подходах выбор метода кластеризации зависит в основном от данных. При статистическом подходе кластер определяется в терминах характеристик функции плотности, которой соответствуют наблюдения. Этот подход более точен, так как при этом мы можем более точно сказать, что является целью кластернрования; статистическое оценивание даст объективный подход к достижению этой цели, а статистическая проверка поможет ответить на вопрос, как близко результат лежит от цели. При статистическом подходе к кластеризации, предложенном в 140], в первую очередь оценивается многомерная функция плотности для произведенных наблюдений. Затем с целью, ° распределения наблюдений по кластерам применяется' метод «подъема на холм» (Ы11 сй(шЫпд); кластеры определяются в терминах моды л плотности )(х).
Процедура «подъема на холм» заклюл чается в следующем. Сначала оценивается. 1(х). Затем для каждого наблюдения х~ определяются два ближайших элемента (по минимальному расстоянию) Наблюл денне становится частью «пути» или «холма» )(л), если. л ближайшее дает большее значение 1(х). В результате перебора всех наблюдений получатся пути, которые л поднимаются на «холмы» (или холм) 1(х). Наблюдения на каждом пути группируются и образуют кластеры. Путь заканчивается наблюдением, для которого блие жайшее другое приводит к меньшему значению 1(х). Алгоритм, основанный на минимальном расстоянии, может привести к болыпому числу путей (кластеров)- Для устранения подобной ситуации для каждого наблюдения выбирается другое, расстояние до которого равно второму минимальному значению.
Если для элемента (наблюдения) х; первый ближайший элемент л л л Равен хм а втоРой х, и )(х») ~~(х;)-'61(х;), то пУть пРодолжается. Процедура первых двух ближайших наблюдений применяется для построения начального приближения разбиения на группы. Два пути по обеим сторонам «холма» (моды) в этой процедуре будут всегда несвязанными. Для устранения л последствий этой ситуации сравним 1(х) в трех точках между каждой вершиной и ее ближайшей вершиной.
л Значения 1(х) в этих точках указывают либо на то, что две ближайшие вершины составляют «холм» (в этом случае наблюдения, соответствующие двум путям, объединяются), либо на «долнну», которая лежит между холмами, — в этом случае пути оставляем разомкнутыми. Процедура повторяется до тех пор, пока все наблюдения не будут соответствовать одному холму или пока между каждой вершиной н ближайшей к ней не будет 94 долины. Три точки между ближайшими вершинами могут быть выбраны, например, по следующему правилу: первая точка соответствует одной четвертой отрезкй прямой, соединяющей вершины, вторая — одной второй отрезка, третья — трем четвертым отрезка. Брайен [401 описывает вычислительную программу, которая выполняет оценивание функции плотности и производит кластеризацию по методу, изложенному выше. Он приводит примеры, для которых этот метод привел к удовлетворительным результатам.
В одном из этих примеров привлекаются хорошо известные данные наблюдений Фишера за ирисами; этот пример будет описан в следующей главе. 5.4. Замечания Из параграфов 5.2 н 5.3, очевидно, следует, что процедура Брайена может быть модифицирована многими способами. Например, могут быть применены различные оценки для функции плотности. Однако оценка Брайена в отношении величины а обладает определенной гибкостью.
Решение некоторых вопросов его процедуры кластеризации довольно произвольно и может быть модифицировано, однако все это имеет второстепенное значение. Другое определение кластера, с помощью некоторой вероятностной модели, предложено Лингом [231].-Он дает. определения кластера и двух показателей, которые служат мерами компактностн и относительной изоляции. Далее он развивает соответствующую вероятностную модель для выборочных распределений этих показателей. Вольф [4021 описывает кластерный метод, основанный на разбиении смеси многомерных распределений, н приводит полное описание программы для 1ВМ 360/65 этого метода.
Кунц и Фукунага [208) приводят общее выражение для критерия при непараметрической кластеризации, которое аналогично (4.6). Они описывают цроцедуру кластеризации, основанную на их критерии; эта процедура отыскивает «долиныяз т. е. определяет области с низкими частотами (седловины). ГЛАВА б ПРИЛОЖЕНИЯ 6Л. Прилоигеиие к регистрации отдаленных объектов В исследовании проблемы регистрации отдаленных объектов [167], [226], [227] имеют дело с участком (экраном), который представляет собой прямоугольную область, плошадь которой составляет г строк (линий сканирования) и с столбцов (число различаемых элементов объектов) на одной сканируемой линии'.
Для каждой точки (объекта 1) имеется вектор измеренйй (характеристик) р)с',!Хм, г=1,2, ..., и; 1=1,2..., с. Для рекогносцировки участка необходимо «как можно эффективнее» решить гсг к задач на распознавание (участок, рекогносцнруется последовательно точка за точкой). Для решения этой задачи, т. е. для кластеризации наблюдений отдаленных объектов (мультиспектральных данных сканирования) центр пилотируемых космических ' кораблей воспользовался программой Болла и Холла [15], [16], [18] ИСОМАН (1БОРАТА — НегаВче Бе!!в Огдап1х!пд Ра!а Апа!уз(з Тес(гп(г(пе) (итеративный самообучаюшийся метод анализа наблюдений). Цель про. цесса кластеризации двояка [194]: а) проверить однородность мультиспектральных данных сканирования, т. е.
необходимость разделения класса различаемых элементов на несколько уннмодальных подклассов и б) кластеризовать данные сканируемой линии, т. е. классифицировать объекты. по группам. Итеративная процедура Болла и Холла -[15], [16], [!8] была коротко описана в параграфе !.6. Сначала * т. е. разрешающая способность прибора, сканирующего !регистрирующего) объекты. — Примеч. пер. выбирается й кластеров, которые представляют собой Й случайно выбранных точек; оставшиеся объекты приписываются к кластерам с ближайшим центром. Затем вычисляются центры кластеров и два кластера 7 и У объединяются, если Ю777 меньше заданного порогового значения г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
