模式识别讲座课件

PatternRecognitionNanyangTechnologicalUniversityDr.Shi,DamingHarbinEngineeringUniversity1PatternRecognitionNanyangTec标题添加点击此处输入相关文本内容点击此处输入相关文本内容总体概述点击此处输入相关文本内容标题添加点击此处输入相关文本内容标题添加点击此处输入相点击此处输入总体概述点击此处输入标题添WhatisPatternRecognitionClassifyrawdataintothe‘category’ofthepattern.Abranchofartificialintelligenceconcernedwiththeidentificationofvisualoraudiopatternsbycomputers.Forexamplecharacterrecognition,speechrecognition,facerecognition,etc.

Twocategories:syntactic(orstructural)patternrecognitionandstatisticalpatternrecognitionIntroductionPatternRecognition=PatternClassification3WhatisPatternRecognitionCla44WhatisPatternRecognitionTrainingPhaseTrainingdataUnknowndataFeatureExtractionLearning(Featureselection,clustering,discriminantfunctiongeneration,grammarparsing)

Recognition(statistical,structural)ResultsRecognitionPhaseKnowledge5WhatisPatternRecognitionTraWhatisPatternRecognitionTrainingPhaseTrainingdataUnknowndataFeatureExtractionLearning(Featureselection,clustering,discriminantfunctiongeneration,grammarparsing)

Recognition(statistical,structural)ResultsRecognitionPhaseKnowledge6WhatisPatternRecognitionTraCategorisationBasedonApplicationAreasFaceRecognitionSpeechRecognitionCharacterRecognitionetc,etcBasedonDecisionMakingApproachesSyntacticPatternRecognitionStatisticalPatternRecognitionIntroduction7CategorisationBasedonApplicaSyntacticPatternRecognitionAnyproblemisdescribedwithformallanguage,andthesolutionisobtainedthroughgrammaticalparsingInMemoryofProf.FU,King-SunandProf.ShuWenhaoIntroduction8SyntacticPatternRecognitionAStatisticalPatternRecognitionInthestatisticalapproach,eachpatternisviewedasapointinamulti-dimensionalspace.Thedecisionboundariesaredeterminedbytheprobabilitydistributionofthepatternsbelongingtoeachclass,whichmusteitherbespecifiedorlearned.Introduction9StatisticalPatternRecognitioScopeoftheSeminarModule1Distance-BasedClassificationModule2ProbabilisticClassificationModule3LinearDiscriminantAnalysisModule4NeuralNetworksforP.R.Module5ClusteringModule6FeatureSelectionIntroduction10ScopeoftheSeminarModule1DModule1Distance-BasedClassificationNanyangTechnologicalUniversityDr.Shi,DamingHarbinEngineeringUniversityPatternRecognition11Module1Distance-BasedClassiOverviewDistancebasedclassificationisthemostcommontypeofpatternrecognitiontechniqueConceptsareabasisforotherclassificationtechniquesFirst,aprototypeischosenthroughtrainingtorepresentaclassThen,thedistanceiscalculatedfromanunknowndatatotheclassusingtheprototype

Distance-BasedClassification12OverviewDistancebasedclassifClassificationbydistanceObjectscanberepresentedbyvectorsinaspace.Intraining,wehavethesamples:Inrecognition,anunknowndataisclassifiedbydistance:Howtorepresentclasses?Distance-BasedClassification13ClassificationbydistanceObjePrototypeTofindthepattern-to-classdistance,weneedtouseaclassprototype(pattern):(1)SampleMean.Forclassci,(2)MostTypicalSample.chooseSuchthatisminimized.Distance-BasedClassification14PrototypeTofindthepattern-tPrototype–NearestNeighbour(3)NearestNeighbour.chooseSuchthatisminimized.Nearestneighbourprototypesaresensitivetonoiseandoutliersinthetrainingset.Distance-BasedClassification15Prototype–NearestNeighbour(Prototype–k-NN(4)k-NearestNeighbours.K-NNismorerobustagainstnoise,butismorecomputationallyexpensive.Thepatternyisclassifiedintheclassofitsknearestneighboursfromthetrainingsamples.Thechosendistancedetermineshow‘near’isdefined.Distance-BasedClassification16Prototype–k-NN(4)k-NearestDistanceMeasuresMostfamiliardistancemetricistheEuclideandistanceAnotherexampleistheManhattandistance:Manyotherdistancemeasures…Distance-BasedClassification17DistanceMeasuresMostfamiliarMinimumEuclideanDistance(MED)ClassifierEquivalently,18MinimumEuclideanDistance(MEDecisionBoundaryGivenaprototypeandadistancemetric,itispossibletofindthedecisionboundarybetweenclasses.LinearboundaryNonlinearboundaryDecisionBoundary=DiscriminantFunctionDistance-BasedClassificationlightnesslengthlightnesslength19DecisionBoundaryGivenaprotoExampleDistance-BasedClassification20ExampleDistance-BasedClassifiExampleAnyfishisavectorinthe2-dimensionalspaceofwidthandlightness.fishDistance-BasedClassificationlightnesslength21ExampleAnyfishisavectorinExampleDistance-BasedClassification22ExampleDistance-BasedClassifiSummaryClassificationbythedistancefromanunknowndatatoclassprototypes.Choosingprototype:SampleMeanMostTypicalSampleNearestNeighbourK-NearestNeighbourDecisionBoundary=DiscriminantFunctionDistance-BasedClassification23SummaryClassificationbythedModule2ProbabilisticClassificationNanyangTechnologicalUniversityDr.Shi,DamingHarbinEngineeringUniversityPatternRecognition24Module2ProbabilisticClassifReviewandExtend25ReviewandExtend25MaximumAPosterior(MAP)ClassifierIdeally,wewanttofavourtheclasswiththehighestprobabilityforthegivenpattern:WhereP(Ci|x)istheaposteriorprobabilityofclassCi

givenx26MaximumAPosterior(MAP)ClasBayesianClassificationBayes’Theoreom:WhereP(x|Ci)istheclassconditionalprobabilitydensity(p.d.f),whichneedstobeestimatedfromtheavailablesamplesorotherwiseassumed.WhereP(Ci)isaprioriprobabilityofclassCi.ProbabilisticClassification27BayesianClassificationBayes’MAPClassifierBayesianClassifier,alsoknownasMAPClassifierSo,assignthepatternxtotheclasswithmaximumweightedp.d.f.ProbabilisticClassification28MAPClassifierBayesianClassifAccuracyVS.RiskHowever,intherealworld,lifeisnotjustaboutaccuracy.Insomecases,asmallmisclassificationmayresultinabigdisaster.Forexample,medicaldiagnosis,frauddetection.TheMAPclassifierisbiasedtowardsthemostlikelyclass.–maximumlikelihoodclassification.ProbabilisticClassification29AccuracyVS.RiskHowever,intLossFunctionOntheotherhand,inthecaseofP(C1)>>P(C2),thelowesterrorratecanbeattainedbyalwaysclassifyingasC1Asolutionistoassignalosstomisclassification.whichleadsto…Alsoknownastheproblemofimbalancedtrainingdata.ProbabilisticClassification30LossFunctionOntheotherhandConditionalRiskInsteadofusingthelikelihoodP(Ci|x),weuseconditionalriskcostofactionigivenclassj

Tominimizeoverallrisk,choosetheactionwiththelowestriskforthepattern:ProbabilisticClassification31ConditionalRiskInsteadofusiConditionalRiskProbabilisticClassification32ConditionalRiskProbabilisticExampleAssumingthattheamountoffraudulentactivityisabout1%ofthetotalcreditcardactivity:C1=FraudP(C1)=0.01C2=NofraudP(C2)=0.99Iflossesareequalformisclassification,then:ProbabilisticClassification33ExampleAssumingthattheamounExampleHowever,lossesareprobablynotthesame.Classifyingafraudulenttransactionaslegitimateleadstodirectdollarlossesaswellasintangiblelosses(e.g.reputation,hasslesforconsumers).Classifyingalegitimatetransactionasfraudulentinconveniencesconsumers,astheirpurchasesaredenied.Thiscouldleadtolossoffuturebusiness.Let’sassumethattheratiooflossfornotfraudtofraudis1to50,i.e.,Amissedfraudis50timesmoreexpensivethanaccidentallyfreezingacardduetolegitimateuse.ProbabilisticClassification34ExampleHowever,lossesareproExampleByincludingthelossfunction,thedecisionboundarieschangesignificantly.InsteadofWeuseProbabilisticClassification35ExampleByincludingthelossfProbabilityDensityFunctionRelativelyspeaking,it’smucheasytoestimateaprioriprobability,e.g.simplytakeToestimatep.d.f.,wecan(1)Assumeaknownp.d.f,andestimateitsparameters(2)Estimatethenon-parametricp.d.ffromtrainingsamplesProbabilisticClassification36ProbabilityDensityFunctionReMaximumLikelihoodParameterEstimationWithoutthelossofgenerality,weconsiderGaussiandensity.P(x|Ci)=TrainingexamplesforclassCiParametervaluestobeidentifiedWearelookingforthatmaximizethelikelihood,soThesamplecovariancematrix!37MaximumLikelihoodParameterEDensityEstimationifwedonotknowthespecificformofthep.d.f.,thenweneedadifferentdensityestimationapproachwhichisanon-parametrictechniquethatusesvariationsofhistogramapproximation.(1)Simplestdensityestimationistouse“bins”.e.g.,in1-Dcase,takethex-axisanddivideintobinsoflengthh.Estimatetheprobabilityofasampleineachbin.kNisthenumberofsamplesinthebin(2)Alternatively,wecantakewindowsofunitvolumeandapplythesewindowstoeachsample.Theoverlapofthewindowsdefinestheestimatedp.d.f.ThistechniqueisknownasParzenwindowsorkernels.ProbabilisticClassification38DensityEstimationifwedonotSummaryBayesianTheoreomMaximumAPosteriorClassifier=MaximumLikelihoodclassiferDensityEstimationProbabilisticClassification39SummaryBayesianTheoreomProbaModule3LinearDiscriminantAnalysisNanyangTechnologicalUniversityDr.Shi,DamingHarbinEngineeringUniversityPatternRecognition40Module3LinearDiscriminantALinearClassifier-1Alinearclassifierimplementsdiscriminantfunctionoradecisionboundaryrepresentedbyastraightlineinthemultidimensionalspace.Givenaninput,x=(x1…xm)TthedecisionboundaryofalinearclassifierisgivenbyadiscriminantfunctionWithweightvectorw=(w1…wm)TLDA41LinearClassifier-1AlinearLinearClassifier-2Theoutputofthefunctionf(x)foranyinputwilldependuponthevalueofweightvectorandinputvector.Forexample,thefollowingclassdefinitionmaybeemployed:Iff(x)>0ThenxisBalletdancerIff(x)≤0ThenxisRugbyplayerLDA42LinearClassifier-2TheoutpuLinearClassifier-3x1x2f(x)>0f(x)<0f(x)=0wTheboundaryisalwaysorthogonaltotheweightvectorwTheinnerproductoftheinputvectorandtheweightvector,wTx

wTxisthesameforallpointsontheboundary--(-b).LDA43LinearClassifier-3x1x2f(x)>Perceptronx=(x1

…xm)Tw=(w1

…wm)TInputsOutput

Activation

Function

w2

w1

Linear

Combiner

bx2x1yLDA44Perceptronx=(x1…xm)Tw=(wMulti-classproblemLDA45Multi-classproblemLDA45LimitationofPerceptronAsingle-layerperceptroncanperformpatternclassificationonlyonlinearlyseparablepatterns.(a)LinearlySeparablePatterns(b)Non-linearlySeparablePatternsLDA46LimitationofPerceptronAsingGeneralizedLinearDiscriminantFunctionsDecisionboundarieswhichseparatebetweenclassesmaynotalwaysbelinear

Thecomplexityoftheboundariesmaysometimesrequesttheuseofhighlynon-linearsurfaces

Apopularapproachtogeneralizetheconceptoflineardecisionfunctionsistoconsiderageneralizeddecisionfunctionas:LDAwhereisanonlinearmappingfunction47GeneralizedLinearDiscriminanSummaryLinearclassifierVectoranalysisPerceptronPerceptroncannotclassifylinearlynon-separablepatternsMLP,RBF,SVMLDA48SummaryLinearclassifierLDA48Module4NeuralNetworksforPatternRecognitionNanyangTechnologicalUniversityDr.Shi,DamingHarbinEngineeringUniversityPatternRecognition49Module4NeuralNetworksforPDetailsinanotherseminar:NeuralNetworks50Detailsinanotherseminar:50Module5ClusteringNanyangTechnologicalUniversityDr.Shi,DamingHarbinEngineeringUniversityPatternRecognition51Module5ClusteringNanyangTecSupervisedLearningVS.unsupervisedLearningClusteringSupervisedLearning(Thetargetoutputisknown)Foreachtraininginputpattern,thenetworkispresentedwiththecorrecttargetanswer(thedesiredoutput)byateacher.UnsupervisedLearning(Thetargetoutputisunknown)Foreachtraininginputpattern,thenetworkadjustsweightswithoutknowingthecorrecttarget.Inunsupervisedtraining,thenetworkself-organizestoclassifysimilarinputpatternsintoclusters.52SupervisedLearningVS.unsupeClusteringCluster:asetofpatternsthataremoresimilartoeachotherthantopatternsnotinthecluster.Givenunlabelledsamplesandhavenoinformationabouttheclasses.Wanttodiscoverifthereareanynaturallyoccurringclustersinthedata.Twoapproaches:ClusteringbyDistanceMeasureClusteringbyDensityEstimationClustering53ClusteringCluster:asetofpaClusteringbyDistanceTwoissues:Howtomeasurethesimilaritybetweensamples?Howtoevaluateapartitioningofasetintoclusters?TypicaldistancemetricsincludeEuclideanDistance,HammingDistance,etc.Clustering54ClusteringbyDistanceTwoissuGoodnessofPartitioningWecanuseameasureofthescatterofeachclustertogaugehowgoodtheoverallclusteringis.Ingeneral,wewouldlikecompactclusterswithalotofspacebetweenthem.WecanusethemeasureofgoodnesstoiterativelymovesamplesfromoneclustertoanothertooptimizethegroupingClustering55GoodnessofPartitioningWecanCriterion:sumofsquarederrorThiscriteriondefinesclustersastheirmeanvectorsmi

inthesensethatitminimizesthesumofthesquaredlengthsoftheerrorx-mi.TheoptimalpartitionisdefinedasonethatminimizesJe,alsocalledminimumvariancepartition.Workfinewhenclustersformwellseparatedcompactclouds,lesswhentherearegreatdifferencesinthenumberofsamplesindifferentclusters.Clustering56Criterion:sumofsquarederroCriterion:ScatterScattermatricesusedinmultiplediscriminantanalysis,i.e.,thewithin-scattermatrixSWandthebetween-scattermatrixSB

ST=SB+SW thatdoesdependonlyfromthesetofsamples(notonthepartitioning)Thecriteriacanbetominimizethewithin-clusterormaximizethebetween-clusterscatterThetrace(sumofdiagonalelements)isthesimplestscalarmeasureofthescattermatrix,asitisproportionaltothesumofthevariancesinthecoordinatedirectionsClustering57Criterion:ScatterScattermatrIterativeoptimizationOnceacriterionfunctionhasbeemselected,clusteringbecomesaproblemofdiscreteoptimization.Asthesamplesetisfinitethereisafinitenumberofpossiblepartitions,andtheoptimalonecanbealwaysfoundbyexhaustivesearch.Mostfrequently,itisadoptedaniterativeoptimizationproceduretoselecttheoptimalpartitionsThebasicidealiesinstartingfromareasonableinitialpartitionand“move”samplesfromoneclustertoanothertryingtominimizethecriterionfunction.Ingeneral,thiskindsofapproachesguaranteelocal,notglobal,optimization.Clustering58IterativeoptimizationOnceaK-MeansClustering-1k-meansclusteringalgorithmInitialization.t=0.Chooserandomvaluesfortheinitialcentersck(t),

k=1,…,KSampling.DrawasamplefromthetrainingsamplesetSimilaritymatching.k(x)denoteindexofbestmatchingcenter4)

Updating.Foreveryk=1,…,K5)

Continuation.t=t+1,gobacktostep(2)untilnonoticeablechangesareobservedClustering59K-MeansClustering-1k-meansK-MeansClustering-2c1c2Clustering60K-MeansClustering-2c1c2ClusK-MeansClustering-3c1c3c2Clustering61K-MeansClustering-3c1c3c2ClClusteringbyDensityEstimatione.g.Findingthenucleusandcytoplasmpelsinwhitebloodcells.ImageGrey-levelHistogram:Setß=valley(localminimum)Ifvalue>ßpeliscytoplasmIfvalue<ßpelisnucleusthisisclusteringbasedondensityestimation.peaks=clustercentres.valleys=clusterboundariesClustering62ClusteringbyDensityEstimatiParameterizedDensityEstimationWeshallbeginwithparameterizedp.d.f.,inwhichtheonlythingthatmustbelearnedisthevalueofanunknownparametervector

Wemakethefollowingassumptions:

Thesamplescomefromaknownnumbercofclasses

ThepriorprobabilitiesP(j)foreachclassareknown

P(x|j,j)(j=1,…,c)areknown

Thevaluesofthecparametervectors1,2,…,careunknownClustering63ParameterizedDensityEstimatiMixtureDensityThecategorylabelsareunknown,andthisdensityfunctioniscalledamixturedensity,andOurgoalwillbetousesamplesdrawnfromthismixturedensitytoestimatetheunknownparametervector.Onceisknown,wecandecomposethemixtureintoitscomponentsanduseaMAPclassifieronthederiveddensities.Clustering64MixtureDensityThecategorylaChineseYing-YangPhilosophyEverythingintheuniversecanbeviewedasaproductofaconstantconflictbetweentheopposites–YingandYang.YingnegativefemaleinvisiblepositivemalevisibleYangTheoptimalstatusisreachedifYing-YangachievesharmonyClustering65ChineseYing-YangPhilosophyEvBayesianYing-YangClusteringTofindaclustersytopartitioninputdataxxisvisiblebutyisinvisiblexdecidesyintrainingbutydecidesxinrunningp(x,y)=p(y|x)p(x)p(x,y)=p(x|y)p(y)xyp(,)Clustering66BayesianYing-YangClusteringTBayesianYingYangHarmonyLearning(1)TominimisethedifferencebetweentheYing-Yangpair:Toselecttheoptimalmodel(clusternumber):whereClustering67BayesianYingYangHarmonyLeaBayesianYingYangHarmonyLearning(2)ParameterlearningusingEMalgorithmE-Step:M-Step:Clustering68BayesianYingYangHarmonyLeaSummaryClusteringbyDistanceGoodnessofparetitioningK-meansClusteringbyDensityEstimationBYYClustering69SummaryClusteringbyDistanceCModule6FeatureSelectionNanyangTechnologicalUniversityDr.Shi,DamingHarbinEngineeringUniversityPatternRecognition70Module6FeatureSelectionNanyMotivationFeatureSelectionClassifierperformancedependonacombinationofthenumberofsamples,numberoffeatures,andcomplexityoftheclassifier.Q1:Themoresamples,thebetter?Q2:Themorefeatures,thebetter?Q3:Themorecomplex,thebetter?However,thenumberofsamplesisfixedwhentrainingBothrequirestoreducethenumberoffeatures71Motivatio