Microsoft Word - deim2016再提出.docx

Size: px

Start display at page:

Download "Microsoft Word - deim2016再提出.docx"

しおりこのえ
5 years ago
Views:

1 DEIM Forum 2016 F2-4 推薦システムにおける文脈適応及び計算時間短縮を実現する切り出し法と構成モジュールの自動合成方式福田正向清木康慶應義塾大学環境情報学部神奈川県藤沢市遠藤 {t13504yf, あらまし E コマース市場の拡大に伴い, Web 上に流通する商品数が増大し, 限られた時間で多数の商品の中からユーザーの嗜好や文脈にマッチした商品を探索することが困難になる情報過多問題が深刻化しているその解決策として推薦システムの研究開発が行われているが, ユーザーの嗜好や文脈に合わせた推薦システムを行うためには計算量が非常に膨大になってしまうという問題がある. 本研究ではこうした問題を解決するために, ユーザーが置かれた文脈に合わせて動的に部分空間選択を行い, ユーザーの文脈に適応した推薦システムを実現し, さらに計算時間を大幅に削減することを可能にする切り出し法という手法を実装し, 実験の結果として大幅に短い計算時間でより高い精度を示した. さらにユーザーの嗜好類型及び状況に合わせて動的に推薦システムの構成モジュールを自動合成するアーキテクチャーを提案する. 切り出し法は他の様々な推薦システム手法と組み合わせて用いることが可能な汎用的なものであり, 今後の推薦システム開発の基盤として活用可能なものである. キーワード推薦システム, レコメンド, 意味の数学モデル, 文脈, 部分空間選択, 計算量削減 1. はじめに膨大な計算時間及び計算資源を要する. 現在, 情報化の進展に伴い, 個人の嗜好は多様化し, 従来のマスマーケティングによる画一的なアプローチでは顧客のニーズに訴求し販売促進を行うことが難しくなっている. 顧客個人のニーズを的確に把握し, それに合わせて最適な商品を推薦する必要がある. いわば潜在需要の発掘が社会的な課題となっている. また, EC 市場やデジタルコンテンツ市場の成長に伴い, インターネット上の商品やコンテンツの量は飛躍的に増大している. これは, インターネットで様々なモノが買えるという意味でユーザーに利便性をもたらす一方, 商品数の急増に対し, ユーザーが購買のための商品探索に使える時間は限られているので本当にユーザーが求める商品に出会いにくくなるという情報過多問題を生み出しつつある. こうした背景から推薦システムの研究が進んでいるが, 大規模 EC サイトなどにおいて, 文脈適応性などの高度な性質を持つ推薦システムが十分に普及しているとは言い難い. 推薦を行これに対する解決策として, 本稿では切り出し法と構成モジュールの自動合成方式という二つの手法を提案する. 一つ目の, 切り出し法は, クラスタリングと部分空間選択を組み合わせて推薦システムの計算時間を大幅に短縮し, かつ文脈に適応した推薦を可能にする手法であり, 協調フィルタリング等の推薦アルゴリズムの前処理として用いることができる. 二つ目の, 推薦システムの構成モジュールの自動合成方式は, 推薦システムの機能特性を決定する各種構成モジュールをその役割ごとに階層化し, 処理手順をレシピとして生成し, ユーザーの嗜好類型や置かれた条件によって最適なレシピを決定する方式である. これにより, 多様な嗜好類型や変化する条件に柔軟に対応できる. 2. 提案手法本稿における提案手法である, 切り出し法と構成モジュールの自動合成方式のそれぞれについて, その概要と具体的手順と期待できる効果を示す. う対象ユーザーを行に, 対象アイテムの列とする行列を仮定すると, 大規模 EC サイトの場合は数千万ユーザーと 1 億点以上のアイテムからなる極めて巨大な行列となる. さらにこれはスパースな行列であることが知られており, 一般的な推薦手法を適用すると非常に 2.1. 切り出し法ユーザーが置かれた文脈に即した推薦を大幅に少ない計算時間で行うことを可能にする前処理手法として, 切り出し法を提案する. 切り出し法は現在広く採用されている推薦手法である協調フィルタリング

2 と特に親和性が高く, 協調フィルタリングを用いた推薦アルゴリズムに文脈適応性を付加し, 計算時間を短縮できる. 図 1. 空間における切り出し法のイメージ切り出し法の概要を説明する. 図 1. にあるように, 前処理としてユーザーの嗜好をクラスタリングした上で, 推薦対象ユーザーの嗜好と最も近い嗜好クラスタ ( 嗜好類型 ) を特定し, さらに直近期間において購買閲覧したアイテムのメタデータ ( ジャンル等 ) を次元とする部分空間を文脈にマッチした部分空間とみなし, その部分空間内で推薦手法の処理を実行することで計算対象のデータ量が大幅に削減される. 文脈に応じて部分空間選択を行い, 文脈に適応した検索を可能にし, 計算量の削減も可能な方式として意味の数学モデル [1] が提案されているまた, 意味の数学モデルとクラスタリングを組み合わせ, 部分空間選択の後にクラスタリングを行うことで意味的知識発見を行う研究 [2] もある. 切り出し法は意味の数学モデルとクラスタリングの組み合わせを推薦システムの前処理手法として応用したものである. 従来の意味の数学モデルとクラスタリングの組み合わせを行う研究との処理的, 機能的な大きな違いは, 従来の手法が部分空間選択をした上でクラスタリングを行うのに対し, 切り出し法はクラスタリングを行った上で文脈に合わせて動的に部分空間選択を行うという処理の順序の違いにより, 推薦処理ごとに毎回クラスタリングを実行する必要がなく, 迅速な推薦処理が可能な点が挙げられる. 図 2. 対象クラスタと対象部分空間で区画されるデータ領域を計算対象として切り出す図 2. のようにユーザーを行に, アイテムを列とする嗜好行列から計算対象となる領域が切り出されるイメージから切り出し法と名付ける. 一般的なユーザーベース協調フィルタリングでは過去の嗜好データ ( 例えば各アイテムへの評価値ベクトル ) が類似しているユーザーの嗜好を基に対象ユーザーの嗜好を推定する. この類似しているというのは嗜好を表現する多次元空間での距離的な近さと考えることができる. この近さを計算するときに従来手法の多くは全ユーザー集合との嗜好空間上の距離計算を行った. 一方, 切り出し法は距離が近いと思われるユーザー集合を求めてそのユーザー集合の中だけで距離計算を行う. さらに, ユーザーが直近の利用履歴を文脈として部分空間選択を行った上で距離計算を行うために計算量がさらに削減され, さらに, より文脈に即した推薦が可能である. 例えて言えば, ある人が咳や熱などの症状を認識し病院を探すとき, 全国の病院の中から探すのではなく住んでいる都道府県の病院を探すはずである. また, 咳や熱という症状はいわば文脈でありそれらと関連の低い診療科は考慮から外して病院を探すであろう. 切り出し法においてもまずは自分に近いクラスタを探す. その際にクラスタの重心との距離計算を行うのはいわば都道府県の県庁所在地と自宅との距離を計算するのに似ている. さらに文脈に即した部分空間選択を行うのは病気の症状に照らして診療科を絞るのと似ている. つまり, 切り出し法は人間が探索行動を取る際の思考処理の流れとよく似た, 自然な手法であると言える. 切り出し法のベースとなる洞察についてここで触れておくと, 人間の嗜好には長期に渡って変化しにくい嗜好と, 短期的に文脈に応じて変化する嗜好があり, その二層構の嗜好に基づいて購買意思決定が行われていると仮定している. この長期において変化しにくい嗜好を計算するのが嗜好空間の全空間上でのクラスタリングに対応し, 短期的に変化する文脈に応じた嗜好の計算に必要な処理が直近の閲覧使用履歴等に基づく部分空間選択である. 人間の嗜好の本質について考え, それに基づいて考案したのが切り出し法であり, 極めて自然な方法であると考える. 自然であるがゆえにシンプルであり, 実装コストも比較的低く, また, 他の手法と柔軟に組み合わせることができると考える. 以下では説明の便宜上, ユーザーベースの協調フィルタリングをベースとして具体的な手法の手順を説明する. Step1: サンプリング過去のユーザーとアイテムに対する評価値を蓄積したデータベースから, 一定数のユーザーをサンプルとしてランダムに抽出する.

Step2: クラスタリングユーザーを行とし, アイテムのメタデータ ( 本稿では映画のジャンルを用いる ) を列とし評価値を成分とする嗜好行列を仮定する. アイテムのジャンル等のメタデータを列することで行列のスパース性が抑えられる. さらに, 嗜好行列に対してクラスタリングを実行し, 各ユーザークラスタの重心ベクトルを取得し保存する.

3 Step2: クラスタリングユーザーを行とし, アイテムのメタデータ ( 本稿では映画のジャンルを用いる ) を列とし評価値を成分とする嗜好行列を仮定する. アイテムのジャンル等のメタデータを列することで行列のスパース性が抑えられる. さらに, 嗜好行列に対してクラスタリングを実行し, 各ユーザークラスタの重心ベクトルを取得し保存する. Step3: 対象ユーザーの最近傍クラスタの特定推薦を行う対象のユーザーの映画の評価値のジャンルごとの平均を成分とする嗜好ベクトルを求め, Step2 で求めたユーザークラスタの重心との距離を算出し, 最近傍クラスタを特定する. Step4: 対象ユーザーの文脈抽出と部分空間選択対象ユーザーの最近見た映画のジャンルの集合をユーザーの映画鑑賞における文脈とみなす. 対象ユーザーが直近 n 週間鑑賞した映画のジャンルを次元とする部分空間として選択する. この部分空間はユーザーの文脈に対応したものである. 選択された部分空間内において, 協調フィルタリングなどの既存の推薦手法を適用する. 以上の, 切り出し法により, 文脈に適応した推薦が大幅に少ない計算量で可能になる. Step5: 部分空間上において協調フィルタリングなどの推薦手法を適用選択された部分空間内において, 協調フィルタリングなどの既存の推薦手法を適用する. 以上の, 切り出し法により, 文脈に適応した推薦が大幅に少ない計算量で可能になる切り出し法の効果 1) 文脈に適応した推薦を可能にする 2) データ領域を絞り込むことで, 計算時間を短縮する切り出し法を推薦システムの前処理部に組み込むことで, 推薦システムが文脈適応可能なものとなり, また計算時間も大幅に短縮される. 多様なアルゴリズムと柔軟に組み合わせて使うことができ, シンプルな構成なので実装コストも比較的低いため費用対効果の高い手法だと言える推薦システムの構成モジュールの自動合成方法推薦システムを構成するモジュールを自動的に合成し, ユーザーの嗜好類型や置かれた状況や条件に適した推薦システムの構築の自動化手法を提案する. 従来, 単一の推薦システムをあらゆるユーザーやその状況に対して適用されてきた. しかし, ユーザーの嗜好の多様化や急な変化, またグローバル化による市場の拡大に伴うユーザーの国籍や民族, 文化的多様性の増大により, それら多様なユーザーの嗜好類型やユーザーの置かれた状況や条件に適応して柔軟に推薦システム自体の機能や構を変化させる必要が生じている. 推薦自体の自動化が推薦システムであるのに対し, 本手法は推薦システム自体の構成変化を自動化する. 図 3 推薦システムのレシピ探索図 3 は本手法のイメージを示している. 推薦システムの手法や処理の流れを階層化し, 各レイヤーは機能的には同一または類似した性質を持つ手法及びモジュールであり, レイヤーごとに手法及びモジュールの選択を行い, それら手法及びモジュールの組み合わせのパスをレシピと呼ぶ. このアーキテクチャーは人工知能の研究のプランニング領域の手法として知られる階層的タスクネットワーク [5] に近い考え方を推薦システム構築に応用したものだと言える. レシピによって推薦システムの性質や特徴が異なり, ユーザーの嗜好類型ごと, また置かれた条件や状況ごとに最適なレシピを探索する手法を示す. 以下に本手法の具体的な手順を示す. Step1: 推薦システムを構成する処理を実行するモジュールを実装する. 推薦システムを構成するモジュール, 例えば類似度計算や回帰分析のような機能を有するモジュールを複数個実装する. 類似度計算には内積やユークリッド距離や相関係数など複数の手法が考えられるが, それぞれをモジュールとして他の処理が可能なモジュールと組み合わせられる形で実装する. Step2: 役割的に共通するモジュールを整理して処理の順に階層化. 図 3 のように, 役割的に共通するモジュールをまとめて, 順に並べた木構造を形成する. Step3: モジュールを組み合わせてレシピを生成する. 多重ループなどの方法で各階層からモジュールを選択しレシピとして一連のパスを作る. Step4: ユーザーの類型や条件のそれぞれに対して各

4 レシピをテスト. 性別や年齢, またはユーザーの嗜好クラスタなどで分類できるユーザーの類型や, あるジャンルから商品を探そうとしているなどの条件の組み合わせに対して各レシピで推薦を行うテストを実行する Step5: ユーザーの類型や条件に対して最も精度の良いレシピを記録し, 今後は同じ類型同じ条件のユーザーにそのレシピを適用する. テストの結果として最も精度の良かったレシピを対象のユーザーの類型や条件に対して最適なレシピだとして記録する. 今後, 同じ類型のユーザーが同じ条件にある場合に最適なレシピに基づく推薦システムで推薦を行う構成モジュールで自動合成方式の効果各階層にモジュールを追加することで, 非常に多様な推薦システムを自動的に合成することができる. これにより, 嗜好の時間的変化やユーザーの多様性や状況の変化に柔軟に適応できる. 3. 実現方式ここでは, 提案手法の切り出し法を実現する方式としての今回実装したシステムの構築手順を解説する. 本システムは切り出し法の有効性を検証する目的で MovieLens100k [4] という映画の評価値のデータセットを用いて評価値予測を行う.MovieLens100k の概要を以下に整理する. 表 1. MovieLens100k の概要データセット名 MovieLens100k ユーザー数 943 アイテム数 1682 評価値 1 から 5 の整数値評価個数 100,000 期間 1997/09/19~1998/04/22 また, MovieLens で用いられる映画には, メタデータとして Comedy や Action などの 18 種のジャンルがある. 本システムはジャンルを次元とする特徴空間を用いる. 本システムは Python で実装し, RDBMS として MySQL を用いた. 本システムの実装の大まかな流れを示す. データセット内のユーザー集合からランダムに一定数をサンプリングして, ユーザーを行とし, 映画のジャンルを列とし, ジャンルごとの評価値平均を成分とする嗜好行列を定義する. 次に, 嗜好行列に対して k-means のクラスタリングを行い嗜好傾向の類似したユーザーを集めた嗜好クラスタにユーザーを分類する. 推薦対象ユーザーに対して, 過去 n ヶ月間に観て評価した映画のジャンルを文脈ととらえて部分空間選択を行い, 部分空間上で k-nn 法を用いて協調フィルタリングを行う. 相関量計算をして推薦対象ユーザーとの相関量の高い k 人のユーザーの推薦を検討している映画の評価値の平均を求めて, それを説明変数として線形回帰モデルを構築し, 評価値予測を行い, 誤差を算出して精度を評価する. 本システムを実装した詳細な手順を以下に示す Step1: サンプリング. ユーザーからランダムに適切な数をサンプリングする. Step2: 嗜好行列に k-means クラスタリングを適用する. 嗜好行列に k-means でクラスタリングを行い, ユーザーを嗜好傾向が近いもの同士を集めた嗜好クラスタに分類する. その際, 各クラスタの重心も算出しておく. Step3: 推薦対象ユーザーと各嗜好クラスタの重心との距離を計算し, 最近傍嗜好クラスタを特定する. ユーザーの嗜好ベクトルと各嗜好クラスタの重心との距離を算出し, 最近傍嗜好クラスタを特定する. Step4: 過去 2 ヶ月間に推薦対象ユーザーが評価した映画のジャンルを文脈に対応する部分空間とし, 部分空間選択を行う. 過去 2 ヶ月間に推薦対象ユーザーが評価した映画のジャンルを抽出し, それを文脈に対応する部分空間とみなす. Step5: 部分空間上で推薦ユーザーと他のユーザーの嗜好ベクトルを用いて相関量計算を行う. 選択した部分空間上でユーザー同士の相関量計算を行い, 対象ユーザーの嗜好傾向に類似したユーザーと相関量を求める. Step6: 相関量が高い順に k 人を抽出し, 推薦を検討する映画の評価値の平均を算出する. 相関量が高い順に k 人を抽出し, 推薦対象として検討している映画に対する評価値の平均を算出する. Step7:Step6 で求めた評価値の平均を説明変数とした回帰モデルを構築する算出した評価値平均を説明変数とした線形回帰モデルを構築する. Step8: テストとして評価値予測を行う. 線形回帰モデルを用いてテスト期間の評価値の予測を行い, 誤差を算出する.

5 4. 実験切り出し法の効果を検証するために, 今回実装したシステムを用いて以下の条件で実験を行った. 学習期間を 1997 年 12 月 13 日から 1998 年 2 月 13 日, テスト期間を 1998 年 2 月 14 日から 1998 年 4 月 23 日までとする. 実験の比較対照群として切り出し法を用いない従来の方式で協調フィルタリングで予測を行う評価値と, 切り出し法を用いて予測する評価値をテスト期間からランダムにサンプリングする. 精度の評価指標としては RMSE を用いる. RMSE は誤差二乗平均平方根であり, 以下の式に従って算出する. を実測値, を予測値とする. を実現する切り出し法と, ユーザーの多様化する嗜好類型や急速に変化する諸々の状況に推薦方式を適応させるための推薦システムの構成モジュールの自動合成方式を提案した. これらの手法は推薦システムの過去の研究成果として提案されてきた他の多くの推薦手法と組み合わせて用いることができる. 切り出し法は協調フィルタリングなど他の手法の前処理として導入することで推薦システムの文脈適応性を向上し計算時間短縮を容易に実現できる. また, 推薦システムの構成モジュールの自動合成方式はレイヤーの種類を増減したり, レイヤーにモジュールを追加したりすることで非常に多様な嗜好類型や状況への対応が可能となり, 推薦システム自体の自動生成につながると考える. 本稿で提案した手法は今後の推薦システム研究の基盤を構成しうると考える. 今後は, 研究と実験 [6] を進めて提案手法を改良し, 有効性のさらなる検証を行う. この RMSE は誤差を表しているで, RMSE が小さいほど, 精度は高いとみなすことができる. 切り出し法を適用しない協調フィルタリングを行った従来手法と, 切り出し法を適用した協調フィルタリングの評価値予測の実験結果を以下の表 2 に示す. 表 2. 実験結果手法 RMSE 計算時間切り出し法適秒用しない手法参考文献 [1] 清木康金子昌史北川高嗣, 意味の数学モデルによる画像データベース探索方式とその学習機構, 電子情報通信学会論文誌,1996 [2] 吉田尚史図子泰三清木康北川高嗣, ドキュメントデータ群を対象とした意味的連想検索のためのメタデータ空間生成方式, 情報処理学会論文誌, 2000 [3] 田中克己角谷和俊, 情報推薦システム入門理論と実践, 共立出版, 2012 [4] MovieLens, [5] スチュワートラッセルピーターノーヴィグ, エージェントアプローチ人工知能, 共立出版, 1997 切り出し法を秒適用した手法表 2 の実験結果からわかる通り, 切り出し法を用いたケースでは, 従来手法に比べて計算時間が約 5 分の 1 に短縮され, 大幅に高速化し, さらに RMSE も減少して精度が向上している. 推薦にとって重要な限られた計算対象領域を切り出すことで精度を落とさずに計算時間の大幅な短縮が可能になったことを示している. 計算するデータの量を小さくしても精度が落ちていないのは部分空間選択による文脈効果であると考えられる. 5. 結論と今後の展望本稿では, 推薦システムの文脈適応と計算時間短縮

画像類似度測定の初歩的な手法の検証

画像類似度測定の初歩的な手法の検証島根大学総合理工学部数理情報システム学科計算機科学講座田中研究室 S539 森瀧昌志 1 目次第 1 章序論第章画像間類似度測定の初歩的な手法について.1 A. 画素値の平均を用いる手法.. 画素値のヒストグラムを用いる手法.3 C. 相関係数を用いる手法.4 D. 解像度を合わせる手法.5 E. 振れ幅のヒストグラムを用いる手法.6 F. 周波数ごとの振れ幅を比較する手法第