В данной лекции рассматривается раздел машинного обучения — кластеризация (алгоритмы сегментации) как метод обучения без учителя. В отличие от классификации, где классы объектов предопределены заранее, кластеризация позволяет самостоятельно разбить данные на неизвестные ранее группы на основе понятия «расстояния» между объектами. Подробно разбираются иерархические (агломеративные и дивизивные), плотностные, модельные, концептуальные, сетевые и итеративные алгоритмы. Основной фокус сделан на методе k-средних (k-means): его принцип работы, критерии остановки, преимущества, недостатки (чувствительность к выбросам, необходимость заранее знать число кластеров, зависимость от начальных центров) и способы их преодоления (k-means++, нечёткая кластеризация). Также упомянуты индексы для выбора оптимального числа кластеров (Галинского-Харабаша и др.).
Основные мысли
1. Ключевое отличие кластеризации от классификации — отсутствие целевого поля (правильных ответов). Это обучение без учителя.
2. Без понятия расстояния (метрики) кластеризация невозможна. Выбор метрики (евклидово, манхэттенское, косинусное, Жаккара) зависит от предметной области.
3. Иерархические алгоритмы строят полную дендрограмму от 1 до N кластеров, но имеют сложность O(N²).
4. Плотностные алгоритмы (например, DBSCAN) хороши для невыпуклых кластеров и борьбы с выбросами, но требуют подбора двух параметров (радиус и minPts).
5. Метод k-средних — итеративный алгоритм, требующий заранее заданного числа кластеров. Он чувствителен к начальным центрам и выбросам, работает только с выпуклыми (эллипсоидными) кластерами.
6. Проблемы k-средних решаются через:
o k-means++ (удалённый выбор начальных центров);
o удаление выбросов или случайные подвыборки;
o нечёткую кластеризацию (вероятностная принадлежность точке к нескольким кластерам).
7. Выбор числа кластеров (k) можно оценить с помощью индексов (Галинского-Харабаша, Хартигана) или критерия «плотности» кластеров (минимизация внутрикластерных расстояний).
Показывать лекцию целиком
Краткое изложение
Введение
• Машинное обучение делится на три группы: классификация, ассоциативные правила, сегментация (кластеризация). Обучение с подкреплением — четвёртая группа.
• Кластеризация — разделение объектов на группы, которые не известны заранее (в отличие от классификации).
Роль расстояния
• Расстояние между объектами — основа любого алгоритма кластеризации.
• Примеры метрик: евклидово, манхэттенское, косинусное, Жаккара.
Иерархические алгоритмы
• Строят дендрограмму для любого числа кластеров (от 1 до N).
• Агломеративные (снизу вверх): каждый объект — отдельный кластер, затем объединяются ближайшие.
• Дивизивные (сверху вниз): все объекты — один кластер, затем расщепляются по самому удалённому расстоянию.
• Способы измерения расстояния между кластерами: ближайший сосед, дальний сосед, среднее и др.
• Сложность: O(N²).
Неиерархические алгоритмы
• Модельные — основаны на вероятностных распределениях (максимизация правдоподобия). Требуют серьёзной математики, но масштабируемы.
• Концептуальные (например, Cobweb) — сложны, применяются редко.
• Плотностные (например, DBSCAN) — задаются радиус и минимальное число точек в нём. Работают с невыпуклыми кластерами, сложность O(N log N). Проблема — подбор двух параметров.
• Сетевые — используют вейвлет-анализ (очень сложны, не рассматриваются детально).
• Итеративные (ключевые) — многократно повторяют один шаг до условия остановки.
Метод k-средних (k-means)
1. Задать число кластеров k.
2. Выбрать случайно k точек как начальные центры.
3. Приписать каждую точку к ближайшему центру.
4. Пересчитать центры как среднее арифметическое точек в кластере.
5. Повторять шаги 3–4, пока не выполнится условие остановки.
Условия остановки:
• Достигнуто максимальное число итераций.
• Точки перестали менять кластер.
• Центры перестали смещаться (или смещение меньше порога).
Проблемы k-средних:
1. Не гарантируется глобальный минимум (застревание в локальном).
2. Результат зависит от выбора начальных центров.
3. Число кластеров надо знать заранее.
4. Сильная чувствительность к выбросам.
5. Работает только с выпуклыми (эллипсоидными) кластерами.
Решения проблем:
• Выбор начальных центров — алгоритм k-means++ (центры максимально удалены друг от друга).
• Выбросы — удаление или метод случайных подвыборок (усреднение картинок).
• Число кластеров — индексы Галинского-Харабаша, Хартигана, Коржановского-Лея. Хороший кластер — плотный (малая сумма расстояний до центра).
• Невыпуклые кластеры — не решается k-means, нужны плотностные алгоритмы.
• Нечёткая кластеризация — точка принадлежит всем кластерам с вероятностями. Отсечка по порогу (например, 0,7) позволяет убрать пограничные точки для последующего ручного анализа.
Переход к практике
Далее лектор планирует перейти к реализации алгоритмов в R.
Выводы
1. Кластеризация — мощный инструмент разведочного анализа данных, но она требует осознанного выбора метрики, алгоритма и настройки параметров.
2. Иерархические методы дают полную картину, но дороги в вычислительном плане. Плотностные хороши для сложных форм кластеров и выбросов. K-means — простой и быстрый, но имеет жёсткие ограничения.
3. Главные «болевые точки» k-means: необходимость задавать число кластеров, чувствительность к выбросам и начальным центрам, а также ориентация только на выпуклые кластеры.
4. Реализация нечёткой кластеризации и k-means++ существенно повышает практическую применимость метода.
5. Для выбора числа кластеров следует использовать объективные критерии (индексы), а не полагаться на визуальную оценку.
Вопросы для самопроверки
1. Чем принципиально отличается задача кластеризации от задачи классификации?
2. Почему в кластеризации невозможно обойтись без понятия «расстояние» между объектами?
3. В чём разница между агломеративным и дивизивным иерархическими алгоритмами?
4. Какие три способа измерения расстояния между кластером и отдельной точкой были упомянуты?
5. Как работает плотностной алгоритм кластеризации (DBSCAN)? Какие два параметра он требует и в чём сложность их подбора?
6. Опишите пошагово алгоритм k-средних (k-means).
7. Назовите три критерия остановки итераций в k-means.
8. Перечислите пять основных недостатков метода k-средних.
9. Как метод k-means++ решает проблему выбора начальных центров?
10. Что такое нечёткая кластеризация и как она помогает бороться с пограничными точками?
11. Почему k-means не подходит для выделения кластеров в виде «загогулины» (невыпуклой формы)?
12. Какие индексы можно использовать для выбора оптимального числа кластеров? Какой простой критерий «хорошего» кластера предложил лектор
