Все научные статьи
Дулин С.К., Дулина Н.Г. О выборе функции сходства документов геоинформационного портала отрасли
Научная статья
Электронныйаа научныйа журналаа ИССЛЕДОВАНОаа Ваа РОССИИа 1982аа Дулин С.К. fs.dulin@ccas.ru), Дулина Н.Г. ВЦ РАН, Москва
1. Введение
Геоинформационная система (ГИС) - это программно-аппаратный человеко-машинный комплекс, обеспечивающий сбор, обработку, отображение и распространение пространственно-координированных данных, интеграцию данных и знаний о территории для их эффективного использования при решении научных и прикладных географических задач, связанных с инвентаризацией, анализом, моделированием, прогнозированием и управлением окружающей средой и территориальной организацией общества [1].
ГИС является закономерным расширением концепции баз данных, дополняя их наглядностью представления и возможностью решать задачи пространственного анализа. Специфика ГИС в том, что ее главные составные части представляют собой взаимосвязанные исходные сведения (данные или документы), их графическое представление (карта, картинка, график и т.д.) и способы или методы перехода от одного к другому. Другими словами - ядро ГИС это как бы функция, областью определения которой является база исходных (табличных, графических, текстовых) данных, областью существования - графическое представление этих данных, а самой функциональной зависимостью является методика перевода одного в другое.
Развитие современных ГИС-технологий позволяет ставить задачу создания геоинформационного портала отрасли, в состав которого должны входить функции, позволяющие осуществлять поиск требуемого геоинформационного ресурса по его текстовому описанию, формирование заявки на подключение к ресурсу, администрирование и актуализация каталога геоинформационных ресурсов отрасли. Создание геоинформационного портала позволит увязать геоинформационные ресурсы в единую интегрированную геоинформационную базу данных [2] отрасли для эффективного решения следующих задач:
Хаа рассматривать все виды геоинформационных ресурсов отрасли во взаимосвязи. Это
означает,аа чтоаа всеаа видыаа графическойаа пространственнойаа информацииаа будут
представлять собой некоторую иерархию в соответствии с масштабами, в которых
Электронныйаа научныйа журналаа ИССЛЕДОВАНОаа Ваа РОССИИа 1983аа Х Оперативно получать графическую информацию необходимого вида и содержания. На текущий момент в отрасли в качестве типовых уже используются геоинформационные ресурсы. В их состав входят: общая схема сети железных дорог, схемы железных дорог, схемы диспетчерских участков, схемы станций. Определен состав объектов и перечень условных обозначений для типовых геоинформационных ресурсов. Разработаны технологии и регламенты их актуализации. Однако в процессе принятия решений руководство отрасли зачастую использует и другую графическую информацию, например, схемы транспортных коридоров, схемы развития водно-транспортных узлов, схемы крупных железнодорожных узлов, и т.п. Необходимо сформулировать требования к виду, масштабу, составу объектов и их условным обозначениям для каждого из таких ресурсов, разработать технологию и регламент их корректировки и актуализации, определить должностное лицо, отвечающее за правильность информации.
Для выполнения действий по созданию, ведению и использованию интегрированной базы геоданных отрасли необходимо специальное программное обеспечение, опирающееся на типовые функции геоинформационных систем.
Общепринятое кодирование геопространственной информации в цифровой растровой и/или векторной форме с ограниченным использованием знаковых представлений влечет за собой ограничения в части организации семантического поиска геоданных, обусловленные отсутствием унификации описания единой модели для вербальной и невербальной информации [3], а с другой стороны сложностью структуризации системы геоязыков, используемых для формирования геоинформационных ресурсов. Знания о пространственных объектах не могут быть достаточно адекватно переданы только в лингвистической и/или формально-логической формах, о чем говорит использование широкого спектра геоописаний разной геоязыковой
Электронныйаа научныйа журналаа ИССЛЕДОВАНОаа Ваа РОССИИ а1984аа Согласно теории А.А.Лютого [4] геоинформационные описания должны основываться на трех основных сферах представления геознаний: невербальные знания, которые не могут быть представлены в лингвистической форме, вербальные знания, которые не могут быть адекватно переведены в невербальную форму, и та часть знаний, которая может быть представлена и в вербальной, и в невербальной формах. В комплексе проводимых исследований карты, аэрофотоснимки, литологические и стратиграфические колонки, картопо-добные диаграммы, палеотектонические схемы, геохимические диаграммы, схемы корреляции и так далее, должны рассматриваться как соответствующим образом оформленные геотексты.
При таком подходе геоинформационный портал можно рассматривать как электронную библиотеку, которая включает геотексты на разных геоязыках. Кроме геотекстов, библиотека, конечно же, включает вербальную информацию, позиционированную во времени и пространстве, то есть пространственно-определенные вербальные тексты на разных естественных языках.
Таким образом, геоинформационный портал рассматривается как семиотически неоднородный по языковой принадлежности его текстов. Наряду с моноязычными вербальными текстами в нем могут присутствовать поли- и кроссязычные тексты. Аналогично и геотексты в нем могут быть моногеоязычными, поли- и кроссгеоязычными.
В настоящее время отечественные исследовательские проекты по созданию геоинформационного портала находятся на начальных стадиях выполнения. С концептуальной точки зрения эти проекты могут быть разделены на два основных направления:
- разработка принципов интеграции геопространственной информации на растровой и/или векторной основе с присоединенными базами фактографических и метаданных, а также пространственно-определенной вербальной информации;
- разработка принципов и подходов к многоуровневому семантическому моделированию и интеграции геопространственной и пространственно-определенной вербальной информации с одновременным использованием электронных знаковых форм представления геотекстов, а также растровой и/или векторной форм их представления.
При размещении геоданных, представленных средствами разной геоязыковой принадлежности, особый интерес вызывает проблема группируемости данных в наборы, классы, категории, проекты и другие классификации, соответствующие однородности (достаточной близости) геоданных, дающей основание для помещения их в одну и ту же
Электронныйаа научныйа журналаа ИССЛЕДОВАНОаа Ваа РОССИИа 1985аа Что касается отношений, то помимо типичных (общих) для реляционной БД родовидовых отношений или отношений типа часть-целое необходимо позаботиться об отображении топологических (соединение, узел пересечения и др.) и пространственных (касание, внутри, снаружи и др.) отношений. Можно заметить, что в действительности пространственные отношения могут быть представлены в рамках реализации топологических отношений заданием соответствующей топологии.
Проблема группируемости данных в наборы (кластеризация, классификация) предполагает разработку соответствующих критериев и методов оценивания степени близости (сходства) помещаемых в набор геоданных. Выбор критериев и оценок в задаче группируемости данных является едва ли не решающим элементом эффективности этой процедуры. Далее в работе рассматривается использование функции сходства в рамках подхода концептуальной кластеризации.
2. Концептуальная кластеризация. Проблемная функция сходства
Методы кластерного анализа получили широкое распространение в различных исследованиях прикладного характера. Задача кластерного анализа в классической постановке выглядит следующим образом [5]: пусть m - целое число, меньшее п - общего числа индивидов п. Необходимо на основании данных, содержащихся в множестве X, разбить множество объектов U на z кластеров (подмножеств) pi, рг, рз,.--Рг так, чтобы каждый объект Uk принадлежал одному и только одному подмножеству разбиения и объекты, принадлежащие одному и тому же кластеру, были сходными, в то время как объекты, принадлежащие разным кластерам, были разнородными.
В качестве примера можно рассматривать п железнодорожных станций, каждая из
которых характеризуется занимаемой территорией (Xi), количеством путей (Хг),
количествома стрелока (Хз),а пропускнойа способностьюа (Х4) иа т.п.,а где
X1 =(х[,...,х1т)(вектор измерений) представляет собой набор указанных характеристик
Электронныйаа научныйа журналаа ИССЛЕДОВАНОаа Ваа РОССИИа 1986аа Решением задачи кластерного анализа обычно является разбиение, удовлетворяющее некоторому критерию оптимальности. Этот критерий может представлять собой некоторый функционал, который характеризует уровни желательности различных разбиений и группировок. Таким образом, для того чтобы решить задачу кластерного анализа, необходимо количественно определить понятия сходства и разнородности.
Неотрицательную вещественную функцию S(X', XJ) = Sy назовем функцией сходства, если :1) 0< Sy <1; 2) Su=1; 3) Syаа =Sji.
Введение формального определения сходства между объектами множества U соответствует заданию в нем некоторой топологии, тем самым пространство описаний превращается в топологическое пространство.
Обширный класс существующих алгоритмов основан на задании топологии меры сходства. При этом любая мера сходства представляет собой некоторую функцию, ставящую в соответствие каждой паре объектов ui и Uj число, характеризующее степень сходства между ними. Используемые на практике меры сходства отличаются значительным разнообразием свойств.
Можно выделить три типа мер сходств:
- коэффициенты подобия (квалифицированные коэффициенты связи);
- коэффициенты связи (корреляции);
- показатели расстояния в метрическом пространстве.
Наиболее распространенной математической основой для классификации объектов служит вычисление с помощью признаков парных функций в парах объектов. Коэффициенты типа расстояния, используемые для интервальных или порядковых шкальных признаков, имеют общий вид
где j и к- объекты; Хц - значение признака i для объекта j; п - общее число признаков; г - положительное целое число.
Обычно используются два частных случая. Первый из них - квартал, или Манхэттенское расстояние (г =1); второй - таксономическое расстояние (г =2).
Использование для классификации элементов множества функций расстояния - это один из простейших и наиболее эвристических подходов к решению проблем, связанных с
Электронныйаа научныйа журналаа ИССЛЕДОВАНОаа Ваа РОССИИа 1987аа Можно рассчитывать на получение удовлетворительных практических результатов при классификации объектов с помощью функций расстояния только в тех случаях, когда классы объектов обнаруживают тенденцию к проявлению кластеризационных свойств.
Классификация объектов с помощью функций расстояния - одна из первых идей автоматического распознавания образов. Этот простой метод классификации оказывается весьма эффективным инструментом при решении таких задач, в которых классы характеризуются степенью изменчивости, ограниченной в разумных пределах .
Наиболее интересными с точки зрения рассматриваемых в данной работе проблем
являются коэффициенты подобия. Как известно, любой вектор X1 =(х[,...,х1т) элементы
которого действительные целые числа - номера градаций соответствующих признаков, всегда можно записать в двоичном коде. Тогда без потери общности можно считать, что
любой объект Ui, принадлежащий U описывается вектором X1 = (х[,...,х1т), каждая из компонента которогоаа принимаета значенияаа 0аа илиаа 1,аа т.е.аа признакаа х1-аа булевый.аа Для
построения измерителей сходства Ui и Uj объектов введем следующие обозначения частот:
п(1,1) - число совпадающих двоичных признаков у обоих объектов;
п(0,0) - число совпадающих нулевых признаков у обоих объектов;
п(1,0), п(0,1) - число несовпадающих признаков, соответственно;
Рц - общее число совпадающих признаков;
Qij - общее число несовпадающих признаков;
m - общее число признаков, по которым идет сравнение.
Известен целый ряд различных измерителей подобия, выражаемых через эти величины:
Sij= Рц/т; ( 0< Sij <1 ) - равноважность нулевых и единичных признаков;
Sij= n(l,l)/ m - коэффициент Рао;
Sij= (Рц - Qij)/m - коэффициент Хаммана;
Sij = n(l,l)/(n(l,l) + Qij); ( 0< Sij <1 ) - коэффициент Джекарда;
Sij = 2n(l,l)/(2n(l,l) + Qij ); ( 0< Sy <1 ) - коэффициент Дейка (придает вдвое больший вес совпадающим признакам );
Sij = n(l,l)/(n(l,l) +2Qij); ( 0< Sij <1 ) - придает больший вес несовпадающим признакам;
Электронныйаа научныйа журналаа ИССЛЕДОВАНОаа Ваа РОССИИа 1988аа Эти показатели называются коэффициентами подобия. Сравнение показывает, что различные коэффициенты подобия, рассчитанные для одних и тех же объектов Ui и Uj, будут различны по величине. Выбор того или иного коэффициента определяется характером решаемой задачи (относительной важностью нулевых и единичных признаков, важностью поразрядного совпадения или несовпадения) и является во многом субъективным.
Независимо от выбранного способа определения подобия или сходства, задача кластеризации заключается в том, чтобы сгруппировать наблюдения или объекты по категориям или кластерам так, чтобы члены категории или кластера были схожи в некотором проблемно-ориентированном смысле, а члены разных категорий и кластеров -различны. В рамках искусственного интеллекта и машинного обучения задача кластеризации классифицируется как часть общей проблемы обучения на основе наблюдения и открытия.
Большая часть работы над задачей кластеризации включает численные и статистические методы кластеризации научных данных. Исследователи в области кластерного анализа и численной таксономии сосредоточили свои усилия на подборе подходящих метрик да измерения сходства между точками и кластерами, а также на разработке алгоритмов для минимизации межкластерного расстояния, измеренного в терминах некоторой целевой функции. В машинном обучении и организации знаний в базу знаний работу над задачей кластеризации целесообразно проводить, основываясь на понятии концептуальной кластеризации, введенном Michalski R.S. [5]. Методы концептуальной кластеризации обеспечивают не только "хорошую" классификацию на основе некоторой метрики, но и дают возможность найти осмысленное описание этой классификации.
В концептуальной кластеризации кластер описывается предложением на некотором языке, а не набором точек в кластере, - например, для мономиальной кластеризации [5] кластеры описываются мономами от п булевских характеристик.
В случае мономиальной кластеризации интерпретация 1Д монома (термин "моном" в значении "одночлен" выбран для сохранения смысловой связи с понятием
"мономиальная кластеризация") от переменныха х1 ,...,хпа есть стандартная логическая
интерпретация, т.е. множество булевых векторов длины п (от тех же переменных), которые удовлетворяют моному. Для мономиальной или конъюнктивной концептуальной кластеризации кластеризуемые объекты описываются с помощью п булевых
Электронныйаа научныйа журналаа ИССЛЕДОВАНОаа Ваа РОССИИа 198 9аа х1 ,...,хп. Тогда областью для задачи мономиальной кластеризации будет X={XN}, N>1.
Аналогично, многие другие области для задачи кластеризации наилучшим образом описываются в виде параметрического семейства X={Xn} множеств, где N некоторое подходящее число, как правило отражающее "размер" элемента. Например, если интересует кластеризация в евклидовом пространстве, то областью X может быть совокупность {En}, N>1, где En - N-мерное евклидово пространство.
Цель концептуальной кластеризации состоит в том, чтобы по данному конечному множеству элементов найти главную кластеризацию, покрывающую множество, такую, что каждый кластер этой кластеризации покрывает сходные элементы (то есть является плотным), а различные кластеры покрывают несходные элементы (то есть имеют большое расстояние). Определения плотности и расстояния должны зависеть только от кластеров, то есть от утверждений на языке описания кластера, а не точек, покрываемых этими кластерами - таким образом будет выполнено первейшее условие концептуальной кластеризации.
Специалисты по концептуальной кластеризации вместо общепринятой функции сходства F(ui, Uj) двух объектов Ui и Uj предлагают рассматривать концептуальную связность [5] (conceptualcohesiveness) F(ui, Uj, E, С), где E - влияние окружающих объектов среды), а С - набор понятий, применимых для описания как Ui так и Uj.
В значительной степени подход, предлагаемый в данной работе, моделирует концептуальную связность посредством сравнения структур связей объектов Ui и Uj со всеми остальными структурированными объектами множества. Этот подход позволяет учитывать свойства, которые характеризуют кластер как целое и которые невыводимы из свойств индивидуальных сущностей. Для того чтобы обнаруживать такие свойства система знаний должна быть снабжена способностью распознавать конфигурации объектов, которые соответствуют определенным концепциям. Процедура концептуальной кластеризации в системе знаний должна быть резидентной, так как любое поступающее знание вызывает адекватное мероприятие по реорганизации, а возможно и по реструктуризации системы знаний.
Качество кластеризации - это вещественное число, показывающее, в какой мере достигнуты как плотность кластеров, так и расстояние между ними.
Суть одного из наиболее распространенных алгоритмов кластеризации -аггломеративного алгоритма, заключается в следующем: дано множество элементов U, подлежащее кластеризации. Начинаем с формирования кластера для каждого элемента U,
Электронныйаа научныйа журналаа ИССЛЕДОВАНОаа Ваа РОССИИа 1990аа
Основное назначение функции сходства - поставить в соответствие каждой паре компонентов системы знаний числовую оценку, характеризующую близость этих компонентов по группе выбранных признаков. Можно говорить, что с определенной степенью точности эта функция моделирует семантическое сходство двух компонентов, если группа признаков в совокупности может быть интерпретирована как некоторое свойство или качество. В более общем случае следует рассматривать функцию F, которая позволяла бы получать оценку отношения R между каждой парой компонентов с точки зрения их близости в смысле некоторой проблемы или возможного (желательного) совместного участия в решении некоторой проблемы. Назовем такую функцию проблемной функцией сходства. Запишем эту функцию в виде F(ai#fi(pi, р2,.-Рт )) = R, где fi - важнейшие показатели близости или соучастия по группе существенных для заданной проблемы признаков, свойств, которыми обладают компоненты рассматриваемой системы, ai - важности или веса важнейших показателей, корректирующие их вклад в оценку отношения, рк - существенные для заданной проблемы признаки, свойства компонентов системы.
Несмотря на серьезные достижения исследователей в области кластерного анализа, разработанные алгоритмы оказываются слишком статичными для динамического формирования базы геоданных, которая по сути является базой знаний. В базе знаний связи между компонентами знаний носят многопрофильный, многозначный характер, поэтому ответственное устранение или добавление компонента знаний требует проверки всевозможных связей, в которых потенциально может участвовать удаляемое или приобретаемое знание. Такая проверка носит глобальный характер и, как правило, приводит к реорганизации структуры знаний. Поэтому, для поддержания базы геоданных (базы знаний) в состоянии адекватной динамической реорганизации была разработана
Электронныйаа научныйа журналаа ИССЛЕДОВАНОаа Ваа РОССИИа 19 91аа 3. Интерпретация сходства для анализа согласованности геоданных
Рассмотрим некоторую абстрактную совокупность геоданных как множество взаимосвязанных элементов, внутренняя структура которых не учитывается: интерес представляют только связи между парами геоданных, которые могут быть положительными, отрицательными или индифферентными. При этом весьма важным является вопрос, связанный с алгоритмами и методами определения взаимосвязей между п объектами, которые, как было указано выше, необходимо распределить по N классам так, чтобы в каждом классе оказались объекты, наиболее сходные друг с другом по совокупности m выбранных признаков. Таким образом, рассмотривается случай, когда геоданные заданной совокупности имеют формализованную структуру, т.е. могут быть описаны некоторым конечным набором параметров (реквизитов), то есть имеется совокупность однородных геоданных любой природы О = {Oi}, (i = 1, ... , п), где однородность понимается в смысле описания каждого объекта из рассматриваемой совокупности в виде одинакового упорядоченного набора (вектора) из m
характеристик - реквизитов: oi= (р[ ,...,р1т).
При информационном моделировании, говоря о сравнении любых двух объектов из этой совокупности, понимают оценку их сходства на основе интегрированного сходства соответствующих характеристик этих двух объектов [6]. При этом, в зависимости от характера и условий решаемой задачи, в сравнении могут участвовать либо все m реквизитов, либо некоторое их подмножество из k < m элементов. Естественно, что сами реквизиты могут иметь различную природу и тип, главное, что для каждого pi имеется некоторая функция, позволяющая дать численную оценку для каждой пары характеристик из этой группы. В реальных приложениях не все объекты из рассматриваемой совокупности могут обладать полным набором признаков: для некоторых из них значения отдельных признаков могут быть неизвестными или неприменимыми. В таких ситуациях однородность всей совокупности объектов может быть восстановлена, если присвоить отсутствующимаа признакамаа нулевыеаа значения,аа восстановив,аа такимаа образом,аа вектор
Электронныйаа научныйа журналаа ИССЛЕДОВАНОаа Ваа РОССИИа 19 92аа Построение функции сходства - задача, весьма тесно связанная с построением модели предметной области и определяется, вообще говоря, не только фактическим содержанием рассматриваемой предметной области, совокупности объектов и связей между ними, но и характером решаемой задачи. Можно говорить, что функция сходства является важной составляющей модели предметной области, определяющей единство этой модели при изменении значений данных.
Основное назначение функции сходства - определять меру близости объектов рассматриваемой совокупности между собой и тем самым проводить кластеризацию этой совокупности на некоторое количество классов. Поскольку функция сходства задается на пространстве признаков, описывающих объекты предметной области, то такое преобразование многомерных данных в данные близости является промежуточным шагом кластеризации. Поскольку в данной работе алгоритм кластеризации основан на преобразованиях матрицы связности, которая имеет знаковую структуру, то основной проблемой является построение функции сходства и выбор пороговых значений аир, определяющих знак связи.
Может использоваться множество различных типов таких преобразований, включая вычисление евклидовых расстояний между строками многомерной матрицы, вычисление корреляций или ковариаций между столбцами матрицы, вычисление меры пересечения, а также много других видов коэффициентов.
Один из подходов к количественному определению оценки схожести заключается в попытке найти основу для суждений о сходстве. Это обычно достигается с помощью детального описания свойств, на основе которых можно выразить сходство. Такой подход приводит к детализации и дроблению дескрипторов объектов, которые необходимо классифицировать. Каждому объекту приписываются длинные списки дескрипторов, т.е. векторы значений признаков, а классификация проводится по матрице данных, скомпанованной из набора таких векторов. Сам же набор основных признаков объектов определяется областью применения. Объекты, подлежащие классификации, представлены в пространстве, измерениями которого являются признаки. Это признаковое пространство является формально n-мерным, но в связи с корреляцией между признаками оно обычно может быть преобразовано в пространство меньшей размерности с небольшой потерей информации. Кроме того, для решения специальных задач там, где интересуют только некоторые свойства объектов, или там, где классификация должна служить нуждам некоторых специальных практических приложений, могут использоваться только несколько признаков вместо многих или в общем случае разным признакам
Электронныйаа научныйа журналаа ИССЛЕДОВАНОаа Ваа РОССИИа 19 93аа Введем F - функцию сходства объектов по совокупности к выбранных признаков, нормированную на максимальный диапазон значения признака на множестве из п объектов [6]. Для двух объектов OiH Oj, сходство которых устанавливается с точностью до к признаков {pi}mk функция может быть записана как:
F(oi,Oj)= \--Twm\р^,Р^\ к i=1max | p'ml- pJml|
Здесь 0 < wml < 1 - вес ml-того признака. Введенная таким образом функция соответствует введенному выше коэффициенту подобия Хаммана.
При таком определении функции F она принимает значения из отрезка [0,1], причем единица означает "полное сходство" элементов Oi и Oj, а ноль - их "полное различие" (отсутствие сходства).
Промежуточные значения могут быть интерпретированы как интегральная степень сходства двух геоданных по к выбранным признакам, что дает нам возможность рассматривать это множество в качестве полного неориентированного графа с нагруженными нормированными связями. Если на основе значений F(Oi, Oj) = fy устанавливать знак связи, то он уже будет интерпретироваться как результат объективной оценки сходства объектов, а не как субъективная оценка эксперта.
Одной из важных задач формирования структуры знаковых связей для последующего распределения п объектов по N классам на основании этой структуры является выбор порогового значения а функции F, до которого (т.е. когда 0 < F(Oi, Oj) < а) объекты Oi и Oj считаются несходными по к признакам и после которого (а < F(Oi, Oj)< 1) - сходными. Если присвоить знак "минус" всем связям с 0 < F(oi, Oj)< а и знак "плюс" -в противном случае, то получится структура множества со знаковыми связями, описанная в литературе как знаковый граф.
Более общий случай возникает, если задать два пороговых значения а и р и присваивать знак "минус", если 0 < F(Oi, Oj)< а, значение 0, если а < F(Oi, Oj)< Р, и знак "плюс", если и р < F(Oi, Oj) < 1. Этим вводится так называемый диапазон индифферентности (а, Р), значение связи внутри которого говорит об индифферентности к сходству по к выбранным признакам. При равенстве а = Р мы возвращаемся к предыдущему случаю.
Изменение значений пороговых величин может приводить к соответствующим изменениям и в определении сходства между парами объектов, а, следовательно, - и в структуре знаковой матрицы связности.
Нечувствительность структуры по нижнему пороговому значению а и по верхнему
Электронный аанаучныйа журналаа ИССЛЕДОВАНОаа Ваа РОССИИа 1994аа Структура со знаковыми связями является согласованной, если в ней нет ни одной несогласованной структурной компоненты по выбранному структурному признаку. В частности, структура, согласованная по тернарному критерию Хайдера [6], не содержит ни одного диссонансного треугольника (в котором число отрицательных связей нечетно) и представляет собой два подмножества (одно из них может быть пусто), внутри каждого из которых объекты связаны только неотрицательными связями, а между объектами из разных подмножеств - связи только неположительные. Поликонсонанс степени N в отличие от консонанса Хайдера допускает существование N таких подмножеств.
Можно заметить, что изменяя а и р до некоторых критических значений oik и Рк, любую несогласованную структуру можно привести в согласованное состояние. Действительно, в предельном варианте, когда а = 0 и р = 1, любая структура индифферентно согласована, так как все объекты попарно сходны.
Устойчивость знаковой структуры по а и р определяется как сохранение согласованного состояния при варьировании а и р в некотором диапазоне 0 < а < а* и Р* < Р < 1. Если а = Р, то знаковая структура устойчива только в рамках нечувствительности по а и р. Нетрудно заметить, что чем меньше диапазон (а, Р), тем существенней знак связи и менее устойчива знаковая структура.
Полученные значения F(Oi, Oj) являются нечеткой характеристикой взаимосвязи соответствующих двух объектов, что позволяет определить согласованность на такой совокупности другим способом. К сожалению, пока не удалось воспользоваться преимуществами подхода с позиций нечеткой логики для анализа структур со взвешенными связями, так как вместо комбинаторного характера, который имеют задачи на знаковой структуре, здесь приходится сталкиваться с проблемой индивидуального
учета значения каждой изаа п^п ~ 'аа связи. Более того, имеющийся в настоящее время
2
конструктивный анализ с позиций нечеткой логики, так или иначе, использует механизм порогов.
Оценивая предложенное сведение множества объектов, обладающих набором характеристик, к системе объектов со знаковыми связями, нельзя отрицать значительное огрубление семантики взаимоотношений этих объектов. Однако следует заметить, что это в определенном смысле один из способов сведения семантической согласованности к структурной. На проведение такой операции без существенного огрубления, конечно же,
Электронныйаа научныйа журналаа ИССЛЕДОВАНОаа Ваа РОССИИа 19 95аа Несмотря на то, что в задачу данной работы не входит изучение рассогласованности множеств, которая подробно изучена в других работах [6,7], воспользуемся пока интуитивным представлением о проблеме структурной согласованности и рассмотрим способ вычисления силы связи и установления знака связи посредством задания пороговых значений.
Безусловно, предлагаемая функция сходства - не единственный способ определения близости объектов по ряду выбранных свойств. В данном случае она важна как пример возможности такого определения. Как уже было сказано выше, выбор порогов сходства аир весьма существенно влияет на состояние согласованности множества. Поэтому вопрос выбора аир является важным и достаточно сложным. Этот вопрос должен решаться с учетом семантики предметной области, которой принадлежат объекты и характера решаемой задачи. Попробуем, тем не менее, высказать некоторые общие соображения, основываясь исключительно на структурных особенностях согласованных множеств.
После вычисления F(oi, Oj) = fyа для всех пар объектов имеетсяаа п'паа ЧLчисел fy.
2
Предположим, необходимо привести заданное множество объектов к консонансу степени N, т.е. к согласованной структуре из N непересекающихся групп [6]. Будем исходить из предположения, что исходная структура достаточно близка к консонансу. Тогда по крайней мере выбор аир должен примерно соответствовать пропорции положительных и отрицательных связей при консонансе (предположим, что индифферентные связи пока отсутствуют), иначе неудачным выбором а и р может быть лиспорчена почти консонансная структура. Пусть в i-той группе содержится Zi объектов, тогда общее количество положительных связей в N группах равноа $+ =}_гу гг -я) При условии
У Zаа = п получаем maxS+ = п^п ~ 1 ^а при N=1 и minS+ =аа и(и ~ N)при Zi = JLдля
tiа '22NN
любого i. Как видно, maxS+ и minS+ сильно различаются. Нужно еще какое-то условие. В частности,аа еслиаа дополнительноаа существуетаа условиеаа равномощностиаа Nаа групп,аа то
соотношение отрицательных связей $ =Ч (1-Ч) и положительных s+=аа будет
2а N2N
SIS+ N. Значит, при выборе порогов а и р в этом случае следует задать а так, чтобы количество отрицательных связей было примерно в N раз больше.
jд
Е- |
Рассмотрим функцию у=а Vv(/i), где v (fy) - количество связей со значением fy.
Электронныйаа научныйа журналаа ИССЛЕДОВАНОаа Ваа РОССИИа 1996аа Найдем f*ij, при которома 7( г \ = Чп------- >. Зададим некий диапазон устойчивости 5 и
11 2 N
выберем а = f*y - 5 , a Р = f*y + 5, давая возможность образоваться индифферентным связям, а вместе с ними и устойчивости структуры.
Для такого приближенного задания а и р на основе значения согласованной структуры недостаточно одного только количества групп. Необходимо знать хотя бы соотношение объектов в группах.
При устранении рассогласованности выявляются связи, знаки которых следует изменить на противоположные (или заменить на 0). Замена знака связи на 0 является изменением соответствующего значения fy так, чтобы новое значение попало в интервал (а, Р), а изменение знака на противоположный - это "переброс" значения связи fy через этот интервал. Суммарное отклонение измененных значений связей от первоначальных и есть те суммарные затраты на согласование структуры, которые следует минимизировать.
В заключение приведем инвертированную относительно начальной постановку задачи, которая может оказаться полезной в некоторых приложениях. Среди имеющихся m признаков выбрать к признаков таких, чтобы разбиение п объектов на N классов на основе сходства по этим признакам требовало наименьших затрат в смысле суммарного изменения значений функций сходства. Еще более сложная модификация этой задачи возникает, когда требуется найти максимальное количество признаков, за счет сходства по которым удается добиться требуемого уровня согласованности системы.
4. Заключение
В работах [6,7] был предложен механизм по обеспечению согласованности динамически формируемой базы геоданных, основанный на анализе структурных взаимосвязей между ее отдельными компонентами и последующей ее реструктуризации с целью уменьшения существующей рассогласованности. При этом основной критерий структурной согласованности определялся на основе понятия поликонсонанса степени N [6], то есть возможности приведения множества к структуре, состоящей не более, чем из N кластеров.
Проведенные исследования показали, что наиболее существенным фактором, влияющим на функционирование алгоритмов поддержки согласованности геоданных, является функция сходства, на основе которой определяются взаимосвязи между различными геоинформационными объектами из заданной совокупности. В представленной работе в качестве примера для обсуждения проблемы выбора приведен толькоаа одинаа вариантаа используемойаа функцииаа сходства.аа Ваа действительности,аа для
Электронныйаа научныйа журналаа ИССЛЕДОВАНОаа Ваа РОССИИа 19 97аа итература
- Зейлер М. Моделирование нашего мира (руководство ESRI по проектированию базы геоданных). California: ESRI Press, 1999. - 254 с.
- Дулин С.К., Розенберг И.Н. Согласованное пополнение геоинформационного портала отрасли неструктурированными данными// Системы и средства информатики. ИЛИ РАН. - М.: Наука, 2005. - С. 193-217.
- Зацман И.М., Лютый А.А. Семиосфера электронного образа Земли и знаковое представление геотекстов //Системы и средства информатики.- М.: Наука, 2001.-Вып. 11. - С. 132-148.
- ютый А.А. Язык карты: сущность, система, функции.- М.: ГЕОС, 2002. - 327 с.
- Michalski R.S., Stepp R.E. Conceptual clastering: inventing goal-oriented>
- Дулин С.К. Введение в теорию структурной согласованности. - М.: ВЦ РАН, 2005. -135 с.
- Дулин С.К., Розенберг И.Н. Об одном подходе к структурной согласованности геоданных // Мир транспорта. 2005.
Все научные статьи