Comments 16
Преобразование Фурье(ПФ) тоже дает разложение вектора (матрицы) на ортогональные составляющие. При этом БПФ во много раз быстрее Метода Главных Компонент -Преобразование Карунена — Лоэва (также известно как преобразование Хотеллинга(МГК) .
Например, для размерности 1000 выигрыш в скорости вычисления составит примерно два порядка.
Есть ли доказательства, что МГК эффективнее, чем ПФ для уменьшения размерности данных?
Если знаете, дайте ссылку.
Есть ли доказательства, что МГК эффективнее, чем ПФ для уменьшения размерности данных?
Это зависит от того, что вы понимаете под эффективностью. PCA даёт наименьшую среднеквадратичную ошибку для оценки (данных с уменьшенной размерностью). Это следует просто из того факта, что норма Фробениуса матрицы может быть посчитана через её сингулярные числа, а в методе PCA отбрасываются наименьшие сингулярные числа.
Подробнее можно тут почитать, допустим.
Если вы под эффективностью понимаете вычислительную сложность либо какую-то другую метрику, то я не знаю.
Изложу свою точку зрения.
ПФ тоже дает наименьшую среднеквадратическую ошибку.
В PCA мы ищем ортогональные функции, которые аппроксимируют исходные данные. Критерий поиска -минимум среднеквадратической ошибки. Потом мы из этих функций выбираем с наибольшим вкладом по фактически надуманному критерию.
В ПФ все совершенно точно также, за исключением лишь одного. Мы априори задаем форму ортогональных функций, и таким образом существенно сокращаем сложность задачи.
БПФ позволяет нам решать задачу со скоростью пропорциональной N*log2(N). PCA имеет сложность N^2. Т е скорость вычисления в N/log2(N) у БПФ выше. Так как число данных тысячи и миллионы, то ускорение вычислений получается десятки , тысячи раз.
Конечная цель этих преобразований - уменьшить размерность данных. В PCA у нас функции задаются векторами, число элементов которых существенно больше 3, а в ПФ функции заранее известны и фактически задаются тремя коэффициентами. Получается, что ПФ даете более компактное представление данных чем PCA. А это и есть цель применения преобразования.
Меня интересует есть ли публикации по данному сравнению. Критерий сравнения - максимальное сжатие данных при одинаковой ошибке принятия решений.
В ПФ все совершенно точно также, за исключением лишь одного. Мы априори задаем форму ортогональных функций, и таким образом существенно сокращаем сложность задачи.
Как раз за счёт того, что ортогональный базис задан априори, ошибка аппроксимации и будет выше. В методе PCA ортогональный базис специально подбирают так, чтобы наименее существенные размерности после отбрасывания внесли наименьшую ошибку.
Самый простой пример, который можно привести -- данные, идеально ложащиеся на некое произвольное подпространство. PCA -- это как раз способ найти такое подпространство (и ошибка аппроксимации в таком случае будет нулевой). А каким образом определить некий базис, чтобы произвольное подпространство в этот базис укладывалось ( чтобы можно было уменьшить размерность) ?
PCA имеет сложность N^2.
Я почему-то считал что сложность SVD порядка N^3, но спорить не буду, N^2 так N^2.
ПФ имеет изначально нулевую ошибку, так как число данных на входе равна числу данных на выходе. А по заданной ошибке производится сокращение размерности.
Но меня собственно интересует информация о сравнительной эффективности сжатия данных. Ответа на свой вопрос пока не нашел. Вы, очевидно, его тоже не знаете.
Как раз за счёт того, что ортогональный базис задан априори, ошибка аппроксимации и будет выше. В методе PCA ортогональный базис специально подбирают так, чтобы наименее существенные размерности после отбрасывания внесли наименьшую ошибку.
Постулат кажется правдоподобным, но для пруфа хотелось бы конкретики, т.е. конкретный набор данных, оценка выигрыша на Python !
А для Фурье не требуется периодичность сигнала? Обычно его для упаковки звука используют, потому что он хорошо на синусоиды раскладывается. Или это только одно из возможных применений?
Можете пояснить за счёт чего предобработка PCA улучшит кластеризацию? Ожидал бы ровно противоположное, что качество кластеризации ухудшится
Почему-то совершенно не упомянуты родственные алгоритмы t-SNE и Truncated SVD. Между тем:
Для двумерной визуализации
t-SNEобычно работает лучше, чемPCA. При этом для моделей машинного обучения всё-равно обычно используютPCA, потому что оно быстрее, а красота разделения для моделей не важна, в отличие от визуализации.Для разреженных матриц, в частности получающихся при векторизации текстов, например при помощи упомянутого в статье
TfidfVectorizer, лучше использовать алгоритмы, умеющие в эти самые разреженные матрицы, например,Truncated SVD. Это экономит кучу памяти, а заодно и времени.
Полагаю, что все методы сжатия данных, в которых применяется среднеквадратическая ошибка будут плохо работать , когда классы данных различаются неочевидным образом.
Так как такое сжатие приводит в выкидыванию мелких признаков, которые в большинстве задач диагностики и являются информационными.
PCA как и другие методы возможно эффективен, если надо различить квадрат красного цвета от зеленого, но мало что даст,если зеленый будет с желтыми точками. Эти точки PCA и выкинет по методу наименьших квадратов.
Можете прокомментировать "Реализация РСА. Пример 3"? Там сказано про улучшение кластеризации, но я увидел тоже самое, только сбоку.
Как применять метод PCA для уменьшения размерности данных