Introduction to Pattern Recognition and Machine Learning

1 126/2/15 12:15 pmIISc Lecture Notes Series ISSN: 2010-2402 Editor-in-Chief: Gadadhar MisraEditors: Chandrashekar S Jog Joy Kuri K L Sebastian Diptiman Sen Sandhya Visweswariah Published:Vol. 1: Introduction to Algebraic Geometry and Commutative Algebra by Dilip P Patil & Uwe StorchVol. 2: Schwarz s Lemma from a Differential Geometric Veiwpoint by Kang-Tae Kim & Hanjin LeeVol. 3: Noise and Vibration Control by M L MunjalVol. 4: Game Theory and Mechanism Design by Y NarahariVol. 5 Introduction to Pattern Recognition and Machine Learning by M.

2 Narasimha Murty & V. Susheela Devi Dipa - Introduction to Pattern 110/4/2015 1:29:09 PMWorld 226/2/15 12:15 pmPublished byWorld Scientific Publishing Co. Pte. Toh Tuck Link, Singapore 596224 USA office: 27 Warren Street, Suite 401-402, Hackensack, NJ 07601UK office: 57 Shelton Street, Covent Garden, London WC2H 9 HELibrary of Congress Cataloging-in-Publication DataMurty, M. Narasimha. Introduction to Pattern Recognition and Machine Learning / by M Narasimha Murty & V Susheela Devi (Indian Institute of Science, India). pages cm. -- (IISc lecture notes series, 2010 2402 ; vol.)

3 5) ISBN 978-9814335454 1. Pattern Recognition systems. 2. Machine Learning . I. Devi, V. Susheela. II. Title. 2015 2014044796 British Library Cataloguing-in-Publication DataA catalogue record for this book is available from the British 2015 by World Scientific Publishing Co. Pte. Ltd. All rights reserved. This book, or parts thereof, may not be reproduced in any form or by any means, electronic or mechanical, including photocopying, recording or any information storage and retrieval system now known or to be invented, without written permission from the photocopying of material in this volume, please pay a copying fee through the Copyright Clearance Center, Inc.

4 , 222 Rosewood Drive, Danvers, MA 01923, USA. In this case permission to photocopy is not required from the publisher. In-house Editors: Chandra Nugraha/Dipasri SardarTypeset by Stallion PressEmail: in SingaporeDipa - Introduction to Pattern 310/4/2015 1:29:09 PMSeries PrefaceWorld Scientific Publishing Company - Indian Institute of Science CollaborationIISc Press and WSPC are co-publishing books authored by world renowned sci-entists and engineers. This collaboration, started in 2008 during IISc s centenary year under a Memorandum of Understanding between IISc and WSPC, has resulted in the establishment of three Series: IISc Centenary Lectures Series (ICLS), IISc Research Monographs Series (IRMS), and IISc Lecture Notes Series (ILNS).

5 This pioneering collaboration will contribute significantly in disseminating current Indian scientific advancement IISc Centenary Lectures Series will comprise lectures by designated Centenary Lecturers - eminent teachers and researchers from all over the IISc Research Monographs Series will comprise state-of-the-art mono-graphs written by experts in specific areas. They will include, but not limited to, the authors own research IISc Lecture Notes Series will consist of books that are reasonably self-contained and can be used either as textbooks or for self-study at the postgraduate level in science and engineering.

6 The books will be based on material that has been class-tested for most Board for the IISc Lecture Notes Series (ILNS):Gadadhar Misra, Editor-in-Chief S Jog Kuri L Sebastian Sen Visweswariah - Introduction to Pattern 210/4/2015 1:29:09 PMMay 2, 2013 14:6BC: 8831 - Probability and Statistical TheoryPST wsThis page intentionally left blankThis page intentionally left blankApril 8, 2015 13:2 Introduction to Pattern Recognition and Machine Learning - 9in x 6inb1904-fmpage viiTableofContentsAbout the AuthorsxiiiPrefacexv1. Introduction11.

7 Classifiers:AnIntroduction ..52. 143. MachineLearning .. 252. Types of Data371. FeaturesandPatterns .. 372. DomainofaVariable .. 393. TypesofFeatures .. Nominaldata .. Interval-valuedvariables .. Spatio-temporaldata .. 494. Proximitymeasures .. Fractionalnorms .. Aremetricsessential?.. Similaritybetweenvectors .. Proximity between spatial patterns .. Proximity between temporal patterns ..62viiApril 8, 2015 13:2 Introduction to Pattern Recognition and Machine Learning - 9in x 6inb1904-fmpage Peakdissimilarity.

8 Dynamic Time Warping (DTW) distance ..643. Feature Extraction and Feature Selection751. 762. Mutual Information (MI) for Feature Selection ..783. Chi-squareStatistic .. 794. Goodman 815. 816. Singular Value Decomposition (SVD) ..837. Non-negative Matrix Factorization (NMF) ..848. Random Projections (RPs) for FeatureExtraction .. Advantages of random projections ..889. LocalitySensitiveHashing(LSH).. 8810. Class Separability .. 9011. Genetic and Evolutionary Algorithms .. HybridGAforfeatureselection.

9 9212. Feature selection based on an FeaturerankingusingF-score .. Feature ranking using linear support vectormachine(SVM)weightvector .. Feature ranking using numberoflabelchanges .. 10313. Feature Selection for Time Series Data .. Piecewise aggregate approximation .. Waveletdecomposition .. Singular Value Decomposition (SVD) .. Common principal component loading basedvariable subset selection (CLeVer) .. 104 April 8, 2015 13:2 Introduction to Pattern Recognition and Machine Learning - 9in x 6inb1904-fmpage ixTableofContentsix4.

10 Bayesian Learning1111. 1112. NaiveBayesClassifier .. 1133. Frequency-Based Estimation of Probabilities .. 1154. Posterior Probability .. 1175. 1196. 1265. Classification1351. ClassificationWithoutLearning .. 1352. Classification in High-Dimensional Spaces .. Shrinkage divergence proximity (SDP) .. 1433. RandomForests .. Fuzzyrandomforests .. 1484. Linear Support Vector Machine (SVM) .. SVM Adaptation of cutting plane algorithm .. 1555. 1566. Usinggenerativemodels.