[Cluster Analysis] Measure Clustering

Requirements of Clustering

Clustering 알고리즘을 어떤 측면에서 평가할 것인가에 대한 기준이다.

모든 조건을 만족하는 알고리즘은 존재하지 않는다.

 

• Attribute type
  • 다른 type의 attribute을 다룰 수 있는가
  • ability to deal with different types of attributes
• Dynamic data
  • dynamic data를 다룰 수 있는가
  • ability to handle dynamic data
  • 데이터가 변하는 동적 상황에서 clustering에 대한 overhead가 크지 않은가
• Shape of cluster
  • 임의의 모양의 cluster를 찾을 수 있는가
  • discovery of clusters with an arbitarray shape
  • 같은 cluster로 분류되야 함에도 알고리즘에 따라 쪼개려고 할 수 있다.
  • 별모양 등의 cluster는 찾지 못하고 원만 가능한 알고리즘이 존재한다. 
  • KNN은 취약하다.
• Domain knowledge/input parameter
  • domain knowledge나 input parameter이 많지 않은가
  • minimal requirements for domain knowledge to determine input parameters
  • 배경지식이 필요하거나 parameter를 잘 세팅해야만 하는 알고리즘은 별로이다.
• Noise/Outlier
  • noise나 outliers을 다룰 수 있는가
  • able to deal with noises and outliers
  • noise나 outlier에 민감하거나 취약한 것은 별로이다.
• Record order
  • input record의 순서에 따라 결과가 변하지 않은가
  • insensitive to the order of input records
  • input record의 순서에 따라 결과가 변하는 것은 별로이다.
  • BIRCH는 input record의 순서에 따라 결과가 달라진다.
• High dimensionality : 높은 차원에 대해서도 clustering이 가능한가
• Scalability : data가 증가함에 따라 exponential하게 시간이 증가하면 안된다.
• Constraints
  • user가 제시한 constraint을 충족할 수 있는가
  • incorporation of user-specified constraints

 

---

Good Clustering

좋은 clustering의 조건은 다음과 같다.

• high intra-class similarity : class 내의 similairty는 높다.
• low inter-class similarity : class 간의 similarity는 낮다.

 

Clustering의 quality의 결과는 아래의 요소에 의해 결정된다.

• 사용된 similarity measure
• smililarity measure의 구현 방법
• hidden pattern을 얼마나 잘 찾아내는지

 

---

Measure Clustering

Dissimilarity/similarity metric

Distance function으로 표현된 dissimilarity/similarity을 이용하여 clustering의 quality을 평가한다.

 

Distance function은 attribute type에 따라 다르게 설정된다.

다른 variable들에 대해 weigth을 달리 설정하여 계산할 수 있다.

 

Qaulity Function

두 object 사이의 similarity를 측정하는 distance function과 cluster의 goodness를 측정하는 quality function은 다르다.

얼마나 좋은지는 주관적이기 때문에 절대적으로 결정하기는 어렵다.