Data MiningClassification: Alternative TechniguesLecture Notes for Chapter 5byTan, Steinbach, Kumar
Data Mining Classification: Alternative Techniques Lecture Notes for Chapter 5 by Tan, Steinbach, Kumar
Instance-Based ClassifiersSet of Stored Cases·Store thetraining records·Use training records toAtrlAtrNClasspredict the class label ofAunseencasesBBUnseen CasecAtrlAtrNAcB
Instance-Based Classifiers Atr1 . AtrN Class A B B C A C B Set of Stored Cases Atr1 . AtrN Unseen Case • Store the training records • Use training records to predict the class label of unseen cases
Instance Based ClassifiersExamples:-Rote-learnerMemorizes entire training data and performsclassification only if attributes of record match one ofthe training examples exactlyNearest neighborUses k“closest"points (nearest neighbors)forperforming classification
Instance Based Classifiers Examples: – Rote-learner ◆ Memorizes entire training data and performs classification only if attributes of record match one of the training examples exactly – Nearest neighbor ◆ Uses k “closest” points (nearest neighbors) for performing classification
Nearest Neighbor ClassifiersBasic idea:- If it walks like a duck, quacks like a duck, thenit's probably a duckComputeTestDistanceRecordTrainingChoosekoftheRecords"nearest"records
Nearest Neighbor Classifiers Basic idea: – If it walks like a duck, quacks like a duck, then it’s probably a duck Training Records Test Record Compute Distance Choose k of the “nearest” records
Nearest-Neighbor ClassifiersUnknownrecordRequires three thingsThesetofstoredrecordsDistanceMetricto computedistancebetweenrecordsThevalue of k.thenumberofnearestneighborstoretrieveToclassifyan unknownrecord:Computedistancetoothertraining recordsIdentifyk nearest neighborsUseclasslabelsofnearestneighborstodeterminetheclasslabelofunknownrecord(e.g., by taking majority vote)
Nearest-Neighbor Classifiers 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) Unknown record