Hierarchical clustering algorithm

8330 단어 algorithm
  • 여러 데이터를 클러스터로 분류하는 방법 중 하나입니다. 아래 wikipedia 기사 개요
  • h tp : // 엔.ぃきぺぢ아. 오 rg / uki / 히에라 r 치카 l_c ぅ s terin g

  • N 요소 각각의 쌍에 대해 요소 간 거리 $d(i,j)$ 를 정의할 수 있으면 적용할 수 있는 기법입니다.
  • agglomerative의 두 종류가 있다.
  • 여기서는 agglomorative 만 설명합니다



    • 알고리즘


  • 이러한 a ~ f의 요소를 클러스터링하는 것을 생각한다
    • 여기서 설명을 위해 요소들 사이의 거리는 도면의 요소들 사이의 유클리드 거리로 정의된다고 가정한다. 임의의 두 요소 사이의 거리가 정의되면이 기술을 적용 할 수 있습니다. a ~ f 중 가장 가까운 두 요소를 클러스터링합니다. (b, c), (d, e)를 각각 하나의 클러스터로 만듭니다.
  • 이후, 마찬가지로 가까운 클러스터끼리를 병합해 간다.
  • 다음에 가까운 클러스터는 (de, f)이므로 병합합니다.
    • 두 클러스터 $\mathcal{A}$, $\mathcal{B}$ 사이의 거리는 여러 정의 방법을 가질 수 있습니다. complete-linkage clustering: \max {\, d(x,y) : x \in \mathcal{A},\, y \in \mathcal{B}\,}. 각 클러스터 내 요소의 최대 거리 single-linkage clusteirng: \min {\, d(x,y) : x \in \mathcal{A},\, y \in \mathcal{B} \,}. 각 클러스터 내 요소의 최소 거리 그 밖에도, average-linkage clustering 등 복수의 수법이 있다.
    • 최종적으로 하나의 클러스터가 될 때까지 계속되지만, 클러스터의 개수(number criterion)나 클러스터 간의 거리(distance criterion) 등을 정해 어딘가에서 클러스터링을 정지한다. 일반적으로 aggomerative의 계산량은 $O(N^3)$이지만, complete-linkage clustering, single-linkage clustering의 경우에는 $O(N^2)$ 알고리즘(CLINK, SLINK)이 알려져 있다 있습니다. SLINK 알고리즘
  • 논문은 여기
  • 계산량 $O(N^2)$, 메모리 $O(N)$.
  • 계산량의 $O(N^2)$ 는 각 요소 사이의 거리를 반드시 한 번은 계산해야 하기 때문입니다. $O(N)$ 의 메모리는 결과의 저장을 위해서 반드시 필요.

  • 계통수(dendrogram)를 요소 N의 배열 2개 $\Pi$, $\Lambda$ 로 표현한다. 논문에서는 pointer representation이라고합니다.
  • $\Pi$ : 소속된 클러스터의 index를 저장한다. 클러스터의 index는 클러스터 내의 node의 index로 가장 큰 것.
  • $\Lambda$ : 노드가 클러스터에 속할 때의 거리를 유지합니다.


  • 예를 들어, 다음과 같은 dendrogram 을 표현할 때, $\Pi$, $\Lambda$ 는 각각 다음과 같이 된다.

  • SLINK는 이 두 벡터를 생성하고 왼쪽에서 계산합니다.

    • algorithm


  • 배열의 왼쪽(인덱스가 작은 쪽)으로부터 차례로 dendrogram을 갱신해 간다.
  • 왼쪽의 n개로 dendrogram을 작성해, 가장 오른쪽에 요소를 추가해 기존의 데이터를 갱신해 가는 이미지 

    • pi = Array.new(N, 0)
lambda = Array.new(N, 0.0)

N.times do |n|
  # STEP 1
  pi[n] = n
  lambda[n] = Float::INFINITY

  # STEP 2
  m = Array.new(n) {|idx| d(n, idx) }

  # STEP 3
  n.times do |i|
    parent = pi[i]
    if lambda[i] >= m[i]
      m[parent] = [ m[parent], lambda[i] ].min
      lambda[i] = m[i]
      pi[i] = n
    else      
      m[parent] = [ m[parent], m[i] ].min
    end
  end

  # STEP 4
  n.times do |i|
    parent = pi[i]
    pi[i] = n if lambda[i] >= lambda[parent]
  end
end
  • STEP 1: 가장 오른쪽에 요소(n)를 추가합니다. 이 때 pi [n] = n, lambda [n] = infinity가됩니다.
  • STEP 2: 배열 m에 i번째 요소와의 거리를 저장한다. 이 배열 m은 순차적으로 갱신되어 간다
  • STEP 3:
  • lambda[i]>=m[i] 일 때 (i와 n 사이의 거리가 기존 요소보다 가까울 때),
  • parent와 n 사이의 거리 m[parent]를 d(i,parent), d(parent,n) 중 짧은 쪽으로 업데이트합니다. (i와 n은 같은 클러스터에 속하기 때문에)
  • lambda[i]를 m[i]로 업데이트
  • 부모를 n으로 업데이트

  • lambda[i]
  • m[parent] 를 d(parent,n), d(i,n) 의 어느쪽이든 짧은 쪽으로 갱신. parent와 n의 거리를 계산하기 위해서는 아이와 n의 거리와도 비교할 필요가 있다


  • STEP 4:
  • 노드 i의 부모 pi가 n으로 업데이트 될 때 노드 i의 부모를 n으로 변경

    • 【ASP.NET Core】 JSON 파일에서 정적으로 형식화 된 구성 정보를 쉽게 얻는 방법
    Arrooow (iOS 게임) 솔버 만들기

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage