HIERARCHICAL-CONCEPTUAL-CLUSTERING-USING-A-分层概念聚类课件

《HIERARCHICAL-CONCEPTUAL-CLUSTERING-USING-A-分层概念聚类课件》由会员分享，可在线阅读，更多相关《HIERARCHICAL-CONCEPTUAL-CLUSTERING-USING-A-分层概念聚类课件（33页珍藏版）》请在装配图网上搜索。

1、OutlinelWhat is hierarchical conceptual clustering?lOverview of SubduelConceptual clustering in SubduelEvaluation of hierarchical clusteringslExperiments and resultslConclusionsWhat is clustering?What is hierarchical conceptual clustering?lUnsupervised concept learninglGenerating hierarchies to expl

2、ain datalApplicationsHypothesis generation and testingPrediction based on groupsFinding taxonomiesExample hierarchical conceptual clusteringAnimalsBodyTemp:unregulatedHeartChamber:fourBodyTemp:regulatedFertilization:internalFertilization:externalName:mammalBodyCover:hairName:birdBodyCover:feathersNa

3、me:reptileBodyCover:cornified-skinHeartChamber:imperfect-fourFertilization:internalName:fishBodyCover:scalesHeartChamber:twoName:amphibianBodyCover:moist-skinHeartChamber:threeThe ProblemlHierarchical conceptual clustering in discrete-valued structural databaseslExisting systems:Continuous-valuedDis

4、crete but unstructuredWe can do better!(Field under explored)Related WorklCobweblLabyrinthlAutoClasslSnoblIn Euclidian space:Chameleon,CurelUnsupervised learning algorithmsThe SolutionlTake Subdue and extend it!Overview of SubduelData mining in graph representations of structural databasesACBDACBDFE

5、fcbadeabcgOverview of SubduelIteratively searching for best substructure by MDL heuristicACBDcbaOverview of SubduelCompress using best substructure S SFEfdegOverview of SubduelFuzzy matchInexact matching of subgraphsApplications:lDefining fuzzy conceptslEvaluation of clusteringsConceptual Clustering

6、 with SubduelUse Subdue to identify clustersThe best subgraph in an iteration defines a clusterlWhen to stop within an iteration?1)Use limit option2)Use size option3)Use first minimum heuristic(new)The First Minimum HeuristiclUse subgraph at first local minimumDetect it using prune2 optionThe First

7、Minimum HeuristiclNot a greedy heuristic!Although first local minimum is usually the global minimumFirst local minimum is caused by a smaller,more frequently occurring subgraphSubsequent minima are caused by bigger,less frequently occurring subgraphs=First subgraph is more generalThe First Minimum H

8、euristicA multi-minimum search space:Lattice vs.TreelPrevious work defined classification treesInadequate in structured domainslBetter hierarchical description:classification latticeA cluster can have more than one parentA parent can be at any level(not only one level above)Hierarchical Clustering i

9、n SubduelSubdue can compress by a subgraph after each iterationlSubsequent clusters may be defined in terms of previously defined clusterslThis results in a hierarchyHierarchical Conceptual Clustering of an Artificial DomainHierarchical Conceptual Clustering of an Artificial DomainRootEvaluation of

10、ClusteringslTraditional evaluation:Not applicable to hierarchical domainslNo known evaluation for hierarchical clusteringsMost hierarchical evaluations are anecdotalNew Evaluation Heuristic for Hierarchical ClusteringsProperties of a good clustering:Small number of clusterslLarge coverage good gener

11、ality Big cluster descriptionslMore features more inferential powerMinimal or no overlap between clusterslMore distinct clusters better defined conceptsNew Evaluation Heuristic for Hierarchical ClusteringsBig clusters:bigger distance between disjoint clustersOverlap:less overlap bigger distanceFew c

12、lusters:averaging comparisonsExperiments and ResultslValidation in an artificial domainlValidation in unstructured domainslComparison to existing systemslReal world applicationsThe Animal DomainNameBody Cover Heart ChamberBody Temp.Fertilizationmammalhairfourregulatedinternalbirdfeathersfourregulate

13、dinternalreptilecornified-skinimperfect-fourunregulatedinternalamphibianmoist-skinthreeunregulatedexternalfishscalestwounregulatedexternalanimal hairmammalBodyCoverFertilizationHeartChamberBodyTempinternalregulatedNamefourHierarchical Clustering of the Animal DomainAnimalsBodyTemp:unregulatedHeartCh

14、amber:fourBodyTemp:regulatedFertilization:internalFertilization:externalName:mammalBodyCover:hairName:birdBodyCover:feathersName:reptileBodyCover:cornified-skinHeartChamber:imperfect-fourFertilization:internalName:fishBodyCover:scalesHeartChamber:twoName:amphibianBodyCover:moist-skinHeartChamber:thr

15、eeHierarchical Clustering of the Animal Domain by Cobwebanimalsamphibian/fishmammal/birdreptilemammalbirdfishamphibianComparison of Subdue and CobweblQuality of Subdues lattice(tree):2.60lQuality of Cobwebs tree:1.74lTherefore Subdue is betterlReasons for a higher score:Better generalization resulti

16、ng in less clustersEliminating overlap between(reptile)and(amphibian/fish)Chemical Application:Clustering of a DNA sequenceChemical Application:Clustering of a DNA sequence Coverage61%68%71%DNA O|O=P OH C NC CC C O O|O=P OH|O|CH2C N C C O C /C C N C /O CConclusionslGoal of hierarchical conceptual cl

17、ustering of structured databases was achievedlSynthesized classification latticelDeveloped new evaluation heuristic for hierarchical clusteringslGood performance in comparison to other systems,even in unstructured domainsFuture WorklMore experiments on real-world domainslComparison to other systemslIncorporation of evaluation tool into Subdue供娄浪颓蓝辣袄驹靴锯澜互慌仲写绎衰斡染圾明将呆则孰盆瘸砒腥悉漠堑脊髓灰质炎(讲课2019)脊髓灰质炎(讲课2019)供娄浪颓蓝辣袄驹靴锯澜互慌仲写绎衰斡染圾明将呆则孰盆瘸砒腥悉漠堑脊髓灰质炎(讲课2019)脊髓灰质炎(讲课2019)