ММО и поиск достоверных закономерностей в данных. Учебное пособие. Сенько (1185323), страница 9

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

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

Причём конкретный вид моделиопределяется выбранными способами задания различных её элементов.Рассмотримосновные составляющие моделиЗадание системы опорных множеств. Под опорными множествами модели АВОпонимается наборы признаков, по которым осуществляется сравнение распознаваемых иэталонных объектов. Примером системы опорных множеств является множествотупиковых тестов. Система опорных множествAможет задаваться через систему подмножеств множестванекоторого алгоритма1,,nAили черезсистему характеристических бинарных векторов.Каждому подмножествуразмерности n . Пустьω  {1 ,, n } ,i , , i .1k{1,{i1 ,, n}, ik }  {1,может быть сопоставлен, n} .

Тогда {i1 ,бинарный вектор, ik } сопоставляется векторвсе компоненты которого равны 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обозначатьсявозможно, - части. Данная оценка близости, которая будетпо заданнойG (ω, s* , s ) , формируется на основе введённых ранее функций близости и,дополнительныхпараметров.различного уровня сложности:A)s*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 при фиксированном характеристическом векторе ωможет вычисляться как среднее значение близостиK l : l (ω, s* ) класса1ml G(ω, s , s ) , где ms K l*s* к эталонным объектам из класса- число объектов обучающей выборки изlKl .Общая оценкаs* за класс K l вычисляется как сумма оценок l (ω, s* ) по опорныммножествам из системыA :Γˆ l ( s* )   (ω, s )ω Al(1)*Наряду с формулой (1) используется формулаΓˆ l ( s* )  wl  (ω, s )ω AИспользование взвешивающих параметровправильно распознанных объектовl(2)*w1 , , 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 )2d ( s* , s )(3)включает в себямножества. В этом случае число опорных множеств вBω ( s* , s )  1 равно.всевозможные опорные A , удовлетворяющих условию-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) может производиться сиспользованием эвристического релаксационного метода, аналогичного тому, что былиспользован при обучении алгоритма «Линейная машина».Тестовый алгоритм был впервые предложен в работе [], гдегеологического прогнозирования.для решении задачи4.5Методы,основанныенаголосованиипосистемамлогических закономерностейОдним из эффективных подходов к решению задач прогнозирования и распознаванияявляется использование коллективных решений по системам закономерностей.закономерностьюпонимаетсяраспознающийилипрогностическийПодалгоритм,определённый на некоторой подобласти признакового пространства или связанный снекоторым подмножеством признаков.В качестве примера закономерностей могут быть приведены представительные наборы,являющиеся по сути подмножествами признаковых описаний, характерных для одного израспознаваемыхклассов.Аналогомпредставительныйнабороввзадачсвещественнозначной информацией являются логические закономерности классов.

Подлогической закономерностью класса K l понимается область признакового пространства,имеющая форму гиперпараллелепипедаи содержащая только объекты из K l ..Рис. На рисунке представлена логическая закономерность, содержащая объекты классаK1 , обозначенные синим кружком, и не содержащая объектов обозначенных по другомуклассов K 2 и K 3Математически логическая закономерность класса K l , которую мы будем обозначатьr (l ) , описывается с помощью наборов предикатов видаPi [r (l )]  " air (l )  xi  bir (l ) " ,где i  1,(1),n .Напомним, что предикатом называется утверждение, принимающее значения «ИСТИНА»или «ЛОЖЬ» в зависимости от значений входящих в них переменных.

Полностьюлогическая закономерность задаётся конъюнкцией предикатов вида (1):P[r (l )]  P1[r (l )] &Очевидно, что множество векторов ( x1 ,& Pn [ r (l )](2), xn ) , для которых, как раз представляет собойгиперпараллелепипед в многомерном пространстве признаков. Не все признаки являютсяна самом деле существенными для закономерности r (l ) . Для несущественного признакаxi отрезок [air (l ) , bir (l ) ] совпадает с отрезком, из которого принимает значения признакxi .На этапе обучениязакономерностейдля каждого классаRl .r (l )Границы ( aiK l строитсямножество логических, bir (l ) ) подбираются таким образом, чтобыравенство P[ r (l )]  «ИСТИНА» выполнялось бы на максимально большом числеобъектов обучающей выборки из классаKlиравенство P[ r (l )]  «ЛОЖЬ»выполнялось бы на всех объектах обучающей выборки из класса K l .

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

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