IntroductiontoSpatialDataMining.ppt

introductiontospatialdatamining,7.1patterndiscovery7.2motivation7.3classificationtechniques7.4associationrulediscoverytechniques7.5clustering7.6outlierdetection,learningobjectives,learningobjectives(lo)lo1:understandtheconceptofspatialdatamining(sdm)describetheconceptsofpatternsandsdmdescribethemotivationforsdmlo2:learnaboutpatternsexploredbysdmlo3:learnabouttechniquestofindspatialpatternsfocusonconceptsnotprocedures!mappingsectionstolearningobjectiveslo1-7.1lo2-7.2.4lo3-7.3-7.6,examplesofspatialpatterns,historicexamples(section7.1.5,pp.186)1855asiaticcholerainlondon:awaterpumpidentifiedasthesourcefluorideandhealthygumsnearcoloradorivertheoryofgondwanaland-continentsfitlikepiecesofajigsawpuzllemodernexamplescancerclusterstoinvestigateenvironmenthealthhazardscrimehotspotsforplanningpolicepatrolroutesbaldeaglesnestontalltreesnearopenwaternilevirusspreadingfromnortheastusatosouthandwestunusualwarmingofpacificocean(elnino)affectsweatherinusa,whatisaspatialpattern?,whatisnotapattern?random,haphazard,chance,stray,accidental,unexpectedwithoutdefinitedirection,trend,rule,method,design,aim,purposeaccidental-withoutdesign,outsideregularcourseofthingscasual-absenceofpre-arrangement,relativelyunimportantfortuitous-whatoccurswithoutknowncausewhatisapattern?afrequentarrangement,configuration,composition,regularityarule,law,method,design,descriptionamajordirection,trend,predictionasignificantsurfaceirregularityorunevenness,whatisspatialdatamining?,metaphorsminingnuggetsofinformationembeddedinlargedatabasesnuggets=interesting,useful,unexpectedspatialpatternsmining=lookingfornuggetsneedleinahaystackdefiningspatialdataminingsearchforspatialpatternsnon-trivialsearch-as“automated”aspossiblereducehumaneffortinteresting,usefulandunexpectedspatialpattern,whatisspatialdatamining?-2,non-trivialsearchforinterestingandunexpectedspatialpatternnon-trivialsearchlarge(e.g.exponential)searchspaceofplausiblehypothesisexample-figure7.2,pp.186ex.asiaticcholera:causes:water,food,air,insects,;waterdeliverymechanisms-numerouspumps,rivers,ponds,wells,pipes,.interestingusefulincertainapplicationdomainex.shuttingoffidentifiedwaterpump=savedhumanlifeunexpectedpatternisnotcommonknowledgemayprovideanewunderstandingofworldex.waterpump-choleraconnectionleadtothe“germ”theory,whatisnotspatialdatamining?,simplequeryingofspatialdatafindneighborsofcanadagivennamesandboundariesofallcountriesfindshortestpathfrombostontohoustoninafreewaymapsearchspaceisnotlarge(notexponential)testingahypothesisviaaprimarydataanalysisex.femalechimpanzeeterritoriesaresmallerthanmaleterritoriessearchspaceisnotlarge!sdm:secondarydataanalysistogeneratemultipleplausiblehypothesesuninterestingorobviouspatternsinspatialdataheavyrainfallinminneapolisiscorrelatedwithheavyrainfallinst.paul,giventhatthetwocitiesare10milesapart.commonknowledge:nearbyplaceshavesimilarrainfallminingofnon-spatialdatadiapersalesandbeersalesarecorrelatedineveningsgpsproductbuyersareof3kinds:outdoorsenthusiasts,farmers,technologyenthusiasts,whylearnaboutspatialdatamining?,twobasicreasonsfornewworkconsiderationofuseincertainapplicationdomainsprovidefundamentalnewunderstandingapplicationdomainsscaleupsecondaryspatial(statistical)analysistoverylargedatasetsdescribe/explainlocationsofhumansettlementsinlast5000yearsfindcancerclusterstolocatehazardousenvironmentsprepareland-usemapsfromsatelliteimagerypredicthabitatsuitableforendangeredspeciesfindnewspatialpatternsfindgroupsofco-locatedgeographicfeaturesexercise.name2applicationdomainsnotlistedabove.,whylearnaboutspatialdatamining?-2,newunderstandingofgeographicprocessesforcriticalquestionsex.howisthehealthofplanetearth?ex.characterizeeffectsofhumanactivityonenvironmentandecologyex.predicteffectofelninoonweather,andeconomytraditionalapproach:manuallygenerateandtesthypothesisbut,spatialdataisgrowingtoofasttoanalyzemanuallysatelliteimagery,gpstracks,sensorsonhighways,numberofpossiblegeographichypothesistoolargetoexploremanuallylargenumberofgeographicfeaturesandlocationsnumberofinteractingsubsetsoffeaturesgrowexponentiallyex.findteleconnectionsbetweenweathereventsacrossoceanandlandareassdmmayreducethesetofplausiblehypothesisidentifyhypothesissupportedbythedataforfurtherexplorationusingtraditionalstatisticalmethods,spatialdatamining:actors,domainexpert-identifiessdmgoals,spatialdataset,describedomainknowledge,e.g.well-knownpatterns,e.g.correlatesvalidationofnewpatternsdatamininganalysthelpsidentifypatternfamilies,sdmtechniquestobeusedexplainthesdmoutputstodomainexpertjointeffortfeatureselectionselectionofpatternsforfurtherexploration,thedataminingprocess,fig.7.1,pp.184,choiceofmethods,2approachestominingspatialdata1.pickspatialfeatures;useclassicaldmmethods2.usenovelspatialdataminingtechniquespossibleapproach:definetheproblem:capturespecialneedsexploredatausingmaps,othervisualizationtryreusingclassicaldmmethodsifclassicaldmperformpoorly,trynewmethodsevaluatechosenmethodsrigorouslyperformancetuningasneeded,learningobjectives,learningobjectives(lo)lo1:understandtheconceptofspatialdatamining(sdm)lo2:learnaboutpatternsexploredbysdmrecognizecommonspatialpatternfamiliesunderstanduniquepropertiesofspatialdataandpatternslo3:learnabouttechniquestofindspatialpatternsfocusonconceptsnotprocedures!mappingsectionstolearningobjectiveslo1-7.1lo2-7.2.4lo3-7.3-7.6,7.2.4familiesofsdmpatterns,commonfamiliesofspatialpatternslocationprediction:wherewillaphenomenonoccur?spatialinteraction:whichsubsetsofspatialphenomenainteract?hotspots:whichlocationsareunusual?note:otherfamiliesofspatialpatternsmaybedefinedsdmisagrowingfield,whichshouldaccommodatenewpatternfamilies,7.2.4locationprediction,questionaddressedwherewillaphenomenonoccur?whichspatialeventsarepredictable?howcanaspatialeventsbepredictedfromotherspatialevents?equations,rules,othermethods,examples:wherewillanendangeredbirdnest?whichareasarepronetofiregivenmapsofvegetation,draught,etc.?whatshouldberecommendedtoatravelerinagivenlocation?exercise:listtwopredictionpatterns.,7.2.4spatialinteractions,questionaddressedwhichspatialeventsarerelatedtoeachother?whichspatialphenomenadependonotherphenomenon?examples:exercise:listtwointeractionpatterns.,7.2.4hotspots,questionaddressedisaphenomenonspatiallyclustered?whichspatialentitiesorclustersareunusual?whichspatialentitiessharecommoncharacteristics?examples:cancerclusterscdctolaunchinvestigationscrimehotspotstoplanpolicepatrolsdefiningunusualcomparisongroup:neighborhoodentirepopulationsignificance:probabilityofbeingunusualishigh,7.2.4categorizingfamiliesofsdmpatterns,recallspatialdatamodelconceptsfromchapter2entities-categoriesofdistinct,identifiable,relevantthingsattribute:properties,features,orcharacteristicsofentitiesinstanceofanentity-individualoccurrenceofentitiesrelationship:interactionsorconnectionamongentities,e.g.neighbordegree-numberofparticipatingentitiescardinality-numberofinstanceofanentityinaninstanceofrelationshipself-referencing-interactionamonginstanceofasingleentityinstanceofarelationship-individualoccurrenceofrelationshipspatternfamilies(pf)inentityrelationshipmodelsrelationshipsamongentities,e.g.neighborvalue-basedinteractionsamongattributes,e.g.valueofstudent.ageisdeterminedbystudent.date-of-birth,7.2.4familiesofsdmpatterns,commonfamiliesofspatialpatternslocationprediction:determinationofvalueofaspecialattributeofanentityisbyvaluesofotherattributesofthesameentityspatialinteraction:n-ryinteractionamongsubsetsofentitiesn-ryinteractionsamongcategoricalattributesofanentityhotspots:self-referencinginteractionamonginstancesofanentity.note:otherfamiliesofspatialpatternsmaybedefinedsdmisagrowingfield,whichshouldaccommodatenewpatternfamilies,uniquepropertiesofspatialpatterns,itemsinatraditionaldataareindependentofeachother,whereaspropertiesoflocationsinamapareoften“auto-correlated”.traditionaldatadealswithsimpledomains,e.g.numbersandsymbols,whereasspatialdatatypesarecomplexitemsintraditionaldatadescribediscreteobjectswhereasspatialdataiscontinuousfirstlawofgeographytobler:everythingisrelatedtoeverything,butnearbythingsaremorerelatedthandistantthings.peoplewithsimilarbackgroundstendtoliveinthesameareaeconomiesofnearbyregionstendtobesimilarchangesintemperatureoccurgraduallyoverspace(andtime),example:clusterngandauto-correlation,noteclusteringofnestsitesandsmoothvariationofspatialattributes(figure7.3,pp.188includesmapsoftwootherattributes)alsoseefig.7.4(pp.189)fordistributionswithnoautocorrelation,moransi:ameasureofspatialautocorrelation,givensampledovernlocations.moraniisdefinedaswhereandwisanormalizedcontiguitymatrix.,fig.7.5,pp.190,morani-example,pixelvaluesetin(b)and(c)aresamemoraniisdifferent.q?whichdatasetbetween(b)and(c)hashigherspatialautocorrelation?,figure7.5,pp.190,basicofprobabilitycalculus,givenasetofevents,theprobabilitypisafunctionfrominto0,1whichsatisfiesthefollowingtwoaxiomsandifaandbaremutuallyexclusiveeventsthenp(ab)=p(a)p(b)conditionalprobability:giventhataneventbhasoccurredtheconditionalprobabilitythateventawilloccurisp(a|b).abasicruleisp(ab)=p(a|b)p(b)=p(b|a)p(a)bayesrule:allowsinversionsofprobabilitieswellknownregressionequationallowsderivationoflinearmodels,learningobjectives,learningobjectives(lo)lo1:understandtheconceptofspatialdatamining(sdm)lo2:learnaboutpatternsexploredbysdmlo3:learnabouttechniquestofindspatialpatternsmappingsdmpatternfamiliestotechniquesclassificationtechniquesassociationruletechniquesclusteringtechniquesoutlierdetectiontechniquesfocusonconceptsnotprocedures!mappingsectionstolearningobjectiveslo1-7.1lo2-7.2.4lo3-7.3-7.6,mappingtechniquestospatialpatternfamilies,overviewtherearemanytechniquestofindaspatialpatternfamiliychoiceoftechniquedependsonfeatureselection,spatialdata,etc.spatialpatternfamiliesvs.techniqueslocationprediction:classification,functiondeterminationinteraction:correlation,association,colocationshotspots:clustering,outlierdetectionwediscussthesetechniquesnowwithemphasisonspatialproblemseventhoughthesetechniquesapplytonon-spatialdatasetstoo,given:1.spatialframework2.explanatoryfunctions:3.adependentclass:4.afamilyoffunctionmappings:find:classificationmodel:objective:maximizeclassification_accuracyconstraints:spatialautocorrelationexists,nestlocations,distancetoopenwater,vegetationdurability,waterdepth,locationpredictionasaclassificationproblem,colorversionoffig.7.3,pp.188,techniquesforlocationprediction,classicalmethod:logisticregression,decisiontrees,bayesianclassifierassumeslearningsamplesareindependentofeachotherspatialauto-correlationviolatesthisassumption!q?whatwillamaplooklikewherethepropertiesofapixelwasindependentofthepropertiesofotherpixels?(seebelow-fig.7.4,pp.189)newspatialmethodsspatialauto-regression(sar),markovrandomfieldbayesianclassifier,spatialautoregressionmodel(sar)y=wy+x+wmodelsneighborhoodrelationshipsmodelsstrengthofspatialdependencieserrorvectorsolutionsand-canbeestimatedusingmlorbayesianstat.e.g.,spatialeconometricspackageusesbayesianapproachusingsampling-basedmarkovchainmontecarlo(mcmc)method.likelihood-basedestimationrequireso(n3)ops.otheralternativesdivideandconquer,sparsematrix,ludecomposition,etc.,spatialautoregression(sar),modelevaluation,confusionmatrixmfor2classproblems2rows:actualnest(true),actualnon-nest(false)2columns:predictednests(positive),predictednon-nest(negative)4cellslistingnumberofpixelsinfollowinggroupsfigure7.7(pp.196)nestiscorrectlypredictedtruepositive(tp)modelcanpredictnestwheretherewasnonefalsepositive(fp)no-nestiscorrectlyclassified-(truenegative)(tn)no-nestispredictedatanest-(falsenegative)(fn),modelevaluationcont,outcomesofclassificationalgorithmsaretypicallyprobabilitiesprobabilitiesareconvertedtoclass-labelsbychoosingathresholdlevelb.forexampleprobabilitybis“nest”andprobabilitypower(2,n)possibleassociationskeyassumptionfewassociationsaresupportabovegiventhresholdassociationswithlowsupportarenotintrestingkeyinsight-monotonicityifanassociationitemsethashighsupport,tensodoallitssubsetsdetailspsuedocodeonpp.203executiontraceexample-fig.7.11(pp.203)onnextslide,associationrules:example,spatialassociationrules,spatialassociationrulesaspecialreferencespatialfeaturetransactionsaredefinedaroundinstanceofspecialspatialfeatureitem-types=spatialpredicatesexample:table7.5(pp.204),colocationrules,motivationassociationrulesneedtransactions(subsetsofinstanceofitem-types)spatialdataiscontinuousdecomposingspatialdataintotransactionsmayalterpatternsco-locationrulesforpointdatainspacedoesnotneedtransaction,worksdirectlywithcontinuousspaceuseneighborhooddefinitionandspatialjoins“naturalapproach”,colocationrules,participationindex=minpr(fi,c)wherepr(fi,c)offeaturefiinco-locationc=f1,f2,fk:=fractionofinstancesoffiwithfeaturef1,fi-1,fi+1,fknearbyn(l)=neighborhoodoflocationl,co-locationrulesvs.associationrules,co-locationexample,co-locationexample,dataset=spatialfeaturea,b,c,andtheirinstancesedges=neighborrelationshipcolocationapproach:support(a,b)=min(2/2,3/3)=1support(b,c)=min(2/2,2/2)=1spatialassociationruleapproachcasreferencefeaturetransactions:(b1)(b2)support(b)=2/2=1butsupport(a,b)=0.transactionsloseinformationpartioning1:transactions=(a1,b1,c1),(a2,b2,c2)support(a,b)=1,support(b,c)=1partioning2:transactions=(a2,b1,c1),(b2,c2)support(a,b)=0.5,support(b,c)=1,learningobjectives,learningobjectives(lo)lo1:understandtheconceptofspatialdatamining(sdm)lo2:learnaboutpatternsexploredbysdmlo3:learnabouttechniquestofindspatialpatternsmappingsdmpatternfamiliestotechniquesclassificationtechniquesassociationruletechniquesclusteringtechniquesoutlierdetectiontechniquesfocusonconceptsnotprocedures!mappingsectionstolearningobjectiveslo1-7.1lo2-7.2.4lo3-7.3-7.6,ideaofclustering,clusteringprocessofdiscoveringgroupsinlargedatabases.spatialview:rowsinadatabase=pointsinamulti-dimensionalspacevisualizationmayrevealinterestinggroupsadiversefamilyoftechniquesbasedonavailablegroupdescriptionsexample:census2001attributebasedgroupshomogeneousgroups,e.g.urbancore,suburbs,ruralcentralplacesormajorpopulationcentershierarchicalgroups:necorridor,metropolitanarea,majorcities,neighborhoodsareaswithunusuallyhighpopulationgrowth/declinepurposebasedgroups,e.g.segmentpopulationbyconsumerbehaviourdatadrivengroupingwithlittleaprioridescriptionofgroupsmanydifferentwaysofgroupingusingage,income,spending,ethnicity,.,spatialclusteringexample,exampledata:populationdensityfig.7.13(pp.207)onnextslidegroupinggoal-centralplacesidentifylocationsthatdominatesurroundings,groupsares1ands2groupinggoal-homogeneousareasgroupsarea1anda2note:clusteringliteraturemaynotidentifythegroupinggoalsexplicitly.suchclusteringmethodsmaybeusedforpurposebasedgroupfinding,spatialclusteringexample,exampledata:populationdensityfig.7.13(pp.207)groupinggoal-centralplacesidentifylocationsthatdominatesurroundings,groupsares1ands2groupinggoal-homogeneousareasgroupsarea1anda2,spatialclusteringexample,figure7.13(pp.206),techniquesforclustering,categorizingclassicalmethods:hierarchicalmethodspartitioningmethods,e.g.k-mean,k-medoiddensitybasedmethodsgridbasedmethodsnewspatialmethodscomparisonwithcompletespatialrandomprocessesneighborhoodemourfocus:section7.5:partitioningmethodsandnewspatialmethodssection7.6onoutlierdetectionhasmethodssimilartodensitybasedmethods,algorithmicideasinclustering,hierarchicalallpointsinoneclustersthensplitsandmergestillastoppingcriterionisreachedpartitionalstartwithrandomcentralpointsassignpointstonearestcentralpointupdatethecentralpointsapproachwithstatisticalrigordensityfindclustersbasedondensityofregionsgrid-basedquantizetheclusteringspaceintofinitenumberofcellsusethresholdingtopickhighdensitycellsmergeneighboringcellstoformclusters,learningobjectives,learningobjectives(lo)lo1:understandtheconceptofspatialdatamining(sdm)lo2:learnaboutpatternsexploredbysdmlo3:learnabouttechniquestofindspatialpatternsmappingsdmpatternfamiliestotechniquesclassificationtechniquesassociationruletechniquesclusteringtechniquesoutlierdetectiontechniquesfocusonconceptsnotprocedures!mappingsectionstolearningobjectiveslo1-7.1lo2-7.2.4lo3-7.3-7.6,ideaofoutliers,whatisanoutlier?observationsinconsistentwithrestofthedatasetex.pointd,lorginfig.7.16(a),pp.216techniquesforglobaloutliersstatisticaltestsbasedonmembershipinadistributionpr.iteminpopulationislownon-statisticaltestsbasedondistance,nearestneig