A Theoretic Framework of K-Means-Based Consensus Clustering

1 Introduction

Consensus clustering, also known as cluster ensemble, aims to find a single partitioning of data from multiple existing basic partitionings [Monti et al., 2003; Zhang et al., 2010]. It has been recognized that consensus clustering may help to generate robust partitionings, find bizarre clusters, handle noise and outliers, and integrate solutions from multiple distributed sources [Nguyen and Caruana, 2007].

Consensus clustering is NP-complete in essence [Filkov and Steven, 2004a; Topchy et al., 2005]. In the literature, many algorithms have been proposed to address the computational challenges, among which a K-means-based method proposed in [Topchy et al., 2003] attracts great interests. However, the general theory for utility functions that work for K-means-based Consensus Clustering (KCC) is yet unavailable, which prevents KCC from being widely used.

In this paper, we provided a systematic study on the theoretic framework of K-means-based consensus clustering. The major contributions are summarized as follows. First, we formally defined the concept of KCC, and provided a necessary and sufficient condition for the so-called KCC utility functions, which establishes the general KCC framework. Second, we redesigned the computational procedures for KCC

utility functions and K-means clustering, and thus extended the framework to the more general scenario where incomplete basic partitionings present. Third, we proposed the standard and normalized forms of a KCC utility function, and gave some particular examples for practical uses.

Extensive experiments on various real-world data sets demonstrated that KCC is highly efficient and is comparable to the state-of-the-art methods in terms of clustering quality. We found that: a) While multiple utility functions can improve the usability of KCC on different types of data, the ones based on Shannon entropy generally exhibit more robust performances; b) The generation strategy of basic partitionings is a critical factor that influences the performance of KCC; c) KCC is very robust with even very few basic partitionings of high quality, or on severely incomplete basic partitionings.

2 RelatedWork

Consensus clustering (CC) is essentially a combinatorial optimization problem. The existing literature can be roughly divided into two categories: CC with implicit objectives (CCIO) and CC with explicit objectives (CCEO).

Methods in CCIO do not set global objective functions. Rather, they directly adopt some heuristics to find approximate solutions. The representative methods include the graph-based algorithms [Strehl and Ghosh, 2002; Fern and Brodley, 2004], the co-association matrix based methods [Fred and Jain, 2005; Wang et al., 2009], Relabeling and Voting methods [Fischer and Buhmann, 2003; Ayad and Kamel, 2008], Locally Adaptive Cluster based methods [Domeniconi and Al-Razgan, 2009], genetic algorithm based methods [Yoon et al., 2006], and still many more.

Methods in CCEO have explicit global objective functions for consensus clustering. The Median Partition problem based on Mirkin distance is among the oldest ones [Filkov and Steven, 2004b; Gionis et al., 2007]. In the inspiring work, [Topchy et al., 2003] proposed a Quadratic Mutual Information based objective function and used K-means clustering to find the solution. This elegant idea could be traced back to the work by Mirkin on the Category Utility Function [Mirkin, 2001]. Other solutions for different objective functions include EM algorithm [Topchy et al., 2004], nonnegative matrix factorization [Li et al., 2007], kernel-based methods [Vega-Pons et al., 2010], simulated annealing [Lu et al., 2008], and among others.

More algorithms for consensus clustering could be found in some survey papers [Ghaemi et al., 2009; Vega-Pons and Ruiz-shulcloper, 2011; Li et al., 2010]. In general, compared with CCIO methods, CCEO methods might offer better interpretability and higher robustness to clustering results, via the guidance of objective functions. However, they often bear high computational costs. Moreover, one CCEO method typically works for one objective function, which seriously limits its applicative scope. These indeed motivate our study in this paper. We attempt to build a general theoretic framework for efficient K-means-based consensus clustering using multiple utility functions.

3 ProblemFormulation

We begin by introducing some basic mathematical notations. Let X = {x1, x2, · · · , xn} denote a set of data objects. A partitioning of X into K crisp clusters can be represented as a collection of K subsets of objects in C = {Ck|k = 1, · · · ,K}, with Ck ⋂ Ck′ = ∅, ∀k ̸= k′ , and ⋃Kk=1 Ck = X, or as a label vector π = (Lπ(x1), · · · , Lπ(xn))′ , where Lπ(xi) maps xi to one of the K labels: {1, · · · ,K}.

Given r existed partitionings, i.e., basic partitionings, of X in Π = {π1, π2, · · · , πr}, the goal of consensus clustering is formulated as to find a consensus partitioning π such that

is maximized, where Γ : Zn++ × Znr ++ ↦→ R is a consensus function, U : Zn++ × Zn++ ↦→ R is a utility function, and wi ∈ [0, 1] is a user-specified weight for πi, with ∑ri=1 wi = 1. Apparently, the choice of the utility function in Eq. (1) is crucial to the success of consensus clustering, and largely determines the heuristics to employ.

3.1 K-means-based Consensus Clustering

Though being more recognized in the clustering field [Jain and Dubes, 1988], K-means [MacQueen, 1967] is essentially a very fast and robust heuristic for combinatorial optimization. A natural idea is, can we use K-means to optimize Eq. (1)? Or equivalently, can we transform the consensus clustering problem equivalently to a much simpler K-means clustering problem?

We first restrict the computation of U to the contingency matrix, a co-occurrence matrix for the clusters of two partitionings. Suppose we have π and πi, the consensus partitioning and the ith basic partitioning with K and Ki clusters, respectively. The ith contingency matrix is defined as M (i) = [n(i) kj ]K×Ki , where n(i) kj denotes the number of data objects in both cluster Ck of π and cluster C (i) j of πi, ∀ k, j. The summations can thus be given by having nk+ = ∑Ki j=1 n(i) kj and n(i) +j = ∑Kk=1 n(i) kj , ∀ k, j. Let p(i) kj = n(i) kj /n, pk+ = nk+/n, and p(i) +j = n(i) +j /n, we then have the normalized contingency matrix M (i) n , ∀ i, based on which a wide range of utility functions can be defined accordingly.

K-means does not work on the contingency matrix. As inspired by [Topchy et al., 2003], a binary matrix is introduced for it. Let X (b) = {x(b) l |1 ≤ l ≤ n} be a binary data set derived from r basic partitionings in Π such that x(b) l = (x(b) l,1 , · · · , x(b) l,r ), x(b) l,i = (x(b) l,i1 , · · · , x(b) l,iKi ), and

Accordingly, X (b) is an n × ∑ri=1 Ki binary matrix with |x(b) l,i | = 1, ∀ l, i. We can thus employ K-means on X (b) to generate one partitioning π′ with K clusters. If π′ = π in Eq. (1), it means we can transform consensus clustering to K-means clustering equivalently, and thus enable the Kmeans-based Consensus Clustering (KCC) scheme.

Let mk = (mk,1, · · · ,mk,r) denote the centroid of the kth cluster of π′ , with mk,i = (mk,i1, · · · ,mk,iKi ). We then have the following definition:

Definition 1 A utility function U is a KCC Utility Function, if ∀ Π = {π1, · · · , πr} and K ≥ 2, there exists a distance function f such that

holds for any feasible region F.

Accordingly, the critical point of KCC is to identify KCC utility functions (U) and their corresponding distance functions (f) so that the left-hand-side problem in Eq. (3) can turn into the right-hand-side problem.

4 General Theory of KCCUtility Function

In this section, we propose the necessary and sufficient condition for being a KCC utility function, and thus establish the general framework of KCC. We also extend the theory to the situation where incomplete basic partitionings exist.

4.1 The Necessary and Sufficient Condition

Here we formulate how a utility function can be a KCC utility function. A lemma is first given as follows:

Lemma 1 A utility function U is a KCC utility function, if and only if ∀ Π and K ≥ 2, there exist a differentiable convex function φ and a strictly increasing function gΠ,K such that

PROOF.We first give one fact as follows. Suppose f is a distance function that fits K-means clustering. Then according to [Wu et al., 2012], f : Rd ×Rd ↦→ R is a point-to-centroid distance that can be derived by a continuously differentiable convex function φ:

Accordingly, we have

Since both ∑x(b) l ∈X (b) φ(x(b) l ) and n are constants given Π,

Now let us turn back to the proof of the sufficient condition. As gΠ,K is strictly increasing, we have

So we finally have Eq. (3), which indicates that U is a KCC utility function. The sufficient condition holds.

We then prove the necessary condition. Suppose the distance function f in Eq. (3) is derived from a differentiable convex function φ. By Eq. (3) and Eq. (7), we have Eq. (8).

Let Υ(π) denote ∑ri=1 wiU(π, πi) and Ψ(π) denote ∑Kk=1 pk+φ(mk) for convenience. Note that Eq. (8) holds for any feasible region F because Eq. (7) is derived from the equality rather than equivalence relationship in Eq. (6). Therefore, for any two consensus partitionings π′ and π′′ , if we let F = {π′ , π′′ }, we have

which indicates that Υ and Ψ have the same ranking over all the possible partitionings in the universal set F = {π|Lπ(x(b) l ) ∈ {1, · · · ,K}, 1 ≤ l ≤ n}. Define a mapping gΠ,K that maps Ψ(π) to Υ(π), π ∈ F. According to Eq. (9), gΠ,K is a function, and ∀ x > x′ , gΠ,K (x) > gΠ,K (x′ ). This implies that gΠ,K is strictly increasing. So the necessary condition holds, and the lemma thus follows. ■

We here use Π and K as the subscripts for g, because these parameters directly affect the ranking of π in F given by Υ or Ψ. That is, different mapping functions may exist for different settings of Π and K. Next, we go a further step to analyze Eq. (4). Recall the contingency matrix mentioned in Section 3.1. Let P (i) k = (p(i) k1 /pk+, p(i) k2 /pk+, · · · , p(i) kKi /pk+), ∀ i, k. We give without proof the following lemma:

Lemma 2 For K-means clustering on X (b) , the centroids

We then have the following important theorem:

Theorem 1 U is a KCC utility function, if and only if ∀ Π = {π1, · · · , πr} and K ≥ 2, there exists a set of continuously differentiable convex functions {μ1, · · · , μr} such that

The convex function φ for the corresponding K-means clustering is given by

where

PROOF.We first prove the sufficient condition. If we substitute U(π, πi) in Eq. (11) into the left-hand-side of Eq. (4) and use Eq. (12) and Eq. (13), we have

Let gΠ,K (x) = aΠ x + bΠ , with aΠ = 1a and bΠ = - 1a ∑ri=1 wici. gΠ,K is thus a strictly increasing function for a > 0. We then have ∑ri=1 wiU(π, πi) = gΠ,K (∑Kk=1 pk+φ(mk)). U is thus a KCC utility function by Lemma 1. The sufficient condition follows.

We then prove the necessary condition. Due to the arbitrariness of Π in Eq. (4), we can let Π .= Πi = {πi}, ∀ i. Accordingly, mk reduces to mk,i, and φ(mk,i) reduces to φi(mk,i), i.e., the φ function defined only on the ith "block" of mk without involvement of the weight wi. Then by Eq. (4), we have

where gΠi,K is the mapping function when Π reduces to Πi. By summing up U(π, πi) from i = 1 to r, we have

which, in comparison to Eq. (4), indicates that

If we take the partial derivative with respect to mk,ij on both sides, we have

As (γ) and (δ) do not contain any weight parameters wl, 1 ≤ l ≤ r, the right-hand-side of Eq. (17) has one and only one weight parameter: wi. This implies that (α) is a constant, otherwise the left-hand-side of Eq. (17) would contain multiple weight parameters other than wi because of the existence of φ(mk) in g′Π,K . Analogously, since (β) does not contain all pk+, 1 ≤ k ≤ K, (γ) must also be a constant. These results imply that gΠ,K and gΠi,K , 1 ≤ i ≤ r, are all linear functions. Without loss of generality, we let

Eq. (17) thus turns into

∂φi(mk,i)/∂mk,ij is the function of {mk,i1, · · · ,mk,iKi } only, which implies that ∂φ(mk)/∂mk,ij is not the function of mk,l, ∀ l ̸= i. As a result, given the arbitrariness of i, we have φ(mk) = ϕ(φ1(mk,1), · · · , φr(mk,r)), which indicates

Accordingly, Eq. (20) turns into ∂ϕ/∂φi = wiai/aΠ , which leads to

Let νi(x) = ai aΠ φi(x)+ di wi , 1 ≤ i ≤ r, Eq. (12) thus follows. Moreover, according to Eq. (15) and Eq. (19), we have

Let μi(x) = aiφi(x) + bi, 1 ≤ i ≤ r, Eq. (11) follows. Further let a = 1/aΠ and ci = di/wi - bi/aΠ , we also have Eq. (13). The necessary condition thus follows. ■

Theorem 1 gives the general necessary and sufficient condition for being a KCC utility function. That is, a KCC utility function must be a weighted average of a set of convex functions defined on P (i) k , 1 ≤ i ≤ r, respectively. From this perspective, Theorem 1 can serve as the criterion to verify whether a given utility function is a KCC utility function or not. Nevertheless, the most important thing is, Theorem 1 indicates the way to conduct the K-means-based consensus clustering. That is, we first design or designate a set of convex functions μi defined on P (i) k , 1 ≤ i ≤ r, from which the utility function as well as the consensus function can be derived by Eq. (11) and Eq. (1), respectively; then after setting a and ci in Eq. (13), we can determine the corresponding φ for K-means clustering by Eq. (12), which is further used to derive the point-to-centroid distance f using Eq. (5); the K-means clustering is finally employed to find the consensus partitioning π. In practice, we often simplify the above procedure by letting a = 1, ci = 0, μ ≡ μi ≡ νi, ∀ i, which also become the default settings in the experiments to follow.

4.2 Two Forms of KCCUtility Functions

Let μ ≡ μi, ∀ i, in Eq. (11). We denote the KCC utility function derived by μ in Eq. (11) as Uμ for short. In what follows, we introduce two special forms of KCC utility functions given any Uμ (or equivalently μ).

Standard Form. Let P (i) = (p(i) +1 , · · · , p(i) +Ki ), and let μs(P (i) k ) = μ(P (i) k ) - μ(P (i) ). Then by Eq. (11), we obtain a new utility function Uμs as follows:

As μ(P (i) ) is a constant given πi, μs and μ will lead to a same point-to-centroid distance f, and thus a same consensus partitioning π. It is easy to show Uμs is non-negative, and thus can be viewed as the utility gain from a consensus clustering. We here define Uμs as the standard form of Uμ. If we further let μss(P (i) k ) = μs(P (i) k ) - μs(P (i) ), we have μss = μs ⇒ Uμss = Uμs . This implies that any KCC utility function has one and only one standard form.

Normalized Form. Let μn(P (i) k ) = μs(P (i) k )/|μ(P (i) )|, we have a new KCC utility function as follows:

Apparently, Uμn ≥ 0, which can be viewed as the utility gain ratio to the constant |μ(P (i) )|, and thus is called the normalized form of Uμ. It is noteworthy that a KCC utility function also has one and only one normalized form.

In summary, given a convex function μ, we can derive a KCC utility function Uμ, as well as its only standard form Uμs and normalized form Uμn . Given clear physical meanings, the standard form and normalized form will be adopted as two major forms of KCC utility functions in the experimental section below. Table 1 shows some sample KCC utility functions, which are all in their standard forms.

4.3 Handling Incomplete Basic Partitionings

Here, we introduce how to conduct K-means-based consensus clustering with the presence of incomplete basic partitionings (IBPs). An IBP πi is obtained by clustering a data subset Xi ⊆ X, 1 ≤ i ≤ r, with the constraint that ⋃ri=1 Xi = X. The problem is, given r IBPs in Π = {π1, · · · , πr}, how to cluster X into K crisp clusters using KCC?

We first adjust the way for utility computation on IBPs. We still have maximizing Eq. (1) as the objective function, but modify the normalized contingency matrix M (i) n so that: n(i) = |Xi|, p(i) kj = n(i) kj /n(i) , p(i) k+ = n(i) k+/n(i) , p(i) +j = n(i) +j /n(i) , and p(i) = n(i) /n, ∀ j, k, i.

We then adjust K-means clustering for the incomplete binary data set X (b) . Let the distance f be the sum of the distances on different basic partitionings, i.e.,

where fi is f on the ith "block" of X (b) , and I(xl ∈ Xi) = 1 if xl ∈ Xi and 0 otherwise. Further let the centroid mk,i = (mk,i1, · · · ,mk,iKi ), with

In what follows, we give without proof a theorem about the convergence of K-means clustering on incomplete X (b) :

Note: ‖x‖p - Lp norm of x; H - Shannon entropy; D - KL-divergence; cos - cosine similarity.

N/A: Failure due to the out-of-memory error.

Table 3: Experimental Data Sets

• † : two clusters containing only two objects were deleted as noise.
• ‡: the values of the last attribute were normalized by a scaling factor 100.

Theorem 2 K-means clustering using f in Eq. (25) as the distance function and using m in Eq. (26) as the centroid, is guaranteed to converge in finite iterations.

Theorem 3 U is a KCC utility function, if and only if ∀ Π = {π1, · · · , πr} and K ≥ 2, there exists a set of continuously differentiable convex functions {μ1, · · · , μr} such that

The convex function φi, 1 ≤ i ≤ r, for the corresponding K-means clustering is given by

where

The proof is similar to the one for Theorem 1, so we omit it here. Eq. (27) is very similar to Eq. (11) except for having additional parameters p(i) , ∀ i. This implies that the basic partitioning on a larger data subset will have more impact on the consensus clustering, which is considered reasonable. Since Eq. (27) reduces to Eq. (11) when IBPs turn into complete BPs, Theorem 3 is indeed a more general version of Theorem 1.

5 Experimental Results

In this section, we present experimental results of KCC on various real-world data sets listed in Table 3.

5.1 Experimental Setup

Validation measure. Having the class labels, we adopted normalized Rand index (Rn), a long-standing and robust measure [Jain and Dubes, 1988], for cluster validity.

Clustering tools. Three consensus clustering methods, namely KCC, the graph partitioning algorithm (GP), and the hierarchical algorithm (HCC), were employed in the experiments. GP is a tool consisting of three benchmark algorithms: CSPA, HGPA and MCLA [Strehl and Ghosh, 2002]. HCC was implemented by ourselves in MATLAB following the algorithmic description in [Fred and Jain, 2005]. We also implemented KCC in MATLAB, which includes ten utility functions, namely Uc, UH, Ucos, UL5 and UL8 , and their corresponding normalized versions (denoted as NUx).

Parameter settings. To generate basic partitionings (BPs), we used the kmeans function of MATLAB with squared Euclidean distance for UCI data sets and with cosine similarity for text data sets. The default settings are as follows: 1) r = 100; 2) the number of clusters K is set to the number of true clusters; 3) Random Parameter Selection (RPS) is the default generation strategy for BPs by randomizing Ki within [K, √n]; 4) wi = 1/n, ∀ i. For each Π, KCC and GP were run ten times to obtain the average results, whereas HCC was run only once due to its deterministic nature. In each run, KCC called K-means ten times for the best objective values, and GP called CSPA, HGPA and MCLA only once.

5.2 Clustering Efficiency of KCC

The primary concern about consensus clustering is the efficiency. Along this line, we compared KCC (using Uc) with GP and HCC in terms of execution efficiency. As can be seen from Table 2, KCC was the fastest one on nine out of eleven data sets, even though it called kmeans 10×10 times on each data set. For large-scale data sets, such as satimage and reviews, the advantage of KCC was particularly evident. HCC seems more suitable for small data sets for its n-squared complexity. GP consumed much less time than HCC on largescale data sets, but it suffered from high space complexity which led to memory failures marked as "N/A" in Table 2.

5.3 Clustering Quality of KCC

The clustering results of KCC are shown in Table 4. Eight out of ten utility functions performed the best on at least one data set. For some data sets such as breast w the differences were very sharp. This implies that the diversity of utility functions is indeed beneficial. KCC achieves an edge by allowing the flexible choice of utility functions.

We then validated the robustness of each utility function on all data sets. A utility function Ui is scored by score(Ui) = ∑j Rn(Ui ,Dj ) maxi Rn(Ui,Dj) , where Rn(Ui, Dj) is the Rn value of the clustering result by applying Ui on data set Dj. The bottom row of Table 4 shows the scores, where the highest score was won by NUH, closely followed by UH, and then NUcos and Ucos. We therefore took NUH as the default choice for KCC. It is interesting that though being the first utility function proposed in the literature, Uc and its normalized version generally performed the worst among all.

Next we compared KCC using NUH with the other two methods GP and HCC. As can be seen from Fig. 1, KCC showed comparable clustering performances. Indeed, KCC outperformed GP on 5 out of 8 data sets, and beat HCC on 5 out of 9 data sets. Note that in the left (right) sub-graph we omitted three (two) data sets, on which GP (HCC) suffered memory failures when running on a PC with 4GB RAM.

Note that we so far relied on RPS to generate basic partitionings, which led to poor clustering results on wine, dermatology, la12 and sports. One way to deal with these is to adjust RPS. Indeed, we found that by narrowing the interval of Ki in RPS to [2, 2K], the performances of KCC on la12 and sports improved substantially. Similar situations happened to wine and dermatology when we replaced RPS by RFS (Random Feature Selection), where partial data attributes (e.g., 20%) were randomly selected for each basic clustering. We omit details here for space concern.

In summary, KCC is flexible and competitive to GP and HCC in terms of clustering quality. Among the ten utility functions, NUH shows more robust performances and thus becomes the primary choice for KCC.

5.4 Performances on Incomplete BPs

Here, we demonstrate the ability of KCC in handling incomplete BPs (IBP). To this end, we adopted two strategies to generate IBPs. Strategy-I is to randomly remove some data instances from a data set first, and then employ kmeans on the incomplete data set to generate an IBP. Strategy-II is to employ kmeans on the whole data set first, and then randomly remove some labels from the complete BP. The removal ratio rr was set from 0% to 90% to watch the variations.

Fig. 2 shows that IBPs generally exerted little impact on KCC when rr < 70%. For mm, the performance of KCC was even improved from around 0.6 to over 0.8 when 10% ≤ rr ≤ 70%! This result strongly indicates that KCC is very robust to IBPs - it can recover the whole cluster structure from cluster fragments. It is also interesting to see that the effect of Strategy-I was comparable to the effect of Strategy-II. In some cases, e.g., on mm, or on breast w and iris when rr is sufficiently large, Strategy-I even led to better performances. This observation is somewhat surprising, since Strategy-II was thought to reserve the structural information more. It is however encouraging since Strategy-I is closer to real-life scenarios of knowledge fusion.

6 Conclusions

In this paper, we established a general theoretic framework of K-means-based consensus clustering (KCC). Experiments demonstrated the effectiveness of KCC compared with some state-of-the-art methods. In particular, KCC shows robust performances even if only a few high-quality basic partitionings are available or they suffers severe incompleteness.

Acknowledgments

This work was partially supported by the National Natural Science Foundation of China (NSFC) under Grants 71171007, 70901002, 71028002 and 71031001, by the Foundation for the Author of National Excellent Doctoral Dissertation of PR China under Grant 201189, and by the Program for New Century Excellent Talents in University under Grant NCET-11-0778. Dr. Jie Cao's work was supported in part by NSFC under Grant 71072172.