4.3. Основные определения

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

Определение 4.2. Матрица сходства S имеет точную структуру дерева, если всякий раз, когда узел, в котором объединяются впервые, находится левее узла, в котором объединяются

Если более сходны друг с другом, чем , то естественно, что объединяется в узел (кластер) раньше, чем или, что то же, если наименьший кластер, содержащий содержит также ХР и

Определение дерева по Джонсону [186 (параграф 2.1)] включает ультраметрическое неравенство и удовлетворяет понятию точной структуры дерева. Это же относится и к Джардайну и Сибссщу [179].

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

Определение 4.3. Расстояние между двумя матрицами сходства определим Как

где - весовая функция сходства .

Определение 4.4. Расстоянием между матрицей сходства S и деревом называется

где S — любая матрица сходства с точной структурой дерева .

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