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

Knowledgediscovery&datamining

Tools,methods,andexperiencesFoscaGiannottiand

DinoPedreschiPisaKDDLabCNUCE-CNR&Univ.Pisahttp://www-kdd.di.unipi.it/Atutorial@EDBT2000Konstanz,27-28.3.2000EDBT2000tutorial-Intro2ContributorsandacknowledgementsThepeople@PisaKDDLab:FrancescoBONCHI,GiuseppeMANCO,MircoNANNI,ChiaraRENSO,SalvatoreRUGGIERI,FrancoTURINIandmanystudentsThemanyKDDtutorialistsandteacherswhichmadetheirslidesavailableontheweb(allofthemlistedinbibliography);-)Inparticular:JiaweiHAN,SimonFraserUniversity,whoseforthcomingbookDatamining:conceptsandtechniqueshasinfluencedthewholetutorialRajeevRASTOGIandKyuseokSHIM,LucentBellLabsDanielA.KEIM,UniversityofHalleDanielSilver,CogNovaTechnologiesTheEDBT2000boardwhoacceptedourtutorialproposalKonstanz,27-28.3.2000EDBT2000tutorial-Intro3TutorialgoalsIntroduceyoutomajoraspectsoftheKnowledgeDiscoveryProcess,andtheoryandapplicationsofDataMiningtechnologyProvideasystematizationtothemanymanyconceptsaroundthisarea,accordingthefollowinglinestheprocessthemethodsappliedtoparadigmaticcasesthesupportenvironmenttheresearchchallengesImportantissuesthatwillbenotcoveredinthistutorial:methods:timeseries,exceptiondetection,neuralnetssystems:parallelimplementationsKonstanz,27-28.3.2000EDBT2000tutorial-Intro4TutorialOutlineIntroductionandbasicconceptsMotivations,applications,theKDDprocess,thetechniquesDeeperintoDMtechnologyDecisionTreesandFraudDetectionAssociationRulesandMarketBasketAnalysisClusteringandCustomerSegmentationTrendsintechnologyKnowledgeDiscoverySupportEnvironmentTools,LanguagesandSystemsResearchchallengesKonstanz,27-28.3.2000EDBT2000tutorial-Intro5Introduction-moduleoutlineMotivationsApplicationAreasKDDDecisionalContextKDDProcessArchitectureofaKDDsystemTheKDDstepsinshortKonstanz,27-28.3.2000EDBT2000tutorial-Intro6EvolutionofDatabaseTechnology:

fromdatamanagementtodataanalysis1960s: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.2000EDBT2000tutorial-Intro7Motivations

“NecessityistheMotherofInvention”Dataexplosionproblem:

Automateddatacollectiontools,maturedatabasetechnologyandinternetleadtotremendousamountsofdatastoredindatabases,datawarehousesandotherinformationrepositories.

Wearedrowningininformation,butstarvingforknowledge!

(JohnNaisbett)Datawarehousinganddatamining:On-lineanalyticalprocessingExtractionofinterestingknowledge(rules,regularities,patterns,constraints)fromdatainlargedatabases.Konstanz,27-28.3.2000EDBT2000tutorial-Intro8Alsoreferredtoas:

Datadredging,Dataharvesting,DataarcheologyAmultidisciplinaryfield:DatabaseStatisticsArtificialintelligenceMachinelearning,ExpertsystemsandKnowledgeAcquisitionVisualizationmethodsArapidlyemergingfieldArapidlyemergingfieldKonstanz,27-28.3.2000EDBT2000tutorial-Intro9MotivationsforDM

AbundanceofbusinessandindustrydataCompetitivefocus-KnowledgeManagementInexpensive,powerfulcomputingenginesStrongtheoretical/mathematicalfoundationsmachinelearning&logicstatisticsdatabasemanagementsystemsKonstanz,27-28.3.2000EDBT2000tutorial-Intro10WhatisDMusefulfor?MarketingDatabaseMarketingDataWarehousingKDD&DataMining

Increaseknowledgetobasedecisionupon.E.g.,impactonmarketingKonstanz,27-28.3.2000EDBT2000tutorial-Intro11TheValueChain

Data

Customerdata

Storedata

DemographicalData

Geographicaldata

Information

XlivesinZSisYyearsoldXandSmovedWhasmoneyinZ

Knowledge

AquantityYofproductAisusedinregionZ

CustomersofclassYusex%ofCduringperiodD

Decision

PromoteproductAinregionZ.

MailadstofamiliesofprofilePCross-sellserviceBtoclientsCKonstanz,27-28.3.2000EDBT2000tutorial-Intro12ApplicationAreasandOpportunitiesMarketing:segmentation,customertargeting,...Finance:investmentsupport,portfoliomanagementBanking&Insurance:creditandpolicyapprovalSecurity:frauddetectionScienceandmedicine:hypothesisdiscovery,

prediction,classification,diagnosisManufacturing:processmodeling,qualitycontrol, resourceallocationEngineering:simulationandanalysis,pattern recognition,signalprocessingInternet:smartsearchengines,webmarketingKonstanz,27-28.3.2000EDBT2000tutorial-Intro13ClassesofapplicationsMarketanalysistargetmarketing,customerrelationmanagement,marketbasketanalysis,crossselling,marketsegmentation.RiskanalysisForecasting,customerretention,improvedunderwriting,qualitycontrol,competitiveanalysis.FrauddetectionText(newsgroup,email,documents)andWebanalysis.Konstanz,27-28.3.2000EDBT2000tutorial-IntroMarketAnalysisWherearethedatasourcesforanalysis?Creditcardtransactions,loyaltycards,discountcoupons,customercomplaintcalls,plus(public)lifestylestudies.TargetmarketingFindclustersof“model”customerswhosharethesamecharacteristics:interest,incomelevel,spendinghabits,etc.DeterminecustomerpurchasingpatternsovertimeConversionofsingletoajointbankaccount:marriage,etc.Cross-marketanalysisAssociations/co-relationsbetweenproductsalesPredictionbasedontheassociationinformation.Konstanz,27-28.3.2000EDBT2000tutorial-IntroCustomerprofilingdataminingcantellyouwhattypesofcustomersbuywhatproducts(clusteringorclassification).IdentifyingcustomerrequirementsidentifyingthebestproductsfordifferentcustomersusepredictiontofindwhatfactorswillattractnewcustomersProvidessummaryinformationvariousmultidimensionalsummaryreports;statisticalsummaryinformation(datacentraltendencyandvariation)MarketAnalysisandManagementMarketAnalysis(2)Konstanz,27-28.3.2000EDBT2000tutorial-IntroRiskAnalysisFinanceplanningandassetevaluation:cashflowanalysisandpredictioncontingentclaimanalysistoevaluateassetscross-sectionalandtimeseriesanalysis(financial-ratio,trendanalysis,etc.)Resourceplanning:summarizeandcomparetheresourcesandspendingCompetition:monitorcompetitorsandmarketdirections(CI:competitiveintelligence).groupcustomersintoclassesandclass-basedpricingproceduressetpricingstrategyinahighlycompetitivemarketKonstanz,27-28.3.2000EDBT2000tutorial-IntroFraudDetectionApplications:widelyusedinhealthcare,retail,creditcardservices,telecommunications(phonecardfraud),etc.Approach:usehistoricaldatatobuildmodelsoffraudulentbehaviorandusedataminingtohelpidentifysimilarinstances.Examples:autoinsurance:detectagroupofpeoplewhostageaccidentstocollectoninsurancemoneylaundering:detectsuspiciousmoneytransactions(USTreasury'sFinancialCrimesEnforcementNetwork)medicalinsurance:detectprofessionalpatientsandringofdoctorsandringofreferencesKonstanz,27-28.3.2000EDBT2000tutorial-IntroMoreexamples:Detectinginappropriatemedicaltreatment:AustralianHealthInsuranceCommissionidentifiesthatinmanycasesblanketscreeningtestswererequested(saveAustralian$1m/yr).Detectingtelephonefraud:Telephonecallmodel:destinationofthecall,duration,timeofdayorweek.Analyzepatternsthatdeviatefromanexpectednorm.BritishTelecomidentifieddiscretegroupsofcallerswithfrequentintra-groupcalls,especiallymobilephones,andbrokeamultimilliondollarfraud.Retail:Analystsestimatethat38%ofretailshrinkisduetodishonestemployees.FraudDetection(2)Konstanz,27-28.3.2000EDBT2000tutorial-IntroSportsIBMAdvancedScoutanalyzedNBAgamestatistics(shotsblocked,assists,andfouls)togaincompetitiveadvantageforNewYorkKnicksandMiamiHeat.AstronomyJPLandthePalomarObservatorydiscovered22quasarswiththehelpofdataminingInternetWebSurf-AidIBMSurf-AidappliesdataminingalgorithmstoWebaccesslogsformarket-relatedpagestodiscovercustomerpreferenceandbehaviorpages,analyzingeffectivenessofWebmarketing,improvingWebsiteorganization,etc.WatchforthePRIVACYpitfall!OtherapplicationsKonstanz,27-28.3.2000EDBT2000tutorial-Intro20Theselectionandprocessingofdatafor:theidentificationofnovel,accurate,andusefulpatterns,andthemodelingofreal-worldphenomena.Datamining

isamajorcomponentoftheKDDprocess-automateddiscoveryofpatternsandthedevelopmentofpredictiveandexplanatorymodels.WhatisKDD?Aprocess!Konstanz,27-28.3.2000EDBT2000tutorial-Intro21SelectionandPreprocessingDataMiningInterpretationandEvaluationDataConsolidationKnowledgep(x)=0.02WarehouseDataSourcesPatterns&ModelsPreparedDataConsolidatedDataTheKDDprocessKonstanz,27-28.3.2000EDBT2000tutorial-Intro22TheKDDProcessCoreProblems&ApproachesProblems:identificationofrelevantdatarepresentationofdatasearchforvalidpatternormodelApproaches:top-downdeductionbyexpertinteractivevisualizationofdata/models*bottom-upinduction

fromdata*DataMiningOLAPKonstanz,27-28.3.2000EDBT2000tutorial-IntroLearningtheapplicationdomain:relevantpriorknowledgeandgoalsofapplicationDataconsolidation:CreatingatargetdatasetSelectionandPreprocessing

Datacleaning:(maytake60%ofeffort!)Datareductionandprojection:findusefulfeatures,dimensionality/variablereduction,invariantrepresentation.Choosingfunctionsofdataminingsummarization,classification,regression,association,clustering.Choosingtheminingalgorithm(s)Datamining:searchforpatternsofinterestInterpretationandevaluation:analysisofresults.visualization,transformation,removingredundantpatterns,…UseofdiscoveredknowledgeThestepsoftheKDDprocessKonstanz,27-28.3.2000EDBT2000tutorial-Intro24IdentifyProblemorOpportunityMeasureeffectofActionActonKnowledgeKnowledgeResultsStrategyProblemThevirtuouscycleKonstanz,27-28.3.2000EDBT2000tutorial-Intro25Applications,operations,techniquesKonstanz,27-28.3.2000EDBT2000tutorial-Intro26RolesintheKDDprocessKonstanz,27-28.3.2000EDBT2000tutorial-Intro27IncreasingpotentialtosupportbusinessdecisionsEndUserBusinessAnalystDataAnalystDBA

MakingDecisionsDataPresentationVisualizationTechniquesDataMiningInformationDiscoveryDataExplorationOLAP,MDAStatisticalAnalysis,QueryingandReportingDataWarehouses/DataMartsDataSourcesPaper,Files,InformationProviders,DatabaseSystems,OLTPDataminingandbusinessintelligenceKonstanz,27-28.3.2000EDBT2000tutorial-Intro28GraphicalUserInterfaceDataConsolidationSelectionandPreprocessingDataMiningInterpretationandEvaluationWarehouseKnowledgeDataSourcesArchitectureofaKDDsystemKonstanz,27-28.3.2000EDBT2000tutorial-Intro29AbusinessintelligenceenvironmentKonstanz,27-28.3.2000EDBT2000tutorial-Intro30SelectionandPreprocessingDataMiningInterpretationandEvaluationDataConsolidationKnowledgep(x)=0.02WarehouseDataSourcesPatterns&ModelsPreparedDataConsolidatedDataTheKDDprocessKonstanz,27-28.3.2000EDBT2000tutorial-Intro31GarbageinGarbageout

Thequalityofresultsrelatesdirectlytoqualityofthedata50%-70%ofKDDprocesseffortisspentondataconsolidationandpreparationMajorjustificationforacorporatedatawarehouseDataconsolidationandpreparationKonstanz,27-28.3.2000EDBT2000tutorial-Intro32FromdatasourcestoconsolidateddatarepositoryRDBMSLegacyDBMSFlatFilesDataConsolidationandCleansingWarehouseObject/RelationDBMSMultidimensionalDBMSDeductiveDatabaseFlatfilesExternalDataconsolidationKonstanz,27-28.3.2000EDBT2000tutorial-Intro33DeterminepreliminarylistofattributesConsolidatedataintoworkingdatabaseInternalandExternalsourcesEliminateorestimatemissingvaluesRemoveoutliers(obviousexceptions)DeterminepriorprobabilitiesofcategoriesanddealwithvolumebiasDataconsolidationKonstanz,27-28.3.2000EDBT2000tutorial-Intro34SelectionandPreprocessingDataMiningInterpretationandEvaluationDataConsolidationKnowledgep(x)=0.02WarehouseTheKDDprocessKonstanz,27-28.3.2000EDBT2000tutorial-Intro35GenerateasetofexampleschoosesamplingmethodconsidersamplecomplexitydealwithvolumebiasissuesReduceattributedimensionalityremoveredundantand/orcorrelatingattributescombineattributes(sum,multiply,difference)ReduceattributevaluerangesgroupsymbolicdiscretevaluesquantizecontinuousnumericvaluesTransformdatade-correlateandnormalizevaluesmaptime-seriesdatatostaticrepresentationOLAPandvisualizationtoolsplaykeyroleDataselectionandpreprocessingKonstanz,27-28.3.2000EDBT2000tutorial-Intro36SelectionandPreprocessingDataMining

InterpretationandEvaluationDataConsolidationKnowledgep(x)=0.02WarehouseTheKDDprocessKonstanz,27-28.3.2000EDBT2000tutorial-Intro37DataminingtasksandmethodsAutomatedExploration/Discoverye.g..discoveringnewmarketsegmentsclusteringanalysisPrediction/Classificatione.g..forecastinggrosssalesgivencurrentfactorsregression,neuralnetworks,geneticalgorithms,

decisiontreesExplanation/Descriptione.g..characterizingcustomersbydemographics

andpurchasehistorydecisiontrees,associationrulesx1x2f(x)xifage>35andincome<$35kthen...Konstanz,27-28.3.2000EDBT2000tutorial-Intro38Clustering:partitioningasetofdataintoasetofclasses,calledclusters,whosememberssharesomeinterestingcommonproperties.Distance-basednumericalclusteringmetricgroupingofexamples(K-NN)graphicalvisualizationcanbeusedBayesianclusteringsearchforthenumberofclasseswhichresultinbestfitofaprobabilitydistributiontothedataAutoClass(NASA)oneofbestexamplesAutomatedexplorationanddiscoveryKonstanz,27-28.3.2000EDBT2000tutorial-Intro39LearningapredictivemodelClassificationofanewcase/sampleManymethods:ArtificialneuralnetworksInductivedecisiontreeandrulesystemsGeneticalgorithmsNearestneighborclusteringalgorithmsStatistical(parametric,andnon-parametric)PredictionandclassificationKonstanz,27-28.3.2000EDBT2000tutorial-Intro40Theobjectiveoflearningistoachievegoodgeneralizationtonewunseencases.GeneralizationcanbedefinedasamathematicalinterpolationorregressionoverasetoftrainingpointsModelscanbevalidatedwithapreviouslyunseentestsetorusingcross-validationmethodsf(x)xGeneralizationandregressionKonstanz,27-28.3.2000EDBT2000tutorial-Intro41ClassificationandpredictionClassifydatabasedonthevaluesofatargetattribute,e.g.,classifycountriesbasedonclimate,orclassifycarsbasedongasmileage.Useobtainedmodeltopredictsomeunknownormissingattributevaluesbasedonotherinformation.Konstanz,27-28.3.2000EDBT2000tutorial-Intro42Objective:

Developageneralmodelor hypothesisfromspecificexamplesFunctionapproximation(curvefitting)Classification(conceptlearning,patternrecognition)x1x2ABf(x)xSummarizing:inductivemodeling=learningKonstanz,27-28.3.2000EDBT2000tutorial-Intro43Learnageneralizedhypothesis(model)fromselecteddataDescription/InterpretationofmodelprovidesnewknowledgeMethods:InductivedecisiontreeandrulesystemsAssociationrulesystemsLinkAnalysis…ExplanationanddescriptionKonstanz,27-28.3.2000EDBT2000tutorial-Intro44GenerateamodelofnormalactivityDeviationfrommodelcausesalertMethods:ArtificialneuralnetworksInductivedecisiontreeandrulesystemsStatisticalmethodsVisualizationtoolsException/deviationdetectionKonstanz,27-28.3.2000EDBT2000tutorial-Intro45OutlierandexceptiondataanalysisTime-seriesanalysis(trendanddeviation):Trendanddeviationanalysis:regression,sequentialpattern,similarsequences,trendanddeviation,e.g.,stockanalysis.Similarity-basedpattern-directedanalysisFullvs.partialperiodicityanalysisOtherpattern-directedorstatisticalanalysisKonstanz,27-28.3.2000EDBT2000tutorial-Intro46SelectionandPreprocessingDataMiningInterpretationandEvaluationDataConsolidationandWarehousingKnowledgep(x)=0.02WarehouseTheKDDprocessKonstanz,27-28.3.2000EDBT2000tutorial-IntroAdataminingsystem/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.2000EDBT2000tutorial-IntroFindalltheinterestingpatterns:Completeness.Canadataminingsystemfindalltheinterestingpatterns?Searchforonlyinterestingpatterns:Optimization.Canadataminingsystemfindonlytheinterestingpatterns?ApproachesFirstgenerateallthepatternsandthenfilterouttheuninterestingones.Generateonlytheinterestingpatterns-miningqueryoptimization.Completenessvs.optimizationKonstanz,27-28.3.2000EDBT2000tutorial-Intro49EvaluationStatisticalvalidationandsignificancetestingQualitativereviewbyexpertsinthefieldPilotsurveystoevaluatemodelaccuracyInterpretationInductivetreeandrulemodelscanbereaddirectlyClusteringresultscanbegraphedandtabledCodecanbeautomaticallygeneratedbysomesystems(IDTs,Regressionmodels)InterpretationandevaluationKonstanz,27-28.3.2000EDBT2000tutorial-Intro50Visualizationtoolscanbeveryhelpfulsensitivityanalysis(I/Orelationship)histogramsofvaluedistributiontime-seriesplotsandanimationrequirestrainingandpracticeResponseVelocityTempInterpretationandevaluationKonstanz,27-28.3.2000EDBT2000tutorial-Intro1989IJCAIWorkshoponKDDKnowledgeDiscoveryinDatabases(G.Piatetsky-ShapiroandW.Frawley,eds.,1991)1991-1994WorkshopsonKDDAdvancesinKnowledgeDiscoveryandDataMining(U.Fayyad,G.Piatetsky-Shapiro,P.Smyth,andR.Uthurusam