ON THE BEHAVIOR OF CERTAIN METRIC ON THE PERMUTATIONS GROUP
Liviu P. Dinu · 2006
When a new metric is introduced, often there is a hidden variable in the similarity relation (frequently depends on the specific area of research), so that we should always speak of similarity with respect to some property, and there is a plethora of measures in part because researchers are often inexplicit on this point. On the other hand, one should have some knowledge about the nature of the problem to be solved. A result that is mathematically sound may be highly implausible and might not reflect what is known about the analyzed process. In information sciences, in computational linguistics or in some automatically categorization problems (especially based on combining rankings) we have to take into account the natural tendency of the objects to place the most important information in the first part of the message. So, if the differences between two objects are at the top (i.e., in essential points), the distance has to have a bigger value then when the differences are at the bottom of the objects. A similar situation can be found in genomics, where the difference on the first positions between two codons is more important than the difference on the last positions (Marcus, 1974). Following the upper motivations, we have introduced the rank distance [Dinu, 2003] as a similarity measure on rankings with linguistics and biological motivations. In some related papers we have investigated the behavior of this metrics in topics like aggregation of classifications, categorization [Dinu 2003], computational linguistics (especially the similarity of Romance languages, [Dinu and Dinu 2005]), the DNA sequence comparison [Dinu and Sgarro 2006], the similarity of trees structures [Dinu 2005]. From a computational point of view, rank distance has a good behavior w.r.t. the so-called string problem, i.e. the median string can be computed in a polynomial time by using rank distance [Dinu and Manea, 2006] (we remind that the same problem is NP-hard via other metrics, like Levenshtein, Kendall, etc.) In many cases (computational linguistics, statistics, coding, classification task, etc.), it is enough to use metrics that work on string without repetitions (i.e. rankings or permutations). In this paper we investigate some mathematical properties of the rank distance related on its expected and maximum values on the permutations group. We compute these values and show when they are reached.