|
Kendall Tau Distance
The Kendall tau rank distance is a metric (distance function) that counts the number of pairwise disagreements between two ranking lists. The larger the distance, the more dissimilar the two lists are. Kendall tau distance is also called bubble-sort distance since it is equivalent to the number of swaps that the bubble sort algorithm would take to place one list in the same order as the other list. The Kendall tau distance was created by Maurice Kendall. Definition The Kendall tau ranking distance between two lists \tau_1 and \tau_2 is : K_d(\tau_1, \tau_2) = , \, . where * \tau_1(i) and \tau_2(i) are the rankings of the element i in \tau_1 and \tau_2 respectively. K_d(\tau_1,\tau_2) will be equal to 0 if the two lists are identical and \frac n (n-1) (where n is the list size) if one list is the reverse of the other. Kendall tau distance may also be defined as : K_d(\tau_1,\tau_2) = \sum_ \bar_(\tau_1,\tau_2) where * ''P'' is the set of unordered pairs of distinct element ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Metric (mathematics)
In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general setting for studying many of the concepts of mathematical analysis and geometry. The most familiar example of a metric space is 3-dimensional Euclidean space with its usual notion of distance. Other well-known examples are a sphere equipped with the angular distance and the hyperbolic plane. A metric may correspond to a metaphorical, rather than physical, notion of distance: for example, the set of 100-character Unicode strings can be equipped with the Hamming distance, which measures the number of characters that need to be changed to get from one string to another. Since they are very general, metric spaces are a tool used in many different branches of mathematics. Many types of mathematical objects have a natural notion of distance and t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bubble Sort
Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed. These passes through the list are repeated until no swaps had to be performed during a pass, meaning that the list has become fully sorted. The algorithm, which is a comparison sort, is named for the way the larger elements "bubble" up to the top of the list. This simple algorithm performs poorly in real world use and is used primarily as an educational tool. More efficient algorithms such as quicksort, timsort, or merge sort are used by the sorting libraries built into popular programming languages such as Python and Java. Analysis Performance Bubble sort has a worst-case and average complexity of O(n^2), where n is the number of items being sorted. Most practical sorting algorithms have substantially better worst-case or average complexity, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Maurice Kendall
Sir Maurice George Kendall, FBA (6 September 1907 – 29 March 1983) was a prominent British statistician. The Kendall tau rank correlation is named after him. Education and early life Maurice Kendall was born in Kettering, Northamptonshire as the only child of engineering worker John Roughton Kendall and Georgina, née Brewer. His paternal grandfather was a publican, running The Woolpack at Kettering. As a young child he survived a case of cerebral meningitis, which was frequently fatal at that time. After growing up in Derby, England, he studied mathematics at St John's College, Cambridge, where he played cricket and chess (with future champions Conel Hugh O'Donel Alexander and Jacob Bronowski). After graduation as a Mathematics Wrangler in 1929, he joined the British Civil Service in the Ministry of Agriculture. In this position he became increasingly interested in using statistics towards agricultural questions, and one of his first published papers to the Royal Sta ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Discordant Pairs
In statistics, a concordant pair is a pair of observations, each on two variables, (X''1'',Y''1'') and (X''2'',Y''2''), having the property that : \sgn (X_2 - X_1)\ = \sgn (Y_2 - Y_1), where "sgn" refers to whether a number is positive, zero, or negative (its sign). Specifically, the signum function, often represented as sgn, is defined as: : \sgn x = \begin -1, & x 0 \end That is, in a concordant pair, both elements of one pair are either greater than, equal to, or less than the corresponding elements of the other pair. In contrast, a discordant pair is a pair of two-variable observations such that : \sgn (X_2 - X_1)\ = - \sgn (Y_2 - Y_1). That is, if one pair contains a higher value of ''X'' then the other pair contains a higher value of ''Y''. Uses The Kendall tau distance between two series is the total number of discordant pairs. The Kendall tau rank correlation coefficient, which measures how closely related two series of numbers are, is proportional to the di ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Inversion (discrete Mathematics)
In computer science and discrete mathematics, an inversion in a sequence is a pair of elements that are out of their natural order. Definitions Inversion Let \pi be a permutation. There is an inversion of \pi between i and j if i \pi(j). The inversion is indicated by an ordered pair containing either the places (i, j) or the elements \bigl(\pi(i), \pi(j)\bigr). The inversion set is the set of all inversions. A permutation's inversion set using place-based notation is the same as the inverse permutation's inversion set using element-based notation with the two components of each ordered pair exchanged. Likewise, a permutation's inversion set using element-based notation is the same as the inverse permutation's inversion set using place-based notation with the two components of each ordered pair exchanged. Inversions are usually defined for permutations, but may also be defined for sequences:Let S be a sequence (or multiset permutation). If i S(j), either the pair ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Merge Sort
In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output. Merge sort is a divide-and-conquer algorithm that was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up merge sort appeared in a report by Goldstine and von Neumann as early as 1948. Algorithm Conceptually, a merge sort works as follows: #Divide the unsorted list into ''n'' sublists, each containing one element (a list of one element is considered sorted). #Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list. Top-down implementation Example C-like code using indices for top-down merge sort algorithm that recursively splits the list (called ''runs'' in this example) into sublists until sublist size i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kendall Tau Rank Correlation Coefficient
In statistics, the Kendall rank correlation coefficient, commonly referred to as Kendall's τ coefficient (after the Greek letter τ, tau), is a statistic used to measure the ordinal association between two measured quantities. A τ test is a non-parametric hypothesis test for statistical dependence based on the τ coefficient. It is a measure of rank correlation: the similarity of the orderings of the data when ranked by each of the quantities. It is named after Maurice Kendall, who developed it in 1938, though Gustav Fechner had proposed a similar measure in the context of time series in 1897. Intuitively, the Kendall correlation between two variables will be high when observations have a similar (or identical for a correlation of 1) rank (i.e. relative position label of the observations within the variable: 1st, 2nd, 3rd, etc.) between the two variables, and low when observations have a dissimilar (or fully different for a correlation of −1) rank between the two variables ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Spearman's Rank Correlation Coefficient
In statistics, Spearman's rank correlation coefficient or Spearman's ''ρ'', named after Charles Spearman and often denoted by the Greek letter \rho (rho) or as r_s, is a nonparametric measure of rank correlation ( statistical dependence between the rankings of two variables). It assesses how well the relationship between two variables can be described using a monotonic function. The Spearman correlation between two variables is equal to the Pearson correlation between the rank values of those two variables; while Pearson's correlation assesses linear relationships, Spearman's correlation assesses monotonic relationships (whether linear or not). If there are no repeated data values, a perfect Spearman correlation of +1 or −1 occurs when each of the variables is a perfect monotone function of the other. Intuitively, the Spearman correlation between two variables will be high when observations have a similar (or identical for a correlation of 1) rank (i.e. relative position lab ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kemeny–Young Method
The Kemeny–Young method is an electoral system that uses ranked ballots and pairwise comparison counts to identify the most popular choices in an election. It is a Condorcet method because if there is a Condorcet winner, it will always be ranked as the most popular choice. This method assigns a score for each possible sequence, where each sequence considers which choice might be most popular, which choice might be second-most popular, which choice might be third-most popular, and so on down to which choice might be least-popular. The sequence that has the highest score is the winning sequence, and the first choice in the winning sequence is the most popular choice. (As explained below, ties can occur at any ranking level.) The Kemeny–Young method is also known as the Kemeny rule, VoteFair popularity ranking, the maximum likelihood method, and the median relation. Description The Kemeny–Young method uses preferential ballots on which voters rank choices according to thei ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
SIAM Journal On Discrete Mathematics
'' SIAM Journal on Discrete Mathematics'' is a peer-reviewed mathematics journal published quarterly by the Society for Industrial and Applied Mathematics (SIAM). The journal includes articles on pure and applied discrete mathematics. It was established in 1988, along with the ''SIAM Journal on Matrix Analysis and Applications'', to replace the ''SIAM Journal on Algebraic and Discrete Methods''. The journal is indexed by ''Mathematical Reviews'' and Zentralblatt MATH. Its 2009 MCQ was 0.57. According to the ''Journal Citation Reports'', the journal has a 2016 impact factor of 0.755. Although its official ISO abbreviation is ''SIAM J. Discrete Math.'', its publisher and contributors frequently use the shorter abbreviation ''SIDMA''. References External links * Combinatorics journals Publications established in 1988 English-language journals Discrete Mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way ana ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Biometrika
''Biometrika'' is a peer-reviewed scientific journal published by Oxford University Press for thBiometrika Trust The editor-in-chief is Paul Fearnhead (Lancaster University). The principal focus of this journal is theoretical statistics. It was established in 1901 and originally appeared quarterly. It changed to three issues per year in 1977 but returned to quarterly publication in 1992. History ''Biometrika'' was established in 1901 by Francis Galton, Karl Pearson, and Raphael Weldon to promote the study of biometrics. The history of ''Biometrika'' is covered by Cox (2001). The name of the journal was chosen by Pearson, but Francis Edgeworth insisted that it be spelt with a "k" and not a "c". Since the 1930s, it has been a journal for statistical theory and methodology. Galton's role in the journal was essentially that of a patron and the journal was run by Pearson and Weldon and after Weldon's death in 1906 by Pearson alone until he died in 1936. In the early days, the American ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
