relations (version 0.6-6)

consensus: Consensus Relations

Description

Compute consensus relations of a relation ensemble.

Usage

relation_consensus(x, method = NULL, weights = 1,
                   control = list(), ...)

Arguments

x

an ensemble of relations (see relation_ensemble), or something which can be coerced to such.

method

a character string specifying one of the built-in methods for computing consensus relations, or a function to be taken as a user-defined method, or NULL (default value). If a character string, its lower-cased version is matched against the lower-cased names of the available built-in methods using pmatch. See Details for available built-in methods and defaults.

weights

a numeric vector with non-negative case weights. Recycled to the number of elements in the ensemble given by x if necessary.

control

a list of control parameters. See Details.

…

a list of control parameters (overruling those specified in control).

Value

The consensus relation(s).

Details

Consensus relations “synthesize” the information in the elements of a relation ensemble into a single relation, often by minimizing a criterion function measuring how dissimilar consensus candidates are from the (elements of) the ensemble (the so-called “optimization approach”), typically of the form \(L(R) = \sum w_b d(R_b, R) ^ p\), where \(d\) is a suitable dissimilarity measure (see relation_dissimilarity), \(w_b\) is the case weight given to element \(R_b\) of the ensemble, and \(p \ge 1\). Such consensus relations are called “central relations” in R<U+00E9>gnier (1965). For \(p = 1\), we obtain (generalized) medians; \(p = 2\) gives (generalized) means (least squares consensus relations).

Available built-in methods are as follows. Apart from Condorcet's and the unrestricted Manhattan and Euclidean consensus methods, these are applicable to ensembles of endorelations only.

"Borda"

the consensus method proposed by Borda (1781). For each relation \(R_b\) and object \(x\), one determines the Borda/Kendall scores, i.e., the number of objects \(y\) such that \(y R_b x\). These are then aggregated across relations by weighted averaging. Finally, objects are ordered according to their aggregated scores. Note that this may result in a weak order (i.e., with objects being tied).

One can enforce a linear order by setting the control parameter L to TRUE, and obtain a relation ensemble with up to n or all such solutions by additionally setting the control parameter n to some positive integer or "all", respectively.

"Copeland"

the consensus method proposed by Copeland (1951). For each relation \(R_b\) and object \(x\), one determines the Copeland scores, i.e., the number of objects \(y\) such that \(y R_b x\), minus the number of objects \(y\) such that \(x R_b y\). Like the Borda method, these are then aggregated across relations by weighted averaging. Finally, objects are ordered according to their aggregated scores. Note that this may result in a weak order (i.e., with objects being tied).

One can enforce a linear order by setting the control parameter L to TRUE, and obtain a relation ensemble with up to n or all such solutions by additionally setting the control parameter n to some positive integer or "all", respectively.

"Condorcet"

the consensus method proposed by Condorcet (1785). For a given ensemble of crisp relations, this minimizes the criterion function \(L\) with \(d\) as symmetric difference distance and \(p = 1\) over all possible crisp relations. In the case of endorelations, consensus is obtained by weighting voting, such that \(x R y\) if the weighted number of times that \(x R_b y\) is no less than the weighted number of times that this is not the case. Even when aggregating linear orders, this can lead to intransitive consensus solutions (“effet Condorcet”).

One can obtain a relation ensemble with up to n or all such solutions consensus relations by setting the control parameter n to some positive integer or "all", respectively.

"CS"

the consensus method of Cook and Seiford (1978) which determines a linear order minimizing the criterion function \(L\) with \(d\) as generalized Cook-Seiford (ranking) distance and \(p = 1\) via solving a linear sum assignment problem.

One can obtain a relation ensemble with up to n or all such consensus relations by setting the control parameter n to some positive integer or "all", respectively.

"SD/F"

an exact solver for determining the consensus relation of an ensemble of crisp endorelations by minimizing the criterion function \(L\) with \(d\) as symmetric difference distance (“SD”) and \(p = 1\) over a suitable class (“Family”) of crisp endorelations as indicated by F, with values:

G

general (crisp) endorelations.

A

antisymmetric relations.

C

complete relations.

E

equivalence relations: reflexive, symmetric, and transitive.

L

linear orders: complete, reflexive, antisymmetric, and transitive.

M

matches: complete and reflexive.

O

partial orders: reflexive, antisymmetric and transitive.

S

symmetric relations.

T

tournaments: complete, irreflexive and antisymmetric (i.e., complete and asymmetric).

W

weak orders (complete preorders, preferences, “orderings”): complete, reflexive and transitive.

preorder

preorders: reflexive and transitive.

transitive

transitive relations.

Consensus relations are determined by reformulating the consensus problem as a binary program (for the relation incidences), see Hornik and Meyer (2007) for details. The solver employed can be specified via the control argument solver, with currently possible values "glpk", "lpsolve", "symphony" or "cplex" or a unique abbreviation thereof, specifying to use the solvers from packages Rglpk (default), lpSolve, Rsymphony, or Rcplex, respectively. Unless control option sparse is false, a sparse formulation of the binary program is used, which is typically more efficient.

For fitting equivalences and weak orders (cases E and W) it is possible to specify the number of classes \(k\) using the control parameter k. For fitting weak orders, one can also specify the number of elements in the classes via control parameter l.

Additional constraints on the incidences of the consensus solution can be given via the control parameter constraints, in the form of a 3-column matrix whose rows give row and column indices \(i\) and \(j\) and the corresponding incidence \(I_{ij}\). (I.e., incidences can be constrained to be zero or one on an object by object basis.)

One can obtain a relation ensemble with up to n or all such consensus relations by setting the control parameter n to some positive integer or "all", respectively. (See the examples.)

"manhattan"

the (unrestricted) median of the ensemble, minimizing \(L\) with \(d\) as Manhattan (symmetric difference) distance and \(p = 1\) over all (possibly fuzzy) relations.

"euclidean"

the (unrestricted) mean of the ensemble, minimizing \(L\) with \(d\) as Euclidean distance and \(p = 2\) over all (possibly fuzzy) relations.

"euclidean/F"

an exact solver for determining the restricted least squares Euclidean consensus relation of an ensemble of endorelations by minimizing the criterion function \(L\) with \(d\) as Euclidean difference distance and \(p = 2\) over a suitable family of crisp endorelations as indicated by F, with available families and control parameters as for methods "SD/F".

"majority"

a generalized majority method for which the consensus relation contains of all tuples occurring with a relative frequency of more than \(100 p\) percent (of 100 percent if \(p = 1\)). The fraction \(p\) can be specified via the control parameter p. By default, \(p = 1/2\) is used.

"CKS/F"

an exact solver for determining the consensus relation of an ensemble of crisp endorelations by minimizing the criterion function \(L\) with \(d\) as Cook-Kress-Seiford distance (“CKS”) and \(p = 1\) over a suitable class (“Family”) of crisp endorelations as indicated by F, with available families and control parameters as for methods "SD/F".

One can obtain a relation ensemble with up to n or all such consensus relations by setting the control parameter n to some positive integer or "all", respectively.

References

J. C. Borda (1781), M<U+00E9>moire sur les <U+00E9>lections au scrutin. Histoire de l'Acad<U+00E9>mie Royale des Sciences.

W. D. Cook and M. Kress (1992), Ordinal information and preference structures: decision models and applications. Prentice-Hall: New York. ISBN: 0-13-630120-7.

W. D. Cook and L. M. Seiford (1978), Priority ranking and consensus formation. Management Science, 24/16, 1721--1732.

M. J. A. de Condorcet (1785), Essai sur l'application de l'analyse <U+00E0> la probabilit<U+00E9> des d<U+00E9>cisions rendues <U+00E0> la pluralit<U+00E9> des voix. Paris.

A. H. Copeland (1951), A Reasonable Social Welfare Function. mimeo, University of Michigan.

K. Hornik and D. Meyer (2007), Deriving consensus rankings from benchmarking experiments. In R. Decker and H.-J. Lenz, Advances in Data Analysis. Studies in Classification, Data Analysis, and Knowledge Organization. Springer-Verlag: Heidelberg, 163--170.

F. Marcotorchino and P. Michaud (1982). Agr<U+00E9>gation de similarit<U+00E9>s en classification automatique. Revue de Statistique Appliqu<U+00E9>e, 30/2, 21--44. http://www.numdam.org/item?id=RSA_1982__30_2_21_0.

S. R<U+00E9>gnier (1965), Sur quelques aspects math<U+00E9>matiques des probl<U+00E8>mes de classification automatique. ICC Bulletin, 4, 175--191.

Examples

# NOT RUN {
## Consensus equivalence.
## (I.e., in fact, consensus partition.)
## Classification of 30 felines, see Marcotorchino and Michaud (1982).
data("Felines")
## Consider each variable an equivalence relation on the objects.
relations <- as.relation_ensemble(Felines)
## This gives a relation ensemble of length 14 (number of variables in
## the data set).
## Now fit an equivalence relation to this:
E <- relation_consensus(relations, "SD/E")
## And look at the equivalence classes:
ids <- relation_class_ids(E)
## Or, more nicely:
split(rownames(Felines), ids)
## Which is the same as in the paper ...

## Consensus linear order.
## Example from Cook and Kress, pages 48ff.
## Relation from paired comparisons.
pm <- matrix(c(0, 1, 0, 1, 1,
               0, 0, 0, 1, 1,
               1, 1, 0, 0, 0,
               0, 0, 1, 0, 0,
               0, 0, 1, 1, 0),
             nrow = 5,
             byrow = TRUE,
             dimnames = list(letters[1:5], letters[1:5]))
## Note that this is a Cook and Kress "preference matrix" where entry
## (i,j) is one iff object i is preferred to object j (i > j).
## Set up the corresponding '<' relation:
R <- as.relation(t(pm))
relation_incidence(R)
relation_is_tournament(R)
## Closest linear order:
L <- relation_consensus(R, "SD/L")
relation_incidence(L)
## Visualize provided that Rgraphviz is available.
if(require("Rgraphviz")) plot(L)
## But note that this linear order is not unique.
L <- relation_consensus(R, "SD/L", control = list(n = "all"))
print(L)
if(require("Rgraphviz")) plot(L)
## (Oh no: c is once first and once last.)
## Closest weak order relation with at most 3 indifference classes:
W3 <- relation_consensus(R, "SD/W", control = list(k = 3))
relation_incidence(W3)
# }