Задачи комбинированного типа. Функция конкурентного сходства. Лекция 5

Задачи комбинированного типа Таксономия(S) Выбор признаков (X) Построение решающего правила (D) (SD) (SX) (DX) Одновременное построение таксономии, решающего правила и выбор информативной системы признаков (SDX)

Задача SX Ищется такое подпространство признаков X b, а в нем такой вариант таксономии S w множества объектов Z, при которых суммарные потери N машинных ресурсов и информации были бы минимальными. Запишем это так: Ищется такое подпространство признаков X b, а в нем такой вариант таксономии S w множества объектов Z, при которых суммарные потери N машинных ресурсов и информации были бы минимальными. Запишем это так: w,b=argmin N(X b,S wb )/Z, w,b=argmin N(X b,S wb )/Z, b B,w W b B,w W где В – множество индексов для всех рассматриваемых наборов признаков X b, а W – множество индексов для всевозможных разбиений S w объектов из Z на классы. где В – множество индексов для всех рассматриваемых наборов признаков X b, а W – множество индексов для всевозможных разбиений S w объектов из Z на классы. В общем виде эта задача переборная. В общем виде эта задача переборная.

Особенности «естественных» классификаций: Разбиение производится по небольшому числу «существенных» признаков. Разбиение производится по небольшому числу «существенных» признаков. Позволяет предсказывать неизвестные свойства объектов путем распространения единичных наблюдений на весь класс. Позволяет предсказывать неизвестные свойства объектов путем распространения единичных наблюдений на весь класс. Часто представляет из себя не просто разбиение множества объектов на классы, а некую иерархическую структуру. Часто представляет из себя не просто разбиение множества объектов на классы, а некую иерархическую структуру. На каждом уровне иерархии используется свое, наиболее информативное подпространство признаков. На каждом уровне иерархии используется свое, наиболее информативное подпространство признаков.

Алгоритм NatClass Пространство существенных признаков Xb, Q(Xb)=Qr+Qt Пространство существенных признаков Xb, Q(Xb)=Qr+Qt Разделяющая способность Qt - через качество таксономии в Xb Разделяющая способность Qt - через качество таксономии в Xb Прогностическая способность Qr Прогностическая способность Qr Для каждого таксона вычисляется квадрат отклонения реального значения признака от спрогнозированного Для каждого таксона вычисляется квадрат отклонения реального значения признака от спрогнозированного, где Эффективность таксономии для прогнозирования i-го признака: Эффективность таксономии для прогнозирования i-го признака: где К –число таксонов в таксономии, w(x) – монотонно возрастающая весовая функция. Выбор наиболее информативной системы признаков может осуществляется посредством алгоритма AdDel. Выбор наиболее информативной системы признаков может осуществляется посредством алгоритма AdDel.

Задача SDX Необходимо привести неструктурированный массив данных к виду, удобному для восприятия человека Необходимо привести неструктурированный массив данных к виду, удобному для восприятия человека Сокращение числа объектов (переход к эталонам) Сокращение числа объектов (переход к эталонам) Сокращение числа признаков (переход к наиболее информативным) Сокращение числа признаков (переход к наиболее информативным) Задача формулируется в терминах задач комбинированного типа как задача SDX Задача формулируется в терминах задач комбинированного типа как задача SDX

Задачи комбинированного типа ПРЕДПОСЫЛКИ: Необходимость решать практические задачи, где: Число объектов меньше числа признаков Генетические задачи Медицинская диагностика Криминалистика Статистические методы не работают ЦЕЛЬ: Разработка согласованных и универсальных алгоритмов решения задач распознавания образов комбинированного типа, применимых к плохо обусловленным прикладным задачам.

Функция конкурентного сходства r1 r2 F=0 F=(r2-r1)/(r2+r1) F [-1, 1]

Формулировка компактности через FRiS-функцию Среднее значение конкурентного сходства для всех объектов выборки ~ компактность выборки Среднее значение конкурентного сходства для всех объектов выборки ~ компактность выборки F=0.87F=0.38F=0.03 В зависимости от принципов по которым определяются ближайший «свой» и «чужой» представители можно моделировать различные виды компактности Похожесть на ближайшего соседа – локальная компактность Похожесть на типичного представителя – унимодальная и полимодальная компактность

Плотность распределения FRiS-функции в статистической постановке задачи распознавания

Зависимость ожидаемой величины FRiS-функции от вероятности ошибочного распознавания