A new validity function of FCM clustering algorithm based on intra-class compactness and inter-class separation

Abstract

Fuzzy C-means (FCM) clustering algorithm is a widely used method in data mining. However, there is a big limitation that the predefined number of clustering must be given. So it is very important to find an optimal number of clusters. Therefore, a new validity function of FCM clustering algorithm is proposed to verify the validity of the clustering results. This function is defined based on the intra-class compactness and inter-class separation from the fuzzy membership matrix, the data similarity between classes and the geometric structure of the data set, whose minimum value represents the optimal clustering partition result. The proposed clustering validity function and seven traditional clustering validity functions are experimentally verified on four artificial data sets and six UCI data sets. The simulation results show that the proposed validity function can obtain the optimal clustering number of the data set more accurately, and can still find the more accurate clustering number under the condition of changing the fuzzy weighted index, which has strong adaptability and robustness.

Keywords

Fuzzy C-means clustering algorithm clustering validity function membership matrix intra-class compactness inter-class separation

1 Introduction

With the continuous development of science and technology, the amount of data accumulated by all walks of life has increased dramatically. In order to mine valuable information from massive data, data mining technology came into being. As one of the important means of data mining, cluster analysis has been widely used in pattern recognition, information retrieval, image processing and so on [1, 2]. As an unsupervised learning method, clustering is to divide the similar samples into one class and dissimilar samples into different classes without prior knowledge of data [3]. The clustering algorithms can be divided into two major directions: hard clustering and fuzzy clustering. Hard clustering partitions data using either 1 or 0 method, which each data sample must be clearly assgined to one of classes, such as K-means clustering algorithm [4]. However, in reality most of the data is uncertain. For this reason, Ruspini introduced the concept of fuzzy theory [5] based on hard clustering method to produce fuzzy clustering, such as FCM clustering algorithm [6]. So that has the similarity between class and class division basis, data samples have better clustering results and become more effective, more close to the real need. FCM clustering algorithm has become one of the most widely used clustering algorithms by virtue of its simple principle, fast calculation speed and wide problem solving scope [7]. However, FCM clustering algorithm needs to be verified by clustering validity, so as to determine the optimal number of clustering and judge the quality of clustering results. Therefore, finding an appropriate clustering validity function is one of the important directions for studying clustering validity [8].

Any clustering validity function cannot apply all data sets due to the complexity of data structure and different attributes. So fuzzy clustering validity function has been innovating. At present, the exploration direction of fuzzy clustering validity functions focuses on the following two aspects:

(1) Fuzzy clustering validity function based on membership degree. In 1965, Zadeh took the lead in proposing separation degree, a measure of clustering effectiveness [9]. However, this metric cannot judge the result of clustering well. Then Bedzek first proposed the partition coefficient (V_PC) [10]. This is the first index used to describe the validity of fuzzy clustering by the degree of coincidence of data objects. According to V_PC and Shannon’s theorem in Shannon’s information theory, the partition entropy (V_PE) was proposed [11]. In order to suppress the monotonically changing characteristics of V_PC and V_PE with the number of clusters, Dave proposed a modified partition coefficient (V_MPC) [12] and new indicators (V_P) was proposed by Chen and Links in 2004 [13] and more.

(2) Fuzzy clustering validity function based on membership degree and data set geometry structure. For example, Xie and Beni proposed the Xie-Beni validity function (V_XB) based on this idea [14]. Fakuyame-Sugeno validity function (V_FS) was proposed in 1989 [15]. Knows et al. proposed the clustering validity function (V_K) [16]. Bensaid et al. proposed the clustering validity function (V_SC) [17]. K. L. Wu and M. S. Yang proposed the clustering validity function (V_PCAES) [18]. J. S. Wang proposed the clustering validity function (V_W) [19] and L. F. Zhu et al. proposed the clustering validity function (V_Z) [20] and more.

Various validity functions have their own advantages and disadvantages, which leads to that they can only be applied to a part of data sets. However, the evaluation of clustering validity is a key part of clustering analysis, so we absorb the advantages of traditional clustering validity function, and design a new clustering validity function to make it have better stability. This paper proposes a new validity function (V_HY) The function combines the fuzzy membership matrix with the geometric structure of the data so as to improve the relationship between the function and the geometric structure of the data set, which can effectively overcome the influence of noise data, overlapping data and high-dimensional data, accurately find the optimal number of clustering, and has good robustness. Experimental simulation results show that can obtain the correct number of clustering partition on both artificial data sets and UCI data sets and the clustering results of V_HY have better stability when the fuzzy weighted index is changed.

The paper is divided into five chapters. The first section mainly introduces the research background and significance. The second section introduces the FCM clustering algorithm and the composition of some clustering effectiveness functions. The third section introduces the principle of the proposed clustering effectiveness function. The fourth section is the experimental simulation and result analysis. The fifth section summarizes the full text and prospects the next work.

2 FCM Clustering algorithm and typical clustering validity functions

2.1 FCM clustering algorithm

The fuzzy C-means (FCM) clustering algorithm proposed by Bezdek is the most representative one of the fuzzy clustering methods, and is also the most widely used clustering algorithm. FCM clustering algorithm uses n data objects {x₁x₂, … , x_n } of data X to divided into c fuzzy clustering and to find the minimum objective function, which is defined as Equation (1): $J_{m} (U, V) = \sum_{i = 1}^{c} \sum_{j = 1}^{n} {(u_{ij})}^{m} {∥ x_{j} - v_{i} ∥}^{2}$ (1) where, J_m (U, V) is the square error clustering criterion, the minimum value of J_m (U, V) is named as the least square error stationary point; V = {v₁, v₂, …, v_n} is the corresponding set dividing cluster center in data set X; Parameter c represents the number of clusters divided and the number of clusters; The parameter m, mɛ(1, ∞), is the fuzzy exponent to control the degree of fuzziness of each data set; x_j - v_i represents the European distance between data object x_j and cluster center v_i; u_ij (0≤ u_ij ≤ 1) is the membership degree of data object x_j of cluster center v_i. In Equation (1), u_ij∈U, wherein, U is a membership matrix with fuzzy division of c × n that must satisfy the following conditions, and U₀ is called the initial membership matrix.

$\begin{matrix} J_{m} (U, V) = \sum_{i = 1}^{c} \sum_{j = 1}^{n} {(u_{ij})}^{m} {∥ x_{j} - v_{i} ∥}^{2} \\ 0 < \sum_{j = 1}^{c} u_{ij} < n for = 1, 2, \dots, c \end{matrix}$ (1)

Clustering validity is a problem of finding the optimal solution of c under the condition of J_m minimization. In fact, more attention must be paid to the validity of clustering if cluster analysis is to make a great contribution to engineering applications. Since J_m decreases monotonically with the decrease of c, an effective partition evaluation criterion is needed [22]. The process of FCM clustering algorithm is described as follows.

Step 1: Fix cluster parameters c and fuzzy factors m (usually between 1.5 and 2.5). When m=1, FCM clustering algorithm is equivalent to K-means algorithm; When m approaches 1 indefinitely, FCM clustering algorithm tends to be more and more clustering algorithm of hardening fraction. On the contrary, when m tends to be infinite, all data objects x_j and cluster center v_i will coincide, while data object x_j belongs to each cluster will have the same membership degree, with the value of 1/c;

Step 2: Initialize fuzzy division membership matrix.

Step 3: According to Equation (2), update the cluster center V_t+1 ={ v₁, v₂, …, v_c }. $v_{i} = \frac{\sum_{j = 1}^{n} {u_{ij}^{(t)}}^{m} \cdot x_{i}}{\sum_{j = 1}^{n} {u_{ij}^{(t)}}^{m}}, = 1, 2, \dots, C$ (2)

Step 4: According to Equation (3), update the fuzzy partition matrix U_t+1 = (u_ij) _c×n. $u_{ij} = {[\sum_{k = 1}^{c} {(\frac{{∥ x_{j} - v ∥}_{i}^{2 (t)}}{{∥ x_{j} - v_{k} ∥}^{2 (t)}})}^{2 / (m - 1)}]}^{- 1}$ (3)

For i = 1, 2, …, candj = 1, 2, …, n.

Step 5: Calculate e = V_t+1 - V_t. If e ≤ ɛ (ɛis a threshold value usually from 0.001 to 0.01), the algorithm is stopped and the final clustering result is calculated; Otherwise t = t+1 and go to Step 3.

2.2 Typical clustering validity functions

2.2.1 Partition coefficient (V_PC) [10]

The V_PC defined by Bezdek is used to measure the overlap between clusters, which is defined as Equation (4). $V_{PC} = \frac{1}{n} \sum_{i = 1}^{c} \sum_{j = 1}^{n} u_{ij}^{2}$ (4)

The main advantage of V_PC is its simple operation, while the disadvantage is that it decreases monotonously with the increase of c and has no direct correlation with some attributes of the data itself. The value of V_PC is between 1/c and 1, and the maximum value indicates that the clustering result is the most effective.

2.2.2 Partition Entropy (V_PE) [11]

Bezdek also used the V_PE to measure the fuzziness of clustering partition, and the index was similar to V_PC, which was defined as Equation (5): $V_{PE} = - \frac{1}{n} \sum_{i = 1}^{c} \sum_{j = 1}^{n} [u_{ij} {log}_{a} (u_{ij})]$ (5)

Bezdek proved it is suitable for all probability cluster partitions. The disadvantage of this validity function is that it decreases monotonically with the increase of c and lacks connection to the data structure. On the other hand, the calculated minimum value indicates that the clustering result is the most effective.

2.2.3 The modified partition coefficient (V_MPC) [12]

V_MPC is shown in Equation (6). The V_MPC index optimizes the monotonely decreasing trend of V_PC, but does not improve other defects of the V_PC index. $V_{MPC} = 1 - \frac{c}{c - 1} (1 - V_{PC})$ (6)

2.2.4 Xie-Beni clustering validity index (V_XB) [14]

V_XBproposed by Xie and Beni is realized by Equation (7). V_XB is the first clustering validity function to take the structure of the data set into consideration. $V_{XB} = \frac{\frac{1}{n} \sum_{i = 1}^{c} \sum_{j = 1}^{n} u_{ij}^{m} {∥ v_{i} - x_{j} ∥}^{2}}{min_{i \neq j} {∥ v_{i} - v_{j} ∥}^{2}}$ (7)

It is the ratio of the compactness of the intra-class to the separation of the inter-classes. Obviously, the larger the inter-class distance, the more discrete the inter-class, and the smaller the intra-class distance, the more compact the intra-class. Therefore, the minimum value of V_XB indicates that the clustering result is the most effective.

2.2.5 P clustering validity function (V_P) [13]

V_P is proposed by Chen and Linkens, and it is the vidlity index of the subtracted form. It is a validity function only concerned with membership degree, which is defined in Equation (8).

$\begin{matrix} V_{P} = & \frac{1}{n} \sum_{j = 1}^{n} max_{i} (u_{ij}) - \frac{1}{k} \sum_{i = 1}^{c - 1} \sum_{j = i + 1}^{c} \\ [\frac{1}{n} \sum_{k = 1}^{n} \min (u_{ik}, u_{jk})] \end{matrix}$ (8) where, $\frac{1}{n} \sum_{j = 1}^{n} max_{i} (u_{ij})$ represents the sum of the maximum membership of data in each class. The larger the value is, the better the compactness within the class will be. $\frac{1}{k} \sum_{i = 1}^{c - 1} \sum_{j = i + 1}^{c} [\frac{1}{n} \sum_{k = 1}^{n} \min (u_{ik}, u_{jk})]$ is the similarity between two classes, the smaller the similarity between two classes, the better the clustering effect. Its maximum value corresponds to the most effective clustering result.

2.2.6 Separation coefficient (V_SC) [17]

Bensaid et al. proposed V_SC in 1996. V_SC is the ratio of the sum of the tightness of the cluster to the sum of the separation degree, which is defined as Equation (9). $V_{SC} = \sum_{i = 1}^{c} \frac{\sum_{j = 1}^{n} u_{ij} {∥ v_{i} - x_{j} ∥}^{2}}{n_{i} \sum_{i = 1}^{c} {∥ v_{i} - v_{j} ∥}^{2}}$ (9)

V_SC replaces the measure of compactness within a class with the average sum of the whole and the average sum of the compactness within a class. The smaller the V_SC value, the better the clustering.

2.2.7 Fakuyame-Sugeno validity function (V_FS) [15]

The definition of the V_FS function is shown in Equation (10). $V_{FS} = \sum_{i = 1}^{c} \sum_{k = 1}^{n} u_{k 1}^{m} ({∥ x_{k} - v_{i} ∥}^{2} - {∥ v_{i} - \bar{ν} ∥}^{2})$ (10) where, $\sum_{i = 1}^{c} \sum_{k = 1}^{n} u_{k 1}^{m} v_{i} - {\bar{ν}}^{2}$ measures the degree of separation between classes. The greater the value, the better clustering results. So the smallest V_FS value is corresponding to the best clustering results.

2.2.8 Kwons clustering validity function (V_K) [16]

V_K is an effective indicator proposed by Kwon et al. It effectively counteracts the decreasing trend of V_XB by adding penalty terms to the molecules of the V_XB index. Like V_XB, the minimum value of V_K corresponds to the optimal number of clusters. V_K is calculated by Equation (11):

$V_{K} = \frac{\sum_{i = 1}^{c} \sum_{j = 1}^{n} u_{ij}^{2} {∥ x_{j} - v_{i} ∥}^{2} + \frac{1}{c} \sum_{i = 1}^{c} {∥ v_{i} - \bar{v} ∥}^{2}}{min_{i \neq k} {∥ v_{i} - v_{k} ∥}^{2}}$ (11)

2.2.9 PCAES validity function (V_PCAES) [18]

V_PCAES is a subtractive form of validity index proposed by Wu and Yang. It describes the compactness and separability of clustering by fuzzy membership function and relative value of center distance of an exponential structure. V_PCAES is defined as Equation (12).

$\begin{matrix} V_{PCAES} = & \sum_{i = 1}^{c} \sum_{j = 1}^{n} \frac{u_{ij}^{2}}{u_{mj}} - \sum_{i = 1}^{c} \exp \\ (\frac{- min_{k \neq i} {∥ v_{i} - v_{k} ∥}^{2}}{β_{T}}) \end{matrix}$ (12)

Where, $u_{mj} = min_{1 ⩽ i ⩽ c} \sum_{j = 1}^{n} u_{ij}^{2}$ , $β_{T} = \frac{1}{c} \sum_{i = 1}^{c} ∥ v_{i} {- \bar{v} ∥}^{2}$ . The maximum value of V_PCAES represents the best clustering result.

2.2.10 HF clustering validity function (V_HF) [24]

The V_HF validity function is constructed from two validity function that are WL and Tang. Is definition is given as follows Equation (13). The minimum value of V_HF corresponds to the optimal number of clusters.

$V_{HF} = \frac{\frac{1}{N} \sum_{i = 1}^{c} \sum_{j = 1}^{n} u_{ij} {∥ x_{j} - v_{i} ∥}^{2} + \frac{1}{c (c - 1)} \sum_{i = 1}^{c} \sum_{k = 1, k \neq i}^{c} {∥ v_{i} - v_{k} ∥}^{2}}{\frac{1}{2 c} (min_{i \neq j} {∥ v_{i} - v_{j} ∥}^{2} + \underset{i \neq j}{median} {∥ v_{i} - v_{j} ∥}^{2})}$ (13)

2.2.11 VZ clustering validity function (V_Z) [20]

L. F. Zhu proposed V_Z in 2019 which is defined in Equation (14). Where, the numerator $\sum_{j = 1}^{n} \frac{1 - min_{i} u_{ij}}{\sum_{i = 1}^{c} ∥ x_{j} - v_{i} ∥}$ represents compactness within the class, and the denominator $\sum_{k = 1}^{c} \sum_{i = 1; i \neq k}^{c} ∥ v_{i} - \bar{v} ∥ / \frac{c (c - 1)}{2}$ represents separation between classes. Smaller V_Z corresponds to the optimal clustering validity function. $V_{Z} = \frac{\sum_{j = 1}^{n} \frac{1 - min_{i} u_{ij}}{\sum_{i = 1}^{c} ∥ x_{j} - v_{i} ∥}}{\sum_{k = 1}^{c} \sum_{i = 1; i \neq k}^{c} ∥ v_{i} - \bar{v} ∥ / \frac{c (c - 1)}{2}}$ (14)

2.2.12 ECS validity function (V_ECS) [25]

The V_ECS is proposed by Ouchicha in 2020, which is defined in Equation (15) $V_{ECS} = \frac{SC - {SC}_{\min}}{{SC}_{\max} - {SC}_{\min}} + \frac{PEC - {PEC}_{\min}}{{PEC}_{\max} - {PEC}_{\min}}$ (15)

Where, in the V_ECS, the SC was denified as $\frac{\frac{1}{N} \sum_{i = 1}^{c} \sum_{j = 1}^{n} u_{ij} {∥ x_{j} - v_{i} ∥}^{2}}{\frac{1}{c} \sum_{i = 1}^{c} {∥ v_{i} - \bar{ν} ∥}^{2}}$ , and the PEC was denified as $\frac{\frac{1}{N (1 - m)} \sum_{i = 1}^{c} \sum_{j = 1}^{n} \log (u_{ij}^{m} + {(1 - u_{ij})}^{m})}{V_{PC}}$ . V_ECS was the normalized of SC and PEC. The minimum value of V_ECS corresponds to the optimal number of clusters.

3 A new clustering validity function

Based on the classical clustering validity functions, this paper proposes a new clustering validity function, which is defined as Equation (16): $V_{HY} = \frac{comp}{sep}$ (16) where comp is the intra-class compactness, sep is the inter-class separation. comp is defined as Equation (17) sep is defined as Equation (18) $\begin{matrix} comp = \sum_{i = 1}^{c} \sum_{j = 1}^{n} u_{ij}^{m} {∥ x_{j} - v_{i} ∥}^{2} + \\ \frac{1}{c} \sum_{i = 1}^{c - 1} \sum_{k = i + 1}^{c} [\frac{1}{n} \sum_{j = 1}^{n} \min (u_{ij}, u_{kj})] \end{matrix}$ (17) $sep = min_{1 ⩽ i ⩽ c} \sum_{j = 1}^{n} u_{ij}^{m} + min_{i \neq k} {∥ v_{i} - v_{k} ∥}^{2}$ (18)

In the comp of V_HY the $\sum_{i = 1}^{c} \sum_{j = 1}^{n} u_{ij}^{m} {∥ x_{j} - v_{i} ∥}^{2}$ represents the distance between the cluster center v_i and the data samplex_j. The smaller value of ∥x_j - v_i ∥ ², the more x_j is similar to the v_i. The second term of the comp, $\frac{1}{c} \sum_{i = 1}^{c - 1} \sum_{k = i + 1}^{c} [\frac{1}{n} \sum_{j = 1}^{n} min (u_{ij}, u_{kj})]$ represents the degree of similarity between class i and class k. If x_j is infinitely close to v_i, u_ij is close to 1 and u_kj is close to 0. So min(u_ij, u_kj) infinite close to 0, it is proved that there is a good separation between class i and class k. It also shows that the x_j in the same classes are more compact Therefore the IAC gets the minimum value to indicate that the classification is the best.

In the sep of V_HY, the $min_{1 ⩽ i ⩽ c} \sum_{j = 1}^{n} u_{ij}^{m}$ represents that the x_j is the membership of the cluster center v_i. The maximum membership value indicates the more compact within the class i. If the minimum of the membership is large, it will prove that all of the classes is compact. The second term of the sep $min_{i \neq k} {∥ v_{i} - v_{k} ∥}^{m}$ represents the distance between two cluster centers v_i and v_k. The largest value represents the better separate between v_i and v_k. If the minimum of the ∥v_i - v_k ∥ ² is large, it will prove the class between the i and k is well separated Therefore the minimum value of V_HY represents the optimal number of clustering.

Apply V_HY to the FCM clustering algorithm, and the algorithm procedure is shown in Fig. 1. Based on V_HY, the FCM clustering algorithm procedure is described as follows.

Fig. 1

Fowchart of FCM clustering algorithm based on V_HY.

Step 1: Determine the maximum number of clustering of c_max( $c_{\max} ⩽ \sqrt{n}$ ) the maximum iteration times I_max, the fuzzy weighted index c and the termination threshold ɛ .

Step 2: According to the c = [2, c_max], initialize the number of clustering and the cluster center V^(γ+1).

Step 3: Update the fuzzy partitioning matrix U^(γ+1) and cluster center. Judge whether the ∥V_t+1 - V_t∥ is smaller than the ɛ. If ∥V_t+1 - V ∥ _t < ɛ, go to the next step, otherwise continue Step 3.

Step 4: Let c increase by 1, the FCM algorithm is called to obtain the optimal solution, and calculate the value of V_HY. Judge whether the c is smaller than the c_max. If c < c_max, go to Step 2, otherwise go to the next step.

Step 5: Select the minimum value of V_HY index, that is to say min{ V_HY (U, V, c) }, whichis corresponding to the clustering number c_b for optimal clustering number. Output the value of V_HY.

4 Simulation experiments and results analysis

4.1 Test data sets

The selected experimental data sets are divided into four artificial data sets and six UCI data sets, as listed in Table 1. In the artificial data sets, Data_2_3 is a set of two-dimensional three-class data set with clear classification according to Gauss distribution. Data_2_3(Noise) is a two-dimensional three-class data set in which 100 noise data are added into Data_2_3. Data_2_3(overlap) is a set of data sets with overlapping data from one class to another. Data_3_6 is a data set of three-dimensional six-class that are uniformly distributed. The sample distribution of artificial data set is shown in Fig. 2.

Table 1
Experimental data set

Data Data numbers Attributes Classes

Data_2_3 300 2 3

Data_2_3(noise) 400 2 3

Data_2_3(overlap) 300 2 3

Data_3_6 600 3 6

Iris

Seeds 210 7 3

Heart 270 13 2

WPBC 198 34 2

Segment 2310 19 7

Phoneme 5404 5 2

Data	Data numbers	Attributes	Classes
Data_2_3	300	2	3
Data_2_3(noise)	400	2	3
Data_2_3(overlap)	300	2	3
Data_3_6	600	3	6
Iris
Seeds	210	7	3
Heart	270	13	2
WPBC	198	34	2
Segment	2310	19	7
Phoneme	5404	5	2

Fig. 2

Artificial data sets.

The datasets selected from UCI database. Iris dataset contains 3 classes of 50 instances each, where each class refers to a type of iris plant. One class is linearly separable from the other two; the latter are not linearly separable from each other. Seeds dataset comprised kernels belonging to three different varieties of wheat: Kama, Rosa and Canadian, 70 elements each, randomly selected for the experiment. Heart dataset is a heart disease database similar to a database already present in the repository (Heart Disease databases) but in a slightly different form. WPBC dataset is about Wisconsin Prognostic Breast Cancer. Segment dataset an image data described by high-level numeric-valued attributes with 7 classes. Phoneme dataset was in use in the European ESPRIT 5516 project: ROARS. The aim of this project is the development and the implementation of a real time analytical system for French and Spannish speech recognition. The detail number of attributes, samples and classes of UCI data sets are listed in Table 1.

Seven kinds of typical clustering validity functions (V_MPC, V_SC, V_P, V_XB, V_K, V_PCAES, V_Z) were selected to carry out the compare experiments to verify the validity of V_HY. According to the experience knowledge [23], the value of the fuzzy weighted value index m range is 1.5 ⩽ m ⩽ 2.5, the number of clustering c range is $2 ⩽ c ⩽ \sqrt{n}$ . In this paper, Select m = 2and 2 ⩽ c ⩽ 14 to carry out the experiments, then observe the accuracy of each clustering validity function to find the optimal clustering number when different data sets are selected. Finally, change the value of m to observe whether V_HY is robust.

4.2 Cluster effectiveness simulation experiments and result analysis

Before the comparative test, the feasibility of V_HY was judged by observing the changing trend of comp and sep. The results are shown in Fig. 3. It can be seen from the Fig. 3(a)-(b) that under the condition of Data_2_3, comp and sep change greatly when c = 2, 3, 4. When c = 3, the comp and sep decrease rapidly, and the comp is smaller than the sep, so that V_HY reaches the minimum. It can be seen from the Fig. 3(c)-(d) that under the condition of iris dataset, After c = 4, the change range of the comp and sep are very slow, and presents a decreasing trend, the comp value is always greater than the value of the sep, so when c = 3, the change trend of the comp and sep are the largest, so it can get that the minimum value of V_HY is c = 3, and the number of iris optimal clusters is c = 3.

Fig. 3

The varying trends of V_HY, comp and sep.

Simulation results for artificial data sets (Data_2_3, Data_2_3(noise), Data_2_3(overlap) and Data_3_6) are shown in Fig. 4–7. It can be seen from Fig. 4(a)–(i) that for the clearly divided data set Data_2_3, the optimal number of clustering can be found for V_MPC, V_P, V_XB, V_K, V_Z and V_HY. Figure 5(a)–(i) shows that under the influence of noisy data, the optimal clustering number c = 3 can be obtained by V_P, V_XB, V_K, V_Z and V_HY. Figure 6(a)–(i) shows that in the case of overlap of samples in Data_2_3(overlap) data set, only V_MPC and V_HY found the optimal clustering number c = 3. Figure 7(a)–(i) shows that V_MPC, V_P, V_XB, V_K, V_Z and V_HY can found the optimal number of clustering c = 3 when data set dimensions are added. The simulation results on artificial data sets show that only V_HY can find the optimal clustering number of all four artificial data sets. V_P, V_XB, V_K and V_Z can find the optimal clustering number of three data sets. V_MPC can find the optimal clustering number of two data sets. V_PCAES, V_SC and V_ECScannot find the optimal clustering number.

Fig. 4

The varying trends of validity indices on Data_2_3 data set.

Fig. 5

The varying trends of validity indices on Data_2_3(noise) data set.

Fig. 6

The varying trends of validity indices on Data_2_3(overlap) data set.

Fig. 7

The varying trends of validity indices on Data_3_6 data set.

These shows that the validity of V_HY is better than that of these typical clustering validity functions. In addition, V_HY is less affected by noise and overlapping data in the data set. The structure and sample size of artificial data set are relatively simple. In order to verify the clustering validity of V_HY in complex data sets, simulation experiments are carried out on UCI data set.

The simulation results for the UCI data sets (Iris, Seeds, Heart, WPBC, Segment and Phoneme) are shown in Fig. 8–13. It can be seen from Fig. 8(a)–(i) that only V_HY can get the optimal number of cluster c = 3. The second dimension and the third dimension of Iris data set have high similarity, so V_P, V_SC, V_XB, V_K, V_Z V_ECS can only get the optimal number of clustering c = 2, indicating that V_HY can well cluster overlapping data. It can be seen from Fig. 9(a)–(i) that for Seeds data set, V_P andV_HY get the optimal number of clustering c = 3. Figure 10(a)–(i) shows that for Heart data set, V_P, V_SC, V_XB, V_K, V_Z, V_ECS and V_HY can obtain the optimal number of clustering c = 2. Figure 11 shows that V_SC, V_P, V_PCAES, V_ECS and V_HY can obtain the optimal number of clustering c = 2 for WPBC data set. According to the simulation results shown in Fig. 9–11, it can be found that when processing the data set of Seeds, Heart and WPBC with higher dimension, only V_p and V_HY can get the optimal number of clustering. It shows that V_P and V_HY can find the optimal clustering number better than other typical clustering validity functions in the case of data sets with high dimension. Figures 12 and 13 simulate Segment and Phoneme data set, and only V_HY can get the optimal clustering number c = 2. Segment and Phoneme have higher number of data samples and dimensions, indicating that V_HY clustering effect is significantly better than V_MPC, V_SC, V_P, V_XB, V_K, V_PCAES and V_Z when the number and dimension of data sets are relatively higher. It can be seen from the simulation results in Figs. 8–13 that only V_HY can find the optimal clustering number of all real data sets. On the other hand, V_HY can still find the optimal number of clustering in the data set with overlapped samples, higher dimensions and larger number of sample.

Fig. 8

The varying trends of validity indices on Iris data set.

Fig. 9

The varying trends of validity indices on Seeds data set.

Fig. 10

The varying trends of validity indices on Heart data set.

Fig. 11

The varying trends of validity indices on WPBC data set.

Fig. 12

The varying trends of validity indices on Phoneme data set.

Fig. 13

The varying trends of validity indices on Segment data set.

The simulation results of V_MPC, V_SC, V_P, V_XB, V_K, V_PCAES, V_Z, V_ECS and V_HY in the artificial data set and UCI data set respectively show that V_HY is obviously superior to V_MPC, V_SC, V_P, V_XB, V_K, V_PCAES, V_ECS and V_Z in finding the optimal number of clustering. In order to clear out V_HY clustering validity of observations is superior to other traditional clustering validity function, the clustering validity function values under different data sets based on V_MPC, V_p, V_SC, V_XB, V_K, V_Z, V_PCAES, V_ECS and V_HY shown in Figs. 4–13 are normalized and shown in Fig. 14(a)–(j) in the same coordinate system.

Fig. 14

Comparison of clustering validity functions after normalization.

The optimal clustering number under different clustering validity functions are listed in Table 2. The time used to simulate the data set is shown in Table 2 by combining the cluster effectiveness function and FCM algorithm respectively. Table 2 data unit is second. From the four experiments, it can be found that the computing time of V_HY is shorter than some traditional clustering functions. The optimal clustering number under different clustering validity functions are listed in Table 3.

Table 2

The calculation time of different clustering effectiveness functions

Data	V _MPC	V _SC	V _XB	V _P	V _K	V _PCAES	V _Z	V _ECS	V _HY
Data_2_3	1.168325	0.802044	0.734430	0.719251	0.785017	0.710793	0.678986	0.702661	0.658120
Data_3_6	2.089145	0.899391	1.054201	0.911183	1.029304	0.966372	1.031130	1.072874	1.051658
Iris	0.605263	0.492917	0.479303	0.456325	0.540419	0.462467	0.440059	0.512592	0.481719
Segment	3.902832	3.856291	3.853804	3.872426	3.888810	3.888275	3.859189	3.858039	3.862162

Table 3

Optimal clustering results of different clustering validity functions on different data sets

Data	Optimal c	V _MPC	V _SC	V _XB	V _P	V _K	V _PCAES	V _ECS	V _Z	V _HY
Data_2_3	3	3	2	3	3	3	14	2	3	3
Data_2_3(noise)	3	4	2	3	3	3	14	2	3	3
Data_2_3(overlap)	3	3	2	2	2	2	13	2	2	3
Data_3_6	6	6	2	6	6	6	9	2	6	6
Iris	3	4	2	2	2	2	10	2	2	3
Seeds	3	3	2	2	2	2	10	2	2	3
Heart	2	3	2	2	2	2	7	2	2	2
WPBC	2	3	2	7	2	7	2	2	7	2
Phoneme	2	4	2	4	4	4	14	2	4	2
Segment	7	3	2	2	3	2	13	2	2	7

4.3 Robustness verification of clustering validity functions under different fuzzy weighted index

m is the fuzzy weighted index, and the introduction of m extends the hard clustering division into the fuzzy clustering division. According to the previous experiences, the value range of m is 1.5 < m ⩽ 2.5. In this simulation experiments, select V_MPC, V_SC, V_XB, V_P, V_K, V_PCAES, V_Z, V_HY and m = 1.2, 1.5, 2.0, 3.0, 5.0, then carry out simulation experiments on the data sets listed in Table 1. The simulation results are listed in Tables 4 and 5.

Table 4
Imapct of different m values on each index by using manual datasets

Data m Optimal c Validity index

V _MPC V _SC V _XB V _P V _K V _PCAES V _Z V _HY

Data_2_3 1.2 3 14 2 3 3 3 13 3 3

1.5 3 7 2 3 3 3 7 3 3

2.0 3 3 2 3 3 3 14 3 3

3.0 3 3 2 3 3 3 4 3 3

5.0 3 3 2 3 3 3 10 2 3

Data_2_3(noise) 1.2 3 14 2 3 3 3 6 3 3

1.5 3 4 2 3 3 3 12 3 3

2.0 3 5 2 3 3 3 12 3 3

3.0 3 3 2 3 3 3 5 3 3

5.0 3 3 2 3 3 3 12 2 3

Data_2_3(overlap) 1.2 3 14 2 2 2 2 12 2 3

1.5 3 12 2 2 2 2 11 2 3

2.0 3 3 2 2 2 2 13 2 3

3.0 3 3 2 2 2 2 13 2 2

5.0 3 3 2 2 2 2 13 2 2

Data_3_6 1.2 6 8 3 4 4 4 14 4 5

1.5 6 6 2 4 6 4 9 4 6

2.0 6 6 2 6 6 6 8 6 6

3.0 6 6 2 6 6 6 12 6 6

5.0 6 3 2 11 6 11 11 11 6

Data	m	Optimal c	Validity index
Data_2_3	1.2	3	14	2	3	3	3	13	3	3
	1.5	3	7	2	3	3	3	7	3	3
	2.0	3	3	2	3	3	3	14	3	3
	3.0	3	3	2	3	3	3	4	3	3
	5.0	3	3	2	3	3	3	10	2	3
Data_2_3(noise)	1.2	3	14	2	3	3	3	6	3	3
	1.5	3	4	2	3	3	3	12	3	3
	2.0	3	5	2	3	3	3	12	3	3
	3.0	3	3	2	3	3	3	5	3	3
	5.0	3	3	2	3	3	3	12	2	3
Data_2_3(overlap)	1.2	3	14	2	2	2	2	12	2	3
	1.5	3	12	2	2	2	2	11	2	3
	2.0	3	3	2	2	2	2	13	2	3
	3.0	3	3	2	2	2	2	13	2	2
	5.0	3	3	2	2	2	2	13	2	2
Data_3_6	1.2	6	8	3	4	4	4	14	4	5
	1.5	6	6	2	4	6	4	9	4	6
	2.0	6	6	2	6	6	6	8	6	6
	3.0	6	6	2	6	6	6	12	6	6
	5.0	6	3	2	11	6	11	11	11	6

Table 5

Imapct of different m values on each index by using UCI datasets

Data	m	Optimal c	Validity index
			V _MPC	V _SC	V _XB	V _P	V _K	V _PCAES	V _Z	V _HY
Iris	1.2	3	9	2	2	2	2	11	2	3
	1.5	3	8	3	2	2	2	8	2	3
	2.0	3	4	2	2	2	2	10	2	3
	3.0	3	3	2	2	2	10	9	2	2
	5.0	3	3	2	11	2	11	13	11	2
Seeds	1.2	3	11	2	2	2	2	14	11	3
	1.5	3	8	2	2	3	2	10	2	3
	2.0	3	3	2	2	3	2	11	2	3
	3.0	3	3	2	2	2	2	7	2	2
	5.0	3	3	2	2	2	2	11	2	2
Heart	1.2	2	11	2	2	2	2	13	13	2
	1.5	2	6	2	2	2	2	6	12	2
	2.0	2	3	2	2	2	2	7	2	2
	3.0	2	3	2	8	2	8	11	8	2
	5.0	2	3	2	12	2	12	14	12	2
WPBC	1.2	2	9	2	3	3	5	11	5	2
	1.5	2	4	2	9	2	9	14	9	2
	2.0	2	3	2	2	2	2	2	2	2
	3.0	2	3	2	5	11	5	2	8	2
	5.0	2	3	2	14	11	14	2	14	3
Phoneme	1.2	2	12	2	4	6	4	13	6	2
	1.5	2	8	2	4	8	4	14	8	2
	2.0	2	4	2	4	4	4	9	4	2
	3.0	2	4	2	10	4	10	14	10	2
	5.0	2	3	2	2	5	5	2	2	2
Segment	1.2	7	11	2	2	2	2	13	12	2
	1.5	7	11	2	2	2	2	13	11	2
	2.0	7	3	2	7	3	2	8	2	7
	3.0	7	3	2	Invalid	3	Invalid	11	Invalid	3
	5.0	7	3	2	Invalid	10	Invalid	13	Invalid	2

The simulation results on Data_2_3 and Data_2_3(noise) are shown that the change of m value has no influence on V_SC, V_XB, V_P, V_K and V_HY, but has little influence on V_Z and V_MPC, while has great influence on V_PCAES. Only m = 5, V_Z cannot find the optimal cluster number, and V_MPC cannot find the optimal cluster number when m = 1.2 and 1.5. However, since V_SC is a monotone function, the effect of changing m value on V_SC is not representative. Data_2_3(overlap) results show that only V_HY and V_MPC can find the correct number of clustering when changing the value of m, but V_HY misdetermines the clustering result as c = 2 when m = 3.0 and 5.0; V_MPC misdetermines the clustering result as c = 14 and 12 when m = 1.2 and 1.5, indicating that V_HY has better stability than V_MPC. The results of Data_3_6 show that the optimal clustering can be found in V_MPC, V_XB, V_P, V_K, V_Z and V_HY under the condition of changing m, but only V_HY can find the optimal clustering number in m =1.5, 2.0, 3.0 and 5.0, while V_MPC, V_XB, V_P, V_K, V_Z and V_HY can only find the optimal clustering number in part of m values, while V_PCAES and V_SC cannot find the optimal clustering number.

Simulation results on Iris data set show that only V_HY and V_MPC can find partially correct clustering number when changing the value of m, but V_HY can find the optimal clustering number at m = 1.2, 1.5 and 2.0, while V_MPC can only find the optimal clustering number at m = 3.0 and 5.0. The result on Seeds dataset shows that V_MPC, V_P and V_HY can find partially correct number of clustering. The accuracy of V_MPC and V_HY is higher than V_P. V_HY has a small change under the influence of m, while V_MPC has a big change under the influence of V_MPC. Heart results show that the optimal number of clustering can be found under different values of m for both V_HY and V_P, while V_XB, V_K and V_Z can only be found under partial values of m. The results of WPBC show that V_XB, V_PCAES, V_P, V_K, V_Z and V_HY can find part of the optimal clustering number c = 2, but V_HY has a higher accuracy rate than V_XB, V_PCAES, V_P, V_K and V_Z. The simulation results on Phoneme data set show that the optimal number of clusters c = 2 can be found by V_HY under different values of m. The simulation results on Segment data set show that the optimal number of clusters can be found only by V_HY and V_XB in the case of m =2.0, and even in the case of m =3.0 and 5.0, V_XB, V_K adn V_Z are invalid, that is to say that the minimum value cannot be found.

Therefore, the experimental results show that the proposed clustering validity function V_HY under different values of m is more accurate, reliable and robust to the optimal number of clustering.

5 Conclusion

Aiming at the defects of existing validity functions, this paper proposes a new clustering validity function V_HY, and carries out simulation experiments on four artificial data sets and six UCI data sets. The experimental results show that the V_HY index can be used to find the optimal clustering number in the case of noise, data overlap between classes, high-dimensional data and large data samples, and V_HY does not change significantly with the change of fuzzy weighted index m so as to show the good robustness.

Due to the endless emergence of data sets, it is impossible to correctly evaluate the validity of data only by relying on one clustering validity function. Moreover, in the process of research, the structure of validity function becomes more and more complex and the amount of calculation becomes larger and larger. For this reason, V_HY is not applicable to all datasets, and the complex calculation process is also difficult to understand. Therefore, in the future research process, the combined clustering validity function will be studied in depth, though absorbing the advantages of each validity function, a more accurate validity evaluation method is obtained.

References

Liang

S.Y.

and Han

D.Q.

, and Y, Yang, Cluster validity index for irregular clustering results, Applied Soft Computing 95 (2020), 106583.

Gargiulo

, Silvestri

and Ciampi

, A clustering based methodology to support the translation of medical specifications to software models, Applied Soft Computing 71 (2018), 199–212.

Zalik

K.R.

, Cluster validity index for estimation of fuzzy clusters of different, Pattern Recognition 43(10) (2010), 3374–3390.

Hartigan

J.A.

and Wong

M.A.

, Algorithm AS 136: A k-means clustering algorithm, Journal of the royal statistical society. series c (applied statistics), 28(1) (1979), 100–108.

Ruspini

E.H.

, A new approach to clustering, Information and Controll 15(1) (1969), 22–33.

Bezdek

J.C.

, Ehrlich

and Full

, FCM: The fuzzy c-means clustering algorithm, Computers & Geosciences 10(2-3) (1984), 191–203.

Ghosh

and Dubey

S.K.

, Comparative analysis of k-means and fuzzy c-means algorithms, International Journal of Advanced Computer Science and Applications 4(4) (2013).

Bezdek

J.C.

, Moshtaghi

and Runkler

, The generalized C index for internal fuzzy cluster validity, IEEE Trans on Fuzzy Systems 24(6) (2016), 1500–1512.

Zadeh.

L.A.

, Fuzzy sets as a basis for a theory of possibility, Fuzzy sets and systems 1(1) (1978), 3–28.

10.

Bezdek

J.C.

and Pal

N.R.

, Some New Indexes of Cluster Validity, IEEE Transactions on System, Man and Cybernetics 28(Part B) (1998), 301–315.

11.

Simovici

D.A.

and Jaroszewicz

, An axiomatization of partition entropy, IEEE Transactions on Information Theory 48(7) (2002), 2138–2142.

12.

Silva

, An interval-based framework for fuzzy clustering applications, IEEE Trans on System 23(6) (2015), 2174–2187.

13.

Chen

M.Y.

and Linkens

D.A.

, Rule-base self-generation and simplification for data-driven fuzzy models, Fuzzy Sets and sms 142(2) (2004), 243–265.

14.

Xie

L.X.

and Beni

G.A.

, A validity measure for fuzzy clustering, IEEE Transactions on Pattern Analysis and Machine Intelligence 13(8) (1991), 841–847.

15.

Fukuyama

and Sugeno

, A new method of choosing the number of clusters for the fuzzy c-means method, 5th Fuzzy Systems Symposium (1989), 247–250.

16.

Kwon

S.H.

, Cluster validity index for fuzzy clustering, Electronics Letters 34(22) (1998), 2176–2177.

17.

Bensaid

A.M.

, Hall

L.O.

, Bezdek

J.C.

, Clarke

L.P.

, Silbiger

M.L.

and Arrington

J.A.

, Validity-guided (re) clustering with applications to image segmentation, IEEE Transactions on Fuzzy Systems 4(2) (1996), 112–123.

18.

K.L.

and Yang

M.S.

, A cluster validity index for fuzzy clustering, Pattern Recognition Letters 26(9) (2005), 1275–1291.

19.

Wang

, A new clustering validity function for the fuzzy C-means algorithm, Proc Control Decis Conf 6 (2008), 2477–2480.

20.

Zhu

L.F.

, Wang

J.S.

and Wang

H.Y.

, A novel clustering validity function of FCM clustering algorithm, IEEE Access 7(2019), 152289–152315.

21.

Liu

, A new robust fuzzy clustering validity index for imbalanced data sets, Information Sciences 547 (2021), 579–591.

22.

Renjit

2019 Fifth International Conference on Science Technology Engineering and Mathematics, IEEE (2019), 49–54 An intelligent subtype fuzzy cluster based relevant user data retrieval model for effective classification,.

23.

Rezaee

, A cluster validity index for fuzzy clustering, Fuzzy sets and systems 161(23) (2010), 3014–3025.

24.

Haouas

2017 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE), IEEE (2017), 1–6 A new efficient fuzzy cluster validity index: Application to images clustering,.

25.

Ouchicha

, Ammor

and Meknassi

, A new validity index in overlapping clusters for medical image, Automatic Control and Computer Sciences 54(3) (2020), 238–248.

A new validity function of FCM clustering algorithm based on intra-class compactness and inter-class separation

Abstract

Keywords

1 Introduction

2 FCM Clustering algorithm and typical clustering validity functions

2.1 FCM clustering algorithm

2.2.1 Partition coefficient (V PC ) [10]

4.1 Test data sets

Table 1 Experimental data set Data Data numbers Attributes Classes Data_2_3 300 2 3 Data_2_3(noise) 400 2 3 Data_2_3(overlap) 300 2 3 Data_3_6 600 3 6 Iris Seeds 210 7 3 Heart 270 13 2 WPBC 198 34 2 Segment 2310 19 7 Phoneme 5404 5 2

References

2.2.1 Partition coefficient (V_PC) [10]

Table 1
Experimental data set

Data Data numbers Attributes Classes

Data_2_3 300 2 3

Data_2_3(noise) 400 2 3

Data_2_3(overlap) 300 2 3

Data_3_6 600 3 6

Iris

Seeds 210 7 3

Heart 270 13 2

WPBC 198 34 2

Segment 2310 19 7

Phoneme 5404 5 2