Journal of Classification 3:31%327 (t986)

lournal of

Classification ©1986 Springer-VerlagNew York Inc

s-Consensus Index Method: An Additional Axiom Ralph Stinebrickner Berea College

Abstract: A consensus index method is an ordered pair consisting of a consensus method and a consensus index Day and McMorris (t985) have specified two minimal axioms, one which should be satisfied by the consensus method and the other by the consensus index The axiom for consensus indices is not satisfied by the s-consensus index In this paper, an additional axiom, which states that a consensus index equal to one implies profile unanimity, is proposed The s-consensus method together with a modification of the s-consensus index (i e , normalized by the number of distinct nontrivial clusters in the profile) is shown to satisfy the two axioms proposed by Day and McMorris and the new axiom Keywords: Consensus; Intersection method; n-tree, Numerical taxonomy

1. Introduction In numerical taxonomy (Sneath and Sokal 1973), considerable attention has been focused on the construction of a consensus tree from a collection of n-trees (see Adams 1972; Margush and McMorris 1981, McMorris and Neumann 1983; Neumann 1983; Sokal and Rohlf 1981) and on the computation of a consensus index (see Rohlf 1982). Day and McMorris (1985) use three paradigms to describe consensus indices. In addition, they specify two minimal axioms, one of which should be satisfied by a consensus method and the other by a consensus index. Among the nine consensus indices which are considered by Day and McMorris (1985), only the a index (Day 1983) satisfies the axiom for consensus indices. In particular, the sconsensus index Is (Stinebrickner 1984) does not satisfy this axiom. Day and McMorris (1985) proposed two indices I~' and I~" which incorporate the essential features o f / , and which do satisfy the axiom for indices. In this paper, a third minimal axiom is suggested. It is shown that /,' and Is" do not satisfy the additional axiom However, another consensus Author's Address: Ralph Stinebrickner, Department of Mathematics, Berea College, Berea, Kentucky 40404, U S A

320

R Stinebriekner

index is proposed which again incorporates the essential features of the sconsensus index. This new index together with the s-consensus method satisfies the two axioms of Day and McMorris and the third axiom. The following section includes the definitions of n-tree and s-consensus index, and the axioms of Day and McMorris. 2. The Axioms for a Consensus Index Method

Let S be a set of n objects (operational taxonomic units in taxonomic applications) and P ( S ) be the set of all subsets of S. Throughout this note, S - - {1,2 . . . . . n}, and 1 2 . . . j will denote the subset {1,2 . . . . . j} of S. The following definition of n-tree was given by Margush and McMorris (1981). Definition 1. An n-tree is a subset T of P ( S ) satisfying the following three conditions" 1. S E T , O fiT. 2.{i} E T f o r a l l i E

S.

3. I f A , B E T w i t h A N B ~ t h e n A

c B o r B _ _ . A.

A subset of S which is an element of an n-tree T is called a cluster of T. S and the singletons are called trivial clusters of an n-tree T, and T" denotes the set of nontrivial clusters of T. Let T denote the collection of all n-trees on S and T k denote its k-fold Cartesian product. A k-tuple of n-trees is called a profile and is denoted by P -- (Tt,/'2 . . . . . Tk). Then a consensus method is a function C: U T k ---* T and a consensus index for T is a function I: U T k ---* [0,I] k~2

k~2

where [0,1] is the closed real interval between 0 and 1. C(P) is called the consensus tree and I ( P ) the consensus index for profile P. C ' ( P ) is the set of nontrivial clusters of C(P). Day and MeMorris (1985) define a consensus index method for T to be any pair (C,I) such that C is a consensus method and I is a consensus index. A consensus index method is called a CI-method (Day and McMorris 1985) if the following two axioms are satisfied" (C) (I)

For a l l k > l 2 a n d T E T , P - C(P) ~ T.

(T,T .....

For all k >t 2 and T E T, P-~ ( T , T . . . . .

T) E T kimplies T) E T k implies I ( P ) ~ 1.

In the presence of profile unanimity, these axioms require that the consensus tree be the unanimous choice and that the consensus index be 1 (i.e., indicate complete agreement).

321

s-Consensus Index Method: An AdditionalAxiom

One consensus index method consists of the s-consensus tree and sconsensus index (Stinebrickner 1984) which are described in the following definitions. Definition 2. Let P = (TI,T2 . . . . . T k) be a profile and s be a real number such t h a t 0 ~ < s~< 1. For e a c h x E S, 1 ~< i~< k, and positive integer j, let A~j = max {A.A E T~, xE A and IA I ~< J} where the maximum is with respect to set inclusion and ]A[ is the number of elements in A. Then the s-consensus tree is given by n

cs(e)= u c/ where k

L i={

k

~,Ai~i.xE

k

Sandl,=iN A i ~ i [ / [ ~ I A ~ / I > I

s} .

k

If A - - N A~j belongs to Cs(P), then the consensus strength of A is i=l

k

~,(A) = Ih 1 / t s~l A~jl where j is the least positive integer such that AEL

i.

Definition 3. Assume C ~ ( P ) = {A1,A2 . . . . . index is

Am}.

Then the s-consensus

m

Z ~(Ah) Is(p)=

h-1n - 2

As mentioned earlier, Cs satisfies Axiom (C). However, notice that if P = (T,T ..... T), then Is(P) ffi IT't/(n - 2). Thus Is(P) = 1 if and only if T is fully resolved, bifurcating into n - 2 nontrivial subsets of S. Therefore, I s does not in general satisfy Axiom (I). Day and McMorris (1985) suggest two indices which satisfy Axiom (I): 1 if C~(P) ffi ¢J and TI ffi .--- Tk ,

1~' ( P ) =

0 ifc~(e) = 0 and Tp ;~ Tq forsome l<~p
322

R Stinebriekner

and for s < l ,

I/' (P) --

1 ifC~(P)'=OandTl ~ =Tk , 0 ifC~(P)---- ~ and Tp ~ T~forsome l<~p
3. An Additional Axiom Day and McMorris (1985) claim that Axioms (C) and (I) are minimal, comprehensible and reasonable requirements for CI-methods. There is another axiom which also seems to fit the description. (N)

For all k>~2 and P E T k, I ( P ) = 1 implies P = ( T . . . . . TET

T) for some

Notice that Axiom (N) is the converse of Axiom (I). Certainly if a consensus index for a particular profile is equal to 1 (i.e., represents complete agreement), then the profile should consist of identical n-trees. In order to see that I~.' and Is" do not satisfy Axiom (N), let S--. {1,2 . . . . . 6} and P = (TbT2) where T~ = {12,34} and T~ = {12,56}. Then C~(P) == {12} for each s, 0~
0 i f C S ' ( e ) = 0 andTp ~ T o f o r s o m e l < ~ p < q < ~ k m

,

k

~_, y ( A h ) / l iU1 T,'] otherwise . h=l

Example. Before proceeding, an example of the above mentioned consensus indices will be given. Let S--{1,2,3,4,5,6}, P ffi (TI, T2) where T~' ffi {123,56} and T~ ffi {234} and s== .25. Then C~'(P) ffi {23} since 123n234 ffi 23. 3,(23) -- 123]/1123tj2341 ffi .5. Now n - 2 = 4, Ic;(e)t = 1, and IT~U T~t ffi 3. Therefore, Is(P) ffi .125, Is' (P) - .5, Is" (P) ffi (.5 - .25)/(1 - .25) ffi .333 and Is" (P) ffi .5/3 == .167

323

s - C o n s e n s u s Index Method: An Additional Axiom

Now consider the consensus index method (Cs,Is'") for some s, 0~
k

then ~ y(A h) =

IT'I-- [ U T~*I Consequently Is'" satisfies Axiom (I) It

h= 1

i=1

remains to show that Is"' is a consensus index (i.e., if k~>2 and P E T k, then O<~Is'" ( P ) ~ < I ) and that I~'" satisfies Axiom (N) If C~(P)= ¢J, then 0<~ Is" (P)~< 1 and Axiom (N) is satisfied. Therefore, throughout the following lemmas and theorems, it will be assumed that C~(P) ~ ~. Let P be a profile, k>~2 and suppose C;(P) = {AI,A2 . . . . . Am} Let A h E C~(P) and let j be the smallest positive integer such that Ah E L i. k

Recall that by Definition 2, A h = i~_l Air] where Ax"j E T,? Call the Airi the k

contributors to A h If B E U T,,

IB[ = j and B = A,~/for some i, then A h

is said to be obliged to B for its presence in C ' ( P ) or more briefly A h is obliged to B Notice A~g is obliged only to the largest contributors to the intersection.

Suppose O T~'- {BI,B2 . . . . .

B~}. For each p, l~
i=1

Op = {A h " l<~h<~m and A h is obliged to B a} Notice that if Ah is obliged to Bp, then Ah c_ Bp. As the following lemma indicates, the elements of Op are pairwise disjoint Lemma 1

I f A and A' are members of Op and A ;e A ', then A N A' = ¢J. x E A N A'and

Proof Suppose A and A' belong to Op, A N A ' # O ,

ta,l

= J.

k

Then A and A' belong to L i and A - - - A ' =

f~ A~i, where

i=1

Airi = max{A A E Tix E A andtAl~
Thus

In the remaining proofs, distinguish the contributors to A h by appendk

ing an additional h

Lemma 2

Thus A h = i~l

A x;i h.

~ 7 (A) x< 1 for each p, 1 ~ p
Proof k

IAh[

A, o,

where A h

i

A,,o, l u.=l A jhl k

Since A h E Op, then A h is obliged to Bp

Thus Bp C_ U A~ih since i=1

R Stinebriekner

324

k

Bp = A~j~ for some A~ e O~,

i,

IBpt~
and

IAhl

It follows that for each

IAhl

k ~< Ig, I I,,ut A~inl Therefore,

A~op IA, t

Z ~,(Ah) ~<

Inpl

AhEO p

However, the sets in Op are pairwise disjoint by Lemma 1 and are also subsets of n,. Thus ~ IAhl ~ Inpl, and ~ "y(Ah) ~< 1. •

Ah~O.

A,~O.

The next lemma follows from the observation that each A in C~(P) has a largest contributor and hence belongs to some Op. m

Lemma

3 "

t

y(A~) ~< Z

h=l

Y~ ~(A).

p=l AEOp

Theorem 1 O<<.Is"(P)~
Proof Clearly, Is'"(P)>~O. It is sufficient to show that if C;(P) ;~ o, then m

Z

k

m

Z ~/(Ah}

~(A~)I l u r;I ~ 1 o r

h~l

"=

k

~< [,Ul

h=l

"=

From Lemma 2, ]~ y (A) ~< 1. Then

A~O,

t

k

Z Z ~,(A)

~<

,=

I,..% T,I .

p=l AEO r

Using Lemma 3, m

k

h-l

"=

It remains to show that Is"' satisfies Axiom (N).

T.I .

325

s-Consensus Index Method: An Additional Axiom

Lemma 4

Ifls'" (P)

1, then ~, y(A)= l foreachp, 16p6t.

=

AEo.

Proof Suppose ~ ~/(A) < 1 for some p Then AeOp t

Z Z ~/(A) < t p=l AEOp m

since ~ y(A)~
Lemma 5 If Aq = N .4iiq belongs to Op and if i=1

~

y ( A ) = 1, then

AEOp

k

k

Proof Suppose Aq = i=N A~m belongs to Op and ~

y(A)= 1

Since

A¢op

B. = A~. for some i, then k

Igpl < I u~ A~jqt If

Iapl

k

<

I.~1 A~ja t, then IA~I

<

IAql .....

Using Lemma 1 and the observation that Ah _ Bp for each Ah in Op, then

Z

AI,~o,

~(Ah}-- Z

IAhl k

AI,~o,, l U1 A~.1.hl

< Z Ah~Op

Z IAhl A,,~o,, ~< IB,,I Wpl IB,,l --1

IAhl lB,,l

326

R S t i ne bri e kne r

k

Therefore, IBpl = I=O A~ml • Theorem 2 For all k>/2 and PET k, Is'" (P) for some T E T.

-~-

1 implies P

,=

(T . . . . .

T)

Proof A proof by contradiction will be given. Assume that Is'" ( P ) = 1 and that P = ( T l . . . . . Tk) is a kPr°file where 7~ ;~ Tr for some i ; ~ i' {Bp" l<~p<~t, BpEiUl T~'and Bp q i~l Ti'}. Then there is an

Suppose M =

element B~ of M which has minimum cardinality j among the elements of M. Now two cases are considered Case 1. Assume no element in C~(P) is obliged to Br Then ">,(A) = 0 By the contrapositive of Lemma 4, I~'" (P) < 1. AEO,

Case 2. Assume that some Ah in C~(P) is obliged to B r. Of course, k

ah

=

iA 1

A~ih Lemma 4 implies that ~ ~(A) = 1 and Lemma 5 implies ,4Eo k

k

k

that IB, I •= [U tA~jh [ SinceB, _ U A ~ih, ' then Br -- iU A~ih and A~jh _.C B~ '~

i~ 1

A

1

for each i. Since B~ e i__OlTi', then B-= Axijh ~ Br for some i. Therefore, k

A h c_ B. However, B E N T~" because Br is the smallest cluster which k

i=l

does not belong to N 7'/"and

[BI < IB, I. Therefore, A~ h ~ B for each i.

Since B c4 Br, Ah is not obliged to B , Since both Case 1 and Case 2 have led to contradictions, the proof of Theorem 2 is complete • 4. Conclusion Day and McMorris (1985) began a formalization of consensus index methods by describing two axioms which a consensus index method should satisfy. In addition, they proposed a change in the s-consensus index which would allow the altered s-consensus index method to satisfy the two axioms. A third axiom was proposed in the present paper and the s-consensus index was adjusted accordingly in order to provide a consensus index method k

which would satisfy all three axioms. In order to formulate I~" (P), 1U1 T~?] was suggested as the divisor. This suggestion seems to have merit when one is considering ways to redefine or define other consensus indices in order to bring them into agreement with the three axioms.

s-Consensus Index Method: An Additional Axiom

327

References ADAMS, E N Iit (1972), "Consensus Techniques and the Comparison of Taxonomic Trees," Systematic Zoology, 21, 390-397 DAY, W H E (1983), "The Role of Complexity in Comparing Classifications," Mathematical Biosciences, 66, 97-114 DAY, W I L E , and MCMORRIS, F R (1985), "A Formalization of Consensus Index Methods," Bulletin o.f Mathematical Biology, 47, 215-229 MARGUSH, T , and MCMORRIS, F R (1981), "Consensus n-Trees," Bulletin of Mathematical Biology, 43, 239-244 MCMORRIS, F R , and NEUMANN, D A (1983), "Consensus Functions Defined on Trees," Mathematical Social Sciences, 4, 131-136 NEUMANN, D A (1983), "Faithful Consensus Methods for n-Trees," Mathematical Biosciences, 63, 271-287 ROHLF, F J (1982), "Consensus Indexes for Comparing Classifications," Mathematical Biosciences, 59, 131-144 SNEATH, P H A , and SOKAL, R R (1973), Numelical Taxonomy, San Franesico W H Freeman SOKAL,. R R , and ROHLF, F J (1981), "Taxonomic Congruence 'in the Leptopodomorpha Re-examined," Systematic Zoology, 30, 309-325 STINEBRICKNER, R (1984), "s-Consensus Trees and Indices," Bulletin Of Mathematical Biology, 46, 923-935