Computer Science/Data Science 86 [Density-based Clustering] DBSCAN DBSCAN = Densit Based Spatial Clustering of Applications with Noise Distance-based가 아니기 때문에 noise를 가진 spatial db에서 어떠한 모양의 cluster더라도 발견해낼 수 있다. 다만 parameter(Eps, MinPts)에 대해 sensitive하다. core 주변에 충분한 neighbor들이 존재하는 점 $N_{Eps} \geq MinPts$ cluster 어떤 점으로부터 최대한 density-connected한 points들의 집합 maximal set of density-connected points outlier 주변에 충분히 density한 점들이 없는 점 $N_{Eps}(p) < MinPts$ 방법 임의의 점 .. 2022. 6. 12. [Cluster Analysis] Density-Based Clustering Density-Based Clustering 일정 이상의 density를 가지는 점들을 같은 cluster로 취급한다. Distance-based가 아닌 density-based이다. 특징 Shape of cluster 어떤 모양의 cluster이든 발견할 수 있다. K-Means는 긴 것은 자르는 경향이 있고 원 모양대로 묶인다. Density-based는 별모양이든 반원 모양이든 모양대로 묶을 수 있다. Robust Noise에 견딜 수 있다. K-means는 noise에 의해 중심이 이동되기 때문에 noise에 영향을 받는다. 1 DB scan 1번의 scan으로 clustering이 가능하기 때문에 효율적이다. Density threshold 묶을 density의 threshold를 정해주어야 한.. 2022. 6. 12. [Hierarchical Clustering] CHAMELEON CHAMELEON Dynamic modeling을 이용한 bottom-up 방식의 hierarchical clustering method이다. 두 cluster 간 interconnectivity와 closeness가 상대적으로 크면 두 cluster를 merge한다. 이를 통해 주변 상황에 맞게(dynamic하게) merge 할 수 있다. 단, 몇 개의 cluster로 나눌 것인지 미리 정해주어야 한다. CHAMELEON은 성능은 괜찮지만 scalability가 좋지 않다. Relative Interconnectivity edge의 수를 기준으로 판단 두 그룹 간 edge cut의 수 / 두 개 각각의 edge cut 수의 평균 $RI(C_i, C_j) = \frac{|EC_{\{ C_i, C_j \}.. 2022. 6. 12. [Hierarchical Clustering] ROCK - using Links ROCK RObust Clustering using linKs 특징 Categorical data에 대해서도 clustering 할 수 있다. Proximity를 계산하기 위해 link의 개념을 사용한다. Distance-based가 아니다. Jaccard Coefficient Categorical data에 주로 사용되는 measure이다. Jaccard coefficient-based similarity function $Sim(T_1, T_2) = \frac{|T_1 \cap T_2|}{|T_1 \cup T_2|}$ 예를 들어, $T_1 = \{a, b, c \}, T_2 = \{ c, d, e \}$의 jacard coefficient-based similarity는 $Sum(T_1, T_2) =.. 2022. 6. 6. [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. 이전 1 2 3 4 5 6 7 8 ··· 18 다음
