《數(shù)據(jù)挖掘》英文版全冊(cè)配套課件

《數(shù)據(jù)挖掘》全冊(cè)配套課件DataMining:IntroductionLectureNotesforChapter1IntroductiontoDataMiningbyTan,Steinbach,KumarLotsofdataisbeingcollected

andwarehousedWebdata,e-commercepurchasesatdepartment/

grocerystoresBank/CreditCard

transactionsComputershavebecomecheaperandmorepowerfulCompetitivePressureisStrongProvidebetter,customizedservicesforanedge(e.g.inCustomerRelationshipManagement)WhyMineData?CommercialViewpointWhyMineData?ScientificViewpointDatacollectedandstoredat

enormousspeeds(GB/hour)remotesensorsonasatellitetelescopesscanningtheskiesmicroarraysgeneratinggene

expressiondatascientificsimulations

generatingterabytesofdataTraditionaltechniquesinfeasibleforrawdataDataminingmayhelpscientistsinclassifyingandsegmentingdatainHypothesisFormationMiningLargeDataSets-MotivationThereisofteninformation“hidden”inthedatathatis

notreadilyevidentHumananalystsmaytakeweekstodiscoverusefulinformationMuchofthedataisneveranalyzedatallTheDataGapTotalnewdisk(TB)since1995NumberofanalystsFrom:R.Grossman,C.Kamath,V.Kumar,“DataMiningforScientificandEngineeringApplications”WhatisDataMining?ManyDefinitionsNon-trivialextractionofimplicit,previouslyunknownandpotentiallyusefulinformationfromdataExploration&analysis,byautomaticor

semi-automaticmeans,of

largequantitiesofdata

inordertodiscover

meaningfulpatterns

Whatis(not)DataMining?WhatisDataMining?

CertainnamesaremoreprevalentincertainUSlocations(O’Brien,O’Rurke,O’Reilly…inBostonarea)Grouptogethersimilardocumentsreturnedbysearchengineaccordingtotheircontext(e.g.Amazonrainforest,A,)WhatisnotDataMining?Lookupphonenumberinphonedirectory

QueryaWebsearchengineforinformationabout“Amazon”Drawsideasfrommachinelearning/AI,patternrecognition,statistics,anddatabasesystemsTraditionalTechniques

maybeunsuitableduetoEnormityofdataHighdimensionality

ofdataHeterogeneous,

distributednature

ofdataOriginsofDataMiningMachineLearning/Pattern

RecognitionStatistics/

AIDataMiningDatabasesystemsDataMiningTasksPredictionMethodsUsesomevariablestopredictunknownorfuturevaluesofothervariables.DescriptionMethodsFindhuman-interpretablepatternsthatdescribethedata.From[Fayyad,et.al.]AdvancesinKnowledgeDiscoveryandDataMining,1996DataMiningTasks...Classification[Predictive]Clustering[Descriptive]AssociationRuleDiscovery[Descriptive]SequentialPatternDiscovery[Descriptive]Regression[Predictive]DeviationDetection[Predictive]Classification:DefinitionGivenacollectionofrecords(trainingset)Eachrecordcontainsasetofattributes,oneoftheattributesistheclass.Findamodelforclassattributeasafunctionofthevaluesofotherattributes.Goal:previouslyunseenrecordsshouldbeassignedaclassasaccuratelyaspossible.Atestsetisusedtodeterminetheaccuracyofthemodel.Usually,thegivendatasetisdividedintotrainingandtestsets,withtrainingsetusedtobuildthemodelandtestsetusedtovalidateit.ClassificationExamplecategoricalcategoricalcontinuousclassTestSetTrainingSetModelLearnClassifierClassification:Application1DirectMarketingGoal:Reducecostofmailingbytargetingasetofconsumerslikelytobuyanewcell-phoneproduct.Approach:Usethedataforasimilarproductintroducedbefore.Weknowwhichcustomersdecidedtobuyandwhichdecidedotherwise.This{buy,don’tbuy}decisionformstheclassattribute.Collectvariousdemographic,lifestyle,andcompany-interactionrelatedinformationaboutallsuchcustomers.Typeofbusiness,wheretheystay,howmuchtheyearn,etc.Usethisinformationasinputattributestolearnaclassifiermodel.From[Berry&Linoff]DataMiningTechniques,1997Classification:Application2FraudDetectionGoal:Predictfraudulentcasesincreditcardtransactions.Approach:Usecreditcardtransactionsandtheinformationonitsaccount-holderasattributes.Whendoesacustomerbuy,whatdoeshebuy,howoftenhepaysontime,etcLabelpasttransactionsasfraudorfairtransactions.Thisformstheclassattribute.Learnamodelfortheclassofthetransactions.Usethismodeltodetectfraudbyobservingcreditcardtransactionsonanaccount.Classification:Application3CustomerAttrition/Churn:Goal:Topredictwhetheracustomerislikelytobelosttoacompetitor.Approach:Usedetailedrecordoftransactionswitheachofthepastandpresentcustomers,tofindattributes.Howoftenthecustomercalls,wherehecalls,whattime-of-thedayhecallsmost,hisfinancialstatus,maritalstatus,etc.Labelthecustomersasloyalordisloyal.Findamodelforloyalty.From[Berry&Linoff]DataMiningTechniques,1997Classification:Application4SkySurveyCatalogingGoal:Topredictclass(starorgalaxy)ofskyobjects,especiallyvisuallyfaintones,basedonthetelescopicsurveyimages(fromPalomarObservatory).3000imageswith23,040x23,040pixelsperimage.Approach:Segmenttheimage.Measureimageattributes(features)-40ofthemperobject.Modeltheclassbasedonthesefeatures.SuccessStory:Couldfind16newhighred-shiftquasars,someofthefarthestobjectsthataredifficulttofind!From[Fayyad,et.al.]AdvancesinKnowledgeDiscoveryandDataMining,1996ClassifyingGalaxiesEarlyIntermediateLateDataSize:72millionstars,20milliongalaxiesObjectCatalog:9GBImageDatabase:150GB

Class:StagesofFormationAttributes:Imagefeatures,Characteristicsoflightwavesreceived,etc.Courtesy:ClusteringDefinitionGivenasetofdatapoints,eachhavingasetofattributes,andasimilaritymeasureamongthem,findclusterssuchthatDatapointsinoneclusteraremoresimilartooneanother.Datapointsinseparateclustersarelesssimilartooneanother.SimilarityMeasures:EuclideanDistanceifattributesarecontinuous.OtherProblem-specificMeasures.IllustratingClusteringEuclideanDistanceBasedClusteringin3-Dspace.IntraclusterdistancesareminimizedInterclusterdistancesaremaximizedClustering:Application1MarketSegmentation:Goal:subdivideamarketintodistinctsubsetsofcustomerswhereanysubsetmayconceivablybeselectedasamarkettargettobereachedwithadistinctmarketingmix.Approach:Collectdifferentattributesofcustomersbasedontheirgeographicalandlifestylerelatedinformation.Findclustersofsimilarcustomers.Measuretheclusteringqualitybyobservingbuyingpatternsofcustomersinsameclustervs.thosefromdifferentclusters.Clustering:Application2DocumentClustering:Goal:Tofindgroupsofdocumentsthataresimilartoeachotherbasedontheimportanttermsappearinginthem.Approach:Toidentifyfrequentlyoccurringtermsineachdocument.Formasimilaritymeasurebasedonthefrequenciesofdifferentterms.Useittocluster.Gain:InformationRetrievalcanutilizetheclusterstorelateanewdocumentorsearchtermtoclustereddocuments.IllustratingDocumentClusteringClusteringPoints:3204ArticlesofLosAngelesTimes.SimilarityMeasure:Howmanywordsarecommoninthesedocuments(aftersomewordfiltering).ClusteringofS&P500StockDataObserveStockMovementseveryday.Clusteringpoints:Stock-{UP/DOWN}SimilarityMeasure:Twopointsaremoresimilariftheeventsdescribedbythemfrequentlyhappentogetheronthesameday.Weusedassociationrulestoquantifyasimilaritymeasure.

AssociationRuleDiscovery:DefinitionGivenasetofrecordseachofwhichcontainsomenumberofitemsfromagivencollection;Producedependencyruleswhichwillpredictoccurrenceofanitembasedonoccurrencesofotheritems.RulesDiscovered:

{Milk}-->{Coke}{Diaper,Milk}-->{Beer}AssociationRuleDiscovery:Application1MarketingandSalesPromotion:Lettherulediscoveredbe

{Bagels,…}-->{PotatoChips}PotatoChips

asconsequent=>Canbeusedtodeterminewhatshouldbedonetoboostitssales.Bagelsintheantecedent=>Canbeusedtoseewhichproductswouldbeaffectedifthestorediscontinuessellingbagels.Bagelsinantecedent

and

Potatochipsinconsequent

=>CanbeusedtoseewhatproductsshouldbesoldwithBagelstopromotesaleofPotatochips!AssociationRuleDiscovery:Application2Supermarketshelfmanagement.Goal:Toidentifyitemsthatareboughttogetherbysufficientlymanycustomers.Approach:Processthepoint-of-saledatacollectedwithbarcodescannerstofinddependenciesamongitems.Aclassicrule--Ifacustomerbuysdiaperandmilk,thenheisverylikelytobuybeer.So,don’tbesurprisedifyoufindsix-packsstackednexttodiapers!AssociationRuleDiscovery:Application3InventoryManagement:Goal:Aconsumerappliancerepaircompanywantstoanticipatethenatureofrepairsonitsconsumerproductsandkeeptheservicevehiclesequippedwithrightpartstoreduceonnumberofvisitstoconsumerhouseholds.Approach:Processthedataontoolsandpartsrequiredinpreviousrepairsatdifferentconsumerlocationsanddiscovertheco-occurrencepatterns.SequentialPatternDiscovery:DefinitionGivenisasetofobjects,witheachobjectassociatedwithitsowntimelineofevents,findrulesthatpredictstrongsequentialdependenciesamongdifferentevents.Rulesareformedbyfirstdisoveringpatterns.Eventoccurrencesinthepatternsaregovernedbytimingconstraints.(AB)(C)(DE)<=ms<=xg>ng<=ws(AB)(C)(DE)SequentialPatternDiscovery:ExamplesIntelecommunicationsalarmlogs,

(Inverter_ProblemExcessive_Line_Current)(Rectifier_Alarm)-->(Fire_Alarm)Inpoint-of-saletransactionsequences,ComputerBookstore: (Intro_To_Visual_C)(C++_Primer)--> (Perl_for_dummies,Tcl_Tk)AthleticApparelStore: (Shoes)(Racket,Racketball)-->(Sports_Jacket)RegressionPredictavalueofagivencontinuousvaluedvariablebasedonthevaluesofothervariables,assumingalinearornonlinearmodelofdependency.Greatlystudiedinstatistics,neuralnetworkfields.Examples:Predictingsalesamountsofnewproductbasedonadvetisingexpenditure.Predictingwindvelocitiesasafunctionoftemperature,humidity,airpressure,etc.Timeseriespredictionofstockmarketindices.Deviation/AnomalyDetectionDetectsignificantdeviationsfromnormalbehaviorApplications:CreditCardFraudDetectionNetworkIntrusion

Detection

TypicalnetworktrafficatUniversitylevelmayreachover100millionconnectionsperdayChallengesofDataMiningScalabilityDimensionalityComplexandHeterogeneousDataDataQualityDataOwnershipandDistributionPrivacyPreservationStreamingDataMaterials“IntroductiontoDataMining”,Pang-NingTan,MichaelSteinbach,VipinKumar“MiningMassiveDatasets”,JureLeskovec,AnandRajaraman,andJeffUllmanDataMining:DataLectureNotesforChapter2IntroductiontoDataMiningbyTan,Steinbach,KumarWhatisData?CollectionofdataobjectsandtheirattributesAnattributeisapropertyorcharacteristicofanobjectExamples:eyecolorofaperson,temperature,etc.Attributeisalsoknownasvariable,field,characteristic,orfeatureAcollectionofattributesdescribeanobjectObjectisalsoknownasrecord,point,case,sample,entity,orinstanceAttributesObjectsAttributeValuesAttributevaluesarenumbersorsymbolsassignedtoanattributeDistinctionbetweenattributesandattributevaluesSameattributecanbemappedtodifferentattributevaluesExample:heightcanbemeasuredinfeetormetersDifferentattributescanbemappedtothesamesetofvaluesExample:AttributevaluesforIDandageareintegersButpropertiesofattributevaluescanbedifferentIDhasnolimitbutagehasamaximumandminimumvalueMeasurementofLengthThewayyoumeasureanattributeissomewhatmaynotmatchtheattributesproperties.TypesofAttributesTherearedifferenttypesofattributesNominalExamples:IDnumbers,eyecolor,zipcodesOrdinalExamples:rankings(e.g.,tasteofpotatochipsonascalefrom1-10),grades,heightin{tall,medium,short}IntervalExamples:calendardates,temperaturesinCelsiusorFahrenheit.RatioExamples:temperatureinKelvin,length,time,countsPropertiesofAttributeValuesThetypeofanattributedependsonwhichofthefollowingpropertiesitpossesses:Distinctness: =

Order: <> Addition: +- Multiplication: */Nominalattribute:distinctnessOrdinalattribute:distinctness&orderIntervalattribute:distinctness,order&additionRatioattribute:all4propertiesAttributeTypeDescriptionExamplesOperationsNominalThevaluesofanominalattributearejustdifferentnames,i.e.,nominalattributesprovideonlyenoughinformationtodistinguishoneobjectfromanother.(=,

)zipcodes,employeeIDnumbers,eyecolor,sex:{male,female}mode,entropy,contingencycorrelation,

2testOrdinalThevaluesofanordinalattributeprovideenoughinformationtoorderobjects.(<,>)hardnessofminerals,{good,better,best},

grades,streetnumbersmedian,percentiles,rankcorrelation,runtests,signtestsIntervalForintervalattributes,thedifferencesbetweenvaluesaremeaningful,i.e.,aunitofmeasurementexists.

(+,-)calendardates,temperatureinCelsiusorFahrenheitmean,standarddeviation,Pearson'scorrelation,tandFtestsRatioForratiovariables,bothdifferencesandratiosaremeaningful.(*,/)temperatureinKelvin,monetaryquantities,counts,age,mass,length,electricalcurrentgeometricmean,harmonicmean,percentvariationAttributeLevelTransformationCommentsNominalAnypermutationofvaluesIfallemployeeIDnumberswerereassigned,woulditmakeanydifference?OrdinalAnorderpreservingchangeofvalues,i.e.,

new_value=f(old_value)

wherefisamonotonicfunction.Anattributeencompassingthenotionofgood,betterbestcanberepresentedequallywellbythevalues{1,2,3}orby{0.5,1,10}.Intervalnew_value=a*old_value+bwhereaandbareconstantsThus,theFahrenheitandCelsiustemperaturescalesdifferintermsofwheretheirzerovalueisandthesizeofaunit(degree).Rationew_value=a*old_valueLengthcanbemeasuredinmetersorfeet.DiscreteandContinuousAttributesDiscreteAttributeHasonlyafiniteorcountablyinfinitesetofvaluesExamples:zipcodes,counts,orthesetofwordsinacollectionofdocumentsOftenrepresentedasintegervariables.Note:binaryattributesareaspecialcaseofdiscreteattributesContinuousAttributeHasrealnumbersasattributevaluesExamples:temperature,height,orweight.Practically,realvaluescanonlybemeasuredandrepresentedusingafinitenumberofdigits.Continuousattributesaretypicallyrepresentedasfloating-pointvariables.TypesofdatasetsRecordDataMatrixDocumentDataTransactionDataGraphWorldWideWebMolecularStructuresOrderedSpatialDataTemporalDataSequentialDataGeneticSequenceDataImportantCharacteristicsofStructuredDataDimensionalityCurseofDimensionalitySparsityOnlypresencecountsResolutionPatternsdependonthescaleRecordDataDatathatconsistsofacollectionofrecords,eachofwhichconsistsofafixedsetofattributesDataMatrixIfdataobjectshavethesamefixedsetofnumericattributes,thenthedataobjectscanbethoughtofaspointsinamulti-dimensionalspace,whereeachdimensionrepresentsadistinctattributeSuchdatasetcanberepresentedbyanmbynmatrix,wheretherearemrows,oneforeachobject,andncolumns,oneforeachattributeDocumentDataEachdocumentbecomesa`term'vector,eachtermisacomponent(attribute)ofthevector,thevalueofeachcomponentisthenumberoftimesthecorrespondingtermoccursinthedocument.TransactionDataAspecialtypeofrecorddata,whereeachrecord(transaction)involvesasetofitems.Forexample,consideragrocerystore.Thesetofproductspurchasedbyacustomerduringoneshoppingtripconstituteatransaction,whiletheindividualproductsthatwerepurchasedaretheitems.GraphDataExamples:GenericgraphandHTMLLinksChemicalDataBenzeneMolecule:C6H6OrderedDataSequencesoftransactionsAnelementofthesequenceItems/EventsOrderedDataGenomicsequencedataOrderedDataSpatio-TemporalDataAverageMonthlyTemperatureoflandandoceanDataQualityWhatkindsofdataqualityproblems?Howcanwedetectproblemswiththedata?Whatcanwedoabouttheseproblems?Examplesofdataqualityproblems:NoiseandoutliersmissingvaluesduplicatedataNoiseNoisereferstomodificationoforiginalvaluesExamples:distortionofaperson’svoicewhentalkingonapoorphoneand“snow”ontelevisionscreenTwoSineWavesTwoSineWaves+NoiseOutliersOutliersaredataobjectswithcharacteristicsthatareconsiderablydifferentthanmostoftheotherdataobjectsinthedatasetMissingValuesReasonsformissingvaluesInformationisnotcollected

(e.g.,peopledeclinetogivetheirageandweight)Attributesmaynotbeapplicabletoallcases

(e.g.,annualincomeisnotapplicabletochildren)HandlingmissingvaluesEliminateDataObjectsEstimateMissingValuesIgnoretheMissingValueDuringAnalysisReplacewithallpossiblevalues(weightedbytheirprobabilities)DuplicateDataDatasetmayincludedataobjectsthatareduplicates,oralmostduplicatesofoneanotherMajorissuewhenmergingdatafromheterogeoussourcesExamples:SamepersonwithmultipleemailaddressesDatacleaningProcessofdealingwithduplicatedataissuesDataPreprocessingAggregationSamplingDimensionalityReductionFeaturesubsetselectionFeaturecreationDiscretizationandBinarizationAttributeTransformationAggregationCombiningtwoormoreattributes(orobjects)intoasingleattribute(orobject)PurposeDatareductionReducethenumberofattributesorobjectsChangeofscaleCitiesaggregatedintoregions,states,countries,etcMore“stable”dataAggregateddatatendstohavelessvariabilityAggregationStandardDeviationofAverageMonthlyPrecipitationStandardDeviationofAverageYearlyPrecipitationVariationofPrecipitationinAustraliaSamplingSamplingisthemaintechniqueemployedfordataselection.Itisoftenusedforboththepreliminaryinvestigationofthedataandthefinaldataanalysis.

Statisticianssamplebecauseobtainingtheentiresetofdataofinterestistooexpensiveortimeconsuming.

Samplingisusedindataminingbecauseprocessingtheentiresetofdataofinterestistooexpensiveortimeconsuming.Sampling…Thekeyprincipleforeffectivesamplingisthefollowing:usingasamplewillworkalmostaswellasusingtheentiredatasets,ifthesampleisrepresentative

Asampleisrepresentativeifithasapproximatelythesameproperty(ofinterest)astheoriginalsetofdataTypesofSamplingSimpleRandomSamplingThereisanequalprobabilityofselectinganyparticularitemSamplingwithoutreplacementAseachitemisselected,itisremovedfromthepopulationSamplingwithreplacementObjectsarenotremovedfromthepopulationastheyareselectedforthesample.Insamplingwithreplacement,thesameobjectcanbepickedupmorethanonceStratifiedsamplingSplitthedataintoseveralpartitions;thendrawrandomsamplesfromeachpartitionSampleSize

8000points 2000Points 500PointsSampleSizeWhatsamplesizeisnecessarytogetatleastoneobjectfromeachof10groups.CurseofDimensionalityWhendimensionalityincreases,databecomesincreasinglysparseinthespacethatitoccupiesDefinitionsofdensityanddistancebetweenpoints,whichiscriticalforclusteringandoutlierdetection,becomelessmeaningfulRandomlygenerate500pointsComputedifferencebetweenmaxandmindistancebetweenanypairofpointsDimensionalityReductionPurpose:AvoidcurseofdimensionalityReduceamountoftimeandmemoryrequiredbydataminingalgorithmsAllowdatatobemoreeasilyvisualizedMayhelptoeliminateirrelevantfeaturesorreducenoiseTechniquesPrincipleComponentAnalysisSingularValueDecompositionOthers:supervisedandnon-lineartechniquesDimensionalityReduction:PCAGoalistofindaprojectionthatcapturesthelargestamountofvariationindatax2x1eDimensionalityReduction:PCAFindtheeigenvectorsofthecovariancematrixTheeigenvectorsdefinethenewspacex2x1eDimensionalityReduction:ISOMAPConstructaneighbourhoodgraphForeachpairofpointsinthegraph,computetheshortestpathdistances–geodesicdistancesBy:Tenenbaum,deSilva,Langford(2000)DimensionalityReduction:PCAFeatureSubsetSelectionAnotherwaytoreducedimensionalityofdataRedundantfeaturesduplicatemuchoralloftheinformationcontainedinoneormoreotherattributesExample:purchasepriceofaproductandtheamountofsalestaxpaidIrrelevantfeaturescontainnoinformationthatisusefulforthedataminingtaskathandExample:students'IDisoftenirrelevanttothetaskofpredictingstudents'GPAFeatureSubsetSelectionTechniques:Brute-forceapproch:TryallpossiblefeaturesubsetsasinputtodataminingalgorithmEmbeddedapproaches:FeatureselectionoccursnaturallyaspartofthedataminingalgorithmFilterapproaches:FeaturesareselectedbeforedataminingalgorithmisrunWrapperapproaches:UsethedataminingalgorithmasablackboxtofindbestsubsetofattributesFeatureCreationCreatenewattributesthatcancapturetheimportantinformationinadatasetmuchmoreefficientlythantheoriginalattributesThreegeneralmethodologies:FeatureExtractiondomain-specificMappingDatatoNewSpaceFeatureConstructioncombiningfeaturesMappingDatatoaNewSpaceTwoSineWavesTwoSineWaves+NoiseFrequencyFouriertransformWavelettransformDiscretizationUsingClassLabelsEntropybasedapproach3categoriesforbothxandy5categoriesforbothxandyDiscretizationWithoutUsingClassLabelsDataEqualintervalwidthEqualfrequencyK-meansAttributeTransformationAfunctionthatmapstheentiresetofvaluesofagivenattributetoanewsetofreplacementvaluessuchthateacholdvaluecanbeidentifiedwithoneofthenewvaluesSimplefunctions:xk,log(x),ex,|x|StandardizationandNormalizationSimilarityandDissimilaritySimilarityNumericalmeasureofhowaliketwodataobjectsare.Ishigherwhenobjectsaremorealike.Oftenfallsintherange[0,1]DissimilarityNumericalmeasureofhowdifferentaretwodataobjectsLowerwhenobjectsaremorealikeMinimumdissimilarityisoften0UpperlimitvariesProximityreferstoasimilarityordissimilaritySimilarity/DissimilarityforSimpleAttributespandqaretheattributevaluesfortwodataobjects.EuclideanDistanceEuclideanDistance

Wherenisthenumberofdimensions(attributes)andpkandqkare,respectively,thekthattributes(components)ordataobjectspandq.Standardizationisnecessary,ifscalesdiffer.EuclideanDistanceDistanceMatrixMinkowskiDistanceMinkowskiDistanceisageneralizationofEuclideanDistance

Whererisaparameter,nisthenumberofdimensions(attributes)andpkandqkare,respectively,thekthattributes(components)ordataobjectspandq.MinkowskiDistance:Examplesr=1.Cityblock(Manhattan,taxicab,L1norm)distance.AcommonexampleofthisistheHammingdistance,whichisjustthenumberofbitsthataredifferentbetweentwobinaryvectorsr=2.Euclideandistancer

.“supremum”(Lmaxnorm,L

norm)distance.ThisisthemaximumdifferencebetweenanycomponentofthevectorsDonotconfuserwithn,i.e.,allthesedistancesaredefinedforallnumbersofdimensions.MinkowskiDistanceDistanceMatrixMahalanobisDistanceForredpoints,theEuclideandistanceis14.7,Mahalanobisdistanceis6.isthecovariancematrixoftheinputdataXMahalanobisDistanceCovarianceMatrix:BACA:(0.5,0.5)B:(0,1)C:(1.5,1.5)Mahal(A,B)=5Mahal(A,C)=4CommonPropertiesofaDistanceDistances,suchastheEuclideandistance,havesomewellknownproperties.d(p,q)

0forallpandqandd(p,q)=0onlyif

p

=q.(Positivedefiniteness)d(p,q)=d(q,p)forallpandq.(Symmetry)d(p,r)

d(p,q)+d(q,r)forallpointsp,q,andr.

(TriangleInequality) whered(p,q)isthedistance(dissimilarity)betweenpoints(dataobjects),pandq.AdistancethatsatisfiesthesepropertiesisametricCommonPropertiesofaSimilaritySimilarities,alsohavesomewellknownproperties.s(p,q)=1(ormaximumsimilarity)onlyifp

=q.

s(p,q)=s(q,p)forallpandq.(Symmetry)

wheres(p,q)isthesimilaritybetweenpoints(dataobjects),pandq.SimilarityBetweenBinaryVectorsCommonsituationisthatobjects,pandq,haveonlybinaryattributesComputesimilaritiesusingthefollowingquantities M01

=thenumberofattributeswherepwas0andqwas1 M10=thenumberofattributeswherepwas1andqwas0 M00

=thenumberofattributeswherepwas0andqwas0 M11

=thenumberofattributeswherepwas1andqwas1SimpleMatchingandJaccardCoefficients SMC=numberofmatches/numberofattributes =(M11+M00)/(M01+M10+M11+M00) J=numberof11matches/numberofnot-both-zeroattributesvalues =(M11)/(M01+M10+M11)SMCversusJaccard:Examplep=1000000000

q=0000001001

M01

=2(thenumberofattributeswherepwas0andqwas1)M10

=1(thenumberofattributeswherepwas1andqwas0)M00

=7(thenumberofattributeswherepwas0andqwas0)M11

=0(thenumberofattributeswherepwas1andqwas1)

SMC=(M11+M00)/(M01+M10+M11+M00)=(0+7)/(2+1+0+7)=0.7

J=(M11)/(M01+M10+M11)=0/(2+1+0)=0

CosineSimilarityIfd1andd2aretwodocumentvectors,thencos(d1,d2)=(d1

d2)/||d1||||d2||,where

indicatesvectordotproductand||d||isthelengthofvectord.

Example:

d1

=3205000200 d2