[連載]フリーソフトによるデータ解析・マイニング第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={t1,t2,…,tM}であり、各々のトランザクションは、アイテム集合Iall={i1,i2,…,ik}の子集合により構成されている。つまり、任意のトランザクションtjは、アイテムの集合Ij,を持つ(IjIall )。かつ、その子集合は空集合ではない。つまり、データベースから検出されるアイテムの相関ルール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[Is](D,σ):データベースの中の最小支持度数を満たすアイテムの集合
Ck:kアイテムの候補集合
Lk:kアイテムの頻出アイテム集合

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

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

Ck=apriori_gen(Lk-1:K-1アイテム頻出集合Lk-1からkアイテム候補集合Ckを生成
Ckt=subset(Ck,t):Ckとトランザクションの照合により頻出の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")
as(data.tran,

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

 データファイルから直接読み込むこともできる。表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では、アルゴリズムのパフォーマンスを制御する。

例3.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))
inspect(head(SORT(data.ap, by =

 呼び出した結果は、左からルールの条件部(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))
inspect(head(SORT(data.ap, by =

 相関ルールの概念に関する説明に関しては[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). データマイニング、共立出版