Основные цели при решении задач таксономии

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

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

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

1. характеристика одного наиболее типичного представителя класса (прецедента);

2. максимальное отклонение значений каждого признака от значения этого признака у прецедента;

3. список объектов, принадлежащих этому классу.

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

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

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

Вариационные (основаны на оптимизации того или иного показателя качества выражений кластерной структуры);

Агломеративные (на последовательном объединении пар наиболее близких кластеров);

 

Иногда при формулировке задачи таксономии, в дополнение к множествам O и P, могут быть заданы дополнительные априорные данные о характеристиках множества С. Таким образом, исходя из состава входных данных можно выделить четыре основных типа задач таксономии:

1. Кроме множеств О и P задано необходимое количество классов m.

2. Кроме множеств О и P заданы ограничения на число объектов в классах.

3. Кроме множеств О и P заданы ограничения на пространственные характеристики классов.

4. Заданы множества О и P, и ничего не известно о множестве С.

Большинство известных методов ИАД, направленных на решение задачи таксономии, способны решать задачи 1 – 3. К этим методам относятся:

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

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

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

 

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

 

Гипотеза компактности

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

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

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

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

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

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

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

Мера компактности может быть любой:

- она может характеризоваться средним расстоянием от центра тяжести до всех точек образа;

- средней длиной ребра полного графа или ребра кратчайшего незамкнутого пути, соединяющего точки одного образа;

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

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

Гипотеза λ-компактности

Гипотеза компактности оперирует абсолютными значениями расстояний между векторами в пространстве характеристик. Однако на некоторых примерах можно показать, что важную роль в задачах анализа данных играют не только сами расстояния, но и отношения между ними. Так, расстояние между точками 5 и 6 на рис. 2, а меньше, чем между 6 и 7, но, делая «вручную» таксономию этого множества точек на два таксона, эксперты обычно проводят границу по ребру 5-6. Глаз человека улавливает на этой границе нарушение однородности расстояний между соседними точками и придает этому факту большее значение, чем абсолютной величине расстояний.

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

Формулировка гипотезы λ -компактности опирается на понятие λ -расстояния, которое учитывает нормированное расстояние d между элементами множества и характеристику τ локальной плотности множества в окрестностях этих элементов.

Нормированное расстояние:

где δ - расстояние между двумя любыми точками a и b графа, равное длине ребра, которое соединяет эти точки в полном графе,

D - диаметр графа, самое длинное в графе ребро.

Нормированная характеристика локальной неоднородности

βmin - самое короткое ребро из смежных ребру (a, b)

λ- расстояние

 

Тема 11-12 Оценка сложных объектов, выбор, классификация (распознавание образов), формирование заключения.