- •Постановка задачи классификации (с учителем)
- •Решение задачи многоклассовой классификации одним классификатором
- •Решение задачи многоклассовой классификации независимыми бинарными классификаторами.
- •I. Обзор методов классификации с учителем
- •2 . Линейное расстояние (манхеттенская мера) тоже выражение что и (п.1) но для общего случая
- •3. Обобщенное степенное расстояние Минковского
- •4. Взвешенное Эвклидово расстояние
- •5. Расстояние Махаланобиса
- •1. Компонентный анализ и 2. Выделение главных компонент
- •1. Компонентный анализ
- •2. Размерность пространства дискриминационных функций q
Решение задачи многоклассовой классификации одним классификатором
Задаем зачения идеального классификатор Уид, который на известных объектах из Хобуч принимает заданные нами ( уловные) значения:
на рис приведены значения группирующей переменной выхода Уид для 4-классов – внизу условные номера (имена) пациентов.
Пусть уровени классов Р1=220
Р2=180 Р3=140 Р4=100
Затем ( регрессией или З.Л.П. ) строим реальный, максимально к Уид приближенный классификатор У=F(X) который в Х должен максимально приближать Уид.
Затем ищем оптимальные пороги (щтриховые линии R1 R2 R3 ) относительно которых будем принимать решения классификации
Плюсы подхода
–1. все проблемы - решаем одним классификатором.
2. Однозначность классификации (качество – другой вопрос)
Минус подхода - как правило классификатор должен быть сложным, нелинейным - такой сделать качественным очень сложно
Решение задачи многоклассовой классификации независимыми бинарными классификаторами.
Основной принцип - группировка классов в группы и независимое решение задач классификации для каждой из них
Группируя выборки классов и решая классификацию отдельно для каждой выборки, требуется, при прочих равных условиях, классификатор всегда проще, за счет чего точность подхода всегда выше чем в п. 1..
Примеры
А) “один против всех” строится так чтобы
Решение о принадлежности точки классу принимается при
и
Распознающая система К классов
состоит из построенных независимо друг от друга К функций
Поэтому существует механизм возникновения неопределенных ситуаций
О механизме ошибок бинарных классификаторов.
Ошибки каждого отдельного классификатора при двух возможных вариантах ответа могут быть следующие;
Ошибка 1 рода – пропуск цели своим Классификатором – то есть, когда он отказался от своего больного.
И ошибка 2 рода: Классификатор должен был пропустить пациента с не своим диагнозом, а потянул одеяло на себя – ошибочно признал диагноз своим. Тогда для системы классификаторов возникает следующие 2 основных по последствиям для пациента варианта сочетания на нем ошибок 1 и 2 рода:
С огласованная ошибка: и и
i-тый
класс
j-тый
класс
Все другие сочетания ошибок приводят к «несогласованным» ошибкам классификаторов то есть к их конфликту или отказу от классификации что позволяет продолжать обследование пациента
Конфликт за «своего» (0+1) Конфликт за «своего» (0+2)
и и
i-тый
класс
i-тый
класс
Конфликт за «чужого» (1+2) Отказ от классификации
все
Касательно последнего случая
– не беда если область отказа где-то на хвостах распределения Х– скажем температура пациента - 00С. Но плохо, если эта область реального интереса, Тогда будем иметь необходимость дополнительных обследований пациента.
Как снижать процент конфликтов (распознаваемых ошибок)? – есть определенные приемы, о них позже.
Если нераспознаваемых ошибок много и нет других вариантов то для этих объектов выделяется отдельный класс.
Б) “группировки по два” или двоичное кодирование – пример 4-х классов
Запишем номер класса в виде q значного двоичного числа. Например, для 4 классов это классы 0 00, 1 01, 2 10, и 3 11
К=4 представлен q =2 разрядами двоичного числа.
Теперь если мы обучим классификаторы определять номер разряда (0 или 1) то нам понадобится не К кдассификаторов а q – в 2 раза меньше чтобы однозначно определить номер класса.
Е сли не очень ясно – пример: чтобы определить номер класса (их 4) на рис. достаточно построить только 2 границы,
г раницей штриховой мы отделили 0 от 1 в первом разряде числа а границей точечной 0 от 1 во втором разряде числа. Если проверка первого классификатора дала область 11+10 а второго 10+01, то общий у них класс 10 то есть третий К=3
И обратим внимание - кажлая из этих границ проще чем “один против всех” - поэтому есть шансы получать лучшее качество распознавателей
Заметим что для нахождения наилучшего сочетания границ надо перебрать 3 различных варианта сочетаний номеров и выбрать лучший по качесту распознавания. Имеется в виду следующее см рисунок
и
3. Решение задач многоклассовой классификации системой решающих правил
Системы из линейных элеменарных классификаторов попарно разделяющие классы - Yij(Х) в пространстве Х образуют симплексы – выпуклые областии.
Образуем системы (1)
Iкл)–Y13(Х)>0,
Y12(Х)>0;
знак Y23(Х) –безразличен (1-нет)
II кл) – Y12(Х)<0,
Y23(Х)>0;
знак Y13(Х) –безразличен (2-нет)
IIIкл) – Y13(Х)<0,
Y23(Х)>0;
знак Y12(Х) –безразличен (3-нет)
В общем случае нужно строить такие, что бы
для и
для
Тогда из можно строить системы подобные (1)
Ответ в каком случае выигрышно применять какую схему может дать только непосредственное применение схемы.
Другой пример классификации с помощью системы функций - получение системы дискриминантных функций и отнесение объекта к классу по расстоянию до их центров.
Метрику расстояния выбирают при этом разную в зависимости от свойств выборки – Эвклидову, Махолонобиса, Рао …..
Ну и последнее – что считать показателем качества распознающей системы – естественно таковой считать процент правильного распознавания. Так в ряде методов и применяется такой критерий.
Так и получив классификатор с помощью любой другой процедуры (с другим критерием) мы обязательно вычислим % распознавания.
Но при всей своей естественности этот критерий нелинеен (целочисленен) и достаточно груб – при одном и том же значении критерия возможно предлагать множество классиикаторов (границ). Поэтому в дальнейшем задачах ДА вы увидете другие, не такие в лоб прямые варианты критериев, но они будут более гибкие и косвенно связанные с % распознавания.
Методы классификации с “учителем”
Рассмотрим упрощенную схему методов классификации с учителем
Вероятностный подход
Изучение материала проведем в 2 этапа