特異値分解とは
特異値分解 (SVD)はPCAとほとんど同じと思ってください。SVDはPCAが適用できないような行列に対して、データ削減や特徴抽出が可能な方法となります。
PCAを行う行列は正方行列であり、ランクがフルである、つまり逆行列を持つ正則行列である必要がありました。SVDでは疑似逆行列を利用するので正方行列ではない行列やランク落ちしている行列からでも、計算処理が可能となります。
MAT_A = \begin{pmatrix} a & b \\ c & d \\ \end{pmatrix}正則行列は、逆行列を持つ正方行列を指します。正方行列とは上記のようにN x N行列のことで、横と縦の数が一致した行列を指します。
データは常に正則行列であるとは限りません。PCAは正則行列である必要がある制約条件がありました。SVDは疑似逆行列を利用することで、PCAに似た計算処理を可能にするのです。
SVDはどんな時に用いられるのか
SVDが必要な背景としては、例えば推薦システムなどで用いられます。推薦システムは例えばユーザに映画を紹介したい、あるいはユーザに商品を紹介したい等のシステムです。この際に、ユーザー数と映画数が同じでないと計算上不都合が生じてしまうのです。実際には要素数が同じなどありえません。そこで、疑似行列を使った処理(SVD)を用いる、ということです。
どのようにしてSVDを用いて推薦システムを作るのか解説していきます。
SVDによる推薦システム
今ユーザー3名が5つの映画にそれぞれ次のような評価をつけたとします。
review_user1 = [1,4,5,4,5] review_user2 = [1,3,1,4,4] review_user3 = [1,2,5,4,1] mat = numpy.array( [review_user1, review_user2, review_user3 ] )
上記のデータをSVDします。numpyのライブラリを使うことで一発で求まることができます。
def learn( mat ): u,s,v=numpy.linalg.svd( mat ) return [u, s, v]
U, S, Vが求まりました。この関係ですが、元の行列matはU S V^tで求めるように分解をしています。Sは 対角行列 となっており、対角成分に特異値が並んでいます。対角成分は左上が最大で右下が最小となるようになっています。なんだか面白い行列が出てきました。
さて、このUSVを求めたら類似度はどのように求まるかというと、つぎのようにすれば求まります。eには現在自分の映画5個における評価を入れておきます。e= numpy.array([1,5,4,4,5])
def getSimilar( usv, e, dim =2): u, s, v = usv vv = numpy.array( numpy.matrix(v).T ) U = numpy.matrix( u[ :, 0:dim ] ) V = numpy.matrix( vv[ :, 0:dim ] ) S = numpy.matrix( numpy.diag( s[:dim] ) ) E = numpy.matrix( e ) pos = E * U * S.I result = [] for i, user in enumerate(V): val = float(user *pos.T) val /= (numpy.linalg.norm( user ) * numpy.linalg.norm( pos )) result.append( [val+1, i ]) return sorted( result, reverse=True )
getSimilar関数はコサイン積をとっています。Dimは次元数という意味で、PCAで言うところの寄与数の高いところ順に内積を取るイメージを取ってください。これにより自分と似ているユーザーが返ってきます。
最後に
実は今紹介したSVDによる推薦システムは、データにSVDを適用し、コサイン積を求めたものでした。推薦システムとしては1つ大きな問題が残っております。それは評価していないアイテム、例えば見ていない映画の評価を0とするとした評価がSVD適用時に考慮されてしまっているということです。見ていないものが、つまらなかった(評価0)は少し辺です。そして、スッカスカの巨大行列をSVDするっていうのは何か違和感があります。そこで評価していないものはスキップするというようなアイディアを取り入れた方法を使う必要があります。これが matrix factorization(MF)という手法になります。Netflixの推薦エンジンのコンペ
で圧倒的なスコアを叩き出したエンジンがまさにMFを使っていました。MFについて、次回ご説明します。
参考文献
https://ja.wikipedia.org/wiki/%E7%89%B9%E7%95%B0%E5%80%A4%E5%88%86%E8%A7%A3