数据采集和营销工具（英文版）.PPT

Knowledgediscovery-)Inparticular:JiaweiHAN,SimonFraserUniversity,whoseforthcomingbookDatamining:conceptsandtechniqueshasinfluencedthewholetutorialRajeevRASTOGIandKyuseokSHIM,LucentBellLabsDanielA.KEIM,UniversityofHalleDanielSilver,CogNovaTechnologiesTheEDBT2000boardwhoacceptedourtutorialproposal,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,3,Tutorialgoals,IntroduceyoutomajoraspectsoftheKnowledgeDiscoveryProcess,andtheoryandapplicationsofDataMiningtechnologyProvideasystematizationtothemanymanyconceptsaroundthisarea,accordingthefollowinglinestheprocessthemethodsappliedtoparadigmaticcasesthesupportenvironmenttheresearchchallengesImportantissuesthatwillbenotcoveredinthistutorial:methods:timeseries,exceptiondetection,neuralnetssystems:parallelimplementations,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,4,TutorialOutline,IntroductionandbasicconceptsMotivations,applications,theKDDprocess,thetechniquesDeeperintoDMtechnologyDecisionTreesandFraudDetectionAssociationRulesandMarketBasketAnalysisClusteringandCustomerSegmentationTrendsintechnologyKnowledgeDiscoverySupportEnvironmentTools,LanguagesandSystemsResearchchallenges,,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,5,Introduction-moduleoutline,MotivationsApplicationAreasKDDDecisionalContextKDDProcessArchitectureofaKDDsystemTheKDDstepsinshort,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,6,EvolutionofDatabaseTechnology:fromdatamanagementtodataanalysis,1960s:Datacollection,databasecreation,IMSandnetworkDBMS.1970s:Relationaldatamodel,relationalDBMSimplementation.1980s:RDBMS,advanceddatamodels(extended-relational,OO,deductive,etc.)andapplication-orientedDBMS(spatial,scientific,engineering,etc.).1990s:Datamininganddatawarehousing,multimediadatabases,andWebtechnology.,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,7,Motivations“NecessityistheMotherofInvention”,Dataexplosionproblem:Automateddatacollectiontools,maturedatabasetechnologyandinternetleadtotremendousamountsofdatastoredindatabases,datawarehousesandotherinformationrepositories.Wearedrowningininformation,butstarvingforknowledge!(JohnNaisbett)Datawarehousinganddatamining:On-lineanalyticalprocessingExtractionofinterestingknowledge(rules,regularities,patterns,constraints)fromdatainlargedatabases.,,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,8,Alsoreferredtoas:Datadredging,Dataharvesting,DataarcheologyAmultidisciplinaryfield:DatabaseStatisticsArtificialintelligenceMachinelearning,ExpertsystemsandKnowledgeAcquisitionVisualizationmethods,Arapidlyemergingfield,Arapidlyemergingfield,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,9,MotivationsforDM,AbundanceofbusinessandindustrydataCompetitivefocus-KnowledgeManagementInexpensive,powerfulcomputingenginesStrongtheoretical/mathematicalfoundationsmachinelearningstatisticalsummaryinformation(datacentraltendencyandvariation),MarketAnalysisandManagement,MarketAnalysis(2),Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,RiskAnalysis,Financeplanningandassetevaluation:cashflowanalysisandpredictioncontingentclaimanalysistoevaluateassetscross-sectionalandtimeseriesanalysis(financial-ratio,trendanalysis,etc.)Resourceplanning:summarizeandcomparetheresourcesandspendingCompetition:monitorcompetitorsandmarketdirections(CI:competitiveintelligence).groupcustomersintoclassesandclass-basedpricingproceduressetpricingstrategyinahighlycompetitivemarket,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,FraudDetection,Applications:widelyusedinhealthcare,retail,creditcardservices,telecommunications(phonecardfraud),etc.Approach:usehistoricaldatatobuildmodelsoffraudulentbehaviorandusedataminingtohelpidentifysimilarinstances.Examples:autoinsurance:detectagroupofpeoplewhostageaccidentstocollectoninsurancemoneylaundering:detectsuspiciousmoneytransactions(USTreasurysFinancialCrimesEnforcementNetwork)medicalinsurance:detectprofessionalpatientsandringofdoctorsandringofreferences,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,Moreexamples:Detectinginappropriatemedicaltreatment:AustralianHealthInsuranceCommissionidentifiesthatinmanycasesblanketscreeningtestswererequested(saveAustralian$1m/yr).Detectingtelephonefraud:Telephonecallmodel:destinationofthecall,duration,timeofdayorweek.Analyzepatternsthatdeviatefromanexpectednorm.BritishTelecomidentifieddiscretegroupsofcallerswithfrequentintra-groupcalls,especiallymobilephones,andbrokeamultimilliondollarfraud.Retail:Analystsestimatethat38%ofretailshrinkisduetodishonestemployees.,FraudDetection(2),Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,SportsIBMAdvancedScoutanalyzedNBAgamestatistics(shotsblocked,assists,andfouls)togaincompetitiveadvantageforNewYorkKnicksandMiamiHeat.AstronomyJPLandthePalomarObservatorydiscovered22quasarswiththehelpofdataminingInternetWebSurf-AidIBMSurf-AidappliesdataminingalgorithmstoWebaccesslogsformarket-relatedpagestodiscovercustomerpreferenceandbehaviorpages,analyzingeffectivenessofWebmarketing,improvingWebsiteorganization,etc.WatchforthePRIVACYpitfall!,Otherapplications,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,20,Theselectionandprocessingofdatafor:theidentificationofnovel,accurate,andusefulpatterns,andthemodelingofreal-worldphenomena.DataminingisamajorcomponentoftheKDDprocess-automateddiscoveryofpatternsandthedevelopmentofpredictiveandexplanatorymodels.,WhatisKDD?Aprocess!,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,21,TheKDDprocess,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,22,TheKDDProcess,CoreProblems&ApproachesProblems:identificationofrelevantdatarepresentationofdatasearchforvalidpatternormodelApproaches:top-downdeductionbyexpertinteractivevisualizationofdata/models*bottom-upinductionfromdata*,DataMining,,OLAP,,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,Learningtheapplicationdomain:relevantpriorknowledgeandgoalsofapplicationDataconsolidation:CreatingatargetdatasetSelectionandPreprocessingDatacleaning:(maytake60%ofeffort!)Datareductionandprojection:findusefulfeatures,dimensionality/variablereduction,invariantrepresentation.Choosingfunctionsofdataminingsummarization,classification,regression,association,clustering.Choosingtheminingalgorithm(s)Datamining:searchforpatternsofinterestInterpretationandevaluation:analysisofresults.visualization,transformation,removingredundantpatterns,…Useofdiscoveredknowledge,ThestepsoftheKDDprocess,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,24,,IdentifyProblemorOpportunity,MeasureeffectofAction,ActonKnowledge,,,,,,Knowledge,Results,Strategy,Problem,Thevirtuouscycle,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,25,Applications,operations,techniques,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,26,RolesintheKDDprocess,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,27,,,,,,,,,Increasingpotentialtosupportbusinessdecisions,EndUser,BusinessAnalyst,DataAnalyst,DBA,MakingDecisions,DataPresentation,VisualizationTechniques,DataMining,InformationDiscovery,DataExploration,OLAP,MDA,StatisticalAnalysis,QueryingandReporting,DataWarehouses/DataMarts,DataSources,Paper,Files,InformationProviders,DatabaseSystems,OLTP,,Dataminingandbusinessintelligence,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,28,GraphicalUserInterface,DataConsolidation,SelectionandPreprocessing,DataMining,InterpretationandEvaluation,,,,,Warehouse,Knowledge,,,,,,,,,,,,,DataSources,ArchitectureofaKDDsystem,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,29,Abusinessintelligenceenvironment,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,30,TheKDDprocess,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,31,GarbageinGarbageoutThequalityofresultsrelatesdirectlytoqualityofthedata50%-70%ofKDDprocesseffortisspentondataconsolidationandpreparationMajorjustificationforacorporatedatawarehouse,,Dataconsolidationandpreparation,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,32,Fromdatasourcestoconsolidateddatarepository,,,,,RDBMS,,,,,LegacyDBMS,,,,,FlatFiles,DataConsolidationandCleansing,,,,,Warehouse,,,,,Object/RelationDBMSMultidimensionalDBMSDeductiveDatabaseFlatfiles,,,,,External,,Dataconsolidation,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,33,DeterminepreliminarylistofattributesConsolidatedataintoworkingdatabaseInternalandExternalsourcesEliminateorestimatemissingvaluesRemoveoutliers(obviousexceptions)Determinepriorprobabilitiesofcategoriesanddealwithvolumebias,Dataconsolidation,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,34,SelectionandPreprocessing,DataMining,InterpretationandEvaluation,DataConsolidation,,,,,,,,,,,,,,,,,,,,,,,,,Knowledge,,p(x)=0.02,,,,,,,,,,Warehouse,,,,,,,TheKDDprocess,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,35,GenerateasetofexampleschoosesamplingmethodconsidersamplecomplexitydealwithvolumebiasissuesReduceattributedimensionalityremoveredundantand/orcorrelatingattributescombineattributes(sum,multiply,difference)ReduceattributevaluerangesgroupsymbolicdiscretevaluesquantizecontinuousnumericvaluesTransformdatade-correlateandnormalizevaluesmaptime-seriesdatatostaticrepresentationOLAPandvisualizationtoolsplaykeyrole,Dataselectionandpreprocessing,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,36,SelectionandPreprocessing,DataMining,InterpretationandEvaluation,DataConsolidation,,,,,,,,,,,,,,,,,,,,,,,,,Knowledge,,p(x)=0.02,,,,,,,,,,Warehouse,,,,,,,TheKDDprocess,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,37,Dataminingtasksandmethods,AutomatedExploration/Discoverye.g..discoveringnewmarketsegmentsclusteringanalysisPrediction/Classificatione.g..forecastinggrosssalesgivencurrentfactorsregression,neuralnetworks,geneticalgorithms,decisiontreesExplanation/Descriptione.g..characterizingcustomersbydemographicsandpurchasehistorydecisiontrees,associationrules,ifage>35andincome<$35kthen...,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,38,Clustering:partitioningasetofdataintoasetofclasses,calledclusters,whosememberssharesomeinterestingcommonproperties.Distance-basednumericalclusteringmetricgroupingofexamples(K-NN)graphicalvisualizationcanbeusedBayesianclusteringsearchforthenumberofclasseswhichresultinbestfitofaprobabilitydistributiontothedataAutoClass(NASA)oneofbestexamples,Automatedexplorationanddiscovery,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,39,LearningapredictivemodelClassificationofanewcase/sampleManymethods:ArtificialneuralnetworksInductivedecisiontreeandrulesystemsGeneticalgorithmsNearestneighborclusteringalgorithmsStatistical(parametric,andnon-parametric),Predictionandclassification,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,40,Theobjectiveoflearningistoachievegoodgeneralizationtonewunseencases.GeneralizationcanbedefinedasamathematicalinterpolationorregressionoverasetoftrainingpointsModelscanbevalidatedwithapreviouslyunseentestsetorusingcross-validationmethods,,,,,,,,,,,f(x),x,Generalizationandregression,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,41,Classificationandprediction,Classifydatabasedonthevaluesofatargetattribute,e.g.,classifycountriesbasedonclimate,orclassifycarsbasedongasmileage.Useobtainedmodeltopredictsomeunknownormissingattributevaluesbasedonotherinformation.,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,42,Objective:DevelopageneralmodelorhypothesisfromspecificexamplesFunctionapproximation(curvefitting)Classification(conceptlearning,patternrecognition),A,B,,Summarizing:inductivemodeling=learning,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,43,Learnageneralizedhypothesis(model)fromselecteddataDescription/InterpretationofmodelprovidesnewknowledgeMethods:InductivedecisiontreeandrulesystemsAssociationrulesystemsLinkAnalysis…,Explanationanddescription,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,44,GenerateamodelofnormalactivityDeviationfrommodelcausesalertMethods:ArtificialneuralnetworksInductivedecisiontreeandrulesystemsStatisticalmethodsVisualizationtools,Exception/deviationdetection,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,45,Outlierandexceptiondataanalysis,Time-seriesanalysis(trendanddeviation):Trendanddeviationanalysis:regression,sequentialpattern,similarsequences,trendanddeviation,e.g.,stockanalysis.Similarity-basedpattern-directedanalysisFullvs.partialperiodicityanalysisOtherpattern-directedorstatisticalanalysis,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,46,SelectionandPreprocessing,DataMining,InterpretationandEvaluation,DataConsolidationandWarehousing,,,,,,,,,,,,,,,,,,,,,,,,,Knowledge,,p(x)=0.02,,,,,,,,,,Warehouse,,,,,,,TheKDDprocess,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,Adataminingsystem/querymaygeneratethousandsofpatterns,notallofthemareinteresting.Interestingnessmeasures:easilyunderstoodbyhumansvalidonnewortestdatawithsomedegreeofcertainty.potentiallyusefulnovel,orvalidatessomehypothesisthatauserseekstoconfirmObjectivevs.subjectiveinterestingnessmeasuresObjective:basedonstatisticsandstructuresofpatterns,e.g.,support,confidence,etc.Subjective:basedonuser’sbeliefsinthedata,e.g.,unexpectedness,novelty,etc.,Areallthediscoveredpatterninteresting?,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,Findalltheinterestingpatterns:Completeness.Canadataminingsystemfindalltheinterestingpatterns?Searchforonlyinterestingpatterns:Optimization.Canadataminingsystemfindonlytheinterestingpatterns?ApproachesFirstgenerateallthepatternsandthenfilterouttheuninterestingones.Generateonlytheinterestingpatterns-miningqueryoptimization.,Completenessvs.optimization,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,49,EvaluationStatisticalvalidationandsignificancetestingQualitativereviewbyexpertsinthefieldPilotsurveystoevaluatemodelaccuracyInterpretationInductivetreeandrulemodelscanbereaddirectlyClusteringresultscanbegraphedandtabledCodecanbeautomaticallygeneratedbysomesystems(IDTs,Regressionmodels),Interpretationandevaluation,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,50,Visualizationtoolscanbeveryhelpfulsensitivityanalysis(I/Orelationship)histogramsofvaluedistributiontime-seriesplotsandanimationrequirestrainingandpractice,,,,Response,Velocity,Temp,,,,,,,,,,,,,,,,,,Interpretationandevaluation,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,1989IJCAIWorkshoponKDDKnowledgeDiscoveryinDatabases(G.Piatetsky-ShapiroandW.Frawley,eds.,1991)1991-1994WorkshopsonKDDAdvancesinKnowledgeDiscoveryandDataMining(U.Fayyad,G.Piatetsky-Shapiro,P.Smyth,andR.Uthurusamy,eds.,1996)1995-1998AAAIInt.Conf.onKDDandDM(KDD’95-98)JournalofDataMiningandKnowledgeDiscovery(1997)1998ACMSIGKDD1999SIGKDD’99Conf.,Importantdatesofdatamining,Konstanz,27-28.3.2000,EDBT2000tutorial-Intro,52,References-general,P.AdriaansandD.Zantinge.DataMining.Addison-Wesley:Harlow,England,1996.M.S.Chen,J.Han,andP.S.Yu.Datamining:Anoverviewfromadatabaseperspective.IEEETrans.KnowledgeandDataEngineering,8:866-883,1996.U.M.Fayyad,G.Piatetsky-Shapiro,P.Smyth,andR.Uthurusamy.AdvancesinKnowledgeDiscoveryandDataMining.AAAI/MITPress,1996.J.HanandM.Kamber.DataMining:ConceptsandTechniques.MorganKaufmann,2000.Toappear.T.ImielinskiandH.Mannila.Adatabaseperspectiveonknowledgediscovery.CommunicationsofACM,39:58-64,1996.G.Piatetsky-Shapiro,U.Fayyad,andP.Smith.Fromdataminingtoknowledgediscovery:Anoverview.InU.M.Fayyad,etal.(eds.),AdvancesinKnowledgeDiscoveryandDataMining,1-35.AAAI/MITPress,1996.G.Piatetsky-ShapiroandW.J.Frawley.KnowledgeDiscoveryinDatabases.AAAI/MITPress,1991.MichaelBerry&GordonLinoff.DataMiningTechniquesforMarketing,SalesandCustomerSu