知識資源の用語管理（第2回）　　　　　　　　　　　　　　2009年12月11日　辻慶太

Size: px

Start display at page:

Download "知識資源の用語管理（第2回）　　　　　　　　　　　　　　2009年12月11日　辻慶太"

すずりしげまつ
5 years ago
Views:

1 情報分析 ( 第 2 回 ) 2012 年 4 月 18 日辻慶太 0. はじめに先週の感触では推薦システムにご関心を持つ方がいらっしゃった気がするので, 今回は推薦で用いられている手法を 2 つ紹介します具体的には協調フィルタリングとアソシエーションルールの 2 つを紹介しますまた実際の論文例を眺めた方が色々イメージが湧きやすいと思うので, 現在投稿中の辻らの論文を流し読みして頂きますその上で R での実行方法を復習しますちなみに推薦システムの全体像をもっと知りたいという場合は神嶌の解説論文がお勧めです授業用 HP( に置いてあります 1. 協調フィルタリング協調フィルタリングを用いた研究例 : 樽井勇之 (2011) 協調フィルタリングとコンテンツ分析を利用した観光地推薦手法の検討上武大学経営情報学部紀要. 蒋再興ら (2011) 協調フィルタリングに基づく授業推薦システム電子情報通信学会技術研究報告. 新美怜志ら (2011) 協調フィルタリングを用いた音楽推薦とマッピング手法情報処理学会研究報告. 澤井里枝ら (2010) SNS を利用した協調フィルタリングによる番組推薦手法情報処理学会研究報告. 吉岡貴芳ら (2010) 協調フィルタリングによる学習用コンテンツ推薦と英語多読学習支援システム教育システム情報学会研究報告. 伊藤心平 (2010) 協調フィルタリングにおけるセレンディビティの向上全国大会講演論文集. 堀幸雄ら (2009) 協調フィルタリングを用いた共著関係の予測情報知識学会誌. 岩根良輔ら (2008) 協調フィルタリングを用いて個人の嗜好を反映するレシピ検索手法の提案情報処理学会研究報告. 以下は人工知能の話題 : 協調フィルタリングを適宜修正して引用 : レンタルビデオ店には非常にたくさんの映画がありますあまりに多すぎてどれが面白いかよくわかりませんそんなとき, 面白そうな映画を選んでくれるシステムを推薦システム (recommender system) といいますこの推薦システムには二種類の主な実現方法があります一つは, 好きな監督俳優ジャン 1

ルなどを決めると, それにあった映画を見つけるという内容に基づくフィルタリング (content-based filtering) という方法ですそして, もう一つがここで紹介する協調フィルタリング (collaborative filtering) ですこの映画は面白かったとか, この映画はつまらなかったとかの批評のデータをいろいろな人から集めておき, そのデータを参考にして,

2 ルなどを決めると, それにあった映画を見つけるという内容に基づくフィルタリング (content-based filtering) という方法ですそして, もう一つがここで紹介する協調フィルタリング (collaborative filtering) ですこの映画は面白かったとか, この映画はつまらなかったとかの批評のデータをいろいろな人から集めておき, そのデータを参考にして, 面白そうな映画を推薦する方法ですここでは, 協調フィルタリングの一つである J. Riedl らの GroupLens の方法 ( 注 1) を紹介しますもとは, ネットニュースの記事の推薦システムでしたが, 現在は改良されて映画の推薦をする MovieLens に発展していますこの MovieLens( 注 2) は GroupLens のページで試してみることができます ( 英語 ) また実験室レベルでは映画に限らず様々な分野に GroupLens は適用されていますそれでは, 協調フィルタリングがどんなものか紹介しましょう次の 5 本の映画がある場合について考えてみます : 人工知能の休日 AI ウォーズ 13 日の人工知能 AI ジョーンズ七人の人工知能 A さんが, 推薦システムで面白そうな映画を探していますこの 5 本の映画の中で, 人工知能の休日と AI ウォーズの 2 本は見たことがありません, 残り 3 本の映画については見たことがあります A さんのこれら 3 本の映画についての評価は下の図のようなものでした 1~5 の 5 段階評価で 1 は面白くなかった,5 は面白かったこと, また,? は見ていないことを示しています協調フィルタリングでは, 他の人の評価を参考にして, 推薦する映画を決めますここでは図の B さん,C さん,D さんの評価を参考にすることにしますまず,A さんの評価と他の三人の評価がどれくらい似ているかを調べます A さんと B さんの評価を比べると, AI ジョーンズと七人の人工知能についての評価は 2

一致します B さんは 13 日の人工知能を見たことがないので無視しますこのことから,A さんと B さんは似ているといえます ( 注 3) 次に A さんと C さんを比べると,A さんは 13 日の人工知能を,2 と評価していてつまらないと思っていますが,C さんはこの映画を 5 と評価していてとても面白いと思っていますまた, AI ジョーンズについても逆の評価をしています

3 一致します B さんは 13 日の人工知能を見たことがないので無視しますこのことから,A さんと B さんは似ているといえます ( 注 3) 次に A さんと C さんを比べると,A さんは 13 日の人工知能を,2 と評価していてつまらないと思っていますが,C さんはこの映画を 5 と評価していてとても面白いと思っていますまた, AI ジョーンズについても逆の評価をしていますこのことから,A さんと C さんの好みは正反対であるといえます最後に,A さんと D さんですが, 評価が一致しているものもありますが, 逆のものもありますですので,A さんと D さんは似ているとも似ていないともいえますので, 中立とします次に,A さんに人工知能の休日や AI ウォーズを推薦するかどうかを, 他の三人の意見をもとに決めます下の図は,A さんが見たことのない二つの映画についての,B さん,C さん, D さんの評価です人工知能の休日について考えてみると,A さんと評価が似ている B さんは 1 と低く評価しているので,A さんにとってもつまらないと予測されますまた,C さんは 5 と高い評価をしていますが,A さんと C さんの好みは正反対なので, やはり,A さんにはつまらないと予測されます ( 注 4) ですので,A さんには人工知能の休日は推薦しません AI ウォーズについては,A さんと好みが似ている B さんが高い評価をしているので,A さんにとっても面白いと推測されます D さんはあまり良い評価をしていませんが,A さんと D さんの関連は中立なので, この評価は重視しませんですので,A さんには AI ウォーズを推薦しますこの協調フィルタリングの手法は, 映画以外にも, 雑誌やニュースの記事, 書籍などいろいろなものに応用できますまた, 電子商取引サイトなどで商品を提示したりするのにも利用されています (Amazon とか?) ここで説明した方法の改良や, 新しい方法が考案され, また, 内容に基づくフィルタリングと組み合わせる方法についても研究されています注 1:P. Resnick, N. Iacovou, M. Suchak, P. Bergstrom, and J. Riedl. "GroupLens: Open Architecture for Collaborative Filtering of Netnews" In Conference on Computer Supported Cooperative Work, pp (1994) 3

注 2:GroupLens は,NetPerceptions によって商用化され協調フィルタリング手法による商用システムの成功例として知られています継続された研究プロジェクトは, MovieLens へと独自の発展をとげました注 3: 正確には,A さんと B さんの映画の 5 段階評価をベクトルと見なして, ベクトルの相関係数を求めて, 似ているかどうかの指標として利用します似ている

4 注 2:GroupLens は,NetPerceptions によって商用化され協調フィルタリング手法による商用システムの成功例として知られています継続された研究プロジェクトは, MovieLens へと独自の発展をとげました注 3: 正確には,A さんと B さんの映画の 5 段階評価をベクトルと見なして, ベクトルの相関係数を求めて, 似ているかどうかの指標として利用します似ているとき, 相関係数は 1 に近づき, 正反対のとき -1 に近づき, 中立の場合は 0 になります注 4: 正確には, 他の 3 人それぞれについて, その映画の評価から, その人の全映画についての平均評価を引き, それに A さんとの相関係数を掛けたものを総和が大きいものから順に推薦します ( ほとんどの映画に 4 か 5 を付ける人が 5 を付けてもあまり人に勧めている感はありません一方, ほとんどの映画に 1 か 2 を付ける人が 5 を付けていたら絶賛推薦中と言うことができます ) 協調フィルタリングを行うソフトやパッケージは? お手軽なのはない? 4

5 R で協調フィルタリングってできる? パッケージが見つからないんだけど別添の論文を書いたとき, 辻は自分でプログラムを書いて実行しました 5

6 2. アソシエーションルール上の協調フィルタリングと違って, こちらは R にはっきりとしたパッケージがあります (arules といいます ) アソシエーションルールを用いた研究例 : 遠山清人ら (2010) アソシエーションルールを用いた電子メールのマルチラベル分類情報処理学会全国大会講演論文集第 72 回, p."2-461"-"2-462". 杉村博 (2009) テンプレートにもとづく時系列データからの相関ルールマイニングシステム情報処理学会全国大会講演論文集第 71 回, p."2-51"-"2-52". 裴明花ら (2006) 重要な顧客層および相関ルール発見のための繰返し購買パターンを考慮した相関ルールマイニング情報処理学会論文誌. 上田芳弘ら (2002) 相関ルールを用いた組織内における文書校正支援電子情報通信学会論文誌 D. 山本幸枝ら (2001) 相関ルールを用いた英文情報の分野判別電子情報通信学会技術研究報告. 川原稔ら (1998) 文献情報検索支援システムにおける相関ルール選択基準情報処理学会研究報告. データベースシステム研究会報告. 橋本和夫ら (1997) テキスト検索のための相関ルールの発見電子情報通信学会技術研究報告. AI, 人工知能と知識処理. アソシエーションルールの概要例えばスーパーのレジでは様々な商品購入のデータが収集できます一人の客の買い物かごは, どのような商品が同時に買われたかを示すデータと考えることができますそこから, 例えば目玉商品 A と日用品 B を購入した顧客は, 同時に高級品 C と日用品 D も高い確度で購入するという事実がわかれば : A,B,C,D のセット商品を発売する顧客の利便性を考えて, 商品の配置を近づける顧客に店内を長く歩き回ってもらうため, 商品の配置を遠ざける A や B の特売を行う際には C や D の在庫を増やしておくといった販売戦略を立てることができますこの購買傾向は : { 目玉商品 A, 日用品 B } { 高級品 C, 日用品 D } という式で表現できます 6

7 一般に X,Y を商品の集合として ( この例では X={ 目玉商品 A, 日用品 B },Y={ 高級品 C, 日用品 D } X Y と記述される傾向をアソシエーションルール (association rule) と呼びますアソシエーションルールは相関ルールと呼ばれることもありますですが相関は一般に correlation に対する訳語として用いられているので, あまり良い呼び方ではありません用語 (1): トランザクション, アイテム買い物かごのような 1 つのまとまりをトランザクションと呼びますまたトランザクションを構成するもの ( 商品など ) をアイテムと呼びます下の場合, アイテムは { ミルク, パン, バター, ビール } ですトランザクション 1 ミルクアイテムパン 2 パンバター 3 ビール 4 ミルクパンバター 5 パンバター表 : トランザクションとアイテム上の表から得られるアソシエーションルールとしては,{ ミルク } { パン },{ ミルク, パン } { バター } などがあり得ます先ほど説明した通りですが, 一応言葉で書くと,{ ミルク, パン } { バター } はミルクとパンを同時に買う人は, バターも買うという意味ですさてここでアソシエーションルールの説明を正確に行えるよう以下の用語を導入します I = { i1,i2,...,im } をアイテムの集合とします T = { t1,t2,...,tn } をトランザクションの集合としますトランザクション ti はアイテムの ( 部分 ) 集合と言えます ( すなわち T I ) トランザクション ti とアイテム集合 X に関して ti X が成り立つとき, ti は X を含むといいます { パン, ミルク, ビール } というトランザクションはアイテム集合 { パン, ミルク, ビール },{ パン, ミルク },{ ミルク, ビール },{ パン, ビール },{ パン },{ ミルク },{ ビール } を含むと言えます 7

8 用語 (2): サポート, 確信度 X,Y をアイテムの集合とします ( ただし X Y =φ) この時, データベース D 中の X Y を含むトランザクションの全トランザクションに対する割合が s% であるとき, アソシエーションルール X Y は D において s% のサポート (support: 支持度とも言う ) を持つと言います以下ではこれを support(x Y)= s% と表記します例えば先ほどの表では, アイテム集合 { ミルク, パン } は 5 つのトランザクション中 2 つに現れているので 2/5=40% のサポートを持ちますではアイテム集合 { パン, バター } のサポートはいくらでしょう? さて再び X,Y をアイテムの集合とします ( ただし X Y =φ) この時, データベース D 中の X を含むトランザクションのうち,Y を含むものの割合が c% であるとき, アソシエーションルール X Y は D において c% の確信度 (confidence) を持つと言います以下ではこれを conf( X Y )=c% と表記します例えばアイテム集合 { ミルク, パン } は 2 つのトランザクションに現れますこのうち { バター } も含んだトランザクションは 1 つなので,conf ( { ミルク, パン } { バター } )=1/2=50% の確信度を持ちます統計を習った方なら, 確信度とは条件付き確率 P(Y X) であると理解することができるでしょうではアソシエーションルール { パン } { バター } の確信度はいくらでしょう? 価値のあるアソシエーションルールは基本的に以下の 2 つを満たすルールです : 確信度 conf が高いサポート support もある程度高い ( なぜなら, サポートが小さいアソシエーションルールは, わずかなデータにしか当てはまらないという意味で, 出番の尐ないルールだからです例えばミルクとパンとバターとアイスとビールと猫缶とドッグフードを買った人は自転車も買っていたこのルールの確信度は 100% だといっても, それは過去にそういう特殊な人が一人いた結果によるものならば, あまり嬉しい情報ではありません ) 8

9 アソシエーションルールの数え上げは大変さて m 種類のアイテムを使って作ることのできるアソシエーションルールは全部で : m m C k k 2 ( 2 k 2) 個あります m 個のアイテムからアソシエーションルールに用いる k 個のアイテムを選ぶ組み合わせは mck 通りありますそしてそれぞれの組合わせにおいて, アソシエーションルールの前提部 ( の左側 ) と結論部 ( の右側 ) の分け方が 2 k -2 通りあるからです従ってアイテム数 m=10 の場合, アソシエーションルールは約 57,000 個,m=100 の場合は個ありますそれらのサポートや確信度を全て求めるのは現実的に不可能です先ほど価値のあるアソシエーションルールとは, 確信度が高く, サポートもある程度高いルールだと述べました従ってすべてのアソシエーションルールが求まらなくても, 価値のあるルールだけ求まれば良いと開き直りましょう ( 価値の尐ないルールは求まらなくて良いと考えましょう ) その為のアルゴリズムを以下で紹介していきますアプリオリアルゴリズム Agrawal らは 1993 年, 指定した確信度とサポート値 ( 以上 ) をとるアソシエーションルールをすべて発見するアプリオリアルゴリズムを提案しましたそれに基づいて IBM アルマデン研究所で開発された Quest システムは世界初の本格的なデータマイニングシステムですアプリオリという名前は先験的な知識を使うことから来ているそうです基本となる考え方 : あるアイテム集合 i の頻度が minsup 以下だったら, そのアイテム集合 i を含むアイテム集合の頻度は必ず minsup 以下になる例えば, アイテム集合 { パン, バター } がデータベース中に 5 回しか現れていなかったら, これを含むあらゆるアイテム集合, 例えば { パン, バター, ビール },{ ヨーグルト, パン, バター, 塩 } などは 5 回以下しかデータベース中に現れていないはずです従ってそういう組合せは考えない余計な数え上げはしないというのがアプリオリアルゴリズムの考え方になります 9

10 例えば : 次に L1 の要素から以下のように C2 を作ります : 10

11 作った C2 のトランザクション中の頻度を調べ,minsup 以上の要素だけ L2 とします : 11

12 最終的に以下の L1,L2,L3 が得られ, そこからアソシエーションルールを作れば, どのルールもサポートの高いルールになります : 12

13 R によるアソシエーションルール (1) まずアソシエーションルールの関数を含んだパッケージ arules をインストールする必要がありますパッケージ CRAN ミラーサイトの設定 Japan (Tsukuba) などを選択再度パッケージパッケージのインストール arules を選択再度パッケージパッケージの読み込み arules を選択とします (2) 読み込みには以下のようにして read.transactions 関数を用います : > 売上げ <- read.transactions("shohin.csv", format = "basket", sep=",") (3) 次に以下のように apriori 関数を用います : > ルール <- apriori( 売上げ, parameter=list(supp=0.05, conf=0.8, target="rules")) (4) 得られた結果は summary( ルール ) などとしても見られません次のようにしてファイルに出力します : > WRITE( ルール, "kekka.txt") (5) kekka.txt を開くと以下のようなアソシエーションルールが記されています : rules support confidence lift 1 { 天ぷら粉業務用中袋 } => { 徳用醤油 } { 調理用ワイン赤 } => { 上白糖業務用 } { 上白糖業務用 } => { 調理用ワイン赤 } { 調理用ワイン赤 } => { おいしいたぬき } { おいしいたぬき } => { 調理用ワイン赤 } { 上白糖業務用 } => { おいしいたぬき } { おいしいたぬき } => { 上白糖業務用 } : : : : : : : : : : : : : : : : : : : : : : : : : 28 { 上白糖業務用, 調理用ワイン赤 } => { おいしいたぬき } 練習 (1) ある商品売上げデータ ( をダウンロードし, サポート 0.03, 確信度 0.75 でアソシエーションルールを作成して表示して下さい (2) ある食品売上げデータ ( をダウンロードし, サポート 0.001, 確信度 0.8 でアソシエーションルールを作成して表示して下さい 13

コンピュータ応用・演習情報処理システム

コンピュータ応用・演習情報処理システム 2010 年 12 月 15 日データエンジニアリング演習情報処理システムデータマイニング ~ データからの自動知識獲得手法 ~ 1. 演習の目的 (1) 多種多様な膨大な量のデータを解析し, 企業の経営活動などに活用することが望まれている. 大規模データベースを有効に活用する, データマイニング技術の研究が脚光を浴びている 1 1. 演習の目的 (2) POS データを用いて顧客の購買パターンを分析する.

知識資源の用語管理（第2回） 2009年12月11日 辻慶太

知識資源の用語管理（第2回）　　　　　　　　　　　　　　2009年12月11日　辻慶太