Глава 19. Классификация

Навостри ум свой математикой… но остерегайся только классификации букашек…

— Г. К. Лихтенберг (эпиграф к главе у Лагутина, сокращённо)

Этой главой открывается часть V — анализ многомерных данных. Когда в таблице несколько столбцов-признаков, появляется эффект существенной многомерности: верный вывод можно получить только при одновременном учёте всех взаимосвязанных признаков. Две группы точек могут не отличаться ни по одной координате в отдельности — и при этом очевидно разделяться по новому признаку, например по сумме координат.

Удачная классификация способна даже открыть новое направление исследований. Астрономы давно знали и светимость звёзд, и их спектральные классы, но лишь в 1913 г. Герцшпрунг и Рессел нанесли звёзды на плоскость «спектр — светимость». Оказалось, что звёзды образуют на ней несколько ярко выраженных кластеров, по положению в которых можно предсказывать эволюцию звезды. Диаграмма Герцшпрунга — Рессела до сих пор — рабочий инструмент астрономов.

Если признаков больше трёх, глазами кластеры уже не увидишь. Глава — про методы, которые делают это за нас:

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

Параграфы

• §1. Нормировка, расстояния и классы — N1–N3, метрики Минковского, четыре типа классов.
• §2. Эвристические методы — A1–A5, точка Штейнера.
• §3. Иерархические процедуры — ближний и дальний сосед, Уорд, формула Ланса — Уильямса, инверсии.
• §4. Быстрые алгоритмы — редуктивность и порог δ.
• §5. Функционалы качества разбиения — F1–F9, многомерная нормальная модель, собака или волк.
• §6. Неизвестное число классов — мера концентрации и аппроксимация матрицы связей.
• §7. Сравнение методов — кто лучше восстанавливает классы и кто устойчивее к шуму.
• §8. Представление результатов — семь характеристик классификации и степень разделенности.
• §9. Поиск в глубину — обход графа и нить Ариадны.

Практика

• Задачи с разборами
• Контрольные вопросы

Что уносим из главы

Классификация сильнее других разделов статистики зависит от решений исследователя: как нормировать признаки, какое взять расстояние, какой метод и сколько классов. Универсального «правильного» ответа нет. Есть методы, хорошие для круглых облаков (k-средних, Уорд), и методы, ловящие ленты (ближний сосед, кратчайший незамкнутый путь). Когда же за данными стоит вероятностная модель — смесь нормальных законов, — классификация превращается в честную задачу оценивания, а ошибки можно оценить числом.

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