§7. Сравнение методов

Всякий необходимо причиняет пользу, употреблённый на своём месте. Напротив того: упражнения лучшего танцмейстера в химии неуместны; советы опытного астронома в танцах глупы.

— Козьма Прутков

Определяющее значение при выборе метода классификации имеет общее число объектов $n$. Если оно велико (сотни или тысячи), то необходимо применять:

• эвристический алгоритм A4 («Форель»), скомбинированный с A2 (кратчайший незамкнутый путь) — §2;
• или быстрые иерархические процедуры для редуктивных мер отдалённости — §4.

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

Для $n \le 200$ у Лагутина приводятся результаты экспериментального сравнения нескольких методов классификации (в частности, A3 из §2 и P1–P5 из §3) путём их применения к моделированным совокупностям объектов.

Объекты генерировались как точки в $m$-мерном единичном гиперкубе ($3 \le m \le 7$). Задавалось число классов $k$ ($3 \le k \le 7$), и наудачу в гиперкубе выбирались центры классов $\boldsymbol y_l$ ($l = 1, \dots, k$). Для каждого класса с помощью датчика случайных чисел моделировались $m$ длин сторон гиперпараллелепипеда с центром в $\boldsymbol y_l$, в который затем случайно бросались $n_l$ точек ($30 \le n_l \le 50$). При фиксированных $m$ и $k$ каждое разбиение генерировалось 50 раз, и показатели усреднялись (всего было обработано около 2000 выборок).

Кроме того, генерировались «шумящие» объекты, равномерно распределённые в гиперкубе. Их количество составляло заданный процент $p$ от $n$ ($10\,\% \le p \le 30\,\%$). Эти объекты предназначались только для того, чтобы «сбивать с толку» алгоритмы классификации, но, естественно, не участвовали в расчёте показателей качества классификации. Одним из таких показателей было расстояние Хемминга (метрика D1 из §1) между моделированным разбиением и разбиением, которое построил алгоритм.

Изложим кратко основные выводы.

• Наилучшей (почти идеальной) по восстанавливаемости разбиения проявила себя иерархическая процедура P5 («метод Уорда»).
• Следом за ней идут процедура P2 («дальнего соседа») и алгоритм A3 (метод k-средних Болла и Д. Холла). Случайный выбор эталонов в алгоритме A3 показал себя как крайне неудачный.
• Самой плохой оказалась процедура P1 («ближнего соседа»).
• По уровню устойчивости к шуму лидерами стали алгоритмы A3 и P5. Замыкает список снова P1.

Не следует воспринимать эти результаты как приговор методу «ближнего соседа», а также близким к нему «по духу» (имеющим цепочечный эффект) алгоритмам A1 («связные компоненты») и A2 («кратчайший незамкнутый путь») из §2. Речь может идти лишь о том, что на первичном этапе классификации, не обладая информацией о структуре классов, лучше применять менее чувствительные методы.

В случае, когда классы имеют сложную форму, скажем, относятся к типу C3 из §1 («класс типа ленты или слабое сгущение»), именно алгоритмы P1, A1 и A2 позволяют правильно произвести разбиение.

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

Наш мини-эксперимент

Мы повторили схему книги в уменьшенном масштабе, на TS-библиотеке этой главы:

• $m$ от 3 до 7, $k$ от 3 до 5;
• стороны параллелепипедов от 0,1 до 0,3, $n_l$ от 15 до 25;
• по 100 выборок на каждый уровень шума;
• число классов $k$ алгоритмам сообщалось, иерархические дендрограммы разрезались на $k$ классов;
• показатель — доля пар объектов (без шумящих), разбитых не так, как при моделировании.

Выводы книги подтверждаются:

• Уорд — лучший, особенно с шумом.
• Ближний сосед с шумом проваливается полностью. Шумящие точки становятся одиночными «классами», и разрез на $k$ классов отдаёт их под класс, а настоящие облака склеивает.
• Случайные эталоны у k-средних плохи на чистых данных: даже без шума ошибка около 10 %.

Есть и любопытная деталь, которой в книге нет. С шумом самые удалённые эталоны становятся хуже случайных: самыми удалёнными объектами оказываются как раз шумящие точки в углах гиперкуба. Рецепт из §2 хорош для чистых данных.

Включи 20 % шума и сравни: «Эталоны: самые удалённые» против «случайных», затем переключись на A2 и A1. Цепочечные методы на шуме теряются первыми.

Сравнение Миллигана и Купера

Г. Миллиган и М. Купер в 1985 г. опубликовали результаты экспериментального сравнения в похожих условиях тридцати методов классификации. В их число вошли алгоритмы минимизации функционалов (см. §5)

(Калинский и Харабаш, 1974) и инвариантного функционала $F7 = \det\boldsymbol W_{int}/\det\boldsymbol W_{tot}$ (Фридман и Рубин, 1967). Первый оказался самым лучшим, а второй — в группе самых плохих. Дело, скорее всего, в удачной нормировке матриц рассеяния у $F4$ (сравните с формулой (9) главы 16).

Смысл по-пацански: красивая инвариантность $F7$ на практике не спасает. Простой «дисперсионный» $F4$, отношение разброса внутри к разбросу между с честными степенями свободы, работает лучше.

Проверь себя