Файл: Ципилева Т.А_Геоинформационные системы_Учебное пособие_Томск_ТМЦДО_2004.pdf

44

Рассмотрим два простейших алгоритма АК, известных как эвристические алгоритмы. Отличительной чертой этих алгоритмов является то, что они выделяют таксоны простой гиперсферической формы. Базовым алгоритмом является алгоритм ФОРЕЛЬ (от первых букв ФОРмальный АЛгоритм).

2.2.2 Эвристический алгоритм «Форель»

Алгоритм ФОРЕЛЬ работает с ТОС, элементами которой являются только количественные данные. Объекты, включенные в один класс, попадают в гиперсферу с центром С и радиусом R . Изменяя радиус, можно получить разное количество классов К. При фиксированном заданном радиусе R алгоритм ФОРЕЛЬ работает следующим образом.

1.Центр C(1) некоторой гиперсферы с радиусом R помещается в любую из точек исходного множества объектов.

2.Определяются точки, оказавшиеся внутри этой гиперсфе-

ры. Для этого вычисляется расстояние ρ от точки C(1) до всех М точек и те из них, для которых ρ ≤ R , считаются «внутренними».

3.Для внутренних точек вычисляется центр тяжести (точка

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

4.Центр сферы перемещается в вычисленный центр тяже-

сти C(2) .

5.Для нового центра сферы вновь находятся внутренние точки и их центр тяжести.

6.Процедура перемещения гиперсферы повторяется до тех пор, пока не перестанут изменяться координаты центра тяжести

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

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

45

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

Очевидно, что количество классов K тем больше, чем меньше радиус R . Желательное количество классов может быть подобрано соответствующим подбором R . Для этого рекомендуется последовательно уменьшать радиус от R = Rmax , при котором

все точки объединяются в один класс, до тех пор, пока K не будет равен заданному (или наиболее близкому к заданному) числу классов.

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

K mi ρ ( ( ))

F = ∑∑ 2a xa ;C t , t=1 a=1

объектов в классе (мощность класса) Sl . Лучшему варианту

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

2.2.3 Вариационный алгоритм «Краб»

Семейство алгоритмов КРАБ (КРАтчайший Путь) основано на формировании незамкнутого связного графа и проведении разбиения множества исходных объектов с его помощью. Эти алгоритмы позволяют строить классы произвольной формы и

46

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

Естественно, человек стремится использовать некоторую форму близости (ρ) точек и считает, что классификация тем

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

больше устраивает, когда распределение точек по классам приблизительно равномерно (h). Чем больше отличие в мощности

классов, тем хуже классификация. Психологические эксперименты показали, что человек не всегда объединяет точки в один класс по принципу «ближний к ближнему». Так, для рисунка 2.2 пятая по счету точка ближе к четвертой, но человек проведет границу классов между четвертой и пятой точками. Он обращает внимание на изменения плотности точек (λ). Если подобрать

подходящие меры для (ρ), (d ), (h) и (λ), то можно добиться совпадения результатов автоматической и ручной группировки.

Рисунок 2.2 – Пример выделения человеком двух классов

Для подбора (ρ), (d ), (h) и (λ) используют свойства крат-

чайшего незамкнутого пути (КНП) – связный граф без петель, соединяющий все точки и имеющий минимальную длину ребер

(рис. 2.3) .

47

Рисунок 2.3 − Кратчайший незамкнутый путь, соединяющий шесть точек

Если разрезать одно ребро (рис. 2.4), то получится два класса, если разрезать (К–1) ребро КНП, мы получим К классов точек.

1. Мерой близости объектов внутри классов считают среднюю длину ребер КНП, соединяющего все точки одного класса:

классами также считают по КНП

как среднюю длину ребер, со- Рисунок 2.4 – К определению d единяющих классы:

3. Через КНП можно определить и меру локальной неоднородности расстояний между точками (λ). Для этого обозначим

48

длину некоторого ребра ai , а длину наименьшего примыкающе-

го к нему ребра через βmin . Тогда λi = βmin / ai . Чем меньше

величина λi = βmin / ai , тем больше отличие в длинах соседних ребер, тем с большим основанием можно считать, что по ребру

ai пройдет граница.

βmin α

Рисунок 2.5 − Определение меры локальной неоднородности

Общая мера неоднородности определяется по формуле:

1K −1

λ= K −1 ∑i=1 λi .

4.Равномерность распределения точек по классам может

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

h = K K ∏K mi .

i=1 M

Общий критерий качества в алгоритме КРАБ сформулирован так:

F = ln λd ××ρh .

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

Выделяемые классы могут иметь любую форму. Алгоритм КРАБ:

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

50

2.3 Базовые модели данных в ГИС

2.3.1 Инфологическая модель

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

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

кие понятия, как тип сущности и экземпляр сущности. Понятие

«тип сущности» относится к набору однородных личностей, предметов, событий или идей, выступающих как целое. «Экземпляр сущности» относится к конкретной вещи в наборе. Например, типом сущности может быть ГОРОД, а экземпляром – Москва, Киев и т.д.

Объекты могут быть атомарными и составными. Атомарный объект – это объект некоторого типа, разло-

жение которого на более мелкие объекты внутри этого типа невозможно, например, в группе людей атомарным объектом будет один человек, дробление которого на более мелкие составные части переведет его в тип – части тела человека.

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

Объекты характеризуются свойствами (атрибутами) и взаимосвязью с другими объектами.

Атрибут – поименованная характеристика сущности. Его наименование должно быть уникальным для конкретного типа сущности, но может быть одинаковым для различного типа сущностей (например, атрибут «цвет» может быть определен

51

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

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

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

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

Цель инфологического проектирования – формализация объектов реального мира и методов обработки информации в соответствии с поставленными задачами обработки и выдачи информации.

Инфологическая модель носит описательный характер и включает в себя ряд компонентов (рис. 2.6):

1)описание предметной области;

2)описание методов обработки;

3)описание информационных потребностей пользователей.