Мы продолжаем тему, начатую в предыдущей статье, там же вы найдете список всех статей по numpy-программированию. Здесь же мы будем искать наиболее часто встречающиеся последовательности, для этого нам потребуется массив последовательностей m, а также векторы distance, a и b, полученные в указанной статье. Если забыли, как мы их вывели, то не стесняйтесь заглянуть туда, чтобы освежить память.
Первое, что мы можем сделать, уполовинить вектор расстояний, выбрав половину наименьших расстояний:
Напомню, что длина вектора расстояний равна длине матрице последовательностей, поэтому использование индексов вектора расстояний, позволяет потом эти индексы использовать для матрицы. По этой причине мы используем argsort, способ разделения на части был описан здесь.
Для получения близких значений последовательностей мы будем использовать функцию isclose, похожую функцию мы рассматривали в этой статье. Для этой функции нам потребуется средняя точка, от которой мы будем искать близкие последовательности. Эту среднюю точку мы можем получить по аналогии с определением расстояния, только для расстояния нам нужно было определить разницу (diff), а сейчас получим среднее (mean). Еще для функции isclose потребуется параметр близости. Его можно вычислить, например, поделив расстояния на максимальное значение в исходном векторе, но мы возьмем определенное значение 0.3 (30%), исходя из логических соображений. Для каждой конкретной задачи этот параметр будет иметь свое значение.
Первой проблемой функции isclose является то, что она возвращает булево значение (близко ли?), но эта проблема решается использованием маски, то есть функция будет маской для матрицы последовательностей, указывая на близкие значения.
Второй проблемой этой функции будет то, что мы можем подставить только один центр, а не матрицу лучших центров. Одним из решений прохода по всем центрам будет цикл, но это недопустимо в матричном программировании. Для решения второй проблемы, numpy имеет целый ряд функций, которые работают наподобие map в python. Здесь мы используем функцию vectorize.
Настало время написать функцию max_closest:
На вход подается вектор исходных последовательностей и размер окна, как и в предыдущей статье, а вот последний параметр rtol содержит параметр относительной близости. Возвращает функция, два параметра: максимальное количество схожих последовательностей и массив центров, которые имеют максимальное количество схожих последовательностей (их может быть несколько).
В первой строке мы находим число строк матрицы со скользящим окном, во второй получаем эту самую матрицу. В третьей строке получаем индексы для вектора расстояний, который вычисляется в четвертой строке. В пятой строке получаем половину вектора расстояний, а в шестой - вектор половины расстояний, отсортированных по убыванию. В седьмой строке получаем матрицу центров наименьших расстояний.
Восьмая строка формируют функцию, которая будет возвращать количество близких последовательностей, для этого мы должны с помощью функции isclose определить какие строки из матрицы скользящего окна являются близкими каждому центру из матрицы центров. Результат функции isclose подставляется в виде индексов в матрицу скользящего окна (объяснение смотрите выше). Так как нам нужно только количество строк, то берем нулевой индекс shape.
В девятой строке находим наибольшее количество схожих последовательностей. Это значение возвращается в качестве первого выходного параметра, но также используется для получения массива центров с максимальным количеством близких точек.
Если передать в эту функцию наш исходный вектор с длиной окна 3 и коэффициентом схожести 0.3, то получим 3 центра, у которых будет 5 близких последовательностей. Ниже проиллюстрировано пять схожих последовательностей первого центра:
Это не самый лучший алгоритм поиска последовательностей, зато его удалось объяснить за несколько статей. Но самое главное: мы с вами обошли ограничение на использование циклов с помощью функции vectorize. Мы два раза использовали уменьшение длины, узнали много новых функций numpy. Надеюсь было понятно и интересно.