증분 계층 구조는

Question

나는이 방식을 다음 증분 클러스터링 알고리즘을 우리는 새로운 데이터 포인트가 고려 될 때마다 점진적으로 업데이트 할 수 있습니다.

트리의 각 내부 노드는 해당 노드 아래의 중심의 평균으로 표시됩니다. 주어진 중심점을 업데이트 할 때 (새로운 중심점이이 중심점에 지정되었으므로)이 중심 위에있는 모든 노드를 재구성해야합니다.

Let x a new data-point 
c = searchClosestCenter(x, tree) // return the centroid closest to x 
if(distance(x, c) > threshold) 
    x becomes a new cluster center (i.e. a new centroid) 
    AddCenterToTree(x, tree) 
else 
    assign x to c (i.e. update the centroid by taking x) 
    UpdateTree(c) // update all nodes that are on top of c 

방법이 기능은이 경우에 정의 할 수 있습니다 :

따라서 알고리즘은 무언가 같이된다? 거기에 더 좋은 해결책이 있습니까?

Answer 1

R-tree을 사용하는 것은 어떻습니까? 리프 페이지의 오브젝트를 요약하기 위해 최소 경계 사각형을 사용합니다. kd 트리를 사용할 수도 있지만, 불균형해질 수 있기 때문에 시간이 지남에 따라 성능이 저하됩니다 (재구성하지 않는 한).

어쨌든, R-tree는이 유형의 데이터에 대한 매우 대중적인 데이터 구조입니다. 그것은 오라클, SQLite, Postgres, MySQL, ...에 사용됩니다.

R * -tree는 R 트리의 향상된 버전입니다. 그들은 더 나은 분할 전략, 삽입에 대한 약간의 변경, 그리고 트리 발란싱을 향상시키기 위해 분할 대신에 재 삽입을합니다. 검색은 동일합니다.

최적화로 다음과 같은 최적화를 통해 R-tree를 향상시킬 수 있습니다. 이전 항목을 제거하고 새 항목을 삽입하는 대신 "바꾸기"작업을 추가 할 수 있습니다. 먼저 새로운 평균이 삽입 될 곳을 확인하십시오. 이전과 같은 페이지 인 경우 페이지에서 페이지를 교체하고 결국 경계 상자를 업데이트하십시오.