Лекция 5 (2012 Лекции МОТП (Сенько))

МАТЕМАТИЧЕСКИЕ ОСНОВЫТЕОРИИ ПРОГНОЗИРОВАНИЯЛекторСенько Олег ВалентиновичЛекция 5Принцип частичнойпрецедентностиСуществует ряд методов распознавания, основанных наПринципе частичной прецедентности. Данный принципподразумеваетпоискфрагментовописаний,распознаваемые классыпоK1,обучающейпозволяющихразделить, KL .Распознаваемый объект оцениваетсянайденных фрагментов.выборкепо совокупностиТестовый алгоритмОднойизпервыхпрецедентностиреализацийявляетсяпринципачастичнойтестовыйалгоритм,предложенный в 1966 году. Данный алгоритм основан напонятии тупикового теста.

Исходный вариант тестовогоалгоритма предназначен для распознавания объектов кописываемых с помощью бинарных или категориальныхпризнаков X1,, Xni. Иными словами X i {a1 ,, aki i } ,где ki - число значений, принимаемых признаком X ii  1,2,,nТестовый алгоритмОбучающей выборке St ставится в соответствие таблицаΤnmL ,j-ой строкой которой являются значения признаков дляsjобъекта.Определение 1. Тестом таблицы ΤnmL называетсясовокупность столбцов {i1,из ΤnmL, ir } таких, что после удалениявсех столбцов, за исключением столбцов {i1, , ir }в полученной таблицеΤrmLвсе пары строк,соответствующие разным классам различны хотя бы поодному признакуТестовый алгоритмОпределение 2. ТестT = {i1, , ir } называется тупиковым,если никакое его отличное от Tподмножество (собственноеподмножество) тестом не является.На этапе обучения ищется множествовсевозможныхтупиковых тестов T ( St ) для таблицы ΤnmL .Предположим что нам требуется распознать объект s* светорным описанием ( x*1,описании фрагмент ( x*i1 ,T = {i1, , ir },T T (St ), x*n ).

Выделим в векторном, x*ir ) , соответствующий тестуТестовый алгоритмФрагмент( x*i1 ,, x*ir )фрагментов строк ( xTji1 ,сравнивается с множеством, xTjir )соответствующих классу K i:таблицы ΤnmL ,{( xTji1 ,, xTjir ) | s j  Ki } . ВT(xxслучаях, когда выполняются равенства *i1ji1 ,фиксируем полное совпадение.Обозначим число полных совпадений через Gi (T, s*.), x*ir  xTjir )Тестовый алгоритмОценка объекта s* за класс K i вычисляется по формуле: i ( s* )  m1iобъектовT T ( St )Gi (T, s* ), где mi - числообучающей выборки из класса K i .Тестовый алгоритм• Классификация объекта s* может производится спомощью по вектору оценок [ 1 (s* ),,  L ( s* )] спомощью стандартного решающего правила, т.е.

объектотносится в тот класс, оценка за который максимальна.Задача нахождения множества всех тупиковых тестовтаблицы ΤnmL сводится к задаче поиска всех тупиковыхпокрытий матрицы сравнений C nmL , которая строится поматрице ΤnmL .Тестовый алгоритмКаждой паре классов K i и K i в матрице C nmL сопоставленаiiCподматрица nmL , состоящая из mi mi строк. Пустьстрока(ciif 1, , ciifn )матрицы C iinmL соответствует сравнениюописаний объекта x g из класса K i и объекта x g  из K iкласса.Элементciifj  0 , если xgj  xgj , и ciifj  1 , если xgj  xgj .Таким образом C nmL имеет размерность M  n , гдеL i 1M   mi mii 1 i '1Тестовый алгоритмМы будем говорить, что столбец с номером j матрицыC nmLпокрывает строку (c f 1, , c fn ) , если c fj  1 .

Набор столбцов{ j1, , jr }образует покрытие матрицы C nmL ,если f {1,, M } j { j1, , jr }такое, что c fj  1 .Покрытие J тупиковым, если его произвольное собственноеподмножество, покрытием не является. Очевидно что дляпроизвольного набора столбцов обладание свойствомтупикового набора для ΤnmL, эквивалентно обладаниюсвойством тупикового покрытия для C nmLТестовый алгоритм• Таким образом задача о поиске всевозможных тупиковыхтестов сводится к известной задаче о поиске всевозможныхтупиковых покрытий.• Нахождение всех тупиковых тестов является сложнойкомбинаторной задачей.

Однако эффективные алгоритмыпоиска разработаны для некоторых типов таблиц. Прирешении практических задач эффективен подход , основанныйна вычислении только части тупиковых тестов.Представительные наборыДругим известным классом алгоритмов распознавания ,основанным на принципе частичной прецедентности,являются алгоритмы типа КОРА. В отличие от тестовогоалгоритма, где в качестве информативных элементовиспользуются несжимаемые наборы признаков – тупиковыетесты, в алгоритмах типа КОРА в качестве информативныхэлементов используются несжимаемые фрагменты описанийэталонных объектов обучающей выборки.Представительные наборыОпределение 3.Пусть ( xv1 ,объекта, xvn ) - признаковое описаниеsv  Ki .

Набор ( xvj ,, xvjr ) называетсяпредставительным набором для класса K i , если для1, xun ) таблицы ΤnmLсоответствующей объекту su  Ki j j { j1 ,произвольной строкитакое, чтоxvj  xuj( xu1,, jr }Представительные наборы• Определение 4. Представительный набор называетсятупиковым, если никакое его собственное подмножествопредставительным набором не является.• На этапе обучения для каждого из классовтаблице ΤnmL ищется множествоK1,, K L повсевозможныхтупиковых представительных наборов.

ПустьVi -множество всевозможных представительных наборовдля классаKiПредставительные наборыПредположим, что нам требуется распознать объект s* сописанием ( x*1,, x*n ) . Пустьu  ( xv1,, xvn ) -представительный набор.Функция ( s* , u ) равна 1, еслии( x*i1  xvi1 ,, x*ir  xvir )( s* , u ) равна 0 в противном случае.1s(s)( s* , u )Оценка * вычисляется по формуле i *| Vi | uViПредставительные наборыДля нахождения тупиковых представительных наборов для классаK i , содержащихся в эталонном описании x v объекта sv  KiiCформируются матрица сравнения nmL со всеми описаниямидругих классов таблицыПустьсравнениюЭлемент cifj  0строкаTnmL .(cif1, , civfn )матрицы C inmLсоответствуетx v с описанием x g объекта s.g  Ki, если x j  xgj , и cifj  1 , если x j  xgj .iCТаким образом матрица nmL имеет размер (m  mi )  n .Представительные наборыiCТупиковые покрытия матриц сравнения nmL определяюттупиковые представительные наборы, являющиесяфрагментами описанияx v .

Полное множествопредставительных наборов для класса K i являетсяобъединением множеств представительных наборов,найденных для описаний всех объектов обучающей выборкиизK i , Таким образом задача поиска всех представительныхнаборов сводится к решениюmi задач поиска тупиковыхпокрытий для матриц сравнения размера (m  m.i )  nОбобщение на задачи свещественнозначной информацииПервоначальные варианты тестового алгоритма иалгоритма типа КОРА были разработаны для бинарныхили категориальных переменных. Они не могут бытьнапрямую использованы в задачах с признаками,принимающими значения из интервалов вещественнойоси. Для того, чтобы обеспечить возможность работы сподобной информацией могут быть использованы дваподхода.Обобщение на задачи свещественнозначной информацией• Первый подход основан на разбиении области возможныхзначений каждого вещественнозначного признака на kсвязных подмножеств (интервалов, полуинтервалов,отрезков).

Значению признака, принадлежащего j-омуэлементу разбиения присваивается значение j. Разбиениеоптимизируется с целью достижения максимальногоразделения классов. Выбирается такое число элементовразбиения k, при котором достигается максимальнаяточность распознавания.Обобщение на задачи свещественнозначной информациейДругой подход основан на модификации понятий теста ипредставительного набора с использованием пороговыхпараметров (1, ,  n )Определение 5. Тестом таблицы ΤnmL называется совокупностьстолбцов {i1,, ir }таких, что после удаления из ΤnmL всехстолбцов, за исключением столбцов {i1,таблицеΤrmL, ir }в полученнойдля всех пар строк, соответствующих разнымклассам абсолютная величина различий хотя бы по одномупризнаку X jпревышает  j .Обобщение на задачи свещественнозначной информацией• Аналогичным образом вводится модифицированноеопределение представительного набора.Определение 6.

Пусть( xv1, , xvn ) - признаковоеописание объекта sv  Ki . Набор ( xvj1 , , xvjr )называется представительным набором для класса K i ,( xu1, , xun ) таблицы ΤnmLсоответствующей объекту sv  Ki j j { j1 , , jr }такое, что | x j  xuj |  j .если для произвольной строкиОбобщение на задачи свещественнозначной информациейГлавным требованием при выборе   порогов являетсядостижение максимальной отделимости объектов разныхклассов при сохранении сходства внутри классов.Поиск тупиковых тестов и тупиковых представительныхнаборов при модифицированных определенияханалогичен их поиску в первоначальных вариантахметодов.Алгоритмы вычисления оценокТестовый алгоритм и алгоритм с представительными наборамиявляются частью более общей конструкции, основанной напринципе частичной прецедентности и носящей названиеалгоритмов вычисления оценок.Существует много вариантов моделей данного типа.

Причёмконкретный вид модели определяется выбранными способамизадания различных её элементов. Рассмотрим основныесоставляющие модели.Алгоритмы вычисления оценок• Задание системы опорных множеств. Под Опорнымимножествами модели АВО понимается наборы признаков, покоторым осуществляется сравнение распознаваемых иэталонных объектов. Примером системы опорных множествявляется множество тупиковых тестов.

Система опорныхмножеств  A некоторого алгоритмаможет задаватьсячерез систему подмножеств множества {1, , n} или черезAсистему характеристических бинарных векторов.Алгоритмы вычисления оценокКаждому подмножеству{1, , n}может быть сопоставленбинарный вектор размерности n . Пусть {i1, , ik }{1, , n} . Тогда{i1, , ik } сопоставляется вектор ω  (1, ,n ) , все компонентыкоторого равны 0 кроме равных 1 компонент i1 , ,ir .Теоретические исследования свойств тупиковых тестов дляслучайных бинарных таблиц показали, что характеристическиевекторы для почти всех тупиковых тестов имеют асимптотически(при неограниченном возрастании размерности таблицыобучения) одну и ту же длину.Алгоритмы вычисления оценокДанный результат является обоснованием выбора в качествесистемы опорных векторов всевозможные наборы,включающие фиксированное число признаковk или A  {ω : | ω | k} .

Оптимальное значение k находится в процессеобучения или задаётся экспертом.Другой часто используемой системе опорных множествсоответствует множество всех подмножеств {1, , n} заисключением пустого множества.Алгоритмы вычисления оценокИными словами в систему опорных множеств входитпроизвольный набор признаков или A  {ω} \ ω0, где ω0 -вектор, все компоненты которого равны 0.Задание функции близости. Пусть опорное множество{i1, , ik }соответствует характеристическому вектору ω . Фрагмент ( xi1 , , xik )описания ( x1, , xn ) объекта S  называется ω - частьюобъекта и обозначается ωS .Алгоритмы вычисления оценокПод функцией близости ω (S , S )соответствующихпонимается функция отω -частей сравниваемых объектов,принимающая значения 1 (объекты близки) или 0 (объектыудалены).Примеры функций близости1, | xi  xi |  i i : i  1ω ( S , S )  0, в противном случаегде (1, ,  n ) - пороговые параметры для различий посоответствующим признакам.Алгоритмы вычисления оценок1, [i | xi  xi |]  ω ( S , S )  0, в противном случае, где  - пороговыйпараметр.Оценки близости распознаваемого объекта S* к эталону S  позаданной ω - части.