数据挖掘：实用机器学习工具与技术_01数据挖掘概述

1、Data MiningPractical Machine Learning Tools and TechniquesSlides for Chapter 1 of Data Mining by I. H. Witten, E. Frank andM. A. Hall2Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Whats it all about?Data vs informationData mining and machine learningStructural descriptionsR

2、ules: classification and associationDecision treesDatasetsWeather, contact lens, CPU performance, labor negotiation data, soybean classificationFielded applicationsRanking web pages, loan applications, screening images, load forecasting, machine fault diagnosis, market basket analysisGeneralization

3、as searchData mining and ethics3Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Data vs. informationSociety produces huge amounts of dataSources: business, science, medicine, economics, geography, environment, sports, Potentially valuable resourceRaw data is useless: need tec

4、hniques to automatically extract information from itData: recorded factsInformation: patterns underlying the data4Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1) Information is crucialExample 1: in vitro fertilizationGiven: embryos described by 60 featuresProblem: selection

5、of embryos that will surviveData: historical records of embryos and outcomeExample 2: cow cullingGiven: cows described by 700 featuresProblem: selection of cows that should be culledData: historical records and farmers decisions5Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1

6、)Data miningExtractingimplicit,previously unknown,potentially usefulinformation from dataNeeded: programs that detect patterns and regularities in the dataStrong patterns good predictionsProblem 1: most patterns are not interestingProblem 2: patterns may be inexact (or spurious)Problem 3: data may b

7、e garbled or missing6Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Machine learning techniquesAlgorithms for acquiring structural descriptions from examplesStructural descriptions represent patterns explicitlyCan be used to predict outcome in new situationCan be used to und

8、erstand and explain how prediction is derived(may be even more important)Methods originate from artificial intelligence, statistics, and research on databases7Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Structural descriptionsExample: if-then rulesHardNormalYesMyopePresby

9、opicNoneReducedNoHypermetropePre-presbyopicSoftNormalNoHypermetropeYoungNoneReducedNoMyopeYoungRecommended lensesTear production rateAstigmatismSpectacle prescriptionAgeIf tear production rate = reducedthen recommendation = noneOtherwise, if age = young and astigmatic = no then recommendation = soft

10、8Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Can machines really learn?Definitions of “learning” from dictionary:To get knowledge of by study,experience, or being taughtTo become aware by information orfrom observationTo commit to memoryTo be informed of, ascertain; to re

11、ceive instructionDifficult to measureTrivial for computersThings learn when they change their behavior in a way that makes them perform better in the future.Operational definition:Does a slipper learn?Does learning imply intention?9Data Mining: Practical Machine Learning Tools and Techniques (Chapte

12、r 1)The weather problemConditions for playing a certain gameYesFalseNormalMildRainyYesFalseHighHot OvercastNoTrueHighHotSunnyNoFalseHighHotSunnyPlayWindyHumidityTemperatureOutlookIf outlook = sunny and humidity = high then play = noIf outlook = rainy and windy = true then play = noIf outlook = overc

13、ast then play = yesIf humidity = normal then play = yesIf none of the above then play = yes10Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Ross QuinlanMachine learning researcher from 1970sUniversity of Sydney, Australia1986 “Induction of decision trees” ML Journal1993 C4.5

14、: Programs for machine learning. Morgan Kaufmann199? Started11Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Classification vs. association rulesClassification rule:predicts value of a given attribute (the classification of an example)Association rule:predicts value of arbit

15、rary attribute (or combination)If outlook = sunny and humidity = highthen play = noIf temperature = cool then humidity = normalIf humidity = normal and windy = falsethen play = yesIf outlook = sunny and play = no then humidity = highIf windy = false and play = no then outlook = sunny and humidity =

16、high12Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Weather data with mixed attributesSome attributes have numeric valuesYesFalse8075RainyYesFalse8683OvercastNoTrue9080SunnyNoFalse8585SunnyPlayWindyHumidityTemperatureOutlookIf outlook = sunny and humidity 83 then play = noI

17、f outlook = rainy and windy = true then play = noIf outlook = overcast then play = yesIf humidity 85 then play = yesIf none of the above then play = yes13Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)The contact lenses dataNoneReducedYesHypermetropePre-presbyopicNoneNormalY

18、esHypermetropePre-presbyopicNoneReducedNoMyopePresbyopicNoneNormalNoMyopePresbyopicNoneReducedYesMyopePresbyopicHardNormalYesMyopePresbyopicNoneReducedNoHypermetropePresbyopicSoftNormalNoHypermetropePresbyopicNoneReducedYesHypermetropePresbyopicNoneNormalYesHypermetropePresbyopicSoftNormalNoHypermet

19、ropePre-presbyopicNoneReducedNoHypermetropePre-presbyopicHardNormalYesMyopePre-presbyopicNoneReducedYesMyopePre-presbyopicSoftNormalNoMyopePre-presbyopicNoneReducedNoMyopePre-presbyopichardNormalYesHypermetropeYoungNoneReducedYesHypermetropeYoungSoftNormalNoHypermetropeYoungNoneReducedNoHypermetrope

20、YoungHardNormalYesMyopeYoungNoneReducedYesMyopeYoungSoftNormalNoMyopeYoungNoneReducedNoMyopeYoungRecommended lensesTear production rateAstigmatismSpectacle prescriptionAge14Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)A complete and correct rule setIf tear production rate

21、= reduced then recommendation = noneIf age = young and astigmatic = noand tear production rate = normal then recommendation = softIf age = pre-presbyopic and astigmatic = noand tear production rate = normal then recommendation = softIf age = presbyopic and spectacle prescription = myopeand astigmati

22、c = no then recommendation = noneIf spectacle prescription = hypermetrope and astigmatic = noand tear production rate = normal then recommendation = softIf spectacle prescription = myope and astigmatic = yesand tear production rate = normal then recommendation = hardIf age young and astigmatic = yes

23、 and tear production rate = normal then recommendation = hardIf age = pre-presbyopicand spectacle prescription = hypermetropeand astigmatic = yes then recommendation = noneIf age = presbyopic and spectacle prescription = hypermetropeand astigmatic = yes then recommendation = none15Data Mining: Pract

24、ical Machine Learning Tools and Techniques (Chapter 1)A decision tree for this problem16Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Classifying iris flowersIris virginica1.95.12.75.8102101525121Iris virginica2.56.03.36.3Iris versicolor1.54.53.26.4Iris versicolor1.44.73.27

25、.0Iris setosa0.21.43.04.9Iris setosa0.21.43.55.1TypePetal widthPetal lengthSepal widthSepal lengthIf petal length 2.45 then Iris setosaIf sepal width 2.10 then Iris versicolor.17Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Example: 209 different computer configurationsLine

26、ar regression functionPredicting CPU performance0032128CHMAX00816CHMINChannelsPerformanceCache (Kb)Main memory (Kb)Cycle time (ns)45040001000480209673280005124802082693232000800029219825660002561251PRPCACHMMAXMMINMYCTPRP = -55.9 + 0.0489 MYCT + 0.0153 MMIN + 0.0056 MMAX+ 0.6410 CACH - 0.2700 CHMIN +

27、 1.480 CHMAX18Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Data from labor negotiationsgoodgoodgoodbadgood,badAcceptability of contracthalffull?nonenone,half,fullHealth plan contributionyes?noyes,noBereavement assistancefullfull?nonenone,half,fullDental plan contributionye

28、s?noyes,noLong-term disability assistanceavggengenavgbelow-avg,avg,genVacation12121511(Number of days)Statutory holidays?yesyes,noEducation allowanceShift-work supplementStandby payPensionWorking hours per weekCost of living adjustmentWage increase third yearWage increase second yearWage increase fi

29、rst yearDurationAttribute44%5%?Percentage?13%?Percentage?nonenone,ret-allw, empl-cntr40383528(Number of hours)none?tcfnonenone,tcf,tc?Percentage4.04.4%5%?Percentage4.54.3%4%2%Percentage2321(Number of years)40321Type19Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Decision tr

30、ees for the labor data20Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Soybean classificationDiaporthe stem canker19DiagnosisNormal3ConditionRootYes2Stem lodgingAbnormal2ConditionStem?3Leaf spot sizeAbnormal2ConditionLeaf?5Fruit spotsNormal4Condition of fruit podsFruitAbsent

31、2Mold growthNormal2ConditionSeedAbove normal3PrecipitationJuly7Time of occurrenceEnvironmentSample valueNumber of valuesAttribute21Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)The role of domain knowledgeIf leaf condition is normaland stem condition is abnormaland stem can

32、kers is below soil lineand canker lesion color is brownthendiagnosis is rhizoctonia root rotIf leaf malformation is absentand stem condition is abnormaland stem cankers is below soil lineand canker lesion color is brownthendiagnosis is rhizoctonia root rotBut in this domain, “leaf condition is norma

33、l” implies“leaf malformation is absent”!22Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Fielded applicationsThe result of learningor the learning method itselfis deployed in practical applicationsProcessing loan applicationsScreening images for oil slicksElectricity supply

34、forecastingDiagnosis of machine faultsMarketing and salesSeparating crude oil and natural gasReducing banding in rotogravure printingFinding appropriate technicians for telephone faultsScientific applications: biology, astronomy, chemistryAutomatic selection of TV programsMonitoring intensive care p

35、atients23Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Processing loan applications (American Express)Given: questionnaire withfinancial and personal informationQuestion: should money be lent?Simple statistical method covers 90% of casesBorderline cases referred to loan off

36、icersBut: 50% of accepted borderline cases defaulted!Solution: reject all borderline cases?No! Borderline cases are most active customers24Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Enter machine learning1000 training examples of borderline cases20 attributes:ageyears wi

37、th current employeryears at current addressyears with the bankother credit cards possessed,Learned rules: correct on 70% of caseshuman experts only 50%Rules could be used to explain decisions to customers25Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Screening imagesGiven:

38、 radar satellite images of coastal watersProblem: detect oil slicks in those imagesOil slicks appear as dark regions with changing size and shapeNot easy: lookalike dark regions can be caused by weather conditions (e.g. high wind)Expensive process requiring highly trained personnel26Data Mining: Pra

39、ctical Machine Learning Tools and Techniques (Chapter 1)Enter machine learningExtract dark regions from normalized imageAttributes:size of regionshape, areaintensitysharpness and jaggedness of boundariesproximity of other regionsinfo about backgroundConstraints:Few training examplesoil slicks are ra

40、re!Unbalanced data: most dark regions arent slicksRegions from same image form a batchRequirement: adjustable false-alarm rate27Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Load forecastingElectricity supply companiesneed forecast of future demandfor powerForecasts of min/

41、max load for each hour significant savingsGiven: manually constructed load model that assumes “normal” climatic conditionsProblem: adjust for weather conditionsStatic model consist of:base load for the yearload periodicity over the yeareffect of holidays28Data Mining: Practical Machine Learning Tool

42、s and Techniques (Chapter 1)Enter machine learningPrediction corrected using “most similar” daysAttributes:temperaturehumiditywind speedcloud cover readingsplus difference between actual load and predicted loadAverage difference among three “most similar” days added to static modelLinear regression

43、coefficients form attribute weights in similarity function29Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Diagnosis of machine faultsDiagnosis: classical domainof expert systemsGiven: Fourier analysis of vibrations measured at various points of a devices mountingQuestion: w

44、hich fault is present?Preventative maintenance of electromechanical motors and generatorsInformation very noisySo far: diagnosis by expert/hand-crafted rules30Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Enter machine learningAvailable: 600 faults with experts diagnosis300

45、 unsatisfactory, rest used for trainingAttributes augmented by intermediate concepts that embodied causal domain knowledgeExpert not satisfied with initial rules because they did not relate to his domain knowledgeFurther background knowledge resulted in more complex rules that were satisfactoryLearn

46、ed rules outperformed hand-crafted ones31Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Marketing and sales ICompanies precisely record massive amounts of marketing and sales dataApplications:Customer loyalty:identifying customers that are likely to defect by detecting chang

47、es in their behavior(e.g. banks/phone companies)Special offers:identifying profitable customers(e.g. reliable owners of credit cards that need extra money during the holiday season)32Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Marketing and sales IIMarket basket analysisA

48、ssociation techniques findgroups of items that tend tooccur together in atransaction(used to analyze checkout data)Historical analysis of purchasing patternsIdentifying prospective customersFocusing promotional mailouts(targeted campaigns are cheaper than mass-marketed ones)33Data Mining: Practical

49、Machine Learning Tools and Techniques (Chapter 1)Machine learning and statisticsHistorical difference (grossly oversimplified):Statistics: testing hypothesesMachine learning: finding the right hypothesisBut: huge overlapDecision trees (C4.5 and CART)Nearest-neighbor methodsToday: perspectives have c

50、onvergedMost ML algorithms employ statistical techniques34Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)StatisticiansSir Ronald Aylmer FisherBorn: 17 Feb 1890 London, EnglandDied: 29 July 1962 Adelaide, AustraliaNumerous distinguished contributions to developing the theory

51、and application of statistics for making quantitative a vast field of biologyLeo BreimanDeveloped decision trees1984 Classification and Regression Trees. Wadsworth.35Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Generalization as searchInductive learning: find a concept des

52、cription that fits the dataExample: rule sets as description languageEnormous, but finite, search spaceSimple solution:enumerate the concept spaceeliminate descriptions that do not fit examplessurviving descriptions contain target concept36Data Mining: Practical Machine Learning Tools and Techniques

53、 (Chapter 1)Enumerating the concept spaceSearch space for weather problem4 x 4 x 3 x 3 x 2 = 288 possible combinationsWith 14 rules 2.7x1034 possible rule setsOther practical problems:More than one description may surviveNo description may surviveLanguage is unable to describe target conceptor data

54、contains noiseAnother view of generalization as search:hill-climbing in description space according to pre-specified matching criterionMost practical algorithms use heuristic search that cannot guarantee to find the optimum solution37Data Mining: Practical Machine Learning Tools and Techniques (Chap

55、ter 1)BiasImportant decisions in learning systems:Concept description languageOrder in which the space is searchedWay that overfitting to the particular training data is avoidedThese form the “bias” of the search:Language biasSearch biasOverfitting-avoidance bias38Data Mining: Practical Machine Learning Tools and Techniques (Chapter 1)Language biasImportant question:is language universalor does it restrict what can be learned?Universal language can express arbitrary subsets of examplesIf language incl