Graduate School of Information Science and Technology, Osaka

Presentation on theme: "Graduate School of Information Science and Technology, Osaka"— Presentation transcript:

1 Application of Collaborative Filtering for Software Component Retrieval System
Graduate School of Information Science and Technology, Osaka Makoto Ichii, Reishi Yokomori, Katsuro Inoue

2 ソフトウェア部品検索システム 過去に開発された大量のソフトウェア資産 再利用や理解を支援するツールが必要 ソフトウェア検索システム
企業内で開発 ＷＷＷ上で公開 再利用や理解を支援するツールが必要 部品数が多いために把握が困難 部品に詳しい人が不在 ソフトウェア検索システム ソフトウェア資産をデータベースに登録 キーワード入力により部品を検索・取得 まず，研究の背景としまして，ソフトウェア部品検索システムについて説明します． ソフトウェア開発の現場には，過去に開発された大量のソフトウェア資産が蓄積されています． たとえば企業内で開発されたプロダクトや，SourceForgeなど，ＷＷＷ上で公開されているプロダクトです． そして，これらをソフトウェア部品として再利用・理解することを支援するツールが必要とされています． それは， ・部品数が多い為に把握が困難であったり， ・作者など，部品に詳しい人が不在である， という理由によります． このようなツールの一形態として，ソフトウェア検索システムがあります． これは，ソフトウェア資産をデータベースに登録し， キーワード入力などにより，部品を検索し，取得するツールです．

3 Javaソフトウェア部品検索システム SPARS-J
Webインターフェースによる検索・部品情報の表示 キーワードによる全文検索 利用関係にある部品の一覧表示 パッケージ階層の表示 　(パッケージブラウザ) 我々の研究チームでは，Javaを対象とした検索システム SPARS-Jの研究開発を行っている これは，Javaのクラスを部品として，ソースコードを検索するツール 検索および部品の情報表示にはCGIによるWebインターフェースを利用している ここから，キーワード入力による検索を行う． また，検索結果から得た部品に関して，その部品と利用関係にある部品の一覧表示を行ったり， Javaのパッケージ階層の表示をおこない，ブラウジングを行う事もできる．

4 研究の目的 SPARS-Jでは，部品の静的な解析結果のみを利用している
過去のユーザの検索行動をフィードバックする事で，検索の支援ができないか？ 様々なユーザが，それぞれの目的でシステムを利用 過去に同じ目的で検索したユーザがいるかもしれない そのユーザが利用した部品を提示することで，ユーザの検索の労力を減らせる 協調フィルタリングの利用により，「部品の推薦」という形でユーザの部品検索を支援する 今説明しましたSPARS-Jの検索機能は， 部品の静的な解析結果のみを利用して実現されています． ここで，我々は %ユーザが利用することにより蓄積されるデータ，たとえば ユーザの過去の検索行動をフィードバックすることで， 検索の支援ができないか？と考えた 様々なユーザが，それぞれの目的でシステムを利用する． たとえば，現在システムを利用しているユーザと， 同じ目的で検索したユーザが過去にいる事が考えられます． この場合，その過去のユーザが利用した部品を現在のユーザへ提示することで， ユーザは検索の労力なく，必要な部品を取得できます． そこで，本研究では協調フィルタリングという手法の利用により， 「部品の推薦」という形でユーザの部品検索を支援することを目的とします．

5 協調フィルタリング(1/2) 大量のアイテムの中から，ユーザから得た情報をもとに，推薦するアイテムを決定する手法
書店などのオンラインショップで利用されている 様々な手法が提案されている 本研究では，ユーザ間の相関をもとにした手法を応用 ユーザが未評価のアイテムに対して，その評価値を推測する では，協調フィルタリングという手法について説明します． 協調フィルタリングとは，大量のアイテムの中から， ユーザにアイテムを推薦する，情報フィルタリングの1手法です． 情報フィルタリングの中でも，ユーザに推薦するアイテムを決定するのに 他のユーザから得た情報を利用するのが協調フィルタリングです． %ここでいうアイテムとは，映画や音楽・本など， %ユーザに対して推薦されるものです． Amazonといった書店などのオンラインショップで利用される事が多く， 「おすすめ商品」や「注目している商品と同時に購入されている商品」という形で 商品を推薦されます． 具体的な手法としては様々な手法が提案されており，大別すると 機械学習を利用する方法と，ユーザ間の相関を利用する手法がある． 本研究では，より簡易に実装できるユーザ間の相関を利用する手法を応用した手法を提案する amazon.co.jp

6 協調フィルタリング(2/2) 5 3 1 ? 1 ? 4 5 4 1 2 3 2 ? 4 アイテム ユーザ A B C D E 評価 D
好みが似ている 推薦 3 2 ? 4 協調フィルタリングの基本となる考え方について，簡単に解説します． ・ここに，A～Eの5個のアイテムがあるとします．アイテムは映画や音楽・本といったものです．． ・それを見たり聴いたり読んだりするユーザがいるとする． ・まず，ユーザはこれらに対して好みで評価をつける．ここでは5段階とする． 　たとえば映画だとすると，A,B,Cは見た事があり，それぞれ「おもしろい」「普通」「おもしろくない」という評価 　D,Ｅはまだ見ていないという状態． 　そして，次にD,Eのどちらを見たらいいのか？という事について，推薦を行う． ・ここで，他の人の評価を見てみると，ユーザ3人の評価はこのようになっていた． 　本来ならば相関係数やベクトル類似度などを求めるが，簡単のためにここでは見た目の類似性で． 　＊その辺を実際に求めた方が良いかも． 　(1) の人は，自分が高く評価したAを低く評価し，自分が低く評価したCを高く評価しているので，どうも好みが逆らしい． 　(2)の人は，Aが高めでCが低めというあたり，好みがにているらしい 　(3)の人は，逆とは言えないまでも，似ていないらしい ・好みが似ているのは(2)の人という事で，(2)の人が高く評価しているアイテム:D を推薦． ユーザから，各アイテムに対する評価を得る ユーザの評価をもとに，アイテムを推薦する 評価の類似度の高いユーザを求める 類似度の高いユーザの評価をもとに，推薦するアイテムを決定

7 以降は，簡単のために「アイテム」＝「部品」として説明
概念の対応 (1/2) 「アイテム」 本来同一である部品が，複数存在 コピーして利用されている部品など 「類似部品群」と呼ばれる 類似部品を個別に扱うと，本来同じ部品に対する評価が別々のものとして扱われてしまう 「類似部品群」をアイテムとして扱う 「評価」 明示的に評価を入力するのは，労力がいる 表示履歴を，部品に対する暗黙的な評価として扱う 表示した部品に，評価値 1をつける 表示していない部品は評価値 0 以降は，簡単のために「アイテム」＝「部品」として説明 この協調フィルタリングの手法を，ソフトウェア部品検索システムに適用するにあたり， 概念の対応付けを行います． まずアイテムですが，これは推薦の対象となるものであり，素直に考えるならば 部品がそれにあたります． しかし，ソフトウェア部品に関しては，本来同一である部品が複数存在することがあります． これはコピーして利用されている部品などで，「類似部品群」と呼ばれています． ユーザにとって，その中からどれを選ぶか，ということはたいした意味を持ちませんが， 協調フィルタリングを適用する場合，本来同じ部品に対する評価が，別のものとして扱われてしまいます． このため，類似部品を個別に扱うことは適切ではないと考え， 「類似部品群」をアイテムとして扱い，推薦を行います． しかし，説明する上で「部品群」というものが単位だとややこしくなるので， 以降の説明では，単にアイテム＝部品，とします． 次に評価です． 協調フィルタリングを行うには，各部品に対する評価をユーザから得る必要があります． しかし，明示的に個々の部品への評価を入力するのは労力がかかりすぎます． 労力を減らすために別の労力を要求していては意味がありません． そこで，特別な入力などはせず，表示履歴を部品への暗黙的な評価として扱うことにします． 具体的には，表示した部品に対して，ユーザは評価値1をつけた，として扱い， そして，表示していない部品は評価値0として扱います．

8 概念の対応 (2/2) 「ユーザ」 同じユーザでも，時と場合により異なる目的で検索を行う 検索目的が変われば，別のユーザとして扱う必要がある
部品に対する評価の傾向が変化する 履歴を全て使うと，目的に合わない部品を推薦してしまう 検索目的が変われば，別のユーザとして扱う必要がある ブラウザを閉じた段階で目的を終えたと判断する 「ブラウザを閉じるまで」=「セッション」をユーザとして扱う 最後にユーザの対応付けです． 一人の，同じユーザでも，時と場合により異なる目的で検索を行うことがあると思います． 　これは表示履歴つまり部品に対する評価の傾向が変化することになります． 　このため，そのまま履歴すべてを使ったユーザ間の類似度は意味をもたなくなり， 　目的に合わない部品を推薦してしまうことになります． よって，ユーザの検索目的が変われば，別のユーザとして扱う必要があります． しかし，一般に検索目的の変化を知ることは難しいため， ブラウザを閉じた段階，つまりシステムの使い終わった段階で目的を終えたと判断します． すなわち，セッションを1ユーザとして扱います．

9 提案手法の手順 ユーザの検索履歴を，セッションごとに取得する 対象となるセッションへ，部品を推薦する セッション間の相関係数を求める
他セッションの評価(履歴)をもとに，推薦部品を決定 では，提案手法の具体的な手順について説明します． まず，ユーザの検索履歴を，セッションごとに取得します． そして，対象となるセッションへの推薦部品を， ユーザ間の相関を元に求めます．

10 履歴の取得 セッションの追加 履歴の記録 部品 :表示済 1 2 3 4 5 6 7 セッション a b c d e ユーザ Webブラウザ
部品データベース 履歴データベース 部品 :表示済 セッションの追加 履歴の記録 1 2 3 4 5 6 7 セッション a b では検索履歴の取得から説明していきます． ・部品データベース中に部品(1)～(7)があり， 　それらへの表示履歴が，履歴データベース中にある状態を考えます． そして，ユーザはシステムの使用を開始したところだとします． ユーザは検索を行い，データベースから部品を取得します． このとき，新しいセッション(e)として履歴が保存される 同様に他の部品も表示すると，このように，履歴に追加される． c d e

11 部品の推薦 各セッションとの相関係数を求める 各部品の推薦値を,相関係数と評価値から求める 推薦する部品を利用者に提示する 1 1 1 1
ユーザ Webブラウザ 部品データベース 履歴データベース 3 部品 7 セッションeとの 相関係数 :表示済 各セッションとの相関係数を求める 各部品の推薦値を,相関係数と評価値から求める 推薦する部品を利用者に提示する 1 2 3 4 5 6 7 セッション a 1 1 1 1 0.58 b 1 1 1 0.67 (0)では続いて部品の推薦について説明します． 　今のユーザに対して推薦を行います．なお，詳細な計算式は，時間の都合上省略します． (1)まず，表示履歴を評価値に対応させます． 　推薦部品を求めるという事は，見ていない部品の評価値を，過去の履歴から推測する事に該当します． 　そして，推測した値が1に近ければ，表示するに違いない，ということで推薦します． %　なお，既に表示済みの部品についてはユーザは知っているとみなして推薦しません． (2)このために，過去のセッションとの相関係数を求めます． 　そのために，該当セッションの未評価部品も，評価値0とします． (2.5)まずセッションaとの相関係数を求めます． 　これは，これらの0,1の並びを利用して求められ， (3)0.58となります． 　なお，単純にこれらをベクトルとし，ベクトル同士の相関係数として求めると 　低すぎる値になってしまうため，求める式を調整してあります． (4)同様にセッションb,c,dに対しても求めると (5)0.67,0,0.67 と求められます． (6)では，続いて，まだ見ていない部品それぞれに対する推薦値を求めます． (7)まず，部品3に対する推薦値を求めます． 　これは，それぞれのセッションでの部品3に対する評価値を， 　相関係数を利用して重み付けし，加重平均を取る事により求められます． (8)部品3の場合は，0.64となります． (9)同様に残りの部品に対しても求めると， (10)このように0,0,0.64と求められます． 　以上で，まだ見ていない部品について，それぞれ推薦値が求められたので， 　この中から推薦値の高い部品を選び，ユーザに提示します． (11)今の例では，部品3と7が推薦されます． c 1 1 1 d 1 1 1 0.67 “?”に入る値を推測 e 1 1 ? ? 1 ? ? ? 推薦値 0.64 0.64

12 SPARS-Jへの実装 推薦部 部品登録部 部品データベース 部品検索部 部品の登録 部品の推薦 履歴の取得 ユーザ 検索・表示
履歴データベース 部品の推薦 部品データベース 履歴の取得 ユーザ ・現在のSPARS-Jの構成 ・推薦部を追加し，履歴の収集・および推薦を行う 部品検索部 検索・表示

13 スクリーンショット ZipEntryを利用している部品の一覧 推薦画面 ( ZipEntryを利用する部品を, 推薦部品で絞り込み)
推薦画面 (履歴の表示，全推薦クラスの表示) 部品情報表示 ( java.util.zip.ZipEntry クラス) SPARS-J トップページ 検索結果一覧 セッション中で表示した部品 推薦部品 推薦機能以外の部分も含めて，スクリーンショットの説明を行う SPARS-Jトップページ 検索結果一覧 1件目を開く. 部品情報表示画面 右のフレームにソースコードを表示 左上にはパッケージ情報が表示される 左下にはクラスのメソッド一覧． 利用関係を見る．ZipEntryを使うクラス一覧. たとえばZipEntryの変数が宣言されているクラスは63件 推薦を使う. 上にセッションで表示した部品. 説明の流れでは1件しかみてないが，2件見たあと，という画面 下に推薦部品．　今は全部． 推薦部品のうち，ZipEntryクラスの利用クラス一覧を見る 3件まで絞り込まれている．　非常にリーズナブル． 推薦部品による絞り込みが無い時 : 63部品 →3部品

14 適用実験の概要(1/2) 目的 内容 被験者 SPARS-J データベース 推薦機能が検索効率の改善に役立つかどうか検証する
SPARS-Jを利用してのJavaプログラム作成 与えられたスケルトンコードに対して実装 SPARS-Jで検索したソースコードを参考する 練習課題を含む5個の課題(P0～P4)を用意 被験者 井上研究室の学生・研究員 8名 (A1～A8) 2グループ(GP1,GP2)に分け，比較 SPARS-J データベース JDK，WWW上から収集したソースなど 　　約35,000 クラス 履歴データベースは空の状態から開始 … public static void main(String[] args) { // 入力ファイル: data/a.gif File inFile = new File("data", "a.gif"); String inFileSuffix = "gif"; // 出力ファイル: data/b.png File outFile = new File("data", "b.png"); String outFileSuffix = "png"; ImageConverter imageConverter = new ImageConverter(); try { BufferedImage image = imageConverter.readImage(inFile, inFileSuffix); if (image != null) { // ビューアで確認 new Viewer(image); imageConverter.writeImage(image, outFile, outFileSuffix); } else { System.out.println("Image is null"); } } catch (Exception e) { e.printStackTrace(); /** * 拡張子に応じた形式でイメージを読み込み, BufferedImageで返す * file 読み込み元 ファイル suffix 拡張子 読み込んだイメージ */ public BufferedImage readImage(File file, String suffix) throws IOException { BufferedImage image = null; // ここにコードを書いて下さい return image; 実装したシステム上で， 推薦機能が検索効率の改善に役立つかどうかを検証するため， 適用実験を行いました． 実験内容は，SPARS-Jを利用してのJavaプログラム作成です． 具体的には，図のようなスケルトンコードを渡し， SPARS-Jで検索したソースコードを参考に， 未実装部分を埋める作業をしてもらいました． 記述する部分を主要な部分に限定する事で， 被験者間の技術の差が出にくいようにしています． 被験者としては，井上研究室の学生および研究員8名に協力していただき， 全体を2グループに分けて比較しました．

15 適用実験の概要(2/2) 手順 評価項目 検索時間 適合率 これらを，推薦機能を利用する場合/利用しない場合で比較
作業時間全体から コーディング時間を引いたもの 適合率 表示した部品のうち，プログラムに利用できる部品の割合 これらを，推薦機能を利用する場合/利用しない場合で比較 GP1 (A1～A4) GP2 (A5～A8) 1 P0 2 P1, P2 P3, P4 3 SPARS-Jと課題に慣れる グループ分けの参考にする 推薦機能　無し 推薦機能　有り 続いて実験の手順について説明します． まず，全被験者が課題P0を行います． これは，SPARS-Jおよび課題に慣れ，以降の段階で， 慣れによる差が出ないようにするためです． また，この結果をもとにグループ分けを行いました． 続いて，グループ1がP1,P2を，グループ2がP3,P4を行います． これは推薦を利用しません． 最後に，グループ1がP3,P4を，グループ2がP1,P2を，つまり先ほどと異なる課題を， 推薦を利用して行います． 各実験の中では，以下を評価項目として計測しました． 一つめは検索時間です． これは作業時間全体から，コーディング時間を引いた物です． コーディング時間を引いたのは，プログラミング能力による差を減らすためです． もう一つは適合率です． これは，表示した部品のうち，プログラムに利用できる部品の割合です． これは，実際にプログラムに利用したかどうかとは関係なく，客観的に定めます． これらの値を，推薦機能を利用する場合，利用しない場合で比較しました．

16 実験結果と考察(1/4) 検索時間の比較 適合率の比較 推薦 無し 推薦 有り 実験結果．
実験結果．それぞれのグラフは，各課題についてのグループ内の平均の値を表しており， それぞれ，薄い青が推薦機能無し，濃い青が推薦機能有り　の場合の結果を示している． 上のグラフは検索時間を表しており，値が小さい方が良い結果となっている． また，下半分は適合率で，値が大きいほうが良い結果となっている． これらを見ると，全体的に推薦機能を利用した場合に，良い結果が出ているのが分かり， 中でも課題P1については大きな差がでていることが分かる． しかし，課題P3についてはあまり差が出ていないことがわかる． -- 次ページへのつなぎ -- 続いてこれらの考察を行う

17 実験結果と考察(2/4) 課題P1では大きな差が見られる 課題P3ではあまり差が見られない どの被験者も知識の無い分野の課題
未知の分野に関して検索するときに有効である 課題P3ではあまり差が見られない 課題分野の知識のある被験者の存在 推薦機能を利用しなくても，効率の良い検索ができた 推薦機能の有無による差が見られない被験者の存在 課題P1で差が見られたという点について，P1が他の課題と異なった点は 　他の課題では誰かが知っている事があったのに対して， 　この課題の分野に関して，誰も知識を持っていなかったという事があげられる． 　これより，未知の分野を検索するときに推薦機能が有効であるといえる (たぶん) 課題P3ではあまり差がみられないという事について考察する． 原因の1つめとしては，課題の分野の知識を持つ被験者が，推薦機能を利用しないグループに固まっていたことがあげられる． 分野について知っている事で，推薦機能を利用しなくても，効率の良い検索ができたと思われる また，前のページのグラフではなく，続いて示すユーザ別の比較によって分かったことだが， 推薦機能の有無で，検索効率に差が見られない被験者がいたことも原因． 次ページへのつなぎ つづいてこの点について考察します

18 実験結果と考察(3/4) 検索時間の比較 (被験者ごと) 適合率の比較 (被験者ごと) 推薦 無し 推薦 有り
課題の難易度にやや差があるので一慨には言えないが，全体的に推薦機能を使用した方が結果が良いのが分かる． しかし，被験者A2,A7については逆転が見られる．

19 実験結果と考察(4/4) 効率の上がっていない被験者が存在する 「表示済み部品は推薦しない」という方針が原因
該当する被験者の検索行動 : まず様々な部品に軽く目を通し，後半はそれらを見直しながら有効な部品を絞り込んでいく 利用できる部品は，序盤で履歴に入ってしまい，ほとんど推薦されない 推薦機能を有効に利用できていなかった 表示済み部品も推薦するかどうか，利用者が選択できるようにする などの対応が必要 これらの被験者は，どうして推薦により効率が上がらなかったのか，ということを考察． 結論からいうと， 本研究では「未知の部品の中から，ユーザにとって有効な部品を推薦する」ということを考えていて 「ユーザが表示済みの部品については，推薦しない」としたことが原因 これはどういうことか． ・該当する被験者の検索履歴を追ってみたところ，これらの被験者は 　まず，さまざまな部品に軽く目を通した後で， 　それらを見直して有効な部品を絞り込んでいく という行動をとっていた． このため，推薦を利用しようと考えたときに， 　利用できる部品は，序盤で履歴に入ってしまい，ほとんど推薦されなかった． (それどころか，推薦値の低い，使えない部品が推薦されてしまった. 　利用者の心理として，推薦値が低くても推薦される異常は使えると思ってしまう) つまり，推薦機能を有効に利用できていない

20 まとめと今後の課題 まとめ 今後の課題 ソフトウェア部品を対象とした推薦手法を提案し，SPARS-Jに適用した
適用実験により，ユーザの検索効率の向上が確認された 今後の課題 精度の向上 履歴の重み付けなど ユーザーインターフェースの改良 表示済み部品の扱い 検索画面などからのシームレスな利用 より大規模な実験 ではまとめます． 本研究では，協調フィルタリングを基にしたソフトウェア部品の推薦手法を提案し，SPARS-Jに適用しました． また，適用実験により，検索効率の向上に役立つことが確認されました． 今後の課題としては，まず，精度の向上があります． 　たとえば，現在はすべて評価値1として扱っている履歴に対して，参照回数や，参照元などで重み付けを行うことで， 　実現できると考えられます． また，ユーザーインターフェースの改良があります． 　これは， 　　・先ほど考察しました，表示済み部品の扱いをユーザが選べるようにすることや， 　　・現在は推薦は専用のページ以外では利用できないが，それ以外，検索結果画面などからもシームレスに利用できるようにすること 　などです． 最後に，より大規模な実験があげられます． 以上です．