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

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

MetaTrader 5 — Трейдинг |
115 0
Hammad Dilber
Hammad Dilber

Содержание

  1. Введение: от облака точек к форме
  2. Фильтрация на графике
  3. Симплексы: строительные блоки
  4. Фильтрация Вьеториса — Рипса
  5. Реализация: CTDARips
  6. Сортировка и поиск за O(1)
  7. Граничная матрица над Z/2
  8. Реализация: CTDABoundary
  9. Разбор примера и проверка корректности
  10. Что дальше?
  11. Заключение


Введение: от облака точек к форме

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

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


Фильтрация на графике

Три изображения одного и того же облака точек: изолированные точки, затем кольцо из ребер, образующее цикл, и, наконец, цикл, заполненный треугольниками

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

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

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

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


Симплексы: строительные блоки

Одна точка, две точки, соединенные линией, и три точки, образующие заполненный треугольник

Рис. 2. Три типа симплексов, используемых в этой библиотеке: вершина (размерность 0), ребро (размерность 1) и заполненный треугольник (размерность 2).

Симплициальный комплекс состоит из простых частей, называемых симплексами. 0-симплекс — это одна вершина. 1-симплекс — это ребро, соединяющее две вершины. 2-симплекс — это заполненный треугольник с тремя вершинами. Существуют и симплексы более высоких размерностей (3-симплекс — это тетраэдр вместе с его внутренней областью), но эта библиотека ограничивается треугольниками, которых достаточно для выявления связных компонент и циклов.

Размерность симплекса на единицу меньше числа его вершин. Симплекс-вершина состоит из одной вершины и имеет размерность 0. Ребро имеет две вершины и размерность 1. Треугольник имеет три вершины и размерность 2. Библиотека хранит каждый симплекс в небольшой структуре фиксированного размера.

//+------------------------------------------------------------------+
//| SSimplex - one simplex in the filtration                         |
//|                                                                  |
//|  Stores the vertex set (sorted ascending), the filtration value  |
//|  at which the simplex enters, and its dimension. Up to 3 vertices|
//|  are kept (max dim = 2 = triangle); unused slots hold -1.        |
//+------------------------------------------------------------------+
struct SSimplex
  {
   double   filtration;     // filtration value at which simplex appears
   int      dim;            // 0 = vertex, 1 = edge, 2 = triangle
   int      v[3];           // sorted vertex indices, unused = -1

   void     Reset()
     {
      filtration = 0.0;
      dim        = 0;
      v[0]       = -1;
      v[1]       = -1;
      v[2]       = -1;
     }
  };

Структура содержит три элемента: значение фильтрации, при котором появляется симплекс, его размерность и множество вершин. Массив вершин вмещает три индекса, поскольку треугольник — симплекс наибольшей размерности из тех, что мы строим. Для вершины используется одна ячейка, а в двух остальных остаётся значение -1. Для ребра используются две ячейки. Вершины хранятся в порядке возрастания их индексов, что важно при последующем поиске ребра по его конечным точкам.

Значение фильтрации является ключевым полем. Для вершины это значение равно 0, поскольку каждая точка присутствует с самого начала. Для ребра это расстояние между его двумя конечными точками, поскольку это наименьшее значение эпсилон, при котором ребро появляется в комплексе. Для треугольника это наибольшая из длин трёх его рёбер, поскольку для образования треугольника необходимо наличие всех трёх рёбер. Это единственное правило — значение фильтрации равно длине самого длинного ребра — составляет суть построения Вьеториса — Рипса.


Фильтрация Вьеториса — Рипса

Правило Вьеториса — Рипса применяется механически. Зафиксируем параметр масштаба эпсилон. Тогда:

Ребро (i, j) существует, если расстояние (i, j) ≤ эпсилон. Треугольник (i, j, k) существует, если существуют все три его ребра.

По мере увеличения эпсилон от 0 симплексы только добавляются и никогда не удаляются. При малом значении эпсилон получается разреженный комплекс из изолированных вершин. При большом значении эпсилон получается плотный комплекс, в котором каждая тройка вершин образует заполненный треугольник. Фильтрация представляет собой полную упорядоченную последовательность симплексов, каждый из которых помечен значением эпсилон, при котором он входит в комплекс.

Запись непрерывного диапазона значений эпсилон была бы невозможна. Ключевое наблюдение, позволяющее получить конечное представление фильтрации, состоит в том, что комплекс изменяется только при определённых значениях эпсилон — когда появляется новое ребро или треугольник. Эти значения и есть значения фильтрации симплексов. Поэтому вместо того, чтобы изменять эпсилон по всему непрерывному диапазону, мы строим каждый симплекс один раз, помечаем его значением фильтрации и сортируем всё множество по этому значению. Чтение отсортированного списка от начала до конца точно воспроизводит процесс фильтрации.

В порядке сортировки есть одна тонкость. Если два симплекса имеют одинаковое значение фильтрации, то симплекс меньшей размерности должен стоять первым. Ребро не может появиться раньше своих конечных точек, а треугольник — раньше своих ребер. При равных значениях фильтрации сортировка по размерности гарантирует, что каждый симплекс появляется после своих граней; это условие необходимо для последующего построения граничной матрицы.

Стоит явно указать вычислительные затраты на это построение. Для N точек существует не более N(N-1)/2 ребер и N(N-1)(N-2)/6 треугольников, поэтому количество треугольников растёт пропорционально кубу N. При окне в 80 баров облако точек состоит из 78 точек, а полный комплекс насчитывает десятки тысяч треугольников. Именно из-за этого кубического роста в четвёртой статье установлено ограничение на размер окна, а этап редукции в следующей статье является наиболее ресурсоёмкой частью конвейера.


Реализация: CTDARips

Класс CTDARips выстраивает фильтрацию на основе матрицы расстояний. Он хранит симплексы в одном динамическом массиве, отслеживает число симплексов каждой размерности и предоставляет функции поиска, необходимые модулю построения границ.

//+------------------------------------------------------------------+
//| CTDARips - builds the Vietoris-Rips filtration up to maxDim <= 2 |
//+------------------------------------------------------------------+
class CTDARips
  {
private:
   SSimplex          m_simplices[];     // sorted filtration order
   int               m_count;           // total simplex count (logical size)
   int               m_capacity;        // allocated capacity of m_simplices
   int               m_N;               // number of points
   int               m_maxDim;          // max dim built (<= 2)
   double            m_maxFiltration;   // max filtration value in complex

   int               m_vertexIdx[];     // [N]    : global idx of vertex {v}
   int               m_edgeIdx[];       // [N*N]  : global idx of edge {i,j}
   int               m_dimCount[3];     // simplex count per dim

   //--- helpers
   void              SwapSimplex(int i, int j);
   bool              SimplexLess(int a, int b) const;
   void              QuickSort(int low, int high);
   void              BuildLookups();
   void              EnsureCapacity(int needed);
   void              AppendSimplex(double f, int dim, int v0, int v1, int v2);

public:
                     CTDARips();
                    ~CTDARips() {}

   bool              Build(const CTDADistance &dist,
                           double maxEpsilon,
                           int    maxDim = 2);

   int               Size()          const { return m_count; }
   int               SizeByDim(int d) const;
   double            MaxFiltration() const { return m_maxFiltration; }
   bool              Get(int idx, SSimplex &out) const;

   int               VertexGlobalIdx(int v)      const;
   int               EdgeGlobalIdx(int i, int j) const;
  };

Симплексы хранятся в одном плоском массиве m_simplices, емкость которого увеличивается удвоением по той же схеме с амортизированной оценкой сложности, что была представлена в предыдущей статье. Перечисление симплексов по одному с увеличением размера массива на единицу для каждого из них имело бы квадратичную сложность. Удвоение емкости обеспечивает амортизированную сложность O(1) для каждой операции добавления. Два массива поиска — m_vertexIdx и m_edgeIdx — заполняются после сортировки; их назначение описано в следующем разделе.

В методе Build формируется фильтрация. Метод выполняет три прохода: сначала добавляет вершины, затем ребра, затем треугольники.

//+------------------------------------------------------------------+
//| Build the full Vietoris-Rips filtration                          |
//+------------------------------------------------------------------+
bool CTDARips::Build(const CTDADistance &dist, double maxEpsilon, int maxDim)
  {
   m_N      = dist.Size();
   m_maxDim = (maxDim > 2 ? 2 : (maxDim < 0 ? 0 : maxDim));

   if(m_N < 2)
     {
      Print("TDARips::Build - need at least 2 points");
      return false;
     }
   if(maxEpsilon <= 0.0)
     {
      Print("TDARips::Build - maxEpsilon must be > 0");
      return false;
     }

   //--- reset logical size, keep allocated capacity for reuse
   m_count            = 0;
   m_maxFiltration    = 0.0;
   m_dimCount[0]      = 0;
   m_dimCount[1]      = 0;
   m_dimCount[2]      = 0;

   //--- 0-simplices: every vertex, filtration 0
   for(int i = 0; i < m_N; i++)
      AppendSimplex(0.0, 0, i, -1, -1);

   if(m_maxDim < 1)
     {
      QuickSort(0, m_count - 1);
      BuildLookups();
      return true;
     }

   //--- 1-simplices: edges with d <= maxEpsilon
   for(int i = 0; i < m_N; i++)
      for(int j = i + 1; j < m_N; j++)
        {
         double d = dist.Get(i, j);
         if(d > maxEpsilon) continue;
         AppendSimplex(d, 1, i, j, -1);
        }

   if(m_maxDim < 2)
     {
      QuickSort(0, m_count - 1);
      BuildLookups();
      return true;
     }

   //--- 2-simplices: triangles with all three edges within maxEpsilon
   for(int i = 0; i < m_N; i++)
      for(int j = i + 1; j < m_N; j++)
        {
         double dij = dist.Get(i, j);
         if(dij > maxEpsilon) continue;
         for(int k = j + 1; k < m_N; k++)
           {
            double dik = dist.Get(i, k);
            if(dik > maxEpsilon) continue;
            double djk = dist.Get(j, k);
            if(djk > maxEpsilon) continue;

            double f = MathMax(dij, MathMax(dik, djk));
            AppendSimplex(f, 2, i, j, k);
           }
        }

   //--- sort the entire filtration in ascending order
   QuickSort(0, m_count - 1);
   BuildLookups();
   return true;
  }

Сначала метод ограничивает максимальную размерность диапазоном 0–2 и проверяет корректность входных данных. Затем он сбрасывает логический размер, повторно используя ранее выделенную емкость. После этого выполняется три прохода.

В первом проходе каждая вершина добавляется со значением фильтрации 0. Если при вызове запрошена только размерность 0, метод выполняет сортировку и завершает работу. Во втором проходе перебираются все пары (i, j), где j больше i, считывается расстояние между точками каждой пары и добавляется ребро, если это расстояние не превышает maxEpsilon. Значение фильтрации ребра равно самому расстоянию. В третьем проходе перебираются все тройки (i, j, k), проверяется, что длины всех трех ребер не превышают maxEpsilon, и добавляется треугольник, значение фильтрации которого равно наибольшей из трех длин ребер. Операторы continue позволяют сразу перейти к следующей тройке, как только одно из ребер оказывается слишком длинным, и тем самым избежать считывания третьего расстояния, если уже первое не удовлетворяет условию.

После всех проходов один вызов QuickSort сортирует весь массив сначала по значению фильтрации, а затем по размерности. Заключительный вызов BuildLookups индексирует отсортированные вершины и ребра. После завершения метода Build объект содержит полный список симплексов, упорядоченный в соответствии с фильтрацией.


Сортировка и поиск за O(1)

Компаратор сортировки реализует правило разрешения равенства из теоретического раздела: по возрастанию значения фильтрации, а при равенстве значений — по возрастанию размерности.

//+------------------------------------------------------------------+
//| Sorting order: filtration ascending, ties broken by dim ascending|
//+------------------------------------------------------------------+
bool CTDARips::SimplexLess(int a, int b) const
  {
   if(m_simplices[a].filtration < m_simplices[b].filtration) return true;
   if(m_simplices[a].filtration > m_simplices[b].filtration) return false;
   return (m_simplices[a].dim < m_simplices[b].dim);
  }

Симплекс с меньшим значением фильтрации идет первым. Если значения фильтрации двух симплексов равны, первым идет симплекс меньшей размерности. Это свойство гарантирует, что грани симплекса появляются раньше самого симплекса. Библиотека использует быструю сортировку «на месте» вместо встроенной, поскольку компаратор осуществляет сравнение по трём полям, а массив хранит структуры по значению.

После сортировки положение каждого симплекса в массиве соответствует его глобальному индексу, и именно по этому индексу на него ссылаются все остальные компоненты конвейера. Модуль построения границ, получив треугольник, должен быстро ответить на конкретный вопрос: каков глобальный индекс ребра между вершинами i и j? Просмотр всего массива в поисках этого ребра привел бы к квадратичной сложности построения границы. Таблицы поиска позволяют этого избежать.

//+------------------------------------------------------------------+
//| After sort, build vertex/edge -> global-index lookup tables      |
//+------------------------------------------------------------------+
void CTDARips::BuildLookups()
  {
   ArrayResize(m_vertexIdx, m_N);
   for(int v = 0; v < m_N; v++) m_vertexIdx[v] = -1;

   ArrayResize(m_edgeIdx, m_N * m_N);
   ArrayInitialize(m_edgeIdx, -1);

   for(int s = 0; s < m_count; s++)
     {
      const int dim = m_simplices[s].dim;
      if(dim == 0)
        {
         m_vertexIdx[m_simplices[s].v[0]] = s;
        }
      else if(dim == 1)
        {
         int a = m_simplices[s].v[0];
         int b = m_simplices[s].v[1];
         m_edgeIdx[a * m_N + b] = s;
         m_edgeIdx[b * m_N + a] = s;     // symmetric
        }
     }
  }

Функция BuildLookups заполняет два массива. Таблица вершин позволяет по индексу точки напрямую получить глобальный индекс симплекса, которому принадлежит эта вершина. Таблица ребер представляет собой сетку размером N на N, которая сопоставляет паре индексов точек глобальный индекс соединяющего их ребра или -1, если это ребро отсутствует в комплексе. Записываются оба направления — (i, j) и (j, i), — поэтому вызывающий код может найти ребро без предварительного упорядочивания его вершин. С помощью этих таблиц модуль построения границ находит глобальный индекс любой грани за постоянное время.

Таблица ребер использует N² целых чисел. При размерах окон, используемых в трейдинге, такая таблица содержит несколько тысяч записей и заменяет квадратичный поиск поиском за постоянное время. Тот же компромисс — память в обмен на скорость — используется во всей библиотеке.


Граничная матрица над Z/2

Сетка размером 7 на 7, показывающая, какие симплексы меньшей размерности являются гранями каждого симплекса

Рис. 3. Граничная матрица над Z/2 для одного заполненного треугольника. В каждом столбце перечислены грани одного симплекса: ребра указывают на две свои вершины, а треугольник — на свои три ребра.

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

Мы работаем над полем Z/2, состоящим из двух элементов, что означает, что коэффициенты принимают значения либо 0, либо 1, а арифметические операции выполняются по модулю 2. Здесь не нужно учитывать знаки и ориентации, благодаря чему матрицу просто хранить, а её редукция выполняется быстро. Столбец либо содержит заданную грань, либо не содержит её. На рисунке выше показана полная матрица для одного заполненного треугольника: три пустых столбца вершин, три столбца ребер, каждый из которых указывает на две вершины, и один столбец треугольника, указывающий на три ребра.

Работа над полем Z/2 также придаёт сложению столбцов простой и ясный смысл. Сумма двух столбцов представляет собой симметрическую разность множеств их граней: грань, присутствующая в обоих множествах, исключается, а грань, присутствующая только в одном из них, сохраняется. Например, при сложении границы ребра (v0, v1) с границей ребра (v1, v2) получается:

{v0, v1} + {v1, v2} = {v0, v2}

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


Реализация: CTDABoundary

Полная граничная матрица размером N × N состояла бы почти исключительно из нулей: граница треугольника содержит лишь три ребра из тысяч. CTDABoundary хранит матрицу в разреженном виде: как плоский список индексов граней и набор смещений для каждого столбца.

//+------------------------------------------------------------------+
//| CTDABoundary - sparse column form of the boundary over Z/2       |
//|                                                                  |
//|  Column j stores the global indices of the (k-1)-faces of the    |
//|  k-simplex at position j in the sorted filtration:               |
//|    - 0-simplex (vertex)    : empty column                        |
//|    - 1-simplex (edge ij)   : {vertex(i), vertex(j)}              |
//|    - 2-simplex (tri ijk)   : {edge(ij), edge(ik), edge(jk)}      |
//+------------------------------------------------------------------+
class CTDABoundary
  {
private:
   int               m_entries[];      // flat face-index storage
   int               m_colStart[];     // start offset of column j
   int               m_colSize[];      // size of column j
   int               m_numCols;        // = number of simplices
   int               m_totalEntries;   // logical size used in m_entries
   int               m_entriesCap;     // allocated capacity of m_entries

   void              Sort3Asc(int &a, int &b, int &c) const;
   void              ReserveEntries(int needed);

public:
                     CTDABoundary();
                    ~CTDABoundary() {}

   bool              Build(const CTDARips &rips);

   int               NumCols()      const { return m_numCols; }
   int               ColSize(int j) const;
   int               Entry(int j, int k) const;
   void              GetColumn(int j, int &out[]) const;
   int               TotalEntries() const { return m_totalEntries; }
  };

Данные хранятся в трёх массивах. Массив m_entries представляет собой один длинный буфер, в котором индексы граней всех столбцов хранятся подряд. Массив m_colStart хранит позицию начала каждого столбца в этом буфере, а массив m_colSize — число записей в каждом столбце. Чтение столбца j означает чтение m_colSize[j] записей, начиная с m_colStart[j]. При этом вся разреженная матрица упаковывается в три массива без лишних нулей.

Метод `Build` один раз проходит по отсортированной фильтрации и записывает по одному столбцу на каждый симплекс.

//+------------------------------------------------------------------+
//| Build the boundary column-by-column over the sorted filtration   |
//+------------------------------------------------------------------+
bool CTDABoundary::Build(const CTDARips &rips)
  {
   m_numCols = rips.Size();
   if(m_numCols <= 0)
     {
      Print("TDABoundary::Build - empty filtration");
      return false;
     }

   ArrayResize(m_colStart, m_numCols);
   ArrayResize(m_colSize,  m_numCols);
   m_totalEntries = 0;
   ReserveEntries(3 * m_numCols);

   for(int j = 0; j < m_numCols; j++)
     {
      SSimplex s;
      rips.Get(j, s);
      m_colStart[j] = m_totalEntries;

      if(s.dim == 0)
        {
         m_colSize[j] = 0;          // vertices have empty boundary
         continue;
        }

      if(s.dim == 1)
        {
         // boundary of edge {i,j} = vertex i + vertex j
         int va = rips.VertexGlobalIdx(s.v[0]);
         int vb = rips.VertexGlobalIdx(s.v[1]);
         int lo = (va < vb ? va : vb);
         int hi = (va < vb ? vb : va);

         m_entries[m_totalEntries]     = lo;
         m_entries[m_totalEntries + 1] = hi;
         m_totalEntries += 2;
         m_colSize[j] = 2;
         continue;
        }

      // boundary of triangle {i,j,k} = edge(i,j) + edge(i,k) + edge(j,k)
      int eab = rips.EdgeGlobalIdx(s.v[0], s.v[1]);
      int eac = rips.EdgeGlobalIdx(s.v[0], s.v[2]);
      int ebc = rips.EdgeGlobalIdx(s.v[1], s.v[2]);
      Sort3Asc(eab, eac, ebc);

      m_entries[m_totalEntries]     = eab;
      m_entries[m_totalEntries + 1] = eac;
      m_entries[m_totalEntries + 2] = ebc;
      m_totalEntries += 3;
      m_colSize[j] = 3;
     }
   return true;
  }

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

Сортировка элементов каждого столбца по возрастанию выполняется намеренно. Алгоритм редукции, описанный в следующей статье, считывает ведущий элемент столбца как его последнюю запись, поэтому каждый столбец сортируется на этапе построения, чтобы это считывание не требовало дополнительных операций. В буфере заранее зарезервировано по три записи на каждый столбец — это максимальное количество, необходимое для любого столбца, — поэтому размер буфера никогда не изменяется во время выполнения цикла. После завершения работы метода Build граничная матрица полностью построена и доступна только для чтения.


Разбор примера и проверка корректности

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

Две панели: квадрат из четырех ребер с пустым центром, образующий цикл, и тот же квадрат с диагональю, разделяющей его на два заполненных треугольника

Рис. 4. Слева: четыре ребра замыкают цикл вокруг пустого центра — одномерной дыры (H1). Справа: как только длина диагонали становится не больше эпсилон и входит в комплекс, два треугольника заполняют квадрат, и цикл исчезает.

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

Библиотека воспроизводит этот процесс для больших наборов данных. Прилагаемый скрипт TDA_Rips_Demo.mq5 извлекает окно цен закрытия с текущего графика, выполняет весь конвейер обработки вплоть до построения граничной матрицы и выводит сводку по каждому этапу.

#include <TDA/TDAPointCloud.mqh>
#include <TDA/TDADistance.mqh>
#include <TDA/TDARips.mqh>
#include <TDA/TDABoundary.mqh>

input int    InpWindow     = 80;    // bars of close history to embed
input int    InpEmbDim     = 3;     // embedding dimension d
input int    InpDelay      = 1;     // time delay tau
input double InpMaxEpsFrac = 1.0;   // VR cutoff = frac * max pairwise distance
input int    InpMaxDim     = 2;     // max simplex dim (1 = edges, 2 = triangles)

void OnStart()
  {
   double closes[];
   int copied = CopyClose(_Symbol, _Period, 0, InpWindow, closes);
   if(copied != InpWindow)
      return;

   //--- point cloud and distance matrix
   CTDAPointCloud cloud;
   if(!cloud.Build(closes, InpWindow, InpEmbDim, InpDelay))
      return;

   CTDADistance dist;
   if(!dist.Build(cloud, TDA_NORM_EUCLIDEAN))
      return;

   //--- Vietoris-Rips filtration up to maxDim
   double maxEps = InpMaxEpsFrac * dist.MaxDistance();
   CTDARips rips;
   if(!rips.Build(dist, maxEps, InpMaxDim))
      return;
   rips.PrintSummary();

   //--- boundary matrix over Z/2
   CTDABoundary boundary;
   if(!boundary.Build(rips))
      return;
   boundary.PrintSummary();
  }

При запуске на окне из 80 баров GBPUSD H1 с порогом отсечения по умолчанию скрипт выдаёт следующие результаты.

Этап
Показатель
Значение
Облако точек
Точки (N)
78
Фильтрация
Вершины
78
Фильтрация
Рёбра
3003
Фильтрация
Треугольники
76076
Фильтрация
Общее количество симплексов
79157
Фильтрация
Максимальное значение фильтрации
0,014544
Граница
Ненулевые элементы
234234

Эти числа уже сами по себе позволяют проверить корректность результатов. По умолчанию порог отсечения равен полному диаметру облака точек, поэтому расстояние между любой парой точек не превышает этот порог: каждая пара образует ребро, а каждая тройка — треугольник. Число ребер 3003 точно соответствует C(78,2) — количеству способов выбрать две точки из 78. Число треугольников 76076 точно соответствует C(78,3). Число ненулевых элементов граничной матрицы равно 234234: 3003 ребра по две грани плюс 76076 треугольников по три грани. Полученные количества в точности совпадают с комбинаторными расчётами, что служит простейшим подтверждением полноты и корректности перечисления.

Геометрическая структура тоже соответствует ожиданиям. Обработка этим конвейером облака точек, полученного выборкой из зашумлённой окружности, даёт комплекс, который на промежуточных масштабах содержит ровно одно персистентное кольцо — как на рисунке в начале статьи. Полная численная проверка значений рождения и смерти будет проведена в следующей статье, где этап редукции превратит этот каркас в полноценную диаграмму персистентности. На данный момент фильтрация и её граница построены, упорядочены и проверены посредством подсчёта.


Что дальше?

У нас есть фильтрация и граничная матрица. Но персистентность мы пока не вычислили. Граничная матрица кодирует, какие симплексы входят в границы других симплексов, но циклы и компоненты связности в ней пока представлены лишь неявно. В следующей статье мы извлечём их из матрицы.

  • Гомологии разных размерностей: H0 — для компонент связности, H1 — для циклов, H2 — для полостей.
  • Стандартный алгоритм редукции: сложение столбцов над Z/2 до тех пор, пока ведущие элементы столбцов не станут попарно различными.
  • CTDAReduction, преобразующий граничную матрицу в список пар рождения и смерти, характеризующих персистентность.
  • CTDADiagram и фасад CTDA, а также полная численная проверка библиотеки.


Заключение

В этой статье расстояния преобразуются в формальный топологический каркас, необходимый для вычисления персистентных гомологий, и создаются две проверенные структуры данных, готовые к использованию.

Что было построено

  • CTDARips: перечисляет вершины, ребра и треугольники размерности ≤ 2, присваивает каждому симплексу значение фильтрации, сортирует весь список по возрастанию значения фильтрации, а при равенстве значений — по возрастанию размерности, и строит таблицы поиска с доступом за время O(1), задающие отображения (вершина) → глобальный индекс и (i,j) → глобальный индекс ребра. Глобальный индекс симплекса — это его позиция в отсортированном массиве фильтрации.
  • CTDABoundary: принимает отсортированную фильтрацию и записывает разреженную граничную матрицу над Z/2 в столбцовом виде. В каждом столбце хранятся глобальные индексы граней (столбцы вершин пусты, столбцы ребер содержат два индекса вершин, а столбцы треугольников — три индекса ребер). Индексы в каждом столбце хранятся по возрастанию, поэтому ведущий элемент столбца — это последняя запись, и дополнительная сортировка не требуется.

Инварианты и верификация

  • Грани всегда предшествуют кограням (при равенстве значений фильтрации порядок определяется размерностью), поэтому индексы граней в столбцах граничной матрицы меньше индекса самого столбца.
  • Индексы в столбцах предварительно отсортированы, что позволяет процедуре редукции считывать ведущие элементы за время O(1).
  • Компромисс между расходом памяти и скоростью (таблица поиска ребер размером N², плоский буфер записей) обеспечивает быстрое построение границ ценой небольшого дополнительного расхода памяти.
  • Проверка корректности при реальном запуске (N = 78) показала точное совпадение с комбинаторными формулами (число ребер = C(78,2), число треугольников = C(78,3), общее число ненулевых элементов граничной матрицы = 2 × число ребер + 3 × число треугольников), что подтвердило полноту и правильность индексирования.

Когда фильтрация и разреженная граничная матрица готовы, а инварианты соблюдены, конвейеру остается выполнить лишь этап редукции, чтобы получить пары рождения и смерти. В следующей статье будет реализован CTDAReduction, построены диаграммы персистентности и проведена численная проверка значений рождения и смерти.

#
Имя файла
Тип
Описание
1
TDAPointCloud.mqh
Заголовочный файл
Вложение Такенса в фазовое пространство (из предыдущей статьи)
2
TDADistance.mqh
Заголовочный файл
Матрица попарных расстояний (из предыдущей статьи)
3
TDARips.mqh
Заголовочный файл
Фильтрация Вьеториса — Рипса (представлена в этой статье)
4
TDABoundary.mqh
Заголовочный файл
Разреженная граничная матрица над Z/2 (представлена в этой статье)
5
TDA_Rips_Demo.mq5
Скрипт
Готовая к запуску демонстрационная программа: строит фильтрацию и граничную матрицу, выводит сводку

Перевод с английского произведен MetaQuotes Ltd.
Оригинальная статья: https://www.mql5.com/en/articles/23106

Прикрепленные файлы |
MQL5.zip (8.96 KB)
Проектирование конечного автомата торговой стратегии на MQL5: Замена вложенных конструкций if-else явными состояниями Проектирование конечного автомата торговой стратегии на MQL5: Замена вложенных конструкций if-else явными состояниями
Вложенные условные конструкции if-else внутри функции OnTick() создают неявные состояния, которые сложно изолировать, отлаживать и расширять без возникновения регрессионных ошибок. Реализация конечного автомата (FSM) на MQL5 использует интерфейс IState, посредник CStrategyContext и четыре конкретных состояния, чтобы отделить логику обнаружения от логики поведения. Структура из трёх подключаемых файлов устраняет циклические зависимости подключаемых файлов и чётко разделяет объявления, определения и создание экземпляров, делая внесение изменений безопаснее, а отладку — быстрее.
Индикатор скользящего коэффициента Шарпа с доверительными границами в MQL5 Индикатор скользящего коэффициента Шарпа с доверительными границами в MQL5
В данной статье представлен пользовательский индикатор для MetaTrader 5, который вычисляет скользящий коэффициент Шарпа в годовом выражении и отображает полосы статистической значимости с настраиваемой z-оценкой на основе асимптотической стандартной ошибки по формуле Ло. В индикаторе используется кольцевой буфер доходностей с инкрементальным расчетом дисперсии, что обеспечивает обновление за время O(1). Мы объясняем, как неопределенность масштабируется пропорционально n^(-1/2), почему интервалы расширяются при высоких значениях коэффициента Шарпа и как настроить приведение к годовому выражению для каждого инструмента, чтобы корректно использовать индикатор.
Отложенная загрузка хендлов индикаторов в MQL5: Менеджер ресурсов для мультитаймфреймовых советников Отложенная загрузка хендлов индикаторов в MQL5: Менеджер ресурсов для мультитаймфреймовых советников
Мультитаймфреймовые торговые советники, которые инициализируют все хэндлы индикаторов в OnInit(), несут фиксированные затраты на запуск, даже если большинство хэндлов никогда не используется. CIndicatorCache использует отложенную загрузку с поиском по составному ключу, методы получения/освобождения AcquireHandle() и ReleaseHandle() с подсчетом ссылок и детерминированный метод FlushAll() для полной очистки кэша. Хэндлы создаются при первом запросе и повторно используются на последующих тиках, что сокращает задержку при запуске, позволяет избежать повторного выделения памяти в куче и предотвращает утечки ресурсов терминала благодаря централизованному владению ресурсами.
Метаразметка классических стратегий (Часть 2): Фильтрация сделок по ADX и определение размера позиций Метаразметка классических стратегий (Часть 2): Фильтрация сделок по ADX и определение размера позиций
Пересечение линий DI часто дает сигналы на боковом рынке, где +DI и -DI колеблются без устойчивого преобладания одной из линий. Мы создаем двухслойную гибридную модель: алгоритм выбора гиперпараметров TPE в Optuna оптимизирует фильтр рыночного режима по порогу ADXR, периоду расчета DI и минимальному расстоянию между линиями DI, чтобы максимизировать точность (precision) сигналов на отложенном валидационном интервале; затем случайный лес использует одиннадцать признаков, рассчитанных на основе ADX, для допуска входов в рынок или определения размера позиций с помощью afml.bet_sizing. Полученная модель отфильтровывает всплески сигналов на боковом рынке и калибрует размер позиции при торговле EURUSD на H1.