Scalable Density Clustering for Spark - crim.ca · 3 APACHE • Popular distributed in-memory...

W W W . C R I M . C A

Principal partenaire financier

Scalable Density Clustering for Spark

THOMAS TRIPLET, PH.D., ENG.

MARCH 9TH 2016

2

TECHNOLOGIES BIG-DATA

• Hadoop Core – HDFS: Système de fichiers distribué – YARN: Gestion des ressources CPU et planification – MapReduce: Traitement en lot (batch) des données à grande échelle

• Écosystème Hadoop – NoSQL: HBase, Cassandra, Accumulo, etc… – SQL: Hive, Stinger (Hortonworks), Impala (Cloudera), Presto (FB), Tajo, Drill (MapR) – Transfert: Sqoop, Flume – Calcul/ML: Spark, Storm, Giraph, Mahout – Scripts: Pig, Cascading – Administration: Hue, ZooKeeper, Knox – Recherche: Solr, ElasticSearch

3

APACHE

• Popular distributed in-memory computing framework • 10-100x faster than Hadoop MapReduce and low latency • Linear horizontal scalability • Fault tolerant (RDDs) • Applications range from long-running batch jobs to stream processing • High-level Scala, Java, Python and R APIs

4

AGENDA

• Clustering algorithms (unsupervised learning) – Distance-based (k-means) – Density-based (DBSCAN)

• PatchWork – Algorithm – Results – Performance

• Conclusion

• Future Work

5

• Class labels are known and pre-defined

• Training and testing datasets are (manually) labeled with same classes

• Goal is to learn function/rule that can classify new data points

• Examples: SVMs, Neural nets, Bayesian classifiers, Decision trees…

• Class labels of the data are unknown

• Group/cluster similar data points without prior knowledge

• Goal is to discover structure or pattern in the data

• Examples: k-means, EM, DBScan, HCA…

INTRODUCTION: MACHINE LEARNING

Supervised Learning Unsupervised Learning (clustering)

5

• Class labels are known and pre-defined

• Training and testing datasets are (manually) labeled with same classes

• Goal is to learn function/rule that can classify new data points

• Examples: SVMs, Neural nets, Bayesian classifiers, Decision trees…

• Class labels of the data are unknown

• Group/cluster similar data points without prior knowledge

• Goal is to discover structure or pattern in the data

• Examples: k-means, EM, DBScan, HCA…

INTRODUCTION: MACHINE LEARNING

Supervised Learning Unsupervised Learning (clustering)

PatchWork ➔

6

• Popular algorithm: k-means (implemented in MLLib)

• Relies on distance function between data points

• Easy to implement

• Linear complexity (big-data)

• Easy to distribute

• Discovers spherical clusters of similar sizes only

• Sensitive to noise and local optima

• Prior knowledge of k.

• Popular algorithm: DBScan(not in MLLib)

• Relies on the density of data points in feature space

• Natural protection against noise and outliers

• Discovers clusters of arbitrary shape and size

• No prior knowledge of k

• Discovers clusters of similar densities only

• Quadratic complexity: not scalable

INTRODUCTION: CLUSTERING

Distance-based Density-based

6

• Popular algorithm: k-means (implemented in MLLib)

• Relies on distance function between data points

• Easy to implement

• Linear complexity (big-data)

• Easy to distribute

• Discovers spherical clusters of similar sizes only

• Sensitive to noise and local optima

• Prior knowledge of k.

• Popular algorithm: DBScan(not in MLLib)

• Relies on the density of data points in feature space

• Natural protection against noise and outliers

• Discovers clusters of arbitrary shape and size

• No prior knowledge of k

• Discovers clusters of similar densities only

• Quadratic complexity: not scalable

INTRODUCTION: CLUSTERING

Distance-based Density-based

PatchWork ➔

7

PATCHWORK ALGORITHM

2 main steps:

1. createCells( dataPoints ) à cells à RDD[(string, int)]

2. createClusters( cells) à clusters

8

STEP 1: CELL CREATION

9

STEP 1: CELL CREATION

10

STEP 1: CELL CREATION

4( -1,2 ; )

4( -1,3 ; )

4( -2,2 ; )

1( -3,4 ; )

4( 2,3 ; )

3( 2,4 ; )

3( 3,3 ; )

3( 3,4 ; )

11

STEP 1: CELL CREATION

1( -1,2 ; )

1( -2,2 ; )

1( -1,2 ; )

1( -1,2 ; )

.

.

.

1( 3,4 ; )

1( 3,4 ; )

1( 3,4 ; )

)

)

)

)

)

)

)

)

4( -1,2 ;

4( -1,3 ;

4( -2,2 ;

1( -3,4 ;

4( 2,3 ;

3( 2,4 ;

3( 3,3 ;

3( 3,4 ;

setOfCells = dataPoints.map(Pà(cellID(P),1)) .reduceByKey(_ + _)

12

STEP 2: CLUSTER CREATION

•

13

EXPERIMENTAL SETUP

• 6 servers, each with: – Intel Xeon E5-2650 8 cores @2.6GHz – 192GB memory – 30TB storage

• Cloudera CDH 5.4.0 • Apache Spark 1.3

14

DATASETSAggregation Compound

Jain Spiral

15

RESULTS (JAIN DATASET)K-means

DBScan PatchWork

16

RESULTS (SPIRAL DATASET)K-means

DBScan PatchWork

17

RESULTS (AGGREGATION DATASET)K-means

DBScan PatchWork

18

RESULTS (COMPOUND DATASET)K-means

DBScan PatchWork

19

PERFORMANCER

unni

ng T

ime

(sec

onds

)

1

10

100

1,000

10,000

100,000

Millions of data points10,000.0 100,000.0 1,000,000.0 10,000,000.0 100,000,000.0 1,000,000,000.0 10,000,000,000.0

DBSCAN PatchWork MLLib k-means ||

20

PERFORMANCE: SCALABILITYN

orm

aliz

ed e

xecu

tion-

time

0

0.25

0.5

0.75

1

Number of servers1 2 3 4 5

MLLib k-means|| PatchWork

21

CONCLUSION

22

FUTURE WORK

• Tests against new clustering algorithms available in Spark 1.6

• Better distribution of step 2

• Indexing for region query using R-trees

• Streaming version

Q & A

Contact: thomas.triplet@crim.ca

Availability: https://github.com/crim-ca/patchwork (MIT Licence)

Reference: Frank Gouineau, Tom Landry, Thomas Triplet (2016) PatchWork, a Scalable Density-Grid Clustering Algorithm. In Proc. 31th ACM Symposium On Applied Computing, Data-Mining track

WWW.CRIM.CA

Suivez-nous Dialoguez avec nous

Suivez-nous #CRIM_ca wwwCRIMca

Tous droits réservés © 2016 CRIM. 405, avenue Ogilvy, bureau 101, Montréal (Québec) H3N 1M3/514 840-1234/1 877 840-2746

Thomas Triplet, Ph.D., Eng. thomas.triplet@crim.ca

Principal partenaire financierLe CRIM est un centre de recherche appliquée en TI qui développe, en mode collaboratif avec ses clients et partenaires, des technologies innovatrices et du savoir-faire de pointe, et les transfère aux entreprises et aux organismes québécois afin de les rendre plus productifs et plus compétitifs localement et mondialement. Le CRIM dispose de quatre équipes de recherche en TI de calibre mondial. Le CRIM œuvre principalement dans les domaines des interactions et interfaces personne-système, de l’analytique avancée et des architectures et technologies avancées de développement et tests. Détenteur d’une certification ISO 9001:2008, son action s’inscrit dans les politiques et stratégies pilotées par le ministère de l'Économie, de l'Innovation et des Exportations (MEIE), son principal partenaire financier.