# Deterministic Annealing Approach to Fuzzy C-Means Clustering Based on Entropy Maximization

Authors: Makoto Yasuda
Journal: Advances in Fuzzy Systems
 (2011)

---

## Abstract

This paper is dealing with the fuzzy clustering method which combines the deterministic annealing (DA) approach with an entropy, especially the Shannon entropy and the Tsallis entropy. By maximizing the Shannon entropy, the fuzzy entropy, or the Tsallis entropy within the framework of the fuzzy c-means (FCM) method, membership functions similar to the statistical mechanical distribution functions are obtained. We examine characteristics of these entropy-based membership functions from the statistical mechanical point of view. After that, both the Shannon- and Tsallis-entropy-based FCMs are formulated as DA clustering using the very fast annealing (VFA) method as a cooling schedule. Experimental results indicate that the Tsallis-entropy-based FCM is stable with very fast deterministic annealing and suitable for this annealing process.


---

## Body

## 1. Introduction

Statistical mechanics investigates the macroscopic properties of a physical system consisting of several elements. Recently, research activities that attempt to apply statistical mechanical models or tools to information science have become popular.The deterministic annealing (DA) method [1] is a deterministic variant of the simulated annealing (SA) method [2]. DA characterizes the minimization problem of the cost function as the minimization of the free energy, which depends on temperature and tracks its minimum while decreasing the temperature, and thus it can deterministically optimize the cost function at each temperature. Hence, DA is more efficient than SA, but does not guarantee a global optimal solution.There exists a strong relationship between the membership functions of the fuzzy c-means (FCM) clustering [3] with the maximum entropy or entropy regularization methods [4, 5] and the statistical mechanical distribution function. That is, FCM regularized with the Shannon entropy gives a membership function similar to the Boltzmann (or Gibbs) distribution function [1, 4], and FCM regularized with the fuzzy entropy [6] gives a membership function similar to the Fermi-Dirac distribution function [7]. These membership functions are suitable for the annealing methods because they contain a parameter corresponding to the system temperature.Tsallis [8] achieved nonextensive extension of the Boltzmann-Gibbs statistics. Tsallis postulated a generalization form of entropy with a generalization parameter q, which, in a limit of q→1, reaches the Shannon entropy. Later on, Ménard et al. [9] derived a membership function by regularizing FCM with the Tsallis entropy.In this study, the membership function which takes the familiar form of the statistical mechanical distribution function is derived by maximizing the Shannon and fuzzy entropy within the framework of FCM. Similarly, the Tsallis entropy-based FCM membership function is derived [10, 11] by maximizing the Tsallis entropy. Then, the formulations of the free energy for these membership functions are calculated and examined from the statistical mechanical viewpoint.On the other hand, there are some representative cooling schedules of the temperature for SA; for example, inversely proportional to a logarithmic function and inversely proportional to exponential function are well adopted. Rosen [12] proposed the more effective method for SA known as very fast annealing (VFA).However, an applicability of VFA to DA is not known yet. In order to achieve good clustering by DA, a reliable annealing process is desirable. Therefore, by introducing VFA to DA, we formulate the Shannon- and Tsallis-entropy based FCMs as very fast DA clustering, to examine their reliabilities.Experiments are performed on the numerical and iris data [13], and the obtained results indicate that Tsallis-entropy-based FCM clustering is suitable for very fast DA clustering because of its shape of the membership function.


## 2. Entropy Maximization Method

LetX={x1,…,xn}(xk=(xk1,…,xkp)∈Rp) be a data set in the p-dimensional real space, which should be divided into c clusters. In addition, let V={v1,….,vc}(vi=(vi1,…,vip)) be the centers of clusters, and let uik∈[0,1] (i=1,…,c; k=1,…,n) be the membership functions. Furthermore, let(1)J=∑k=1n∑i=1cuikmdik(m>1)
be the objective function of FCM, where dik=∥xk-vi∥2.


### 2.1. Shannon Entropy Maximization of FCM

First, we introduce the Shannon entropy into the FCM clustering. The Shannon entropy is given by(2)S=-∑k=1n∑i=1cuiklog⁡uik.
Under the normalization constraint of (3)∑i=1cuik=1(∀k),
and setting m to 1, the fuzzy entropy functional is given by(4)δS-∑k=1nαkδ(∑i=1cuik-1)-β∑k=1n∑i=1cδ(uikdik),
where αk and β are the Lagrange multipliers and αk must be determined so as to satisfy (3). The stationary condition for (4) leads to the following membership function(5)uik=e-βdik∑j=1ce-βdjk
and the cluster centers(6)vi=∑k=1nuikxk∑k=1nuik.


### 2.2. Fuzzy Entropy Maximization of FCM

We then introduce the fuzzy entropy into the FCM clustering.The fuzzy entropy is given by(7)Ŝ=-∑k=1n∑i=1c{ûiklog⁡ûik+(1-ûik)log⁡(1-ûik)}.
The fuzzy entropy functional is given by(8)δŜ-∑k=1nαkδ(∑i=1cûik-1)-β∑k=1n∑i=1cδ(ûikdik),
where αk and β are the Lagrange multipliers [14]. The stationary condition for (8) leads to the following membership function:(9)ûik=1eαk+βdik+1
and the cluster centers(10)vi=∑k=1nûikxk∑k=1nûik.
In (9), β defines the extent of the distribution [7]. Equation (9) is formally normalized as(11)ûik=1eαk+βdik+1/∑j=1c1eαk+βdjk+1.


### 2.3. Tsallis Entropy Maximization of FCM

Letṽi and ũik be the centers of clusters and the membership functions, respectively.The Tsallis entropy is defined as(12)S̃=-1q-1(∑k=1n∑i=1cũikq-1),
where q∈R is any real number. The objective function is rewritten as(13)Ũ=∑k=1n∑i=1cũikqd̃ik,
where d̃ik=∥xk-ṽi∥2.Accordingly, the Tsallis entropy functional is given by(14)δS̃-∑k=1nαkδ(∑i=1cũik-1)-β∑k=1n∑i=1cδ(ũikqd̃ik).
The stationary condition for (14) yields the following membership function:(15)ũik={1-β(1-q)d̃ik}1/(1-q)Z̃,
where(16)Z̃=∑j=1c{1-β(1-q)d̃jk}1/(1-q).
In this case, the cluster centers are given by(17)ṽi=∑k=1nũikqxk∑k=1nũikq.In the limit ofq→1, the Tsallis entropy recovers the Shannon entropy [8] and ũik approaches uik in (5).


## 2.1. Shannon Entropy Maximization of FCM

First, we introduce the Shannon entropy into the FCM clustering. The Shannon entropy is given by(2)S=-∑k=1n∑i=1cuiklog⁡uik.
Under the normalization constraint of (3)∑i=1cuik=1(∀k),
and setting m to 1, the fuzzy entropy functional is given by(4)δS-∑k=1nαkδ(∑i=1cuik-1)-β∑k=1n∑i=1cδ(uikdik),
where αk and β are the Lagrange multipliers and αk must be determined so as to satisfy (3). The stationary condition for (4) leads to the following membership function(5)uik=e-βdik∑j=1ce-βdjk
and the cluster centers(6)vi=∑k=1nuikxk∑k=1nuik.


## 2.2. Fuzzy Entropy Maximization of FCM

We then introduce the fuzzy entropy into the FCM clustering.The fuzzy entropy is given by(7)Ŝ=-∑k=1n∑i=1c{ûiklog⁡ûik+(1-ûik)log⁡(1-ûik)}.
The fuzzy entropy functional is given by(8)δŜ-∑k=1nαkδ(∑i=1cûik-1)-β∑k=1n∑i=1cδ(ûikdik),
where αk and β are the Lagrange multipliers [14]. The stationary condition for (8) leads to the following membership function:(9)ûik=1eαk+βdik+1
and the cluster centers(10)vi=∑k=1nûikxk∑k=1nûik.
In (9), β defines the extent of the distribution [7]. Equation (9) is formally normalized as(11)ûik=1eαk+βdik+1/∑j=1c1eαk+βdjk+1.


## 2.3. Tsallis Entropy Maximization of FCM

Letṽi and ũik be the centers of clusters and the membership functions, respectively.The Tsallis entropy is defined as(12)S̃=-1q-1(∑k=1n∑i=1cũikq-1),
where q∈R is any real number. The objective function is rewritten as(13)Ũ=∑k=1n∑i=1cũikqd̃ik,
where d̃ik=∥xk-ṽi∥2.Accordingly, the Tsallis entropy functional is given by(14)δS̃-∑k=1nαkδ(∑i=1cũik-1)-β∑k=1n∑i=1cδ(ũikqd̃ik).
The stationary condition for (14) yields the following membership function:(15)ũik={1-β(1-q)d̃ik}1/(1-q)Z̃,
where(16)Z̃=∑j=1c{1-β(1-q)d̃jk}1/(1-q).
In this case, the cluster centers are given by(17)ṽi=∑k=1nũikqxk∑k=1nũikq.In the limit ofq→1, the Tsallis entropy recovers the Shannon entropy [8] and ũik approaches uik in (5).


## 3. Statistical Mechanical Interpretation of Entropy-Based FCM

### 3.1. Shannon-Entropy-Based FCM Statistics

In the Shannon-entropy-based FCM, the sum of the states (the partition function) for the grand canonical ensemble of fuzzy clustering can be written as(18)Z=∏k=1n∑i=1ce-βdik.
By substituting (18) for F=-(1/β)(logZ) [15], the free energy becomes(19)F=-1β∑k=1nlog⁡{∑i=1ce-βdik}.
Stable thermal equilibrium requires a minimization of the free energy. By formulating deterministic annealing as a minimization of the free energy, ∂F/∂vi=0 yields(20)vi=∑k=1nuikxk∑k=1nuik.
This cluster center is the same as that in (6).


### 3.2. Fuzzy-Entropy-Based FCM Statistics

In the fuzzy-entropy based FCM, by analogy with statistical mechanics, the grand partition function for the grand canonical ensemble of fuzzy clustering can be written as(21)Ξ̂=∏k=1n∏i=1c(1+e-αk-βdik),
because data can belong to any cluster. By substituting (21) for F̂=-(1/β)(logΞ̂-αk∂logΞ̂/∂αk) [15], the free energy becomes(22)F̂=-1β∑k=1n{∑i=1clog⁡(1+e-αk-βdik)+αk}.
It should be noted that Jm=1-TŜ, the Legendre transform of the fuzzy entropy, gives the same form for the free energy.


### 3.3. The Tsallis-Entropy-Based FCM Statistics

On the other hand,Ũ and S̃ satisfy(23)S̃-βŨ=∑k=1nZ̃1-q-11-q,
which leads to(24)∂S̃∂Ũ=β.
Equation (24) makes it possible to regard β-1 as an artificial system temperature T [15]. Then, the free energy can be defined as(25)F̃=Ũ-TS̃=-1β∑k=1nZ̃1-q-11-q.Ũ can be derived from F̃ as(26)Ũ=-∂∂β∑k=1nZ̃1-q-11-q.∂F̃/∂ṽi=0 also gives(27)ṽi=∑k=1nũikqxk∑k=1nũikq.


## 3.1. Shannon-Entropy-Based FCM Statistics

In the Shannon-entropy-based FCM, the sum of the states (the partition function) for the grand canonical ensemble of fuzzy clustering can be written as(18)Z=∏k=1n∑i=1ce-βdik.
By substituting (18) for F=-(1/β)(logZ) [15], the free energy becomes(19)F=-1β∑k=1nlog⁡{∑i=1ce-βdik}.
Stable thermal equilibrium requires a minimization of the free energy. By formulating deterministic annealing as a minimization of the free energy, ∂F/∂vi=0 yields(20)vi=∑k=1nuikxk∑k=1nuik.
This cluster center is the same as that in (6).


## 3.2. Fuzzy-Entropy-Based FCM Statistics

In the fuzzy-entropy based FCM, by analogy with statistical mechanics, the grand partition function for the grand canonical ensemble of fuzzy clustering can be written as(21)Ξ̂=∏k=1n∏i=1c(1+e-αk-βdik),
because data can belong to any cluster. By substituting (21) for F̂=-(1/β)(logΞ̂-αk∂logΞ̂/∂αk) [15], the free energy becomes(22)F̂=-1β∑k=1n{∑i=1clog⁡(1+e-αk-βdik)+αk}.
It should be noted that Jm=1-TŜ, the Legendre transform of the fuzzy entropy, gives the same form for the free energy.


## 3.3. The Tsallis-Entropy-Based FCM Statistics

On the other hand,Ũ and S̃ satisfy(23)S̃-βŨ=∑k=1nZ̃1-q-11-q,
which leads to(24)∂S̃∂Ũ=β.
Equation (24) makes it possible to regard β-1 as an artificial system temperature T [15]. Then, the free energy can be defined as(25)F̃=Ũ-TS̃=-1β∑k=1nZ̃1-q-11-q.Ũ can be derived from F̃ as(26)Ũ=-∂∂β∑k=1nZ̃1-q-11-q.∂F̃/∂ṽi=0 also gives(27)ṽi=∑k=1nũikqxk∑k=1nũikq.


## 4. Effects of Annealing Temperature

### 4.1. Dependency of Shapes of Membership Functions on Temperature

By reducing the temperature according to the annealing schedule, the deterministic annealing method achieves thermal equilibrium which minimizes the free energy. At absolute zero, the particle system settles down to the ground state, that is, the state of minimum energy. Figure1 shows the forms of the entropy functions S, Ŝ, and S̃. Figure 2 shows the forms of the membership functions uik, ûik, and ũik.The plots of the entropy functionsS, S¯ and S̃ at (a) high and (b) low temperature (n=1, c=2, q=1.5, αk=-2).
(a)
T=105(b)
T=103The plots of the membership functionsuik, u¯ik and ũik at (a) high and (b) low temperature (n=1, c=2, q=1.5, αk=-2).
(a)
T=105(b)
T=103In the deterministic annealing method, cluster distribution which minimizes the free energy is searched at the given temperature. At high temperature, the membership functions are widely distributed and clusters to which a data belongs are fuzzy. In case ofũik with q=2, the width of the distribution is roughly proportional to β-0.5. At the limit of low temperature, on the other hand, fuzzy clustering reaches hard clustering. The relationship F=U-TS suggests that the higher temperature causes the larger entropy state, that is, chaotic state. This increase of the entropy is the result of the extent of the membership function.In Figure2, it can be seen that ûik has a flat peak, though both uik and ũik have Gaussian forms. Also, it can be found that ũik has a more gentle base slope than uik.


### 4.2. Cooling Schedule

#### 4.2.1. Representative Annealing Methods

In SA, the temperature decreases according to a cooling schedule. The representative cooling schedules [16] for SA are(i)
proportional to an exponential function(28)T=Thighrt,
where Thigh is a sufficiently high initial temperature, r is a parameter which defines a temperature reduction speed, and t is the number of iterations,(ii)
inversely linear function(29)T=Thight,(iii)
inversely proportional to a logarithmic function(30)T=Thighln⁡(t),(iv)
inversely proportional to exponential function(31)T=Thigher-1t.


#### 4.2.2. Very Fast Annealing

Rosen proposed another inversely proportional to exponential function known as very fast annealing (VFA).In VFA,T is given by(32)T=Thighe-mt(1/D),
where m is a temperature reduction parameter and D is a dimension of a state space. Equations (31) and (32) are compared in Figure 3. It is observed that VFA initially decreases a temperature extremely.The plots of the cooling functions of (a) proportional to an exponential (r=0.1,1,10) and (b) very fast annealing methods (m=1.0,2.0,3.0).
(a)
Inversely proportional to an exponential function(b)
Very fast annealingIn Section6, we apply VFA as a cooling schedule of entropy based FCM clustering using DA.


## 4.1. Dependency of Shapes of Membership Functions on Temperature

By reducing the temperature according to the annealing schedule, the deterministic annealing method achieves thermal equilibrium which minimizes the free energy. At absolute zero, the particle system settles down to the ground state, that is, the state of minimum energy. Figure1 shows the forms of the entropy functions S, Ŝ, and S̃. Figure 2 shows the forms of the membership functions uik, ûik, and ũik.The plots of the entropy functionsS, S¯ and S̃ at (a) high and (b) low temperature (n=1, c=2, q=1.5, αk=-2).
(a)
T=105(b)
T=103The plots of the membership functionsuik, u¯ik and ũik at (a) high and (b) low temperature (n=1, c=2, q=1.5, αk=-2).
(a)
T=105(b)
T=103In the deterministic annealing method, cluster distribution which minimizes the free energy is searched at the given temperature. At high temperature, the membership functions are widely distributed and clusters to which a data belongs are fuzzy. In case ofũik with q=2, the width of the distribution is roughly proportional to β-0.5. At the limit of low temperature, on the other hand, fuzzy clustering reaches hard clustering. The relationship F=U-TS suggests that the higher temperature causes the larger entropy state, that is, chaotic state. This increase of the entropy is the result of the extent of the membership function.In Figure2, it can be seen that ûik has a flat peak, though both uik and ũik have Gaussian forms. Also, it can be found that ũik has a more gentle base slope than uik.


## 4.2. Cooling Schedule

### 4.2.1. Representative Annealing Methods

In SA, the temperature decreases according to a cooling schedule. The representative cooling schedules [16] for SA are(i)
proportional to an exponential function(28)T=Thighrt,
where Thigh is a sufficiently high initial temperature, r is a parameter which defines a temperature reduction speed, and t is the number of iterations,(ii)
inversely linear function(29)T=Thight,(iii)
inversely proportional to a logarithmic function(30)T=Thighln⁡(t),(iv)
inversely proportional to exponential function(31)T=Thigher-1t.


### 4.2.2. Very Fast Annealing

Rosen proposed another inversely proportional to exponential function known as very fast annealing (VFA).In VFA,T is given by(32)T=Thighe-mt(1/D),
where m is a temperature reduction parameter and D is a dimension of a state space. Equations (31) and (32) are compared in Figure 3. It is observed that VFA initially decreases a temperature extremely.The plots of the cooling functions of (a) proportional to an exponential (r=0.1,1,10) and (b) very fast annealing methods (m=1.0,2.0,3.0).
(a)
Inversely proportional to an exponential function(b)
Very fast annealingIn Section6, we apply VFA as a cooling schedule of entropy based FCM clustering using DA.


## 4.2.1. Representative Annealing Methods

In SA, the temperature decreases according to a cooling schedule. The representative cooling schedules [16] for SA are(i)
proportional to an exponential function(28)T=Thighrt,
where Thigh is a sufficiently high initial temperature, r is a parameter which defines a temperature reduction speed, and t is the number of iterations,(ii)
inversely linear function(29)T=Thight,(iii)
inversely proportional to a logarithmic function(30)T=Thighln⁡(t),(iv)
inversely proportional to exponential function(31)T=Thigher-1t.


## 4.2.2. Very Fast Annealing

Rosen proposed another inversely proportional to exponential function known as very fast annealing (VFA).In VFA,T is given by(32)T=Thighe-mt(1/D),
where m is a temperature reduction parameter and D is a dimension of a state space. Equations (31) and (32) are compared in Figure 3. It is observed that VFA initially decreases a temperature extremely.The plots of the cooling functions of (a) proportional to an exponential (r=0.1,1,10) and (b) very fast annealing methods (m=1.0,2.0,3.0).
(a)
Inversely proportional to an exponential function(b)
Very fast annealingIn Section6, we apply VFA as a cooling schedule of entropy based FCM clustering using DA.


## 5. Fuzzy C-Means as Clustering Algorithm Using Very Fast Annealing DA

The very fast deterministic annealing algorithm for the Tsallis-entropy-based FCM is given as follows.(1)
Set the number of clustersc, the highest temperature Thigh, the temperature reduction rate m, and the threshold of convergence test δ1 and δ2;(2)
generate initial clusters at random positions and assign each data point to the nearest cluster. Set current temperatureT to Thigh;(3)
calculateũik by (15);(4)
calculate cluster centers by (17);(5)
compare the difference between the current centers and those obtained at the previous iterationv̂i. If the convergence condition If max1≤i≤c∥vi-v̂i∥<δ1 is satisfied, then go to (6), otherwise go back to (3);(6)
ifmax1≤i≤c∥vi-v̂i∥<δ2 is satisfied, then stop. Otherwise decrease the temperature with (32) and go back to (3).In case of Shannon-entropy-based FCM, (15) is replaced by (5) and (17) is replaced by (6), respectively.


## 6. Experiments

### 6.1. Experiment 1

In experiment 1, we generated five randomly placed clusters composed of 2,000 data points shown in Figure4. We set c to be 10, δ1 to be 50, and δ2 to be 2 (measured by the scale of Figure 4). We also set Thigh=1.0×106(β=1.0×10-6) or Thigh=1.0×105(β=1.0×10-5).Figure 4
The numerical data.First, we have applied the inversely exponential scheduling method to the Tsallis-entropy-based FCM clustering. The cooling schedule is illustrated in Figure5. The changes of β are parameterized by the temperature reduction rate r: from 1 to 1000.Figure 5
The inversely exponential cooling schedule of DA. The temperature decreases fromThigh. (Inverse of temperature β increases from 1.0×10-5 or 1.0×10-6 to 1.0×10-3) The curves are parameterized by the temperature reduction rate r.At the higher levels ofT (Figure 5 (A)), clusters are created near the center of gravity of data because β is comparatively small and the membership function extends over the whole data area and is extremely uniform. As T is lowered from Figure 5 (B) to (C), the width of the membership functions becomes narrower; that is, the Tsallis entropy decreases, and the associations become less fuzzy. And finally, the desired result is obtained.In case ofr=10 or r=1 (Figure 5 (E) or (F)), it is observed that ũik and ṽi converge more rapidly. In case of Thigh=1.0×106(β=1.0×10-6), however, the initial distribution of ũik becomes too wide and the algorithm is not converged with r=100 and r=10 (indicated by “not converged” in Figure 5). Thus, it is important to set Thigh and r values properly.To examine the effectiveness of VFA as a cooling schedule of DA, we made numerical experiments of the Shannon- and Tsallis-entropy-based FCM clustering.The shifts of cluster centers with decreasing temperature are illustrated in Figures7 and 8.Initially, clusters are located randomly. At the higher levels ofT, clusters move to near the center of gravity of data because β is comparatively small and the membership function extends over the whole data area and is extremely uniform.AsT is lowered, the width of the membership functions becomes narrower and the associations of data become less fuzzy. In this process, in the Shannon-entropy-based FCM clustering, the clusters move to their nearest local data distribution centers. However, in the Tsallis-entropy-based FCM clustering, clusters can move a long distance to optimal positions because of their gentle base slopes.Figures9 and 10 illustrate the three-dimensional plots of uik and ũik in the progress of very fast DA clustering.At the higher temperature, roughness ofũik is smaller than that of uik. After that, the shapes of both membership functions do not change greatly, because VFA reduces the temperature extremely only at the early annealing stage.Consequently, because the Tsallis-entropy-based FCM has gentle slope in the region far from the origin, clusters can move long distance to optimal positions stably and the temperature can be reduced rapidly. This feature makes it possible to use VFA as a cooling schedule of DA for the Tsallis-entropy-based FCM. On the other hand, final cluster positions obtained by the Shannon-entropy-based FCM tend to depend on their initial positions.


### 6.2. Experiment 2

In experiment 2, the iris data set [13] consisting of 150 four-dimensional vectors of iris flowers are used. Three clusters of flowers detected are Versicolor, Virginia, and Setosa. Each cluster consists of 50 vectors.The Shannon- and Tsallis-entropy-based FCM with DA are examined. VFA is used as a cooling schedule of DA. We set the parameters as follows:c=3, Thigh=2, δ1=0.1, δ2=0.01, and q=1.5.The minimum, maximum, and average values of misclassified data of 100 trials are summarized in Table1. The Shannon-entropy-based FCM gives slightly better results than the Tsallis-entropy-based FCM. However, it is found that the Tsallis-entropy-based FCM gives the best results when the temperature reduction rate m=1.0 or 2.0, though the best results for the Shannon-entropy-based FCM are obtained only when m=2.0. Furthermore, variances of the Tsallis-entropy-based FCM are smaller than those of the Shannon-entropy-based FCM. These features indicate that a wide range of m values are applicable to Tsallis-entropy-based FCM.Table 1
Comparison of minimum, maximum, and average values of misclassified iris data (100 trials).
Tsallis-entropy-based FCMShannon-entropy-based FCMmMin.Max.Ave.mMin.Max.Ave.1.0141414.001.0151615.012.0141514.012.0111312.973.0141514.683.0111413.59Figure6 shows the reduction of the objective values of the Tsallis- and Shannon-entropy-based FCM with decreasing the temperature by VFA. The Shannon-entropy-based FCM does not converge properly when T=0.023 for m=2.0 and T=0.029 for m=3.0. That is, with larger m values, the Shannon-entropy-based FCM becomes unstable.Figure 6
Reduction of the objective values for iris data with decreasing the temperature by VFA. The curves are parameterized by the temperature reduction ratem.The shifts of cluster centers of Shannon entropy based clustering with decreasing the temperature by VFA (m=1.0,2.0,3.0).
(a)
m=1.0(b)
m=2.0(c)
m=3.0The shifts of cluster centers of Tsallis entropy based clustering with decreasing the temperature by VFA (m=1.0,2.0,3.0, q=1.5).
(a)
m=1.0(b)
m=2.0(c)
m=3.0The changes of the landscape ofuik with decreasing the temperature.
(a)
T=3.7×104(b)
T=1.3×104(c)
T=4.9×103The changes of the landscape ofũik with decreasing the temperature (q=1.5).
(a)
T=3.7×104(b)
T=1.3×104(c)
T=4.9×103


## 6.1. Experiment 1

In experiment 1, we generated five randomly placed clusters composed of 2,000 data points shown in Figure4. We set c to be 10, δ1 to be 50, and δ2 to be 2 (measured by the scale of Figure 4). We also set Thigh=1.0×106(β=1.0×10-6) or Thigh=1.0×105(β=1.0×10-5).Figure 4
The numerical data.First, we have applied the inversely exponential scheduling method to the Tsallis-entropy-based FCM clustering. The cooling schedule is illustrated in Figure5. The changes of β are parameterized by the temperature reduction rate r: from 1 to 1000.Figure 5
The inversely exponential cooling schedule of DA. The temperature decreases fromThigh. (Inverse of temperature β increases from 1.0×10-5 or 1.0×10-6 to 1.0×10-3) The curves are parameterized by the temperature reduction rate r.At the higher levels ofT (Figure 5 (A)), clusters are created near the center of gravity of data because β is comparatively small and the membership function extends over the whole data area and is extremely uniform. As T is lowered from Figure 5 (B) to (C), the width of the membership functions becomes narrower; that is, the Tsallis entropy decreases, and the associations become less fuzzy. And finally, the desired result is obtained.In case ofr=10 or r=1 (Figure 5 (E) or (F)), it is observed that ũik and ṽi converge more rapidly. In case of Thigh=1.0×106(β=1.0×10-6), however, the initial distribution of ũik becomes too wide and the algorithm is not converged with r=100 and r=10 (indicated by “not converged” in Figure 5). Thus, it is important to set Thigh and r values properly.To examine the effectiveness of VFA as a cooling schedule of DA, we made numerical experiments of the Shannon- and Tsallis-entropy-based FCM clustering.The shifts of cluster centers with decreasing temperature are illustrated in Figures7 and 8.Initially, clusters are located randomly. At the higher levels ofT, clusters move to near the center of gravity of data because β is comparatively small and the membership function extends over the whole data area and is extremely uniform.AsT is lowered, the width of the membership functions becomes narrower and the associations of data become less fuzzy. In this process, in the Shannon-entropy-based FCM clustering, the clusters move to their nearest local data distribution centers. However, in the Tsallis-entropy-based FCM clustering, clusters can move a long distance to optimal positions because of their gentle base slopes.Figures9 and 10 illustrate the three-dimensional plots of uik and ũik in the progress of very fast DA clustering.At the higher temperature, roughness ofũik is smaller than that of uik. After that, the shapes of both membership functions do not change greatly, because VFA reduces the temperature extremely only at the early annealing stage.Consequently, because the Tsallis-entropy-based FCM has gentle slope in the region far from the origin, clusters can move long distance to optimal positions stably and the temperature can be reduced rapidly. This feature makes it possible to use VFA as a cooling schedule of DA for the Tsallis-entropy-based FCM. On the other hand, final cluster positions obtained by the Shannon-entropy-based FCM tend to depend on their initial positions.


## 6.2. Experiment 2

In experiment 2, the iris data set [13] consisting of 150 four-dimensional vectors of iris flowers are used. Three clusters of flowers detected are Versicolor, Virginia, and Setosa. Each cluster consists of 50 vectors.The Shannon- and Tsallis-entropy-based FCM with DA are examined. VFA is used as a cooling schedule of DA. We set the parameters as follows:c=3, Thigh=2, δ1=0.1, δ2=0.01, and q=1.5.The minimum, maximum, and average values of misclassified data of 100 trials are summarized in Table1. The Shannon-entropy-based FCM gives slightly better results than the Tsallis-entropy-based FCM. However, it is found that the Tsallis-entropy-based FCM gives the best results when the temperature reduction rate m=1.0 or 2.0, though the best results for the Shannon-entropy-based FCM are obtained only when m=2.0. Furthermore, variances of the Tsallis-entropy-based FCM are smaller than those of the Shannon-entropy-based FCM. These features indicate that a wide range of m values are applicable to Tsallis-entropy-based FCM.Table 1
Comparison of minimum, maximum, and average values of misclassified iris data (100 trials).
Tsallis-entropy-based FCMShannon-entropy-based FCMmMin.Max.Ave.mMin.Max.Ave.1.0141414.001.0151615.012.0141514.012.0111312.973.0141514.683.0111413.59Figure6 shows the reduction of the objective values of the Tsallis- and Shannon-entropy-based FCM with decreasing the temperature by VFA. The Shannon-entropy-based FCM does not converge properly when T=0.023 for m=2.0 and T=0.029 for m=3.0. That is, with larger m values, the Shannon-entropy-based FCM becomes unstable.Figure 6
Reduction of the objective values for iris data with decreasing the temperature by VFA. The curves are parameterized by the temperature reduction ratem.The shifts of cluster centers of Shannon entropy based clustering with decreasing the temperature by VFA (m=1.0,2.0,3.0).
(a)
m=1.0(b)
m=2.0(c)
m=3.0The shifts of cluster centers of Tsallis entropy based clustering with decreasing the temperature by VFA (m=1.0,2.0,3.0, q=1.5).
(a)
m=1.0(b)
m=2.0(c)
m=3.0The changes of the landscape ofuik with decreasing the temperature.
(a)
T=3.7×104(b)
T=1.3×104(c)
T=4.9×103The changes of the landscape ofũik with decreasing the temperature (q=1.5).
(a)
T=3.7×104(b)
T=1.3×104(c)
T=4.9×103


## 7. Conclusion

By maximizing the Tsallis-entropy, the membership function of the Tsallis-entropy-based FCM is formulated. It has a more gentle base slope in the region far from the origin than that of the Shannon- and fuzzy-entropy-based FCMs. This feature allows clusters to move long distance and the temperature can be reduced rapidly in the Tsallis-entropy-based FCM.Next, the deterministic annealing (DA) method using very fast annealing (VFA) as its cooling schedule is applied to the Tsallis-entropy-based FCM. VFA initially decreases a temperature extremely, and experimental results showed that the Tsallis-entropy-based FCM was suitable for DA combined with VFA.Our future works include convergence and computational time test under various conditions (temperatures and parameters, especiallyq-value) of the Tsallis-entropy-based FCM using very fast deterministic annealing. They also include experiments and examinations of its applications.



---

*Source: 960635-2011-11-20.xml*