Реферат: Некоторые подходы к задачам распознавания и их приложениям
НЕКОТОРЫЕ ПОДХОДЫ К ЗАДАЧАМРАСПОЗНАВАНИЯ
ОБРАЗОВ И ИХ ПРИЛОЖЕНИЯМ
Е. Т. РАМАЗАНОВ
Сейчас статистические исследования развиваются внаправлении научногопредсказывания, прогнозирования социально- экономической среды. Один из подходоврешение вопроса прогнозирование заключается в решении задач классификаций.
Одно из условий развития науки в направлении научногопрогнозирования заключается в возможностях современной ЭВМ, которые позволяютобрабатывать огромные массивыинформации.
Известно что существует множество подходов решений вопроса научного прогнозирования, такиекак эксперимент, компьютернаямоделирования. Возникает вопрос, на сколько можно доверятьрезультатам решений предсказываниие, и, вообще,достоверен ли полученный результат, насколько разница она с действительностью.Безусловно что решая конкретную заданную задачу,каждый метод имеет свои плюсы и минусы и исследователь используя тот или инойметод стремится к тому что бы ошибка разницы была достаточномаленькой,и если уж совсем ошибкине возможно устранить, то оценить их(здесьвопрос достоверности он переносит в иное поле,исследовательрешает вопрос объективно имитирует лиреальный процесс или явление созданная модель.или. Строит критерий качества т.е. применяетидей оптимизации. Если да то он доверяет результату ). Оценитьошибку достоверности предсказывание порой и невозможно сделать ибостатистические оценки гипотез вероятностны.
Описанный здесь подход может быть эффективен с точки зрение достоверного предсказывания.
Задачаклассификаций тесно связана с такими дисциплинами как математическая статистика,теория вероятностей, кластерный анализ. Было проделана огромная работа поразработке методов и подходов решений задач классификаций. Фундаментомпослужили такие работы как Дж. Хартигана, Миркина, Дюрана М.Б., Дж. Вэн Райзена, Айвазяна. и др.
Решение задачи классификаций основана на кластерноманализе.
Изложенныездесь основные идей кластерного анализа основываются на работах [2 ]и[ 3].
Пусть множество Т=( Т 1Т2 Т3 ,…, Тn) обозначает nобьектов .
Предположим,что существует некоторое множествонаблюдаемых
показателейили характеристик. Обозначим это множество
С=(С1 С2 С3,… ., Ср); этими характеристиками обладает каждый индивид из множества Т. Наблюдаемыехарактеристики могут быть количественными или качественными. Наблюдениечасто называют измерениями. Результатизмерение i-й характеристики(измерение ) Tj–обьекта обозначим хij , а вектор Хj=[ хij] размером рХ1 будет отвечать каждому рядуизмерений для j — го обьекта.Таким образом исследователь множеством
Х=(Х1 Х2Х3 ,…, Хp) описывает множество Т.
Множество Х может представлено как к точек в р — мерном евклидовом пространстве Ер .
Задача кластерного анализа заключается втом чтобы на оснований данных вмножестве Х разбить множество Т на m-классов m<n.
Так чтобы, каждый обьект принадлежал одному и только одному подмножеству разбиение ,ичто бы обьекты принадлежащие одному и тому жеклассу были сходными в то время как обьектыразличных классов были бы разнородными.
Разбиение здесь следует понимать как разделение множество Т на определенноечисло непустых попарно непересекающихсяподмножеств.
Решение задачи кластерного анализа являетсяразбиение удовлетворяющее некоторому критерию оптимальности. в качествекритерия может быть функционал например сумма квадратов отклонений
W=<img src="/cache/referats/19129/image002.gif" v:shapes="_x0000_i1025">=<img src="/cache/referats/19129/image004.gif" v:shapes="_x0000_i1026"> xi-измерениеi-го обьекта.
Критерий оптимальности показывает когда мыполучили нужное разбиение.
Очевидно чтобы решить задачу кластерногоанализа необходимо количественно определить понятия сходства иразнородности .
Задача была бы решена если Тi Тj обьекты попадали в один и тот же класс всякий раз когда расстояние междуточками ХiХj былобы достаточным малым и ,наоборот, обьекты попадали бы в разные классы когда между соответствующими точками расстояние было бы достаточно большим.
Расстояние d(XiXj) между точками ХiХj p мерном евклидовом пространстве можно задать положительно определенной функцией, котораяявляется метрикой и удовлетворяет аксиомам метрики. Отметим что функция расстояние d(XiXj) задает соответственно сходствомежду обьектами ТiТj . Существует множество видов функцийрасстояние использующий в евклидовомпространстве.например евклидова метрика, Л норма, расстояние Махаланобиса. приведем лишьевклидова метрику
d(XiXj)=<img src="/cache/referats/19129/image006.gif" v:shapes="_x0000_i1027"> ;
Расстояние между nобьектами можно задать в виде симметричной матрицы размером nХn. Такую матрицу иногда называют матрицей связей.
Также можно определить меру сходства. Мерасходства s(XiXj) положительно определенная функция иудовлетворяет следушимусловиям:
1. s(Xi Xi)=1;
2. s(Xi Xj)=s(Xj Xi) ;
3. s(XiXj) определена в интервале [0 1] ;
мы можем задать меру сходство с помощью функций расстояние
например:
s(XiXj)=1/1+d(Xi Xj) ;
Существуетмножество методов классификаций.описаниеэтих методов и принципов вы можете найтив работе 3. Интересен аппроксимационный подход. Пусть имеется матрица связей D
размером nxn. Рассмотрим отношение эквивалентности Rn, которое порождает разбиение множество Х на непустые mклассы
Rn=(RnRn Rn…Rn). представим Rkв виде бинарной матрицы. Элемент матрицы равны 1, если обьекты лежат в одном классе и равны 0 в противномслучае. Требуется найти разбиение сбулевой матрицей Rn, которая бы в наибольшей мересоответствовала матрице связей. Как сопоставить матрицу связей Dи матрицу Rnдруг с другом. В работе [6] предлагают, взвешивать матрицу Rn, вводя некоторыйкоэффицент маштаба <img src="/cache/referats/19129/image008.gif" v:shapes="_x0000_i1028">,и сдвига<img src="/cache/referats/19129/image010.gif" v:shapes="_x0000_i1029"> с критериемаппроксимаций.
K(Rn,<img src="/cache/referats/19129/image008.gif" v:shapes="_x0000_i1030">,<img src="/cache/referats/19129/image010.gif" v:shapes="_x0000_i1031">)=<img src="/cache/referats/19129/image012.gif" v:shapes="_x0000_i1032">;
Где dij=d(XiXj); rij-элементыматрицы Rn. Для аналитического решениеудобно что либо зафиксировать.
Если задан порог близости <img src="/cache/referats/19129/image014.gif" v:shapes="_x0000_i1033">Qс элементами равной 1 если dij<img src="/cache/referats/19129/image016.gif" v:shapes="_x0000_i1034"><img src="/cache/referats/19129/image018.gif" v:shapes="_x0000_i1035">, и равные0 в противном случае. Близость междуматрицами Qи Rk оценивается расстоянием Хемминга .
r(Q, Rn)=<img src="/cache/referats/19129/image016.gif" v:shapes="_x0000_i1036"><img src="/cache/referats/19129/image020.gif" v:shapes="_x0000_i1037"> ;
где <img src="/cache/referats/19129/image022.gif" v:shapes="_x0000_i1038"> весовые коэффициенты.
Требуется найти матрицу Rnаппроксимирующего матрицу Q. Существует большая группа методовкластерного анализа в основе которой лежит решение этой задачи.
Предположим, что мы имеем результатразбиение построенного нами алгоритма классификаций. Справедливо ли отнес обьект Тi
классу Rn, когда в действительности он принадлежит,быть может, к другому классу. Вэтом случай исследователь идет по одному из пути. Обрабатывает набор данных разными алгоритмами. результаты сравнивает между собой, или если естьэксперт,то сравнивает с его разбиением. Но экспертного разбиение может и небыть, а сравнение результатов разных алгоритмов может быть не достаточным.
В таком случае исследователь может проверит кластер данных на«реальность». Понятие реальности кластера данных основывается на идеях Дж.Хартигана.
Как вообще предполагается строитьпрогнозирования социально-экономической среды в задачах классификаций.Рассмотрим на примере . Пусть имеем nгородов каждую из которых характеризуем некоторыми параметрами. напримерс1-потребление электроэнергий, с2- личным потреблением и.т.д.
Тогда Х векторпредставляет собой набор указанных характеристик Задача классификацийзаключается в том чтобы разбить города по уровню развития. Ппредположим, чтомы разбили города по уровнюрразвития, ипредположим ,что результатразбиение реален.
Теперьизменим параметр одного города проверим снова не изменился ли результат разбиение на основе результатаможно строить прогнозы.Прогноз будет достоверным ибо алгоритм классификацийразбивает правильно. в заключении стоить отметит, что исследователь должен убедится в том, чтоалгоритм классификаций разбивает правильно.
Применение алгоритмов распознавания для решений задач сегментации. Одним изинтересных приложений теорий распознавания является возможности использоватьнекоторые модели этой теорий для решения задач в разных областях математики. В частности для решения трудных комбинаторных задач и таких как задача сегментации программ[6]. Под задачей сегментации обычнопринято понимать задачу разбиения последовательной программы навзаимозависимые по управлению и информационной части (блоки, сегменты и. т.д. ) в соответствии с той или иной целью. Для решения задач сегментациисуществует ряд методов. Которые разделяются условно на несколько подходов. Которые позволяют в основном получитьлишь приближенные решения при неизвестной погрешности определяемых решений. Один из таких подходовявляется кластерный подход[6]. Кластерный подход основывается на представлениизадачи сегментации как задачикластерного анализа. Сама программа в этом случае является точкой n-мерного пространства.
Для решения задачи сегментации программ кластерный подход опирается на классическую графовуюпостановку задачи сегментации иобладающей некоторыми специфическими особенностями.
Формулировка задачи состоит в следующем: Требуетсяразрезать вершины полного, взвешенного графа на части таким образом, чтобы суммарный вес вершин, попавших в каждоеподмножество не превосходил заданного значения, а суммарный вес внешних по отношению к разбиению ребер был быминимален. При решении различных прикладныхзадач распознавания и классификации успешно применяется метод опорных подмножеств.Впервые метод опорных подмножеств был описан Ю.И. Журавлевым. Принципиальную возможностьприменения метода опорных подмножеств для решения задачи сегментации былоописана в работе[6]. Основной трудностью здесь является содержательная интерпретацияпараметров данного метода, задающих соответствующий класс алгоритмов вычисленияоценок.
Интересным подходом для решениязадач распознавания образов и классификаций, а также некоторых дискретныхэкстремальных задач, в частности задачи сегментацииявляется нейросетевой подход.
СПИСОК ЛИТЕРАТУРЫ
Гонсалес Р.К. Принципы распознавания образов./Пер. с англ. И.Б.Гуревича: под ред. Ю.И. Журавлева: М. Мир 1978. Мандель И.Д. Кластерный анализ./ М.: Финансы и статистика.1988. Дж. Вэн Райзен Классификация и кластер./Труды науч.семинара.: М. Мир.1980 Дюран М.Б. Кластерный анализ. — : М. Финансы и статистика, 1977.-220с. Аркадьев А.Г. и Браверманн Э.М. Обучение машины классификаций объектов./М.Наука.1971. Дюсембаев А.Е. Математические модели сегментации программ. — М.: Физматлит,2001.-208с.
Вишняков Ю.С., Сулейманов Б.С. Построение алгоритмов распознавания для обработки видеоизображении, корректных для заданной контрольной выборки М.: Наука,1989.-126с. Журавлев Ю.И. Алгоритмы вычисления оценок и их применение. — М.: Фан,1989.-119с. Хартиган Дж. А. Задачи связанные с функциями распознавания в кластер-анализе. –М.:Мир, 1989.- 230c. Кнут.Д. Исскуство прогаммирования для ЭВМ. М.:Мир,1977.-T.2.-724c.