_учебник_ Журавлев Ю.И. Распознавание. Математические методы. Программная система. Практические применения (2005) (_учебник_ Журавлев Ю.И. Распознавание. Математические методы. Программная система. Практические применения (2005).doc), страница 2

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

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

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

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

1. Алгоритмы распознавания, основанные на вычислении оценок. Распознавание осуществляется на основе сравнения распознаваемого объекта с эталонными по различным наборам признаков, и использования процедур голосования. Оптимальные параметры решающего правила и процедуры голосования находятся из решения задачи оптимизации модели распознавания - определяются такие значения параметров, при которых точность распознавания (число правильных ответов на обучающей выборке) является максимальной /25,26, 80/.

2. Алгоритмы голосования по тупиковым тестам. Сравнение распознаваемого объекта с эталонными осуществляется по различным «информативным» подмножествам признаков. В качестве подобных подсистем признаков используются тупиковые тесты (или аналоги тупиковых тестов для вещественнозначных признаков) различных случайных подтаблиц исходной таблицы эталонов /15, 25, 26, 80/.

3. Алгоритмы голосования по логическим закономерностям.

По обучающей выборке вычисляются множества логических закономерностей каждого класса – наборы признаков и интервалы их значений, свойственные каждому классу. При распознавании нового объекта вычисляется число логических закономерностей каждого класса, выполняющихся на распознаваемом объекте. Каждое отдельное «выполнение» считается «голосом» в пользу соответствующего класса. Объект относится в тот класс, нормированная сумма «голосов» за который является максимальной. Настоящий метод позволяет оценивать веса признаков, логические корреляции признаков, строить логические описания классов, находить минимальные признаковые подпространства /76, 77, 81/.

4. Алгоритмы статистического взвешенного голосования.

По данным обучающей выборки находятся статистически обоснованные логические закономерности классов. При распознавании новых объектов вычисляется оценка вероятности принадлежности объекта к каждому из классов, которая является взвешенной суммой «голосов» /37, 56, 70, 78, 80/.

5. Линейная машина.

Для каждого класса объектов находится некоторая линейная функция. Распознаваемый объект относится в тот класс, функция которого принимает максимальное значение на данном объекте. Оптимальные линейные функции классов находятся в результате решения задачи поиска максимальной совместной подсистемы системы линейных неравенств, которая формируется по обучающей выборке. В результате находится специальная кусочно-линейная поверхность, правильно разделяющая максимальное число элементов обучающей выборки /19, 46/.

6. Линейный дискриминант Фишера.

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

7. Метод к-ближайших соседей.

Классический статистический метод. Распознаваемый объект относится в тот класс, из которого он имеет максимальное число «соседей». Оптимальное число соседей и априорные вероятности классов оцениваются по обучающей выборке /19/.

8. Нейросетевая модель распознавания с обратным распространением

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

9. Метод опорных векторов.

Метод построения нелинейной разделяющей поверхности с помощью опорных векторов. В новом признаковом пространстве (спрямляющем пространстве) строится оптимальная разделяющая гиперплоскость, представляющая собой нелинейную поверхность в исходном признаковом пространстве. Построение данной поверхности сводится к решению задачи квадратичного программирования /62/.

10. Алгоритмы решения задач распознавания коллективами различных распознающих алгоритмов.

Задача распознавания решается в два этапа. Сначала независимо применяются различные алгоритмы Системы. Далее автоматически находится оптимальное коллективное решение с помощью специальных методов-«корректоров». В качестве корректирующих методов используются различные подходы /25, 26, 69, 84/.

11. Методы кластерного анализа (автоматической классификации или обучения без учителя) /19/.

Используются следующие известные подходы:

- алгоритмы иерархической группировки;

- кластеризация c критерием минимизации суммы квадратов отклонений;

- метод к-средних.

Возможно решение задачи классификации как при заданном, так и неизвестном числе классов.

12. Алгоритм построения коллективных решений задачи кластеризации.

Задача кластеризации решается в два этапа. Сначала находится набор различных решений (в виде покрытий или разбиений) при фиксированном числе кластеров с помощью различных алгоритмов Системы. Далее находится оптимальная коллективная кластеризация в результате решения специальной дискретной оптимизационной задачи /50/.

Поскольку для практического пользователя важнейшим моментом является оценка точности распознавания алгоритмов при решении новых задач, разработаны программные средства автоматического контроля качества распознавания и прогноза, а также оценки знаний. Система разработана для персональных компьютеров Pentium 200 и выше под управлением операционных систем Windows 95 OSR2, Windows 2000, Windows XP.

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

• обработка данных социологических опросов;

• прогнозирование тенденций изменения макроэкономических показателей;

• анализ финансовых данных и прогноз финансовых показателей;

• оценка экономического состояния предприятий и перспектив их инвестирования;

• проблемы прогнозирования экологических последствий по малым выборкам прецедентов;

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

• задачи геологического прогнозирования;

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

• задачи прогнозирования свойств новых органических соединений в химии на основе имеющегося банка исследованных органических соединений;

• обработка и анализ данных в биологии, с целью оптимизации селекционных и генетических исследований;

• обширный круг задач распознавания изображений.

Основные отличительные признаки созданного продукта от имеющихся аналогов состоят в следующем:

- разнообразие имеющихся методов и более широкие их практические возможности;

- способность автоматической обработки больших массивов данных;

- возможность решения задач прогноза и распознавания редких или уникальных событий и процессов (исследование непредставительных или мало репрезентативных выборок);

- способность обработки разнотипных, частично-противоречивых и неполных данных;

- использование оригинальных разработок авторов (алгоритмы вычисления оценок, модели частичной прецедентности, коллективные методы распознавания и кластеризации, и другие), отсутствующих в аналогах данного проекта;

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

Настоящая система и ее предшественники (пакеты прикладных программ ПАРК /29/, ОБРАЗ /9/, диалоговая система ДИСАРО /23/, системы ЛОРЕГ /6/ и TaxonSearch /79/) использовались для решения и исследования многочисленных прикладных задач, многие из которых получили практическое внедрение.

Приложения в области бизнеса и финансов:

- оценка стоимости квартир по ее внутренним и внешним характеристикам (жилая площадь, строительный материал дома, местонахождение, этаж, удаленность от станции метро, и др.;

- оценка экономического состояния предприятий легкой промышленности по комплексу финансовых показателей и структуре рабочего персонала;

- подтверждение кредитных карточек;

- оценка стоимости жилья в частном секторе г.Бостона;

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

Приложения в медицине и здравоохранении:

- кластеризация возрастных распределений населения

- распознавание рака груди;

- прогноз результатов лечения остеогенной саркомы;

- прогноз динамики депрессивных синдромов;

- диагностика инсульта;

- прогноз результатов лечения рака мочевого пузыря;

- прогноз состояния пациента через год после сердечного приступа по данным эхокардиограмм;

- диагностика сердечных сосудов;

- прогноз летального исхода при гепатите;

- прогноз диабета;

- диагностика меланомы по комплексу геометрических и радиологических признаков;

- оценка степени тяжести заболевания пневмонией.

Задачи технической диагностики:

- распознавание солеобразования в нефтедобывающем оборудовании;

- контроль состояния технических устройств.

Приложения в сельском хозяйстве:

- прогноз урожайности пшеницы по состоянию посевов за 2 и за 4 недели до созревания;

- распознавание преобладающих пород в лесных массивах по данным дистанционного зондирования.

Приложения в химии, физике и биологии:

- распознавание мест локализации протеина;

- прогноз свойств твердых сплавов стали;

- прогноз свойств новых неорганических соединений;

- распознавание наличия особенностей в ионосфере по виду отраженного сигнала.

Приложения в геологии:

- распознавание месторождений редких металлов и нефти.

Приложения в области обработки изображений:

- распознавание рукописных цифр;

- распознавание трехмерных объектов.

Иллюстративные примеры практических применений системы РАСПОЗНАВАНИЕ приведены в четвертой главе.

Настоящая монография выполнена при поддержке Российского фонда фундаментальных исследований (проекты №02-01-08007 инно, 02-01-00558, 03-01-00580, 02-07-90134, 02-07-90137) и Программы №17 «Параллельные вычисления и многопроцессорные вычислительные системы» Президиума РАН.

Часть книги написана молодыми исследователями Бирюковым А.С. (глава 5), Ветровым Д.П. (разд. 1.4.4, 3.6, 3.8, 3.10, 3.11, 3.12), Кропотовым Д.А. (разд. 3.7, 3.8, 3.10, 3.11, 3.13). В авторский коллектив программной системы входят также и другие исследователи: Докукин А.А., Катериночкина Н.Н., Обухов А.С., Романов М.Ю., Рязанов И.В., Челноков Ф.Б.

Практическая реализация системы РАСПОЗНАВАНИЕ выполнена в ООО «Центр технологий анализа и прогнозирования «РЕШЕНИЯ» при поддержке Фонда содействия развитию малых форм предприятий в научно-технической сфере. В следующей версии системы РАСПОЗНАВАНИЕ предполагается расширить пакет методов распознавания и кластерного анализа. Будут включены решающие деревья в задачах распознавания, новые алгоритмы поиска логических закономерностей, алгоритм восстановления компонент смесей нормальных выборок и проекционный метод кластерного анализа, алгоритмы генерации новых информативных сложных признаков и минимизации признаковых пространств, новые средства визуализации данных и знаний. Система будет адаптирована для решения задач прогнозирования дискретных событий по выборкам многомерных данных. Дополнительная информация о системе, новости по ее модификации, а также сведения о возможности ее приобретения размещаются по адресу http://www.solutions-center.ru.

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