алгоритм «гусеница»

МГК, как много в этом слове.

По теме сказать нечего :)

wtf МГК?

метод главных компонентов вестимо (<соврал>какое-то разложение ковариационной матрицы</соврал>). Он как-то используется в гусенице. В интернетах были реализации, на Matlab/Octave должно быть не очень сложно.

PS Новосибирск наталкивает на мысль об НГТУ/АВТ, угадал?

Не совсем:) НГУ/ФИТ:)

Люблю такие штуки.)

Фактически этот алгоритм - вариация на тему преобразования Карунена-Лоэва (можно погуглить Karhunen-Loeve Transform).

Если коротко, PCA (Principal Component Analysis) - это разложение по собственным векторам матрицы ковариаций.

В твоем случае есть пара нюансов:

1) Обычно матрица ковариаций (<> - означает усреднение): COVij=<Xi*Xj>-<Xi>*<Xj>. В "Гусенице": COVij=<Xi*Xj>. Это хитрая вещь, так как мой скромный опыт говорит о том, что проще интерпретировать матрицу корреляций COVij=<Xi*Xj>/(<Xi>*<Xj>).

2) В классической постановке задачи PCA мы стартуем от вектора случайных величин. Т.е. предполагается, что у нас есть несколько реализаций случайного процесса по которым можно набрать статистику. В "Гусенице" ты выбираешь из длинного сигнала куски, последовательно смещаясь. Ползешь.) Обрати внимание, точно таким же образом вычисляется автокорреляционная функция!

A(tau)=1/T*int(f(t)*f(t+tau), 0...T)

- где f(t) - случайный процесс, int - интегрирование от 0 до T. Тут мы для каждого tau проводим усреднение по по всему сигналу. Фактически, тут зарыта эргодическая гипотеза: усреднение по реализациям считается эквивалентным усреднению по времени. То есть статистические свойства сигнала считаются постоянными.

После получения собственных векторов матрицы ковариаций, авторы алгоритма предлагают разложить по этим векторам исходную матрицу. Свертка матрицы (исходного ряда) с матрицей (собственных векторов матрицы ковариаций) дают матрицу (фактически - это и есть результат преобразования Карунена-Лоэва).) Результат предлагают анализировать (там абзац про кривые Лиссажу, привет!).

Цель анализа - ответить на вопрос. Какие компоненты тебе интересны, а какие - нет? Приняв решение, ты выкидываешь неинтересное и восстанавливаешь матрицу исходного ряда, используя только "интересные" собственные вектора. Восстанавливаешь ряд. Смотришь что осталось. Делаешь умное лицо.

Написано, конечно, очень хитро. И в этом я вижу обман трудящихся. За исключением пары нюансов, этой процедуре лет 100.

Помог?)

Меня тут понесло слегка. Тебе, наверное, просто хотелось узнать как этот алгоритм реализовать?

Извини. В двух словах:

Так как придется много работать с матрицами, я бы стартовал от надежной библиотеки, реализующей линейную алгебру. В таких задачах FORTRAN может быть адекватным выбором, кстати.

1) Как из исходного сигнала сделать матрицу - ясно. С матрицей ковариаций сложности, я думаю, не возникнет (в методичке очень лаконичная формула). Однако, я обычно туплю в такие моменты. Помни, что тебе нужно сделать из матрицы M на k, матрицу M на M.)

2) Алгоритм нахождения собственных векторов и собственных значений - это золотая классика. Процедура отлично описана в Numerical Recipes In C. При выборе конкретного алгоритма, помни: матрица ковариаций - симметричная! Можно сначала привести к тридиагональной форме с помощью отражений Хаусхолдера (Householder) и потом использовать QR алгоритм с неявными сдвигами. Там просто куча вкусностей.)

3) Сложности на этом заканчиваются. Дальше тебе нужно будет свертывать матрицы направо и налево. Следуй своим инстинктам.)

Помог!)

За второй пост огромное спасибо (после прочтения первого я был в культурном шоке =) ), часть конечно не понятно, но когда 2 интерпритации разных уже проще разобраться. Реализация планируется на c/c++ + QT(кроссплатформенность нужна). А алгоритм нужен для нахождения наиболее встречаемых слов (хороших) среди тех которые всегда встречаются с какой-то частотой. Спасибо.

Numerical Recipes - говно. GSL тебе в помощь