Feature reduction fuzzy C-Means algorithm leveraging the marginal kurtosis measure

The feature reduction fuzzy c-means (FRFCM) algorithm has been proven to be effective for clustering data with redundant/unimportant feature(s). However, the FRFCM algorithm still has the following disadvantages. 1) The FRFCM uses the mean-to-variance-ratio (MVR) index to measure the feature importance of a dataset, but this index is affected by data normalization, i.e., a large MVR value of original feature(s) may become small if the data are normalized, and vice versa. Moreover, the MVR value(s) of the important feature(s) of a dataset may not necessarily be large. 2) The feature weights obtained by the FRFCM are sensitive to the initial cluster centers and initial feature weights. 3) The FRFCM algorithm may be unable to assign the proper weights to the features of a dataset. Thus, in the feature reduction learning process, important features may be discarded, but unimportant features may be retained. These disadvantages can cause the FRFCM algorithm to discard important feature components. In addition, the threshold for the selection of the important feature(s) of the FRFCM may not be easy to determine. To mitigate the disadvantages of the FRFCM algorithm, we first devise a new index, named the marginal kurtosis measure (MKM), to measure the importance of each feature in a dataset. Then, a novel and robust feature reduction fuzzy c-means clustering algorithm called the FRFCM-MKM, which incorporates the marginal kurtosis measure into the FRFCM, is proposed. Furthermore, an accurate threshold is introduced to select important feature(s) and discard unimportant feature(s). Experiments on synthetic and real-world datasets demonstrate that the FRFCM-MKM is effective and efficient.

Keywords: Fuzzy c-means; feature reduction learning; marginal kurtosis measure; mean-to-variance ratio

AS a data-driven technique for data analysis, clustering has been widely used in research fields such as statistics, pattern recognition and machine learning. Given a dataset X consisting of data points xi where i  = 1, 2,. . . , n, clustering algorithms aim to group X into k clusters S ={ S1, S2,. . . , Sk } such that the data points x i  ∈ Sk have the highest similarity and the data points between different clusters have the highest dissimilarity. Perhaps two of the most well-known partition-based clustering algorithms are the k-means [[1]] and the fuzzy c-means (FCM) [[2]], and the latter is a generalization of the former. The k-means is known for its simplicity, and the FCM remains popular due to its capability to express the data points that belong to more than one cluster. They have been widely studied and applied in many areas [[4], [6]]. However, the k-means and FCM do not take the feature importance into account, and they cluster data using equal feature weights without considering the structure of the data. That is, the features that are important or less important may make the same contribution to the clustering. As a result, their clustering performance will be affected by the existence of unimportant feature(s) or redundant feature(s), which may cause the k-means and FCM to produce incorrect clustering results and significantly degrade the clustering performance in some applications [[7]].

To overcome these shortcomings, feature weighting and feature selection techniques are used in the traditional k-means and FCM. Feature selection techniques assume that each of the selected features has the same degree of importance. The feature weighting method is an extension of the former and makes feature weights take values in the interval of [0,1]; the more important a feature is, the larger the weight should be.

Feature weighting is an important technique, which can be found in many literatures [[8]]. In clustering analysis, some variants of the k-means and FCM have been presented, such as the weighted k-means (WKM) [[9]]; the entropy-weighted k-means (EWKM) [[10]]; the Minkowski weighted k-means (MWKM) [[11]]; the Minkowski metric fuzzy weighted c-means (MWFCM) [[12]]; the weighted FCM using feature-weight learning (WFCM) [[13]]; the two version of feature-weighted FCM, which is called simultaneous clustering and attribute discrimination (SCAD1 & SCAD2) [[14]]; and the enhanced soft subspace clustering (ESSC) [[15]] algorithm, which can be referred to as an extension of conventional feature weighting clustering. By using a feature weighting technique in the k-means or FCM, the performance may be improved. However, these algorithms do not have a mechanism to remove unimportant features in the clustering process, except for the FRFCM [[16]] that uses feature reduction techniques. As a pioneer work of feature reduction methods, the FRFCM algorithm uses the mean-to-variance-ratio (MVR) to measure the feature importance and integrate it into the objective function to control the within cluster dispersion term and the entropy term. The feature reduction technique is also introduced to the multi-view k-means clustering [[17]] algorithm. Subsequently, this feature reduction learning method is extended to feature-weighted possibilistic c-means clustering [[18]].

The main contributions of this paper are as follows: (1) an MKM index is proposed to measure the feature importance, (2) a new and robust feature reduction fuzzy clustering algorithm is proposed to cluster high dimension data, and (3) a threshold with a theoretical basis is designed to determine which features need to be retained and which features need to be deleted in the clustering process.

The rest of the paper is organized as follows. Section 2 first introduces the feature-weighted k-means and feature-weighted FCM clustering algorithms used in the present work, and then introduces feature reduction fuzzy c-means clustering in detail. Section 3 introduces the techniques of the proposed algorithm, its convergence proof, and complexity analysis. Section 4 presents the results of the experiment, and, finally, Section 5 presents the conclusion and ideas for future work.

In this section, we provide a review of the literature on feature weighted clustering methods including the FRFCM. The commonalities and characteristics of each algorithm are discussed.

A. Feature Weighting using K-Means

Huang et al. [[9]] proposed the WKM algorithm which has the following objective function:

(1) $\begin{array}{c}\hfill J\left(\text{U},\text{V},\text{w}\right)=\sum _{i=1}^n\sum _{k=1}^c{\mu }_{\mathit{ik}}\sum _{j=1}^d{w}_j^{\beta }{\left(x_{\mathit{ij}}-v_{\mathit{jk}}\right)}^2\hfill \\ \hfill s.t.\sum _{j=1}^d{w}_j=1,\sum _{k=1}^c{\mu }_{\mathit{ik}}=1,{\mu }_{\mathit{ik}}\in \left\{0,1\right\}.\hfill \\ \hfill \hfill \end{array}$

In its implementation, it adds an extra step to the basic k-means to determine the feature weights of each iteration in the k-means clustering process. The weight of each feature is inversely proportional to the sum of the variances within the feature cluster. Therefore, unimportant features can be identified, and the influence of unimportant features on the clustering result is significantly reduced, which can improve the clustering accuracy and performance. However, the WKM requires the user to subjectively specify an additional parameter, i.e., the index of the feature weights. Therefore, it is difficult for users to determine an appropriate value for this parameter to obtain a desired quality clustering result. In addition, the feature weights generated using this method may not represent the feature importance well [[19]].

Jing et al. [[10]] proposed the entropy weighting K-means method EWKM, which is developed as a subspace clustering technique, and particularly useful for high-dimensional sparse data since it uses using feature weighting methods. The EWKM minimizes the differences within the cluster and maximizes the negative entropy. The reason behind this is that it uses more dimensions to identify clusters of high-dimensional sparse data, avoiding problems related to identifying such clusters using only a few dimensions. The EWKM has the following objective function:

(2) $\begin{array}{c}\hfill J\left(\text{U},\text{V},\text{w}\right)=\sum _{k=1}^c[\sum _{i=1}^n\sum _{j=1}^d{\mu }_{\mathit{ik}}{w}_{\mathit{kj}}{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2\hfill \\ \hfill +\gamma \sum _{j=1}^d{w}_{\mathit{kj}}log{w}_{\mathit{kj}}]\hfill \\ \hfill s.t.\sum _{j=1}^d{w}_{\mathit{kj}}=1,\left\{w_{\mathit{kj}}\right\}⩾0,\left\{w_{\mathit{kj}}\right\}⩾0.\hfill \\ \hfill \hfill \end{array}$

In its implementation, it extends the standard k-means algorithm with an additional step to calculate the feature weight of each cluster in each iteration of the clustering process. The weight is inversely proportional to the sum of the intra-cluster variances of the variables in the cluster. Because the EWKM requires many calculations, it is very time-consuming.

B. Feature Weighting in Fuzzy clustering

WFCM was proposed by Wang et al. [[13]] to improve the performance of the FCM. The WFCM attempts to minimize the following objective function:

(3) $J\left(\text{U},\text{V},\text{w}\right)=\sum _{i=1}^n\sum _{k=1}^c{\mu }_{\mathit{ij}}^m\sum _{j=1}^d{w}_j^2{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2$

where wj is a feature weight calculated by the algorithm proposed by Yeung and Wang [[21]].

SCAD2 was proposed by Frigui and Nasraoui [[14]] by using a central weighing scheme. The objective function of SCAD2 is as follows.

(4) $J\left(\text{U},\text{V},\text{w}\right)=\sum _{j=1}^k\sum _{i=1}^n\sum _{l=1}^p{\mu }_{\mathit{ij}}^m{w}_{\mathit{jl}}^q{\left(x_{\mathit{ij}}-v_{\mathit{jl}}\right)}^2$

In SCAD2, the feature weights produced by it do not properly represent the importance of the features in the clusters in some situations [[22]].

By using the between-cluster information of the dataset, Deng et al. [[15]] proposed ESSC algorithm. The ESSC uses the following objective function:

(5) $\begin{array}{c}\hfill J\left(\text{U},\text{V},\text{W}\right)=\sum _{k=1}^c\sum _{i=1}^n{\mu }_{\mathit{ik}}^m\sum _{j=1}^d{w}_{\mathit{kj}}{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2\hfill \\ \hfill +\gamma \sum _{k=1}^c\sum _{j=1}^d{w}_{\mathit{kj}}ln{w}_{\mathit{kj}}-\eta \sum _{k=1}^c\sum _{i=1}^n{\mu }_{\mathit{ik}}^m\sum _{j=1}^d{w}_{\mathit{kj}}{\left(v_{\mathit{kj}}-v_{0j}\right)}^2\hfill \\ \hfill \hfill \end{array}$

where v0j denotes the jth feature of the center of the whole dataset and ${\sum }_{k=1}^c{\sum }_{i=1}^n{\mu }_{\mathit{ik}}^m{\sum }_{j=1}^d{w}_{\mathit{kj}}{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2$ is the within cluster dispersion. The ESSC algorithm minimizes the within cluster dispersion and maximizes the negative entropy, and meanwhile minimizes the weighted distance between cluster centers and data center. The obtained feature weights also do not well represent the feature importance of the clusters for some datasets.

C. Fuzzy C lustering With Feature Reduction Schema

As a pioneer work on feature reduction learning algorithms, Yang et al [[16]] developed a fuzzy clustering algorithm named the FRFCM, which uses the feature-weighted entropy with a feature reduction scheme to cluster data. Their proposed algorithm uses the mean-to-variance-ratio (MVR) index to measure the feature importance of a dataset, and then the MVR index is integrated into the objective function to control the within cluster weighted feature dispersion term and entropy term. By calculating the feature weight using an updating equation, the FRFCM sets a threshold to discard feature(s) with small weight(s) less than it. After reducing the unimportant features from data, the FRFCM can improve the accuracy of the clustering algorithm and speed up the clustering process. The objective function of the FRFCM algorithm is given as follows:

(6) $\begin{array}{cc}\hfill \underset{\text{U},\text{V},\text{w}}{min}J\left(\text{U},\text{V},\text{w}\right)=& \sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m\sum _{j=1}^d{\delta }_j{w}_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2\hfill \\ \hfill & +\frac{n}{c}\sum _{j=1}^d{\left(w_{j}log{\delta }_j{w}_j\right)}^2\hfill \end{array}$

subject to

$\sum _{k=1}^c{u}_{\mathit{ik}}=1,\sum _{j=1}^d{w}_j=1,\forall j=1,...,n.$

where ${\delta }_j={\left(\frac{\mathit{mean}\left(\text{x}\right)}{\mathit{var}\left(\text{x}\right)}\right)}_j,j=1,2,\cdots ,d.$

The iteration formula of wj is as follows:

(7) $w_j=\frac{\frac{1}{{\delta }_j}exp\left(-\frac{c}{n}{\sum }_{k=1}^c{\sum }_{i=1}^n{u}_{\mathit{ik}}^m{\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2\right)}{{\sum }_{t=1}^d\frac{1}{{\delta }_t}exp\left(-\frac{c}{n}{\sum }_{k=1}^c{\sum }_{i=1}^n{u}_{\mathit{ik}}^m{\delta }_t{\left(x_{\mathit{it}}-v_{\mathit{kt}}\right)}^2\right)}$

In Equation (7), since δj is irrelevant to subscripts i and k, it can be modified as follows:

(8) $w_j=\frac{\frac{1}{{\delta }_j}exp\left(-\frac{c}{n}{\delta }_j{\sum }_{k=1}^c{\sum }_{i=1}^n{u}_{\mathit{ik}}^m{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2\right)}{{\sum }_{t=1}^d\frac{1}{{\delta }_t}exp\left(-\frac{c}{n}{\sum }_{k=1}^c{\sum }_{i=1}^n{u}_{\mathit{ik}}^m{\delta }_t{\left(x_{\mathit{it}}-v_{\mathit{kt}}\right)}^2\right)}$

Let $S_j={\sum }_{k=1}^c{\sum }_{i=1}^n{u}_{\mathit{ik}}^m{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2$ , where Sj is the sum of the within-cluster dispersion of the jth feature. Because the denominator is a positive constant, if we denote this constant as Const, then Equation. (7) can be simplified as follows:

(9) $w_j=\frac{1}{{\delta }_j\mathit{Const}}exp\left(-\frac{c}{n}{\delta }_j{S}_j\right)$

Since δj is used to measure the feature importance, the FRFCM should produce a large weight for a feature with a large δj, and the algorithm should retain the feature(s) with large weight(s) in the feature reduction clustering process. However, as can be seen from Equation 9, the updated equation of wj is a function of δj and Sj and can produce a large weight for the jth feature if both δj and Sj are small; it cannot produce a large weight for a large δj unless Sj is small enough. As a consequence, important feature(s) may not be identified by the FRFCM, which make the algorithm incorrectly discard important features from the dataset in the first iteration of the FRFCM. This is one of the shortcomings of the FRFCM algorithm. In addition, the FRFCM still has two other disadvantages. 1) The MVR values for the important feature(s) of some datasets are not necessarily large. For example, the MVR index of the iris dataset is δ = [8 . 522, 16 . 244, 1 . 207, 2 . 058], indicating that the 1st feature and 2nd feature are two important features, yet most feature weighting clustering algorithms consider the 3rd feature and 4th feature as two important features [[16]]. Moreover, the MVR index changes when some data are normalized. A large MVR value may become small and also a small MVR value may become large if the data are normalized. 2) The feature weights obtained by the FRFCM are very sensitive to the initialization. These disadvantages can degrade the performance of the FRFCM.

Next, we propose a novel feature reduction fuzzy c-means clustering algorithm that leverages the marginal kurtosis measure to mitigate the above disadvantages of the FRFCM algorithm.

A. Problem Definition

In data mining and data analysis tasks, if a feature or variable possesses only one mode (Fig. 1 (a)), it is a less important feature or variable. However, if a feature or value has two different modes (Fig. 1 (b)), it remains important for the learning algorithm. Owing to incompetence of the MVR index in [[16]] in measuring feature importance with this distribution, in this paper we devise a new index to measure feature importance.

Graph: Fig. 1 Features of two modal types. (a) Unimodal distribution; (b) bimodal distribution.

Definition 1. Given a dataset X, let η = (X - EX) 2, the marginal kurtosis measure of X is defined as follows:

(10) $\begin{array}{c}\hfill {\delta }_j={\left(\frac{E\eta }{\sqrt{\mathrm{var}\left(\eta \right)}}\right)}_j\hfill \\ \hfill ={\left(\frac{E\left({\left(\text{X}-E\left(\text{X}\right)\right)}^2\right)}{\sqrt{E{\left({\left(\text{X}-E\left(\text{X}\right)\right)}^2-E\left({\left(\text{X}-E\left(\text{X}\right)\right)}^2\right)\right)}^2}}\right)}_j\hfill \\ \hfill ={\left(\frac{E\left({\left(\text{X}-E\left(\text{X}\right)\right)}^2\right)}{\sqrt{E\left({\left(\text{X}-E\left(\text{X}\right)\right)}^4\right)-{\left(E\left({\left(\text{X}-E\left(\text{X}\right)\right)}^2\right)\right)}^2}}\right)}_j\hfill \\ \hfill ={\left(1/\sqrt{\frac{E\left({\left(\text{X}-E\left(\text{X}\right)\right)}^4\right)}{{\left(E\left({\left(\text{X}-E\left(\text{X}\right)\right)}^2\right)\right)}^2}-1}\right)}_j\hfill \\ \hfill ={\left(\frac{1}{\sqrt{\mathrm{kurtosis}\left(\text{X}\right)-1}}\right)}_j\hfill \\ \hfill \hfill \end{array}$

In Equation (10), δj is the mean-to-standard-variance-ratio of η, and it is actually a function of the kurtosis of X. Thus, we name it the marginal kurtosis measure, and denote it as MKM. Compared with the MVR of X, the MKM of X has the property of being unaffected by data normalization.

Next, we use an example to illustrate the advantage of the MKM over the MVR to measure the feature importance.

Example 1. In this example, we produce a synthetic dataset with 400 data points. Component x2 and component x3 of this dataset are generated from a Gaussian mixture model ${\sum }_{k=1}^2{\alpha }_{k}N\left({\mu }_k,{\sum }_k\right)$ with the parameters α1 = α2 = 0.5, ${\sum }_1=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$ and ${\sum }_2=\left(\begin{array}{cc}0.5& 0\\ 0& 0.5\end{array}\right)$ . Components x1 and x4 follow uniform distributions over the interval [0, 4] and the interval [0, 2], respectively. We denote this dataset as D1. The MVR value of the original dataset D1 is δMVR = [1.497, 0.981, 1.089, 3.085]. Since δ1 and δ4 are larger than δ2 and δ3, the 1st feature and 4th feature are considered to be two important features. However, if D1 is normalized, the MVR of D1 becomes δMVR = [5.944, 8.940, 8.906, 6.161], and then the 2nd feature and 3rd feature become important features (Fig. 3). Since the feature importance is an attribute of a dataset, the feature importance should remain unchanged, even if the data are normalized. However, when D1 is normalized, the MVR index of D1 is changed. If the MVR index is used to measure the feature importance, the algorithm actually cannot differentiate the important feature(s).

To present an intuitive understanding of the property of feature importance, we further investigate the distribution of the features of dataset D1 shown in Fig. 4. We can clearly see that the 2nd feature and 3rd feature are compact with a cluster-like structure; therefore, they should be more important than the other two features, which coincides with δMKM = [1 . 072, 1 . 360, 1 . 341, 1 . 143] indicating the 2nd feature and 3rd feature of dataset D1 are two importance features. If the MVR is used to measure the feature importance, the MVR of D1 is δMVR = [1 . 497, 0 . 981, 1 . 089, 3 . 085], indicating that the 1st feature and 4th feature are important features, but in fact, the 2nd feature and 3rd feature are actually two important features of dataset D1. What mislead the algorithm is that if D1 is normalized, the MVR of D1 becomes δMVR = [5 . 944, 8 . 940, 8 . 908, 6 . 161], and then the 2nd and 3rd features become important features. Similarly, the 3rd feature and 4th feature of the iris dataset are two important features because these features have a cluster-like structure, as shown in Fig. 5, and the MKM of iris is δMKM = [0 . 834, 0 . 666, 1 . 282, 1 . 222]; however, the MVR of iris is δMVR = [8 . 103, 13 . 455, 5 . 228, 4 . 527]. Thus, in this paper, we use the MKM index to measure the feature importance instead of the MVR index.

B. The F ormulation of Feature Reduction Fuzzy C-Means Clustering L everaging the M arginal K urtosis M easure

In this section, inspired by the work of Yang et al. [[16]], we propose a novel and robust feature reduction fuzzy clustering algorithm leveraging the marginal kurtosis measure, named the FRFCM-MKM, to mitigate the disadvantages of the FRFCM algorithm. In this method, the MKM index is used to measure the feature importance of a dataset, and each feature has an individual weight updating equation in each iteration. We develop a new threshold to determine which feature(s) is/are to be discarded. In this process, the features with small weights less than the threshold will be removed from datasets. Let X ={  x i | i  = 1, 2,. . . , n } be a dataset of ${ℝ}^d$ space, and the weights of the features are denoted as a weight vector w = [w1,. . . , wd] T. The objective function of the FRFCM-MKM algorithm is minimized in the form that follows:

(11) $\begin{array}{cc}\hfill J\left(U,V,w\right)=& \sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m\sum _{j=1}^d{\delta }_j{w}_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2\hfill \\ \hfill & +\tau ·n·c\sum _{j=1}^d{\left(w_j-{\delta }_j\right)}^2\hfill \end{array}$

To obtain the optimal clustering results, the FRFCM-MKM is minimized subject to the following constraints:

(12) $s.t\sum _{k=1}^c{u}_{\mathit{ik}}=1,\sum _{j=1}^d{w}_j=1,w_j⩾0$

where δj is computed by Equation (10). δj is the marginal kurtosis measure of X, and utilized to control parameter wj in the FRFCM-MKM algorithm. From the above, we see that the clustering problem of finding the optimal cluster assignments of objects is now formulated as a constrained optimization problem, i.e., to find the optimal values of U, V, and w subject to a set of constraints. Considering that U, V and w are continuous variables, we can use the method of Lagrange multipliers with the first order necessary condition to derive their solutions.

(13) $\begin{array}{cc}\hfill L=& J+\sum _{i=1}^n{\lambda }_i\left(1-\sum _{k=1}^c{u}_{\mathit{ik}}\right)\hfill \\ \hfill & +\beta \left(1-\sum _{j=1}^d{w}_j\right)+\sum _{j=1}^d{\gamma }_j{w}_j\hfill \end{array}$

(14) $\frac{\partial L}{\partial u_{\mathit{ik}}}={\mathit{mu}}_{\mathit{ik}}^{m-1}\sum _{j=1}^d{\delta }_j{w}_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2-{\lambda }_i=0$

(15) $\frac{\partial L}{\partial v_{\mathit{kj}}}=-2{\delta }_j{w}_j\sum _{i=1}^n{u}_{\mathit{ik}}^m{v}_{\mathit{kj}}\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)=0$

(16) $\begin{array}{cc}\hfill \frac{\partial L}{\partial w_j}=& \sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m{\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2\hfill \\ \hfill & +\gamma \left(w_j-{\delta }_j\right)-\beta +{\gamma }_j=0\hfill \end{array}$

(17) ${\gamma }_j⩾0$

(18) ${\gamma }_j{w}_j=0$

According to Equation (14), the iteration formula of uij can be obtained as follows:

(19) $\begin{array}{cc}\hfill u_{\mathit{ik}}=& {\left[\sum _{j=1}^d{\delta }_j{w}_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2\right]}^{\frac{1}{1-m}}/\hfill \\ \hfill & \sum _{s=1}^c{\left[\sum _{j=1}^d{\delta }_j{w}_j{\left(x_{\mathit{sj}}-v_{\mathit{kj}}\right)}^2\right]}^{\frac{1}{1-m}}\hfill \end{array}$

From Equation (15), we obtain

(20) $v_{\mathit{kj}}=\sum _{i=1}^n{u}_{\mathit{ik}}^m{x}_{\mathit{ij}}/\sum _{i=1}^n{\mu }_{\mathit{ik}}^m$

From Equation (16), it can be obtained that

(21) $\begin{array}{c}\hfill w_j=\underset{I}{\underbrace{\frac{1}{\left|I^{+}\right|}-\frac{1}{\left|I^{+}\right|}\sum _{s\in I^{+}}{\delta }_j+{\delta }_j}}+\hfill \\ \hfill \underset{\mathit{II}}{\underbrace{\frac{1}{2\tau ·n·c\left|I^{+}\right|}\sum _{s\in I^{+}}\sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m{\delta }_j{\left(x_{\mathit{is}}-v_{\mathit{ks}}\right)}^2-\frac{1}{2\tau ·n·c}\sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m{\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2}}\hfill \\ \hfill \hfill \end{array}$

(22) $\begin{array}{c}\hfill I^{-}=\left\{j:w_j=0\right\}\hfill \\ \hfill I^{+}=\left\{j:w_j>0\right\}\hfill \\ \hfill \hfill \end{array}$

I - denotes the set of indexes of the zero-weight (redundant) features, while I+ denotes the set of indexes of the positive weight (important) features. |I-| and |I+| are the cardinality of I- and I+, respectively. The elements of I- and I+ are computed by the same method as in [[23]], which is outlined as follows.

Here we give the detailed derivation of the update equations of wj from the Lagrangian in Equation (13) and the Karush–Kuhn–Tucker conditions in Equations (16)–(18). Combining Equations (13) and (16) results in

(23) $\begin{array}{cc}\hfill w_j=& \frac{\beta }{2\tau ·n·c}-\frac{1}{2\tau ·n·c}\sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m{\delta }_j\hfill \\ \hfill & {\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2-\frac{1}{2\tau ·n·c}{\gamma }_j+{\delta }_j\hfill \end{array}$

According to ${\sum }_{j=1}^d{w}_j=1$ , it can be obtained that

(24) $\begin{array}{c}\hfill \frac{\beta p}{2\tau ·n·c}-\frac{1}{2\tau ·n·c}\sum _{j=1}^d\sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m{\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2\hfill \\ \hfill \hfill \\ \hfill -\frac{1}{2\tau ·n·c}\sum _{j=1}^d{\gamma }_j+\sum _{j=1}^d{\delta }_j=1\hfill \\ \hfill \hfill \\ \hfill \beta =\frac{2\tau ·n·c}{d}\left(1-\sum _{j=1}^d{\delta }_j\right)+\frac{1}{d}\sum _{j=1}^d\sum _{i=1}^n\sum _{k=1}^c{\mu }_{\mathit{ik}}^m{\delta }_j\hfill \\ \hfill {\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2+\frac{1}{d}\sum _{j=1}^d{\gamma }_j\hfill \\ \hfill \hfill \end{array}$

By plugging Equation (24) into Equation (23), the closed-form solution for the feature weights is obtained as

(25) $\begin{array}{c}\hfill w_j=\frac{1}{d}-\frac{1}{d}\sum _{j=1}^d{\delta }_j+\frac{1}{2\tau ·n·c·d}\sum _{j=1}^d\sum _{i=1}^n\sum _{k=1}^c\hfill \\ \hfill u_{\mathit{ik}}^m{\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2+\frac{1}{2\tau ·n·c·d}\sum _{j=1}^d{\gamma }_j-\frac{1}{2\tau ·n·c}\hfill \\ \hfill \sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m{\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2-\frac{1}{2\tau ·n·c}{\gamma }_j+{\delta }_j\hfill \\ \hfill \hfill \end{array}$

Now we consider Equation (17) for two respective cases.

1) γj = 0, ∀ j ∈ {1,. . . , d}, Equation. (25) becomes

$\begin{array}{c}\hfill w_j=\frac{1}{d}-\frac{1}{d}\sum _{j=1}^d{\delta }_j+\frac{1}{2\tau ·n·c·d}\sum _{j=1}^d\sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m{\delta }_j\hfill \\ \hfill {\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2-\frac{1}{2\tau ·n·c}\sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m{\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2+{\delta }_j\hfill \\ \hfill \hfill \end{array}$

For each feature j, this set of solutions is valid only if

$\begin{array}{c}\hfill \frac{1}{d}-\frac{1}{d}\sum _{j=1}^d{\delta }_j+\frac{1}{2\tau ·n·c·d}\sum _{j=1}^d\sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m{\delta }_j\hfill \\ \hfill {\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2-\frac{1}{2\tau ·n·c}\sum _{i=1}^n\sum _{j=1}^k{u}_{\mathit{ij}}^m{\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2+{\delta }_j⩾0\hfill \\ \hfill \hfill \end{array}$

Otherwise, we consider the second case.

2) If γj > 0 for at least one j, according to Equation (18) when γj > 0, wj = 0; therefore,

(26) $\begin{array}{c}\hfill \frac{1}{d}-\frac{1}{d}\sum _{j=1}^d{\delta }_j+\frac{1}{2\tau ·n·c·d}\sum _{j=1}^d\sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m{\delta }_j\hfill \\ \hfill {\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2+\frac{1}{2\tau ·n·c·d}\sum _{j=1}^d{\gamma }_j-\frac{1}{2\tau ·n·c}\hfill \\ \hfill \sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m{\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2-\frac{1}{2\tau ·n·c}{\gamma }_j+{\delta }_j=0\hfill \\ \hfill \hfill \end{array}$

From the above equation, we obtain that

(27) $\begin{array}{c}\hfill \frac{1}{2\tau ·n·c}{\gamma }_j=\frac{1}{d}-\frac{1}{d}\sum _{j=1}^d{\delta }_j+\frac{1}{2\tau ·n·c·d}\hfill \\ \hfill \sum _{j=1}^d\sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m{\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2+\frac{1}{2\tau ·n·c·d}\sum _{j=1}^d{\gamma }_j\hfill \\ \hfill -\frac{1}{2\tau ·n·c}\sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m{\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2+{\delta }_j\hfill \\ \hfill \hfill \end{array}$

Constrained by Equation (12), obviously, it is known that not all wj can be 0. Therefore, the set { j|j = 1,. . . , d} is separated into two subsets denoted as I- and I+, where

(28) $\begin{array}{c}\hfill I^{-}=\left\{j:w_j=0\right\}\hfill \\ \hfill I^{+}=\left\{j:w_j>0\right\}\ne \phi \hfill \\ \hfill \hfill \end{array}$

Therefore, Equation (27) becomes

$\begin{array}{c}\hfill \frac{1}{2\tau ·n·c}{\gamma }_j=\frac{1}{d}-\frac{1}{d}\sum _{j=1}^d{\delta }_j+\frac{1}{2\tau ·n·c·d}\hfill \\ \hfill \sum _{j=1}^d\sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m{\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2+\frac{1}{2\tau ·n·c·d}\hfill \\ \hfill \left(\sum _{s\in I^{+}}{\gamma }_s+\sum _{s\in I^{-}}{\gamma }_s\right)-\frac{1}{2\tau ·n·c}\sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m{\delta }_j\hfill \\ \hfill {\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2+{\delta }_j=\frac{1}{d}-\frac{1}{d}\sum _{j=1}^d{\delta }_j+\frac{1}{2\tau ·n·c·d}\hfill \\ \hfill \sum _{j=1}^d\sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m{\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2+\frac{\left|I^{-}\right|}{2\tau ·n·c·d}{\gamma }_j\hfill \\ \hfill -\frac{1}{2\tau ·n·c}\sum _{i=1}^n\sum _{j=1}^k{u}_{\mathit{ik}}^m{\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2+{\delta }_j\frac{\left|I^{+}\right|}{2\tau ·n·c·d}\hfill \\ \hfill {\gamma }_j=\frac{1}{d}-\frac{1}{d}\sum _{j=1}^d{\delta }_j+\frac{1}{2\tau ·n·c·d}\sum _{j=1}^d\sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m\hfill \\ \hfill {\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2-\frac{1}{2\tau ·n·c}\sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m{\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2+{\delta }_j\hfill \\ \hfill \hfill \end{array}$

From the above equation, it can be obtained that

(29) $\begin{array}{c}\hfill {\gamma }_j=\frac{2\tau ·n·c}{\left|I^{+}\right|}-\frac{2\tau ·n·c}{\left|I^{+}\right|}\sum _{j=1}^d{\delta }_j\hfill \\ \hfill +\frac{1}{\left|I^{+}\right|}\sum _{j=1}^d\sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m{\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2-\hfill \\ \hfill \frac{d}{\left|I^{+}\right|}\sum _{i=1}^n\sum _{j=1}^k{u}_{\mathit{ik}}^m{\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2+\frac{2\tau ·n·c·d}{\left|I^{+}\right|}{\delta }_j\hfill \\ \hfill \hfill \end{array}$

By replacing the γj in Equation (25) with Equation (29), after some simplification, we obtain the final form as in Equation (21).

How to choose the threshold is an important step for the proposed clustering algorithm. To develop a feature-reduction scheme using an FRFCM algorithm, Yang et al. [[16]] used $1/\sqrt{\mathit{nd}}$ as a threshold to determine which feature(s) is/are to be selected or discarded. Yet, $1/\sqrt{\mathit{nd}}$ decreases if n is increasing. For different sized datasets generated from the same distribution, they must have the same feature importance, and should have similar feature weights in the feature weighting clustering algorithm. Consequently, the thresholds should be equal. However, the thresholds computed by $1/\sqrt{\mathit{nd}}$ range from 0.071 to 0.0071 (Table 1), though the feature importance of the datasets are equal. Thus, $1/\sqrt{\mathit{nd}}$ is not a suitable threshold for some data in the feature reduction learning algorithm.

Table 1 Threshold for different sized datasets drawn from same distribution

Now, we try to find a proper threshold to remove the feature(s) with small weight(s) instead of using $1/\sqrt{\mathit{nd}}$ as a threshold. Since δj is a feature importance measure, we can construct a threshold using the information of the δjs. In Equation (11), if the δjs are normalized, let τ→ + ∞, and it can obtain wj ≈ δj when the FRFCM-MKM algorithm converges, which inspired us to use the δjs to construct a threshold. According to the property of the Pythagorean means, as the smallest of the three Pythagorean means, the harmonic mean tends to emphasize the impact of small δj s while minimizing the impact of large δj s. Then, we pick $\sqrt{d}/{\sum }_{j=1}^d\frac{1}{{\delta }_j}$ as a threshold since $\sqrt{d}/{\sum }_{j=1}^d\frac{1}{{\delta }_j}<d/{\sum }_{j=1}^d\frac{1}{{\delta }_j}<$ $\sqrt[d]{{\prod }_{j=1}^d{\delta }_j}<\frac{1}{d}{\sum }_{j=1}^d{\delta }_j=\frac{1}{d}$ . The proposed FRFCM-MKM algorithm can be summarized as follows.

C. FRFCM-MKM Algorithm

Next, we provide the detailed proof of convergence theorems for the FRFC-Means algorithm.

D. Convergence Theorems for FRFCM-MKM Algorithm

Theorem 1. If V and w are fixed, then U is a strict local minimum of J (U, V, w) if and only if U is calculated by (19).

Theorem 2. If U and w are fixed, then V is a strict local minimum of J (U, V, w) if and only if V is calculated by (20).

Theorem 3. If U and V are fixed, then w is a strict local minimum of J (U, V, w) if and only if w is calculated by (21).

Referring to [[24], [26]], Theorems 1 and 2 can be easily proved. Because the main difference between FCM and FRFCM-MKM exists in the involved feature weights, here we only give a detailed proof of theorem 3 below.

Proof. We first prove the necessary condition for minimum of J (U, V, w) by using the Lagrangian multiplier method to transform the constraint minimization problem into an unconstrained problem. We take the Lagrangian function as follows.

(30) $\begin{array}{c}\hfill L_1\left(\text{w},\beta \right)=\sum _{i=1}^N\sum _{j=1}^K{u}_{\mathit{ik}}^m\sum _{j=1}^d{\delta }_j{w}_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2+\hfill \\ \hfill \tau ·n·c\sum _{j=1}^d{\left(w_j-{\delta }_j\right)}^2+\beta \left(1-\sum _{j=1}^d{w}_j\right)\hfill \\ \hfill \hfill \end{array}$

where 21 β is Lagrangian multiplier, By setting the gradient of L1 with respect to wj and β to zero it can be obtained:

(31) $\begin{array}{cc}\hfill \frac{\partial L_1}{\partial w_j}=& \sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m{\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2\hfill \\ \hfill & +2\tau ·n·c·\left(w_j-{\delta }_j\right)-\beta =0\hfill \end{array}$

(32) $\frac{\partial L_1}{\partial \beta }=\sum _{j=1}^d{w}_j-1=0$

Then, follow the steps from Equation (20) to Equation (26), we have

(33) $\begin{array}{c}\hfill w_j=\frac{1}{d}-\frac{1}{d}\sum _{j=1}^d{\delta }_j+\frac{1}{2\tau ·n·c·d}\sum _{j=1}^d\sum _{i=1}^n\sum _{k=1}^c\hfill \\ \hfill u_{\mathit{ik}}^m{\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2+\frac{1}{2\tau ·n·c·d}\sum _{j=1}^d{\gamma }_j-\frac{1}{2\tau ·n·c}\hfill \\ \hfill \sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m{\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2-\frac{1}{2\tau ·n·c}{\gamma }_j+{\delta }_j\hfill \\ \hfill \hfill \end{array}$

The necessary condition is proved.

Secondly, we prove the sufficient condition for minimum of J (U, V, w). To analysis the sufficiency of Theorem 3, we can check Hessian Matrix of Lagrangian function L1 (w, β) denoted as HL1 (w, β), because

(34) $\begin{array}{c}\hfill \frac{\partial L_2}{\partial w_j}=\sum _{i=1}^n\sum _{k=1}^c{u}_{\mathit{ik}}^m{\delta }_j{\left(x_{\mathit{ij}}-v_{\mathit{kj}}\right)}^2\hfill \\ \hfill +2\tau ·n·c·\left(w_j-{\delta }_j\right)-\beta =0\hfill \\ \hfill \frac{{\partial }^2{L}_2}{\partial w_j\partial w_l}={\kappa }_{\mathit{jl}}2\tau \hfill \\ \hfill \hfill \end{array}$

where κjl is Kronecker index with ${\kappa }_{\mathit{jl}}=\{\begin{array}{c}\hfill 1,\mathrm{if}j=l\hfill \\ \hfill 0,\mathrm{if}j\ne l\hfill \\ \hfill \hfill \end{array}$ ,

$\frac{{\partial }^2{L}_2}{\partial w_l\partial \beta }=\frac{{\partial }^2{L}_2}{\partial \beta \partial w_l}=1.$

Thus, the bordered Hessian matrix with regard to w and β is

(35) $\begin{array}{cc}\hfill & {\text{H}}_{L_1}\left(\text{w},\beta \right)\hfill \\ \hfill & =\left[\begin{array}{ccccc}\hfill 2\tau ·n·c\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 2\tau ·n·c\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill 0\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill 2\tau ·n·c\hfill \\ \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill \end{array}\right]\hfill \end{array}$

Since we know τ > 0, and n · c > 0, the ${\text{H}}_{L_1}\left(\text{w},\beta \right)$ is a diagonal matrix with positive diagonal entries. So the matrix ${\text{H}}_{L_1}\left(\text{w},\beta \right)$ is positive definite. J (U, V, w) must have the minimum point, and Equation (25) is a sufficient condition for w to be a local minimum of J (U, V, w).

And in the same way, the case of feature reduction can be proved. Then theorem 3 can be verified. □

In this section, to evaluate the performance of the proposed FRFCM-MKM algorithm, the WKM, EWKM, WFCM, SCAD2, ESSC, and the FRFCM are chosen for analysis. A series of experiments are performed with various datasets. In most cases, running the clustering algorithm on raw data does not work well. Therefore, we normalized each feature fj = [x1j, x2j,. . . , xnj] T by subtracting its mean and dividing it by its range, as shown below:

${\text{y}}_j=\frac{{\text{f}}_j^T-{\text{f}}_j·1^T·1}{max\left({\text{f}}_j\right)-min\left({\text{f}}_j\right)}$

where 1 is an all one element vector.

We set the threshold value ɛ and the maximum number of restarts to ɛ = 105 and t = 300, respectively, in all the algorithms. The parameter of the fuzziness m in all fuzzy-type clustering algorithms and our algorithm is set to 2. The experiments are performed on a PC with an Intel Core i5-4590 with 4 GB of memory. All code is written in the MATLAB computing environment.

A. Performance M etrics

Three performance metrics including the accuracy (AC) [[27]], the normalized mutual information (NMI) [[28]], and the adjusted Rand index (ARI) [[29]] are used to evaluate the performance of clustering algorithms. They are averaged over thirty different runs with random initialization of the feature weights and with random initializations of the centroids using the initialization strategy in reference [[30]].

Accuracy: We evaluate the clustering results by comparing the obtained labels using clustering algorithms with the provided ground truths. The second metric we use is the AC with $\mathit{AC}=\frac{1}{n}{\sum }_{k=1}^c{d}_k$ , where dk indicates the number of data points that are correctly clustered for cluster k, and n is number of the data points in the dataset. A larger AC means better performance of the clustering algorithm.

ARI: The Rand index (RI) proposed by Rand [[31]] measures the agreement between two crisp partitions of a set of data points. The ARI is the adjusted form of the Rand index. The ARI has a maximum value of 1, and its expected value is 0 in the case of random clusters. A larger ARI implies more agreement between two partitions, and, hence, the greater effectiveness of the algorithm since the two partitions are produced by a clustering algorithm and human experts, respectively. The adjusted Rand Index is computed as follows:

(36) $\mathit{ARI}=\frac{{\sum }_{\mathit{ij}}\left(\begin{array}{c}\hfill n_{\mathit{ij}}\hfill \\ \hfill 2\hfill \\ \hfill \hfill \end{array}\right)-\left[{\sum }_i\left(\begin{array}{c}\hfill a_i\hfill \\ \hfill 2\hfill \\ \hfill \hfill \end{array}\right){\sum }_j\left(\begin{array}{c}\hfill b_j\hfill \\ \hfill 2\hfill \\ \hfill \hfill \end{array}\right)\right]/\left(\begin{array}{c}\hfill n\hfill \\ \hfill 2\hfill \\ \hfill \hfill \end{array}\right)}{\frac{1}{2}\left[{\sum }_i\left(\begin{array}{c}\hfill a_i\hfill \\ \hfill 2\hfill \\ \hfill \hfill \end{array}\right)+{\sum }_j\left(\begin{array}{c}\hfill b_j\hfill \\ \hfill 2\hfill \\ \hfill \hfill \end{array}\right)\right]-\left[{\sum }_i\left(\begin{array}{c}\hfill a_i\hfill \\ \hfill 2\hfill \\ \hfill \hfill \end{array}\right){\sum }_j\left(\begin{array}{c}\hfill b_j\hfill \\ \hfill 2\hfill \\ \hfill \hfill \end{array}\right)\right]/\left(\begin{array}{c}\hfill n\hfill \\ \hfill 2\hfill \\ \hfill \hfill \end{array}\right)}$

where n is the total number of data points, c is the number of clusters, nij = |S i  ∩ Sj|, $a_i={\sum }_{j=1}^c\left|S_i\cap S_j\right|$ and $b_i={\sum }_{i=1}^c\left|S_i\cap S_j\right|$ .

NMI: The NMI [[28]] index is another popular index that is used to evaluate clustering results. This index measures the agreement of the clustering results produced by an algorithm and the ground truth. If we refer to a class as the ground truth and a cluster as the results of a clustering algorithm, the NMI is calculated as follows:

(37) $\mathit{NMI}=\frac{{\sum }_i{\sum }_j{n}_{\mathit{ij}}log\left(\frac{n·n_{\mathit{ij}}}{a_i·b_j}\right)}{\sqrt{{\sum }_{i=1}{n}_{i}log\left(\frac{n_i}{n}\right)\left({\sum }_j{n}_{j}log\left(\frac{n_j}{n}\right)\right)}}$

where n is the total number of data points, c is the number of clusters, nij = |S i  ∩ Sj|, $a_i={\sum }_{j=1}^c\left|S_i\cap S_j\right|$ and $b_i={\sum }_{i=1}^c\left|S_i\cap S_j\right|$ .

B. Experiment

In this experiment, we generate the same dataset denoted by D2 as that used in example 1 of reference [[16]]. This dataset has 400 data points with components x2 and x3 being generated from the Gaussian mixture model ${\sum }_{k=1}^2{\alpha }_{k}N\left({\mu }_k,{\sum }_k\right)$ , where the parameters α1 = α2 = 0.5, μ1 = (3, 3) T, μ2 = (7, 7) T, ${\sum }_1=\left(\begin{array}{cc}\hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill \\ \hfill \hfill \end{array}\right)$ and ${\sum }_2=\left(\begin{array}{cc}\hfill 0.5\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0.5\hfill \\ \hfill \hfill \end{array}\right)$ . Components x1 and x4 follow uniform distributions over the intervals [0, 10] and [0, 12], respectively.

To compare the feature weight representation abilities of the WKM, FRFCM and FRFCM-MKM, we apply the WKM, FRFCM and FRFCM-MKM algorithms to dataset D2 thirty times to examine whether the algorithms assign proper weights to features. Since the prototype-based clustering algorithms are sensitive to the initialization, to reduce the sensitivity of the initialization for clustering algorithms, we first choose five sets of centers V1, V2, V3, V4 and V5 from D2 as the initial cluster centers by using the initialization strategy in the k-means++ [[30]] and then implement the WKM, FRFCM and FRFCM-MKM with different initial feature weights. To save space, though the algorithms are conducted thirty times, we merely plot the bar graphs of the first ten runs to study the feature assignment problem of the three algorithms. For the WKM, we plot the bar graphs of the final weights, but for the FRFCM and FRFCM-MKM, the bar graphs are for the first iterations since the weights in the first iterations play a vital role in the feature reduction process. Each color of the bar graphs represents the weight assignment for a run of the algorithm. As shown in the bar graphs (Table 2), for the five sets of fixed initial clusters, the WKM and FRFCM do not properly assign weights to features using random initial weights because different initial weights may lead to different weight assignments. Especially, the FRFCM algorithm may assign small weights to important features (i.e., the 2nd and 3rd features) but large weights to unimportant features (i.e., the 1st and 4th features). Thus, in the feature reduction process, the 2nd and 3rd features may be discarded. The case of D2 being normalized is given in Table 3. ${\tilde{\text{V}}}_1$ to ${\tilde{\text{V}}}_5$ are five sets of fixed initial cluster centers. The bar graphs show that the weights produced by the FRFCM are less sensitive to different initial feature weights when the data are normalized. However, the FRFCM still does not properly assign weights to features since the 2nd and 3rd features obtain small weights. However, our method is always capable of properly assigning weights to features whether the data are normalized or not, and the 2nd and 3rd features always obtain large weights.

Table 2 Weight assignments of the WKM, FRFCM and FRFCM-MKM for unnormalized D2 with fixed cluster centers

Table 3 Weight assignments of the WKM, FRFCM and FRFCM-MKM for normalized D2 with fixed initial weights

We next run the WKM, FRFCM and FRFCM-MKM for the unnormalized and normalized D2 datasets with equal initial feature weights w = [1/4, 1/4, 1/4, 1/4] T and with random initial cluster centers. The bar graphs of the weight assignments for these algorithms are shown in Tables 4 and 5, which demonstrate that the FRFCM-MKM represents the features importance well. When the initial weights are fixed and the centers are randomly initialized, both the WKM and FRFCM do not represent the features well.

Table 4 Weight assignments of the WKM, FRFCM and FRFCM-MKM for unnormalized D2 when the initial feature weights are fixed as w = [1/4, 1/4, 1/4, 1/4] T

Table 5 Weight assignments of the WKM, FRFCM and FRFCM-MKM for normalized D2 when the initial feature weights are fixed as w = [1/4, 1/4, 1/4, 1/4] T

The reason that the FRFCM-MKM represents the features well is that the second term in the objective function is used to control the value of wj s; and the larger the value of τ is, the closer the value of wj is to that of δj, and the more robust the algorithm. Fig. 6 shows the weight assignments of the FRFCM-MKM under different parameters. As τ increases, the feature weights remain the same for each run, which indicates the robustness of the proposed method.

Now we compare the clustering results achieved by the WKM, EWKM, WFCM, SCAD2, ESSC, FRFCM and FRFCM-MKM algorithms. Table 8 lists the clustering results of the WKM, EWKM, WFCM, SCAD2, ESSC, FRFCM and FRFCM-MKM algorithms for unnormalized and normalized D2. The WKM and EWKM produce unsuitable feature weights, and the clustering results are worse. The SCAD2 and ESSC produce suitable feature weights on normalized D2 (Table 7), and the clustering result are desirable. The FRFCM does not produce suitable feature weights for dataset D2, and the important feature(s) is/are discarded from the data at the first iteration, which leads to an incorrect clustering result. When D2 is normalized, the FRFCM assigns comparative larger weights to the four features (Table 3). Meanwhile, the threshold calculated by $1/\sqrt{\mathit{nd}}$ is 0.025, and this value is used to determine which feature(s) will be retained or removed. However, the threshold is so small that the FRFCM fails to remove any feature(s) in the clustering process. In this case, the FRFCM algorithm clusters the data well in the full space, but the feature reduction mechanism in the FRFCM fails. The proposed algorithm outperforms the other clustering methods on the dataset D2 with AC = 0.998, NMI = 0.977 and ARI = 0.990, and the main reason is that the FRFCM-MKM properly represents the feature weights. Then, in the feature reduction learning process, the 1st feature and 4th feature are discarded. The FRFCM-MKM is actually implemented in a 2-D subspace of D2, as shown in Fig. 2(a); therefore, the desired result can be obtained. Moreover, The weights obtained by the FRFCM-MKM always represent the importance of features well regardless of whether the data are normalized or not because the weight update equation is dominated by part I (see Equation (21)), and part II is merely used to adjust the weight value. This characteristic makes the FRFCM-MKM produce almost equal weights for when the data are normalized and not unnormalized, and this makes the feature weights robust to the initialization. This experiment demonstrates that the FRFCM-MKM can properly assign the weights to the features, and it also shows that the weights produced by the FRFCM-MKM are robust to the initialization.

Graph: Fig. 2 (a) Two component data points generated from a Gaussian mixture model; (b)The Gaussian mixture model data points by adding component x3.

Graph: Fig. 3 (a) δMVR value of D1 (unnormalized); (b) δMVR value for D1 (normalized),

Graph: Fig. 4 Distribution of the different features of dataset D1. (a) 1st feature. (b) 2nd feature. (c) 3rd feature. (d) 4th feature.

Graph: Fig. 5 Distribution of the different features of the iris dataset. (a) 1st feature. (b) 2nd feature. (c) 3rd feature. (d) 4th feature.

Table 6 Weight assignments of the WKM, FRFCM and FRFCM-MKM for unnormalized D2 with the centers and weights randomly initialized

Table 7 The final weight assignments of the SCAD2 and ESSC on normalized D2

Table 8 Comparing the clustering results achieved by seven algorithms on dataset D2

Experiment 2: the effect of suppressing noisy/redundant feature(s)

In this experiment, for the iris dataset, we add h (h = 4, 8, 12) noisy features to 4 real ones. The noisy features are Gaussian noise. We let the noisy features follow a Gaussian distribution, i.e., ${\tilde{x}}_j\sim N\left(0,h\right)$ , where j = 1,. . . , h, h = 4, 8, 12, and normalized these datasets. Now we compare the noisy feature suppression abilities of the WKM, EWKM, WFCM, SCAD2, ESSC, FRFCM and FRFCM-MKM on the noisy iris dataset. Because the feature weights produced by the comparing algorithms is relative to the dispersion of features, the obtained weights of noisy feature is much larger. However, the FRFCM-MKM algorithms produce close-to-zero weights for noisy features. The reason is that the weight update equation is mainly controlled by part I (see Equation (21)). Fig. 7 (a)∼(c) demonstrate that the WMK is able to produce large weights for important features and small weights for unimportant features and noisy features, but the weights produced by the WMK are sensitive to the initialization. The WMK may produce large feature weight(s) for noisy features when the initialization is improper. The FRFCM can assign proper features weights for the noisy iris dataset, but the assignment decreases the weights of the important features and assigns comparatively large weights to noisy features (Fig. 7. (d)∼(f)). Moreover, the thresholds computed by $1/\sqrt{\mathit{nd}}$ for the noisy Iris are 0.029, 0.024, and 0.020, respectively. The thresholds are so small that the FRFCM is not capable of removing any unimportant features and noisy features from the dataset; hence, the FRFCM cannot suppress the noisy features well. The FRFCM-MKM algorithm suppresses the noisy features well and produces large weights for the 3rd and 4th features since these features are important features, small weights for the 1st and 2nd features, and close-to-zero weights for the noisy features (Fig. 7(g)∼(i)). Thus, unimportant features and noisy features can be identified and discarded. It would be interesting to note that, on the iris with noisy features, our proposed method performs surprisingly well. Our method achieves the same results as on the original iris with AC = 0.967, NMI = 0.885 and ARI = 0.904. It indicates that the FRFCM-MKM can suppress noisy features well and the noisy features have no negative effect on our method. Compared with the FRFCM, the improvements of FRFCM-MKM on the iris with 4 and 8 noisy features are 5.11% for AC, 10.04% for NMI and 15.01% for ARI. Because the EWKM, SCAD2 and ESSC are unable to identify the noisy features and assign large weights to the noisy features (Fig. 8), the clustering performance is rather poor. The clustering results of the seven algorithms are listed in Table 9.

Graph: Fig. 6 The weight assignments of the FRFCM-MKM under different parameters.

Graph: Fig. 7 (a)∼(c)Weight assignments of the WKM with 4, 8, and 12 noisy features added to iris, respectively. (d)∼(f) Weight assignments of the FRFCM with 4, 8, and 12 noisy features added to iris, respectively. (g)∼(i) Weight assignments of the FRFCM-MKM with 4, 8, and 12 noisy features added to iris, respectively.

Graph: Fig. 8 (a)∼(c) Weight assignments of the EWKM with 4, 8, and 12 noisy features added to iris, respectively. (d)∼(f) Weight assignments of SCAD2 with 4, 8, and 12 noisy features added to iris, respectively. (g)∼(i) Weight assignments of ESSC with 4, 8, and 12 noisy features added to iris, respectively.

Table 9 Comparing the clustering results achieved by the seven algorithms on the Iris data and noisy Iris data

Now we perform clustering on six high-dimensional synthetic datasets to demonstrate the effectiveness of the proposed algorithm. Each dataset contains 1024 samples and 16 clusters, and the datasets used in this experiment can be downloaded from the webpage of the Speech and Image Processing Unit [[32]]. The detailed information on these six high dimensional synthetic datasets is summarized in Table 10.

Table 10 Brief information for the high dimensional synthetic datasets

Table 11 shows the clustering results for the seven different methods on the datasets ranging from 64 to 1,024 samples. The clustering algorithms are applied to the six synthetic datasets Dim64 to Dim1024 that represent higher dimensionality varying datasets. Compared with the other approaches, the FRFCM-MKM algorithm achieves excellent clustering results as represented by the AC, NMI and ARI on Dim256∼Dim1024. As shown in Table 12, Moreover, the run-time of the FRFCM-MKM algorithm on these six datasets are lowest compared with those of the other algorithms. Its run-time ranges from 0.004 to 0.006 seconds on Dim256∼Dim1024. The average time of WKM, EWKM, FCM, WFCM, SCAD2, ESSC, FRFCM and FRFCM-MKM on dim032 to dim1024 are 0.159, 0.421, 0.068, 4.136, 0.832, 0.842, 0.058, 0.005 second respectively. The FRFCM-MKM is 10 times faster than the FRFCM in average. The SCAD2, ESSC and FRFCM methods also achieve desirable results; however, the run-times of these algorithms are relatively high. Although the FRFCM uses a feature reduction scheme, when these data are normalized, the FRFCM fails to discard the unimportant features from Dim032∼Dim256. The FRFCM can remove 40 unimportant features and retain 472 features for dim512. Meanwhile, the FRFCM removes 523 unimportant features from Dim1024 and retains 501 features. However, the FRFCM-MKM retains 5, 5, 4, 6, 5, and 10 features for Dim032∼Dim1024, respectively, and it only utilizes a small number of features in the clustering process (Table 12).

Table 11 Clustering performance on dim032-dim1024 using the WKM, EWKM, FCM, WFCM, SCAD2, ESSC, FRFCM and FRFCM-MKM

Table 12 Numbers of original and final features obtained from the FRFCM and the FRFCM-MKM and the total run-times (in seconds) for the synthetic datasets for each algorithm

In this experiment, we investigate the performances of the proposed algorithm on some real world datasets, and their properties are summarized in Table 13. We compare the AC, NMI and ARI of the FRFCM-MKM with those of the WKM, EWKM, FCM, WFCM, SCAD2, and FRFCM-MKM. The comparisons use different initial cluster centers with different initial feature weights.

Table 13 Summary of some real world Datasets

Table 14 shows the clustering results of seven different clustering algorithms on thirteen real datasets. Compared with the other approaches, the FRFCM-MKM achieves excellent clustering results on nine out of thirteen datasets according to the AC, NMI and ARI. The improvement of the FRFCM-MKM compared to the FRFCM is significant both in the performance metrics and feature reduction. On the easily-clustered datasets such as iris, wdbc_all, breast_cancer, FRFCM-MKM is superior to the other six algorithms. The differences between FRFCM-MKM and FRFCM on the iris dataset are 6.67%, 11.62%, and 21.51% for AC, NMI and ARI metric. On the wdbc_all dataset the differences are 0.76%, 3.94%, and 3.45%, while on the breast_cancer dataset they are 1.16%, 14.15%, 2%. The final features by running FRFCM-MKM on these datasets are 2, 10, and 5, respectively, compared with 4, 30 and 9 by FRFCM. On other hard-clustered datasets such as glass, movement_libras, and SMK_CAN_1987 FRFCM-MKM is still superior to the other six algorithms. The differences between FRFCM-MKM and FRFCM on glass are 7.55%, 7.64% and 18.29% for AC, NMI and ARI metric. On the movement_libras on the SMK_CAN_1987 dataset they are 1.49%, 12.90% and 5.26%. As shown in Table 15, the FRFCM-MKM retains 4, 26, and 21 features in the final step on these datasets respectively, while FRFCM retains7, 90 and 19993 features. On the wpbc dataset, the proposed algorithm retains 11 important features in the cluster process with AC = 0.576, while the FRFCM retains 31 features with AC = 0.581. On the ORL dataset, our method uses 215 important features of the data to cluster with AC = 0.503. Although the EWKM algorithm performs best on these data with AC = 0.600, it uses all 2567 features for clustering; therefore, the EWKM takes more time to cluster data. The clustering performance of the proposed algorithm is not the best on these data sets, but its performances are almost equivalent to those of the comparison algorithm while using a small number of features. Table 16 shows the average performance on all datasets. The performance of proposed algorithm is obviously better than the other six methods in terms of AC, NMI and ARI. According to the experimental results on the datasets, we can infer the following conclusions:

Table 14 Clustering performances on real datasets using the WKM, EWKM, SCAD2, FCM, FRFCM, and FRFCM-MKM