Data Mining: Practical Machine Learning Tools and Techniques

Data MiningPractical Machine Learning Tools and TechniquesP088407-FM.qxd 5/3/05 2:21 PM Page iThe Morgan Kaufmann Series in Data Management SystemsSeries Editor:Jim Gray,Microsoft ResearchData Mining: Practical Machine LearningTools and Techniques,Second EditionIan H.Witten and Eibe FrankFuzzy Modeling and Genetic Algorithms forData Mining and ExplorationEarl CoxData Modeling Essentials,Third EditionGraeme C.Simsion and Graham C.WittLocation-Based ServicesJochen Schiller and Agn s VoisardDatabase Modeling with Microsoft Visio forEnterprise ArchitectsTerry Halpin,Ken Evans,Patrick Hallock,and Bill MacleanDesigning Data-Intensive Web ApplicationsStefano Ceri,Piero Fraternali,Aldo Bongio,Marco Brambilla,Sara Comai,andMaristella MateraMining the Web: Discovering Knowledgefrom Hypertext DataSoumen ChakrabartiAdvanced SQL: 1999UnderstandingObject-Relational and Other AdvancedFeaturesJim MeltonDatabase Tuning: Principles,Experiments,and Troubleshooting TechniquesDennis Shasha and Philippe BonnetSQL: 1999Understanding RelationalLanguage ComponentsJim Melton and Alan R.SimonInformation Visualization in Data Miningand Knowledge DiscoveryEdited by Usama Fayyad,Georges G.Grinstein,and Andreas WierseTransactional Information Systems: Theory,Algorithms,and the Practice ofConcurrencyControl and RecoveryGerhard Weikum and Gottfried VossenSpatial Databases: With Application to GISPhilippe Rigaux,Michel Scholl,and Agn sVoisardInformation Modeling and RelationalDatabases: From Conceptual Analysis toLogical DesignTerry HalpinComponent Database SystemsEdited by Klaus R.Dittrich and AndreasGeppertManaging Reference Data in EnterpriseDatabases: Binding Corporate Data to theWider WorldMalcolm ChisholmData Mining: Concepts and TechniquesJiawei Han and Micheline KamberUnderstanding SQL and Java Together: AGuide to SQLJ,JDBC,and RelatedTechnologiesJim Melton and Andrew EisenbergDatabase: Principles,Programming,andPerformance,Second EditionPatrick ONeil and Elizabeth ONeilThe Object Data Standard: ODMG 3.0Edited by R.G.G.Cattell,Douglas K.Barry,Mark Berler,JeffEastman,DavidJordan,Craig Russell,OlafSchadow,Torsten Stanienda,and Fernando VelezData on the Web: From Relations toSemistructured Data and XMLSerge Abiteboul,Peter Buneman,and DanSuciuData Mining: Practical Machine LearningTools and Techniques with JavaImplementationsIan H.Witten and Eibe FrankJoe Celkos SQL for Smarties: Advanced SQLProgramming,Second EditionJoe CelkoJoe Celkos Data and Databases: Concepts inPracticeJoe CelkoDeveloping Time-Oriented DatabaseApplications in SQLRichard T.SnodgrassWeb Farming for the Data WarehouseRichard D.HackathornDatabase Modeling & Design,Third EditionToby J.TeoreyManagement ofHeterogeneous andAutonomous Database SystemsEdited by Ahmed Elmagarmid,MarekRusinkiewicz,and Amit ShethObject-Relational DBMSs: Tracking the NextGreat Wave,Second EditionMichael Stonebraker and Paul Brown,withDorothy MooreA Complete Guide to DB2 UniversalDatabaseDon ChamberlinUniversal Database Management: A Guideto Object/Relational TechnologyCynthia Maro SaraccoReadings in Database Systems,Third EditionEdited by Michael Stonebraker and JosephM.HellersteinUnderstanding SQLs Stored Procedures: AComplete Guide to SQL/PSMJim MeltonPrinciples ofMultimedia Database SystemsV.S.SubrahmanianPrinciples ofDatabase Query Processing forAdvanced ApplicationsClement T.Yu and Weiyi MengAdvanced Database SystemsCarlo Zaniolo,Stefano Ceri,ChristosFaloutsos,Richard T.Snodgrass,V.S.Subrahmanian,and Roberto ZicariPrinciples ofTransaction Processing for theSystems ProfessionalPhilip A.Bernstein and Eric NewcomerUsing the New DB2: IBMs Object-RelationalDatabase SystemDon ChamberlinDistributed AlgorithmsNancy A.LynchActive Database Systems: Triggers and RulesFor Advanced Database ProcessingEdited by Jennifer Widom and Stefano CeriMigrating Legacy Systems: Gateways,Interfaces & the Incremental ApproachMichael L.Brodie and Michael StonebrakerAtomic TransactionsNancy Lynch,Michael Merritt,WilliamWeihl,and Alan FeketeQuery Processing For Advanced DatabaseSystemsEdited by Johann Christoph Freytag,DavidMaier,and Gottfried VossenTransaction Processing: Concepts andTechniquesJim Gray and Andreas ReuterBuilding an Object-Oriented DatabaseSystem: The Story ofO2Edited by Fran ois Bancilhon,ClaudeDelobel,and Paris KanellakisDatabase Transaction Models For AdvancedApplicationsEdited by Ahmed K.ElmagarmidA Guide to Developing Client/Server SQLApplicationsSetrag Khoshaan,Arvola Chan,AnnaWong,and Harry K.T.WongThe Benchmark Handbook For Databaseand Transaction Processing Systems,SecondEditionEdited by Jim GrayCamelot and Avalon: A DistributedTransaction FacilityEdited by Jeffrey L.Eppinger,Lily B.Mummert,and Alfred Z.SpectorReadings in Object-Oriented DatabaseSystemsEdited by Stanley B.Zdonik and DavidMaierP088407-FM.qxd 5/3/05 5:42 PM Page iiData MiningPractical Machine Learning Tools and Techniques,Second EditionIan H. WittenDepartment ofComputer ScienceUniversity ofWaikatoEibe FrankDepartment ofComputer ScienceUniversity ofWaikatoAMSTERDAM"BOSTON"HEIDELBERG"LONDONNEW YORK"OXFORD"PARIS"SAN DIEGOSAN FRANCISCO"SINGAPORE"SYDNEY"TOKYOMORGAN KAUFMANN PUBLISHERS IS AN IMPRINT OF ELSEVIERP088407-FM.qxd 4/30/05 10:55 AM Page iiiPublisher:Diane CerraPublishing Services Manager:Simon CrumpProject Manager:Brandy LillyEditorial Assistant:Asma StephanCover Design:Yvo Riezebos DesignCover Image:Getty ImagesComposition:SNP Best-set Typesetter Ltd.,Hong KongTechnical Illustration:Dartmouth Publishing,Inc.Copyeditor:Graphic World Inc.Proofreader:Graphic World Inc.Indexer:Graphic World Inc.Interior printer:The Maple-Vail Book Manufacturing GroupCover printer:Phoenix Color CorpMorgan Kaufmann Publishers is an imprint ofElsevier.500 Sansome Street,Suite 400,San Francisco,CA 94111This book is printed on acid-free paper. 2005 by Elsevier Inc.All rights reserved.Designations used by companies to distinguish their products are often claimed as trademarksor registered trademarks.In all instances in which Morgan Kaufmann Publishers is aware ofaclaim,the product names appear in initial capital or all capital letters.Readers,however,shouldcontact the appropriate companies for more complete information regarding trademarks andregistration.No part ofthis publication may be reproduced,stored in a retrieval system,or transmitted inany form or by any meanselectronic,mechanical,photocopying,scanning,or otherwisewithout prior written permission ofthe publisher.Permissions may be sought directly from Elseviers Science & Technology Rights Department inOxford,UK:phone:(+44) 1865 843830,fax:(+44) 1865 853333,e-mail:[email protected] may also complete your request on-line via the Elsevierhomepage (http://elsevier.com) by selecting Customer Supportand then ObtainingPermissions.Library ofCongress Cataloging-in-Publication DataWitten,I.H.(Ian H.)Data mining :practical machine learning tools and techniques / Ian H.Witten,Eibe Frank. 2nd ed.p.cm. (Morgan Kaufmann series in data management systems)Includes bibliographical references and index.ISBN:0-12-088407-01.Data mining.I.Frank,Eibe.II.Title.III.Series.QA76.9.D343W58 2005006.3dc222005043385For information on all Morgan Kaufmann publications,visit our Web site at www.mkp.comor www.books.elsevier.comPrinted in the United States ofAmerica050607080954321Working together to grow libraries in developing countrieswww.elsevier.com | www.bookaid.org | www.sabre.orgP088407-FM.qxd 5/3/05 2:22 PM Page ivForewordJim Gray,Series EditorMicrosoft ResearchTechnology now allows us to capture and store vast quantities ofdata.Findingpatterns,trends,and anomalies in these datasets,and summarizing them with simple quantitative models,is one ofthe grand challenges ofthe infor-mation ageturning data into information and turning information intoknowledge.There has been stunning progress in data mining and machine learning.Thesynthesis ofstatistics,machine learning,information theory,and computing hascreated a solid science,with a rm mathematical base,and with very powerfultools.Witten and Frank present much ofthis progress in this book and in thecompanion implementation ofthe key algorithms.As such,this is a milestonein the synthesis ofdata mining,data analysis,information theory,and machinelearning.Ifyou have not been following this eld for the last decade,this is agreat way to catch up on this exciting progress.Ifyou have,then Witten andFranks presentation and the companion open-source workbench,called Weka,will be a useful addition to your toolkit.They present the basic theory ofautomatically extracting models from data,and then validating those models.The book does an excellent job ofexplainingthe various models (decision trees,association rules,linear models,clustering,Bayes nets,neural nets) and how to apply them in practice.With this basis,theythen walk through the steps and pitfalls ofvarious approaches.They describehow to safely scrub datasets,how to build models,and how to evaluate a modelspredictive quality.Most ofthe book is tutorial,but Part II broadly describes howcommercial systems work and gives a tour ofthe publicly available data miningworkbench that the authors provide through a website.This Weka workbenchhas a graphical user interface that leads you through data mining tasks and hasexcellent data visualization tools that help understand the models.It is a greatcompanion to the text and a useful and popular tool in its own right.vP088407-FM.qxd 5/3/05 2:23 PM Page vThis book presents this new discipline in a very accessible form:as a text both to train the next generation ofpractitioners and researchers and to informlifelong learners like myself.Witten and Frank have a passion for simple andelegant solutions.They approach each topic with this mindset,grounding allconcepts in concrete examples,and urging the reader to consider the simpletechniques rst,and then progress to the more sophisticated ones ifthe simpleones prove inadequate.Ifyou are interested in databases,and have not been following the machinelearning eld,this book is a great way to catch up on this exciting progress.Ifyou have data that you want to analyze and understand,this book and the asso-ciated Weka toolkit are an excellent way to start.viFOREWORDP088407-FM.qxd 5/3/05 2:23 PM Page viContentsForewordvPrefacexxiiiUpdated and revised contentxxviiAcknowledgmentsxxixPart IMachine learning tools and techniques11Whats it all about?31.1Data mining and machine learning4Describing structural patterns6Machine learning7Data mining91.2Simple examples:The weather problem and others9The weather problem10Contact lenses: An idealized problem13Irises: A classic numeric dataset15CPU performance: Introducing numeric prediction16Labor negotiations: A more realistic example17Soybean classication: A classic machine learning success181.3Fielded applications22Decisions involving judgment22Screening images23Load forecasting24Diagnosis25Marketing and sales26Other applications28viiP088407-FM.qxd 4/30/05 10:55 AM Page vii1.4Machine learning and statistics291.5Generalization as search30Enumerating the concept space31Bias321.6Data mining and ethics351.7Further reading372Input: Concepts, instances, and attributes412.1Whats a concept?422.2Whats in an example?452.3Whats in an attribute?492.4Preparing the input52Gathering the data together52ARFF format53Sparse data55Attribute types56Missing values58Inaccurate values59Getting to know your data602.5Further reading603Output: Knowledge representation613.1Decision tables623.2Decision trees623.3Classication rules653.4Association rules693.5Rules with exceptions703.6Rules involving relations733.7Trees for numeric prediction763.8Instance-based representation763.9Clusters813.10Further reading82viiiCONTENTSP088407-FM.qxd 4/30/05 10:55 AM Page viii4Algorithms: The basic methods834.1Inferring rudimentary rules84Missing values and numeric attributes86Discussion884.2Statistical modeling88Missing values and numeric attributes92Bayesian models for document classication94Discussion964.3Divide-and-conquer:Constructing decision trees97Calculating information100Highly branching attributes102Discussion1054.4Covering algorithms:Constructing rules105Rules versus trees107A simple covering algorithm107Rules versus decision lists1114.5Mining association rules112Item sets113Association rules113Generating rules efciently117Discussion1184.6Linear models119Numeric prediction: Linear regression119Linear classication: Logistic regression121Linear classication using the perceptron124Linear classication using Winnow1264.7Instance-based learning128The distance function128Finding nearest neighbors efciently129Discussion1354.8Clustering136Iterative distance-based clustering137Faster distance calculations138Discussion1394.9Further reading139CONTENTSixP088407-FM.qxd 4/30/05 10:55 AM Page ix5Credibility: Evaluating whats been learned1435.1Training and testing1445.2Predicting performance1465.3Cross-validation1495.4Other estimates151Leave-one-out151The bootstrap1525.5Comparing data mining methods1535.6Predicting probabilities157Quadratic loss function158Informational loss function159Discussion1605.7Counting the cost161Cost-sensitive classication164Cost-sensitive learning165Lift charts166ROC curves168Recallprecision curves171Discussion172Cost curves1735.8Evaluating numeric prediction1765.9The minimum description length principle1795.10Applying the MDL principle to clustering1835.11Further reading1846Implementations: Real machine learning schemes1876.1Decision trees189Numeric attributes189Missing values191Pruning192Estimating error rates193Complexity ofdecision tree induction196From trees to rules198C4.5: Choices and options198Discussion1996.2Classication rules200Criteria for choosing tests200Missing values,numeric attributes201xCONTENTSP088407-FM.qxd 4/30/05 10:55 AM Page xGenerating good rules202Using global optimization205Obtaining rules from partial decision trees207Rules with exceptions210Discussion2136.3Extending linear models214The maximum margin hyperplane215Nonlinear class boundaries217Support vector regression219The kernel perceptron222Multilayer perceptrons223Discussion2356.4Instance-based learning235Reducing the number ofexemplars236Pruning noisy exemplars236Weighting attributes237Generalizing exemplars238Distance functions for generalized exemplars239Generalized distance functions241Discussion2426.5Numeric prediction243Model trees244Building the tree245Pruning the tree245Nominal attributes246Missing values246Pseudocode for model tree induction247Rules from model trees250Locally weighted linear regression251Discussion2536.6Clustering254Choosing the number ofclusters254Incremental clustering255Category utility260Probability-based clustering262The EM algorithm265Extending the mixture model266Bayesian clustering268Discussion2706.7Bayesian networks271Making predictions272Learning Bayesian networks276CONTENTSxiP088407-FM.qxd 4/30/05 10:55 AM Page xiSpecic algorithms278Data structures for fast learning280Discussion2837Transformations: Engineering the input and output2857.1Attribute selection288Scheme-independent selection290Searching the attribute space292Scheme-specic selection2947.2Discretizing numeric attributes296Unsupervised discretization297Entropy-based discretization298Other discretization methods302Entropy-based versus error-based discretization302Converting discrete to numeric attributes3047.3Some useful transformations305Principal components analysis306Random projections309Text to attribute vectors309Time series3117.4Automatic data cleansing312Improving decision trees312Robust regression313Detecting anomalies3147.5Combining multiple models315Bagging316Bagging with costs319Randomization320Boosting321Additive regression325Additive logistic regression327Option trees328Logistic model trees331Stacking332Error-correcting output codes3347.6Using unlabeled data337Clustering for classication337Co-training339EM and co-training3407.7Further reading341xiiCONTENTSP088407-FM.qxd 4/30/05 10:55 AM Page xii8Moving on: Extensions and applications3458.1Learning from massive datasets3468.2Incorporating domain knowledge3498.3Text and Web mining3518.4Adversarial situations3568.5Ubiquitous data mining3588.6Further reading361Part IIThe Weka machine learning workbench3639Introduction to Weka3659.1Whats in Weka?3669.2How do you use it?3679.3What else can you do?3689.4How do you get it?36810The Explorer36910.1Getting started369Preparing the data370Loading the data into the Explorer370Building a decision tree373Examining the output373Doing it again377Working with models377When things go wrong37810.2Exploring the Explorer380Loading and ltering les380Training and testing learning schemes384Do it yourself: The User Classier388Using a metalearner389Clustering and association rules391Attribute selection392Visualization39310.3Filtering algorithms393Unsupervised attribute lters395Unsupervised instance lters400Supervised lters401CONTENTSxiiiP088407-FM.qxd 4/30/05 10:55 AM Page xiii10.4Learning algorithms403Bayesian classiers403Trees406Rules408Functions409Lazy classiers413Miscellaneous classiers41410.5Metalearning algorithms414Bagging and randomization414Boosting416Combining classiers417Cost-sensitive learning417Optimizing performance417Retargeting classiers for different tasks41810.6Clustering algorithms41810.7Association-rule learners41910.8Attribute selection420Attribute subset evaluators422Single-attribute evaluators422Search methods42311The Knowledge Flow interface42711.1Getting started42711.2The Knowledge Flow components43011.3Conguring and connecting the components43111.4Incremental learning43312The Experimenter43712.1Getting started438Running an experiment439Analyzing the results44012.2Simple setup44112.3Advanced setup44212.4The Analyze panel44312.5Distributing processing over several machines445xivCONTENTSP088407-FM.qxd 4/30/05 10:55 AM Page xiv13The command-line interface44913.1Getting started44913.2The structure ofWeka450Classes,instances,and packages450The weka.core package451The weka.classiers package453Other packages455Javadoc indices45613.3Command-line options456Generic options456Scheme-specic options45814Embedded machine learning46114.1A simple data mining application46114.2Going through the code462main()462MessageClassier()462updateData()468classifyMessage()46815Writing new learning schemes47115.1An example classier471buildClassier()472makeTree()472computeInfoGain()480classifyInstance()480main()48115.2Conventions for implementing classiers483References485Index505About the authors525CONTENTSxvP088407-FM.qxd 5/3/05 9:13 AM Page xvP088407-FM.qxd 4/30/05 10:55 AM Page xviList of FiguresFigure 1.1Rules for the contact lens data.13Figure 1.2Decision tree for the contact lens data.14Figure 1.3Decision trees for the labor negotiations data.19Figure 2.1A family tree and two ways ofexpressing the sister-ofrelation.46Figure 2.2ARFF le for the weather data.54Figure 3.1Constructing a decision tree interactively:(a) creating arectangular test involving petallengthand petalwidthand (b)the resulting (unnished) decision tree.64Figure 3.2Decision tree for a simple disjunction.66Figure 3.3The exclusive-or problem.67Figure 3.4Decision tree with a replicated subtree.68Figure 3.5Rules for the Iris data.72Figure 3.6The shapes problem.73Figure 3.7Models for the CPU performance data:(a) linear regression,(b) regression tree,and (c) model tree.77Figure 3.8Different ways ofpartitioning the instance space.79Figure 3.9Different ways ofrepresenting clusters.81Figure 4.1Pseudocode for 1R.85Figure 4.2Tree stumps for the weather data.98Figure 4.3Expanded tree stumps for the weather data.100Figure 4.4Decision tree for the weather data.101Figure 4.5Tree stump for the ID codeattribute.103Figure 4.6Covering algorithm:(a) covering the instances and (b) thedecision tree for the same problem.106Figure 4.7The instance space during operation ofa covering algorithm.108Figure 4.8Pseudocode for a basic rule learner.111Figure 4.9Logistic regression:(a) the logit transform and (b) an examplelogistic regression function.122xviiP088407-FM.qxd 4/30/05 10:55 AM Page xviiFigure 4.10The perceptron:(a) learning rule and (b) representation as a neural network.125Figure 4.11The Winnow algorithm:(a) the unbalanced version and (b) the balanced version.127Figure 4.12A kD-tree for four training instances:(a) the tree and (b)instances and splits.130Figure 4.13Using a kD-tree to nd the nearest neighbor ofthe star.131Figure 4.14Ball tree for 16 training instances:(a) instances and balls and(b) the tree.134Figure 4.15Ruling out an entire ball (gray) based on a target point (star)and its current nearest neighbor.135Figure 4.16A ball tree:(a) two cluster centers and their dividing line and(b) the corresponding tree.140Figure 5.1A hypothetical lift chart.168Figure 5.2A sample ROC curve.169Figure 5.3ROC curves for two learning methods.170Figure 5.4Effects ofvarying the probability threshold:(a) the error curveand (b) the cost curve.174Figure 6.1Example ofsubtree raising,where node C is raisedtosubsume node B.194Figure 6.2Pruning the labor negotiations decision tree.196Figure 6.3Algorithm for forming rules by incremental reduced-errorpruning.205Figure 6.4RIPPER:(a) algorithm for rule learning and (b) meaning ofsymbols.206Figure 6.5Algorithm for expanding examples into a partial tree.208Figure 6.6Example ofbuilding a partial tree.209Figure 6.7Rules with exceptions for the iris data.211Figure 6.8A maximum margin hyperplane.216Figure 6.9Support vector regression:(a) e=1,(b) e=2,and (c) e=0.5.221Figure 6.10Example datasets and corresponding perceptrons.225Figure 6.11Step versus sigmoid:(a) step function and (b) sigmoidfunction.228Figure 6.12Gradient descent using the error function x2+1.229Figure 6.13Multilayer perceptron with a hidden layer.231Figure 6.14A boundary between two rectangular classes.240Figure 6.15Pseudocode for model tree induction.248Figure 6.16Model tree for a dataset with nominal attributes.250Figure 6.17Clustering the weather data.256xviiiLIST OF FIGURESP088407-FM.qxd 4/30/05 10:55 AM Page xviiiFigure 6.18Hierarchical clusterings ofthe iris data.259Figure 6.19A two-class mixture model.264Figure 6.20A simple Bayesian network for the weather data.273Figure 6.21Another Bayesian network for the weather data.274Figure 6.22The weather data:(a) reduced version and (b) correspondingAD tree.281Figure 7.1Attribute space for the weather dataset.293Figure 7.2Discretizing the temperatureattribute using the entropymethod.299Figure 7.3The result ofdiscretizing the temperatureattribute.300Figure 7.4Class distribution for a two-class,two-attribute problem.303Figure 7.5Principal components transform ofa dataset:(a) variance ofeach component and (b) variance plot.308Figure 7.6Number ofinternational phone calls from Belgium,19501973.314Figure 7.7Algorithm for bagging.319Figure 7.8Algorithm for boosting.322Figure 7.9Algorithm for additive logistic regression.327Figure 7.10Simple option tree for the weather data.329Figure 7.11Alternating decision tree for the weather data.330Figure 10.1The Explorer interface.370Figure 10.2Weather data:(a) spreadsheet,(b) CSV format,and (c) ARFF.371Figure 10.3The Weka Explorer:(a) choosing the Explorer interface and(b) reading in the weather data.372Figure 10.4Using J4.8:(a) nding it in the classiers list and (b) theClassifytab.374Figure 10.5Output from the J4.8 decision tree learner.375Figure 10.6Visualizing the result ofJ4.8 on the iris dataset:(a) the treeand (b) the classier errors.379Figure 10.7Generic object editor:(a) the editor,(b) more information(click More),and (c) choosing a converter (click Choose).381Figure 10.8Choosing a lter:(a) the ltersmenu,(b) an object editor,and(c) more information (click More).383Figure 10.9The weather data with two attributes removed.384Figure 10.10Processing the CPU performance data with M5 .385Figure 10.11Output from the M5 program for numeric prediction.386Figure 10.12Visualizing the errors:(a) from M5 and (b) from linearregression.388LIST OF FIGURESxixP088407-FM.qxd 4/30/05 10:55 AM Page xixFigure 10.13Working on the segmentation data with the User Classier:(a) the data visualizer and (b) the tree visualizer.390Figure 10.14Conguring a metalearner for boosting decision stumps.391Figure 10.15Output from the Apriori program for association rules.392Figure 10.16Visualizing the Iris dataset.394Figure 10.17Using Wekas metalearner for discretization:(a) conguringFilteredClassier,and (b) the menu oflters.402Figure 10.18Visualizing a Bayesian network for the weather data (nominalversion):(a) default output,(b) a version with themaximum number ofparents set to 3in the searchalgorithm,and (c) probability distribution table for thewindynode in (b).406Figure 10.19Changing the parameters for J4.8.407Figure 10.20Using Wekas neural-network graphical user interface.411Figure 10.21Attribute selection:specifying an evaluator and a searchmethod.420Figure 11.1The Knowledge Flow interface.428Figure 11.2Conguring a data source:(a) the right-click menu and (b) the le browser obtained from the Conguremenu item.429Figure 11.3Operations on the Knowledge Flow components.432Figure 11.4A Knowledge Flow that operates incrementally:(a) theconguration and (b) the strip chart output.434Figure 12.1An experiment:(a) setting it up,(b) the results le,and (c) a spreadsheet with the results.438Figure 12.2Statistical test results for the experiment in Figure 12.1.440Figure 12.3Setting up an experiment in advanced mode.442Figure 12.4Rows and columns ofFigure 12.2:(a) row eld,(b) columneld,(c) result ofswapping the row and column selections,and (d) substituting Runfor Datasetas rows.444Figure 13.1Using Javadoc:(a) the front page and (b) the weka.corepackage.452Figure 13.2DecisionStump:A class ofthe weka.classiers.treespackage.454Figure 14.1Source code for the message classier.463Figure 15.1Source code for the ID3 decision tree learner.473xxLIST OF FIGURESP088407-FM.qxd 5/3/05 2:24 PM Page xxList of TablesTable 1.1The contact lens data.6Table 1.2The weather data.11Table 1.3Weather data with some numeric attributes.12Table 1.4The iris data.15Table 1.5The CPU performance data.16Table 1.6The labor negotiations data.18Table 1.7The soybean data.21Table 2.1Iris data as a clustering problem.44Table 2.2Weather data with a numeric class.44Table 2.3Family tree represented as a table.47Table 2.4The sister-ofrelation represented in a table.47Table 2.5Another relation represented as a table.49Table 3.1A new iris ower.70Table 3.2Training data for the shapes problem.74Table 4.1Evaluating the attributes in the weather data.85Table 4.2The weather data with counts and probabilities.89Table 4.3A new day.89Table 4.4The numeric weather data with summary statistics.93Table 4.5Another new day.94Table 4.6The weather data with identication codes.103Table 4.7Gain ratio calculations for the tree stumps ofFigure 4.2.104Table 4.8Part ofthe contact lens data for which astigmatism =yes.109Table 4.9Part ofthe contact lens data for which astigmatism =yesandtear production rate =normal.110Table 4.10Item sets for the weather data with coverage 2 or greater.114Table 4.11Association rules for the weather data.116Table 5.1Condence limits for the normal distribution.148xxiP088407-FM.qxd 4/30/05 10:55 AM Page xxiTable 5.2Condence limits for Students distribution with 9 degrees offreedom.155Table 5.3Different outcomes ofa two-class prediction.162Table 5.4Different outcomes ofa three-class prediction:(a) actual and(b) expected.163Table 5.5Default cost matrixes:(a) a two-class case and (b) a three-classcase.164Table 5.6Data for a lift chart.167Table 5.7Different measures used to evaluate the false positive versus thefalse negative tradeoff.172Table 5.8Performance measures for numeric prediction.178Table 5.9Performance measures for four numeric prediction models.179Table 6.1Linear models in the model tree.250Table 7.1Transforming a multiclass problem into a two-class one:(a) standard method and (b) error-correcting code.335Table 10.1Unsupervised attribute lters.396Table 10.2Unsupervised instance lters.400Table 10.3Supervised attribute lters.402Table 10.4Supervised instance lters.402Table 10.5Classier algorithms in Weka.404Table 10.6Metalearning algorithms in Weka.415Table 10.7Clustering algorithms.419Table 10.8Association-rule learners.419Table 10.9Attribute evaluation methods for attribute selection.421Table 10.10Search methods for attribute selection.421Table 11.1Visualization and evaluation components.430Table 13.1Generic options for learning schemes in Weka.457Table 13.2Scheme-specic options for the J4.8 decision tree learner.458Table 15.1Simple learning schemes in Weka.472xxiiLIST OF TABLESP088407-FM.qxd 5/3/05 2:24 PM Page xxiiPrefaceThe convergence ofcomputing and communication has produced a society thatfeeds on information.Yet most ofthe information is in its raw form:data.Ifdatais characterized as recorded facts,then informationis the set ofpatterns,or expectations,that underlie the data.There is a huge amount ofinformationlocked up in databasesinformation that is potentially important but has notyet been discovered or articulated.Our mission is to bring it forth.Data mining is the extraction ofimplicit,previously unknown,and poten-tially useful information from data.The idea is to build computer programs thatsift through databases automatically,seeking regularities or patterns.Strong pat-terns,iffound,will likely generalize to make accurate predictions on future data.Ofcourse,there will be problems.Many patterns will be banal and uninterest-ing.Others will be spurious,contingent on accidental coincidences in the par-ticular dataset used.In addition real data is imperfect:Some parts will begarbled,and some will be missing.Anything discovered will be inexact:Therewill be exceptions to every rule and cases not covered by any rule.Algorithmsneed to be robust enough to cope with imperfect data and to extract regulari-ties that are inexact but useful.Machine learning provides the technical basis ofdata mining.It is used toextract information from the raw data in databasesinformation that isexpressed in a comprehensible form and can be used for a variety ofpurposes.The process is one ofabstraction:taking the data,warts and all,and inferringwhatever structure underlies it.This book is about the tools and techniques ofmachine learning used in practical data mining for nding,and describing,structural patterns in data.As with any burgeoning new technology that enjoys intense commercialattention,the use ofdata mining is surrounded by a great deal ofhype in thetechnicaland sometimes the popularpress.Exaggerated reports appear ofthe secrets that can be uncovered by setting learning algorithms loose on oceansofdata.But there is no magic in machine learning,no hidden power,noxxiiiP088407-FM.qxd 4/30/05 10:55 AM Page xxiiialchemy.Instead,there is an identiable body ofsimple and practical techniquesthat can often extract useful information from raw data.This book describesthese techniques and shows how they work.We interpret machine learning as the acquisition ofstructural descriptionsfrom examples.The kind ofdescriptions found can be used for prediction,explanation,and understanding.Some data mining applications focus on pre-diction:forecasting what will happen in new situations from data that describewhat happened in the past,often by guessing the classication ofnew examples.But we are equallyperhaps moreinterested in applications in which theresult oflearningis an actual description ofa structure that can be used toclassify examples.This structural description supports explanation,under-standing,and prediction.In our experience,insights gained by the applicationsusers are ofmost interest in the majority ofpractical data mining applications;indeed,this is one ofmachine learnings major advantages over classical statis-tical modeling.The book explains a variety ofmachine learning methods.Some are peda-gogically motivated:simple schemes designed to explain clearly how the basicideas work.Others are practical:real systems used in applications today.Manyare contemporary and have been developed only in the last few years.A comprehensive software resource,written in the Java language,has beencreated to illustrate the ideas in the book.Called the Waikato Environment forKnowledge Analysis,or Weka1for short,it is available as source code on theWorld Wide Web at http://www.cs.waikato.ac.nz/ml/weka.It is a full,industrial-strength implementation ofessentially all the techniques covered in this book.It includes illustrative code and working implementations ofmachine learningmethods.It offers clean,spare implementations ofthe simplest techniques,designed to aid understanding ofthe mechanisms involved.It also provides aworkbench that includes full,working,state-of-the-art implementations ofmany popular learning schemes that can be used for practical data mining orfor research.Finally,it contains a framework,in the form ofa Java class library,that supports applications that use embedded machine learning and even theimplementation ofnew learning schemes.The objective ofthis book is to introduce the tools and techniques formachine learning that are used in data mining.After reading it,you will under-stand what these techniques are and appreciate their strengths and applicabil-ity.Ifyou wish to experiment with your own data,you will be able to do thiseasily with the Weka software.xxivPREFACE1Found only on the islands ofNew Zealand,the weka(pronounced to rhyme with Mecca)is a ightless bird with an inquisitive nature.P088407-FM.qxd 4/30/05 10:55 AM Page xxivThe book spans the gulfbetween the intensely practical approach taken bytrade books that provide case studies on data mining and the more theoretical,principle-driven exposition found in current textbooks on machine learning.(A briefdescription ofthese books appears in the Further readingsection at theend ofChapter 1.) This gulfis rather wide.To apply machine learning tech-niques productively,you need to understand something about how they work;this is not a technology that you can apply blindly and expect to get good results.Different problems yield to different techniques,but it is rarely obvious whichtechniques are suitable for a given situation:you need to know something aboutthe range ofpossible solutions.We cover an extremely wide range oftechniques.We can do this because,unlike many trade books,this volume does not promoteany particular commercial software or approach.We include a large number ofexamples,but they use illustrative datasets that are small enough to allow youto follow what is going on.Real datasets are far too large to show this (and inany case are usually company condential).Our datasets are chosen not to illustrate actual large-scale practical problems but to help you understand whatthe different techniques do,how they work,and what their range ofapplicationis.The book is aimed at the technically aware general reader interested in theprinciples and ideas underlying the current practice ofdata mining.It will also be ofinterest to information professionals who need to become acquaintedwith this new technology and to all those who wish to gain a detailed technicalunderstanding ofwhat machine learning involves.It is written for an eclecticaudience ofinformation systems practitioners,programmers,consultants,developers,information technology managers,specication writers,patentexaminers,and curious laypeopleas well as students and professorswhoneed an easy-to-read book with lots ofillustrations that describes what themajor machine learning techniques are,what they do,how they are used,andhow they work.It is practically oriented,with a strong how toavor,andincludes algorithms,code,and implementations.All those involved in practicaldata mining will benet directly from the techniques described.The book isaimed at people who want to cut through to the reality that underlies the hypeabout machine learning and who seek a practical,nonacademic,unpretentiousapproach.We have avoided requiring any specic theoretical or mathematicalknowledge except in some sections marked by a light gray bar in the margin.These contain optional material,often for the more technical or theoreticallyinclined reader,and may be skipped without loss ofcontinuity.The book is organized in layers that make the ideas accessible to readers whoare interested in grasping the basics and to those who would like more depth oftreatment,along with full details on the techniques covered.We believe that con-sumers ofmachine learning need to have some idea ofhow the algorithms theyuse work.It is often observed that data models are only as good as the personPREFACExxvP088407-FM.qxd 5/3/05 2:24 PM Page xxvwho interprets them,and that person needs to know something about how themodels are produced to appreciate the strengths,and limitations,ofthe tech-nology.However,it is not necessary for all data model users to have a deepunderstanding ofthe ner details ofthe algorithms.We address this situation by describing machine learning methods at succes-sive levels ofdetail.You will learn the basic ideas,the topmost level,by readingthe rst three chapters.Chapter 1 describes,through examples,what machinelearning is and where it can be used;it also provides actual practical applica-tions.Chapters 2 and 3 cover the kinds ofinput and outputor knowledge representationinvolved.Different kinds ofoutput dictate different styles ofalgorithm,and at the next level Chapter 4 describes the basic methods ofmachine learning,simplied to make them easy to comprehend.Here the prin-ciples involved are conveyed in a variety ofalgorithms without getting into intricate details or tricky implementation issues.To make progress in the appli-cation ofmachine learning techniques to particular data mining problems,it isessential to be able to measure how well you are doing.Chapter 5,which can beread out ofsequence,equips you to evaluate the results obtained from machinelearning,addressing the sometimes complex issues involved in performanceevaluation.At the lowest and most detailed level,Chapter 6 exposes in naked detail thenitty-gritty issues ofimplementing a spectrum ofmachine learning algorithms,including the complexities necessary for them to work well in practice.Althoughmany readers may want to ignore this detailed information,it is at this level thatthe full,working,tested implementations ofmachine learning schemes in Wekaare written.Chapter 7 describes practical topics involved with engineering theinput to machine learningfor example,selecting and discretizing attributesand covers several more advanced techniques for rening and combining theoutput from different learning techniques.The nal chapter ofPart I looks tothe future.The book describes most methods used in practical machine learning.However,it does not cover reinforcement learning,because it is rarely appliedin practical data mining;genetic algorithm approaches,because these are justan optimization technique;or relational learning and inductive logic program-ming,because they are rarely used in mainstream data mining applications.The data mining system that illustrates the ideas in the book is described inPart II to clearly separate conceptual material from the practical aspects ofhowto use it.You can skip to Part II directly from Chapter 4 ifyou are in a hurry toanalyze your data and dont want to be bothered with the technical details.Java has been chosen for the implementations ofmachine learning tech-niques that accompany this book because,as an object-oriented programminglanguage,it allows a uniform interface to learning schemes and methods for pre-and postprocessing.We have chosen Java instead ofC++,Smalltalk,or otherxxviPREFACEP088407-FM.qxd 4/30/05 10:55 AM Page xxviobject-oriented languages because programs written in Java can be run onalmost any computer without having to be recompiled,having to undergo com-...