Задача построения решающего правила Лекция 4,5

Статистический подход к задаче распознавания. Генеральная совокупность изучаемых объектов Г. Генеральная совокупность изучаемых объектов Г. Данное множество объектов (явлений, ситуаций) разбито на ряд подмножеств (классов, образов) Г 1,…,Г,…,Г k, где k – число образов, k>1; Данное множество объектов (явлений, ситуаций) разбито на ряд подмножеств (классов, образов) Г 1,…,Г,…,Г k, где k – число образов, k>1; каждый объект из Г описывается набором характеристик Х={X 1,…,X j,…,X n }; каждый объект из Г описывается набором характеристик Х={X 1,…,X j,…,X n }; j – множество возможных значений признака X j, j – множество возможных значений признака X j, = 1 х…х j х… n задает многомерное пространство переменных; = 1 х…х j х… n задает многомерное пространство переменных; Произвольному объекту а Г может быть поставлен в соответствие вектор Х(а)=( X 1 (a),…,X j (a),…,X n (a)), Х(а) будем обозначать через х, X j (a) – через x j ; Произвольному объекту а Г может быть поставлен в соответствие вектор Х(а)=( X 1 (a),…,X j (a),…,X n (a)), Х(а) будем обозначать через х, X j (a) – через x j ; Номинальная переменная Y c множеством значений Y ={1, 2, …,, …, k} соответствует имени класса. Номинальная переменная Y c множеством значений Y ={1, 2, …,, …, k} соответствует имени класса.

Основные обозначения и определения Задача распознавания образов состоит в том, чтобы для произвольного а Г по значениям x 1,…,x j,…x n предсказать y. Задача распознавания образов состоит в том, чтобы для произвольного а Г по значениям x 1,…,x j,…x n предсказать y. Отображение d: Y назовем решающей функцией. Ей соответствует разбиение множества на k непересекающихся подмножеств 1,…,,… k покрывающих, где ={x | d(x)= }. Через D 0 обозначим множество всевозможных отображений Y. Отображение d: Y назовем решающей функцией. Ей соответствует разбиение множества на k непересекающихся подмножеств 1,…,,… k покрывающих, где ={x | d(x)= }. Через D 0 обозначим множество всевозможных отображений Y. Объект а из генеральной совокупности Г выбирается случайным образом. Поэтому величины X 1,…,X j,…,X N являются случайными величинами. Объект а из генеральной совокупности Г выбирается случайным образом. Поэтому величины X 1,…,X j,…,X N являются случайными величинами. Под стратегией природы понимается совместное распределение Р(у, х) случайной величины Y и n-мерной случайной величины Х=( X 1,…,X j,…,X N ), у Y, х. В дальнейшем стратегию природы будем обозначать через с. Под стратегией природы понимается совместное распределение Р(у, х) случайной величины Y и n-мерной случайной величины Х=( X 1,…,X j,…,X N ), у Y, х. В дальнейшем стратегию природы будем обозначать через с. P(y, x)=P(y)P(x|y)=P(x)P(y|x) P(y, x)=P(y)P(x|y)=P(x)P(y|x) P(s) – априорная вероятность образа s. P(s) – априорная вероятность образа s. P(x|y)=Ps(x) P(x|y)=Ps(x) P(y|x)=Px(s) P(y|x)=Px(s)

Вероятность ошибки для фиксированной стратегии природы с в случае использования решающего правила d обозначим P(d, c); Вероятность ошибки для фиксированной стратегии природы с в случае использования решающего правила d обозначим P(d, c); P(d, c)=P(1)*P 1 +…+P(s)*P s +…+P(k)*P k, где P s – вероятность ошибки s-го образа, т.е. вероятность того, что объект другого образа будет ошибочно распознан как объект s-го образа; P(d, c)=P(1)*P 1 +…+P(s)*P s +…+P(k)*P k, где P s – вероятность ошибки s-го образа, т.е. вероятность того, что объект другого образа будет ошибочно распознан как объект s-го образа; Оптимальной решающей функцией в случае произвольной стратегии природы с называется такая функция d 0, при которой выполняется соотношение: P(d0, c)= inf{P(d, c)| d D0}; Оптимальной решающей функцией в случае произвольной стратегии природы с называется такая функция d 0, при которой выполняется соотношение: P(d0, c)= inf{P(d, c)| d D0}; Байесовской решающей функцией в случае произвольной стратегии природы с называется такая функция d*, которая при эмпирическом факте Х(а)=х объект а относит к тому образу, при котором условная вероятность Px( )=P{Y(a)= |X(a)=x} максимальна, то есть Px( )=max {Px(s)| s=1..k}. Когда максимальное значение достигается на нескольких образах, объект а относится к любому из них.; Байесовской решающей функцией в случае произвольной стратегии природы с называется такая функция d*, которая при эмпирическом факте Х(а)=х объект а относит к тому образу, при котором условная вероятность Px( )=P{Y(a)= |X(a)=x} максимальна, то есть Px( )=max {Px(s)| s=1..k}. Когда максимальное значение достигается на нескольких образах, объект а относится к любому из них.; Оптимальной решающей функцией является Байесовская решающая функция d* Оптимальной решающей функцией является Байесовская решающая функция d* Байесовская решающая функция

Оптимальной решающей функцией является Байесовская решающая функция d* d*: =argmax {PsPs(x)| s=1..k} d*: =argmax {PsPs(x)| s=1..k} НО: НО: Стратегия природы с, определяющая значения Ps и Ps(x)(s=1..k) на практике неизвестна Стратегия природы с, определяющая значения Ps и Ps(x)(s=1..k) на практике неизвестна Дана обучающая выборка А, представленная таблицей {x i (a j ),y(a j )|i=1,..,N, j=1,..,M} Дана обучающая выборка А, представленная таблицей {x i (a j ),y(a j )|i=1,..,N, j=1,..,M} Требуется получить эмпирические оценки s и s (x) по выборке Требуется получить эмпирические оценки s и s (x) по выборке При подстановке эмпирических оценок Байесов классификатор перестает быть оптимальным При подстановке эмпирических оценок Байесов классификатор перестает быть оптимальным

Существующие подходы к решению задачи распознавания Статистические Статистические параметрические параметрические оценка параметров распределений; оценка параметров распределений; непараметрические непараметрические метод парзеновского окна; метод парзеновского окна; метод парзеновского окна метод парзеновского окна Эвристические Эвристические сходство сходство метод ближайших соседей; метод ближайших соседей; метод ближайших соседей метод ближайших соседей метод потенциальных функций; метод потенциальных функций; метод потенциальных функций метод потенциальных функций отбор эталонных объектов. отбор эталонных объектов. отбор эталонных объектов отбор эталонных объектов разделимость разделимость линейный дискриминант Фишера; линейный дискриминант Фишера; линейный дискриминант Фишера линейный дискриминант Фишера метод опорных векторов метод опорных векторов метод опорных векторов метод опорных векторов логические закономерности логические закономерности деревья решений; деревья решений; ассоциативные правила; ассоциативные правила; Нейронные сети Нейронные сети

Гипотеза компактности В задачах классификации это предположение о том, что схожие объекты гораздо чаще лежат в одном классе, чем в разных; или, другими словами, что классы образуют компактно локализованные подмножества в пространстве объектов. Это также означает, что граница между классами имеет достаточно простую форму. В задачах классификации это предположение о том, что схожие объекты гораздо чаще лежат в одном классе, чем в разных; или, другими словами, что классы образуют компактно локализованные подмножества в пространстве объектов. Это также означает, что граница между классами имеет достаточно простую форму. Унимодальная компактность Унимодальная компактность Полимодальная компактность Полимодальная компактность Локальная компактность Локальная компактность

Статистические подходы Оценивание априорных вероятностей частотами Оценивание априорных вероятностей частотами s =M(s)/M, где М(s) – число объектов класса s в обучающей выборке s =M(s)/M, где М(s) – число объектов класса s в обучающей выборке Оценивание условных вероятностей (функций правдоподобия) для каждого класса сводится к следующей задаче: Оценивание условных вероятностей (функций правдоподобия) для каждого класса сводится к следующей задаче: Дано: Дано: Аm = {а1,..., аm} простая выборка (xi без ответов yi ). Аm = {а1,..., аm} простая выборка (xi без ответов yi ). Найти: Найти: эмпирическую оценку плотности (x), аппроксимирующую истинную плотность p(x) на всём X: эмпирическую оценку плотности (x), аппроксимирующую истинную плотность p(x) на всём X: (x) p(x) при m. (x) p(x) при m. Существует несколько основных подходов к оцениванию плотностей Существует несколько основных подходов к оцениванию плотностей Параметрическое оценивание плотности: Параметрическое оценивание плотности: (x) = ϕ (x, θ). (x) = ϕ (x, θ). Восстановление смеси распределений: Восстановление смеси распределений: (x) =w 1 ϕ (x, θ 1 )+…+w k ϕ (x, θ k ), k < m. (x) =w 1 ϕ (x, θ 1 )+…+w k ϕ (x, θ k ), k < m. Непараметрическое оценивание плотности: Непараметрическое оценивание плотности: пропорциональна m(V)/|V|, где V – локальная окрестность точки x. пропорциональна m(V)/|V|, где V – локальная окрестность точки x.

N-мерное нормальное распределение s – вектор матожидания класса s s – матрица ковариаций для класса s В случае нормальных распределений разделяющая поверхность PsPs(x)= PyPy(x) квадратична для всех y, s Y, y s. Если s = y, то она вырождается в линейную. В предположении о независимости признаков матрица ковариации становится диагональной и легко обращается

Правило ближайшего соседа, k ближайших соседей

Вместо всех объектов выборки можно использовать небольшое число эталонов Границы ошибки правила ближайшего соседа P*

Метод потенциальных функций Каждому объекту приписывается заряд +1-первому образу -1-второму образу Измеряется суммарный потенциал во всех точках поля P=1/(r*r+a) Распознавание производится по знаку потенциала

Линейный дискриминант Фишера w J(w)=(m1-m2) 2 /(D1+D2)->max

Метод опорных векторов Разделяющая граница Разделяющая граница -w0=0 -w0=0 Ширина полосы максимальна 2/||w||->max Ширина полосы максимальна 2/||w||->max При наличии объектов, попадающих в полосу вводится штраф При наличии объектов, попадающих в полосу вводится штраф Сводится к задаче выпуклого квадратичного программирования Сводится к задаче выпуклого квадратичного программирования Решается с помощью множителей Лагранжа Решается с помощью множителей Лагранжа Опорные вектора – объекты по которым проходят границы полосы Опорные вектора – объекты по которым проходят границы полосы w Нелинейное обобщение метода опорных векторов с помощью ядерных функций K(x,y)= *

Деревья решений Внутренняя вершина – предиктор расщепления Внутренняя вершина – предиктор расщепления Висячие вершины –имя класса Висячие вершины –имя класса Дерево не обязательно бинарное Дерево не обязательно бинарное Преимущества Преимущества Возможность работы с разнотипными данными Возможность работы с разнотипными данными Интуитивная понятность решений Интуитивная понятность решений Выбор признаков, существенных для решаемой задачи Выбор признаков, существенных для решаемой задачи Наиболее популярные алгоритмы CART, C4.5 Наиболее популярные алгоритмы CART, C4.5 х {0,2} да нет y [0,2] z=ясно да нет да нет Если : (х {0,2})&~(y [0,2])&(z=ясно) То: Класс 0

Деревья решений Критерии расщепления Критерии расщепления Мера энтропии Мера энтропии E(T)=-(p 1 *logp 1 +p 2 *logp 2 ) E(T)=-(p 1 *logp 1 +p 2 *logp 2 ) Индекс Gini Индекс Gini G(T)=1-(p 1 2 +p 2 2 ) G(T)=1-(p 1 2 +p 2 2 ) Критерии остановки Критерии остановки Достижение максимальной глубины(числа вершин) Достижение максимальной глубины(числа вершин) Отсутствие вершин, пригодных для расщепления Отсутствие вершин, пригодных для расщепления Критерии отсечения вершин Критерии отсечения вершин Незначительное увеличение ошибки распознавания Незначительное увеличение ошибки распознавания Компромисс между сложностью и точностью решения Компромисс между сложностью и точностью решения

Ансамбль классификаторов Каждое решающее правило может обучаться на своей подвыборке Каждое решающее правило может обучаться на своей подвыборке Бэггинг Бэггинг Бустинг Бустинг Случайные подпространства признаков Случайные подпространства признаков Обобщающий классификатор Обобщающий классификатор Простое голосование Простое голосование Взвешенное голосование Взвешенное голосование Выбор наиболее компетентного решающего правила Выбор наиболее компетентного решающего правила Обобщающий классификатор РП 1РП 2РП k … Обучающая выборка ОВ1ОВ2ОВ k …

Сравнение эффективности алгоритмов распознавания Основной показатель качества средняя частота ошибок на контроле, с доверительным интервалом. Основной показатель качества средняя частота ошибок на контроле, с доверительным интервалом. Средняя переобученность (разность частоты ошибок на контроле и обучении). Средняя переобученность (разность частоты ошибок на контроле и обучении). Графики эмпирических распределений частоты ошибок на контроле и переобученности. Эмпирические распределения позволяют оценивать риски, свзязанные с переобучением. Графики эмпирических распределений частоты ошибок на контроле и переобученности. Эмпирические распределения позволяют оценивать риски, свзязанные с переобучением. ROC-кривые на обучающих и контрольных данных. Если число классов превышает 2, то для каждого класса строится своя ROC-кривая. ROC-кривые на обучающих и контрольных данных. Если число классов превышает 2, то для каждого класса строится своя ROC-кривая. ROC-кривые Профиль представительности объектов. Для каждого объекта вычисляется доля разбиений, при которых он попадает в контроль, и на нём допускается ошибка. График профиля представительности позволяет идентифицировать объекты, являющиеся выбросами с точки зрения данного алгоритма. Профиль представительности объектов. Для каждого объекта вычисляется доля разбиений, при которых он попадает в контроль, и на нём допускается ошибка. График профиля представительности позволяет идентифицировать объекты, являющиеся выбросами с точки зрения данного алгоритма. Профиль представительности Профиль представительности

ROC-кривая TPR-верно распознанный первый образ TPR-верно распознанный первый образ FRP-ошибочно распознанный образ FRP-ошибочно распознанный образ

Существующие системы тестирования RapidMiner, WEKA, R, Matlab, STATISTICA RapidMiner, WEKA, R, Matlab, STATISTICA RapidMinerWEKARMatlab STATISTICA RapidMinerWEKARMatlab STATISTICA