ML-Distance Measure

Key to clustering. “similarity” and “dissimilarity” can also commonly used terms.

There are numerous distance functions for

• Different types of data
  • Numeric data
  • Nominal data
• Different specific applications

Minkowski Distance

We denote distance with: $dist(x_i,x_j)$, where $x_i$ and $x_j$ are data points (vectors)

$$dist(x_i,x_j)=((x_{i1}-x_{j1}{)}^h+(x_{i2}-x_{j2}{)}^h+...+(x_{in}-x_{jn}{)}^h{)}^{1/h}$$

Most commonly used functions are Euclidean distance and Manhattan (city block) distance

• If $h=1$, it is the Manhattan distance

$$dist(x_i,x_j)=|x_{i1}-x_{j1}|+|x_{i2}-x_{j2}|+\cdots +|x_{ir}-x_{jr}|$$

• If $h=2$, it is the Euclidean distance

$$dist(x_i,x_j)=\sqrt{(x_{i1}-x_{j1}{)}^2+(x_{i2}-x_{j2}{)}^2+\cdots +(x_{ir}-x_{jr}{)}^2}$$

• Weighted Euclidean distance

$$dist(x_i,x_j)=\sqrt{w_1(x_{i1}-x_{j1}{)}^2+w_2(x_{i2}-x_{j2}{)}^2+\cdots +w_r(x_{ir}-x_{jr}{)}^2}$$

• Chebychev distance:

$$dist(x_i,x_j)=max(|x_{i1}-x_{j1}|,|x_{i2}-x_{j2}|,\cdots ,|x_{ir}-x_{jr}|)$$

Distance functions for binary attributes

Simple Matching Coefficient (SMC)

• Definition: Measures the proportion of matching elements (both 1s and 0s) between two binary vectors.

• Formula:

  $$SMC=\frac{TP+TN}{TP+TN+FP+FN}$$

  Where:

  • $TP$: True Positives (both vectors are 1).
  • $TN$: True Negatives (both vectors are 0).
  • $FP$: False Positives (vector 1 is 1, vector 2 is 0).
  • $FN$: False Negatives (vector 1 is 0, vector 2 is 1).

• Range: $SMC\in [0,1]$, where 1 indicates perfect matching.

• Use Case: Suitable when both 1s and 0s carry equal importance.

---

Jaccard Similarity Coefficient

• Definition: Measures the similarity between two binary vectors by considering only the matches for 1s. Ignores 0s.

• Formula:

  $$Jaccard=\frac{TP}{TP+FP+FN}$$

  Where:

  • $TP$: True Positives (both vectors are 1).
  • $FP$: False Positives (vector 1 is 1, vector 2 is 0).
  • $FN$: False Negatives (vector 1 is 0, vector 2 is 1).

• Range: $Jaccard\in [0,1]$, where 1 indicates perfect similarity.

• Use Case: Ideal for sparse data or cases where 1s are more significant than 0s.

---

Hamming Distance

• Definition: Measures the total number of differing bits between two binary vectors. It counts mismatched positions.

• Formula:

  $$HammingDistance=\sum _{i=1}^n|x_{i1}-x_{i2}|$$

  Where $x_{i1}$ and $x_{i2}$ are the corresponding elements in the two vectors.

• Range: $Hamming\in [0,n]$, where 0 indicates no differences (identical vectors).

• Use Case: Suitable for measuring the difference between binary strings or vectors.

---

Comparison Table

Measure	Formula	Focus	Range	Best Use Case
SMC	$\frac{TP+TN}{TP+TN+FP+FN}$	Matches for 1s and 0s	$[0,1]$	Equal importance for 1s and 0s
Jaccard	$\frac{TP}{TP+FP+FN}$	Matches for 1s only	$[0,1]$	Sparse data, where 1s matter more
Hamming	$\sum |x_{i1}-x_{i2}|$	Mismatched positions	$[0,n]$	Binary strings or sequences

---

Example for Binary Vectors

Given two binary vectors:

$$x_1=[1,1,0,1,0],x_2=[1,0,0,1,1]$$

1. Simple Matching Coefficient (SMC):

   • $TP=2$, $TN=1$, $FP=1$, $FN=1$
   • $$SMC=\frac{TP+TN}{TP+TN+FP+FN}=\frac{2+1}{2+1+1+1}=0.6$$

2. Jaccard Similarity:

   • $TP=2$, $FP=1$, $FN=1$
   • $$Jaccard=\frac{TP}{TP+FP+FN}=\frac{2}{2+1+1}=0.5$$

3. Hamming Distance:

   • Number of mismatched positions: $1$ (index 2), $1$ (index 5).
   • $$HammingDistance=2$$

Distance functions for nominal attributes

Nominal attributes: with more than two states or values.

the commonly used distance measure is also based on the simple matching method.

Given two data points $x_i$ and $x_j$, let the number of attributes be $r$, and the number of values that match in $x_i$ and $x_j$ be $q$.

$$dist(x_i,x_j)=\frac{r-q}{r}$$

Distance Function for Text Documents

This section explains how text documents are represented and how distances or similarities between them are measured.

---

Representing Text Documents

• Definition:
  • A text document consists of a sequence of sentences, and each sentence is a sequence of words.
• Simplification:
  • To simplify, a document is usually represented as a Bag of Words (BOW) in document clustering.
  • In the Bag of Words model:
    • The sequence and position of words are ignored.
    • Focus is on word occurrence or frequency.
• Vector Representation:
  • A document is converted into a vector, where each dimension corresponds to a specific term (word), and the value represents the frequency or presence of the term.

Example:

Term	Document 1	Document 2
aid	0	1
back	1	0
dog	1	0
men	0	1
...	...	...

---

Measuring Distance or Similarity

Similarity vs. Distance:

• Instead of using distance, it is common to use similarity to compare text documents.
• Most Common Similarity Measure:
  • Cosine Similarity: Measures the cosine of the angle between two vectors.

Cosine Similarity:

• Formula:$$\text{Cosine Similarity}=\frac{\overrightarrow{v_1}\cdot \overrightarrow{v_2}}{\parallel \overrightarrow{v_1}\parallel \parallel \overrightarrow{v_2}\parallel }$$Where:
  • $\overrightarrow{v_1}$ and $\overrightarrow{v_2}$: Vector representations of two documents.
  • $\parallel \overrightarrow{v_1}\parallel$: The Euclidean norm of vector $\overrightarrow{v_1}$.
• Range:
  • $CosineSimilarity\in [0,1]$
  • $1$: Documents are identical.
  • $0$: Documents are completely dissimilar.

Data Standardization

In the Euclidean space, standardization of attributes is recommended so that all attributes can have equal impact on the computation of distances.

Standardize attributes: to force the attributes to have a common value range

Interval-scaled attributes

Their values are real numbers following a linear scale.

Two main approaches to standardize interval scaled attributes, range and z-score. $f$ is an attribute

Range Standardization

$$range(x_{if})=\frac{x_{if-min(f)}}{max(f)-min(f)}$$

Z-Score Standardization

Z-score: transforms the attribute values so that they have a mean of zero and a mean absolute deviation of 1. The mean absolute deviation of attribute $f$, denoted by $S_f$, is computed as follows.

$$S_f=\frac{1}{n}(|x_{1f}-m_f|+|x_{2f}-m_f|+\cdots +|x_{nf}-m_f|)$$$$m_f=\frac{1}{n}(x_{1f}+x_{2f}+\cdots +x_{nf})$$

Z-score:

$$z(x_{if})=\frac{x_{if}-m_f}{S_f}$$