Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 46
Текст из файла (страница 46)
234 Гл. 6. Обучение бее учителя и гр леироека Если цель состоит в нахождении подклассов, более целесообразны прог4вдуры группировки (кластерного анализа). Грубо говоря, процедуры группировки дают описание данных в терминах кластеров, или групп точек данных, обладающих сильно схожими внутренними свойствами. Более формальные процедуры используют функции критериев, такие, как сумма квадратов расстояний от центров кластеров, и ищут группировку, которая приводит к экстремуму функции критерия. Поскольку даже это может привести к не- Рнс. б.7, Множества данных, ннеющне одинаковые статистики второго порядка. разрешимым вычислительным проблемам, были предложены другие процедуры, интуитивно многообещающие, но приводящие к реше.
пням, не имеющим установленных свойств. Использование этих процедур обычно оправдывается простотой их применения и часто дает интересные результаты, которые могут помочь в применении более строгих процедур. а.7. меРы пОдОБия Так как процедура группировки описывается как процедура нахождения естественных группировок в множестве данных, мы вынуждены определить, что понимается под естественной группировкой. Что подразумевается под словами, что выборки в одной 6.7. Мери яадебия группе более схожи, чем выборки в другой? Этот вопрос в действительности содержит две отдельные части: как измерять сходство между выборками и как нужно оценивать разделение множества выборок иа группы? В этом разделе рассмотрим первую из этих ча« отей. Наиболее очевидной мерой подобия (или различия) между двумя выборками является расстояние между ними.
Один из путей, по которому можно начать исследование группировок, состоит в определении подходящей функции расстояния и вычислении матрицы расстояний между всеми парами выборок. Если расстояние является хорошей мерой различия, то можно ожидать, что расстояние между выборками в одной и той же группе будет значительно меньше, чем расстояние между выборками из разных групп. Предположим на минуту, что две выборки принадлежат одной и той же группе, если евклидово расстояние между ними меньше, чем некоторое пороговое расстояние йе. Сразу очевидно, что выбор 4, очень важен.
Если расстояние де очень большое, все выборки будут собраны в одну группу. Если д. очень мало„каждая выборка образует отдельную группу. Для получения «естественных» групп расстояние е~е должно быть больше, чем типичные внутригрупповые расстояния, и меньше, чем типичные межгрупповые расстояния (рис. 6.8). Менее очевидным является факт, что результаты группировки зависят от выбора евклидова расстояния как меры различия.
Этот выбор предполагает, что пространство признаков изотропно. Следовательно, группы, определенные евклндовым расстоянием, будут инвариантны относительно сдвигов или вращений — движений точек данных, не меняющих их взаимного расположения. Однако они, вообще говоря, не будут инвариантны линейным или другим преобразованиям, которые искажают расстояния.
Таким образом, как показано на рис. 6.9, простое масштабирование координатных осей может привести к различному разбиению данных на группы. Конечно, это не относится к задачам, в которых произвольное масштабирование является неестественным или бессмысленным преобразованием. Однако, если группы должны иметь какое-либо значение, они должны быть инвариантны преобразованиям, естествен» ным для задачи. Один из путей достижения инвариантности состоит в нормировании данных перед группировкой. Например, чтобы добиться инвариантности к сдвигу н изменению масштаба, нужно так перенести оси и выбрать такой масштаб, чтобы все признаки имели нулевое среднее значение и единичную дисперсию.
Чтобы добиться инвариантности к вращению, нужно так повернуть оси, чтобы оии совпали с собственными векторами матрицы ковариаций выборок. Это преобразование к главным комлоненпиик может проводиться до масштабной нормировки или после нее. ! о о а б д Рис. 6.8. Действие порога расстояния на группировку (линиями соединены точки с расстояниями, меньшиии чем Ые). а — большое Ые, б — среднее Фа, в — малое 4.
и лА лч Рнс. 6.9. Влияние масштабирования на вид группировки. 237 б.7. Мери лодобля Однако читатель не должен делать вывода, что такого рода нормировка обязательно нужна. Рассмотрим, например, вопрос переноса и масштабирования осей так, чтобы каждый признак имел нулевое среднее значение и единичную дисперсию. Смысл такой нормировки состоит в том, что она предотвращает превосходство некоторых признаков при вычислении расстояний только потому, что они выражаются большими числовыми значениями.
Вычитание среднего и деление на стандартное отклонение являются подходящей нормировкой, если разброс значений соответствует нормальной случайной дисперсии. Однако она может быть совсем неподходя- а д' Рнс. 6.10. Нежелательные эффекты нормнровання. а — ненормнрованные, б — нормнрованные. щей, если разброс происходит благодаря наличию подклассов (рис.
6.10). Таким образом, такая обычная нормировка может быть совсем бесполезной в наиболее интересных случаях. В п. 6.8.3 описаны лучшие способы достижения инвариантности относительно масштабирования. Вместо нормировки данных и использования евклидова расстояния можно применить некоторое нормированное расстояние, такое, как махаланобисово. В более общем случае мы можем вообще избавиться от использования расстояния и ввести неметрическую функцию подобия з(х, х') для сравнения двух векторов х и х'. Обычно зто симметрическая функция, причем ее значение велико, когда х и х' подобны.
Например, когда угол между двумя векторами выбран в качестве меры их подобия, тогда нормированное произведение хтх' ~п~ '11 может быть подходящей функцией подобия. Эта мера — косинус угла между х и х' — инвариантна относительно вращения и расширения, хотя она не инвариантна относительно сдвига и обычных линейных преобразований. Когда признаки бинарны (О или 1), функция подобия имеет про- стую негеометрическую интерпретацию в терминах меры обладания Гл. б. Обучение без учителя и группировки общими признаками или же атрибутами. Будем говорить, что выборда х обладает 1-м атрибутом, если х~ — — 1.
Тогда х'х' — это просто число атрибутов, которыми обладают х и х', и ~!хйЩх'~1= =(х'хх "х')Ч~ есть среднее геометрическое числа атрибутов х и числа атрибутов х'. Таким образом, з (х, х') — зто мера относительного обладания общими атрибутами. Некоторые простые варианты втой формулы представляют хгх' а(х, х') = — „ (доля общих атрибутов) и з(х, х')= хгх+ х'гх' — хгх' (отношение числа общих атрибутов к числу атрибутов, принадлежащих х или х'). Последняя мера (иногда называемая козффициентом Танимото) часто встречается в области информационного поиска и биологической таксономии. В других приложениях встречаются самые разнообразные меры подобия, Считаем нужным упомянуть, что фундаментальные понятия теории измерений необходимы при использовании любой функции подобия или расстояния.
Вычисление подобия между двумя векторами всегда содержит в себе комбинацию значений их компонент. Однако в большинстве случаев применения распознавания образов компоненты вектора признаков являются результатом измерении очевидно несравнимых величин. Каким образом, используя наш прежний пример о классификации пород древесины, можно сравнивать яркость с ровностью волокон р должно ли сравнение зависеть от того, как измеряется яркость— в свечах на квадратный метр или в фут-ламбертах? Как нужно обрабатывать векторы, чьи компоненты содержат смесь из номинальных, порядковых, интервальных и относительных шкалгг) В конечном счете, нет методологического ответа иа зти вопросы.
Когда пользователь выбирает некоторую функцию подобия или нормирует свои данные каким-либо конкретным методом, он вводит информацию, которая задает процедуру. Мы приводили примеры альтернатив, которые могли бы оказаться полезными. Впрочем, мы можем только предупредить начинающего об этих подводных камнях в методах группировок, 6.В. ФУНКЦИИ КРИТЕРИЕВ ДЛЯ ГРУППИРОВКИ Предположим, что мы имеем множество Я из и выборок х„... ..., х„, которые хотим разделить на точно с непересекающихся поде) Зги фундаментальные соображения относятся не только к группировкам. Они появляются, например, когда для неизвестной плотности вероятности выбрана параметрическая форма, В задачах группировки онн проявляются более четко.
6.8. Функции яриомриеа для аруилирмни множеств Я'„..., Я;. Кюкдое подмножество должно представлять группу, причем выборки из одной группы более подобны между со. бой, чем выборки из разных групп. Чтобы хорошо поставить задачу, единственный путь — это определить функцию критерия, которая измеряет качество группировки любой части данных. Тогда задач~ заключается в определении такого разделения, которое максимизи рует функцию критерия. В этом разделе мы рассмотрим характери стики некоторых в основном подобных функций критериев, отло жив временно вопрос о нахождении оптимального разделения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
