Hopkins Statistic
31 Jul 2024
Hopkins statistic (Lawson and Jurs 1990)은 데이터셋의 클러스터링 경향을 판단하는 데 사용되는 지표입니다. 데이터가 uniform distribution을 가지는지, 아니면 유의미한 cluster를 내포하는지를 평가하는 데 유용합니다. Hopkins statitic을 사용하면 clustering 분석을 시작하기 전에 데이터가 이에 적합한지 사전 확인하는 데 도움이 될 수 있습니다.
How Hopkins Statistic works
Hopkins statistic 은 다음과 같이 계산됩니다. $D$를 원래의 데이터셋이라고 하면:
- $D$에서 무작위로 $m$개의 데이터 샘플 $(p_1, …, p_m)$을 선택합니다. 이를 집합 $R$이라고 합니다.
- $D$와 같은 범위를 갖는 random uniform distribution $U$로부터 $m$개의 포인트 $(q_1, …, q_n)$를 생성합니다.
- $R$내에서 각 점 $p_i$에 대해, nearest neighbor인 $p_j$까지의 거리를 계산합니다: $w_i=dist(p_i, p_j)$
- $U$의 각 점 $q_i$에 대해, $R$의 nearest neighbor인 $p_j$까지의 거리를 계산합니다: $u_i=dist(q_i, p_j)$
- Hopkins statistic $H$는 아래와 같이 정의됩니다. $d$는 데이터의 차원을 의미합니다: \(H={\Sigma_{i=1}^m u_i^d \over \Sigma_{i=1}^m u_i^d + \Sigma_{i=1}^m w_i^d}\)
Interpretation of Hopkins Statistic
만약 $D$ 가 uniform distribution을 갖는다면, 실제 포인트 간의 거리($\Sigma_{i=1}^n w_i$)와 randomly uniformly 생성된 포인트와의 거리($\Sigma_{i=1}^n u_i$)는 서로 비슷할 것입니다. 이에 따라 $H$가 0.5에 가까워집니다. 한편 $D$에 cluster가 존재하면 $\Sigma_{i=1}^n w_i$은 0에 가까워질 것입니다. 이에 따라 $H$는 1에 가까워질 것입니다.
- $H \approx$ 0.5$: 데이터가 uniform distribution을 가지며, clustering 경향이 없음을 나타냅니다.
- $H \approx 0$: 데이터 포인트들이 규칙적으로 배치되어 있음을 나타냅니다. (e.g. grid)
- $H \approx 1$: 데이터에 강한 clustering 경향이 있음을 나타냅니다.
$H$를 실제로 응용할 때는, $H$가 0.75보다 크다면 데이터가 90% confidence level에서 clustering 경향이 있음을 나타냅니다. 반대로 $H$가 0.5보다 훨씬 낮다면 데이터가 규칙적인 간격을 갖고 분포되어 있음을 의미하며, 해당 데이터는 clustering 분석에 유용하지 않습니다.
$H$를 통해 데이터의 clustering 경향을 확인하기 위해 hopkins statistic을 0.5를 threshold로 잡고 반복적으로 수행할 수 있습니다. 만약 값이 0.5 아래로 점차 떨어지면, 해당 데이터는 clustering 경향이 없는 것으로, 값이 0.5보다 점차 커지면, clustering 경향이 있는 것으로 판단할 수 있습니다.
References
- https://www.datanovia.com/en/lessons/assessing-clustering-tendency/