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

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

Будаева Алина Алибековна

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И СРЕДСТВА ПРОГРАММНОЙ ПОДДЕРЖКИ ПОИСКА ОПТИМАЛЬНЫХ ГРУППИРОВОК В ЗАДАЧАХ

ТАКСОНОМИИ

Специальность: 05.13.01 - «Системный анализ, управление и обработка

информации»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Владикавказ-2004

Работа выполнена в Северометаллургическом институте университете).

Кавказском ордена Дружбы народов горно-(государственном технологическом

Научный руководитель: д.т.н, проф. Гроппен В.О.

Официальные оппоненты: д.т.н., проф. Васильев И.Е.

к.т.н. Кузнецов С.Н.

Консультанты: д.с.н., проф. Дзагкоев К.С.

д.м.н. Загалов СБ.

Ведущая организация: Научно-производственный комплекс «Югцветметавтоматика», г. Владикавказ.

Защита состоится 28 декабря 2004 г. в 1330 на заседании диссертационного совета Д 212.246.01 в Северо-Кавказском ордена Дружбы народов горно-металлургическом институте (государственном

технологическом университете), по адресу: 362021, РСО-Алания, г. Владикавказ, ул. Николаева, 44, СКГТУ.

С диссертацией можно ознакомиться в библиотеке СКГМИ (ГТУ).

Автореферат разослан 26 ноября 2004 г.

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

Алкацев М.И.

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

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

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

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

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

различных вариантов разбиений, что и дни питшиой 'i*tpe обесценивает

) ЮС НЛЦМЦАЛМА» к I вИММТМА

с<

Угчт

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

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

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

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

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

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

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

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

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

На защиту выносятся:

• Содержательные и формальные постановки оптимизационных задач таксономии объектов применительно к различным предметным областям.

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

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

Апробация работы.

Основные положения диссертации докладывались на:

• Международной научно-практической конференции в г. Новочеркасске в 2001 г. - «Моделирование. Теория, методы и средства»;

• Межвузовской научно-практической конференции в г. Владикавказе в 2001 г. - «Новые информационные технологии и их применение»;

• Международной конференции во Владикавказе в 2002г. - «Новые информационные технологии в науке, образовании, экономике»;

• Международной конференции в г. Владикавказе, в 2002г. -«Информационные технологии и системы: наука и практика»;

• Международной научно-технической конференции, во Владикавказе в 2003 году - «Информационные технологии и системы: новые информационные технологии в науке, образовании, экономике»;

• на ежегодных научно-практических конференциях СевероКавказского горно-металлургического института (государственного технологического университета) и на семинарах кафедры автоматизированной обработки информации СКГМИ.

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

Публикации. По материалам диссертации опубликовано 7 печатных

работ.

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения, списка литературы из 121 наименования, приложения, содержит 31 рисунок, 6 таблиц и 143 страницы текста.

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

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

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

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

1П - число таксонов z{i,í) - булева переменная, равная единице, если í-Й объект

принадлежит таксону, и равная нулю в противном случае. rQ>j) - расстояние между /-М иу'-М объектами в-пространстве.

- радиус таксона.

- расстояние между центром таксона и объектом.

G(X, Ц) - ориентированный граф, множество дуг которого U, а множество вершин -

A(G) - множество контуров на графе G(X, U)

-

--

Я,

м

-

-

ЧК})

множество дуг, принадлежащих контуру а е Л(С) индекс типа объектов; множество индексов объектов типа; Эталон ¿-ГО типа;

расстояние между эталоном типа и объектом

типа;

- стоимость объекта типа; верхняя граница стоимости выбранных объектов;

- булева переменная, равная единице, если приобретается объект к-го типа, и нулю в противном случае;

Рассмотрим математические модели.

Пусть т объектов следует распределить между И таксонами таким образом, чтобы суммарное расстояние между объектами, принадлежащими одному таксону, было минимально. Формальная постановка задачи имеет вид:

(1)

В случае если критерий разбиения - максимальная схожесть с центром, то целевая функция системы (1) заменяется выражением (2):

шахтах /•(с,,/?)-г(р,»')-»тт

(2)

Возможна модификация задачи (2). Пусть требуется распределить максимальное число объектов по п таксонам таким образом, чтобы расстояние объекта до центра «своего» таксона не превышало величины

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

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

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

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

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

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

Формальная постановка задачи имеет вид:

Возможна аналогичная модификация задачи (2). Пусть следует распределить как можно больше объектов по не более п таксонам таким образом, чтобы максимальное расстояние объекта от центра «своего» таксона не превышало величины суммарные затраты на распознавание образов объектов не могут превысить некоторой заданной величины 5".

Формальная постановка такой задачи для каждого конкретного случая размещения передатчиков имеет вид:

V/ :шах г(с1,р) г(р,1)^ Д,;

■2>(0 (10)

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

1. Выбор математических моделей, на которых ищется оптимальная таксономия.

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

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

Принятие решения об оптимальном упорядочении объектов на основе экспертных оценок первым способом включает этапы:

1. Постановка задачи (содержательная и формальная).

2. Проведение экспертизы (метод Дельфи).

3. Построение графа доминирования объектов.

4. Проверка (тест) графа на наличие бикомпонент. Если таковые есть, то переход к шагу 5, нет - к шагу 8.

5. Определение весовых оценок для экспертных заключений и постановка задачи о минимальном разрезе.

6. Решение задачи о минимальном разрезе на графе доминирования объектов.

6. Решение задачи о минимальном разрезе на графе доминирования объектов.

7. Удаление на графе доминирования объектов дуг, отвечающих минимальному разрезу.

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

Недостатком описанного выше подхода является то, что вследствие наличия противоречий приходится отбрасывать некоторые мнения экспертов. Во втором способе каждой альтернативе будет соответствовать точка в пространстве, с координатами, равными количеству голосов экспертов, ставящих каждую альтернативу на 1, 2, 3, ..., N место, где N - обшее число альтернатив. При этом идеальным вариантом будет альтернатива, которую все эксперты поставили на первое место.

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

Преимуществом такого подхода является то, что:

1. эксперты оценивают сразу все альтернативы;

2. учитываются голоса всех экспертов.

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

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

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

образом: Алгоритм 1

Шаг 1. Построить граф 0(Х, и), вершинами которого являются объекты и центры таксонов. Веса дуг соответствуют расстояниям между соответствующими точками. Шаг 2. Все вершины, соответствующие точкам таксонам, «стягиваются» в одну.

Шаг 3. Если на полученном графе образовались параллельные ребра, то из них оставляется только одно, обладающее минимальным весом, а остальные удаляются. Шаг 4. На полученном графе алгоритмом Прима ищется

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

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

Алгоритм 2

Шаг1. Строится матрица М, строки которой соответствуют объектам, а столбцы - таксонам, причем в каждую клеточку (/, ]) таблицы М записывается расстояние от (-Г0 объекта до центрау .¡-го таксона; Шаг 2. В каждой строке матрицы выбирается минимальный элемент. ШагЗ. Конец алгоритма: выбранные на шаге 2 клеточки матрицы определяют распределение объектов по таксонам.

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

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

следовательно, максимальная близость объектов достигается при минимальном расстоянии. Пусть Цд, |) - расстояние от q до ближайшего объекта в образе I.

Алгоритм 3

Шаг 3. Если / = п, то перейти к шагу 5, нет - к шагу 4;

Шаг5' Если ¿(^г')=т;!п-Ф'Д то г(д,{) = \, в противном случае

Шаг 6. Конец алгоритма.

Для решения задачи (5) можно применить методы дискретной оптимизации, или воспользоваться вариацией алгоритма 3.

Алгоритм 4

Шаг 3. Если ь(д,/) < О, то 0 = 1, иначе г(д,/) = 0; Шаг 5. Если «у = т, то перейти к шагу 7, иначе - к шагу 6;

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

Для поиска оптимальной таксономии на основании системы (10), можно воспользоваться регулярными методами дискретной оптимизации, такими, как прямой перебор, методы типа ветвей и границ или динамическое

программирование. В последнем случае величины R и S могут рассматриваться, как ресурсы, растрачиваемые по ходу поиска решения.

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

ITJJi) - ментальная толерантность к-го респондента; Тф(к) - физическая толерантность к-гр респондента; T(k) - общая толерантность к-го респондента; Nell)mp(k) - внутренняя напряженность k-го респондента; Мвнеш(к) - внешняя напряженность к-го респондента; N(k) - общая напряженность k-го респондента; UA - нормированная оценка на i-тый вопрос по j-тому варианту к-го респондента;

B3[i,J] - нормированная эталонная оценка на i-тый вопрос по j-тому

L[k, l\ - отметка на i-тый вопрос к-го респондента; L,[i] - эталонная отметка на i-тый вопрос;

- количество вопросов;

шЩ - количество вариантов по i-тому вопросу;

- расстояние между к-м респондентом и лучшим эталоном (характеристики объектов - значения Т,„ И Тф);

d (к,ЛЗГ$ - расстояние между к-м респондентом и лучшим эталоном (характеристики объектов - значения dj[ХЭЩЛЭП) - расстояние между худшим и лучшим эталоном (характеристики эталонов - значения

- расстояние между худшим и лучшим эталоном (характеристики эталонов - значения

- выбранный студент;

Z(p) - булева переменная, равна «1» - если р-й объект входит в группу аналогов, и «О» в противном случае;

- X-расстояние между p-м и выбранным студентом;

Q - максимально возможное расстояние между аналогами студента.

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

Алгоритм 5

Шаг 1. Ввод базы данных с сочетаниями технологических параметров каждого блока и его качественными характеристиками.

Шаг 2. Вводятся параметры определяющие таксономию блоков.

ШагЗ. На основании введенных на предыдущем шаге параметров генерируются два таксона такие, что блоки, в которых

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

Шаг 4. Сочетания режимов, соответствующие блокам, попавшим в первый таксон, выдаются на печать, как рекомендуемые.

Шаг 5. Сочетания режимов, соответствующие блокам, попавшим во второй таксон, выдаются на печать, как нерекомендуемые.

Шаг 6. Конец алгоритма.

В идеале, работа алгоритма 5 приводит к разделению всех объектов на два таксона: таксон рекомендуемых и нерекомендуемых режимов работы. Каждый таксон можно характеризовать двумя параметрами: координатами центра и радиусом. Таким образом, взаимное расположение двух таксонов 0Пр2Д2ЛЯ£ТСЯ трСМЯ Пйр2МСТр2МИ1 КХ рЗДИуС&МИ Я) И 2 ТНКЖС РАССТОЯНИЕМ между центрами таксонов Ь Возможны 4 варианта взаимного размещения таксонов:

• £ > В этом случае соотношение между радиусами Л| И ^ не имеет

значения.

• Ь<Я1+Я2,Ь>2шт{Я|;К2}.

• ¿<2тт{Л,;й2} >Д2.

• Ь < 2тт {Я); Л2}; Я]< Я2.

В большинстве случаев полученные группы пересекаются. Несмотря на это, имеется возможность выделить в каждом таксоне объекты, принадлежащие только ему одному. Именно на них и основываются дальнейшие прогнозы. На следующем этапе, выделенные рекомендуемые и нерекомендуемые режимы работы будут приняты в качестве эталонов.- При этом важно определить основные параметры, характерные для каждого режима. Для этого необходимо выделить наиболее компактные области в таксонах, соответствующих рекомендуемым и нерекомендуемым режимам и определить характеристики полученных областей. Формально модель выделения указанных областей запишется в виде (12):

где Я - максимально допустимая удаленность от центра таксона; Q -максимально возможное расстояние между объектами одного таксона.

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

Методика определения количественных характеристик напряженности и толерантности респондентов по отношению к их окружению, и, соответственно, регионов основывалась на том, что в анкете помимо выбора варианта ответа, необходимо было выразить свое отношение к каждому варианту вопросов (дать количественную оценку). А именно: 1 - очень плохо, 2 - плохо, 3 - среднее, 4 - хорошо, 5 - очень хорошо. Данный прием был

варианта ответа, необходимо было выразить свое отношение к каждому варианту вопросов (дать количественную оценку). А именно: 1 - очень плохо, 2 - плохо, 3 - среднее, 4 - хорошо, 5 - очень хорошо. Данный прием был предназначен для возможности оценивания таких характеристик как «Ментальная и физическая толерантность», «Внутренняя и внешняя напряженность» респондентов. При этом оценки вариантов ответов указывают на развитие ментального уровня, а выбранные варианты соответствуют поведению респондента в различных ситуациях. В работе приведено описание двух методов определения количественных характеристик толерантности и социальной напряженности: 1) статистический - по средним значениям; 2) таксономический - по степени удаленности от идеального объекта. Рассмотрим каждый из них.

1) Статистический подход (система (13)):

2) Таксономический подход основывается на понятии расстояния между эталоном и респондентом, при этом в качестве характеристик объектов выступают оценки и отметки вариантов ответов.

V*: Г, (*) = -!-£ В,('.¿М)

1 г.|

(13)

л ы "Г?

I <-| 1-1

Заметим, что характеристики респондентов однотипны, поэтому в системе (14) используется 8-расстояние. На основе полученных значений вычисляются соответственно показатели толерантности и напряженности (система (15)).

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

Vi;r(*)=l-4^b ti(k) = 1 -

(¡\х.эт,л.эт) а„(хзт,л.эт)

(16)

Таким образом, после выполнения расчетов по указанным формулам (выражения (13) - (16)), k-ый респондент оценивается величинами TJJi), Тф{К), Т(к), Л^нуф^), N,HelIJ(A), N(k). Тогда, для оценки толерантности и напряженности в регионах необходимо представление респондентов точкой в пространстве, с координатами: {Тм(к), Тф(к\ Т(к), Nt„m(k), Ntw,m{k), N(k)}. Далее производится группировка респондентов в каждом регионе по похожести указанных величин. Область (области), в которую попало наибольшее число респондентов, и будет характеризовать регион в целом. Данной задаче соответствует математическая модель (1).

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

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

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

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

Следующим этапом в задаче реализуется поиск аналогов заданного студента. Для этого потребуется модификация задачи (3) (выражение (17)).

т

тах

Чр-.г{Кр)1(р)<Я Чр,д:г{р,дУг{р)г(д)<<2 ур-.г{р)=щ />=1,2,...,«

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

(17)

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

В рамках данной диссертационной работы были созданы следующие программные продукты: «Подсистема поиска оптимальных стратегий изготовления МКПО»; «Автоматизированная система анализа уровня толерантности и напряженности народов Северного Кавказа»; «Автоматизированная система прогнозирования персональной успеваемости студентов в вузе».

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

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

• преимущественно все анализируемые блоки за 2002 - 2003 гг. изготавливались с разными значениями параметров. Т.е практически каждый набор соответствовал одному блоку МКП, таким образом, для более точных выводов информации недостаточно.

• Среди найденных по всем операциям технологического цикла режимов определены два: рекомендуемый и нерекомендуемый.

Автоматизированная система анализа уровня толерантности и напряженности народов Северного Кавказа связана с оценкой проведенного в регионах Северного Кавказа исследования. В рамках работы были опрошены 2229 респондентов из 7 регионов Северного Кавказа. Исследование проводилось в течение трех лет, что позволило проанализировать динамику уровня социальной напряженности и толерантности в указанных регионах. В результате выполнения работы:

• получены количественные показатели социальной напряженности и толерантности в республиках Северного Кавказа.

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

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

Результаты работы системы представлены в виде графиков и диаграмм (сайт www.skgtu.ru).

Автоматизированная система прогнозирования персональной успеваемости студентов является составной частью подсистемы АСУ ВУЗ «Деканат». Данная программа состоит из двух основных модулей. В первом -происходит расчет расстояний между всеми студентами заданной группировки (специальность, факультет); во втором - непосредственно прогнозирование, на основе найденных показателей близости студентов. Как уже упоминалось ранее, прогноз строится на основе средних значений оценок студентов, попавших в группу аналогов. При этом определяется точность прогноза и его максимальная ошибка. В найденной группировке аналогов заданного студента, могут присутствовать студенты разных курсов, что естественно не позволяет делать прогноз на весь дальнейший период обучения. Таким образом, наиболее реальным представляется делать прогноз на ближайший год. Вывод результатов производится в виде таблицы прогнозируемых оценок. При этом приводится сравнение реальной успеваемости студента с прогнозируемой.

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

ЗАКЛЮЧЕНИЕ

Настоящая диссертационная работа является законченной научно-исследовательской работой, в которой решены актуальные научно-технические задачи.

Основными результатами выполненной работы являются:

1. Разработка основ теории оптимизационных задач таксономии, выделение в рамках этой теории классов моделей, поиск оптимальных решений На КОТОрЫХ БОЗмОЖСН эффсКТИБКЫтИ аЛГСрИТмшпИ.

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

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

Выводы:

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

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

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

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

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

Публикации. По теме диссертации опубликованы работы:

1. Будаева А А. Использование информационных технологий для прогнозирования толерантности в регионах //Новые информационные технологии в науке, образовании, экономике: Материалы международной конференции. Владикавказ: Издательство «Терек», 2002. С. 145-148.

2. Будаева А.А. Использование методов таксономии при проектировании ЛВС //Новые информационные технологии и их применение: Материалы межвузовской научно-практической конференции: сборник трудов. Владикавказ: Издательство Владикавказского научного центра, 2001. С. 102105.

3. Будаева А.А. Оптимальная таксономия //Информационные технологии и системы: новые информационные технологии в науке, образовании, экономике: Материалы международной конференции. Владикавказ: Издательство Владикавказского научного центра, 2003. С. 84-87.

4. Будаева АА. Применение таксономии для групповой оценки объектов (альтернатив) //Устойчивое развитие горных территорий: проблемы и перспективы интеграции науки и образования: Материалы V международной конференции. Владикавказ: Издательство «Терек», 2004. С. 563-565.

6. Будаева А.А., Копылов И.В. Об одной модели поиска эффективных стратегий решения задач таксономии большой размерности в подсистеме АСУ «ВУЗ» // Труды СКГТУ. Владикавказ: Издательство «Терек», 2002. Вып. 9. С. 118-124.

7. Будаева А.А., Хадонов З.М. Классификация задач прогнозирования успеваемости студентов в системе дистанционного образования //Новые информационные технологии в науке, образовании, экономике: Материалы международной конференции. Владикавказ: Издательство Владикавказского научного центра, 2002. С. 15-16.

Сдано в набор 12.11.2004 г., подписано в печать 22.11.2004 г.

Гарнитура Таймс. Печать трафаретная. Формат 60x84 1/16. Бумага офсетная. Усл. печ. л. 1,28. Тираж 100 экз. Заказ№ 34.

Типография ООО НПКП «МАВР», Лицензия Серия ПД № 01107, 362040, г. Владикавказ, ул. Августовских событий, 8, тел. 44-19-31

»2618 4

Введение.

Глава 1 Обзор методов таксономии.

1.1 Основные понятия. Базовые эмпирические гипотезы.

1.2 Меры близости и сходства.

1.3 Основные типы процедур кластерного анализа.

1.3.1 Методы кластеризации полным перебором.

1.3.2 Кластеризация методами математического программирования.

1.3.3 Кластеризация на основе матрицы сходств.

1.3.4 Неиерархические кластер-процедуры.

1.4 Обзор литературы.

1.5 Постановка и систематизация задач исследования.

1.6 Выводы.

Глава 2 Постановка и методы решения задач оптимальной таксономии.

2.1 Условные обозначения, определения и допущения:.

2.2 Содержательные и формальные постановки задач.

2.3 Выбор математических моделей.

2.3.1 Метод «Дельфи».

2.3.2 Применение таксономии для выбора математической модели.

2.4 Алгоритмы поиска оптимальной таксономии объектов.

2.5 Выводы.

Глава 3 Решение прикладных задач оптимальной таксономии применительно к различным предметным областям.

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

3.1.1 Допущения и принципы.

3.1.2 Процедура генерации рекомендаций по реализации технологических режимов.

3.1.2.1 Этапы решения задачи.

3.1.2.2 Алгоритм выделения рекомендуемых и нерекомендуемых режимов.

3.1.2.3 Анализ взаимного расположения первых двух таксонов.

3.1.2.4 Определение основных характеристик выделенных режимов.

3.2 Использование таксономии для автоматизированного контроля уровня толерантности и напряженности в регионах Северного Кавказа.

3.2.1 Определения, обозначения.

3.2.2 Математическая модель поиска напряженности и толерантности

3.3 Использование таксономии при прогнозировании персональной успеваемости студентов.

3.3.1 Допущения и принципы.

3.3.2 Описание этапов решения задачи.

3.4 Выводы.

Глава 4 Постановка и результаты экспериментальной проверки программных комплексов.

4.1 Поиск оптимальных стратегий изготовления МКПО.

4.2 Анализ уровня толерантности и напряженности народов Северного Кавказа.!.

4.3 Прогнозирование персональной успеваемости студентов.

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

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

Полярной по отношению к этой технологии принятия решений, является другая, более древняя и более простая — таксономия — теория классификации и систематизации сложно организованных областей действительности [1]. Суть таксономии в свое время изложил Демокрит в «Письме ученому соседу»: «Если тебе, мой друг, нужно разобраться в сложном нагромождении фактов или вещей, ты сначала разложи их на небольшое число куч по похожести. Картина прояснится, и ты поймешь природу этих вещей»[2]. Иными словами принятие решения с помощью таксономии сводится к классификации: достаточно отнести объект к одному из таксонов, для компонент которого известно решение. Таким образом, достоинством таксономии является простота, этим объясняется её популярность: на ней базируются различные уставы (например, воинские, монастырские, учебных заведений), кодексы, методы диагностики в медицине и технике и т.п. Особо важное место таксономия занимает в тех отраслях науки, которые связаны с изучением массовых явлений и процессов. Необходимость развития методов таксономии и их использования продиктована, прежде всего, тем, что они помогают построить научно обоснованные классификации, выявить внутренние связи между единицами наблюдаемой совокупности. Кроме того, методы таксономии могут использоваться с целью сжатия информации, что является важным фактором в условиях постоянного увеличения и усложнения потоков статистических данных [3-9].

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

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

В последнее время потребность в таксономии в самых разных областях проявляется все чаще, прежде всего, в связи с процессами использования новых информационных технологий (НИТ) для обработки информации. В настоящее время практически невозможно найти области научных исследований и практической деятельности, в которых не разрабатывались бы базы данных (БД) или базы знаний (БЗ). В свою очередь создаваемые БД/БЗ должны удовлетворять определенным требованиям их использования для решения практических задач пользователями систем и/или служить одной из составляющих более сложных систем обработки информации — инструментальных аналитических систем, систем автоматизированного проектирования, систем поддержки принятия решений. И зачастую оказывается, что только предварительные исследования по таксономии соответствующих предметных областей позволяют находить достаточно эффективные и гармоничные решения по систематизации и классификации этих областей, что, в свою очередь, дает возможность разрабатывать эффективные БД с широким диапазоном их возможного использования.

В области создания информационных технологий и автоматизированных информационных систем (ИТ и АИС) необходимость в развитии таксономии осознана достаточно давно. Первые шаги в этом направлении были связаны с систематизацией огромного количества стандартов, регламентирующих развитие вычислительных систем и сетей [10-14].

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

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

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

Научная новизна диссертационной работы заключается в:

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

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

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

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

В данной работе на защиту выносятся:

• содержательные и формальные постановки оптимизационных задач таксономии объектов применительно к различным предметным областям;

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

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

• результаты экспериментального анализа эффективности созданных программных средств.

Апробация результатов работы.

Основные положения диссертации докладывались на Межвузовской научно-практической конференции в г. Владикавказ 2001 - «Новые информационные технологии и их применение»; Международной конференции Владикавказ 2002 - «Новые информационные технологии в науке, образовании, экономике»; Международной конференции в г. Владикавказе, 2002 - «Информационные технологии и системы: наука и практика»; Международной научно-технической конференции, Владикавказ, 2003 - «Информационные технологии и системы: новые информационные технологии в науке, образовании, экономике», на ежегодных научно-практических конференциях Северо-Кавказского горно-металлургического института (государственного технологического университета) и на семинарах кафедры автоматизированной обработки информации СКГМИ. По материалам диссертации опубликовано 7 печатных работ.

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

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 121 наименования, приложения, содержит 31 рисунок, 6 таблиц и 144 страницы текста.

Выводы:

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

Настоящая диссертационная работа является законченной научно-исследовательской работой, в которой решены актуальные научно-технические задачи.

Основными результатами выполненной работы являются:

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

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

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

1. Советский энциклопедический словарь. М.: Советская энциклопедия, 1990.

2. Материалисты древней Греции. М.: Мир, 1957.

3. Мандель И.Д. Кластерный анализ. М.: Финансы и статистика, 1988.

4. Backer Е. Cluster Analysis by Optimal Decomposition of Induced Fuzzy Sets. Delfts: Univ. Press, 1978.

5. Everitt B. Cluster analysis. London: Heinemann, 1981.

6. Forgy E.W. Cluster Analysis of Multivariate Data: Efficiency Versus Interpretability of Classifications, paper presented at Biometric Society meetings. Riverside, California, (abstract in Biometrics) Vol. 21, No. 3, 1965, P. 768.

7. Jambu M., Lebeaux M.-O. Cluster Analysis and Data Analysis. Amsterdam: North-Holland, 1983.

8. Rao M.R. Cluster Analysis and Mathematical Programming, Journal of the American Statistical Association, J. Amer. Statist. Assoc., Vol. 66, 1971, pp 622-626.

9. Tryon R.C. Cluster Analysis, Ann Arbor: Edwards Bros., 1939.

10. ГОСТ P ISO/IEC TO 10000-1-93 Информационная технология. Функциональный стандарт. Основы и таксономия международных функциональных стандартов. Часть 1. Основы.

11. ГОСТ Р ISO/IEC ТО 10000-2-93 Информационная технология. Функциональный стандарт. Основы и таксономия международных функциональных стандартов. Часть 2. Таксономия профилей.

12. Цыгичко В.Н. Прогнозирование социально-экономических процессов. -М.: Финансы и статистика, 1986.

13. ISO/IEC TR 10000-1: 1995 Information technology. Framework and taxonomy of International Standardized Profiles. Part 1. General principles and documentation framework.

14. ISO/IEC TR 10000-2: 1994 Information technology Framework and taxonomy of International Standardized Profiles. Part 2. Principles and Taxonomy of OSI Profiles.

15. Миркин Б.Г. Анализ качественных признаков и структур. М.: Статистика, 1980. С. 210-256.

16. Аркадьев А.Г., Браверман Э.М. Обучение машины распознаванию образов. М.: Наука, 1971. С. 10-35.

17. Загоруйко Н.Г. Линейные решающие функции, близкие к оптимальным //Вычислительные системы. Новосибирск, 1965. Вып. 19. С. 67—76.

18. Загоруйко Н.Г., Ёлкина В.Н., Емельянов С.В., Лбов Г.С. Пакет прикладных программ ОТЭКС. М.: Финансы и статистика, 1986. 96 с.

19. Прим З.Л. Кратчайшие связывающие сети и некоторые обобщения // Кибернетический сб. 1962. № 2. С. 75-124.

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

21. Боннер Р.Е. Некоторые методы классификации, в сборнике переводов «Автоматический анализ сложных изображений» М.: «Мир», 1969. С. 205-234.

22. Гладких Б.А. Некоторые проблемы классификации. //В кн.: Распознавание образов в экономико-статистическом исследовании. Новосибирск, ИЭ и ОПП СО АН СССР, 1974. С. 5-30.

23. Sepkovski J.J. Quantified coefficients of association and measurement of similarity. «J. Int. Ass. Math.», 1974, V.6, № 2. P. 135-152.

24. Айвазян C.A., Бежаева З.И., Староверов O.B. Классификация многомерных наблюдений. М.: Статистика, 1974. 240 с.

25. Айзерман А.А., Браверман Э.М., Розоноэр Э.И. Метод потенциальных функций в теории обучения машин. М.: Наука, 1970. С. 26-35.

26. Wallace C.S., Boulton D.M. An informational measure for classification. «The Computer J.», 1968. V. 11. P. 185-194.

27. Елисеева И.И., Рукавишников В.О. Группировка, корреляция, распознавание образов (статистические методы классификации и измерения связей). М.: Статистика, 1977. 144 с.

28. Мамчур Е. А. Проблема выбора теории. М.: Наука, 1975. С. 68-82.

29. Дюк В., Самойленко A. Data mining: Учебный курс (+CD). СПб; М.; Харьков; Минск: Питер, 2001. С. 116-130.

30. Jensen R.E. A dynamic programming algorithm for cluster analysis. Operations Res., 12,Nov.-Dec. 1969. P. 1034-1057.

31. Vinod H.D. Integer programming and theory of grouping. JASA, Jun., 1969. P. 506-519.

32. Двоенко С.Д. Неиерархический дивизимный алгоритм группировки //АиТ. 1999. №9. С. 47-57.

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

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

35. Загоруйко Н.Г., Ёлкина В.Н., Лбов Г.С. Алгоритмы обнаружения эмпирических закономерностей. Новосибирск: Наука, 1985. 110 с.

36. Загоруйко Н.Г. Классификация задач прогнозирования на таблицах «объект—свойство» //Вычислительные системы. Новосибирск, 1981. Вып. 88. С. 3-8.

37. Загоруйко Н.Г. Методы обнаружения закономерностей. Серия «Математика, кибернетика» № 11, М.: Знание, 1981. С. 19—35.

38. Загоруйко Н. Г. Анализ данных и анализ знаний //Вычислительные системы. Новосибирск, 1994. Вып. 150. С. 3-17.

39. Блехер П. М., Кельберт М. Я. Доказательство сходимости алгоритма «Форель» //Прикладной статистический анализ. М.: Наука, 1978. С. 358361.

40. Берж К. Теория графов и её применения. М.: Изд. Иностранной литературы, 1962. С. 35-78.

41. Елкина В.Н., Загоруйко Н.Г. Количественные критерии качества таксономии и их использование в процессе принятия решений //Вычислительные системы. Новосибирск, 1969. Вып. 36. С. 29-47.

42. Загоруйко Н. Г. Таксономия в анизотропном пространстве. Эмпирическое предсказание и распознавание образов //Вычислительные системы. Новосибирск, 1978. Вып. 76. С. 26-34.

43. Загоруйко Н.Г. Метакритерий для отбора предикатов в алгоритмах прогнозирования: Тр. 3-го Сибирского Конгресса по прикладной и индустриальной математике (ИНПРИМ-98). Новосибирск, 1998. Часть IV. С. 95-96.

44. Tryon R.C. and Bailey D.E. The ВС TRY computer system of cluster and factor analysis, Multivar. Behav. Res., 1966. P. 1, 95-111.

45. Fisher W. D. Clustering and Aggregation in Economics. The Johns Hopkins Press, Baltimore, Maryland, 1968. P. 134-145.

46. Cole A.J. Numerical Taxonomy, Academic Press, New York, 1969. P. 25-69.

47. Jardine N. and Sibson R. Mathematical Taxonomy, John Wiley and Sons, New York, 1971. P. 313-368.

48. Jardine C.J., Jardine N. and Sibson C. The structure and construction of taxonomic hierarchies, Mathematical Biosciences, Vol. 1, No. 2, 1967. P. 173-179.

49. Jardine N. and Sibson R. A model for taxonomy, Math. Biosci., 2, 1968. P. 465-482.

50. Jardine N. and Sibson R. The construction of hierarchic and nonhierarchic classifications, Comput. J. Vol. 11, 1968. P. 177-184.

51. Jardine N. Towards a general theory of clustering, Biometrics, 25, 1969. P. 609-610.

52. Anderberg M.R. An Annotated Bibliography of Cluster Analysis, Mechanical Engineering Department, University of Texas at Austin (in preparation), 1972. 478 p.

53. Anderberg M.R. Cluster Analysis for Applications, Academic press, New York, 1973. P. 128-198.

54. Ball G.H. A Comparison of Some Cluster. Seeking Techniques, Report Number RADC-TR-66-514, Stanford Research Inst. Menlo Park, California, 1966. P. 47.

55. Bryan J.K. Classification and clustering using density estimation, Ph. D. Dissertation, University of Missouri, Columbia, Missouri, Aug., 1971. P. 25— 39.

56. Elkins T.A. Cubical and spherical estimation of multivariate probability density, J. Amer. Statist. Assoc., Vol. 64, 1969. P. 1947-1948.

57. Parzen E. On estimation of probability density function and mode, Ann. Math. Statist., Vol. 33, 1962. P. 1065-1076.

58. Rosenblatt M. Remarks on some nonparametric estimates of a density function, AMS 27, 1956. P. 832-837.

59. Sokal R.R. and Sneath P.H. A Principles of Numerical Taxonomy, San Francisco: W. H. Freeman and Company, 1963. P. 332-346.

60. Holley W.A. Description and user's guide for the IBM 360/44 ISODATA PROFRAM, Lockheed Electronics Co., Inc., HASD, Houston, Texas, Tech. Rep. 640-TR-030, Sept., 1971. P. 271-325.

61. Kan E.P.F. and Holley W.A. Experience with ISODATA, Lockheed Electronics Co., Inc., HASD, Houston, Texas, Tech. Memo TM 642-354, Mar., 1972. P. 187-203.

62. Kan E.P.F. ISODATA: Thresholds for splitting clusters, Lockheed Electronics Co., Inc., HASD, Houston, Texas, Tech. Rep. 640-TR-058, Jan., 1972. P. 1565.

63. Kan E.P.F. and Holley W.A. More on clustering techniques with final recommendations on ISODATA, Lockheed Electronics Co., Inc., HASD, Houston, Texas, Tech. Rep. LEC 640-TR-l 12, May., 1972. P. 23-75.

64. Koontz W.L. and Fukunaga K. A nonparametric valley-seeking technique for clustering analysis, IEE Trans, on Computers, Vol. C-21, No. 2, Febr., 1972. P.171-178.

65. Ruspini E.H. A new approach to clustering, Information and Control, Vol. 15, 1969. P. 22-32.

66. Singleton R.C. Minimum squared-error clustering, Unpublished Internal Communication at Stanford Research Institute, Menlo Park, California, 1967. 687 p.

67. Wolfe J.H. Pattern clustering by multivariate mixture analysis, Multivariate Behavioral Research, Vol. 5, No. 3, 1970. P. 329-350.

68. Edwards A.W.F. and Cavalli-Sforza L.L. A method for cluster analysis, Biometrics, Vol. 21, No. 2, 1965. P. 362-375.

69. MacNaughton-Smith P. and Williams W.T., Dale M.B. and Mockett L.G. Dissimilarity analysis: A new technique of hierarchical division, Nature, Vol. 201, 1964. 426 p.

70. Rescigno A. And Maccacaro G.A. The information content of biological classifications, in C. Cherry (ed.), Information Theory, 4th London Symposium, Butterworths, London, 1961. P. 437-446.

71. Lance G.N. and Williams W.T. A general theory of classificatory sorting strategies. I. Hierarchical systems, Comput. J., Vol. 9, No. 4, 1967. P. 373— 380.

72. MacNaughton-Smith P. Some statistical and other numerical techniques for classifying individuals, (home office res. rpt. no. 6) H. M. O., London, 1965. 369 p.

73. Ward J.H. Jr. Hierarchical grouping to optimize an objective function, J. Amer. Statist. Assoc., Vol. 58, No. 301, 1963. P. 236-244.

74. Ball G.H. and Hall D.J. ISODATA, A Novell Method of Data Analysis and Pattern Classification, Technical Report, Monlo Park, California: Stanford Research Inst., 1965. P. 72.

75. MacQueen J.B. Some methods for classification and analysis of multivariate observations, Western Management Sci. Inst., University of California, working paper 96, 1966. P. 325-327.

76. Gower J.C. A comparison of some methods of cluster analysis, Biometrika, Vol. 23, No. 4, 1967. P. 623-637.

77. Sokal R.R. and Michener C.D. A statistical methods for evaluating systematic relationships, University of Kansas Sci. Bull., Mar., 20, 1958. P. 1409-1438.

78. Williams W.T. and Lambert J.M. Multivariate methods in plant ecology I. Association analysis in plant communities, J. Ecology, Vol. 47, No.l, 1959. P. 83-101.

79. Rand W.M. The Development of Objective Criteria for Evaluating Clustering Methods, Ph. D. Dissertation, UCLA, Cited in Dissertation Abstracts, Vol. 30, No. 11, May, 1970. P. 336-342.

80. Fisher L. and Van Ness J. Admissible clustering procedures, Biometrika 58, 1971. P. 91-104.

81. Hartigan J. A. Representation of similarity matrices by trees, J. Amer. Statist. Assoc., Vol. 62,1967. P. 1140-1158.

82. Johnson S.C. Hierarchical clustering schemes, Phychometrika, Vol. 32, No.3 Sept. 1967. P. 241-254.

83. Fisher L. and Van Ness J. Admissible discriminant analysis, J. Amer. Statist. Assoc. 68, 1973. P. 603-607.

84. Hartigan J. A. Direct clustering of a data matrix, J. Amer. Statist. Assoc., Vol. 67, 1972. P. 123-129.

85. Wishart D. Mode analysis: A generalization of nearest neighbor which reduces chaining effects, In A.J. Cole (ed.), Numerical Taxonomy, Academic Press, New York, 1969. P. 282-319.

86. Sorenson T. A method of establishing groups of equal amplitude in plant sociology based on similarity of species content and its application for analyses of the vegetation on Danish commons, Biol. Skr. 5, 1968. P. 1—34.

87. Bonner R.E. On some clustering techniques //IBM Journal, Jan., 1964. P. 2232.

88. Hyvarinen L. Classification of Qualitative Data, Brit. Info. Theory J., 1962. P. 83-89.

89. Sebestyen G. S. Pattern recognition by an adaptive process of sample set construction, IRE Trans, on Info. Theory, Vol. IT-8, Sept, 1962. P. 111-126.

90. Jancey R.C. Multidimensional group analysis, Australian J. Botany, Vol. 14, No. 1, 1966. P. 127-130.93. Ёлкина B.H., Загоруйко Н.Г., Новоселов Ю.А. Математические проблемы агроинформатики. Новосибирск: изд. Ин-та математики СО РАН, 1987. С. 147-174.

91. Загоруйко Н.Г., Ёлкина В.Н., Тимеркаев B.C. Алгоритм заполнения пропусков в эмпирических таблицах (алгоритм ZET) //Вычислительные системы. Новосибирск, 1975. Вып. 61. С. 3-27.

92. Загоруйко Н.Г., Ульянов Г.В. Локальные методы заполнения пробелов в эмпирических таблицах //Вычислительные системы. Новосибирск, 1988. Вып. 126. С. 75-121.

93. Воронин Ю.А. Введение мер сходства и связи для решения геолого-географических задач. Докл. АН СССР, 1971. Т. 199. № 5. С. 1011-1015.

94. Загоруйко Н.Г. Согласование разнотипных шкал //Вычислительные системы. Новосибирск, 1983. Вып. 99. С. 3-14.

95. Лбов Г.С. Методы обработки разнотипных экспериментальных данных. Новосибирск: Наука, 1981. С. 58-79.

96. Черный Л.Б. Порождение мер связи между объектами с помощью мер связи между признаками. //В кн.: Проблемы анализа дискретной информации. Новосибирск: изд. ИЭиОПП СО АН СССР, 1975. С. 167174.

97. Шустрович A.M. Об адекватных парных мерах сходства в задачах распознавания образов с разнородными признаками //Вычислительные системы, Новосибирск, 1977. Вып. 69. С. 147-152.

98. Meril Т., Green О.М. On the effectiveness of receptors in recognition systems // IEEE Trans. Inform. Theoiy, 1963. V. IT-9. P. 11-17.

99. Бурков В.Н., Гроппен В.О. Максимальная циркуляция и минимальный разрез на планарных орграфах. Кибернетика № 6, 1975. С. 85-89.

100. Бурков В.Н., Гроппен В.О. Разрезы в сильносвязных графах и потенциалы перестановок. Автоматика и телемеханика, № 6, 1972. С. 111-119.

101. Бурков В.Н., Гроппен В.О. Решение задачи о минимальном разрезе в бисвязном орграфе алгоритмами типа ветвей и границ. Автоматика и телемеханика № 9,1974. С. 104-110.

102. Ш.Оре О. Теория графов. М.: Наука, Главная редакция физико-математической литературы, 1980. 336 с.

103. Лесин В.В., Лисовец Ю.П. Основы методов оптимизации. М.: Изд-во МАИ, 1998. С. 223-268.

104. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. М.: Мир, 1985. С. 93-138.

105. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. М.: Наука, 1986. С. 30-95.

106. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. 960 с.

107. Нефедов В.Н., Осипова В.А. Курс дискретной математики. Учеб. пособие. М.: Изд-во МАИ, 1992. С. 5-67.

108. Солдатова Г.У. Психология межэтнической напряженности. М.: Смысл, 1998. С. 48-56.

109. Будаева А.А. Использование информационных технологий для прогнозирования толерантности в регионах //Новые информационные технологии в науке, образовании, экономике: Материалы международной конференции. Владикавказ, 2002. С. 145-148.

110. Будаева А.А Учет прогнозирования толерантности методами таксономии //Информационные технологии и системы: наука и практика: Материалы международной конференции. Владикавказ: Издательство Владикавказского научного центра, 2002. С. 263-265.

111. Будаева А.А., Копылов И.В. Об одной модели поиска эффективных стратегий решения задач таксономии большой размерности в подсистеме АСУ «ВУЗ» //Труды СКГТУ. Владикавказ: Издательство «Терек», 2002. Вып. 9. С. 118-124.