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. 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.

2 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. 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.

3 , 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).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.

4 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. 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. Classifiers:AnIntroduction.

5 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 .. 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).

6 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 .. 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.

7 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 .. Usinggraph-basedmethods .. Usingco-trainingmethods .. SVM for semi-supervised classification .. Random forests for semi-supervisedclassification .. 1667. ClassificationofTime-SeriesData .. Distance-basedclassification .. Model-basedclassification.

8 170 April 8, 2015 13:2 Introduction to Pattern Recognition and Machine Learning - 9in x 6inb1904-fmpage xxTableofContents6. Classification using Soft Computing Techniques 1771. Introduction .. 1772. FuzzyClassification .. Fuzzyk-nearest neighbor algorithm .. 1793. RoughClassification .. Roughsetattributereduction .. 1814. GAs .. Weighting of attributes using GA .. Binary Pattern classification using GA .. Rule-based classification using GAs .. Timeseriesclassification .. Using generalized Choquet integral withsigned fuzzy measure for classificationusingGAs .. Decision tree induction usingEvolutionaryalgorithms .. 1915. NeuralNetworksforClassification .. Multi-layer feed forward networkwith backpropagation .. Training a feedforward neural networkusingGAs.

9 1996. Multi-labelClassification .. Multi-labelkNN(mL-kNN) .. Probabilistic classifier chains (PCC) .. Binaryrelevance(BR) .. Usinglabelpowersets(LP).. Neural networks for Multi-labelclassification .. Evaluation of multi-label classification .. 2097. Data Clustering2151. NumberofPartitions .. 2152. ClusteringAlgorithms .. 219 April 8, 2015 13:2 Introduction to Pattern Recognition and Machine Learning - 9in x 6inb1904-fmpage Leaderalgorithm .. BIRCH: Balanced Iterative 2303. WhyClustering? .. Datacompression .. Outlierdetection .. Patternsynthesis .. 2434. Knowledge-basedclustering .. 2505. CombinationofClusterings .. 2558. Soft Clustering2631. 2642. FuzzyClustering .. FuzzyK-meansalgorithm .. 2673. RoughK-meansalgorithm .. 2714.

10 Clustering Based on Evolutionary Algorithms .. 2725. ClusteringBasedonNeuralNetworks .. 2816. OKMalgorithm .. 2857. Matrix factorization-based methods .. Divide-and-conquerapproach .. Latent Semantic Analysis (LSA) .. Probabilistic Latent Semantic Analysis(PLSA).. Non-negative Matrix Factorization(NMF) .. LDA .. 316 April 8, 2015 13:2 Introduction to Pattern Recognition and Machine Learning - 9in x 6inb1904-fmpage xiixiiTableofContents9. Application Social and Information Networks 3211. Introduction .. 3212. 3223. Identification of Communities in Networks .. Graphpartitioning .. Linkage-basedclustering .. Hierarchicalclustering .. Modularity optimization for partitioninggraphs .. 3334. 3415. InformationDiffusion.