Обсуждение статьи "Фильтрация Вьеториса — Рипса в MQL5: Построение симплексов и граничной матрицы"

[MetaQuotes]

Опубликована статья Фильтрация Вьеториса — Рипса в MQL5: Построение симплексов и граничной матрицы:

Мы преобразуем облако точек, построенное с помощью вложения ценового ряда, в фильтрацию Вьеториса — Рипса и соответствующую ей граничную матрицу. В статье вершины, ребра и треугольники перечисляются с указанием значений фильтрации и сортируются в порядке добавления в фильтрацию; также создаются таблицы поиска вершин и ребер за время O(1). Вы получаете классы CTDARips и CTDABoundary на MQL5, а также разреженную граничную матрицу над Z/2, пригодную для последующей редукции при вычислении персистентности.

В предыдущей статье были получены два конкретных геометрических объекта: облако точек, полученное с помощью вложения Такенса, и его полная матрица попарных расстояний. Эти объекты необходимы, но недостаточны для ответа на интересующие нас топологические вопросы (Существуют ли кластеры? Есть ли длительно сохраняющийся цикл?). Далее нам нужен воспроизводимый и поддающийся вычислению топологический объект, который фиксирует, при каких значениях параметра масштаба эпсилон появляются симплексы по мере увеличения этого параметра: фильтрация Вьеториса — Рипса (а также граничные соотношения, позволяющие вычислять гомологии).

Конкретная задача этой статьи — реализация следующей процедуры: по заданному облаку из N точек, полученному с помощью вложения, и порогу отсечения maxEpsilon перечислить все симплексы размерности не выше maxDim ≤ 2, присвоить каждому симплексу его значение фильтрации (для вершины — 0, для ребра — расстояние между его концами, для треугольника — максимальная из длин трех его ребер) и получить две структуры данных, пригодных для редукции. Реализация должна обеспечивать соблюдение ключевых инвариантов, необходимых на этапе редукции: симплексы отсортированы по значению фильтрации (при равенстве значений приоритет отдается меньшей размерности, чтобы грани предшествовали кограням), таблицы поиска вершин и ребер обеспечивают получение глобальных индексов за время O(1), а индексы в каждом столбце граничной матрицы хранятся в порядке возрастания, чтобы его ведущий элемент можно было определить без дополнительных операций. Практические ограничения (число ребер O(N²), число треугольников O(N³)) обусловливают необходимость ограничения размерности и использования таблиц поиска, повышающих скорость работы за счет дополнительного расхода памяти.

Рис. 1. Одно облако точек в трёх масштабах. При малом значении эпсилон точки изолированы. При среднем значении эпсилон кольцо из ребер образует цикл. При большом значении эпсилон треугольники заполняют цикл, и он исчезает.

Рисунок выше передает суть всей статьи. На рисунке трижды изображено одно и то же облако точек при трёх значениях параметра масштаба, который мы называем эпсилон. Сами точки на всех трех изображениях остаются неизменными. Меняется лишь правило их соединения.

Слева величина эпсилон невелика. Расстояние между любыми двумя точками превышает эпсилон, поэтому облако состоит лишь из изолированных точек. Здесь двенадцать компонент связности и ни одного цикла. В середине величина эпсилон больше. Теперь каждая точка соединяется со своими соседями, и ребра смыкаются, образуя кольцо. Имеется одна компонента связности и один цикл. Справа величина эпсилон ещё больше. Теперь соединяются и точки на противоположных сторонах кольца, треугольники заполняют его внутреннюю область, и цикл исчезает. Одна компонента связности, без циклов.

Цикл на средней панели — это сигнал. Он возник, когда кольцо замкнулось, и исчез, когда его внутренняя область заполнилась. Диапазон значений эпсилон, в котором цикл существовал, — это его персистентность. Цикл, сохраняющийся длительное время, — это реальная особенность данных. Цикл, который возникает и почти сразу же исчезает, — это шум. В данной статье разрабатывается инструментарий именно для измерения персистентности. Далее объясняется, как он работает.

Автор: Hammad Dilber