8037_9789814335454_tp.indd 1 26/2/15 12:15 pm IISc Lecture Notes Series ISSN: 2010-2402 Editor-in-Chief: Gadadhar Misra Editors: 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 Storch Vol. 2: Schwarz’s Lemma from a Differential Geometric Veiwpoint by Kang-Tae Kim & Hanjin Lee Vol. 3: Noise and Vibration Control by M L Munjal Vol. 4: Game Theory and Mechanism Design by Y Narahari Vol. 5 Introduction to Pattern Recognition and Machine Learning by M. Narasimha Murty & V. Susheela Devi Dipa - Introduction to pattern recognition.indd 1 10/4/2015 1:29:09 PM World Scientific 8037_9789814335454_tp.indd 2 26/2/15 12:15 pm Published by World Scientific Publishing Co. Pte. Ltd. 5 Toh Tuck Link, Singapore 596224 USA office: 27 Warren Street, Suite 401-402, Hackensack, NJ 07601 UK office: 57 Shelton Street, Covent Garden, London WC2H 9HE Library of Congress Cataloging-in-Publication Data Murty, 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. 5) ISBN 978-9814335454 1. Pattern recognition systems. 2. Machine learning. I. Devi, V. Susheela. II. Title. TK7882.P3M87 2015 006.4--dc23 2014044796 British Library Cataloguing-in-Publication Data A catalogue record for this book is available from the British Library. Copyright © 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 publisher. For photocopying of material in this volume, please pay a copying fee through the Copyright Clearance Center, Inc., 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 Sardar Typeset by Stallion Press Email: [email protected] Printed in Singapore Dipa - Introduction to pattern recognition.indd 3 10/4/2015 1:29:09 PM Series Preface World Scientific Publishing Company - Indian Institute of Science Collaboration IISc 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 worldwide. The “IISc Centenary Lectures Series” will comprise lectures by designated Centenary Lecturers - eminent teachers and researchers from all over the world. 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 work. The “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 part. Editorial Board for the IISc Lecture Notes Series (ILNS): Gadadhar Misra, Editor-in-Chief ([email protected]) Chandrashekar S Jog ([email protected]) Joy Kuri ([email protected]) K L Sebastian ([email protected]) Diptiman Sen ([email protected]) Sandhya Visweswariah ([email protected]) Dipa - Introduction to pattern recognition.indd 2 10/4/2015 1:29:09 PM May2,2013 14:6 BC:8831-ProbabilityandStatisticalTheory PST˙ws TThhiiss ppaaggee iinntteennttiioonnaallllyy lleefftt bbllaannkk April8,2015 13:2 IntroductiontoPatternRecognitionandMachineLearning-9inx6in b1904-fm pagevii Table of Contents About the Authors xiii Preface xv 1. Introduction 1 1. Classifiers: An Introduction . . . . . . . . . . . . . . 5 2. An Introduction to Clustering . . . . . . . . . . . . . 14 3. Machine Learning . . . . . . . . . . . . . . . . . . . 25 2. Types of Data 37 1. Features and Patterns . . . . . . . . . . . . . . . . . 37 2. Domain of a Variable . . . . . . . . . . . . . . . . . 39 3. Types of Features . . . . . . . . . . . . . . . . . . . 41 3.1. Nominal data . . . . . . . . . . . . . . . . . . 41 3.2. Ordinal data . . . . . . . . . . . . . . . . . . . 45 3.3. Interval-valued variables . . . . . . . . . . . . 48 3.4. Ratio variables . . . . . . . . . . . . . . . . . . 49 3.5. Spatio-temporal data . . . . . . . . . . . . . . 49 4. Proximity measures . . . . . . . . . . . . . . . . . . 50 4.1. Fractional norms . . . . . . . . . . . . . . . . 56 4.2. Are metrics essential? . . . . . . . . . . . . . . 57 4.3. Similarity between vectors . . . . . . . . . . . 59 4.4. Proximity between spatial patterns . . . . . . 61 4.5. Proximity between temporal patterns . . . . . 62 vii April8,2015 13:2 IntroductiontoPatternRecognitionandMachineLearning-9inx6in b1904-fm pageviii viii Table of Contents 4.6. Mean dissimilarity . . . . . . . . . . . . . . . . 63 4.7. Peak dissimilarity . . . . . . . . . . . . . . . . 63 4.8. Correlation coefficient . . . . . . . . . . . . . . 64 4.9. Dynamic Time Warping (DTW) distance . . . 64 3. Feature Extraction and Feature Selection 75 1. Types of Feature Selection . . . . . . . . . . . . . . . 76 2. Mutual Information (MI) for Feature Selection . . . 78 3. Chi-square Statistic . . . . . . . . . . . . . . . . . . 79 4. Goodman–Kruskal Measure . . . . . . . . . . . . . . 81 5. Laplacian Score . . . . . . . . . . . . . . . . . . . . . 81 6. Singular Value Decomposition (SVD) . . . . . . . . 83 7. Non-negative Matrix Factorization (NMF) . . . . . . 84 8. Random Projections (RPs) for Feature Extraction . . . . . . . . . . . . . . . . . . . . . . . 86 8.1. Advantages of random projections . . . . . . . 88 9. Locality Sensitive Hashing (LSH) . . . . . . . . . . . 88 10. Class Separability . . . . . . . . . . . . . . . . . . . 90 11. Genetic and Evolutionary Algorithms . . . . . . . . 91 11.1. Hybrid GA for feature selection . . . . . . . . 92 12. Ranking for Feature Selection . . . . . . . . . . . . . 96 12.1. Feature selection based on an optimization formulation . . . . . . . . . . . . . . . . . . . . 97 12.2. Feature ranking using F-score . . . . . . . . . 99 12.3. Feature ranking using linear support vector machine (SVM) weight vector . . . . . . . . . 100 12.4. Ensemble feature ranking . . . . . . . . . . . . 101 12.5. Feature ranking using number of label changes . . . . . . . . . . . . . . . . . 103 13. Feature Selection for Time Series Data . . . . . . . . 103 13.1. Piecewise aggregate approximation . . . . . . 103 13.2. Spectral decomposition . . . . . . . . . . . . . 104 13.3. Wavelet decomposition . . . . . . . . . . . . . 104 13.4. Singular Value Decomposition (SVD) . . . . . 104 13.5. Common principal component loading based variable subset selection (CLeVer) . . . . . . . 104 April8,2015 13:2 IntroductiontoPatternRecognitionandMachineLearning-9inx6in b1904-fm pageix Table of Contents ix 4. Bayesian Learning 111 1. Document Classification . . . . . . . . . . . . . . . . 111 2. Naive Bayes Classifier . . . . . . . . . . . . . . . . . 113 3. Frequency-Based Estimation of Probabilities . . . . 115 4. Posterior Probability . . . . . . . . . . . . . . . . . . 117 5. Density Estimation . . . . . . . . . . . . . . . . . . . 119 6. Conjugate Priors . . . . . . . . . . . . . . . . . . . . 126 5. Classification 135 1. Classification Without Learning . . . . . . . . . . . 135 2. Classification in High-Dimensional Spaces . . . . . . 139 2.1. Fractional distance metrics . . . . . . . . . . . 141 2.2. Shrinkage–divergence proximity (SDP) . . . . 143 3. Random Forests . . . . . . . . . . . . . . . . . . . . 144 3.1. Fuzzy random forests . . . . . . . . . . . . . . 148 4. Linear Support Vector Machine (SVM) . . . . . . . 150 4.1. SVM–kNN . . . . . . . . . . . . . . . . . . . . 153 4.2. Adaptation of cutting plane algorithm . . . . 154 4.3. Nystrom approximated SVM . . . . . . . . . . 155 5. Logistic Regression . . . . . . . . . . . . . . . . . . . 156 6. Semi-supervised Classification . . . . . . . . . . . . . 159 6.1. Using clustering algorithms . . . . . . . . . . . 160 6.2. Using generative models . . . . . . . . . . . . 160 6.3. Using low density separation . . . . . . . . . . 161 6.4. Using graph-based methods . . . . . . . . . . 162 6.5. Using co-training methods . . . . . . . . . . . 164 6.6. Using self-training methods. . . . . . . . . . . 165 6.7. SVM for semi-supervised classification . . . . 166 6.8. Random forests for semi-supervised classification . . . . . . . . . . . . . . . . . . . 166 7. Classification of Time-Series Data . . . . . . . . . . 167 7.1. Distance-based classification . . . . . . . . . . 168 7.2. Feature-based classification . . . . . . . . . . . 169 7.3. Model-based classification . . . . . . . . . . . 170