Takeのベンチマークテスト(FIT2018)

FIT2018 に発表した原稿 1 に掲載されたTakeパッケージの利用方法に関するスクリプトについて説明する。 そこでは3つのスクリプトが掲載されており、ランク情報に基づく相関ルール分析、バイクラスタリング、 そして、Take と Orange3-associate のベンチマークテストに関するものである。 いずれもデータとして「 online retailデータセット 」を利用している。

準備

本節で扱っているPythonスクリプトの全ては github よりダウンロードできる。 ただし、既に「 mcmdのベンチマークテスト(FIT2018) 」の節を実行済みであれば、同じものなのでダウンロードの必要はない。 ダウンロードしたディレクトリ下 bench/fit2018/nysol_take に 以下の4つのスクリプトがある。

  • mkdata.py : online retailデータセットのダウンロードとデータクリーニング用スクリプト

  • bench.py : Orange3とのベンチマーク用スクリプト( リスト 27 )

  • friends.py : 原稿のfig.1に示されたランク情報に基づいた2アイテム相関ルールの視覚化のスクリプト( リスト 28 )

  • bicluster.py : 原稿のfig.3に示されたバイクラスタリングのスクリプト( リスト 29 )

リスト 23 ベンチマークスクリプトのダウンロード
1$ git clone https://github.com/nysol/bench.git
2$ cd bench/fit2018/nysol_take

takeベンチマークテスト(vs. Orange3)

nysol.takeの処理速度を評価するにあたって、Pythonで利用可能なデータマイニングモジュール Orange3-associate をベンチマークとする速度比較テストを実施した。 Orange3-associateモジュールは、機械学習のパッケージ Orange3 のアドオンパッケージであり、 Orange3のインストールも必要となる。

利用データ

利用したデータは、「 オンラインストア購買データ 」節で解説されている オンラインストアの購買履歴データである。 上述のgitからダウンロードしたスクリプト mkdata.py を実行すれば、 DATAディレクトリの下にデータが生成される( リスト 24 )。 20〜30分ほど時間を要する。 基本データの生成は直ぐに終わるが、ベンチマークテストのために、基本データを定数倍したデータを生成している。 これは、単に基本データをそのまま定数回コピーして作成するのではなく、 トランザクション毎に30%ほどのアイテムをランダムに入れ替える処理を行っており、 その作業に20〜30分の時間を要する。 データは リスト 25 に例示されるような8項目の54万行ほどのデータである。

リスト 24 オンラインストア購買履歴データの取得スクリプトの実行
 1$ ./mkdata.py
 2downloading original dataset...
 3reading xlsx...
 4writing xlsx as tsv...
 5#END# kgtab2csv i=./DATA/onlineRetail.tsv o=./DATA/online_all.csv; IN=541910 OUT=541909; 2018/09/15 13:41:52; 2018/09/15 13:41:52
 6#END# kgcut f=InvoiceNo,StockCode i=./DATA/online_all.csv; IN=541909 OUT=541909; 2018/09/15 13:41:52; 2018/09/15 13:41:52
 7#END# kguniq k=InvoiceNo,StockCode; IN=541909 OUT=531225; 2018/09/15 13:41:52; 2018/09/15 13:41:52
 8#END# kgfldname -q o=./DATA/onlineM_all.csv; IN=531225 OUT=531225; 2018/09/15 13:41:52; 2018/09/15 13:41:52
 9#END# kgcut f=StockCode i=./DATA/online_all.csv; IN=541909 OUT=541909; 2018/09/15 13:41:52; 2018/09/15 13:41:52
10#END# kguniq k=StockCode; IN=541909 OUT=4070; 2018/09/15 13:41:52; 2018/09/15 13:41:52
11#END# kgnumber a=num s=StockCode; IN=4070 OUT=4070; 2018/09/15 13:41:52; 2018/09/15 13:41:52
12#END# kgjoin f=num i=./DATA/online_all.csv k=StockCode; IN=541909 OUT=541909; 2018/09/15 13:41:53; 2018/09/15 13:41:53
13#END# kgcut f=InvoiceNo,num:StockCode; IN=541909 OUT=541909; 2018/09/15 13:41:53; 2018/09/15 13:41:53
14#END# kgtra f=StockCode k=InvoiceNo; IN=541909 OUT=25900; 2018/09/15 13:41:53; 2018/09/15 13:41:53
15#END# kgcut -nfno f=StockCode o=./DATA/onlineT_all.csv; IN=25900 OUT=25900; 2018/09/15 13:41:53; 2018/09/15 13:41:53
16START enlarge 10
170
181
19:
20START enlarge 100
210
221
23:
24START enlarge 1000
250
261
27:
28999
リスト 25 オンラインストア購買履歴データ
1$ head onlineRetail.csv
2InvoiceNo,StockCode,Description,Quantity,InvoiceDate,UnitPrice,CustomerID,Country
3536365,85123A,WHITE HANGING HEART T-LIGHT HOLDER,6,2010-12-01 08:26:00,2.55,17850.0,United Kingdom
4536365,71053,WHITE METAL LANTERN,6,2010-12-01 08:26:00,3.39,17850.0,United Kingdom
5   :     :     :     :

リスト 25 に示されたデータから、 TakeとOrangeの頻出アイテム列挙メソッドで用いるトランザクションデータを作成した。 InvoiceNo を単位に StockCode をアイテムとするトランザクションデータである。 さらに、アイテム数はそのままに、オリジナルデータに3割のノイズを乗せたデータを追加し、 サイズ違いのデータ(s-10:10倍,s-100:100倍,s-1000:1000倍)を用意した。 トランザクションデータは リスト 26 に示されるように、 行をトランザクションとし、0から始まる整数をアイテム番号としたスペース区切りのデータである。 全データセットのサイズは、 表 17 に示される通りである。

リスト 26 トランザクションデータ
1$ head onlineO_all.basket
2800,1662,3044,3536,2984,2985,2794
31547,1546
43372,817,2770,1659,816,3305,1655,829,1247,1536,1658,1537
51816,1817,1862,1815
6818
7 :
表 17 ベンチマークに用いたデータ一覧

名称

トランザクション数

item数

サイズ

内容

org

25,900

4070

2,559,662

オリジナルのデータ

s-10

259,000

4070

25,238,529

orgを10倍したデータ

s-100

2,590,000

4,070

252,014,860

orgを100倍したデータ

s-1000

25,900,000

4,070

2,519,826,014

orgを1000倍したデータ

処理内容

評価に使ったコードは、 リスト 27 に示される通りである。 頻出アイテム集合の列挙には、 Orange3-associateでは、frequent_itemsetsメソッドを、Takeからはlcmメソッドを利用した。 計測結果は、 OUTPUT/bench/bench_5.txt に出力される。 TakeのcoreメソッドのTakeのlcmはOrangeのfrequent_itemsetに比べて、 3-4倍高速であることがわかる。

リスト 27 ベンチマークスクリプト
 1#!/usr/bin/env python
 2# -*- coding: utf-8 -*-/
 3import os
 4import sys
 5import time
 6from pprint import pprint
 7
 8import nysol.take.extcore as ntc
 9import Orange
10from orangecontrib.associate.fpgrowth import *
11
12loop=5
13
14iPath=root="./DATA"
15oPath=root="./OUTPUTS/bench"
16os.system("mkdir -p %s"%(oPath))
17oFile="%s/bench_%d.txt"%(oPath,loop)
18
19# takeの頻出アイテム列挙メソッドlcmの実行
20def L1(iFile,minFreq):
21        ntc.lcm(type="Ff",sup=minFreq,i=iFile,o="xxrsl11")
22
23# Orange3-associateの頻出アイテム列挙メソッドfrequent_itemsetsの実行
24def O1(iFile,minFreq):
25        tbl = Orange.data.Table(iFile)
26        X, mapping = OneHot.encode(tbl)
27        itemsets =frequent_itemsets(X, minFreq)
28
29sec={}
30mean={}
31params=[]
32
33params.append(["L1" ,   1,"%s/onlineT_all.csv"%iPath])
34params.append(["O1" ,   1,"%s/onlineO_all.basket"%iPath])
35params.append(["L1" ,  10,"%s/onlineT_size10.csv"%iPath])
36params.append(["O1" ,  10,"%s/onlineO_size10.basket"%iPath])
37params.append(["L1" , 100,"%s/onlineT_size100.csv"%iPath])
38params.append(["O1" , 100,"%s/onlineO_size100.basket"%iPath])
39params.append(["L1" ,1000,"%s/onlineT_size1000.csv"%iPath])
40params.append(["O1" ,1000,"%s/onlineO_size1000.basket"%iPath])
41
42for param in params:
43        func   =param[0]
44        size   =param[1]
45        iFile  =param[2]
46        minFreq=size*100
47        name="%s_%d"%(func,size)
48        print("START:",name)
49        sec[name]=[]
50        for i in range(loop):
51                st=time.time()
52                eval(func+'("%s",%d)'%(iFile,minFreq))
53                sec[name].append(time.time()-st)
54        mean[name]=0
55        for i in range(loop):
56                mean[name]+=sec[name][i]
57        mean[name]/=loop
58
59print("write to: ",oFile)
60with open(oFile, "w") as file:
61        pprint(sys.argv[0], stream=file)
62        pprint(loop, stream=file)
63        pprint(sec, stream=file)
64        pprint(mean, stream=file)

結果

出力結果をまとめたものを 表 18 に示している。 defは リスト 27 の関数名を表す。 org,s-10,s-100,s-1000は 表 17 に示したサイズ別データセットの名称である。

表 18 ベンチマークの結果(単位:秒)。

program

def

org

s-10

s-100

s-1000

Take.lcm

L1

0.269

1.427

19.39

250.3

Orange.frequent_itemsets

O1

0.569

5.598

58.72

778.4

ベンチマークテストを実施した計算環境は以下の通りである。

  • PC: MacPro(2013)

  • CPU: 2.7GHz 12-Core Intel Xeon E5

  • memory: 64GB

  • hdd: USB3 HDD

注釈

ここ以降の内容は、近い将来「 チュートリアル 」の節に移動します。

ランク情報に基づく相関ルール分析

相関ルール分析は、データマイニングの分野で代表的な分析手法で、 特にルールを高速に列挙する技術は飛躍的な進展を遂げてきた。 しかしながら、パラメータの設定次第では時に大量のルールが出力され、 そこから興味深いルールを抽出するまでにユーザに多大な負担を強いることも少なくない。

この問題を解決する一つの方法として相互ランク情報に基づいたルールの抽出方法が提案されている 2 。 Takeモジュールでは、 mfriends 及び mpal メソッドとして実装されている。 この手法の特徴は、相関ルール列挙において2アイテムルール \(A=>B(|A|=1,|B|=1)\) のみを列挙し、 そこから \(A,B\) 相互に関連の強いルールを選択するというものである。 \(A=>B\) 及び \(B=>A\) の評価指標(supportやconfidence)が、それぞれの前件部を共通としてもつルール集合の中で ユーザが指定した k 位以内であるとき、アイテム集合 \(A\) と \(B\) の関連が強いと考える。 リスト 28 は、OnlineStoreのデータから、そのようなルールを列挙するPythonコードである。 そして、グラフで視覚化した結果を 図 1 に示す。 赤い節点が一つのアイテムを示し、エッジが関連の強い結びつきを表している。

リスト 28 ルールの相互ランク情報に基づいた2アイテム相関ルールの列挙とその可視化を実現するスクリプト
 1#!/usr/bin/env python
 2# -*- coding: utf-8 -*-/
 3import os
 4import networkx as nx
 5
 6import matplotlib
 7matplotlib.use('Agg') # 追加
 8import matplotlib.pyplot as plt
 9
10import nysol.mcmd as nm
11import nysol.take as nt
12from nysol.util.margs import Margs
13
14iFile=("./DATA/online_all.csv")
15oPath=("./OUTPUTS/friends")
16os.system("mkdir -p %s"%oPath)
17
18# Make a similarity graph of StockCode: frequent 2-itemset enumeration
19
20# iFile
21# InvoiceNo,StockCode,Description,Quantity,InvoiceDate,UnitPrice,CustomerID,Country
22# 536365,85123A,WHITE HANGING HEART T-LIGHT HOLDER,6,2010/12/1 8:26,2.55,17850,United Kingdom
23# 536365,71053,WHITE METAL LANTERN,6,2010/12/1 8:26,3.39,17850,United Kingdom
24f=None
25f <<= nm.mcut(f="InvoiceNo,StockCode",i=iFile)
26f <<= nm.muniq(k="InvoiceNo,StockCode",o="%s/tra.csv"%oPath)
27f.run(msg="on")
28
29nt.mitemset(S=100,tid="InvoiceNo",item="StockCode",l=2,u=2,i="%s/tra.csv"%oPath,O=oPath).run()
30
31# patterns.csv
32# pid,size,count,total,support%0nr,lift,pattern
33# 86,2,833,25900,0.03216216216,8.209,22386 85099B
34# 501,2,784,25900,0.03027027027,17.1523,22697 22699
35# 129,2,733,25900,0.0283011583,7.4039,21931 85099B
36
37# Filitering the friend pairs of StockCode in the similarity graph of StockCode.
38f=None
39f <<= nm.msplit(f="pattern",a="item1,item2",i="%s/patterns.csv"%oPath)
40f <<= nm.mcut(f="item1,item2,lift",o="%s/rules.csv"%oPath)
41f.run(msg="on")
42
43nt.mfriends(ef="item1,item2",ei="%s/rules.csv"%oPath,sim="lift", rank=5, udout=True, eo="%s/friends.csv"%oPath).run()
44
45# visualization of the graph
46f=None
47f <<= nm.mcal(c="cat(\" \",$s{item1},$s{item2})", a="edges", i="%s/friends.csv"%oPath)
48f <<= nm.mcut(f="edges",nfno=True,o="%s/edges.csv"%oPath)
49f.run(msg="on")
50
51G = nx.read_edgelist("%s/edges.csv"%oPath)
52pos=nx.spring_layout(G)
53plt.figure(figsize=(10, 10))
54nx.draw(G, pos=pos,node_size=40,iterations=20)
55
56plt.savefig("%s/friends.png"%oPath)
../_images/friends.png

図 1 リスト 28 の実行結果

バイクラスタリング

顧客 \(v\in V\) が商品 \(u\in U\) を一定数以上購入していた時に枝を \((v,u)\in E\) を張るようような二部グラフ \(G=(V\cup U,E)\) について、枝が密に貼られている２つの部の部分集合 を抽出することで、 商品の購入パターンが似た顧客集合を得ることができる。 これはバイクラスタリングと呼ばれる手法である。 \(G\) 上の密な部分集合の定義としては、極大二部クリーク 4 を用いることができるが、 現実のデータにおいては例外的な接続関係が多く含まれるために、何の工夫もなければ、 多数のクリークが列挙されることとなり、 元のデータを小数のグループで表現するというクラスタリングの目的が損なわれてしまう。 そこで、与えられた二部グラフ \(G\) を「研磨(polish)」することで、 元の性質をできる限り失わずに、劇的にクラスタの数を削減する方法が提案されている 3 。 Takeでは、そのような研磨処理は mbipolish メソッドを利用することで実現できる。 リスト 29 onlineStoreのデータから顧客と商品の二部グラフを構成し、 それを研磨し極大二部クリークを列挙するPythonコードである。

リスト 29 ルールの相互ランク情報に基づいた2アイテム相関ルールの列挙とその可視化を実現するスクリプト
 1#!/usr/bin/env python
 2# -*- coding: utf-8 -*-/
 3import os
 4import nysol.mcmd as nm
 5import nysol.take as nt
 6
 7iFile=("./DATA/online_all.csv")
 8oPath=("./OUTPUTS/bicluster")
 9os.system("mkdir -p %s"%oPath)
10
11# 購入回数が5回以上の商品-顧客のペアを選択することで二部グラフを構成する。
12f=None
13f <<= nm.mcut(f="StockCode,CustomerID",i=iFile)
14f <<= nm.mdelnull(f="StockCode,CustomerID")
15f <<= nm.mcount(k="StockCode,CustomerID",a="freq")
16f <<= nm.mselnum(f="freq",c='[5,]',o="%s/bipartiteGraph.csv"%oPath)
17f.run()
18# bipartiteGraph.csvの内容
19# StockCode%0,CustomerID%1,freq
20# 10125,12731,5
21# 10133,12748,5
22# 10135,14096,11
23# 11001,14096,7
24
25# 二部クリークの列挙
26# 出力項目StockCode,CustomerIDはベクトル型で出力されており、それぞれのサイズがsize1,size2項目
27nt.mbiclique(ei="%s/bipartiteGraph.csv"%oPath, ef="StockCode,CustomerID", o="%s/clique_non-polish.csv"%oPath).run()
28# clique_non-polish.csvの内容
29# StockCode%0,CustomerID%1,size1,size2
30# 10125 20682 20685 ... 90119 90166 CRUK DOT,14096,453,1
31# 15036,12748 12841 12877 12971 13089 13098 14060 16186 16700,1,9
32# 15036 15044D 20723 22355 22502 22661,12877,6,1
33#                     :
34
35# 二部グラフの研磨を行う。出力も二部グラフとなる。
36nt.mbipolish(ei="%s/bipartiteGraph.csv"%oPath, ef="StockCode,CustomerID", sim="R", th=0.3, eo="%s/bipartiteGraphPolish.csv"%oPath).run( )
37# bipartiteGraphPolish.csvの内容
38# StockCode,CustomerID
39# 10133,12748
40# 10135,14096
41# 11001,14096
42#      :
43
44# 研磨された二部グラフから鈍くリークを列挙する。
45nt.mbiclique(ei="%s/bipartiteGraphPolish.csv"%oPath,ef="StockCode,CustomerID", o="%s/clique_polish.csv"%oPath).run()
46# clique_polish.csvの内容
47# StockCode%0,CustomerID%1,size1,size2
48# 15056BL 15056N 20679,15854,3,1
49# 16011 20975 22440,17596,3,1
50# 16014 16015 16016 22300,18077,4,1
51# 16161U,17365,1,1
52#          :
53
54# 研磨なしの二部クリークのサイズ別件数(size2:顧客のサイズのみを示してる)
55f=None
56f <<= nm.mchgnum(f="size2",R="1,3,5,7,9,11,21,31,41,51,MAX",v="1-2,3-4,5-6,7-8,9-10,11-20,21-30,31-40,41-50,51-",i="%s/clique_non-polish.csv"%oPath)
57f <<= nm.mcut(f="size2")
58f <<= nm.mcount(k="size2",a="freq",o="%s/hist_non-polish.csv"%oPath)
59f.run(meg="on")
60# hist_non-polish.csvの内容
61# size2%0,freq
62# 1-2,2636
63# 11-20,1512
64# 21-30,140
65# 3-4,9027
66# 31-40,31
67# 41-50,11
68# 5-6,6682
69# 51-,12
70# 7-8,3156
71# 9-10,1501
72
73# 研磨ありの二部クリークのサイズ別件数(size2:顧客のサイズのみを示してる)
74f=None
75f <<= nm.mchgnum(f="size2",R="1,3,5,7,9,11,21,31,41,51,MAX",v="1-2,3-4,5-6,7-8,9-10,11-20,21-30,31-40,41-50,51-",i="%s/clique_polish.csv"%oPath)
76f <<= nm.mcut(f="size2")
77f <<= nm.mcount(k="size2",a="freq",o="%s/hist_polish.csv"%oPath)
78f.run(meg="on")
79# hist_polish.csvの内容
80# size2%0,freq
81# 1-2,205
82# 11-20,6
83# 3-4,31
84# 5-6,17
85# 7-8,4
86# 9-10,2

Footnotes

1

羽室行信,宇野毅明,中元政一,中原孝信,丸橋弘明,「 Take: Pythonにおけるデータマイニング支援ツール」FIT2018:第17回情報科学技術フォーラム,2018/9/20,福岡工業大学.

2

岩﨑幸子,中元政一,中原孝信,宇野毅明,羽室行信,グラフ構造による相関ルールの視覚化ツール：KIZUNA,2017年度人工知能学会(第31回),ウインクあいち,2017/5/24.

3

中原孝信, 大内章子, 宇野毅明, 羽室行信, 「データ研磨の2部グラフへの適用と Twitter からの意見抽出」,2016年度人工知能学会（第30回）,北九州国際会議場, 2016.6.6〜6.9.

4

\(U,V\) の部分集合によって誘導される部分グラフの部間の任意の節点に枝があるような \(G\) の誘導部分グラフを二部クリークと呼び、ある二部クリークが他の二部クリークの真部分集合でなければ、それは極大二部クリークと呼ばれる。