§4. Быстрые алгоритмы

В 1978 г. М. Брюиношем было введено важное понятие редуктивности (сводимости) мер отдалённости. Оно заключается в том, что для произвольного $\delta > 0$ условия $\rho(S_1, S_2) \le \delta$ и $\rho(S_0, S_1 \cup S_2) < \delta$ влекут выполнение хотя бы одного из неравенств $\rho(S_0, S_1) < \delta$ или $\rho(S_0, S_2) < \delta$.

Иными словами, $\delta$-окрестность множества, полученного объединением двух $\delta$-близких классов, включена в объединение $\delta$-окрестностей этих двух классов.

Можно дать другую формулировку свойства редуктивности: если $\rho(S_1, S_2) \le \delta$, а $\rho(S_0, S_1) \ge \delta$ и $\rho(S_0, S_2) \ge \delta$, то $\rho(S_0, S_1 \cup S_2) \ge \delta$. Обладают ли этим свойством $\rho_{\min}$ и $\rho_W$ — вопрос 5.

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

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

Схема с порогом δ

При $k$-м шаге иерархической процедуры приходится искать минимальный элемент в матрице мер отдалённостей классов, то есть минимум из $N_k = (n - k + 1)(n - k)/2$ чисел. Ясно, что минимальный элемент находится среди элементов, не превосходящих некоторый порог $\delta$. При соответствующем выборе $\delta$ массив таких элементов имеет размер намного меньший, чем $N_k$. В этом и состоит основная причина большой скорости работы алгоритмов и экономии компьютерной памяти.

Обозначим через $U_\delta$ множество пар $(i, j)$ номеров классов таких, что $\rho_{ij} \le \delta$, а через $V_\delta$ — массив из номеров классов, присутствующих в $U_\delta$.

1. На первом этапе попарно объединяются классы из $V_\delta$, пока текущее $U_\delta$ не станет пустым.
2. Затем берётся новое значение порога $\delta' > \delta$, и формируются множества $U_{\delta'}$ и $V_{\delta'}$.
3. И так далее, до полного слияния всех объектов в один класс.

Пример: пять точек, метрика города

Рассмотрим работу алгоритма на данных рис. 15 у Лагутина — пять точек на целочисленной решётке: $1 = (1, 1)$, $2 = (1, 2)$, $3 = (3, 3)$, $4 = (7, 2)$, $5 = (7, 4)$. В качестве расстояния используем метрику города D1, мерой отдалённости классов будем считать $\rho_{\min}$.

Матрица расстояний:

Ход алгоритма:

1. Зададим $\delta = 3$. Тогда $U_\delta = \{(1,2), (2,3), (4,5)\}$ и $V_\delta = \{1, 2, 3, 4, 5\}$.
2. Объединяем наиболее близкие объекты 1 и 2 в новый класс под номером 6. Матрица межклассовых мер для классов 3, 4, 5, 6: $\rho(3,6) = \min(4, 3) = 3$, $\rho(4,6) = 6$, $\rho(5,6) = 8$, остальные прежние.
3. При этом изменятся $U_\delta$ и $V_\delta$: $U_\delta = \{(3,6), (4,5)\}$, $V_\delta = \{3, 4, 5, 6\}$, и т. д.
4. Объединяются 4 и 5 (уровень 2) в класс 7, затем 3 и 6 (уровень 3) в класс 8.
5. После этого уже нет пар классов, для которых $\rho_{\min} \le 3$: осталось $\rho(7, 8) = 5$. Поэтому приходится увеличить порог до $\delta' = 5$, что и позволяет завершить процедуру.

При выполнении свойства редуктивности алгоритм строит точно такую же дендрограмму, что и обычная иерархическая процедура. Для присоединения класса 3 к классам 1, 2 достаточно просмотреть окрестности 1 и 2, а не проверять связь 1–4.

Выбери «40 случайных точек» и поиграй с методами. Для ближнего и дальнего соседа, средней связи и Уорда дендрограмма совпадает с обычной, а в памяти держится лишь малая доля из $N_1 = n(n - 1)/2$ пар. Метод центров масс не редуктивен, и для него совпадение не гарантировано.

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

Как выбирать пороги

Эффективность алгоритма существенно зависит от выбора последовательности порогов $\delta < \delta' < \delta'' < \dots$:

• если $\delta$ слишком велико, то $U_\delta$ включает почти все пары классов, и мы практически возвращаемся к традиционной иерархической процедуре;
• если же величина порога слишком мала, то придётся часто формировать множества $U_\delta$ и $V_\delta$.

Обычно используют следующие два способа выбора порогов.

Первый способ (на основе гистограммы $\rho_{ij}$). Порог $\delta$ находится из условия достаточности выделенной компьютерной памяти для хранения всех $\rho_{ij} \le \delta$.

Пусть, например, число объектов равно 100. Тогда на первом шаге имеется $N_1 = 100\cdot99/2 = 4950$ пар классов. При этом задано, что их количество в памяти не должно превышать 200. Предположим, что первые четыре интервала гистограммы содержат 180 пар, а пятый — ещё 40 пар. В таком случае можно поместить в память только 180 пар, причём порог $\delta$ будет равен наибольшему значению $\rho_{ij}$ этих пар.

Смысл по-пацански: не держи в голове весь телефонный справочник района — держи только соседей по подъезду. Порог $\delta$ — это и есть «подъезд»: 180 номеров вместо 4950, а позвонить всё равно придётся только ближайшему.

Второй способ («изменяющееся среднее»). Вычисляется среднее арифметическое всех $\rho_{ij}$; пусть это будет $\delta_1$. Если возможно размещение в памяти всех $\rho_{ij} \le \delta_1$, то полагается $\delta = \delta_1$. Иначе удаляются пары, у которых $\rho_{ij} > \delta_1$, а для оставшихся снова подсчитывается среднее арифметическое $\delta_2$ и т. д. — до тех пор, пока все $\rho_{ij} \le \delta_k$ не уместятся в заданной компьютерной памяти.

Замечание 4. Е. Диде и В. Моро (1984 г.) показали, что если слегка ужесточить условия теоремы 1 из §3, заменив неравенство в) на неравенство

$$\text{в}')\quad C_1 + C_2 + \min\{0, C_3\} \ge 1,$$

то меры отдалённости, удовлетворяющие (5), будут редуктивными.

По кирпичикам — проверим на таблице из §3:

• ближний и дальний сосед, средняя связь: $C_3 = 0$ и $C_1 + C_2 = 1$ — условие выполнено;
• Уорд: $C_1 + C_2 + C_3 = \frac{(n_0 + n_1) + (n_0 + n_2) - n_0}{n_0 + n_1 + n_2} = 1$ — выполнено;
• центры масс: $C_1 + C_2 = 1$, но $C_3 < 0$, и сумма меньше 1 — условие нарушено.

Проверь себя