автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Автоматическое районирование многомерных данных в векторных ГИС

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

Заварзин Андрей Владимирович

АВТОМАТИЧЕСКОЕ РАЙОНИРОВАНИЕ МНОГОМЕРНЫХ ДАННЫХ В ВЕКТОРНЫХ ГИС

Специальность 05.13.17 - теоретические основы информатики

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

Москва 2003

Работа выполнена в Московском государственном университете им. М.В Ломоносова.

Научный руководитель: доктор географических наук, профессор

Тикунов B.C.

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

Ведущая организация: ГУЛ «НПО «Астрофизика» (г. Москва).

Защита состоится 23 октября 2003 г. в 10.00 на заседании диссертационного совета Д 217.031.01 Российского научно-исследовательского института информационных технологий и систем автоматизированного проектирования по адресу Москва, ул. Щепкина, 22.

С диссертацией можно ознакомиться в библиотеке РосНИИ ИТиАП. Автореферат диссертации разослан 22 сентября 2003 г.

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

диссертационного совета Д 217.031.01

кандидат технических наук М.М.Виньков

профессор Грушо А.А.;

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

Мартыненко А.И.

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

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

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

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

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

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

Всюду далее термин «пространственные» указывает на наг яЧИев^

з т

БИБЛИОТЕКА С. Петербург

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

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

Определим понятие районирования формально. Обозначим множество исследуемых пространственных объектов символом 0 = {о,,...,ол,},где о, - /-й объект, N - количество объектов.

Зададим матрицу пространственной смежности объектов Gf/xN = (.Sij) >

Будем называть /-м районом некоторое подмножество смежных объектов

= К е О| Эо„ € 5,: г(о„, о„) = 1; у,/ е 1.....Ы,} с О, где

Ы, = 15, | <, N -мощность /-го района.

Под системой районов, получение которой является целью районирования, будем понимать множество 5 со следующими свойствами:

1. 51 = {5, | / е 1,..., К}, т.е. 5 состоит из К районов.

2. 5, П=6 V/,/ е {1,, где 0-пустое множество.

3. 5( т.е. | > 0 \//е {!,...,£}.

gj,=glj=g(0„0j) =

1, о, и Oj смежны; О, иначе.

к

к

4. Üs.=°>

¡■1

м

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

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

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

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

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

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

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

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

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

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

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

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

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

Методологическую и теоретическую основу исследования составили научные труды отечественных и зарубежных прикладных математиков и географов. Ведущие работы по методам анализа данных и распознаванию образов за рубежом принадлежат M.Jambu, M.Kendall, G.Kramer, J.Kruskal,

G.Lance, J.Mac Queen, W.Williams. Методологическим проблемам классификации принадлежат работы отечественных ученых С.А.Айвазяна, Э.М.Бравермана, В.М.Бухштабера, И.С.Енюкова, Л.Д.Мешалкина, Б.Г.Миркина. Отечественными географами, заложившими и развивающими классификационное движение в геоинформатике, являются И.Г.Александров,

H.Н.Баранский, В.И.Блануца, Н.Н.Колосовский, Г.М.Кржижановский, Т.М.Калашникова, В.А.Рубцов, Ю.Г.Саушкин, В.С.Тикунов, А.М.Трофимов, М.Д.Шарыгин.

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

Научная новизна исследования заключается в:

— определении роли и места районирования в разделе классификации методов анализа данных: постановка задачи районирования является частным случаем постановки задачи «классификации с ограничениями»;

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

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

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

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

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

Внедрение.

1. Разработанные и реализованные методы районирования внедрены в практическую деятельность группы «Меркатор» Института географии РАН. Получен акт о внедрении.

2. Результаты диссертационной работы используются в курсе «Геоинформатика», читаемом на географическом факультете МГУ имени М.В.Ломоносова. Получена справка о внедрении.

3. Разработанное программное обеспечение «GisCluster 2.0» и результаты диссертации, касающиеся свойств алгоритмов районирования многомерных пространственных данных и методики визуализации, внедрены в учебный процесс в/ч 33965. Получен акт о внедрении.

Апробация работы. Основные научные положения, теоретические и

практические результаты диссертационного исследования докладывались и

обсуждались на четырех научных конференциях, в том числе международных:

— на Межведомственной научно-практической конференции (Москва, ФАПСИ при Президенте РФ, 2002);

— на Международной научной конференции «Интернет - Образование -Наука» (Украина, Винница, 2002);

— на Международной научной конференции «Интернет - среда новых технологий и информационного общества» (Болгария, Велико Търново, 2001);

— на Международной научной конференции «Разработка прикладных систем» (Сучава, Румыния, 2001).

В Международной научной конференции 2002 года в Винницком государственном техническом университете (Украина) автор участвовал в качестве члена оргкомитета.

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

Положения, выносимые на защиту:

— классификация методов районирования, произведенная с позиций методов анализа данных;

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

Структура работы. Диссертация состоит из введения, трех глав, выводов по главам и заключения, изложенных на 159 страницах, содержит 32 таблицы и 16 рисунков, список литературы из 67 наименований и 10 приложений.

2. ОСНОВНЫЕ ПОЛОЖЕНИЯ И ВЫВОДЫ ИССЛЕДОВАНИЯ

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

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

В настоящее время в методах анализа данных сложилась система алгоритмов классификации (Айвазян и др., 1983, 1989, 2001). На практике наиболее распространены случаи отсутствия обучающих выборок и однозначного описания законов распределения вероятностей классов. Для данной ситуации в работе (Айвазян, Мхитарян, 2001, с.470) выделены группы методов «ядерной» классификации, иерархической классификации и расщепления смеси вероятностных распределений.

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

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

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

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

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

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

— SAS Bridge for ESRI;

— S-PLUSforArcViewGIS;

— картографический модуль статистического пакета SPSS;

— модуль Mapping Toolbox пакета Matlab.

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

классификации (Заварзин, 2002, а). Примерами общих математических постановок задач для разных предметных областей, в частности, являются:

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

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

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

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

Рис. 1. Система методов автоматического районирования

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

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

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

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

Основными процессами проведения автоматического районирования многомерных пространственных данных в векторных ГИС являются:

1. Манипуляция слоями векторной карты и внешними таблицами анализа.

2. Задание начальных условий алгоритмов.

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

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

5. Запуск и работа алгоритма районирования.

6. Визуализация хода и результатов районирования.

7. Сохранение результатов районирования.

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

Формализацию и решение задачи идентификации пространственных объектов произведем в терминах теории распознавания образов (Заварзин, Месюра, 2001). Обозначим X = {*,,...,%,} - множество картографических названий OTE (столбец имен OTE атрибутивной таблицы слоя векторной карты), К = } - множество значений столбца имен OTE во внешней

таблице. Назовем X множеством эталонов, Y - множеством образов, подаваемых на вход процедуры идентификации. Процедура идентификации состоит в построении инъективного отображения идентификации /: Y -» X.

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

X = {х, ,хг,...,XNx } = {{*||,...,*iWl }, {-*21>— '-^Л»,}..... {XNxt'—>XN,N„x }}»

х, ={x'l¡,...,xlN} - множество возможных вариантов написаний названия /-ЙОТЕ.

Сформируем признаковое пространство V = }:

{0, 3 t б {1, ..., N,}: строка у, содержит строку х]., 1, иначе.

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

Функцию идентификации / зададим итеративно с помощью следующего алгоритма.

1. Положить n=\NY\.

2. Vy, е У найти с, = min{d{ynx]) \ х] е X"} и сформировать множества x;={x-jex'\d(y„x]) = cl}.

3. Vy, е Г: если !х,"| = 1, положить f(y,) = x] е X", X" = Х"\Х^Г = Y\{yt}.

4. Если и =1^1, конец, иначе к шагу 1.

После окончания работы алгоритма задания функции / множества Y и X" содержат OTE, не прошедшие идентификацию.

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

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

Для определения временной сложности расчетов матрицы смежности с помощью программного продукта GisCluster 2.0, разработанного автором, проведен ряд экспериментов на shape-файлах (векторный стандарт компании ESRI, *.shp). Под обозначением Т, далее понимается время проведения эксперимента в секундах на ПК, оснащенном процессором тактовой частоты i.

Зависимость времени расчета матрицы смежности от количества объектов представим следующей таблицей.

п-1

Таблица 1

Время вычисления матриц смежности

Эксперимент 1 2 3 4 5 6

Объектов, N 92 95 110 164 2369 3140

Время, Г500 , сек. 5.5 28 21 14.5 238 15

Для одинакового количества объектов время построения матрицы смежности может значительно различаться; 5.5, 14.5, 21 и 28 секунд для 92-164 картографических объектов и 15 и 238 секунд для порядка 3000 картографических объектов. Такая разница объясняется конфигурацией полигональных объектов. Для двух различных оцифровок субъектов Российской Федерации (эксперименты 2 и 3) каждый картографический полигональный объект представлен гораздо более представительным набором точек, чем объекты модельного примера с 92 объектами (эксперимент 1). Слой округов США (эксперимент 6) состоит из практически прямоугольных объектов, для оцифровки каждого из которых требуется немногим более четырех точек.

Исходя из относительно невысокой скорости получения матрицы смежности актуальным вопросом является организация ее хранения. Так, для хранения матрицы смежности карты территориальных избирательных комиссий (ТИК) России (эксперимент 5) требуется таблица из 2369 строк и 2369 столбцов. Большинство современных СУБД не поддерживают такое количество столбцов.

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

/,« '■ Офункция смежности, О - множество картографических объектов, N - множество натуральных чисел, К0 = N и {0},

/»I

1*1

1 "

тах{X») = {тах(/т(о,)) \ о, € О},

Рш(0 = £Шт(",) = '), '£{0.....тах(/ш)}.

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

PCO 20 16 12 8 4 0

Рис. 2. Распределение смежности для N = 94

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

Таблица 2

Зависимость характеристик смежности от числа объектов

№ Объектов, N Карта aVS(Lm) maXifm)

1. 94 Субъекты РФ 4.319149 10

2. 558 Модельный пример 4.642729 14

3. 2369 ТИК РФ 4.968341 17

4. 3140 Округа штатов США 5.836306 14

Проведенные эксперименты показали, что:

— среднее количество картографических объектов, смежных с данным, варьируется от 4 до 6;

— даже при очень большом количестве картографических объектов (например, более 3000) количество объектов, смежных с данным, всегда меньше некоторого порогового значения max{fm).

Способы «сжатия» и хранения разреженных матриц известны (Джордж, Лю, 1984). Одним из самых простых и эффективных подходов к хранению разреженной бинарной матрицы является ее представление в виде списка списков

G' =(С;',...,G'Nf, G,- =(«,„...,и,е {1,...,ЛГ}, ""» <=>&«, =1-

л

j

/ \ N-94

Л/ \

Г V

1

0 4 8 12 16 i

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

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

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

Таблица 3

Время адаптации матриц смежности

Эксперимент 1 2 3 4

Объектов, N 95 164 2369 3140

Время, Тш, сек 0.2 0.2 3.4 4.1

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

Время

Классов

Рис. 3. Временные характеристики ядерного алгоритма районирования (3140 объектов)

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

Временная трудоемкость агломеративных иерархических алгоритмов районирования при их общепринятой реализации на порядок превосходит ядерные и дивизимные. Для статистического пакета Statgraphics, пяти признаков и N = 2369 объектов время классификации (как и время районирования) составляет Т^ = 1015 секунд, для jV = 3140 объектов - Тш = 2640 секунд.

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

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

Для преодоления указанного недостатка предложен комбинированный алгоритм, базирующийся на прямом расчете межрайонных расстояний для географически смежных районов и частичном использовании формулы Жамбю (Mesura, Zavarzin, 2002а). Редуцирование времени расчетов основано на показанной ранее разреженности матрицы смежности.

Обозначим

G(St, Sz) = max{g(oh, ог]) \ 0kl s St, оу е Slt iel,..,N„, j е 1,..., N,} s {0,1}.

Пусть на итерации n е {1,...,JV-1} был получен район = S, иSy = {ох1, о„ | О,, tSx, олеSr,le 1 ,..,N„ j e 1,..., Ny}.

Из этого следует, что G(SX, Sy) = 1. Тогда расчет межрайонных расстояний D(Sk,Sv) будем производить по следующему алгоритму: + оо, G(St,S4,) = 0;

D(St,Sv) = DJam{St>S№), G(St,Sx) = G(St,Sy) = 1; , û;„(St,S,,),G(St,SJ + G(S4,S,) = 1. где последний случай D'^iS^S^) характеризуется предварительным прямым расчетом недостающего для использования в формуле Жамбю расстояния D(Sk,Sx) ИЛИ D(Sk,Sy).

Здесь и далее:

— ~ алгоритм районирования или классификации ближнего соседа;

— - алгоритм районирования или классификации дальнего соседа;

— £>„„ - центроидный алгоритм районирования или классификации;

— - алгоритм районирования или классификации группового среднего; Ниже приведены результаты замеров времени, потребовавшегося для

проведения иерархического агломеративного районирования по пяти признакам 2369 объектов (ТИК РФ) и 3140 объектов (округа США) с использованием предложенного комбинированного алгоритма. В диссертации в Приложении И приведены графики и полные матрицы данных вида итерация-время для 3140 объектов.

Таблица 4

Зависимость времени районирования от алгоритма и количества объектов (комбинированный метод расчетов)

№ N Тт, сек. •руат '500 ' 1 500 гр }Ш гр •'500 500

1. 2369 ^тт 3978 0.26 -2963

•7&2Г ..... ■ • - .■.».■■Си. ±

■3. : ШТ- • 'ЛГ^..';

4. 2369 1220 0.83 -205

5. 3140 8755 0.30 -6115

• ■ .„роям* , - 1 .^.и^, л'

ф} за**? НЯВ^! Й" ____«ГГ.*» «ас». »••'"■'

8. 3140 д.„„ 4502 0.59 -1862

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

— для случая 2369 объектов и О - О^ в 1.48 раз (5.5 мин);

— для случая 2369 объектов и £> = ВС1Л в 2.06 раз (8.7 мин);

— для случая 3140 объектов и £> = £>ти в 1.12 раз (4.7 мин);

— для случая 3140 объектов и £> = £>„„ в 2.56 раз (26.8 мин).

Ранжирование методов районирования отдельно по каждому эксперименту и агрегирование результатов позволили отсортировать алгоритмы в порядке увеличения времени анализа: Д,„г, £>тт.

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

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

£м-т>1

Л =

Л-1

(2), где

N

N - общее количество объектов, Ы, - количество объектов в /-м классе, к - количество классов.

Легко показать, что Я е [0,1]. Близкие к нулю значения показателя соразмеримости Я свидетельствуют о наиболее равномерном распределении объектов по классам, близкие к единице - наоборот.

При рассмотрении иерархических алгоритмов классификации для возможности сравнения результатов итераций удобно положить к = N. Тогда формула (2) примет следующий вид:

-о2

Д = .!=!_- (3) .

N(N-1)

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

Рис. 4. Значения показателя соразмеримости Д

19

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

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

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

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

Разработанная модель картографического представления хода и результатов анализа позволила при проведении экспериментов над многомерными пространственными данными:

— обнаруживать несоответствия, ошибки в данных;

— выявлять скрытые закономерности в данных;

— определять свойства алгоритмов классификации;

— снижать время получения конечного результата анализа.

Примером практического применения разработанной в ходе диссертационного исследования технологии автоматического районирования может служить проведенный в рамках Атласной информационной системы «Устойчивое развитие России» (Тикунов, 2002) эксперимент по анализу электоральной статистики за 2000 год. Сопоставление хода и результатов работы нескольких алгоритмов районирования позволило выделить в

электоральном ландшафте России ареалы особой манеры поведения избирателей.

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

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

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

Практически значимыми являются разработанные автором:

1. Модель идентификации объектов. Для 89 субъектов РФ произведено «обучение» модели и выявлено ориентировочное количество итераций обучения.

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

3. Модель визуализации хода и результатов районирования. Новизна подхода заключается в рассмотрении хода работы алгоритмов районирования как объекта визуализации и позволяет повысить качество анализа за счет визуального выявления ошибок и скрытых закономерностей в данных.

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

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

В целях продолжения развития положений данного исследования предполагается дальнейшая работа в следующих направлениях:

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

— экспертное оценивание качества работы (степени «полезности») предложенных и реализованных алгоритмов районирования на различных классах задач.

3. ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

Учебники и учебные пособия

1. Заварзин A.B., Тикунов B.C. Классификации // Основы геоинформатики. -М.: Изд-во «Академия», 2003. - С. 213-248.

2. Заварзин A.B. Практикум по дисциплине «Методы анализа данных». - М.: в/ч 33965,2002.-36 с.

Статьи

3. Заварзин A.B., Месюра В.И. Идентификация объектов при автоматической классификации многомерных пространственных данных в векторных ГИС // Измерительная и вычислительная техника в технологических процессах. -2001. №4(18).-С. 177-182.

4. Заварзин A.B., Месюра В.И. Визуализация автоматической классификации многомерных пространственных данных // Оптико-электронные и информационные технологии. - 2002. №1(3). - С.30-38.

5. Заварзин A.B., Месюра В.И. Разработка и исследование иерархических агломеративных алгоритмов районирования // Радиоэлектроника, информатика, управление. - 2003. - №1 (9). - С.76-81.

6. Заварзин A.B., Орешкина Д.Д., Тикунов B.C. Электоральная культура России: классификации и картографирование в геоинформационной среде // Информационный бюллетень ГИС-Ассоциации. - 2003. №1(38)-2(39). - С. 67-72.

7. Кретов B.C., Пинчук И.С., Заварзин A.B. Использование геоинформационных систем при планировании и проведении миротворческих операций // Военная мысль. - 2001. №6. - С. 23-27.

8. Mesura V., Zavarzin A. Development and realization of agglomerative regionalization algorithms and probing of their time complexity // Advances in electrical and computer engineering. - 2002. Vol 2(9). № 1(17). - P. 23-28.

Тезисы докладов, материалы конференций

9. Заварзин A.B. Проблемы автоматического районирования больших объемов многомерных пространственных данных // «Интернет — Образование -Наука». Сбор, матер. III международ, конф. 8-12 октября 2002 г. - Украина, Винница, 2002. - С. 358-362.

10. Заварзин A.B. Классификация многомерных данных при наличии ограничений // Сбор, матер, научно-практич. конф. ФАПСИ 12-13 ноября 2002 г. -М: ГУИС ФАПСИ, 2002. -С.188-193.

11. Mesura V.I., Zavarzin A.V. ER-model of classification system of multidimensional data in vector GIS // Сбор, трудов V международ, научной конф. - Болгария, Велико Търново, 16-19 октября 2002. - С. 53-57.

12. Mesura V.I., Zavarzin A.V. The model of informational web-site // Development and application systems. Proceedings of the 6th International Conference. -Suceava, Romania. - 23-25 May, 2002. - P.376-379.

В совместных публикациях автор диссертации принимал личное участие в проведении исследований, разработке научных положений и выводов, интерпретации полученных результатов, проведении компьютерных экспериментов и расчетов, написании текстов. Научный вклад Заварзина А.В. в публикации №№ 1,3,4, 5, 8, 11,12 составляет не менее 85%, в публикации №№ 6, 7 - 30%.

I

ч

Научное издание

Заварзин Андрей Владимирович

АВТОМАТИЧЕСКОЕ РАЙОНИРОВАНИЕ МНОГОМЕРНЫХ ДАННЫХ В ВЕКТОРНЫХ ГИС

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

Отпечатано в копицентре «Учебная полиграфия» Москва, Ленинские горы, МГУ, 1 Гуманитарный корпус. www.stprint.nl e-mail: 7aka7/3)stprint.ru тел 939-3338 Заказ № 372, тираж 75 экз. Подписано в печать 18. 09.2003 г.

»14983

Sloos-A

Введение.

Глава 1. Теоретические основы автоматической классификации многомерных данных в векторных ГИС.

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

1.1.1 Постановка задачи классификации многомерных данных.

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

1.1.3 Модель смеси распределений.

1.1.4 Методы классификации без обучения.

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

1.2.1 Направления исследований авторов.

1.2.2 Оценочные и типологические классификации многомерных данных

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

1.2.4 Учет при классификации многомерных данных географического пространства.

1.3 Реализация методов автоматической классификации и районирования в современных векторных ГИС.

1.3.1 Реализация в векторных ГИС методов классификации по единственному признаку.

1.3.2 Реализация в векторных ГИС методов классификации по многим признакам.

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

Глава 2. Формирование системы методов автоматического районирования.

2.1 Система методов автоматического районирования.

2.1.1 Обобщение постановки задачи районирования.

2.1.2 Классификация методов районирования.

2.2 Ядерные методы автоматического районирования.

2.2.1 Общая схема ядерного алгоритма районирования.

2.2.2 Алгоритм районирования на основе метода классификации к-медоидов.

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

2.3 Иерархические методы автоматического районирования.

2.3.1 Агломеративные иерархические алгоритмы районирования.

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

2.3.3 Дивизимный иерархический алгоритм районирования барьеров максимальных различий.

2.4 Выводы по главе 2.

Глава 3. Разработка технологии автоматического районирования.-.

3.1 Общая схема процессов автоматической классификации и районирования.

3.1.1 Этапы автоматической классификации многомерных данных в векторных ГИС.

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

3.2 Модели идентификации объектов.

3.2.1 Постановка задачи идентификации объектов.

3.2.2 Формализация задачи идентификации объектов.

3.2.3 Базовая и расширенная модели идентификации объектов.

3.2.4 Исследование разработанных моделей.

3.3 Получение, хранение и использование матрицы смежности.

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

3.3.2 Вычисление матрицы смежности для одинакового количества объектов.

3.3.3 Зависимость времени вычисления матрицы смежности от частоты процессора.

3.3.4 Зависимость времени вычисления матрицы смежности от количества объектов.

3.3.5 Организация хранения матрицы смежности.

3.3.6 Дополнительные сложности программной реализации модуля расчета матрицы смежности.

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

3.4.1 Проблема расчета межрайонных расстояний для агломеративных методов районирования.

3.4.2 Комбинированный алгоритм расчета межрайонных расстояний.

3.4.3 Оценка временной сложности агломеративных алгоритмов районирования.

3.4.4 Пространственные свойства образуемых районов для различных агломеративных алгоритмов районирования.

3.5 Модель визуализации хода и результатов анализа.

3.5.1 Классические средства визуализации.

3.5.2 Картографические средства визуализации.

3.5.3 ER-модель визуализации.

3.5.4 Пример визуализации автоматического районирования.

3.6 Выводы по главе 3.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Методологическую и теоретическую основу исследования составили научные труды отечественных и зарубежных прикладных математиков и географов. Ведущие работы по прикладной статистике и классификации за рубежом принадлежат M.Jambu, M.Kendall, G.Kramer, J.Kruskal, G.Lance, J.Mac Queen, W.Williams. Методологическим проблемам классификации в прикладной статистике посвящены работы отечественных ученых С.А.Айвазяна, Э.М.Бравермана, В.М.Бухштабера, И.С.Енюкова, Л.Д.Мешалкина, Б.Г.Миркина. Отечественными географами, заложившими и развивающими классификационное движение в геоинформатике, являются И.Г.Александров, Н.Н.Баранский, В.И.Блануца, Н.Н.Колосовский, Г.М.Кржижановский, Т.М.Калашникова, В.А.Рубцов, Ю.Г.Саушкин, В.С.Тикунов, А.М.Трофимов, М.Д.Шарыгин. 0 В работе использовались следующие методы исследования: системный анализ; методы анализа данных; методы экспертного оценивания; эксперимент; измерение; сравнение.

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

Научная новизна исследования заключается в:

- определении роли и места районирования в разделе классификации методов анализа данных: постановка задачи районирования является частным случаем постановки задачи «классификации с ограничениями»;

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

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

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

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

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

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

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

- на Межведомственной научно-практической конференции (Москва, ФАПСИ при Президенте РФ, 2002);

- на Международной научной конференции «Интернет — Образование — Наука» (Украина, Винница, 2002);

- на Международной научной конференции «Интернет - среда новых технологий и информационного общества» (Болгария, Велико Търново, 2001);

- на Международной научной конференции «Разработка прикладных систем» (Сучава, Румыния, 2001).

В Международной научной конференции 2002 года в Винницком государственном техническом университете (Украина) автор участвовал в качестве члена оргкомитета.

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

глава «Классификации» в учебнике для ВУЗов «Основы геоинформатики» (Заварзин, Тикунов, 2003); учебно-методическое пособие (Заварзин, 2002 а); шесть научных статей в реферируемых журналах (Кретов, Пинчук, Заварзин, 2001; Заварзин, Месюра, 2001; Заварзин, Месюра, 2002; Mesura, Zavarzin, 2002 а; Заварзин, Месюра, 2003; Заварзин, Орешкина, Тикунов, 2003); четыре статьи в сборниках материалов конференций (Заварзин, 2002 а; Заварзин, 2002 б; Заварзин, 2002 в; Mesura, Zavarzin, 2002 b).

Получено три акта о внедрении результатов исследования:

1. Разработанные и реализованные методы районирования внедрены в практическую деятельность группы «Меркатор» Института географии РАН.

2. Результаты диссертационной работы используются в курсе «Геоинформатика», читаемом на географическом факультете МГУ имени М.В.Ломоносова.

3. Разработанное программное обеспечение «GisCluster 2.0» и результаты диссертации, касающиеся свойств алгоритмов районирования многомерных пространственных данных и методики визуализации, внедрены в учебный процесс в/ч 33965.

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

Структура и объем работы.

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

3.6 Выводы по главе 3

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

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

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

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

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

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

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

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

3. Установлено, что время работы агломеративного алгоритма может отличаться для разных признаков и одного и того же их количества (М = const), т.к. изменяется пространственная конфигурация получаемых районов.

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

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

Заключение

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

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

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

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

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

Результаты проведенных работ позволили сделать ряд выводов.

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

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

Практически значимыми являются разработанные автором:

1. Модель идентификации объектов. Для 89 субъектов РФ произведено «обучение» модели и выявлено ориентировочное количество итераций обучения.

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

3. Модель визуализации хода и результатов районирования. Новизна подхода заключается в рассмотрении хода работы алгоритмов районирования как объекта визуализации и позволяет повысить качество анализа за счет визуального выявления ошибок и скрытых закономерностей в данных.

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

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

1. Айвазян С.А. и др. Прикладная статистика: Исследование зависимостей. -М., Финансы и статистика, 1985. 607 с.

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

3. Айвазян С.А., Мхитарян B.C. Основы эконометрики. Теория вероятностей и прикладная статистика. М., Юнити, 2001. - 656 с.

4. Александров Ю.К. Применение метода случайного поиска. // Математическое обеспечение задач размещения производства. М.: Наука, 1974.

5. Александров Ю.К., Кистанов В.В., Эпштейн А.С. Опыт количественной разработки схемы экономических районов СССР // Известия РАН. Серия географическая, №2 1974.

6. Арманд А.Д. Метод информационных градиентов в географическом районировании // Известия РАН. Серия географическая, №3 1973.

7. Блануца В.И. Система методов автоматической классификации географических объектов: некоторые способы оценки качества классификаций // Известия РАН. Серия географическая, №3 1984.

8. Блануца В.И. Преобразование метода районирования для решения задач географического прогнозирования. // География и природные ресурсы. -1987, №4.

9. Блануца В.И. Проблемный подход к районированию: построение алгоритма и опыт реализации. // География и природные ресурсы. 1989, №1.

10. Блануца В.И. Интегральное экологическое районирование: концепции и методы. Новосибирск: ВО «Наука», 1993. - 159 с.

11. Гайдышев И. Анализ и обработка данных: специальный справочник. СПб: Питер, 2001.-752 с.

12. Гусейн-Заде С.М., Тикунов B.C. Анаморфозы: что это такое? М.: Эдиторал УРСС, 1999.- 168 с.

13. Дэйвинсон М. Многомерное шкалирование. Методы наглядного представления данных. М.: Финансы и статистика, 1988. - 348 с.

14. Дейт Л. Дж. Введение в системы баз данных. Пер. с англ. К.: Диалектика, 1998.

15. ДеМерс. Географические информационные системы. М: Дата+, 1999.-350 с.

16. Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений. Пер. с англ. - М.: Мир, 1984. - 333 с.

17. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир,1976.-512 с.

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

19. Дюран Б., Оделл П. Кластерный анализ. М.: Финансы и статистика,1977.- 176 с.

20. Евдокимова А.К., Солнцева О.И., Тикунов B.C. Изучение распределения тяжелых металлов для характеристики археологических объектов (на примере средневековых городищ Средней Азии) // География и природные ресурсы, 1988, №1. С.97-104.

21. Енюков И.С. Методы, алгоритмы, программы многомерного статистического анализа: пакет ППСА. — М.: Финансы и статистика, 1986.-232 с.

22. Жамбю М. Иерархический кластер-анализ и соответствия. М: Финансы и статистика, 1989. -342 с.

23. Жуков В.Т., Сербенюк С.Н., Тикунов B.C. Математико-картографическое моделирование в географии. -М: Изд-во «Мысль», 1980. 223 с.

24. Заварзин А.В. Классификация многомерных данных при наличии ограничений // Сбор, матер, научно-практич. конф. ФАПСИ 12-13 ноября 2002 г. М: ГУИС ФАПСИ, 2002. - С. 188-193.

25. Заварзин А.В. Проблемы автоматического районирования больших объемов многомерных пространственных данных // Интернет Образование - Наука. Сбор, матер. III международ, конф. 8-12 октября 2002 г. - С.358-362.

26. Заварзин А.В., Месюра В.И. Идентификация объектов при автоматической классификации многомерных пространственных данных в векторных ГИС // Измерительная и вычислительная техника в технологических процессах. -2001. №4(18).-С.177-182.

27. Заварзин А.В., Месюра В.И. Визуализация автоматической классификации многомерных пространственных данных // Оптико-электронные и информационные технологии. 2002. №1(3). - С.30-38.

28. Заварзин А.В., Месюра В.И. Разработка и исследование иерархических агломеративных алгоритмов районирования // Радиоэлектроника, информатика, управление. 2003. - №1 (9). - С.76-81.

29. Заварзин А.В., Орешкина Д.Д., Тикунов B.C. Электоральная культура России: классификации и картографирование в геоинформационной среде // Информационный бюллетень ГИС-Ассоциации. 2003. №1(38)-2(39). - С. 67-72.

30. ЗО.Заварзин А.В., Тикунов B.C. Классификации // Основы геоинформатики. -М.: Изд-во «Академия», 2003. С. 213-248.

31. Изучение ГИС. Создание географических информационных систем с помощью персональных компьютеров. Методология Arc/Info. Калифорния, Институт исследований систем окружающей среды (ESRI), 1997.

32. Иванов В.И., Легостаев С.Е. Цифровые методы картографирования. -Геодезия и картография. 1989. №10.

33. Кальянов Н.Г. CASE структурный системный анализ (автоматизация и применение). -М: «ЛОРИ», 1996.

34. Классификация и кластер. М.: Мир, 1980. - 392 с.

35. Коновалова Н.В., Капралов Е.Г. Введение в ГИС. Петрозаводск: изд-во Петрозавод. ун-та, 1995. - 148 с.

36. Королев Ю.К. Общая геоинформатика. М: Дата+, 1998. - 118 с.

37. Королев Ю.К. Статьи, лекции, доклады по проблемам геоинформатики. М: Дата+, 2000. - 127 с.

38. Кретов B.C., Пинчук И.С., Заварзин А.В. Использование геоинформационных систем при планировании и проведении миротворческих операций // Военная мысль. 2001, №6. - С.23-27.

39. Левиньский С.Е. Таксономические методы в региональных исследованиях. -В сб.: Региональная наука о размещении производительных сил. Новосибирск-Иркутск, 1971.

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

41. Нутенко Л .Я. Математические методы регионализации (некоторые вопросы теории и практического применения). Автореферат диссертации на соискание ученой степени кандидата географических наук. М., 1970.-30 с.

42. Нутенко Л.Я. Типизация географических объектов как задача теории распознавания образов. // Известия РАН. Серия географическая, №6 1971.

43. Прохоров Б.Б. Медико-экологическое районирование и региональный прогноз здоровья населения России. — М: Изд-во МНЭПУ, 1996. — 70 с.

44. Саушкин Ю.Г. История и методология географической науки. М.: Изд-во МГУ, 1969.-423 с.

45. Тикунов B.C. Алгоритм для моделирования тематического содержания типологических карт. Вестник Моск. ун-та, сер. геогр., 1983, N 4, с. 78-84.

46. Тикунов B.C. Классификации в географии: ренессанс или увядание? -Смоленск, Изд-во СГУ, 1997 367 с.

47. Тикунов B.C. Моделирование в картографии. М: Изд-во МГУ, 1997, 405 с.

48. Тикунов B.C. Атласная информационная система «Устойчивое развитие России» // Вестник МГУ, сер. Геогр. 2002, № 5. - С. 21-32.

49. Тикунов B.C., Орешкина Д.Д. «Управляемая демократия»: российский вариант // Эксперт, сообщение. 2000, №11-12. - С. 61-65.

50. Трофимов A.M., Заботин Я.И., Панасюк М.В., Рубцов В.А. Количественные методы районирования и классификации. Казань: изд-во Казанск. ун-та, 1985.- 120 с.

51. Трофимов A.M., Рубцов В.А. Районирование. Математика. ЭВМ. Часть 1. -Казань: изд-во Казанск. ун-та, 1992. 132 с.

52. Трофимов A.M., Рубцов В.А. Районирование. Математика. ЭВМ. Часть 2.

53. Казань: изд-во Казанск. ун-та, 1993. 102 с.

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

55. Тюрин Ю.Н., Макаров А.А. Статистический анализ данных на компьютере. М.: ИНФРА-М, 1998. - 528 с.

56. Ambroise С., Govaert G. Spatial Clustering and the EM Algorithm. France: Universite de technologie de Compienge, 1996.

57. Mesura V., Zavarzin A. Development and realization of agglomerative regionalization algorithms and probing of their time complexity // Advances in electrical and computer engineering. 2002. Vol 2(9). №1(17) 2002. - p.23-28.

58. Mesura V.I., Zavarzin A.V. The model of informational web-site // Development and application systems. Proceedings of the 6th International Conference. -Suceava, Romania. 23-25 May, 2002. - P.376-379.

59. Mesura V.I., Zavarzin A.V. ER-model of classification system of multidimensional data in vector GIS // Сборник трудов пятой научнойконференции с международным участием. Болгария, Велико Търново, 16-19 октября 2002. С.53-57.

60. Monrnonier M.S. Maximum-difference barriers: alternative numerical regionalization method. Geogr. Anal., 1973, vol. 5, №3. - P.245-261.