数据挖掘课件：chap2-data

DataMining: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.TypesofdatasetsRecordDataMatrixDocumentDataTransactionDataGraphWorldWideWebMolecularStructuresOrderedSpatialDataTemporalDataSequentialDataGeneticSequenceDataImportantCharacteristicsofStructuredDataDimensionalityCurseofDimensionalitySparsity

OnlypresencecountsResolutionPatternsdependonthescaleRecordDataDatathatconsistsofacollectionofrecords,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”(Lmax

norm,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

CosineSimilarityIf