機械学習ツール入門

(1)

機械学習・データマイニングのツール紹介

-データベース的観点から-2015年3月11日

川島英之

(2)

機械学習・データマイニング用語

RF R Python SVM K-means 平均 Hadoop Mahout PostgreSQL MySQL SciQL SciDB Weka Esper R+Bigmemory K-最近傍法 libsvm LDA グループ MADLib Hivemall TinySVM DBN AutoPlait SQL

(3)

分析複雑度とデータサイズ

データサイズ

分析複雑度

RF R Python SVM K-means 平均 Hadoop Mahout PostgreSQL MySQL SciQL SciDB Weka Esper R+Bigmemory K-最近傍法 TinySVM LDA グループ MADLib Hivemall libsvm DBN 銀の弾丸 AutoPlait SQL Spark とりあえず分析してみたい！

(4)

リレーショナル

DBMS

データは表！

データが沢山

SQL

Structured

Query Language

標準化

SQL:1992

SQL:1999

SQL:2003

SQL:2008

…

(5)

問合せ言語：

SQL

パケットを題材として

--• 全てのパケットを得る

–

SELECT * FROM packet;

• srcipの情報を全てのパケットから得る

–

SELECT srcip FROM packet;

• HTTPアクセス(port 80)に関するパケットだけを表示

–

SELECT * FROM packet WHERE dstport = 80;

• HTTPアクセスに関するパケットの件数を表示

–

SELECT COUNT(*) FROM packet WHERE dstport = 80;

• dstip毎のパケット件数を表示

(6)

分析複雑度とデータサイズ

データサイズ

分析複雑度

RF R Python SVM K-means 平均 PostgreSQL MySQL SciQL SciDB Weka R+Bigmemory K-最近傍法 TinySVM LDA グループ MADLib Hivemall libsvm DBN 銀の弾丸 AutoPlait SQL Spark Hadoop Mahout Esper

(7)

近傍検索

SELECT R.id, S.id FROM R, S

WHERE (R.x – S.x)

2 _{+ (R.y – S.y)}

2 _{< threshold;}

O

x

(8)

アルゴリズム

1万件，100万件ではどの程度かかる？

𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹 𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝐹𝐹 𝐹𝐹 ∈ 𝑅𝑅 {

𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹 𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝐹𝐹 𝑠𝑠 ∈ 𝑆𝑆 {

𝐼𝐼𝐼𝐼(𝐹𝐹 𝑚𝑚𝐹𝐹𝑡𝑡𝐹𝐹𝐹𝐹𝐹𝑠𝑠 𝑠𝑠)

𝐴𝐴𝐴𝐴𝐴𝐴{𝐹𝐹, 𝑠𝑠}}}

(9)

Query plan of PostgreSQL

Nested Loop

(cost=23757.00..43907042607.00 rows=333333333333

width=16)

Join Filter

: ((((a.x - b.x) * (a.x - b.x)) + ((a.y - b.y) * (a.y - b.y))) < 0)

->

Seq Scan

on loc a (cost=0.00..18850.00 rows=1000000 width=8)

->

Materialize

(cost=23757.00..37664.00 rows=1000000 width=8)

->

Seq Scan on loc b

(cost=0.00..18850.00 rows=1000000 width=8)

今朝の

5時ごろにクエリをサブミット

まだ終わりません

(10)

分析複雑度とデータサイズ

データサイズ

分析複雑度

RF R Python SVM K-means 平均 PostgreSQL MySQL SciQL SciDB Weka R+Bigmemory K-最近傍法 TinySVM LDA グループ MADLib Hivemall libsvm DBN 銀の弾丸 AutoPlait SQL Spark Hadoop Mahout Esper 深く分析してみたい！

(11)

R

• 古くから存在するプログラミング言語・環境

• 豊富なパッケージ

• 決定木

, k-means, random forest, SVM, deep learning…

• 大規模データ対応

• Bigmemory, biganalytics

(12)

動物の分類

library("MASS")

data("Animals")

animals.cluster <-

kmeans

(x=Animals,

centers=5

)

K-meansによる分類データ読み込み

Animal

Body

Brain

Mountain beaver

1.35

8.1 Cow

465

423 Grey Wolf

36.33

119.5 Goat

27.66

115 Guinea pig

1.04

5.5 Dipliodocus

11700

50 Asian elephant

2547

4603

Donkey

187.1

419 Horse

521

655

分類数

(13)

分析複雑度とデータサイズ

データサイズ

分析複雑度

RF R Python SVM K-means 平均 PostgreSQL MySQL SciQL SciDB Weka R+Bigmemory K-最近傍法 TinySVM LDA グループ MADLib Hivemall libsvm DBN 銀の弾丸 AutoPlait SQL Spark Hadoop Mahout Esper C/Java等から呼び出したい！

(14)

Support Vector Machine (SVM)



SVM



２クラス分類問題を扱う



画像認識，音声認識，etc.



マージン最大化

⇒

汎化能力が高い



学習



ベクトルとクラスの組を学習データと

して与える



気圧配置ごとに分類器を作る

マージン識別境界冬型クラス非冬型クラスサポートベクトル

：ベクトル

Hiroki Kimura, Hideyuki Kawashima, Hiroyuki Kusaka, Hiroyuki Kitagawa:

Applying a Machine Learning Technique to

Classification of Japanese Pressure Patterns. Data

(15)

データのベクトル化

・・・・・・・・・ 1016.2 1016.8 1017.3 1017.8 ・・・・・・・・・ 1019.1 1019.7 1020.1 1020.8 ・・・・・・・・・ 1021.9 1022.8 1023.4 1023.9 ・・・・・・・・・ 1023.2 1024.6 1025.7 1026.4 ・・・・・・・・・ 1023.4 1025.2 1026.7 1027.7 ・・・・・・・・・ 1023.9 1026 1027.7 1028.8 ・・・・・・・・・ 1025.2 1027.4 1029.3 1030.6 ・・・・・・・・・ 1027.4 1029.8 1031.6 1032.6 ・・・・・・・・・ 1030 1032.4 1034.1 1034.3 ・・・・・・・・・ 1031.5 1033.5 1034.9 1035 ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・ 1019.1 1019.7 1020.1 1020.8 ・・・・・・・・・ 1021.9 1022.8 1023.4 1023.9 ・・・・・・・・・・・・・・・

1 件のデータ

1×2109

(2109次元ベクトル)

SVMで扱うために，1件のデータを

2109次元ベクトルに変換

可視化したもの

37×57=2109点

15

(16)

実験



実験用データ



1981~2000年の20年分の気圧データ（前線型は相当

温位データ）



学習： 1981~1990年 ⇒ テスト： 1991~2000年



学習： 1991~2000年 ⇒ テスト： 1981~1990年



次元を削減したベクトルを用いて，気圧配置ごと

に20通りの実験



TinySVM（SVMのツール）を利用



http://chasen.org/~taku/software/TinySVM/

16

(17)

分析複雑度とデータサイズ

データサイズ

分析複雑度

RF R Python SVM K-means 平均 Hadoop Mahout PostgreSQL MySQL SciQL SciDB Weka Esper R+Bigmemory K-最近傍法 TinySVM LDA グループ MADLib Hivemall libsvm DBN 銀の弾丸 AutoPlait SQL Spark すぐに結果がほしい！

(18)

Example Query on DSMS

• #Access for each port ?

[1]

•

Group by aggregates

SELECT dst_port,

COUNT(dst_port)

FROM pkt[1 sec]

GROUP BY dst_port

g-pkt

src_ip dst_ip src_port dst_port seq_no packet_size timestamp protocol ack fin syn urg push reset content

22: 2

80: 2

15: 1

22

N

I

C

80 15 80 22

1 second

[1] “Enabling Real Time Data Analysis”, Divesh Srivastava (AT&T Labs), et, al. Keynote talk, VLDB

(19)

まとめ

データサイズ

RF R Python SVM K-means 平均 Hadoop Mahout PostgreSQL MySQL SciQL SciDB Weka Esper R+Bigmemory K-最近傍法 TinySVM LDA グループ MADLib Hivemall libsvm DBN 自作

AutoPlait

SQL Spark 1 1 1 ₂ 3 4

機械学習 ツール入門

機械学習・データマイニングのツール紹介

-データベース的観点から-2015年3月11日

川島英之

機械学習・データマイニング用語

分析複雑度とデータサイズ

データサイズ

分析複雑度

リレーショナル

DBMS

データは表！

データが沢山

SQL

Structured

Query Language

標準化

SQL:1992

SQL:1999

SQL:2003

SQL:2008

…

問合せ言語：

SQL

パケットを題材として

--• 全てのパケットを得る

–

SELECT * FROM packet;

•

srcipの情報を全てのパケットから得る

–

SELECT srcip FROM packet;

•

HTTPアクセス(port 80)に関するパケットだけを表示

–

SELECT * FROM packet WHERE dstport = 80;

•

HTTPアクセスに関するパケットの件数を表示

–

SELECT COUNT(*) FROM packet WHERE dstport = 80;

•

dstip毎のパケット件数を表示

分析複雑度とデータサイズ

データサイズ

分析複雑度

近傍検索

SELECT R.id, S.id FROM R, S

WHERE (R.x – S.x)

2

+ (R.y – S.y)

2

< threshold;

O

x

アルゴリズム

1万件，100万件ではどの程度かかる？

𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹 𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝐹𝐹 𝐹𝐹 ∈ 𝑅𝑅 {

𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹𝐹 𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝐹𝐹 𝑠𝑠 ∈ 𝑆𝑆 {

𝐼𝐼𝐼𝐼(𝐹𝐹 𝑚𝑚𝐹𝐹𝑡𝑡𝐹𝐹𝐹𝐹𝐹𝑠𝑠 𝑠𝑠)

𝐴𝐴𝐴𝐴𝐴𝐴{𝐹𝐹, 𝑠𝑠}}}

Query plan of PostgreSQL

Nested Loop

(cost=23757.00..43907042607.00 rows=333333333333

width=16)

Join Filter

: ((((a.x - b.x) * (a.x - b.x)) + ((a.y - b.y) * (a.y - b.y))) < 0)

->

Seq Scan

on loc a (cost=0.00..18850.00 rows=1000000 width=8)

->

Materialize

(cost=23757.00..37664.00 rows=1000000 width=8)

->

Seq Scan on loc b

(cost=0.00..18850.00 rows=1000000 width=8)

今朝の

5時ごろにクエリをサブミット

まだ終わりません

分析複雑度とデータサイズ

データサイズ

分析複雑度

機械学習ツール入門

_{+ (R.y – S.y)}

_{< threshold;}

：ベクトル