11.4.2. Иерархическая классификация.

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

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

Рассмотрим дерево классификации для объектов. Оно состоит из начальной вершины, конечных вершин и

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

Рис. 11.9. Дерево классификация.

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

1. Все конечные вершины имеют нулевой уровень.

2. Уровни всех не конечных вершин больше нуля.

3. Уровень вершины всегда меньше, чем уровень предшествующей ей вершины.

В частности, если условия 1, 2 и 3 выполнены, то

и выполняется ультраметрическое неравенство

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

выражением

где — весовые коэффициенты. Этот критерий почти совпадает с критерием (11.03). Переменная используемая для обозначения дерева, играет ту же роль, что и Заметим, что каждое дерево характеризуется не только структурой, но также уровнями, которые приписаны вершинам.

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

Для нахождения оптимального в смысле дерева часто используют следующий алгоритм [Джонсон, 1907; Ролф, 1970]. Прежде всего необходимо каким-либо способом ввести расстояние между двумя множествами векторов. Например, в качестве такого можно использовать расстояние между двумя средними векторами. После того как это сделано, можно применить следующую итеративную процедуру:

Шаг 1. Отнести каждый объект к конечной вершине уровня «0» и вычислить расстояние между каждой парой объектов.

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

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

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

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