ММО2 (1185327), страница 4

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

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

Значению признака, принадлежащего элементу j разбиения присваиваетсясамо значение j .Разбиение оптимизируется с целью достижения максимальногоразделения классов. Выбирается такое число элементов разбиения k , при которомдостигается максимальная точность распознавания.Другой подход основан на модификации понятий теста и представительного набора сиспользованием пороговых параметровX1,которые задаются для признаков, Xn .Определение 5. Тестом таблицы{i1 ,1 , ,  n ,называется такая совокупность столбцовTnml, ir } , что для произвольной пары строк s*и s , соответствующих объектам изразных классов, существует такой столбец i из множества{i1 ,, ir } , что абсолютнаявеличина разницы значений, стоящихпревышает  i* .*на пересечении i состроками sиsАналогичным образом вводится модифицированное определение представительногонабора.Главным требованием при выборе- порогов является достижение максимальнойотделимости объектов разных классов при сохранении сходства внутри классов.Поиск тупиковых тестов и тупиковых представительных наборов при модифицированныхопределениях аналогичен их поиску в первоначальных вариантах методов.Тестовый алгоритм и алгоритм с представительными наборами являются частью болееобщей конструкции, основанной на принципе частичной прецедентности и носящейназвание алгоритмов вычисления оценок.Существует много вариантов моделей данного типа.

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

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

Оптимальное значение k находится в процессе обучения илизадаётся экспертом. Другой часто используемой системе опорных множествсоответствует множество всех подмножеств{1,, n} за исключением пустогомножества.Задание функции близости. Близость между объектами по опорноным множествамзадаётся аналогично тому, как задаётся близость между объектами по тупиковым тестамили представительным наборам.

Пусть набор номеров {i1 ,, ik } соответствуетхарактеристическому вектору ω .Фрагмент ( xi1 ,объектаs ., xik ) описания ( x1 , , x n ) объекта x  называетсяПод функцией близостиBω ( s , s )ω - частьюпонимается функция отсоответствующих ω -частей сравниваемых объектов, принимающая значения 1 (объектыблизки) или 0 (объекты удалены).Функции близости обычно задаются с помощью пороговых параметров (1 ,, n ) ,характеризующих близость объектов по отдельным признакам.Примеры функций близости.1) Bω ( s , s )  1 , если при произвольномi {1, , n}, при котором i  1 , всегдавыполняется неравенство | xi  x i |  i .

Bω ( s , s )  0 , если существует такоеi {1, , n} , что одновременно i  1 и | xi  x i |  i .2) Пусть- скалярный пороговый параметр. Функция Bω ( s , s )  1 , еслиnвыполняется неравенствоBω ( s , s )  0 . | xi 1ii x i |   . В противном случаеВажным элементом АВО является оценка близости распознаваемого объектак эталону ss* - части. Данная оценка близости, которая будетпо заданнойобозначаться G (ω, s* , s ) , формируется на основе введённых ранее функций близости и,возможно,дополнительныхпараметров.различного уровня сложности:A) G (ω, s* , s )  Bω ( s* , s ) ,ПриведёмпримерыфункцийблизостиG (ω, s* , s )  p ω Bω ( s* , s ) ,B)гдепараметр,pω -характеризующийинформативность опорного множества с характеристическим вектором ω .nС)G(ω, s* , s )    ( pii )Bω ( s* , s ) , где   - параметр, характеризующийi 1информативность эталона s , параметры p1 ,, pn характеризуют информативностьотдельных признаков.Оценка объектаs*за классK l при фиксированном характеристическом векторе ωможет вычисляться как среднее значение близости s* к эталонным объектам из классаK l : l (ω, s* ) класса1ml G(ω, s , s ) , где ms K l*- число объектов обучающей выборки изlKl .Общая оценкаs* за класс K l вычисляется как сумма оценок l (ω, s* ) по опорныммножествам из системы  A :Γˆ l ( s* )   (ω, s )ω Al(1)*Наряду с формулой (1) используется формулаΓˆ l ( s* )  wl  (ω, s )ω AИспользование взвешивающих параметров w1 ,правильно распознанных объектовl(2)*, wL позволяет регулировать долиK1 , , K L .Прямое вычисление оценок за классы по формулам (1) и (2) в случаях, когда в качествесистем опорных множеств используются наборы с фиксированным числом признаков иливсевозможные наборы признаков, оказывается практически невозможным при сколь либовысокой размерности признакового пространства из-за необходимости вычисленияогромного числа значений функций близости.Однако при равенстве весов всех признаков существуют эффективные формулы длявычисления оценок по формуле (1).

Предположим, что оценки близости распознаваемогообъектаs*к эталону sпо заданнойТогда оценка по формуле (1) принимает видω - части вычисляются по формуле (A).Γˆ l ( s* )  Bs Kl ω Aω( s* , s )BРассмотрим суммуω Aкоторым объектs*ω(s* ,s ). Предположим, что общее число признаков, поблизок объекту sравноd ( s* , s ) . Иными словамиd ( s* , s ) | D( s* , s ) | , где D( s* , s )  {i :| x*i  xi |  i } .

Очевидно функция близостиBω ( s* , s ) равна 1 тогда и только тогда, когда опорное множество,задаваемоехарактеристическим вектором ω , полностью входит в множество D( s* , s ) . Во всехостальных случаях Bω ( s* , s )  0 .Предположим,A  {ω :| ω | k} .условиюBω AωчтосистемаопорныхмножествудовлетворяетусловиюОчевидно, что число опорных множеств, удовлетворяющихBω ( s* , s )  1 ,Ckd ( s* ,s ) .равноОткудаследует,что( s* , s )  C kd ( s* ,s ) . Следовательно оценка по формуле (1) может быть записана ввиде1Γˆ l ( s* ) mlПредположим, что система  Cs K lAkd ( s* , s ).(3)включает в себявсевозможные опорныемножества.

В этом случае число опорных множеств в  A , удовлетворяющих условиюBω ( s* , s )  1 равно2d ( s* , s )-1 . Следовательно оценка по формуле (1) может бытьзаписана в виде1Γˆ l ( s* ) ml   [2d ( s* , s )-1]s K lОбучение алгоритмов вычисления оценок. Для обучения алгоритмов АВО в общемслучае может быть использован тот же самый подход, который используется для обученияв методе «Линейная машина». Предположим, что решается задача обучения алгоритмовдля распознавания объектов , принадлежащих классамраспознавания объекта s j  KlK1 ,, K L .

При правильногодолжна выполняться система неравенствΓl ( sl )  Γl ( s j ), где l  {1,, L} \ l .В наиболее общем из приведённых выше вариантов модели АВО обучение может бытьсведено к поиску максимальной совместной подсистемы системы неравенств s j  K l  St1mlS Kln  ( ptt )ω ( s j , s ) t 1(4)n1(ptt )ω ( s j , s ) ml S Kl t 1Поиск максимальной совместной подсистемы системы (2) может производиться сиспользованием эвристического релаксационного метода, аналогичного тому, что былиспользован при обучении алгоритма «Линейная машина».Тестовый алгоритм был впервые предложен в работе [], гдегеологического прогнозирования.для решении задачи.

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

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