A Clustering Method Based on the Maximum Entropy Principle

Abstract

Clustering is an unsupervised process to determine which unlabeled objects in a set share interesting properties. The objects are grouped into k subsets (clusters) whose elements optimize a proximity measure. Methods based on information theory have proven to be feasible alternatives. They are based on the assumption that a cluster is one subset with the minimal possible degree of “disorder”. They attempt to minimize the entropy of each cluster. We propose a clustering method based on the maximum entropy principle. Such a method explores the space of all possible probability distributions of the data to find one that maximizes the entropy subject to extra conditions based on prior information about the clusters. The prior information is based on the assumption that the elements of a cluster are “similar” to each other in accordance with some statistical measure. As a consequence of such a principle, those distributions of high entropy that satisfy the conditions are favored over others. Searching the space to find the optimal distribution of object in the clusters represents a hard combinatorial problem, which disallows the use of traditional optimization techniques. Genetic algorithms are a good alternative to solve this problem. We benchmark our method relative to the best theoretical performance, which is given by the Bayes classifier when data are normally distributed, and a multilayer perceptron network, which offers the best practical performance when data are not normal. In general, a supervised classification method will outperform a non-supervised one, since, in the first case, the elements of the classes are known a priori. In what follows, we show that our method’s effectiveness is comparable to a supervised one. This clearly exhibits the superiority of our method.

1. Introduction

Pattern recognition is a scientific discipline whose methods allow us to describe and classify objects. The descriptive process involves the symbolic representation of these objects through a numerical vector $\overrightarrow{x}$:

$$\overrightarrow{x}=[x_1,x_2,\dots x_n]\in {\Re }^n$$

(1)

where its n components represent the value of the attributes of such objects. Given a set of objects (“dataset”) X, there are two approaches to attempt the classification: (1) supervised; and (2) unsupervised.

In the unsupervised approach case, no prior class information is used. Such an approach aims at finding a hypothesis about the structure of X based only on the similarity relationships among its elements. These relationships allow us to divide the space of X into k subsets, called clusters. A cluster is a collection of elements of X, which are “similar” between them and “dissimilar” to the elements belonging to other clusters. Usually, the similarity is defined by a metric or distance function d: X × X → ℜ [1–3]. The process to find the appropriate clusters is typically denoted as a clustering method.

1.1. Clustering Methods

In the literature, many clustering methods have been proposed [4,5]. Most of them begin by defining a set of k centroids (one for each cluster) and associating each element in X with the nearest centroid based on a distance d. This process is repeated, until the difference between centroids at iteration t and iteration t − 1 tends to zero or when some other optimality criterion is satisfied. Examples of this approach are k-means [6] and fuzzy c-means [7–9]. Other methods not following the previous approach are: (1) hierarchical clustering methods that produce a tree or a graph in which, during the clustering process, based on some similarity measure, the nodes (which represent a possible cluster) are merged or split; in addition to the distance measure, we must also have a stopping criterion to tell us whether the distance measure is sufficient to split a node or to merge two existing nodes [10–12]; (2) density clustering methods, which consider clusters as dense regions of objects in the dataset that are separated by regions of low density; they assume an implicit, optimal number of clusters and make no restrictions with respect to the form or size of the distribution [13]; and (3) meta-heuristic clustering methods that handle the clustering problem as a general optimization problem; these imply a greater flexibility of optimization algorithms, but also longer execution times [14,15].

We propose a numerical clustering method that lies in the group of meta-heuristic clustering methods, where the optimization criterion is based on information theory. Some methods with similar approaches have been proposed in the literature (see Section 1.6).

1.2. Determining the Optimal Value of k

In most clustering methods, the number k of clusters must be explicitly specified. Choosing an appropriate value has important effects on the clustering results. An adequate selection of k should consider the shape and density of the clusters desired. Although there is not a generally accepted approach to this problem, many methods attempting to solve it have been proposed [5,16,17]. In some clustering methods (such as hierarchical and density clustering), there is no need to explicitly specify k. Implicitly, its value is, nevertheless, still required: the cardinality or density of the clusters must be given. Hence, there is always the need to select a value of k. In what follows, we assume that the value of k is given a priori. We do not consider the problem of finding the optimal value of k. See, for example, [18–20].

1.3. Evaluating the Clustering Process

Given a dataset X to be clustered and a value of k, the most natural way to find the clusters is to determine the similarity among the elements of X. As mentioned, usually, such similarity is established in terms of proximity through a metric or distance function. In the literature, there are many metrics [21] that allow us to find a variety of clustering solutions. The problem is how to determine if a certain solution is good or not. For instance, in Figures 1 and 2, we can see two datasets clustered with k = 2. For such datasets, there are several possible solutions, as shown in Figures 1b,c and 2b,c, respectively.

Frequently, the goodness of a clustering solution is quantified through validity indices [4,8,22,23]. The indices in the literature are classified into three categories: (1) external indices that are used to measure the extent to which cluster labels match externally-supplied class labels (F-measure [24], NMIMeasure [25], entropy [26], purity [27]); (2) internal indices, which are used to measure the goodness of a clustering structure with respect to the intrinsic information of the dataset ([8,28–31]); and (3) relative indices that are used to compare two different clustering solutions or particular clusters (the RAND index [32] and adjusted RAND index [33]).

Clusters are found and then assigned a validity index. We bypass the problem of qualifying the clusters and, rather, define a quality measure and then find the clusters that optimize it. This allows us to define the clustering process as follows:

Definition 1. Given a dataset X to be clustered and a value of k, clustering is a process that allows the partition of the space of X into k regions, such that the elements that belong to them optimize a validity index q.

Let C_i be a partition of X and Π = {C₁, C₂, …C_k} the set of such partitions that represents a possible clustering solution of X. We can define a validity index q as a function of the partition set Π, such that the clustering problem may be reduced to an optimization problem of the form:

$$\begin{array}{l}\mathit{\text{Optimize q}}=f(\mathrm{\Pi })\\ \text{subject to}:g_i(\mathrm{\Pi })\le 0,i=1,2\dots ,m\\ h_j(\mathrm{\Pi })=0,j=1,2,\dots ,p\end{array}$$

(2)

where g_i and h_j are constraints, likely based on prior information about the partition set Π (e.g., the desired properties of the clusters).

We want to explore the space of those feasible partition sets and find one that optimizes a validity index instead, doing an a posteriori evaluation of a partition set (obtained by any optimization criterion) through such an index. This approach allows us to find “the best clustering” within the limits of a validity index. To tightly confirm such an assertion, we resort to the statistical evaluation of our method (see Section 5).

1.4. Finding the Best Partition of X

Finding the suitable partition set Π of X is a difficult problem. The total number of different partition sets of the form Π = {C₁, C₂, …C_k} may be expressed by the function S(N, k) associated with the Stirling number of the second kind [34], which is given by:

$$S(N,k)=\frac{1}{k!}{\displaystyle \sum _{i=0}^k{(-1)}^{k-i}}\left({}_i^k\right)i^N$$

(3)

where N = |X|. For instance, for N = 50 and k = 2, S(N, k) ≈ 5.63 × 10¹⁴. This number illustrates the complexity of the problem that we need to solve. Therefore, it is necessary to resort to a method that allows us to explore efficiently a large solution space. In the following section, we briefly describe some meta-heuristic searches.

1.5. Choosing the Meta-Heuristic

During the last few decades, there has been a tendency to consider computationally-intensive methods that can search very large spaces of candidate solutions. Among the many methods that have arisen, we mention tabu search [35–37], simulated annealing [38,39], ant colony optimization [40], particle swarm optimization [41] and evolutionary computation [42]. Furthermore, among the many variations of evolutionary computation, we find evolutionary strategies [43], evolutionary programming [44], genetic programming [45] and genetic algorithms (GAs) [46]. All of these methods are used to find approximate solutions for complex optimization problems. It was proven that an elitist GA always converges to the global optimum [47]. Such a convergence, however, is not bounded in time, and the selection of the GA variation with the best dynamic behavior is very convenient. In this regard, we rely on the conclusions of previous analyses [48,49], which showed that a breed of GA, called the eclectic genetic algorithm (EGA), achieves the best relative performance. Such an algorithm incorporates the following:

• Full elitism over a set of size n of the last population. Given that, by generation t, the number of individual tested is nt, the population in such a generation consists of the best n individuals.
• Deterministic selection as opposed to the traditional proportional selection operator. Such a scheme emphasizes genetic variety by imposing a strategy that enforces the crossover of predefined individuals. After sorting the individual’s fitness from better to worse, the i-th individual is combined with the (n − i + 1)-th individual.
• Annular (two-point) crossover.
• Random mutation of a percentage of bits of the population.

In Appendix A, we present the pseudocode of EGA. The reader can find detailed information in [48–51].

1.6. Related Works

Our method is meta-heuristic (see Section 1.1). The main idea behind our method is to handle the clustering problem as a general optimization problem. There are various suitable meta-heuristic clustering methods. For instance, in [52–54], three different clustering methods based on differential evolution, ant colony and multi-objective programming, respectively, are proposed.

Both meta-heuristic or analytical methods (iterative, density-based, hierarchical) have objective functions, which are associated with a metric. In our method, the validity index becomes the objective function.

Our objective function is based on information theory. Several methods based on the optimization of information theoretical functions have been studied [55–60]. Typically, they optimize quantities, such as entropy [26] and mutual information [61]. These quantities involve determining the probability distribution of the dataset in a non-parametric approach, which does not make assumptions about a particular probability distribution. The term non-parametric does not imply that such methods completely lack parameters; they aim to keep the number of assumptions as weak as possible (see [57,60]). Non-parametric approaches involve density functions, conditional density functions, regression functions or quantile functions in order to find the suitable distribution. Typically, such functions imply tuning parameters that determine the convergence of searching for the optimal distribution.

A common clustering method based on information theory is ENCLUS (entropy clustering) [62], which allows us to split iteratively the space of the dataset X in order to find those subspaces that minimize the entropy. The method is motivated by the fact that a subspace with clusters typically has lower entropy than a subspace without clusters. In order to split the space of X, the value of a resolution parameter must be defined. If such a value is too large, the method may not able to capture the differences in entropy in different regions in the space.

Our proposal differs from traditional clustering methods (those based on minimizing a proximity measure as k-means or fuzzy c-means) in that, instead of finding those clusters that optimize such a measure and then defining a validity index to evaluate its quality, our method finds the clusters that optimize a purported validity index.

As mentioned, such a validity index is an information theoretical function. In this sense, our method is similar to those mentioned methods based on information theory. However, it does not use explicitly a non-parametric approach to find the distribution of the dataset. It explores the space of all possible probability distributions to find one that optimizes our validity index. For this reason, the use of a suitable meta-heuristic is compulsory. With the exception of the parameters of such a meta-heuristic, our method does not resort to additional parameters to find the optimal distribution and, consequently, the optimal clustering solution.

Our validity index involves entropy. Usually in the methods based on information theory, the entropy is interpreted as a “disorder” measure; thus, an obvious way is to minimize such a measure. In our work, we propose to maximize it due to the maximum entropy principle.

1.7. Organization of the Paper

The rest of this work is organized as follows: In Section 2, we briefly discuss the concept of information content, entropy and the maximum entropy principle. Then, we approach such issues in the context of the clustering problem. In Section 3, we formalize the underlying ideas and describe the main line of our method (in what follows, clustering based on entropy (CBE)). In Section 4, we present a general description of the datasets. Such datasets were grouped into three categories: (1) synthetic Gaussian datasets; (2) synthetic non-Gaussian datasets; and (3) experimental datasets taken from the UCIdatabase repository. In Section 5, we present the methodology to evaluate the effectiveness of CBE regardless of a validity index. In Section 6, we show the experimental results. We use synthetically-generated Gaussian datasets and apply a Bayes classifier (BC) [63–65]. We use the results as a standard for comparison due to its optimal behavior. Next, we consider synthetic non-Gaussian datasets. We prove that CBE yields results comparable to those obtained by a multilayer perceptron network (MLP). We show that our (non-supervised) method’s results are comparable to those of BC and MLP, even though these are supervised. The results of other clustering methods are also presented, including an information theoretic-based method (ENCLUS). Finally, in Section 7, we present our conclusions. We have included three appendices expounding important details.

2. Maximum Entropy Principle and Clustering

The so-called entropy [26] appeals to an evaluation of the information content of a random variable Y with possible values {y₁, y₂, …y_n}. From a statistical viewpoint, the information of the event (Y = y_i) is inversely proportional to its likelihood. This information is denoted by I(y_i), which can be expressed as:

$$I(y_i)=\mathit{log}\left(\frac{1}{p(y_i)}\right)=-\mathit{log}(p(y_i))$$

(4)

From information theory [26,66], the entropy of Y is the expected value of I. It is given by:

$$H(Y)=-{\displaystyle \sum _{i=1}^{N}p(y_i)\mathit{log}(p(y_i))}$$

(5)

Typically, the log function may be taken to be log₂, and then, the entropy is expressed in bits; otherwise, as ln, in which case the entropy is in nats. We will use log₂ for the computations in this paper.

When p(y_i) is uniformly distributed, the entropy of Y is maximal. This means that Y has the highest level of unpredictability and, thus, the maximal information content. Since entropy reflects the amount of “disorder” of a system, many methods employ some form of such a measure in the objective function of clustering. It is expected that each cluster has a low entropy, because data points in the same cluster should look similar [56–60].

We consider a stochastic system with a set of states S = {Π₁, Π₂, …, Π_n} whose probabilities are unknown (recall that Π_i is a likely partition set of X of the form Π = {C₁, C₂, …, C_k}). A possible assertion would be that the probabilities of all states are equal (p(Π₁) = p(Π₂) = … = p(Π_n−1) = p(Π_n)), and therefore, the system has the maximum entropy. However, if we have additional knowledge, then we should be able to find a probability distribution that is better in the sense that it is less uncertain. This knowledge can consist of certain average values or bounds on the probability distribution of the states, which somehow define several conditions imposed upon such distribution. Usually, there is an infinite number of probability models that satisfies these conditions.

The question is: which model should we choose? The answer lies in the maximum entropy principle, which may be stated as follows [67]: when an inference is made on the basis of incomplete information, it should be drawn from the probability distribution that maximizes the entropy, subject to the constraints on the distribution. As mentioned, a condition is an expected value of some measure about the probability distributions. Such a measure is one for which each of the states of the system has a value denoted by g(Π_i).

For example, let X = {9, 10, 9, 2, 1} be a discrete dataset to be clustered with k = 2. We assume that the “optimal” labeling of the dataset is the one that is shown in

Table 1. Unidimensional dataset.

X	C
9	C1
10	C1
9	C1
2	C2
1	C2

.

Such labeling defines a partition Π* of the form Π* = {C₁ = {9, 10, 9}, C₂ = {2, 1}}. The probability model of Π* is given by the conditional probabilities p(x|C_i) that represent the likelihood that, when observing cluster C_i, we can find object x.

Table 2. Probability model of Π*.

X	C	p(x|C1)	p(x|C2)
9	C1	0.333	0.000
10	C1	0.333	0.000
11	C1	0.333	0.000
2	C2	0.000	0.500
1	C2	0.000	0.500

shows such probabilities.

The entropy of X conditioned on the random variable C taking a certain value C_i is denoted as H(X|C = C_i). Thus, we define the total entropy of Π* as:

$$\begin{array}{l}H(\mathrm{\Pi }*)={\displaystyle \sum _{C_i\in \mathrm{\Pi }*}H(X|C=C_i)}\\ H(\mathrm{\Pi }*)=-{\displaystyle \sum _{C_i\in \mathrm{\Pi }*}{\displaystyle \sum _{x\in C_i}p(x|C_i)\mathit{log}(p(x|C_i))}}\end{array}$$

(6)

Given the probability model of Π* and Equation (6), the total entropy of Π* is shown in

Table 3. Probability model and the entropy of Π*.

X	C	p(x|C1)	p(x|C2)	p(x|C1)log (p(x|C1))	p(x|C2)log (p(x|C2))
9	C1	0.333	0.000	−0.528	0.000
10	C1	0.333	0.000	−0.528	0.000
11	C1	0.333	0.000	−0.528	0.000
2	C2	0.000	0.500	0.000	−0.500
1	C2	0.000	0.500	0.000	−0.500
				H(Π*)	2.584
				g(Π*)	1.316

. We may also calculate the mean and the standard deviation of the elements x ∈ C_i denoted as σ(C_i) in order to define a quality index:

$$g(\mathrm{\Pi }*)={\displaystyle \sum _{i=1}^2\sigma (C_i)}$$

(7)

Alternative partition sets are shown in

Table 4. Probability model and entropy of Π₁.

X	C	p(x|C1)	p(x|C2)	p(x|C1)log (p(x|C1))	p(x|C2)log (p(x|C2))
9	C1	0.250	0.000	−0.500	0.000
10	C1	0.250	0.000	−0.500	0.000
11	C1	0.250	0.000	−0.500	0.000
2	C2	0.000	1.000	0.000	0.000
1	C1	0.250	0.000	−0.500	0.000
				H(Π1)	2.000
				g(Π1)	3.960

and

Table 5. Probability model and entropy of Π₂.

X	C	p(x|C1)	p(x|C2)	p(x|C1)log (p(x|C1))	p(x|C2)log (p(x|C2))
9	C2	0.000	0.333	0.000	−0.528
10	C1	0.500	0.000	−0.500	0.000
11	C1	0.500	0.000	−0.500	0.000
2	C2	0.000	0.333	0.000	−0.528
1	C2	0.000	0.333	0.000	−0.528
				H(Π2)	2.584
				g(Π2)	4.059

.

In terms of maximum entropy, partition H(Π₂) is better than H(Π₁). Indeed, we can say that H(Π₂) is as good as H(Π^*). If we assume that a cluster is a partition with the minimum standard deviation, then the partition set Π^* is the best possible solution of the clustering problem. In this case, the minimum standard deviation represents a condition that may guide the search for the best solution. We may consider any other set of conditions depending on the desired properties of the clusters. The best solution will be the one with the maximum entropy, which complies with the selected conditions.

In the example above, we knew the labels of the optimal class and the problem became trivial. In the clustering problems, there are no such labels, and thus, it is compulsory to find the optimal solution based solely on the prior information supplied by one or more conditions. We are facing an optimization problem of the form:

$$\begin{array}{l}\text{Maximize}:H(\mathrm{\Pi })\\ \text{subject to}:g_1(\mathrm{\Pi })\le {ϵ}_1\\ g_2(\mathrm{\Pi })\le {ϵ}_2\\ ⋮\\ g_n(\mathrm{\Pi })\le {ϵ}_n\\ \mathrm{\Pi }\in S\end{array}$$

(8)

where ϵ_i is the upper bound of value of the i-th condition. We do not know the value of ϵ_i, and thus, we do not have enough elements to determine compliant values of g_i. Based on prior knowledge, we infer whether the value of g_i is required to be as small (or large) as possible. In our example, we postulated that g_i(Π) (based on the standard deviation of the clusters) should be as small as possible. Here, g_i(Π) becomes an optimization condition. Thus, we can redefine the above problem as:

$$\begin{array}{l}\mathrm{Optimize}:(H(\mathrm{\Pi }),g_1(\mathrm{\Pi }),g_2(\mathrm{\Pi }),\dots ,g_n(\mathrm{\Pi }))\\ \text{subject to}:\mathrm{\Pi }\in S\end{array}$$

(9)

which is a multi-objective optimization problem [68].

Without loss of generality, we can reduce the problem in Equation (9) to one of maximizing the entropy and minimizing the sum of the standard deviation of the clusters (for practical purposes, we choose the standard deviation; however, we may consider any other statistics, even higher-order statistics). The resulting optimization problem is given by:

$$\begin{array}{l}\mathrm{Maximize}:H(\mathrm{\Pi })^\mathrm{Minimize}:g(\mathrm{\Pi }))\\ \text{subject to}:\mathrm{\Pi }\in S\end{array}$$

(10)

where g(Π) is the sum of the standard deviation of the clusters. In a n-dimensional space, the standard deviation of the cluster C_i is a vector of the form $\overrightarrow{\sigma }=({\sigma }_1,{\sigma }_2,{\sigma }_n)$, where σ_j is the standard deviation of each dimension of the objects $\overrightarrow{x}\in C_i$. In general, we calculate the standard deviation of a cluster as:

$$\sigma (C_i)={\displaystyle \sum _{j=1}^n{\sigma }_i\forall {\sigma }_j\in \overrightarrow{\sigma }}$$

(11)

Then, we define the corresponding g(Π) as:

$$g(\mathrm{\Pi })={\displaystyle \sum _{i=1}^k\sigma (C_i)}$$

(12)

The entropy of the partition set Π denoted by H(Π) is given by Equation (6).

The problem of Equation (10) is intractable via classical optimization methods [69,70]. The challenge is to simultaneously optimize all of the objectives. The tradeoff point is a Pareto-optimal solution [71]. Genetic algorithms are popular tools used to search for Pareto-optimal solutions [72,73].

3. Solving the Problem through EGA

Most multi-objective optimization algorithms use the concept of dominance in their search to find a Pareto-optimal solution. For each objective function, there exists one different optimal solution. An objective vector constructed with these individual optimal objective values constitutes the ideal objective vector of the form:

$$z^{*}=(f_1^{*},f_2^{*},\dots ,f_n^{*})$$

(13)

where $f_i^{*}$ is the i-th objective function. Given two vectors z and w, it is said that z dominates w, if each component of z is less or equal to the corresponding component of w, and at least one component is smaller:

$$z\underset{¯}{\succ }w\leftrightarrow \forall i(z_i\le w_i)\wedge \exists k(z_k<w_k)$$

(14)

We use EGA to solve the problem of Equation (10).

3.1. Encoding a Clustering Solution

We established that a solution (an individual) is a random sequence of symbols s from the alphabet ∑ = {1, 2, 3…k}. Every symbol in s represents the cluster to which an object $\overrightarrow{x}$ ∈ X belongs. The length of s is given by the cardinality of X. An individual determines a feasible partition set Π of X. This is illustrated in Figure 3.

From this encoding, Π₁ = {C₁ = {x₁, x₅}, C₂ = {x₂, x₃, x₄}} and Π₂ = {C₁ = {x₁, x₃, x₄}, C₂ = {x₂, x₅}}. EGA generates a population of feasible partition sets and evaluates them in accordance with their dominance. Evolution of the population takes place after the repeated application of the genetic operators, as described in [48,49].

3.2. Finding The Probability Distribution of the Elements of a Cluster

Based on the encoding of an individual of EGA, we can determine the elements $\overrightarrow{x}$ that belong to C_i for all i = 1, 2, …, k. To illustrate the way $p(\overrightarrow{x}|C_1)$ is calculated, we refer to the partition set shown in Figure 4.

The shaded area represents the proportion of $\overrightarrow{x}$, which belongs to cluster C₁. We divide the probability space of cluster C₁ into a fixed number of quantiles (see Figure 5). The conditional proportion of $\overrightarrow{x}$ in C_i is the proportion of the number of objects $\overrightarrow{x}$ in a given quantile.

An unidimensional case is illustrated in Figure 5. This idea may be extended to a multidimensional space, in which case, a quantile is a multidimensional partition of the space of C_i, as is shown in Figure 6. In general, the $p(\overrightarrow{x}|C_i)$ is the density of the quantile to which $\overrightarrow{x}$ belongs in terms of the percentage of data contained in it. We want to obtain quantiles that contain at most 0.0001 percent of the elements. Thus, we divide the space of C_i into 10,000 quantiles.

3.3. Determining the Parameters of CBE

The EGA in CBE was executed with the following parameter values: Pc = 0.90, Pm = 0.09, Population size = 100, Generations = 800. It is based on a preliminary study, which showed that from a statistical view point, EGA converges to the optimal solution around such values when the problems are demanding (those with a non-convex feasible space) [48,49]. The value of k in all experiments is known a priori from the dataset.

4. Datasets

We present a general description of the datasets used in our work. They comprise three categories: (1) synthetic Gaussian datasets; (2) synthetic non-Gaussian datasets; and (3) experimental datasets taken from the UCI database repository, i.e., real-world datasets. Important details about these categories are shown in Appendix B.

4.1. Synthetic Dataset

Supervised clustering is, in general, more effective than an unsupervised one. Knowing this, we make an explicit comparison between a supervised method and our own clustering algorithm. We will show that the performance of our method is comparable to the one of a supervised method. This fact underlines the effectiveness of the proposed clustering algorithm. It is known that, given a dataset X divided into k classes whose elements are drawn from a normal distribution, a BC achieves the best solution relative to other classifiers [65]. Therefore, we will gauge the performance of CBE relative to BC.

Without the normality assumption, we also want to measure the performance of CBE relative to a suitable classifier; in this regard, we use MLP, which has been shown to be effective without making assumptions about the dataset.

Our claim is that if CBE performs satisfactorily when it is compared against a supervised method, it will also perform reasonably well relative to other clustering (non-supervised) methods. In order to prove this, we generated both Gaussian and non-Gaussian synthetic datasets, as described in Appendix B. For each dataset, the class labels were known. They are meant to represent the expected clustering of the dataset. It is very important to stress that CBE is unsupervised, and hence, it does not require the set of class labels.

4.2. Real-World Datasets

Likewise, we also used a suite of datasets that represent “real-world” problems from the UCI repository, also described in Appendix B.3. We used an MLP as practical approximation to the best expected classification of these datasets.

5. Methodology to Gauge the Effectiveness of a Clustering Method

In what follows, we present the methodology to determine the effectiveness of any clustering method (CM). We solve a large set of clustering problems by generating a sufficiently large supply of synthetic datasets. First, the datasets are made to distribute normally. Given the fact that BC will classify optimally when faced with such datasets, we will use them to compare a CM vs. BC. Afterwards, other datasets are generated, but no longer demanded to be Gaussian. We will use these last datasets to compare a CM vs. MLP. In both cases, we are testing the large number of classification problems to ensure that the behavior of a CM, relative to the best supervised algorithm (BC or MLP), will be statistically significant.

With the real-world datasets, the effectiveness of a CM is given by the number matching between cluster labels obtained by such a CM and the a priori class labels of the dataset.

5.1. Determining the Effectiveness Using Synthetic Gaussian Datasets

Given a labeled Gaussian dataset $X_i^{*}(i=1,2,\dots n)$, we use BC to classify $X_i^{*}$. The same set not including the labels will be denoted X_i. The classification yields $Y_i^{*}$, which will be used as the benchmarking reference. We may determine the effectiveness of any CM as follows:

• Obtain a sample $X_i^{*}$.
• Train the BC based on $X_i^{*}$.
• From the trained BC, obtain the “reference” labels for all $\overrightarrow{x^{*}}\in X_i^{*}$ (denoted by $Y_i^{*}$).
• Train the CM with X_i to obtain a clustering solution denoted as Y_i.
• Obtain the percentage of the number of elements of Y_i that match those of $Y_i^{*}$.

5.2. Determining the Effectiveness of Using Synthetic Non-Gaussian Datasets

Given a labeled non-Gaussian dataset $X_i^{*}$ for i = 1, 2, …N, we followed the same exact steps as described in Section 5.1, but we replaced the BC with an MLP. We are assuming (as discussed in [65]) that MLPs are the best practical choice as a classifier when data are not Gaussian.

5.3. Determining the Effectiveness Using Real-World Datasets

With the real-world datasets, the effectiveness of a CM is given by the percentage matching between cluster labels obtained by such a CM and the a priori class labels of the dataset.

5.4. Determining the Statistical Significance of the Effectiveness

We statistically evaluated the effectiveness of any CM using synthetic datasets (both Gaussian and non-Gaussian). In every case, we applied a CM to obtain Y_i. We denote the relative effectiveness as φ. We wrote a computer program that takes the following steps:

• A set of N = 36 datasets is randomly selected.
• Every one of these datasets is used to train a CM and BC or MLP, when data are Gaussian or non-Gaussian, respectively.
• φ_i is recorded for each problem.
• The average of all φ_i is calculated. Such an average is denoted as ${\overline{\phi }}_m$.
• Steps 1–4 are repeated, until the ${\overline{\phi }}_m$ are normally distributed. The mean and standard deviation of the resulting normal distribution are denoted by ${\mu }^{\prime }$ and ${\sigma }^{\prime }$, respectively.

From the central limit theorem, ${\overline{\phi }}_m$ will be normally distributed for appropriate M. Experimentally (see Appendix C), we found that an adequate value of M is given by:

$$M\approx \frac{b-\ln \left[\ln \left(\frac{a}{P}\right)\right]}{c}$$

(15)

where P is the probability that the experimental χ² is less than or equal to 3.28, and there are five or more observations per quantile; a = 0.046213555, b = 12.40231200 and c = 0.195221110. For p ≤ 0.05, from 15, we have that M ≥ 85. In other words, if M ≥ 85, the probability that $\overline{\phi }$ is normally distributed is better that 0.95. Ensuring that $\overline{\phi }~N({\mu }^{\prime },{\sigma }^{\prime })$, we can easily infer the mean μ and the standard deviation σ of the distribution of φ from:

$$\sigma ={\sigma }^{\prime }\sqrt{N}$$

(16)

$$\mu ={\mu }^{\prime }$$

(17)

From Chebyshev’s inequality [74], the probability that the performance of a CM φ lies in the interval [μ − λσ, μ + λσ] is given by:

$$p(\mu -\lambda \sigma \le \phi \le \mu +\lambda \sigma )\ge 1-\frac{1}{{\lambda }^2}$$

(18)

where λ denotes the number of standard deviations. By setting λ = 3.1623, we ensure that the values of φ will lie in this interval with probability p ≈ 0.9. A lower bound on φ (assuming the symmetric distribution of the φs) is given by μ + λσ.

6. Results

In what follows, we show the results from the experimental procedure. We wanted to explore the behavior of our method relative to other clustering methods. We used a method based on information theory called ENCLUS and two other methods: k-means and fuzzy c-means. For all methods, we used the experimental methodology (with Gaussian and non-Gaussian datasets). All methods were made to solve the same problems.

6.1. Synthetic Gaussian Datasets

Table 6. Average effectiveness (φ) for Gaussian datasets.

Algorithm	Disjoint	Overlapping	Concentric
k-means	0.018	0.42	0.52
fuzzy c-means	0.017	0.36	0.51
ENCLUS	0.019	0.04	0.12
CBE	0.020	0.03	0.04
p-value < 0.05

shows the values of φ for Gaussian datasets. Lower values imply better closeness to the results achieved from BC (see Section 5.1). The Gaussian datasets were generated in three different arrangements: disjoint, overlapping and concentric. Figure 7 shows an example of such arrangements.

All four methods yield similar values for disjoint clusters (simple problem). However, important differences are found when tackling the overlapping and concentric datasets (hard problems). We can see that CBE is noticeable better.

Since BC exhibits the best theoretical effectiveness given Gaussian datasets, we have included the percentual behavior of the four methods relative to it in

Table 7. Performance relative to the Bayes classifier (BC) (%).

Algorithm	Disjoint	Overlapping	Concentric
k-means	0.982	0.576	0.475
fuzzy c-means	0.983	0.636	0.485
ENCLUS	0.981	0.960	0.879
CBE	0.980	0.970	0.960
BC	1.000	1.000	1.000
p-value < 0.05

.

6.2. Synthetic Non-Gaussian Datasets

Table 8. Average effectiveness (φ) for non-Gaussian datasets. ENCLUS, entropy clustering; CBE, clustering-based on entropy.

Algorithm	μ(φ)
k-means	0.56
fuzzy c-means	0.54
ENCLUS	0.13
CBE	0.08
p-value < 0.05

shows the values of φ for non-Gaussian datasets. These do not have a particular arrangement (disjoint, overlapping and concentric). As before, lower values imply better closeness to the results achieved from MLP (see Section 5.2).

The values of CBE and ENCLUS are much better than the ones of traditional clustering methods. Nevertheless, when compared to ENCLUS, CBE is 62.5% better.

Since MLP is our reference for non-Gaussian datasets, we have included the percentual behavior of the four methods relative to it in

Table 9. Performance relative to MLP (%).

Algorithm	Percentual Performance
k-means	0.440
fuzzy c-means	0.460
ENCLUS	0.870
CBE	0.920
MLP	1.000
p-value < 0.05

.

6.3. “Real-World” Datasets

Based on Section 5.3, we calculate the effectiveness for the same set of CMs. Here, we used MLP as a practical reference of the best expected classification. The results are shown in

Table 10. Effectiveness achieved by CBE and other clustering methods for experimental data.

Set	CBE	ENCLUS	k-Means	Fuzzy c-Means	MLP
Abalone	0.596	0.563	0.496	0.511	0.690
Cars	0.917	0.896	0.696	0.712	0.997
Census	0.855	0.812	0.774	0.786	1.000
Hepatitis	0.859	0.846	0.782	0.811	0.987
Yeast	0.545	0.496	0.470	0.486	0.750
Average	0.754	0.723	0.644	0.661	0.885

. Contrary to previous results, a greater value represents a higher effectiveness.

As expected, the best value was achieved by MLP. The relative performance is shown in

Table 11. Performance relative to MLP.

Method	Relative Effectiveness
k-means	0.728
Fuzzy c-means	0.747
ENCLUS	0.817
CBE	0.853
MLP	1.000

.

7. Conclusions

A new unsupervised classifier system (CBE) has been defined based on the entropy as a quality index (QI) in order to pinpoint those elements in the dataset that, collectively, optimize such an index. The effectiveness of CBE has been tested by solving a large number of synthetic problems. Since there is a large number of possible combinations of the elements in the space of the clusters, an eclectic genetic algorithm is used to iteratively find the assignments in a way that increases the intra- and inter-cluster entropy simultaneously. This algorithm is run for a fixed number of iterations and yields the best possible combination of elements given a preset number of clusters k. That the GA will eventually reach the global optimum is guaranteed by the fact that it is elitist. That it will approach the global optimum satisfactorily in a relatively small number of iterations (800) is guaranteed by extensive tests performed elsewhere (see [48,49]).

We found that when compared to BC’s performance over Gaussian distributed datasets, CBE and BC have, practically, indistinguishable success ratios, thus proving that CBE is comparable to the best theoretical option. Here, we, again, stress that BC corresponds to supervised learning, whereas CBE does not. The advantage is evident. When compared to BC’s performance over non-Gaussian sets, CBE, as expected, displayed a much better success ratio. The conclusions above have been reached for a statistical p-value of 0.05. In other words, the probability of such results to persist on datasets outside our study is better than 0.95, thus ensuring the reliability of CBE.

The performance value φ was calculated by: (1) providing a method to produce an unlimited supply of data; (2) This method is able to yield Gaussian and non-Gaussian distributed data; (3) Batches of N = 36 datasets were clustered; (4) For every one of the N Gaussian sets, the difference between our algorithm’s classification and BC’s classification (φ) was calculated; (5) For every batch, $\overline{\phi }$ was recorded; (6) The process described in Steps 3, 4 and 5 was repeated until the $\overline{\phi }$ distributed normally; (7) Once the $\overline{\phi }$ are normal, we know the mean and standard deviation of the means; (8) Given these, we may infer the mean and standard deviation of the original pdf of the φs; (9) From Chebyshev’s theorem, we may obtain the upper bound of φ with probability 0.95. From this methodology, we may establish a worst case upper bound on the behavior of all of the analyzed algorithms. In other words, our conclusions are applicable to any clustering problem (even those outside of this study) with a probability better than 0.95.

For completeness, we also tested the effectiveness of CBE by solving a set of “real world” problems. We decided to use an MLP as the comparison criterion to measure the performance of CBE based on the nearness of its effectiveness with regard to it. Of all of the unsupervised algorithms that were evaluated, CBE achieved the best performance.

Here, two issues should be underlined: (1) Whereas BC and MLP are supervised, CBE is not. The distinct superiority of one method over the others, in this context, is evident; (2) As opposed to BC, CBE was designed not to need the previous calculation of the conditional probabilities of BC; a marked advantage of CBE over BC. It is important to mention that our experiments include tight tests comparing the behavior of other clustering methods. We compared the behavior of k-means, fuzzy c-means and ENCLUS against BC and MLP. The results of the comparison showed that CBE outperforms them (with 95% reliability).

For disjoint sets, which offer no major difficulty, all four methods (k-means, fuzzy c-means, ENCLUS and CBE) perform very well relative to BC. However, when tackling partially overlapping and concentric datasets, the differences are remarkable. The information-based methods (CBE and ENCLUS) showed the best results; nevertheless, CBE was better than ENCLUS. For non-Gaussian datasets, the values of CBE and ENCLUS also outperform the other methods. When CBE is compared to ENCLUS, CBE is 62.5% better.

In conclusion, CBE is a non-supervised, highly efficient, universal (in the sense that it may be easily utilized with other quality indices) clustering technique whose effectiveness has been proven by tackling a very large number of problems (1,530,000 combined instances). It has been, in practice, used to solve complex clustering problems that other methods were not able to solve.