Machine Learning: k-Nearest Neighbor, Naïve Bayes, Boostingk-Nearest Neighbor Instance-Based Learning1-Nearest NeighborSlide 4Distance MetricsFour Aspects of an Instance-Based Learner:1-NN’s Four Aspects as an Instance-Based Learner:Zen Gardensk – Nearest Neighbork-Nearest Neighbor (k = 9)The Naïve Bayes ClassifierSlide 12Deriving Naïve BayesSlide 14Slide 15Slide 16The Naïve Bayes AlgorithmNaïve Bayes ApplicationsBoostingBackground: AdaBoostSlide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Computing Beta1Machine Machine Learning:Learning:k-Nearest Neighbor, Naïve k-Nearest Neighbor, Naïve Bayes, BoostingBayes, Boosting18.4, Skim 20.4 18.4, Skim 20.4 Note: These slides require the TeXPPT Note: These slides require the TeXPPT package package ((http://users.ecs.soton.ac.uk/srg/softwaretools/presentationhttp://users.ecs.soton.ac.uk/srg/softwaretools/presentation/TeX4PPT//TeX4PPT/))CS 632kk-Nearest Neighbor -Nearest Neighbor Instance-Based Instance-Based LearningLearningSome material adapted from slides by Andrew Some material adapted from slides by Andrew Moore, CMU.Moore, CMU.Visit Visit http://www.autonlab.org/tutorials/http://www.autonlab.org/tutorials/ for forAndrew’s repository of Data Mining tutorials.Andrew’s repository of Data Mining tutorials.31-Nearest Neighbor1-Nearest NeighborOne of the simplest of all machine One of the simplest of all machine learning classifierslearning classifiersSimple idea: label a new point the Simple idea: label a new point the same as the closest known pointsame as the closest known pointLabel it red.41-Nearest Neighbor1-Nearest NeighborA type of instance-based learningA type of instance-based learningAlso known as “memory-based” Also known as “memory-based” learninglearningForms a Voronoi tessellation of the Forms a Voronoi tessellation of the instance spaceinstance space5Distance MetricsDistance MetricsDifferent metrics can change the decision surfaceDifferent metrics can change the decision surfaceStandard Euclidean distance metric:Standard Euclidean distance metric:Two-dimensional: Dist(a,b) = sqrt((aTwo-dimensional: Dist(a,b) = sqrt((a11 – b – b11))2 2 + (a+ (a22 – b – b22))22))Multivariate: Dist(a,b) = sqrt(∑ (aMultivariate: Dist(a,b) = sqrt(∑ (aii – b – bii))22))Dist(a,b) =(a1 – b1)2 + (a2 – b2)2Dist(a,b) =(a1 – b1)2 + (3a2 – 3b2)2Adapted from “Instance-Based Learning” lecture slides by Andrew Moore, CMU.6Four Aspects of anFour Aspects of anInstance-Based Learner:Instance-Based Learner:1. A distance metric2. How many nearby neighbors to look at?3. A weighting function (optional)4. How to fit with the local points?Adapted from “Instance-Based Learning” lecture slides by Andrew Moore, CMU.71-NN’s Four Aspects as an1-NN’s Four Aspects as anInstance-Based Learner:Instance-Based Learner:1. A distance metricEuclidian2. How many nearby neighbors to look at?One3. A weighting function (optional)Unused4. How to fit with the local points?Just predict the same output as the nearest neighbor.Adapted from “Instance-Based Learning” lecture slides by Andrew Moore, CMU.8Zen GardensZen GardensMystery of renowned zen garden revealed [CNN Article]Thursday, September 26, 2002 Posted: 10:11 AM EDT (1411 GMT)LONDON (Reuters) -- For centuries visitors to the renowned Ryoanji Temple garden in Kyoto, Japan have been entranced and mystified by the simple arrangement of rocks.The five sparse clusters on a rectangle of raked gravel are said to be pleasing to the eyes of the hundreds of thousands of tourists who visit the garden each year.Scientists in Japan said on Wednesday they now believe they have discovered its mysterious appeal."We have uncovered the implicit structure of the Ryoanji garden's visual ground and have shown that it includes an abstract, minimalist depiction of natural scenery," said Gert Van Tonder of Kyoto University.The researchers discovered that the empty space of the garden evokes a hidden image of a branching tree that is sensed by the unconscious mind."We believe that the unconscious perception of this pattern contributes to the enigmatic appeal of the garden," Van Tonder added.He and his colleagues believe that whoever created the garden during the Muromachi era between 1333-1573 knew exactly what they were doing and placed the rocks around the tree image.By using a concept called medial-axis transformation, the scientists showed that the hidden branched tree converges on the main area from which the garden is viewed.The trunk leads to the prime viewing site in the ancient temple that once overlooked the garden. It is thought that abstract art may have a similar impact."There is a growing realisation that scientific analysis can reveal unexpected structural features hidden in controversial abstract paintings," Van Tonder saidAdapted from “Instance-Based Learning” lecture slides by Andrew Moore, CMU.9k – Nearest Neighbork – Nearest NeighborGeneralizes 1-NN to smooth away Generalizes 1-NN to smooth away noise in the labelsnoise in the labelsA new point is now assigned the A new point is now assigned the most frequent label of its most frequent label of its kk nearest nearest neighborsneighborsLabel it red, when k = 3Label it blue, when k = 710k-Nearest Neighbor (k = k-Nearest Neighbor (k = 9)9)A magnificent job of noise smoothing. Three cheers for 9-nearest-neighbor.But the lack of gradients and the jerkiness isn’t good.Appalling behavior! Loses all the detail that 1-nearest neighbor would give. The tails are horrible!Fits much less of the noise, captures trends. But still, frankly, pathetic comparedwith linear regression.Adapted from “Instance-Based Learning” lecture slides by Andrew Moore, CMU.11TheTheNaïve BayesNaïve BayesClassifierClassifierSome material adapted from slides Some material adapted from slides bybyTom Mitchell, CMU.Tom Mitchell, CMU.12The Naïve Bayes The Naïve Bayes ClassifierClassifier)()|()()|(jijijiXPYXPYPXYP Recall Bayes rule:Recall Bayes rule:Which is short for:Which is short for:We can re-write this as:We can re-write this as:)()|()()|(jijijixXPyYxXPyYPxXyYPkkkjijijiyYPyYxXPyYxXPyYPxXyYP)()|()|()()|(13Deriving Naïve BayesDeriving Naïve BayesIdea: use the training data to directly Idea: use the training data to directly estimate:estimate:Then, we can use these values to estimateThen, we can use these