2010 Лекции МОТП. Записки (2010 Лекции МОТП. Записки.pdf), страница 9

Данные «свойства»существенно зависят от длины обучающей выборки и самого алгоритма ихпоиска. В то же время, кратчайшие и минимальные логические описанияклассов образуют уже неизбыточные подмножества, выражающие какосновные свойства данных множеств, так и свойства самих классов. Поэтомуt52smвычисление D j (S ) и D j (S ) может рассматриваться как один из подходов кпроблеме сортировки логических закономерностей классов. Входящие вD sj (S ) и D mj (S ) предикаты могут рассматриваться как наиболее компактныепредставления о классах, включающие как наиболее представительныезнания (предикаты, покрывающие большое число эталонов), так иуникальные или редкие (предикаты, покрывающие малое число эталонов илиотдельные из них).Определение. Логической сложностью (компактностью) классовназываются величины:1. ψ1(Kj)=<число конъюнкций вD sj (S ) >;2.

ψ2(Kj)=<число переменных вD mj (S ) >.lВеличина Φ( I 0 )=∑ψ ( K ) ,i =1iгде ψ - некоторый критерий логическойсложности класса, называется логической сложностью задачи.Естественно ожидать, что если некоторый класс является компактным,простым множеством объектов, хорошо логически отделимым от другихклассов, то он имеет малое число переменных в минимальном логическомописании класса и/или малое число конъюнкций в кратчайшем.7.

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

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

Здесьиспользуются различные общие подходы: последовательный отброснаименее информативных признаков, с использованием кластеризациипризнаков, и другие. Специальные подходы отбора и преобразованияпризнаков имеются в статистической теории распознавания. Многие моделираспознавания включают и свои специфические способы оценки и отборапризнаков.В настоящем разделе рассматривается метод минимизациипризнакового пространства, ориентированный на модели частичнойпрецедентности [1,2] и основанный на кластеризации признаков с учетом ихинформативности и взаимосвязи.7.1. Информативность признаков и логические корреляцииЗадача минимизации признакового пространства рассматривалась длямоделей распознавания, основанных на голосовании по системамлогических закономерностей [1-3].Пусть P - некоторое множество предикатов, найденное по данным обучения.Определение.

Величина wei (i ) = N (i) / N называется мерой информативностипризнака Xi , если N(i) - число предикатов множества P, содержащих признакXi .Пусть N(i,j) -число одновременных вхождений признаков Xi , Xj в однуN (i, j )закономерность по множеству P. Величину Lcorr (i, j ) = 1 −min( N (i ), N ( j ))назовем логической корреляцией признаков Xi и Xj . Данная величина равнанулю, когда во всех закономерностях, куда входит признак Xi, присутствуетXj (и наоборот), т.е. признаки "дополняют друг друга". Корреляция равнаединице, если ни в одну закономерность с признаком Xi не входит Xj.Отметим, что при выборе критериев φ (Pt) согласно [2,3] равным признакамбудет соответствовать единичная корреляция.

В случаях равных илипропорциональных признаков (столбцов таблицы обучения), в силу свойствлогических закономерностей Nij=0 (что непосредственно следует изалгоритма их поиска) и, следовательно, rij=1.Если min(Ni ,Nj)=0, полагаем rij=0 (данный случай возникает ,например, если xi(S)≡ const).7.2. Кластеризация признаков и выбор подсистем признаковРассмотрим задачу нахождения таких кластеров признаков, длякоторых входящие в них признаки обладают близкими корреляционными54свойствами.

В качестве меры корреляционной близости признаковрассмотрим более "тонкий" критерий чем 1 − Lcorr (i, j ) , а именно, основанныйkна полуметрике r (i, j ) =∑ Lcorr (i, l ) − Lcorr ( j, l ) + k × (1 − Lcorr (i, j )) .l =1,l ≠ i , jПервое слагаемое показывает насколько близки признаки поотношению к другим признакам, а второе – насколько они «схожи» междусобой. Множитель k добавлен для того, чтобы слагаемые были соразмерны ивносили примерно одинаковый вклад в определение близости междупризнаками.В качестве алгоритма кластеризации для заданной полуметрики r (i, j ) ификсированного числа классов использовалась иерархическая группировка[4], в которой расстояние между кластерами определялось согласно функцииr ( Kp, Kq ) = max(r (i, j )) .i∈ K p , j ∈ K qПосле нахождения n кластеров в сокращенную подсистему признаковвключаются наиболее информативные признаки (по одному из каждогокластера).Таким образом задача минимизации признакового пространстварешается следующим образом.

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

ПримерыНа Рис.1 приведены графики изменения точности распознавания в моделираспознавания [3] при двух подходах к минимизации признаковогопространства на примере задачи распознавания состояния ионосферы [5].Исходное признаковое пространство включало 34 признака, задачараспознавания решалась относительно двух классов, обучающая выборкаимела длину 181 объектов, контрольная - 170.

Черная линия соответствуетпоследовательному отсеву менее информативных признаков, серая минимизации признакового пространства согласно предложенному внастоящей работе алгоритму. Видно, что серая линия лежит, как правило,ниже черной. "Волнистость" графиков f ( A) является естественнымследствием набора факторов (не идеальность процедур вычисления55предикатов Pt(S), малая длина выборок, "частичная несогласованность"выборок, когда информативность признака на обучающей таблице иконтрольной имеет некоторое различие). Из рисунка следуют естественныекачественные выводы о данной задаче распознавания. Удаление первой третималоинформативных признаков мало влияет на точность распознавания и независит от используемого метода их сокращения. Оставшиеся 20 признаковвполне компенсируют отсутствие остальных 14. При удаление последующих10 потери при кластеризационной минимизации растут меньше, чем причастотной.24Процент ошибок2220Частотный весКластеризация18161434 29 25 23 20 17 15 13 12 11 1098765432Кол-во признаковПроцент ошибокРис.1 Минимизация признакового пространства на примере задачираспознавания состояния ионосферыДругой пример практической иллюстрации выполнен для задачиоценки тяжести заболевания пневмонией с параметрами N=41, l=4 (рис.2).706050403020100Частотный весКластеризация41 35 30 25 22 20 18 16 14 12 10 8654321Кол-во признаковРис.2.

Минимизация признакового пространства на примере задачи оценкитяжести заболевания пневмониейПри всей условности результатов, обусловленных малыми выборкамиобучения (116 объектов) и контроля (57 объектов) выбор малого числа56информативных признаковпредпочтительнее.сиспользованиемкластеризацииявноЛитература.1.

Журавлев Ю.И. Об алгебраическом подходе для решения задачраспознавания или классификации, Проблемы кибернетики, Наука, Москва,1978, выпуск 33, стр.5-68.2. Ryazanov V.V. Recognition Algorithms Based on Local Optimality Criteria //Pattern Recognition and Image Analysis. 1994. Vol.4. no.2. P.98-109.3. Богомолов В.П., Виноградов А.П., Ворончихин В.А., Журавлев Ю.И.,Катериночкина Н.Н., Ларин С.Б., Рязанов В.В., Сенько О.В. Программнаясистема ЛОРЕГ - алгоритмы распознавания, основанные на голосовании помножествам логических закономерностей. Москва, ВЦ РАН, 1998, 63 с.4.

Р.Дуда, П.Харт, Распознавание образов и анализ сцен. Издательство"Мир", Москва, 1976, 511 с.5. Sigillito, V. G., Wing, S. P., Hutton, L. V., \& Baker, K. B. (1989).Classification of radar returns from the ionosphere using neural networks. JohnsHopkins APL Technical Digest, 10, 262-266.1.2.5. Решающие деревья.Методы распознавания, основанные на построении решающих деревьев, относятся к типулогических методов.В данном классе алгоритмов распознавание некоторого объекта осуществляется какпрохождение по бинарному дереву из корня в некоторую висячую вершину. В каждойвершине вычисляется определенная логическая функция.

В зависимости от полученногозначения функции происходит переход далее по дереву в левую или правую вершинуследующего уровня. Каждая висячая вершина связана с одним из классов, в который иотносится распознаваемый объект, если путь по дереву заканчивается в данной вершине.Бинарным корневым деревом (БД) называется дерево, имеющее следующие свойства:а) каждая вершина (кроме корневой ) имеет одну входящую дугу;б) каждая вершина имеет имеет либо две, либо ни одной выходящей дуги.Вершины, имеющие две выходящие дуги, называются внутренними, а остальные –терминальными или листьями.Пусть задано N предикатов Ρ = { y1 = P1 ( S ), y2 = P2 ( S ),..., y N = PN ( S )} , определенных намножестве допустимых признаковых описаний {S}, именуемые признаковымипредикатами. Каждый предикат отвечает на вопрос, выполняется ли некоторое свойство57на объекте S или нет.

Примерами признаковых предикатов могут быть1, если (1.5 ≤ x2 ( S ) ≤ 3.2) & ( x5 ( S ) = 0)P1 ( S ) = в противном случае,0,1, если 0.5 x2 ( S ) + 1.2 x7 ( S ) < 1P2 ( S ) = в противном случае.0,Каждой строке Si = (ai1 , ai 2 ,...ain ) таблицы обучения Tnml = ( aij ) m×n поставим в соответствиебинарную строку значений предикатов на описании Si ⇒ ( yi1 , yi 2 ,..., yiN ), yij = Pj ( Si ) . В0результате, таблице Tnml = ( aij ) m×n будет соответствовать бинарная таблица TNml = ( yij ) m×Nбинарных «вторичных описаний» объектов обучения.Бинарное дерево называется решающим, если выполнены следующие условия:1. каждая внутренняя вершина помечена признаковым предикатом из Ρ ;2.