_учебник_ Журавлев Ю.И. Распознавание. Математические методы. Программная система. Практические применения (2005) (1185319), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

Тогда U { A}  {U {B}  C*} являетсякорректным относительно {Z}, если {Z} состоит из задач, полных относительно {B} .aij1qlПрименениеIaij2B1qlbi1i2 ...itПрименение~SqB2qlАлгебраическая коррекцияматриц оценокaijkaiji1 aiji2 ...aijit ijqlПрименение C*qlПрименениеBkРис.15. Алгебраическая коррекция эвристических алгоритмов1.4.3. Логическая коррекция множеств распознающих алгоритмов.Подобно тому, как было ранее введено сложение распознающих операторов иумножение их на скаляр, можно рассматривать операции над распознающимиалгоритмами как операции над информационными матрицами. Однако если множествораспознающих операторов образует линейное векторное пространство, то в множествахинформационных матриц таких хороших операций нет /26/. Тем не менее использованиемногоместных операций над множествами информационных матриц позволяет создатьсредства синтеза эффективных распознающих алгоритмов, непосредственным входом52которых являются результаты независимого распознавания объектов алгоритмами иззаданного конечного набора.Рассмотрим для простоты случай отсутствия отказов при классификации.

Пусть заданколлектив из n распознающих алгоритмов A1 , A2 ,..., An , Ak ( I , S ,..., S ) ||  k ||1ij q  l ,qk  1,2,..., n. Пусть матрица || ij ||q  l является информационной матрицей набораS1 ,..., Sq{|| ijk ||q lпосистеме, k  1,2,..., n,|| ij ||предикатовqlP1 ,..., Pl .Множестваматриц} определяют l не всюду определенных булевыхфункций f j ( y1 , y2 ,... yn ), j  1,2,..., l . При этом f j (  ij1 ,  ij2 ,...,  ijn )   ij , i  1,2,..., q , и функцияf j ( y1 , y2 ,... yn ) не определена на остальных 2 n  q наборах. Основная задача состоит втаком доопределении функции на весь дискретный единичный куб E n , при котором будутмаксимально выполнены дополнительные «содержательно обоснованные» условия,обеспечивающие некоторый однозначный и оптимальный выбор такой функции.

Данныефункции будем называть логическими корректорами. Если подобные функции построены,~~то процесс распознавания произвольной новой выборки объектов S t  {S '1 , S ' 2 ,..., S 't }алгоритмами A1 , A2 ,..., An с последующей логической коррекцией может быть представленсхематически на рис. 16.aij1t lПрименениеIaij2t l||  ij1 ||t lB1t l ijПрименение~~St||  ij1 ||t lB2Логическая коррекциярешений алгоритмовaijk||  ij1 ||t lПрименениеBkt lПрименение C*Рис.16. Логическая коррекция алгоритмов распознавания53Существуют разнообразные подходы к выборы типа логических корректоров и методы ихпоиска.

Приведем в качестве примера «монотонный логический корректор». Здесь воснову положена следующая идея. Пусть известно, что при классификации некоторогообъекта S , принадлежащего классу K j , он зачисляется в данный класс алгоритмамиAi1 , Ai2 ,..., Aik . Тогда, если некоторый новый объект S ' классифицируется даннымиалгоритмами как принадлежащий K j , и он относится в K j дополнительно некоторымалгоритмом At , t  {i1 , i2 ,..., ik } , тогда естественно считать коллективной классификаций дляS ' решение S '  K j . Математической формализацией данного правила монотоннойкоррекции алгоритмов будет следующая задача.Даначастичноопределенная~ 1 2f j (  ij ,  ij ,...,  ijn )   ij , i  1,2,..., q .булеваТребуетсяфункциянайти~f j ( y1 , y2 ,..., yn ) ,монотоннуюбулевупричемфункциюf j ( y1 , y2 ,..., yn ) , для которой выполнено f j (  ij1 ,  ij2 ,...,  ijn )   ij , i  1,2,..., q .

Отметим, чтоданная задача не имеет решения в случае противоречивости некоторой пары наборов{ ij1 ,  ij2 ,...,  ijn ; ij } и { tj1 ,  tj2 ,...,  tjn ; tj } ( ijk  tjk , k  1,2,..., n , но  ij   tj ). В данном случаена практике обычно находится монотонная булева функция для непротиворечивогомножества наборов по контрольной выборке и применяются эвристики, либо из каждойпары противоречивых наборов исключается «менее представительный».Различные методы логической коррекции алгоритмов распознавания описаны вработах /32, 36, 60/.1.4.4.

Выпуклый стабилизатор.Одной из наиболее острых проблем, возникающих при решении практическихзадач распознавания образов, является «перенастройка» алгоритмов распознавания.Алгоритм настраивается на заданную выборку, демонстрируя на ней высокое качествоработы, но стремительно деградирует при предъявлении новых объектов. Дляперенастроенных алгоритмов обычно крайне сложно получить оценку качества работы всилу неустойчивости их работы. Перенастройка связана с большим числом параметров,оптимизируемых при обучении, и происходит, как правило, на малых выборках.Припостроенииколлективныхрешений,удаетсяповыситьустойчивостьполучаемого алгоритма по сравнению с исходными, и, тем самым, значительно54уменьшить эффект перенастройки.

В основе идеи стабилизации алгоритмов лежитпонятие неустойчивости алгоритма распознавания на объекте.Пусть имеется задача распознавания с l классами. Каждый объект представленвектором в n-мерном действительном пространстве. Обозначимik ( S j ) оценкуапостериорной вероятности принадлежности j-го объекта к k-му классу, полученную спомощью i-го исходного алгоритма распознавания. Тогда приняв за неустойчивостьалгоритма на данном объекте величинуlZ B (S j ,  )  k 11k2n[ i 1kB( S j   k  ei )   kB ( S j )]2 ,(B – распознающий оператор, соответствующий алгоритму A) получим выражение для~неустойчивости данного алгоритма на контрольной выборке S q  {S1 , S 2 ,..., S q }qZ B ( )   Z B ( S j ,  ) .j 1Будем искать коллективное решение в виде выпуклой комбинации исходных алгоритмовq (S ) kB w ( S )j 1jkB ( F ( j ))q w (S )j 1(S ), k=1…l , S  R n ,jгде F :{1...q}  {1...

p} - некоторая функция, определяющая номер распознающегооператора для каждого объекта контрольной выборки; а w j : R  Rnфункции, обладающие следующими свойствами:w j (S )  0при (S , S j )   ,- весовые55wi ( S )q w (S )j 11при ( S , Si )  0.jВ качестве функции F будем использовать номер наиболее устойчивого насоответствующем объекте алгоритма, который его правильно распознает (если таковойимеется), и номер наиболее устойчивого алгоритма среди всех, если ни один исходныйалгоритм не распознает данный объект верно. Тогда подобрав соответствующим образомвесовую функцию, получим коллективное решение, названное выпуклым стабилизатором.Было показано, что выпуклая стабилизация позволяет сохранить высокиедискриминационныесвойстваисходныхалгоритмов,увеличиваяприэтомихустойчивость по отношению к изменениям положения объектов (а, следовательно,гарантируя перенесение хорошего качества работы на произвольные объекты).

Для тогочтобы использовать выпуклуюстабилизациюалгоритмов, необходимо провестипроцедуру обучения по контрольной (возможно, совпадающей с обучающей) выборке. Изза большого объема вычислений, выполняемых как на этапе обучения, так и на этапераспознавания, данный метод имеет смысл применять на небольших выборках /84/.Другие возможные подходы и алгоритмы построения коллективных решений задачираспознаванияописаныв/47,РАСПОЗНАВАНИЕ, описаны в главе 3.69/.Подходы,используемыевСистеме56Глава2.Математические(классификации без учителя).методыкластерногоанализаВажный раздел теории распознавания составляют методы кластеризации (илиавтоматической классификации, таксономии, самообучения, обучения без учителя,группировки), решающие задачи разбиения выборок объектов (при заданных признаковыхпространствах или матрицах близостей объектов) на классы эквивалентности, причемэквивалентность объектов базируется на мерах близости, сходстваи т.п.

Изперечисленного набора используемых названий, близких друг другу и воспринимаемыхпочти как синонимы, будет далее использоваться обычно термин «кластеризация» узкоспециализированный, но не допускающий двусмысленности как, например, термин«классификация». Соответственно, термин «кластер» будет использоваться как синонимтермину «класс», но обозначать именно множество близких объектов, полученное какрезультат решения задачи кластерного анализа.Методы кластерного анализа позволяют решать задачи минимизации числа эталонов,поиска эталонных описаний, выявления структурных свойств классов и многие другиевопросы анализа данных. Принципы, согласно которым объекты объединяются в одинкластер, являются обычно “внутренним делом” конкретного алгоритма кластеризации.Пользователь, зная данные принципы, может в определенных пределах интерпретироватьрезультаты каждого конкретного метода.

Характеристики

Список файлов книги