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

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

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

4.6 Метод мультимодельных статистически взвешенных синдромов

Метод мультимодельных статистически взвешенных синдромов является методом распознавания, основанном на принятии коллективных решений по системам синдромов. Под "синдромом" понимается такая область признакового пространства, в которой содержание объектов одного из классов, отличается от содержания объектов этого класса в обучающей выборке или по крайней мере в одной из соседних областях. Синдромы ищутся для каждого из распознаваемых классов с помощью построения оптимальных разбиений интервалов допустимых значений единичных признаков или совместных двумерных областей допустимых значений пар признаков. Пример синдромов, характеризующих разделение двух классов , приведён на рисунке 2

Рис. 2 Внутри синдромов I (верхний слева) и II ( верхний справа) преобладают объекты класса , обозначенного . Внутри синдрома IV преобладают объекты класса . обозначенные +.

Поиск синдромов производится с использованием четырёх семейств разбиений, имеющих различный уровень сложности. Примеры разбиений для каждого из семейств приведены на рисунке 3. Семейство I включает всевозможные разбиения интервалов допустимых значений отдельных признаков на два интервала с помощью одной граничной точки. Семейство II включает всевозможные разбиения интервалов допустимых значений отдельных признаков на 3 интервала с помощью двух граничных точек. Семейство III включает всевозможные разбиения совместных

двумерных областей допустимых значений пар признаков на 4 подобласти с помощью двух граничных точек ( по одной точке для каждого из двух признаков).

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

Рис 3. Примеры разбиений для каждого из четырёх семейств, используемых в методе СВС.

В ходе поиска выбирается разбиение с максимальным значением функционала качества. В различных вариантах метода используется два функционала качества, зависящих от обучающей выборки , распознаваемого класса , и разбиения :

- интегральный ;

- локальный .

Обозначим через элементы некоторого разбиения . Пусть является долей объектов класса в обучающей выборке . - доля объектов среди объектов, описания которых принадлежат элементу , - число объектов, описания которых принадлежат . Интегральный функционал задаётся формулой . В то время как локальный функционал задаётся формулой

Метод СВС, впервые предложенный в работе [13] был основан на использовании одномерных семейств разбиений. Позже была предложена модификация СВС –метод мультимодельные статистически взвешенных синдромов (МСВС) [25]. В методе МСВС наряду с одномерными семействами I и II используются также семейства III и IV. Синдромы, задаваемые некоторым оптимальным разбиением включаются в финальный набор, используемый в дальнейшем для распознавания новых объектов, если удовлетворяет специальному критерию. В методе СВС для поиска синдромов используется интегральный функционал . Для формирования финального набора используется простой критерий: все элементы оптимального разбиения включаются в набор, если величина интегрального функционала превышает задаваемый пользователем порог . Опыт решения прикладных задач показывает, что эффективность распознавания достигается при значениях , меняющихся от 2 до 10. Несколько более сложный критерий используется в методе МСВС. Для поиска синдромов используется локальный функционал . Синдромы оптимального разбиения _{включаются в} финальный набор в случае выполнения неравенства , где величина параметра зависит от сложности используемой модели. Экперименты на прикладных задачах показали, что высокая эффективность достигается при для простейших разбиений из семейства I и для разбиений из семейства II-IV.

_{Предположим, что на этапе обучения для класса} найдено множество синдромов . Пусть описание распознаваемого объекта принадлежит синдромам _{из множества . Оценка за класс вычисляется по формуле}

_,

где - доля объектов класса в синдроме , - вес синдрома при классификации объектов класса , который вычисляется по формуле , где - число объектов обучающей выборки, попавших в синдром . Данная формула была получена в работе [] через максимизацию специального функционала, сходного с функционалом правдоподобия.

4.7 Метод опорных векторов.

4.7.1 Линейная разделимость.

Принцип максимизации зазора. Метод опорных векторов является универсальным методом распознавания, позволяющим наряду с линейными реализовывать также нелинейные решающие правила. Исходный вариант метода был предложен для задач с двумя распознаваемыми классами и . В случаях, когда объекты разных классов в обучающей выборке линейно разделимы, обычно существует целая совокупность линейных поверхностей, осуществляющих такое разделение. На рисунке 1 представлены двумерные данные, где объекты двух классов могут быть раделены с помощью прямых A, B, C, D. Однако наша интуиция, подсказывает что наилучшей обобщающей способностью должна обладать разделяющая прямая F, одинаково удалённая от групп объектов из разных классов. Однако наша интуиция, подсказывает что наилучшей обобщающее

й способностью должна обладать разделяющая прямая F, одинаково удалённая от групп объектов из разных классов.

Рис. 1 Иллюстрируются различные варианты разделения классов и .с помощью линейных границ.

Интуитивные представления об оптимальной разделимости формализует проведение разделяющей гиперплоскости посередине между двумя параллельными гиперплоскостями, каждая из которых отделяет объекты одного из классов. При этом две плоскости строятся таким образом, чтобы «зазор» между ними был бы максимальным.

Интуи Рис. 1 Иллюстрируются разделение классов и .с помощью линейных границ с испо льзованием концепции максимального «зазора».

Напомним, что пара параллельных гиперплоскостей и в многомерном пространстве описывается с помощью уравнений:

( ) , (1)

( ) ,

где является направляющим вектором для гиперплоскостей.

Пусть , где - некоторое вещественное число. Нетрудно таким образом подобрать и , чтобы система

( ) , (2)

( ) ,

Описывала те же самые гиперплоскости, что и система (1). Пусть точки и принадлежат плоскостям и соответственно. Расстояние (величина зазора) между гиперплоскостями и равно проекции разности на направление , Данная проекция по определению равна . Однако согласно системе (2) . Следовательно задача поиска двух максимально удалённых друг от друга параллельных гиперплоскостей, каждая из которых отделяет объекты одного из классов, может быть сведена к оптимизационной задаче с ограничениями.

(3)

при

при , .

При этом оптимизация производится по компонентам направляющего вектора и параметру сдвига .

Введём обозначение: при и . Учитывая, функция монотонно возрастает с уменьшением , переходим от задачи (3) к задаче

(4)

, .

Задача (4) относится к хорошо изученному классу задач квадратичного программирования.

Решение задачи квадратичного программирования. Важным инструментом исследования экстремальных значений оптимизируемых функций при ограничениях является функция Лагранжа или лагранжиан, который для задачи (4) записывается в виде

,

где являются неотрицательными вещественными, которые называются множителями Лагранжа.

Из известной теоремы Каруша-Куна-Такера (ККТ) следует, что для точки , в которой функция достигает своего минимума при ограничениях задачи (4), и некоторого вектора значений неотрицательных множителей Лагранжа соблюдаются условия стационарности лагранжиана по переменным .

Также из теоремы ККТ следует необходимость выполнения равенств, которые носят название условий дополняющей нежёсткости

,

Условия стационарности заключаются в выполнении равенств

, (5)

В векторной форме система (5) принимает вид

.

Из условия стационарности также следует выполнение равенства

(6)

Условия стационарности (5,6) для лагранжиана являются необходимыми условиями экстремума при ограничениях задачи (4).

Поиск оптимальных значений множителей Лагранжа. Предположим, что является некоторой точкой, в которой соблюдаются условия стационарности и соблюдаются ограничения задачи (4).

Нетрудно показать, воспользовавшись уравнениями (5,6), что лагранжиан в точке может быть записан в виде .

Отметим, что в силу соблюдения ограничений задачи (4) и неотрицательности множителей Лагранжа в точке выполняется неравенство

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

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