Undergraduate Topics in Computer Science UndergraduateTopicsinComputerScience(UTiCS)delivershigh-qualityinstructionalcontentforunder- graduatesstudyinginallareasofcomputingandinformationscience.Fromcorefoundationalandtheoretical material to final-year topics and applications, UTiCS books take a fresh, concise, and modern approach andareidealforself-studyorforaone-ortwo-semestercourse.Thetextsareallauthoredbyestablished experts in their fields, reviewed by an international advisory board, and contain numerous examples and problems.Manyincludefullyworkedsolutions. Serieseditor IanMackie Advisoryboard SamsonAbramsky,UniversityofOxford,Oxford,UK KarinBreitman,PontificalCatholicUniversityofRiodeJaneiro,RiodeJaneiro,Brazil ChrisHankin,ImperialCollegeLondon,London,UK DexterKozen,CornellUniversity,Ithaca,USA AndrewPitts,UniversityofCambridge,Cambridge,UK HanneRiisNielson,TechnicalUniversityofDenmark,KongensLyngby,Denmark StevenSkiena,StonyBrookUniversity,StonyBrook,USA IainStewart,UniversityofDurham,Durham,UK For further volumes: http://www.springer.com/series/7592 · M. Narasimha Murty V. Susheela Devi Pattern Recognition An Algorithmic Approach 123 Prof.M.NarasimhaMurty Dr.V.SusheelaDevi IndianInstituteofScience IndianInstituteofScience Dept.ofComputerScience Dept.ofComputerScience andAutomation andAutomation Bangalore Bangalore India India [email protected] [email protected] Aco-publicationwiththeUniversitiesPress(India)Pvt.Ltd,licensedforsaleinallcountriesoutsideofIndia,Pakistan, Bhutan,Bangladesh,SriLanka,Nepal,TheMaldives,MiddleEast,Malaysia,IndonesiaandSingapore.Soldanddistributed withintheseterritoriesbytheUniversitiesPress(India)PrivateLtd. ISSN1863-7310 ISBN978-0-85729-494-4 e-ISBN978-0-85729-495-1 DOI10.1007/978-0-85729-495-1 SpringerLondonDordrechtHeidelbergNewYork BritishLibraryCataloguinginPublicationData AcataloguerecordforthisbookisavailablefromtheBritishLibrary LibraryofCongressControlNumber:2011922756 (cid:2)c UniversitiesPress(India)Pvt.Ltd. Apartfromanyfairdealingforthepurposesofresearchorprivatestudy,orcriticismorreview,aspermittedunderthe Copyright,DesignsandPatentsAct1988,thispublicationmayonlybereproduced,storedortransmitted,inanyformorby anymeans,withthepriorpermissioninwritingofthepublishers,orinthecaseofreprographicreproductioninaccordance withthetermsoflicensesissuedbytheCopyrightLicensingAgency.Enquiriesconcerningreproductionoutsidethoseterms shouldbesenttothepublishers. Theuseofregisterednames,trademarks,etc.,inthispublicationdoesnotimply,evenintheabsenceofaspecificstatement, thatsuchnamesareexemptfromtherelevantlawsandregulationsandthereforefreeforgeneraluse. Thepublishermakesnorepresentation,expressorimplied,withregardtotheaccuracyoftheinformationcontainedinthis bookandcannotacceptanylegalresponsibilityorliabilityforanyerrorsoromissionsthatmaybemade. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Contents Preface xi 1. Introduction 1 1.1 What isPattern Recognition? 2 1.2 Data SetsforPattern Recognition 4 1.3 DifferentParadigmsforPattern Recognition 4 Discussion 5 Further Reading 5 Exercises 6 Bibliography 6 2. Representation 7 2.1 Data Structures forPattern Representation 8 2.1.1 Patterns asVectors 8 2.1.2 Patterns asStrings 9 2.1.3 Logical Descriptions 9 2.1.4 Fuzzy and RoughPattern Sets 10 2.1.5 Patterns asTreesand Graphs 10 2.2 Representation ofClusters 15 2.3 ProximityMeasures 16 2.3.1 Distance Measure 16 2.3.2 Weighted Distance Measure 17 2.3.3 Non-Metric Similarity Function 18 2.3.4 Edit Distance 19 2.3.5 Mutual NeighbourhoodDistance(MND) 20 2.3.6 Conceptual Cohesiveness 22 2.3.7 Kernel Functions 22 2.4 Size ofPatterns 23 2.4.1 NormalisationofData 23 2.4.2 UseofAppropriateSimilarityMeasures 24 2.5 Abstractionsofthe DataSet 24 2.6 Feature Extraction 26 vi Pattern Recognition 2.6.1 Fisher’sLinear Discriminant 26 2.6.2 PrincipalComponent Analysis (PCA) 29 2.7 Feature Selection 31 2.7.1 Exhaustive Search 32 2.7.2 Branch and Bound Search 33 2.7.3 Selection ofBest Individual Features 36 2.7.4 Sequential Selection 36 2.7.5 Sequential Floating Search 37 2.7.6 Max–MinApproachto Feature Selection 39 2.7.7 StochasticSearchTechniques 41 2.7.8 Artificial Neural Networks 41 2.8 Evaluation ofClassifiers 41 2.9 Evaluation ofClustering 43 Discussion 43 Further Reading 44 Exercises 44 Computer Exercises 46 Bibliography 46 3. Nearest Neighbour BasedClassifiers 48 3.1 Nearest NeighbourAlgorithm 48 3.2 Variants oftheNN Algorithm 50 3.2.1 k-Nearest Neighbour(kNN) Algorithm 50 3.2.2 Modifiedk-Nearest Neighbour(MkNN) Algorithm 51 3.2.3 Fuzzy kNN Algorithm 53 3.2.4 r NearNeighbours 54 3.3 Use ofthe Nearest NeighbourAlgorithmforTransactionDatabases 54 3.4 Efficient Algorithms 55 3.4.1 TheBranch and Bound Algorithm 56 3.4.2 TheCube Algorithm 58 3.4.3 Searchingforthe Nearest NeighbourbyProjection 60 3.4.4 Ordered Partitions 62 3.4.5 Incremental Nearest NeighbourSearch 64 3.5 Data Reduction 65 3.6 PrototypeSelection 66 3.6.1 Minimal Distance Classifier(MDC) 61 3.6.2 Condensation Algorithms 69 3.6.3 Editing Algorithms 75 3.6.4 Clustering Methods 77 3.6.5 Other Methods 79 Contents vii Discussion 79 Further Reading 79 Exercises 80 Computer Exercises 82 Bibliography 83 4. BayesClassifier 86 4.1 Bayes Theorem 86 4.2 Minimum ErrorRate Classifier 88 4.3 Estimation ofProbabilities 90 4.4 Comparisonwiththe NNC 91 4.5 Naive Bayes Classifier 93 4.5.1 Classificationusing Naive BayesClassifier 93 4.5.2 TheNaiveBayes ProbabilisticModel 93 4.5.3 ParameterEstimation 95 4.5.4 Constructing aClassifierfromthe ProbabilityModel 96 4.6 Bayesian Belief Network 97 Discussion 100 Further Reading 100 Exercises 100 Computer Exercises 101 Bibliography 102 5. Hidden MarkovModels 103 5.1 MarkovModelsforClassification 104 5.2 Hidden MarkovModels 111 5.2.1 HMMParameters 113 5.2.2 Learning HMMs 113 5.3 Classification UsingHMMs 116 5.3.1 ClassificationofTest Patterns 116 Discussion 118 Further Reading 119 Exercises 119 Computer Exercises 121 Bibliography 122 6. DecisionTrees 123 6.1 Introduction 123 6.2 Decision TreesforPattern Classification 125 6.3 Construction ofDecisionTrees 131 viii Pattern Recognition 6.3.1 MeasuresofImpurity 132 6.3.2 Which Attribute to Choose? 133 6.4 Splitting atthe Nodes 136 6.4.1 When toStopSplitting 138 6.5 Overfitting and Pruning 139 6.5.1 Pruning by Finding IrrelevantAttributes 139 6.5.2 UseofCross-Validation 140 6.6 Example ofDecisionTreeInduction 140 Discussion 143 Further Reading 143 Exercises 144 Computer Exercises 145 Bibliography 145 7. Support Vector Machines 147 7.1 Introduction 147 7.1.1 Linear Discriminant Functions 147 7.2 Learning theLinear Discriminant Function 154 7.2.1 Learning the Weight Vector 154 7.2.2 Multi-class Problems 156 7.2.3 Generality ofLinear Discriminants 166 7.3 Neural Networks 169 7.3.1 Artificial Neuron 169 7.3.2 Feed-forwardNetwork 171 7.3.3 Multilayer Perceptron 173 7.4 SVM forClassification 175 7.4.1 Linearly SeparableCase 177 7.4.2 Non-linearly SeparableCase 181 Discussion 183 Further Reading 183 Exercises 183 Computer Exercises 186 Bibliography 187 8. Combinationof Classifiers 188 8.1 Introduction 188 8.2 MethodsforConstructing EnsemblesofClassifiers 190 8.2.1 Sub-samplingthe TrainingExamples 190 8.2.2 Manipulating the Input Features 196 Contents ix 8.2.3 Manipulating the Output Targets 196 8.2.4 Injecting Randomness 197 8.3 MethodsforCombiningClassifiers 199 Discussion 202 Further Reading 203 Exercises 203 Computer Exercises 204 Bibliography 205 9. Clustering 207 9.1 Why is Clustering Important? 216 9.2 Hierarchical Algorithms 221 9.2.1 DivisiveClustering 222 9.2.2 AgglomerativeClustering 225 9.3 Partitional Clustering 229 9.3.1 k-MeansAlgorithm 229 9.3.2 SoftPartitioning 232 9.4 Clustering Large DataSets 233 9.4.1 PossibleSolutions 234 9.4.2 Incremental Clustering 235 9.4.3 Divide-and-Conquer Approach 236 Discussion 239 Further Reading 240 Exercises 240 Computer Exercises 242 Bibliography 243 10. Summary 245 11. An Application: HandwrittenDigit Recognition 247 11.1 Descriptionofthe DigitData 247 11.2 Pre-processingofData 249 11.3 Classification Algorithms 249 11.4 Selection ofRepresentative Patterns 249 11.5 Results 250 Discussion 254 Further Reading 254 Bibliography 254 Index 255