, Prakash Singh Badal
[aut] | Title: | Polynomially Bounded Rank Aggregation under Kemeny's Axiomatic Approach |
|---|---|
| Description: | Polynomially bounded algorithms to aggregate complete rankings under Kemeny's axiomatic framework. 'RankAggSIgFUR' (pronounced as rank-agg-cipher) contains two heuristics algorithms: FUR and SIgFUR. For details, please see Badal and Das (2018) <doi:10.1016/j.cor.2018.06.007>. |
| Authors: | Hannah Parker [aut], Rakhi Singh [cre, aut]
, Prakash Singh Badal
[aut] |
| Maintainer: | Rakhi Singh <[email protected]> |
| License: | GPL (>= 3) |
| Version: | 1.0.0 |
| Built: | 2025-03-10 03:03:03 UTC |
| Source: | https://github.com/prakashvs613/rankaggsigfur |
Data of 100 objects and 15 attributes, in which the first column contains the object
names and each subsequent column is a complete ranking of the 100 objects. The
included 50 15 and 400 15 datasets were generated from this dataset (see
data50x15 and data400x15).
data(data100x15)data(data100x15)
A data frame with 100 rows and 16 columns:
object name
ranking on the first attribute
ranking on the second attribute
ranking on the third attribute
ranking on the fourth attribute
ranking on the fifth attribute
ranking on the sixth attribute
ranking on the seventh attribute
ranking on the eigth attribute
ranking on the ninth attribute
ranking on the tenth attribute
ranking on the eleventh attribute
ranking on the twelfth attribute
ranking on the thirteenth attribute
ranking on the fourteenth attribute
ranking on the fifteenth attribute
Badal, P. S., & Das, A. (2018). Efficient algorithms using subiterative convergence for Kemeny ranking problem. Computers & Operations Research, 98, 198-210. doi:10.1016/j.cor.2018.06.007
data(data100x15) input_rkgs <- t(as.matrix(data100x15[, -1])) obj_names <- data100x15[,1] # Determine the mean seed ranking mean_seed(input_rkgs)data(data100x15) input_rkgs <- t(as.matrix(data100x15[, -1])) obj_names <- data100x15[,1] # Determine the mean seed ranking mean_seed(input_rkgs)
Data of 240 cities across the globe ranked on four criteria from the ED-00015-001.soc dataset in the PrefLib repository. The first column contains the object names and each subsequent column is a complete ranking of the 240 objects with no ties) .
data(data240x4)data(data240x4)
A data frame with 240 rows and 5 columns:
object name
ranking on the first criterion
ranking on the second criterion
ranking on the third criterion
ranking on the fourth criterion
Badal, P. S., & Das, A. (2018). Efficient algorithms using subiterative convergence for Kemeny ranking problem. Computers & Operations Research, 98, 198-210. doi:10.1016/j.cor.2018.06.007
Mattei, N., & Walsh, T. (2013, November). Preflib: A library for preferences https://www.preflib.org/. In International conference on algorithmic decision theory (pp. 259-270). Springer, Berlin, Heidelberg.
data(data240x4) input_rkgs <- t(as.matrix(data240x4[, -1])) obj_names <- data240x4[,1] # Determine the mean seed ranking mean_seed(input_rkgs)data(data240x4) input_rkgs <- t(as.matrix(data240x4[, -1])) obj_names <- data240x4[,1] # Determine the mean seed ranking mean_seed(input_rkgs)
Data of 400 objects and 15 attributes in which the first column contains the object
names and each subsequent column is a complete ranking of the 400 objects. This
data set is generated from the 100 15 dataset (see data50x15)
by adding 100 to the ranks of the objects numbered 1 through 100 to get the ranks of
objects numbered 101 through 200. Similarly, by adding 200 to obtain ranking 201
through 300, and by adding 300 to obtain ranking 301 through 400.
data(data400x15)data(data400x15)
A data frame with 400 rows and 16 columns:
object name
ranking on the first attribute
ranking on the second attribute
ranking on the third attribute
ranking on the fourth attribute
ranking on the fifth attribute
ranking on the sixth attribute
ranking on the seventh attribute
ranking on the eigth attribute
ranking on the ninth attribute
ranking on the tenth attribute
ranking on the eleventh attribute
ranking on the twelfth attribute
ranking on the thirteenth attribute
ranking on the fourteenth attribute
ranking on the fifteenth attribute
Badal, P. S., & Das, A. (2018). Efficient algorithms using subiterative convergence for Kemeny ranking problem. Computers & Operations Research, 98, 198-210. doi:10.1016/j.cor.2018.06.007
data(data400x15) input_rkgs <- t(as.matrix(data400x15[, -1])) obj_names <- data400x15[,1] # Determine the mean seed ranking mean_seed(input_rkgs)data(data400x15) input_rkgs <- t(as.matrix(data400x15[, -1])) obj_names <- data400x15[,1] # Determine the mean seed ranking mean_seed(input_rkgs)
Data of 50 objects and 15 attributes, which were randomly generated from the
100 15 simulated dataset (see data100x15). The first column contains the object
names and each subsequent column is a complete ranking of the 50 objects.
data(data50x15)data(data50x15)
A data frame with 50 rows and 16 columns:
object name
ranking on the first attribute
ranking on the second attribute
ranking on the third attribute
ranking on the fourth attribute
ranking on the fifth attribute
ranking on the sixth attribute
ranking on the seventh attribute
ranking on the eigth attribute
ranking on the ninth attribute
ranking on the tenth attribute
ranking on the eleventh attribute
ranking on the twelfth attribute
ranking on the thirteenth attribute
ranking on the fourteenth attribute
ranking on the fifteenth attribute
Badal, P. S., & Das, A. (2018). Efficient algorithms using subiterative convergence for Kemeny ranking problem. Computers & Operations Research, 98, 198-210. doi:10.1016/j.cor.2018.06.007
data(data50x15) input_rkgs <- t(as.matrix(data50x15[, -1])) obj_names <- data50x15[,1] # Determine the mean seed ranking mean_seed(input_rkgs)data(data50x15) input_rkgs <- t(as.matrix(data50x15[, -1])) obj_names <- data50x15[,1] # Determine the mean seed ranking mean_seed(input_rkgs)
FUR is a heuristic algorithm to obtain a consensus ranking. It contains three branches – Fixed, Update, and Range – that use Subiterative Convergence and Greedy Algorithm iteratively. See ‘Details’ for more information on each branch.
fur( input_rkgs, subit_len_list, search_radius, seed_rkg = c(), objNames = c(), wt = c() )fur( input_rkgs, subit_len_list, search_radius, seed_rkg = c(), objNames = c(), wt = c() )
input_rkgs |
a |
subit_len_list |
a vector containing positive integer(s) for the subiteration lengths to Subiterative Convergence. Recommended values are between 2 and 8. Smaller subiteration lengths result in shorter run-time. |
search_radius |
a positive integer for the maximum change in the rank of each
object in the Greedy Algorithm. The default value
of |
seed_rkg |
a vector of length |
objNames |
a |
wt |
a |
The Fixed branch applies Subiterative Convergence using one subiteration
length from subit_len_list at a time.
The Update branch executes Subiterative Convergence using the first
subiteration length in subit_len_list, and then uses its output in the
next call to Subiterative Convergence with the next subiteration length in the list.
This process repeats until subit_len_list is exhausted.
The Range branch calls Subiterative Convergence on all subiteration lengths in
subit_len_list and only retains the best ranking among these separate calls.
The output from the Subiterative Convergence calls are fed into the Greedy Algorithm as its seed ranking, and the FUR algorithm is terminated when the input to the Greedy Algorithm converges to the output and all branches have been executed at least once.
A list containing the consensus ranking (expressed as ordering), total Kemeny distance, and average tau correlation coefficient corresponding to the consensus ranking.
Badal, P. S., & Das, A. (2018). Efficient algorithms using subiterative convergence for Kemeny ranking problem. Computers & Operations Research, 98, 198-210. doi:10.1016/j.cor.2018.06.007
mean_seed, subit_convergence, rap_greedy_alg, sigfur
## One subiteration length input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3), byrow = FALSE, ncol = 4) subit_len_list <- 2 search_radius <- 1 fur(input_rkgs, subit_len_list, search_radius) # Determined the consensus ranking, total Kemeny # distance, and average tau correlation coefficient ## Multiple subiteration lengths input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3), byrow = FALSE, ncol = 4) subit_len_list <- c(2,3) search_radius <- 1 fur(input_rkgs, subit_len_list, search_radius) ## Five input rankings with five objects ## 2nd ranking == 3rd ranking, so if a third object is weighted as zero, ## we should get the same answer as the first examples input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) ## Multiple subiteration lengths wt = c(1,1,0,1,1) subit_len_list <- c(2,3) search_radius <- 1 fur(input_rkgs, subit_len_list, search_radius,wt=wt) ## Using five input rankings with five objects with prepare_data to ## automatically prepare the weight vector input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) out = prepare_data(input_rkgs) input_rkgs = out$input_rkgs wt = out$wt subit_len_list <- c(2,3) search_radius <- 1 fur(input_rkgs, subit_len_list, search_radius,wt=wt) ## Included dataset of 15 input rankings of 50 objects data(data50x15) input_rkgs <- as.matrix(data50x15[, -1]) subit_len_list <- c(2, 3) search_radius <- 1 fur(input_rkgs, subit_len_list, search_radius)## One subiteration length input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3), byrow = FALSE, ncol = 4) subit_len_list <- 2 search_radius <- 1 fur(input_rkgs, subit_len_list, search_radius) # Determined the consensus ranking, total Kemeny # distance, and average tau correlation coefficient ## Multiple subiteration lengths input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3), byrow = FALSE, ncol = 4) subit_len_list <- c(2,3) search_radius <- 1 fur(input_rkgs, subit_len_list, search_radius) ## Five input rankings with five objects ## 2nd ranking == 3rd ranking, so if a third object is weighted as zero, ## we should get the same answer as the first examples input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) ## Multiple subiteration lengths wt = c(1,1,0,1,1) subit_len_list <- c(2,3) search_radius <- 1 fur(input_rkgs, subit_len_list, search_radius,wt=wt) ## Using five input rankings with five objects with prepare_data to ## automatically prepare the weight vector input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) out = prepare_data(input_rkgs) input_rkgs = out$input_rkgs wt = out$wt subit_len_list <- c(2,3) search_radius <- 1 fur(input_rkgs, subit_len_list, search_radius,wt=wt) ## Included dataset of 15 input rankings of 50 objects data(data50x15) input_rkgs <- as.matrix(data50x15[, -1]) subit_len_list <- c(2, 3) search_radius <- 1 fur(input_rkgs, subit_len_list, search_radius)
Determine the mean seed ranking of the given input rankings. The average rank of an object is the sum of its various rankings from each input ranking divided by the total number of rankings. The mean seed ranking is formed by ranking the objects based on their average ranks, and ties are broken by ranking the first tied object with a higher rank.
mean_seed(input_rkgs, wt = c())mean_seed(input_rkgs, wt = c())
input_rkgs |
a |
wt |
a |
A vector containing the mean seed ranking of the input rankings.
rank, subit_convergence, fur, sigfur
## Four input rankings of five objects input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3), byrow = FALSE, ncol = 4) mean_seed(t(input_rkgs)) # Found the mean seed ranking ## Five input rankings with five objects ## 2nd ranking == 3rd ranking, so if a third object is weighted as zero, ## we should get the same answer as the first examples input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) wt = c(1,1,0,1,1) mean_seed(t(input_rkgs),wt=wt) # Found the mean seed ranking ## Included dataset of 15 input rankings of 50 objects data(data50x15) input_rkgs <- t(as.matrix(data50x15[, -1])) mean_seed(input_rkgs)## Four input rankings of five objects input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3), byrow = FALSE, ncol = 4) mean_seed(t(input_rkgs)) # Found the mean seed ranking ## Five input rankings with five objects ## 2nd ranking == 3rd ranking, so if a third object is weighted as zero, ## we should get the same answer as the first examples input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) wt = c(1,1,0,1,1) mean_seed(t(input_rkgs),wt=wt) # Found the mean seed ranking ## Included dataset of 15 input rankings of 50 objects data(data50x15) input_rkgs <- t(as.matrix(data50x15[, -1])) mean_seed(input_rkgs)
Modified Kemeny algorithm determines the consensus ranking of n objects using
the set of all possible rankings compared to the input rankings. The algorithm is based on
Kemeny's axiomatic approach of minimizing the total Kemeny distance from the input rankings.
In case of multiple rankings with minimum total Kemeny distance, the consensus ranking is
determined using two additional criteria. See ‘Details’ for additional criteria.
The method involves n! comparisons. Hence, it works best on a set of rankings with a small
number of objects.
mod_kemeny(input_rkgs, universe_rkgs, obj_pairs, wt)mod_kemeny(input_rkgs, universe_rkgs, obj_pairs, wt)
input_rkgs |
a |
universe_rkgs |
a matrix containing all possible permutations of ranking n objects. Each row in this matrix represents one permuted ranking. |
obj_pairs |
a |
wt |
a |
Under Kemeny's axiomatic approach, rankings with minimum total Kemeny distance are considered equally optimal. Modified Kemeny attempts to break the tie among such rankings by imposing two additional criteria on the basis of minimizing (a) the maximum and (b) the variance of individual Kemeny distances, applied sequentially.
A list containing the consensus ranking (expressed as ordering), total Kemeny distance, and average tau correlation coefficient corresponding to the consensus ranking.
Badal, P. S., & Das, A. (2018). Efficient algorithms using subiterative convergence for Kemeny ranking problem. Computers & Operations Research, 98, 198-210. doi:10.1016/j.cor.2018.06.007
## Consensus ranking from four rankings of five objects n <- 5 input_rkgs <- matrix(c(3, 2, 5, 1, 2, 3, 1, 2, 5, 1, 3, 4, 4, 5, 4, 5, 1, 4, 2, 3), ncol = n) uni_rkgs <- matrix(unlist(combinat::permn(c(1:n))), byrow = TRUE, ncol = n) obj_pairs <- combinat::combn(1:n,2, simplify=TRUE) wt <- rep(1,nrow(input_rkgs)) mod_kemeny(input_rkgs, uni_rkgs, obj_pairs,wt=wt) # Computed consensus ranking, # total Kemeny distance, #and average tau correlation coefficient## Consensus ranking from four rankings of five objects n <- 5 input_rkgs <- matrix(c(3, 2, 5, 1, 2, 3, 1, 2, 5, 1, 3, 4, 4, 5, 4, 5, 1, 4, 2, 3), ncol = n) uni_rkgs <- matrix(unlist(combinat::permn(c(1:n))), byrow = TRUE, ncol = n) obj_pairs <- combinat::combn(1:n,2, simplify=TRUE) wt <- rep(1,nrow(input_rkgs)) mod_kemeny(input_rkgs, uni_rkgs, obj_pairs,wt=wt) # Computed consensus ranking, # total Kemeny distance, #and average tau correlation coefficient
Prepares the given data for rank aggregation functions. The function
returns a matrix of input rankings and a vector indicating weights of the
ranking for each judge. Useful when scores need to be converted to rankings.
Also helpful in reducing the size of the problem for large p, especially
when p > n!.
prepare_data(df, HighertheBetter = 0)prepare_data(df, HighertheBetter = 0)
df |
a |
HighertheBetter |
an integer with 1 indicating that the higher values in the input correspond to the better rank. An optional parameter. Default value is 0, i.e., the lower the score the better the rank (e.g., score of 1 is the topmost rank). |
A list containing a matrix of input rankings (named input_rkgs) and a
weight vector corresponding to weights for each judge (named wt). These
two objects are used as inputs to subit_convergence,
rap_greedy_alg, fur, and sigfur.
subit_convergence, rap_greedy_alg, fur, sigfur
## Five input rankings with five objects input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) out = prepare_data(input_rkgs) input_rkgs = out$input_rkgs wt = out$wt ## Five input rankings with five objects ## testing the higher the better input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) input_rkgs = input_rkgs*2+input_rkgs #artificially create a score matrix # Testing the higher the better rank out = prepare_data(input_rkgs, HighertheBetter = 1) input_rkgs = out$input_rkgs wt = out$wt## Five input rankings with five objects input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) out = prepare_data(input_rkgs) input_rkgs = out$input_rkgs wt = out$wt ## Five input rankings with five objects ## testing the higher the better input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) input_rkgs = input_rkgs*2+input_rkgs #artificially create a score matrix # Testing the higher the better rank out = prepare_data(input_rkgs, HighertheBetter = 1) input_rkgs = out$input_rkgs wt = out$wt
Greedy Algorithm is a heuristic method that hunts for improved rankings by moving one object at a time (up or down). In case an object’s movement results in an improved ranking, the next object is moved with respect to this improved ranking. The process is repeated until all objects are considered once.
rap_greedy_alg( seed_rkg, input_rkgs, search_radius = 0, objNames = c(), wt = c() )rap_greedy_alg( seed_rkg, input_rkgs, search_radius = 0, objNames = c(), wt = c() )
seed_rkg |
an initial ranking to begin the algorithm. The algorithm is often used in conjunction with Subiterative Convergence. |
input_rkgs |
a |
search_radius |
a positive integer for the maximum change in the rank of each
object. The default value of |
objNames |
a |
wt |
a |
A list containing the consensus ranking (expressed as ordering), total Kemeny distance, and average tau correlation coefficient corresponding to the consensus ranking.
Badal, P. S., & Das, A. (2018). Efficient algorithms using subiterative convergence for Kemeny ranking problem. Computers & Operations Research, 98, 198-210. doi:10.1016/j.cor.2018.06.007
subit_convergence, fur, sigfur
## Four input rankings of five objects input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3), byrow = FALSE, ncol = 4) mean_seed_rkg <- mean_seed(t(input_rkgs)) rap_greedy_alg(mean_seed_rkg, input_rkgs, search_radius = 0) # Determined the consensus ranking, # total Kemeny distance, and average # tau correlation coefficient ## Five input rankings with five objects ## 2nd ranking == 3rd ranking, so if a third object is weighted as zero, ## we should get the same answer as the first examples input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) wt = c(1,1,0,1,1) mean_seed_rkg <- mean_seed(t(input_rkgs),wt=wt) rap_greedy_alg(mean_seed_rkg, input_rkgs, search_radius = 0,wt=wt) # Determined the #consensus ranking, total Kemeny distance, and average tau correlation coefficient ## Using five input rankings with five objects with prepare_data to ## automatically prepare the weight vector input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) out = prepare_data(input_rkgs) input_rkgs = out$input_rkgs wt = out$wt mean_seed_rkg <- mean_seed(t(input_rkgs),wt=wt) rap_greedy_alg(mean_seed_rkg, input_rkgs, search_radius = 0,wt=wt) # Determined the #consensus ranking, total Kemeny distance, and average tau correlation coefficient ## Included dataset of 15 input rankings of 50 objects data(data50x15) input_rkgs <- as.matrix(data50x15[, -1]) mean_seed_rkg <- mean_seed(t(input_rkgs)) # Use the mean seed ranking as the seed ranking rap_greedy_alg(mean_seed_rkg, input_rkgs, search_radius = 1)## Four input rankings of five objects input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3), byrow = FALSE, ncol = 4) mean_seed_rkg <- mean_seed(t(input_rkgs)) rap_greedy_alg(mean_seed_rkg, input_rkgs, search_radius = 0) # Determined the consensus ranking, # total Kemeny distance, and average # tau correlation coefficient ## Five input rankings with five objects ## 2nd ranking == 3rd ranking, so if a third object is weighted as zero, ## we should get the same answer as the first examples input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) wt = c(1,1,0,1,1) mean_seed_rkg <- mean_seed(t(input_rkgs),wt=wt) rap_greedy_alg(mean_seed_rkg, input_rkgs, search_radius = 0,wt=wt) # Determined the #consensus ranking, total Kemeny distance, and average tau correlation coefficient ## Using five input rankings with five objects with prepare_data to ## automatically prepare the weight vector input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) out = prepare_data(input_rkgs) input_rkgs = out$input_rkgs wt = out$wt mean_seed_rkg <- mean_seed(t(input_rkgs),wt=wt) rap_greedy_alg(mean_seed_rkg, input_rkgs, search_radius = 0,wt=wt) # Determined the #consensus ranking, total Kemeny distance, and average tau correlation coefficient ## Included dataset of 15 input rankings of 50 objects data(data50x15) input_rkgs <- as.matrix(data50x15[, -1]) mean_seed_rkg <- mean_seed(t(input_rkgs)) # Use the mean seed ranking as the seed ranking rap_greedy_alg(mean_seed_rkg, input_rkgs, search_radius = 1)
Seed-Based Iteration is a heuristic-based seed generation used in SIgFUR to iteratively perturb the ranking to improve the consensus ranking.
seed_based_iteration(eta, omega, input_rkgs, wt = c())seed_based_iteration(eta, omega, input_rkgs, wt = c())
eta |
a subiteration length for intermittent Subiterative Convergence. The recommended values are between 2 and 8. Smaller subiteration lengths result in shorter run-time. |
omega |
a positive integer for the number of repetitions of perturbing
the seed ranking. An |
input_rkgs |
a |
wt |
a |
A list containing the consensus ranking (expressed as ordering) and total Kemeny distance corresponding to the consensus ranking.
Badal, P. S., & Das, A. (2018). Efficient algorithms using subiterative convergence for Kemeny ranking problem. Computers & Operations Research, 98, 198-210. doi:10.1016/j.cor.2018.06.007
sigfur, subit_convergence, mean_seed
## Four input rankings of five objects eta <- 2 omega <- 10 input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3), byrow = FALSE, ncol = 4) seed_based_iteration(eta, omega, t(input_rkgs)) # Determined seed-based iterations ## Five input rankings with five objects ## 2nd ranking == 3rd ranking, so if a third object is weighted as zero, ## we should get the same answer as the first examples input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) eta <- 2 omega <- 10 wt = c(1,1,0,1,1) seed_based_iteration(eta, omega, t(input_rkgs), wt=wt) # Determined seed-based iterations ## Included dataset of 15 input rankings of 50 objects eta <- 3 omega <- 5 data(data50x15) input_rkgs <- as.matrix(data50x15[, -1]) seed_based_iteration(eta, omega, t(input_rkgs)) # Determined seed-based iterations## Four input rankings of five objects eta <- 2 omega <- 10 input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3), byrow = FALSE, ncol = 4) seed_based_iteration(eta, omega, t(input_rkgs)) # Determined seed-based iterations ## Five input rankings with five objects ## 2nd ranking == 3rd ranking, so if a third object is weighted as zero, ## we should get the same answer as the first examples input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) eta <- 2 omega <- 10 wt = c(1,1,0,1,1) seed_based_iteration(eta, omega, t(input_rkgs), wt=wt) # Determined seed-based iterations ## Included dataset of 15 input rankings of 50 objects eta <- 3 omega <- 5 data(data50x15) input_rkgs <- as.matrix(data50x15[, -1]) seed_based_iteration(eta, omega, t(input_rkgs)) # Determined seed-based iterations
SIgFUR applies Seed-Based Iteration, Greedy Algorithm,
and FUR in sequence for each element of subit_len_list_sbi. The
mean seed ranking is used as the input to Seed-Based Iteration.
The best of all output rankings from FUR is considered as the consensus
ranking.
sigfur( input_rkgs, subit_len_list_sbi, omega_sbi, subit_len_list_fur, search_radius, objNames = c(), wt = c() )sigfur( input_rkgs, subit_len_list_sbi, omega_sbi, subit_len_list_fur, search_radius, objNames = c(), wt = c() )
input_rkgs |
a |
subit_len_list_sbi |
a vector containing positive integer(s) for the subiteration lengths to Seed-Based Iteration. Recommended values are between 2 and 8. Smaller subiteration lengths result in shorter run-time. |
omega_sbi |
a positive integer for the number of repetitions of perturbing
the seed ranking in Seed-Based Iteration. An |
subit_len_list_fur |
a vector containing positive integer(s) for the subiteration lengths to FUR. |
search_radius |
a positive integer for the maximum change in the rank of each
object in the Greedy Algorithm and FUR. The default value
of |
objNames |
a |
wt |
a |
A list containing the consensus ranking (expressed as ordering), total Kemeny distance, and average tau correlation coefficient corresponding to the consensus ranking.
Badal, P. S., & Das, A. (2018). Efficient algorithms using subiterative convergence for Kemeny ranking problem. Computers & Operations Research, 98, 198-210. doi:10.1016/j.cor.2018.06.007
seed_based_iteration, rap_greedy_alg, fur, mean_seed
## Four input rankings of five objects input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3), byrow = FALSE, ncol = 4) subit_len_list_sbi <- c(2:3) omega_sbi <- 10 subit_len_list_fur <- c(2:3) search_radius <- 1 sigfur(input_rkgs, subit_len_list_sbi, omega_sbi, subit_len_list_fur, search_radius) # Determined the consensus ranking, total Kemeny distance, and average tau correlation coefficient ## Five input rankings with five objects ## 2nd ranking == 3rd ranking, so if a third object is weighted as zero, ## we should get the same answer as the first examples input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) subit_len_list_sbi <- c(2:3) omega_sbi <- 10 subit_len_list_fur <- c(2:3) search_radius <- 1 wt = c(1,1,0,1,1) sigfur(input_rkgs, subit_len_list_sbi, omega_sbi, subit_len_list_fur, search_radius, wt=wt) # Determined the consensus ranking, total Kemeny distance, and average tau correlation coefficient ## Using five input rankings with five objects with prepare_data to ## automatically prepare the weight vector input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) out = prepare_data(input_rkgs) input_rkgs = out$input_rkgs wt = out$wt subit_len_list_sbi <- c(2:3) omega_sbi <- 10 subit_len_list_fur <- c(2:3) search_radius <- 1 sigfur(input_rkgs, subit_len_list_sbi, omega_sbi, subit_len_list_fur, search_radius, wt=wt) # Determined the consensus ranking, total Kemeny distance, and average tau correlation coefficient ## Included dataset of 15 input rankings of 50 objects data(data50x15) input_rkgs <- as.matrix(data50x15[, -1]) subit_len_list_sbi <- c(3) omega_sbi <- 5 subit_len_list_fur <- c(2:3) search_radius <- 1 sigfur(input_rkgs, subit_len_list_sbi, omega_sbi, subit_len_list_fur, search_radius)## Four input rankings of five objects input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3), byrow = FALSE, ncol = 4) subit_len_list_sbi <- c(2:3) omega_sbi <- 10 subit_len_list_fur <- c(2:3) search_radius <- 1 sigfur(input_rkgs, subit_len_list_sbi, omega_sbi, subit_len_list_fur, search_radius) # Determined the consensus ranking, total Kemeny distance, and average tau correlation coefficient ## Five input rankings with five objects ## 2nd ranking == 3rd ranking, so if a third object is weighted as zero, ## we should get the same answer as the first examples input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) subit_len_list_sbi <- c(2:3) omega_sbi <- 10 subit_len_list_fur <- c(2:3) search_radius <- 1 wt = c(1,1,0,1,1) sigfur(input_rkgs, subit_len_list_sbi, omega_sbi, subit_len_list_fur, search_radius, wt=wt) # Determined the consensus ranking, total Kemeny distance, and average tau correlation coefficient ## Using five input rankings with five objects with prepare_data to ## automatically prepare the weight vector input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) out = prepare_data(input_rkgs) input_rkgs = out$input_rkgs wt = out$wt subit_len_list_sbi <- c(2:3) omega_sbi <- 10 subit_len_list_fur <- c(2:3) search_radius <- 1 sigfur(input_rkgs, subit_len_list_sbi, omega_sbi, subit_len_list_fur, search_radius, wt=wt) # Determined the consensus ranking, total Kemeny distance, and average tau correlation coefficient ## Included dataset of 15 input rankings of 50 objects data(data50x15) input_rkgs <- as.matrix(data50x15[, -1]) subit_len_list_sbi <- c(3) omega_sbi <- 5 subit_len_list_fur <- c(2:3) search_radius <- 1 sigfur(input_rkgs, subit_len_list_sbi, omega_sbi, subit_len_list_fur, search_radius)
Subiterative Convergence finds the consensus ranking by iteratively applying the
Modified Kemeny algorithm on smaller number of objects, . Starting with a given seed
ranking, the consensus ranking is obtained when the algorithm converges.
subit_convergence( eta, seed_rkg, input_rkgs, universe_rkgs = c(), objNames = c(), wt = c() )subit_convergence( eta, seed_rkg, input_rkgs, universe_rkgs = c(), objNames = c(), wt = c() )
eta |
a subiteration length of number of objects to consider in the smaller
subset. Recommended |
seed_rkg |
an initial ranking to start the algorithm. An ideal seed ranking for Subiterative Convergence is the mean seed ranking of input rankings. |
input_rkgs |
a |
universe_rkgs |
a matrix containing all possible permutations of ranking
|
objNames |
a |
wt |
a |
A list containing the consensus ranking (expressed as ordering), total Kemeny distance, and average tau correlation coefficient corresponding to the consensus ranking.
Badal, P. S., & Das, A. (2018). Efficient algorithms using subiterative convergence for Kemeny ranking problem. Computers & Operations Research, 98, 198-210. doi:10.1016/j.cor.2018.06.007
mod_kemeny, fur, sigfur, mean_seed
## Four input rankings of five objects eta <- 3 seed_rkg <- c(1, 2, 3, 4, 5) input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3), byrow = FALSE, ncol = 4) subit_convergence(eta, seed_rkg, input_rkgs) # Determined the consensus ranking, total Kemeny # distance, and average tau correlation coefficient ## Example with eta=1 eta <- 1 seed_rkg <- c(1, 2, 3, 4, 5) input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3), byrow = FALSE, ncol = 4) subit_convergence(eta, seed_rkg, input_rkgs) # Shows a warning and returns seed ranking ## Five input rankings with five objects ## 2nd ranking == 3rd ranking, so if a third object is weighted as zero, ## we should get the same answer as the first examples input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) eta <- 3 seed_rkg <- c(1, 2, 3, 4, 5) wt = c(1,1,0,1,1) subit_convergence(eta, seed_rkg, input_rkgs, wt=wt) # Determined the consensus ranking, total Kemeny # distance, and average tau correlation coefficient ## Using five input rankings with five objects with prepare_data to ## automatically prepare the weight vector input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) out = prepare_data(input_rkgs) input_rkgs = out$input_rkgs wt = out$wt eta <- 3 seed_rkg <- c(1, 2, 3, 4, 5) subit_convergence(eta, seed_rkg, input_rkgs, wt=wt) # Determined the consensus ranking, total Kemeny # distance, and average tau correlation coefficient ## Included dataset of 15 input rankings of 50 objects data(data50x15) input_rkgs <- as.matrix(data50x15[, -1]) mean_seed_rkg <- mean_seed(t(input_rkgs)) # Use the mean seed ranking as the seed ranking eta <- 2 subit_convergence(eta, seed_rkg = mean_seed_rkg, input_rkgs)## Four input rankings of five objects eta <- 3 seed_rkg <- c(1, 2, 3, 4, 5) input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3), byrow = FALSE, ncol = 4) subit_convergence(eta, seed_rkg, input_rkgs) # Determined the consensus ranking, total Kemeny # distance, and average tau correlation coefficient ## Example with eta=1 eta <- 1 seed_rkg <- c(1, 2, 3, 4, 5) input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3), byrow = FALSE, ncol = 4) subit_convergence(eta, seed_rkg, input_rkgs) # Shows a warning and returns seed ranking ## Five input rankings with five objects ## 2nd ranking == 3rd ranking, so if a third object is weighted as zero, ## we should get the same answer as the first examples input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) eta <- 3 seed_rkg <- c(1, 2, 3, 4, 5) wt = c(1,1,0,1,1) subit_convergence(eta, seed_rkg, input_rkgs, wt=wt) # Determined the consensus ranking, total Kemeny # distance, and average tau correlation coefficient ## Using five input rankings with five objects with prepare_data to ## automatically prepare the weight vector input_rkgs <- matrix(c(3, 2, 5, 4, 1, 2, 3, 1, 5, 4, 2, 3, 1, 5, 4, 5, 1, 3, 4, 2, 1, 2, 4, 5, 3),byrow = FALSE, ncol = 5) out = prepare_data(input_rkgs) input_rkgs = out$input_rkgs wt = out$wt eta <- 3 seed_rkg <- c(1, 2, 3, 4, 5) subit_convergence(eta, seed_rkg, input_rkgs, wt=wt) # Determined the consensus ranking, total Kemeny # distance, and average tau correlation coefficient ## Included dataset of 15 input rankings of 50 objects data(data50x15) input_rkgs <- as.matrix(data50x15[, -1]) mean_seed_rkg <- mean_seed(t(input_rkgs)) # Use the mean seed ranking as the seed ranking eta <- 2 subit_convergence(eta, seed_rkg = mean_seed_rkg, input_rkgs)