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

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

003457ЭЭО

Вовк Алексей Андреевич

ТЕХНОЛОГИЯ ПОСТРОЕНИЯ ОБОБЩЕННОГО «И/ИЛИ» ДЕРЕВА РЕШЕНИЯ ЗАДАЧ

05.13.17 - теоретические основы информатики

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

" 2008

Красноярск - 2008

003457990

Работа выполнена в Сибирском федеральном университете

Научный руководитель:

доктор технических наук, профессор Цибульский Геннадий Михайлович

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

Носков Михаил Валерианович,

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

Ведущая организация:

Институт вычислительной математики и математической геофизики СО РАН

Защита диссертации состоится 30 декабря 2008 года в 14.00 часов на заседании диссертационного совета Д 212.099.11 при Сибирском федеральном университете по адресу: 660074, г. Красноярск, ул. Киренского, 26, корпус Ж, ауд. 1=15.

С диссертацией можно ознакомиться в научной библиотеке Сибирского федерального университета по адресу: ул. Киренского, 26, ауд. Г274.

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

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

Покидышева Л. И.

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

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

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

В рамках цели решаются следующие задачи:

1) Анализ применимости операции над графами теории графов к «И/ИЛИ» деревьям решения задач.

2) Определение операции объединения вершин «И/ИЛИ» дерева, представляющих цели в пространстве целей.

3) Определение операции объединения решающих «И» деревьев в «И/ИЛИ» дерево.

4) Разработка алгоритма объединения решающих «И» деревьев в «И/ИЛИ» дерево.

5) Исследование сходимости процесса построения обобщенного «И/ИЛИ» дерева для класса задач.

Научная новизна работы:

1) Введено понятие совпадающих кластеров в пространстве целей и определена операция объединения пары совпадающих кластеров в объединенный кластер. Введено понятие совпадения «И» и «И/ИЛИ» деревьев решения задач через совпадающие вершины, представленные кластерами в пространстве целей.

2) Определена операция объединения «И/ИЛИ» деревьев. Данная операция позволяет путем объединения решающих «И» деревьев, построенных в

результате взаимодействия решающей системы и пользователя-природоведа, сформировать обобщенное «И/ИЛИ» дерево, описывающее статическую структуру оригинала. Разработан новый алгоритм объединения «И/ИЛИ» деревьев решения задач.

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

4) Выведена теоретическая оценка скорости сходимости процесса построения обобщенного «И/ИЛИ» дерева для класса задач.

Практическая ценность работы:

Разработан программно-аппаратный комплекс, позволяющий осуществлять объединение решающих «И» деревьев задач анализа сложных в обобщенное «И/ИЛИ» дерево. Комплекс внедрен и используется на Институте леса им. В.Н. Сукачёва СО РАН, а также в учебном процессе СФУ.

По материалам исследований опубликовано пять статей, из которых: одна опубликована в сборниках, рекомендованных ВАК, две статьи депонированы.

Диссертационная работа включает: содержание, введение, три главы, и заключение. Работа содержит 104 страницы машинописного текста, 43 рисунка и 21 таблицу. Список литературы содержит 110 наименований.

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

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

В первой главе анализируется понятие «И/ИЛИ» дерева решения задач, как способа представления статической структуры оригинала в пространстве задач. Производится сопоставление понятия «И/ИЛИ» дерева со строгим определением дерева теории графов и применимость операций над графами теории графов к «И/ИЛИ» деревьям решения задач.

В результате установлено, что «И/ИЛИ» дерево лишь частично соответствует определению дерева теории графов и имеет характерные особенности:

1. Наличие циклов в «И/ИЛИ» дереве, что может интерпретироваться следующим образом: одна и та же вершина может являться дочерней для не-

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

2. Корневая вершина «И/ИЛИ» дерева соответствует исходной цели, а все остальные вершины - подцелям исходной цели на разном уровне детализации.

3. Между ребрами дерева существуют отношения «И» и «ИЛИ». Наличие отношения «ИЛИ» указывает на, что «И/ИЛИ» дерево содержит несколько путей достижения исходной цели.

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

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

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

Во второй главе определяется операция объединения «И» деревьев в «И/ИЛИ» дерево. Объединение «И» деревьев осуществляется посредством поиска совпадающих вершин объединяемых деревьев и построения объединенных вершин-элементов результирующего дерева. С этой целью вводится понятие совпадающих кластеров и способ построения

5

понятие совпадающих кластеров и способ построения объединенного кластера. Процесс построения «И/ИЛИ» дерева исследуется на сходимость: формулируется критерий сходимости и оценка скорости сходимости.

Задачу классификации определим следующим образом: В признаковом пространстве X задано т классов множеством своих эталонов {-£(}™ь р(х, у) -метрика, определенная в пространстве X. Для каждого класса задан критерий компактности e¡. Для всех классов выполнено условие е-непересекаемости. Всякий объект х относится к тому классу, для которого p(£¡, x¡) < e¡, т.е. расстояние между исследуемым объектом и эталоном класса, удовлетворяет критерию компактности данного класса. Если же объект не будет отнесён ни к одному известному классу, он будет классифицирован как «неизвестный» или как фон.

Каждая цель «И/ИЛИ» дерева целей является задачей опознавания, определяемая кластером, заданным в признаковом пространстве X(xi,x2,-..pcn) значениями эталонаЕ(е\,ег,-..,е„) и критерия компактности e(s\,E2,...,£„)•

Пусть в некотором признаковом пространстве Х(х\^сг»•••лО заданы два кластера А\ и Ai своими эталонами Е\{е\<ъе\ г,---,е\,п) и £2(^2,ье2,2.- • и критериями компактности 81(61,1,81,2,.. .,£i,„) и £2(22, ь£г,2,-. .,£2,п)-

Кластеры A¡ и Аг называются совпадающими, если эталон каждого из них принадлежит другому кластеру (рис. 1). Т.е. \ец - e2,¡| < min(ei,¡, e2,¡), ¡ ~ l,...,n.

Объединенным кластером для пары совпадающих кластеров А\ и А2 называется кластер А3, эталон е3,2,..., ез,„) и критерий компактности £з(£з,ь£з,2,--->ез,п) которого рассчитываются по формулам:

Е _ СаЕ\+СА2Е2 3= ^ '

где С, и С а, - весовые коэффициенты кластеров А\ иА2;

£3¡ = шах(г1;+1 еу - e3J s2J+1 е2 . - еу |), i = .

Весовой коэффициент (С) кластера Л равен единице (СА = 1), если кластер А был найден в процессе достижения цели или был задан априори. Если кластер А был построен, как объединенный для пары совпадающих кластеров Ai и Аг, то:СЛ= С ^ + САг.

а, ;

а2

Рисунок 1 - Кластеры Л1 и Аг совпадают

А,

Рисунок 2 - Объединение совпадающих кластеров

Так как каждой вершине «И» дерева соответствует кластер то, вершины называются совпадающими, если совпадают соответствующие им кластеры. Вершина А3 называется объединенной вершиной для совпадающих вершин А\ и Аг, если она соответствует объединенному кластеру для совпадающих кластеров вершин А1 и Л2. Весовым коэффициентом вершины называется весовой коэффициент кластера, соответствующего данной вершине. Для обозначения совпадающих вершин используется знак

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

Два двухуровневых «И» дерева называются полностью совпадающими, если на соответствующих уровнях данных деревьев все вершины совпадают.

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

Два двухуровневых «И/ИЛИ» дерева называются полностью совпадающими, если:

1) каждая вершина одного дерева совпадает с вершиной соответствующего уровня другого дерева;

2) для каждого двухуровневого «И» поддерева одного из деревьев найдется полностью совпадающее с ним «И» поддерево другого дерева.

Два «И/ИЛИ» дерева называются полностью совпадающими, если для всякого двухуровневого «И/ИЛИ» поддерева в одном из деревьев существует полностью совпадающее с ним двухуровневое «И/ИЛИ» поддерево в другом дереве.

Два «И/ИЛИ» дерева называются полностью совпадающими, если для всякого двухуровневого «ШИЛИ» поддерева в одном из деревьев существует полностью совпадающее с ним двухуровневое «И/ИЛИ» поддерево в другом дереве.

Два «И/ИЛИ» дерева называются частично совпадающими, если хотя бы один узел одного дерева совпадает с узлом другого соответствующего уровня другого дерева.

Введем способ задания «И/ИЛИ» дерева. «И/ИЛИ» дерево О описывается тройкой С? = {Су ,0Е,С[}, где:

1) множество вершин Су = {<-?,,Сг2,...,Сгп}, где

С, - множество вершин /-го уровня дерева С,п- число уровней дерева

с?;

2) - множество ребер дерева (7;

3) С1 - множество двухуровневых «И» поддеревьев дерева <3.

Приведем алгоритм объединения двух «И/ИЛИ» деревьев. Т.к. «И» дерево является частным случаем «И/ИЛИ» дерева, следовательно, данный алгоритм применим и для объединения «И» дерева с «И/ИЛИ» деревом.

Пусть заданы два дерева С1 =({(?,,С^,...,(?'},и

О2 =({0*. Результатом работы алгоритма является «И/ИЛИ» дерево С?3, обобщающее деревья (?' и (?2:

<53 = ({С?,3.С?3,...^3}^3^3).

Суть алгоритма в последовательном просмотре уровней обоих деревьев и поиске совпадающих вершин на соответствующих уровнях. Если совпадающие вершины найдены, то для каждой пары совпадающих вершин строится объединенная вершина. При этом вхождение совпадающих вершин в

множества и?, О),01,01 заменяются на построенную объединенную вершину. Результирующие дерево строится из объединенных вершин для совпадающих вершин исходных деревьев, вершин, для которых не нашлось совпадающих, и всех ребер исходных деревьев с учетом замены совпадающих вершин на объединенные вершины.

1) Полагаем ¿=1.

2) Строим новое множество С,3 - 0 .

3) Если множество С?2 пустое, то переходим к шагу 11, иначе переходим к шагу 4.

4) Если множество С,1 пустое, то переходим к шагу 11, иначе переходим к ищу 5.

5) Первую вершину из множества С2 обозначим А. Поочередно сравниваем А

с каждой вершиной множества . Если найдена вершина множества ^; совпадающая с А, то обозначаем ее В и переходим к шагу 6, иначе переходим к шагу 10.

6) Для пары совпадающих вершин А и В строим объединенную вершину, которую обозначим С. Добавляем С к множеству в*.

7) Все вхождения вершины А в ребра множества 0\ заменяем на вершину С.

Все вхождения вершины А в поддеревья множества С?2 заменяем на вершину 2

С. Если в и£ образовались одинаковые ребра, то повторения удаляем. Если в £7/ образовались одинаковые поддеревья, то повторения удаляем.

8) Все вхождения вершины В в ребра множества заменяем на вершину С. Все вхождения вершины В в поддеревья множества С?] заменяем на вершину С. Если в образовались одинаковые ребра, то повторения удаляем. Если в

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

9) Исключаем вершину В из множества С?/.

10) Исключаем вершину Л из множества С?,2. Переходим к шагу 3.

11) Строим множество <-?/ = С,3 и С,1 и С,2. (Данную операцию можно интерпретировать так: добавляем к множеству (?,3 все элементы множеств С,1 и С?,2, если таковые остались после выполнения предыдущих шагов алгоритма.

Таким образом, Gf содержит построенные объединенные вершины для совпадающих вершин множеств С- и С,2 и все несовпадающие вершины этих множеств.)

12) Если г = п, то алгоритм завершен, иначе полагаем г = I + 1 и переходим к шагу 2 (другими словами, повторяем шаги 2-11 для каждого уровня объединяемых деревьев).

Результатом работы алгоритма является «И/ИЛИ» дерево (73, обобщающее деревья С1 и О1: О3 = {{Съх ,С1,..,,Огп},С\,С]). Схема предложенного алгоритма приведена на рисунке 3.

Рисунок 3 - Схема алгоритма объединения «И/ИЛИ» деревьев

Пусть и((?1, Сг) - операция построения обобщенного «И/ИЛИ» дерева для двух «И/ИЛИ» деревьев С] и С2, определенная в соответствии с разработанным алгоритмом. Операнды могут быть С] и (72 как «И/ИЛИ» деревьями, так и «И» деревьями.

Пусть «И/ИЛИ» дерево = и{С\, б2). От дерева О] дерево Оз может в общем случае отличаться следующими параметрами:

1) структурой «И/ИЛИ» дерева, а именно:

а) в дереве бз добавились новые вершины, которых не было в (7);

б) в дереве появились отношения «И» или «ИЛИ» между ветвями, которых не было в Си

2) изменились вершины (эталоны и критерии компактности соответствующих вершинам кластеров) дерева С], входящие теперь в состав дерева (73.

Нетрудно видеть, что структура «И/ИЛИ» дерева бз не изменяется по сравнению с деревом при объединении его с «И» деревом С2, если дерево С?2 удовлетворяет условию: Всякое двухуровневое «И» поддерево дерева (?2 полностью совпадает с некоторым двухуровневым «И» поддеревом дерева

Пусть $((7) - функция, вычисляющая сумму весовых коэффициентов всех вершин дерева С?.

Из определения весового коэффициента кластера и операции и следует,

что:

¿МвиЪ))-* 5(01) + 5((?2). (1)

Пусть - функция, вычисляющая количество вершин дерева в. Пусть заданы множество {Т\, Т2,..., Г„} решающих «И» деревьев задач

одного класса и последовательность {С,}м обобщенных «И/ИЛИ» деревьев для задач данного класса, определенных следующим образом:

С, = Г„

ф = м(С7ц, 71), ¡' = 2,3,...,к.

(2)

Тогда коэффициентом прироста дерева 6\+1 по сравнению с деревом назовем величину:

Очевидно, что 3(<3^, ) > 0.

Равенство ¿/((Зь = 0 говорит о том, что в «И/ИЛИ» дереве Сгк+, не

появились новые узлы по сравнению с исходным «И/ИЛИ» деревом (?к при объединении его с решающим «И» деревом 7к+|.

Пусть А], Аг - кластеры, определенные в признаковом пространстве X. Е\, Е\- эталон и критерий компактности кластера А\,Е%,ег — эталон и критерий компактности кластера А2.

ЩАиАг) - операция построения объединенного кластера для пары совпадающих кластеров А\, А2.

Пусть Аг = и(А\,А2) - объединенный кластер для совпадающих кластеров^! и Аг) Е3, £з ~ эталон и критерий компактности кластера Л3.

Коэффициентом изменения кластера Аз по сравнению с кластером А, для совпадающих вершин А\ и А2 будем называть величину:

В(4,А3) =

где р{Еи Ез) - евклидово расстояние между Ех и £3 в пространстве X.

Использование £] в знаменателе данной формулы необходимо, т.к. кластеры, соответствующие вершинам дерева, на разных уровнях дерева описываются качественно различными признаками с различным разбросом значений. На пример, в решающем «И» дереве задачи анализа космофотоснимков лесов Саян кластеры, соответствующие вершинам на уровне пикселей описываются текстурными признаками с разбросом значений 0-90. Значения признаков (площадь, периметр и др.) уровня сегментов имеют разброс 100-2500.

Итак, пусть задана последовательность обобщенных «И/ИЛИ»

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

1) коэффициент прироста обобщенного «И/ИЛИ» дерева с?((?п, С?п+1) не превышает некоторую наперед заданную малую величину;

2) максимальный коэффициент изменения А;) по всем изменившимся вершинам обобщенного «И/ИЛИ» дерева С„+1 по сравнению с обобщенным «И/ИЛИ» деревом (?„ не превышает некоторую наперед заданную малую величину.

Сходимость процесса формирования обобщенного «И/ИЛИ» дерева означает, что на некотором шаге объединения текущего «ИУИЛИ» дерева с очередным «И» деревом полученное «И/ИЛИ» дерево будет отличаться от текущего не более, чем на требуемую величину. Т.е. обобщенное «И/ИЛИ» дерево приобретет устойчивость.

Замечание: Следует отличать введенное понятие сходимости процесса построения обобщенного «И/ИЛИ» дерева решения задач от сходимости последовательностей или рядов. Сходящимися в определениях математического анализа здесь являются последовательности коэффициентов прироста дерева и коэффициентов изменения кластера. Поэтому сходимость последовательности «И/ИЛИ» деревьев правильно будет считать внутренней сходимостью или стабилизацией обобщенного «И/ИЛИ» дерева.

Утверждение: Пусть {Ти Т2,...} множество решающих «И» деревьев задач одного класса и последовательность {С.}™, обобщенных «И/ИЛИ» деревьев для задач данного класса, определенны следующим образом: <?1 = Ти

ф = и((?и, т-д, ¿ = 2,3,... Если для всех «И» деревьев Т-, задач заданного класса существует М е N такое что, q(Tj)<M, т.е. количество вершин во всех возможных решающих «И» деревьях задач данного класса ограничено, то процесс построения обобщенного «И/ИЛИ» дерева для данного класса задач сходится. Доказательство:

1. Докажем, что ¡Ш* ^, ) = 0 _

Иш¿(Сп,вп+1) = Иш = Иш

я->м п-><*> л-*® ^((г )

Величина ,Тп+1)) -д(Оп) показывает, сколько новых узлов поя-

вилось в обобщенном «И/ИЛИ» дереве при объединении его с «И» деревом Г„+[. Так как у деревьев (?„ и Гп+1 совпадают, по крайней мере, корневые вершины, то:

д(и(ОМ) - < д{Сп) + ?(Г„+1) -1 - д((7и) = ^(Гл+1) -1 < М -1

Тогда:

п

Учитывая (1), = .

н

Следовательно, ¿п!" = и, т.к. все деревья Т„ содержат как минимум одну вершину. Тогда:

.. М-1 М-1

hm-< hm-

n->®j(Gn) я_>а> n

Итак:

О < lim d(Gn, Gn+l) < lim = 0

n—>00 л-юз yj '

следовательно: üm d(Gn, Gn+l) = 0

П->CD

2. Пусть {A\,A2, ...} множество кластеров и последовательность кластеров > определенны в признаковом пространствеX, так что:

В\- U(Bi.i,Ai), г = 2,3,... Пусть £„(>„,¡,e„j,т), £n(£n,b£n,2v,en,m) - эталон и критерий компактности кластера Вт £„+,(<?„+,,be„+i>2,...,en+lirn), e„+1(£n+u,en+i,2,...,e„+i,m)-эталон и критерий компактности кластера Aa+i. Докажем, что , Вп+]) = 0.

р(Е»> с +с-}

limD(Bn,Bn+x) = limD(B„M(B„,An+})) = lim-, , -=

— lim « + 1 _iL±]_-

= lim--= lim-

Я—>oo | О I AI-4CO

Ун И + 1 v(« + l) Ы = hm—-= lim—-—-<

millfl Sn l' l Sn+l 1)Л' 1

<lim-^1<Нт.М- = 0

П-* CO

Итак:

0<В(Вп,Вп+,)<Пт 1^-=0> я-*0 V « + 1

следовательно: > $„+1) = 0 .

Утверждение доказано.

Следствие 1: Пусть {Т\, Т2, ...} множество решающих «И» деревьев задач

одного класса и последовательность {С, }", обобщенных «И/ИЛИ» деревьев для задач данного класса, определенны следующим образом: С1 = Г„

^ = а((7и,^),/ = 2,3,... Если для всех «И» деревьев 7], г'=1,2,... задач заданного класса 3М еЫ такое

М-1

что, то У 8 > 0. выполняется ¿/ (С?, Сп+1) < ¿> для п>—;—,

о

пе N.

Доказательство:

= 9(5.) + ~1 - = д(Тп+1)~ 1 ^ -1 ^ М -1 *(<?„) *(<?„) и л ■

М-1 м-1 М-1 _ -Т.к. ,то: „ < м-1 ~

Итак: <Ц<Эп,Сп+,)< 8. Следствие доказано.

Суть следствия заключается в том, что если количество вершин во всех возможных решающих «И» деревьях задач данного класса ограничено некоторым числом М, то необходимая точность 5 будет достигнута не более, чем

М-1 за ^ шагов.

Следствие 2: Пусть {А\,А2,...} множество кластеров и последовательность кластеров {Д }ы, определенны в признаковом пространстве X., так что: Вх=Аи

В^ЩВ^, Ад, 1 = 2,3,....

Тогда У 8 > 0 выполняется Б(ВП, Вп+1 )<8 для п > ^ " 1 , п е N. Доказательство:

Пусть Еп{еп \,еп2,.■ .,епт), £„(£„,ьеп>2,...,еп,т) - эталон и критерий компактности кластера Ва, Еп+1(еп+и,еа+и2,...,еп+1т), еп+,(еп+1,,,еп+,>2)...,е„+1,т)-эталон и критерий компактности кластера А„+1.

С к Е„ + С. Е„.,

" Лг )

пЕ„ + Е„.

Ся + С

Р{Е" и + 1 ^ПГ" я + 1 ; ..

Я + 1 ' .V

1

0 + 1) ы

т

Ек.-^и)2

(И + 1)

И + 1

\2

= 5

-1 + 1

Итак: В(Вп,Вп+1) < 5 . Следствие доказано.

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

I ^ 1 шагов.

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

В третьей главе представлены экспериментальные результаты.

Целью проводимых экспериментальных исследований является проверка работоспособности разработанной технологии построения обобщенного «И/ИЛИ» дерева для решающих «И» деревьев класса задач.

В эксперименте были использованы космофотоснимки «Ьанс^™» лесов Саян и четыре выборки, представляющие участки леса с различными ха-

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

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

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

3) Для множества выделенных примитивов системой осуществлялось построение сегментов. Для каждого сегмента производился расчет признаков уровня сегментов. В полученной системе признаков множестве сегментов разбивалось на кластеры. Разбиение производилась с помощью алгоритма ЗБСЮАТА на априори не заданное число кластеров. Сформированные таким образом кластеры, соответствуют вершинам «И» дерева уровня сегмент.

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

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

Таким образом, было построено четыре решающих «И» дерева для целей пользователя: Ти Т2, Т3, Г4. Последовательность обобщенных «И/ИЛИ» деревьев имела вид:

<?2 = и(ТьТ2)\

<?з = "(0;>, Гз);

С?4 = и( вз, Г4).

На каждом шаге объединения «И» деревьев вычислялись коэффициенты прироста дерева и коэффициенты изменения кластеров. На первом шаге коэффициенты равны:

¿(Гьс2) = 0,429

тахО = 0,202

Ог

На третьем шаге соответственно: = 0,0467

тах£) = 0,086

с„

На основании полученных результатов в целом можно сделать вывод об адекватности предложенных операций построений объединенного кластера и объединения «И/ИЛИ» деревьев. Экспериментально продемонстрировано, что имеет место сходимость процесса построения обобщенного «И/ИЛИ» дерева для класса задач. Установлено также, что скорость сходимости на практике гораздо выше чем, предложенная теоретическая оценка.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1) Введено понятие совпадающих кластеров в пространстве целей и определена операция объединения пары совпадающих кластеров в объединенный кластер. Введено понятие совпадения «И» и «И/ИЛИ» деревьев решения задач через совпадающие вершины, представленные кластерами в пространстве целей.

2) Определена операция объединения «И/ИЛИ» деревьев. Данная операция позволяет путем объединения решающих «И» деревьев, построенных в результате взаимодействия решающей системы и пользователя-природоведа, сформировать обобщенное «И/ИЛИ» дерево, описывающее статическую структуру оригинала. Разработан новый алгоритм объединения «И/ИЛИ» деревьев решения задач.

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

4) Выведена теоретическая оценка скорости сходимости процесса построения обобщенного «И/ИЛИ» дерева для класса задач.

публикации по теме диссертации

1. Вовк, А. А. Технология формирования «И/ИЛИ» дерева задач анализа изображений / А. А. Вовк, Г. М. Цибульский, А. А. Латынцев // Вестник Вестник Сибирской аэрокосмической академии им. академика М. Ф. Решет-нева. -2008. -№2 (19). - С. 33-41.

2. Вовк, А. А. Построение обобщенного «И/ИЛИ» дерева решения задач анализа изображений / А. А. Вовк // Аналитические и численные методы моделирования естественнонаучных и социальных проблем: сборник статей III Международной научно-технической конференции. - Пенза: Приволжский Дом знаний, 2008. - С. 295-297.

3. Вовк, А. А. Сходимость процесса формирования «И/ИЛИ» дерева решения задач анализа изображений / А. А. Вовк; СФУ-Красноярск, 2008. -12 с. - ил. - Библиогр.: 3 назв. - Рус. - Деп. в ВИНИТИ 19.09.08 № 739 - В 2008.

4. Вовк, А. А. Исследование сходимости процесса формирования «И/ИЛИ» дерева решения задач анализа изображений / А. А. Вовк, А. А. Латынцев; СФУ-Красноярск, 2008. - 13 с. - ил. - Библиогр.: 3 назв. - Рус. - Деп. в ВИНИТИ 19.09.08 №740 -В 2008.

5.Вовк, А. А. Формирование обобщенного «И/ИЛИ» дерева для класса задач анализа изображений / А. А. Вовк // Решетневские чтения: материалы XII Международной научной конференции, посвящ. памяти генерального конструктора ракетно-космических систем академика М.Ф. Решетнева; под общ. ред. И.В. Ковалева / Сиб. гос. аэрокосмич. ун-т. - Красноярск, 2008. - С. 101-102.

//

Вовк Алексей Андреевич Технология построения обобщенного «И/ИЛИ» дерева решения задач. Автореферат диссертации на соискание ученой степени кандидата технических наук. Подписано в печать 25.11.2008. Заказ № Формат 60x90/16. Усл. печ. л. 1. тираж 100 экз.

ВВЕДЕНИЕ.

1. «И/ИЛИ» ДЕРЕВЬЯ РЕШЕНИЯ ЗАДАЧ.

1.1 Понятие задачи.

1.1.1 Формулировка задачи. Неопределенности.

1.1.2 Представление задачи в пространстве состояний.

1.1.3 Представление задачи в пространстве задач.

1.2 «И/ИЛИ» деревья.

1.2.1 Определение дерева в теории графов.

1.2.2 «И/ИЛИ» дерево целей.

1.2.3 Операции над графами.

1.3 Получение знаний.

1.3.1 Задачи формирования знаний.

1.3.2 Классификация систем добычи данных.

1.4. Выводы к главе 1.

2. ТЕХНОЛОГИЯ ПОСТРОЕНИЯ ОБОБЩЕННОГО «И/ИЛИ» ДЕРЕВА

2.1 «И» и «И/ИЛИ» деревья.

2.2 Совпадающие кластеры.

2.3 Понятие полного и частичного совпадения «И» деревьев.

2.4 Понятие полного и частичного совпадения «И/ИЛИ» деревьев.

2.5 Построение обобщенного «И/ИЛИ» дерева.

2.6 Разделение пересекающихся кластеров.

2.7 Сходимость процесса построения обобщенного «И/ИЛИ» дерева.

2.8 Выводьгк главе 2.

3. ЭКПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ.

3.1 Цели и задачи экспериментального исследования.

3.2 Описание программно - аппаратной системы для проведения эксперимента.

3.3 Исходные данные.

3.4 Ход эксперимента.

3.5 Выводы к главе 3.

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

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

Для достижения цели решаются следующие задачи:

1. Анализ применимости операции над графами теории графов к «И/ИЛИ» деревьям решения задач.

2. Определение операции объединения вершин «И/ИЛИ» дерева, представляющих цели в пространстве целей.

3. Определение операции объединения решающих «И» деревьев в «И/ИЛИ» дерево.

4. Разработка алгоритма объединения решающих «И» деревьев в «И/ИЛИ» дерево.

5. Исследование сходимости процесса построения обобщенного «И/ИЛИ» дерева для класса задач.

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

1. Введено понятие совпадающих кластеров в пространстве целей и определена операция объединения пары совпадающих кластеров в объединенный кластер. Введено понятие совпадения «И» и «И/ИЛИ» деревьев решения задач через совпадающие вершины, представленные кластерами в пространстве целей.

2. Определена операция объединения «И/ИЛИ» деревьев. Данная операция позволяет путем объединения решающих «И» деревьев, построенных в результате взаимодействия решающей системы и пользователя-природоведа, сформировать обобщенное «И/ИЛИ» дерево, описывающее статическую структуру оригинала. Разработан новый алгоритм объединения «И/ИЛИ» деревьев решения задач.

3. Сформулировано определение сходимости итерационного процесса построения обобщенного «И/ИЛИ» дерева для класса задач. Данное определение базируется на измерении степени сходства получаемых «И/ИЛИ» деревьев на каждом шаге объединения «И/ИЛИ» дерева с очередным решающим «И» деревом задачи данного класса. Сформулирован и доказан критерий сходимости такого процесса.

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

Использование результатов диссертации. Основные результаты работы были внедрены в Институте леса им. В.Н. Сукачёва СО РАН, а также в учебном процессе СФУ.

Личный вклад автора. Автором лично получены основные выносимые на защиту результаты. В работах, опубликованных лично и в соавторстве, автором разработаны теоретические основы, проведены аналитические выкладки и получены экспериментальные результаты.

Апробация работы. Материалы работы обсуждались: на семинаре кафедры «Системы искусственного интеллекта» Красноярского государственного технического университета (2008г.); на семинаре лаборатории мониторинга леса в Институте леса им. В.Н. Сукачёва СО РАН (2008г.).

Публикации. По материалам исследований опубликовано пять статей, из которых: одна опубликована в сборниках, рекомендованных ВАК, две статьи депонированы.

Структура и объем диссертации. Диссертационная работа включает: содержание, введение, три главы, и заключение. Работа содержит 104 страницы машинописного текста, 43 рисунка и 21 таблицу. Список литературы содержит 110 наименований.

3.5 Выводы к главе 3

1. Экспериментально продемонстрирована работоспособность технологии построения обобщенных «И/ИЛИ» деревьев путем многократного объединения решающих «И» деревьев.

2. Процесс построения обобщенного «И/ИЛИ» дерева проиллюстрирован на примере решения задач анализа космофотоснимков лесов Саян, сформировано «И/ИЛИ» дерево

3. Исследована сходимость процесса формирования «И/ИЛИ» дерева. На каждом шаге объединения «И/ИЛИ» дерева с «И» деревом вычислены коэффициенты приоста дерева и коэффициенты изменения кластера.

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

ЗАКЛЮЧЕНИЕ

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

1. Введено понятие совпадающих кластеров в пространстве целей и определена операция объединения пары совпадающих кластеров в объединенный кластер. Введено понятие совпадения «И» и «И/ИЛИ» деревьев решения задач через совпадающие вершины, представленные кластерами в пространстве целей.

2. Определена операция объединения «ИУИЛИ» деревьев. Данная операция позволяет путем объединения решающих «И» деревьев, построенных в результате взаимодействия решающей системы и пользователя-природоведа, сформировать обобщенное «И/ИЛИ» дерево, описывающее статическую структуру оригинала. Разработан новый алгоритм объединения «И/ИЛИ» деревьев решения задач.

3. Сформулировано определение сходимости итерационного процесса построения обобщенного «И/ИЛИ» дерева для класса задач. Данное определение базируется на измерении степени сходства получаемых «И/ИЛИ» деревьев на каждом шаге объединения «И/ИЛИ» дерева с очередным решающим «И» деревом задачи данного класса. Сформулирован и доказан критерий сходимости такого процесса.

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

1. Гладун В.П. Системы планирования действий для сложных сред./ Гладун В.П., Ващенко Н.Д., Галаган Н.И. // Кибернетика. 1982. - №5. - С.88-94.

2. Банерджи Р.Б. Теория решения задач как раздел искусственного интеллекта/ Банерджи Р.Б.// ТИИЭР. 1982. - т.70. - №12.

3. Цибульский Г.М. Агент и агентные задачи системы анализа изображений./ Цибульский Г.М., Латынцев A.A.// Электронный журнал "Исследовано в России". -2005. -N3. -С.663-667 http://zhurnal.аре. relam.ru/articles/2005/060.pdf

4. Ефимов Е.И. Решатели интеллектуальных задач./ Ефимов Е.И.// -М.: Наука, 1982.

5. Пойа Д. Математическое открытие./ Пойа Д.// М., 1998. - С.448.

6. Попов Э.В. Экспертные системы. М.: Наука, 1987. 284 с.

7. Рассел С., Норвиг П. Искусственный интеллект: Современный подход. 2-е изд. М.: «Вильяме», 2007. - 1424 с.

8. Гаврилова Т.А. Базы знаний интеллектуальных систем./ Гаврилова Т.А., Хорошевский В.Ф. СПб.: «Питер», 2000. - 384 с.

9. Gruber Т.А. Translation Approach to Portable Ontology Specifications // Knowledge Acquisition Journal. 1993. Vol. 5. PP. 199-220.

10. Лозовский B.C. Сетевые модели // Искусственный интеллект. В Зх кн. кн. 2

11. Модели и методы: Справочник / Под ред. Д.А. Поспелова. М.: Радио и связь, 1990.

12. Нильсон Н. Искусственный интеллект. Методы поиска решений. М.: Мир, 1973.-272 с.

13. Нильсон Н. Принципы искусственного интеллекта. М.: Радио и связь, 1985.

14. Хант Э. Искусственный интеллект: Пер. с англ. М.: Мир, 1978. 560 с.

15. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. -М.: Энергия, 1980. -344 с.

16. Алексеев В.Е., Таланов В.А. Графы. Модели вычислений. Структуры данных: Учебник. Нижний Новгород: Изд-во ННГУ, 2005. - 307 с.

17. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.-432 с.

18. Ope О. Теория графов. М.: Наука, 1980. - 336 с.

19. Харари Ф. Теория графов / Ф. Харари. М.: Мир, 1973. - 302 с.

20. Мелихов А.Н. Ориентированные графы и конечные автоматы / А. Н. Мелихов // Главная редакция физико-математической литературы. Изд-во «Наука», М.: Мир, 1971. - 416 с.

21. Одрин В.М. Метод морфологического анализа технических систем. М.: ВНИИПИ, 1989.

22. Алексеев А. В., Борисов А. Н. и др. Интеллектуальные системы принятия проектных решений. Рига: Зинатне., 1997.

23. Акимов C.B. Модель морфологического множества уровня идентификации // Труды учебных заведений связи / СПбГУТ. СПб, 2005. № 172. С. 120-135.

24. Крайнюченко И. В., Попов В. П. Системное мировоззрение. Теория и анализ. Учебник для вузов. Пятигорск.: ИНЭУ, 2005. — 218 с.

25. Титов В. Н. Выбор целей в поисковой деятельности. Методы анализа проблем и поиска решений в технике. — М.: Речной транспорт, 1991. —125 с.

26. Братко И. Программирование на языке Пролог для искусственного интеллекта. Пер. с англ. М.: Мир, 1990. 560 с.

27. Павлидис Т. Иерархические методы в структурном распознавании образов / Т. Павлидис // ТИИЭР. 1979. - № 5. - С. 39 - 49.

28. Цибульский Г.М., Денисов Д. А., Харук В.И. Интерактивная сегментация изображений// Исследование Земли из космоса. 1990. №4.

29. Денисов Д. А. Компьютерные методы анализа видеоинформации: монография / Д. А. Денисов; Краснояр. гос. техн. ун-т. Красноярск, 1993. -192 с.

30. Денисов Д. А. Структурные методы описания объектов изображений: препринт / Д. А. Денисов, А. К. Дудкин, В. П. Пяткин; ВЦ СО АН СССР. -Новосибирск, 1988.-35 с.

31. Чукин К. С. Структуры данных для представления изображений / К. С. Чукин // Зарубежная радиоэлектроника. 1983. - №8. - С. 124 - 129.

32. Александров В. В. Представление и обработка изображений: рекурсивный подход / В. В. Александров, И. Д. Горский. Ленинград: Наука, 1985.- 189 с.

33. Фу К.С. Структурные методы в распознавании образов: пер. с англ. / К. С. Фу.-М.: Мир, 1977.-320 с.

34. Цибульский Г.М. Мультиагентный подход к анализу изображений: Монография / Г. М. Цибульский; Отв. Ред. В.В. Москвичев. Новосибирск: Наука, 2005.- 188 с.

35. Девятков В.В. Системы искусственного интеллекта: Учеб. Пособие для ВУЗов. -М.: Изд. МГТУ им. Н.Э. Баумана, 2001. 352 с.

36. Ефимов Е.И. решатели интеллектуальных задач. М.: Наука, 1982.

37. Искусственный интеллект. В 3-х кн. М.: Радио и связь, 1990.

38. Построение экспертных систем / Под ред. Ф. Хейса-Рота, Д. Уотермана, Д. Лената. М.: Мир, 1987. 441 с.

39. Уотерман Д. Руководство по экспертным системам: Пер. с англ. М.: Мир, 1989.-388 с.

40. Вагин В.Н., Викторова Н.П. Вопросы структурного обобщения и классификации в системах принятия решений // Изв. АН СССР. Техн. Кибернетика. 1982. №5. с. 86-89.

41. Гладун В.П. Планирование решений. Киев: Науко думка, 1987. 168 с.

42. Гладун В.П. Эвристический поиск в сложных средах. Киев: Науко думка, 1977.- 172 с.

43. Поспелов Г.С., Поспелов Д.А. Искусственный интеллект. Прикладные системы. М.: Знание, 1986. -48 с.

44. Chassery J.M., Garbay С. Expert systems, image processing and image interpretation. // Proc. 8th Int. Conf. Pattern Recogn., Paris. Oct. 27-31, 1986. Paris, 1986. p. 175-177.

45. Автоматизация поискового конструирования / Под ред. А.И. Половинкина. М.: Радио и связь, 1981.

46. Построение экспертных систем / Под ред. Ф.Хейес-Рота, Д.Уотермана, Д.Лената. М.: Мир, 1987.

47. Fayyad U., Piatetsky-Shapiro G., Smyth P. From Data Mining to Knowledge Discovery: An Overview. In Advances in Knowledge Discovery and Data Mining (Eds. U.M.Fayyad, G.Piatetsky-Shapiro, P.Smyth), Cambridge, Mass: MIT Press, 1996, pp. 1-34.

48. Таунсенд К., Фохт Д. Проектирование и реализация экспертных систем на ПЭВМ. М.: Финансы и статистика, 1991.

49. Нейлор К. Как построить свою экспертную систему. М.: Атомиздат, 1991.

50. Гаврилов А.В. Гибридная экспертная система для профориентации // Науч. труд. НГТУ. 1997. № 3(8). с. 123-132.

51. Дюк В. А., Самойленко А. П. Data Mining: учебный курс. СПб: Питер, 2001.-368 с.

52. Киселев М., Соломатин Е. Средства добычи знаний в бизнесе и финансах// Открытые системы, № 4, 1997, с. 41-44.

53. Тюхтин B.C. Теория автоматического опознавания и гносеология. М.: Наука, 1976.-233 с.

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

55. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. Новосибирск: ИМ СО РАН, 1999.

56. Wettschereck D., Aha D.W., Mohri T. A Review and Empirical Evaluation of Feature Weighting Methods for a Class of Lazy Learning Algorithms. Artificial Intelligence Review. 11. - pp. 273-314.

57. Wang H., Dubitzky W., Dantsch I., Bell D.A. A Lattice Machine Approach to Automated Case Base Design: Marrying Lazy and Eager Learning. Proc. 17th Int. Joint Conference on Artificial Intelligence (IJCAI-99), Sweden, 1999.

58. Aha D.W., Salzberg S.L. Learning to Catch: Applying Nearest Neighbor Algorithms to Dynamic Control Tasks. In P. Cheeseman & R. W. Oldford (Eds.) Selecting Models from Data: Artificial Intelligence and Statistics. New York, NY: Springer-Verlag, 1993.

59. Aha D.W. An Implementation and Experiment with the Nested Generalized Exemplars Algorithm. Technical Report AIC-95-003. Washington, DC: Naval Research Laboratory, Navy Center for Applied Research in Artificial Intelligence, 1995.

60. Brand E., Gerritsen R. Naive-Bayes and Nearest Neighbor // DBMS. 1998. №7.

61. Heckerman D., Geiger D., Chickering D. Learning Bayesian networks: The combination of knowledge and statistical data // Machine Learning. 1995. № 20. -p. 197-243.

62. Heckerman D. Bayesian Networks for Data Mining // Data Mining and Knowledge Discovery. 1997. № 1. - p. 79-119.

63. Brand E., Gerritsen R. Decision Trees // DBMS. 1998. № 7.

64. Breiman L., Friedman J.H., Olshen R.A., Stone C.J. Classification and regression trees. Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software. 1984.

65. Quinlan J.R. Generating production rules from decision trees // In Proceedings of the 10th International Joint Conference on Artificial Intelligence (IJCAI-87). Morgan Kaufmann, 1987. - p. 304-307.

66. Quinlan J.R. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, San Mateo, CA, 1993.

67. Гупал A.M., Пономарев А.А., Цветков A.M. Об одном методе индуктивного вывода с подрезанием деревьев решений // Кибернетика и системный анализ. 1993. - № 5. - с. 174-178.

68. Цветков A.M. Разработка алгоритмов индуктивного вывода с использованием деревьев решений // Кибернетика и системный анализ. -1993. -№ 1. с. 174-178.

69. Fuernkranz J. Separate-and-Conquer Rule Learning. Vienna: Austrian Research Institute for Artificial Intelligence, Technical Report OEFAI-TR-96-25, 1996.

70. Parsaye K. Rules are Much More than Decision Trees // The Journal of Data Warehousing. 1997. - № 1.

71. Уоссермен Ф. Нейрокомпьютерная техника: Теория и практика. М.: Мир, 1992.-240 с.

72. Хардле В. Прикладная непараметрическая регрессия. М.: Мир, 1993.

73. Hastie Т., Tibshirani R., Friedman J. The Elements of Statistical Learning. Springer, 2001.

74. Jain A., Murty M., Flynn P. Data clustering: A review // ACM Computing Surveys. 1999. Vol. 31, №. 3. - pp. 264-323.

75. Уиллиамс У.Т., Ланс Д.Н. Методы иерархической классификации // Статистические методы для ЭВМ / Под ред. М. Б. Малютов. М.: Наука, 1986. с. 269-301.

76. Johnson S.C. Hierarchical clustering schemes // Psychometrika, №32, 1967. p. 241-254.

77. Gruvaeus G., Wainer H. Two additions to hierarchical cluster analysis // The British Journal of Mathematical and Statistical Psychology, №25, 1972. p. 200206.

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

79. Hartigan J. A. Clustering algorithms. New York: Wiley, 1975.

80. Hartigan J. A., Wong, M.A. Algorithm 136. A k-means clustering algorithm. Applied Statistics, 1978.

81. T.Kohonen. Self-Organizing Maps (2-nd edition), Springer, 1997.

82. Agrawal R., Imielinski T., Swami A. Mining Associations between Sets of Items in Massive Databases. In Proc. of the 1993 ACM-SIGMOD Int'l Conf. on Management of Data, 207-216.

83. Agrawal R., Srikant. R. Fast Discovery of Association Rules, In Proc. of the 20th International Conference on VLDB, Santiago, Chile, September 1994.

84. Savasere A., Omiecinski E., Navathe S. An Efficient Algorithm for Mining Association Rules in Large Databases, In Proc. 21st Int'l Conf. Very Large Data Bases, Morgan Kaufmann, San Francisco, 1995.

85. Park J.S., Chen M.-S., Philip S.Y. An Effective HashBased Algorithm for Mining Association Rules, In Proc. ACM SIGMOD Int'l Conf. Management of Data, ACM Press, New York, 1995.

86. Brin S. et al. Dynamic Itemset Counting and Implication Rules for Market Basket Data, In Proc. ACM SIGMOD Int'l Conf. Management of Data, ACM Press, New York, 1997.

87. Srikant R., Agrawal R. Mining Generalized Association Rules, In Proc. of the 21th International Conference on VLDB, Zurich, Switzerland, 1995.

88. Антосик П., Микусинский Я., Сикорский Р. Теория обобщенных функций. Секвенциальный подход. М.: Мир, 1976. — 312 с.

89. Bundy Alan, editor. Artificial Intelligence Techniques. Springer Verlag, 1997.

90. Bull M., Kundt G., Gierl L. Discovering of health risks and case-based forecasting of epidemics in a health surveillance system. In Jan Komorowski and Jan Zytkow, editors, Principles of Data Mining and Knowledge Discovery. Proceedings, p. 68-77, 1997.

91. Практикум по теории статистики I Под ред. P.A. Шмойловой, M.: Финансы и статистика, 2001. 456 с.

92. Елисеева И.И., Юзбашев М.М. Общая теория статистики. М.: Финансы и статистика, 2002. — 480 с.

93. Сошникова Л.А., Тамашевич В.Н., Уебе Г., Шефер М. Многомерный статистический анализ в экономике. М., 1999;

94. Дубров A.M., Мхитарян B.C., Трошин Л.И. Многомерные статистические методы для экономистов и менеджеров. М., 2000.

95. Хайкин С. Нейронные сети. Полный курс. М.: «Вильяме», 2006. -1104 с.

96. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы. М.: Горячая Линия -Телеком, 2007. 452 с.

97. Головко В.А. Нейронные сети: обучение, организация и применение. М.: И11РЖР, 2002. 256 с.

98. Бериков В.Б. Анализ статистических данных с использованием деревьев решений: Учебное пособие. Новосибирск: Изд-во НГТУ, 2002. -60 с.

99. J. Ross Quinlan. С4.5: Programs for Machine learning. Morgan Kaufmann Publishers, 1993.

100. S.Murthy. Automatic construction of decision trees from data: A Multi-disciplinary survey, 1997.

101. Machine Learning, Neural and Statistical Classification. Editors D. Mitchie et.al., 1994.

102. Seidman.C. Data Mining with Microsoft SQL Server 2000: Technical Reference. Microsoft Press, 2001.

103. Ville.B., de. Microsoft Data Mining. Digital Press, 2001.

104. Заде Л. Понятие лингвистической переменной и его применение к принятию приближенных решений. М.: Мир, 1976.

105. Круглов В.В., Дли М.И. Интеллектуальные информационные системы: компьютерная поддержка систем нечеткой логики и нечеткого вывода. М.: Физматлит, 2002.

106. Гладков JT.A., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. М.: Физматлит, 2006. 320 с.

107. Holland J.H. Adaptation in Natural and Artificial Systems, Ann Arbor, MI: The University of Michigan Press. 2nd edn. Boston, MA: MIT Press, 1992.

108. Goldberg D.E. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, 1989.

109. Mitchell M. An Introduction to Genetic Algorithms. MIT Press, Cambridge, MA, 1996.

110. Курейчик B.M., Родзин С.И. Эволюционные алгоритмы: генетическое программирование. Обзор // Известия РАН. ТиСУ. 2002. №1. с. 127-137.

111. Родзин С.И. Гибридные интеллектуальные системы на основе алгоритмов эволюционного программирования // Новости искусственного интеллекта. 2000. №3. с. 159-170.