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

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

  先月号では、相関ルール抽出に関して架空のデータを用いて説明した。その続きとして、リアルのデータを用いて説明をする。
  パッケージ arules の中には幾つかのリアルのデータセットが用意されている。その中の1つがデータセット Income である。データセット Income は、サンフランシスコベイエリアの、あるショッピングモールの顧客9409人が回答したアンケート結果のデータ (IncomeESL) の中から、欠損値を含んでいるものを取り除き、整理したものである。データ IncomeESL は表3に示す14項目に対する回答結果である。表の中のデータのタイプの「順序」は順序尺度、「名義」は名義尺度を指す。表3の変数の数は合計84である。データ Income の中の、順序尺度は調整されているので表3とは異なる。例えば、表3の「収入」項目の変数の数は9になっているが、データ Income では2つ($0-$40,000,$40,000+)に併合されている。データ Income の中の変数の数は合計50である。

表1 アンケート票の項目
項目番号 項目 変数の数 データのタイプ
1
 収入(income)
9 順序
2
 性別(sex)
2 名義
3
 結婚歴(marital status)
5 名義
4
 年齢(age)
7 順序
5
 学歴(education)
6 順序
6
 職業(occupation)
9 名義
7
 ベイエリアでの居住歴(years in Bay Area)
5 順序
8
 夫婦収入(dual income)
3 名義
9
 家族の数(number in household)
9 順序
10
 子供の数(number of children)
10 順序
11
 居住家屋状況(householder status)
3 名義
12
 家の形態(type of home)
5 名義
13
 人種の分類(ethnic classification)
8 名義
14
 自宅での使用言語(language in home)
3 名義

  データの外観を把握するため、変数ごとの相対頻度の棒グラフを関数 itemFrequencyPlot で作成し、図3に示す。棒の長さは項目内での相対頻度である。

> data(Income)
> Income

transactions in sparse format with 6876 transactions (rows) and 50 items (columns)

> par(mar=c(4.5,2,1,2),cex=0.8, cex.axis=0.9)
> itemFrequencyPlot(Income, col="lightblue",horiz=T)

図3 データIncomeの変数の相対頻度

図3 データ Income の変数の相対頻度

  関数 apriori のデフォルト値でルール抽出を行うと、抽出されるルールの数は6346に上る。関数 summary はルールの総数、アイテムの数別のルール数、評価指標の基本統計量を返す。

> Income.ap<-apriori(Income)
<中略>
writing ... [6346 rule(s)] done [0.02s].
creating S4 object ... done [0.03s].

> summary(Income.ap)

set of 8664 rules
rule length distribution (lhs + rhs): sizes

1 2 3 4 5 6 7 8
1 56 615 2287 3387 1925 385 8

Min. 1st Qu. Median Mean 3rd Qu. Max.
1.000 4.000 5.000 4.888 6.000 8.000

summary of quality measures:
support
confidence
lift
Min.
:
0.1001
Min.
:
0.8000
Min.
:
0.8971
1st Qu.
:
0.1101
1st Qu.
:
0.8436
1st Qu.
:
1.0813
Median
:
0.1241
Median
:
0.9027
Median
:
1.3297
Mean
:
0.1393
Mean
:
0.9021
Mean
:
1.4099
3rd Qu.
:
0.1510
3rd Qu.
:
0.9574
3rd Qu.
:
1.5309
Max.
:
0.9129
Max.
:
1.0000
Max.
:
4.3554

data ntransactions support confidence
Income 6876 0.1 0.8

  抽出したルールを呼び出す方法はいろいろある。支持度、確信度、リフトの値をソートして呼び出す方法、条件部、結論部に何らかの制約条件を加える方法などがある。
  例として、結論部が高収入 (income=$40,000+) であるルールを呼び出すコマンドを次に示す。次のコマンドのように、評価指標 (support, confidence, lift) を条件として組み合わせることも可能である。

> Income.ap2 <- subset(Income.ap, subset = rhs %in% "income=$40,000+" & lift>2)
> inspect(sort(Income.ap2)[1:3])

lhs
rhs
support
confidence
lift
[1] {occupation=professional/managerial,
householder status=own}
=> {income=$40,000+} 0.1384526 0.8074640 2.138722
[2] {occupation=professional/managerial,
householder status=own,
language in home=english}
 => {income=$40,000+} 0.1336533 0.8075571 2.138969
[3] {dual incomes=yes, householder
status=own}
=> {income=$40,000+} 0.1260908 0.8156162 2.160315

  条件部と結論部に何らかのアイテムを含む制約条件を付けることも可能である。例として、条件部に学歴 (education) に関するアイテムを含み、結論部に収入 (income) に関するアイテムを含むルールを呼び出すコマンドを次に示す。

> Income.ap3<-subset(Income.ap, subset = lhs %pin% "education" & rhs %pin% "income")
> inspect(sort(Income.ap3,by="lift")[1:3])

lhs
rhs
support
confidence
lift
[1] {education=college graduate,
householder status=own,
ethnic classification=white,
language in home=english}
=> {income=$40,000+} 0.1002036 0.8115430 2.149526
[2] {education=college graduate,
householder status=own,
type of home=house,
language in home=english}
=> {income=$40,000+} 0.1031123 0.8112128 2.148652
[3] {marital status=married,
education=college graduate,
language in home=english}
=> {income=$40,000+} 0.1121291 0.8090241 2.142854

  コマンドの中の「lhs %pin% "education"」は条件部に education を含むことを意味する。
  パッケージ arules の中には、トランザクションデータセット Groceries がある。Groceries は典型的なローカルの食料雑貨店の POS データである。アイテムが169カテゴリに分類された9835のトランザクションにより構成されている。このようにカテゴリの数が多い場合には、次のようにデータを区切って関数 itemFrequencyPlot を用いることが可能である。

> data(Groceries)
> itemFrequencyPlot(Groceries[,1:55])
> itemFrequencyPlot(Groceries[,56:110])
> itemFrequencyPlot(Groceries[,111:169])
<図は省略>

  次のようにデフォルト値のまま関数 apriori を実行すると1つのルールも抽出されない。

> Gr.ap<-apriori(Groceries)
> Gr.ap
set of 0 rules

  これは、デフォルトのパラメータ値が、support = 0.8, confidence = 1 と高いのが原因である。トランザクションの中のアイテム数が多く、ばらつきが大きいときには support 値が高いためにルールが得られない場合が少なくない。そこで次のようにパラメータの値を下げて、関数 apriori を実行すると相関ルールが検出される。

> Gr.ap <- apriori(Groceries,parameter = list(support=0.005,confidence=0.01))
> summary(Gr.ap)
set of 2138 rules

rule length distribution (lhs + rhs):
1 2 3 4
88 1210 792 48
<後略>

  このように、2138のルールが検出されている。結論部の beef に注目したルールを呼び出す例を次に示す。

> beefRules <- subset(Gr.ap,subset= rhs %in% "beef")
> inspect(head(sort(beefRules,by= "confidence"),n=6))

lhs
rhs
support
confidence
lift
[1] {root vegetables,other vegetables} => {beef} 0.007930859 0.1673820 3.190313
[2] {root vegetables,whole milk} => {beef} 0.008032537 0.1642412 3.130449
[3] {root vegetables} => {beef} 0.017386884 0.1595149 3.040367
[4] {other vegetables,rolls/buns} => {beef} 0.005795628 0.1360382 2.592898
[5] {pork} => {beef} 0.007625826 0.1322751 2.521174
[6] {other vegetables,whole milk} => {beef} 0.009252669 0.1236413 2.356613

4.頻出アイテムの抽出

(1) Eclatアルゴリズム

  アソシエーション分析に関しては、Apriori アルゴリズム以外にも幾つかのアルゴリズムが提案されている。そのアルゴリズムの基本は木構造のデータ検索である。木構造検索アルゴリズムは、大きく分けて、幅優先検索 (BFS: Breadth first search) と深さ優先検索 (DFS: Depth firdt search) に分けることができる。Apriori アルゴリズムは幅優先 (BFS) の方法でトランザクションをスキャンする検索アルゴリズムに属する。
  パッケージ arules の中には、Eclat (Equivalence CLAss Transformation) アルゴリズムの関数 eclat がある[1]。関数 eclat は、頻出アイテムを検索するアルゴリズムで、深さ優先 (DFS) の方法でアイテムをスキャンする。アルゴリズム Apriori と Eclat の違いは、コンピュータのメモリの占用や計算時間に関わる問題であるので、深い議論は省略する。
  実証研究によると、Eclat アルゴリズムは、最小支持度の減少による性能の悪化が Apriori より少ないが、頻出アイテムが多いときには、性能が悪くなる可能性がある。次に頻出アイテム抽出の Eclat アルゴリズムを示す。

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

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

(2) 関数 eclat と例

  関数 eclat の書き式を次に示す。基本的な書き式は関数 apriori と同じであるが、引数 parameter で指定するのは支持度とアイテムの最大数で、デフォルト値は support = 0.1, maxlen = 5 になっている。

eclat(data, parameter = NULL, control = NULL)

  関数 eclat が返す結果は、相関ルールXY ではなく、頻出するアイテムの組み合わせの集合{X , Y } である。
  先月号の表1のデータを用いた例を示す。

> data.ec<-eclat(data.tran)
> inspect(sort(data.ec,by="support")[1:5])

items support
1 {ビール} 0.8
2 {オムツ,ビール} 0.6
3 {オムツ} 0.6
4 {ビーツ,弁当} 0.4
5 {パン,ハム} 0.4

  アイテムの組み合わせに注目する際には、1つのアイテムの結果は必要ではない。パッケージの中には関数 size があり、次のようにアイテム数を指定して呼び出すことが可能である。

> data.ec2 <- data.ec[size(items(data.ec)) ==2]
> inspect(sort(data.ec2,by="support")[1:5])

items support
1 {オムツ,ビール} 0.6
2 {ビーツ,弁当} 0.4
3 {パン,ハム} 0.4
4 {ビール,ソーセージ} 0.2
5 {オムツ,ソーセージ} 0.2

  返された結果から分かるように、支持度が最も高い2つのアイテムの組み合わせセットは、{オムツ、ビール}である。この結果は apriori の結果と同じである。
  次にデータ Income を用いた例を示す。

> Income.ec<-eclat(Income)

  関数 apriori の場合と同じく、制約条件を付けて、頻出アイテムセットを呼び出すことができる。ただし、eclat が返す結果には、条件部、結果部のようなものがなく、アイテムセット (items) と支持度 (support) のみである。
  関数 subset を用いて、条件を満たす結果を呼び出すことができる。アイテムセットの中に "income = $40,000 + " を含み、支持度が0.2以上で、かつアイテムの数が2以上のものを抽出するコマンド例を次に示す。

> Income.ec2 <- subset(Income.ec,subset = items %in% "income=$40,000+" & support>0.2 & size(items)>2)
> Income.ec2
set of 17 itemsets
> inspect(sort(Income.ec2,by="support")[1:3])

items
support
[1] {income=$40,000+, ethnic classification=white,
language in home=english}
0.2789412
[2] {income=$40,000+, type of home=house,
language in home=english}
0.2613438
[3] {income=$40,000+, number in household=1,
language in home=english}
0.2523269

5.補助分析

  場合によっては、検出したルール、あるいは頻出アイテムについて、クラスター分析を行い、クラスの特徴を考察することが必要な場合がある。パッケージ arules には、トランザクション、アイテム、相関ルール、頻出アイテムの距離を求める関数 dissimilarity がある。関数 dissimilarity の書き式を次に示す。引数 method では、バイナリデータの距離[2]、"jaccard"、"matching"、"dice"、"affinity" を指定する。デフォルトには "jaccard" が指定されている。

dissimilarity(x, y = NULL, method = NULL, args = NULL, ...)

  ここでは、データ Income の相関ルールの結論部が高収入 (income = $40,000 + ) であるルールについて、階層的クラスターリンク法を用いた分析の例を示す。

> Income.ap<-apriori(Income)
> rules.sub <- subset(Income.ap, subset = rhs %in% "income=$40,000+" & lift>2)
> d<-dissimilarity(rules.sub)
> plot(hclust(d,"ward.D"),hang=-1)

図4 ルールのクラスター樹形図

図4 ルールのクラスター樹形図

  階層的クラスター樹形図から、大まかに2つか4つのクラスに分けられることが考えられる。仮に4つのクラスに分けると、樹形図の葉を左からカウントして class1 = {1:7}、class2 = {8:13}、class4 = {14:23}、class4 = {24:29} となる。葉の番号は関数 hclust の結果オブジェクトの $order で呼び出すことが可能である。

> class1<-hclust(d,"ward.D")$order[1:7]
> inspect(rules.sub[class1])

lhs
rhs
support
confidence
lift
[1] {occupation=professional/managerial,
householder status=own, ethnic
classification=white}
=> {income=$40,000+} 0.1080570 0.8155873 2.160238
[2] {occupation=professional/managerial,
householder status=own, ethnic classification=white,
language in home=english}
=> {income=$40,000+} 0.1077661 0.8169791 2.163924
[3] {occupation=professional/managerial,
householder status=own,
type of home=house}
=> {income=$40,000+} 0.1192554 0.8175474 2.165430
[4] {occupation=professional/managerial,
householder status=own, type of home=house,
language in home=english}
=> {income=$40,000+} 0.1148924 0.8178054 2.166113
[5] {occupation=professional/managerial,
householder status=own,
language in home=english}
=> {income=$40,000+} 0.1336533 0.8075571 2.138969
[6] {age=35+, occupation=professional/managerial,
householder status=own}
=> {income=$40,000+} 0.1052938 0.8264840 2.189100
[7] {age=35+, occupation=professional/managerial,
householder status=own,
language in home=english}
=> {income=$40,000+} 0.1012216 0.8246445 2.184228

  返された結果から、クラス1は居住家屋状況 (householder status = own) と高収入との関連性に関するルールであることが分かる。 次の結果からは、クラス2は学歴 (education = college graduate) と高収入との関連性に関するルールであることが分かる。

> class2<-hclust(d,"ward,D")$order[8:13]
> inspect(rules.sub[class2])

<結果は省略>

  同じく次のコマンドでクラス3、クラス4の相関ルールを呼び出すことができる。

> class3<-hclust(d,"ward.D")$order[14:23]
> inspect(rules.sub[class3])

<結果は省略>

> class4<-hclust(d,"ward.D")$order[24:29]
> inspect(rules.sub[class4])

<結果は省略>

  クラス3、4は、職業 (occupation = professional/managerial) と高収入との関連性に関するルールである。
  関数 eclat の結果について、類似の分析を行うことも可能である。ここでは、階層的クラスター分析の例のみを示しているが、距離データを用いてその他のデータ解析を行うことも可能である。
  誌面上の制約により、パッケージ arules に実装されている2種類のアルゴリズムに基づいて、相関ルールおよび頻出アイテム抽出について説明した。パッケージ arules の中には、トランザクションデータにおけるサンプリング関数 sample、モデルの予測関数 predict、アイテムのクロス表を求める関数 crossTable、2値データを図示する関数 image,ルールの評価指標被覆率を求める関数 coverage などが用意されているが、触れることができなかった。また、パッケージ Rweka には2つのタイプの相関ルール関数 Apriori、Tertius がある。

参考文献:
[1] M. J. Zaki, S. Parthasarathy, M. Ogihara, and W. Li. (1997) New algorithms for fast discovery of association rules. Technical Report 651, Computer Science Department, University of Rochester, Rochester, NY 14627.
[2] B. Goethals(2004). Memory issues in frequent itemset mining, Proceedings of the 2004 ACM symposium on Applied computing, 530 - 534