[클러스터링] 클러스터링의 평가

클러스터링의 평가

데이터 세트에 따라 여러 클러스터링 방법을 적용할 수 있는데, 그 중 어떤 클러스터링 결과가 좋은지 평가해야할 필요가 있다. 일반적으로 클러스터링 평가는 데이터 세트에 대한 클러스터링 분석의 적용성과 구성한 클러스터링 결과의 품질을 기준으로 삼는다. 클러스터링 측정에 주요한 작업에는 다음과 같은 것들이 포함된다.

• 클러스터링 경향성 측정
  어떤 주어진 데이터 세트에서 필연적인 구조가 있는지 평가
• 클러스터링 숫자 결정
  정확한 클러스터 분류를 위해 적절한 클러스터 갯수를 추정
• 클러스터링 품질 측정
  클러스터링 알고리즘을 데이터 세트에 적용했을 때 그 품질을 평가

클러스터링 경향성 측정

주어진 데이터세트에 필연적인 구조가 있는지 확인한다. 가령 균등하게 분포되어있는 데이터세트의 경우 알고리즘을 통해 클러스터 분류는 할 수 있으나 데이터 자체가 본래 균일하게 분포하기 때문에 별다른 정보를 얻을수 없고 결과적으로 의미 없는 클러스터 분류가 될 수 있다. 즉 데이터가 균일한 분포인지 확인해보는 과정이 필요한데 대표적인 방법으로 홉킨스 통계(Hopkins Statistic)라는 간단하고 효율성 높은 통계 기법을 소개한다.

홉킨스 통계(Hopkins Statistic)

공간 상에서 공간에 퍼져 있는 변수의 임의성을 확인하는 공간 통계 테스트 기법으로 어떤 데이터 세트 D가 랜덤 변수 o에대한 샘플이라고 가정하면, 주어진 데이터세트의 데이터 공간 상에서 o가 균일 분포(Uniform distribution)와 상의한 정도를 측정할 수 있다. 과정은 아래와 같다.

1. D의 공간 위에 일정한 간격으로 n개의 점 p1, ..., pn을 배치한다. 이때 모든 점 pi(1≦i≦n)에 대해 가장 가까운 이웃 한 점 v(v∈D)를 찾을 수 있다. pi와 v사이의 거리를 xi라 한다.
   
   
2. 다시 균일한 확률로 D에서 n개의 점 샘플 q1, ..., qn을 추출한다. 모든 qi(1≦i≦n)에 대해서도 같은 방법으로 qi에서 가장 가까운 D-{qi} 중의 한 점 u를 찾을 수 있다. 그리고 qi와 가장 가까운 이웃 u(u∈D-{qi}) 사이의 거리를 yi라 하면
   
   
3. 마지막으로 아래 식으로 홉킨스 통계치 H를 계산한다.
   

만약 데이터세트 D의 분포가 균일하다면  와 의 값이 거의 비슷한 값이 되어 H는 0.5에 가까울 것이다. 그러나 D의 분포가 불균일하여 여러 소집합이 존재한다면 보다 가 훨씬 작은 값이 되어 H값이 0에 가까울 것이다. 이때 귀무가설은 균일 분포의 가설, 즉 D가 공간상에 균일하게 분포해서 의미 있는 클럿그터가 존재하지 않는다는 가설이다. 이에 반하는 불균일 가설, 즉 D의 분포가 일정치 않아 클러스터 구조가 존재한다는 가정은 대안 가설이다. 0.5를 역치로 두고 홉킨스 수치를 반복계산, 대안 가설을 거부할 수 있는지 알아본다. 만약H>0.5인 경우가 대부분이라면 데이터세트 D 상에 통계적으로 유의미한 클러스터가 존재할 가능성이 낮다는 것이다.

클러스터링 숫자(k값) 결정

만약 전체 데이터셋을 한개의 클러스터로 잡는다면 축약성은 최대가 되지만 분석의 의미가 없어진다. 반대로 데이터세트의 오브젝트 각각의 클러스터로 잡는다면 정확성은 높더라도 데이터 종합에는 아무런 도움이 되지 못한다. 따라서 적절한 클러스터 숫자(k값)을 결정하는것은 매우 중요한 단계이다.

• 로 계산하기
  전체 데이터세트의 오브젝트 숫자를 n개라 할때, k값을 로 계산하며, 이때 클러스터마다 개의 데이터 점을 포함한다.
• 엘보우 그래프(elbow graph)이용하기
  
  클러스터 수의 함수로 설명된 분산의 비율을 조사한다. 변화 추이가 급격히 전환하는 변환점(turning point)을 이용하여 적절한 k값을 결정한다.
  
  
• 교차검증(cross-validation) 이용하기
  데이터 양이 충분치 않을때 효과적으로 적용될수 있다. 데이터를 m개의 부분으로 나누고 m-1개의 부분으로 클러스터링 모델을 만들고 나머지 하나를 이용해 클러스터링의 품질을 측정한다.

<출처 : 데이터 마이닝 개념과 기법>