Data Mining

Classification: Alternative Techniques

Rule-Based Classifier

Classify records by using a collection of

“if…then…” rules
Rule: (Condition) → y
– where
◆ Condition is a conjunction of tests on attributes
◆ y is the class label
– Examples of classification rules:
◆ (Blood Type=Warm)  (Lay Eggs=Yes) → Birds
◆ (Taxable Income < 50K)  (Refund=Yes) → Evade=No

9/30/2020 Introduction to Data Mining, 2nd Edition 2

Rule-based Classifier (Example)
Name Blood Type Give Birth Can Fly Live in Water Class
human warm yes no no mammals
python cold no no no reptiles
salmon cold no no yes fishes
whale warm yes no yes mammals
frog cold no no sometimes amphibians
komodo cold no no no reptiles
bat warm yes yes no mammals
pigeon warm no yes no birds
cat warm yes no no mammals
leopard shark cold yes no yes fishes
turtle cold no no sometimes reptiles
penguin warm no no sometimes birds
porcupine warm yes no no mammals
eel cold no no yes fishes
salamander cold no no sometimes amphibians
gila monster cold no no no reptiles
platypus warm no no no mammals
owl warm no yes no birds
dolphin warm yes no yes mammals
eagle warm no yes no birds

R1: (Give Birth = no)  (Can Fly = yes) → Birds

R2: (Give Birth = no)  (Live in Water = yes) → Fishes
R3: (Give Birth = yes)  (Blood Type = warm) → Mammals
R4: (Give Birth = no)  (Can Fly = no) → Reptiles
R5: (Live in Water = sometimes) → Amphibians
9/30/2020 Introduction to Data Mining, 2nd Edition 3
 Application of Rule-Based Classifier

A rule r covers an instance x if the attributes of

the instance satisfy the condition of the rule
R1: (Give Birth = no)  (Can Fly = yes) → Birds
R2: (Give Birth = no)  (Live in Water = yes) → Fishes
R3: (Give Birth = yes)  (Blood Type = warm) → Mammals
R4: (Give Birth = no)  (Can Fly = no) → Reptiles
R5: (Live in Water = sometimes) → Amphibians

Name Blood Type Give Birth Can Fly Live in Water Class
hawk warm no yes no ?
grizzly bear warm yes no no ?

The rule R1 covers a hawk => Bird

The rule R3 covers the grizzly bear => Mammal

9/30/2020 Introduction to Data Mining, 2nd Edition 4

Rule Coverage and Accuracy
Tid Refund Marital Taxable
Coverage of a rule: Status Income Class

– Fraction of records 1 Yes Single 125K No

2 No Married 100K No
that satisfy the
3 No Single 70K No
antecedent of a rule 4 Yes Married 120K No

Accuracy of a rule: 5 No Divorced 95K Yes

6 No Married 60K No
– Fraction of records 7 Yes Divorced 220K No
that satisfy the 8 No Single 85K Yes

antecedent that 9 No Married 75K No

10 No Single 90K Yes
also satisfy the 10

consequent of a (Status=Single) → No
rule Coverage = 40%, Accuracy = 50%

9/30/2020 Introduction to Data Mining, 2nd Edition 5

How does Rule-based Classifier Work?

R1: (Give Birth = no)  (Can Fly = yes) → Birds

R2: (Give Birth = no)  (Live in Water = yes) → Fishes
R3: (Give Birth = yes)  (Blood Type = warm) → Mammals
R4: (Give Birth = no)  (Can Fly = no) → Reptiles
R5: (Live in Water = sometimes) → Amphibians

Name Blood Type Give Birth Can Fly Live in Water Class
lemur warm yes no no ?
turtle cold no no sometimes ?
dogfish shark cold yes no yes ?

A lemur triggers rule R3, so it is classified as a mammal

A turtle triggers both R4 and R5
A dogfish shark triggers none of the rules

9/30/2020 Introduction to Data Mining, 2nd Edition 6

Characteristics of Rule Sets: Strategy 1

Mutually exclusive rules

– Classifier contains mutually exclusive rules if
the rules are independent of each other
– Every record is covered by at most one rule

Exhaustive rules
– Classifier has exhaustive coverage if it
accounts for every possible combination of
attribute values
– Each record is covered by at least one rule
9/30/2020 Introduction to Data Mining, 2nd Edition 7
Characteristics of Rule Sets: Strategy 2

Rules are not mutually exclusive

– A record may trigger more than one rule
– Solution?
◆ Ordered rule set
◆ Unordered rule set – use voting schemes

Rules are not exhaustive

– A record may not trigger any rules
– Solution?
◆ Use a default class
9/30/2020 Introduction to Data Mining, 2nd Edition 8
Ordered Rule Set

Rules are rank ordered according to their priority

– An ordered rule set is known as a decision list
When a test record is presented to the classifier
– It is assigned to the class label of the highest ranked rule it has
triggered
– If none of the rules fired, it is assigned to the default class

R1: (Give Birth = no)  (Can Fly = yes) → Birds

R2: (Give Birth = no)  (Live in Water = yes) → Fishes
R3: (Give Birth = yes)  (Blood Type = warm) → Mammals
R4: (Give Birth = no)  (Can Fly = no) → Reptiles
R5: (Live in Water = sometimes) → Amphibians

Name Blood Type Give Birth Can Fly Live in Water Class
turtle cold no no sometimes ?
9/30/2020 Introduction to Data Mining, 2nd Edition 9
Rule Ordering Schemes

Rule-based ordering
– Individual rules are ranked based on their quality
Class-based ordering
– Rules that belong to the same class appear together

Rule-based Ordering Class-based Ordering

(Refund=Yes) ==> No (Refund=Yes) ==> No

(Refund=No, Marital Status={Single,Divorced}, (Refund=No, Marital Status={Single,Divorced},

Taxable Income<80K) ==> No Taxable Income<80K) ==> No

(Refund=No, Marital Status={Single,Divorced}, (Refund=No, Marital Status={Married}) ==> No

Taxable Income>80K) ==> Yes
(Refund=No, Marital Status={Single,Divorced},
(Refund=No, Marital Status={Married}) ==> No Taxable Income>80K) ==> Yes

9/30/2020 Introduction to Data Mining, 2nd Edition 10

Building Classification Rules

Direct Method:
◆ Extract rules directly from data
◆ Examples: RIPPER, CN2, Holte’s 1R

Indirect Method:
◆ Extract rules from other classification models (e.g.
decision trees, neural networks, etc).
◆ Examples: C4.5rules

9/30/2020 Introduction to Data Mining, 2nd Edition 11

Direct Method: Sequential Covering

1. Start from an empty rule

2. Grow a rule using the Learn-One-Rule function
3. Remove training records covered by the rule
4. Repeat Step (2) and (3) until stopping criterion
is met

9/30/2020 Introduction to Data Mining, 2nd Edition 12

Example of Sequential Covering

(i) Original Data (ii) Step 1

9/30/2020 Introduction to Data Mining, 2nd Edition 13

Example of Sequential Covering…

R1 R1

R2

(iii) Step 2 (iv) Step 3

9/30/2020 Introduction to Data Mining, 2nd Edition 14

 Rule Growing

Two common strategies

Yes: 3
{} No: 4
Refund=No, Refund=No,
Status=Single, Status=Single,
Income=85K Income=90K
(Class=Yes) (Class=Yes)

Refund=
No
Status =
Single
Status =
Divorced
Status =
Married
... Income
> 80K
Refund=No,
Status = Single
Yes: 3 Yes: 2 Yes: 1 Yes: 0 Yes: 3 (Class = Yes)
No: 4 No: 1 No: 0 No: 3 No: 1

(a) General-to-specific (b) Specific-to-general

9/30/2020 Introduction to Data Mining, 2nd Edition 15

 Data Mining
Classification: Alternative Techniques

9/30/2020 Introduction to Data Mining, 2nd Edition 16

Nearest Neighbor Classifiers

Basic idea:
– If it walks like a duck, quacks like a duck, then
it’s probably a duck

Compute
Distance Test
Record

Training Choose k of the

Records “nearest” records

9/30/2020 Introduction to Data Mining, 2nd Edition 17

Nearest-Neighbor Classifiers
Unknown record Requires the following:
– A set of labeled records
– Proximity metric to compute
distance/similarity between a
pair of records (e.g.,
Euclidean distance)
– The value of k, the number of
nearest neighbors to retrieve
– A method for using class
labels of K nearest neighbors
to determine the class label of
unknown record (e.g., by
taking majority vote)

9/30/2020 Introduction to Data Mining, 2nd Edition 18

How to Determine the class label of a Test Sample?

Take the majority vote of class labels among the k-

nearest neighbors
Weight the vote according to distance
– weight factor, 𝑤 = 1/𝑑2

9/30/2020 Introduction to Data Mining, 2nd Edition 19

Nearest Neighbor Classification…

Choosing the value of k:

– If k is too small, sensitive to noise points
– If k is too large, neighborhood may include points from
other classes

9/30/2020 Introduction to Data Mining, 2nd Edition 20

 Data Mining
Classification: Alternative Techniques

9/30/2020 Introduction to Data Mining, 2nd Edition 21

Bayes Classifier

A probabilistic framework for solving classification

problems
Conditional Probability: P( X ,Y )
P (Y | X ) =
P( X )
P( X ,Y )
P( X | Y ) =
P (Y )
Bayes theorem:
P( X | Y ) P(Y )
P(Y | X ) =
P( X )

9/30/2020 Introduction to Data Mining, 2nd Edition 22

Using Bayes Theorem for Classification

Consider each attribute and class

label as random variables

al al us
ir c ir c o
u
Given a record with attributes (X1, te go
te go
ntin
la ss
c a c a co c
X2,…, Xd) Tid Refund Marital Taxable
Status Income Evade
– Goal is to predict class Y
1 Yes Single 125K No
– Specifically, we want to find the value of 2 No Married 100K No
Y that maximizes P(Y| X1, X2,…, Xd ) 3 No Single 70K No
4 Yes Married 120K No
5 No Divorced 95K Yes
Can we estimate P(Y| X1, X2,…, Xd ) 6 No Married 60K No

directly from data? 7 Yes Divorced 220K No

8 No Single 85K Yes
9 No Married 75K No
10 No Single 90K Yes
10

9/30/2020 Introduction to Data Mining, 2nd Edition 23

Using Bayes Theorem for Classification

Approach:
– compute posterior probability P(Y | X1, X2, …, Xd) using
the Bayes theorem
P( X 1 X 2  X d | Y ) P(Y )
P(Y | X 1 X 2  X n ) =
P( X 1 X 2  X d )

– Maximum a-posteriori: Choose Y that maximizes

P(Y | X1, X2, …, Xd)

– Equivalent to choosing value of Y that maximizes

P(X1, X2, …, Xd|Y) P(Y)

How to estimate P(X1, X2, …, Xd | Y )?

9/30/2020 Introduction to Data Mining, 2nd Edition 24
 Example Data
Given a Test Record:
al al us
go
ir c
go
ir cX = (Refund = No, Married, Income = 120K)
in
uo
te te nt a ss
l
ca ca co c
Tid Refund Marital Taxable
Status Income Evade • Can we estimate
1 Yes Single 125K No P(Evade = Yes | X) and P(Evade = No | X)?
2 No Married 100K No
3 No Single 70K No
4 Yes Married 120K No In the following we will replace
5 No Divorced 95K Yes
Evade = Yes by Yes, and
6 No Married 60K No
7 Yes Divorced 220K No Evade = No by No
8 No Single 85K Yes
9 No Married 75K No
10 No Single 90K Yes
10

9/30/2020 Introduction to Data Mining, 2nd Edition 25

 Example Data
Given a Test Record:
al al us
go
ir c
go
ir cX = (Refund = No, Married, Income = 120K)
in
uo
te te nt a ss
l
ca ca co c
Tid Refund Marital Taxable
Status Income Evade

1 Yes Single 125K No

2 No Married 100K No
3 No Single 70K No
4 Yes Married 120K No
5 No Divorced 95K Yes
6 No Married 60K No
7 Yes Divorced 220K No
8 No Single 85K Yes
9 No Married 75K No
10 No Single 90K Yes
10

9/30/2020 Introduction to Data Mining, 2nd Edition 26

Naïve Bayes Classifier

Assume independence among attributes Xi when class is

given:
– P(X1, X2, …, Xd |Yj) = P(X1| Yj) P(X2| Yj)… P(Xd| Yj)

– Now we can estimate P(Xi| Yj) for all Xi and Yj

combinations from the training data

9/30/2020 Introduction to Data Mining, 2nd Edition 27

 Naïve Bayes on Example Data
Given a Test Record:
al al us
go
ir c
go
ir cX = (Refund = No, Married, Income = 120K)
in
uo
te te nt a ss
l
ca ca co c
Tid Refund Marital Taxable
Status Income Evade P(X | Yes) =
1 Yes Single 125K No
P(Refund = No | Yes) x
2 No Married 100K No
3 No Single 70K No
P(Married | Yes) x
4 Yes Married 120K No P(Income = 120K | Yes)
5 No Divorced 95K Yes
6 No Married 60K No
7 Yes Divorced 220K No
P(X | No) =
8 No Single 85K Yes P(Refund = No | No) x
9 No Married 75K No
P(Married | No) x
10 No Single 90K Yes
10

P(Income = 120K | No)

9/30/2020 Introduction to Data Mining, 2nd Edition 28

 Estimate Probabilities from Data
l l
ic a ic a
ous
or or nu s
te g
te g
nti
cla s P(y) = fraction of instances of class y
ca ca co
Tid Refund Marital Taxable – e.g., P(No) = 7/10,
Status Income Evade P(Yes) = 3/10
1 Yes Single 125K No
2 No Married 100K No For categorical attributes:
3 No Single 70K No
4 Yes Married 120K No
P(Xi =c| y) = nc/ n
5 No Divorced 95K Yes
– where |Xi =c| is number of
6 No Married 60K No instances having attribute
7 Yes Divorced 220K No value Xi =c and belonging to
8 No Single 85K Yes class y
9 No Married 75K No
– Examples:
10 No Single 90K Yes
P(Status=Married|No) = 4/7
10

P(Refund=Yes|Yes)=0

9/30/2020 Introduction to Data Mining, 2nd Edition 29

Estimate Probabilities from Data

For continuous attributes:

– Discretization: Partition the range into bins:
◆ Replace continuous value with bin value
– Attribute changed from continuous to ordinal

– Probability density estimation:

◆ Assume attribute follows a normal distribution
◆ Use data to estimate parameters of distribution
(e.g., mean and standard deviation)
◆ Once probability distribution is known, use it to
estimate the conditional probability P(Xi|Y)

9/30/2020 Introduction to Data Mining, 2nd Edition 30

 Estimate
oric a l
Probabilities
or ic a l
uous from Data
teg teg ntin a s s
a a l
c c co c
Tid Refund Marital
Status
Taxable
Income Evade
Normal distribution:
( X i − ij )2
−
1 Yes Single 125K No 1 2 ij2
P( X i | Y j ) = e
2
2 No Married 100K No 2
ij
3 No Single 70K No
4 Yes Married 120K No – One for each (Xi,Yi) pair
5 No Divorced 95K Yes
6 No Married 60K No For (Income, Class=No):
7 Yes Divorced 220K No
– If Class=No
8 No Single 85K Yes
9 No Married 75K No
◆ sample mean = 110
10 No Single 90K Yes ◆ sample variance = 2975
10

1 −
( 120−110 ) 2

P( Income = 120 | No) = e 2 ( 2975 )

= 0.0072
2 (54.54)
9/30/2020 Introduction to Data Mining, 2nd Edition 31
 Issues with Naïve Bayes Classifier
Given a Test Record:

X = (Refund = No, Married, Income = 120K)

Naïve Bayes Classifier:
P(X | No) = P(Refund = No | No) X
P(Refund = Yes | No) = 3/7
P(Refund = No | No) = 4/7 P(Married | No) X
P(Refund = Yes | Yes) = 0
P(Refund = No | Yes) = 1 P(Income=120|No)
P(Marital Status = Single | No) = 2/7
P(Marital Status = Divorced | No) = 1/7 =4/7 X 4/7 X 0.0072= 0.0024
P(Marital Status = Married | No) = 4/7
P(Marital Status = Single | Yes) = 2/7
P(Marital Status = Divorced | Yes) = 1/7
P(Marital Status = Married | Yes) = 0
P(X | Yes) = P(Refund = No | Yes) X

For Taxable Income: P(Married | Yes) X

If class = No: sample mean = 110
sample variance = 2975 P(Income=120 | Yes)
If class = Yes: sample mean = 90
sample variance = 25 =1 X 0 X 1.2 X 10 e (-9) = 0

9/30/2020 Introduction to Data Mining, 2nd Edition 32

Issues with Naïve Bayes Classifier

P(X | No) P(No) > P(X | Yes) P(Yes)

P(No | X) > P(Yes | X) => Class=No

9/30/2020 Introduction to Data Mining, 2nd Edition 33

 Example of Naïve Bayes Classifier

Name Give Birth Can Fly Live in Water Have Legs Class
human yes no no yes mammals
A: attributes
python no no no no non-mammals M: mammals
salmon no no yes no non-mammals
whale yes no yes no mammals N: non-mammals
frog no no sometimes yes non-mammals
komodo no no no yes non-mammals
6 6 2 2
bat
pigeon
yes
no
yes
yes
no
no
yes
yes
mammals
non-mammals
P ( A | M ) =    = 0.06
cat yes no no yes mammals
7 7 7 7
leopard shark yes no yes no non-mammals 1 10 3 4
turtle no no sometimes yes non-mammals P ( A | N ) =    = 0.0042
penguin no no sometimes yes non-mammals 13 13 13 13
porcupine yes no no yes mammals
7
P ( A | M ) P ( M ) = 0.06  = 0.021
eel no no yes no non-mammals
salamander no no sometimes yes non-mammals
gila monster no no no yes non-mammals 20
platypus no no no yes mammals
13
owl
dolphin
no
yes
yes
no
no
yes
yes
no
non-mammals
mammals
P ( A | N ) P( N ) = 0.004  = 0.0027
eagle no yes no yes non-mammals 20

P(A|M)P(M) > P(A|N)P(N)

Give Birth Can Fly Live in Water Have Legs Class
yes no yes no ? => Mammals

9/30/2020 Introduction to Data Mining, 2nd Edition 34

 Data Mining
Classification: Alternative Techniques

9/30/2020 Introduction to Data Mining, 2nd Edition 35

Artificial Neural Networks (ANN)

Basic Idea: A complex non-linear function can be

learned as a composition of simple processing units
ANN is a collection of simple processing units
(nodes) that are connected by directed links (edges)
– Every node receives signals from incoming edges,
performs computations, and transmits signals to
outgoing edges
– Analogous to human brain where nodes are neurons
and signals are electrical impulses
– Weight of an edge determines the strength of
connection between the nodes
– Simplest ANN: Perceptron (single neuron)
9/30/2020 Introduction to Data Mining, 2nd Edition 36
Basic Architecture of Perceptron

Learns linear decision boundaries

Similar to logistic regression (activation function is sign
instead of sigmoid)
9/30/2020 Introduction to Data Mining, 2nd Edition 37
Perceptron Example

X1 X2 X3 Y Input Black box

1 0 0 -1
1 0 1 1
X1
1 1 0 1 Output
1 1 1 1
0 0 1 -1
X2 Y
0 1 0 -1
0 1 1 1 X3
0 0 0 -1

Output Y is 1 if at least two of the three inputs are equal to 1.

9/30/2020 Introduction to Data Mining, 2nd Edition 38

Perceptron Example

Input
nodes Black box
X1 X2 X3 Y
1 0 0 -1 Output
1 0 1 1
X1 0.3 node
1 1 0 1
1 1 1 1
X2 0.3 
0 0 1 -1
Y
0 1 0 -1
0 1 1 1 X3 0.3 t=0.4
0 0 0 -1

Y = sign(0.3 X 1 + 0.3 X 2 + 0.3 X 3 − 0.4)

 1 if x  0
where sign( x ) = 
− 1 if x  0
9/30/2020 Introduction to Data Mining, 2nd Edition 39
Perceptron Learning Rule

Initialize the weights (w0, w1, …, wd)

Repeat
– For each training example (xi, yi)
◆ Compute 𝑦ෝ𝑖
◆ Update the weights:

Until stopping condition is met

k: iteration number; 𝜆: learning rate

9/30/2020 Introduction to Data Mining, 2nd Edition 40

Perceptron Learning Rule

Weight update formula:

Intuition:
– Update weight based on error: e =
– If y = 𝑦,
ො e=0: no update needed
– If y > 𝑦:
ො weight must be increased so that 𝑦ො
will increase
– If y < 𝑦:
ො weight must be decreased so that 𝑦ො
will decrease
9/30/2020 Introduction to Data Mining, 2nd Edition 41
Perceptron Learning

Since y is a linear
combination of input
variables, decision
boundary is linear

9/30/2020 Introduction to Data Mining, 2nd Edition 42

Perceptron Learning

Since y is a linear
combination of input
variables, decision
boundary is linear

For nonlinearly separable problems, perceptron

learning algorithm will fail because no linear
hyperplane can separate the data perfectly

9/30/2020 Introduction to Data Mining, 2nd Edition 43

Nonlinearly Separable Data

XOR Data

y = x1  x2
x1 x2 y
0 0 -1
1 0 1
0 1 1
1 1 -1

9/30/2020 Introduction to Data Mining, 2nd Edition 44

 Multi-layer Neural Network

x1 x2 x3 x4 x5
More than one hidden layer of
Input computing nodes
Layer

Every node in a hidden layer

operates on activations from
Hidden preceding layer and transmits
Layer
activations forward to nodes of
next layer

Output Also referred to as

Layer
“feedforward neural networks”
y

9/30/2020 Introduction to Data Mining, 2nd Edition 45

Multi-layer Neural Network

Multi-layer neural networks with at least one

hidden layer can solve any type of classification
task involving nonlinear decision surfaces
XOR Data

Input Hidden Output

Layer Layer Layer

w31
x1 n1 n3 w53
w41

n5 y

w32
w54
x2 n2 n4
w42

9/30/2020 Introduction to Data Mining, 2nd Edition 46

Why Multiple Hidden Layers?

Activations at hidden layers can be viewed as features

extracted as functions of inputs
Every hidden layer represents a level of abstraction
– Complex features are compositions of simpler features

Number of layers is known as depth of ANN

– Deeper networks express complex hierarchy of features

9/30/2020 Introduction to Data Mining, 2nd Edition 47

Multi-Layer Network Architecture

�
�

Activation value Activation

at node i at layer l Function Linear Predictor

9/30/2020 Introduction to Data Mining, 2nd Edition 48

Activation Functions

9/30/2020 Introduction to Data Mining, 2nd Edition 49

 Data Mining
Classification: Alternative Techniques

9/30/2020 Introduction to Data Mining, 2nd Edition 50

Support Vector Machines

Find a linear hyperplane (decision boundary) that will separate the data
9/30/2020 Introduction to Data Mining, 2nd Edition 51
Support Vector Machines

B1

One Possible Solution

9/30/2020 Introduction to Data Mining, 2nd Edition 52
Support Vector Machines

B2

Another possible solution

9/30/2020 Introduction to Data Mining, 2nd Edition 53
Support Vector Machines

B2

Other possible solutions

9/30/2020 Introduction to Data Mining, 2nd Edition 54
Support Vector Machines

B1

B2

Which one is better? B1 or B2?

How do you define better?
9/30/2020 Introduction to Data Mining, 2nd Edition 55
Support Vector Machines

B1

B2

b21
b22

margin
b11

b12

Find hyperplane maximizes the margin => B1 is better than B2

9/30/2020 Introduction to Data Mining, 2nd Edition 56
 Support Vector Machines

B1

 
w• x + b = 0
 
 
w • x + b = −1 w • x + b = +1

b11

  b12
 1 if w • x + b  1 2
f ( x) =    Margin = 
− 1 if w • x + b  −1 || w ||
9/30/2020 Introduction to Data Mining, 2nd Edition 57
Linear SVM

Linear model:
 
 1 if w • x + b  1
f ( x) =   
 − 1 if w • x + b  −1

Learning the model is equivalent to determining


the values of w and b

– How to find w and b from training data?

9/30/2020 Introduction to Data Mining, 2nd Edition 58

Learning Linear SVM
2
Objective is to maximize: Margin = 
|| w ||
 2
 || w ||
– Which is equivalent to minimizing: L( w) =
2
– Subject to the following constraints:
 
1 if w • x i + b  1
yi =   
− 1 if w • x i + b  −1
or
𝑦𝑖 (w • x𝑖 + 𝑏) ≥ 1, 𝑖 = 1,2, . . . , 𝑁

◆ This is a constrained optimization problem

– Solve it using Lagrange multiplier method

9/30/2020 Introduction to Data Mining, 2nd Edition 59

Example of Linear SVM

Support vectors

x1 x2 y l
0.3858 0.4687 1 65.5261
0.4871 0.611 -1 65.5261
0.9218 0.4103 -1 0
0.7382 0.8936 -1 0
0.1763 0.0579 1 0
0.4057 0.3529 1 0
0.9355 0.8132 -1 0
0.2146 0.0099 1 0

9/30/2020 Introduction to Data Mining, 2nd Edition 60

Learning Linear SVM

Decision boundary depends only on support

vectors
– If you have data set with same support
vectors, decision boundary will not change

– How to classify using SVM once w and b are

found? Given a test record, xi
 
 1 if w • x i + b  1
f ( xi ) =   
− 1 if w • x i + b  −1

9/30/2020 Introduction to Data Mining, 2nd Edition 61

Support Vector Machines

What if the problem is not linearly separable?

9/30/2020 Introduction to Data Mining, 2nd Edition 62

Support Vector Machines

What if the problem is not linearly separable?

– Introduce slack variables
◆ Need to minimize:  2
|| w ||  N k
L( w) = + C  i 
◆ Subject to:
2  i =1 

 
1 if w • x i + b  1 - i
yi =   
− 1 if w • x i + b  −1 + i

◆ If k is 1 or 2, this leads to similar objective function

as linear SVM but with different constraints (see
textbook)

9/30/2020 Introduction to Data Mining, 2nd Edition 63

Support Vector Machines

B1

B2

b21
b22

margin
b11

b12

Find the hyperplane that optimizes both factors

9/30/2020 Introduction to Data Mining, 2nd Edition 64
Nonlinear Support Vector Machines

What if decision boundary is not linear?

9/30/2020 Introduction to Data Mining, 2nd Edition 65

Example of Nonlinear SVM

SVM with polynomial

degree 2 kernel

9/30/2020 Introduction to Data Mining, 2nd Edition 66

Characteristics of SVM

The learning problem is formulated as a convex optimization problem

– Efficient algorithms are available to find the global minima
– Many of the other methods use greedy approaches and find locally
optimal solutions
– High computational complexity for building the model

Robust to noise
Overfitting is handled by maximizing the margin of the decision boundary,
SVM can handle irrelevant and redundant better than many other
techniques
The user needs to provide the type of kernel function and cost function
Difficult to handle missing values

What about categorical variables?

9/30/2020 Introduction to Data Mining, 2nd Edition 67