근린 연쇄 알고리즘

클러스터 분석 이론에서 가장 가까운 이웃사슬 알고리즘은 집적 계층 군집을 위한 몇 가지 방법을 가속화할 수 있는 알고리즘입니다.이러한 방법은 점 집합을 입력으로 사용하고 작은 군집의 쌍을 반복적으로 병합하여 더 큰 군집을 형성하여 점 군집의 계층을 만드는 방법입니다.가장 가까운 이웃사슬 알고리즘을 사용할 수 있는 클러스터링 방법에는 Ward의 방법, 완전한 링크 클러스터링 및 단일 링크 클러스터링이 있습니다.이러한 방법들은 모두 가장 가까운 두 클러스터를 반복적으로 병합하여 작동하지만 클러스터 간의 거리에 대한 다른 정의를 사용합니다.가장 가까운 이웃사슬 알고리즘이 작동하는 군집 거리는 축소 가능 거리라고 불리며 특정 군집 거리 사이의 단순한 부등식을 특징으로 합니다.

알고리즘의 주요 개념은 클러스터의 가장 가까운 인접 그래프에서 경로를 따라 병합하는 클러스터의 쌍을 찾는 것입니다.이러한 모든 경로는 결국 서로 가장 가까운 인접 클러스터 쌍으로 종료되며 알고리즘은 병합하는 쌍으로 해당 클러스터 쌍을 선택합니다.각 경로를 최대한 재사용하여 작업을 절약하기 위해 알고리즘은 스택 데이터 구조를 사용하여 이어지는 각 경로를 추적합니다.이 방법으로 경로를 추적함으로써 근접 근접 체인 알고리즘은 항상 근접한 클러스터 쌍을 검색하여 병합하는 방식과는 다른 순서로 클러스터를 병합합니다.그러나 이러한 차이에도 불구하고 항상 동일한 클러스터 계층을 생성합니다.

가장 가까운 이웃사슬 알고리즘은 군집화할 점 수의 제곱에 비례하는 시간 내 군집을 구성합니다.또한 입력이 명시적 거리 매트릭스 형태로 제공되는 경우 입력 크기에 비례합니다.이 알고리즘은 클러스터 간 거리를 일정 시간 계산할 수 있는 Ward 방법과 같은 클러스터링 방법에 사용되는 경우 포인트 수에 비례하는 메모리 양을 사용합니다.그러나 다른 클러스터링 방법에서는 클러스터 쌍 간의 거리를 추적하는 보조 데이터 구조에서 더 많은 양의 메모리를 사용합니다.

배경

데이터 분석의 많은 문제는 데이터 항목을 밀접하게 관련된 항목의 클러스터로 그룹화하는 것과 관련이 있습니다.계층형 클러스터링은 클러스터가 데이터 항목의 엄격한 파티션이 아닌 계층 또는 트리 같은 구조를 형성하는 클러스터 분석 버전입니다.경우에 따라 이 유형의 클러스터링은 여러 다른 규모의 클러스터 분석을 동시에 수행하는 방법으로 수행될 수 있습니다.그 외의 분석 대상 데이터는 자연스럽게 미지의 트리 구조를 가지며, 분석을 실시함으로써 그 구조를 회복하는 것이 목적이다.이들 두 종류의 분석은 예를 들어 생물학적 분류법에 대한 계층적 군집화의 적용에서 볼 수 있다.본 어플리케이션에서는 서로 다른 생물들이 서로 다른 규모 또는 유사성 수준(종, 속, 과 등)의 군집으로 분류된다.이 분석은 동시에 현 시대의 유기체들의 다단계 그룹화를 제공하며, 과거에 이러한 ^[1]유기체를 만들어냈던 가지치기 과정이나 진화 나무를 정확하게 재구성하는 것을 목표로 한다.

군집화 문제에 대한 입력은 일련의 ^[2]점으로 구성됩니다.군집은 점의 적절한 부분 집합이고 계층적 군집은 군집 내 임의의 두 군집이 내포되거나 분리된 특성을 가진 최대 군집 집합입니다.또는 계층형 클러스터링은 포인트가 있는 바이너리 트리로 나타낼 수 있습니다.클러스터링 클러스터는 ^[3]트리의 각 노드에서 하강하는 하위 트리의 포인트 세트입니다.

집적 클러스터링 방법에서 입력은 또한 포인트에 정의된 거리 함수 또는 그 차이점의 수치측정을 포함한다.거리 또는 유사성은 대칭이어야 한다. 즉, 두 점 사이의 거리는 어느 점을 먼저 고려하느냐에 따라 달라지지 않는다.그러나 미터법 공간의 거리와 달리 삼각 ^[2]부등식을 만족시킬 필요는 없다.다음으로, 차분 함수를 점의 쌍에서 클러스터의 쌍으로 확장한다.클러스터링 방법에 따라 이 확장은 다양한 방법으로 수행됩니다.예를 들어 단일 링크 클러스터링 방법에서는 두 클러스터 간의 거리가 각 클러스터에서 두 점 사이의 최소 거리로 정의됩니다.클러스터 간의 거리를 고려할 때 계층형 클러스터링은 처음에 각 점을 자체 단일 점 클러스터에 배치한 다음 가장 가까운 클러스터 ^[2]쌍을 병합하여 반복하여 새 클러스터를 형성하는 그리디 알고리즘에 의해 정의될 수 있습니다.

이 그리디 알고리즘의 병목현상은 각 단계에서 병합할 2개의 클러스터를 찾는 하위 문제입니다.동적 클러스터 집합에서 가장 가까운 클러스터 쌍을 반복적으로 찾는 알려진 방법은 가장 가까운 쌍을 빠르게 찾을 수 있는 데이터 구조를 유지하기 위해 초선형 공간이 필요하거나 각 가장 가까운 ^[4][5]쌍을 찾는 데 선형 시간보다 더 오래 걸립니다.근접 네이버 체인알고리즘에서는 클러스터 쌍을 다른 순서로 Marge함으로써 그리디 알고리즘보다 적은 시간과 공간을 사용합니다.이렇게 하면 가장 가까운 쌍을 반복적으로 찾는 문제를 피할 수 있습니다.그럼에도 불구하고 많은 유형의 클러스터링 문제에 대해 병합 순서가 ^[2]다르더라도 그리디 알고리즘과 동일한 계층적 클러스터링을 제공할 수 있음을 보장할 수 있습니다.

알고리즘

직관적으로 가장 가까운 이웃 연쇄 알고리즘은 서로 가장 가까운 이웃인 ^[2]한 쌍의 군집에 도달할 때까지 각 군집이 이전 군집의 가장 가까운 이웃인 A → B → C → ... 군집의 사슬을 반복적으로 따릅니다.

보다 상세한 것에 대하여는, 알고리즘은 다음의 ^[2][6]순서를 실행합니다.

• 각 입력점에 대해 1개씩 n개의 원포인트 클러스터로 구성되도록 활성 클러스터 집합을 초기화합니다.
• S를 스택 데이터 구조(처음에는 비어 있음)로 하고 요소가 활성 클러스터가 됩니다.
• 클러스터 집합에 클러스터가 두 개 이상 있는 경우:
  • S가 비어 있는 경우 활성 클러스터를 임의로 선택하여 S에 푸시합니다.
  • C를 S의 맨 위에 있는 활성 군집이라고 합니다. C에서 다른 모든 군집까지의 거리를 계산하고 D를 가장 가까운 다른 군집이라고 합니다.
  • D가 이미 S에 있는 경우 C의 직속 전임자여야 합니다.S에서 두 클러스터를 팝하고 병합합니다.
  • 그렇지 않으면 D가 S에 없는 경우 S에 푸시합니다.

1개의 클러스터에 동일한 근접 네이버를 여러 개 가질 수 있는 경우 알고리즘에는 일관된 타이브레이크 규칙이 필요합니다.예를 들어 임의의 인덱스 번호를 모든 클러스터에 할당하고 인덱스 번호가 가장 작은 클러스터(가장 가까운 네이버 중)를 선택할 수 있습니다.이 규칙에 의해 알고리즘에서 특정 종류의 부정합 동작을 방지할 수 있습니다.예를 들어 이러한 규칙이 없으면 인접 클러스터 D가 C의 ^[7]이전 버전보다 스택 내에서 더 빨리 발생할 수 있습니다.

시간과 공간 분석

루프를 반복할 때마다 클러스터의 가장 가까운 네이버에 대한 단일 검색이 수행되며, 스택에 클러스터 1개를 추가하거나 클러스터에서 클러스터 2개를 제거합니다.모든 클러스터는 스택에 한 번만 추가됩니다. 다시 삭제되면 즉시 비활성화되고 병합되기 때문입니다.스택에 추가되는 클러스터는 총 2n~2개입니다.초기 세트의 싱글 포인트클러스터 n개와 클러스터링을 나타내는 바이너리 트리의 루트 이외의 내부 노드 n~2개가 있습니다.따라서 알고리즘은 2n - 2 푸시 반복과 n - 1 팝 ^[2]반복을 수행합니다.

이러한 각 반복은 가장 가까운 인접 라우터를 찾기 위해 클러스터 간 거리를 n~1회 스캔하는 데 시간을 소비할 수 있습니다.따라서 총 거리 계산 수는 3n² 미만입니다.같은 이유로 이들 거리 계산 이외의 알고리즘에 의해 사용되는 총 시간은 O²(^[2]n)입니다.

데이터 구조는 액티브클러스터의 집합과 액티브클러스터의 서브셋을 포함하는 스택뿐이기 때문에 필요한 공간은 입력 ^[2]포인트 수가 선형적입니다.

정확성

알고리즘이 올바르려면 알고리즘의 스택에서 상위2개의 클러스터를 팝핑하여 Marge하면 스택 상의 나머지 클러스터가 가장 가까운 네이버 체인을 형성하는 속성이 유지됩니다.또한 일반적으로 Gready 알고리즘이 가장 가까운 이웃사슬 알고리즘과는 다른 순서로 Marge를 실행하더라도 알고리즘 중에 생성되는 클러스터는 모두 Gready 알고리즘에 의해 항상 Marge되는 클러스터와 같아야 합니다.이러한 속성은 모두 클러스터 ^[2]간의 거리를 측정하는 방법에 대한 특정 선택에 따라 달라집니다.

이 알고리즘의 정확성은 환원성이라고 하는 거리 함수의 특성에 의존합니다.이 속성은 브루누헤(1977년)에 의해 상호 가장 가까운 이웃 쌍을 사용했지만 가장 가까운 ^[8]이웃의 사슬을 사용하지 않은 이전의 클러스터링 방법과 관련하여 식별되었다.클러스터상의 거리함수 d는 A와 B가 서로 가장 가까운 이웃이 되도록 그리디 계층 클러스터링의 3개의 클러스터 A, B, C에 대해 다음과 같은 부등식이 ^[2]유지되면 축소할 수 있도록 정의된다.

d(A b B, C) min min(d(A, C), d(B, C)).

거리 함수에 환원성 속성이 있는 경우, 2개의 클러스터 C와 D를 Marge하면 가장 가까운E 네이버가 C와 D 중 하나일 경우에만 변경될 수 있습니다.이것은 가장 가까운 네이버체인 알고리즘에 2가지 중요한 결과를 가져옵니다.먼저 이 속성을 사용하면 가장 가까운 네이버가 비활성화되면 즉시 ^[2]스택에서 삭제되기 때문에 알고리즘의 각 단계에서 스택S 위의 클러스터가 가장 가까운 네이버의 유효한 체인을 형성한다는 것을 알 수 있습니다.

둘째, 그리고 더욱 중요한 것은 두 클러스터 C와 D가 모두 탐욕 계층 클러스터링에 속하고 임의의 시점에서 서로 가장 가까운 인접 관계에 있는 경우, 그들은 병합될 때까지 서로 가장 가까운 인접 관계를 유지해야 하기 때문에 탐욕 클러스터링에 의해 병합된다는 것입니다.따라서 가장 가까운 네이버체인 알고리즘에 의해 검출된 서로 가장 가까운 네이버쌍은 모두 그리디 알고리즘에 의해 검출된 클러스터 쌍이기 때문에 가장 가까운 네이버체인 알고리즘은 그리디 ^[2]알고리즘과 정확히 같은 클러스터링을 계산합니다(단, 순서가 다릅니다).

특정 클러스터링 거리에 적용

워드의 방법

Ward의 방법은 두 군집 A와 B 사이의 차이를 하나의 큰 군집으로 병합하면 군집 ^[9]중심까지의 점의 평균 제곱 거리가 증가하는 양으로 측정하는 응집 군집 분석 방법입니다.그것은,

$\displaystyle d(A,B)=\sum _{x\in A,y\in B}{\frac {d^{2}(x,y)}-\sum _{x,y}{\frac {d^2}(x,y)}-{x}-{x}-{x,{x}-{x},{x}}$

$중심{\displaystyle {}_{}}$ c $(\$$})$ 및 $카디널리티{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ A$(\$로 표현됩니다.2개의 클러스터 중 A$}$개의$$ 클러스터는 더 간단한 공식을 $가지고$ 있습니다.

${\displaystyle d(A,B)=param frac {d^{2}(c_{a},c_{b}){1/n_{A}+1/n_{B}}}},}$

거리당 일정한 시간 계산으로 계산할 수 있습니다.특이치에 매우 민감하지만 Ward의 방법은 일반적으로 군집의 둥근 모양과 각 단계에서 ^[10]군집 내에서 가장 작은 분산을 갖는 군집화라는 원칙적인 정의 때문에 집적 군집화의 가장 일반적인 변형입니다.또는 이 거리는 새 군집과 두 이전 군집 사이의 k-평균 비용 차이로 볼 수 있습니다.

Ward의 거리도 축소할 수 있습니다. 병합된 클러스터의 거리로부터 ^[9][11]병합된 클러스터의 거리를 계산하는 다른 공식에서 더 쉽게 알 수 있습니다.

${\displaystyle d(A\cup B,C)=420 frac {n_{A}+n_{C}}{n_{A}+n_{B}+n_{C}}d(A,C)+{\frac {n_{B}+n_{C}}{n_{A}+n_{B}+n_{C}}d(B,C)-{\frac {n_{C}}{n_{A}+n_{B}+n_{C}}}d(A,B).}$

이와 같은 거리 갱신 공식은 Lance & Williams(1967년)의 작품에서 따온 "Lance-Williams 유형의 공식"이라고 불린다.d${\displaystyle (A,}$ $)$ {{$displaystyle d(A$$$, B$)}$가 우측의 3가지 거리 중 가장 작을 $경우{\displaystyle }$($A\displaystyle$ A$}$와 B$\displaystyle$ B$}$가 서로 가장 가까운 이웃인 $경우{\displaystyle }$) 해당 기간의 마이너스 기여는 $(\$}) $계수$에 의해 취소됩니다.다른 두 항 중 하나는 다른 두 거리의 가중 평균에 양의 값을 더하는 것입니다.따라서 조합된 거리는 $최소$ ${\displaystyle d(}$A${\displaystyle ,}$ C$)$ {$displaystyle$ d$(A, C)}$ 및$$ $d{\displaystyle (B,}$ $)$ {$displaystyle$ d($B$, C$)\}$의 $최소값$과 항상 $같으므로$ 환원성의 $정의를 충족합니다.$

Ward의 거리는 축소 가능하기 때문에 Ward의 거리를 사용하는 가장 가까운 이웃사슬 알고리즘은 표준 그리디 알고리즘과 정확히 동일한 클러스터링을 계산합니다.일정 차원의 유클리드 공간에서의 n개의 점에 대해서는, 시간 O²(n)와 공간 O(^[6]n)가 걸린다.

전체 링크 및 평균 거리

완전 링크 클러스터링 또는 원근 클러스터링은 클러스터 간의 차이를 두 클러스터로부터의 두 지점 사이의 최대 거리로 정의하는 집적 클러스터링의 한 형태입니다.마찬가지로 평균 거리 클러스터링에서도 평균 쌍별 거리를 차이점으로 사용합니다.Ward의 거리처럼 이 두 가지 형태의 군집은 Lance-Williams 유형의 공식을 따릅니다.완전한 링크에서는 $거리{\displaystyle }$ d${\displaystyle (Ab}$ B${\displaystyle }$、${\displaystyle C}$ )$${ $displaystyle$ d$($$A\cup$ B,$C)$ }는$$$$ 2개의 $거리{\displaystyle }$ d$A,$ 및 $d{\displaystyle (B,}$ ${\displaystyle C})$의 최대값입니다.따라서 $displaystyle$ d$(B, C)$는 이들 최소2개의 거리와 동일합니다.평균 거리의 $경우{\displaystyle }$ d${\displaystyle (}$ ${\displaystyle Ab}$B${\displaystyle }$,$$C ) { $displaystyle$d ($A$${\displaystyle }$\ $cup$B ,$C$ ) } $just$ 、${\displaystyle }$$displaystyle$$$d ($A$ ,${\displaystyle }$C )$$${\displaystyle (}$ ${\displaystyle \mathrm{displaystyle}}$ d ( A , $C$${\displaystyle }$)$$$d{\displaystyle }$ displaystyle d $( B$ ${\displaystyle ,}$ $C )$의 가중치 평균입니다.이 역시 최소2개의 거리만큼 큰 거리입니다.따라서 이 두 경우 모두 거리는 축소할 ^[9][11]수 있습니다.

Ward의 방법과 달리 이 두 가지 형태의 군집화에는 군집 쌍 간의 거리를 계산하는 상수 시간 방법이 없습니다.대신 모든 클러스터 쌍 간의 거리 배열을 유지할 수 있습니다.두 클러스터가 병합될 때마다 공식을 사용하여 병합된 클러스터와 다른 모든 클러스터 간의 거리를 계산할 수 있습니다.이 어레이를 클러스터링 알고리즘으로 유지하려면 시간과 공간 O(n²)가 필요합니다.근접 인접 체인 알고리즘은 이러한 경우에 대한 그리디 알고리즘과 동일한 클러스터링을 찾기 위해 이 거리 배열과 함께 사용할 수 있습니다.이 어레이를 사용하는 총 시간과 공간도 O(n²)^[12]입니다.

동일한 O(n²) 시공간 경계는 거리 매트릭스 위에 쿼드트리 기반의 priority 큐 데이터 구조를 겹쳐 표준 그리디 클러스터링 알고리즘을 실행하기 위해 사용하는 기술에 의해 다른 방법으로 달성될 수도 있습니다.이 쿼드트리 방식은 축소할 ^[4]수 없는 클러스터링 방식에서도 작동하기 때문에 더 일반적입니다.단, 가장 가까운 인접 라우터 체인알고리즘은 단순한 데이터 ^[12]구조를 사용하면서 시간과 공간의 경계와 일치합니다.

단일 링크

집적 계층형 클러스터링의 ^[11]가장 오래된 형태인 단일 링크 또는 가장 가까운 이웃 클러스터링에서는 클러스터 간의 차이가 두 클러스터로부터의 두 점 사이의 최소 거리로 측정됩니다.이런 차이점을 가지고

$\displaystyle d(A\cup B,C)=\min(d(A,C),d(B,C),}$

(단일 연결은 랜스-윌리엄스의 ^[9][11]공식에도 따르지만, 음의 계수를 사용하여 감소성을 증명하는 것이 더 어렵다.)

완전한 링크 및 평균 거리 계산과 마찬가지로 클러스터 거리 계산의 어려움으로 인해 가장 가까운 이웃사슬 알고리즘이 단일 링크 클러스터링을 계산하기 위해 시간과 공간 O(n²)가 소요됩니다.그러나 단일 링크 클러스터링은 Prim 알고리즘을 사용하여 입력 거리의 최소 스패닝 트리를 계산한 다음 최소 스패닝 트리 에지를 정렬하고 이 정렬 목록을 사용하여 클러스터 쌍의 통합을 유도하는 대체 알고리즘에 의해 보다 효율적으로 찾을 수 있습니다.Prim의 알고리즘 내에서 각 연속되는 최소 스패닝 트리 에지는 부분적으로 구성된 트리를 각 추가 정점에 연결하는 최소 에지의 정렬되지 않은 목록을 통해 순차적 검색을 통해 찾을 수 있습니다.이 옵션을 선택하면 알고리즘이 priority 큐에 있는 정점의 가중치를 조정하는 데 소비하는 시간이 절약됩니다.이러한 방법으로 Prim의 알고리즘을 사용하는 것은 일정시간 ^[13]계산으로 거리에 대한 가장 가까운 이웃사슬 알고리즘으로 달성할 수 있는 최선의 경계를 일치시키는 시간 O(n²)와 공간 O(n)가 필요합니다.

중심 거리

응집 군집 분석에서 일반적으로 사용되는 또 다른 거리 측도는 가중 그룹 ^[9][11]방법이라고도 하는 군집 쌍의 중심 간 거리입니다.거리당 일정한 시간 계산으로 쉽게 계산할 수 있습니다.단, 환원할 수 없습니다.예를 들어, 입력이 등변 삼각형의 세 점 집합을 형성하는 경우, 이러한 두 점을 더 큰 클러스터로 병합하면 클러스터 간 거리가 감소하여 축소 가능성을 위반합니다.따라서 가장 근접한 네이버 체인 알고리즘은 그리디 알고리즘과 동일한 클러스터링을 반드시 찾을 필요는 없습니다.그럼에도 불구하고, Murtagh(1983)는 가장 가까운 이웃사슬 알고리즘이 중심법에 ^[2]"좋은 휴리스틱"을 제공한다고 쓰고 있다.Day & Edelsbrunner(1984)의 다른 알고리즘을 사용하여 이 거리 ^[5]측정의 O(n²) 시간 내에 탐욕 클러스터링을 찾을 수 있습니다.

병합 순서에 민감한 거리

위의 프레젠테이션에서는 병합 순서에 민감한 거리는 명시적으로 허용되지 않습니다.실제로, 그러한 거리를 허용하면 문제가 발생할 수 있습니다.특히, 순서 의존형 클러스터 거리가 존재하며, 이는 감소 가능성을 충족하지만 위의 알고리즘은 최적의 비용으로 계층을 반환합니다.따라서 클러스터 거리가 재귀 공식에 의해 정의되는 경우(위에서 설명한 것 중 일부와 같이), 클러스터 거리가 병합 ^[14]순서에 민감한 방식으로 계층을 사용하지 않도록 주의해야 합니다.

역사

가장 가까운 이웃 연쇄 알고리즘은 1982년 장 폴 벤제크리와^[15] J.^[16] 후안에 의해 개발되고 구현되었다.이 알고리즘은 가장 가까운 ^[8][17]네이버체인을 이용하지 않고 서로 가장 가까운 네이버쌍을 사용하여 계층형 클러스터링을 구축한 이전의 방법에 기초하고 있습니다.

레퍼런스