Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 51
Текст из файла (страница 51)
Длины ребер минимального покрывающего дерева образуют две различные группы, которые легко обнаружить процедурой минимальной дисперсии. Убирая все ребра длиннее некоторого промежуточного значения, мы можем выделить плотное облако как наибольшую связанную компоненту оставшегося графа. Хотя более сложные конфигурации нельзя так легко изобразить, гибкость подхода, использующего теорию графов, позволяет его применить для широкого круга задач группировки. ВЛ2. ПРОБЛЕМА ОБОСНОВАННОСТИ Почти для всех процедур, которые мы пока что рассмотрели, предполагалось, что число групп известно.
Это разумное предположение, если мы обновляем классификатор, который был создан на малом множестве выборок, или если следим за образами, медленно меняющимися во времени. Однако это очень неестественное предположение в случае, когда мы исследуем совершенно неизвестное множество данных. Поэтому в кластерном анализе постоянно присутствует проблема: сколько групп имеется в множестве выборок? Когда группировка производится достижением экстремума функции критерия, обычный подход состоит в том, что необходимо повторить процедуры группировки для с=1, с=2, с=3 и т.
д. н проследить за изменением функции в зависимости от с. Например, ясно, что критерий по сумме квадратов сшибок 1, должен монотонно уменьшаться в зависимости от с, так как квадратичную ошибку можно уменьшать каждый раз, когда с увеличивается, за счет пересылки одной выборки в новую группу.
Если и выборок разделены на с компактных, хорошо разделенных групп, можно ожидать, что 1, будет уменьшаться быстро до момента, когда с=с, после этого уменьшение должно замедлиться, а прн с=я станет равным нулю. Подобные аргументы можно выдвинуть н для процедуры иерархиче. ской группировки, причем обычно предполагается, что большие различия в уровнях, на которых группы объединяются, указывают на наличие естественных группировок. Более формальным подходом к задаче является попытка найти некоторую меру качества, которая показывает, насколько хорошо данное описание из с групп соответствует данным.
Традиционными мерами качества являются хи-квадрат и статистики Колмогорова— Смирнова, но размерность данных обычно требует использования более простых мер, таких, как функция критерия 1 (с). Так как мы предполагаем, что описание на основании (с+1) групп будет точнее, Гг. 6. Обуигниг бгз чиеггя и груипирагии чем на основании с групп, то хотелось бы знать, что дает статистически значимое улучшение Х(с). Формальным способом является выдвижение нулевой гипотезы, что имеются только с групп, и вычисление выборочного распределения для 1(с+1) этой гипотезы, Это распределение показывает, какого улучшения надо ожидать, когда описание из с групп является правильным.
Процедура принятия решений должна принять нулевую гипотезу, если полученное значение г'(с+1) попадает внутрь пределов, соответствующих приемлемой вероятности ложного отказа. К сожалению, обычно очень трудно сделать что.лнбо большее, кроме грубой оценки такого распределения для У(с+1). Конечное решение не всегда достоверно, и статистическая задача проверки правильности группировки в основном не решена. Однако, предполагая, что даже некачественная проверка лучше, чем никакая, мы проведем следующий приблизительный анализ для простого критерия суммы квадратов ошибок.
Предположим, что мы имеем множество Ю нз п выборок и хотим решить, есть ли какое-либо основание для предположения, что они образуют более одной группы. Выдвинем нулевую гипотезу, что все и выборок получены из нормального распределения со средним !ь и матрицей ковариаций ог1. Если эта гипотеза правильна, то любые обнаруженные группы были сформированы случайно, и любое замеченное уменьшение суммы квадратов ошибок, полученное при группировке, не имеет значения. Сумма квадратов ошибок г,(1) — случайная переменная, так как она зависит от определенного множества выборок: 1,(1) = ~ч~ ~(! х — ш!!', г гЯ где т — среднее всех и выборок. Согласно нулевой гипотезе, распределение для 1,(1) приблизительно нормальное со средним пгЬ' и дисперсией 2лпо4. Предположим теперь, что мы разделяем множество выборок на два подмножества Х, и Я', так, чтобы минимизировать Х,(2), где У,(2) =~я~, '~ !!х — п1;)~', ге Я г здесып~ — среднее выборок в Хо Согласно нулевой гипотезе, такое разделение ложно, но тем не менее дает в результате значение 1,(2), меньшее,/,(!).
Если бы мы знали выборочное распределение для 1,(2), то могли бы определить, насколько мало должно быть У,(2), до того, как будем вынуждены отказаться от нулевой гипотезы одногруппового разделения. Так как аналитическое решение для оптимального разделения отсутствует, мы не можем вывести точного 6,1з. Прадстллмние Валкая решения для распределения выборок. Однако можно получить приблизительную оценку, получив проведением гиперплоскости через среднее выборок разделение, бл1ркое к оптимальному.
Для больших л можно показать, что сумма квадратов ошибок для такого разделения приблизительно нормальна со средним пф — 2/п)о' и дисперсией 2и(д — 8/и')о'. Результат совпадает с нашим предположением, что /,(2) меньше, чем У,(1), так как среднее п(о — 2/п)о' для /,(2) для блйзкого к оптимальному разделению меньше, чем среднее для /,(1) — лс(о'. Чтобы стать значимым, уменьшение суммы квадратов ошибок должно быть больше, чем этот результат.
Мы можем получить приблизительное критическое значение для /,(2), предположив, что близкое к оптимальному разделение почти оптимально, используя нормальную аппроксимацию для распределения выборок и оценивая Ф как 1 1 о' = — ~ч', 11 х — п1 )~' = — У, (1). т1 лл е К ЕЯ Конечный результат можно сформулировать следующим образом: отбрасываем нулевую гипотезу с р-процентным уровнем значимости, если — (1 — — — а ~ (44) где а определяется из выражения ОР р = 100 ~ 1 е- ы'"'1(и. -а Таким образом, мы получим тест для решения, оправданно или нет разбиение группы.
Ясно, что задачу с с группами можно решать, применив те же тесты для всех найденных групп. 6.13, ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПРОСТРАНСТВЕ МЕНЬШЕЙ РАЗМЕРНОСТИ И МНОГОМЕРНОЕ МАСШТАБИРОВАНИЕ Сложность принятия решения, имеет ли смысл данное разделение, частично вытекает из-за невозможности визуального представления многомерных данных, Сложность усугубляется, когда применяются меры подобия или различия, в которых отсутствуют знакомые свойства расстояния. Одним из способов борьбы с этим является попытка представить точки данных как точки в некотором пространстве меньшей размерности так, чтобы расстояние между точками в пространстве меньшей размерности соответствовало различиям между точками в исходном пространстве.
Если бы можно было найти достаточно точное представление в двух- или трехмерном Гп. б. Обунеиип без ипипмпп и гриппироека пространстве, это было бы очень важным способом для изучения внутренней структуры данных. Общий процесс нахождения конфигурации точек, в которой расстояние между точками соответствует различиям, часто называют многомерным иагииплбиробалигм. Начнем с более простого случая, когда имеет смысл говорить о расстояниях между л выборками х„х„..., х„. Пусть у~ — олюбражение х, в пространство меньшей размерности, бы — расстояние между х; и хь а лы — расстояние между у, и у~.
Тогда мы ищем конфигурацию точек отображения у„..., у„, такую, для которой л(л — 1)/2 расстояний йы между точками отображений по возможности близки соответствующим начальным расстояниям боп Так как обычно нельзя найти конфигурацию, для которой А~=бы для всех ( и )', нам необходим некоторый критерий для принятия решения, лучше ли одна конфигурация другой.
Следующие функции сумм квадратов ошибок подходят в качестве кандидатов: — ~ (0,2 — 6,,)*, ~ (бц —,'6,у)и 1 (б,у — 6; )~ Кс1 (45) (46) (47) А~=!!у~ — И!. градиент йм по отношению к у; — зто просто единичный вектор в направлении у, — у~. Таким образом, градиенты функции критерии Так как функции критериев содержат только расстояния между точками, они инвариантны к жесткому передвижению всей конфигурации. Более того, они все нормированы, так что их минимальные значения инвариантны относительно раздвижения точек выборок.
Функция У„выявляет наибольшие ошибки независимо от того, большие или малые расстояния бы. Функция Уо выявляет наибольшие частные ошибки независимо от того, большие или малые ошибки !бы — бн!. Функция У,г — полезяый компромисс, выявляющий наибольшее произведение ошибки и частной ошибки. Если функция критерия выбрана, оптимальной считается такая конфигурация у„..., у„, которая минимизирует зту функцию критерия. Оптимальную конфигурацию можно искать с помощью стандартной процедуры градиентного спуска, начиная от некоторой начальной конфигурации и изменяя у, в направлении наибольшего уменьшения функции критерия. Так как 6.)д.
Представление далям» легко вычислить '): 2 'сч Уа — Уу Чча~., = —, ~„(бау — 6„) Х 6,'уу„-ь ' "«у г<у яч г(ау — бау у| — уу Р„Ууу=2Х Ф Ьзу лау 2 "ау — бау Уь — Уу '(ге у,~'.м ° Хбгу у~ь '«у лау ' Начальную конфигурацию можно выбрать случайным или любым другим способом, как-то распределяющим точки отображения.
Если точки отображения лежат в г(-мерном пространстве, то можно найти простую и эффективную начальную конфигурацию путем выбора тех г( координат выборок, у которых наибольшая дисперсия. Следующий пример иллюстрирует результаты, которые можно получить этими методами ').
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
