계층적 군집화 플랫폼에서 근접 이웃 결합 주기는 하이브리드 Ward 방법의 첫 번째 단계에 사용됩니다. 이 작업은 계층적 군집화 루틴에 전달되는 테이블의 크기를 줄이기 위해 수행됩니다. 근접 이웃 결합 주기 알고리즘의 규격은 다음과 같습니다.
하이브리드 목표
알고리즘이 중지되기 전에 허용되는 최대 군집 수를 지정합니다. 기본값은 400입니다.
하이브리드 주기
알고리즘이 중지되기 전에 수행되는 근접 이웃 결합 주기의 최소 수를 지정합니다. 기본값은 30입니다.
하이브리드 초기 K
근접 이웃 결합 주기에 사용되는 초기 이웃 수를 지정합니다. 기본값은 10입니다.
근접 이웃 결합 주기 알고리즘은 다음 단계를 반복합니다.
1. 최근접 이웃을 효율적으로 찾기 위해 VP(Vantage-Point, 기준점) 트리가 생성됩니다.
2. 각 항목마다 k개의 최근접 이웃이 결정됩니다.
3. 근접 이웃 쌍이 거리별로 정렬됩니다.
4. 거리가 가장 짧은 쌍의 절반에 대해 각 쌍의 항목이 이 주기에서 다른 항목과 아직 결합되지 않은 경우 해당 항목을 결합합니다. 결합된 항목은 다음 주기의 항목이 됩니다.
5. 최소 주기 수(하이브리드 주기)에 도달할 때까지 step 1 ~ step 4를 반복합니다.
– 항목 수가 하이브리드 목표보다 작거나 같으면 중지합니다.
– 항목 수가 하이브리드 목표보다 큰 경우 항목 수가 하이브리드 목표 미만이 될 때까지 step 1 ~ step 4를 계속 반복합니다.
각 주기에서 결합된 쌍의 수가 적으면 다음 주기에 대해 최근접 이웃 수, 즉 k가 증가합니다. k의 값은 이전 주기에서 충분한 수의 쌍이 결합되면 이후 주기에서 감소할 수 있습니다. k의 값은 다음 규칙에 따라 증가하고 감소합니다.
• step 4에서 20% 미만의 쌍이 결합되면 k 값이 10씩 증가합니다.
• step 4에서 10% 미만의 쌍이 결합되면 k 값이 20씩 증가합니다.
• step 4에서 5% 미만의 쌍이 결합되면 k 값이 30씩 증가합니다.
• step 4에서 30%를 초과하는 쌍이 결합되면 k 값이 10씩 감소합니다.