Distance measures for classiﬁcation of numerical features

(1)

Distance measures for classification of numerical features

Georgy Minaev Robert Pich´ e Ari Visa Tampere University of Technology,

Finland June 14, 2018

1 List of functions

All tables show the distance functions. The formulad= 1−sis used to transform similarity to distance. Please readPas PN

i=1. N represents the vector length. Addition variables which are used in formulas are shown at the Comment column.

Table 1: Power (p,r) distances [1, chapter 17.2]

id Name d(P,Q) Comment Source

1. Power (p,r) Eu- clidean distance

(P|Pi−Qi|^p)^1/r p= 2, r= 2 [1]

2. Power (p,r) Man- hattan distance

(P

|Pi−Qi|^p)^1/r p= 1, r= 1 [1]

3. Power (p,r) Cheby- shev distance

(P|P_i−Q_i|^p)^1/r p=inf,r=inf,

implementation: d = max(|P−Q|)

[1]

4. Power (p,r) squared Euclidean distance

(P

|Pi−Qi|^p)^1/r p= 2, r= 1,d4=d²₁ [1]

(2)

Table 2: Distances on distribution laws [1, chapter 14.2]

5. Fidelity distance 1−P√

P_iQ_i [1]

6. Matusita distance pP (√

Pi−√

Qi)² d6=√

d7 [1]

7. Squared-chord distance

P(√ Pi−√

Qi)² d7=d²₆ [1]

8. Harmonic mean distance

1−2P((P_iQ_i)/(P_i+Q_i)) [1]

9. Bhattacharya 1 distance

(arccos(√

P_iQ_i))² twice of this is Fisher Dis- tance

[1]

10. Bhattacharya 2 distance

−ln(√

P_iQ_i) [1]

11. Pearsonχ²distance P((Pi−Qi)²/Qi) aka χ²-distance, quasi- distance, non-symmetric

[1]

12. Neyman χ² distance

P((Pi−Qi)²/Pi) quasi-distance, non- symmetric

[1]

13. Probabilistic sym- metricχ² distance

2P

((Pi−Qi)²/(Pi+Qi)) [1]

14. Separation quasi- distance

max(1−Pi/Qi) quasi-distance, non- symmetric

[1]

15. Kullback-Leibler distance

PPiln(Pi/Qi) aka relative entropy, information deviation, information gain, KL- distance, quasi-distance, non-symmetric

[1]

16. Skew divergence KL(P, αQ+ (1−α)P) α= 0.1, KL is Kullback- Leibler distance, quasi- distance, non-symmetric

[1]

17. K-divergence distance

KL(P, αQ+ (1−α)P) α= 1/2, KL is Kullback- Leibler distance, quasi- distance, non-symmetric

[1]

18. Jeffrey divergence P

(Pi−Qi) ln(Pi/Qi) aka J-divergence, divergence distance, KL2-divergence, non- symmetric

[1]

19. Jensen-Shannon divergence

Z=αPi+ (1−α)Qi

αKL(P, Z) + (1−α)KL(Q, Z))

α= 0.1, KL is Kullback- Leibler distance, non- symmetric

[1]

20. Topsøe distance Z= ¹₂(P_i+Q_i) P(Piln_Z^Pⁱ

i+Qiln^Q_Zⁱ

i)

aka information statistics [1]

21. Taneja distance Z= ¹₂(Pi+Qi) PZiln(Zi/√

PiQi)

[1]

22. Resistor-average distance

(1/KL(P, Q) + 1/KL(Q, P))⁻¹ KL is Kullback-Leibler distance

[1]

23. Chernoff distance max(−lnP(P_i^tQ^1−t_i )^1−t) t = 0.1, 0 ≤ t < 1,aka R´enyi cross-entropy, non- symmetric

[1]

24. R´enyi distance _1−t¹ lnPQi(_Q^Pⁱ

i)^t) t= 0.1, 0≤t <1, quasi- distance, if t = 1 than Kullback-Leibler distance, non-symmetric

[1]

(3)

Table 3: Similarities and distances for numerical data [1, chapter 17.1]

25. Ruzicka distance P

|Pi−Qi|/P

max(Pi, Qi) aka Soergel, Tanimoto [1]

26. Roberts distance 1 − P

(((Pi +

Qi)_max(P^min(Pⁱ^,Qⁱ⁾

i,Q_i))/P(Pi+Qi))

[1]

27. Intersection distance

1 −

Pmin(P_i, Q_i)/min(PP_i,PQ_i)

[1]

28. Motyka distance 1−Pmin(P_i, Q_i)/P(P_i+Q_i) aka Sørensen distance, Czekanowski distance, d28= ¹₂+¹₂d29

[1]

29. Bray-Curtis distance

1−_{N( ¯}_{P+ ¯}² _Q)Pmin(Pi, Qi) aka Renkonen % similarity or percentage similarity

[1]

30. Canberra distance P

(|Pi−Qi|/|Pi|+|Qi|) [1]

31. Kulczynski 1 distance

P|Pi−Qi|/P

min(Pi, Qi) [1]

32. Kulczynski 2 distance

1−^N₂(_P¹_¯ +_Q¹_¯)Pmin(Pi, Qi) [1]

33. Baroni-Urbani- Buser distance

1−

P(min(P_i, Q_i)) +pP

(min(P_i, Q_i))P(max(P)−max(P_i, Q_i)) P(max(Pi, Qi)) +pP

(min(Pi, Qi))P(max(P)−max(Pi, Qi)) [1]

(4)

Table 4: Relatives of Euclidean distance [1, chapter 17.2]

34. Penrose size distance

√NP|Pi−Qi| [1]

35. Mean character distance

1 N

P|Pi−Qi| aka Gower distance [1]

36. Lorentzian distance P

ln(1 +|Pi−Qi|) [1]

37. Penrose shape distance

pP((Pi−P¯)−(Qi−Q))¯ ² [1]

38. Clark distance (_N¹ P

((Pi − Qi)/(|Pi| +

|Qi|))²)^1/2

[1]

39. Meehl distance PN−1

i=1 (Pi−Qi−Pi+1+Qi+1)² [1]

40. Hellinger distance q

2P(p

Pi/P¯−p

Qi/Q)¯ ² [1]

41. Whittaker index of association distance

1 2

P P_i/P¯−Q_i/Q¯

[1]

42. Symmetric χ² dis-

tance s

X P¯+ ¯Q N( ¯P+ ¯Q)²

(PiQ¯−QiP¯)² Pi+Qi

aka chi-distance [1]

Table 5: Spectra distances

43. Spearman Corre- lation Coefficient, Pearson Correla- tion Coefficient

1−√^P^[(Qⁱ⁻^Q)(P^¯ ⁱ⁻^P)]^¯

P(Q_i−Q)¯ ²P(P_i−P)¯² [3, 4, 5].

44. Similarity Index (SI)

r

P{^Pi_Qi⁻^Qi×100}²

N non-symmetric [6]

45. Improved Similar- ity Index

q1 N

P{^P_Pⁱ^−Qⁱ

i+Qi ×100}² [6]

46. Absolute Value Dis- tance

(1 +

P(|Qi−Pi|)

P(Pi) )⁻¹ non-symmetric [7]

47. Dot-Product (cosine)

(PQ_iP_i)²

PQ²_iPP_i² [6]

48. Spectral Contrast Angle

PQiPi

√PQ²_iPP_i² d48=√

d47 [6]

(5)

Table 6: Distances from Cha

49. Wave Hedges distance

P |Pi−Qi|

max(P_i,Q_i) [2]

50. Cosine distance 1−√_P^P^Pⁱ^Qⁱ

P_i²√_P

Q²_i [2]

51. Jaccard distance PP_i²^P+P^(PⁱQ^−Q²_i−ⁱP⁾²P_iQ_i [2]

52. Dice distance P^PP^(P_i²ⁱ+^−QPⁱQ⁾²²_i [2]

53. Inner Product distance

1−PP_iQ_i [2]

54. Divergence distance

2P(P_i−Qi)²

(Pi+Qi)² [2]

55. Additive symmetric χ² distance

P(P_i−Qi)²(P_i+Q_i)

PiQi [2]

56. Jensen difference P[¹₂(P_ilnP_i + Q_ilnQ_i) − (^Pⁱ^+Q₂ ⁱ) ln(^Pⁱ^+Q₂ ⁱ)]

[2]

57. Kumar-Johnson distance

P(_2(P^(Pⁱ²^−Q²ⁱ⁾²

iQi)^3/2) [2]

58. Avg(L1, L_∞) distance

1 2(P

(|Pi−Qi|)+maxi|Pi−Qi|) d59= ¹₂(d3+d2) [2]

59. Vicis-Wave Hadges distance

P |Pi−Qi|

min(Pi,Qi) [2]

60. Vicis-Symmetricχ² 1 distance

P (P_i−Qi)²

min(P_i,Q_i)² [2]

P (P_i−Q_i)²

min(P_i,Q_i) [2]

P (Pi−Qi)²

max(P_i,Q_i) [2]

63. max-Symmetric χ² distance

max(P(Pi−Qi)²

P_i ,P(Pi−Qi)²

Q_i ) [2]

64. min-Symmetric χ² distance

min(P(Pi−Qi)²

P_i ,P(Pi−Qi)²

Q_i ) [2]

Table 7: Distances to compare compressed data

65. Hausdorff distance max_x⊆Amin_y⊆Qd(x, y)

where: d(x,y) is the Euclidean distance between points x and y implementation:

[P P, QQ] = meshgrid(P, Q);

maximinj|P Pi,j−QQi,j|

ultrametric, Hausdorff metric

[8].

66. Edit distance See reference, implementation (Matlab 2017b):

tol = 0.1;

edr(P,Q,tol);

Editing metric [9]

67. Levenshtein distance

See reference, implementation: https://en.wikibooks.

org/wiki/Algorithm_

Implementation/Strings/

Editing metric [1]

(6)

References

[1] M. M. Deza and E. Deza,Encyclopaedia of Distances, Springer, Berlin, Heidelberg, 2009.

[2] S. H. Cha,Comprehensive survey on distance/similarity measures between probability density, International Journal of Mathematics and Methods in Applied Sciences, vol. 1, no. 4, pp. 300–307, 2007.

[3] C. Saraiva, R., Lovisolo, L. RF Fingerprinting Location Techniques. in S.A.Zekavat, R.M.Buehrer, eds., Handbook of Position Location: Theory, Practice and Advances, Hoboken, NJ, USA: Wiley, 2011.

[4] G. Minaev, A. Visa, R. Pich´e, Comprehensive Survey of Similarity Measures for Ranked Based Location Fingerprinting Algorithm, International Conference on Indoor Positioning and Indoor Navigation (IPIN), Sept 2017.

[5] Y. Xie, Y. Wang, A. Nallanathan, L. Wang,An Improved K-Nearest-Neighbor Indoor Localization Method Based on Spearman Distance. IEEE Signal Processing Letters 23, No. 3, 351355, 2016.

[6] K. Wan, I. Vidavsky, L.M. Gross, Comparing similar spectra: from similarity index to spectral contrast angle, Journal of the American Society for Mass Spectrometry 13, 85 88, 2002, URL: http://www.

sciencedirect.com/science/article/pii/S1044030501003270.

[7] S.E. Stein, D.R. Scott, Optimization and testing of mass spectral library search algorithms for compound identification, Journal of the American Society for Mass Spectrometry 5, 859-866, 1994, URL: http:

//www.sciencedirect.com/science/article/pii/1044030594870098.

[8] M. Atallah,A linear time algorithm for the Hausdorff distance between convex polygons, Inf. Process, Lett.

17, 207-209, 1983.

[9] R.A. Wagner, M.J. Fischer, The string-to-string correction problem. J. ACM 21, 168-173, 1974, URL:

http://doi.acm.org/10.1145/321796.321811.