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

На правах

Р16 -Мошс"

) 0 Я"1 тс V

Гришина Елена Алексеевна

Исследование моделей и методов приобретения топографических знании па основе алгоритмов распознавания частично упорядоченных объектов

Специальность - 05.13.1! - Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

А В Т О 1> Е Ф Е 1' А Т

диссертации на соискание ученой степени кандидата технических наук

Москва - 2000

Работа выполнена на кафедре Математического моделирования Московского энергетического института (Технического университета).

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

доктор технических наук,

профессор

А. Б. Фролов

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

доктор технических наук, профессор

A. П. Еремеев

кандидат технических наук

B. Е. Савельев

Ведущая организация Московский государственный

горный университет

Защита состоится "30" нояЪр« 2000 г. в аудитории в У8 ч.

на заседании диссертационного совета К-053.16.09 в Московском энергетическом ииституте (Техническом университете) по адресу: 1 И250, Москва, Красноказарменная ул., 17.

Отзывы в двух экземплярах, заверенные печатью, просим присылать по адресу: 111250, Москва, Красноказарменная ул., 14, Ученый Совет МЭИ.

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

Автореферат разослан "21 "ытя j/}jL2000 г.

Ученый секретарь диссертационного совета К-053.16.09

к.т.н., доцент / Дорошенко А.Н. /

c2)/-?tf а О

АКТУАЛЬНОСТЬ ТЕМЫ. В последнее время в технологию создания геоинформационных систем (ГИС) стали внедряться системы, основанные на знаниях. Особенно важны интеллектуальные ГИС для решения задач управления систем быстрого реагирования, таких как скорая помощь, городские милицейские и пожарные силы, ликвидация последствий чрезвычайных ситуаций и т. п. В таких системах важнейшей составляющей базы знаний являются топографические знания о свойствах и пространст&енно-логических отношениях объектов местности. Для интеллектуальных ГИС оперативного планирования радиорелейной и проводной связи, выбора трасс мобильных средств при аварийно-восстановительных работах в условиях чрезвычайных ситуаций необходимо оценивать тип участка местности. Например, при решении задачи оценки и выбора трассы радиорелейной линии связи необходимо выбрать такую трассу, которая позволяет при минимальном количестве мобильных промежуточных радиорелейных станций осуществить устойчивую связь на большие расстояния. Причем увеличение дальности связи может быть достигнуто не только увеличением мощности,но и правильным выбором мест расположения станций. Поэтому необходимо оценивать местность с точки зрения пригодности того или иного участка для размещения станции. Эти оценки, как правило, имеют качественный характер, например местность может быть сильно, средне или слабо пересеченной или непересеченной.

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

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

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

ЦЕЛЬ ДИССЕРТАЦИОННОЙ РАБОТЫ заключается в исследовании методов приобретения топографических знаний с использованием цифровых

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

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

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

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

ОСНОВНЫЕ НАУЧНЫЕ РЕЗУЛЬТАТЫ, которые выносятся на защиту и получены лично автором, сводятся к следующему:

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

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

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

НАУЧНАЯ НОВИЗНА РАБОТЫ заключается в следующем: 1.На основе алгоритма распознавания частично упорядоченных объектов разработаны новые методы приобретения топографических знаний на основе цифровых карт для оценки характера участка местности при решении задачи трассировки линий связи: знания определяются параметрами решающей функции, построенной путем применения алгоритма разделения к цифровой карте как обучающей выборке.

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

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ РЕЗУЛЬТАТОВ работы состоит в использовании методов приобретения топографических знаний на основе цифровых карт в МИР "Коса-АН" (1992 г., промежуточный), НИР "Окно-ИИ" (1992 г., промежуточный), НИР "Зарево-1" (1993 г.), НИР "Решение" (1995г.. промежуточный), НИР "Экран" (1996 г., промежуточный), НИР "Слайд" (1998 г.) 16 ЦНИИИ МО РФ.

ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ ИССЛЕДОВАНИЙ. Результаты диссертации использованы в разработке системы приобретения топографических знаний для интеллектуальной ГИС оперативного

планирования линий связи в ОКР изделий 28Я6, 83т99, 88Э6 концерна "СИСТЕМПРОМ".

АПРОБАЦИЯ РАБОТЫ. Основные положения и результаты диссертационной работы докладывались и обсуждались на Научно-технической конференции 16 ЦНИИИ МО РФ, посвященной 70-летию института в 1993 г., на Научно-технической конференции 16 ЦНИИИ МО РФ в 1996 г. и на Международных форумах информатизации МФИ "Информационные средства и технологии" в 1993,1994,1995, 1999 г.г.

ПУБЛИКАЦИИ. По теме диссертации опубликовано 5 печатных работ.

СТРУКТУРА И ОБЪЕМ РАБОТЫ. Диссертация состоит из введения, 3 глав, заключения, 4 приложений и списка литературы. Работа содержит 170 страниц печатного текста, 34 рисунков, 17 таблиц, список литературы из 119 наименований.

ВО ВВЕДЕНИИ определена актуальность темы исследования, формулируются задачи исследования диссертации, раскрывается научная новизна и практическая значимость полученных результатов, приведены сведения об апробации и внедрении работы.

В ПЕРВОЙ ГЛАВЕ проанализированы методы извлечения знаний из баз данных, а также оценены возможности их применения в разработке методов приобретения топографических знаний на основе цифровых карт.

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

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

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

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

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

Функциональный подход к проблеме сжатия данных заключается в том,что исходную дискретную информацию,как правило,можно интерпретировать как А-значную функцию (или систему Л-значных функций), заданную на некоторой реальной или искусственно введенной области определения (Фролов А. Б.,Я ко ЭАлгоритмы распознавания частично упорядоченных объектов и их применение//Изв.АН СССР.Техническая кибернетика.-1990-Ы5-С. 95-103).Мапример,дискретную последовательность Ь:,Ь2, ...Ь„ ...Ь„ можно рассматривать как функцию натурального аргумента/7:где ¿/.¿»¿...¿¿...¿„е/? и УУ-множество натуральных чисел.Значениями этой функции на данном натуральном числе / является /-ый элемент последовательностиУ(/)=А,.Эту же последовательность можно рассматривать как последовательность значений функции двух аргументов_/(/1/)=6*,где к есть канторовский номер па-

ры чисел (/,у) или последовательность значений функции Г: 1\Г В большего числа аргументов./^'/, о,.../„,)=£*, где А-канторовский номер набора (/;,/;,.../я)-

Область определения функции, как правило, может быть частично (<) и топологически «) упорядочена. Дадим общие определения для указанных отношений при х.уеЛГ,где х=(х,,х2, ...х„)у=(у,,у2, ...у„):(х1.х2, ...хт)й(у,.у2. ...уп\

/я до т щ

еслиУ / х,<у,\(х,,х2, ■■■хт)((у1,у2, ...^т),еслиЕх,<5>)или2>,-=1^1- иВА: такое,что х,=>»,-

; = у / -/ у - / ; -;

при / < к, Хк<уь При этом всегда из (х;, х2, ... хт) < (у/, у2, ... ут) следует, что (*/, х2, ... хт) { (у], у2, ... ут) (при т = 1 эти отношения совпадают). Эти отношения и позволяют уменьшить число явно представленных пар (а, Ь) в описании функции, где а е У, а = (оу, а2, ... ат) - аргумент, Ь - значение.

Идею сокращения описания поясним, рассмотрев простейший случай т = I. Пусть исходное описание задано списком пар (а, Ь). Ясно, что такое описание можно всегда восстановить по списку, содержащему только те пары, которые отличаются от соседних пар предшествующих им в исходном списке. Гак что в сжатом списке не будет одинаковых значений у соседних пар. Можно использовать другие критерии исключения элемента исходного описания функции. Случай многих переменных можно свести к предыдущему путем линейного упорядочивания по рассмотренному выше

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

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

Пусть функция F задана списком L частично упорядоченных пар (а, Ъ). Алгоритм сжатия В формирует результирующий список, состоящий из четверок (аЪ\ р, i), где р, р е {0, 1} - четность четверки, /', 0 < / < /-1 -порядок четверки, / - длина максимальной цепи ао, ah ... at.j в множестве If. По окончании работы алгоритма список LB будет содержать основную информацию, сопровождаемую некоторой вспомогательной информацией о четности и порядке входящих в нее пар (а, Ь).

Работа алгоритма состоит п том, что для первой и каждой последующей пары (а, h) исходного списка L список Lb просматривается в обратном направлении. При этом определяются экстремальные порядки J0 и JI четвёрок (а, Ъ, 0, /) и (a, b, 1, /) таких, что а' < a: Jп - max i, Jj = min i

(a\ b\ 0, i) e LB (a',b\ l,i) eLB

a'< a a'< a

и вычисляются значения

max b, если Jn > Ji или У, не определено,

(а\ b \ 0, Jq) е LB а'й а

b* = { min b, если J0 < Jj,

(a', b \ 1, Ji) e LB a'< а

О, если значение J0 не определено.

{(Jo, 0), если J0 > Ji или Ji не определено,

(У/, 7), если J0 <Ji. Замечание. Значения J0 и J1 считаются неопределенными, если необходимые для их определения четвёрки отсутствуют в списке LR.

Список ¿в при этом остаётся без изменения, если Ь*=Ь или указанных четвёрок не обнаружено(т.е. значения Л,./;не опр.)и Ь=0.В остальных случаях в список ¿в добавляется четвёрка (а, Ь, 0,0), если четвёрок не обнаружено и Ь*0,(а,ЬДУ,еели Ь*<Ь, (а,Ь,и),еели Ь*>Ь и Р=1, (а,Ь,и+1),сели Ь*>Ь и Р=0.

Алгоритм распознавания Ив состоит в вычислении для данного элемента а значения Ь* на основе списка Ьв аналогично вычислению в алгоритме сжатия В.

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

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

Этот подход предлагается применить к цифровым картам [1 - 3].

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

Рассмотрим эти методы и сравним с базовым методом полного перебора сжатого списка Ьв в рассмотренных выше алгоритмах.

Метод таблиц уровней и порядков [4]. В сжатом списке Ьв элементы расположены по возрастанию весов у(а). Вес у(а) элемента а определяется арифметической суммой элементов этого вектора. Множество элементов списка I.в с весом п назовем уровнем п. Предлагается в процессе формирования результирующего списка ¿в заполнять таблицу уровней и таблицу порядков. Таблица уровней пусть содержит для каждого уровня номер первого с конца списка Ьв элемента этого уровня. Если в списке Ьв отсутствуют элементы уровня п, то в таблице уровней для уровня п повторяется номер элемента для л-/-ого уровня. В таблице порядков для каждого порядка / запоминается номер верхнего уровня, в котором встречаются элементы с этим порядком. Верхним уровнем назовем уровень, который ближе к голове ¿в (к начальному элементу списка).

При работе алгоритмов сжатия/? и распознавания /^просматривается спи-

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

Если при просмотре списка Ьв найден элемент списка (а',Ь \р',/'"), такой что а' < а, то для порядкар 'по таблице порядков возможно определить номер уровня Г (Г < /"),ДО которого в списке встречаются элементы с порядком р '.Следует заметить, что порядки элементов уровней от нулевого до Г меньше,чем порядокр '.поэтому элементы этих уровней можно не рассматривать.

Если при последующем просмотре списка 1ц найден элемент списка (а", Ъ ",/>",/") с большим порядком, чем предыдущий, такой что а'<а (и р' < р"), то для порядка р" по таблице порядков будет найден новый номер уровня Г, до которого в списке встречаются элементы с порядком р". При этом Г < так как в таблице порядков с возрастанием номеров порядков номера уровней не уменьшаются. Таким образом, просмотр списка сокращается за счет отсечения хвоста списка с элементами, наборы которых большего веса, чем вес искомого набора, и за счет прерывания просмотра списка перед элементами уровней с меньшими порядками.

Рассмотрим сокращение просмотра списка Ьв в алгоритме сжатия В на примере. Исходные данные для примера показаны на рис. 1 в виде матрицы. Исходный список Ь состоит из частично упорядоченных пар ((дг/, х2), Ь): Ь = {((О, 1), 1), ((1, 0), 1), ((0, 2), 1), ((1, 1), 1), ...}. Результирующий список представлен на рис. 2. Следует заметить, что элемент с вектором (0, 0) отсутствует в исходном списке Ь. Пронумерованные элементы списка Ьв обозначены маленькими кругами. Пунктирными линиями обозначены уровни, номера которых стоят слева от них. Элементы списка, на которые есть ссылка из таблицы ссылок, обведены квадратами. В таблице 1 указаны номера порядков и соответствующие им номера уровней.

Рассмотрим работу алгоритма распознавания Яв на этом примере: определим значение Ь для вектора (1, 7). Вес этого вектора равен 8. Ссылка 8-го уровня указывает на элемент с вектором (8, 0).При просмотре списка ¿д находится элемент с вектором (1,6), который меньше искомого вектора (1,7) по отношению частичного порядка. Порядок этого элемента равен 1. По таблице порядков определяем 6-ой верхний уровень, до которого список ¿а будет просматриваться. В итоге значение Ь*, равное 2, получено из элемента ((1,6), 2, 0,1).

Рассмотренный метод позволяет существенно сократить перебор сжатого списка и уменьшить время работы алгоритмов на больших объемах

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

XI

9 1 2 2 2 2 2 2 2 1 1

8 1 2 2 2 2 2 2 2 1 1

7 2 2 2 2 2 2 2 2 1 1

6 2 2 2 2 2 2 2 2 1 1

5 2 2 2 2 2 2 2 2 1 1

4 2 2 2 2 2 2 2 2 1 1

3 2 2 2 2 2 2 2 2 1 1

2 1 1 2 2 2 2 2 2 1 1

1 1 1 1 2 2 2 2 2 1 1

0 1 1 1 2 2 1 1 1 0

0 1 2 3 4 5 6 7 8 9

Таблица 1. Таблица порядков.

Порядок Уровень

0 1

1 6

2 9

х2

Рис. 1. Исходные данные для примера.

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

Метод списка висячих вершин [4]. По мере построения списка Ьв предлагается формировать лес IVв добавлением в каждый элемент списка Ьв ссылки на один из предыдущих элементов этого списка, а именно, на элемент, определяющий значение Ь* для этого нового элемента списка Ьв. Если для какого-либо элемента списка Ьв значение Ь* определяется как 0, то для этого элемента соответствующей ссылки нет.

Рассмотрим структуру леса Щ на рис. 2 для примера, исходные данные для которого показаны на рис. 1. От каждого элемента списка Ьв (кроме первых двух начальных элементов ((0, 1), 1, 0, 0) и ((1, 0), 1, 0, 0)), обозначенного крупной точкой, идет вверх стрелка на соответствующий элемент, определяющий для него значение Ь*.

При построении списка Ьв и леса \УВ предлагается формировать список висячих вершин Ьв0 этого леса. Причем список ЬВо содержит только ссылки на висячие вершины леса По окончании формирования списка Ьв и леса \УВ для каждого уровня предлагается запоминать текущий список висячих вершин ¿во этого леса.

Используя эти списки висячих вершин возможно сократить

о

Рис. 2. Сжатый список /.3 и лес ]Л/В-

перебор элементов списка LB при поиске элемента, определяющего значение Ь* для искомого вектора а. Сначала для вектора а определяется вес v(a) -номер уровня и соответствующий ему список висячих вершин LBD• Векторе" каждого элемента {а", Ь", р", /") этого списка LBn сравнивается с искомым вектором а по отношению частичного порядка. Если находится такой элемент (а', Ъ \ р\ /") списка LBd, вектор а' которого меньше вектора а в смысле частичного порядка, то в дальнейшем при просмотре списка LBD из него удаляются все элементы с меньшим номером порядка, чем порядок i найденного элемента (а\ Ь \ р\ /"). Каждый элемент (а", Ь". р", /") списка Lud после просмотра исключается, при этом включается в список Lbd элемент (а'". Ь"\ р"\ /'") списка LB, на который указывает в лесе WB исключенный элемент {а", Ь", р", /"'). В случае если этот элемент (а"', Ь'",р"\ Г") уже есть в списке висячих вершин LBd или исключенный элемент (а", Ь", р", /") был корнем дерева - элемент в список не добавляется. Перебор элементов списка L,i прекращается, когда список LBD становится пустым.

Рассмотрим сокращение просмотра результирующего списка LB на том же примере. Вес вектора (1, 7) равен 8 и просмотр начинается с элементов списка висячих вершин LBD для 8-ого уровня, которые показаны на рис. 2 пунктирными стрелками.Вектор(1,6)меньше искомого вектора по отношению частичного порядка, поэтому запоминается значение и порядок этого элемента, равный 1. Элемент ((1,6),2,0,1) заменяется в списке LBD на элемент ((0,6), 1,1,1). Элементы ((1, 3), 2, 0, 0), ((2, 2), 2, 0, 0) удаляются из спискадак как их порядки меньше 1. Элемент ((8,0),1,1,1) исключается, а не заменяется на элемент списка ¿д((3,0),2,0,0),т.к. последний имеет 0-ой порядок. В списке остается элемент((0,6),1,1,1),который удаляется после просмотра, так как элемепт,на который от него идет ссылка имеет нулевой порядок.

По сравнению с базовым методом и методом таблиц уровней и порядков этот метод позволяет оценить неоднородность объекта, описанного исходным списком L, не только количеством элементов сжатого списка Lü и максимальным порядком элемента списка LB, но и новой характеристикой -количеством элементов списка висячих вершин LBn последнего уровня, т. е. количеством висячих вершин леса WB.

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

Сокращение перебора сжатого списка по методу списка висячих

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

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

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

Отличием комбинированного метода от метода таблиц уровней и порядков заключается в том, что при комбинированном методе можно определить количество висячих вершин леса 1УВ, т. е. количество элементов списка висячих вершин Ьво.

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

В ТРЕТЬЕЙ ГЛАВЕ описаны методы приобретения топографических знаний, для чего используются рассмотренные во второй главе алгоритмы.

При оценке местности необходимо приобретать топографические знания о типе рассматриваемого участка местности. Эти знания являются характеристиками местности, а именно: по характеру рельефа местность различают на равнинную, холмистую и горную (низкогорную, среднегорную и высокогорную); по степени пересеченности - на непересеченную и пересеченную (сильно, средне и слабо пересеченную); по степени проходимости - на проходимую (легкопроходимую, труднопроходимую) и непроходимую [1 -3, 5].

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

расположение большинства препятствий (оврагов, промоин, канав, насыпей, гор, рек, каналов и т.п.) по отношению к выбираемому направлению прокладываемой трассы [3].

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

Это утверждение рассмотрим подробнее.

Анализ известной литературы по вопросам топографии позволил сделать следующие выводы.

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

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

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

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

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

(пустой) элемент, если в этой точке нет объекта соответствующего тематического слоя.

Значения элементов таких матриц можно рассматривать как последовательность значений функции F: М В двух аргументов flij) = bk, где к есть канторовский номер пары чисел (/, J). В качестве области определения М предлагается взять множество точек а{ = (х„ у,) равномерной координатной сетки карты земной поверхности (геоиды), где дг„ у,- -координаты точки at [1 - 3]. На этом множестве можно ввести отношение частичного < и линейного ( порядка: а, < а2, где aj = (xh yi), а2 = (х2, v^), если x/<x2nyi^yf,ai( а2, если_у/ <у2 или если у: = у: и */ < х2.

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

За исключением множества высот земной поверхности, остальные из перечисленных множеств значений дополняются ещё и фиктивным элементом, так как не в каждой точке земной поверхности находятся объекты гидрографии и гидротехнических сооружения, населённые пункты, дороги и т.п. Причем фиктивный элемент соответствует нулевому значению b в алгоритмах, описанных в предыдущей главе. Для тематического слоя "рельеф суши" отсутствует фиктивный элемент, поэтому даже нулевое значение высоты будет являться значащим значением [1 - 3].

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

Вес v(ai) элемента а, = (х;, _>>,•), а <= М определяется арифметической суммой элементов этого вектора: v(ai) = х, +у/ [4].

Для тематического слоя "рельеф суши" элемент списка LB имеет следующий вид: ((х, у), г, р, i), где х, у - координаты точки земной поверхности, соответствующей элементу матрицы высот, z - высота земной поверхности в точке с координатами х, у, значение соответствующего элемента матрицы высот, р, р е {0, 1} - четность четверки, /, 0 </</-/ -порядок четверки, / - длина максимальной цепи (х0, уа), (х/, yi), ... fa.,, у\.{) в множестве М [1 - 3].

Для других тематических слоев топографической информации список Lb состоит из аналогичных элементов: ((х, у), q, р, i), где q - значение номера объекта земной поверхности в точке с координатами х, у, значение соответствующего элемента матрицы [3].

При определении частоты дорожной сети и частоты водных препятствий для оценки проходимости участка" местности по дорогам

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

Для определения частоты объектов (горизонталей, дорог, объектов гидрографии и т.п.) используются три характеристики списка ¿в и леса №в построенного для заданного участка: количество элементов списка 1В; количество висячих вершин леса №в (количество элементов списка висячих вершин ¿¡¡о)\ максимальный порядок элементов списка ¿в [4].

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

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

Если элементы а области определения, на которых изменяются значения исходной функции /**, составляют полные уровни, тогда количество висячих вершин леса большое и велико количество элементов списка Ьв. Заметим, что максимальный порядок элементов списка Ьв определяет количество экстремальных значений г или д среди элементов в ветке дерева леса, в которой содержится элемент с этим максимальным порядком. Поэтому при таких исходных данных максимальный порядок элементов списка ¿д для "рельефа суши" равен количеству возвышенностей на оцениваемом участке местности, а для других тематических слоев топографической информации - количество объектов, пересекающих

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

Для определения типа местности участка предлагается формировать множество списков ¿в и лесов (Уц, пересчитывая координаты точек местности при повороте на угол у, с целью нахождения самого короткого списка Ьвт\п среди таких списков. Причем для этого необходим поворот системы координат на угол у от 0° до 90°. И уже по минимальному списку Ьвты и по соответствующему для него лесу \УВтм возможно оценить участок местности по выше названным характеристикам.

Для оценки участка по отношению к выбираемому направлению линии связи предлагается строить список ЬВт и лес IVвт. При этом предлагается разворачивать оси координат таким образом, чтобы направление линии связи составляло угол 45° с осями X и У. На рис. 1. от правого верхнего и левого нижнего углов стрелками показано это направление по отношению к осям координат (оси координат обозначены х/ и х?).

Такое расположение осей обусловлено тем, что при преимущественном расположении топографических объектов перпендикулярно направлению линии связи такое описание исходных данных обусловит бо'льшую длину сжатого списка и бо'льшие значения других характеристик сжатого описания. Также значения характеристик сжатого списка Ьвт и леса 1¥Вт можно сравнить со значениями характеристик списка ¿Вт(„ и леса

Следует заметить, что для оценки участков местности могут быть использованы для сравнения и характеристики максимального сжатого списка ¿вт« и соответствующего леса И^Втах. Один из максимальных таких списков можно легко получить, если развернуть на 90° оси координат относительно их положения при нахождении минимального списка и леса \УВтт-

Если значения характеристик минимального и максимального описания близки, это означает, что объекты равномерно расположены на участке местности и участок имеет "симметричный" характер.

Процесс приобретения топографических знаний для интеллектуальной ГИС оперативного планирования радиорелейной и проводной связи, выбора трасс мобильных средств при аварийно-восстановительных работах в условиях чрезвычайных ситуаций, разбивается на два этапа: предварительный и основной [1,2].

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

в векторном формате. На этом этапе формируются промежуточные списки Ду для каждого тематического слоя. Промежуточный список состоит из элементов (х, у, г), где х, у - координаты точки земной поверхности (координатной равномерной сетки) и г — это высота земной поверхности в этой точке для "рельефа суши" или номер объекта др. слоя. Элементы списка Ц строятся в линейном порядке координат х, у. Список содержит только те элементы, которые отличаются по значению г от предшествующего элемента списка /..V, т.е. в промежуточном списке не встречаются соседние элементы с одинаковыми значениями г. Эти списки строятся в соответствии с методом трехэлементной схемы сжатия повторений символов алфавита.

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

Основной этап приобретения топографических знаний выполняется в оперативном режиме. Исходными данными для основного этапа являются промежуточные списки ¿.у, полученные на предварительном этапе, множество координат вершин многоугольника, описывающего оцениваемый участок местности, и выбираемое направление линии связи. Результатами работы основного этапа являются характеристики списков ¿Д|ШЛ и ¿Вг (лесов Идиш и IVвт) для различных тематических слоев.

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

Затем для каждого тематического слоя формируются списки ¿д на основе информации списков Ду^. Исходный список частично упорядоченных пар Ь не используется, а исходная информация для алгоритма сжатия В формируется перебором координат точек в частичном порядке с восстановлением значений элементов матрицы (высот) из списка Ду\. Для определения самого короткого списка ¿йт1„ строятся списки Ьв с пересчетом координат точек местности при повороте системы координат на угол у от 0° до 90°. Экспериментально было определено, что для этого достаточно построить несколько списков для поворота с шагом 10°. Затем выбирается диапазон угла поворота, дающий более короткие списки ¿д. Этот диапазон угла поворота просчитывается с более мелким шагом в 1°.

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

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

которым производится оценка участка местности.

Все вычисления основного этапа приобретения знаний при использовании предложенных методов сокращения перебора ,чля участка местности размером 60 на 60 км (600 на 600 ячеек) для всех тематических слоев цифровой карты в масштабе 1 : 1 000 000 выполнены па компьютере РегНштП. При использовании базового метода (полного перебора) для вычисления минимального сжатого списка Ьитш для этого участка требуется 3-5 мин для реально самого неоднородного участка. При использовании предложенных методов для такого участка время вычисления уменьшается не менее чем до 40 сек. (практически одинаково для всех предложенных методов), что допустимо для решения практической задачи приобретения топографических знаний для интеллектуальной ГИС оперативного планирования линий связи.

При использовании предложенных методов работа алгоритма значительно ускоряется даже на однородных участках. Матрицы однородных участков местности (равнинных, непересеченных) содержат наибольшую избыточность, которая исключается при сжатии.Поэтому сжатые списки ¿Вт„ для таких однородных участков короче, чем для неоднородных участков.Вре-мя работы алгоритма зависит от длины сжатого списка. Длины сжатого списка Ьвти различны для разных типов местности. Полученные коэффициенты ускорения работы алгоритма для слоя "рельеф суши" с применением предложенных методов для участка размером 60 на 60 км(600 на 600 ячеек) тематического слоя"рельеф суши"в масштабе 1 : 1000000 приведены в табл.2.

Длина сжатого списка также определяется и размером участка. Зависимость коэффициентов ускорения работы алгоритма от размера участка местности показана в таблице 3, в которой приведены нижние значения коэффициента ускорения работы алгоритма для различных по размеру участков в масштабе 1 : 1 000 000. Эти результаты были получены на основе 60 равнинных участков тематического слоя "рельеф суши". _Таблица 2. __Таблица 3.

Длина списка ¿втп Коэффициент ускорения Размер участка в км (в ячейках) Коэффициент ускорения

до 1000 1.5-2 60 на 60 (600 на 600) 1.5

1000-1440 2-3.3 100 на 100(1000 на 1000) 3

1370-2890 3.3-5.1 200 на 200 (2000 на 2000) 6.3

2800-3170 5.1 -5.5 300 па 300 (3000 на 3000) 9

3110 - 5990 5.5-6.4 400 на 400 (4000 на 4000) 14.5

5890 - 6840 6.4-6.5 ! 500 на 501 (¿000 па 5000) 47

6840 - 9600 6.5 - 11

Программа написана на языке программирования С.

В ПРИЛОЖЕНИЯХ приведены краткий обзор методов сжатия данных, описание характеристик местности, алгоритмы программ и акты об использовании.

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

¡.Проведено исследование подходов к задаче приобретения топографических знаний для решения задач трассировки линий связи.

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

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

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

ОСНОВНЫЕ ПОЛОЖЕНИЯ ДИССЕРТАЦИИ ОТРАЖЕНЫ В СЛЕДУЮЩИХ ПЕЧАТНЫХ РАБОТАХ:

1.Гришина Е.А. Методы формирования знаний на основе цифровой топографической информации // Международный форум информатизации МФИ-93. Информационные средства и технологии в науке, технике, обучении: Тез. докл. - Моск. энерг. инст. - 1993 - С. 23.

2.Гришина Е.А. Приобретение картографических знаний в интеллектуальных системах изыскания трасс линий связей магистральных сетей // Международный форум информатизации МФИ-94.Информационные средства и технологии в науке,технике,обучении:Тез.докл.-Моск.энерг.инст.-1994-C.I8.

3.Гришина Е.А. Формирование топографических баз знаний в системах изыскания трасс линий связей магистральных сетей // Международный форум информатизации МФИ-95. Информационные средства и технологии в науке, технике, обучении: Тез. докл. - Моск. энерг. инст. - 1995 - С. 21.

4.Гришина Е.А., Ополченов A.B. Алгоритм компрессии данных на основе их функциональной интерпретации // Международный форум информатизации МФИ-99. Информационные средства и технологии: Докл. -Моек, энерг. инст. - 1999 - Т. 2 - С. 81 -84.

5.Гришина Е.А., Птицын С.Ю. Методы формирования картографических баз знаний при автоматизации решения задач управления спя чью // ! 1ауч||о-'1смшческнП сборник 16 Центрального научно-исследовательского испытательного института. - Мытищи, 1996. - N 3 - С. V ts

11"' /.«¿а_ '"l"1 /*'<•' '.....А'___

Типография МЭИ, Красиокалармсппаи. 13.

ВВЕДЕНИЕ

ГЛАВА 1. Проблема приобретения и использования топографических знаний на основе цифровых карт

1.1. Топографические знания

1.2. Анализ методов извлечения знаний из баз данных

1.3. Анализ методов распознавания объектов

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

Выводы

ГЛАВА 2. Алгоритмы распознавания частично упорядоченных объектов

2.1. Функциональный подход к проблеме сжатия данных

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

Выводы

ГЛАВА 3. Система приобретения топографических знаний

3.1. Методы приобретения топографических знаний на основе цифровых карт

3.2. Общее описание системы приобретения топографических знаний

3.3. Формирование промежуточных списков на основе цифровых карт

3.4. Выделение списков, соответствующих оцениваемому участку местности, из промежуточных списков

3.5. Формирование сжатого списка

3.6. Нахождение минимального сжатого списка и построение сжатого списка по направлению линии связи.

3.7. Приобретение топографических знаний.

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

Выводы

В последнее время в технологию создания геоинформационных систем (ГИС) стали внедряться системы, основанные на знаниях. Особенно важны интеллектуальные ГИС для решения задач управления систем быстрого реагирования, таких как скорая помощь, городские милицейские и пожарные силы, ликвидация последствий чрезвычайных ситуаций и т. п. [64, 18]. В таких системах важнейшей составляющей базы знаний являются топографические знания о свойствах и пространственно-логических отношениях объектов местности.

Для интеллектуальных геоинформационных систем оперативного планирования радиорелейной и проводной связи, выбора трасс мобильных средств при аварийно-восстановительных работах в условиях чрезвычайных ситуаций необходимо оценивать тип участка местности [64, 18]. Например, при решении задачи оценки и выбора трассы радиорелейной линии связи необходимо выбрать такую трассу, которая позволяет при минимальном количестве мобильных промежуточных радиорелейных станций осуществить устойчивую связь на большие расстояния [3, 57]. Причем увеличение дальности связи может быть достигнуто не только увеличением мощности, но и правильным выбором мест расположения мобильных промежуточных радиорелейных станций. Поэтому необходимо оценивать местность с точки зрения пригодности того или иного участка для размещения мобильной промежуточной радиорелейной станции. Эти оценки, как правило, имеют качественный характер, например, местность может быть сильно, средне или слабо пересеченной или непересеченной [60, 72, 75].

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

Источником приобретения топографических знаний являются цифровые карты, которые представляют собой цифровую модель земной поверхности. Существуют два способа хранения цифровых карт: регулярно-ячеистый (растровый) и векторный. При регулярно-ячеистом представлении (при растровом способе) пространственно распределенная характеристика географического объекта представляется как матрица чисел, элементы которой соответствуют ячейкам регулярной сети (пикселам), а при векторном - сохраняются только существенные точки пространственно распределенной характеристики [20, 23]. Картографические объекты, представленные и в векторном, и в регулярно-ячеистом (растровом) представлении, разделяются по видам на тематические слои (рельеф суши, гидрография, населённые пункты и т.п.). В векторном виде один объект топографии представляется одной записью, в которой находится метрика объекта и его идентификатор (возможно, и семантика). Например, в семантике объекта-горизонтали содержится её высота и характеристика (основная или вспомогательная). Метрика горизонтали - это последовательность координат существенных точек, определяющих её начертание.

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

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

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

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

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

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

- разработаны три метода сокращения перебора в алгоритме распознавания частично упорядоченных объектов,

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

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

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

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

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

Практическая ценность результатов работы состоит в использовании методов приобретения топографических знаний на основе цифровых карт в НИР "Коса-АН" (1992 г. промежуточный отчет), "Окно-ИИ" (1992 г. промежуточный отчет), "Зарево-1" (1993 г.), "Решение" (1995 г. промежуточный отчет), "Экран" (1996 г. промежуточный отчет), "Слайд" (1998 г.) 16 ЦНИИИ МО РФ.

Результаты диссертации использованы в разработке системы приобретения топографических знаний для интеллектуальной ГИС оперативного планирования линий связи в ОКР изделий 28Я6, 83т99, 88Э6 концерна "СИСТЕМПРОМ".

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

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

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

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

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

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

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

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

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

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

Этот подход предлагается применить к цифровым картам.

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

- метод таблиц уровней и порядков;

- метод списка висячих вершин;

- комбинированный метод.

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

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

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

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

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

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

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

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

- количество элементов сжатого списка;

- количество висячих вершин леса (количество элементов списка висячих вершин);

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

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

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

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

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

ВЫВОДЫ:

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

106

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

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

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

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

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

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

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

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

2. Аммерал Л. Машинная графика на ПК: Пер. с англ. М.: "Сол Систем", 1992, С.35.

3. Андрианов В. И., Соколов А. В. Средства мобильной связи. СПб.: BHV, 1998.

4. Антонова H.A., Наумов H.A. Методы сжатия данных в вычислительных системах. Методы поэлементного сжатия данных. М.: Наука, 1994.

5. Антонова H.A., Наумов H.A. Методы сжатия данных в вычислительных системах. Методы группового сжатия данных. М.: Наука, 1995.

6. Антонова H.A., Наумов H.A. Методы сжатия данных в вычислительных системах. Методы нумерации в сжатии данных. Методы сжатия двоичной информации. М.: Наука, 1996.

7. Апатова Н. В., Иловайская Е. И. Информационно-обучающая система "Экономические и рекреационные ресурсы Крыма" // Ученые записки СГУ. Вып. 8, Симферополь 1998, с. 17 - 21.

8. Ачасова С.М. Вычисление на нейронных сетей (Обзор) // Программирование. -1991 N2-C. 12-19

9. Ю.Бабко И.М., Меркулов Л.Н. Об оценке эффективности методов сжатия данных // Иерархические системы управления и их адаптация: Сб. н. тр. ВЦ СО АН СССР. Новосибирск, 1984. - С. 46 - 54.

10. П.Бауэр Ф., Гооз Г. Информатика: Пер. с англ. М.: Мир, 1976.

11. Бонгард М. М. .проблема узнавания. М: Наука, 1967.

12. Бычков И. В., Васильев С. Н., Вильвер П. Ю., Кузьмин В. А. Представление экспертных знаний в интеллектуальных ГИС / КИИ'98, VI Национальная конференция с международным участием: Сб. науч. тр., т. 1. Пущино, 1998, с. 287 - 292.

13. Вагин В. Н. Дедукция и обобщение в системах принятия решений. М.: Наука, 1988.

14. Вагин В. H., Викторова H. П. Обобщение и классификация знаний // Искусственный интеллект. Кн. 2. Модели и методы: Справочник / Под ред. Д.А Поспелова. М.: Радио и связь, 1992.

15. Вагин В. Н., Федотов А. А., Фомина М. В. Методы извлечения и обобщения информации в больших базах данных // Изв. АН. Теория и системы управления, 1999, N 5, с. 45 59.

16. Винтер И. А. Геоинформационная система проектирования и анализа радиосетей: Учеб. пособие (Ярослав. Гос. Ун-т им. П. Г. Демидова) / Королев Н. И. Кренев А. Н. Ярославль. - 1999. - 88 с.

17. Гаврилова Т.А., Червинская К.Р. Извлечение и структурирование знаний для экспертных систем. М.: Радио и связь, 1992.

18. Геоинформатика. Толковый словарь основных терминов / Баранов Ю. Б., Берлянт А. М., Капралов Е. Г. и др. // Под ред. А. М. Берлянта и А. В. Кошкарева- М.: Изд. ГИС-Ассоциации (МГУ) 1999, с. 205.

19. ГИС-технологии в геологическом изучении недр / Черемисина Е. Н., Марченко В. В., Чесалов JI. Е. и др. (ВНИИ Геосистем) М., 1996.

20. ГОСТ 28441-90. Картография цифровая. Термины и определения. 1990.

21. Горелик A.JL, Гуревич И.Б., Скрипкин В.А. Современное состояние проблемы распознавания. Некоторые аспекты. -М.: Радио и связь, 1985.

22. Горбань А.Н. Обучение нейронных сетей. М.: СпараГраф, 1990.

23. Горбатов В.А. Теория частично упорядоченных систем. М. "Сов. радио", 1976.

24. Городецкий В.М. Формирование понятийной структуры знаний на основе экспертной и экспериментальной информации // Всесоюз. конф. по искусственному интеллекту: Докл. 1988 - Т. 1 - С. 385 - 390.

25. Гришина Е. А. Методы формирования знаний на основе цифровой топографической информации // Международный форум информатизации МФИ-93. Информационные средства и технологии в науке, технике, обучении: Тез. докл. Моск. энерг. ин-т - 1993 - С. 23.

26. Гришина Е.А., Ополченов А. В. Алгоритм компрессии данных на основе их функциональной интерпретации // Международный форум информатизации МФИ-99. Информационные средства и технологии: Докл. Моск. энерг. ин-т - 1999 - Т. 2 - С. 81 - 84.

27. Гришина Е. А., Птицын С. Ю. Методы формирования картографических баз знаний при автоматизации решения задач управления связью // Научно-технический сборник 16 Центральный научно-исследовательский испытательный института. 1996. - N 3 - С. 32-35.

28. Гуревич Ю.Б., Журавлев Ю.И. Минимизация булевых функций и эффективные алгоритмы распознавания // Кибернетика. 1974 - N 1 - С. 12-19.

29. ДеМерс М. Н. Географические информационные системы: Основы: Пер. с англ. / ДеМерс М. Н. М.: Дата+, 1999.

30. Дмитриев А.Н., Журавлев Ю.И., Кренделев Ф.П. О математических принципах классификации предметов и явлений. // Дискретный анализ -Новосибирск: Ин-т математики СО АН СССР 1966 - Вып. 7 - С. 3-15.

31. Еремин И.И., Мазуров В.Д. Нестационарные процессы математического программирования. -М.: Наука, 1979.

32. Журавлев Ю.И. Экстремальные задачи, возникающие при обосновании эвристических процедур // Проблемы прикладной математики и механики. -М.: Наука, 1971.

33. Журавлев Ю.И. Непараметрические задачи распознавания образов // Кибернетика. 1976 -N 6 - С. 93-103

34. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания и классификации // Проблемы кибернетики. 1978 - Вып. 33 - С. 5 - 68.

35. Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. III // Кибернетика. 1978 - N 2 - С.35 - 43.

36. Журавлев Ю.И. Об алгебраических методах в задачах распознавания и классификации // Распознавание, классификация, прогноз. Математические методы и их применение. 1989. - Вып. 1. - С. 9 - 16.

37. Искусственный интеллект: В 3 кн. Кн.2.Модели и методы: Справочник / Под ред. Д.А.Поспелова М.: Радио и связь, 1990.

38. Использование геоинформационных технологий в управлении социально-экономическим развитием региона: Учеб. пособ. / Логиновский О. В., Козлов А. С. и др. Челябинск: Изд-во Юж.-Урал. гос. ун-т, 1999.

39. Кадач А. В. Эффективные алгоритмы неискажающего сжатия данных сортировкой блоков. Новосибирск, 1997.

40. Кириллов Н. Е. Об одном применении многопрограммных кодов для статистического кодирования // Проблемы передачи информации: Сб. ст. -1960-Вып. 5.-С. 34-46.

41. Классификация и распознавание в дискретных системах. А.А.Болотов, А.Б.Фролов / Под ред. В.Н. Вагина.- М.: Изд-во МЭИ, 1997.

42. Кнутт Д. Искусство программирования для ЭВМ. М.: Мир, 1976.

43. Кондратьев А. И. Теоретико-игровые распознающие алгоритмы. / Отв. ред. Е. В. Золотов. АН СССР, Дальневост. отд-ние, ВЦ М.: Наука, 1990.

44. Коробейников А. П. Методы распознавания образов: Учебное пособие / Коробейников А. П. Ростов-на-Дону: Издат. Центр ДТТУ, 1999.

45. Курбаков К. И. Кодирование и поиск информации в автоматическом словаре. М.: Сов. радио, 1968.

46. Ледли P.C. Программирование и использование цифровых вычислительных машин: Пер. с англ. М.: Мир, 1966.

47. Матаока Т., Харисаки X. Компьютеры на СБИС. М.: Мир, 1986.

48. Молдавский С. Универсальный "геосервер" / Компьютеры + программы. -Киев, 1999.-N I.e. 62-64.

49. Мусин О.Р. Эффективные алгоритмы для теста принадлежности точки многоугольнику и многограннику // Программирование. 1991 - N 4 - С. 72-81.

50. Нефедов В. И. Современные системы подвижной связи: Учеб. пособие. -М., 1999.

51. Новик Д.А. Эффективное кодирование. М.: Энергия, 1965.

52. Организация баз данных в вычислительных системах. И.В. Иванов, А.П.Семенов / Под ред. А.Б. Ковалева М.: Мир, 1980.

53. Патрик Э. Основы теории распознавания образов: Пер. с англ./ Под ред. Б.Р.Левина. М.: Сов. радио, 1980.

54. Першиков В.И., Савинков В.М. Информатика. М.: Фин. и стат., 1991.

55. Попов Э. В. Экспертные системы: решение неформализованных задач в диалоге с ЭВМ. М.: Наука, 1987.

56. Приобретение знаний: Пер. с япон. / Под ред. С. Осуги, Ю. Саэки. М.: Мир, 1990.

57. Распознавание. Нейросети. Виртуальная реальность / Под ред. В. Б. Бетелина (Вопросы кибернетики) М., 1997.

58. Распознавание образов: состояние и перспективы: Пер. с англ.: К.Верхаген, Р.Дейн, Ф.Грун М.: Радио и связь, 1985.

59. Растригин Л.А., Эренштейн Р.Х. Метод коллективного распознавания. -М.: Энергоиздат, 1981.

60. Розенблат Ф. Принципы нейродинамики (персептрон и теория механизмов мозга). М.: Мир, 1965.

61. Романов А. А. Геоинформационные технологии и интерактивная компьютерная обработка изображений в задачах дотационного зондирования океана: Учеб. пособ. (Моск. физ. техн. ин-т (гос. ун-т)) / Романов А. А. - М., 1999. - 230 с.

62. Рязанов Ф.И., Сиваков A.M., Орлецкий Ю.М. Топографическое обеспечение организаций связи. Москва: Радио и связь - 1996.

63. Сиваков A.M. Топография для связистов. М.: Радио и связь, 1994.

64. Тикунов В. С. Устойчивое развитие территорий: картографо-геоинформационное обеспечение / Цапук Д. А. М. - 1999.

65. Топография ./ Бубнов И.А., Кремп А.И. и др. / Под ред. Бубнова И.А. М.: Недра, 1997.

66. Трофимова И. П. Системы обработки и хранения информации М.: Высш. шк., 1989.

67. Ту Дж., Гонсалес Р. Принципы распознавания образов. М.: Мир, 1978.

68. Уэзерелл Ч. Этюды для программистов. М.: Мир, 1982.

69. Федотова А. А., Фомина М. В. Система формирования обобщенных продукционных правил на основе анализа больших баз данных // Сб. научн. тр. Шестой национальной конф. по искусственному интеллекту КИИ-98. т.1. Пущино, Россия, 1998.

70. Фролов А.Б. Яко Э. Алгоритмы распознавания частично упорядоченных объектов и их применение // Изв. АН СССР. Техническая кибернетика. -1990 N 5 - С. 95 - 103.

71. Фу К. Структурные методы в распознавании образов. М.: Мир, 1977.

72. Халугин Е. И., Жалковский Е. А., Жданов Н. Д. Цифровые карты./ Под ред. Е. И. Халугина. М.: Недра, 1992.

73. Ходоровский JI.A. Отображение факторов из базы данных в факты пролога // Всесоюз. конф. по искусственному интеллекту: Докл. 1988 - Т. 3 . С.474-476.

74. Цветков В. Я., Геоинформационные системы и технологии. М.: Фин. и стат.,1998.

75. Цымбал В.П. Теория информации и кодирования. Киев: Наукова думка, 1977.

76. Шерстнев В.Ю. Исчисление для извлечения данных // Всесоюз. конф. по искусственному интеллекту: Докл. 1988 - Т. 1 - С. 411-416.

77. Яко Е. Итеративные канонические разложения булевых функций и их приложения в логическом проектировании. / Диссертация на соиск. уч. степ. к. т. н., М: МЭИ -1983.

78. Aasheim О. Т., Solheim Н. G. Rough Sets as a Framework for Data Mining / Project Report. Faculty of Computer Systems and Telematics, The Norwegian University of Science and Technology, Trondheim, 1996.

79. Bassiouni M.A. Data compression in scientific and statistical databases. // IEEE Trans. On Soft. Ing. 1985 - V. 11 - N 10 - P. 1047 - 1058.

80. Carpenter G. A., Grossberg S. A massively parallel Architecture for a Self-organizing Neural Patteny Recognition Machine // Сотр. Vision, Graphics and Image Proceess. 1987. - V. 37. - P. 54 - 115.

81. Cheng Jicheng. Information Super-Highway and Geographic Information System: On the Information Revolution of Geography // Dizhi Keji Qingbao. Sci. And Technol. Inf. 1997, 16 Suppl., p. 9 - 14.

82. Cormack G. V. Data compression on a database system. // CACM 1985 - V. 28-N 12- P. 1336- 1342.

83. Fano R.M. Transmission of information. MIT Press Wiley. London - 1975.

84. Fukushima K. A. Neural Network Models for Selective Attention in Visual Pattern Recognition // Biol. Cybernetics. 1986. - V. 45 - P. 5 - 45

85. Gaines B.R. and Kohout L.S. Transmission of information. // Int. F. Man-Machine Studies 1977 - V. 9 - P. 1 - 68.

86. Gallager R.G. Variations on a theme by Huffman. // IEEE Trans. On Inform. Theory. 1978 - V. 24 - N 6 - P. 668 - 674.

87. Holsheimer M., Kersten M. L. Architectural Support for Data Mining / Eds. U. M. Fayyad and R. Uthurusamy. AAAI-94 Workshop Knowledge discovery in Database, Seattle, Washington, 1994.

88. Huffman D. A method for the construction of minimum redundancy codes. // Proc. IRE 1952 - V. 40 - P. 1098 - 1101.

89. International Journal of Expert Systems: Reseach and Applications. 1990 -V.2 - N.4.

90. Ireland P. Plugging into Cyberspace // GIS Europe, 1997, n. 8, p. 22 24.

91. Jako E., P. Ittzes. A discrete methematical approach to the analysis of spatial pattern // Abstracta Botanica 22: 121 142, 1998 Department of Plant Taxonomy and Ecology, ELTE, Budapest.

92. Katajainen J., Penttonen M., Teuhola J. Syntax-directed compression of program files. // Software Practice Experience 1986 -V. 16-N3-P. 269 -279.

93. Nunez M. The Use of Background Knowledge in Decision Tree Induction // Machine Learning, 1991, N 6.

94. Proceedings IEE Int. Conf. Artif. Newral Networks. London. - 1989.

95. Proceedings of the Third conference on Artificial Intelligence applications. -Philadelphia 1987.

96. Proceedings of the Fifth International conference on Machine Learning. -Los Altos 1988.

97. Quinlan J. R. Induction of Decision Trees // Machine Learning. 1986. N 1.

98. Ram S., Park J., Ball G. L. Semantic model support for geographic information system // Computer. - Los Alamitos, 1999. - vol. 32, n. 5, p. 74 -81.

99. Reghbati H. K. An overview of data compression techniques. // Computer -1981-P. 71-75

100. Ruth S. S., Kreutzer P. J., Data compression for large business files. // Datamation 1972 - V. 18 - N 8 - P. 62 - 66.170

101. Schwartz E.S., Dictionary for minimum redundancy coding. // Journal of ACM 1963 - N 10 - P. 413 - 439.

102. Snyderman M., Hunt B. The myriad virtues of text compaction. // Datamation 1970 - N 16 - P. 36 - 40

103. Spitzer T. 1997 = nineteen ninety seven // DBMS. Redwood City, 1997. -vol. 10, n. 1, p. 63-64, 66-69.

104. Susan J. E., Olken F., Shoshani A. A compression technique for large statistical Databases // Proc. Very Large Data Base, IEEE -1981 P. 424 434

105. Toon M. The World by Your Window // GIS Europe, 1997, v. 6, 11, 38-41

106. Virtual Frontier. Promo CD // North Wood Geosience Ltd. Klondike Software Inc. 1999.

107. Wagner R. A. Common phrases and minimum text storage. // Communication Of ACM 1973 - V. 16 - N 3 P. 148 - 153.

108. Zadeh L.A. Information and Control 1965 - P. 338-53.

109. Ziv J., Lempel A. A universal algorithm for sequential data compression. // IEEE Trans, on Inform. Theory 1977 - V. 23 - N 3 - P. 337 - 343