[連載] フリーソフトによるデータ解析・マイニング 第40回

アソシエーション分析(1)

1.アソシエーション分析とは

  POS (Point Of Sales:販売時点情報管理) データが獲得しやすくなった昨今、重要な課題の1つは蓄積されたデータを有効に活用することである。説明の便利のため、 POS データをイメージした架空のデータを表1に示す。通常このようなデータをマーケット・バスケット・トランザクション (market basket transaction) と呼ぶ。表1の各行をそれぞれ1つのトランザクション (transaction, 取引)、あるいはバスケットと呼ぶ。

表1 買い物バスケットの事例 (TID: Transaction ID)
TID アイテム集合
1
 {パン、牛乳、ハム、果物}
2
 {パン、オムツ、ビール、ハム}
3
 {ソーセージ、ビール、オムツ}
4
 {弁当、ビール、オムツ、タバコ}
5
 {弁当、ビール、オレンジジュース、果物}

  アソシエーション分析 (associations analysis) は、百貨店や店舗などで集めている表1のようなトランザクションデータを活用するために、バスケットの中の商品間の関連性について分析を行う方法である。アソシエーション分析は、表1に示すような、トランザクションデータから、頻出するアイテムの組み合わせの規則を漏れなく抽出し、その中から興味深い結果を探し出すことを主な目的とする。
  アソシエーション分析は、1990年代初めに英国の有力百貨店マークス&スペンサーの店舗で集めているデータの活用に関して相談を受けたことをきっかけとして、IBM 研究所が研究を始め、Apriori (アプリオリ) というアルゴリズムを開発したと言われている。Apriori アルゴリズムは、巨大なデータベースからアソシエーションルール (associations rules) を抽出することを実現し、データマインニングの実用化に向けて大きく一歩前進した。その後、このアルゴリズムを改良した多くのアルゴリズムが登場している。アソシエーション分析のアルゴリズムにはアソシエーションルールを返すものと頻出アイテムセットを返すものがある。

2.相関ルール

(1) 相関ルールとは

  買い物をする際には、商品の組み合わせに何らかの関連、あるいは規則を持つケースは少なくない。トランザクションデータベースに頻出するアイテム間の何らかの組み合わせの規則をアソシエーションルールと呼ぶ。アソシエーションルールは連関ルール、関連ルール、相関ルールなどに訳されているが、より広く使われているのは相関ルールであるので、相関ルールと呼ぶことにする。
  「商品Aを買うと商品Bも買う」のようなルールを簡潔に、{A}⇒{B}と表すことにする。相関ルールは、通常XY の形式で表す。ルールの「⇒」の左辺を条件部 (antecedent: left-hand-side or LHS)、右辺を結論部 (consequent: right-hand-side or RHS) と呼ぶ。最も広く知られている相関ルールを検出するアルゴリズムは Apriori である。アルゴリズム Apriori を説明するため、まず相関ルールを検出する際の評価指標を紹介する。

(2) 相関ルールの評価指標

  データベースの中から相関ルールを検出する際、何らかの評価指標が必要である。多く用いられている指標としては支持度 (support)、確信度 (confidence) 、リフト (lift) がある。データベースは、トランザクションの集合 D = { t 1 , t 2 , … , t M } であり、各々のトランザクションは、アイテム集合 I all = { i 1 , i 2 , … , i k } の子集合により構成されている。つまり、任意のトランザクション t j は、アイテムの集合 I j を持つ ( I j I all )。かつ、その子集合は空集合ではない。つまり、データベースから検出されるアイテムの相関ルール XY は、X , YI 、かつXY = φ である。
  データベース中の、アイテム集合X を含むトランザクションの数をX の支持度数と呼び、σ(X ) を用いて表す。例えば、表1の中には X = { オムツ、ビール } を含むトランザクションは3つあるので、その支持度数は σ(X ) = 3 である。
  ルールXY の支持度は、アイテム集合XY を含むトランザクションが全体の中に占める比率で定義されている。

式1 X⇒Yの支持度

  確信度とは、アイテム集合XY を含むトランザクションの数σ (XY ) を、条件X を含むトランザクションの数σ (X ) で割った値である。

式2 確信度

  リフトは、確信度をsupp (Y ) で割った値で定義されている。これは確率 Pr(XY ) / Pr (X ) Pr (Y ) の近似値である。

式3 lift(X⇒Y)

  例えば、X = { オムツ }、Y = { ビール } とすると、表1ではσ (X ) = 3、σ (X ) = 4 、σ (XY ) = 3、M = 5 であり、支持度、確信度、リフトの値はそれぞれsupp (XY ) = 3/5 = 0.6、conf (XY ) 3/3 = 1、lift (XY ) = 1/(4/5) = 1.25 である。
  支持度が低いほど、そのルールが現れる比率が低い。しかし、アイテム数が多い、大きいデータベースの中では、個別のアイテムの支持度が大きい値になることは期待できない。ルールの評価は、支持度、確信度、リフトを総合的に考慮する必要がある。

(3) Apriori アルゴリズム

  相関ルール抽出の問題は、G.Piatetsky- Shapiro[1]、R.Agrawal 氏ら[2]の研究に端を発する。R. Agrawal 氏らは、1994年に高速で相関ルールを検出する Apriori アルゴリズムを発表した[3]。その後、Apriori アルゴリズムを改良した幾つかのアルゴリズムが登場しているが、多くのソフトパッケージは、Apriori アルゴリズムに基づいている。Apriori アルゴリズムには頻出アイテム検出、相関ルール検出などいくつかがあるが、本項では、最も基本となる頻出アイテムを検出するアルゴリズムのみを示す。アルゴリズムを簡潔に示すため、次に示す記号を導入する。

  D : トランザクションのデータベース
  σ : 最小支持度数
  F [I s ] (D, σ ) : データベースの中の最小支持度数を満たすアイテムの集合
  C k: k アイテムの候補集合
  L k: k アイテムの頻出アイテム集合

  Apriori の頻出アイテム抽出のアルゴリズム

Aprioriの頻出アイテム抽出のアルゴリズム

C k = apriori_gen ( L k-1 : K-1 ) アイテム頻出集合L k-1 からk アイテム候補集合C k を生成
C kt = subset (C k , t ) :C k とトランザクションの照合により頻出のk アイテムの候補を生成

3.パッケージと解析の例

(1) パッケージ arules とデータ形式

  Rのパッケージ arules には、Apriori アルゴリズムに基づいた相関ルールを検出する関数がある。ここでは、パッケージ arules を用いてアソシエーション分析について説明する。パッケージ arules は CRAN ミラーサイトからダウンロードできる。
  パッケージ arules で扱うデータの形式は、基本的には質的データの、data.frame、tidLists、dgCMatrix、itemMatrix、transaction、matrix 形式を直接・間接に扱う。全体像を把握するため、図1にパッケージ arules のデータ処理とデータ形式の関連関係を示す。これらのデータ形式は関数 as を用いて変換することが可能である。

図1 データ処理とデータ形式の関連関係[4]

図1 データ処理とデータ形式の関連関係 [4]

  表記を簡潔にするため、表1のアイテム名称を a = パン、b = 牛乳、c = ハム、d = 果物、e = オムツ、f = ビール、g = ソーセージ、h = 弁当、i = タバコ、j = オレンジジュースと表し、表2に示す。表 2(b) では、バスケットにあるアイテムは1、バスケットにないものは0で表す。表 2(c) は、各アイテムとトランザクションの番号との関係である。頻出アイテム検出アルゴリズムは、このようなデータ構造のいずれかを用いる。

表2 2種類のデータ表記 (a)
TID アイテム
1
 {a,b,c,d}
2
 {a,e,f,g}
3
 {e,f,g}
4
 {e,f,h,i}
5
 {d,f,h,j}

(b)
TID a b c d e f g h i j
1 1 1 1 1 0 0 0 0 0 0
2 1 0 0 0 1 1 1 0 0 0
3 0 0 0 0 1 1 1 0 0 0
4 0 0 0 0 1 1 0 1 1 0
5 0 0 0 1 0 1 0 1 0 1

(c)
アイテム TID
a 1,2
b 1
c 1
d 1,5
e 2,3,4
f 2,3,4,5
g 2,3
h 4,5
i 4
j 5

  表2(a)形式のデータを入力する例を次に示す。次のように入力したデータはリスト形式になっている。

> data1<- list(c("パン","牛乳","ハム","果物"),c("パン","オムツ","ビール","ハム"),c("ソーセージ","ビール","オムツ"),c("弁当","ビール","オムツ","タバコ"),c("弁当","ビール","オレンジジュース","果物"))
> class(data1)
[1] "list"

  リスト形式のデータは関数 as を用いて、transaction、あるいは itemMatrix などの形式に変換することができる。

> data.tran<-as(data1,"transactions")
> class(data.tran)
[1] "transactions"
attr(,"package")
[1] "arules"

  また、transaction、itemMatrix 形式のデータは、次のように matrix、data.frame 形式に変換することができる。

> as(data.tran,"matrix")

オムツ オレンジジュース ソーセージ タバコ ハム パン ビール 果物 牛乳 弁当
[1,] FALSE FALSE FALSE FALSE TRUE TRUE FALSE TRUE TRUE FALSE
[2,] TRUE FALSE FALSE FALSE TRUE TRUE TRUE FALSE FALSE FALSE
[3,] TRUE FALSE TRUE FALSE FALSE FALSE TRUE FALSE FALSE FALSE
[4,] TRUE FALSE FALSE TRUE FALSE FALSE TRUE FALSE FALSE TRUE
[5,] FALSE TRUE FALSE FALSE FALSE FALSE TRUE TRUE FALSE TRUE

>as(data.tran,"data.frame")

items
{ハム, パン, 果物, 牛乳}
{オムツ, ハム, パン, ビール}
{オムツ, ソーセージ, ビール}
{オムツ, タバコ, ビール, 弁当}
{オレンジジュース, ビール, 果物, 弁当}

  データファイルから直接読み込むこともできる。表 2(b) のようなデータを関数 read.transactions を用いて直接 transaction 形式に読み込むこともできる。勿論、表 2(b) 形式のデータを matrix 形式に読み込み、transaction、itemMatrix 形式に変換して用いることも可能である。
  データを処理する際には、まずデータの概観を把握することが重要である。パッケージ arules には、トランザクションデータのアイテムの頻度の棒グラフを作成する関数 itemFrequency がある。引数 type で、絶対度数、相対度数を指定することができる。デフォルトには相対度数 type = "relative" になっている。作成したデータ data.tran の絶対度数の棒グラフの例を次に示す。

> itemFrequencyPlot(data.tran,type = "absolute")

図2 data.tranのアイテムの棒グラフ

図2 data.tran のアイテムの棒グラフ

  アイテム数が多い場合は、引数 suppor を用いて度数が低いアイテムを取り除くことができる。次にサポート値が2以上のアイテムの棒グラフを作成するコマンドの例を示す。

> itemFrequencyPlot(data.tran,type = "absolute",support=2)
<図は省略>

(2) 関数 apriori

  パッケージ arules の中には、相関ルールを抽出する関数 apriori がある。その書き式を次に示す。

apriori(data, parameter = NULL, appearance = NULL, control = NULL)

  データは、transaction、itemMatrix、matrix、data.frame などの形式を扱う。引数 parameter では、支持度 (support)、確信度 (confidence)、頻出アイテムの最大数 (maxlen: maximum size of mined frequent item sets) をリスト形式で指定する。デフォルト値は support = 0.1, confidence = 0.8, maxlen = 5 になっている。引数 appearance では、アイテムの扱いを指定することができるが、デフォルトでは特別な指定が行われていない。引数 control では、アルゴリズムのパフォーマンスを制御する。

例1

  入力したデータ data.tran を用いた使用例を次に示す。ただし、引数はデフォルト値を用いる。

> data.ap<-apriori(data.tran)

data.ap<-apriori(data.tran)の

  返された結果は、アルゴリズム実行のパラメータ仕様、抽出されたルールの数など基本的な情報である。検出されたルールの数は70である。関数 print を用いて検出されたルールの数を返すこともできる。

> print(data.ap)
set of 70 rules

  この例のような僅か5つのトランザクション、10個のアイテムの小さいデータセットでも70に上るルールが抽出されているので、大規模のデータベースで抽出されるルールの数は膨大であり、すべてを詳細に読むのは非現実的である。
  検出されたルールは、関数 inspect を用いて呼び出す。呼び出す際には、評価指標などを制約条件として加えることが可能である。例として、支持度 (support) を基準としてソートした上位6位のルールを呼び出すコマンドを次に示す。

> inspect(head(sort(data.ap, by = "support"),n=6))

lhs rhs support confidence lift
[1] {} => {ビール} 0.8 0.8 1.000000
[2] {オムツ} => {ビール} 0.6 1.0 1.250000
[3] {パン} => {ハム} 0.4 1.0 2.500000
[4] {ハム} => {パン} 0.4 1.0 2.500000
[5] {弁当} => {ビール} 0.4 1.0 1.250000
[6] {ソーセージ} => {オムツ} 0.2 1.0 1.666667

  呼び出した結果は、左からルールの条件部 (lhs)、結論部 (rhs)、支持度 (support)、確信度 (confidence)、リフト (lift) の順に並べて返す。 支持度が最も高いアイテムは{ビール}で、支持度が最も高い相関ルールは「{オムツ} => {ビール}」である。
  引数 parameter を指定し直すことで、ルールの数をコントロールすることができる。次のようにパラメータの設定を行うと、54個のルールが検出される。maxlen = 3 になっているので、検出された1つのルールの中のアイテム数は最大3である。例えば、結果の第20番のルール「{牛乳,果物,} => {ハム}」のアイテム数は3である。

> data.ap1<-apriori(data.tran,parameter = list(supp =0.2,maxlen=3))
> inspect(head(SORT(data.ap1, by = "support"), n = 20))

lhs rhs support confidence lift
[1] {} => {ビール} 0.8 0.8 1.000000
[2] {オムツ} => {ビール} 0.6 1.0 1.250000
[3] {パン} => {ハム} 0.4 1.0 2.500000
[4] {ハム} => {パン} 0.4 1.0 2.500000
[5] {弁当} => {ビール} 0.4 1.0 1.250000
[6] {ソーセージ} => {オムツ} 0.2 1.0 1.666667
[7] {ソーセージ} => {ビール} 0.2 1.0 1.250000
[8] {牛乳} => {パン} 0.2 1.0 2.500000
[9] {牛乳} => {果物} 0.2 1.0 2.500000
[10] {牛乳} => {ハム} 0.2 1.0 2.500000
[11] {タバコ} => {弁当} 0.2 1.0 2.500000
[12] {タバコ} => {オムツ} 0.2 1.0 1.666667
[13] {タバコ} => {ビール} 0.2 1.0 1.250000
[14] {オレンジジュース} => {果物} 0.2 1.0 2.500000
[15] {オレンジジュース} => {弁当} 0.2 1.0 2.500000
[16] {オレンジジュース} => {ビール} 0.2 1.0 1.250000
[17] {オムツ,ソーセージ} => {ビール} 0.2 1.0 1.250000
[18] {ソーセージ,ビール} => {オムツ} 0.2 1.0 1.666667
[19] {パン,牛乳} => {果物} 0.2 1.0 2.500000
[20] {果物,牛乳} => {パン} 0.2 1.0 2.500000

  相関ルールの概念に関する説明に関しては[5,6,7]があり、アルゴリズムに関しては[8]がある。
  次の号では、リアルのデータを用いて説明を深めると同時に、Eclatアルゴリズムなどについて説明する。

参考文献:
[1] G. Piatetsky-Shapiro(1991). Discovery, analysis, and presentation of strong rules. In G. Piatetsky-Shapiro and W. J. Frawley, editors, Knowledge Discovery in Databases. AAAI/MIT Press, Cambridge, MA.
[2] R. Agrawal, T. Imielinski, and A. Swami(1993). Mining association rules between sets of items in large databases. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, pages 207-216.
[3] R. Agrawal and R. Srikant(1994). Fast algorithms for mining association rules. In J. B. Bocca, M. Jarke, and C. Zaniolo, editors, Proc. 20th Int. Conf. Very Large Data Bases, VLDB, pages 487-499. Morgan Kaufmann, 12-15 September.
[4] Michael Hahsler and Bettina Gr?n and Kurt Hornik(2005). arules - A Computational Environment for Mining Association Rules and Frequent Item Sets. Journal of Statistical Software, Volume 14, Issue 15.
[5] 江原淳、佐藤栄作共訳(1999):データマイニング手法、KAIBUNDO
[6] 豊田秀樹(2001):金鉱を掘り当てる統計学、講談社
[7] 山口和範、高橋淳一、竹内光悦(2004):よくわかる多変量データ解析の基本と仕組み、秀和システム
[8] 福田剛志、徳山豪、森本康彦(2001):データマイニング、共立出版