_учебник_ Журавлев Ю.И. Распознавание. Математические методы. Программная система. Практические применения (2005) (_учебник_ Журавлев Ю.И. Распознавание. Математические методы. Программная система. Практические применения (2005).pdf), страница 15

Последняя задачасводится к решению аналогичной задачи относительно вещественных переменных,которая решается с помощью релаксационного метода /24, 46/. В конечном итоге задачапоиска оптимального предикатаP (S )для опорного эталонаSiзаканчиваетсявычислением множества локально оптимальных предикатов P (S ) со свойством P( S i )  1 ,причем конъюнкции (3.2) являются несократимыми (из них нельзя удалить какой-либосомножитель).Далее все вычисления повторяются для kслучайно выбранных «опорных»эталонов класса K j , а все найденные логические закономерности объединяются в одномножество Pj . Значение параметра k определяется из соотношения(1  h ) k  (1  g ) ,(3.3)где g – параметр «уровень значимости» (0<g<1).Результат работы алгоритма поиска логических закономерностей класса K jформулируетсяследующимзакономерностейобразом:«ВвычисленноммножествелогическихPj ={ P (S ) } класса K j с вероятностью не менее g имеется логическаязакономерность P (S ) , для которой  (P )  h».

Естественно, данный результат может бытьполучен при условии самого существования P (S ) , для которого  (P )  h.Значение параметра k является важным фактором быстродействия программы.Например, при g=0.9 и h=0.1 из (3.3) следует k22. Значение k=22 вполне приемлемо длязадач большой размерности.ПРИМЕЧАНИЕ. Предположение  (P )  h служит лишь для автоматической оценки ивыбора параметра k.

При работе программы здесь возможны три результата:Pj ={ P (S ) } содержитвычисленное множествоPj ={ P (S ) } не содержит P (S ) , для которого  (P )  h,множествоP (S ) , для которого (P )  h,вычисленное множествоPj ={ P (S ) } оказывается пусто.

Последний вариант соответствуетситуации, когда логических закономерностей нет ни для одного из выбранных опорныхобъектов. В данном случае следует выбрать большее число интервалов (более мелкуюсетку) и повторить запуск программы, или искать частичные закономерности.Найденные логические закономерности класса K j могут быть «статистическизначимыми» или нет. Для этого используется «перестановочный тест».

Выполняется72серия из следующих t однотипных расчетов (t – параметр «количество случайныхперестановок»). Осуществляется случайная перестановка строк таблицы обучения, при~этом, как и ранее, первые m1 строк новой таблицы Tnml считаются эталонами первогокласса, следующие по порядку (m2  m1 ) строк - эталонами второго класса, и т.д. (т.е.проводится случайное изменение номеров классов эталонных объектов с сохранением~общего числа эталонов класса).

Для таблиц Tnml находятся наилучшие закономерностиPi , i  1,2,..., t ,с соответствующими оценкамикачества ( Pi ) . Тогда логическаязакономерность Pq из множества Pj ={ P (S ) } считается статистически значимой, если изнеравенств  ( Pq )   ( Pi ) , i=1,2,…,t, выполнено не менее чем 100*g% .При обработке неполных данных возможно использование двух методов обработкипрочерков (неизвестных значений признаков): «жадный подход» и «осторожный подход».При жадном подходе считается, что все пары значений признаков сравниваемых объектов,одно или оба из которых неизвестны, близки (если объекты одного класса) и далеки (еслиобъекты из разных классов), в то время как при осторожном, соответственно, – далеки иблизки. Такой «прямой» способ позволяет автоматически обрабатывать пропущенныезначения и получать хорошие решения, не прибегая к дополнительной обработке ипреобразованиям прочерков.Найденные множества логических закономерностей используются для вычисленияинформационных весов признаков и синтеза логических описаний классов.Информационным весом признака считается величина pi  N i / N , где N i - общеечисло логических закономерностей, в которые входит признак xi , N – общее числологических закономерностей.Оценки распознаваемых объектов за классы вычисляются следующим образом.Пусть Pi ( S )  & (av  xv ( S )  bv ),   {1,2,..., n} - логическая закономерность класса K j .

Считается, что логическая закономерность выполняется на объекте S  и объектполучает«голос»заклассKj ,еслипредикатPi ( S )  & (min(av , xv ( S ' ))  xv ( S )  max( av , xv ( S ' ))) удовлетворяет условию 2) (условию 2  при работе с частичными закономерностями). Оценка S  за класс K j вычисляется каксумма числа голосов по всем закономерностям данного класса, деленная на общее числозакономерностей класса. Классификация объекта проводится с помощью простейшегорешающего правила.73Множества логических закономерностей задают логические описания классов K j ,в качестве которых рассматриваются функции D j ( S )   Pi ( S ) , где дизъюнкции берутсяпо множествам Pj ={ P (S ) }.

Данные функции принимают значение 1 только на эталонах«своего» класса и 0 на всех эталонах «чужих» классов. Они могут рассматриваться какприближения характеристических функций классов K j .Кратчайшим логическим описанием класса Kj назовем логическую суммуD sj ( S )   Pt ( S ) , суммирование в которой проводится по подмножеству множестваPj ,содержащему минимальное число конъюнкций Pt(S), и совпадающей с функцией Dj(S) наэталонных объектах.Минимальным логическим описанием класса Kj назовем логическую суммуD mj ( S )   Pt ( S ) , суммирование в которой проводится по подмножеству множестваP j , содержащую минимальное общее число символов x1(S),x2(S),...,xn(S) в своей записи, исовпадающей с функцией Dj(S) на эталонных объектах.Логические (кратчайшие, минимальные) описания классов являются аналогамипредставлений частичных булевых функций в виде сокращенных дизъюнктивныхнормальных форм (кратчайших, минимальных), а геометрические образы логическихзакономерностей классов - аналогами максимальных интервалов /25, 59/.Если найдено множество P j логических закономерностей класса Kj, то кратчайшееи минимальное логические описания класса находятся как решения задач поискапокрытий множества эталонов класса соответствующими предикатам Pt(S)гиперпараллелепипедами.Пусть P j ={ P1(S), P2(S),…, PN(S) }, причем для каждого эталона класса Kjсуществует хотя бы один предикат из P j , выполняющийся на данном эталоне.Рассмотрим задачу:Na yt 1Nt  min,t P (S ) yt 1tit(3.4) 1,  i : Si  K j , yt  {0,1}.(3.5)Тогда, при at =1 единичные компоненты решения задачи (3.4-3.5) определяютпредикаты кратчайшего логического описания D sj (S ) класса Kj , а при at , равных числупеременных в Pt(S), - предикаты минимального логического описания.Исходные множества P j могут содержать равные или близкие элементы, мощностьP j может быть весьма велика (что однако является благоприятным в процедурахраспознавания).

Данные свойства множеств P j существенно зависят от длины обучающейвыборки и самого алгоритма их поиска. В то же время, кратчайшие и минимальныелогическиеописанияклассовобразуютуженеизбыточныеподмножестваPj ,выражающие как основные свойства данных множеств, так и свойства самих классов.74Поэтому вычисление D sj (S ) и D mj (S ) может рассматриваться как один из подходов кпроблеме сортировки логических закономерностей классов, а входящие в D sj (S ) и D mj (S )предикаты - как наиболее компактные представления о классах, включающие какнаиболее представительные знания (предикаты, покрывающие большое число эталонов),так и уникальные или редкие (предикаты, покрывающие малое число эталонов илиотдельные из них).Рис.

20. Визуализация множества P jРис. 21. Визуализация множествалогических закономерностей класса Kj(«белый кружок»)логических закономерностей кратчайшегоописания класса Kj3.4. Метод статистически взвешенных синдромовМетод статистически взвешенных синдромов (СВС) основан на использованиипроцедуры взвешенного голосования по системам так называемых “синдромов” /37, 70,78/. Под синдромом мы в данном случае понимаем подобласть пространствапрогностическихпризнаковпринадлежащуюразбиениюэтогопространства,обладающему разделяющей способностью.

Мы будем говорить, что разбиениепризнакового пространства обладает разделяющей способностью, еслисодержания объектов одного из классовдолевыев различных его областях значительноотличаются друг от друга. В методе СВС используются только одномерные и двумерныесиндромы. Пододномерным синдромом, задаваемым признаком X i , мы понимаемподобласть признакового пространства, для точек которой признак X i удовлетворяетнеравенствам bi  X i  bi , где bi , bi вещественные граничные точки. Соответственнопод двумерным синдромом, задаваемым признаками X i и X i , понимаетсявекторовпризнаковогопространства,длякоторойпризнакX iподобластьудовлетворяетнеравенствам bi  X i  bi , а признак X i удовлетворяет неравенствам bi  X i  bi .75Одномерные синдромы в методе СВС ищутся для каждого из классов по исходнойобучающейвыборкеспомощьюстабильныходномерныхразбиенийобластейдопустимых значений каждого из признаков.

Соответствующие двумерные синдромызадаются как всевозможные пересечения одномерных синдромов.Рис.22. Пример двумерных синдромов. Символами «крестик» отмечены объекты класса, для котороговычисляются синдромы, символами «нолик» - объекты остальных классов. Видно, что доля крестиков всиндроме II значительно превышает долю крестиков в синдромах I , II и III. В то время какдоля«крестиков» в синдроме III значительно ниже доли «крестиков» в синдромах I , II и IV. Синдромы I , II III иIV являются множеством всевозможных пересечений пары одномерных синдромов (I  II) и (III  IV),которые строятся по признаку x1 и пары одномерных синдромов (I  III) и (II  IV), которые строятся попризнаку x2Для построения одномерных синдромов используются модели I и II, различногоуровня сложности. При этом модель I включает в себя все разбиения области допустимыхзначений признака с помощью одной граничной точки на две подобласти, а модель IIвключает в себя все разбиения области допустимых значений признака с помощью двухграничных точек на три подобласти.