캐노피 클러스터링 알고리즘

캐노피 클러스터링 알고리즘은 앤드류 맥컬럼, 카말 나이감, 라일 언가르가 2000년 도입한 무감독 사전클러스터링 알고리즘이다.^[1]K-평균 알고리즘이나 계층적 군집화 알고리즘의 사전 처리 단계로 자주 사용된다.데이터 세트의 크기 때문에 다른 알고리즘을 직접 사용하는 것이 비현실적일 수 있는 대규모 데이터 세트의 클러스터링 작업을 가속화하기 위한 것이다.

설명

알고리즘은 T 1 ${\displaystyle {임계값\mathrm{}}_{}}$ $T{\displaystyle {}_{}}$ 1 ${\$${\displaystyle {느린\mathrm{}}_{}}$ 거리$)$과 T 2 {\displaystyle $T_{2}}($긴장 거리)를 사용하여 다음과 같이 진행한다. 여기서 > ${\$$T_{2}}.$^[1][2]

1. 클러스터링할 데이터 지점 집합부터 시작하십시오.
2. 이 점을 포함하는 새 '캐노피'를 시작하여 세트에서 점을 제거한다.
3. 세트에 남아 있는 각 포인트에 대해 캐노피의 첫 번째 포인트까지의 거리가 느슨한 ${\displaystyle {거리\mathrm{}}_{}}$ T ${\$}보다 작은 경우 새 캐노피에 할당한다$.$
4. 점의 거리가 T ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}점보다 더 작은 경우, 원래 세트에서 점의 거리를 제거한다$.$
5. 2단계부터 클러스터 집합에 더 이상 데이터 점이 없을 때까지 반복하십시오.
6. 비교적 저렴하게 클러스터된 이러한 캐노피들은 더 비싸지만 정확한 알고리즘을 사용하여 하위 클러스터링될 수 있다.

중요한 점은 개별 데이터 포인트가 여러 개의 캐노피에 포함될 수 있다는 점이다.추가 속도 향상으로 3단계에 대해 대략적이고 빠른 거리 메트릭을 사용할 수 있으며, 4단계에는 더 정확하고 느린 거리 메트릭을 사용할 수 있다.

적용가능성

알고리즘은 거리 함수를 사용하고 거리 임계값의 사양을 요구하기 때문에 차원 높은 데이터에 대한 적용성은 치수성의 저주에 의해 제한된다.값싸고 근사적인 저차원 거리 함수를 이용할 수 있어야만 생산되는 캐노피들은 K-평균이 생산한 군집을 보존할 수 있다.

그 이점은 다음과 같다.

• 각 단계에서 비교해야 하는 교육 데이터의 인스턴스 수가 감소한다.
• 결과 군집이 개선되었다는 몇 가지 증거가 있다.^[3]

참조