Computer Science 254 [Hierarchical Clustering] BIRCH - with 1 DB Scan BIRCH Balanced Interative Reducing and Clustering using Hiearhcies 방법 BIRCH는 CF(Clustering Feature) tree를 통해 1 DB scan만으로 대략적인 cluster 구조를 파악한다. (1 DB scan) DB를 scan하면서 in-memory CF tree를 구성한다. (optional) CF-tree의 leaf nodes에 임의의 clustering algorithm을 적용해서 clustering 결과를 보완할 수 있다. 장단점 장점 : scales linearly 1 scan 만으로 괜찮은 clustering 결과를 찾고 추가적인 scan을 통해 quality를 개선한다. 때문에 linear한 cost를 가진다. 단점 num.. 2022. 6. 6. [Hierarchical Clustering] DIANA (Divisive Analysis) DIANA (DIvisive ANAlysis) Top-down 방식의 hierarchical clustering method이다. Splus 같이 statistical analysis packages에 구현되어있다. 개념적으로는 AGNES(bottom-up)과 반대이지만 순서적으로 완전히 역순은 아니다. 각 object를 하나의 cluster로 만들기 위해 과정을 반복해나간다. Divisive vs. Agglometrative n개의 object가 속해있는 전체 cluster를 두 개의 cluster로 나눌 때 complexity는 agglomerative $_n C _2 = \frac{n(n-1)}{2}$ 가능한 모든 조합에 대해 distance를 계산 divisive $2^{n-1} - 1$ (각 요.. 2022. 6. 6. [Hierarchical Clustering] AGNES, Dendrogram AGNES (AGGlomerative NESting) Bottom-up 방식의 hierarchical clustering 방법이다. cluster 간 거리의 기준으로 single-link를 사용한다. 즉, 두 cluster의 가능한 모든 object의 pair 중 최소 거리를 cluster의 거리로 취급한다. 가장 가까운 cluster끼리 묶어 나간다. 모든 객체를 하나의 cluster로 묶기 위해 과정을 반복해나간다. cluster 간 거리는 계속 증가하는 경향이 있으나 감소하지는 않는다. 가까운 것은 이미 같은 cluster로 묶였기 때문이다. Dendrogram Bottom-up 방식에서 어떤 순서로 cluster가 묶였는지 보여주는 트리 구조이다. 원하는 level에서 dendrogram을 자름으.. 2022. 6. 6. [Cluster Analysis] Hierarchical Clustering Hierarchical Clustering Clustering을 하는 기준으로 distance matrix를 이용한다. 몇 개의 cluster로 나눌 지 결정할 필요 없다. 단, 몇 개로 나뉘었을 때 중단할지나 cluster 내 최대 distance 등 termination condition을 정해주어야 한다. 계층을 구성하는 방법에 따라 agglomerative나 divisive로 나눌 수 있다. bottom-up : agglomerative leaf부터 root까지 구성해나간다. 가장 가까운 것 끼리 묶어 나간다. 예 : AGNES top-down : divisive root부터 leaf까지 구성해나간다. 가장 가까운 것들끼리 분리해 나간다. 예 : DIANA Advanced Hierarchical .. 2022. 6. 6. [K-Medoids] CLARA (Clustering LARge Applications) CLARA Partitioning clustering method인 k-medoids 기법 중 하나이다. 각 cluster를 대표하는 것으로 medoids(real-object)를 사용한다. Medoids를 이용하기 때문에 outlier나 noise에 대해 robust하다. 샘플링을 통해 clustering을 함으로써 scalability가 떨어지는 PAM의 약점을 극복하였다. 방법 데이터셋에 대해 multiple sampling을 수행한다. 샘플링을 한번만 하면 샘플링 방법에 따라 결과가 달라지기 때문에 여러 번을 해서 best clustering 결과를 도출해낸다. 장단점 장점 : 큰 데이터셋에 대해서 PAM을 적용할 수 있다. 약점 sample size에 따라 효율성이 달라진다 sample로 몇개를.. 2022. 6. 6. 이전 1 ··· 6 7 8 9 10 11 12 ··· 51 다음
