ММО3 (2015 Учебное пособие ММО (Сенько))

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 . Наряду с полнымилогическими закономерностями, удовлетворяющими последним условиям, используютсятакже частичные логические закономерности, для которых допускается попадание в нихнебольшойдолиобъектовчужихклассов.Методыпостроениялогическихзакономерностей подробно излагаются в работе [11], а также книге [9].*Предположим, что нам требуется распознать новый объект s .

Для каждого классаK l ищется число закономерностей в Rl , для которых P[r (l )]  «ИСТИНА». Вкачестве оценки за классK l используется доля таких закономерностей в*Rl .Классификация s производится с помощью стандартного решающего правила. То естьобъект относится в тот класс, оценка за который максимальна.4.6МетодмультимодельныхстатистическивзвешенныхсиндромовМетод мультимодельных статистически взвешенных синдромов является методомраспознавания, основанном на принятии коллективных решений по системам синдромов.Под "синдромом" понимается такая область признакового пространства, в которой содержаниеобъектов одного из классов, отличается от содержания объектов этого класса вобучающейвыборке или по крайней мере в одной из соседних областях. Синдромы ищутся для каждого израспознаваемыхклассовспомощьюпостроенияоптимальныхразбиенийинтерваловдопустимых значений единичных признаков или совместных двумерных областей допустимыхзначений пар признаков.Пример синдромов, характеризующих разделение двух классов ,приведён на рисунке 2Рис.

2 Внутри синдромов I (верхний слева) и II ( верхний справа) преобладают объекты классаобозначенного. Внутри синдрома IV преобладают объекты классаПоиск синдромов производится с использованиемK2 .четырёхобозначенныеK1,+.семейств разбиений,имеющих различный уровень сложности. Примеры разбиений для каждого из семействприведены на рисунке 3. Семейство I включает всевозможные разбиения интерваловдопустимых значений отдельных признаков на два интервала с помощью однойграничной точки.

СемействоII включает всевозможные разбиения интерваловдопустимых значений отдельных признаков на 3 интервала с помощью двух граничныхточек. Семейство III включает всевозможные разбиения совместныхдвумерных областей допустимых значений пар признаков на 4 подобласти с помощьюдвух граничных точек ( по одной точке для каждого из двух признаков).СемействоIV включает всевозможные разбиения совместных двумерных областейдопустимых значений пар признаков на 2 подобласти с помощью прямой граничнойлинии, произвольно ориентированной относительно координатных осей .Рис 3.

Примеры разбиений для каждого из четырёх семейств, используемых в методе СВС.В ходе поиска выбирается разбиение с максимальным значением функционала качества.В различных вариантах метода используется два функционала качества, зависящих отобучающей выборки St , распознаваемого класса K l , и разбиения R :- интегральный Fi ( St , Kl , R) ;- локальный Floc ( St , K l , R ) .q1 ,, qr элементы некоторого разбиения R . Пусть  0l являетсядолей объектов классаK l в обучающей выборке St .  il - доля объектов K l средиОбозначим черезобъектов, описания которых принадлежат элементу qi , mi - число объектов, описаниякоторыхпринадлежатqi .ИнтегральныйфункционалзадаётсяформулойFi ( St , Kl , R) r1( il  0l ) 2 mi .

В то время как локальный функционалll  0 (1  0 ) i 1( il   0l ) 2 miзадаётся формулой Floc ( St , K l , R )  maxlli 1, ,r  0 (1   0 )Метод СВС, впервые предложенный в работе [13] был основан на использованииодномерных семейств разбиений. Позже была предложена модификация СВС –методмультимодельные статистически взвешенных синдромов (МСВС) [25].

В методе МСВСнаряду с одномерными семействами I и II используются также семейства III и IV.Синдромы, задаваемые некоторым оптимальным разбиениемR* включаются вфинальный набор, используемый в дальнейшем для распознавания новых объектов, еслиR*удовлетворяет специальному критерию.В методе СВС для поиска синдромовиспользуется интегральный функционал Fi ( St , Kl , R) . Для формирования финальногонабора используется простой критерий: все элементывключаются в набор, еслиоптимального разбиения RFi ( St , Kl , R* )величина интегрального функционалапревышает задаваемый пользователем порог* . Опыт решения прикладных задачпоказывает, что эффективность распознавания достигается при значениях,меняющихся от 2 до 10.

Несколько более сложный критерий используется в методеМСВС. Для поиска синдромов используется локальный функционалСиндромы оптимального разбиения R*Floc ( St , K l , R) .включаются в финальный набор в случаевыполнения неравенства  Floc ( St , K l , R )   , где величина параметразависит отсложности используемой модели. Экперименты на прикладных задачах показали, чтовысокая эффективность достигается при   1 для простейших разбиений из семейства Iи   0.5 для разбиений из семейства II-IV.Предположим, что на этапе обучения для классасиндромовПусть описание xQl .синдромам q1 ,*K l найдено множествораспознаваемого объекта s*принадлежит, qr из множества Ql . Оценка s* за класс K l вычисляется по формулеr( s* , K l )  wi 1rl li iwi 1li,где  il - доля объектов класса K l в синдроме qi , wil - вес синдрома при классификацииобъектов класса1, где mi K l , который вычисляется по формуле wil  mmi i 1 ll (1   )00число объектов обучающей выборки, попавших в синдром qi .

Данная формула былаполучена в работе [] через максимизацию специального функционала, сходного сфункционалом правдоподобия.4.7 Метод опорных векторов.4.7.1 Линейная разделимость.Принцип максимизации зазора. Метод опорных векторовявляется универсальнымметодом распознавания, позволяющим наряду с линейными реализовывать такженелинейные решающие правила. Исходный вариант метода был предложен для задач сдвумя распознаваемыми классами K1 и K 2 .В случаях, когда объекты разных классов вобучающей выборке линейно разделимы, обычно существуетцелаясовокупностьлинейных поверхностей, осуществляющих такое разделение. На рисунке 1 представленыдвумерные данные, где объекты двух классов могут быть раделены с помощью прямыхA, B, C, D.

Однако нашаинтуиция, подсказывает что наилучшей обобщающейспособностью должна обладать разделяющая прямая F, одинаково удалённая от группобъектов из разных классов. Однако нашаинтуиция, подсказывает что наилучшейобобщающеей способностью должна обладать разделяющая прямая F, одинаково удалённая от группобъектов из разных классов.Рис. 1 Иллюстрируются различные варианты разделения классов K1 и K 2 .с помощьюлинейных границ.Интуитивные представления об оптимальной разделимости формализует проведениеразделяющей гиперплоскости посередине между двумя параллельнымигиперплоскостями, каждая из которых отделяет объекты одного из классов.

При этом двеплоскости строятся таким образом, чтобы «зазор» между ними был бы максимальным.ИнтуиРис. 1 Иллюстрируются разделение классов K1 и K 2 .с помощью линейных границ сиспо льзованием концепции максимального «зазора».Напомним, что пара параллельных гиперплоскостей P1пространствегдеRnописывается си P2 в многомерномпомощью уравнений:( P1 )wxt  b1 ,( P2 )wxt  b2 ,(1)w является направляющим вектором для гиперплоскостей.Пусть z   w , гдеподобрать - некоторое вещественное число.

Нетрудно таким образом и b , чтобы система( P1 )zxt  b  1,(2)zxt  b  1 ,( P2 )Описывала те же самые гиперплоскости, что и система (1). Пусть точки x1 и x 2принадлежат плоскостям P1 и P2 соответственно.между гиперплоскостямиP1и P2Расстояние (величина зазора)равно проекции разности ( x1  x 2 )наz ( x1t  xt2 )направление z , Данная проекция по определению равна.