Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 47
Текст из файла (страница 47)
6.8.1. КРИТЕРИЙ СУММЫ КВАДРАТОВ ОШИБОК Самая простая и наиболее используемая функция критериев это сумма квадратов ошибок, Пусть и,— число выборок в Яь и пусть пз, — среднее этих выборок: т,= — „~ х. 1 (25) х«ЯГ Тогда сумма квадратов ошибок определяется как е ,г, = ~~.'~ ~~.'~ (( х — пз; (~з.
(26) 1 х«ЯГ Эта функция имеет простую интерпретацию. Для данной группы Я', сРедний вектоР т~ лУчше всего пРедставлЯет выбоРки в Яг так как он минимизирует сумму квадратов длин векторов «ошибок х — гпо Таким образом, л", измеряет общую квадратичную ошибку, вносимую при представлении и выборок х„..., х„центрами с групп пзы..., т,. Значение/, зависит от того, как выборки сгруппированы в группы, и оптимальным разделением считается то, кото рос минимизирует г,. Группировки такого типа называют разделе нием с минимальной дисперсией. Какого типа задачи группировки подходят для критерия в виде суммы квадратов ошибок? В основном е', — подходящий крите. рий в случае, когда выборки образуют облака, которые достаточно хорошо отделены друг от друга.
Ои хорошо будет работать для двух или трех групп рис. 6.11, но для данных на рис. 6.12 не даст удои летворительных результатов '). Менее явные проблемы возникают, х) Зги два множества данных хорошо известны по разным причинам. Рис, 6.11 показывает два из четырех измерений, сделанных Е. Андерсоном на 150 выборках трех видов ириса.
Зги данные были использованы Р. А. Фишером в его классическом труде о дискриминантиом анализе (Фишер, 1936) и с тех пор стали излюб. ленным пРимеРом дла иллюстуации пРоцедУР гРУппиРовки. Рис. 6.19 хорош~ известен в астрономии хак диаграмма Герцшпрунга — Рассела, которая привела к делению звезд на такие классы, как гиганты, сверхгигаигы, звезды главной последовательносгв и белые карлики. Она была использована Форджи н затем Вишартом для иллюстрации ограничений в простых процедурах группировки. Р 1 и 5 г' б б 1 Якиег лккгстка- см Рис. 6.11. Даумерное представление данных Андерсона об ирисах и и1г вв вк вв вв ва вг лв кв кг кк кв кв ба а ка кг кк м в ° с и ° ° 1 с *и ° 7 г а гв и .гв «» Рнс. 6.12. Пиаграмма Геришпрунга — Рассела, $ га гм гм б.д.
Функции криимриев для группировки 241 когда имеется большое различие между числом выборок из разных групп. В этом случае может случиться, что группировка, которая разделяет большую группу, имеет преимущество перед группировкой, сохраняющей единство группы, только потому, что достигнутое уменьшение квадратичной ошибки умножается на число членов этой суммы (рис.
6.13). Такая ситуация часто вызывается наличием случайных, далеко отстоящих выборок, и возникает проблема интерпретации и оценки результатов группировок. Так как об этом трудно что-либо сказать, мы просто отметим, что если дополнительные условия приводят к тому, что результат минимизации г*, неудовлетворителен, та эти условия должны быть использованы для формулировки лучшей функции критерия. 682 РОДСТВЕННЫЕ КРИТЕРИИ МИНИМУМА ДИСПЕРСИИ Простыми алгебраическими преобразованиями мы можем избавиться от средних векторов в выражении г', и получить эквивалентное выражение г 1=1 , 'о 1 о о~! о ооо о о, о оно Ъ о, у о ог о о о ~дго о о ! о !! о е о о оро л !1 о к о1! Ъ где — !! х — х' (!е. и) хе $1 х'еХ! (28) о о к l о о о о по 1 о оо о о о о о ', о о о о l о о о о ! оо! о В уравнении (28) эг интерпретируется как среднеквадратичное расстояние между точками 1-й группы и подчеркивает тотфакт, что критерий по сумме квадратов ошибок использует как меру подобия евклидова расстояние.
Оно также подсказывает очевидный путь получения других функций критериев. Например, можно заменить яе средним значением, медианой или, может быть, максимальным расстоянием между тачками в группе. В более общем случае можно ввести соответствующую функцию подобия а(х, х') и заменить 81 такими д Рис. 6.!3. Задача расщепления больших групп: сумма квадратов ошибок меньше для и, чем для б. Гл.
б. Обучение бее учителе и груииирееии 242 функциями, как з;= —, ~~~ ~~е' з(х, х') «ЕЯ'е«'ЕЯ'! (29) нли з! = ш1п з(х, х'). «,Х ЕЯ'; (30) 6,8.3. КРИТЕРИИ РАССЕЯНИЯ 6.8.3.1. Матрицы рассеяния Другой интересный класс функций критериев можно получить из матриц рассеяния, используемых в множественном дискриминаитном анализе. Следующие определения непосредственно вытекают из определений, данных в разд. 4.11.
Средний вектор е-й группы гпг= — ~' х. (31) «ЕЯ! Общий средний вектор ! ! гп = — ~ч~Г х = — ~ я,.еп! Я" !'- ! (32) Матрица рассеяния для е-й группы о! = ~~.", (х — ш!) (х — ш!)!. ХЕ Я ! (33) Матрица рассеяния внутри группы с о !г = .а( о!. (34) Матрица рассеяния между группами Как и раньше, мы считаем оптимальным такое разделение, которое дает экстремум критерия. Это приводит к корректно поставленной задаче, и есть надежда, что ее решение вскроет внутреннюю структуру данных, 2243 6.8. Функции крагпгривв длк группировки Общая матрица рассеяния 5т =- ~ (х — гп)(х — ш)'.
(38) ХЕ Я Как и раньше, из этих определений следует, что общая матрица рассеяния представляет собой сумму матрицы рассеяния внутри группы и матрицы рассеяния между группами: 5т=5ч +5в (37) Отметим, что общая матрица рассеяния не зависит от того, как множество выборок разделено на группы.
Она зависит только от общего множества выборок, Матрицы рассеяния, внутригрупповые и межгрупповые, все же зависят от разделения. Грубо говоря, существует взаимный обмен между этими двумя матрицами, при этом межгрупповое рассеяние увеличивается, если внутригрупповое уменьшается. Это удобно, потому что, минимизируя внутри- групповую матрицу, мы максимизируем межгрупповую. Чтобы более точно говорить о степени вн утригруппового и межгруппового рассеяния, нам нужно ввести скалярную меру матрицы рассеяния.
Рассмотрим две меры — след и определитель. В случае одной переменной эти величины эквивалентны, и мы можем определить оптимальное разделение как такое, которое минимизирует 5„, или максимизирует 5в. В случае многих переменных возникают сложности, и было предложено несколько критериев оптимальности.
6.8.3.2. След в качестве критерия Самой простой скалярной мерой матрицы рассеяния является ее след †сум ее диагональных элементов. Грубо говоря, след измеряет квадрат радиуса рассеяния, так как он пропорционален сумме дисперсий по направлениям координат. Таким образом, очевиднойфункцией критерия для минимизации является след 5„,. В действительности это не что иное, как критерий в виде суммы квадратов ошибок, поскольку из (33) и (34) следует г г (г5я = ~~,' (г5;= ~~'.~ ~~.", ~~х — ш;Ц'=,7г. (38) 1 8=1 квЯг Так как (г 5„= (г 5чг+(г 5в и (г 5т не зависит от разделения выборок, мы не получаем никаких новых результатов при попытке максимизировать (г 5в.
Однако нас должно утешать то, что при попытке минимизировать внутригрупповой критерий 1,=1г 5ц, мы максимизируем межгрупповой критерий (г5в= ~у~,'а;3 шв — ш|!'. (39) г=г Гл. б. Обучение бгз учителя и груллироекл 244 6.8.3.3. Определитель в качестве критерия В разд. 4.11 мы использовали определитель матрицы рассеяния для получения скалярной меры рассеяния.
Грубо говоря, он измеряет квадрат величины рассеяния, поскольку пропорционален произведению дисперсий в направлении главных осей. Так как 5н будет вырожденной матрнцей, если число групп меньше ялн равно размерности, то ! 5л ) — явно плохой выбор для функции критерия. Матрица 5„может быть вырожденной н непременно будет таковой в случае, если а — с меньше, чем размерность г( з). Однако, если мы предполагаем, что 5ьт невырожденна, то приходим к функции критерия )л = ) 5и'! = Д 51 ° (4()) Разделение, которое минимизирует .7л, обычно подобно разделению, которое минимизирует г'„но онн не обязательно одинаковы.
Мы заметили ранее, что разделение, которое минимизирует квадратичную ошибку, может изменяться, если изменяется масштаб по осям. Этого не происходит с г'л. Чтобы выяснить, почему это так, рассмотрим невырожденную матрицу Т н преобразование переменных х'=Тх. Считая разделение постоянным, мы получаем новые средние векторы ш;=Тгп, н новые матрицы рассеяния 5; — — ТБ,Т'. Таким образом, Ув изменяется на ) = 15кг1= 1Т5ЮТг 11= )Т ~1ег 6.8.3.4. Инвариантные критерии Нетрудно показать, что собственные значения Лы..., Лл матрицы 5 )5гг инвариантны прн невырожденных линейных преобразованиях данных. Действительно, этн собственные значения являются основными линейными ннварнантамн матриц рассеяния.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
