相似性概念与聚类分析

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

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

不可能认到一个一个的像素点这种程度.提出了实体类别的组织原则第九页，共五十六页，2022年，8月28日概念的形成

格式塔理论与样本的概念归属格式塔学派——整体上认识视觉,提供了根据二维数据形成概念的基本依据邻近律相似律连续律封闭律对称律第十页，共五十六页，2022年，8月28日概念的形成

相似律LawofSimilarity第十一页，共五十六页，2022年，8月28日概念的形成

Lawofproximity邻近律第十二页，共五十六页，2022年，8月28日概念的形成

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

经典概念的颠覆Wittgenstein,L.(1958).PhilosophicalInvestigations(G.E.M.Anscombe,Trans.).USA:BlackwellPublishing.LudwigWittgenstein第十四页，共五十六页，2022年，8月28日概念的非经典定义

EleanorRosch’s的发现上个世纪70年代,EleanorRosch的工作在认知科学领域彻底终结了经典概念的定义-“Thebigbookofconcepts”,writtenbyM.L.Murphy,2002,MIT典型样本与非典型样本第十五页，共五十六页，2022年，8月28日概念的非经典定义

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第十六页，共五十六页，2022年，8月28日概念的非经典定义

PrototypeviewofconceptsAsingleprototypeasacategoryrepresentationItavoidsthecontradictablefeaturesAfeaturelistasacategoryrepresentationItisnotpopularascomputationalcomplexity第十七页，共五十六页，2022年，8月28日概念的非经典定义

Exemplarviewofconcepts(MedinandSchaffer,1978)Conceptsbyrepresentedbyexemplars第十八页，共五十六页，2022年，8月28日概念的非经典定义

KnowledgeapproachofconceptsConceptscanbeconsideredapartofgeneralknowledgegoal-derivedcategories(Barsalou,1985)thingstoeatonadiet,thingstotakefromone’shouseduringafireItslimitation:Muchofaconceptcannotbebasedonpreviousknowledge第十九页，共五十六页，2022年，8月28日概念的非经典定义

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

聚类算法与使用的概念定义类原型聚类算法：紧致型的类样例型聚类算法：连通型的类经典概念对应的聚类算法第二十二页，共五十六页，2022年，8月28日聚类分析

Prototypebasedclustering:C(K)-MEANSRemark:TheessenceofK-meansisthesameasthatofC-means.LBGorGLAalsohasalmostthesamemeaningasK-means第二十三页，共五十六页，2022年，8月28日聚类分析

K-meansanditsextensionsFuzzyC-meansEMtypeclusteringDeterministicannealingclusteringFuzzyc-shellsK-modePCMConditionalfuzzyc-meansGCM(YuJian,2005)第二十四页，共五十六页，2022年，8月28日聚类分析

PrototypebasedclusteringUsuallyusedissimilaritytorepresentsimilarity,thereforeignorethestepofcomputingsimilarityTheiradvantagesareasfollows:fastspeed,andgoodinterpretation,caneasilydealwithtouchingclustersoroverlappingclusterswhenprototypesareproper第二十五页，共五十六页，2022年，8月28日聚类分析

ExemplarbasedclusteringAdditiveclusteringAffinityPropagationMinimumcutandSpectralclusteringHierarchicalclusteringMinimumSpanningtreeDBSCANQT(QualityThreshold）第二十六页，共五十六页，2022年，8月28日聚类分析

AffinityPropagation(Frey&Dueck,2007)第二十七页，共五十六页，2022年，8月28日聚类分析

Minimumcut第二十八页，共五十六页，2022年，8月28日聚类分析

NormalizedCut(ShiandMalik,2000)Subjecttotheconstraints:y(i)∈{1,-b}ytD1=0第二十九页，共五十六页，2022年，8月28日聚类分析

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

IEEETransactionsonPatternAnalysisandMachineIntelligence,Vol22No.0,August2000第三十页，共五十六页，2022年，8月28日聚类分析

SingleLinkage第三十一页，共五十六页，2022年，8月28日聚类分析

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

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

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

现存样例型聚类算法的不足Thepredefinedparameterssuchasthenumberofclustersforadditiveclustering,thepreferencevalueandthedampingfactorfortheaffinitypropagation,thenumberofclustersforspectralclustering,ThresholdforclusterdiameterHighcomplexityofadditiveclustering,qualitythresholdNoconvergenceproofofAffinitypropagationNocalculationresultsforSpectralclusteringifsimilaritymatrixisnotproper第三十六页，共五十六页，2022年，8月28日聚类分析

对应经典概念的聚类算法

如果经典概念的外延来表示划分，即可以用划分矩阵来表示．这样发展出来的算法可以称为划分矩阵型聚类算法。主要有三种技术第三十七页，共五十六页，2022年，8月28日聚类分析

基于矩阵分解技术算法的输入是相似矩阵，计算的主要依据是可将相似矩阵分解成划分矩阵的乘积这样的形式，这样的聚类算法有基于非负矩阵分解的聚类算法，以及异质聚类算法中的矩阵分解聚类算法，可加性聚类算法(additiveclustering)也可以勉强归为这样的算法第三十八页，共五十六页，2022年，8月28日聚类分析

基于信息论算法的输入是概率分布矩阵，文献中的算法有信息瓶颈（informationbottleneck）聚类算法，以及异质聚类算法的互信息联合聚类算法等等第三十九页，共五十六页，2022年，8月28日聚类分析

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