相似性概念与聚类分析

相似性概念与聚类分析第1页，课件共56页，创作于2023年2月机器学习的目的之一：概念人们学习的目的是学习知识,因此,机器学习的一个自然期望是：从数据中学习到知识什么是知识的最基本单位：概念Conceptsarethegluethatholdsourmentalworldtogether。Citedfrompage1inthebookentiled“Thebigbookofconcepts”,writtenbyM.L.Murphy,2002,MIT第2页，课件共56页，创作于2023年2月经典概念的定义：（PlatoandAristotle）概念的内涵：必要而且充分条件（命题描述,命题可以是复合命题）概念的外延：给出论域中符合该概念的所有样例符合排中率（lawoftheexcludedmiddle）要么符合这个概念，要么不符合这个概念这种经典的概念形式称为定义法什么是概念？第3页，课件共56页，创作于2023年2月概念与数据分析数据分析的一个重要的应用就是从数据中学习到概念(语义).CitedfromC.Rother,V.Kolmogorov,andA.Blake,GrabCut:Interactiveforegroundextractionusingiteratedgraphcuts,ACMTrans.Graph.,vol.23,pp.309–314,2004第4页，课件共56页，创作于2023年2月相应的机器学习问题(I)已知:既定概念和该既定概念外延的一个有限子集(即:标定样本)期望:学习既定概念的内涵定义机器学习:分类,回归等技术可以归为此类问题,即所谓的有监督学习第5页，课件共56页，创作于2023年2月相应的机器学习问题(II)已知:

样本集,但其中的样本属于哪一个概念未知(未标定样本)期望:学习出与人类认知相符的概念.最好得到概念的内涵表示,否则,也希望得到概念的外延子集.机器学习:聚类分析可以归为此类问题,无监督学习第6页，课件共56页，创作于2023年2月本次演讲的重点如何从未标定的数据集中提取概念,即聚类分析第7页，课件共56页，创作于2023年2月Outline概念的形成（GestaltTheory）概念的非经典定义聚类分析类的复杂性讨论未来展望第8页，课件共56页，创作于2023年2月概念的形成可分为实体类别(naturalkinds)与抽象类别(abstractkinds)MaxWertheimer(1923)说:“我站在窗前,看到的是房屋,树,天空.”…

不可能认到一个一个的像素点这种程度.提出了实体类别的组织原则第9页，课件共56页，创作于2023年2月概念的形成

格式塔理论与样本的概念归属格式塔学派——整体上认识视觉,提供了根据二维数据形成概念的基本依据邻近律相似律连续律封闭律对称律第10页，课件共56页，创作于2023年2月概念的形成

相似律LawofSimilarity第11页，课件共56页，创作于2023年2月概念的形成

Lawofproximity邻近律第12页，课件共56页，创作于2023年2月概念的形成

Gestalt准则的推广性封闭律,连续律,对称律在高维空间的推广挑战性高,比如对称性:二维与三维不同.相似律和近邻律的推广性受数据空间维数的影响相对较小,因此对于概念的研究来说,似更为重要.另外，封闭律,连续律在概念不重叠和相切的情形下可以由相似律和近邻律来反映第13页，课件共56页，创作于2023年2月概念“游戏”内包含的对象不包含共有的特性马术，游泳，下棋，网球等都属于游戏概念的非经典定义

经典概念的颠覆Wittgenstein,L.(1958).PhilosophicalInvestigations(G.E.M.Anscombe,Trans.).USA:BlackwellPublishing.LudwigWittgenstein第14页，课件共56页，创作于2023年2月概念的非经典定义

EleanorRosch’s的发现上个世纪70年代,EleanorRosch的工作在认知科学领域彻底终结了经典概念的定义-“Thebigbookofconcepts”,writtenbyM.L.Murphy,2002,MIT典型样本与非典型样本第15页，课件共56页，创作于2023年2月概念的非经典定义

Examplesofitems studiedbyRosch&Mervis(1975),orderedbytypicality

Fruit:orange,apple,banana,peach,pear,apricot,plum,grapes,strawberry,grapefruit,pineapple,blueberry,lemon,watermelon,honeydew,pomegranate,date,coconut,tomato,oliveFurniture:chair,sofa,table,dresser,desk,bed,bookcase,footstool,lamp,piano,cushion,mirror,rug,radio,stove,clock,picture,closet,vase,telephone第16页，课件共56页，创作于2023年2月概念的非经典定义

PrototypeviewofconceptsAsingleprototypeasacategoryrepresentationItavoidsthecontradictablefeaturesAfeaturelistasacategoryrepresentationItisnotpopularascomputationalcomplexity第17页，课件共56页，创作于2023年2月概念的非经典定义

Exemplarviewofconcepts(MedinandSchaffer,1978)Conceptsbyrepresentedbyexemplars第18页，课件共56页，创作于2023年2月概念的非经典定义

KnowledgeapproachofconceptsConceptscanbeconsideredapartofgeneralknowledgegoal-derivedcategories(Barsalou,1985)thingstoeatonadiet,thingstotakefromone’shouseduringafireItslimitation:Muchofaconceptcannotbebasedonpreviousknowledge第19页，课件共56页，创作于2023年2月概念的非经典定义

样本如何归属于某个特定概念样本归入与之最相似的特定概念第20页，课件共56页，创作于2023年2月概念，相似性与聚类分析聚类形成的划分子集内样本具有相当的同质性，即类内的样本是相似的，不同类之间的样本是不相似如果借用经典概念，聚类分析得到的是概念的一个外延子集由于聚类分析可以发现数据的内蕴结构，即数据自身蕴含的概念，近年来，聚类分析的应用日益增广第21页，课件共56页，创作于2023年2月聚类分析

聚类算法与使用的概念定义类原型聚类算法：紧致型的类样例型聚类算法：连通型的类经典概念对应的聚类算法第22页，课件共56页，创作于2023年2月聚类分析

Prototypebasedclustering:C(K)-MEANSRemark:TheessenceofK-meansisthesameasthatofC-means.LBGorGLAalsohasalmostthesamemeaningasK-means第23页，课件共56页，创作于2023年2月聚类分析

K-meansanditsextensionsFuzzyC-meansEMtypeclusteringDeterministicannealingclusteringFuzzyc-shellsK-modePCMConditionalfuzzyc-meansGCM(YuJian,2005)第24页，课件共56页，创作于2023年2月聚类分析

PrototypebasedclusteringUsuallyusedissimilaritytorepresentsimilarity,thereforeignorethestepofcomputingsimilarityTheiradvantagesareasfollows:fastspeed,andgoodinterpretation,caneasilydealwithtouchingclustersoroverlappingclusterswhenprototypesareproper第25页，课件共56页，创作于2023年2月聚类分析

ExemplarbasedclusteringAdditiveclusteringAffinityPropagationMinimumcutandSpectralclusteringHierarchicalclusteringMinimumSpanningtreeDBSCANQT(QualityThreshold）第26页，课件共56页，创作于2023年2月聚类分析

AffinityPropagation(Frey&Dueck,2007)第27页，课件共56页，创作于2023年2月聚类分析

Minimumcut第28页，课件共56页，创作于2023年2月聚类分析

NormalizedCut(ShiandMalik,2000)Subjecttotheconstraints:y(i)∈{1,-b}ytD1=0第29页，课件共56页，创作于2023年2月聚类分析

MinimumCut最小切聚类算法（minimumcut），AhmedElgammal,GraphCutsandImageSegmentation,RutgersUniversityJianboShiandJitendraMalik“NormalizedCutsandImageSegmetnation”

IEEETransactionsonPatternAnalysisandMachineIntelligence,Vol22No.0,August2000第30页，课件共56页，创作于2023年2月聚类分析

SingleLinkage第31页，课件共56页，创作于2023年2月聚类分析

Singlelinkage的优缺点优点：SingleLinkage:J.Haritgan(1981,JASA,76(374))证明了只有Singlelinkage可以统计一致的发现发现高密度类，averagelinkage和completelinkage不具有此性质缺点：不能发现不同密度的类受噪音影响特别厉害难点：有一个很难确定的参数，聚类数或者阈值第32页，课件共56页，创作于2023年2月聚类分析

DBSCAN算法算法的思想是寻找具有足够高密度的连通区域划分作为类，而低密度区域的点则作为孤立点。一个点的密度可以看作所有样本点与此点的相似度之和优点：可以发现任意形状类缺点：两个参数（密度水平参数，近邻参数），难以选择第33页，课件共56页，创作于2023年2月聚类分析DBSCAN等算法(DBSCAN)M.Ester,H.-P.Kriegel,J.Sander,andX.Xu.1996.Adensity-basedalgorithmfordiscoveringclustersinlargespatialdatabases.KDD'96第34页，课件共56页，创作于2023年2月聚类分析

QTclusteringQT(QualityThreshold)聚类算法是通过限定类的直径来聚类的。主要思想是：如果定义了相异矩阵对应的图，类的直径应该不大于给定的阈值。因此，其流程如下：选定一个样本，逐渐合并与其最相似的样本，直到再增加样本将导致类的直径超过给定的阈值为止，然后选定下一个样本，重新聚类。Heyer,L.J.,etal.“ExploringExpressionData:IdentificationandAnalysisofCoexpressedGenes”.GenomeResearch,9:1106-1115(1999)第35页，课件共56页，创作于2023年2月聚类分析

现存样例型聚类算法的不足Thepredefinedparameterssuchasthenumberofclustersforadditiveclustering,thepreferencevalueandthedampingfactorfortheaffinitypropagation,thenumberofclustersforspectralclustering,ThresholdforclusterdiameterHighcomplexityofadditiveclustering,qualitythresholdNoconvergenceproofofAffinitypropagationNocalculationresultsforSpectralclusteringifsimilaritymatrixisnotproper第36页，课件共56页，创作于2023年2月聚类分析

对应经典概念的聚类算法

如果经典概念的外延来表示划分，即可以用划分矩阵来表示．这样发展出来的算法可以称为划分矩阵型聚类算法。主要有三种技术第37页，课件共56页，创作于2023年2月聚类分析

基于矩阵分解技术算法的输入是相似矩阵，计算的主要依据是可将相似矩阵分解成划分矩阵的乘积这样的形式，这样的聚类算法有基于非负矩阵分解的聚类算法，以及异质聚类算法中的矩阵分解聚类算法，可加性聚类算法(additiveclustering)也可以勉强归为这样的算法第38页，课件共56页，创作于2023年2月聚类分析

基于信息论算法的输入是概率分布矩阵，文献中的算法有信息瓶颈（informationbottleneck）聚类算法，以及异质聚类算法的互信息联合聚类算法等等第39页，课件共56页，创作于2023年2月聚类分析

基于margin理论现有的方法有支持向量机聚类算法（supportvectorclustering）和最大margin聚类算法（maximummarginclustering）第40页，课件共56页，创作于2023年2月类的复杂性讨论概念的定义是一个非常难的问题．类是什么也一直是聚类分析研究者面对的核心难题．第41页，课件共56页，创作于2023年2月任意形状类(I)第42页，课件共56页，创作于2023年2月任意形状类（II)第43页，课件共56页，创作于2023年2月非同质类第44页，课件共56页，创作于2023年2月相切类第45页，课件共56页，创作于2023年2月重叠类第46页，课件共56页，创作于2023年2月重叠类在图像中的表现第47页，课件共56页，创作于2023年2月混合类第48页，课件共56页，创作于2023年2月CitedfromJain,A.:Dataclustering:50yearsbeyondk-means.PatternRecognitionLetters(Availableonline9Sept.2009)第49页，课件共56页，创作于2023年2月现存聚类算法的优缺点类原型聚类算法可以处理相切类，重叠类，条件是类原型合适。但是对于任意形状类处理不好连通类聚类算法能够处理弱相切类（但是比较复杂），一般的相切类和