Davies-Bouldin Index(DBI)

공대생의 팁 2018.12.20 00:29


 Davies-Bouldin Index(DBI)는 Group 내에서의 Distribution과 비교하여 다른 Group간의 분리 정도의 비율로 계산되는 값으로 모든 두 개의 Group 쌍에 대해 각 Group의 크기의 합을 각 Group의 중심 간 거리로 나눈 값으로서 표현되는 함수입니다.


 DBI는 계산이 빠르고 쉬우며 일관성 있는 값을 제시해주는 장점을 가지고 있어 K-means++ 알고리즘과 같이 특정 Group를 분류하는 것을 목적으로 하는 알고리즘의 성능을 정량적으로 비교하는 방식으로 주로 사용됩니다.


 해당 알고리즘을 사용하여 얻은 Group의 결과가 유효할수록 같은 Group 내의 Distribution은 작아져 Group의 크기는 작아지고, 서로 다른 Group간의 거리가 커지므로 DBI값이 작을수록 해당 알고리즘은 유효한 결과를 갖는다고 판단할 수 있겠습니다.


 다음으로 DBI의 수식에 대해 설명해보도록 하겠습니다.



 위 식은 Davies-Bouldin index의 정의입니다. 여기서 Ri는 다음과 같이 정의됩니다.



 즉, Rij의 최대값을 의미하며 i 와 j는 다른 값이어야 한다는 의미입니다. 여기서 Rij는 다음과 같이 정의됩니다


 여기서 Si는 i번째 scatter로 하나의 Group을 의미하며 M은 Si와 Sj의 distance를 나타냅니다. S는 다음과 같이 정의됩니다.

 


 이때 Ti는 cluster i의 벡터 갯수를 나타냅니다 쉽게 말해 하나의 Group에 속해있는 점들의 갯수를 말합니다. 그리고 Ai는 cluster i의 중심 좌표값을 의미합니다. q=1의 경우 Si는 유클리드 거리, q=2의 경우, 각 cluster의 중심에서의 각 샘플 사이의 거리를 표준편차로 나타낸 것이라 할 수 있겠습니다.



 다음으로 M값에 대해 알아보도록 하겠습니다. aki는 n차원 벡터인 ai의 k번째 요소입니다. 이 때 ai는 i번째 cluster의 중심값이라 할 수 있습니다. 즉 이 식안 i번째와 j번째 cluster의 중심 사이의 거리를 나타낸다 할 수 있겠습니다. p = 1일 때, city block 거리(맨하탄 거리)로 표현되며, p = 2일 때, 유클리드 거리로 나타내집니다.


 cluster인 C가 다음과 같은 조건을 만족한다고 가정해봅니다.



 이 때 S는 다음 조건을 만족합니다.


 

 다음으로 R은 다음 조건을 만족합니다.



 다음으로 간단한 예제를 통해 Davies-Bouldin Index에 대해 이해해보도록 합니다.

 



 다음과 같이 점 4개가 주어졌다고 가정하였을 때 점 (1,1)과 점 (1,3)을 중심으로 하였을 때, 각 Group의 중심은 (1,3)과 (3,3)으로 나타낼 수 있겠습니다.





 반면, 점(1,1)과 점(5,1)이 중심이 되었을 때 각 Group의 중심은 (1,2)와 (5,2)로 나타내어집니다.



 위에서 구한  두 가지의 경우들에 대해 각각 DBI값을 구해보겠습니다. p = q = 2라 가정하였을 때, 첫 번째의 경우에서 DBI는 2가 되며 두 번째의 경우에서 DBI는 0.5가 됩니다. 이 결과를 보았을 때 DBI의 값이 작은 두 번째의 경우가 cluster를 좀 더 자세히 구분했다고 말할 수 있겠습니다.




  






출저 : https://ieeexplore.ieee.org/abstract/document/4766909