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

Вычисляются близости – «голоса» (равные 1 или 0)распознаваемого объекта к эталонам некоторого класса по определеннымразличнымподмножествампризнаков.Данныеблизости(«голоса»)суммируются и нормируются на число эталонов класса. В результатевычисляется нормированное число голосов, или оценка объекта S за классΓj (S ) – эвристическая степень близости объекта S к классуK j . Послевычисления оценок объекта за каждый из классов, осуществляется отнесениеобъекта к одному из классов (т.е.

распознавание класса объекта) с помощьюрешающегоправила.Оптимальныезначенияпараметровалгоритмов7распознавания (если он содержит некоторые неизвестные параметры),определяются из решения задачи оптимизации данной модели распознавания- находятся такие значения параметров, при которых точность распознаванияявляется максимальной на некоторой заданной контрольной выборке.2.1. Тестовый алгоритм распознаванияТестовый алгоритм является одним из первых представителейширокого класса алгоритмов распознавания, основанных на принципечастичной прецедентности, в которых сравнение распознаваемого объекта сэталонными осуществляется по различным «информативным» и «сложно»вычисляемым подмножествам признаков.

В качестве подобных подсистемпризнаков используются тупиковые тесты и их аналоги [1,2,4].Дляxi ( S ) ∈ {0,1,..., k − 1}случаяпризнаковизвестныпонятияцелочисленныхтестаи(kтупикового-значных)теста[21].Определение. Подмножество столбцов (i1, i 2 ,... , i k ) таблицы эталонов T nmlназывается тестом, если любые две строки подтаблицы, образованнойданными столбцами, различны при условии их принадлежности разнымклассам. Тупиковым называется тест, любое собственное подмножествокоторого не является тестом.Для вещественнозначных таблиц T nml легко вводится аналогтестам таблиц конечнозначных, если строки подтаблиц считать различнымипри их различии с точностью до параметров (ε1, ε 2 ,..., ε n ) .Тупиковыйтест-минимальнаяподсистемапризнаков,разделяющая эталоны разных классов.Пример 1.

Таблица T4, 4, 2 :S1 0111 ∈ K1S 2 1010S 3 0011∈ K2S 4 10008Здесь {1,2,3,4}, {2,3,4} – тесты; {1,2} – не является тестом. Таблица имеетдва тупиковых теста: {2,3,4},{1,2,3}.Пример 2. Таблица T5, 4, 2 :S1S2S3S410110 ∈ K11000001101 ∈ K200011Здесь тупиковыми тестами являются наборы {1},{3,4},{4}.Пример 3.

Таблица T6, 4, 2 :010010101011110101000000Здесь 6-й столбец не входит ни в один тупиковый тест. Столбец 4-й входитво все тесты, поскольку после его удаления будут равны строки разныхклассов (1-я и 4-я). Множество тупиковых тестов образуют наборынаборы {1,2,4},{2,3,4},{2,4,5}.Рассмотрим кратко вопрос нахождения тупиковых тестов. ПустьTnml = aijm×n, где aij = x j ( S i ) ∈{0,1,..., k − 1} . Таблице T nml ставится всоответствие матрица сравнения C = cij, Sν ∈ K u , S µ ∈ K v , u ≠ v ,N=∑ (mi> ji , j =1, 2 ,...,li1, aνj ≠ aµj ,cij = i = i (ν , µ ),гдеN ×n0,a=a,νjµj− mi −1 )(m j − m j −1 ).Пример 3.010001001011010010110001111010101011010111009ТаблицаМатрицаобученияС6×4сравненияT4,5, 2Столбцы (i1, i 2 ,...

, i k ) образуют покрытие строк матрицы C = cijN ×n, если ∀i = 1,2,..., N , ∃j ∈ {i1 , i2 ,..., ik } : сij = 1 .Покрытиеназываетсятупиковым,еслипроизвольноеегособственное подмножество не является покрытием. Нетрудно убедиться, чтонаборы {1,2,4}, {1,3,4}, {2,3,4} образуют все тупиковые покрытия матрицысравнения из примера 3. Каждому тупиковому тесту соответствует тупиковоепокрытие строк матрицы сравнения и наоборот.Тупиковый тест, состоящий из минимального числа столбцов,называется минимальным тупиковым тестом.

Задача поиска минимальноготупикового теста может быть сформулирована как задача целочисленноголинейного программирования.Рассмотрим следующую оптимизационную задачу:n∑xj =1j→ min ,ijx j ≥ 1, i = 1,2,..., N ,n∑cj =1(1)x j ∈ {0,1}.Легко видеть, что единичные компоненты решения данной задачиопределяют минимальный тест. Если понимать под локальным минимумомданной задачи любой допустимый бинарный набор ( x1 , x2 ,..., xn ) , в которомлюбая замена некоторой единицы на ноль делает его недопустимым, томножество локально-оптимальных решений задачи определяет множествотупиковых тестов.Тестовыйалгоритмраспознаванияопределяетсяследующимобразом.10Пусть заданы значения неотрицательных числовых параметров(ε1, ε 2 ,..., ε n ) . Значения числовых параметров (ε1, ε 2,..., ε n ) задают порогиблизости соответствующих признаков и могут вычисляются, например, каксредний модуль разности значений признака по обучающей выборке :εν =m2| xv ( S i ) − xv ( S j ) | .

Пусть для заданных значений параметров∑m(m − 1) i , j =1,i > j(ε1, ε 2 ,... , ε n ) и таблицы обучения T nml найдено множество {T } всехтупиковых тестов. Пусть T = {i1 , i2 ,...ik } - некоторый тупиковый тест таблицыT nml , заданный соответствующими номерами ее столбцов. Для простотыобозначений тупиковые тесты будем записывать как множество номеровобразующих тест столбцов.Определим функцию близости между частями описаний некоторогоэталонного объекта Sν и S , соответствующим данному тупиковому тесту:1, | xi ( S ) − xi ( Sν ) |≤ εν , ∀i ∈ T ,иначе.0,BT ( Sν , S ) = Назовем оценкой объекта S(2)за класс K j («мерой близости» кклассу) следующую величину:mj1Γj (S ) =∑ ∑ BT (Sν , S ) .(m j − m j −1 ) ν =m j −1 +1T∈{T }(3)Таким образом, близость объекта к классу определяется какнормированная на число эталонов класса сумма близостей объекта ко всемэталонам данного класса по всем тупиковым тестам.

Пусть вычисленыоценки объекта Sза каждый из классов. Объект Sпринадлежащим классуналичиядвухилиKj ,болеесчитаетсяесли Γ j ( S ) > Γi ( S ), i = 1,2,..., l . В случаеравныхмаксимальныхоценок,алгоритмотказывается от классификации S.ЛЕКЦИЯ 311(тестовый алгоритм, продолжение)Существуют эффективные алгоритмы поиска тупиковых тестов[17,18]. Тем не менее, задача нахождения множества всех тупиковых тестовявляется вычислительно сложной комбинаторной задачей и не может бытьрешена на современных компьютерах даже для относительно небольшихтаблиц обучения (сотни объектов и признаков). Поэтому при решениипрактических задач вычисляют и используют в процедурах голосованияобычно лишь часть тупиковых тестов [17,18] .В Системе РАСПОЗНАВАНИЕ реализован стохастический вариантидеи тестового алгоритма.

Из таблицы обучения выбираются случайно Nподтаблиц, каждая из которых состоит из 3 строк таблицы обучения, Nподтаблиц, состоящих из 4 строк таблицы обучения, и т.д., N подтаблиц,состоящих из k строк таблицы обучения (здесь Nи k – управляющиепараметры программы). Каждая подтаблица не обязана содержать эталоны изкаждого класса, т.е. допускаются подтаблицы с числом строк меньшим числаклассов. Это не приводит к дальнейшему использованию «плохих» тестов,так как каждому тесту впоследствии сопоставляется вес (качество) уже пополной обучающей выборке.

Для каждой подтаблицы находятся всетупиковые тесты либо один минимальный тест в зависимости от выбранногоалгоритма поиска. В последнем случае для таблицы обучения находится неболее N* (k-2) минимальных тестов случайных подтаблиц.Обозначим множество всех найденных тупиковых тестов дляподтаблиц как и ранее через {T }. Пусть M1 ={ Si , S j } множество пар строктаблицы обучения, принадлежащих равным классам, а M2 - множество парстрок из разных классов. Число элементов множеств M1 и M2 обозначим,соответственно, через n1 и n2. Антиблизостью объектов по опорномумножеству T ∈ {T } назовем бинарную величинуDT ( Sν , S µ ) = 1 − BT ( Sν , S µ ) .12Определим «вес» опорного множества (в нашем случае теста T )согласно выражению (4)QT =11()DS,S−DT ( Si , S j )∑∑Tijn2 ( S i , S j )∈M 2n1 ( S i , S j )∈M 1, а черезwT =QT∑ QT(4)– его удельный вес. Данные величиныT ∈{T }показывают, как часто бывают близки эталонные объекты одного класса идалеки объекты разных классов по выбранному опорному множеству.Окончательно, оценки распознаваемого объекта за классыKj ,j=1,2,…,l, вычисляются согласно следующей формуле:1Γ j ( S ) = ∑ wT  K j2 T ∈{T } −1∑BSi ∈K jКлассификацияT((S , Si ) + m − K jосуществляетсяс)−1DT ( S , S i ) ∑.Si ∉K jпомощьюпростейшегорешающего правила.В случаях практических задач с плохой отделимостью классовтупиковые тесты будут иметь большое число столбцов или могут вообщеотсутствовать.

Для управления отделимостью классов введен управляющийпараметр программы (делитель ε - порогов), позволяющий увеличивать-13уменьшать близость объектов. Для небольших по количеству признаковтаблицобучениявозможновычислениевсехтупиковыхтестови,соответственно, голосование по всем тупиковым тестам. Для реализацииданного варианта в Системе предусмотрена кнопка «переборный алгоритм» .2.2. Алгоритмы распознавания, основанные на вычисленииоценокТестовый алгоритм стал первым широко известным в теориираспознаванияпрецедентности.подходом,основаннымЮ.И.Журавлевымбыланапринципепредложеначастичнойболееобщаяформализация с различными способами выбора информативных подсистемпризнаков и формулами для вычисления оценок.