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

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

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

В этом случае для определения границ доверительногоинтервала достаточно решить уравнения относительноm ek 0mek  m  и ( ) k1 ,k!( ) k1 .k!Границы доверительного интервала в этом случае равны соответственно m и m . В программном комплексе РАСПОЗНАВАНИЕ реализованы все упомянутыевыше подходы с автоматическим выбором наиболее подходящего способа подсчетаграниц доверительного интервала для данной задачи.

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

Во многих случаях системапризнаков формируется "стихийно". В ее состав включаются все показатели, влияющие на97классификацию (хотя бы чисто гипотетически), и которые можно вычислить илиизмерить. Независимо от числа имеющихся признаков, исходная система признаков, какправило, избыточна и включает признаки, не влияющие на классификацию илидублирующие друг друга.

В некоторых практических задачах распознавания затраты навычисление части признаков могут быть значительными и конкурировать со стоимостьюпотерь при распознавании. Решение задач обучения при меньшем числе признаков такжеявляется более точным, а полученные решения более устойчивыми. Таким образом,решение задач минимизации признаковых пространств является важным во многихотношениях.Рассмотрим задачу минимизации признакового пространства в следующейпостановке. Пусть имеется модельалгоритмов распознавания, признаковоепространство X1, X2,…,XN и критерий качества f ( A) есть доля правильно распознанныхобъектов контрольной выборки алгоритмом A. Требуется найти такое признаковоеf ( A)  f 0 , где f 0подпространство X i1 , X i2 ,..., X in , с минимальным n , для которого-некоторый минимально допустимый порог точности алгоритма распознавания A,построенного по данным обучения для данного подпространства.В силу своего комбинаторного характера, методы перебора значительного числаразличных признаковых подпространств практически нереализуемы, поэтому обычноиспользуются процедуры последовательного выбора из системы k признаков подсистемыиз k-1 признака.

Здесь используются различные общие подходы (последовательныйотброс наименее информативных признаков, использование кластеризации признаков, ит.п.).Специальныеподходыотбораипреобразованияпризнаковимеютсявстатистической теории распознавания. Многие модели распознавания включают и своиспецифические способы оценки и отбора признаков.Внастоящемразделерассматриваетсяметодминимизациипризнаковогопространства, ориентированный на модели частичной прецедентности /25, 26/ иоснованныйнакластеризациипризнаковсучетомихинформативностиикоррелированности.

Рассмотрим один подход, основанный на использовании алгоритмовголосования по системам логических закономерностей /71/.Пусть P - некоторое множество логических закономерностей, найденное по даннымобучения.Определение 9. Величина wei (i )  N (i ) / P называется мерой информативности признака(информационным весом признака) Xi , если N(i) - число логических закономерностеймножества P, содержащих признак Xi .98Пусть N(i,j) - число одновременных вхождений признаков Xi, Xj в одну закономерностьпо множеству P.

Величину Lcorr(i, j )  1 N (i, j )назовем логическойmin( N (i), N ( j ))корреляцией признаков Xi и Xj . Данная величина равна нулю, когда во всехзакономерностях, куда входит признак Xi, присутствует Xj (и наоборот), т.е. признаки"дополняют друг друга". Корреляция равна единице, если ни в одну закономерность спризнаком Xi не входит Xj. Отметим, что при выборе критериев (Pt) согласно /76/ равнымпризнакам будет соответствовать единичная корреляция. В случаях равных илипропорциональных признаков (столбцов таблицы обучения), в силу свойств логическихзакономерностей Nij=0 (что непосредственно следует из алгоритма их поиска) и,следовательно,Lcorr (i, j )  1 .Если min(Ni ,Nj)=0, полагаемLcorr (i, j ) =0 (данный случай возникает , например,если xi(S)const).Рассмотрим задачу нахождения таких кластеров признаков, для которых входящиев них признаки обладают близкими корреляционными свойствами.

В качестве мерыкорреляционной близости признаков рассмотрим более "тонкий" критерий чем1  Lcorr (i, j ) ,r (i, j ) аименно,основанныйнаполуметрикеN Lcorr(i, l )  Lcorr( j, l )  ( N  2)  (1  Lcorr(i, j)) .l 1,l  i , jПервое слагаемое показывает насколько близки признаки по отношению к другимпризнакам, а второе – насколько они «схожи» между собой.

Множитель N-2 добавлен длятого, чтобы слагаемые были соразмерны и вносили примерно одинаковый вклад вопределение близости между признаками.В качестве алгоритма кластеризации для заданной полуметрикиr (i, j )ификсированного числа кластеров использовалась иерархическая группировка /19/, вкоторой расстояние между кластерами определялось согласно функцииr ( Kp, Kq )  max(r (i, j )) .i K p , j  K qПосле нахождения n кластеров в сокращенную подсистему признаков включаютсянаиболее информативные признаки (по одному из каждого кластера).Таким образом задача минимизации признакового пространства решаетсяследующим образом.

Предполагается, что для исходного признакового пространствавыполнено f ( A)  f 0 . Вычисляется матрица значений r (i, j ) .99Пусть на некотором шаге k=0,1,2,… получено с помощью кластеризации N-kгруппировок признаков а из каждой группировки выбран признак с максимальным весом.ВрезультатебудетX N  k  { X i1 , X i2 ,..., X i N k } .полученопризнаковоеподпространствоПусть AN-k - построенный в данном подпространствеалгоритм распознавания.

В качестве решения задачи минимизации признаковогопространствапринимаетсямаксимальному k при ограниченииX N  k  { X i1 , X i2 ,..., X i N k } ,соответствующееf ( AN  k )  f 0 .На Рис.27 приведены графики изменения точности распознавания в моделиголосования по системам логических закономерностей при двух подходах к минимизациипризнакового пространства на примере задачи распознавания состояния ионосферы /83/.Исходное признаковое пространство включало 34 признака, задача распознаваниярешалась относительно двух классов, обучающая выборка имела длину 181 объектов,контрольная - 170. Черная линия соответствует последовательному отсеву менееинформативных признаков, серая - минимизации признакового пространства согласноизложенному выше алгоритму.

Видно, что серая линия лежит, как правило, ниже черной."Волнистость" графиковf ( A) является естественным следствием набора факторов(неидеальность процедур вычисления предикатов Pt(S), малая длина выборок, "частичнаянесогласованность" выборок, когда информативность признака на обучающей таблице иконтрольной имеет некоторое различие). Из рисунка следуют естественные качественныевыводы о данной задаче распознавания. Удаление первой трети малоинформативныхпризнаков мало влияет на точность распознавания и не зависит от используемого методаих сокращения - оставшиеся 20 признаков вполне компенсируют отсутствие остальных14. При удаление последующих 10 потери при кластеризационной минимизации растутменьше, чем при частотной.10024Процент ошибок2220Частотный весКластеризация18161434 29 25 23 20 17 15 13 12 11 10 98765432Кол-во признаковРис.27. Минимизация признакового пространства на примере задачи распознавания состояния ионосферы3.13.

Алгоритмы кластерного анализаВ настоящем разделе приводятсяреализованныхвсистемедополнительныйРАСПОЗНАВАНИЕматериалыалгоритмовкописаниямкластерногоанализа,изложенным в главе 2. Коллективное решение задачи кластерного анализа находитсясогласно подходу, описанному в 2.4.Алгоритмиерархическойгруппировкиреализуетстандартнуюсхемуиерархической кластеризации на заданное число кластеров. В качестве функций d(Ti, Tj)расстояния между группировками объектов реализованы два «противоположных»подхода:1. d min (Ti , T j ) minS Ti , S  T j ( S , S  );2.

d max (Ti , T j )  max  ( S , S  ) .S Ti , S  T jПри использовании первого подхода ближайшим соседом каждого объекта будетобъект из того же кластера. Это главное свойство данного подхода. При выполненииданного свойства, тем не менее, в пределах одного кластера могут быть весьма далекиеобъекты, менее близкие, чем некоторые объекты из различных кластеров.Наоборот, при использовании второго подхода центральным условием алгоритмаявляется создание таких кластеров, в которых не будет «очень непохожих» объектов.Здесь близость объектов разных кластеров отходит на второй план, главное – построениекластеров с минимальными диаметрами.Когда размеры кластеров существенно больше расстояния между ними, алгоритм«ближайший сосед» формирует кластеры из малого числа объектов или вообще101состоящие из единичных точек.

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

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