相似性概念与聚类分析.ppt

《相似性概念与聚类分析.ppt》由会员分享，可在线阅读，更多相关《相似性概念与聚类分析.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、机器学习及其应用2009,南京大学相似性，概念与聚类分析于剑北京交通大学计算机学院.Email:机器学习的目的之一：概念o人们学习的目的是学习知识,因此,机器学习的一个自然期望是：从数据中学习到知识o什么是知识的最基本单位：概念Concepts are the glue that holds our mental world together。Cited from page 1 in the book entiled“The big book of concepts”,written by M.L.Murphy,2002,MITo经典概念的定义：（PlatoandAristotle）o概念的内

2、涵：必要而且充分条件（命题描述,命题可以是复合命题）o概念的外延：给出论域中符合该概念的所有样例o符合排中率（lawoftheexcludedmiddle）o要么符合这个概念，要么不符合这个概念o这种经典的概念形式称为定义法什么是概念？概念与数据分析o数据分析的一个重要的应用就是从数据中学习到概念(语义).Cited from C.Rother,V.Kolmogorov,and A.Blake,GrabCut:Interactive foreground extraction using iterated graph cuts,ACM Trans.Graph.,vol.23,pp.309314

3、,2004 相应的机器学习问题(I)o已知:既定概念和该既定概念外延的一个有限子集(即:标定样本)o期望:学习既定概念的内涵定义o机器学习:分类,回归等技术可以归为此类问题,即所谓的有监督学习相应的机器学习问题(II)o已知:样本集,但其中的样本属于哪一个概念未知(未标定样本)o期望:学习出与人类认知相符的概念.最好得到概念的内涵表示,否则,也希望得到概念的外延子集.o机器学习:聚类分析可以归为此类问题,无监督学习本次演讲的重点o如何从未标定的数据集中提取概念,即聚类分析Outlineo概念的形成（GestaltTheory）o概念的非经典定义o聚类分析o类的复杂性讨论o未来展望概念的形成o可

4、分为实体类别(naturalkinds)与抽象类别(abstractkinds)oMaxWertheimer(1923)说:o“我站在窗前,看到的是房屋,树,天空.”不可能认到一个一个的像素点这种程度.o提出了实体类别的组织原则概念的形成格式塔理论与样本的概念归属o格式塔学派整体上认识视觉,提供了根据二维数据形成概念的基本依据n邻近律n相似律n连续律n封闭律n对称律概念的形成相似律LawofSimilarity概念的形成Lawofproximity邻近律概念的形成Gestalt准则的推广性o封闭律,连续律,对称律在高维空间的推广挑战性高,比如对称性:二维与三维不同.o相似律和近邻律的推广性受数

5、据空间维数的影响相对较小,因此对于概念的研究来说,似更为重要.o另外，封闭律,连续律在概念不重叠和相切的情形下可以由相似律和近邻律来反映o概念概念“游戏游戏”内包含的对象内包含的对象不包含共有的特性不包含共有的特性马术，马术，游泳，游泳，下棋，网球等下棋，网球等都属于游戏都属于游戏概念的非经典定义经典概念的颠覆经典概念的颠覆Wittgenstein,L.(1958).Philosophical Investigations(G.E.M.Anscombe,Trans.).USA:Blackwell Publishing.Ludwig Wittgenstein概念的非经典定义EleanorRosc

6、hs的发现o上个世纪70年代,EleanorRosch的工作在认知科学领域彻底终结了经典概念的定义-“Thebigbookofconcepts”,writtenbyM.L.Murphy,2002,MITo典型样本与非典型样本概念的非经典定义ExamplesofitemsstudiedbyRosch&Mervis(1975),orderedbytypicalityoFruit:orange,apple,banana,peach,pear,apricot,plum,grapes,strawberry,grapefruit,pineapple,blueberry,lemon,watermelon,h

7、oneydew,pomegranate,date,coconut,tomato,oliveoFurniture:chair,sofa,table,dresser,desk,bed,bookcase,footstool,lamp,piano,cushion,mirror,rug,radio,stove,clock,picture,closet,vase,telephone概念的非经典定义PrototypeviewofconceptsoAsingleprototypeasacategoryrepresentationItavoidsthecontradictablefeaturesoAfeatur

8、elistasacategoryrepresentationItisnotpopularascomputationalcomplexity概念的非经典定义Exemplarviewofconcepts(MedinandSchaffer,1978)oConceptsbyrepresentedbyexemplars概念的非经典定义KnowledgeapproachofconceptsoConceptscanbeconsideredapartofgeneralknowledgeogoal-derivedcategories(Barsalou,1985)othingstoeatonadiet,thing

9、stotakefromoneshouseduringafireoItslimitation:Muchofaconceptcannotbebasedonpreviousknowledge概念的非经典定义样本如何归属于某个特定概念o样本归入与之最相似的特定概念概念，相似性与聚类分析聚类形成的划分子集内样本具有相当的同质性，即类内的样本是相似的，不同类之间的样本是不相似o如果借用经典概念，聚类分析得到的是概念的一个外延子集o由于聚类分析可以发现数据的内蕴结构，即数据自身蕴含的概念，近年来，聚类分析的应用日益增广聚类分析聚类算法与使用的概念定义o类原型聚类算法：紧致型的类o样例型聚类算法：连通型的类o

10、经典概念对应的聚类算法聚类分析Prototypebasedclustering:C(K)-MEANSRemark:The essence of K-means is the same as that of C-means.LBG or GLA also has almost the same meaning as K-means 聚类分析K-meansanditsextensionsoFuzzyC-meansoEMtypeclusteringoDeterministicannealingclusteringoFuzzyc-shellsoK-modeoPCMoConditionalfuzzyc-

11、meansoGCM(YuJian,2005)聚类分析PrototypebasedclusteringoUsuallyusedissimilaritytorepresentsimilarity,thereforeignorethestepofcomputingsimilarityoTheiradvantagesareasfollows:fastspeed,andgoodinterpretation,caneasilydealwithtouchingclustersoroverlappingclusterswhenprototypesareproper聚类分析Exemplarbasedcluste

12、ringoAdditiveclusteringoAffinityPropagationoMinimumcutandSpectralclusteringoHierarchicalclusteringoMinimumSpanningtreeoDBSCANoQT(QualityThreshold）聚类分析AffinityPropagation(Frey&Dueck,2007)聚类分析Minimumcut聚类分析NormalizedCut(ShiandMalik,2000)Subject to the constraints:1.y(i)1,-b2.ytD1=0聚类分析MinimumCuto最小切聚类

13、算法（minimumcut），AhmedElgammal,GraphCutsandImageSegmentation,RutgersUniversityJianboShiandJitendraMalik“Normalized Cuts and ImageSegmetnation”IEEETransactionsonPatternAnalysisandMachineIntelligence,Vol22No.0,August2000聚类分析SingleLinkage聚类分析Singlelinkage的优缺点o优点：SingleLinkage:J.Haritgan(1981,JASA,76(374)

14、证明了只有Singlelinkage可以统计一致的发现发现高密度类，averagelinkage和completelinkage不具有此性质o缺点：o不能发现不同密度的类o受噪音影响特别厉害o难点：有一个很难确定的参数，聚类数或者阈值聚类分析DBSCAN算法o算法的思想是寻找具有足够高密度的连通区域划分作为类，而低密度区域的点则作为孤立点。o一个点的密度可以看作所有样本点与此点的相似度之和o优点：可以发现任意形状类o缺点：两个参数（密度水平参数，近邻参数），难以选择聚类分析oDBSCAN等算法(DBSCAN)M.Ester,H.-P.Kriegel,J.Sander,andX.Xu.1996.

15、A density-based algorithm for discovering clusters in large spatial databases.KDD96聚类分析QTclusteringoQT(QualityThreshold)聚类算法是通过限定类的直径来聚类的。主要思想是：如果定义了相异矩阵对应的图，类的直径应该不大于给定的阈值。因此，其流程如下：选定一个样本，逐渐合并与其最相似的样本，直到再增加样本将导致类的直径超过给定的阈值为止，然后选定下一个样本，重新聚类。Heyer,L.J.,etal.“ExploringExpressionData:IdentificationandA

16、nalysisofCoexpressedGenes”.GenomeResearch,9:1106-1115(1999)聚类分析现存样例型聚类算法的不足oThepredefinedparameterssuchasthenumberofclustersforadditiveclustering,thepreferencevalueandthedampingfactorfortheaffinitypropagation,thenumberofclustersforspectralclustering,ThresholdforclusterdiameteroHighcomplexityofadditi

17、veclustering,qualitythresholdoNoconvergenceproofofAffinitypropagationoNocalculationresultsforSpectralclusteringifsimilaritymatrixisnotproper聚类分析对应经典概念的聚类算法o如果经典概念的外延来表示划分，即可以用划分矩阵来表示这样发展出来的算法可以称为划分矩阵型聚类算法。o主要有三种技术聚类分析基于矩阵分解技术o算法的输入是相似矩阵，计算的主要依据是可将相似矩阵分解成划分矩阵的乘积这样的形式，这样的聚类算法有基于非负矩阵分解的聚类算法，以及异质聚类算法中的矩

18、阵分解聚类算法，可加性聚类算法(additiveclustering)也可以勉强归为这样的算法聚类分析基于信息论o算法的输入是概率分布矩阵，文献中的算法有信息瓶颈（informationbottleneck）聚类算法，以及异质聚类算法的互信息联合聚类算法等等聚类分析基于margin理论o现有的方法有支持向量机聚类算法（supportvectorclustering）和最大margin聚类算法（maximummarginclustering）类的复杂性讨论类的复杂性讨论概念的定义是一个非常难的问题类是什么也一直是聚类分析研究者面对的核心难题任意形状类(I)任意形状类（II)非同质类相切类重叠类重

19、叠类在图像中的表现混合类Cited from Jain,A.:Data clustering:50 years beyond k-means.Pattern Recognition Letters(Available on line 9 Sept.2009)现存聚类算法的优缺点o类原型聚类算法可以处理相切类，重叠类，条件是类原型合适。但是对于任意形状类处理不好o连通类聚类算法能够处理弱相切类（但是比较复杂），一般的相切类和重叠类处理不了.oEssentially,allmodelsarewrong,butsomeareuseful.CitedfromBox,GeorgeE.P.;NormanR

20、.Draper(1987).Empirical Model-Building and Response Surfaces.Wiley.pp.p.424.ISBN0471810339o“thereisnosingleclusteringalgorithmthathasbeenshowntodominateotheralgorithmsacrossallapplicationdomains”A.K.Jain,2009,PRL,2009相似性的二值表示o一个是在得到相似性得到以后，如何判断对象与类别之间的关系。o一般假设相似性与一个理想相似性是一一对应的.o所谓的理想相似性是指其值与0或者1很接近os(i,k)=e(i,k)+(i,k),其中，e(i,k)取值为0或者1相似性的二值表示定理Texasclustering(Yu,HaoandZhou)o由此而来,我们得到新的基于相似度的聚类算法未来展望o类的表示（概念的表示）o数据的表示（特征空间）o如何结合领域知识聚类算法：semi-supervisedclusteringo现有算法的性能客观评估谢谢.