Алгоритм кластеризации

**Определение:** Метод автоматической классификации (обучения без учителя), целью которого является разбиение множества объектов $X$ на непересекающиеся или пересекающиеся подмножества (кластеры) $Y$, таким образом, чтобы объекты внутри одного кластера были близки друг к другу относительно выбранной метрики $\rho$, а объекты из разных кластеров — существенно различны. **Математическая постановка (по К.В. Воронцову):** Дано пространство объектов $X$ и обучающая выборка $X^\ell = \{x_1, ..., x_\ell\}$. Задана функция расстояния $\rho(x, x')$. Требуется построить алгоритм $a: X \to Y$ (где $Y$ — множество меток кластеров), который минимизирует функционал внутрикластерного расстояния и/или максимизирует функционал межкластерного расстояния. **Фундаментальная проблема:** Задача кластеризации является *некорректно поставленной*. Не существует единственно правильного разбиения. Результат зависит от: 1. Выбора метрики пространства признаков. 2. Выбора критерия качества (функционала). 3. Эвристических допущений конкретного алгоритма (гипотеза компактности, гипотеза плотности и др.).