D ATA C LASSIFI C A TION - Charu Aggarwal
D ataC lassificationAlgorithms and Applications
Chapman & Hall/CRCData Mining and Knowledge Discovery SeriesSERIES EDITORVipin KumarUniversity of MinnesotaDepartment of Computer Science and EngineeringMinneapolis, Minnesota, U.S.A.AIMS AND SCOPEThis series aims to capture new developments and applications in data mining and knowledgediscovery, while summarizing the computational tools and techniques useful in data analysis. Thisseries encourages the integration of mathematical, statistical, and computational methods andtechniques through the publication of a broad range of textbooks, reference works, and handbooks. The inclusion of concrete examples and applications is highly encouraged. The scope of theseries includes, but is not limited to, titles in the areas of data mining and knowledge discoverymethods and applications, modeling, algorithms, theory and foundations, data and knowledgevisualization, data mining systems and tools, and privacy and security issues.PUBLISHED TITLESADVANCES IN MACHINE LEARNING AND DATA MINING FOR ASTRONOMYMichael J. Way, Jeffrey D. Scargle, Kamal M. Ali, and Ashok N. SrivastavaBIOLOGICAL DATA MININGJake Y. Chen and Stefano LonardiCOMPUTATIONAL BUSINESS ANALYTICSSubrata DasCOMPUTATIONAL INTELLIGENT DATA ANALYSIS FOR SUSTAINABLEDEVELOPMENTTing Yu, Nitesh V. Chawla, and Simeon SimoffCOMPUTATIONAL METHODS OF FEATURE SELECTIONHuan Liu and Hiroshi MotodaCONSTRAINED CLUSTERING: ADVANCES IN ALGORITHMS, THEORY,AND APPLICATIONSSugato Basu, Ian Davidson, and Kiri L. WagstaffCONTRAST DATA MINING: CONCEPTS, ALGORITHMS, AND APPLICATIONSGuozhu Dong and James BaileyDATA CLASSIFICATION: ALGORITHMS AND APPLICATIONSCharu C. AggarawalDATA CLUSTERING: ALGORITHMS AND APPLICATIONSCharu C. Aggarawal and Chandan K. Reddy
DATA CLUSTERING IN C : AN OBJECT-ORIENTED APPROACHGuojun GanDATA MINING FOR DESIGN AND MARKETINGYukio Ohsawa and Katsutoshi YadaDATA MINING WITH R: LEARNING WITH CASE STUDIESLuís TorgoFOUNDATIONS OF PREDICTIVE ANALYTICSJames Wu and Stephen CoggeshallGEOGRAPHIC DATA MINING AND KNOWLEDGE DISCOVERY,SECOND EDITIONHarvey J. Miller and Jiawei HanHANDBOOK OF EDUCATIONAL DATA MININGCristóbal Romero, Sebastian Ventura, Mykola Pechenizkiy, and Ryan S.J.d. BakerINFORMATION DISCOVERY ON ELECTRONIC HEALTH RECORDSVagelis HristidisINTELLIGENT TECHNOLOGIES FOR WEB APPLICATIONSPriti Srinivas Sajja and Rajendra AkerkarINTRODUCTION TO PRIVACY-PRESERVING DATA PUBLISHING: CONCEPTSAND TECHNIQUESBenjamin C. M. Fung, Ke Wang, Ada Wai-Chee Fu, and Philip S. YuKNOWLEDGE DISCOVERY FOR COUNTERTERRORISM ANDLAW ENFORCEMENTDavid SkillicornKNOWLEDGE DISCOVERY FROM DATA STREAMSJoão GamaMACHINE LEARNING AND KNOWLEDGE DISCOVERY FORENGINEERING SYSTEMS HEALTH MANAGEMENTAshok N. Srivastava and Jiawei HanMINING SOFTWARE SPECIFICATIONS: METHODOLOGIES AND APPLICATIONSDavid Lo, Siau-Cheng Khoo, Jiawei Han, and Chao LiuMULTIMEDIA DATA MINING: A SYSTEMATIC INTRODUCTION TOCONCEPTS AND THEORYZhongfei Zhang and Ruofei ZhangMUSIC DATA MININGTao Li, Mitsunori Ogihara, and George TzanetakisNEXT GENERATION OF DATA MININGHillol Kargupta, Jiawei Han, Philip S. Yu, Rajeev Motwani, and Vipin KumarRAPIDMINER: DATA MINING USE CASES AND BUSINESS ANALYTICSAPPLICATIONSMarkus Hofmann and Ralf Klinkenberg
RELATIONAL DATA CLUSTERING: MODELS, ALGORITHMS,AND APPLICATIONSBo Long, Zhongfei Zhang, and Philip S. YuSERVICE-ORIENTED DISTRIBUTED KNOWLEDGE DISCOVERYDomenico Talia and Paolo TrunfioSPECTRAL FEATURE SELECTION FOR DATA MININGZheng Alan Zhao and Huan LiuSTATISTICAL DATA MINING USING SAS APPLICATIONS, SECOND EDITIONGeorge FernandezSUPPORT VECTOR MACHINES: OPTIMIZATION BASED THEORY,ALGORITHMS, AND EXTENSIONSNaiyang Deng, Yingjie Tian, and Chunhua ZhangTEMPORAL DATA MININGTheophano MitsaTEXT MINING: CLASSIFICATION, CLUSTERING, AND APPLICATIONSAshok N. Srivastava and Mehran SahamiTHE TOP TEN ALGORITHMS IN DATA MININGXindong Wu and Vipin KumarUNDERSTANDING COMPLEX DATASETS: DATA MINING WITH MATRIXDECOMPOSITIONSDavid Skillicorn
D ataC lassificationAlgorithms and ApplicationsEdited byCharu C. AggarwalIBM T. J. Watson Research CenterYorktown Heights, New York, USA
CRC PressTaylor & Francis Group6000 Broken Sound Parkway NW, Suite 300Boca Raton, FL 33487-2742 2015 by Taylor & Francis Group, LLCCRC Press is an imprint of Taylor & Francis Group, an Informa businessNo claim to original U.S. Government worksPrinted on acid-free paperVersion Date: 20140611International Standard Book Number-13: 978-1-4665-8674-1 (Hardback)This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made topublish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materialsor the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If anycopyright material has not been acknowledged please write and let us know so we may rectify in any future reprint.Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in anyform by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming,and recording, or in any information storage or retrieval system, without written permission from the publishers.For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400.CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have beengranted a photocopy license by the CCC, a separate system of payment has been arranged.Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe.Library of Congress Cataloging‑in‑Publication DataData classification : algorithms and applications / edited by Charu C. Aggarwal.pages cm ‑‑ (Chapman & Hall/CRC data mining and knowledge discovery series ; 35)Summary: “This book homes in on three primary aspects of data classification: the core methods for dataclassification including probabilistic classification, decision trees, rule‑based methods, and SVM methods;different problem domains and scenarios such as multimedia data, text data, biological data, categorical data,network data, data streams and uncertain data: and different variations of the classification problem such asensemble methods, visual methods, transfer learning, semi‑supervised methods and active learning. Theseadvanced methods can be used to enhance the quality of the underlying classification results”‑‑ Provided bypublisher.Includes bibliographical references and index.ISBN 978‑1‑4665‑8674‑1 (hardback)1. File organization (Computer science) 2. Categories (Mathematics) 3. Algorithms. I. Aggarwal, CharuC.QA76.9.F5.D38 2014005.74’1‑‑dc23Visit the Taylor & Francis Web site athttp://www.taylorandfrancis.comand the CRC Press Web site athttp://www.crcpress.com2013050912
To my wife Lata, and my daughter Sayani
ContentsEditor BiographyxxiiiContributorsxxvPreface1An Introduction to Data ClassificationCharu C. Aggarwal1.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2Common Techniques in Data Classification . . . . . . . . . . .1.2.1Feature Selection Methods . . . . . . . . . . . . . . .1.2.2Probabilistic Methods . . . . . . . . . . . . . . . . . .1.2.3Decision Trees . . . . . . . . . . . . . . . . . . . . . .1.2.4Rule-Based Methods . . . . . . . . . . . . . . . . . .1.2.5Instance-Based Learning . . . . . . . . . . . . . . . .1.2.6SVM Classifiers . . . . . . . . . . . . . . . . . . . . .1.2.7Neural Networks . . . . . . . . . . . . . . . . . . . . .1.3Handing Different Data Types . . . . . . . . . . . . . . . . . .1.3.1Large Scale Data: Big Data and Data Streams . . . . .1.3.1.1 Data Streams . . . . . . . . . . . . . . . . .1.3.1.2 The Big Data Framework . . . . . . . . . . .1.3.2Text Classification . . . . . . . . . . . . . . . . . . . .1.3.3Multimedia Classification . . . . . . . . . . . . . . . .1.3.4Time Series and Sequence Data Classification . . . . .1.3.5Network Data Classification . . . . . . . . . . . . . . .1.3.6Uncertain Data Classification . . . . . . . . . . . . . .1.4Variations on Data Classification . . . . . . . . . . . . . . . . .1.4.1Rare Class Learning . . . . . . . . . . . . . . . . . . .1.4.2Distance Function Learning . . . . . . . . . . . . . . .1.4.3Ensemble Learning for Data Classification . . . . . . .1.4.4Enhancing Classification Methods with Additional Data1.4.4.1 Semi-Supervised Learning . . . . . . . . . .1.4.4.2 Transfer Learning . . . . . . . . . . . . . . .1.4.5Incorporating Human Feedback . . . . . . . . . . . . .1.4.5.1 Active Learning . . . . . . . . . . . . . . . .1.4.5.2 Visual Learning . . . . . . . . . . . . . . . .1.4.6Evaluating Classification Algorithms . . . . . . . . . .1.5Discussion and Conclusions . . . . . . . . . . . . . . . . . . 262728293031ix
x23ContentsFeature Selection for Classification: A ReviewJiliang Tang, Salem Alelyani, and Huan Liu2.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . .2.1.1Data Classification . . . . . . . . . . . . . . . . . .2.1.2Feature Selection . . . . . . . . . . . . . . . . . .2.1.3Feature Selection for Classification . . . . . . . . .2.2Algorithms for Flat Features . . . . . . . . . . . . . . . . .2.2.1Filter Models . . . . . . . . . . . . . . . . . . . .2.2.2Wrapper Models . . . . . . . . . . . . . . . . . . .2.2.3Embedded Models . . . . . . . . . . . . . . . . . .2.3Algorithms for Structured Features . . . . . . . . . . . . . .2.3.1Features with Group Structure . . . . . . . . . . . .2.3.2Features with Tree Structure . . . . . . . . . . . . .2.3.3Features with Graph Structure . . . . . . . . . . . .2.4Algorithms for Streaming Features . . . . . . . . . . . . . .2.4.1The Grafting Algorithm . . . . . . . . . . . . . . .2.4.2The Alpha-Investing Algorithm . . . . . . . . . . .2.4.3The Online Streaming Feature Selection Algorithm2.5Discussions and Challenges . . . . . . . . . . . . . . . . . .2.5.1Scalability . . . . . . . . . . . . . . . . . . . . . .2.5.2Stability . . . . . . . . . . . . . . . . . . . . . . .2.5.3Linked Data . . . . . . . . . . . . . . . . . . . . .37.Probabilistic Models for ClassificationHongbo Deng, Yizhou Sun, Yi Chang, and Jiawei Han3.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.2Naive Bayes Classification . . . . . . . . . . . . . . . . . . . . .3.2.1Bayes’ Theorem and Preliminary . . . . . . . . . . . . .3.2.2Naive Bayes Classifier . . . . . . . . . . . . . . . . . . .3.2.3Maximum-Likelihood Estimates for Naive Bayes Models3.2.4Applications . . . . . . . . . . . . . . . . . . . . . . . .3.3Logistic Regression Classification . . . . . . . . . . . . . . . . .3.3.1Logistic Regression . . . . . . . . . . . . . . . . . . . .3.3.2Parameters Estimation for Logistic Regression . . . . . .3.3.3Regularization in Logistic Regression . . . . . . . . . . .3.3.4Applications . . . . . . . . . . . . . . . . . . . . . . . .3.4Probabilistic Graphical Models for Classification . . . . . . . . .3.4.1Bayesian Networks . . . . . . . . . . . . . . . . . . . .3.4.1.1 Bayesian Network Construction . . . . . . . .3.4.1.2 Inference in a Bayesian Network . . . . . . . .3.4.1.3 Learning Bayesian Networks . . . . . . . . . .3.4.2Hidden Markov Models . . . . . . . . . . . . . . . . . .3.4.2.1 The Inference and Learning Algorithms . . . .3.4.3Markov Random Fields . . . . . . . . . . . . . . . . . .3.4.3.1 Conditional Independence . . . . . . . . . . .3.4.3.2 Clique Factorization . . . . . . . . . . . . . .3.4.3.3 The Inference and Learning Algorithms . . . .3.4.4Conditional Random Fields . . . . . . . . . . . . . . . .3.4.4.1 The Learning Algorithms . . . . . . . . . . . .3.5Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69707172737475767676777878787981818182828383
Contents45Decision Trees: Theory and AlgorithmsVictor E. Lee, Lin Liu, and Ruoming Jin4.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . .4.2Top-Down Decision Tree Induction . . . . . . . . . . . . . .4.2.1Node Splitting . . . . . . . . . . . . . . . . . . . . .4.2.2Tree Pruning . . . . . . . . . . . . . . . . . . . . . .4.3Case Studies with C4.5 and CART . . . . . . . . . . . . . . .4.3.1Splitting Criteria . . . . . . . . . . . . . . . . . . . .4.3.2Stopping Conditions . . . . . . . . . . . . . . . . . .4.3.3Pruning Strategy . . . . . . . . . . . . . . . . . . . .4.3.4Handling Unknown Values: Induction and Prediction4.3.5Other Issues: Windowing and Multivariate Criteria . .4.4Scalable Decision Tree Construction . . . . . . . . . . . . . .4.4.1RainForest-Based Approach . . . . . . . . . . . . . .4.4.2SPIES Approach . . . . . . . . . . . . . . . . . . . .4.4.3Parallel Decision Tree Construction . . . . . . . . . .4.5Incremental Decision Tree Induction . . . . . . . . . . . . . .4.5.1ID3 Family . . . . . . . . . . . . . . . . . . . . . . .4.5.2VFDT Family . . . . . . . . . . . . . . . . . . . . .4.5.3Ensemble Method for Streaming Data . . . . . . . .4.6Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . .xi87.Rule-Based ClassificationXiao-Li Li and Bing Liu5.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5.2Rule Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5.2.1Two Algorithms for Rule Induction . . . . . . . . . . . . . . . . . .5.2.1.1 CN2 Induction Algorithm (Ordered Rules) . . . . . . . .5.2.1.2 RIPPER Algorithm and Its Variations (Ordered Classes) .5.2.2Learn One Rule in Rule Learning . . . . . . . . . . . . . . . . . . .5.3Classification Based on Association Rule Mining . . . . . . . . . . . . . . .5.3.1Association Rule Mining . . . . . . . . . . . . . . . . . . . . . . .5.3.1.1 Definitions of Association Rules, Support, and Confidence5.3.1.2 The Introduction of Apriori Algorithm . . . . . . . . . . .5.3.2Mining Class Association Rules . . . . . . . . . . . . . . . . . . . .5.3.3Classification Based on Associations . . . . . . . . . . . . . . . . .5.3.3.1 Additional Discussion for CARs Mining . . . . . . . . . .5.3.3.2 Building a Classifier Using CARs . . . . . . . . . . . . .5.3.4Other Techniques for Association Rule-Based Classification . . . . .5.4Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5.4.1Text Categorization . . . . . . . . . . . . . . . . . . . . . . . . . .5.4.2Intrusion Detection . . . . . . . . . . . . . . . . . . . . . . . . . .5.4.3Using Class Association Rules for Diagnostic Data Mining . . . . .5.4.4Gene Expression Data Analysis . . . . . . . . . . . . . . . . . . . .5.5Discussion and Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 42144144147148149150
xii678ContentsInstance-Based Learning: A SurveyCharu C. Aggarwal6.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.2Instance-Based Learning Framework . . . . . . . . . . . . . . . . . . . . . . . .6.3The Nearest Neighbor Classifier . . . . . . . . . . . . . . . . . . . . . . . . . .6.3.1Handling Symbolic Attributes . . . . . . . . . . . . . . . . . . . . . . .6.3.2Distance-Weighted Nearest Neighbor Methods . . . . . . . . . . . . . .6.3.3Local Distance Scaling . . . . . . . . . . . . . . . . . . . . . . . . . .6.3.4Attribute-Weighted Nearest Neighbor Methods . . . . . . . . . . . . . .6.3.5Locally Adaptive Nearest Neighbor Classifier . . . . . . . . . . . . . .6.3.6Combining with Ensemble Methods . . . . . . . . . . . . . . . . . . .6.3.7Multi-Label Learning . . . . . . . . . . . . . . . . . . . . . . . . . . .6.4Lazy SVM Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.5Locally Weighted Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.6Lazy Naive Bayes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.7Lazy Decision Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.8Rule-Based Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.9Radial Basis Function Networks: Leveraging Neural Networks for Instance-BasedLearning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.10 Lazy Methods for Diagnostic and Visual Classification . . . . . . . . . . . . . .6.11 Conclusions and Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Support Vector MachinesPo-Wei Wang and Chih-Jen Lin7.1Introduction . . . . . . . . . . . .7.2The Maximum Margin Perspective7.3The Regularization Perspective . .7.4The Support Vector Perspective . .7.5Kernel Tricks . . . . . . . . . . .7.6Solvers and Algorithms . . . . . .7.7Multiclass Strategies . . . . . . .7.8Conclusion . . . . . . . . . . . 75176180187.Neural Networks: A ReviewAlain Biem8.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . .8.2Fundamental Concepts . . . . . . . . . . . . . . . . . . . .8.2.1Mathematical Model of a Neuron . . . . . . . . . .8.2.2Types of Units . . . . . . . . . . . . . . . . . . . .8.2.2.1 McCullough Pitts Binary Threshold Unit8.2.2.2 Linear Unit . . . . . . . . . . . . . . . .8.2.2.3 Linear Threshold Unit . . . . . . . . . .8.2.2.4 Sigmoidal Unit . . . . . . . . . . . . . .8.2.2.5 Distance Unit . . . . . . . . . . . . . . .8.2.2.6 Radial Basis Unit . . . . . . . . . . . . .8.2.2.7 Polynomial Unit . . . . . . . . . . . . .8.2.3Network Topology . . . . . . . . . . . . . . . . . .8.2.3.1 Layered Network . . . . . . . . . . . . .8.2.3.2 Networks with Feedback . . . . . . . . .8.2.3.3 Modular Networks . . . . . . . . . . . .8.2.4Computation and Knowledge Representation . . . 211211211212212212212213213
Contents8.2.58.38.48.58.68.7Learning . . . . . . . . . . . . . . . . . . . . .8.2.5.1 Hebbian Rule . . . . . . . . . . . . .8.2.5.2 The Delta Rule . . . . . . . . . . . .Single-Layer Neural Network . . . . . . . . . . . . . . .8.3.1The Single-Layer Perceptron . . . . . . . . . .8.3.1.1 Perceptron Criterion . . . . . . . . .8.3.1.2 Multi-Class Perceptrons . . . . . .
introduction to privacy-preserving data publishing: concepts and techniques benjamin c. m. fung, ke wang, ada wai-chee fu, and philip s. yu knowledge discovery for counterterrorism and law enforcement david skillicorn knowledge discovery from data streams joão gama machine learning and knowledge discovery for engineering systems health management
Note The term Cisco ATA is used throughout this manual to refer to both the Cisco ATA 186 and the Cisco ATA 188, unless differences between the Cisco ATA 186 and Cisco ATA 188 are explicitly stated. Default Boot Load Behavior Before configuring the Cisco ATA, you need to know how the default Cisco ATA boot load process works.
ATA (analogais telefona adapters) ANALOGO SIGNĀLU PĀRVEIDOTĀJI (faksiem un analogajiem telefoniem) Cisco SPA122, ATA ar diviem portiem 50.00 33.60 97.00 188.00 Grandstream HT502, ATA ar diviem portiem Grandstream GXW4004, ATA ar četriem portiem Grandstream GXW4008, ATA ar astoņiem portiem IP KONFERENČU IEKĀRTAS
ATA Pediatric Operating Procedures December 23, 2016 Page 1 ATA Operating Procedures for Pediatric Telehealth (December î ï, î ì í ò) PREAMBLE The American Telemedicine Association (ATA), with members from the United States and throughout the world, is the principal organization bri
Cisco ATA 191 and ATA 192 Analog Telephone Adapter User Guide for Multiplatform Firmware First Published: 2018-02-05 Americas Headquarters Cisco Systems, Inc.
Cisco ATA 191 Multiplatform Analog Telephone Adapter The Cisco ATA 191 Multiplatform Analog Telephone Adapter is a 2-port handset-to-Ethernet adapter that brings traditional analog devices into the IP world. Product Overview The Cisco ATA 191 Multiplatform Analog Telephone Adapter turns traditional telephone, fax, and overhead paging
interested in taking the ATA Certification Exam. The handbook is an overview of the process before, during, and after a candidate takes the ATA Certification Exam. Introduction to the ATA Exam ATA has established a certification program that allows translators to demonstrate tha
3 Cisco ATA 186 and Cisco ATA 188 Analog Telephone Adaptor Administrator’s Guide for SIP (version 3.0) OL-4654-01 CONTENTS Preface 13 Overview 13 Audience 13 Organization 14 Conventions 14 Related Documentation 18 Obtaining Documentation 18 World Wide Web 18 Documentation CD-ROM 19 Ordering Documentation 19 Documentation Feedback 19
Anatomi Panggul Panggul terdiri dari : 1. Bagian keras a. 2 tulang pangkal paha ( os coxae); ilium, ischium/duduk, pubis/kemaluan b. 1 tulang kelangkang (os sacrum) c. 1 tulang tungging (0s coccygis) 2. Bagian lunak a. Pars muscularis levator ani b. Pars membranasea c. Regio perineum. ANATOMI PANGGUL 04/09/2018 anatomi fisiologi sistem reproduksi 2011 19. Fungsi Panggul 1. Bagian keras: a .
