April 2, 2013

XVIDEOS' Entire Video Databaseでk近傍法

k近傍法(k-NN)はクエリと似ているk個の訓練データからクラスを決定する手法.最近傍探索のアプリケーションのひとつ.すごく単純.実装もすごく簡単.回帰や次元削減にも使える.ただ,単純に線形探索する場合,データの数が増えるとその分計算も大変(O(Nd); Nは訓練データ数, dは次元数).なので色々高速化・効率化のアルゴリズムも提案されている(→最近傍探索2011 | Preferred Research).

が,250万件くらいなので線形探索でk近傍法を試してみる.クロスバリデーションしようと思ったら大変だけど...結果が面白そうだったら改良手法も試す.

k近傍法.k=3だったら赤,k=5だったら青に分類される(Wikipediaより)

  • 類似度はJaccard係数を使います.
    $$J(A,B)=\frac{|A \cap B|}{|A \cup B|}$$
  • データはMongoDBに突っ込んでからpymongoで操作します.

MongoDBとpymongo


まずターミナルからMongoDBの起動.

$ mongod

pymongoでxvideosデータベースのvideosコレクションにxvideos.com-db.csvのタイトルとタグ,ジャンルをぶち込む.



k近傍法


この例だと,['shower', 'morning', 'toy', 'sexy']というタグに対して近いデータ10件を集めて,多数決でのジャンルを決める.ちなみに結果は「Sexy」.




関連