Блог

Допустим, у нас есть матрица N x M, где N — количество записей в данных временных рядов, а M — столбцы, содержащие наблюдения за каждый период. Какие относительно эффективные методы доступны для поиска коррелированных столбцов, когда N исчисляется тысячами, а M (наблюдений) может исчисляться десятками тысяч? Я знаю, что эта проблема может подпадать под «коинтеграцию».

Я знаю о некоторых других сообщениях на SO о корреляции, но я сосредоточен на огромном размере задачи здесь, с тысячами столбцов. Очевидно, что эффективный алгоритм является отправной точкой, но помимо этого существуют ли дополнительные «хитрости» и методы, которые могут уменьшить проблемное пространство на порядки?

Хорошо, сложность наивного решения O(N * M^2)

Поскольку ваш вопрос очень открытый, я пойду с PCA

1. Вы могли бы начать с того, что ваши данные создают корреляционную матрицу O(N^2 * M) (в десятки раз быстрее), если вы предполагаете некоторую регулярность, вы могли бы вычислить эту корреляцию, используя случайное подмножество столбцов, возможно, уменьшая еще один порядок величины.
2. Затем вы извлекаете собственные векторы, связанные с наибольшими собственными значениями. Вы можете извлечь их все со сложностью O(N^3) , использование SVD может быть полезно для частичной декомпозиции.
3. Вычислите D x M представление с уменьшенной размерностью со сложностью O(M * N * D) (по одной корреляции с каждым из D основных компонентов)
4. Выполните поиск по парам O(M^2 * D) , вычисляя корреляции со сложностью O(D) в вашем пространстве с уменьшенной размерностью.