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

пгл л, п РОССИЙСКАЯ АКАДЕМИЯ ЯАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР.

"5 ДПР ШЗ

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

АИДАРХ'НОВ МАХМЕТ БЕРКУТБАЕВИЧ

ТЕОРИЯ И ПРИМЕНЕНИЕ ГРУППОВЫХ. МЕТОДОВ КЛАССИФИКАЦИЙ ДЛЯ КОНЕЧНЫХ И КОНТИНУАЛЬНЫХ МНОЖЕСТВ ОБЪЕКТОВ

05.13.16 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях. '

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

Москва - 1993

Работа выполнена в Институте математики и механики и Инс-; титуте космических исследований Академии наук Республики Казахстан. 1 . ■ ■'

Научный консультант: академик РАН и РАЕН, доктор физико-математических наук, профессор Ю. И, Журавлев

Официальные оппоненты: : •

академик РАО, доктор физико-математических наук, ( профессор . В.Л. Матросов

доктор физико-математических наук

К. В. Рудаков

доктор фи&ико-математаческих наук

г———-•-- , • Е.В.Щэпин

Ведущая организация: Институт технической кибернетики АН Республики Беларусь

: ^ . 99 Ы ■ ;

Защита состоится "ОСА"' ' • ■ /■.--■'• 1993 г. в часов на заседании специализированного Совета Д 002.32.06 при Вычислительном Центре.РАН по адресу: . .

117867, Москва, ГСП-1, ул. Вавилова, 40

С диссертацией можно ознакомиться в библиотеке МИ РАН.

Автореферат разослан " 1093 г.

Ученый секретарь

специализированного Совета Д,002.32.06 ■

кандидат физико-математических наук СЗг&й^^С. М. Швартин/

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

Актуальность темы. Проблема распознавания и классификации в теченне достаточно продолжительного времени привлекает к*себе пристальное внимание многих исследователей в области прикладной математики и информатики.

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

Становление распознавания как самостоятельной научной теории характеризуется следующими этапами:

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

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

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

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

С другой стороны для решения задач классификации

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

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

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

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

Связь темы исследования с планами НИР. Настоящая работа выполнена в соотвествии с программой АН РК "Разработка математического обеспечения автоматизации научных исследований" на 1980-19SS гг. cn гос. per. 8005В001) и в'рамках Республиканской региональной программы Р.077.01 "Создание и развитие автоматизированных систем и зффектиьного использования вычислительной техники в отраслях Республики Казахстан, на 1986-1990 гг. и на период до Я005 года".

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

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

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

Среди основных содержательных результатов отметим следующие, . обладающие новизной.

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

2. Исследованы основные х.етрячйсгшэ свойства пространства классификаций конечного множества объектов,

3. Построены алгоритмы синтеза; групповых классификаций, основанные на метрическом подходе. Получены оценки их сложности. • . '

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

5. Получено координатное представление классификаций, основанное на структурных свойствах пространства классификаций конечного множества объектов.

В. Построен прямой (без оптимизации) метод точного пост- ■ роения групповой классификации конечного множества объектов.

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

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

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

10. Исследованы.принципы построения алгоритмов распознавания и классификации на континуальных множествах положительной меры. ' ■

11. Построены алгоритмы распознавания конечных множеств объектов, сходящиеся почти всюду к корректному алгоритму для задачи распознавания континуальных множеств.

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

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

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

В этом плане, применение методов, предложенных в работе, позволит решать широкие классы прикладных задач.

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

Работа проводилась в рамках 2 хоздоговорных научно-исследовательских работ, 2 договоров о научно-техническом.сотрудничестве и по постановлению правительства Республики Казахстан, соответственно.

Результаты внедрения подтверждены соотвествующими документами.

Апробация. Основные результаты диссертации докладывались и обсуждались на: i Всесоюзном совещании по статистическому и дискретному анализу нечисловой информации, экспертным оценкам и дискретной оптимизации САлма-Ата, 1981 г.), Советско-Германских семинарах "Дискретная математика и ее приложения в кибернетике" (Москва, 1983 г. , Алма-Ата, 1985 г. , йена, 1986 г.); Международной конференции "Проблемы искусственного интеллекта и распознавания образов" СКиев, 1984 г.), н Всесоюзной конференции "Математические методы распознавания образов" СДилижан, 1985 г."), Всесоюзном симпозиуме "Машинное обнаружение закономерностей" (Минск, .1985 г.), х 'Всесоюзном совещании "Проблемы управления-86" (Алма-Ата, 1986 г.), XI Всесоюзной конференции "Икформатика-87" СЕреван, 1987 г.), m Всесоюзной конференции "Математические методы распознавания образов" С Львов, 1987 г.), и Республиканской кок'$еренции "Проблемы вычислительной математики и автоматизации научных исследований" (Алма-Ата, 1988 г.), Всесоюзной школе-семинаре по

рудопрсшысловой гидрогеохимии" СЧита, 1988 г.), IV Всесоюзной конференции "Математические методы распознавания образов" (Рига, 1989 г.), Республиканской научно-технической конференции "Использование достижений НТП в области охраны природы Казахстана" (Алма-Ата, 1990 г.О, Международной научно-технической конференции "Применение статистических методов в производстве и управлении" (Пермь, 1990 г.), Республиканском совещании "Проблемы создания систем обработки, анализа и понимания изображений" (Ташкент, 1991 г.), V Всесоюзной конференции "Математические методы распознавания образов" (Звенигород, 1991 г.), Международной конференции при специализированной выставке "СПЕКТР-914 (Минск, 1992 г.), а также на ежегодных отчетно-научных конференциях Института математики и механики АНРК с 1980 по 1991 гг.

Публикации. По основным результатам диссертации опубликовано 25 работ. Всего по материалам выполненных исследований по теме диссертации опубликовано 35 работ. Личный вклад автора в совместных работах [14,15,18,22-24], имеющих прикладной характер, состоит в формальной постановке задач и разработке методов и алгоритмов, относящихся к групповому синтезу классификаций и дешифрированию многозональных космоснимков.

Структура и объем работы.. Диссертация состоит из введения, шести глав, заключения, списка литературы из 126 наименований. Объем диссертации - 245 страниц.

СОДЕРЖАНИЕ РАБОТЫ. ! '

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

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

Пусть задано конечное множество объектов м^б^ ... ,8п) из некоторого объектного множества р. Для каждого б определено - описание объекта б. Пусть зс(м) - пространство всевозможных классификаций для множества объектов м и А1,...,две{А)

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

к (м)^, кехСм).

Тогда основная задача г^синтеза групповой классификации для множества объектов и состоит в следующем. Найти к*(м)ехСм), удовлетворяющую условию

Решение задачи го для представлений классификаций, заданных в виде информационных матриц Сматриц смежности}, рассмотрено как решение задачи гх. Для представлений, заданных в виде наборов центров - как задача гг.

Первая из решаемых задач ъ^ состоит в последовательном решении подзадач

Пусть на множества м={Б}, задано бинарное отношение иСм). Пространство всевозможных бинарных отношений вСм) множества м обозначим через эгСм). Пусть рСи', п") - метрика в пространстве жСм). Очевидно, что жСм)эХ(м), поэтому р определена и в а:См).

Задача 2 состоит в построении результирующего бинарного отношения п*(М) и заключается в следующем.

Найти 1?*См)еЗ!См), минимизирующее функционал рСЮ:

Если в результата решения задачи г- удается построить результирующее бинарное отношение П*(м), являющееся отношением эквивалентности, то тем самим решается основная задача г .

Задача г,г состоит в построении алгоритма, выделяющего из в*(м) компактные подмножества (ядра) м0см.

Задача г1Э заключается в построении алгоритма, формирующего классификацию кСп) по выделенному множеству м0 и м1=м\м0.

Вторая из ротаешх в главэ эчдач 2, рассмотрена как последовательное решение подзадач ггх и Згг. При этом оадача г2, состоит в построении оптимального результирующего характеристиче-

т

См,,Км)). Пусть аСк',к") - метрика в эсСм)

рСк") = ш1п (рСЮ к-хСм)

»

ского набора центров рСм) по исходных) наборам центров 0^..,, полученным заданным множеством алгоритмов а^ ... , Ат.

Задача ггг, аналогично г13, заключается в построении * алгоритма, формирующего классификацию к(м) по центрам мо, определяемым из р*См) и множеству м =м\м .

Для реализации решения перечисленных выше задач получены следующие результаты.

Показывается, что если исходные классификации к1Г.,.,к заданы в виде информационных матриц ||о?.|| х» , .....п, то

^ у

можно легко перейти к графовым представлениям классификаций ■ а"={м, {^.э^) и,' соответственно, к их матрицам смежности

' Н^Ч'^Ипхп

Решение задачи основано на построении и анализе модели <з(пО-результирующих графов (оСчСт))), где сСеСга))=Г{3), 1«5(т)зл1. Определим сСдСт)) следующим

образом.

Пусть в - совокупность т-мерных булевских векторов ЪгСЬ,, ... ,10 с нормой ||ь||=<зСт) и ?Съ) = { 111^=1}, тогда

а=С (Б), {(э , = и п о" 13 Ьев Ь)

(Се .8 3)5 = и • п г ■ (С8 )) .

1 1 Ьев ке^СьЭ

Множество ребер графа вСчСт)) модели юСсгСт))) может быть записано в белее приемлемой ' с вычислительной точки зрения форме. Введем характеристические функции х,»...»^ на •парах Сз ,8„)емхм

и' V

• Г 1, если Сэ ,з )е{(з,,з,)» ,

хС3>д)=| и * I } V

и ^ | о, в противном случае,

тогда

(С

я,^)} = (Сз^З,,) в и, в^ЗДСт)}, и,-0,1, j=l,. . .п

Обозначим через (нСдСт))) модель оСш)-результирующих бинарных отношений, соответствующих (сСйСт))).

Определение 1.2. Модель дсСсгСт))), содержащая граф с(<з(т)) с соотвествующим бинарным отношением кСвСт))е;(нС(зСгаЛ), 1 <£)Ст)йп, удовлетворяющим условию

У pCR.R^ = min > pCli'.Ky)

H'CSCM)""1

называется полной над mcd и {а,,..., а }<={а}.

1 Л»

Модель (rcqcho)) в этом случае также называется полной над MCD И (At, . . . , AJc{A).

Теорема 1.1. Модель {«СQCm)))С (RCqCm)) >) . полна над и и

A J.....Ав. Значения QCm)=k, при m=2k И (jCmD=k+l, При m=2k+l,

являются оптимальными.

Теорема 1.1 устанавливает оптимальное значение QCm), тем самым позволяет легко получить оптимальное бинарное отношение Сграф), т.е. решение задачи zn,

Рассмотрено обобщение задачи zjt на случай, когда задаются веса предпочтительности w,.■ • • > wm алгоритмов AJt...,Am, где W >0, i=l.....m, W+...+W=l.

i ' f ' 1 го ~

Определим множество ребер графа aCqCm),w)e{GCQCm),w}, где -i- <q(m)íl, следующим образом: .. ..

m

{Csi,sj)) = {Csij,sj0)|^K[<xliCsu,si0)MäCra)}, u,-u,i, j=l,. . . ,n

Определение 1.3. Модель (rcqcih),«)j называется полной над множествами mcd и {а.}"с(а}, если существует бинарное отношение R(QCm),w)e(BCQCm),w)}, удовлетворяющее условию

ю m

I pCr.wA)= mirV / I рСВ'.И^

lAr v w r'escm) iAt

Теорема 1.2. Модель qcи)-результирующих бинарных отношений Сграфов) с весами w=Cw ,...,» ) (RCqCm),«)} C{cCQCm),w)}) полна над MCD, fAt)"c(A). - ,

Доказанная теорема позволяет получить решение для более общей, чем z задачи.1

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

Определение 1.4. Бинарное . отношение kcc(s}x(sj называется отношением слабой эквивалентности, рели для любой вершины существуют хотя бы две вершины зц ;и з^ такие, что из

Cs ,s и (s ,s )cr следует Cs ,s .

w и с w uc J u >U с

Приводится алгоритм выделения слабоэквнвалентных подмножеств (ядер} в q(i,0-результирующем графе, который позволяет получить эталонное множество 'М0«М, т.е. решение z и конкретный пример использования алгоритма.

Пусть каждый алгоритм а( из исход-.ого множества применительно к заданному множеству m=(s ,...,s }cd строит подмножества следующего вида:

А,(Хм) ,M) = {S,}=M,, M, = (s...... s }, i=l,...,m,

' '''S '¿m

где - центр j-го класса, полученного алгоритмом a(, ¿(i) -j

количество классов классификации л(-го алгоритма.

Результаты работы алгоритмов а , i=l,...,m будем представлять в форме характеристического набора центров.

Определение 1.6. Булев набор ß(At)=Cß .. ,ßIn) называется характеристическим набором центров . для множества м в алгоритме а(, если выполняются следующие условия:

Г 1, если s ем

. . 1=1.....J=i,-...п

3 ^ 0, если

Построена модель результирующих характеристических наборов центров S(p(a.....,а ,M,e(m),w)}, зависящая от параметра е(ш),

Д 1 IÖ ..

—<е(т)^1 и вектора параметров весов w, представительности

(предпочтительности) алгоритмов At}т.е. w=(wi(. .. ,wj,

m

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

набор «Ср.....} ,е(га),ы)=р(е(т),у) модели следующим образом:

г 1 №

in

Требуется построить результирующий набор ß\ удоваетворя-

эдий условию

р (ß*) = min ipjCp)

ßcU"

Определение 1.7. Модель .....Pm, 0Cm), кО ) называется

полной над м,а.....,а , t -ли для любых допустимых Meß,

я,

а .. ,aine{a) и соответствующих ßi,...,ßm в модели существует набор рСеС ш) , W) , удовлетворяющий МИНИМуМу 'Р..

Теорема 1.3. Модель ,...,ßB,eCm),w)) полна над м,

а ,----А

Im ,

Теорема устанавливает оптимальное значение для в(т), с помощью которого легко строится решение z .

В последнем . параграфе рассмотрена задача восстановление классификации z Cz,'), Показывается, что для решения этой задачи не могут быть использованы итерационные алгоритмы классификации и поэтому эта задача поставлена как задача распознавания. Рассмотрены некоторые применения алгебраической теории •распознавания для построения специальной алгебры, позволяющей реально строить корректный алгоритм, просто реализуемый в вычислительном отношении. В построенной алгебре операторов помимо обычных операций сложения, умножения и умножения на скаляр используется операция специального умножения вектора на оператор, определяемая как соответствующее умножение вектора на определенный столбец матрицы оценок. В специальном расширении строится корректный алгоритм (теорема 1.4), показывается устойчивость корректного алгоритма (теорема 1.6).

Результаты, полученные в главе помимо самостоятельного значения, используются (задача z ) как вспомогательные для построения алгоритмов метрического подход?.

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

Рассматривается пространство классификаций х(м) для множества объектов m=|s ,...,s ) со стандартным представлением

классификаций КС м) = {к См).....,к^(м)), показывается, что оно

является структурой.

Обозначим через зАм) . множество классификаций м на I,

litsn классов, т.е. U зЛм)=хСм). Пусть ,кп(£>- произвольная

классификация иэ з&мЭ. Зададим отображение d : xcm)xxcm)-»z с помощью следующей формулы:.

■ г

u

d(kuc-e ),KVUJ5=2n- у max {iku Ct U )|>-

п u п 11 ,l. n,j u n,i ai

l

V

j.l

- y max { ik° ,cí>k" ,c-0 i) ifrl .».».« ».j ь

u

где к1сг) = {к1 C-t Э,.. .',к1 . (.1.)}, ÍUsn, tefu.ti).

n l n. 1 t n,4> 1 l

l

Теорема 2.1. Отображение d является расстоянием в хСм), Исследуются метрические свойства пространства классификаций х( м). Доказываются утверждения 2,1-2,7 и теоремы 2.2-2.6, определяющие основные. метрические свойства, необходимые для построения алгоритмов решения zc, использующих метрический подход.

Утверждение 2.7. Если kJL&íkJ.Z-í'), и класс

к C¿-1D=K С£)ик С-О, то

nV ni n.J

dck с-е),к'сг-1))=ш1п{1к c-oi,ik с-оп

п п , ni ' nj

Пусть классификации. из эЛм) занумерованы с помощью множества индексов Q^, 2iCsn-l..

Теорема 2.2. min dCK1C¿D,KJC¿)}=2, при 2s¿¿n-2. -- ljSJ "

' V •

Теорема 2. 3. min dCKlC¿),KJCt))=l-e-tl.,npn -e,te{l,2(i.. ,n) --""«d " "

Теорема 2.4. Пусть классификация еч0 образована из классификации кЧо в результате перестановки двух объектов из классов к' С-С) и к' С -С), wu, u,u=l,,.. ,1, тогда

no) п ц

,0, если ! к' С -О I = I к' С-О 1=1

' ni) .пи

я г к'г /■» iíJf.m=J ? если лишь один из классов п ' п I ' о и и имеет мощность равную 1

М, если I к' С О I> 1 и 1к' Сг)1>1

' пи

где eisten.

Теорема 2.5. max шах аСк'С-б),KJCi.D)s2Cn-0, причем ра-

2üi£n-2 IjiJ " "

венство достигается при /п s t * .

• Обозначим шах аСк'С-О.к-'СО).

Теорема 2.6. При

если Для t выполнены -следующие условия:

или и в разложении п:

псг,о= п=к0^+к1г+к2, к,*1

если и в разложении п: п=к0-Сг+к1'С+к2| к1=0, к2й1

Проведен анализ доказанных утверждений, позволяющий сделать некоторые заключения о геометрической структуре метрического пространства (ЭССм) ;<!}..

Показывается возможность более эффективного применения введенной метрики в сравнении с часто используемой метрикой Хеммингова типа для оценки близости классификаций.

. Рассмотрены задачи гэ и г4, просто решаемые с использованием метрики и являющиеся вспомогательными для построения алгоритмов решения го.

Задача гг - является решением задачи ге в множестве хСм) = «(к^м),.,. ,квСм)1, задача - есть минимизация уСк^м))» =аСк" м),к|См)), 1=1,...,и," где к'См) - классификация м.

Для решения вадачи га построено четыре локально-экстремальных алгоритма а*,- а\ а9; а*. Первые два алгоритма предназначены для решения задачи гв при условии, когда все исходные классификации к1...,',к определяют разбиение м на I классов. Алгоритмы а3 и а4 реааот задачу го в обцем случае,

когда число классов в классификациях к1..... кв

произвольно. "

Построенные алгоритмы используют в качестве начального приближения решения задачи гэ. Если а' и а3 построены на идеях обычного "сеточного" поиска, то а2 и ал используют, как вспомогательные, решения задачи гп, которая играет роль оценочной задачи и на каждом шаге своей работы решение гА.

Заметим, что оптимальное решение задачи г, осуществляется последовательным преобразованием бинарного отношения в отношение эквивалентности, которое "минимально" изменяет матрицу бинарного отношения. Построенные алгоритмы а2, а* решают, в некотором смысле, обратную задачу, осуществляя направленный поиск классификации в пространстве классификаций х(м), минимально удаленную от оптимального бинарного отношения в аСм), построенного для задачи г. ■

Теорема 2.7. Сложность сСа1) алгоритма а1 есть оСп5пО.

Теорема 2.8. Сложность сса2) алгоритма а2 порядка п2Сп3+ш), т.е. с(а2) =оСп2Сп3+тЗ).

Теорема 2.9. Сложность сса3) алгоритма а3 имеет порядок п5ш, т.е. сса3)=оспбпо. .

Теорема 2.10. Сложность сса4) алгоритма а* есть оСп2(п3+

+ш)).

Вторая часть главы. 2, посвященная структурному подходу, начинается с исследования некоторых "структурных" свойств хСм), которые можно использовать для решения задачи га.

В дискретной булевой алгебре, в силу принципа исчерпыва:-ния. всякий ненулевой элемент представляет собой верхнюю грань некоторого дизъюнктного множества атомов. Структура х(м) не является булевой алгеброй, так как в ней не выполнены дистрибутивные законы, однако по аналогии с дискретной булевой алгеброй показывается, что хп",См) - базис в хСм).

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

Пусть кехСм), тогда

Г к, ее [ о, ее

где о=кпСп) - нуль множества хСм).

Множество х"_1См) можно записать в следующем виде:

если <х=1

ак= '

если а=0

х 00= и I/ кСи,«)

ц« 1 + 1

где кСи,и) - обозначение классификации из ж^'ЧмЗ,в которой объекты зц, о>и, принадлежат одному классу.

Пусть и\'= {Си,«)) - мно-ество пар индексов, определявших хп",См). Зафиксируем порядок расположения пар з множестве

иу, где ШУ1=с^=ы и пронумеруем их. Пусть а, .„е(0,1), тогда

* (и,'О)

V « КСи, и)=К, КеХСм) С1) .

(и.ллеиу '

при соответствующем задании значений параметров а(ц

Каждой классификации кехСм) соответствует допустимое множество пар индексов и\'С к) сиу, которое определим с помощью булевского набора аСк) следующим образом:

аСк) =Са<1,2)'а(1 .э>"-••*<,,„>.....«(п.п.п5^",'^'-;"0^

( 1, если (и,о)еиу(к)

С<<и',иГ[ 0, если Си,«)яМк) Таким образом, каждой классификации кехСм) однозначно соответствуют координатные представления в базисе х^Чм) . через набор аСк) размерности N с булевыми переменными а^к).

Рассмотрим совокупность допустимых иусиу. Очевидно, что соответствующие им наборы а образуют некоторое подмножество е" множества вершин единичного и-мерного куба вм, т.е. в"сем и каждому аеЕ* в соответствии с формулой С1) однозначно соответствует классификация кСа)ех(м).

Теорема 2.11'. Формула С1) устанавлиряет взаимно однозначное соответствие между хСм) и Е*.

""юрема 2.12. ^ Вес набора аСк), где неэ&м), 1аг«лп-1, 1м1=п, равен п-1 С||вСк)|1=а--С).

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

Пусть оСк()=а1-Со;^а^,., 4 - координатные првдгтав-

ления классификаций к^ полученных алгоритмами а)( 1=1,2,...,т,

и d0 метрика в е".

а = j

Тогда задача Zco состоит в следующем.

. Найти c¡*€E*cEH, удовлетворяющий условию.

■а п

^ doCa*, min ^d0Ca,a')

Пусть а-Са^^,.;. ,ан)еЕы и значения Oj определены следующим образом: .

m

' 1, если Y aj>

, j=l.....N (2)

О, в остальных случаях

Теорема 2.13. Набор аеЕн, определенный согласно (2), принадлежит е*. . '

Теорема 2.14. Набор, oge* со значениями аргументов, определенными по формуле С2) является решением задачи zco.

Таким образом, мы получили простое решение, задачи zc, ко-..торое легко находится по решению задачи zc0,-. используя формулу (1), в силу теоремы 2.1.1'.

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

Определение 2.8. Алгоритм классификаций а называется корректным для задачи zke{Zk}, если асгь)=к*(м), где к*См) - истинная классификация множества hcd.

В множестве алгоритмов классификации (а) введем операции сложения, умножения и умножения на параметр а, ае{0.1). Пусть a',a"e{a), a'(zk)=k' , a"czk)=k", к',к"ехсм).

Определим алгоритмы a-д', а'+а", а'*а" следующим образом

, если а=1

4 п

ceA'CZt

Си)=о, если «г=0

п

CA'+A")CzkD=K'V К"

A'XA"CZ Э=К'Л К" к

Рассмотрим задачи гк=См,Хм)), обладающие следующим свойством относительно множества алгоритмов классификации (а).

Пусть га*(а)=<{а},+,•,{0,1}> - алгебра алгоритмов относительно первых двух операций.

Определение 2.10. Если множество классификаций (асм.хм))}, ае{а) содержит • базисное множество хп"Чм), то задача гк=См, Хм)) называется полной относительно множества Смодели) (А). •

Теорема 2.15. Если {гк( - множество задач, полных относительно (а), то модель и*{а} является корректной относительно

(V-

Приводится пример построения полной модели алгоритмов классификации. В качестве модели «¿(а) рассмотрено параметрическое обобщение алгоритма классификации с одним порогом на расстояние между объектами. .

Теорема 2.16. Модель п*{^(А)} является корректной над

<2Ь). ' Г

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

В третьей главе рассматриваются задачи классификации на континуальной информации.

Пусть м=(з) - множество объектов континуальной мощности и

а1,а2.....\п совокупность алгоритмов распознавания или

классификации, решающих задачу гк для множества мер, где р- ограниченное измеримое множество. Предполагается, что в полученных алгоритмами а4 классификациях к1См)={К11См),... ,к.гСм)(,

1=1,2.....ш, классы к^См) являются измеримыми множествами с

положительной мерой, т.е. р(киСм))>0, 1=1,...,ш, ¿=1,..

Пусть аСк'.к") - метрика в пространстве хСм)-класс..фикаций с конечным числом классов и .

№

*>Ск)= У аСк,к,), кезсСм).

Тогда задача гск сострит в нахождении к1(м)€(К5См),К2См),

...,к См)}=х (m)cxCmD С соответствующего алгоритма i=l,2,...,m, минимизирующей функционал ?>:

ipC К.) = m i n ipck) ' KtGXoCM) .

Очевидно, что решение^ задачи zck не представляет принципиальных трудностей, если будет введена метрика в пространстве хСм). Показывается, что метрика cick.k') введенная для пространства классификаций х(м) конечного множества объектов

n=is .....s ) может быть обобщена для различных пространств

классификаций континуального множества объектов. .

Рассмотрим пространство классификаций эсСм) для множества м, удовлетворяют э следуг им ограничениям:

и

зс(м5= и xjcm), j.i

a»wsanax{-t ,... ,-tj , где. xj(m) "- пространство классификаций для и на j классов таких, что все классы измеримы с положительной

мерой и для произвольной классификации к=(к1.....к )exJ(M) не

существует классификации к'^к; к' = {к J,. ,•., к J} еэс'3 С иЭ такой, что для каждого класса к4 классификации к найдется класс K't классификации к', удовлетворяющий условию jj(k пкр^дСк )=jjCKp. •

Таким образом, хСм) - пространство классификаций множества .м на конечное,, не превышающее w, • число классов, причем для

любой классификации к(м)ехСм), kcm)={kjcm).....к^См)}, -Ш,

mck4cmd)>0, и не существует различных классификаций, классы которых совпадают почти всюду на м.

у Пусть мера мне лества .м равна {¿См). Рассмотрим обобщение отображения d,введенного для конечного множества, м на случай измеримого м и пространства классификаций х(м).

: Пусть к'См) и к"См) - произвольные классификации из хСм) и

Зададим отображение d:xCM)><x(M)->R с помощью следующей формулы: ' ■ ; . , '

V V

dCK',K")s=2^M)-T max рСК'ПК")- V шах рСК"пК') jfri mw * ■ ¡¡ft tail' 1 J

Теорема 3.1. Отображение d является расстоянием в хСм).

Рассмотрены вопросы построения меры в пространствах описа-

кий с разнотипными признаками.

Далее рассматриваются некоторые обобщения рассмотренного

пространства классификаций.

м

Пусть ЭС(М) = U An) тах{1.....1 }SW<®.

t u -С.1 u 1 n

Хц(м) - пространство классификаций для континуального множества м с t измеримыми класами. Некоторые классы классификаций из хиСм) могут сг держать как конечное, так и счетное число объектов. Пусть к',к" - произвольные классификации из зсСм) и к* = {к*.....к^,}, к"={к;\... ,ir„>.

Классификации к' и к" будем считать равными, если соответствующие им классы, имеющие положительную меру, совпадают почти всюду на и. А имзнно, если для любого класса к|,^Скр>0, 'i=l,2f... ,1' из к* в классификации к" найдется K'j, p(Kj') >0, j=l,2.....1", удовлетворяющие /jck'дк")=0.

* J

Очевидно, что при этом к1 и к" могут содержать разное число классов, если некоторые классы имеют меру, равную нулю.

Пусть мера /jCm) множества м равна рч>0 и отображение dt:KuCимеет следующий вид:

v v

d,(K',К")=2и - У шах ц(К'пК")- Y max /jCК"ПК'D

k н L* j * Lt 1 j

j.l Si" J.l lSl i.V

Теорема 3.3. Отображение dfc является метрикой а У.цСи).

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

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

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

Одной из основных задач главы является построение процедур

разбиения исходной конечной информации, заданной в виде описаний объектов п числовыми признаками с известной информационной матрицей, на два подмножества • обучение и контроль, являвшихся в некотором'смысле оптимальными. Для этого каждому объекту s и«"годного множества m={s ,... .s^} ставится в соотвествие окрестность устойчивого распознавания o(s,iCs)) радиуса aCs). Формулируется задача оптимального разбиения м на множестъа мо и м .

Представить множество м= (si..... s^) в виде объединения

двух непересекающихся подмножеств: обучающего множества мо= (s .....s } и контрольного множества (s1,.,s4),

1=m+q, ТЭК, ЧТОб ЧЧМ >= г Час У(М' ), ¥ (M ' ) =М U 0(S,l(s)).

н'с и s е н'

При этом должны соблюдаться два условия:

1) в информационной матрице элементов s].....sb

все столбцы попарно различны;

2) элементы s1/...,s4 попарно неизоморфны элементам s.....,s . • • .

ira

Пусть существует некоторое разбиение м=мои м , MQn м^ 0.

Сопоставим элементам st..... е M .булевы переменные

у,......у_. Переменная у..= х, если s., с м,, и у = о, если з.,е

1 1 V V 1 V V

•:mq. Введем булеву функцию Иу,,____уа) следующим образом.

Пусть - бинарный вектор, единичные

координаты которого имеют номера Ц,..-.,^. Выделим в M элементы с номерами ц, ,- Лк и образуем из них множество м^, остальные элементы образуют, очевидно, множество м0. Тогда

0, если для м0и мвыполнены условия 1)и г),

1, в противном случае.

Показывается, что функций ffy,,... .у^) является монотонной булевой функцией.

Обозначим через Q(f) множество граничных точек - всех верхних нулей f(yt.....у^).

Теорема 4.1, хотя бы одна точка, в которой достигается максимум ччм') лежит в множестве Q(f),

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

является наилучшей, в- смысле значения функционала, из всех возможных множеств вершин с таким же весом (нормой).

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

множества м .

Пусть задано объектное множество П=(э}: Представим {s} как объединение непересекающихся подмножеств к', i=l,2,...,t: {s}= U к', к' п к! = 0,

Пусть к^ к - множества мощности континиума, причем все объекты Kj имеют один информационный вектор. Тогда .начальную информацию ja к,...,к») будем задавать набором <к1,а;..,;к,а>, где - информационный вектор области Kt, i = l ,2, . . . ,t.

Определение 4.4. Начальная информация ' (к^,,.., к7), заданная в виде набора. <к .с^;... ;К' ,а /,' называется континуальной обучающей информацией.

Пусть задан набор числовых признаков х с областями

значений, соответственно, ' [а.,61,..., [а ,!> ¡. Е„дем

11 п п

рассматривать допустимые., объекты s с описаниями

j( s) = (х 1.....хп), т.е. такие, для которых [а4,-6.].

i=l,2,...,п. Тогда множество допустимых ■ объектов есть n-мерный прямоугольный параллелепипед [а ,6 ;'... ;an,f>n]-TI.

Пусть во множестве допустимых объектов ГГ= {sj задана метрика

_ *• -

р( J(s*),Jis"))=p(s',s"), з',s"e {s), и каждый объект э е U к ,

' j = 1 предъявляемый для распознавания, имеет описание j(з()=

=(х,...,х1п). Определим среднее расстоачие r<sj,k > от

объекта s( до множества к} следующим образом.

Rls,,^) = [й<К,)Г' J ... J p(s,sJ)dxt...dxn или

KJ

R(s

j.Kj) = [/J(Kj)]"1 | ... [ 7<x1-----xn)p(s,s1)dx.. . .dxn.

KJ

если задана неотрицательная непрерывная функция ?(Xj.....,

определенная в П.

Для решения основной .задачи - распознавания z построена модель ;а! алгоритмов распознавания. Оператор а* для каждого

объекта в вычисляет числовой вектор .....Rit)' где Ru "

=ß ( s ! к.). Оператор а" по набору числовых характеристик (r ^-.-.r^) г числяет вектор ссл(st) = (^,... , где (iV-(o.i,4!, называемый информационным вектором в алгоритме

а.

Рассматривается решающее правило л", зависящее от положительных параметров 5 ,...,5

Пусть задан класс весовых положительных непрерывных функций [у} на множестве {s}, определена метрика в "{s} и область вариации параметров ... Этим определяется

модель алгоритмов распознавания, в которой конкретный алгоритм д s (А) выделяется фиксированием функции s) с (y(s)), метрики p(s',s") и параметров'

.■■' Определим области к ,..".',к , зафиксировав для этого расстояние в {s} следующим образом. Пусть s'=(xj,...,

s" = {x'j.....>Г), р( s'; s': )=шах IxJ-x" Окрестностью 0(s,à) для

■ -.элемента .s радиуса -г в ' этой метрике; очевидно, является ..Открытый n-гчрный куб с центром в s и с длиной ребра, равной . который' будем обозначать через q ( s, t ). Тогда каждая из ;.рбл.ас-гей ■ класть объединение конечного числа открытых

.■cri-мерн'ых . кубоз; кU, Q,(s,i(s) ), . • .

■;.■;;'..'.Пусть;'' -.''-области, кjj";•...'.,К . нами уже зафиксированы. ■■•Сопоставив/калсдому, • признаку положительный параметр р( - вес Щт??;.признака-, '.'in., Для определения модели алгоритмов

'¡множестве "допустимых объектов {s} =П используем метрику

Кг'С'.-'Г .pU',*">= ZPJXI-X-;!. '

À" Î

огда формула ; для вычисления r 4 ^ примет вид

• K1J=MK л> ---f'ïU,.....X.) £pjxlk-xjdx1...dxn.

Прямое вычисление r^ по формулам, аналогичным формулам вычисления.мощности объединения конечного числа множеств может оказаться практически невозможным уже при небольших m , так как

I».

для этого необходимо вычислять ¿2 M интегралов j по произ-

вольному параллелепипеду Сс , а ;...;с ,а ).

С1 <1 "

1 п

= Г ... [ (р, |х. ~ х 1+. . . +р |х, -X I №.. . .с!х ,

nJ Л ^ 1 1 11 1' п 1 1| п 1 I»'

где (X

,....,х, ) 5 [с .а] и т - количество нубов.

11 1п 11 пп j

составляющих к .

Приводится эффективная процедура для вычисления числовых оценок в распознающем операторе.'

Теорема 4.3. Сложность вычисления й но большая, чем

__и

сложность вычисления 1+т,(т -1)п/2 интегралов типа л .

^ 1 * - п

Рассматривается принципиальная схема оптимизации модель

'распознавания, сводящаяся к выделению максимальной совместной подсистемы неравенств и ее решению.

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

Пусть в п-мерном евклидовом пространстве пг' задана ограниченная замкнутая область р, называемая объектной. Известно, что область в - объединение конечного числа

подобластей (классов) к.....к^, причем, вообще говоря, к^к^*

Ф 0, и*«, и, и= 1 , 2.....1.

Пусть для каждого класса "к .....к^ известны некоторые фиксированные подобласти к^с к , р(к})>0, .1=1,2,... ,1. Рассматривается континуальная обучающая информация

Пусть

С . . - • . I .

X с р \ ( и К ) , зпг' р(х ,у) Ь 2 с > 0, х £ X, у е и К .

¿.1 J .¡-ч

Сначала рассматриваются задачи -¿е(г) с конечным множеством х.

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

Пусть - совокупность неотрицательных, интв!рируемых

на в функций. Определим среднее расстояние от объекта у е о до некоторой области оси, р(а)>0 для кая. ,ои функция у'х)е (х;},но формуле

С

1

K(y,G) г - Г... Г i(x) р(х,у) dx ...dx .

/j(g) g

Введем положительные числовые параметры с1.....cfJ

Тогда оператор а' для каждого объекта х1 е хч вычисляет вектор числовых характеристик <П(1,. . . i= t, 2 , . . .,q, • j=l,2,

nfj - 'jtrul'1 = oj[r(x',kj)1",=cjjj(kj) [ Jy<x)p(x,x')dx j

В качестве оператора а" . используется пороговое рошаощее правило с положительными параметрами о < d^ < d2J, j-1,. ,1.

Тогда (А) = {а|а=а'(т(х),с) A"(d1,d2), У(х)е(г(х)},

' с=<с,.....d, = (d4.....dve>' d*=(dzi.....äzl)]-

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

_ Теорема ' 5.1. Алгебраическое замыкание м{а} класса I алгоритмов корректно , на множестве задач {zj. ■ -V; ;Построен корректный алгоритм распознавания а и дана его ^запись в явном ввде, из'которой следует, что для его построения, -'достаточно построить q:операторов со специальными свойствами. ■V : Исследуется _ устойчивость корректного алгоритма (теорема: 5.£). . Дартся' рекомендации' для построения алгоритма а с "наибольшим р диусом устойчиворти.

Рароматривается задача zf^.x) для контрольного множества , х'континуальной мощности. Для решения задачи z(JQ,x) использу-' ется последовательность корректных алгоритмов Aqic,: 1С 4 j

' Ao(£r(<d/d > £ l iA'(i,J)Jk}A"<d ,d ),

Построенных для _ конечных. . исходных множеств мощности qC е), сходящаяся почти всюду к корректному алгоритму а при с-Ю. Применение алгоритмов Ач(С) стало'возможным вследствие отображения множества х на, конечное множество объектов, соответствущев минимальной с-сети.

Для степени, замыкания а' относительно операторов а'и,л

верна

Теорема 5.3. Справедливо нераг ■нсгво

1п £ -|-|1п а;|<к|1п('

J.1 и(0(е.)) 12

21 п I -3—+|1п(а ) |- |1п. а. |,

где о(?) - открытый шар радиуса о .¿'<е, ¿-I... ,1.

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

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

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

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

ЗАКЛЮЧЕНИЕ С ОСНОВНЫЕ РЕЗУЛЬТАТЫ).

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

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

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

2. Построен- модель результирующих' характеристических наборов центров классов и доказана ее полнота, позволяющая выделять оптимальные наборы..

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

4. Введена метрика в пространстве классификаций конечного множества объектов. Показана bol .ложность ' ее более эффективного применения . сравнении с часто используемой метрикой Хеммингова типа для решения задач групповой классификации;

5. Исследованы основные метрические свойства пространства классификаций конечного множества объектов.

6. Разработаны алгоритмы группового синтеза классификаций, основанные на метрических свойствах пространства классификаций и получены оценки их сложности.-

7. Построено и исследовано координатное представление в . пространстве классификаций, являющегося не дистрибутивной структурой.

8. Получен прямой Сне оптимизационный} точный метод группового синтеза классификаций, основанный на координатном представлении классификаций.

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

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

в этих пространствах.

И. Исследованы принципы построения алгоритмов распознавания и классификации на континуальных множествах положительной меры.

12. Получено решение задачи разбиения Сне стандартной классификации) начальной информации на обучающее и контрольное множества.

13. Построена модели алгоритмов распознавания на континуальной обучающей информации, основа! ще на вычислении числовых характеристик, зависящих' от значения среднего расстояния распознаваемого объекта до соответствующего класса.

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

15. Доказана корректность алгебраического замыкания модели распознавания на континуальной ; обучающей ■ информации для множества задач с произвольной конечной выборкой объектов.

1В. Получен корректный алгоритм распознавания на континуальной обучающей информации и доказана его устойчивость.

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

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

19. Решены некоторые прикладное задачи геологического прогнозирования, экологии, сельскохозяйственного мониторинга.

Основное содержание диссертации отражено в следующих публикациях.

1. Айдарханов М.Б. Построение корректных алгс_ итмов в расширениях моделей алгоритмов распознавания //Вестник АН Каз.ССР, 1979, ЛИ, 38-42.

2. Айдарханой М.Б, Один подход к построению моделей распознавания // Вестник АН Каз.ССР. 1980, Й10, с.48-51.

3. АПдаруянсв М.Б. Устойчивость -экстремального ' алгоритма р. алгебраическом расширении одной модели распознавания. // 1-е Всесоюзное совещание по статистическому и дискретному анализу нечисловой информации, экспертным оценкам и дискретной оптимизации. Тезисы докладов, Москва - Алма-Ата , 1981, с. 354.

4. \йдархаиов М.Б. Алгоритмы распознавания в континуальной обучающей информации, i, // Ж. ' вычисл. матем.и матем. физ., 1981, с. 3544-1551. ' _

5. Айдарханов.М.Б.. Алгоритмы прогнозирования состояний некоторых сложных систем. //Известия АН Каз.ССР, " серия физик.о-математичи„-кал, 19' 1, $1, с. 1-4.

6. Айдарханов М.Б. Алгоритмы распознавания в континуальной обучающей информации, ii. //Ж. вычисл. матем.и матем. физ. , 1932, JÉ¿, с.441-448. . ' ,

7.; Айдарханов М.Б. К" решению задач распознавания с информацией, заданной' перечислением областей. // Ж. вычисл. матем. ■ и,: мчтем. физ., .1983, $3, а 719-729.

'8,. . "Айдарханов М.Б. Задачи распознавания с информацией, -заданной перечислением -областей; //. Проблемы искусственного ..'интеллекта и распознавание образов, научная конференция с ';участием"ученых из социалистических стран. Тезисы докладов и ^''сройцвнк^...:;1984Vi• Секция;2, с. 8-10.

"Ц-МЬ А- АйдархановМ.Б.'-'Модели распознавания на расширенной ^информации.1 //В кн.• ■ "Математические методы распознавания . образов.' . Тезисы.: Докладов . 2ой Всесоюзной конференции.

Ереван, 1985. с. 12-14. ; ;' 10. Айдарханов М.Б. .0 с выборе начальной информации в ..задача*: распознавания образов. // Машинное обнаружение ; закономерностей,-. Материалы Всесоюзного симпозиума. Минск, .1985, с. 14. '

11. Айдарханов М.Б. . О выборе исходной информации в некоторых задачах распознавания //Вестник АН Каз.ССР, 1986, #9, с.63-Б7. -.

12. Айдарханов М.Б. Об анализе выделенных на изображениях объектов. //Сборник материалов ной Всесоюзной конференции "Информатика-87". М.: - 1987, с.235-236.

13. Айдарханов М.Б. О подходе к анализу исходной инфор-

машш.//В кн."Математические методы распознавания образов" Тезисы m Всесоюзной конференции. М.-Л.: 1987, с.39-40.

14. Давлетгалиева К. Н. , Мухамедгалиев А. Ф., Айдарха-нов М.Б. и др. Применение кластерного анализа при гидрогеохимических поисках рудных месторождений на примерз Чу-Илийского рудного пояса. //Известия АН Каз.ССР, серия геологическая. 1987, j£6, 80-83.

15. Абсаметоь М.К., Айдарханов М.Б» Применение метода распознавания образов при гидрогеох..мических исследованиях.//В сб.:"Всесоюзная школа-семинар по рудопромыслоЕой гидрогеохимии" Тезисы докладов, Чита, 1988, с. 4-6.

16. Айдарханов М.Б. 0 подходе к анализу исходной информации в задачах распознавания образов // Ж. вычисл. матем. и матем. физ. , 1988, т. 28, Jj 11, с. 1750-1754. .

17. Айдарханов М.Б. 0 некоторых свойствах пространства классификаций.//В кн.: "Математические методы распознавания образов" Тезисы докладов iv Всесоюзной конференции. ' Рига, 19Я9, ч. 2, с. 3-6. : : -

18. Айдарханов М.Б., Мухамедгалиев А.Ф. Синтез гр>пповых решений в задачах классификации.//В. кн. :'.'Второй международный семинар:"Теория и применение искусственного интеллекта", пРБ, Созопол, 1989, с.24-27.

19. Айдарханов М.Б. Об одной задаче синтеза - кпассифнка-' ций.//В сб. Всесоюзной научно-технической конференции с международным • участием стран , членов СЭВ "Применение статистических методов г производстве и упрэв; нии", Пермь, 1990, с. 276.

20. Айдарханов М.Б. 0 некотЬрых метрических свойствах пространства классификаций. // Ж. вычисл. матем. и матем. физ. , 1991, JH , т.31 ^ с. 169-173.

21. Айдарханов М.Б. Анализ возможностей некоторых метрик в пространстве классификаций.//В кн. 'Математические методы распознавания образов" Тезисы докладов v Всесоюзной конференции. Киев, 1991, с. 8-9.

22. Айдарханов М.Б., Антипов С.М. , Мухамедгалиез А. Ф., Утембаев Н. А. Методика дистанционного зондирозания из космоса экологической обстановки района Карачаганаксхого газоконденсатного месторождения.// Научна*} конференция при.

международной ' специализированной выставке СПЕКТР,' - 91 "Оптическое, спектрометрическое и радиометрическое оборудование . экологического.мониторинга. " Т. зисы докладов. Минск, 1991, с. 99-96. ;

23. ЛПдарх .нов М.Б., Мухамедгалиев А.Ф., Утембаев H.A. Применание ■ систем цифровой Ьбработки изображений для решения экологических задач. //В. сб.' Проблемы создания систем обработки, анализа к понимания изображении. .. Тезисы докладов конференции. Ташкент,:1991, с. 42-43,

24. Айдарханов .М.Б,. Мухамедгалиев А Ф., Утембаев H.A. Технология - обработки материалов . космической съемки ' для решения задач анализа' экологической■ обстановки в районах разработки полезных ископаемых, // Наука Казахстана - освоении" космоса. Экспресс-информация.: Алма-Ата, 1992, . с.39-41, : .

25. Айдархансв. М.Б. . Принципы[синтеза алгоритмов и реше- : ннй; в задачах.' Групповых .классйфикаций.'"'//-Доклады АН PK, 1992,

Подписано в'печать.I2.02.S3 Формат 60x84^/16. Бщ.тли. й I Печать офсетная. Усл.н.л. 1,85 Усл.кр.-отт. 1.92. Уч.-иьд.л. 1,98 Таран-100. Заказ 351

Типография издательства 'Тальм" 480021, Алма-Ата, уд.Шеачанко', 26