Knowledgediscovery&datamining

Tools,methods,andexperiencesFoscaGiannottiand

DinoPedreschiPisaKDDLabCNUCE-CNR&Univ.Pisahttp://www-kdd.di.unipi.it/Atutorial@EDBT2000EDBT2000tutorial1Konstanz,March2000ContributorsandacknowledgementsThepeople@PisaKDDLab:FrancescoBONCHI,GiuseppeMANCO,MircoNANNI,ChiaraRENSO,SalvatoreRUGGIERI,FrancoTURINIandmanystudentsThemanyKDDtutorialistsandteacherswhichmadetheirslidesavailableontheweb(allofthemlistedinbibliography);-)Inparticular:JiaweiHAN,SimonFraserUniversity,whoseforthcomingbookDatamining:conceptsandtechniqueshasinfluencedthewholetutorialRajeevRASTOGIandKyuseokSHIM,LucentBellLabsDanielA.KEIM,UniversityofHalleDanielSilver,CogNovaTechnologiesTheEDBT2000boardwhoacceptedourtutorialproposalKonstanz,27-28.3.20002EDBT2000tutorial-IntroTutorialgoalsIntroduceyoutomajoraspectsoftheKnowledgeDiscoveryProcess,andtheoryandapplicationsofDataMiningtechnologyProvideasystematizationtothemanymanyconceptsaroundthisarea,accordingthefollowinglinestheprocessthemethodsappliedtoparadigmaticcasesthesupportenvironmenttheresearchchallengesImportantissuesthatwillbenotcoveredinthistutorial:methods:timeseries,exceptiondetection,neuralnetssystems:parallelimplementationsKonstanz,27-28.3.20003EDBT2000tutorial-IntroTutorialOutlineIntroductionandbasicconceptsMotivations,applications,theKDDprocess,thetechniquesDeeperintoDMtechnologyDecisionTreesandFraudDetectionAssociationRulesandMarketBasketAnalysisClusteringandCustomerSegmentationTrendsintechnologyKnowledgeDiscoverySupportEnvironmentTools,LanguagesandSystemsResearchchallengesKonstanz,27-28.3.20004EDBT2000tutorial-IntroIntroduction-moduleoutlineMotivationsApplicationAreasKDDDecisionalContextKDDProcessArchitectureofaKDDsystemTheKDDstepsinshortKonstanz,27-28.3.20005EDBT2000tutorial-IntroEvolutionofDatabaseTechnology:

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.20006EDBT2000tutorial-IntroMotivations

“NecessityistheMotherofInvention”Dataexplosionproblem:

Automateddatacollectiontools,maturedatabasetechnologyandinternetleadtotremendousamountsofdatastoredindatabases,datawarehousesandotherinformationrepositories.

Wearedrowningininformation,butstarvingforknowledge!

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

Datadredging,Dataharvesting,DataarcheologyAmultidisciplinaryfield:DatabaseStatisticsArtificialintelligenceMachinelearning,ExpertsystemsandKnowledgeAcquisitionVisualizationmethodsArapidlyemergingfieldArapidlyemergingfieldKonstanz,27-28.3.20008EDBT2000tutorial-IntroMotivationsforDM

AbundanceofbusinessandindustrydataCompetitivefocus-KnowledgeManagementInexpensive,powerfulcomputingenginesStrongtheoretical/mathematicalfoundationsmachinelearning&logicstatisticsdatabasemanagementsystemsKonstanz,27-28.3.20009EDBT2000tutorial-IntroWhatisDMusefulfor?MarketingDatabaseMarketingDataWarehousingKDD&DataMining

Increaseknowledgetobasedecisionupon.E.g.,impactonmarketingKonstanz,27-28.3.200010EDBT2000tutorial-IntroTheValueChain

Data

Customerdata

Storedata

DemographicalData

Geographicaldata

Information

XlivesinZSisYyearsoldXandSmovedWhasmoneyinZ

Knowledge

AquantityYofproductAisusedinregionZ

CustomersofclassYusex%ofCduringperiodD

Decision

PromoteproductAinregionZ.

MailadstofamiliesofprofilePCross-sellserviceBtoclientsCKonstanz,27-28.3.200011EDBT2000tutorial-IntroApplicationAreasandOpportunitiesMarketing:

segmentation,customertargeting,...Finance:investmentsupport,portfoliomanagementBanking&Insurance:creditandpolicyapprovalSecurity:

frauddetectionScienceandmedicine:

hypothesisdiscovery,

prediction,classification,diagnosisManufacturing:

processmodeling,qualitycontrol, resourceallocationEngineering:

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

isamajorcomponentoftheKDDprocess-automateddiscoveryofpatternsandthedevelopmentofpredictiveandexplanatorymodels.WhatisKDD?Aprocess!Konstanz,27-28.3.200020EDBT2000tutorial-IntroSelectionand

PreprocessingDataMiningInterpretationandEvaluationData

ConsolidationKnowledgep(x)=0.02WarehouseDataSourcesPatterns&

ModelsPreparedDataConsolidatedDataTheKDDprocessKonstanz,27-28.3.200021EDBT2000tutorial-IntroTheKDDProcessCoreProblems&ApproachesProblems:identificationofrelevantdatarepresentationofdatasearchforvalidpatternormodelApproaches:top-downdeductionbyexpertinteractivevisualizationofdata/models*bottom-upinduction

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

Datacleaning:(maytake60%ofeffort!)Datareductionandprojection:findusefulfeatures,dimensionality/variablereduction,invariantrepresentation.Choosingfunctionsofdataminingsummarization,classification,regression,association,clustering.Choosingtheminingalgorithm(s)Datamining:searchforpatternsofinterestInterpretationandevaluation:analysisofresults.visualization,transformation,removingredundantpatterns,…UseofdiscoveredknowledgeThestepsoftheKDDprocessIdentifyProblemor

OpportunityMeasureeffectofActionActonKnowledgeKnowledgeResultsStrategyProblemThevirtuouscycleKonstanz,27-28.3.200024EDBT2000tutorial-IntroApplications,operations,techniquesKonstanz,27-28.3.200025EDBT2000tutorial-IntroRolesintheKDDprocessKonstanz,27-28.3.200026EDBT2000tutorial-IntroIncreasingpotentialtosupportbusinessdecisionsEndUserBusinessAnalystDataAnalystDBA

MakingDecisionsDataPresentationVisualizationTechniquesDataMiningInformationDiscoveryDataExplorationOLAP,MDAStatisticalAnalysis,QueryingandReportingDataWarehouses/DataMartsDataSourcesPaper,Files,InformationProviders,DatabaseSystems,OLTPDataminingandbusinessintelligenceKonstanz,27-28.3.200027EDBT2000tutorial-IntroGraphicalUserInterfaceDataConsolidationSelectionandPreprocessingDataMiningInterpretationandEvaluationWarehouseKnowledgeDataSourcesArchitectureofaKDDsystemKonstanz,27-28.3.200028EDBT2000tutorial-IntroAbusinessintelligenceenvironmentKonstanz,27-28.3.200029EDBT2000tutorial-IntroSelectionand

PreprocessingDataMiningInterpretationandEvaluationData

ConsolidationKnowledgep(x)=0.02WarehouseDataSourcesPatterns&

ModelsPreparedDataConsolidatedDataTheKDDprocessKonstanz,27-28.3.200030EDBT2000tutorial-IntroGarbageinGarbageout

Thequalityofresultsrelatesdirectlytoqualityofthedata50%-70%ofKDDprocesseffortisspentondataconsolidationandpreparationMajorjustificationforacorporatedatawarehouseDataconsolidationandpreparationKonstanz,27-28.3.200031EDBT2000tutorial-IntroFromdatasourcestoconsolidateddatarepositoryRDBMSLegacyDBMSFlatFilesDataConsolidationandCleansingWarehouseObject/RelationDBMS

MultidimensionalDBMS

DeductiveDatabase

FlatfilesExternalDataconsolidationKonstanz,27-28.3.200032EDBT2000tutorial-IntroDeterminepreliminarylistofattributesConsolidatedataintoworkingdatabaseInternalandExternalsourcesEliminateorestimatemissingvaluesRemoveoutliers(obviousexceptions)DeterminepriorprobabilitiesofcategoriesanddealwithvolumebiasDataconsolidationKonstanz,27-28.3.200033EDBT2000tutorial-IntroSelectionand

PreprocessingDataMiningInterpretationandEvaluationDataConsolidationKnowledgep(x)=0.02WarehouseTheKDDprocessKonstanz,27-28.3.200034EDBT2000tutorial-IntroGenerateasetofexampleschoosesamplingmethodconsidersamplecomplexitydealwithvolumebiasissuesReduceattributedimensionalityremoveredundantand/orcorrelatingattributescombineattributes(sum,multiply,difference)ReduceattributevaluerangesgroupsymbolicdiscretevaluesquantizecontinuousnumericvaluesTransformdatade-correlateandnormalizevaluesmaptime-seriesdatatostaticrepresentationOLAPandvisualizationtoolsplaykeyroleDataselectionandpreprocessingKonstanz,27-28.3.200035EDBT2000tutorial-IntroSelectionand

PreprocessingDataMining

InterpretationandEvaluationDataConsolidationKnowledgep(x)=0.02WarehouseTheKDDprocessKonstanz,27-28.3.200036EDBT2000tutorial-IntroDatamining

tasksandmethodsAutomatedExploration/Discoverye.g..

discoveringnewmarketsegmentsclustering

analysisPrediction/Classificatione.g..

forecastinggrosssalesgivencurrentfactorsregression,neuralnetworks,geneticalgorithms,

decisiontreesExplanation/Descriptione.g..

characterizingcustomersbydemographics

andpurchasehistorydecisiontrees,association

rulesx1x2f(x)xifage>35andincome<$35k

then...Konstanz,27-28.3.200037EDBT2000tutorial-IntroClustering:partitioningasetofdataintoasetofclasses,calledclusters,whosememberssharesomeinterestingcommonproperties.Distance-basednumericalclusteringmetricgroupingofexamples(K-NN)graphicalvisualizationcanbeusedBayesianclusteringsearchforthenumberofclasseswhichresultinbestfitofaprobabilitydistributiontothedataAutoClass(NASA)oneofbestexamplesAutomatedexplorationanddiscoveryKonstanz,27-28.3.200038EDBT2000tutorial-IntroLearningapredictivemodelClassificationofanewcase/sampleManymethods:ArtificialneuralnetworksInductivedecisiontreeandrulesystemsGeneticalgorithmsNearestneighborclusteringalgorithmsStatistical(parametric,andnon-parametric)PredictionandclassificationKonstanz,27-28.3.200039EDBT2000tutorial-IntroTheobjectiveoflearningistoachievegoodgeneralizationtonewunseencases.GeneralizationcanbedefinedasamathematicalinterpolationorregressionoverasetoftrainingpointsModelscanbevalidatedwithapreviouslyunseentestsetorusingcross-validationmethodsf(x)xGeneralizationandregressionKonstanz,27-28.3.200040EDBT2000tutorial-IntroClassificationandpredictionClassifydatabasedonthevaluesofatargetattribute,e.g.,classifycountriesbasedonclimate,orclassifycarsbasedongasmileage.Useobtainedmodeltopredictsomeunknownormissingattributevaluesbasedonotherinformation.Konstanz,27-28.3.200041EDBT2000tutorial-IntroObjective:

Developageneralmodelor hypothesisfromspecificexamplesFunctionapproximation(curvefitting)Classification(conceptlearning,patternrecognition)x1x2ABf(x)xSummarizing:inductivemodeling=learningKonstanz,27-28.3.200042EDBT2000tutorial-IntroLearnageneralizedhypothesis(model)fromselecteddataDescription/InterpretationofmodelprovidesnewknowledgeMethods:InductivedecisiontreeandrulesystemsAssociationrulesystemsLinkAnalysis…ExplanationanddescriptionKonstanz,27-28.3.200043EDBT2000tutorial-IntroGenerateamodelofnormalactivityDeviationfrommodelcausesalertMethods:ArtificialneuralnetworksInductivedecisiontreeandrulesystemsStatisticalmethodsVisualizationtoolsException/deviationdetectionKonstanz,27-28.3.200044EDBT2000tutorial-IntroOutlierandexceptiondataanalysisTime-seriesanalysis(trendanddeviation):Trendanddeviationanalysis:regression,sequentialpattern,similarsequences,trendanddeviation,e.g.,stockanalysis.Similarity-basedpattern-directedanalysisFullvs.partialperiodicityanalysisOtherpattern-directedorstatisticalanalysisKonstanz,27-28.3.200045EDBT2000tutorial-IntroSelectionand

PreprocessingDataMiningInterpretationandEvaluationDataConsolidationandWarehousingKnowledgep(x)=0.02WarehouseTheKDDprocessKonstanz,27-28.3.200046EDBT2000tutorial-IntroAdataminingsystem/querymaygeneratethousandsofpatterns,notallofthemareinteresting.Interestingnessmeasures:easilyunderstoodbyhumansvalidonnewortestdatawithsomedegreeofcertainty.potentiallyusefulnovel,orvalidatessomehypothesisthatauserseekstoconfirmObjectivevs.subjectiveinterestingnessmeasuresObjective:basedonstatisticsandstructuresofpatterns,e.g.,support,confidence,etc.Subjective:basedonuser’sbeliefsinthedata,e.g.,unexpectedness,novelty,etc.Areallthediscoveredpatterninteresting?Findalltheinterestingpatterns:Completeness.Canadataminingsystemfindalltheinterestingpatterns?Searchforonlyinterestingpatterns:Optimization.Canadataminingsystemfindonlytheinterestingpatterns?ApproachesFirstgenerateallthepatternsandthenfilterouttheuninterestingones.Generateonlytheinterestingpatterns-miningqueryoptimization.Completenessvs.optimizationEvaluationStatisticalvalidationandsignificancetestingQualitativereviewbyexpertsinthefieldPilotsurveystoevaluatemodelaccuracyInterpretationInductivetreeandrulemodelscanbereaddirectlyClusteringresultscanbegraphedandtabledCodecanbeautomaticallygeneratedbysomesystems(IDTs,Regressionmodels)InterpretationandevaluationKonstanz,27-28.3.200049EDBT2000tutorial-IntroVisualizationtoolscanbeveryhelpfulsensitivityanalysis(I/Orelationship)histogramsofvaluedistributiontime-seriesplotsandanimationrequirestrainingandpracticeResponseVelocityTempInterpretationandevaluationKonstanz,27-28.3.200050EDBT2000tutorial-Intro1989IJCAIWorkshoponKDDKnowledgeDiscoveryinDatabases(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’99Co