Этой зимой вам предстоит оптимизировать алгоритм кластеризации k-means. Кластеризация — это группировка похожих объектов в группы (кластеры) без предварительного знания о классах, относящийся к обучению без учителя, где сходство определяется алгоритмом, а не заданными меткам. Кластеризация очень часто применяется в маркетинге, сегментации изображений, кластеризации геоданных. (Статья про кластеризацию на habr)
Одним из самых популярных и простых методов кластеризации является k-means. Он широко применяется благодаря своей простоте. В рамках зимней школы, мы будет работать над алгоритмом k-means из библиотеки OpenCV. Стандартный алгоритм k-means использует случайную расстановку начальных центров кластеров, но в OpenCV реализован ещё один алгоритм генерации начальных центров (generateCentersPP). Вариант k-means, использующий функцию generateCentersPP, называют k-means++.
- https://ru.wikipedia.org/wiki/K-means%2B%2B
- https://en.wikipedia.org/wiki/K-means%2B%2B
- https://www.hse.ru/data/2016/09/05/1120164888/ArthurV07.pdf
- https://dzaima.github.io/intrinsics-viewer/#riscv
Задачи для двух подгрупп:
- Оптимизировать k-means для случая, когда размерность пространства признаков равна 4. (подгруппа №1 – 2 студента)
- Оптимизировать k-means для случая, когда размерность пространства признаков равна 16. (подгруппа №2 – 2 студента)
- Написать итоговую презентацию для защиты (ну и сама защита).
Данные задачи ставят следующие цели для каждой из подгрупп:
- Проведение вычислительной оптимизации основного цикла алгоритма k-means для конкретной размерности пространства признаков. (студент А из подгруппы С)
- Проведение экспериментов, которые докажут или опровергнут преимущество алгоритма generateCentersPP. Проведение вычислительной оптимизации алгоритма generateCentersPP для конкретной размерности пространства признаков. (студент B из подгруппы С)
- Написание презентации для защиты (студент A, B из подгруппы С)