Transcript No - Binus Repository

Matakuliah : M0614 / Data Mining & OLAP
Tahun
: Feb - 2010
Classification and Prediction (cont.)
Pertemuan 09
Learning Outcomes
Pada akhir pertemuan ini, diharapkan mahasiswa
akan mampu :
• Mahasiswa dapat menggunakan teknik analisis
classification by decision tree induction, Bayesian
classification, classification by back propagation, dan
lazy learners pada data mining. (C3)
3
Bina Nusantara
Acknowledgments
These slides have been adapted from Han, J.,
Kamber, M., & Pei, Y. Data Mining: Concepts
and Technique and Tan, P.-N., Steinbach, M.,
& Kumar, V. Introduction to Data Mining.
Bina Nusantara
Outline Materi
• Rule-based classification
• Classification by back propagation
• Lazy learners (or learning from your neighbours)
5
Bina Nusantara
Rule-Based Classifier
•
Classify records by using a collection of “if…then…” rules
•
Rule: (Condition)  y
– where
• Condition is a conjunctions of attributes
• y is the class label
– LHS: rule antecedent or condition
– RHS: rule consequent
– Examples of classification rules:
• (Blood Type=Warm)  (Lay Eggs=Yes)  Birds
• (Taxable Income < 50K)  (Refund=Yes)  Evade=No
Rule-based Classifier (Example)
Name
human
python
salmon
whale
frog
komodo
bat
pigeon
cat
leopard shark
turtle
penguin
porcupine
eel
salamander
gila monster
platypus
owl
dolphin
eagle
Blood Type
warm
cold
cold
warm
cold
cold
warm
warm
warm
cold
cold
warm
warm
cold
cold
cold
warm
warm
warm
warm
Give Birth
yes
no
no
yes
no
no
yes
no
yes
yes
no
no
yes
no
no
no
no
no
yes
no
Can Fly
no
no
no
no
no
no
yes
yes
no
no
no
no
no
no
no
no
no
yes
no
yes
Live in Water
no
no
yes
yes
sometimes
no
no
no
no
yes
sometimes
sometimes
no
yes
sometimes
no
no
no
yes
no
Class
mammals
reptiles
fishes
mammals
amphibians
reptiles
mammals
birds
mammals
fishes
reptiles
birds
mammals
fishes
amphibians
reptiles
mammals
birds
mammals
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
Rule Extraction from a Decision Tree

Rules are easier to understand than large trees

One rule is created for each path from the root to
a leaf

Each attribute-value pair along a path forms a
conjunction: the leaf holds the class prediction

Rules are mutually exclusive and exhaustive
•
Example: Rule extraction from our buys_computer decision-tree
age?
<=30
student?
no
no
IF age = young AND student = no
THEN buys_computer = no
IF age = young AND student = yes
THEN buys_computer = yes
IF age = mid-age
31..40
yes
yes
yes
>40
credit rating?
excellent
fair
yes
THEN buys_computer = yes
IF age = old AND credit_rating = excellent THEN buys_computer = yes
IF age = young AND credit_rating = fair
April 7, 2016
THEN buys_computer = no
Data Mining: Concepts and Techniques
8
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
hawk
grizzly bear
Blood Type
warm
warm
Give Birth
Can Fly
Live in Water
Class
no
yes
yes
no
no
no
?
?
The rule R1 covers a hawk => Bird
The rule R3 covers the grizzly bear => Mammal
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
lemur
turtle
dogfish shark
Blood Type
warm
cold
cold
Give Birth
Can Fly
Live in Water
Class
yes
no
yes
no
no
no
no
sometimes
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
Rule Coverage and Accuracy
• Coverage of a rule:
– Fraction of records that
satisfy the antecedent of a
rule
• Accuracy of a rule:
– Fraction of records that
satisfy both the antecedent
and consequent of a rule
Tid Refund Marital
Status
Taxable
Income Class
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
No
7
Yes
Divorced 220K
8
No
Single
85K
Yes
9
No
Married
75K
No
10
No
Single
90K
Yes
10
(Status=Single)  No
Coverage = 40%, Accuracy = 50%
60K
No
Characteristics of Rule-Based Classifier
• 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
From Decision Trees To Rules
Classification Rules
Refund
Yes
No
NO
Marita l
Status
{Single,
Divorced}
{Married}
NO
Taxable
Income
< 80K
NO
(Refund=Yes) ==> No
(Refund=No, Marital Status={Single,Divorced},
Taxable Income<80K) ==> No
(Refund=No, Marital Status={Single,Divorced},
Taxable Income>80K) ==> Yes
(Refund=No, Marital Status={Married}) ==> No
> 80K
YES
Rules are mutually exclusive and exhaustive
Rule set contains as much information as the
tree
Rules Can Be Simplified
Refund
Yes
No
NO
Marita l
Status
{Single,
Divorced}
{Married}
NO
Taxable
Income
< 80K
NO
> 80K
YES
Tid Refund Marital
Status
Taxable
Income Cheat
1
Yes
Single
125K
No
2
No
Married
100K
No
3
No
Single
70K
No
4
Yes
Married
120K
No
5
No
Divorced 95K
6
No
Married
7
Yes
Divorced 220K
No
8
No
Single
85K
Yes
9
No
Married
75K
No
10
No
Single
90K
Yes
60K
10
Initial Rule:
(Refund=No)  (Status=Married)  No
Simplified Rule: (Status=Married)  No
Yes
No
Effect of Rule Simplification
• Rules are no longer mutually exclusive
– A record may trigger more than one rule
– Solution?
• Ordered rule set
• Unordered rule set – use voting schemes
• Rules are no longer exhaustive
– A record may not trigger any rules
– Solution?
• Use a default class
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
turtle
Blood Type
cold
Give Birth
Can Fly
Live in Water
Class
no
no
sometimes
?
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},
Taxable Income<80K) ==> No
(Refund=No, Marital Status={Single,Divorced},
Taxable Income<80K) ==> No
(Refund=No, Marital Status={Single,Divorced},
Taxable Income>80K) ==> Yes
(Refund=No, Marital Status={Married}) ==> No
(Refund=No, Marital Status={Married}) ==> No
(Refund=No, Marital Status={Single,Divorced},
Taxable Income>80K) ==> Yes
Building Classification Rules
• Direct Method:
• Extract rules directly from data
• e.g.: RIPPER, CN2, Holte’s 1R
• Indirect Method:
• Extract rules from other classification models (e.g.
decision trees, neural networks, etc).
• e.g: C4.5rules
Rule Induction: Sequential Covering Method
•
Sequential covering algorithm: Extracts rules directly from training data
•
Typical sequential covering algorithms: FOIL, AQ, CN2, RIPPER
•
Rules are learned sequentially, each for a given class Ci will cover many tuples
of Ci but none (or few) of the tuples of other classes
•
Steps:
– Rules are learned one at a time
– Each time a rule is learned, the tuples covered by the rules are removed
– The process repeats on the remaining tuples unless termination condition,
e.g., when no more training examples or when the quality of a rule returned
is below a user-specified threshold
•
Comp. w. decision-tree induction: learning a set of rules simultaneously
April 7, 2016
Data Mining: Concepts and Techniques
19
Sequential Covering Algorithm
while (enough target tuples left)
generate a rule
remove positive target tuples satisfying this rule
Examples covered
by Rule 2
Examples covered
by Rule 1
Examples covered
by Rule 3
Positive
examples
April 7, 2016
Data Mining: Concepts and Techniques
20
How to Learn-One-Rule?
•
Star with the most general rule possible: condition = empty
•
Adding new attributes by adopting a greedy depth-first strategy
– Picks the one that most improves the rule quality
•
Rule-Quality measures: consider both coverage and accuracy
– Foil-gain (in FOIL & RIPPER): assesses info_gain by extending condition
FOIL _ Gain  pos '(log 2
pos '
pos
 log 2
)
pos ' neg '
pos  neg
It favors rules that have high accuracy and cover many positive tuples
•
Rule pruning based on an independent set of test tuples
FOIL _ Prune( R) 
pos  neg
pos  neg
Pos/neg are # of positive/negative tuples covered by R.
If FOIL_Prune is higher for the pruned version of R, prune R
April 7, 2016
Data Mining: Concepts and Techniques
21
Rule Generation
• To generate a rule
while(true)
find the best predicate p
if foil-gain(p) > threshold then add p to current rule
else break
A3=1&&A1=2
A3=1&&A1=2
&&A8=5
A3=1
Positive
examples
April 7, 2016
Negative
examples
Data Mining: Concepts and Techniques
22
Aspects of Sequential Covering
• Rule Growing
• Instance Elimination
• Rule Evaluation
• Stopping Criterion
• Rule Pruning
Rule Growing
• Two common strategies
{}
Yes: 3
No: 4
Refund=No,
Status=Single,
Income=85K
(Class=Yes)
Refund=
No
Status =
Single
Status =
Divorced
Status =
Married
Yes: 3
No: 4
Yes: 2
No: 1
Yes: 1
No: 0
Yes: 0
No: 3
(a) General-to-specific
...
Income
> 80K
Yes: 3
No: 1
Refund=No,
Status=Single,
Income=90K
(Class=Yes)
Refund=No,
Status = Single
(Class = Yes)
(b) Specific-to-general
Rule Growing (Examples)
•
•
CN2 Algorithm:
– Start from an empty conjunct: {}
– Add conjuncts that minimizes the entropy measure: {A}, {A,B}, …
– Determine the rule consequent by taking majority class of instances covered
by the rule
RIPPER Algorithm:
– Start from an empty rule: {} => class
– Add conjuncts that maximizes FOIL’s information gain measure:
• R0: {} => class (initial rule)
• R1: {A} => class (rule after adding conjunct)
• Gain(R0, R1) = t [ log (p1/(p1+n1)) – log (p0/(p0 + n0)) ]
• where t: number of positive instances covered by both R0 and R1
p0: number of positive instances covered by R0
n0: number of negative instances covered by R0
p1: number of positive instances covered by R1
n1: number of negative instances covered by R1
Rule Evaluation
• Metrics:
– Accuracy
– Laplace
– M-estimate
nc

n
nc  1

nk
nc  kp

nk
n : Number of instances
covered by rule
nc : Number of instances
covered by rule
k : Number of classes
p : Prior probability
Stopping Criterion and Rule Pruning
• Stopping criterion
– Compute the gain
– If gain is not significant, discard the new rule
• Rule Pruning
– Similar to post-pruning of decision trees
– Reduced Error Pruning:
• Remove one of the conjuncts in the rule
• Compare error rate on validation set before and after
pruning
• If error improves, prune the conjunct
Summary of Direct Method
• Grow a single rule
• Remove Instances from rule
• Prune the rule (if necessary)
• Add rule to Current Rule Set
• Repeat
Direct Method: RIPPER
• For 2-class problem, choose one of the classes as positive class, and
the other as negative class
– Learn rules for positive class
– Negative class will be default class
• For multi-class problem
– Order the classes according to increasing class prevalence
(fraction of instances that belong to a particular class)
– Learn the rule set for smallest class first, treat the rest as negative
class
– Repeat with next smallest class as positive class
Direct Method: RIPPER
•
Growing a rule:
– Start from empty rule
– Add conjuncts as long as they improve FOIL’s information gain
– Stop when rule no longer covers negative examples
– Prune the rule immediately using incremental reduced error pruning
– Measure for pruning: v = (p-n)/(p+n)
• p: number of positive examples covered by the rule in
the validation set
• n: number of negative examples covered by the rule in
the validation set
– Pruning method: delete any final sequence of conditions that
maximizes v
Direct Method: RIPPER
• Building a Rule Set:
– Use sequential covering algorithm
• Finds the best rule that covers the current set of positive
examples
• Eliminate both positive and negative examples covered by
the rule
– Each time a rule is added to the rule set, compute the new
description length
• stop adding new rules when the new description length is d
bits longer than the smallest description length obtained so
far
Direct Method: RIPPER
•
Optimize the rule set:
– For each rule r in the rule set R
• Consider 2 alternative rules:
– Replacement rule (r*): grow new rule from scratch
– Revised rule(r’): add conjuncts to extend the rule r
• Compare the rule set for r against the rule set for r*
and r’
• Choose rule set that minimizes MDL principle
– Repeat rule generation and rule optimization for the remaining positive
examples
Indirect Methods
P
No
Yes
Q
No
-
Rule Set
R
Yes
No
Yes
+
+
Q
No
-
Yes
+
r1:
r2:
r3:
r4:
r5:
(P=No,Q=No) ==> (P=No,Q=Yes) ==> +
(P=Yes,R=No) ==> +
(P=Yes,R=Yes,Q=No) ==> (P=Yes,R=Yes,Q=Yes) ==> +
Indirect Method: C4.5rules
• Extract rules from an unpruned decision tree
• For each rule, r: A  y,
– consider an alternative rule r’: A’  y where A’ is obtained by
removing one of the conjuncts in A
– Compare the pessimistic error rate for r against all r’s
– Prune if one of the r’s has lower pessimistic error rate
– Repeat until we can no longer improve generalization error
Indirect Method: C4.5rules
• Instead of ordering the rules, order subsets of rules (class ordering)
– Each subset is a collection of rules with the same rule
consequent (class)
– Compute description length of each subset
• Description length = L(error) + g L(model)
• g is a parameter that takes into account the presence of
redundant attributes in a rule set
(default value = 0.5)
Example
Name
human
python
salmon
whale
frog
komodo
bat
pigeon
cat
leopard shark
turtle
penguin
porcupine
eel
salamander
gila monster
platypus
owl
dolphin
eagle
Give Birth
yes
no
no
yes
no
no
yes
no
yes
yes
no
no
yes
no
no
no
no
no
yes
no
Lay Eggs
no
yes
yes
no
yes
yes
no
yes
no
no
yes
yes
no
yes
yes
yes
yes
yes
no
yes
Can Fly
no
no
no
no
no
no
yes
yes
no
no
no
no
no
no
no
no
no
yes
no
yes
Live in Water Have Legs
no
no
yes
yes
sometimes
no
no
no
no
yes
sometimes
sometimes
no
yes
sometimes
no
no
no
yes
no
yes
no
no
no
yes
yes
yes
yes
yes
no
yes
yes
yes
no
yes
yes
yes
yes
no
yes
Class
mammals
reptiles
fishes
mammals
amphibians
reptiles
mammals
birds
mammals
fishes
reptiles
birds
mammals
fishes
amphibians
reptiles
mammals
birds
mammals
birds
C4.5 versus C4.5rules versus RIPPER
C4.5rules:
Give
Birth?
(Give Birth=No, Can Fly=Yes)  Birds
(Give Birth=No, Live in Water=Yes)  Fishes
No
Yes
(Give Birth=Yes)  Mammals
(Give Birth=No, Can Fly=No, Live in Water=No)  Reptiles
Live In
Water?
Mammals
Yes
( )  Amphibians
RIPPER:
No
(Live in Water=Yes)  Fishes
(Have Legs=No)  Reptiles
Sometimes
Fishes
(Give Birth=No, Can Fly=No, Live In Water=No)
 Reptiles
Can
Fly?
Amphibians
Yes
Birds
(Can Fly=Yes,Give Birth=No)  Birds
No
Reptiles
()  Mammals
C4.5 versus C4.5rules versus RIPPER
C4.5 and C4.5rules:
PREDICTED CLASS
Amphibians Fishes Reptiles Birds
ACTUAL Amphibians
2
0
0
CLASS Fishes
0
2
0
Reptiles
1
0
3
Birds
1
0
0
Mammals
0
0
1
0
0
0
3
0
Mammals
0
1
0
0
6
0
0
0
2
0
Mammals
2
0
1
1
4
RIPPER:
PREDICTED CLASS
Amphibians Fishes Reptiles Birds
ACTUAL Amphibians
0
0
0
CLASS Fishes
0
3
0
Reptiles
0
0
3
Birds
0
0
1
Mammals
0
2
1
Advantages of Rule-Based Classifiers
•
•
•
•
•
As highly expressive as decision trees
Easy to interpret
Easy to generate
Can classify new instances rapidly
Performance comparable to decision trees
Classification by Backpropagation
• Backpropagation: A neural network learning algorithm
• Started by psychologists and neurobiologists to develop and test
computational analogues of neurons
• A neural network: A set of connected input/output units where each
connection has a weight associated with it
• 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
April 7, 2016
Data Mining: Concepts and Techniques
40
Classification by Backpropagation
• Backpropagation: A neural network learning algorithm
• Started by psychologists and neurobiologists to develop and test
computational analogues of neurons
• A neural network: A set of connected input/output units where each
connection has a weight associated with it
• 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
April 7, 2016
Data Mining: Concepts and Techniques
41
Neural Network as a Classifier
•
•
Weakness
– Long training time
– Require a number of parameters typically best determined empirically,
e.g., the network topology or “structure.”
– Poor interpretability: Difficult to interpret the symbolic meaning behind the
learned weights and of “hidden units” in the network
Strength
– High tolerance to noisy data
– Ability to classify untrained patterns
– Well-suited for continuous-valued inputs and outputs
– Successful on a wide array of real-world data
– Algorithms are inherently parallel
– Techniques have recently been developed for the extraction of rules from
trained neural networks
April 7, 2016
Data Mining: Concepts and Techniques
42
A Neuron (= a perceptron)
- mk
x0
w0
x1
w1
xn

f
output y
For Example
wn
n
y  sign(  wi xi  m k )
i 0
Input
weight
vector x vector w
•
weighted
sum
Activation
function
The n-dimensional input vector x is mapped into variable y by means of
the scalar product and a nonlinear function mapping
April 7, 2016
Data Mining: Concepts and Techniques
43
A Multi-Layer Feed-Forward Neural Network
Output vector
w(jk 1)  w(jk )   ( yi  yˆi( k ) ) xij
Output layer
Hidden layer
wij
Input layer
Input vector: X
April 7, 2016
Data Mining: Concepts and Techniques
44
How A Multi-Layer Neural Network Works?
•
The inputs to the network correspond to the attributes measured for each
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, although usually only one
•
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 in that none of the weights cycles back to an
input unit or to an output unit of a previous layer
•
From a statistical point of view, networks perform nonlinear regression:
Given enough hidden units and enough training samples, they can closely
approximate any function
April 7, 2016
Data Mining: Concepts and Techniques
45
Defining a Network Topology
• First decide the network topology: # of units in the input layer, # of
hidden layers (if > 1), # of units in each hidden layer, and # of units in
the output layer
• Normalizing the input values for each attribute measured in the training
tuples to [0.0—1.0]
• One input unit per domain value, each initialized to 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
April 7, 2016
Data Mining: Concepts and Techniques
46
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”
•
Steps
– Initialize weights (to small random #s) and biases in the network
– Propagate the inputs forward (by applying activation function)
– Backpropagate the error (by updating weights and biases)
– Terminating condition (when error is very small, etc.)
April 7, 2016
Data Mining: Concepts and Techniques
47
Lazy vs. Eager Learning
•
•
•
Lazy vs. eager learning
– Lazy 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 (the above discussed methods): Given a set of training set,
constructs a classification model before receiving new (e.g., test) data to
classify
Lazy: less time in training but more time in predicting
Accuracy
– Lazy method effectively uses a richer hypothesis space since it uses many
local linear functions to form its implicit global approximation to the target
function
– Eager: must commit to a single hypothesis that covers the entire instance
space
April 7, 2016
Data Mining: Concepts and Techniques
48
Lazy Learner: Instance-Based Methods
•
•
Instance-based learning:
– Store training examples and delay the processing (“lazy
evaluation”) until a new instance must be classified
Typical approaches
– k-nearest neighbor approach
• Instances represented as points in a Euclidean space.
– Locally weighted regression
• Constructs local approximation
– Case-based reasoning
• Uses symbolic representations and knowledge-based
inference
April 7, 2016
Data Mining: Concepts and Techniques
49
Nearest Neighbor Classifiers
• Basic idea:
– If it walks like a duck, quacks like a duck, then it’s probably a
duck
Compute
Distance
Training
Records
Choose k of the
“nearest” records
Test
Record
Nearest-Neighbor Classifiers
Unknown record

Requires three things
– The set of stored records
– Distance Metric to compute
distance between records
– The value of k, the number of
nearest neighbors to retrieve

To classify an unknown record:
– Compute distance to other
training records
– Identify k nearest neighbors
– Use class labels of nearest
neighbors to determine the
class label of unknown record
(e.g., by taking majority vote)
Definition of Nearest Neighbor
X
(a) 1-nearest neighbor
X
X
(b) 2-nearest neighbor
(c) 3-nearest neighbor
K-nearest neighbors of a record x are data points
that have the k smallest distance to x
The k-Nearest Neighbor Algorithm
• All instances correspond to points in the n-D space
• The nearest neighbor are defined in terms of Euclidean distance,
dist(X1, X2)
• Target function could be discrete- or real- valued
• For discrete-valued, k-NN returns the most common value among
the k training examples nearest to xq
• Vonoroi diagram: the decision surface induced by 1-NN for a
typical set of training examples
.
_
_
+
_
_
April 7, 2016
_
. +
xq
+
_
+
.
.
.
Data Mining: Concepts and Techniques
.
53
Nearest Neighbor Classification
• Compute distance between two points:
– Euclidean distance
d ( p, q ) 
 ( pi
i
q )
2
i
• Determine the class from nearest neighbor list
– take the majority vote of class labels among the k-nearest
neighbors
– Weigh the vote according to distance
• weight factor, w = 1/d2
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
X
Nearest Neighbor Classification…
•
Scaling issues
– Attributes may have to be scaled to prevent distance measures from
being dominated by one of the attributes
– Example:
• height of a person may vary from 1.5m to 1.8m
• weight of a person may vary from 90lb to 300lb
• income of a person may vary from $10K to $1M
Nearest neighbor Classification…
• k-NN classifiers are lazy learners
– It does not build models explicitly
– Unlike eager learners such as decision tree induction and rulebased systems
– Classifying unknown records are relatively expensive
Example: PEBLS
• PEBLS: Parallel Examplar-Based Learning System (Cost &
Salzberg)
– Works with both continuous and nominal features
• For nominal features, distance between two nominal values
is computed using modified value difference metric (MVDM)
– Each record is assigned a weight factor
– Number of nearest neighbor, k = 1
Example: PEBLS
Tid Refund Marital
Status
Taxable
Income Cheat
1
Yes
Single
125K
No
d(Single,Married)
2
No
Married
100K
No
= | 2/4 – 0/4 | + | 2/4 – 4/4 | = 1
3
No
Single
70K
No
d(Single,Divorced)
4
Yes
Married
120K
No
5
No
Divorced 95K
Yes
6
No
Married
No
d(Married,Divorced)
7
Yes
Divorced 220K
No
= | 0/4 – 1/2 | + | 4/4 – 1/2 | = 1
8
No
Single
85K
Yes
d(Refund=Yes,Refund=No)
9
No
Married
75K
No
= | 0/3 – 3/7 | + | 3/3 – 4/7 | = 6/7
10
No
Single
90K
Yes
60K
Distance between nominal attribute values:
= | 2/4 – 1/2 | + | 2/4 – 1/2 | = 0
10
Marital Status
Class
Single
Married
Class
Yes
No
Yes
0
3
No
3
4
Divorced
Yes
2
0
1
No
2
4
1
Refund
d (V1 ,V2 )  
i
n1i n2i

n1 n2
Example: PEBLS
Tid
Refund
Marital
Status
Taxable
Income
Cheat
X
Yes
Single
125K
No
Y
No
Married
100K
No
10
Distance between record X and record Y:
d
( X , Y )  wX wY  d ( X i , Yi ) 2
i 1
where:
Number of times X is used for prediction
wX 
Number of times X predicts correctly
wX  1 if X makes accurate prediction most of the time
wX > 1 if X is not reliable for making predictions
Dilanjutkan ke pert. 10
Classification and Prediction (cont.)
Bina Nusantara