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

Наряду с полнымилогическими закономерностями, удовлетворяющими последним условиям, используютсятакже частичные логические закономерности, для которых допускается попадание в нихнебольшойдолиобъектовчужихклассов.Методыпостроениялогическихзакономерностей подробно излагаются в работе [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 , Данная проекция по определению равна. Однако согласно|z|системе (2)z (x1t  xt2 ) 2.|z||z|удалённых друг от другаСледовательно задачапоискадвух максимальнопараллельных гиперплоскостей, каждая из которых отделяетобъекты одного из классов, может быть сведена к оптимизационной задаче сограничениями.2 max|z|(3)zxtj  b  1 при s j  St  K1zxtj  b  1 при s j  St  K 2 , j  1,,m.При этом оптимизация производится по компонентам направляющего вектораz  ( z1 ,, zn )и параметру сдвига b .Введём обозначение: j  1 при s j  St  K1 и2монотонно возрастает с уменьшением|z|s j  St  K 2 .

Учитывая, функцияnzi 12i, переходим от задачи (3) к задаче1 n 2 zi  min2 i 1(4) j (zxtj  b)  1 , j  1, , m .Задача(4)относитсяпрограммирования.кхорошоизученномуклассузадачквадратичногоРешениезадачиквадратичногопрограммирования.Важныминструментомисследования экстремальных значений оптимизируемых функций при ограниченияхявляется функция Лагранжа или лагранжиан, который для задачи (4) записывается в видеL(z, b, λ ) где(1 ,12nmi 1j 1 zi2    j [ j (zxtj  b)  1] ,, m ) являются неотрицательными вещественными, которые называютсямножителями Лагранжа.Из известной теоремы Каруша-Куна-Такера (ККТ) следует, что для точкикоторой функция1 n 2 zi2 i 1(z* , b* ) , вдостигает своего минимума при ограничениях задачи (4), инекоторого вектора значений неотрицательных множителей Лагранжа λ *  (1* ,, m* )соблюдаются условия стационарности лагранжиана L(z, b, λ ) по переменным ( z , b) .Также из теоремы ККТ следует необходимость выполнения m равенств, которые носятназвание условий дополняющей нежёсткости *j [ j (z*xtj  b)  1]  0 , j  1, , mУсловия стационарности заключаются в выполненииmL(z, b, λ ) zi*    *j  j x ji  0 , i  1,zij 1( z* ,b* , λ* )n равенств,n(5)В векторной форме система (5) принимает видmz    *j  j x j  0 .*j 1Из условия стационарности также следует выполнение равенстваmL(z, b, λ )   *j  j  0bj 1( z* ,b* ,λ* )(6)Условия стационарности (5,6) для лагранжиана L(z, b, λ ) являются необходимымиусловиями экстремума при ограничениях задачи (4).Поиск оптимальных значений множителей Лагранжа.