Performance evaluation of FMIG clustering using fuzzy validity indexes

Abstract

The clustering of high-dimensional data presents a critical computational problem. Therefore, it is convenient to arrange the cluster centres on a grid with a small dimensional space that reduces computational cost and can be easily visualized. Moreover, in real applications there is no sharp boundary between classes, real datasets are naturally defined in a fuzzy context. Therefore, fuzzy clustering fits better for complex real datasets to determine the best distribution. Self-organizing map (SOM) technique is appropriate for clustering and vector quantization of high-dimensional data. In this paper we present a new fuzzy learning approach called FMIG (fuzzy multilevel interior growing self-organizing maps). The proposed algorithm is a fuzzy version of MIGSOM (multilevel interior growing self-organizing maps). The main contribution of FMIG is to define a fuzzy process of data mapping and to take into account the fuzzy aspect of high-dimensional real datasets. This new algorithm is able to auto-organize the map accordingly to the fuzzy training property of the nodes. In the second step, the introduced scheme for FMIG is clustered by means of fuzzy C-means (FCM) to discover the interior class distribution of the learned data. The validation of FCM partitions is directed by applying six validity indexes. Superiority of the new method is demonstrated by comparing it with crisp MIGSOM, GSOM (growing SOM) and FKCN (fuzzy Kohonen clustering network) techniques. Thus, our new method shows improvement in term of quantization error, topology preservation and clustering ability.

Appendix

1.1 Description of the used validity indexes

Let $X=\left\{ {x_1 ,x_2 ,...,x_n } \right\}$ be a dataset in an m-dimensional Euclidean space Rm with its ordinary Euclidean norm $\left\| . \right\|$ and let C, be the matrix of cluster centres with $c_i$, the centre of the cluster $C_i$ ($1\le i\le \mathrm{{nbc}})$. In case of fuzzy clustering, a pattern (point) may belong to all the clusters with a certain fuzzy membership grade. Consider the matrix $U=\left| {u_{ik} } \right|$ where $u_{ik}$ is the value of membership of the point k in cluster $i$, and $u_{ik}$ is in the interval [0,1] ($1\le k\le n)$.

We present below the validity indices studied in this work depending on the geometric aspects of clusters (compactness, separation) and the data properties (noise, overlap) evaluated by each index.

1.1.1 SVI index

SVI (Separation Validity Index) (Wu and Yang 2005) is given by

$$\begin{aligned} \mathrm{{SVI}}=\frac{\varvec{\pi }}{S} \end{aligned}$$

(17)

$\varvec{\pi }$ is a global compactness of the partition, it makes the sum of $\pi _i$, $1\le i\le \mathrm{{nbc}}$.

The compactness of the cluster c$^i$ is defined by

$$\begin{aligned} \pi _i =\frac{\sigma _i }{n_{{i}} }1\le i\le \mathrm{{nbc}} \end{aligned}$$

(18)

The variation $\sigma _i$ and the cardinality $n_{i}$ of the cluster c$_i$ are given, respectively, as

$$\begin{aligned} \sigma _i =\sum \limits _{k=1}^n ({u}_{ik} )^m\left\| {x_k \left. {-\nu _i } \right\| } \right. ^{2},n_i =\sum \limits _{k=1}^n {u_{ik} } ,1\le i\le \mathrm{{nbc}} \end{aligned}$$

(19)

with ${u}_{ik}$, the membership degree of the vector $x_k$ to the cluster c$_i$ and $\nu _i$ the centre of c$_i$.

$S$ is the global separation between the nbc clusters defined as 

$$\begin{aligned} S=\sum \limits _{i=1}^{\mathrm{{nbc}}+1} {\sum \limits _{\begin{array}{c} j=1\\ j\ne i \end{array}}^{\mathrm{{nbc}}+1} {(\mathrm{de}\nu _{ij} )^2} } \end{aligned}$$

(20)

$\mathrm{de}\nu _{ij}$ is the deviation between the centres of $c_i$ and $c_j$.

$$\begin{aligned} de\nu _{ij} =(\mu _{ij} )^{(2+\omega )/{2\omega }}\left\| {z_j -z_i } \right\| \end{aligned}$$

(21)

$\left[ {z_1 ,z_2 ,...,z_{\mathrm{{nbc}},} z_{\mathrm{{nbc}}+1} } \right] =\left[ {\nu _1 ,\nu _2 ,...,\nu _{\mathrm{{nbc}},} \overline{x} } \right] ^T,$ where $\overline{x}$ is the mean of X.

$$\begin{aligned} \overline{x} =\sum \limits _{k=1}^n {{x_k }/n} \end{aligned}$$

(22)

$\mu _{ij}$ is the degree of membership of $z_j$ to the centre $z_i$.

$$\begin{aligned}&\mu _{ij} =\frac{1}{\sum \limits _{\begin{array}{c} l=1\\ l\ne j \end{array}}^{\mathrm{{nbc}}+1} {\left( {\frac{\left\| {z_j -z_i } \right\| }{\left\| {z_j -z_l } \right\| }}\right) ^\omega } },1\le i\le \mathrm{{nbc}}+1;\nonumber \\&\qquad \qquad 1\le j\le \mathrm{{nbc}}+1,j\ne i \end{aligned}$$

(23)

1.1.2 XBI index

This index is normalized and gives the best number of clusters at its minimum value (Mingoti and Lima 2006) as shown:

$$\begin{aligned} \mathrm{{XBI}}(\mathrm{{nbc}})=\frac{\max _{k=1,..,nbc} \left\{ {\sum \limits _{j=1}^n {\frac{u_{kj}^2 \left\| {x_j -c_k } \right\| ^2}{n_k }} } \right\} +\max \mathrm{{Diff}}(\mathrm{{nbc}})}{\min _{i,j\ne i} \left\| {c_i -c_j } \right\| ^2} \end{aligned}$$

(24)

where

$\max _{k=1,..,\mathrm{{nbc}}} \left\{ {\sum \limits _{j=1}^n {\frac{u_{kj}^2 \left\| {x_j -c_k } \right\| ^2}{n_k }} } \right\}$ gives the max fuzzy distance between points $x_j$ with membership degree $u_{kj}$ to the center $c_k$.

This index introduced the $\max \mathrm{{Diff}}(\mathrm{{nbc}})$ factor in order to compare the nbc-partitions obtained by increasing nbc. Thus, we can find out the best partition.

$$\begin{aligned}&\max \mathrm{{Diff}}(\mathrm{{nbc}})=\max \nolimits _{\mathrm{{nbc}}\max ,...,\mathrm{{nbc}}} \mathrm{{diff}}_{dw}\end{aligned}$$

(25)

$$\begin{aligned}&\mathrm{{diff}}_{dw} =dw(\mathrm{{nbc}})-dw(\mathrm{{nbc}}+1) \end{aligned}$$

(26)

with $dw$ intra-cluster distance measured for different values of nbc.

1.1.3 PCAESN index

Called Partition Coefficient And Exponential Separation (PCAES) (Hu et al. 2004), this validity index takes into account two factors with a normalized partition coefficient and an exponential separation measure to validate separately each fuzzy cluster $i$. PCAES is then defined as:

$$\begin{aligned} \mathrm{{PCAES}}(\mathrm{{nbc}})=\sum \limits _{i=1}^{\mathrm{{nbc}}} {\mathrm{{PCAESi}}} \end{aligned}$$

(27)

The validity index of cluster i is measured by:

$$\begin{aligned} \mathrm{{PCAESi}}=\sum \limits _{j=1}^n {{\mu _{ij}^2 }/{\mu _M }-} \text{ exp } ( {-\min \{\left\| {a_\mathrm{i} -a_k} \right\| ^{2}\} /{\beta _\mathrm{T}}}) \end{aligned}$$

(28)

where$\sum \limits _{j=1}^n {{\mu _{ij}^2 }/{\mu _M }}$: the compactness of the cluster i compared to the most compact cluster with its value of compactness $\mu _M$measured by:

$$\begin{aligned} \mu _M =\mathop {\min }\limits _{1\le i\le nbc} \left\{ {\sum \limits _{j=1}^n {\mu _{ij}^2 } } \right\} \end{aligned}$$

(29)

$\mu _{ij}$ is the membership degree of vector j ($1\le j\le n)$ to cluster i ($1\le k\le \mathrm{{nbc}})$,

$\text{ exp } ( {{-\min \{ }\left\| {a_\mathrm{i} -a_k } \right\| ^{2}{\} } / {\beta _\mathrm{T} }})$ is the separation measure relative to the total average separation $\beta _\mathrm{T}$ of the nbc clusters given by:

$$\begin{aligned} \beta _\mathrm{T} =\frac{\sum \nolimits _{l=1}^{nbc} {\left\| {a_l -\overline{a} } \right\| ^2} }{nbc} \end{aligned}$$

(30)

$a_\mathrm{i}$ is the center of cluster $i$, and $\overline{a} =\sum \nolimits _{i=1}^{\mathrm{{nbc}}} {a_i /nbc}$, the average of center vectors $a_\mathrm{i}$.

Normalisation of PCAES index:

Basically, each validity index measure PCAESi ($i =1{\ldots }{\mathrm{nbc}}$) is obtained by a subtraction between the compactness and separation values which are defined in the interval [0 1]. Consequently, we present PCAES values as

$$\begin{aligned} -\mathrm{{nbc}}< \text{ PCAES } ( {\mathrm{{nbc}}})\, <\mathrm{{nbc}} \end{aligned}$$

(31)

Thus, to obtain the value of PCAES in [0 1], we have specified PCAESN Tlili et al. (2014) as following:

$$\begin{aligned} \mathrm{{PCAESN}}(\mathrm{{nbc}})=0.5+\left[ {( {\mathrm{{PCAES}}(\mathrm{{nbc}})/nbc})/2} \right] \end{aligned}$$

(32)

1.1.4 VOS index

Validity Overlap Separation (VOS) (Pal and Bezdek 1992) gives its values in the interval [0 1] and reaches its best partition for the minimum value.

This index is given by

$$\begin{aligned} \mathrm{{VOS}}(\mathrm{{nbc}},U)=\frac{Overlap^N(\mathrm{{nbc}},U)}{\mathrm{{Sep}}^N(\mathrm{{nbc}},U)}, \end{aligned}$$

(33)

where $Overlap^N(nbc,U)$ gives an inter-cluster overlap for different values of nbc, normalized by the max overlap for nbc = 2...nbcmax.

$$\begin{aligned} \mathrm{{Overlap}}^N(\mathrm{{nbc}},U)=\frac{\mathrm{{Overlap}}(\mathrm{{nbc}},U)}{\mathrm{{Overlap}}_{\max } } \end{aligned}$$

(34)

$Sep^N(nbc,U)$ calculates the separation between clusters for different values of nbc, normalized by the max separation for nbc = 2...nbcmax.

$$\begin{aligned} Sep^N(nbc,U)=\frac{Sep(nbc,U)}{Sep_{\max } } \end{aligned}$$

(35)

1.2 Overlap function

$$\begin{aligned} \mathrm{{Overlap}}(\mathrm{{nbc}},U)=\frac{2}{\mathrm{{nbc}}(\mathrm{{nbc}}-1)}\sum \limits _{p=1}^{\mathrm{{nbc}}-1} {\sum \limits _{q=p+1}^{nbc} {P(\overline{F} _p ,\overline{F} _q )} } \end{aligned}$$

(36)

$P(\overline{F} _p ,\overline{F} _q )$ defines the total overlap between two fuzzy clusters $\overline{F} _p$ and $\overline{F} _q$:

$$\begin{aligned} P(\overline{F} _p ,\overline{F} _q )=\sum \limits _\mu {f(\mu :} \overline{F} _p ,\overline{F} _q ) \end{aligned}$$

(37)

The function $f(\mu :\overline{F} _p ,\overline{F} _q )$ calculates the overlap degree between two fuzzy clusters $\overline{F} _p$ and $\overline{F} _q$ at a membership degree $\mu$ given by

$$\begin{aligned} f(\mu :\overline{F} _p ,\overline{F} _q )=\sum \limits _{j=1}^\mathrm{nbc} {\delta (x_j ,} \mu :\overline{F} _p ,\overline{F} _q ) \end{aligned}$$

(38)

$\delta (x_j , \mu :\overline{F} _p ,\overline{F} _q )$ indicates whether two clusters are overlapping at the membership degree $\mu$ for data point $x_j$. It returns an overlap value of $\omega (x_j )$ when the membership degrees of two clusters are both greater than $\mu$; otherwise it returns 0.0:

$$\begin{aligned}&\delta (x_j , \mu :\overline{F} _p ,\overline{F} _q )\nonumber \\&\quad =\left\{ {\begin{array}{l} \omega (x_j )\quad \text{ if } (\mu _{\overline{F} _p } (x_j )\ge \mu ) \text{ and }\, (\mu _{\overline{F} _q } (x_j )\ge \mu ), \\ 0 \quad \text{ otherwise } \\ \end{array}} \right. \end{aligned}$$

(39)

$\omega (x_j )$  is a weight factor for each point $x_j$ between clusters. $\omega (x_j )$ is a value in [0 1].

1.3 Separation function

The separation measure is obtained using the similarity distance $S(\overline{F} _p ,\overline{F} _q )$ between two fuzzy clusters $\overline{F} _p$ and $\overline{F} _q$. It is defined as

$$\begin{aligned} Sep(nbc,U)=1-\underbrace{\min }_{p\ne q}S(\overline{F} _p ,\overline{F} _q ) \end{aligned}$$

(40)

$S(\overline{F} _p ,\overline{F} _q )$ is the maximum membership degree between two clusters $\overline{F} _p$ and $\overline{F} _q$ in the interval [0 1]:

$$\begin{aligned} S(\overline{F} _p ,\overline{F} _q )=\underbrace{\max }_{x\in X}\min (\mu _{\overline{F} p} (x),\mu _{\overline{F} q} (x)), \end{aligned}$$

(41)

where $\mu _{\overline{F} p} \text{( }x\text{) }$, $\mu _{\overline{F} q} (x)$ are the membership degrees of vector $x$, respectively, in $\overline{F} _p$ and $\overline{F} _q$.

1.3.1 Dunn index

The validity indice Dunn (1974) is based on inter-cluster distance and the diameter of a hyperspheric cluster. Dunn index is given as

$$\begin{aligned}&\mathrm{{Dunn}}(\mathrm{{nbc}})=\min \nolimits _{i=1,...,\mathrm{{nbc}}}\\&\quad \times \left\{ {\min \nolimits _{j=i+1,...,\mathrm{{nbc}},j\ne i} \left\{ {\left. {\frac{d(c_{i,} c_j )}{\max _{k=1,...,nbc} \left\{ {\mathrm{{diam}}(c_k )} \right\} }} \right\} } \right. } \right\} \\&d(c_{i,} c_j )=\min \nolimits _{\mathop {x\in C}\nolimits _i ,\mathop {y\in C}\nolimits _j } \left\{ {d(x,y)} \right\} \end{aligned}$$

$diam(c_k )$ is the diameter of the cluster $c_k$.

1.3.2 FVINOS index

Fuzzy Validity Index with Noise-Overlap Separation (Tlili et al. 2014) (FVINOS) is inspired from the Davies–Bouldin validity index Mingoti and Lima (2006). FVINOS is defined as

$$\begin{aligned}&\mathrm{{FVINOS}}(\mathrm{{nbc}})=\frac{1}{\mathrm{{nbc}}}\sum \limits _{i=1}^{\mathrm{{nbc}}} \nonumber \\&\quad \times {\left( {\frac{\max _{k=1,\ldots ,\mathrm{{nbc}},k\ne i} \left\{ {S_i +S_k } \right\} +\max \mathrm{{Diff}}_i (\mathrm{{nbc}})}{\min _{l=1,\ldots ,nbc,l\ne i} \left\{ {d_{i,l} } \right\} }}\right) } \end{aligned}$$

(42)

$\min _{l=1,...,\mathrm{{nbc}},l\ne i} \left\{ {d_{i,l} } \right\}$ calculates the minimum separation between two clusters $i$ and l.

max Diff(nbc) factor is given to compare each two successive obtained partitions. In consequence, the best partition of the dataset is found.

$$\begin{aligned} \max \mathrm{{Diff}}_i (\mathrm{{nbc}})=\max \nolimits _{\mathrm{{nbc}}\max ,...,\mathrm{{nbc}}} \mathrm{{diff}}_i (\mathrm{{nbc}}) \end{aligned}$$

(43)

$$\begin{aligned} \mathrm{{diff}}_i (\mathrm{{nbc}})&= \max _{k=1,..,\mathrm{{nbc}},k\ne i} \left\{ {S_i (\mathrm{{nbc}})+S_k (\mathrm{{nbc}})} \right\} \nonumber \\&-\max \nolimits _{k=1,..,\mathrm{{nbc}}\!+\!1,k\ne i} \left\{ {S_i (\mathrm{{nbc}}\!+\!1)\!+\!S_k (nbc\!+\!1)} \right\} \nonumber \\ \end{aligned}$$

(44)

$\mathrm{diff}_i (\mathrm{nbc})$ calculates the difference between max sums of compactness in a pair of clusters $i$ and k; this is calculated for the obtained partition at nbc and nbc+1.

We define the average of fuzzy compactness relative to cluster $i$ as

$$\begin{aligned} S_i =\frac{1}{n_i }\sum \limits _{\mathop {x\in C}\nolimits _i } {(u_i (x)^m)\times d(x,c_i )}, \end{aligned}$$

(45)

where $u_i (x)$ is the membership degree of point $x$ to cluster $i$, $m$ is the fuzzifier factor.

$d(x,c_i )$ is the Euclidean distance separating $x$ from the cluster centre $c_i$.