1 情報分析（第2 回） 2012 年 4 月 18 日 辻慶太 0. はじめに 先週の感触では推薦システムにご関心を持つ方がいらっしゃった気がするので，今回は推薦で 用いられている手法を2 つ紹介します。具体的には協調フィルタリングとアソシエーションルー ルの2 つを紹介します。また実際の論文例を眺めた方が色々イメージが湧きやすいと思うので， 現在投稿中の辻らの論文を流し読みして頂きます。その上でR での実行方法を復習します。ちな みに推薦システムの全体像をもっと知りたいという場合は神嶌の解説論文がお勧めです。授業用 HP（http://slis.sakura.ne.jp/jb/）に置いてあります。 1. 協調フィルタリング ■協調フィルタリングを用いた研究例： ・樽井勇之 (2011)「協調フィルタリングとコンテンツ分析を利用した観光地推薦手法の検討」 上武大学経営情報学部紀要. ・蒋再興ら (2011)「協調フィルタリングに基づく授業推薦システム」電子情報通信学会技術研 究報告. ・新美怜志ら (2011)「協調フィルタリングを用いた音楽推薦とマッピング手法」情報処理学会 研究報告. ・澤井里枝ら (2010)「SNS を利用した協調フィルタリングによる番組推薦手法」情報処理学 会研究報告. ・吉岡貴芳ら (2010)「協調フィルタリングによる学習用コンテンツ推薦と英語多読学習支援シ ステム」教育システム情報学会研究報告. ・伊藤心平 (2010)「協調フィルタリングにおけるセレンディビティの向上」全国大会講演論文 集. ・堀幸雄ら (2009)「協調フィルタリングを用いた共著関係の予測」情報知識学会誌. ・岩根良輔ら (2008)「協調フィルタリングを用いて個人の嗜好を反映するレシピ検索手法の提 案」情報処理学会研究報告. ■以下は「人工知能の話題：協調フィルタリング」を適宜修正して引用： http://www.ai-gakkai.or.jp/jsai/whatsai/AItopics2.html レンタルビデオ店には非常にたくさんの映画があります。あまりに多すぎてどれが面白いかよ く わ か り ま せ ん 。 そ ん な と き ， 面 白 そ う な 映 画 を 選 ん で く れ る シ ス テ ム を 推 薦 シ ス テ ム （recommender system）といいます。 この推薦システムには二種類の主な実現方法があります。一つは，好きな監督・俳優・ジャン
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 ジョーンズ”と“七人の人工知能”についての評価は
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. 175-186 (1994)
4 注2：GroupLens は，NetPerceptions によって商用化され協調フィルタリング手法による商 用 シ ス テ ム の 成 功 例 と し て 知 ら れ て い ま す 。 継 続 さ れ た 研 究 プ ロ ジ ェ ク ト は ， MovieLens へと独自の発展をとげました。 注3： 正確には，A さんと B さんの映画の 5 段階評価をベクトルと見なして，ベクトルの相 関係数を求めて，似ているかどうかの指標として利用します。「似ている」とき，相関 係数は1 に近づき，「正反対」のとき－1 に近づき，「中立」の場合は 0 になります。 注4：正確には，他の 3 人それぞれについて，その映画の評価から，その人の全映画につい ての平均評価を引き，それに A さんとの相関係数を掛けたものを総和が大きいものか ら順に推薦します。（ほとんどの映画に4 か 5 を付ける人が 5 を付けてもあまり人に勧 めている感はありません。一方，ほとんどの映画に1 か 2 を付ける人が 5 を付けていた ら絶賛推薦中と言うことができます）。 --- ■協調フィルタリングを行うソフトやパッケージは？ → お手軽なのはない？
5
「R で協調フィルタリングってできる？ パッケージが見つからないんだけど」
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 } という式で表現できます。
7
一般にX，Y を商品の集合として（この例では X={ 目玉商品 A，日用品 B }，Y={ 高級品 C，日 用品D } X → Y と記述される傾向をアソシエーションルール（association rule)と呼びます。 ※アソシエーションルールは相関ルールと呼ばれることもあります。ですが｢相関｣は一般に “correlation”に対する訳語として用いられているので，あまり良い呼び方ではありません。 ■用語(1)：トランザクション，アイテム 買い物かごのような１つのまとまりをトランザクションと呼びます。またトランザクションを 構成するもの（商品など）をアイテムと呼びます。下の場合，アイテムは {ミルク，パン，バタ ー，ビール} です。 表：トランザクションとアイテム 上の表から得られるアソシエーションルールとしては，{ミルク} → {パン}，{ミルク，パン} → {バ ター} などがあり得ます。先ほど説明した通りですが，一応言葉で書くと，{ミルク，パン} → {バ ター}は「ミルクとパンを同時に買う人は，バターも買う」という意味です。 さてここでアソシエーションルールの説明を正確に行えるよう以下の用語を導入します。 I = { i1，i2,...,im } をアイテムの集合とします。 T = { t1，t2,...,tn } をトランザクションの集合とします。 トランザクション ti はアイテムの（部分）集合と言えます（すなわち T ⊆ I ）。 トランザクション ti とアイテム集合 X に関して ti ⊇ X が成り立つとき, 「ti は X を含む」 といいます。{パン，ミルク，ビール} というトランザクションはアイテム集合 {パン，ミルク， ビール} ，{パン，ミルク}，{ミルク，ビール}，{パン，ビール}，{パン}，{ミルク}，{ビール} を含 むと言えます。 トランザクション 1 ミルク パン 2 パン バター 3 ビール 4 ミルク パン バター 5 パン バター アイテム
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％だ」といっても，それは過去にそういう特殊な人が一人いた結果に よるものならば，あまり嬉しい情報ではありません）。
9 ■アソシエーションルールの数え上げは大変 さてm 種類のアイテムを使って作ることのできるアソシエーションルールは全部で：
m k k k mC 2 ) 2 2 ( 個あります。m 個のアイテムからアソシエーションルールに用いる k 個のアイテムを選ぶ組み 合わせはmCk通りあります。そしてそれぞれの組合わせにおいて，アソシエーションルールの前 提部（“→”の左側）と結論部（“→”の右側）の分け方が 2k－2 通りあるからです。 従ってアイテム数m=10 の場合，アソシエーションルールは約 57,000 個，m=100 の場合は 5.15 ×1047個あります。それらのサポートや確信度を全て求めるのは現実的に不可能です。 先ほど価値のあるアソシエーションルールとは，確信度が高く，サポートもある程度高いルー ルだと述べました。従ってすべてのアソシエーションルールが求まらなくても，価値のあるルー ルだけ求まれば良いと開き直りましょう（価値の尐ないルールは求まらなくて良いと考えましょ う）。その為のアルゴリズムを以下で紹介していきます。 ■アプリオリアルゴリズム Agrawal らは 1993 年，指定した確信度とサポート値（以上）をとるアソシエーションルール をすべて発見する「アプリオリアルゴリズム」を提案しました。それに基づいてIBM アルマデン 研究所で開発された Quest システムは世界初の本格的なデータマイニングシステムです。 ※アプリオリという名前は「先験的」な知識を使うことから来ているそうです。 基本となる考え方： あるアイテム集合i の頻度が minsup 以下だったら，そのアイテム集合 i を含むアイテム集合 の頻度は必ずminsup 以下になる。 例えば，アイテム集合 { パン，バター } がデータベース中に 5 回しか現れていなかったら，こ れを含むあらゆるアイテム集合，例えば { パン，バター，ビール }，{ ヨーグルト，パン，バタ ー，塩 } などは 5 回以下しかデータベース中に現れていないはずです。 → 従って「そういう組合せは考えない。余計な数え上げはしない」というのがアプリオリアルゴ リズムの考え方になります。10 例えば：
11
12
最終的に以下のL1，L2，L3 が得られ，そこからアソシエーションルールを作れば，どのルール もサポートの高いルールになります：
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 {天ぷら粉業務用中袋} => {徳用醤油} 0.0721003134796238 1 9.11428571428571 2 {調理用ワイン赤} => {上白糖業務用} 0.054858934169279 1 18.2285714285714 3 {上白糖業務用} => {調理用ワイン赤} 0.054858934169279 1 18.2285714285714 4 {調理用ワイン赤} => {おいしいたぬき} 0.054858934169279 1 18.2285714285714 5 {おいしいたぬき} => {調理用ワイン赤} 0.054858934169279 1 18.2285714285714 6 {上白糖業務用} => {おいしいたぬき} 0.054858934169279 1 18.2285714285714 7 {おいしいたぬき} => {上白糖業務用} 0.054858934169279 1 18.2285714285714 : : : : : : : : : : : : : : : : : : : : : : : : : 28 {上白糖業務用,調理用ワイン赤} => {おいしいたぬき} 0.054858934169279 1 18.2285714285714 ■練習 (1) ある商品売上げデータ（http://slis.sakura.ne.jp/jb/shohin.csv)をダウンロードし，サポート 0.03，確信度 0.75 でアソシエーションルールを作成して表示して下さい。 (2) ある食品売上げデータ（http://slis.sakura.ne.jp/jb/groceries.csv)をダウンロードし，サポー ト0.001，確信度 0.8 でアソシエーションルールを作成して表示して下さい。
