m 데이터 포인트에 대한 m x m 근접 행렬은 각 노드가 일부 다른 노드에 연결되고 일부 노드 그룹 사이의 에지의 가중치가 쌍별 근접도를 따르는 조밀한 그래프로 정의될 수 있습니다. 각 개체는 서로 유사한 방법을 가지고 있지만 대부분의 데이터 세트에서 개체는 소수의 개체와 거의 동일하고 대부분의 다른 개체와 거의 동일합니다.
이 기능은 실제 클러스터링 프로세스를 시작하기 전에 일부 낮은 유사도(높은 비유사도) 값을 0으로 설정하여 근접도 그래프(행렬)를 희소화하는 데 사용할 수 있습니다. 예를 들어, 정의된 임계값 아래(위)에서 동일한(비유사성)을 갖는 모든 링크를 나누거나 포인트의 k개의 가장 가까운 이웃에 대한 링크만 유지함으로써 희소화를 구현할 수 있습니다. 이 방법은 가장 가까운 이웃 그래프로 알려진 것을 생성합니다.
희소화의 이점은 다음과 같습니다 -
데이터 크기 축소 − 데이터를 클러스터링하기 위해 처리해야 하는 데이터 양이 매우 줄어듭니다. 희소화는 근접 행렬에서 항목의 99% 이상을 제거할 수 있습니다. 이에 따라 관리할 수 있는 문제의 크기가 커집니다.
클러스터링이 더 잘 작동할 수 있음 − 희소화 방법은 개체의 가장 가까운 이웃에 대한 링크를 유지하면서 더 별개의 개체에 대한 연결을 분할합니다. 이것은 객체 영향의 가장 가까운 이웃이 객체 자체와 유사한 클래스(클러스터)에 속한다는 가장 가까운 이웃 원칙을 유지하기 위한 것입니다. 이렇게 하면 노이즈 및 이상값의 영향이 줄어들고 클러스터 간에 구분이 생성됩니다.
그래프 분할 알고리즘을 사용할 수 있음 − 특히 병렬 컴퓨팅 및 집적 회로 설계 분야에서 희소 그래프의 최소 분할 분할을 발견하기 위한 발견적 알고리즘에 대한 많은 작업이 있었습니다. 근접 그래프의 희소화는 Opossum 및 Chameleon과 같은 클러스터링 단계에 대한 그래프 파티셔닝 알고리즘 사용에 적용 가능한 그래프 파티셔닝을 생성합니다.
근접 그래프의 희소화는 실제 클러스터링 알고리즘이 필요하기 이전의 원래 단계로 간주되어야 합니다. 최상의 희소화는 근접 행렬을 원하는 클러스터와 상관관계가 있는 연결된 요소로 나눌 수 있지만 실제로는 이것이 나타납니다.
개별 에지가 두 개의 클러스터를 연결하거나 개별 클러스터가 연결이 끊긴 여러 하위 클러스터로 분할되는 것은 간단합니다. 실제로 Jarvis-Patrick과 SNN이 밀도 기반 클러스터링을 사용할 때 희소 근접성 그래프가 변경되어 새로운 근접성 그래프를 생성하는 것을 볼 수 있습니다. 이 새로운 근접성 그래프는 희소화될 수 있습니다. 클러스터링 알고리즘은 이러한 모든 전처리 절차의 결과인 근접 그래프와 함께 작동합니다.