模式识别国家重点实验室(精)

模式识别国家重点实验室中国科学院自动化研究所NationalLaboratoryofPatternRecognitionInstituteofAutomation,ChineseAcademyofSciencesAhierarchicalpartitionschemeinfeaturespaceformultivariateclusteringZhangKai,MingTang,HanqingLuNationLaboratoryofPatternRecognition模式识别国家重点实验室中国科学院自动化研究所NationalLaboratoryofPatternRecognitionInstituteofAutomation,ChineseAcademyofSciencesClusteringanalysisandpatternseeking•DistancebasedclusteringmethodsExample:K-nearestmethodsAdvantage：Easilyexecuted，highconvergencequality.Disadvantage：1.Noisesensitive,whichcausesinappropriateclustercenters.2.Clusteringresultisinfluencedbyinitialchoiceofclustercenter.3.Misclassificationwhenvarianceonvariousdirectionsdiffersgreatly.模式识别国家重点实验室中国科学院自动化研究所NationalLaboratoryofPatternRecognitionInstituteofAutomation,ChineseAcademyofSciences•DensitybasedmethodsAdvantage：1.Abilitytofindclusterswitharbitraryshape.Disadvantage：1.Algorithmcomplexityincreasesexponentiallywithdimensions.2.Thresholdisdifficulttoset.模式识别国家重点实验室中国科学院自动化研究所NationalLaboratoryofPatternRecognitionInstituteofAutomation,ChineseAcademyofSciencesMean-shiftclusteringAlgorithmdescription:Assigneachsamplepointtothemodeitconvergencestoaccordingtothefollowingiterativeprocedure:Nomalizedgradientestimation：Meanshiftvector:)(2)()(2xMhdxfxfhnkxnkkyhSixixy,...,2,1,11)(xxnxMxSxixhhi)(1)(模式识别国家重点实验室中国科学院自动化研究所NationalLaboratoryofPatternRecognitionInstituteofAutomation,ChineseAcademyofSciencesIllustrationofmeanshiftclusteringprocess模式识别国家重点实验室中国科学院自动化研究所NationalLaboratoryofPatternRecognitionInstituteofAutomation,ChineseAcademyofSciencesDrawbacksofMeanshiftclustering1.Difficultyinbandwidth(localwindow)selection。2.Withoutproperindexingoftheinputdata,eachstepofsampleshiftrequiresasearchingthroughoutthewholedataset,whosealgorithmcomplexityisO(N*N);Butindexingcostslargecomputationandextraspace。3.Unabletodealwithplateausindensitydistribution。4.Convergingspeedslowsdownnearlocalmaximumdensitypoint,whichdragsdowntheoverall模式识别国家重点实验室中国科学院自动化研究所NationalLaboratoryofPatternRecognitionInstituteofAutomation,ChineseAcademyofSciences•gradientdirection•versusconjugatedirection•Waysofimprovement1.adoptlatticepartitionoffeaturespacetoreducesearchingprice.2.usesingledimensionaldensityestimateasaguidance3.introducehigherorderinformationtospeedupconvergenceprocess.模式识别国家重点实验室中国科学院自动化研究所NationalLaboratoryofPatternRecognitionInstituteofAutomation,ChineseAcademyofSciences模式识别国家重点实验室中国科学院自动化研究所NationalLaboratoryofPatternRecognitionInstituteofAutomation,ChineseAcademyofSciencesSingledimensionestimate&featureintervalpartition1.peaks2.valleys3.plateaus4.sparseregions模式识别国家重点实验室中国科学院自动化研究所NationalLaboratoryofPatternRecognitionInstituteofAutomation,ChineseAcademyofSciences模式识别国家重点实验室中国科学院自动化研究所NationalLaboratoryofPatternRecognitionInstituteofAutomation,ChineseAcademyofSciences•Advantages：1.Unsupervisedclassification2.Reductionofcomputationprice:a.Operationunitissamplesetinsteadofsinglesample.b.Singledimensionestimateisenough,notmultivariateone.c.Meanshiftisexecutedonasmallportionofsamples3.Lowrequirementofstoragespaceandindexing•Disadvantages：Iftheshapeofclassiscomplexorhighlynon-linear,classificationisnotpreciseenough.模式识别国家重点实验室中国科学院自动化研究所NationalLaboratoryofPatternRecognitionInstituteofAutomation,ChineseAcademyofSciencesSolutions1.ClassificationinanewcoordinatesystemafterK-Ltransform2.Re-partitionoftheregionobtainedoriginally。3.Raisethethresholdtoobtainrelativelydenselydistributedsampleareas,thenusemeanshifttodealwiththerestsamplepoints.Duetothesmallnumberofamplesinthesesparseregions,searchingcostformeanshiftismoderatelylow,andatthesametimenaturalshapesofdifferentclassesaremaintainedwell.模式识别国家重点实验室中国科学院自动化研究所NationalLaboratoryofPatternRecognitionInstituteofAutomation,ChineseAcademyofSciencesExampleofcomplexnon-linearclassification模式识别国家重点实验室中国科学院自动化研究所NationalLaboratoryofPatternRecognitionInstituteofAutomation,ChineseAcademyofSciencesAnotherexampleofclassification模式识别国家重点实验室中国科学院自动化研究所NationalLaboratoryofPatternRecognitionInstituteofAutomation,ChineseAcademyofSciencesReferences:[1]DorinComaniciu,“AnAlgorithmforData-DrivenBandwidthSelection”IEEETrans.PatternAnalysisMachineIntelligence,vol.25,No.2,February,2003[2]DorinComaniciuandPeterMeer“DistributionFreeDecompositionofMultivariateData”PatternAnalysis&Applications(1999)2:22-30[3]MingTangandSongdeMa,“GeneralSchemeofRegionCompetitionBasedonScalespace”IEEETrans.PatternAnalysisMachineIntelligence,vol.23,No.12,December,2001[4]PeterKruizingaandNikolayPetkov,“NonlinearOperatorforOrientatedTexture”,IEEETransonImageProcessing,Vol.8.No.10.October1999[5]YizongCheng,MeanShift,ModeSeeking,andClusteringIEEETrans.Patt.Anal.Mach.Intell.,vol.17.No.8.August1995[6]DorinComaniciu,PeterMeer,MeanshiftAnalysisandApplicationsIEEEInt'lConf.Comp.Vis.,Kerkyra,Greece,1197-1203,1999模式识别国家重点实验室中国科学院自动化研究所NationalLaboratoryofPatternRecognitionInstituteofAutomation,ChineseAcademyofSciencesThankyou!