В этот раз в серии статей по numpy-программированию мы будем решать практическую задачу. Предыдущие статьи нашего сериала:
- Numpy для продвинутых
- Продолжаем numpy-программирование для продвинутых
- Создаем скользящее окно без циклов
- Перебор значений без циклов
- Поиск локального максимума с помощью numpy-программирования
- Numpy для работы с координатами прямоугольников
- Отличие матричного программирования от numpy-программирования
- Numpy: вычисление разницы каждого элемента вектора с каждым.
В этой статье мы займемся выявлением паттернов, в нашем случае это будет поиск повторяющихся числовых последовательностей. Сложность заключается в том, что числовые значения могут не совпадать, но быть близкими. Насколько близкими они должны быть?
Для объяснения решения этой задачи, мы возьмем последовательность из двух чисел. На самом деле, два числа это слишком мало, так как повторение двухчисловой последовательности может быть случайностью, но нам нужно понять суть. Первое, что приходит в голову, когда мы говорим о двухчисловой последовательности, это - координаты точки, следовательно близость двух точек это - отрезок (вспоминаем геометрию). Как посчитать расстояние между двумя точками? Вряд ли кто вспомнит формулу евклидова расстояния, но все помнят теорему Пифагора. Как нам посчитать катеты треугольника? Отнимаем координату по Х конца от координаты по Х начала, так мы получим горизонтальный катет. Вертикальный катет получим, вычитая Y конца из Y начала. Расстояние между точками будет равно сумме квадратов разностей координат точек.
Подобная логика будет сохраняться и для последовательности из 3 чисел. Мы можем представить это как отрезок в трехмерном измерении. Самое интересное, что это можно использовать для последовательностей из 4, 5, 6 и т.д. чисел.
Что нам дает вычисление расстояния между точками? Мы можем найти самые близкорасположенные точки, и ответить на вопрос насколько близко должны быть точки друг от друга, но самое главное, мы узнаем какие числовые последовательности ближе всего расположены, то есть повторяются.
Теперь перейдем от теории к практике. Для наглядности возьмем числовой ряд: 70, 69, 72, 52, 6, 65, 65, 51, 60, 92, 56, 6, 72, 38, 21, 30, 21, 4, 84, 31. Нужно найти наиболее близкую повторяющуюся последовательность из трех чисел. Для начала сделаем матрицу со скользящим окном равным 3. Как это делается было объяснено тут. В результате получаем матрицу размером 18, 3 (из 20 элементов мы можем получить только 18 трехчисловых последовательностей). В предыдущей статье мы рассматривали способ сравнения каждого элемента с каждым. Разница лишь в том, что там был вектор, а тут будет матрица. Вдобавок нам нужно не просто вычесть координаты, но возвести их в квадрат, квадраты сложить построчно, после чего получить квадратный корень на каждую строчку. Оформим все это в виде функции min_distance:
Первые две строчки функции объяснены в статье про скользящее окно, третья строка - в статье про разницу каждого с каждым. Четвертая строка вычисляет расстояние каждого элемента с каждым. И можно было бы этот вектор передать как результат, но нам бы хотелось еще и увидеть два этих близких трехчисловых элемента. Для этого найдем индекс минимального расстояния (5 строка функции), который нам понадобится, чтобы получить индексы из промежуточных векторов a и b, которые будут индексами близких элементов в матрице m. То есть возвращать функция будет не только вектор расстояний между всеми элементами, но и две числовые последовательности схожие друг с другом:
Это еще не полноценный поиск паттернов, так как мы нашли только две самые близкие последовательности. В следующей статье мы продолжим с этого места. Так что ждите, продолжение следует.