Computer Science/Data Science 86 [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. [K-Medoids] PAM (Partitioning Around Medoids) PAM (Partitioning Around Medoids) PAM은 cluster를 대표하는 것으로 real object를 이용한다. 방법 initial : 랜덤하게 k개의 object를 선택한다. (random seed) tc 계산 : seed 중 1개($i$), seed가 아닌 object 중 1개($j$)를 선택하고 total swapping cost $TC_{ih}$를 계산한다. total swapping cost : i 대신 h를 쓸 때 전체적인 badness(distance)의 변화 $TC_{ih} < 0$ → i 대신 h를 사용한다. reassign : seed가 아닌 object를 가장 가까운 seed와 같은 cluster로 묶는다. 수렴할 때 까지 2-3의 과정을 반복한다. Total .. 2022. 6. 6. 이전 1 ··· 3 4 5 6 7 8 9 ··· 18 다음
