Similarity and Distance Measures in proxyC

This vignette explains how proxyC compute the similarity and distance measures.

Notation

$\vec{x} = [x_i, x_{i + 1}, \dots, x_n] \\ \vec{y} = [y_i, y_{i + 1}, \dots, y_n]$ The length of the vector $n = ||\vec{x}||$ , while $|\vec{x}|$ is the absolute values of the elements.

Operations on vectors are element-wise:

$\vec{z} = \vec{x}\vec{y} \\ n = ||\vec{x}|| = ||\vec{y}|| =||\vec{z}||$

Summation of the elements of vectors is written using sigma without specifying the range:

$\sum{\vec{x}} = \sum_{i=1}^{n}{x_i}$

When the elements of the vector is compared with a value in a pair of square brackets, the summation is counting the number of elements that equal (or unequal) to the value:

$\sum{[\vec{x} = 1]} = \sum_{i=1}^{n}{[x_i = 1]}$

Similarity Measures

Similarity measures are available in proxyC::simil().

Cosine similarity (“cosine”)

$simil = \frac{\sum{\vec{x}\vec{y}}}{\sqrt{\sum{\vec{x} ^ 2}} \sqrt{\sum{\vec{y} ^ 2}}}$

Pearson correlation coefficient (“correlation”)

$simil = \frac{Cov(\vec{x},\vec{y})}{Var(\vec{x}) Var(\vec{y})}$

Jaccard similarity (“jaccard” and “ejaccard”)

The values of $x$ and $y$ are Boolean for “jaccard”.

$e = \sum{\vec{x} \vec{y}} \\ w = \text{user-provided weight} \\ simil = \frac{e}{\sum{\vec{x} ^ w} + \sum{\vec{y} ^ w} - e}$

Fuzzy Jaccard similarity (“fjaccard”)

The values must be $0 \le x \le 1.0$ and $0 \le y \le 1.0$ .

$simil = \frac{\sum{min(\vec{x}, \vec{y})}}{\sum{max(\vec{x}, \vec{y})}}$

Dice similarity (“dice” and “edice”)

The values of $x$ and $y$ are Boolean for “dice”.

$e = \sum{\vec{x} \vec{y}} \\ w = \text{user-provided weight} \\ simil = \frac{2 e}{\sum{\vec{x} ^ w} + \sum{\vec{y} ^ w}}$

Hamann similarity (“hamann”)

$e = \sum{\vec{x} \vec{y}} \\ n = ||\vec{x}|| = ||\vec{y}|| \\ u = n - e \\ simil = \frac{e - u}{e + u}$

Faith similarity (“faith”)

$t = \sum{[\vec{x} = 1][\vec{y} = 1]} \\ f = \sum{[\vec{x} = 0][\vec{y} = 0]} \\ n = ||\vec{x}|| = ||\vec{y}|| \\ simil = \frac{t + 0.5 f}{n}$

Simple matching (“matching”)

$simil = \sum{[\vec{x} = \vec{y}]}$

Distance Measures

Similarity measures are available in proxyC::dist(). Smoothing of the vectors can be performed when method is “chisquared”, “kullback”, “jefferys” or “jensen”: the value of smooth will be added to each element of $\vec{x}$ and $\vec{y}$ .

Manhattan distance (“manhattan”)

$dist = \sum{|\vec{x} - \vec{y}|}$

Canberra distance (“canberra”)

$dist = \frac{|\vec{x} - \vec{y}|}{|\vec{x}| + |\vec{y}|}$

Euclidian (“euclidian”)

$dist = \sum{\sqrt{\vec{x}^2 + \vec{y}^2}}$

Minkowski distance (“minkowski”)

$p = \text{user-provided parameter} \\ dist = \Bigl( \sum{|\vec{x} - \vec{y}| ^ p} \Bigr) ^ \frac{1}{p}$

Hamming distance (“hamming”)

$dist = \sum{[\vec{x} \ne \vec{y}]}$

The largest difference between values (“maximum”)

$dist = \max{\vec{x} - \vec{y}}$

Chi-squared divergence (“chisquared”)

$O_{ij} = \text{augmented matrix from } \vec{x} \text{ and } \vec{y} \\ E_{ij} = \text{matrix of expected count for } O_{ij} \\ dist = \sum{\frac{(O_{ij} - E_{ij}) ^ 2}{ E_{ij}}} \\$

Kullback–Leibler divergence (“kullback”)

$\vec{p} = \frac{\vec{x}}{\sum{\vec{x}}} \\ \vec{q} = \frac{\vec{y}}{\sum{\vec{y}}} \\ dist = \sum{\vec{q} \log_2{\frac{\vec{q}}{\vec{p}}}}$

Jeffreys divergence (“jeffreys”)

$\vec{p} = \frac{\vec{x}}{\sum{\vec{x}}} \\ \vec{q} = \frac{\vec{y}}{\sum{\vec{y}}} \\ dist = \sum{\vec{q} \log_2{\frac{\vec{q}}{\vec{p}}}} + \sum{\vec{p} \log_2{\frac{\vec{p}}{\vec{q}}}}$

Jensen-Shannon divergence (“jensen”)

$\vec{p} = \frac{\vec{x}}{\sum{\vec{x}}} \\ \vec{q} = \frac{\vec{y}}{\sum{\vec{y}}} \\ \vec{m} = \frac{1}{2} (\vec{p} + \vec{q}) \\ dist = \frac{1}{2} \sum{\vec{q} \log_2{\frac{\vec{q}}{\vec{m}}}} + \frac{1}{2} \sum{\vec{p} \log_2{\frac{\vec{p}}{\vec{m}}}}$

References

Choi, S., Cha, S., & Tappert, C. C. (2010). A survey of binary similarity and distance measures. Journal of Systemics, Cybernetics and Informatics, 8(1), 43–48.
Nielsen, F. (2019). On the Jensen–Shannon Symmetrization of Distances Relying on Abstract Means. Entropy, 21(5), 485. https://doi.org/10.3390/e21050485
Jain, G., Mahara, T., & Tripathi, K. N. (2020). A Survey of Similarity Measures for Collaborative Filtering-Based Recommender System. In M. Pant, T. K. Sharma, O. P. Verma, R. Singla, & A. Sikander (Eds.), Soft Computing: Theories and Applications (pp. 343–352). Springer. https://doi.org/10.1007/978-981-15-0751-9_32
Miyamoto, S. (1990). Hierarchical Cluster Analysis and Fuzzy Sets. In S. Miyamoto (Ed.), Fuzzy Sets in Information Retrieval and Cluster Analysis (pp. 125–188). Springer Netherlands. https://doi.org/10.1007/978-94-015-7887-5_6