Evolutionary approach to multimodal clustering on multidimensional formal contexts is proposed. Its main advantage is that it allows one to find a well-grounded number of clusters corresponding to the global or close to the global extremum of the function that characterizes the quality of solution of the clustering problem. This approach is efective when the proximity measure for a data being clustered is not Euclidean. Formal context is the data model in Formal Concept Analysis, the area in data analysis where mathematically rigorous methods from lattice theory have been applied for discovering relationships on heterogeneous data. Taking into account the efect of data heterogeneity in cluster analysis can be efectively implemented using multimodal clustering methods. The paper contains main definitions from Formal Concept Analysis, description the principle of evolutionary computation and evolutionary approach to multimodal clustering. Experimental study of proposed approach is performed on the task of phenotyping of disease of myocardial infarction.
One of the features of the data used in the area of data intensive processing is heterogeneity. Accordingly, in the methods of intensive data processing, it is necessary to take into account their heterogeneity, which makes it possible to preserve knowledge presented in data sets obtained on domains of diferent nature.
There are a lot of works, for example [
Multimodal clustering involves not one, but several sets of objects to be clustered simultaneously. Such sets can be formed by heterogeneous data. A multimodal cluster is a subset in the form of combinations of objects from different sets. The very fact of the combination of certain objects in a multimodal cluster can carry important information and serve as the basis for clusters interpretation.
The simplest variant of multimodal clustering is biclustering, which was first
proposed in [
Biclustering data in the form of an object-attribute representation is also
used in Formal Concept Analysis (FCA) [
Triclustering is a generalization of biclustering [
The generalization of the approach based on the construction of concept
lattices to the n-dimensional case of multimodal clustering is presented in [
Evolutionary computation has been applied in clustering [
The rest of the paper is organized as follows. In Section 2, there is brief description of multimodal clustering on formal contexts. It contains main definitions from FCA and explanation why triclustering is not scalable biclustering. Section 3 contains the description of the main contribution of this paper as evolutionary algorithm of multimodal clustering on formal contexts. In the Section 4, the results of experimental study of proposed approach are presented. They are illustrated on the task of phenotyping of disease of myocardial infarction. 2
Multimodal Clustering on Formal Contexts
We perceive multimodal clustering on formal context which is the data model
in FCA. That is why we brieyfl consider the main issues of the FCA [
A′ := {m ∈ M | < g, m > I ∈ for all g ∈ A} B′ := {g ∈ G| < g, m > I ∈ for all m ∈ B} (1) then the pair (A, B) that A′ = B, B′ = A is named as formal concept. The composition of mappings demonstrates following properties of A and B: (A, B) that A′′ = B, B′′ = A; A and B is called the extent and the intent of a formal context K = (G, M, I) respectively.
By other words, a formal concept is a pair (A, B) of subsets of objects and attributes which are connected so that every object in A has every attribute in B, for every object in G that is not in A, there is an attribute in B that the object does not have and for every attribute in M that is not in B, there is an object in A that does not have that attribute.
If for formal concepts (A1, B1) and (A2, B2), A1 ⊑ A2 and B2 ⊑ B1 then (A1, B1) ≤ (A2, B2) and formal concept (A1, B1) is less general than (A2, B2).This order is represented by concept lattice. A lattice consists of a partially ordered set in which every two elements have a unique supremum (also called a least upper bound or join) and a unique infimum (also called a greatest lower bound or meet).
In the concept lattice, formal concepts are hierarchically grouped together according to their common attributes. Such grouping of objects is really bicluclustering of them i.e. clustering on the two sets simultaneously, the set of objects and the set of attributes.
Example 1. Consider an example of a formal context and the concept lattice built on it. In the Fig. 1 a) a fragment of the data contained in the myocardial infarction database is shown in the form of a two-dimensional binary context. The context has 7 objects and 4 binary attributes. The objects are patient IDs, and the meaning of the attributes is as follows: •gb is the presence of an essential hypertension of a patient; •ant im is the presence of an anterior myocardial infarction (left ventricular); •im pg p is the presence of a right ventricular myocardial infarction; •let is is the lethal outcome of a patient.
The concept lattice built on the considered formal context is shown on the Fig.
1 b). It has seven formal concepts including top and bottom ones which are
unit and zero elements of an abstract lattice correspondingly. Information about
patients is contained in five formal concepts, shown as filled circles. It is used so
called reduced labeling [
In this example, all the patients have anterior myocardial infarction. According with reduced labeling, we can see in the lattice that ant im attribute is presented in all vfie filled concepts. Among patients, those ones with IDs 1500,1503 and 1655 have the lethal outcome. On the left in the lattice there is a separate path with the nodes as the following formal concepts:
({1500, 1503, 1655}, {ant im, let is}), (1655, {ant im, let is, gb}). The first concept is more general than the second, since it is located above it. The first concept reflects two facts: the presence of a myocardial infarction and a lethal outcome for all of three patients. The second concept reflects the peculiarity of patient 1655: he is the only one of the three who has essential hypertension.
Thus, the formal context and concept lattice are a visual tool for representing knowledge. 2.1
Multidimensional or polyadic formal contexts arise as generalization of usual formal contexts. A multidimensional, n-ary formal context is defined by a relation R ⊆ D1 × D2 × . . . × Dn on data domains D1, D2, . . . , Dn. The context is an n+1 set:
K =< K1, K2, . . . , Kn, R >,
(2)
where Ki ⊆ Di. Every n-ary context begets k -ary contexts, whose number is
k
given by the Stirling formula [
According to multimodal clustering, for any dimension of formal context, the
purpose of its processing is to find n-sets H = < X1, X2, . . . , Xn > which have
the closure property [
In the Formal Concept Analysis, biclustering algorithms have been
developed in suficient detail [
The simplest multidimensional formal context is a triadic context (tricontext) of the form T = (G, M, B, I), where B is a set specifying the conditions for the belonging of attributes to objects, I ⊆ G × M × B is a ternary relation. Accordingly, the ternary concepts (triconcepts) are defined as triplets of the form: (C1, C2, C3), C1 ⊆
G, C2 ⊆
M, C3 ⊆
B, (4) with corresponding closure conditions for prime operators. Prime operators have several other implementations here: (5) (6) (7) (8) m′ = {(g, b)|(g, m, b) ∈ I} g′ = {(m, b)|(g, m, b) ∈ I} b′ = {(g, m)|(g, m, b) ∈ I} as well as the corresponding double prime operators: m′′ = { m∼ |(g, b) ∈ m′ T(g, m∼, b) ∈ I} g′′ = {∼g |(m, b) ∈ g′ T(∼g , m, b) ∈ I} b′′ = {∼ b |(g, m) ∈ b′ T(g, m, ∼ b ) ∈ I}
If formal context T is represented by a three dimensional tensor, then a triconcept is a 3-dimensional rectangle full of crosses.
Although there are several recognized algorithms for constructing
threedimensional formal concepts, for example, the Data-Peeler algorithm [
If C = (X, Y, Z), X ⊆ K1, Y ⊆ K2, Z ⊆ K3 is a cluster then its density is defined as d(C) = |I ∩ (X × Y × Z)|
v(C) v(C) = |X| × |Y | × |Z | where cluster volume is
Example 2. A three-dimensional formal context can be built on the data
from the infarct database presented in the Example 1. The use of drugs on
certain days of hospitality may be a third dimension in the context. The standard
maximum treatment time for myocardial infarction is 21 days (at least in Russia),
which defines the scale of the third dimension. Fig. 2 shows a regular
threedimensional cluster built on the context from the Example 1 with additional
attributes. It is built with our evolutionary modeling framework [
The cluster on the Fig. 2 is not dense. This means that not all combinations of elements from the three subsets of the cluster take place. The “informativeness” of multidimensional clusters depends on their density, but not absolutely.
In this example, we are not sure that the Ticlid was applied to these three patients only on these days, but the fact contained in this cluster may be of interest to cardiologists. “Absolutely reliable” facts have been contained in absolutely dense clusters, which are formal concepts. However, special facts that fall out of the general regularities can also be found in loose clusters. As for this example, this subset of patients may not form absolutely dense clusters and the facts should be searched for in low-density clusters by their additional analysis.
Evolutionary methods make it possible to simulate the clustering process in such a way that they allow to investigate the density distributions across clusters and thereby have a detailed picture of clustering. 3
Evolutionary Approach to Multimodal Clustering
Evolutionary Approach to Multimodal Clustering is based on Evolutionary
Computation [
Let X is a set of solutions of a problem. Every solution x ∈ X can be characterized by a quality measure named as fitness function f(x). This measure, in general, is a mapping f : X → Y where Y ⊆ R is the subset of a set of real numbers. This is basis for existence many variations of fitness functions which for example characterize configuration of clusters.
Let solutions of a problem depend on a set of parameters P . Most problems which have been solved by using Evolutionary Computation can be formulated as the following optimization problem: it is required to find optimal values of parameters p∗ which deliver maximum fitness value y∗ ∈ Y, so the following is true: p∗ = argmaxp∗ ∈P f(x) (9) Evolutionary approach to solving this problem consists in the following.
Building encoding scheme. Encoding scheme is the mapping φ : P → S
where set S contains objects which encode parameters from P. Genetic
algorithms [
Evolutionary algorithm. For given encoding scheme the following algorithm solves the problem (7).
A. Randomly generate an initial set (population) S0 of objects from S.
B. Start evolution of the populations by applying a set of operators A to population S0 and further iteratively so that for every Sk+1 = A(Sk) exists at least one f[φ−1 (Sk+1)] ≥ f[φ−1 (Sk)], (10) where sk ∈ Sk and sk+1 ∈ Sk+1.
C. Finish the evolution of the population in accordance with the stopping criterion. Most often, the criterion for stopping is the immutability of the iftness function values over several steps of evolution.
If the set of operators A consists of genetic operators of selection, mutation
and recombination (crossover) then evolutionary algorithm is named as genetic
algorithm [
Selection works so that condition (10) is supported by the following “biological” principle: good parents produce good ofspring (that is not true in Nature). So the higher fitness chromosomes have more opportunity to be selected than the lower ones and good solution is always alive in the next generation.
Crossover is the genetic operator that mixes two chromosomes together to form a new ofspring. It does mixing by replacing fragments of chromosome’s code divided in certain one or several randomly selected points.
MutationMutation involves modification of the gene values by randomly selecting new value from the alphabet at random point in the strings of genes.
Being realized, the algorithm (A. – C.) provides fairly accurate solution of the problem (9).
Fairly accurate means that evolutionary algorithm stops in a neighbourhood of global extreme of fitness function f. The size of a neighbourhood around extreme depends on the fitness function and parameters of genetic operators. When evolutionary algorithm works too fast it may stop at local extreme. This feature is traditionally considered as the lack of the algorithm but it may be useful for clustering since local extreme of quality measure may be “semantically better” than global extreme because it may correspond to the cluster containing an interesting fact. In our experiments we have observed just that situations. 3.2
Here we outline our solution to applying evolutionary computation to clustering in multidimensional contexts.
There are two crucial parameters of clustering problem: a measure of
similarity of clustering objects (proximity measure) and number of clusters – is
it given or not before clustering. Evolutionary algorithms have advantage over
traditional clustering methods when:
1. measure of similarity of clustering objects is not traditional (Euclidian norm)
[
Consider this in more detail.
1. Many clustering algorithms use proximity measures of objects based on
calculating the distances between them. Evolutionary and genetic algorithms
work on the black box principle. The black box inputs are the values of the
parameters P (see previous Section) and at the outputs we get the
corresponding solutions, for which we calculate the values of the fitness function.
A dependence between input and output may be very complex and not
being expressed analytically as traditional proximity measures. For our
experiments, there is no analytical dependence between cluster congfiurations
specified by chromosomes and, for example, cluster densities. Therefore, the
iftness function used in this case does not use the traditional proximity
measure.
2. In evolutionary and genetic algorithms for clustering [
Chromosome encoding. After analyzing the existing variants of
chromosome encoding [
Fitness function. As in FCA, we control cluster density (7), its volume (8)
and special kind of interestingness. There is the trade-of problem between the
density and the volume of triclusters [
For the binary encoding scheme, fitness function has the form: where α i is user defined coeficient, which in general depends on cluster density, N is the number of chromosomes in population which is equal to the maximal number of clusters.
For the chained integer-encoding scheme fitness function is the following: f(d) = 1 N
X α id(Ci),
N i=1 f(d) = 1 XN 1 XKj α id(Ci), N j=1 Kj i=1 (11) (12) where Kj is the number of clusters in the j-th chromosome.
Interestingness of a clusters. In a genetic algorithm, the whole fitness of population hides the features of individual chromosomes. But if selection leaves chromosomes with maximum fitness, then there is a chance that they will lead evolution to good solutions. Patient ID values found in clusters, other attributes corresponding to them from the “treatment” and “treatment outcomes” domains are evaluated for the presence of information in them that can be treated as facts. The formal criteria for selecting such “interesting” clusters are the following.
A single cluster. The presence of a single cluster at the end of evolution
means that the algorithm most likely stopped at the global extremum of a fitness
function [
Dense clusters. The densest clusters among the received are very important since the information they contain may be certainly treated as facts.
Clusters of the maximum volume are interesting if they are dense enough. A large number of objects from diferent domains in the cluster is a sign that some pattern occurs on the data.
Clusters with given values of density and volume are interesting when density or volume values are specified in relation to some other characteristics of the clustering task. 4
4.1
Experimental studies of the proposed approach were carried out in order to
test the performance of the genetic algorithm under various parameters and for
checking the possibility of interpreting clustering results as facts.
We use Myocardial Infarction Complications Data Set [
Based on the data of myocardial infarction, the task of phenotyping this disease was solved. Phenotyping refers to the determination of the form of the disease based on the clinical profile. A clinical profile is a cluster that can include various data describing both the disease itself and the methods of its treatment, as well as the conditions of patients. Therefore, we were interested in various triples of attribute sets from the domains ”patient”, ”treatment”, ”treatment results”. 4.3
In the experiments, we investigated, first of all, the efectiveness of various options for implementing the evolutionary clustering algorithm, as well as its performance.
Diversity in clusters. To ensure diversity in clusters, we used large values of mutation probability. The graph in Fig. 3 shows that when a certain threshold value of the mutation probability is reached, the number of clusters increases sharply and remains unchanged with an increase in the mutation probability. In this case, the algorithm found 30 local extrema of the fitness function. 33 24 19 6 27 14 123 .
Scaling algorithm performance. The algorithm processes very long threesection chromosomes of about 2000 genes fairly quickly. To investigate algorithm performance we have constructed seven formal contexts acquired from the whole set which number of objects and attributes are shown in Table 1 where ECG is electrocardiogram.
Fig. 4 shows clustering execution time for each of the seven contexts. The graph on this figure shows that the cluster construction time depends quasilinearly on the amount of data.
Anamnesis
Analyzes
ECG Therapy results
Full data 1700 1700 1700 1700 1700 1700 1700
Fig. 4: Clustering execution time for several formal contexts.
Conflicting criteria. As we expected the criteria for maximizing the volume and density of clusters contradict each other. In the graphs on Figure 5 it is shown that the volume (graph a) and density (graph b) of clusters synchronously change during evolution.
a) b)
Fig. 5: Efect of the mutation probability value on the number of clusters. The combination of cluster density and volume in a single tfiness function masks certain relationships between attributes in clustering results. Therefore, here we make a principal conclusion that it is necessary to apply two optimization criteria in this clustering task with genetic algorithm.
Comparison with Data-Peeler. We were also interested in absolutely
dense clusters, the formal concepts. As expected, there were few such clusters,
which follows from the sparsity of myocardial data. To compare our results with
well known another algorithm, we selected Data-Peeler [
The results in the last row of Table 2 can be explained by the high sparsity of data in this formal context. Accordingly, the Data-Peeler algorithm has built a lot of small concepts. We were interested in special clusters. First of all, these are clusters with large groups of patients characterized by certain combinations of attributes from the domains ”patient”, ”treatment”, ”treatment results”. Several such groups were obtained. 1. We have found that the lethal outcome of myocardial infarction is inherent in elderly patients over 60 years of age. This fact is consistent with the known data of cardiology. 2. In more detail, cases of heart attack in the anamnesis correlate with a fatal outcome, which also looks natural.
For both this groups of patients, we found absolutely dense clusters built on tensors with age and anamnesis attributes.
Unexpected result. We have found one unexpected result, which is as follows. On the data of myocardial infarction, there are stable (not changing according with diferent parameters of the genetic algorithm) and rather dense clusters in which a subgroup of patients with a lethal outcome have not got certain drugs. At the same time, patients with a non-lethal outcome had these drugs. 5
This paper proposes an approach to multimodal clustering on multidimensional formal contexts using evolutionary computation. This approach has been shown to be efective in experiments on clustering three-dimensional formal contexts based on data of patients with myocardial infarction.
The presented experimental results reflect the initial stage of research in this area. In the future, it is planned to do the following. 1. Evaluate the informativeness of the obtained clusters not manually, but using a user interface focused on doctors. 2. Experiments have confirmed that the criteria of cluster density and volume contradict each other. Therefore, it is necessary to apply multi-objective evolutionary clustering with appropriate algorithms. 3. Transition to the dimension of formal contexts greater than three. Separate groups of parameters can be represented as dimensions. Then their combinations obtained in clusters will reflect in more detail the relationships in heterogeneous data.
Acknowledgments. The reported study was funded by Russian Foundation of Basic Research, the research projects № 19-07-01178, № 20-07-00055 and RFBR and Tula Region according to research project № 19-47-710007.