Big Data Learning with Evolutionary Algorithms
Isaac Triguero

Mikel Galar

School of Computer Science
University of Nottingham
United Kingdom
Isaac.Triguero@nottingham.ac.uk

Dept. Automatic and Computation
Public University of Navarre
Spainmikel.galar@unavarra.es

http://www.cs.nott.ac.uk/~pszit/BigDataCEC2017.html

5th June 2017

Outline Introduction to Big Data Big Data Analytics
 Evolutionary algorithms in the big data
context
 A demo with MLlib
 Conclusions

2

What is Big Data?
There is no a standard definition!
“Big Data” involves data whose volume, diversity andcomplexity requires new techniques, algorithms andanalyses to extract valuable knowledge (hidden) .

Data Intensive
applications

3

What is Big Data? The 5V’s definition

4

Big data has many faces

5How to deal with data intensive
applications? Scale-up vs. Scale-outTraditional HPC way of doing things
Communication network (Infiniband)
Lots ofcommunication
c

c

…

c

c

c

workernodes(lots of them)

OS

OS

OS

OS

OS

Limited I/O

Network for I/O

centralstoragei

Lots ofcomputations

input data(relatively small)

Source: Jan Fostier. Introduction to MapReduce and its Application to Post-Sequencing Analysis

Data-intensive jobs
Fast communication network (Infiniband)

Limitedcommunication

…
OS

OS

OS

Low computeintensity

OS

OS

Lots of I/O

Network for I/Oa b c d e
input data (lots of it)

f g h i jdoesn’tscale

centralstorageData-intensive jobs
Communication network
Limitedcommunication…

Low computeintensity

b c

a c

b e

d f

a d

e j

g j

h i

g i

f h

Solution: store data on local disks of the nodes that perform
computations on that data (“data locality”)

input data
(lots of it)

Distributed systems in Big Data
• Objective: To apply an operation to all data
– One machine cannot process or store all data
• Data is distributed in a cluster of computing nodes• It does not matter which machine executes theoperation• It does not matter if it is run twice in different nodes(due to failures or stalled nodes)• We look for an abstraction of the complexity behind
distributed systems– DATA LOCALITY is crucial• Avoid data transfers between machines as much as
possibleDistributed systems in Big Data
New programming model: MapReduce– “Moving computation is cheaper than moving
computation and data at the same time”– Idea• Data is distributed among nodes (distributed filesystem)• Functions/operations to process data are distributed to
all the computing nodes• Each computing node works with the data stored in it• Only the necessary data is moved across the network

MapReduce• Parallel Programming model• Divide & conquer strategy
 divide: partition dataset into smaller, independent
chunks to be processed in parallel (map) conquer: combine, merge or otherwise aggregate
the results from the previous step (reduce)• Based on simplicity and transparency to theprogrammers, and assumes data locality• Becomes popular thanks to the open-source project
Hadoop! (Used by Google, Facebook, Amazon, …)
12

MapReduce: How it works

MapperReducerMapReduce: Example• WordCountHadoop• Open source framework for Big Data processing– Based on two Works published by Google• Google File System (GFS)[Ghe03]• MapReduce algorithm[Dea04]– Composed of• Hadoop Distributed File System (HDFS) Î Storage• Implementation of the MapReduce algorithm ÎProcessing[Ghe03] S. Ghemawat, H. Gobioff, S.-T. Leung. The Google file system. In Proceedings of the nineteenth ACM symposium on Operating
systems principles (SOSP ’03). ACM, New York, NY, USA, 29-43. 2003
[Dea04] J. Dean, S. Ghemawat. MapReduce: simplified data processing on large clusters. In Proceedings of the 6th conference on Symposium
on Opearting Systems Design & Implementation - Volume 6 (OSDI’04), Vol. 6. USENIX Association, Berkeley, CA, USA, 10-10. 2004.

Hadoop• Hadoop is:– An open-source framework written in Java
– Distributed storage of very large data sets (Big Data)– Distributed processing of very large data sets
• This framework consists of a number of modules– Hadoop Common– Hadoop Distributed File System (HDFS)– Hadoop YARN – resource manager– Hadoop MapReduce – programming model
http://hadoop.apache.org/
16

Hadoop: A master/slave architecture

Slave

Master– Master: NameNode, JobTracker– Slave: {DataNode, TaskTraker}, ..., {DataNode,
TaskTraker}

JobTracker

Secondary
NamenodeSingle Box
Single Box
Optional to have in Two Box

Single Box
In Separate Box

Namenode

TaskTraker
Datanode 1… … …

TaskTraker
Datanode 2… … …

TaskTraker
Datanode 3
… … …

……

TaskTraker
Datanode N
… … …

17

Distributed File System: HDFS
• HDFS – Hadoop Distributed File System– Distributed File System written in Java– Scales to clusters with thousands of computing nodes• Each node stores part of the data in the system– Fault tolerant due to data replication– Designed for big files and low-cost hardware• GBs, TBs, PBs– Efficient for read and append operations (random
updates are rare)– High throughput (for bulk data) more important than
low latency

Hadoop MapReduce: Main
Characteristics• Automatic parallelization:– Depending on the size of the input data Î there will be
multiple MAP tasks!
– Depending on the number of Keys <k, value> Î there
will be multiple REDUCE tasks!
• Scalability:– It may work over every data center or cluster ofcomputers.
• Transparent for the programmer– Fault-tolerant mechanism.
– Automatic communications among computers
19

Data Sharing in Hadoop MapReduce
HDFS
read

HDFS
write

HDFS
read

iter. 1

HDFS
write

. . .

iter. 2

Input
HDFS
read

Input

query 1

result 1

query 2

result 2

query 3

result 3. . .
Slow due to replication, serialization, and disk IO
20

Paradigms that do not fit with Hadoop
MapReduce• Directed Acyclic Graph (DAG) model:– The DAG defines the dataflow of the application, and thevertices of the graph defines the operations on the data
• Graph model:– More complex graph models that better represent thedataflow of the application– Cyclic models -> Iterativity.
• Iterative MapReduce model:– An extented programming model that supports iterative
MapReduce computations efficiently
21

New platforms to overcome Hadoop’s
limitations
GIRAPH (APACHE Project)(http://giraph.apache.org/)
Iterative graph processing

GPS - A Graph Processing System,(Stanford)
http://infolab.stanford.edu/gps/
Amazon's EC2Distributed GraphLab(Carnegie Mellon Univ.)
https://github.com/graphlabcode/graphlab
Amazon's EC2Spark (UC
Berkeley)http://spark.incubator.apache.org/research.html

Twister (Indiana University)
http://www.iterativemapreduce.org/
Private Clusters
PrIter (University of Massachusetts
Amherst, Northeastern UniversityChina)
http://code.google.com/p/priter/
Private cluster and Amazon EC2 cloud
HaLoop(University of Washington)
http://clue.cs.washington.edu/node/14
http://code.google.com/p/haloop/
Amazon’s EC2
GPU based platforms
Mars
Grex

22

Big data technologies

23

What is Spark?
Fast and Expressive Cluster Computing
Engine Compatible with Apache Hadoop

Efficient

Usable• General execution graphs• In-memory storage• Rich APIs in Java, Scala,Python• Interactive shell24

What is Spark?
• Data processing engine (only)• Without a distributed file system– Uses other existing DFS• HDFS, NoSQL…
• Hadoop is not a prerequisite• Works with different cluster management tools– Hadoop (YARN)– Mesos– Standalone mode (included in Spark)What is Spark?

Spark Goal
• Provide distributed memory abstractions for clusters
to support apps with working sets
• Retain the attractive properties of MapReduce:– Fault tolerance (for crashes & stragglers)– Data locality– Scalability
Initial Solution: augment data flow model with “resilient
distributed datasets” (RDDs)

27

RDDs in Detail• An RDD is a fault-tolerant collection of elements thatcan be operated on in parallel.
• There are two ways to create RDDs:– Parallelizing an existing collection in your driverprogram– Referencing a dataset in an external storage
system, such as a shared filesystem, HDFS, Hbase.
• Can be cached for future reuse

28

Operations with RDDs
• Transformations (e.g. map, filter, groupBy, join)– Lazy operations to build RDDs from other RDDs
• Actions (e.g. count, collect, save)– Return a result or write it to storage
Transformations(define a new RDD)

mapfiltersampleunion
groupByKey
reduceByKey
join
cache
…

Parallel operations(return a result to driver)reducecollectcountsavelookupKey…
29

Operations with RDDs
• RDDs – Simple example>>> lines = sc.textFile("README.md") # Creates an RDD>>> lines.count() # Counts the number of elements in the RDD
127>>> lines.first() # First element of the RDD -> 1st line of
README.md
u'# Apache Spark‘• Simple wordCount in Sparktext_file = sc.textFile("hdfs://...")
counts = text_file.flatMap(lambda line: line.split(" "))\.map(lambda word: (word, 1)) \.reduceByKey(lambda a, b: a + b)
counts.saveAsTextFile("hdfs://...")

Spark vs. hadoop
HadoopHadoopBinMem

250

87

106

121

150

157

143

197

200

Spark

100

33

61

Hadoop ~ 4 files, >300 lines

Iteration time (s)Lines of code for KMeans
Spark ~ 90 lines –

300

274

K-Means

50
0
25

50

100

Number of machines[Zaharia et. al, NSDI’12]

31

Spark• Driver and Workers– A Spark program is composedof two programs• Driver program• Workers program– Executed in the computing nodes– Or in local threads– RDDs are distributed acrossthe whole clusterSparkSQL: Datasets y DataFrames• Structured APIs
– DataFrames (>= Spark 1.3)
• Idea: RDDs of rows with columns that can be accessedby their names• Similar to Pandas in Python (dataframes in R)• Avoid Java serialization performed by RDDs
• API natural for developers familiar with building queryplans (SQL)• Introduced as a part of Tungsten project– Efficient memory management• Concept of schema to describe data

SparkSQL: Datasets y DataFrames• Structured APIs
– Datasets (>= Spark 1.6)
• Idea: Strongly typed RDDs
• Functional transformations (map, flatMap, filter)• Best of both RDDs and DataFrames– Object-oriented programming– Compile-time type safety– Catalyst optimization– Tungsten off-heap memory optimization• Only for Scala and Java

SparkSQL: Datasets y DataFrames• Structured APIs
– DataFrames and Datasets– Fused in Spark 2.0 (November 2016)• A DataFrame is just a Dataset of Rows: Dataset[Row]– Both make us of Catalyst and Tungsten projects

SparkSQL: Datasets y DataFrames• Structured APIs in Spark– Analysis of the reported errors before a job isexecuted

Flinkhttps://flink.apache.org/

37

Big Data: Technology
and Chronology

2001-20102010-20172001
3V’s Gartner
2009-2013 Flink
TU Berlin
Flink Apache (Dec.
2014) Volker
MarklDoug Laney
2004
MapReduce
GoogleBig
Data

Jeffrey Dean

Big Data
Analytics:
Mahout, MLLib, …
HadoopEcosystem2010 Spark2008

U Berckeley

HadoopApache Spark
Feb. 2014Yahoo!

Matei Zaharia

2010-2017:

Doug Cutting

Applications
New
Technology
38

Big Data Ecosystem

Cluster management

Cluster management

Data serialization
Pig
Scripting para
MapReduce

NoSQL Database

Sqoop
Hadoop to RDBMSSQLStreaming data
Streaming data

ZooKeeper
Coordinador
DAG execution

NoSQL on HDFS
Kafka
Gestión defuentes de datos
ZepelinWeb-based notebook

DockerContainers

Log data

ImpalaInteractive SQLOutline
 Introduction to Big Data Big Data Analytics
 Evolutionary algorithms in the big data
context
 A demo with MLlib
 Conclusions

41

Big Data Analytics
Potential scenarios

Clustering

Classification

Real Time Analytics/
Big Data Streams

Association

Recommendation
Systems

Social Media Mining
Social Big Data

42

Big Data Analytics:
A 3 generational view

43

Mahout (Samsara)• First ML library initially based on Hadoop MapReduce.
• Abandoned MapReduce implementations from version 0.9.
• Nowadays it is focused on a new math environment called
Samsara.
• It is integrated with Spark, Flink and H2O• Main algorithms:– Stochastic Singular Value Decomposition (ssvd, dssvd)– Stochastic Principal Component Analysis (spca, dspca)– Distributed Cholesky QR (thinQR)– Distributed regularized Alternating Least Squares (dals)– Collaborative Filtering: Item and Row Similarity– Naive Bayes Classification
http://mahout.apache.org/

44

Spark Libraries

https://spark.apache.org/mllib/

45

FlinkML

https://ci.apache.org/projects/flink/flink-docs-master/apis/batch/libs/ml/
46

Scalability• Speed-up (m cores)– How much faster can the same data be processedwith m cores instead of 1 core
• 𝑆𝑝𝑒𝑒𝑑𝑢𝑝 𝑚 =𝑟𝑢𝑛𝑡𝑖𝑚𝑒 𝑜𝑛 1 𝑐𝑜𝑟𝑒𝑟𝑢𝑛𝑡𝑖𝑚𝑒 𝑜𝑛 𝑚 𝑐𝑜𝑟𝑒𝑠– The data size is kept constant and the number of coresis increased– Ideal speed-up is linear• Speedup(m) = m– In practice• Difficult to obtain due to communicationand synchronization overhead

Scalability• Size-up (data, m)– How much time does it take to execute m times larger
data• 𝑆𝑖𝑧𝑒𝑢𝑝 𝑑𝑎𝑡𝑎, 𝑚 =𝑟𝑢𝑛𝑡𝑖𝑚𝑒 𝑓𝑜𝑟 𝑝𝑟𝑜𝑐𝑒𝑠𝑠𝑖𝑛𝑔 𝑚·𝑑𝑎𝑡𝑎
𝑟𝑢𝑛𝑡𝑖𝑚𝑒 𝑓𝑜𝑟 𝑝𝑟𝑜𝑐𝑒𝑠𝑠𝑖𝑛𝑔 𝑑𝑎𝑡𝑎

– The number of cores is kept constant and the data size
is increased– Ideal size-up is linear• Sizeup(data, m) = m– In practice• Few algorithms are linear withrespect to the data

Scalability• Scale-up (data, m)– Measures the ability of the system to run a m-times
greater job with a m-times larger system• 𝑆𝑖𝑧𝑒𝑢𝑝 𝑑𝑎𝑡𝑎, 𝑚 =𝑟𝑢𝑛𝑡𝑖𝑚𝑒 𝑓𝑜𝑟 𝑝𝑟𝑜𝑐𝑒𝑠𝑠𝑖𝑛𝑔 𝑜𝑛 1 𝑐𝑜𝑟𝑒𝑟𝑢𝑛𝑡𝑖𝑚𝑒 𝑓𝑜𝑟 𝑝𝑟𝑜𝑐𝑒𝑠𝑠𝑖𝑛𝑔 𝑚·𝑑𝑎𝑡𝑎 𝑜𝑛 𝑚 𝑐𝑜𝑟𝑒𝑠– Both the number of cores and the data are increased– Ideal scale-up is 1
• Scale-up(data, m) = 1– In practice• Few algorithms achieve ascale-up of 1

Machine Learning in Big Data:
Global vs. Local
Two main ways for learning a model in Big Data:– Locally• A model is created for each partition of the data
(only using the data of that partition)• All the models are combined when predicting theclass of a new example Æ Ensemble– Globally• A single model is created using all the available data
• They try to obtain the same model as the one thatwould be obtained if the method could be executed ina single nodeMachine Learning in Big Data:
Global vs. Local
Local model– Advantages• Usually faster• Gets faster as the number of partitions is increased• Any existing model can be applied• Only the aggregation phase has to be designed– Disadvantages• Slow in test phase, too many models have to be executed• Loss of accuracy as the number of partitions increases– With few partitions, accuracy can improve due to the ensemble
effect– With too many partitions, the accuracy tends to drop, since there
are not enough examples in each partition• They do not take advantage of the data as a whole

Machine Learning in Big Data:
Global vs. Local
Global model– Advantages• Greater accuracy is expected (not proved)• All the examples are used to learn a single model• Anyway, a global ensemble can also be built• The model is independent of the number of partitions• Faster in test phase– Disadvantages• More complex design and implementation• Distributed nature of Big Data processing has to be taken
into account (computation/communication)

Decision Trees for Big Data
• Decision Trees in Spark– Differences with respect to classical models• All the nodes in a level are learned with a single passthrough the whole dataset• Numeric attributes are discretized into bins in order toreduce the computational cost

Decision Trees for Big Data
• Decision Trees in Spark– Differences with respect to classical models• All the nodes in a level are learned with a single passthrough the whole dataset

Decision Trees for Big Data
• Decision Trees in Spark– Differences with respect to classical models• Numeric attributes are discretized into bins in order toreduce the computational costOutline Introduction to Big Data Big Data Analytics
 Evolutionary algorithms in the big data
context
 A demo with MLlib
 Conclusions

56

Data Preprocessing for Big Data
Data Preprocessing: Tasks to discover quality dataprior to use knowledge extraction algorithms.
Knowledge
Patterns
Targetdata

Processed
dataInterpretation
Data Mining Evaluation

data

Preprocessing
Selection
57

Evolutionary algorithms for data
preprocessing• Many preprocessing stages can be modelled as optimisation
processes. For example:– Feature selection/weighting– Instance selection/Generation• Evolutionary algorithms have excelled in this task in data witha moderate size.
• However, their practical application is limited to problems
with no more than tens of thousands of instances because of:– Excessive chromosome size
– Runtime requirements
58

Evolutionary algorithms for instance
reduction in Big data
I. Triguero, D. Peralta, J. Bacardit, S.García, F. Herrera. MRPR: A MapReduce solution for prototype reduction in
big data classification. Neurocomputing 150 (2015) 331–345
I. Triguero, D. Peralta, J. Bacardit, S.García, F. Herrera. A Combined MapReduce-Windowing Two-Level Parallel
Scheme for Evolutionary Prototype Generation. Evolutionary Computation (CEC), 2014 IEEE Congress on, 30363043

59

Instance Reduction
 Objective: reduce the number of samples

to find better decision boundaries
between classes, by selecting relevantsamples or artificially generating newones.
 We focused on Prototype Generation(PG) models, which are based on the
Nearest Neighbour (NN) classifier.
 Advantages:
9 Reduce Storage Requirements
9 Remove noisy samples
9 Speed up learning process60

Evolutionary Prototype Generation (EPG)
EPG algorithms adjust the positioning of the
prototypes.
 Each individual encodes a single prototype or acomplete generated set with real codification.
 The fitness function is computed as theclassification performance in the training set using
the Generated Set.
 Currently, best performing approaches use
Differential Evolution.
 Known issues: Dealing with big data becomes impractical

I. Triguero, S. García, F. Herrera, IPADE: Iterative Prototype Adjustment for Nearest Neighbor Classification.
IEEE Transactions on Neural Networks 21 (12) (2010) 1984-1990

61

Evolutionary Prototype Generation for
Big Data sets
Objectives
 The design of a scalable EPG.
approach that embraces thehuge storage and processing
capacity of cloud platforms.
 To do so, we rely on the successof Hadoop MapReduce in
combination with a windowing
scheme for evolutionary models.
62

Parallelising EPG with windowing

0

Ex/n

2·Ex/n3·Ex/nEx

Training set

Iterations
0

Iter

Main properties:
9Avoids a (potentially biased) static prototype
selection/generation
9This mechanism also introduces some generalization pressure
63

Parallelising EPG with windowing
Properties:
 Within this scheme, the algorithm disposes of the whole

information although it is accessed in successive iterations.
 This model itself aims to improve the runtime requirementsof EPG models. But it does not deal with the memory
consumption problem.
 This is why we use this strategy as a second level
parallelization scheme after a previous distribution of theprocessing in a cluster of computing elements.

64

MRPR: Evolutionary Prototype
Generation for Big Data sets

65

Evolutionary Prototype Generation for
Big Data sets
Experimental Study• 4 big data sets: Poker (1M), KddCup (4.8M), Susy (5M),
RLCP(5.7M).
• Performance measures: Accuracy, reduction rate, runtime, testclassification time and speed up.
• 3x5 fold-cross validation• Number of mappers = 64/128/256/512/1024.
• Number of reducers=1• PG techniques tested: SSMA-SFLSDE, LVQ3, RSP3
• PS techniques tested: DROP3, FCNN
66

Evolutionary Prototype Generationfor Big Data sets

67

Evolutionary Prototype Generationfor Big Data sets

68

Evolutionary Prototype Generationfor Big Data sets

69

Evolutionary Prototype Generationfor Big Data sets
Evolutionary algorithms continue to be the best performing
models for Instance reduction in the big data context.
 Great synergy between the windowing and MapReduce
approaches. They complement themselves in the proposed twolevel scheme.
 Without windowing, EPG could not be applied to datasets larger
than approximately ten thousands instances.
 The application of this model has resulted in a very big reductionof storage requirements and classification time for the NN rule.
https://github.com/triguero/MRPR

70

Evolutionary algorithms for
imbalanced Big data sets

I Triguero, M Galar et. al. Evolutionary undersampling for imbalanced big data classification.
IEEE Congress on Evolutionary Computation (CEC), 2015.
I Triguero, M Galar et. al. Evolutionary Undersampling for Extremely Imbalanced Big Data Classification under
Apache Spark. IEEE Congress on Evolutionary Computation (CEC), 2016.
I Triguero, M Galar et. al. A First Attempt on Global Evolutionary Undersampling for Imbalanced Big Data.
IEEE Congress on Evolutionary Computation (CEC), 2017.

71

Class imbalance problem

An example of an imbalanced data-set
72

Class imbalance problem

Standard classifiers Æ models biased in favour of the majority class73

Class imbalance problem
Skewed data distribution by itself is notharmful But… a series of difficulties usually turn up
 Small sample size
 Overlapping or class separability
 Small disjuncts
(a) Class overlapping(b) Small disjuncts
74Class imbalance problem
Two main approaches to tackle thisproblem: Data sampling Undersampling Oversampling Hybrid approaches
 Algorithmic modifications
 Cost-sensitive approaches
 Ensemble models-- -- - - -- - - ---- - -- - ---- - + ++ + +V. López et al, An insight into classification with imbalanced data: Empirical results and current trends on using data intrinsic
characteristics, Information Sciences 250 (2013)
M. Galar et al, A Review on Ensembles for the Class Imbalance Problem: Bagging-, Boosting-, and Hybrid-Based Approaches,
IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews 42 (4) (2012)75

Evolutionary Undersampling

Evolutionary undersampling (EUS) aims to select the best
subset of negative instances from the original training set.



EUS not only intends to balance the training set, but also toincrease the overall performance on both classes of the
problem.



To do so, a genetic algorithm is used to search for an optimal
subset of instances.

This resulting set can be used by any standard classification
model.

S. Garcia and F. Herrera, “Evolutionary under-sampling for classification with imbalanced data sets: Proposals and taxonomy”, Evolutionary
Computation, 17 (3) (2009). 275–306

76

Evolutionary Undersampling in the big data
context
 EUS

does not generate more data, as opposed tooversampling methods.

 However, the increasing number of instances would lead to

obtain an excessive chromosome size that can limit theirapplication.
 The required runtime increases not only with the numberof examples but also with the imbalance ratio (IR).

77Evolutionary undersamplingRepresentation of the solution

Performance: g-mean, 1NN hold-one-outFitness Function

We use the CHC algorithm and GM as performance measure.
L. J. Eshelman, The CHC adaptive search algorithm: How to have safe search when engaging in nontraditional genetic recombination, in Foundations ofGenetic Algorithms, G. J. E. Rawlins, Ed. San Francisco, CA: Morgan Kaufmann, 265-283, 1991.

78

EUS-BD: A two-level parallelisation model
for EUS A two-level parallelisation scheme:
 The

MapReduce phase will allow us to divide thecomputational effort over different machines.
Goal: Memory limitations and runtime.

 The

windowing scheme will be applied to reduce thecomputational time required by EUS.
Goal: Runtime.

79

Windowing for Class Imbalance Disjoint windows with equal class distribution may lead to

information loss of the positive class.
 The minority class set will be always used to evaluate achromosome.
 The

majority class set is divided into several disjoint
strata. The size of each subset will correspond to thenumber of minority class instances.
 It means: Fixed number of strata.

80

The EUS-BD scheme

81

EUS-BD known issuesThis is a local model!

Extremely imbalanced cases: lackof density from the minority
class.



We used Spark to alleviate thatissue splitting training data into
positive and negative sets. The
positive set was accessible in all
the maps (via broadcast)

Too smallamount ofpositivedata.

Or evennominorityclasselements!
82

EUS-BD for Extremely Imbalanced
datasets83

EUS-BD for Extremely Imbalanced
datasets84

EUS-BD for Extremely Imbalanced
datasets85

Can we develop a Global
Evolutionary model?
 Ideally, EUS should have access to all the data as a whole.

Can we do that with the current technology?

 A binary representation of the selected instances implies

a chromosome size equal to the number of negative
instances.

 However,

the resulting selected dataset tends to be
fairly small, and balanced.

 Assumption:

The number of positive instance is so
reduced that it perfectly fits in main memory of a single
computer.
86

Global Evolutionary Undersampling87Outline What is Big data?
 How to deal with Data Intensive applications?
 Big Data Analytics
 A demo with MLlib
 Conclusions

88

Demo
• In this demo we will show two ways ofworking with Apache Spark:– Interactive mode with Spark Notebook.
– Standalone mode with IntelliJ.

• All the code used in this presentation isavailable at:
http://www.cs.nott.ac.uk/~pszit/BigDataCEC201
7.html89

DEMO with Spark Notebook in local

http://spark-notebook.io/90

DEMO with Spark Notebook in local
Advantages:
9 Interactive.
9 Automatic plots.
9 It allows connection with a cluster.
9 Tab completion
Disadvantages:
 Built-in for specific spark versions.
 Difficult to integrate your own code.
91DEMO with IntelliJ IDE

https://www.jetbrains.com/idea/

92

MapReduce in a cluster• Hadoop V2– YARNMapReduce in a cluster• Hadoop V2

MapReduce in a cluster• Hadoop V2– Container• A subset of the resources of the cluster (part of a node)– Number of cores– Quantity of RAM memory• A hold request is made• Once granted, a process (task) can be run in thecontainer

MapReduce in a cluster• Hadoop V2– ApplicationMaster• New concept• Responsible for the processing• Responsible for negotiating with the ResourceManager
and working with the NodeManagers• In charge of the fault tolerance– ResourceManager is no longer used for this task

MapReduce in a cluster• Hadoop V2– Execution of a MapReduce process
1. The client launches the process (connection with the
ResourceManager)

MapReduce in a cluster• Hadoop V2– Execution of a MapReduce process
2. The ResourceManager requests a container where theApplicationMaster is executed

MapReduce in a cluster• Hadoop V2– Execution of a MapReduce process
3. The ApplicationMaster request the containers to
execute all the tasks (in different nodes)

MapReduce in a cluster• Hadoop V2– Execution of a MapReduce process
4. All the tasks are executed in the containers– Containers are released once its tasks are finished5. The ApplicationMaster ends when all the tasks havebeen executed. Then, its container is released

Spark: Execution in a cluster• SparkContext (sc) is created in the driver– Using the sc a connection with the cluster
manager is established– Once connected, executors are requested• The processes that perform the computation and store
the data– The driver sends the code and tasks to the
executors

Outline Introduction to Big Data Big Data Analytics
 Evolutionary algorithms in the big data
context
 A demo with MLlib
 Conclusions

102

Conclusions• We need new strategies to deal with big datasets– Choosing the right technology is like choosing theright data structure in a program.
• The world of big data is rapidly changing. Being upto-date is difficult but necessary.
• Evolutionary models are powerful tools in data
mining. They need to be adapted and redesigned totake the maximum advantages of their promisingproperties.
103

Big Data Learning with Evolutionary Algorithms
Isaac Triguero

Mikel Galar

School of Computer Science
University of Nottingham
United Kingdom
Isaac.Triguero@nottingham.ac.uk

Dept. Automatic and Computation
Public University of Navarre
Spainmikel.galar@unavarra.es

http://www.cs.nott.ac.uk/~pszit/BigDataCEC2017.html

5th June 2017

Extra slides

105

Evolutionary algorithms for Feature
Selection/Weighting in Big Data
D. Peralta,et al. Evolutionary Feature Selection for Big Data Classification: A MapReduce Approach. Mathematical
Problems in Engineering, 2015
I. Triguero, et al. ROSEFW-RF: The winner algorithm for the ECBDL'14 Big Data Competition: An extremely
imbalanced big data bioinformatics problem. Knowledge-Based Systems (2015)106

Feature Selection
Var. 1.
A
B
C
D

1
0
0
0
1

Var. 13

Var. 5
2
0
0
0
1

3
0
0
1
0

4
0
0
1
1

5
0
1
0
0

6
0
1
0
1

7
0
1
1
0

8
0
1
1
1

9
1
0
0
0

10
1
0
0
1

11
1
0
1
0

12 13 14 15 16
1
1
1
1
1
0
1
1
1
1
1
0
0
1
1
1
0
1
0
1

The outcome of FS would be: Less data Æ algorithms could learn quicker
 Higher accuracy Æ the algorithm generalizes better Simpler results Æ easier to understand them107

Evolutionary Feature Selection
Each individual represents a setof selected features (binary
vector).
 The individuals are crossed andmutated to generate new
candidate sets of features.
 Fitness function:
 Classification performance inthe training dataset using only
the features in thecorresponding set.


L. J. Eshelman, The CHC adaptative search algorithm: How to have safe search when engaging in nontraditional genetic
recombination, in: G. J. E. Rawlins (Ed.), Foundations of Genetic Algorithms, 1991, pp. 265--283.
108

Evolutionary Feature Weighting
Each individual represents theimportance of the features in the range
0,1 (real vector).
 The individuals are crossed and mutatedto generate new candidate importances.
 Fitness function:
 Classification performance in the
training dataset using taking into
consideration the weights of thefeatures.


Neri, F., Tirronen, V., Scale factor local search in differential evolution. Memetic Computing 1:2 (2009) 153-171

109

Evolutionary Feature
Selection/Weighting for Big Data
MapReduce EFS process

The vector of weights
is binarized with athreshold110Evolutionary Feature
Selection/Weighting for Big Data
Dataset reduction

No reduce phase

The maps
remove thediscardedfeatures111

Evolutionary Feature Selection
Experimental Study: EFS scalability in MapReduce

CHC is quadratic w.r.t. the number of instances
 Splitting the dataset yields nearly quadratic acceleration112

Evolutionary Feature Selection
Experimental Study: ClassificationTwo datasets epsilon
 ECBDL14, after applying
Random OversamplingThe reduction rate is controlledwith the weight thresholdThree classifiers in Spark
 SVM
 Logistic Regression Naïve Bayes

Performance measures

Training runtime

113

Evolutionary Feature Selection
Experimental Study: results

114

Evolutionary Feature Weighting at
GECCO-2014• Details of the training data: 32 million training samples (56.7GB of disk space) 2.9 million of test samples (5.1GB of disk space) 631 features (539 real & 92 nominal values)
 2 labels; 98% non-contact samples

Oversampling

Feature Selection

Learning a Random
ForestClassifying the test set

I. Triguero, et al. ROSEFW-RF: The winner algorithm for the ECBDL'14 Big Data Competition: An extremely imbalanced big data
bioinformatics problem. Knowledge-Based Systems (2015)115

Results
Team
EfdamisTPR
0.73043

TNR
0.73018

TPR * TNR
0.53335

ICOS

0.703210.730160.51345

UNSW

0.699160.727630.50873

EfdamisWithout FS
HyperEns

0.70410.640030.71030.763380.500175
0.48858

PUC-Rio_ICA

0.657090.71460

0.46956

I. Triguero, et al. ROSEFW-RF: The winner algorithm for the ECBDL'14 Big Data Competition: An extremely imbalanced big data
bioinformatics problem. Knowledge-Based Systems (2015)116

Evolutionary Feature
Selection/Weighting
The proposed MapReduce processes provide several advantages:
 It enables tackling Big Data problems
 The feature weight vector is more flexible than a binary vector
 The data reduction process in MapReduce provides a scalable andflexible way to apply the feature selection/weighting, Both the accuracy and the runtime of the classification were
improved after the preprocessing.
https://github.com/triguero/MR-EFS

117