다스굽타의 목표

Dasgupta's objective

계층형 클러스터링 연구에서 Dasgupta의 목표는 클러스터화 요소에 대한 유사성 측정에서 정의된 클러스터화의 품질 측정입니다.2016년에 [1]이것을 공식화한 산조이 다스굽타의 이름을 따서 붙여졌다.이 제품의 주요 특성은 유사성이 울트라메트릭 공간에서 발생할 때 이 품질 측정에 대한 최적의 클러스터링이 울트라메트릭 공간의 기본 구조를 따른다는 것입니다.이런 의미에서 이 목적을 위해 좋은 집단을 생성하는 클러스터링 방법은 주어진 유사성 [2]측정의 기초가 되는 근거에 근접할 것으로 예상할 수 있다.

Dasgupta의 공식에서, 군집화 문제에 대한 입력은 특정 요소 쌍 간의 유사성 점수로 구성되며, 비방향 G ( ,) { G = ( ,E )} ( 요소를 정점으로 하고 가장자리에 음이 아닌 실제 가중치를 가진다.가중치가 크면 서로 더 유사하다고 간주해야 하는 요소를 나타내며, 가중치가 작거나 누락된 가장자리는 유사하지 않은 요소의 쌍을 나타냅니다.계층형 클러스터링은 트리(꼭 2진수 트리일 필요는 없습니다)로 설명할 수 있습니다.그 후 클러스터는 각 트리 노드에서 내려오는 요소의 서브셋이며 C의 C(\ C 요소의 수입니다.입력 그래프의 각 {\uv}에 대해 w { w)는 의 무게를 나타내고 {C u vv를 모두 하는 특정 클러스터 중 가장 작은 클러스터를 나타냅니다.그러면 Dasgupta는 클러스터링[1] 비용을

이 목적을 위한 최적의 군집화는 NP-찾기가 어렵습니다.그러나, 가장 희박한 절단 문제에 대한 근사 알고리즘을 사용하여 요소를 반복적으로 세분화하는 분할(하향식) 클러스터링 알고리즘에 의해 다항식 시간에서 목표의 최소값을 근사하는 클러스터링을 찾을 수 있다. 즉, 총 무게의 비율을 최소화하는 파티션을 찾는 문제가 있다.절단된 모서리를 [1]절단 쌍의 총 수로 조정합니다.마찬가지로 근사 목적상 절삭 가장자리의 총 중량과 절삭의 작은 쪽의 요소 수의 비율을 최소화할 수 있다.가장 희박한 컷 문제에 대해 가장 잘 알려진 근사치를 사용하여 이 접근법의 근사비는 O { O n[3]입니다.

레퍼런스

  1. ^ a b c Dasgupta, Sanjoy (2016), "A cost function for similarity-based hierarchical clustering", Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), New York, New York: ACM, pp. 118–127, arXiv:1510.05043, doi:10.1145/2897518.2897527, MR 3536559
  2. ^ Cohen-Addad, Vincent; Kanade, Varun; Mallmann-Trenn, Frederik; Mathieu, Claire (2018), "Hierarchical clustering: objective functions and algorithms", Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), Philadelphia, Pennsylvania: Society for Industrial and Applied Mathematics, pp. 378–397, arXiv:1704.02147, doi:10.1137/1.9781611975031.26, MR 3775814
  3. ^ Arora, Sanjeev; Rao, Satish; Vazirani, Umesh (2009), "Expander flows, geometric embeddings and graph partitioning", Journal of the ACM, 56 (2): A5:1–A5:37, doi:10.1145/1502793.1502794, MR 2535878