Как ускорить попарную нормализованную корреляцию в тысячу раз.
Нормализованная корреляция - это вычисление скалярного произведения двух последовательностей, деленного на произведение их длин.
C(si,sj) = sumk=1..L[siksjk/(|si| |sj|)]
Если длина последовательности 1000, а последовательностей тоже 1000, то всего получается 1000*1000*(1000-1)/2=499500000 умножений и чуть меньше сложений. То есть, сложность O(LN2). Здесь L - длина последовательности, а N - их количество
Если мы можем выделить некую существенную часть из каждой последовательностей, и некое вычисление над этими частями дает приближение к корреляции, то мы можем отфильтровать заведомо плохие пары. Если сия существенная часть вычисляется быстро или может быть вычислена зараннее.
В принципе, последовательности можно условно разделить на две категории - хорошие и плохие. Для хороший последовательностей очень просто вычислить существенную часть, для плохих - тяжело. Плюс, плохие последовательности, скорее всего, слабо коррелируют с самими собой, сдвинутыми по времени.
Хорошие последовательности имеют спектр вида 1/f - "розовый" шум или даже красный шум, с большими низкими частотами и амплитуда частоты (примерно) уменьшается с её возрастанием. Низкие частоты вносят большой вклад в корреляцию, поэтому разумно брать их в качестве существенной части.
Плохие последовательности имеют спектр вида 1 - "белый" шум, где все частоты представлены равномерно. Это производная "красного" шума. Здесь существенную часть выбрать сложно, ведь корреляция по одной частотной составляющей может быть перекрыта любыми другими частотами.
Если говорить о практической пользе, то "хорошие" последовательности наблюдаются в колебаниях цен на продукты, а "плохие" - в "выгоде", (ценаi+1-ценаi)/ценаi.
Ну, как уже было сказано, если взять пяток-другой (десяток-другой) коэффициентов разложения Фурье последовательностей с меньшими частотами, то можно примерно предсказать коэффициент нормализованной корреляции для двух последовательностей.
С плохими последовательностями такой трюк не пройдет.
Для плохих последовательностей не работает даже разложение по сингулярным значениям (это квадраты собственных значений).
Но для них придумали особый подход - проекции на случайные вектора.
Мы генерируем псевдослучайные последовательности, числом M и длиной L, со значениями 1 и -1, и выполняем с ними свертку всех последовательностей. Получается вектор длиной M, sketch vector, набросок.
Так вот, доказано, что расстояние между нормализованными векторами-набросками пропорционально корреляции между последовательностями: D(x, x) = 2(1+corr(x,y)). D - расстояние, x - временная последовательность, x - нормализованный вектор-набросок. Отсекая по расстоянию, мы отсекаем по корреляции. Можно отсечь все с корреляцией менее порога (колебания цены на схожие продукты), можно отсечь все с корреляцией выше порога (конкурирующие компании).
Все. Остались только технические вопросы - как сделать подходящий генератор псевдослучайных чисел, как считать побыстрее в процессе добавления элементов в последовательности и тп. Это, натурально, решается очень просто.
C(si,sj) = sumk=1..L[siksjk/(|si| |sj|)]
Если длина последовательности 1000, а последовательностей тоже 1000, то всего получается 1000*1000*(1000-1)/2=499500000 умножений и чуть меньше сложений. То есть, сложность O(LN2). Здесь L - длина последовательности, а N - их количество
Если мы можем выделить некую существенную часть из каждой последовательностей, и некое вычисление над этими частями дает приближение к корреляции, то мы можем отфильтровать заведомо плохие пары. Если сия существенная часть вычисляется быстро или может быть вычислена зараннее.
В принципе, последовательности можно условно разделить на две категории - хорошие и плохие. Для хороший последовательностей очень просто вычислить существенную часть, для плохих - тяжело. Плюс, плохие последовательности, скорее всего, слабо коррелируют с самими собой, сдвинутыми по времени.
Хорошие последовательности имеют спектр вида 1/f - "розовый" шум или даже красный шум, с большими низкими частотами и амплитуда частоты (примерно) уменьшается с её возрастанием. Низкие частоты вносят большой вклад в корреляцию, поэтому разумно брать их в качестве существенной части.
Плохие последовательности имеют спектр вида 1 - "белый" шум, где все частоты представлены равномерно. Это производная "красного" шума. Здесь существенную часть выбрать сложно, ведь корреляция по одной частотной составляющей может быть перекрыта любыми другими частотами.
Если говорить о практической пользе, то "хорошие" последовательности наблюдаются в колебаниях цен на продукты, а "плохие" - в "выгоде", (ценаi+1-ценаi)/ценаi.
Ну, как уже было сказано, если взять пяток-другой (десяток-другой) коэффициентов разложения Фурье последовательностей с меньшими частотами, то можно примерно предсказать коэффициент нормализованной корреляции для двух последовательностей.
С плохими последовательностями такой трюк не пройдет.
Для плохих последовательностей не работает даже разложение по сингулярным значениям (это квадраты собственных значений).
Но для них придумали особый подход - проекции на случайные вектора.
Мы генерируем псевдослучайные последовательности, числом M и длиной L, со значениями 1 и -1, и выполняем с ними свертку всех последовательностей. Получается вектор длиной M, sketch vector, набросок.
Так вот, доказано, что расстояние между нормализованными векторами-набросками пропорционально корреляции между последовательностями: D(x, x) = 2(1+corr(x,y)). D - расстояние, x - временная последовательность, x - нормализованный вектор-набросок. Отсекая по расстоянию, мы отсекаем по корреляции. Можно отсечь все с корреляцией менее порога (колебания цены на схожие продукты), можно отсечь все с корреляцией выше порога (конкурирующие компании).
Все. Остались только технические вопросы - как сделать подходящий генератор псевдослучайных чисел, как считать побыстрее в процессе добавления элементов в последовательности и тп. Это, натурально, решается очень просто.