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

На правах рукописи

Борисова Ирина Артемовна

МЕТОДЫ РЕШЕНИЯ ЗАДАЧ РАСПОЗАНАВАИИЯ ОБРАЗОВ КОМБИНИРОВАННОГО ТИПА

Специальность 05.13.17 - Теоретические основы информатики

Автореферат диссертации на соискание ученой степени кандидата технических наук

Новосибирск 2008

003451565

Работа выполнена в Институте математики им. С.Л. Соболева СО РАН,

г. Новосибирск

Научный руководитель: доктор технических наук, профессор

Загоруйко Николай Григорьевич

Официальные оппоненты: доктор технических наук, профессор

Попов Александр Александрович доктор физико-математических наук, с.н.с. Витяев Евгений Евгеньевич

Ведущая организация: Институт вычислительной математики и

математической геофизики СО РАН, г. Новосибирск

Защита состоится « Д » ноября 2008 года в 14-00, на заседании диссертационного совета Д 212.173.06 при Новосибирском государственном техническом университете по адресу: 630092, г. Новосибирск, пр. Карла Маркса, 20.

С диссертацией можно ознакомиться в библиотеке Новосибирского государственного технического университета.

Автореферат разослан « №» октября 2008 г.

Ученый секретарь диссертационного совета

Чубич В.М.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Основным объектом исследования в данной работе являются задачи распознавания образов комбинированного типа. Такого рода задачи возникают в случае, когда для более полного и всестороннего анализа выборки одновременно и согласованно решается несколько задач распознавания образов основных типов (к ним относятся задачи построения решающего правила, таксономии, выбора информативных признаков). Комбинированные задачи хорошо согласуются с механизмами анализа информации, используемыми человеком, и открывают новые возможности для решения сложных плохо обусловленных прикладных задач, количество которых неуклонно возрастает в последнее время. Ярким примером этих задач являются задачи в генетике и медицине, в которых небольшое число объектов (пациентов, страдающих определенным заболеванием) описывается огромным количеством признаков (симптомов, вплоть до описания активности отдельных генов). В связи с практической значимостью такого рода «некорректных» с точки зрения классической теории распознавания задач, разработка методов их решения приобретает все большую актуальность.

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

Основные направления исследований. В качестве основы для большинства предложенных алгоритмов используется функция конкурентного сходства (РШЗ-функция) и некоторые ее модификации. Исследуется эффективность РШБ-функции при выборе информативной системы признаков. Показывается применимость ЕШБ-функции для обнаружения зон локального сгущения объектов. Сочетание этих свойств позволяет успешно использовать РШЗ-функции при формировании критериев качества решений различных задач комбиниро-

ванного типа.

Методы исследований опираются на аппарат методов оптимизации, используются элементы математической статистики, широко применяется имитационное моделирование.

Научная новизна работы состоит в том, что в ней впервые получены и выносятся на защиту следующие наиболее важные результаты:

1. В рамках исследования применимости ГИБ-функций показана их эффективность в качестве критерия информативности при решении задачи одновременного построения решающего правила и выбора наиболее информативного подпространства признаков. Предложена методика оценки надежности получаемых информативных систем признаков, их «неслучайности». Также предложена методика оценки надежности распознавания каждого нового объекта при использовании решающих правил, полученных с помощью алгоритма РШ8-8и>1р.

2. Разработан алгоритм РШЗ-Тах для решения задачи комбинированного типа - одновременного построения таксономии и решающего правила, ее описывающего. Этот алгоритм не только хорошо воспроизводит результаты, получаемые человеком-экспертом при решении задачи таксономии в пространствах малых размерностей, но и позволяет автоматически определять наилучшее число таксонов из заданного диапазона.

3. Сформулированы основные требования, предъявляемые к «естественным» классификациям. Установлена связь между задачей построения «естественной» классификации и задачей комбинированного типа - построением таксономии с одновременным выбором наиболее информативного подпространства признаков. Для решения данной задачи разработан алгоритм ЫаЮазэ.

4. Сформулирована наиболее сложная задача распознавания образов комбинированного типа - задача одновременного построения таксономии и решающего правила для ее описания в наиболее информативном признаковом пространстве. Предложена методика решения этой задачи, позволяющая макси-

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

Достоверность и обоснованность предлагаемых решений подтверждается результатами применения предложенных алгоритмов как к модельным, так и к реальным задачам различной природы, а также результатами обсуждения этих идей в сообществе специалистов.

Практическая ценность работы состоит в том, что использование разработанных алгоритмов для задач комбинированного типа с плохо обусловленными данными показывает их более высокую эффективность по сравнению с существующими аналогами. Предложенные алгоритмы позволяют имитировать действия человека при анализе информации. Большая часть разработок включена в пакет сервисных программ, автоматизирующих работу эксперта при анализе спектров образцов мелкодисперсных материалов, созданный по заказу Института Криминалистики ФСБ.

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

• KDS-2001,2007 (Knowledge-Dialog-Solutions),

• PRIA-2004,2007 (Pattern Récognition and Image Analysis),

• PRIP-2005,2007 (Pattern Récognition and Image Processing),

• MMPO-12,13 (Математические Методы Распознавания Образов),

• ACIT-SE-2005 (Automation, Control and Information Technology),

• BGRS-2006 (Bioinformatics of Genome Regulation and Structure),

• 30HT-2007 (Знания, Онтологии, Теории).

Отдельные этапы работы прошли экспертизу в ходе выполнения проектов, поддержанных грантами РФФИ (проекты № 02-01-00082-а, №05-01-00241-а).

Личный вклад. Основные результаты, связанные с разработкой, исследованием и апробацией алгоритмов FRiS-Tax, Nat-Class и FRiS-SDX получены ав-

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

Публикации. По теме диссертации опубликованы 16 работ, из них 2 научные статьи в журналах, входящих в перечень изданий, рекомендованных ВАК РФ, 2 научные статьи в ведущих рецензируемых журналах, 2 - в сборниках научных трудов, 10-в сборниках трудов конференций.

Структура работы. Диссертационная работа изложена на 121 страницах и состоит из введения, обзора литературы (глава 1), четырех глав, содержащих основные результаты, и заключения. Иллюстративный материал представлен 24 рисунками и 1 таблицей. Список литературы включает 77 ссылок.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

В первой главе представлен обзор задач распознавания образов основного и комбинированного типа. Приводится формулировка каждой из них и описываются основные подходы к их решению.

Исторически сложилось, что в области распознавания образов выделяются несколько основных типов задач: это задача построения решающего правила Б, задача выбора информативной системы признаков X и задача таксономии Б. Для всех этих задач разработан широкий спектр методов их решения, как эвристических, так и статистических, с обоснованной надежностью и строго ограниченным кругом применения. Однако при решении реальных практических задач невозможно сказать заранее, какой класс алгоритмов целесообразно к

ним применять, какие ограничения на создаваемые решения накладывать, функционал качества какого вида использовать.

Задачи комбинированного типа возникают тогда, когда появляется необходимость одновременно и согласованно решать несколько задач основных типов для одной и той же выборки. К ним относятся задачи:

• БХ - задача одновременного построения решающего правила и наиболее информативного пространства признаков;

• ЭХ - задача таксономии и одновременного отыскания информативного пространства признаков;

• вБ — задача одновременного построения таксономии и решающего правила для дальнейшего ее распознавания;

• ББХ - задача одновременного построения таксономии, решающего правила для ее распознавания и пространства информативных признаков. Обычно такого рода задачи возникают при анализе массивов данных, непредставительных с точки зрения формальных статистических методов. В таких массивах среди описывающих признаков могут присутствовать неинформативные, объектов обучающей выборки может быть недостаточно для обнаружения скрытой закономерности, среди объектов могут присутствовать «выбросы». Переход к задачам комбинированного типа позволяет снимать часть требований к исходной обучающей выборке и учитывать возможные неточности в ней. Кроме того, задачи комбинированного типа лучше согласуются с человеческими принципами анализа информации, так как в реальной жизни распознающей системе под названием «человек» обычно приходится решать задачи классификации, группировки и выбора признаков одновременно.

Хотя термин «задача комбинированного типа» известен с 70-х годов, эту область нельзя назвать тщательно проработанной. Если задачей БХ занималось и занимается большое количество исследователей, то задача вХ решается в основном в статистической постановке, когда выбор признаков осуществляется после фиксации вероятностной модели рассматриваемой выборки с точностью

до нескольких параметров. Что касается наиболее сложной и интересной задачи комбинированного типа - задачи SDX - серьезных исследований, касающихся методов ее решения, очень немного.

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

Во второй главе дается определение функции конкурентного сходства (FRiS-функции) и исследуется ее применимость при решении задачи комбинированного типа DX.

Рассмотрим обучающую выборку А, состоящую из т объектов, описанных множеством из п признаков X. Все объекты разделены на к классов. Каждый класс г описывается набором из /г эталонных образцов (столпов) Sz2 ■>•■■■> Srt j • Соответственно, вся обучающая выборка Л описыва-к

ется набором столпов " =

IX . В общем случае Sx может состоять как из ре-

г=1

альных объектов выборки А так и из искусственно сгенерированных эталонов классов. Мы будем рассматривать только случай SzczÄ. Для объекта а из обучающей выборки А, относящегося к классу т определим

- расстояние до ближайшего столпа «своего» об-

„ „ _min р(а, s )

раза, а r2(a,S)= r>_i k т'*т i=\,..,l ■ ~ расстояние до ближаишего

столпа образа-конкурента. Тогда функция конкурентного сходства объекта а со своим классом вычисляется по формуле:

r2(a,S)-r\{a,S)

F(a,S) =

r2{a,S) + r\(a,S)

Если мы найдем среднее значение РШБ-функции при фиксированном наборе столпов 5 по всей выборке, то полученная величина:

(1)

аеА

характеризует, насколько полно этот набора столпов описывает выборку. Чем больше Р(8), тем более подробное и точное описание выборки у нас имеется. На этом свойстве РШ8-функции основывается алгоритм РШЗ-БЫр, создающий в процессе работы сокращенное описание выборки А в виде набора столпов 5. Его использование позволяет сократить описание выборки, избавиться от ошибок и «выбросов», содержащихся в ней, но при этом сохранить информацию, необходимую для дальнейшего распознавания новых объектов. Непосредственно распознавание при этом осуществляется по следующему правилу: объект относится к тому классу, конкурентное сходство с которым оказывается максимальным.

Аналог величины , вычисленный для случая, когда все объекты выборки считаются ее столпами (когда в качестве г1 берется расстояние до ближайшего объекта «своего» образа, а в качестве г2 - расстояние до ближайшего объекта из образа «конкурента») обозначим за Он позволяет оценить, насколько отделены друг от друга образы в пространстве описывающих признаков X. Поэтому величина может использоваться в качестве критерия для выбора наиболее информативного подпространства признаков, в котором образы максимально отделены друг от друга.

В рамках данной работы показывается, что критерий ^ , основанный на функции конкурентного сходства, оказывается эффективнее существующих аналогов, таких как средняя ошибка распознавания, оцениваемая в режиме скользящего экзамена 17, критерий Фишера £?> взвешенный критерий семейства алгоритмов ЫЕЫЕР IV. Результаты сравнения этих критериев на серии модельных задач приводятся на рис. 1. Здесь по оси абсцисс откладывается количество

признаков в выбранной информативной подсистеме, по оси ординат - надежность этой подсистемы при распознавании контрольной выборки, р

Рис. 1 Сравнение эффективности четырех критериев выбора информативной системы признаков.

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

Эксперименты показали, что при использовании РИБ-функции можно достаточно точно предсказывать эффективность полученных подпространств при распознавании контрольной выборки. Более того, было продемонстрировано, как величина БИЯ-функции, вычисленная для нового объекта г, может использоваться для оценки надежности распознавания этого объекта. Хотя зависимость между значением Р&Б-функции и вероятность ошибочного распознава-

10

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

Объединение наработок по применению FRiS-функций к проблеме выбора признаков X и построения решающих правил D позволяет перейти к отысканию такого решения задачи DX (одновременного выбора системы признаков и построения решающего правила). Целью является отыскание такого набора эталонов S* и такого подпространства признаков Y*ef?(X), для которых среднее значение функции конкурентного сходства, вычисленное по формуле (1) было максимальным:

max

YeP(X),' aeA SQA

где Fy(a,S)- величина функции конкурентного сходства объекта а с набором столпов S в подпространстве Y.

Алгоритм, отыскивающий приближенные решения этой экстремальной задачи, называется FRiS-Agent и состоит в следующем. С помощью алгоритма AdDel осуществляется направленный поиск системы информативных признаков У, обеспечивающей максимальное значение среднему значению FRiS-функции, вычисленной с опорой на множество эталонных объектов Sy. В свою очередь выбор Sy в фиксированном подпространстве Y осуществляется алгоритмом FRiS-StoIp.

Сравнение результатов работы этого алгоритма с аналогами, используемыми для решения задачи DX, показало его преимущества.

В третьей главе описывается новый алгоритм FRiS-Tax, основанный на использовании функции конкурентного сходства, который позволяет решать задачу SD (одновременного построения таксономии и решающего правила для ее распознавания). Этот алгоритм хорошо воспроизводит действия человека-эксперта в процессе разбиения объектов на классы и позволяет автоматически выбирать «разумное» число классов.

При решении задачи таксономии все объекты выборки А изначально относятся к одному классу. Пусть этот класс описывается набором столпов 5'={$1, ..., Тогда для каждого объекта аеА можно найти расстояние г1(а,Б) (от объекта до ближайшего столпа из множества 5). Но отсутствие образа-конкурента не позволяет определить расстояние г2 (от объекта до ближайшего столпа образа-конкурента). В связи с этим, на первом этапе вводится виртуальный образ-конкурент, ближайший столп которого удален от каждого объекта выборки на фиксированное расстояние, равное г2*. Тогда в задаче таксономии РШБ-функция объекта а еА имеет вид приобретает вид:

г2*+г\(а,Я)

Эту величину мы будем называть редуцированной РИ8-функцией. Наибольший интерес для нас будет представлять среднее значение редуцированной РШБ-функции при фиксированном наборе столпов 51 по выборке:

Р*(Б)=(1/т)^Р*(а,3) (2)

аеЛ

При фиксированном числе столпов / эта величина достигает своего максимума, когда столпы из £ располагаются в центрах зон локального сгущения объектов. Таким образом, решая экстремальную задачу:

^ *(£)-> шах

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

Алгоритм РШЗ-СЛ^ег, отыскивающий приближенное решение этой задачи, на каждом шаге выбирает объект, добавление которого в список столпов мак-

12

симально увеличивает значение критерия (2). Когда же заданное число столпов достигнуто, все объекты выборки распределяются между кластерами, определяемыми этими столпами, и окончательное положение столпа для каждого кластера уточняется.

Полученный набор столпов уже может рассматриваться как готовый результат, если эксперта устраивает его качество. В противном случае кластеризация передается на второй этап работы алгоритма, называемый РШЗ-Скзэ. На этом этапе происходит процедура укрупнения таксонов, усложнения их формы. Если процедура кластеризации проведена удачно, то кластеры, относящиеся к разным классам, отделяются друг от друга зонами с пониженной плотностью объектов. А на границе кластеров, относящихся к одному классу, такого понижения плотности нет, объекты выборки там распределены достаточно равномерно. Соседние кластеры, на границах которых сохраняется характера распределения объектов, признаются принадлежащими одному классу. Это позволяет создавать таксоны произвольной формы, не обязательно линейно разделимые.

Последовательное применение РИЯ-О^ег и РИЗ-ОаББ образует алгоритм РШ8-Тах, разбивающий выборку на заданное число кластеров I. Число получаемых классов при этом может варьироваться, в зависимости от того, какое число кластеров было объединено на втором этапе. Чтобы отыскать оптимальное число кластеров из заданного диапазона (не больше Ь), необходимо последовательно построить кластеризации (этап РШБ-С^ег) для всех /<£, и по формуле (1) вычислить качество Fl каждой кластеризации. Именно то число кластеров I, при котором - является локальным максимумом

((РЫ£Р,)&(РМ <¥,)) и оказывается наилучшим. На процедуру укрупнения таксонов (этап РИБ-СЬзз) передают только варианты кластеризации, удовлетворяющие условию локальной максимальности. После второго этапа отсеиваются совпадающие варианты классификации, и такие, которые в результате объединения образуют единственный класс. Анализ оставшихся вариантов в различных модельных экспериментах показал, что все они в том или ином смысле

13

признаются человеком-экспертом «разумными» и различаются степенью детализации.

Эффективность предложенного алгоритма была подтверждена на модельных примерах и реальной задаче. На Рис.2 сравниваются результаты его работы с существующими аналогами (алгоритмами Kmeans, Fore], Scat). Для оценки качества получаемых разбиений с числом таксонов к используется величина v -средняя однородность получаемых таксонов относительно заранее известной «естественной» классификации.

Рис.2 Сравнение результатов работы пяти алгоритмов таксономии.

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

свойствами «естественных».

Понятие «естественная классификация» часто возникает при попытке формализовать понятия качества классификации. Им обычно обозначают некий

14

идеал, к которому следует стремиться при разработке методов таксономии. Знакомство с этими классификациями позволяет обнаружить ряд их интересных свойств:

• Как правило, естественные классификации имеют иерархическую структуру - в них имеются классы, подклассы, подподклассы и т.д.

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

• Важнейшим свойством является индуктивность - возможность на основе «естественной» классификации предсказывать неизвестные (скрытые) свойства объектов классов по небольшому числу известных (существенных) свойств, лежащих в основе этой классификации. Общеизвестный пример подобных предсказаний - классификация химических элементов по атомному весу в таблице Менделеева, на основе которой можно предсказывать многие физические и химические свойства этих элементов.

Таким образом, в процессе построения «естественной» классификации, необходимо не только разбивать объекты на классы, но и выбирать подмножество существенных характеристик - решать задачу вХ вместо задачи в. При этом для каждого подмножества характеристик, претендующих на звание существенных, оценивается функция качества зависит от двух составляющих - «геометрического» качества таксономии (21 в пространстве этих характеристик и качества ожидаемой предсказательной силы Qr полученных таксонов во всем признаковом пространстве. Если для оценки 2/ существует множество разных методик, то вид критерия требует дополнительных пояснений.

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

прецедентов из этого класса. Фактически же мы можем оценить только возможности прогнозирования тех признаков, которые содержатся в исходной таблице «объект-признак». Прогнозы могут быть разными по сложности и получаемой точности. Если всех пациентов госпиталя разделили на таксоны по существенным симптомам, а признак «температура тела» не вошел в их число, то для будущих прогнозов температуры можно попытаться найти закономерную связь между принадлежностью пациента к данному таксону и температурой его тела. Можно воспользоваться при этом любыми способами прогнозирования. В самом простом случае можно вычислить среднее значение температуры в таксоне и всем новым пациентам, отнесенным к этому таксону, приписывать найденное среднее значение. Такой прогноз будет явно не очень хорошим, но все же лучше, чем средняя температура по больнице.

Если совокупность прогнозируемые значений признаков, не попавших в число существенных для каждого класса г, рассматривать как столп этого класса лг|, то в качестве оценки надежности прогнозов может использоваться среднее значение РИЗ-функции, вычисленное по формуле (1), а задача построения «Естественной классификации» при этом запишется следующим образом:

<2Г (Г, Б у) = У (а, Я7)-> шах

а^А УсР(Х),]У1<п* ■

Здесь значение функции конкурентного сходства в пространстве Х\У, п*- ограничение на количество существенных признаков, а £У может быть найдено следующим образом. В пространстве характеристик 7, претендующих на роль существенных, строится разбиение, удовлетворяющее геометрическому критерию £?/> одним из существующих алгоритмов таксономии. Центры масс полученных таксонов в пространстве всех признаков X используются в качестве прогнозируемых по имени таксона значений этих признаков и образуют множество столпов 51-. А непосредственно выбор наилучшего подпространства У* осуществляется одним из алгоритмов направленного перебора, например, АсЮе1.

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

В пятой главе рассматривается наиболее общая задача комбинированного типа - задача SDX. Ее можно рассматривать как задачу представления данных в виде, удобном для дальнейшего анализа и использования человеком, который в силу особенностей своего восприятия предпочитает иметь дело с небольшим числом групп объектов (задача S), описанным в небольшом информативном подпространстве признаков (задача X). Подобное сокращенное описание должно содержать систему простых правил (задача D), в соответствии с которыми каждый новый объект может быть отнесен к той или иной группе. Кроме того, сокращенное описание выборки должно удовлетворять требованию «естественности», то есть содержать систему простых правил, по которым для нового объекта значения признаков, не вошедших в число информативных, должны восстанавливаться по значениям его информативных признаков и по общим характеристикам группы, к которой относится этот объект.

Если каждая группа объектов определяется своим типичным представителем (столпом), в качестве прогнозируемых значений признаков нового объекта берутся их значения для столпа, который оказался ближайшим к этому объекту в пространстве информативных характеристик, а для оценки надежности такого прогноза используется функция конкурентного сходства, задача SDX записывается следующим образом:

Qf (У) = У Fy (a, s* I s* = arg minpY (a, s)) -» max

f?A szSy YcXWS*.

SY = arg max ^FY(a,S)

ScA, _ A |S|Sm* a*A

Набор столпов Sy при ограничении на его мощность т* для фиксированной подсистемы признаков У отыскивается с помощью алгоритма таксономии FRiS-Тах, который в процессе работы строит набор столпов, обеспечивающий максимум среднего значения функции конкурентного сходства по выборке. Пред-

сказательная сила набора признаков У вычисляется как среднее значение конкурентного сходства в исходном пространстве X каждого объекта а исходной выборки А со столпом, ближайшим к нему в подпространстве У.

Далее рассматривается более сложная задача - построение решения задачи вБХ в виде иерархической классификации, описываемой деревом Т. Корневой вершине 1° этого дерева соответствует все множество объектов обучающей выборки А, итоговым классам классификации - висячие вершины. Поддереву в виде вершины Т и всех связанных с ней вершин следующего уровня 7]'+1, Г2'+|,

соответствует разбиение группы объектов на подгруппы. На каждом таком разветвлении может использоваться свое собственное подпространство признаков У1. Каждой промежуточной вершине (классу) ставится в соответствие свой эталонный образец (столп), который используется уже для распознавания новых объектов по дереву в соответствии со следующим итеративным правилом. Если промежуточный класс Т в подпространстве 1* разбивается на

подклассы ,Г2'+|.....Т*] с эталонами с\, с2, с'к соответственно, то при

распознавании нового объекта а, попавшего по цепочке в класс Т, он относится к тому подклассу, расстояние до эталона которого оказывается минимальным.

Каждой висячей вершине ставится в соответствие свой эталонный образец (столп) в объединенном пространстве признаков У, используемых на всех этапах классификации по дереву Т. При распознавании нового объекта а отыскивается вершина (класс), в которую он попадает, и, вычисляется функция конкурентного сходства этого объекта со столпом этого класса Т(а) в полном пространстве признаков X. Оптимизируемым при построении дерева критерием качества в этом случае является:

аеЛ

Приближенные решения для этой задачи отыскиваются за счет перехода к серии задач, каждой из которых соответствует разбиение одной висящей вер-

шины в дереве, обеспечивающее максимальное увеличение итогового функционала качества

Алгоритм РШБ-БОХ, реализующий эту идею, подтвердил свою эффективность на реальной прикладной задаче, связанной с анализом спектральных характеристик различных химических соединений.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ.

1. Показано, что РИБ-функция является эффективным базисом для решения задач распознавания образов комбинированного типа. На ее основе создан ряд алгоритмов, применимых к плохо обусловленным задачам в условиях отсутствия априорной информации о типе распределения объектов выборки, о связях между объектами и признаками.

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

3. Показано, что в процессе решения задачи БХ целесообразно опираться не на все объекты выборки, а лишь на некоторый набор эталонных образцов (столпов). Среднее значение РШЗ-функции, вычисленное с опорой на набор столпов, является наиболее эффективным критерием качества при решении задачи выбора информативной для распознавания системы признаков. Кроме того величина функции конкурентного сходства контрольного объекта с образом, к которому он был отнесен, дает возможность сопроводить принятое решение оценкой уверенности в правильности этого решения.

4. Предложен алгоритм РШЯ-Тах, опирающийся на РШБ-функции в процессе решения задачи ББ. Он позволяет строить разбиение выборки на адекватные с точки зрения человеческого восприятия кластеры и классы. Использование среднего значения РШв-функции для оценки качества таксономии позволило

автоматизировать процесс выбора оптимального числа кластеров и таксонов в создаваемой таксономии.

5. Замечено, что ключевым свойством всех анализируемых естественных классификаций являлась их высокая предсказательная способность. Формализация этого понятия, а также рассмотрение задачи построения классификации, обладающей свойствами «естественной», как задачи комбинированного типа SX, позволила сформировать критерий качества для построения таксономии с одновременным выбором системы существенных признаков. Для решения этой задачи был разработан алгоритм NatClass, который позволяет строить как одноуровневые таксономии, так и многоуровневые, представленные в виде иерархического дерева.

6. Предложенная в диссертации формулировка задачи SDX в терминах FRiS-функций позволяет использовать для ее решения все основные наработки, полученные ранее, и предложить эффективный алгоритм FRiS-SDX для построения иерархической классификации с одновременным выбором решающего правила и пространства наиболее информативных признаков.

Содержание диссертации отражено в следующих работах:

1. Борисова, И. А. Естественная классификация / И. А. Борисова, Н.Г. Загоруйко II Интеллектуальный анализ информации. Сборник трудов российско-украинского научного семинара, Киев, 19-21 мая 2004 г. - Киев: Просвета, 2004. -С. 33 -42.

2. Zagoruiko, N.G. Principles of natural classification / N.G. Zagoruiko, I.A. Boris-ova // Pattern Recognition and Image Analysis. - Germany: Springer Verlag GmbH, 2005. - vol 15. - №1. - P.27 - 29. [Принципы естественной классификации]

3. Borisova, I. A. Algorithms of Natural Classification and Systematization / I. A. Borisova, A. N. Zagoruiko, N.G. Zagoruiko // Pattern Recognition and Information Processing. Proceedings of the 8-th International Conference, Minsk, 18-20 May 2005. - Minsk, 2005. - P. 236 - 239. [Алгоритмы естественной классификации и систематизации]

4. Alves, A. Predictive Analysis of Gene Data from Human SAGE Libraries / A. Alves, N. Zagoruiko, O. Okun, O. Kutnenko and I. Borisova // Procceedings of the Workshop W10 "Discovery Challenge" ECML/PKDD, Portugal, 3-7 October 2005. -Porto, 2005. - P. 60 - 71. [Предсказывающий анализ генетических данных из библиотек Human SAGE]

5. Загоруйко, Н.Г. Выбор информативного подпространства признаков (Алгоритм GRAD) / Н.Г. Загоруйко, О. А. Кутненко, И. А. Борисова // Математические методы распознавания образов. Доклады 12-ой Всероссийской конференции, Москва, 2005. - Москва, 2005. - С. 106-109.

6. Борисова, И.А. Таксономия траекторий и восстановление структуры генных сетей / И.А. Борисова, Н.Г. Загоруйко, А.В. Ратушный, В.А. Лихошвай, Н. А. Колчанов // Анализ структурных закономерностей. Вычислительные системы. -Новосибирск, 2005 г. - выпуск 174. - С. 54-64.

7. Zagoruiko, N.G. Selection of informative subset of gene expression profiles in prognostic analysis of type 2 diabetes / N.G. Zagoruiko, O.A. Kutnenko, I. A. Boris-ova, A.N. Kiselev, A.A. Ptitsin // Proceedings of the 5-th International Conference on Bioinformatics of Genome Regulation and Structure, Novosibirsk, 16- 22 July 2006. - Novosibirsk, 2006. - Volume 1. - P. 212 - 215. [Выбор информативных профилей активности генов в прогнозировании диабета второго типа]

8. Zagoruiko, N.G. Criteria of informativeness and suitability of a subset of attributes, based on the similarity function / N.G. Zagoruiko, LA. Borisova, O.A. Kutnenko // Pattern Recognition and Information Processing. Proceedings of the 9-th International Conference, Minsk, 22-24 May 2007. - Minsk, 2007. - P. 257-261. [Критерий информативности и пригодности подмножества признаков, основанный на функции сходства]

9. Борисова, И.А Критерий информативности и пригодности подмножества признаков / И.А. Борисова, Н.Г. Загоруйко, О.А. Кутненко И Knowledge-Dialog-Solution. Proceedings of the 13-th International Conference, Varna, 18-25 June 2007. -Sofia, 2007.-P. 567-571.

10. Борисова, И.А. Использование FRiS-функции для построения решающего правила и выбора признаков(задача комбинированного типа DX) / И. А. Борисова, В.В. Дюбанов, Н.Г. Загоруйко, О.А. Кутненко // Знания. Онтологии. Теории. Материалы Всероссийской Конференции, Новосибирск, 2007. - Новосибирск,

2007.-том 1,-С. 37-44.

11. Борисова, И. А. Функция конкурентного сходства в задаче таксономии / И. А. Борисова, Н.Г. Загоруйко // Знания. Онтологии. Теории. Материалы Всероссийской Конференции, Новосибирск, 2007. - Новосибирск, 2007. - том 2. -С. 67-76.

12. Zagoruiko, N.G. Function of rival similarity in pattern recognition / N.G. Zagoruiko, I.A. Borisova, V.V. Dubanov, O.A. Kutnenko // Proceedings of the Eighth International Conference Pattern Recognition and Image Analysis, Yoshkar-Ola, 8-12 October 2007. - Yoshkar-Ola, 2007. - Vol. 2. - P. 63-66. [Функция конкурентного сходства в распознавании образов]

13. Загоруйко, Н.Г. Методы поиска ближайшего аналога в большой базе изображений / Н.Г. Загоруйко, И.А. Борисова, В.В. Дюбанов, О.А. Кутненко // Математические методы распознавания образов. Доклады 13-й Всероссийской конференции, Москва, 2007. - Москва, 2007. - С. 131-134.

14. Борисова, И.А. Алгоритм таксономии FRiS-Tax / И.А. Борисова // Научный вестник НГТУ -Новосибирск : Изд-во НГТУ, 2007. - №3. - С. 3-12.

15. Борисова, И.А. Критерии информативности и пригодности подмножества признаков, основанные на функции сходства / И.А. Борисова, Н.Г. Загоруйко, О.А. Кутненко // Заводская лаборатория. Диагностика материалов. - Москва,

2008. -№1, том 74. - С. 68-71.

16. Zagoruiko, N.G. Methods of recognition based on the function of rival similarity / N.G. Zagoruiko, I.A. Borisova, "V.V. Dyubanov, O.A. Kutnenko // Pattern Recognition and Image Analysis. - Germany: Springer Verlag GmbH, 2008. - Vol. 18, №.1. - P. 1-6. [Методы распознавания, основанные на функции конкурентного сходства]

Отпечатано в типографии Новосибирского государственного технического университета 630092, г. Новосибирск, пр. К. Маркса, 20, тел./факс (383) 346-08-57 формат 60 X 84/16 объем 1.5 п.л., тираж 100 экз.. заказ №1372 подписано в печать 07.10.08г.

Введение.

Глава 1. Формулировка задач распознавания образов основного и комбинированного типов с кратким обзором существующих подходов к их решению.

1.1. Задачи распознавания образов основных типов.

1.1.1. Формулировка задачи построения решающего правила.

1.1.2. Формулировка задачи таксономии.

1.1.3. Формулировка задачи выбора системы информативных признаков.

1.2. Задачи распознавания образов комбинированного типа.

1.2.1. Построение решающего правила + выбор признаков (DX).

1.2.2. Таксономия+выбор признаков (SX).

1.2.3. Таксономия+построение решающего правила (SD).

1.2.4. Таксономия+распознавание+выбор признаков (SDX).

Выводы по первой главе.

Глава 2. Функция конкурентного сходства в задаче DX.

2.1. Функция конкурентного сходства.

2.2. Реальная и случайная информативность в задаче DX.

2.2.1. Эффект «псевдоинформативности» в задаче DX.

2.2.2. Сравнение критериев информативности.

2.2.3. Оценка «неслучайности» выбранных подсистем.

2.2.4. Проверка на реальных данных.

2.3. Целесообразность и эффективность применения аппарата FRiS-функций в задаче DX.

2.3.1 Построение решающего правила алгоритмом FRiS-Stolp.

2.3.2. Оценка надежности распознавания конкретных объектов.

2.3.3. Алгоритм FRiS-Agent в задаче DX.

Выводы по второй главе.

Глава 3. Использование функций конкурентного сходства при решении задачи SD.

3.1. Редуцированная функция конкурентного сходства.

3.2. Алгоритм FRiS-Tax.

3.2.1 Кластеризация (этап FRiS-Cluster).

3.2.2. Построение классификации (этап FRiS-Class).

3.2.3. Выбор оптимального числа таксонов.

3.3. Примеры работы алгоритма.

3.4. Экспериментальная проверка алгоритма FRiS-Tax, сравнение с существующими аналогами.

Выводы по третьей главе.

Глава 4. Задача «естественной» классификации и ее связь с задачей комбинированного типа SX.

4.1. Дискуссионная природа термина «естественная классификация».

4.2. Специфические свойства «естественных» классификаций.

4.3. Формулировка задачи построения «естественной» классификации в терминах задач комбинированного типа.

4.3.1 Критерий качества в задаче « естественной классификации».

4.3.2 Алгоритм NatClass.

4.4. Иерархическая таксономия.

4.4.1. Иерархический NatClass.

4.4.2. Другие возможные подходы к построению иерархической естественной классификации.

4.5. Экспериментальная проверка эффективности алгоритма NatClass.

4.6. Связь FRiS-функции и предсказательной способности таксономии.Г.

Выводы по четвертой главе.

Глава 5. Использование FRiS функции для решения задачи SDX.

5.1. Формальная постановка задачи SDX.

5.1.1. Формулировка задачи SDX в терминах FRiS-функций.

5.2. Алгоритм отыскания решения задачи SDX.

5.3.Иерархическая классификация.

5.3.1. Алгоритм решения иерархической задачи SDX.

5.4. Экспериментальная проверка.

Выводы по пятой главе.

Человек обладает врожденной способностью к обработке информации, ее систематизации, обобщению, упрощению. Эта способность с древнейших времен интересовала исследователей, которые пытались понять ее механизмы. Процесс изучения способности человека производить знания продолжается до сих пор, по сути, он бесконечен. Долгое время им интересовались в основном философы, затем к ним подключились биологи, физиологи, психологи. С появлением компьютеров решение этих вопросов стало уже делом не только удовлетворения некоторого абстрактного научного любопытства. Теперь изучение и формализация человеческой способности к анализу информации, к познанию мира дает возможность частично наделять этой способностью искусственные объекты - компьютеры.

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

Одним из наиболее важных этапов обработки информации нам представляется ее систематизация и упрощение - представление в виде, доступном для понимания, более подробного исследования и дальнейшего использования. Человеком для этого используются различные приемы, многие из которых формализованы в рамках предметной области, называемой интеллектуальным анализом данных (ИАД), и относятся к задачам распознавания образов.

Упоминание о первом из них — группировке встречается еще у Демокрита в «Письме к ученому соседу». Он пишет: «Если тебе, мой друг, нужно разобраться в сложном нагромождении фактов или вещей, ты сначала разложи их на небольшое число куч по похожести. Картина прояснится, и ты поймешь природу этих вещей». Этот способ познания - создание классификационных структур на множестве объектов схожей природы широко используется наукой и в наши дни. Его формализация и развитие делается в рамках научного направления, которое называется большим количеством синонимов: таксономия, группировка, кластерный анализ, автоматическая классификация, обучение без учителя, самообучение и т.д. В задаче таксономии упрощение информации происходит за счет сокращения числа рассматриваемых объектов. Вместо изучения каждого отдельного представителя выборки появляется возможность сосредоточить внимание на изучении классов сходных объектов. Похожесть в рамках класса позволяет заменять множества объектов из этого класса неким эталонным (идеальным) образцом.

Этой задачей занимались такие известные российские и зарубежные ученые как Воронин Ю.А., Загоруйко Н.Г., Ивахненко А.Г., Шлезингер М.И., Ватанабе М.С., Себестиан Г.С, Фукунага К. и другие. Далее мы будем обозначать задачу таксономии символом S.

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

Исследованиям задачи построения решающего правило посвящено огромное количество работ. Значительный вклад в развитие этой области внесли Журавлев Ю.И., Лбов Г.С., Вапник В.Н, Червоненкис А.Я, Мазуров В.Д, Симон, Фу К., Михальский Р. С. и многие другие исследователи. Задачу построения решающего правила далее мы будем обозначать символом D.

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

Методики выбора информативной системы признаков активно разрабатывались в рамках ИАД такими исследователями как Айвазяном С.А., Барабашом, Мерилом, Грином и рядом других. Далее эту задачу мы будем обозначать символом X.

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

Объект исследований. Задача SDX считается сложной и общего подхода к ее решению не существует. Прежде чем приступить к решению этой задачи, мы рассмотрим более простые задач комбинированного типа SX, DX, SD, в каждой из которых одновременно используются два из трех описанных выше приема упрощения информации [16]. Это позволит нам создать необходимый фундамент для решения задачи SDX непосредственно. Именно задачи распознавания образов комбинированного типа являются основными объектами исследования в данной работе. Комбинированные задачи хорошо согласуются с механизмами анализа информации, используемыми человеком, и S открывают новые возможности для решения сложных плохо обусловленных прикладных задач.

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

Основные направления исследований. Требование согласованности алгоритмов здесь оказывается очень важным. Для его выполнения необходимо иметь единый базис для решения всех задач. В этой работе таким базисом стали функции конкурентного сходства (FRiS-функции) [68]. Выбор функций конкурентного сходства в качестве основы для большинства представленных алгоритмов решения задач комбинированного типа объясняется еще и тем, что основным методом исследования для нас является моделирование интеллектуальной деятельности человека при решении комбинированных задач. FRiS-функция оказывается при этом особенно эффективной, так как она моделирует психофизиологические особенности человеческого восприятия при оценке близости между объектами.

Методы исследований Помимо имитационного моделирования для решения задач распознавания образов комбинированного типа привлекается аппарат методов оптимизации и математическая статистика.

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

Именно задачам комбинированного типа, их связям с естественно-человеческой методологией познания, методам решения этих задач, анализу возможностей алгоритмов комбинированного типа, и областям их-применения посвящена данная диссертация.

На защиту выносятся следующие основные результаты:

• В рамках исследования применимости FRiS-функций показана их эффективность в качестве критерия информативности при решении задачи одновременного построения решающего правила и выбора наиболее информативного подпространства признаков. Предложена методика оценки надежности получаемых информативных систем признаков, их «неслучайности». Также предложена методика оценки надежности распознавания каждого нового объекта при использовании решающих правил, полученных с помощью алгоритма FRiS-Stolp.

• Разработан алгоритм FRiS-Tax для решения задачи комбинированного типа - одновременного построения таксономии и решающего правила, ее описывающего. Этот алгоритм не только достаточно точно воспроизводит действия человека эксперта при решении задач таксономии в пространствах малых размерностей, но и позволяет автоматически определять оптимальное число таксонов из заданного диапазона.

• Сформулированы основные требования, предъявляемые к «естественным» классификациям. Установлена связь между задачей построения «естественной» классификации и одной из задач распознавания образов комбинированного типа — задачей построения таксономии с одновременным выбором наиболее информативного подпространства признаков. Для решения данной задачи разработан алгоритм NatClass.

• Сформулирована наиболее сложная задача распознавания образов комбинированного типа - SDX - задача одновременного построения таксономии и решающего правила для ее описания в наиболее информативном признаковом пространстве. Предложена методика ее решения, позволяющая максимально структурировать массивы данных в случае отсутствия какой бы то ни было дополнительной информации относительно природы этих данных.

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

Достоверность и обоснованность предлагаемых решений подтверждается результатами применения предложенных алгоритмов как к модельным, так и к реальным задачам различной природы.

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

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

• KDS-2001, 2007 (Knowledge-Dialog-Solutions),

• PRIA-2004, 2007 (Pattern Recognition and Image Analysis),

• PRIP-2005, 2007 (Pattern Recognition and Image Processing),

• MMPO-12, 13 (Математические Методы Распознавания Образов),

• ACIT-SE-2005 (Automation, Control and Information Technology),

• BGRS-2006 (Bioinformatics of Genome Regulation and Structure),

• 30HT-2007 (Знания, Онтологии, Теории).

Отдельные этапы работы прошли экспертизу в ходе выполнения проектов, поддержанных грантами РФФИ (проекты № 02-01-00082-а, №05-01-00241-а).

Публикации. По теме диссертации опубликованы 16 работ, из них 2 научные статьи в журналах, входящих в перечень изданий, рекомендованных ВАК РФ, 2 научные статьи в ведущих рецензируемых журналах, 2 - в сборниках научных трудов, 10 - в сборниках трудов конференций.

Структура работы. Диссертационная работа изложена на 121 страницах и состоит из введения, обзора литературы (глава 1), четырех глав, содержащих основные результаты, и заключения. Иллюстративный материал представлен 24 рисунками и 1 таблицей. Список литературы включает 77 ссылок.

Выводы по пятой главе

1.Задача SDX (одновременного выбора наилучшего разбиения множества объектов на классы, решающего правила для их распознавания и наиболее информативного подпространства признаков) может рассматриваться как задача систематизации и структуризации информации в самом общем виде [76].

2. Формулировка этой задачи в терминах FRiS-функций позволяет использовать для ее решения все основные наработки, полученные в данной работе, и предложить эффективный алгоритм для построения иерархической классификации с одновременным выбором решающего правила и пространства наиболее информативных признаков.

Заключение

Разработка методов решения задач распознавания образов комбинированного типа является актуальным направлением исследований. Сами задачи такого вида лучше согласуются с общими механизмами анализа информации, используемыми человеком. Объясняется это тем, что в силу особенностей восприятия человеческий мозг обычно решает несколько базовых задач по систематизации и структуризации новых данных одновременно и согласованно. Таким образом, рассматривая возникающие прикладные задачи анализа данных как задачи комбинированного типа, мы можем имитировать действия человека-эксперта и в некоторых случаях заменять его. Кроме того, комбинированный подход позволяет минимизировать число дополнительных предположений относительно анализируемой выборки, а получаемые решения оказываются более устойчивыми к ошибкам и выбросам в исходных данных. В связи с этим особенно полезным комбинированный подход оказывается при решении задач Data Mining в условиях, которые не позволяют применить методы классической статистики. Ярким примером являются задачи, в которых число объектов М меньше числа описывающих их характеристик N и, кроме того, априорная информация о распределениях объектов, о зависимостях между объектами и между признаками отсутствует.

Наиболее общей задачей комбинированного типа, интересующей нас в данном исследовании, является задача SDX, когда одновременно решается задача таксономии (S), построения решающего правила для ее описания (D) и выбора информативного пространства признаков (X). Для корректного решения этой сложной задачи необходимо уметь решать все три основные задачи распознавания образов согласовано.

Единым базисом для решения всех задач распознавания образов в данной работе является функция конкурентного сходства. Именно использование этой функции, имитирующей особенности человеческого восприятия при определении меры похожести объектов и явлений, позволило нам создать ряд алгоритмов для решения более простых комбинированных задач SX, DX, SD и перейти к решению интересующей нас в первую очередь задачи SDX.

Перечислим основные результаты, полученные в данной работе:

1. В рамках анализа существующих подходов к решению задачи DX был исследован процесс возникновения «псевдоинформативных» признаков в плохо обусловленных задачах распознавания. Продемонстрировано, что критерий выбора информативной системы признаков для дальнейшего распознавания, основанный на функции конкурентного сходства (Fs), оказывается более устойчивым к эффекту «псевдоинформативности» и позволяет получать лучшие результаты, в сравнении с наиболее популярными критериями выбора признаков. Кроме того, показано, что сравнение значения меры (Fs), вычисляемой для наилучшей информативной подсистемы признаков на основе обучающей таблицы, и аналогичной величины, вычисленной на серии случайных таблиц того же размера, позволяет получить качественную оценку степени «неслучайности» выбранного подпространства признаков.

Было обнаружено, что в процессе решения задачи DX целесообразно опираться не на все объекты выборки, а лишь на некоторый набор эталонных образцов (столпов). Среднее значение функции конкурентного сходства, вычисленное с опорой на набор столпов, является наиболее эффективным критерием выбора информативной для распознавания системы признаков. Кроме того, величина функции конкурентного сходства контрольного объекта с образом, к которому он был отнесен, дает возможность сопроводить принятое решение оценкой уверенности в правильности этого решения.

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

3. При анализе наиболее удачных «естественных» классификаций было обнаружено, что ключевым их свойством является высокая предсказательная способность. Формализация этого понятия, а также рассмотрение задачи автоматического построения классификации, обладающей свойствами «естественной», как задачи комбинированного типа SX, позволила сформировать новый критерий качества для построения таксономии с одновременным выбором системы существенных признаков. Для ее решения был разработан алгоритм NatClass, который позволяет строить таксономии, обладающие свойствами «естественных», в виде иерархического дерева.

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

Формулировка задачи SDX в терминах FRiS-функций позволяет использовать для ее решения все основные наработки, полученные в данной работе, и предложить эффективный алгоритм FRiS-SDX для построения иерархической классификации с одновременным выбором решающего правила и отысканием пространства наиболее информативных признаков.

5. Все предложенные в работе алгоритмы проверялись как на различных модельных задачах, так и на реальных данных. Такая проверка подтвердила их применимость и эффективность в процессе решения задач распознавания образов комбинированного типа. Кроме того, большая часть описанных здесь алгоритмов вошла в пакет программ «Спектран» для интеллектуального анализа спектральных характеристик химических веществ, созданного по заказу Института Криминалистики ФСБ. Данная разработка получила высокую оценку заказчика.

1. Айвазян, С.А. Прикладная статистика: Классификация и снижение размерности / С.А. Айвазян, В.М. Бухштабер, И.С. Енюков, Л.Д. Мешалкин. -Москва: Финансы и статистика, 1989. 607 с.

2. Айвазян, С.А. Прикладная статистика: Основы моделирования и первичная обработка данных / С.А. Айвазян, И.С. Енюков, Л.Д. Мешалкин. -Москва: Финансы и статистика, 1983. — 471 с.

3. Аркадьев, А.Г. Обучение машины классификации объектов / А.Г. Аркадьев, Э.М. Браверманн. Москва: Наука, 1971. - 192 с.

4. Боровков, А.А. Математическая статистика / А.А. Боровков. -Новосибирск: Наука, 1997. 772 с.

5. Вапник, В.Н. Алгоритмы и программы восстановления зависимостей / В.Н. Вапник, Т.Г. Глазкова, В.А. Кощеев, А. И. Михальский, А.Я. Червоненкис; Под редакцией В. Н. Вапника. М.: Наука, Главная редакция физико-математической литературы, 1984. - 816 с.

6. Вапник, В.Н. Теория распознавания образов / В.Н. Вапник, А.Я. Червоненкис. Москва: Наука, 1974. - 415 с.

7. Витяев, Е.Е. Извлечение знаний из данных. Компьютерное познание. Модели когнитивных процессов / Е.Е. Витяев. Новосибирск: Издательство НГУ, 2006. - 293 с.

8. Воронин Ю.А. Введение в теорию классификаций / Ю.А. Воронин. -Новосибирск, 1982. 194 с.

9. Горелик, А.Л. Современное состояние проблемы распознавания / А.Л. Горелик, И.Б. Гуревич, В.А. Скрипкин. Москва: Радио и связь, 1985. - 160 с.

10. Жук, Е.Е. Устойчивость в кластер анализе многомерных наблюдений / Е.Е. Жук, Ю.С. Харин. Минск: Белгосуниверситет, 1998. - 240 с.

11. Журавлев, Ю.И. Распознавание: Математические методы. Программная система. Практические применения / Ю.И. Журавлев, В.В. Рязанов, О.В. Сенько. Москва: Фазис, 2006. - 176 с.

12. Забродин, В.Н. О критериях естественности классификаций / В.Н. Забродин // НТИ, сер.2, 1981. - №8. - С. 92-112.

13. Загоруйко, Н.Г. Прикладные методы анализа данных и знаний / Н.Г. Загоруйко. Новосибирск: Издательство И.М., 1999. — 270 с.

14. Загоруйко, Н.Г. Методы распознавания и их применение / Н.Г. Загоруйко.- Москва: Сов. Радио, 1972. 208 с.

15. Ивахненко, А.Г. Применение принципа самоорганизации для объективной кластеризации изображений, системного анализа и долгосрочного прогноза / А.Г. Ивахненко // Автоматика. 1986. - №1. С. 5-11.

16. Колмогоров, А.Н. "К вопросу о пригодности найденных статистическим путем формул прогноза"/ А.Н. Колмогоров // Заводская лаборатория. 1933. -№1. - С. 164-167.

17. Котюков, В.И. Формирование решающих правил / В.И. Котюков // Вычислительные системы. Новосибирск, 1971. - Вып.44. - С. 37-48.

18. Красилов, В.А. Нерешенные проблемы теории эволюции / В.А. Красилов.- Владивосток: Изд-во ДВГУ, 1986. 138 с.

19. Лапко, А.В. Непараметрические системы обработки информации / А.В. Лапко, С.В. Ченцов. Москва: Наука, 2000. - 352 с.

20. Лбов, Г.С. Построение дерева разбиений в задаче группировки объектов с использованием логических функций / Г.С. Лбов, Т.М. Пестунова // Анализ данных в экспертных системах: Вычислительные системы. Новосибирск, 1986.-Вып. 117. С. 63-77.

21. Лбов, Г.С. Логические решающие функции и вопросы статистической устойчивости решений / Г.С. Лбов, Н.Г. Старцева. Новосибирск: Издательство ИМ., 1999.-212 с.

22. Мазуров, В.Д. Метод комитетов в распознавании образов / В.Д. Мазуров // Метод комитетов в распознавании образов. Свердловск: Изд. УО АН СССР, 1974.-С. 10-40.

23. Миленький, А.В. "Классификация сигналов в условиях неопределенности / А.В. Миленький. Москва: Советское радио, 1975. - 328 с.

24. Раудис, Ш.Ю. Об определении объема обучающей выборки линейного классификатора / Ш.Ю. Раудис // Вычислительные системы. Новосибирск, 1967.-Вып.28.-С. 79-88.

25. Себестиан, Г.С. Процессы принятия решений при распознавании образов/ Г.С. Себастиан. Киев: Техника, 1965. — 151 с.

26. Смирнов, Е.С. Таксономический анализ / Е.С. Смирнов. Москва: МГУ, 1969.-352 с.

27. Ту, Д. Принципы распознавания образов / Дж. Ту, Р. Гонсалес. Москва: Мир, 1978.-411 с.

28. Фу, К. Последовательные методы в распознавании образов и обучении машин / К. Фу. Москва: Наука, 1971. - 256 с.

29. Фукунага К. Введение в статистическую теорию распознавания образов / К. Фукунага. Москва: Наука, 1979. - 367 с.

30. Шлезингер, М. Десять лекций по статистическому и структурному распознаванию /М. Шлезингер, В. Главач. Киев: Наукова Думка, 2004. - 548 с.

31. Шлезингер, М.И. О самопроизвольном разделении образов / М.И. Шлезингер // Читающие автоматы и распознавание образов: сб. науч. трудов -Киев: Наукова думка, 1965. С. 46-61.

32. Battiti, R. Using Mutual Information for Selecting Features in Supervised Neural Net Learning / Battiti R. // IEEE Trans. Neural Networks. 1994. - vol. 5, no. 4.-P. 537-550.

33. Boser, E. A training algorithm for optimal margin classifiers / E. Boser, I.M. Guyon, V.N. Vapnik // 5th Annual ACM Workshop on COLT. Pittsburgh, 1992. -P. 144-152.

34. Dempster, A. Maximum likelihood from incomplete data via the EM algorithm / A. Dempster, N. Laird, D. Rubin // Journal of the Royal Statistical Society, Series B. 1977. - Vol. 39(1). - P. 1-38.

35. Dy, J.G. Feature Subset Selection and Order Identification for Unsupervised Learning / J.G. Dy, C.E. Brodley // Proc. 17th Int'l Conf. Machine Learning. 2000. - P. 247-254.

36. Everitt, B.S. Cluster analysis. Third edition. / B. Everitt. London: Edvard Arnold, 1993.- 170 pp.

37. Fukunaga, K. A criterion and an algorithm for grooping data / K. Fukunaga, W.L.G. Koontz // IEEE Trans. Сотр., С-19. 1970. - P. 917-923.

38. Gennari, J.H. Models of incremental concept formation / J.H. Gennari, P. Langeley, D. Fisher// Artificial Intelligence 40. 1989. - P. 11 -61.

39. John, G. Irrelevant features and the subset selection problem / G. John, R. Kohavi, K. Pfleger // Machine Learning: Proc. Of the 11-th Int. Conf. Morgan Kaufmann, 1994. - P.121-129.

40. Kim, Y. Feature Selection in Unsupervised Learning via Evolutionary Search / Y. Kim, W. Street, F. Menczer // Proc. Sixth ACM SIGKDD Int'l Conf. Knowledge Discovery and Data Mining. -2000. P. 365-369.

41. Kira, K. The Feature Selection Problem: Traditional Methods and a New Algorithm / K. Kira, L. Rendell // Proc. 10th Nat'l Conf.Artificial Intelligence (AAAI-92). 1992. - P. 129-134.

42. Kohavi, R. Wrappers for Feature Subset Selection / R. Kohavi, G.H. John // Artificial Intelligence. 1997. - vol. 97, nos. 1-2. - P. 273-324.

43. Kwak, N. Input Feature Selection by Mutuallnformation Based on Parzen Window / N. Kwak, C.-H. Choi // IEEE Trans. Pattern Analysis and Machine Intelligence. 2002. - vol. 24, no. 12. - P. 1667-1671.

44. Law, M.H.C. Simultaneous Feature Selectio and Clustering Using Mixture Models / M.H.C. Law, M.A.T. Figueiredo, A.K. Jain // IEEE Trans. Pattern Analysis and Machine Intelligence. 2004. - vol. 26, no. 9. - P. 1-13.

45. MacQueen J. "Some methods for classification and analysis of multivariate observations / J. MacQueen // Proceedings of the 5th Berkley Symposium on Mathematical Statistic and Probability. University of California Press, 1967. -Vol.1.-P. 281-297.

46. Merill, T. On the effectiveness of receptors in recognition systems / T. Merill, О. M. Green // IEEE Trans. Inform. Theory. 1963. - Vol. IT-9. - P. 11-17.

47. Michalski, R.S. Machine Learning and Data Mining, Methods and Applications / R. S. Michalski, I. Bratko, M. Kubat. N.Y.: John Wiley & Sons, 1998.-472 pp.

48. Mitra, P. Unsupervised Feature Selection Using Feature Similarity / P. Mitra, C.A. Murthy // IEEE Trans. Pattern Analysis and Machine Intelligence. 2002. -Vol. 24, No. 3. - P. 301-312.

49. Niemann, H. Pattern analysis and understanding / H. Niemann. Springer-Verlag, 1990. 371 pp.

50. Pawalk, Z. Rough sets: preset state and the future / Z. Pawalk // Foundations of Computing and Decision Sciences. 1993. - Vol. 18(3-4). - P. 157-166.

51. Robnik-Sikonja, M. Theoretical and Empirical. Analysis of ReliefF and RReliefF / M. Robnik-Sikonja, I. Kononenko // Machine Learning. 2003. - Vol. 53. -P. 23-69.

52. Sahami, M. Using Machine Learning to Improve Information Access / M. Sahami // PhD thesis, Computer Science Dept., Stanford Univ. 1998. - 240 p.

53. Siedlecki, W. "On automatic feature selection / W. Siedlecki, J. Sklansky // Int. Journal of Patt. Rec. and Art. Intel. 1988. - Vol. 2 (2). - P. 179-220.

54. Siedlecki, W. A note on genetic algorithms for large-scale feature selection"/ W. Siedlecki, J. Sklansky // Pattern Recognition Letters. 1989. - Vol.10. - P. 335347.

55. Thrun, S.B. The Monk's problems: A performance comparison of different learning algorithms / S. B. Thrun et al. // Technical Report CMU-CS-91-97. -Carnegie Mellon University, 1991. 112 pp.

56. Watanabe, M.S. Knowing and Guessing: Formal and Qualitative Study/ M.S. Watanabe. N.Y.: John Wiley, 1969. 267 pp.

57. Xu, L. Best first strategy for feature selection / L. Xu, P. Yan, T. Chang // 9-Int. Conf. on Patt. Rec. IEEE Сотр. Society Press, 1989. - P. 706-708.

58. Борисова, И.А. Естественная классификация / И.А. Борисова, Н.Г. Загоруйко // Интеллектуальный анализ информации. Сборник трудов российско-украинского научного семинара, Киев, 19-21 мая 2004 г. Киев: Просвгга, 2004. - С. 33 - 42.

59. Zagoruiko, N.G. Principles of natural classification / N.G. Zagoruiko, I.A. Borisova // Pattern Recognition and Image Analysis. Germany: Springer Verlag GmbH, 2005. - vol 15, №1. - P.27 - 29. Принципы естественной классификации.

60. Борисова, И.А. Использование FRiS-функции для построения решающего правила и выбора признаков(задача комбинированного типа DX) / И.А. Борисова, В.В. Дюбанов, Н.Г. Загоруйко, О.А. Кутненко // Знания. Онтологии.

61. Теории. Материалы Всероссийской Конференции, Новосибирск, 2007. -Новосибирск, 2007. том 1. - С. 37-44.

62. Борисова, И.А. Функция конкурентного сходства в задаче таксономии / И.А. Борисова, Н.Г. Загоруйко // Знания. Онтологии. Теории. Материалы Всероссийской Конференции, Новосибирск, 2007. Новосибирск, 2007. - том 2. - С. 67-76.

63. Борисова, И.А. Алгоритм таксономии FRiS-Tax / И.А. Борисова // Научный вестник НГТУ Новосибирск : Изд-во НГТУ, 2007. - №3. - С. 3-12.

64. Борисова, И.А. Критерии информативности и пригодности подмножества признаков, основанные на функции сходства / И.А. Борисова, Н.Г. Загоруйко, О.А. Кутненко // Заводская лаборатория. Диагностика материалов. Москва, 2008. - №1, том 74. - С. 68-71.

65. Борисова, И.А. Задачи комбинированного типа в интеллектуальном анализе данных"/ И.А. Борисова, Н.Г. Загоруйко // Сборник научных трудов научной сессии МИФИ-2008. Москва, 2008. - том 10. - С. 209-210.