Предлагается количественная мера компактности образов, основанная на использовании функции конкурентного сходства (FRiS-функции). Рассматривается метод цензурирования обучающей выборки путем исключения «шумящих» объектов, что повышает компактность образов и приводит к улучшению качества распознавания контрольной выборки. Состав исключаемых объектов определяется автоматически. Эффективность алгоритма цензурирования иллюстрируется решением модельной задачи распознавания двух образов.
Training dataset censoring.pdf Цензурирование обучающей выборки состоит в исключении из нее объектов, которые понижают компактность образов. Это могут быть как «случайные» объекты, свойства которых сильно отличаются от свойств остальных объектов своих образов, так и объекты, находящие в зоне пересечения с объектами других образов. Такие данные разрушают компактность образов и усложняют решающие правила, что ведет к увеличению числа ошибок при распознавании контрольной выборки. Назовем подобные объекты «шумящими» и будем исключать их из обучающей выборки. Предлагаемый метод повышения компактности основывается на использовании новой меры для оценки сходства между объектами - функции конкурентного сходства, с помощью которой можно описывать любые распределения образов набором эталонных объектов («столпов»). Использование столпов позволяет оценить вклад в компактность образов каждого объекта выборки и получить количественную меру компактности всей совокупности образов или любого отдельного образа, а также выбрать объекты, вносящие отрицательный вклад в компактность образов. В итоге решающее правило, построенное по очищенной обучающей выборке, обеспечивает повышение качества распознавания контрольных объектов. 1. Функция конкурентного сходства Сформулируем следующие требования, которым должна удовлетворять мера F(z,a\b) сходства объекта z с объектом a в конкуренции с объектом b. 1. Свойство нормированности. Если оценивается мера сходства объекта z с объектом a в конкуренции с объектом b, то при совпадении объектов z и a мера F(z,a|b) должна иметь максимальное значение равное 1, а при совпадении z с b -минимальное значение равное -1. Во всех остальных случаях мера конкурентного сходства принимает значения от -1 до 1. 2. Свойство антисимметричности. Значения сходства z с а в конкуренции с b и сходства z с b в конкуренции с а связаны соотношением F(z,a|b) = -F(z,b|a). При одинаковых расстояниях r(z,a) и r(z,b) объект z в равной степени будет похожим на объекты a и b и F(z,a\b) = F(z,b\a) = 0. 3 Свойство инвариантности. Значение F(z,a\b) должно сохраняться при аффинных преобразованиях пространства признаков: при сдвиге начала координат, повороте координатных осей, а также при умножении всех координат на одно и то же число. Предлагаемая нами функция конкурентного сходства FRiS (Function of Rival Similarity) [1] F(z, a \ b) = (1) r (z, b) + r (z, a) удовлетворяет всем этим требованиям. Как расстояния r между объектами, так и сходство F между ними не зависит от аффинных преобразований пространства признаков. Но независимые изменения масштабов разных координат меняют вклад, вносимый отдельными характеристиками в оценку и расстояний, и сходства. Меняя веса характеристик, можно подчеркнуть сходство или различие между заданными объектами, что обычно и делается при выборе информативных признаков и построении решающих правил в распознавании образов. Сходство в шкале порядка, используемое в методе k ближайших соседей, отвечает на вопрос: «На объект какого образа z похож больше всего?». Конкурентное сходство, измеряемое с помощью FRiS-функции, отвечает на этот вопрос и, кроме того, на такой вопрос: «Какова абсолютная величина сходства z с a е A в конкуренции с b е B ?» Оказалось, что дополнительная информация, которую дает абсолютная шкала по сравнению со шкалой порядка, позволяет существенно улучшить методы анализа данных (АД). Функция конкурентного сходства используется нами в алгоритмах решения широкого круга как известных, так и новых задач АД [2]. Определим меру сходства F(zAIB) объекта z с образом A в конкуренции с образом B как F(z,a|b), где a (b) - ближайший к z объект образа A(B), т.е. помимо указанных выше свойств мера сходства F(z,A|B) удовлетворяет свойству локальности: F(z,A|B) зависит не от характера распределения всего множества объектов образов A и B, а от особенностей распределения объектов в окрестности z. Окрестностью объекта будем называть сферу минимального радиуса, содержащую объекты анализируемых образов. Отметим, что в зависимости от рассматриваемой задачи образы могут быть представлены как непосредственно своими объектами, так и своими эталонами (столпами). 2. Выбор эталонных объектов Для распознавания образов необходимо выбрать объекты-эталоны (столпы), c которыми будут сравниваться контрольные объекты. Набор столпов считается достаточным для описания выборки, если сходство F всех объектов обучающей выборки с ближайшими своими столпами в конкуренции с ближайшими объектами других образов превышает пороговое значение F*, например F* = 0 . Здесь описано решающее правило, которое основано на использовании FRiS-функции и строится с помощью алгоритма FRiS-Stolp. Этот алгоритм работает при любом соотношении количества объектов к количеству признаков и при произвольном виде распределения образов. В качестве столпов выбираются объекты, которые обладают высокими значениями двух свойств: обороноспособности по отношению к объектам своего образа и толерантности по отношению к объектам других образов. Чем выше обороноспособность эталона, тем меньше будет ошибок типа «пропуск цели». Чем выше толерантность эталона, тем меньше будет ошибок типа «ложная тревога». В результате для каждого образа выбираются такие столпы, на которые свои объекты похожи больше, чем на объекты конкурирующих образов. Алгоритм выбирает эталоны для произвольного количества образов, но объяснять его работу будем на примере распознавания двух образов - А = {аг,..., aM } и B = {Ьх,...,ЬМв }, представленных наборами из MA и MB объектов обучающей выборки соответственно. Поясним алгоритм FRiS-Stolp с помощью рис. 1. Рис. 1. Оценка обороноспособности и толерантности объекта at е A Начнем с выбора первого столпа для образа A. 1. Оценим качество исполнения роли столпа всеми объектами ai, i = 1,.,МA, по очереди. Вначале проверим, хорошо ли объект ai защищает объекты aj, J = 1,...,Ma , образа A. Для каждого объекта aj, J = 1,.,Ma , определим расстояния r(a,,ai) и r(a.,Ь), где Ье B является ближайшим соседом объекта a:, т. е. j ' j j j J j' = arg min r(a,,bm), и по формуле (1) получим значение F(a,,ai |Ь,) функm=1,..., М B J ции сходства объекта a, с ai е A в конкуренции с Ь,> е B (см. рис. 1). 2. Выделим m(ai) объектов a, е A, сходство которых с ai не меньше заданного порога F*: F+ = F(a,, ai | Ьу) - F* > 0 , j е {1,..., МА }. Эти объекты надежно защищены ai. Получим оценку D(ai) обороноспособности объекта ai: Ma D(a
Загоруйко Николай Григорьевич | Новосибирский государственный университет; Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук (г. Новосибирск) | профессор, доктор технических наук, профессор кафедры общей информатики; заведующий лабораторией анализа данных | zag@math.nsc.ru |
Кутненко Ольга Андреевна | Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук (г. Новосибирск) | доцент, кандидат технических наук, доцент кафедры дискретного анализа и исследования операций | olga@math.nsc.ru |
Zagoruiko N.G., Borisova I.A., Dyubanov V.V., Kutnenko O.A. Methods of recognition based on the function of rival similarity // Pattern Recognition and Image Analisys. 2008. V. 18. No. 1. P. 1-6.
Borisova I.A., Dyubanov V.V., Kutnenko O.A., Zagoruiko N.G. Use FRiS-function for taxonomy, attribute selection and decision rule construction // Knowledge Processing and Data Analysis. Berlin - Heidelberg: Springer-Verlag, 2011. P. 256-270.
Браверман Э.М. Эксперименты по обучению машины распознаванию зрительных образов // Автоматика и телемеханика. 1962. Т. 23. № 3. С. 349-365.
Загоруйко Н.Г., Борисова И.А., Дюбанов В.В., Кутненко О.А. Количественная мера компактности и сходства в конкурентном пространстве // Сибирский журнал индустриальной математики. 2010. Т. XIII. № 1(41). С. 59-71.