data science training in mumbai
                     Machine Learning
k-Nearest Neighbor 
Classifiers
1-Nearest Neighbor Classifier
Training Examples (Instances) Test Examples
Some for each CLASS (What class to assign this?)
1-Nearest Neighbor
x
http://www.math.le.ac.uk/people/ag153/homepage/KNN/OliverKNN_Talk.pdf
2-Nearest Neighbor
?
3-Nearest Neighbor
X
8-Nearest Neighbor
X
Controlling COMPLEXITY in k-NN
Ingredient Sweetness Crunchiness Food type
apple 10 9 fruit
Bacon 1 4 protein
banana 10 1 fruit
carrot 7 10 vegetable
celery 3 10 vegetable
cheese 1 1 protein



Measuring similarity with 
distance
Locating the tomato's nearest neighbors requires a distance 
function, or a formula that measures the similarity between the two 
instances.
There are many different ways to calculate distance. Traditionally, the 
k-NN
algorithm uses Euclidean distance, which is the distance one would 
measure if it were possible to use a ruler to connect two points, 
illustrated in the previous
figure by the dotted lines connecting the tomato to its neighbors.
Euclidean distance
Euclidean distance is specified by the following formula, where p and q 
are the
examples to be compared, each having n features. The term p1 refers to 
the value
of the first feature of example p, while q1 refers to the value of the first 
feature of
example q:
Application of KNN
Which Class Tomoto belongs to given the feature values:
Tomato (sweetness = 6, crunchiness = 4), 
K = 3, 5, 7, 9
K = 11,13,15,17
Bayesian Classifiers
Understanding probability 
The probability of an event is estimated from the observed data 
by dividing the number of trials in which the event occurred by 
the total number of trials
 For instance, if it rained 3 out of 10 days with similar 
conditions as today, the probability of rain today can be 
estimated as 3 / 10 = 0.30 or 30 percent. 
Similarly, if 10 out of 50 prior email messages were spam, 
then the probability of any incoming message being spam can 
be estimated as 10 / 50 = 0.20 or 20 percent.
For example, given the value P(spam) = 0.20, we can calculate 
P(ham) = 1 – 0.20 = 0.80
Note: The probability of all the possible outcomes of a trial must always sum to 1 
Understanding probability cont.. 
For example, given the value P(spam) = 0.20, we can calculate 
P(ham) = 1 – 0.20 = 0.80
Because an event cannot simultaneously happen and not happen, an 
event is always mutually exclusive and exhaustive with its 
complement
The complement of event A is typically denoted Ac or A'. 
Additionally, the shorthand notation P(¬A) can used to denote the 
probability of event A not occurring, as in P(¬spam) = 0.80. This 
notation is equivalent to P(Ac).
Understanding joint probability 
Often, we are interested in monitoring several nonmutually exclusive 
events for the same trial
All 
emails
Lotter
y 5%
Spam Ham
20% 80%
Understanding joint probability 
Lottery appearing in 
Spam
Lottery 
appearin
g in Ham
Lottery 
without 
appearin
g in 
Spam
Estimate the probability that both P(spam) and P(Spam) occur, which can be written as P(spam 
∩ Lottery). the notation A ∩ B refers to the event in which both A and B occur. 
Calculating P(spam ∩ Lottery) depends on the joint probability of the two 
events or how the probability of one event is related to the probability of 
the other.
 If the two events are totally unrelated, they are called 
independent events
 If P(spam) and P(Lottery) were independent, we could easily 
calculate P(spam ∩ Lottery), the probability of both events 
happening at the same time. 
Because 20 percent of all the messages are spam, and 5 percent of 
all the e-mails contain the word Lottery, we could assume that 1 
percent of all messages are spam with the term Lottery.
 More generally, for independent events A and B, the probability of 
both happening can be expressed as P(A ∩ B) = P(A) * P(B). 
0.05 * 0.20 = 0.01
Bayes Rule
 Bayes Rule: The most important Equation in ML!!
Class Prior Data Likelihood given Class
P ( Class) P ( DataClass)
P ( Class Data) =
P ( Data)
Data Prior (Marginal)
Posterior Probability
(Probability of class AFTER seeing the data)
Naïve Bayes Classifier
Conditional Independence
P ( Fever,  BodyAcheViral ) =P ( Fever Viral ) P ( BodyAcheViral )
Viral 
Infection
Body 
Fever
Ache
P ( Fever,  BodyAche) ¹P ( Fever) P ( BodyAche)
 Simple Independence between two variables:
P ( X1, X2 ) =P ( X1 ) P ( X2 )
 Class Conditional Independence assumption:
P ( X1, X2 ) ¹P ( X1 ) P ( X2 )
P ( X1, X2 C ) =P ( X1 C ) P ( X2 C )
Naïve Bayes Classifier 
Conditional Independence among variables given 
Classes!
D
P ( C) P ( X , X P C P X C,..., X C ) ( )Õ ( d )
P ( C X , X ,..., X ) 1 2 D= = d=11 2 D P ( X , X ,..., X C ') Då 1 2 D åÕP ( Xd C¢C )¢
C¢ d=1
 Simplifying assumption
 Baseline model especially when large number of features
 Taking log and ignoring denominator: D
log ( P ( C X1, X2 ,..., XD ) ) µ log ( P ( C) ) +å log ( P ( Xd C) )
d=1
Naïve Bayes Classifier for
Categorical Valued Variables
Let’s Naïve Bayes!
D
log ( P ( C X1, X2 ,..., XD ) ) µ log ( P ( C) ) +å log ( P ( Xd C ) )
d=1
Class Prior Parameters:
#EXMP
P ( Like =Y) =??? LS COLOR SHAPE
LIK
E
P ( Like =N) =??? 20 Red Square Y
10 Red Circle Y
Class Conditional Likelihoods 10 Red Triangle N
10 Green Square N
P ( Color =Red Like =Y) =????
5 Green Circle Y
P ( Color =Red Like =N ) =???? 5 Green Triangle N
... 10 Blue Square N
P ( Shape =Triangle Like =N ) =???? 10 Blue Circle N
20 Blue Triangle Y
Naïve Bayes Classifier for
Text Classifier
Text Classification Example
 Doc1 = {buy two shirts get one shirt half off}
 Doc2 = {get a free watch. send your contact details now}
 Doc3 = {your flight to chennai is delayed by two hours}
 Doc4 = {you have three tweets from @sachin}
Four Class Problem:
P ( promodoc1) =0.84
 Spam,  
P spamdoc2 =0.94
 Promotions, ( )
 P ( maindoc3) =0.75Social, 
 Main P ( social doc4 ) =0.91
Bag-of-Words Representation
 Structured (e.g. Multivariate) data – fixed number of 
features
 Unstructured (e.g. Text) data
 arbitrary length documents, 
 high dimensional feature space (many words in 
vocabulary),
 Sparse (small fraction of vocabulary words present in a doc.)
 Bag-of-Words Representation:
 Ignore Sequential order of words
• RRaewpDreosce n=t a{sb au yW tewigoh tsehdi-rStes tg –e Tte ornme  Fsrheiqrtu heanlcfy o offf} each term
• Stemming = {buy two shirt get one shirt half off}
• BoW’s = {buy:1, two:1, shirt:2, get:1, one:1, half:1, 
off:1}
Naïve Bayes Classifier with BoW
BoW = {buty:1, two:1, shirt:2, get:1, one:1, half:1, 
off:1}
 Make an “independence assumption” about words | 
class
P ( doc1 promo)
=P ( buy:1,  two:1,  shirt :2,  get :1,  one:1,  half :1,  off :1 promo)
=P ( buy:1 promo) P ( two:1 promo) P ( shirt : 2 promo)
   P ( get :1 promo) P ( one:1 promo) P ( free:1 promo)
1 1 2
=P ( buy promo) P ( two promo) P ( shirt promo)
1 1 1
   P ( get promo) P ( one promo) P ( free promo)
Naïve Bayes Text Classifiers
 Log Likelihood of document given class.
M
doc={ tf ( wm) } m=1
tf ( wm) =Number of times word wm occurs in doc
tf ( w ) tf ( w ) tf ( w )
P ( doc class) =P ( w1 class)
1 P ( w2 class)
2 ...P ( wM class)
M
 Parameters in Naïve Bayes Text classifiers:
P ( wm c) =Probability that word wm occurs in documents of class c
P ( shirt promo) ,P ( freespam) ,P ( buyspam) ,P ( buy promo) ,...
Number of parameters = ??
Naïve Bayes Parameters
 Likelihood of a word given class. For each word, each class.
P ( wm c) =Probability that word wm occurs in documents of class c
 Estimating these parameters from data:
N ( wm,c) =Number of times word wm occurs in documents of class c
doc1
doc
N ( free,spam) tf ( freedoc) 2= å ...
docÎspam docm
doc1
doc2
N ( free, promo) = å tf ( freedoc) doc3
docÎpromo ...
...
docn
Bayesian Classifier
Multi-variate real-valued 
data
Bayes Rule
Class Prior Data Likelihood given Class
P ( Class) P ( DataClass)
P ( Class Data) =
P ( Data)
Data Prior (Marginal)
Posterior Probability
(Probability of class AFTER seeing the data)
P ( c) P ( xc)
P ( cx) = xÎRD
P ( x)
Simple Bayesian Classifier
Each Class Conditional 
P ( c) P ( xc) Probability is assumed to be a 
P ( cx) = Uni-Modal (Single Cloud) 
P ( x) (NORMAL) Distribution
1 1 T
P ( xc) =N ( xm æ - 1 öc,Sc ) = D 1 expç - ( x- m ) S ( x- m )è
( 2 ) 2 2
c c c ø÷
p 2 Sc
Sum: ò P ( xc) dx=1
xÎRD
Mean: òxP ( xc) dx=mc
xÎRD
T
Co-Variance: ò ( x- mc ) ( x- mc ) P ( xc) dx=Sc
xÎRD
Controlling COMPLEXITY