Читать онлайн «Лекции по алгоритмам кластеризации и многомерного шкалирования»

Лекции по алгоритмам кластеризации и многомерного шкалирования К. В. Воронцов 21 декабря 2007 г. Материал находится в стадии разработки, может содержать ошибки и неточности. Перепечатка любых фрагментов данного материала без согласия автора является плагиатом. Содержание 1 Кластеризация и многомерное шкалирование 2 1. 1 Алгоритмы кластеризации . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1. 1. 1 Эвристические графовые алгоритмы . . . . . . . . . . . . . . . . 3 1. 1. 2 Функционалы качества кластеризации . . . . . . . . . . . . . . . 6 1. 1. 3 Статистические алгоритмы . . . . . . . . . . . . . . . . . . . . . . 7 1. 1. 4 Иерархическая кластеризация . . . . . . . . . . . . . . . . . . . . 10 1. 2 Многомерное шкалирование . . . . . . . . . . . . . . . . . . . . . . . . . 14  2 1 Кластеризация и многомерное шкалирование Во многих прикладных задачах измерять степень сходства объектов существен- но проще, чем формировать признаковые описания. Например, гораздо легче срав- нить две фотографии и сказать, что они принадлежат одному человеку, чем понять, на основании каких признаков они схожи. Задача классификации объектов на основе их сходства друг с другом, когда принадлежность обучающих объектов каким-либо классам не задаётся, называется задачей кластеризации. В §1. 1 рассматриваются статистические, иерархические и графовые алгоритмы кластеризации. В §1. 2 рассматриваются методы многомерного шкалирования, позволяющие восстанавливать признаковые описания объектов по матрице попарных расстояний между ними. §1. 1 Алгоритмы кластеризации Задача кластеризации (или обучения без учителя) заключается в следующем. Имеется обучающая выборка X ℓ = {x1 , . . . , xℓ } ⊂ X и функция расстояния между объектами ρ(x, x′ ). Требуется разбить выборку на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из объектов, близких по метрике ρ, а объекты разных кластеров существенно отличались. При этом каж- дому объекту xi ∈ X ℓ приписывается метка (номер) кластера yi . Алгоритм кластеризации — это функция a : X → Y , которая любому объек- ту x ∈ X ставит в соответствие метку кластера y ∈ Y . Множество меток Y в некото- рых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного критерия качества кластеризации. Решение задачи кластеризации принципиально неоднозначно, и тому есть несколько причин. Во-первых, не существует однозначно наилучшего критерия ка- чества кластеризации.