728x90 반응형 clustering11 [CS246] CURE Algorithm: Extension of k-means to clusters of arbitrary shapes Motivationk-mean과 BFR 알고리즘은 convex하거나 fixed-axis와 같은 클러스터 shape에 여러 가정이 있었다.CURE 알고리즘은 이러한 cluster shape에 어떠한 가정을 하지 않고 유클리드 거리만을 가정한다. 데이터가 정규분포일 필요도 없고, 고정된 축일 필요도 없다. 따라서 centroid 개념도 필요하지 않다. 대신에, collection of representative points가 클러스터의 표현을 나타낸다.클러스터 개수는 $k$개라고 가정한다. CURE는 Clustering Using REpresentatives의 앞글자를 따온 것이고, 원래 논문의 제목은 "CURE: An Efficient Clustering Algorithm for Large Databas.. 2023. 10. 2. [CS246] BFR Algorithm: Extension of k-means to large data Motivationk-mean 알고리즘은 모든 데이터를 메모리에 올리고 클러스터링 알고리즘을 수행한다.그러나 현실세계의 데이터는 너무 커서(데이터베이스로 관리 등) 메인메모리에 올릴 수 없다.BFR 알고리즘을 매우 큰 데이터(disk-resident data sets)에 k-mean 클러스터링을 적용하는 알고리즘이다. BFR은 논문의 세 저자 Paul S. Bradley, Usama M. Fayyad, Cory A. Reina의 앞글자를 딴 것이다.(논문: Scaling Clustering Algorithms to Large Database)BFR OverviewAssume모든 클러스터는 axis-aligned ellipse이다. (그러나 각 axis마다 표준편차가 다른 것은 허용된다)Ideadata p.. 2023. 10. 1. [Clustering] Cluster Evaluation (silhouette coefficient, proximity matrix, clustering tendency) Measures of Cluster ValidityUnsupervised measure, Internal indexgoodness of a clustering structure w/o respect to external informationCluster Cohesion (compactness, tighness)Cluster Seperation (isolation) Supervised measure, External indexwhich cluster labels match externally supplied class labelsEntropy Relative measureCompare two different clustering resultsunsupervised/supervised measure 모두 적.. 2023. 6. 3. [Clustering] Density-Based Methods, DBSCAN Basic Concept of Density-Based ClusteringMajor features임의의 모양에 대한 clustering이 가능 (arbitrary shape)noise 조절1번만 조회 (one scan)종료 조건으로 density parameter가 필요함density-based clustering으로 DBSCAN, OPTICS, DENCLUE, CLIQUE 등이 있고 DBSCAN에 대하여 알아보자. DBSCANDensity-Based Spatial Clustering of Applications with NoiseDBSCAN 알고리즘은 2014 KDD test of time award를 수상했다.arbitrary shaperobust to noisescales well to large.. 2023. 5. 25. [Clustering] BIRCH Algorithm Basic Concepts of BIRCHBIRCH (Balanced Iterative Reducing and Clustering Using Hierarchies) Clustering Feature Tree(CF-Tree)를 점진적으로 증가시켜 데이터의 계층을 구성한다.(1) 데이터를 scan하여 CF tree를 구성한다.(2) arbitrary clustering 알고리즘을 이용하여 CF-tree의 leaf node를 cluster로 한다. Scales Linearlysingle scan만으로도 좋은 클러스터링이 가능하다.약간의 추가적인 scan으로 더 좋은 퀄리티 향상이 가능하다.전체적인 시간복잡도는 $O(n)$ 이다. Weaknessnumeric data만 적용할 수 있다.데이터 순서에 민감하다. .. 2023. 5. 23. [Clustering] Hierarchical Clustering (계층적 군집화) IntroductionHierarchical tree 형태로 nested cluster를 구성한다.Dendrogram으로 클러스터를 시각화한다.Clustering criteria로 주로 distance matrix를 이용한다. Strengths of Hierarchical Clustering클러스터가 몇 개인지 직접 가정할 필요가 없다. (k-means는 우리가 직접 $k$를 정해야했다)dendrogram에서 적정 수준에서 cutting을 하면 어떠한 클러스터 개수도 가능하다. 계층적 클러스터는 (아마도) 의미있는 분류체계와 대응될 것이다. (meaningful taxonomies)biological science에서 특히 유용하다. (animal kingdom, phylogeny reconstructi.. 2023. 5. 22. 이전 1 2 다음 728x90 반응형
