Consensus-Based Agglomerative Hierarchical Clustering

Chapter 1 CONSENSUS-BASED AGGLOMERATIVE HIERARCHICAL CLUSTERING Jos´e Luis Garc´ıa-Lapresta1and David P´erez-Rom´an2 1PRESAD Research Group, BORDA Research Unit, IMUVA, Dept. de Econom´ıa Aplicada, Universidad de Valladolid, Spain 1PRESAD Research Group, BORDA Research Unit, Dept. de Organizaci´on de Empresas y C.I.M., Universidad de Valladolid, Spain Abstract In this contribution, we consider that a set of agents assess a set of alternatives through numbers in the unit interval. In this setting, we introduce a measure that assigns a degree of consensus to each subset of agents with respect to every subset of alternatives. This consensus measure is defined as 1 minus the outcome generated by a symmetric aggregation function to the distances between the corresponding individual assessments. We establish some properties of the consensus measure, some of them depending on the used aggregation function. We also introduce an agglomerative hierarchical clustering procedure that is generated by similarity functions based on the previous consensus measures. Keywords: Consensus, clustering, aggregation functions, OWA operators. 1. Introduction When a group on agents show their opinions about a set of alternatives, an important issue is to know the homogeneity of these opinions. In this chapter we consider that agents evaluate each alternative by means of a number in the unit interval. For measuring the consensus in a group of agents over a subset of alternatives, we propose to aggregate the distances between the corresponding individual assessments through an appropriate symmetric aggregation function. This outcome measures the dispersion of individual opinions in a similar way to the Gini index [19] measures the inequality of individual incomes (see 2Consensus-based agglomerative hierarchical clustering Yitzhaki [32]). The consensus measure we propose is just 1 minus the mentioned dispersion measure. The most important is not to know the degree of consensus in a specific group of agents, but comparing the consensus of different group of agents with respect to an alternative or a subset of alternatives. This is the starting point of the agglomerative hierarchical clustering procedure we propose. We consider as linkage clustering criterion one generated by a consensus-based similarity function that merges clusters or individuals by maximizing the consensus. The rest of the chapter is organized as follows. Section 2 contains some notation and basic notions. In Section 3, we introduce and analyze the proposed consensus measures. Section 4 contains our proposal of consensus-based agglomerative hierarchical clustering. In Section 5, we illustrate the introduced procedures with an example. Finally, in Section 6, we conclude with some remarks. 2. Preliminaries Given y,z∈[0,1]k, by y≥zwe mean yi≥zifor every i∈ {1,...,k}. Given y∈[0,1]k, the decreasing reordering of the coordinates of yis indicated as y[1]≥ ··· ≥ y[k]. In particular, y[1]=max{y1,...,yk}and y[k]= min{y1,...,yk}. Given a real number y, by bycwe denote the integer part of y, i.e., the greatest integer number smaller than or equal to y. With #Iwe denote the cardinality of I. With P2(A) = {I⊆A|#I≥2}we denote the family of subsets of at least two elements. We begin by defining standard properties of real functions on [0,1]k. For further details the interested reader is referred to Fodor and Roubens [12], Calvo et al. [6], Beliakov et al. [4], Torra and Narukawa [27], Grabisch et al. [20] and Beliakov et al. [3]. Definition 1.1 Let F :[0,1]k−→ [0,1]be a function. 1 F is idempotent if for every y ∈[0,1]it holds F(y·1) = y. 2 F is symmetric if for every permutation πon {1,...,k}and every y∈ [0,1]kit holds F(yπ(1),...,yπ(k)) = F(y). 3 F is monotonic if for all y,z∈[0,1]kit holds y≥z⇒F(y)≥F(z). 4 F is compensative if for every y∈[0,1]kit holds y[k]≤F(y)≤y[1]. 5 F is self-dual if for every y∈[0,1]kit holds F(1−y) = 1−F(y). 6 F is stable for translations if for all y∈[0,1]kand t ∈[0,1]such that y+t·1∈[0,1]kit holds F(y+t·1) = F(y)+t. Preliminaries 3 Definition 1.2 1 Given k ∈N, a function F(k):[0,1]k−→ [0,1]is called an k-ary aggregation function if it is monotonic and satisfies the boundary conditions F(k)(0) = 0and F(k)(1) = 1. In the extreme case of k =1, the convention F(1)(y) = y for every y ∈[0,1]is considered. 2 An aggregation function is a sequence F =F(k)k∈Nof k-ary aggregation functions. 3 An aggregation function F =F(k)k∈Nsatisfies a property (in particular, those appearing in Definition 1.1) whenever F(k)satisfies the same property for every k ∈N. It is easy to see that for every k-ary aggregation function, idempotency and compensativeness are equivalent. For the sake of simplicity, the k-arity is omitted whenever it is clear from the context. An interesting class of aggregation functions is the family of OWA operators, introduced by Yager [29]. Aweighting vector of dimension kis a vector w= (w1,...,wk)∈[0,1]k such that k ∑ i=1 wi=1. Definition 1.3 Given a weighting vector wof dimension k, the OWA operator associated with wis the aggregation function Fw:[0,1]k−→ [0,1] defined as Fw(y1,...,yk) = k ∑ i=1 wi·y[i]. Some well-known aggregation functions are specific cases of OWA operators. With appropriate weighting vectors w= (w1,...,wk)we obtain 1 The maximum, for w= (1,0,...,0). 2 The minimum, for w= (0,...,0,1). 3 The arithmetic mean, for w=1 k,...,1 k. 4 The t-trimmed means: If t=1, for w=0,1 k−2,..., 1 k−2,0. If t=2, for w=0,0,1 k−4,..., 1 k−4,0,0. .... 4Consensus-based agglomerative hierarchical clustering 5 The median: (a) If kis odd, for wi=(1,if i=k+1 2, 0,otherwise. (b) If kis even, for wi=(0.5,if i∈k 2,k 2+1, 0,otherwise. 6 The mid-range, for w= (0.5,0,...,0,0.5). OWA operators are continuous, idempotent (hence, compensative), symmetric, and stable for translations. They have been characterized by Fodor et al. [11]. Centered OWA operators have been introduced by Yager [31] in order to give “the most weight to the central scores in the argument tuples and less weighting to the extreme values”. We now introduce a more general notion than that provided by Yager. It was introduced by Garc´ ıa-Lapresta and Mart´ ınez-Panero [14]. Definition 1.4 Given a weighting vector wof dimension k, the OWA operator associated with wis centered if the following two conditions are satisfied: 1 wk+1−i=wifor every i ∈ {1,...,k}. 2 wi≤wjwhenever i <j≤ bk+1 2cor i >j≥ bk+1 2c. The first condition is equivalent to the property of self-duality (see Garc´ ıa- Lapresta and Llamazares [13, Proposition 5]). The second condition is weaker than the original of Yager [31], called strongly decaying, that requires strict inequalities wi<wj. Yager [31] requires a third condition in the definition of centered OWA operators, inclusiveness:wi>0 for every i∈ {1,...,k}. That condition is very restrictive for our purposes, since it eliminates some interesting OWA operators as median and trimmed means, among others. Definition 1.5 An extended OWA (EOWA) operator is a sequence of OWA operators (Fwk)k∈Nwith associated weighting vectors wk= (wk 1,...,wk k), one for each dimension k ∈N. Following Mayor and Calvo [24], Calvo and Mayor [7], Beliakov et al. [4, pp. 54-56] and Beliakov et al. [3, pp. 73-76]), we can show graphically an EOWA operator as a weighting triangle where the entries in each row add up to one: Consensus 5 w1 1 w2 1w2 2 w3 1w3 2w3 3 w4 1w4 2w4 3w4 4 w5 1w5 2w5 3w5 4w5 5 ... ... ... ... ... ... ... ... ... ... ... A very useful approach for obtaining the EOWA weights is the functional method introduced by Yager [30, 31]. Given a BUM function, i.e., a monotonic function f:[0,1]−→ [0,1]such that f(0) = 0 and f(1) = 1, the associated EOWA weights are defined as wk i=fi k−fi−1 k,i=1,...,k.(1) Yager [31] proposes to generate BUM functions by means of centering functions. Acentering function is a function g:[0,1]−→ Rsatisfying the following conditions: 1g(x)>0 for every x∈[0,1]. 2g(0.5+x) = g(0.5−x)for every x∈[0,0.5]. 3g(x)<g(y)for x<y≤0.5 and g(x)<g(y)for x>y≥0.5. Then, the function f:[0,1]−→ [0,1]defined as f(x) = Zx 0 g(y)dy Z1 0 g(y)dy (2) is a BUM function. 3. Consensus For measuring the degree of consensus among a group of agents that provide their opinions on a set of alternatives, different proposals can be found in the literature (see Mart´ ınez-Panero [23] for an overview of different notions of consensus). In the social choice framework, the notion of consensus measure was introduced by Bosch [5] in the context of linear orders. Additionally, Bosch [5] and Alcalde-Unzu and Vorsatz [1] provided axiomatic characterizations of 6Consensus-based agglomerative hierarchical clustering several consensus measures in the context of linear orders. Garc´ ıa-Lapresta and P´ erez-Rom´ an [15] extended that notion to the context of weak orders and they analyzed a class of consensus measures generated by distances. Alcantud et al. [2] provided axiomatic characterizations of some consensus measures in the setting of approval voting. In turn, Erdamar et al. [8] extended the notion of consensus measure to the preference-approval setting through different kinds of distances, and Garc´ ıa-Lapresta et al. [18] introduced another extension to the framework of hesitant linguistic assessments. Let A={1,...,m}, with m≥2, be a set of agents and let X={x1,...,xn}, with n≥2, be the set of alternatives which have to be evaluated in the unit interval. Aprofile is a matrix V=      v1 1··· v1 i··· v1 n ··· ··· ··· ··· ··· va 1··· va i··· va n ··· ··· ··· ··· ··· vm 1··· vm i··· vm n       = (va i) consisting of mrows and ncolumns of numbers in [0,1], where the element va i represents the assessment given by the agent a∈Ato the alternative xi∈X. Let V= (va i)be a profile, πa permutation on A,σa permutation on {1,...,n},I∈P2(A)and /0 6=Y⊆X. The profiles Vπ,Vσand V−1, and the subsets Iπand Yσare defined as follows: 1Vπ= (ua i)where ua i=vπ(a) i. 2Vσ= (ua i)where ua i=va σ(i). 3V−1= (ua i)where ua i=1−va i. 4Iπ=π−1(a)|a∈A, i.e., a∈Iπ⇔π(a)∈I. 5Yσ={xσ−1(i)|xi∈Y}, i.e., xi∈Yσ⇔xσ(i)∈Y. We now introduce a consensus measure associated with a symmetric aggregation function. Given a profile, it assigns a degree of consensus in each subset of at least two agents with respect to a subset of alternatives. Definition 1.6 Let F =F(k)k∈Nbe a symmetric aggregation function. Given a profile V = (va i), the degree of consensus in a subset of agents I ∈ P2(A)over a subset of alternatives /0 6=Y⊆X is defined as CF(V,I,Y) = 1−F va i−vb ia,b∈I,a<b xi∈Y!. Consensus 7 In Proposition 1.1 we establish some properties of the consensus notion introduced in Definition 1.6. Normalization means that the degree of consensus is always in the unit interval. Anonymity means that all agents are treated in the same way. Unanimity establishes necessary and sufficient conditions for reaching maximum consensus. Maximum dissension establishes necessary and sufficient conditions for reaching minimum consensus in two agents. Positiveness establishes that with more than two agents the degree of consensus is never minimum. Neutrality means that all alternatives are treated in the same way. And reciprocity means that if all the agents reverse their assessments, then the degree of consensus does not change. Proposition 1.1 Let F =F(k)k∈Nbe a symmetric aggregation function. The following properties are satisfied: 1Normalization: CF(V,I,Y)∈[0,1]. 2Anonymity: CF(Vπ,Iπ,Y) = CF(V,I,Y)for every permutation πon A. 3Unanimity: If for every xi∈Y there exists ti∈[0,1]such that va i=ti for every a ∈I, then CF(V,I,Y) = 1. Additionally, if F(k)(y) = 0⇔y=0, for all k ∈Nand y∈[0,1]k, and CF(V,I,Y) = 1, then for every xi∈Y there exists ti∈[0,1]such that va i=tifor every a ∈I. 4Maximum dissension: If va i=0and vb i=1or va i=1and vb i=0 for all xi∈Y, then CF(V,{a,b},Y) = 0. Additionally, if F(k)(y) = 1⇔y=1, for all k ∈Nand y∈[0,1]k, and CF(V,{a,b},Y) = 0, then va i=0and vb i=1or va i=1and vb i=0for all xi∈Y . 5Positiveness: If F(k)(y) = 1⇔y=1, for all k ∈Nand y∈[0,1]k, and #I>2, then CF(V,I,Y)>0. 6Neutrality: CF(Vσ,I,Yσ) =CF(V,I,Y)for every permutation σon {1,...,n}. 7Reciprocity: CF(V−1,I,Y) = CF(V,I,Y). PROOF: It is straightforward. Remark 1.1 Let (Fwk)k∈Nan EOWA operator with associated weighting vectors wk= (wk 1,...,wk k),k∈N. It is easy to check that Fwk(y) = 0⇔y= 0, for every y∈[0,1]k, if and only if wk 1>0; and Fwk(y) = 1⇔y=1, for every y∈[0,1]k, if and only if wk k>0. Consequently, any EOWA operator satisfying wk 1>0 and wk k>0 for every k∈Nverifies all the properties included in Proposition 1.1. Therefore, when 8Consensus-based agglomerative hierarchical clustering considering the EOWA operators generated by the maximum, the minimum, the trimmed means and the median, the corresponding consensus measures do not satisfy the strong versions of unanimity and maximum dissension. For our purposes, an interesting class of EOWA operators is the one generated by centered OWA operators (in the sense of Definition 1.4) satisfying wk 1=wk k>0 for every k∈N. 4. Clustering There are many clustering algorithms (see Ward [28], Jain et al. [21] and Everitt et al. [9], among others). Most methods of hierarchical clustering use an appropriate metric (for measuring the distance between pairs of observations), and a linkage criterion which specifies the similarity/dissimilarity of sets as a function of the pairwise distances of observations in the corresponding sets. Ward [28] proposed an agglomerative hierarchical clustering procedure, where the criterion for choosing the pair of clusters to merge at each step is based on the optimization of an objective function. Usually, clusters are merged by minimizing a distance between clusters. The complete, single and average linkage clustering take into account the maximum, minimum and mean distance between elements of each cluster, respectively. In turn, centroid linkage clustering is based on the distances between the clusters centroids. In all the mentioned linkage clustering criteria there is a loss of information. In our proposal, clusters are merged when maximizing the consensus and, consequently, all the information is used for merging clusters. Definition 1.7 Let F =F(k)k∈Nbe a symmetric aggregation function. Given a profile V = (va i), the similarity function relative to a subset of alternatives /0 6=Y⊆X SY F:P(A)\{/0}2−→ [0,1] is defined as SY F(I,J) = (CF(V,I∪J,Y),if #(I∪J)≥2, 1,if #(I∪J) = 1. Remark 1.2 In the extreme case of two agents and a single alternative, the similarity between these agents on that alternative is just 1 minus the distance between their assessments. More formally, given an alternative xi∈Xand two different agents a,b∈A, we have S{xi} F({a},{b}) = CF(V,{a,b},{xi}) = 1−va i−vb i. An illustrative example 9 The agglomerative hierarchical clustering procedure we propose has some similarities to the ones provided by Garc´ ıa-Lapresta and P´ erez-Rom´ an [16, 17], in different settings. Given an aggregation function F=F(k)k∈Nand a profile V= (va i), our proposal consists of a sequential process addressed by the following stages: 1 The initial clustering is AY 0={{1},...,{m}}. 2 Calculate the similarities between all the pairs of agents, SY F({a},{b}) for all a,b∈A. 3 Select the two agents a,b∈Athat maximize SY Fand construct the first cluster AY 1={a,b}. 4 The new clustering is AY 1=AY 0\{{a},{b}}∪AY 1. 5 Calculate the similarities SY F(AY 1,{c})and take into account the previously computed similarities SY({c},{d}), for all {c},{d} ∈ AY 1. 6 Select the two elements of AY 1that maximize SY Fand construct the second cluster Ai 2. 7 Proceed as in previous items until obtaining the next clustering Ai 2. The process continues in the same way until obtaining the last cluster, AY m−1= {A}. In the case of several pairs of agents or clusters are in a tie, then proceed in a lexicographic manner in 1,...,m. 5. An illustrative example In order to illustrate the agglomerative hierarchical clustering procedure introduced in Section 4, consider a set of eight experts A={1,2,3,4,5,6,7,8} assessing a set of six alternatives X={x1,x2,x3,x4,x5,x6}through the following profile V=         1.0 0.9 0.7 0.5 0.5 0.0 0.5 1.0 0.8 0.0 0.6 0.4 0.3 0.8 1.0 0.8 0.6 0.6 0.6 1.0 0.2 0.6 0.7 1.0 0.4 0.4 0.4 0.3 0.9 0.7 0.3 0.7 0.3 0.3 0.7 1.0 0.0 0.9 0.2 1.0 0.0 1.0 0.5 1.0 0.5 0.7 1.0 0.7         . In order to show the importance of the aggregation function for defining the consensus measure that generates the cluster formation, we have considered