Chapter 9.

Classification: Advanced Methods

• Bayesian Belief Networks

• Artificial Neural Networks
• Support Vector Machines
• Lazy Learners (or Learning from Your Neighbors)
• Other Classification Methods
• Additional Topics Regarding Classification
• Summary

3
Artificial Neural Networks

McCulloch (1898 – 1969) & Pitts (1923 – 1969)

USA
4
Artificial Neural Networks

Source: [Link]
Biological Neural Networks

Biological neural networks

– 10 neurons (neural cells)
– Only a small portion of these cells are used
– Main features
• distributed nature, parallel processing
• each region of the brain controls specialized task(s)
• no cell contains too much information: simple
and small processors
• information is saved mainly in the connections among neurons
 Neural Networks
• learning and generalization through examples
• simple building block: neuron
• Dendrites: collecting signals from other neurons
• Soma (cell body): spatial summation and processing
• Axon: transmitting signals to dendrites of other cells

Input from Other neurons

Output to Other neurons

Send signal down the Axon

[Link]
From Biological to Artificial Intelligence

[Link]

[Link]
 Biological vs. Artificial Neural Networks
From biological neuron to schematic structure of artificial neuron
• biological:
Input from Other neurons
o Inputs
Output to Other neurons
o Summation of inputs
o Processing unit
o Output

Send signal down the Axon

x1
w1 y = f ( w1 x1 + ... + wn xn )
• artificial:
wN
xN
Biological vs. Artificial Neural Networks

• Artificial neural nets: neuron 1

o Formation of artificial neurons y1

w11 neuron 2
y2
x1
w1i neuron i

xN yi
wNi

neuron M-1
wNM y M -1
neuron M
yM
A neural network: A set of connected input/output units where each
connection has a weight associated with it
Biological vs. Artificial Neural Networks
• Multi-layer neural nets:
o Serial connection of single layers:
y1
w11
y2
x1
w1i
xN yi
wNi

wNM y M -1
yM

• Training: finding the best values of weights wij

o Training happens iteratively and through exposing the network to
examples: wij (new ) = wij (old) + Dwij
 How A Multi-Layer Neural Network Works

• The inputs to the network correspond to the attributes from training tuple
• Inputs are fed simultaneously into the units making up the input layer
• They are then weighted and fed simultaneously to a hidden layer
• The number of hidden layers is arbitrary
• The weighted outputs of the last hidden layer are input to units making up the output
layer, which emits the network's prediction
• The network is Feed-Forward.
• From a statistical point of view, networks perform nonlinear regression:

12
Feed Forward vs. Recurrent Neural Networks
Recurrent NN: connections between feed-forward NN: None of the
nodes can create a cycle, allowing output weight's cycles back to an input unit
from some nodes to affect subsequent or to an output unit of a previous
input to the same nodes. layer

2023-03-19 MGSC5126: Data Mining 13

 From a statistical point of view, networks perform nonlinear regression:
Given enough hidden units and enough training samples, they can closely
approximate any function

2023-03-19 MGSC5126: Data Mining 14

Neurons
• Receives n-inputs

• Multiplies each input by its weight

• Applies activation function to the sum of results

• Outputs result
 Activation Functions

• Controls when unit is “active”

or “inactive”
• Threshold function outputs 1
when input is positive and 0
otherwise
• Sigmoid function:
 Defining a Network Topology
• Decide the network topology: Specify # of units in the input layer, # of
hidden layers (if > 1), # of units in each hidden layer, and # of units in the
output layer
• One input unit per domain value, each initialized to 0
o Normalize the input values for each attribute measured in the training tuples to
[0.0—1.0]
• Output, if for classification and more than two classes, one output unit per
class is used
• Once a network has been trained and its accuracy is unacceptable, repeat
the training process with a different network topology or a different set of
initial weights

18
Classification by Backpropagation

• Backpropagation: A neural network learning algorithm

• During the learning phase, the network learns by adjusting the
weights so as to be able to predict the correct class label of the
input tuples
• Also referred to as connectionist learning due to the
connections between units

19
Backpropagation
 Backpropagation

• Iteratively process a set of training tuples & compare the network's

prediction with the actual known target value
• For each training tuple, the weights are modified to minimize the
mean squared error between the network's prediction and the actual
target value
• Modifications are made in the “backwards” direction: from the output
layer, through each hidden layer down to the first hidden layer, hence
“backpropagation”

21
 Backpropagation
Steps
• Initialize weights to small random numbers, associated with
biases
• Propagate the inputs forward (by applying activation
function)
• Backpropagate the error (by updating weights and biases)
• Terminating condition (when error is very small, etc.)

22
Neural Network as a Classifier
• Strength
o High tolerance to noisy data
o Ability to classify untrained patterns
o Well-suited for continuous-valued inputs and outputs
o Successful on an array of real-world data, e.g., hand-written letters
o Algorithms are inherently parallel
o Techniques have recently been developed for the extraction of rules from trained
neural networks
• Weakness
o Long training time
o Require a number of parameters typically best determined empirically, e.g., the
network topology or “structure.”
o Poor interpretability: Difficult to interpret the symbolic meaning behind the learned
weights and of “hidden units” in the network

23
Support Vector Machine

Vladimir Naumovich Vapnik (1936 - )

Russia
24
SVM—Support Vector Machines

Let’s imagine we have training data:

• two labels: red and blue
• two features: x and y

Goal: build a classifier that, given a pair of

(x,y) coordinates, outputs if it’s
either red or blue.

2023-03-19 Capstone Project: BUSS-5802-11 25

SVM—Support Vector Machines

A support vector machine takes these data

points and outputs the hyperplane (which in
two dimensions it’s simply a line) that best
separates the tags.

2023-03-19 Capstone Project: BUSS-5802-11 26

SVM—Support Vector Machines

Question: what exactly is the best

hyperplane?

For SVM, it’s the one that maximizes

the margins from both labels.

2023-03-19 Capstone Project: BUSS-5802-11 27

 SVM—When Data Is Linearly Separable

There are infinite lines (hyperplanes) separating

the two classes
but we want to find the best one (the one that
minimizes classification error on unseen data)

SVM searches for the hyperplane with the largest margin, i.e., maximum
marginal hyperplane (MMH)
28
 SVM—General Philosophy

2023-03-19 MGSC5126: Data Mining 29

What is a Support Vector?

• The support vectors are the essential or critical training examples —

they lie closest to the decision boundary
• The complexity of trained classifier is characterized by the # of
support vectors rather than the dimensionality of the data

2023-03-19 MGSC5126: Data Mining 30

SVM—Linearly Separable
A separating hyperplane can be written as
W●X+b=0
where W={w1, w2, …, wn} is a weight vector and b a scalar (bias)

31
SVM—General Philosophy

2023-03-19 MGSC5126: Data Mining 32

 SVM—Nonlinear Seperable

• It uses a nonlinear mapping to transform the original training data into a higher
dimension
• With the new dimension, it searches for the linear optimal separating
hyperplane (i.e., “decision boundary”)

33
 Nonlinear Data

what we’ll do:

we will add a third dimension. Up until now,
we had two dimensions: $x$ and $y$. We
create a new z dimension, and we rule that it
be calculated a certain way that is convenient
for us:
z = x² + y²
This will give us a three-dimensional space. :

2023-03-19 MGSC5126: Data Mining 34

 Nonlinear Data

z = x² + y²
Taking a slice of that space, it looks like this:. :

2023-03-19 MGSC5126: Data Mining 35

 Nonlinear Data

What SVM can do now?

since we are in three dimensions now, the

hyperplane is a plane parallel to the x axis at a
certain z (let’s say z = 1).

2023-03-19 MGSC5126: Data Mining 36

 Nonlinear Data

Let’s map it to to two dimensions:

2023-03-19 MGSC5126: Data Mining 37

SVM—History and Applications

• Features: training can be slow but accuracy is high owing to

their ability to model complex nonlinear decision boundaries
(margin maximization)
• Used for: classification and numeric prediction

• Applications:
o handwritten digit recognition, object recognition, speaker
identification, benchmarking time-series prediction tests

38
Why Is SVM Effective on High Dimensional Data?

n The support vectors are the essential or critical training examples —

they lie closest to the decision boundary
n If all other training examples are removed and the training is repeated,
the same separating hyperplane would be found
n Thus, an SVM with a small number of support vectors can have good
generalization, even when the dimensionality of the data is high

39
SVM vs. Neural Network

• SVM • Neural Network

o Deterministic algorithm • Nondeterministic algorithm
o Nice generalization • Generalizes well but
properties doesn’t have strong
mathematical foundation
o Hard to learn – learned in
batch mode using • Can easily be learned in
incremental fashion
quadratic programming
techniques • To learn complex
functions—use multilayer
o Using kernels can learn
perceptron (nontrivial)
very complex functions
40
SVM Related Links

• SVM Website: [Link]

• Representative implementations
o LIBSVM: an efficient implementation of SVM, multi-class
classifications, nu-SVM, one-class SVM, including also various
interfaces with java, python, etc.
o SVM-light: simpler but performance is not better than
LIBSVM, support only binary classification and only in C
o SVM-torch: another recent implementation also written in C

41
Lazy vs. Eager Learning

2023-03-19 MGSC5126: Data Mining 42

Lazy vs. Eager Learning

• Lazy learning also known as just-in-time learning (e.g., instance-based

learning): Simply stores training data (or only minor processing) and
waits until it is given a test tuple

• Eager learning: Given a set of training tuples, constructs a classification

model before receiving new (e.g., test) data to classify

Lazy: less time in training but more time in predicting

43
Lazy vs. Eager Learning (Accuracy)

Accuracy
• Lazy method: effectively uses a richer hypothesis space since it
uses many local linear functions to form an implicit global
approximation to the target function

• Eager method: must commit to a single hypothesis that covers

the entire instance space

44
Lazy Learner: Instance-Based Methods

• Instance-based learning:
o Store training examples and delay the processing (“lazy
evaluation”) until a new instance must be classified
• Typical approaches
o k-nearest neighbor approach
Instances represented as points in a Euclidean space.
o Case-based reasoning
Uses symbolic representations and kn
o Locally weighted regression
Constructs local approximation
Kowledge-based inference

45
 k-Nearest Neighbor (K-NN)
Finds records in a database that have similar numerical values
of a set of predictor variables.

2023-03-19 MGSC5126: Data Mining 46

k-Nearest Neighbors (k-NN)
The nearest neighbor are defined in terms of Euclidean
distance, dist(X1, X2)
k-Nearest Neighbors (k-NN)
For discrete-valued, k-NN returns the most common value among
the k training examples nearest to xq
The k-Nearest Neighbor Algorithm
• Vonoroi diagram: the decision surface induced by 1-NN for a
typical set of training examples

_
_
_ _ .
+
_
. +
xq +
. . .
_ + .

49
The k-Nearest Neighbor Algorithm

2023-03-19 MGSC5126: Data Mining 50

The k-Nearest Neighbor Algorithm

What is the K ?

2023-03-19 MGSC5126: Data Mining 51

k-Nearest Neighbor Rules
• The nearest neighbor to a record is the one that has the smallest
distance from it.
– If k = 1, then the 1-NN rule classifies a record in the same category as its
nearest neighbor.
– k-NN rule finds the k-Nearest Neighbors to each record we want to classify
and then assigns the classification as the classification of majority of the k
nearest neighbors.
• Typically, various values of k are used and then results inspected
to determine which is best.
The k-Nearest Neighbor Algorithm

• How can I determine the value of k, the number of

neighbors?
• In general, the larger the number of training tuples is, the
larger the value of k is
• Nearest-neighbor classifiers can be extremely slow when
classifying test tuples O(n)
• By simple presorting and arranging the stored tuples into
search tree, the number of comparisons can be reduced to
O(logN)

2023-03-19 MGSC5126: Data Mining 53

K-NN in Action: Example
We have generated data for 2-dimentional 3-class problem where classes are
non-linearly separable.
We use the k-nn with
K= 5
Metric = Euclidean Distance

Three Classes: Blue, Red, Green

X
2023-03-19 MGSC5126: Data Mining 54
K-NN in Action: Example 1
We have generated data for 2-dimentional 3-class problem where the classes
are non-linearly separable.
We use the k-nn with
K= 5
Metric = Euclidean Distance

2023-03-19 MGSC5126: Data Mining 55

Discussion on the k-NN Algorithm

• k-NN for real-valued prediction for a given unknown tuple

o Returns the mean values of the k nearest neighbors
• Distance-weighted nearest neighbor algorithm
o Weight the contribution of each of the k neighbors according
to their distance to the query xq wº 1
Give greater weight to closer neighbors d ( xq , x )2
i

56
K-NN in Action – Example 3
let us consider an example where the data concerned with credit default. Age and Loan are
two numerical variables (predictors) and Default is the target.

New customer

2023-03-19 MGSC5126: Data Mining 57

By observing the data mentioned above, we can use the training set in order to classify an
unknown case (Age=48 and Loan=$142,000) using Euclidean distance. If K=1 then the nearest
neighbor is the last case in the training set with Default=Y.

2023-03-19 MGSC5126: Data Mining 58

 Age Loan Default Distance
25 $40,000 N 102000
35 $60,000 N 82000
45 $80,000 N 62000
20 $20,000 N 122000
35 $120,000 N 22000 2
52 $18,000 N 124000
23 $95,000 Y 47000
40 $62,000 Y 80000
60 $100,000 Y 42000 3
48 $220,000 Y 78000
33 $150,000 Y 8000 1

48 $142,000 ?

With K=3, there are two Default=Y and one Default=N out of three closest
neighbors. The prediction for the unknown case is again Default=Y.

2023-03-19 MGSC5126: Data Mining 59

How is K in K-means different from K in K-NN?

K-Means Clustering and k-Nearest Neighbors algorithm, both are

commonly used algorithms in Machine Learning.
They are often confused with each other, especially when we are
talking about the k-factor. The ‘K’ in K-Means Clustering has nothing
to do with the ‘K’ in K-NN algorithm.
k-Means Clustering is an unsupervised learning algorithm that is
used for clustering whereas K-NN is a supervised learning algorithm
used for classification.

2023-03-19 MGSC5126: Data Mining 60

 Case-Based Reasoning (CBR)
• CBR: Uses a database of problem solutions to solve new problems
• Store symbolic description (tuples or cases)—not points in a Euclidean space
• Applications: Customer-service (product-related diagnosis), legal ruling
• Methodology
o Instances represented by rich symbolic descriptions (e.g., function graphs)
o Search for similar cases, multiple retrieved cases may be combined
o Tight coupling between case retrieval, knowledge-based reasoning, and
problem solving

61
Case-Based Reasoning (CBR)

2023-03-19 MGSC5126: Data Mining 62

Case-Based Reasoning (CBR) -Challenges

• Find a good similarity metric

• Indexing based on syntactic similarity measure, and
when failure, backtracking, and adapting to additional
cases

63
Fuzzy Systems

64
Fuzzy Logic

The World is Vague

“A person with n hair count is bald”

“Nikolas has n+1 hair count?”

Nikolas is bald.

1
Fuzzy Sets Approximation

The World is Vague

A person with n hair count is bold

“Nikolas has n+1 hair count?”

Nikolas is bald
Vague statement

Vagueness means lack of clarity or distinctness

2
Boolean Logic

• Assumes that every fact is either entirely true or false

• Eliminates vagueness from natural language

3
Boolean Logic Representation

Slow Fast
Speed = 0 Speed = 1

bool speed;
get the speed
if ( speed == 0)
{// speed is slow}
else
{// speed is fast}
Fuzzy Logic Representation

Slowest Slow Fast Fastest

[ 0.0 – 0.25 ] [ 0.25 – 0.50 ] [ 0.50 – 0.75 ] [ 0.75 – 1.00 ]

float speed;
get the speed
if ((speed >= 0.0)&&(speed < 0.25))
{// speed is slowest}
else if ((speed >= 0.25)&&(speed < 0.5))
{// speed is slow}
else if ((speed >= 0.5)&&(speed < 0.75))
{// speed is fast}
else // speed >= 0.75 && speed < 1.0
{// speed is fastest}

5
Fuzzy Logic

• Extends Boolean logic to handle the expression of vague

concepts

• A way to represent variation or imprecision in logic

o A way to make use of natural language in logic

o Allows degree of truth to a fact

6
Definition of Fuzzy Sets

A set that allows elements to belong to it to a particular extent.

A fuzzy set is defined by a membership function

that maps elements of a given domain (a crisp µ
set) into values in [0, 1].
1

mA: U [0, 1] 0.5

mA A
0
25 30 40

7
Fuzziness VS. Probability
Which would you choose to drink?

Degree of membership function Probability of being

to potable liquids fuzzy set potable liquids

Figure 1: masked

8
Figure: Adapted from B. R. Kosanovic, Fuzziness and Probability
Fuzziness VS. Probability
Which would you choose to drink?

Degree of membership function Probability of being

to potable liquids fuzzy set potable liquids

Figure 1: masked Figure 2: Unmasked

8
Figure: Adapted from B. R. Kosanovic, Fuzziness and Probability
Case Study: Fuzzy Air Conditioner

Speed of a heater fan changes based on the room temperature and

humidity

10
Fuzzy Linguistic Variables

Temp: {Cold, Cool, Warm, Hot}

Humidity: {Low, Med, High}

The Linguistic Variables are “Vocabulary” of a Fuzzy Logic System!

11
Membership Functions

• Degree of Truth or Membership

“How cool is 65 F° ?”

12
Membership Functions

• How cool is 65 F° ?
“It is Cool with the degree of 0.4”
μ

0.4

65

13
Fuzzification

Calculate Input Membership Levels

65 F° Þ Cool = 0.4, Warm= 0.7
0.7

0.4

65

25% Humidity ÞLow = 0.8, Medium = 0.2

0.8

0.2

25

19
 Fuzzy-Inference (“If-Then” -Rules-)

#1: IF Temp = Cold AND Humidity = high THEN Speed = Stop

#2: IF Temp = Warm AND Humidity = Low THEN Speed = Fast

#3: IF Temp = Cool AND Humidity = Med THEN Speed = Slow

#4: IF Temp = Hot AND Humidity = high THEN Speed = Stop

The Rules of the Fuzzy Logic Systems are the “Laws” it Executes!

21
Multiclass Classification

Classification involving more than two classes (i.e., > 2 Classes)

• Method 1: One-vs.-all (OVA): Learn a classifier one at a time
o Given m classes, train m classifiers: one for each class
o To classify a tuple X, the set of classifiers vote as an ensemble
• Method 2: All-vs.-all (AVA): Learn a classifier for each pair of classes
o Given m classes, construct m(m-1)/2 binary classifiers
o To classify a tuple X, each classifier votes. X is assigned to the class with maximal vote
• Comparison
o All-vs.-all tends to be superior to one-vs.-all
o Problem: Binary classifier is sensitive to errors, and errors affect vote count

80