We propose a new algorithm for consensus clustering, FCAConsensus, based on Formal Concept Analysis. As the input, the algorithm takes T partitions of a certain set of objects obtained by k-means algorithm after T runs from different initialisations. The resulting consensus partition is extracted from an antichain of the concept lattice built on a formal context objects classes, where the classes are the set of all cluster labels from each initial k-means partition. We compare the results of the proposed algorithm in terms of ARI measure with the state-of-theart algorithms on synthetic datasets. Under certain conditions, the best ARI values are demonstrated by FCA-Consensus.
Although the subject of consensus partition has been considered in the literature
as early as in 1960s ([
As the input the consensus clustering approach usually takes T partitions of
a certain set of objects obtained, for example, by k-means algorithm after its T
different executions with possibly different k. The resulting consensus partition
is built from the matrix objects classes, where the classes are the set of all
cluster labels from each initial k-means partition. Thus, the main goal of
consensus clustering is to find (recover) an optimal partition, i.e. to guess the proper
number of resulting clusters and put the objects into each part correctly (see, for
example, [
In [
Here, our main goal is to propose a novel lattice-based consensus clustering
algorithm by means of FCA and show its competitive applicability. To the best of
our knowledge, a variant of FCA-based consensus approach was firstly proposed
for clustering genes [
The paper is organised in five sections. In Section 2, we refresh some definitions from FCA, introduce partitions and the lattice of partitions, and show how any partition lattice can be mapped to a concept lattice. In Section 3, we introduce our modification of Close-by-One algorithm for consensus clustering. In Section 4, we describe our experimental results over synthetic data both for individual properties of FCA-Consensus and for comparison with the state-of-the-art clustering methods. Section 5 concludes the paper and outlines prospective ways of research and developments. 2
First, we recall several notions related to lattices and partitions.
is called block.
Definition 1. A partition of a nonempty set A is a set of its subsets = fB j B Ag such that S B = A and B \ C = ; for all B; C 2 . Every element of
B2 Definition 2. A partition lattice of set A is an ordered set (P art(A); _; ^) where P art(A) is a set of all possible partitions of A and for all partitions and supremum and infimum are defined as follows: _ = fN (B) [
[ C2N (B)
N (C)jB 2 g; ^ = fB \ C j for all B 2 and C 2 g; where N (B) = fC j B 2 and B \ C 6= ;g.
; C 2 and B \ C 6= ;g and N (C) = fB j B 2 ; C 2 Definition 3. Let A be a set and let ; than the partition if every block B of 2 P art(A). The partition is a union of blocks of , that is is finer .
Equivalently one can use traditional connection between supremum, infimum and partial order in the lattice: iff _ = ( ^ = ).
Now, we recall some basic notions of Formal Concept Analysis (FCA) [
A0 = fm 2 M j gIm for all g 2 Ag; B0 = fg 2 G j gIm for all m 2 Bg: (1)
The pair (A; B), where A G, B M , A0 = B, and B0 = A is called a (formal) concept (of the context K) with extent A and intent B (in this case we have also A00 = A and B00 = B).
The concepts, ordered by (A1; B1) (A2; B2) () A1 A2 form a complete lattice, called the concept lattice B(G; M; I).
Theorem 1. (Ganter&Wille [
Theorem 2. (this paper) For a given partition lattice L = (P art(A); _; ^) there exist a formal context K = (P2; A2; I), where P2 = ffa; bg j a; b 2 A and a 6= bg, A2 = f j 2 P art(A) and j j = 2g and fa; bgI when a and b belong to the same block of . The concept lattice B(P2; A2; I) is isomorphic to the initial lattice (P art(A); _; ^).
Proof. According to Theorem 1 the concept lattice of the context KDM = (J (L); M (L); ) is isomorphic to the Dedekind–McNeille completion of L. The Dedekind–McNeille completion of a lattice is its isomorphic lattice by the definition (as a minimal completion which forms a lattice). So, we have to show that contexts K and KDM (or their concept lattices) are isomorphic.
E.g., from [
It is evident that all the atoms are join-irreducible and all the coatoms are meet-irreducible and that there are no other irreducible elements of the partition lattice L.
Let and be two partitions from L, 2 J (L) and 2 M (L), and . It means that all blocks of are subsets of blocks of and the non-trivial block fi; jg 2 is a subset of one of the blocks of . Note that A2 coincides with the coatom set. It directly implies that fi; jgI iff an atom with block fi; jg is finer than a coatom .
In addition we can show the correspondence between elements of L = (P art(A); _; ^) and formal concepts of B(P2; A2; I). Every (A; B) 2 B(P2; A2; I) corresponds to = V B and every pair fi; jg from A is in one of blocks, where 2 P art(A). Every (A; B) 2 BDM (J (L); M (L); ) corresponds to = V B = W A. Example 1. In Fig. 1, one can see the diagram of a concept lattice isomorphic to the partition lattice of 4-element set. To work in FCA terms we need to introduce a (formal) partition context that corresponds to the matrix X from the previous subsection. Let us consider such a context KR = (G; tMt; I G tMt), where G is a set of objects, t = 1; : : : ; T , and each Mt consists of labels of all clusters in the t-th k-means partition from the ensemble. For example, gImt1 means that object g has been clustered to the first cluster by t-th clustering algorithm in the ensemble.
Our FCA-Consensus algorithm looks for S, an antichain of concepts of KR, such that for every (A; B) and (C; D) the condition A \ C = ; is fulfilled. Here, the concept extent A corresponds to one of the resulting clusters, and its intent contains all labels of the ensemble members that voted for the objects from A being in one cluster. The input cluster sizes may vary, but it is a reasonable consensus hypothesis that at least dT =2e should vote for a set of objects to be in cluster.
One can prove a theorem below, where by true partition we mean the original partition into clusters to be recovered.
Theorem 3. In the concept lattice of a partition context KR = (G; tMt; I G tMt), there is the antichain of concepts S such that all extents of its concepts Ai coincide with Si from , the true partition, if and only if Si00 = Si where i = 1; : : : ; j j.
Proof. The proof is obvious because of the fact that parts of partitions are nonintersecting and each part should be closed to form a concept extent.
In fact, it happens if all ensemble algorithms have voted for all objects from Si to belong in a same concept (cluster). However, this is a rather strong requirement and we should experimentally study good candidates for such an antichain.
The algorithm below works incrementally by adding objects one by one and
checking a new “canonicity” conditions, like it is in algorithms ADDI [
Algorithm 1: Main((G; M; I); T )
Thus, the resulting antichain S may not cover all objects but we can add each non-covered object g to a concept (A; B) 2 S with maximal size of the intersection, jB \g0j. Traditionally, the algorithm consists of two parts, a wrapper procedure, Main, and a recursive procedure, Process. 4
All evaluations are done on synthetic datasets that have been generated using Matlab. Each of the datasets consists of 300 five-dimensional objects comprising three randomly generated spherical Gaussian clusters. The variance of each Algorithm 2: Process((G; M; I); T; S) cluster lies in 0:1 0:3 and its center components are independently generated from the Gaussian distribution N (0; 0:7).
Let us denote thus generated partition as with k clusters. The profile of partitions R = f 1; 2; : : : ; T g for consensus algorithms is constructed as a result of T runs of k-means clustering algorithm starting from random k centers.
We carry out the experiments in four settings:
This criterion expresses similarity of two partitions; its values vary from 0 to 1, where 1 means identical partitions, and 0 means totally different ones.
IR 0.6 A 0.9 0.8 0.7 0.5 0.4 0.3
The lattice-based consensus results have been compared with the results of the
following algorithms (Fig. 5–8):
– AddRemAdd ([
70%
To provide the reader with more details we show the values of ARI graphically for each dataset out of ten used. The summarised conclusions are given in the next section. 5
Our experiments lead us to the following conclusions: – The “Optimal voting threshold” as related to the minimum intent size for the resulting antichain of concepts is not constant; moreover, it is not usually the majority of ensemble members (see Fig. 2). – Our FCA-based consensus clustering method works better when the number of clusters at the ensemble clusterers is equal to the number of true clusters (see Fig. 3).
1 2 3 4 5 6 7 8 9
10
Fig. 4. Influence of different numbers of objects to ARI
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
One straightforward step to be taken is testing our algorithm over real
datasets. The algorithm can be modified for application on the space of all
partition labels when the number of objects is greater than that of the labels.
The algorithm complexity and time-efficiency should be carefully studied and
compared with those of the existing algorithms. An interesting venue is to
consider the partition lattices as a search space for finding an optimal partition.
For example, one can build a pattern structure [
Acknowledgments We would like to thank Jaume Baixeries, Amedeo Napoli, Alexei Buzmakov, Mehdi Kaytoue, and Oleg Anshakov for their comments, remarks and help while preparing this paper. The paper was prepared within the framework of the Basic Research Program at the National Research University Higher School of Economics (HSE) and supported within the framework of a subsidy by the Russian Academic Excellence Project “5-100”. The third co-author was partially supported by Russian Foundation for Basic Research, grants no. 16-29-12982 and 16-01-00583.