From similarity to distance: axiom set,monotonic transformations and metric determinacy

Sergej V. Znamenskij

Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika, Tome 11 (2018) no. 3, pp. 331-341.

Résumé

How to normalise similarity metric to a metric space for a clusterization? A new system of axioms describes the known generalizations of distance metrics and similarity metrics, the Pearson correlation coefficient and the cosine metrics. Equivalent definitions of order-preserving transformations of metrics (both monotonic and pivot-monotonic) are given in various terms. The metric definiteness of convex metric subspaces $\mathbb{R}^n$ and $\mathbb{Z}$ among the pivot-monotonic transformations is proved. Faster formulas for the monotonic normalization of metrics are discussed.

Détail

Keywords: metric space, similarity axioms, similarity normalization, metric determinacy, longest common subsequence.

Bibliographie

[1] C. Alexander, “Semi-developable space and quotient images of metric spaces”, Pacific J. Math., 37 (1971), 277–293 | DOI | MR | Zbl

[2] E. Arias-Castro, Some theory for ordinal embedding, 2015, arXiv: 1501.02861 [math.ST] | MR

[3] A.V. Arkhangel'skii, L.S. Pontryagin, General Topology I: Basic Concepts and Constructions Dimension Theory, Springer, 1990

[4] I. Borg, P.J. Groenen, Modern multidimensional scaling: Theory and applications, Springer, 2005 | MR | Zbl

[5] S. Budalakoti, R. Akella, A.N. Srivastava, E. Turkov, Anomaly Detection in Large Sets of High-Dimensional Symbol Sequences, NASA/TM-2006-214553, September, 2006

[6] M. Bukatin, R. Kopperman, S. Matthews, H. Pajoohesh, “Partial metric spaces”, Amer. Math. Monthly, 116:8 (2009), 708–718 | DOI | MR | Zbl

[7] E. Chávez, G. Navarro, “A Probabilistic Spell for the Curse of Dimensionality”, ALENEX'01, LNCS, 2153, Springer, 2001, 147–160 | Zbl

[8] E. Chávez, G. Navarro, R. Baeza-Yates, J.L. Marroquín, “Searching in metric spaces”, ACM Computing Surveys, 33:3 (2001), 273–321 | DOI

[9] S. Chen, B. Ma, K. Zhang, “On the similarity metric and the distance metric”, Theoretical Computer Science, 410:24–25 (2009), 2365–2376 | DOI | MR | Zbl

[10] P. Corazza, “Introduction to metric-preserving functions”, American Mathematical Monthly, 104:4 (1999), 309–323 | DOI | MR

[11] M.M. Deza, E. Deza, Encyclopedia of Distances, Springer, 2009 | MR | Zbl

[12] A.J. Dobson, “Unrooted Trees for Numerical Taxonomy”, Journal of Applied Probability, 11:1 (1974), 32–42 | DOI | MR | Zbl

[13] N. J. P. van Eck, L. Waltman, How to Normalize Co-Occurrence Data? An Analysis of Some Well-Known Similarity Measures, No ERS-2009-001-LIS, ERIM report series research in management Erasmus Research Institute of Management, Erasmus Research Institute of Management, 2009 http://hdl.handle.net/1765/14528

[14] C.H. Elzinga, M. Studer, “Normalization of Distance and Similarity in Sequence Analysis”, LaCOSA II (Lausanne, June 8–10, 2016), 445–468

[15] D.J. Greenhoe, Properties of distance spaces with power triangle inequalities, 2016 | DOI | MR

[16] R. Heckmann, Workshop Domains II, Informatik Berichte 96-04, Technische Universitat Braunschweig, 1996 | Zbl

[17] A. Islam, D. Inkpen, “Semantic text similarity using corpus-based word similarity and string similarity”, ACM Transactions on Knowledge Discovery from Data, 2:2 (2008), 1–25 | DOI | MR

[18] J.C. Kelly, “Bitopological spaces”, Proc. London Math. Soc., 13:3 (1963), 71–89 | DOI | MR | Zbl

[19] M. Kleindessner, U. von Luxburg, “Uniqueness of Ordinal Embedding JMLR”, Workshop and Conference Proceedings, 35, 2014, 1–28

[20] L. Leydesdorff, L. Vaughan, “Co-occurrence matrices and their applications in information science: extending ACA to the web environment”, Journal of the American Society for Information Science and Technology, 57:12 (2006), 1616–1628 | DOI

[21] S. Lim, “Cleansing Noisy City Names in Spatial Data Mining”, 2010 International Conference on Information Science and Applications (ICISA) (2010)

[22] S.G. Matthews, “Partial metric topology”, Proc. 8th Summer Conference on General Topology and Applications, Ann. New York Acad. Sci., 728, 1994, 183–197 | DOI | MR | Zbl

[23] E. Mêgnigbêto, “Controversies arising from which similarity measures can be used in co-citation analysis”, Malaysian Journal of Library $\$ Information Science, 18:2 (2013), 25–31

[24] G. Navarro, R. Paredes, N. Reyes, C. Bustos, “An empirical evaluation of intrinsic dimension estimators”, Information Systems, 64 (2017), 206–218 | DOI

[25] V.W. Niemytzki, “On the “third axiom of metric space””, Trans. Amer. Math. Soc., 29 (1927), 507–513 | MR | Zbl

[26] K. Nyirarugira, T. Kim, “Stratified gesture recognition using the normalized longest common subsequence with rough sets”, Signal Processing: Image Communication, 30 (2015), 178–189 | DOI

[27] S.J. O'Neill, Two topologies are better than one, Technical report, University of Warwick, April 1995 | Zbl

[28] R.N. Shepard, “The analysis of proximities: Multidimensional scaling with an unknown distance function. I”, Psychometrika, 27 (1962), 125–140 | DOI | MR | Zbl

[29] R.N. Shepard, “Representation of structure in similarity data: Problems and prospects”, Psychometrika, 39:4 (1974), 373–422 | DOI | MR

[30] T. Skopal, “On fast non-metric similarity search by metric access methods”, Proc. 10th International Conference on Extending Database Technology, EDBT'06, LNCS, 3896, Springer, 2006, 718–736

[31] T. Skopal, B. Bustos, “On nonmetric similarity search problems in complex domains”, ACM Computing Surveys, 43:4 (2011), 34 | DOI

[32] A. Tversky, “Features of similarity”, Psychological Review, 84 (1977), 327–352 | DOI

[33] A. Tversky, I. Gati, “Similarity, separability and the triangle inequality”, Psychological Review, 89 (1982), 123–154 | DOI

[34] A. Ugon, T. Nicolas, M. Richard, P. Guerin, P. Chansard, C. Demoor, L. Toubiana, “A new approach for cleansing geographical dataset using Levenshtein distance, prior knowledge and contextual information”, Studies in health technology and informatics, 210 (2015), 227–229 | DOI

[35] M. Vlachos, G. Kollios, D. Gunopulos, “Discovering similar multidimensional trajectories”, Proceedings of the International Conference on Data Engineering, ICDE '02,, IEEE Computer Society Press, San Jose, CA, USA, 2002, 673–684 | DOI

[36] W.A. Wilson, “On quasi-metric spaces”, Am. J. Math., 53 (1931), 675–684 | DOI | MR

[37] S.V. Znamenskij, “Models and axioms for similarity metrics”, Programmnye systemy: Theoriya i prilozheniya, 8:4 (2017), 247–357 (in Russian) | MR

[38] S. Znamenskii, V. Dyachenko, “An Alternative Model of the Strings Similarity”, Selected Papers of the XIX International Conference on Data Analytics and Management in Data Intensive Domains, DAMDID/RCDL 2017, CEUR Workshop Proceedings, 177–183 (in Russian)