Sunday, November 28, 2010

Сингулярное разложение SVD

Есть такая тема в линейной алгебре, которую почему-то упорно игнорируют в институтах. Называется она сингулярное разложение матрицы или, на английском, Singular Value Decomposition. По-сути, сингулярное разложение матрицы это способ разложить матрицу в серию последовательных приближений, тем самым раскрывая её внутреннюю структуру. Используется это во множестве областей таких как text mining, обработка сигналов, сжатие изображений и пр.
Что это такое, я расскажу на примере котировок на бирже. Допустим у нас есть набор котировок в конце дня для нескольких акций.

GAZP AVAZ SBER
2.11 170.16 102.35 35.36
3.11 170.19 103.3 35.65
8.11 174.2 103.95 36.27
9.11 176.1 103.59 37.4
10.11 174.47 100.44 36.9
11.11 172.6 98.4 35.19
12.11 171.88 97.94 33.6
13.11 171.69 97.8 32.95
15.11 171.79 99.2 32.96
16.11 169.57 95.26 29.81
17.11 168.81 97.2 35.8
18.11 170.7 99.66 33.8
19.11 172.2 98.7 33.5

Нас мало интересуют сами котировки, поэтому имеет смысл привести их к общему знаменателю. Будем рассматривать выручку от инвестиций в процентах, по формуле

Ri = 100% * (Vi – Vi-1)/Vi

Это не совсем корректно с финансовой точки зрения, но для наших целей сойдет:

GAZP AVAZ SBER
0.16 0.49 0.02
0.02 0.93 0.83
2.36 0.63 1.74
1.09 -0.35 3.12
-0.93 -3.04 -1.34
-1.07 -2.03 -4.64
-0.42 -0.47 -4.53
-0.11 -0.14 -1.92
0.06 1.43 0.01
-1.29 -3.97 -9.54
-0.45 2.04 20.1
1.12 2.53 -5.59
0.88 -0.96 -0.88


Так вот, математики утверждают, что любую матрицу можно разложить в произведение трех матриц:

A = U*W*VT               (1)

где U и V – ортогональные матрицы, а W – диагональная матрица. Причем, хитрые математики предпочитают когда все отсортировано, поэтому диагональные элементы матрицы W располагаются в порядке убывания. Это и есть сингулярное разложение или SVD. В нашем случае оно будет иметь вид:


0 -0.08 0.02
0.04 -0.12 0.12
0.08 -0.21 -0.71
0.12 0.05 -0.45
-0.07 0.48 -0.11
-0.2 0.26 0.12
-0.19 -0.01 0.13
-0.08 -0.02 0.04
0.01 -0.22 0.19
-0.41 0.45 -0.02
0.82 0.2 0.17
-0.21 -0.58 0.07
-0.04 0.06 -0.41
*
24.51 0 0
0 6.09 0
0 0 2.79

*
0.02 0.15 0.99
-0.4 -0.9 0.14
-0.92 0.4 -0.04

Диагональные элементы wk матрицы W называются сингулярными числами. Столбцы матрицы U называются левыми сингулярными векторами {uk}, и т.к. матрица ортогональна, то эти векторы формируют ортонормированный базис. Т.е. ui*uj = 1 только если i=j, во всех остальных случаях ui*uj = 0. Строки матрицы V называются правыми сингулярными векторами {vk} и формируют другой ортонормированный базис. Теперь мы можем переписать наше равенство (1) в виде:
Ar = Σk=1r(uk * wk * vkt)
Причем Ar гарантированно является наиболее точным приближением матрицы A среди всех матриц с рангом r.

Это очень важное свойство. Теперь, удаляя наименьшие (т.е. последние) сингулярные числа и проводя обратное преобразование, мы можем эффективно убирать шумы из наших данных. На этом построены, например, некоторые способы улучшения и сжатия изображений.

В некотором смысле, SVD разложение напоминает Фурье-преобразование. Только если в Фурье-преобразовании нам заранее задан набор базисов относительно которых мы раскладываем нашу функцию. То здесь базисы выбираются исходя из степени их влияния на результирующую матрицу.

Перейдем теперь к более реалистичному примеру. Для него я взял дневные котировки 18 крупных российских компаний за последний год (AFLT, AVAZ, BEGY, GAZP, KMAZ, KRSG, LKOH, LSNG, MDMBP, MMBM, ROSB, ROSN, SBER, SIBN, SNGS, TATN, TRNFP, VTBR)
Аналогично примеру выше, применил операцию SVD для этих котировок и получил разложение A = U*W*VT. Получившиеся матрицы слишком большие чтобы приводить их в тексте, для желающих повторить эксперимент, данные можно взять тут.


Рассмотрим матрицу V, особый интерес в ней для нас представляют первые столбцы. Ведь помните, что в матрице W диагональные значения отсортированы и, стало быть, во всем этом произведении U*W*V Наибольшее значение имеют первые столбцы матрицы U и первые строки матрицы VT (т.е. столбцы матрицы V) Более того, строки матрицы V соответствуют отдельным компаниям (это простое следствие закона произведения матриц) Давайте возьмем первые три столбца полученной матрицы V и отметим соответствующие точки на графике:





Здесь, на рисунке, цвета точек определяются принадлежности соответствующей компании той или иной отрасли. Например, мы видим, что нефтегазовый сектор (синий цвет) очень плотно сгруппировался в правом нижнем углу. Российский автопром (красный) находится в стороне от остальных компаний. А вот банковский сектор (голубой) разделился на две группы, одна - крупные банки с большим количеством гос. капитала находятся рядом с нефтегазовым сектором (кто бы сомневался), остальные же банки в стороне. Конкретные значения для каждой компании приведены на рисунке ниже. Думаю, что анализ подобных графиков может открыть много интересного в структуре российского, да и не только российского бизнеса.

Матрица U является более интересной с точки зрения временной характеристики. Она отражает то, как вели себя котировки той или иной компании в разное время. Сегодня я не буду углубляться в изучение этой матрицы.










P.S. для расчета сингулярного разложения я использовал Java библиотеку Jama - очень простая, надежная и удобная библиотека, единственный недостаток - не поддерживаются разреженные матрицы, что не значительно в нашей ситуации, но может быть очень важно если SVD используется для анализа текста (об этом я расскажу чуть позже). Кроме того, сингулярное разложение умеют выполнять многие математические пакеты, такие как Mathcad или Mathematica. О другом и, пожалуй, самом известном применении SVD латентно семантическом анализе я напишу в ближайших постах.

1 comment:

  1. Ортогональная матрица => квадратная, а U не квадратная.
    в одной библиотеке U - прямоугольная и Ut * U = E, а U * Ut <> E

    Как то странно)

    ReplyDelete