Алгоритмы кластеризации для построения ε-покрытия хаотических аттракторов

Материал из Машинное обучение - Кафедра прикладной кибернетики
Перейти к навигации Перейти к поиску

Задание

Прочитать и законспектировать вводный материал по хаотическим аттракторам и численным «множество-ориентированным» методам приближения инвариантных множеств (разбиения/покрытия). Рекомендуемые источники: [1], [2], [3].

Прочитать и законспектировать основы алгоритмов кластеризации и векторной квантизации: SOM (карты Кохонена), Neural Gas, Growing Neural Gas (GNG), а также классические методы k-means/k-medoids и жадный k-center (farthest-first). Рекомендуемые источники: [4]–[8].

Сгенерировать численные траектории как облака точек аттракторов по крайней мере для двух систем (например, Лоренц и Рёсслер):

  • проинтегрировать ОДУ (Python, solve_ivp),
  • отбросить переходной участок,
  • нормировать и проредить точки (равномерно по времени или по дуговой длине),
  • собрать выборку S (типично M ≈ 10⁵ точек).

Реализовать и сравнить не менее трёх подходов к построению ε-покрытия множества S (прототипами будут центры кластеров/узлы сети):

  • Жадный k-center (farthest-first) — добавлять в X точку с максимальным расстоянием до текущего набора; останавливаться при ρ(X,S) ≤ ε или при |X| = N. (Гарантия 2-аппроксимации для метрической постановки.)
  • k-means / k-medoids — разбиение на k кластеров; центры/медоиды используются как узлы покрытия; контролировать радиусы кластеров.
  • SOM / Neural Gas / GNG — обучить прототипы на S; оценить равномерность (карта попаданий BMU) и радиус покрытия после обучения; для GNG варьировать параметры роста, чтобы избежать избыточной концентрации в «густых» областях.
  • (Опционально) Poisson-disk sampling в ограничителе вокруг S с отбраковкой по минимальному расстоянию и проверкой близости к S (k-d-дерево).

Оценить качество и равномерность покрытия:

  • радиус покрытия ρ(X,S) = sup_{a∈S} min_{x∈X} ||a−x||₂,
  • (асимметричное и симметричное) расстояние Хаусдорфа d_H(X,S),
  • распределение расстояний «точка → ближайший прототип», коэффициент вариации,
  • дисперсию числа попаданий BMU (для SOM/GNG), pair-correlation для равномерности,
  • эмпирическую оценку размерности по box-counting через наклон графика log N(ε) vs log(1/ε).

Поставить два сценария сравнения и построить соответствующие кривые:

  • (A) фиксировать ε и минимизировать |X|,
  • (B) фиксировать |X| = N и минимизировать ρ(X,S).

Провести не менее трёх независимых прогонов (разные сиды/подвыборки) и приводить медианы/IQR; фиксировать вычислительную среду (ОС, Python, версии библиотек).

Подготовить краткий теоретический результат (на выбор, один пункт):

  • доказать 2-аппроксимационную оценку жадного farthest-first для $k$-center в метрическом пространстве (в виде аккуратного конспекта-доказательства),
  • показать, что ошибка квантизации SOM/Neural Gas мажорирует радиус покрытия при ограничениях на локальную плотность (эскиз с аккуратными оценками).

Реализация — на Python (numpy, scipy, scikit-learn, при желании MiniSom или собственная SOM/GNG), float64, фиксированные сиды; репозиторий с requirements.txt, скриптом run_all.py и README с инструкциями воспроизводимости.

Результаты работы (отчёт, оформленный в виде курсовой с графиками, таблицами, описанием методов и параметров; приложения с листингами кода) прислать научному руководителю на e-mail или в Telegram (см. ниже).

Важно: отчёт обязательно должен быть набран в LaTeX (рекомендуется biblatex со стилем ГОСТ).

Список литературы

  1. Dellnitz, M., Junge, O. Set-Oriented Numerical Methods for Dynamical Systems. In: Handbook of Dynamical Systems, Vol. 2. Elsevier, 2002, pp. 221–264.
  2. Krauskopf, B., Osinga, H. M., Doedel, E. J. Computing Invariant Manifolds via Continuation of Orbit Segments. In: Numerical Continuation Methods for Dynamical Systems. Springer, 2007, pp. 117–154.
  3. Falconer, K. Fractal Geometry (3rd ed.). Wiley, 2014.
  4. Kohonen, T. Self-Organizing Maps (3rd ed.). Springer, 2001.
  5. Martinetz, T., Schulten, K. A “Neural-Gas” Network Learns Topologies. In: Artificial Neural Networks, 1991, pp. 397–402.
  6. Fritzke, B. A Growing Neural Gas Network Learns Topologies. NIPS 7, 1995, pp. 625–632.
  7. Bishop, C. M. Pattern Recognition and Machine Learning. Springer, 2006. (Гл. 9: кластеризация.)
  8. Gonzalez, T. F. Clustering to Minimize the Maximum Intercluster Distance. Theoretical Computer Science 38 (1985): 293–306. (Жадный farthest-first, 2-аппроксимация.)
  9. Peitgen, H.-O., Jürgens, H., Saupe, D. Chaos and Fractals. Springer, 1992.
  10. Bridson, R. Fast Poisson Disk Sampling in Arbitrary Dimensions. SIGGRAPH Sketches, 2007.
  11. Документация: [1], MiniSom.

Научный руководитель

ФИО: Мокаев Тимур Назирович — [e-mail] · [Telegram]

Источник — https://apcyb.wiki/index.php?title=Алгоритмы_кластеризации_для_построения_ε-покрытия_хаотических_аттракторов&oldid=1048