Distance Measurements

Any distance metric $d({\bf x},{\bf y})$ between two points ${\bf x}$ and ${\bf y}$ must satisfy:

1. $d({\bf x},{\bf y}) \ge 0, \;\;\;\; (d({\bf x},{\bf y})=0\;\;\; \mbox{iff} \;\;\; {\bf x}={\bf y})$;
2. $d({\bf x},{\bf y})=d({\bf y},{\bf x})$;
3. $d({\bf x},{\bf y}) \le d({\bf x},{\bf z})+d({\bf z},{\bf y})$.

where ${\bf z}$ is an arbitrary point.

Several specific distance measurements can be used in the feature space in the process of pattern classification.

• Distance between two points

  
  

  $$d_p({\bf x},{\bf y})=\left[\sum_{n=1}^N \left\vert x_n-y_n \right\vert^p\right]^{1/p}$$
  
  
  where $p$ can take any value such as 1, 2, and infinity.
  • $p=2$, $d_p({\bf x},{\bf y})$ becomes Euclidean distance:
    
    $$d_2({\bf x},{\bf y})=\sqrt{ \sum_{n=1}^N (x_n-y_n)^2 } =[ ({\bf x}-{\bf y})^T({\bf x}-{\bf y}) ]^{1/2}$$
    
    

  • $p=1$, $d_p({\bf x},{\bf y})$ is called city-block distance or Manhattan distance
    
    $$d_1({\bf x},{\bf y}) = \sum_{n=1}^N \vert x_n-y_n \vert$$
    
    
    which is much less costly to compute than the Euclidean distance, as absolute operation is much easier than multiplication and square root operation.

  • $p=\infty$, $d_p({\bf x},{\bf y})$ is so called maximum distance or Chebychev distance
    
    $$d_{\infty}({\bf x},{\bf y}) = max \{ \left\vert x_n-y_n \right\vert,\;\;n=1,\cdots,N \}$$
    
    

  

• Intra-cluster distances (diameters)

  Let $\omega_i=\{{\bf x}_i^{k}, k=1,2,\cdots,K_i\}$ be a set of $K_i$ points all belonging to the ith class or cluster, with $i=1,2,\cdots,C$. This cluster can be represented by either all of its members ${\bf x}_i^{k}, k=1,2,\cdots,K_i$, or the estimation of some statistic parameters, such as the mean vector and covariance matrix of the distribution with the points treated as the samples.

  The mean vector and covariance matrix of the ith distribution with $K_i$ samples can be estimated as
  

  $${\bf m}_i=\frac{1}{K_i}\sum_{{\bf x} \in \omega_i} {\bf x};\;... ...{\bf x} \in \omega_i} ({\bf x}-{\bf m}_i)({\bf x}-{\bf m}_i)^T$$
  
  
  Recall that the density function of a normally distributed random vector ${\bf x}$ is:
  
  $$p(x_1,\cdots, x_N)=N({\bf x}, {\bf m}, {\bf\Sigma})= \frac{1... ...rac{1}{2}({\bf x}-{\bf m})^T{\bf\Sigma}^{-1}({\bf x}-{\bf m})]$$
  
  
  When $N=1$, ${\bf\Sigma}$ and ${\bf m}$ become $\sigma^2$ and $\mu$, respectively, and
  
  $$p(x)=N(x,\mu,\sigma)=\frac{1}{\sqrt{2\pi}\sigma} e^{-(\frac{x-\mu}{\sigma})^2}$$
  
  
  How tight or scattered the samples belonging to a cluster are grouped or distributed can be measured by the following:
  • The max diameter:
    
    $$d_{max}(\omega_i)=\max_{{\bf x},{\bf y}\in \omega_i} d({\bf x},{\bf y})$$
    
    

  • The average diameter:
    
    $$d_{average}(\omega_i)=\frac{1}{K_i(K_i-1)}\sum_{{\bf x},{\bf y}\in\omega_i,{\bf x}\ne {\bf y}} D({\bf x},{\bf y})$$
    
    

  • The average distance from each sample to the mean vector of the cluster:
    
    $$\frac{1}{K_i} \sum_{{\bf x}\in \omega_i} d({\bf x},{\bf m}_i)$$
    
    

  • The covariance ${\bf\Sigma}_i$ is a good measurement of the tightness of the samples, and its determinant $\det [{\bf\Sigma}_i]$ or trace $tr[{\bf\Sigma}_i]$ could be used as such a scalar measurement.

• Distance between a point and a cluster/class of points
  • The max- and min-distances:
    
    $$d_{max}({\bf x}, \omega_i)=\max_{{\bf y}\in \omega_i} d({\bf ... ...bf x}, \omega_i)=\min_{{\bf y}\in \omega_i} d({\bf x},{\bf y})$$
    
    

  • The centroid distance:
    
    $$d_{centroid}({\bf x}, \omega_i)=d({\bf x},{\bf m}_i)$$
    
    

  • The Mahalanobis distance can be used to measure the distance between a pattern point ${\bf x}$ and a class $\omega_i$ of patterns represented by their mean vector ${\bf m}_i$ and the covariance matrix ${\bf\Sigma}_i$:
    
    $$d_M({\bf x}, \omega_i)=({\bf x}-{\bf m}_i)^T {\bf\Sigma}_i^{-1} ({\bf x}-{\bf m}_i)$$
    
    

• Inter-cluster Distances
  • The max- and min-distances:
    
    $$d_{max}(\omega_i, \omega_j)=\max_{{\bf x}\in \omega_i, {\bf y... ...{{\bf x}\in \omega_i,{\bf y}\in \omega_j} d({\bf x},{\bf y})$$
    
    

  • The Hausdorff distance: the maximal distance from samples of one cluster to the nearest sample of another cluster:
    
    $$d_{hausdorff}(\omega_i, \omega_j)=\max\{\; \max_{{\bf x}\i... ...omega_j}[\min_{{\bf x}\in \omega_i} D({\bf x},{\bf y})]\; \}$$
    
    
    To obtain $max_{{\bf x}\in \omega_i}[\min_{{\bf y}\in \omega_j} d({\bf x},{\bf y})]$, we first find the minimum of all distances between a particular ${\bf x}\in \omega_i$ to each of ${\bf y}\in\omega_j$, and then find the maximum of such distances for all ${\bf x}\in \omwega_i$.

  • The average distance between two clusters is the average of all pair-wise distances (e.g., Euclidean) between members of the two classes:
    
    $$d_{average}(\omega_i, \omega_j) =\frac{1}{K_i K_j}\sum_{{\bf x}\in \omega_i,{\bf y}\in \omega_j} d({\bf x},{\bf y})$$
    
    

  • The centroid distance is the distance (e.g., Euclidean) between the centroids (mean vectors) of the two classes:
    
    $$d_{centroid}(\omega_i, \omega_j)=d({\bf m}_i,{\bf m}_j)$$
    
    

  • The Bhattacharyya distance can be used to measure the distance between two classes $\omega_i$ and $\omega_j$ represented by their mean vectors and covariance matrices:

    
    

    $$d_B(\omega_i, \omega_j)=\frac{1}{4}({\bf m}_i-{\bf m}_j)^T ... ...right\vert\;\left\vert{\bf\Sigma}_j\right\vert)^{1/2}}\right]$$
    
    
    Note that the first term measures the difference between the two mean vectors of the two clusters, while the second term measures the difference between the distributions of the two clusters, even though the two mean vectors are the same. The second term is always positive due to the AM-GM inequality of arithmetic mean (AM) and geometric mean (GM):
    
    $$\frac{1}{n}\sum_{i=1}^n x_i \ge \left(\prod_{i=1}^n x_i\right)^{1/n}$$
    
    
    In particular, we can easily show that
    
    $$\frac{x+y}{2} \ge \sqrt{xy},\;\;\;\;\;\mbox{i.e.,}\;\;\;\;\;\log \left( \frac{(x+y)/2}{\sqrt{xy}} \right) \ge 0$$