データマイニング

トップページ研究分野と周辺

データマイニング(Data Mining)とは、膨大なデータの集積から何らかの知識(傾向、法則等)を導出する方法を探る研究分野である。検索が探す目的を明確にして行なうのに対し、データマイニングは何が見つかるかは分からないが、有意義なものを探し出したいという場合も含む。

テキストマイニング(Text Mining)はデータマイニングの一種で、対象がテキスト(文章)となる。自由記述文を対象とする場合、事前に自然言語処理を行う場合も多い。

テキストマイニング

相関ルール抽出

相関ルール(Association Rule)とは、或る事象(Xとする)の下で或る事象(Y)が発生する関係を表し、矢印を用いてX→Yと記述される場合が多い。矢印の左側のXの部分を条件部(前提部ともいう)、Yの部分を帰結部(結論部ともいう)と呼ぶ。Xが起きたとき必ずYが起きるのではなく、一定の確率で起きる事を示している。

例えば、コンビニでAさんが(パン、牛乳、ジャム)を買い、Bさんが(お握り、お茶、漬物)を買ったとする。もし、両者と同じ組合せで購入する人が沢山いれば、「パンを買う人は牛乳とジャムを買う」「パンと牛乳を買う人はジャムも買う」「お握りとお茶を買う人は漬物も買う」といった相関ルールが読み取れるだろう。この様に同時に購入されやすい商品やサービスの分析は、バスケット分析とも呼ばれる。

レシート一枚に書かれる商品の集合をトランザクション、パン等の一つの商品をアイテムと呼ぶ。例えばA,B,Cの3個のアイテムから成るトランザクションから、図の様に12の相関ルールが抽出される。X→YとY→Xのように向きが逆ならば、別のルールと考える。条件部と帰結部は、複数のアイテム(アイテムセット)から成っていてもよい。

バスケット分析による相関ルール抽出は、同時に売れやすい商品を近くに配置したり、或る商品を購入した人に関係の高い商品をお勧めする等、ビジネス上非常に有益であるため、データマイニングの代表と言えるほど、研究が盛んである。

相関ルールの概念図

支持度と確信度

相関ルールの重要度を表す指標として支持度(support)と確信度(confidence)がある。支持度は全トランザクションのうち、前提部と帰結部に登場する全てのアイテムを含むトランザクションの割合であり、そのルールが登場する頻度を表すものと言える。確信度は、前提部のアイテムを買う人が帰結部のアイテムを買う確率である。支持度と確信度の双方が高いほど重要なルールで、通常は最低支持度(minsup)と最低確信度(minconf)を予め決め、両者をクリアするルールを抽出する。

図の4つのトランザクションの例で、相関ルールA→Bを計算する。A,Bを含むトランザクションは一段目と二段目の2つだから、支持度は2/4=50%となる。これに対し確信度は、条件部を含むトランザクションのうち、帰結部も同時に含むトランザクションの割合である。相関ルールA→Bの場合は、条件部Aは全トランザクションに含まれている。このうち、Bも含むトランザクションは上2つとなっている。従ってこのルールの場合、確信度も2/4=50%となる。

相関ルールの概念図

アプリオリ・アルゴリズム

相関ルールはアイテムの組合せだから、構成するアイテム数が増加するにつれて、在り得るルールの数は急激に増大する。アイテム数3では総ルール数12だったのが、アイテム数10では約5万7千個になり、アイテム数が100を超える規模になると、全てのルールの支持度や確信度を検討するのは、単純に組合せを作っていく方法だと、スーパーコンピュータを使っても実際に計算可能な時間(実時間)内で処理する事は、不可能となってくる。

これを解決したのが、1994年にR.Agrawal等が発表したアプリオリ・アルゴリズム(Apriori algorithm)だった。或るアイテムセットの支持度は、必ずその部分アイテムセットの支持度以下である事を使って計算を省略する。まず、全ての単体アイテム(一つだけのアイテム。ここではA,B,C,D)の支持度を数える(一段目、最低支持数2とすると、Dは既に失格となる)。

次にアイテム数2のセットの支持度を調べるが、Dを含む組は必ず1以下なので除外出来る。残りを調べると、BCが失格となる(二段目)。ここで合格したアイテムセットに出て来る全単体アイテム(ここではA,B,C)から作られる全てのアイテム数3のセット(ここではABCのみ)の検討に移る。この際、ここではABCの部分となる全てのアイテム数2のセットの合否をみる。この場合、BCが失格(1)だったので、それを含むABCも失格(1以下)と分かる。

一般に、アイテム数Nの合格セットに出て来る全単体アイテムから、アイテム数N+1の全セットを構成し、各セットのアイテム数Nの部分集合の合否を使って合否判定する。最低支持度以上のセットが無くなればセット抽出を終了する(この後の確信度計算はすぐ終わる)。アプリオリ・アルゴリズムの登場によって、相関ルール抽出は現実になったのである。

相関ルールの概念図