Лекция 5. Принцип частичной прецедентности_ тестовый алгоритм_ модель ABO (2015 Лекции (Сенько))

Лекция 5Прицип частичной прецедентности, тестовый алгоритм,модель АВОЛектор – Сенько Олег ВалентиновичКурс «Математические основы теории прогнозирования»4-й курс, III потокСенько Олег Валентинович ()МОТП, лекция 21 / 24Содержание лекции1Тестовый алгоритм2Представительные наборы3Алгоритмы вычисления оценокСенько Олег Валентинович ()МОТП, лекция 22 / 24Принцип частичной прецедентности. Тестовый алгоритм.Существует ряд методов распознавания, основанных на принципечастичной прецедентности. Данный принцип подразумевает поиск пообучающей выборке фрагментов описаний, позволяющих разделитьраспознаваемые классы K1 , . . . , KL . Распознаваемый объектоценивается по совокупности найденных фрагментов.

Одной из первыхреализаций принципа частичной прецедентности является тестовыйалгоритм, предложенный в 1966 году. Данный алгоритм основан напонятии тупикового теста. Исходный вариант тестового алгоритмапредназначен для распознавания объектов, описываемых с помощьюбинарных или категориальных признаков X1 , . . . , Xn . Иными словамиXi ∈ {ai1 , . . . , aiki }, , i = 1, 2, . . . , n.Сенько Олег Валентинович ()МОТП, лекция 23 / 24Тестовый алгоритмПусть обучающая выборка Set , содержит объекты из классовK1 , . . .

, KL . При этом общее число объектов равно m. Выборке Setставится в соответствие таблица TnmL , j-ой строкой которойявляются значения признаков для объекта sj .Определение 1. Тестом таблицы TnmL называется совокупностьстолбцов i1 , . . . , ir таких, что после удаления из TnmL всех столбцов,за исключением i1 , . . . , ir , в полученной таблице все пары строк,соответствующие разным классам различны хотя бы по одномупризнакуОпределение 2.

Тест T = {i1 , . . . , ir } называется тупиковым, еслиникакое его отличное от T подмножество (собственное подмножество)тестом не является.На этапе обучения ищется множество всевозможных тупиковых тестовTe(Set ) для таблицы TnmL . Предположим что нам требуетсяраспознать объект s∗ с векторным описанием (x∗1 , . . .

, x∗n ) .Сенько Олег Валентинович ()МОТП, лекция 24 / 24Тупиковые тестыВыделим в векторном описании фрагмент (x∗i1 , . . . , x∗ir ) ,соответствующий теcтуT = {i1 , . . . , ir }, T ∈ Te(Set ).Фрагмент (x∗i1 , . . . , x∗ir ) сравнивается с множеством фрагментовстрок таблицы TnmL , соответствующих классу Kl :{(xtji1 , . .

. , xtjir ) | sj ∈ Kl } . В случаях, когда выполняются равенстваx∗i1 = xtji1 , . . . , x∗ir = xtjirфиксируем полное совпадение распознаваемого объекта s∗ с объетомsj ∈ Kl тесту T . Обозначим число полных совпадений черезGl (TnmL , s∗ , T ) .

Оценка объекта s∗ за класс Kl вычисляется поформуле:1 Xγ(s∗ ) =Gl (TnmL , s∗ , T ),mlet )T ∈Te(Sгде ml - числообъектов обучающей выборки из класса Kl .Сенько Олег Валентинович ()МОТП, лекция 25 / 24Тупиковые тестыКлассификация объекта s∗ может производится по вектору оценок[γ1 (s∗ ), . . . , γL (s∗ )] с помощью стандартного решающего правила, т.е.объект относится в тот класс, оценка за который максимальна. Задачанахождения множества всех тупиковых тестов таблицы TnmL сводитсяк задаче поиска всех тупиковых покрытий матрицы сравнений CnmL ,которая строится по матрице TnmL . Каждой паре классов Kl и Kl0 в0матрице CnmL сопоставлена подматрица CllnmL , состоящая из ml ml0000строк.

Пусть (cllf 1 , . . . , cllf n ) строка матрицы CllnmL соответствуетсравнению описаний объекта xg из класса Kl и описание объекта xg000из класса Kl0 . Элемент cllf i = 0 , если xgi = xg0 i , и cflli = 1 , еслиxgi 6= xg0 i . Таким образом CnmL имеет размерность M × n ,P Pl−1где Ll=1l0 =1 ml ml0 .Сенько Олег Валентинович ()МОТП, лекция 26 / 24Методы поиска тупиковых тестов.

Задача о покрытии.Мы будем говорить, что столбец с номером j матрицы CnmLпокрывает строку (cf 1 , . . . , cf n ) , если cf j = 1 . Набор столбцов{j1 , . . . , jr } образует покрытие матрицы CnmL , если при любомf ∈ {1, . . . , M } существует такое j 0 ∈ {j1 , . . .

, jr } , что cf j 0 = 1 .Покрытие Je называется тупиковым, если его произвольноесобственное подмножество, покрытием не является. Очевидно, чтодля произвольного набора столбцов обладание свойством тупиковогонабора для TnmL эквивалентно обладанию свойством тупиковогопокрытия для CnmL . Таким образом задача о поиске всевозможныхтупиковых тестов сводится к известной задаче о поиске всевозможныхтупиковых покрытий. Нахождение всех тупиковых тестов являетсясложной комбинаторной задачей. Однако эффективные алгоритмыпоиска разработаны для некоторых типов таблиц. При решениипрактических задач эффективен подход, основанный на вычислениитолько части тупиковых тестов.Сенько Олег Валентинович ()МОТП, лекция 27 / 24Предстаительные наборыДругим известным классом алгоритмов распознавания, основанным напринципе частичной прецедентности, являются алгоритмы типаКОРА.

В отличие от тестового алгоритма, где в качествеинформативных элементов используются несжимаемые наборыпризнаков – тупиковые тесты, в алгоритмах типа КОРА в качествеинформативных элементов используются несжимаемые фрагментыописаний эталонных объектов обучающей выборки.Определение3. Пусть (xv1 , . . . , xvn ) - признаковое описание объектаTsv ∈ Set Kl . Набор (xvj1 , . . . , xvjr ) называется представительнымнабором для класса Kl при выполнении следующего условия. Пусть(xuj1 , . . .

, xujr ) произвольная строка таблицы TnmL , котораяTсоответствует объекту su , не принадлежащему Set Kl . Тогдасуществует такое j 0 ∈ {j1 , . . . , jr }, что xuj 0 6= xvj 0 .Сенько Олег Валентинович ()МОТП, лекция 28 / 24Представительные наборыОпределение 4. Представительный набор называется тупиковым,если никакое его собственное подмножество представительнымнабором не является.На этапе обучения для каждого из классов K1 , . . . , kL по таблицеTnmL ищется множество всевозможных тупиковых представительныхнаборов.

Пусть Vel - множество всевозможных представительныхнаборов для класса Kl .Предположим, что нам требуется распознать объект s∗ с описанием(x∗1 , . . . , x∗n ) . Пусть v = (xvj1 , . . . , xvjr ) - представительный наборомФункция B(s∗ , v) равна 1, при выполнении всех неравенств(x∗j1 = xvj1 , . . .

, x∗jr = xvjr ) и B(s∗ , v) равна 0 в противном случае.Оценка s∗ за класс Kl вычисляется по формулеΓ(s∗ , Kl ) =1 XB(s∗ , v)| Vel | ev∈VlСенько Олег Валентинович ()МОТП, лекция 29 / 24Представительные наборыДля нахождения тупиковых представительных наборов для класса Kl ,содержащихся в эталонном описании xv объекта sv формируютсяматрица сравнения ClvnmL со всеми описаниями других классовlvlvтаблицы TnmL . Пусть строка (clvf 1 , . . .

, cf n ) матрицы CnmLсоответствует сравнению xv с описанием xg объекта sg , неTlvпринадлежащему Kl Set . Элемент clvf 1 = 0, если xvj = xgj , и cf 1 = 1,если xvj 6= xgj . Таким образом матрица ClvnmL имеет размер(m − ml )n. Тупиковые покрытия матриц сравнения ClvnmL определяюттупиковые представительные наборы, являющиеся фрагментамиописания xv . Полное множество представительных наборов длякласса Kl является объединением множеств представительныхнаборов, найденных для описаний всех объектов обучающей выборкииз Kl , Таким образом задача поиска всех представительных наборовсводится к решению ml задач поиска тупиковых покрытий для матрицсравнения размера (m − ml )n.Сенько Олег Валентинович ()МОТП, лекция 210 / 24Представительные наборыПервоначальные варианты тестового алгоритма и алгоритма типаКОРА были разработаны для бинарных или категориальныхпеременных.

Они не могут быть напрямую использованы в задачах спризнаками, принимающими значения из интервалов вещественнойоси. Для того, чтобы обеспечить возможность работы с подобнойинформацией могут быть использованы два подхода.Первый подход основан на разбиении области возможных значенийкаждого вещественнозначного признака на k связных подмножеств(интервалов, полуинтервалов, отрезков). Значению признака,принадлежащего j-ому элементу разбиения присваивается значение j.Разбиение оптимизируется с целью достижения максимальногоразделения классов.

Выбирается такое число элементов разбиения k,при котором достигается максимальная точность распознавания.Сенько Олег Валентинович ()МОТП, лекция 211 / 24Вещественнозначная информацияДругой подход основан на модификации понятий теста ипредставительного набора с использованием пороговых параметров(ε1 , . .

. , εn ), которые задаются для признаков X1 , . . . , Xn .Определение 5. Тестом таблицы TnmL называется совокупностьстолбцов i1 , . . . , ir таких, что после удаления из TnmL всех столбцов,за исключением столбцов i1 , . . . , ir в полученной таблице TrmL длявсех пар строк, соответствующих разным классам абсолютнаявеличина различий хотя бы по одному признаку Xj превышает εj .Сенько Олег Валентинович ()МОТП, лекция 212 / 24Вещественнозначная информацияАналогичным образом вводится модифицированное определениепредставительного набора.Определение6.

Пусть (xv1 , . . . , xvn )- признаковое описание объектаTsv ∈ Set Kl . Набор (xvj1 , . . . , xvjr ) называется представительнымнабором для класса Kl при выполнении следующего условия. Пусть(xuj1 , . . . , xujr ) произвольная строка таблицы TnmL соответствующаяTобъекту su , не принадлежащему Set Kl . Тогда существует такоеj 0 ∈ {j1 , .