Robust and Sparse Fuzzy K-Means Clustering

1 Introduction

The classical K-Means problem is a clustering algorithm which assigns a set of data points into clusters so that the data points in the same cluster have high similarity but are dissimilar if they belong to other clusters. The K-Means algorithm is widely used due to its efficiency. A variety of modifications and generalizations have been proposed and developed over the years. Among different variants of K-Means algorithm, fuzzy K-Means (FKM) algorithm is the most popular. It was originally proposed by [Ruspini, 1969] and had been modified by [Bezdek, 1980]. The essential difference between K-Means and FKM algorithms is FKM allows a data point to have memberships in all clusters rather than having a distinct membership to one single cluster. The K-Means problem is a well-known example for a hard clustering, whereas FKM is a continuous generalization of the K-Means problem that is named as a soft clustering. For the reason that ambiguity exists in real world datasets, FKM clustering has gained more attention recently.

It can be seen that these K-Means-type (hard or soft) algorithms can effectively tackle numerous problems in various fields such as medical imaging, target recognition and image segmentation. Because the philosophy of K-Means-type algorithms is extensively used, a large number of modifications had been proposed [Feiping et al., 2011; Cai et al., 2013]. Here we only discuss some of typical algorithms related to the proposed method.

⇤Corresponding authors

There are two major issues in the application of FKM algorithms. The first issue is the lack of robustness during clustering. Generally FKM algorithms use a Euclidean distance measure to assign memberships to each sample for clustering, which only can provide good clustering result without outliers. To overcome this drawback, the work [Zhang et al., 2003] replaced the Euclidean norm with kernel distance measures. However, this method does not consider any spatial dependence of the data elements, which not only makes it very sensitive to outliers but also takes more time to converge the algorithm. Recently, a set of novel FKM algorithms have been formulated to address this issue by using new techniques and improve their performance. For instance, [Ji et al., 2011] introduced the local spatial weights in the objective function, which allows the suppression of outliers and helps to resolve ambiguity. [Zhao et al., 2011] introduced a non-local spatial constraint term into the objective function to deal with image noise more effectively. [Ji et al., 2012] combined local spatial information embedded in the data to further improve its robustness to outliers. [Kannan et al., 2012] proposed robust FKM based kernel function by incorporating normed kernel function and center initialization algorithm. [Wang et al., 2013] incorporated an adaptive spatial information-theoretic fuzzy clustering into the conventional FKM to improve the robustness.

The second issue is the difficulty of choosing an appropriate regularization for the FKM algorithm. It is well-known that FKM can be extended with regularization to reduce the effect of outliers and further improve its performance. In [Li et al., 2008; Namkoong et al., 2010], the problem can obtain the desired solution by:

where x is the variable to be solved, y is the variable observed, and γ(> 0) is a parameter of regularization. Φ(x) is used to restrict the admissible solution within the space of smooth functions. However, there is no rule for selecting the Φ(x). In general, the derivative of x is chosen for Φ(x), which measures the roughness of x. Recently, regularization has been applied to the clustering problem and several objective functions were formulated using different regularization terms such as [Li and Mukaidono, 1995; Miyamoto and Umayahara, 1998; ¨Ozdemir and Akarun, 2002; Yu and Yang, 2007]. Although these regularization-based methods are better than previous methods, deciding regularization constant is an important problem which was set empirically and time consuming.

On the basis of the above analysis, it can be seen that FKM is a simple and effective method, however, its membership values might be inaccurate in an outlier environment. One of the reasons is the distance measures without robustness used in clustering. Another reason is the distributions and sparseness on memberships. To address these two weaknesses, we propose a robust and sparse fuzzy K-Means clustering algorithm by incorporating robust loss function, rather than the square data fitting term, to handle outliers, and further combining the concept of sparsity, which introduces a regularization, to make their memberships of each sample with respect to different clusters have suitable sparseness.

This paper tends to address the above highlighted drawbacks by introducing a novel robust objective function of fuzzy K-Means with a regularization about the concept of sparsity. Furthermore, the dynamic γ strategy is given in this paper, which suggests that the proposed method can be improved further if the parameter γ can be estimated correctly. A large number of experiments demonstrate that the proposed method is more powerful in clustering benchmark datasets.

2 RelatedWork

There is a large number of KM extensions proposed in past years, such as [Pham, 2001; Stelios and Vassilios, 2010; Nie et al., 2014a]. Due to the limited space, we only review some closely relevant work as follows.

2.1 Fuzzy C-Means Algorithm

FCM is one of the most popular fuzzy clustering techniques, which was proposed by Dunn [Dunn, 1973] and eventually modified by Bezdek [Bezdek, 1980]. In this approach, the data points have their membership values with the cluster centers, which will be updated iteratively.

Let X=[x1↪ ▷▷▷↪ xn] be a set of n objects. To cluster X into c clusters, the standard fuzzy C-Means algorithm minimizes the following objective function:

where f is called the loss function, m is an appropriate level of cluster fuzziness, vk is interpreted as the centroid of the k-th cluster, and uik denotes the grade of membership of the i-th object in the k-th cluster and satisfies the following conditions:

To minimize (1) subject to Pck=1uik =1 by using Lagrangian multiplier method, a considered point was demonstrated to be a local minimum solution of (1) if and only if:

where dik =kxi-vkk2 .

The iterative FCM algorithm is stopped if max♣u(t+1) ik - u(t) ik ♣ < " where " is a small positive integer and t denotes number of iterations [Bezdek, 2013; Isazadeh and Ghorbani, 2003]. Noted that for m= 1, FCM algorithm converges in theory to the traditional K-Means solution [Smyth, 2000].

2.2 Agglomerative Fuzzy K-Means Algorithm

To tackle some issues during clustering, like the number of clusters and initial cluster centers, [Li et al., 2008] introduced a penalty term to the objective function of FKM. Clustering X into c clusters by this algorithm is to minimize the following objective function:

subject to

where U is an n-by-c partition matrix, V is an c-by-m matrix containing the cluster centers, and dik is a dissimilarity measure between the k-th cluster center and the i-th object.

The alternating minimization procedure between membership matrix U and cluster center matrix V can be applied to (4), which follows:

The first term in (4) is the cost function of the standard KMeans algorithm. The second term is added to maximize the negative objects-to-clusters membership entropy in the clustering process, which can simultaneously minimize the within cluster dispersion and maximize the negative weight entropy to determine clusters to contribute to the association of objects.

3 The ProposedMethod

3.1 Formulation

To overcome the outlier sensitivity problem of the data-driven term and achieve an optimal approximate solution in related work, we formulate a robust and sparse fuzzy K-Means clustering combined with different kinds of norms, like `2↪1-norm

[Ding et al., 2006] and capped `1-norm [Jiang et al., 2015], to make the proposed algorithm more robust to outliers. It is to minimize the following objective function:

subject to

where U is an n-by-c membership matrix. ˜ dik is a measure which can be flexibly defined as some alternative norms to measure the dissimilarity by different ways. For instance, ˜ dik = kxi -vkk22 is commonly used in clustering. In this paper, we replace this Least Square term with Least Absolute term ˜ dik = kxi-vkk2 (`2↪1-norm) and the capped `1-norm term ˜ dik=min(kxi-vkk2↪ ") (where " is a threshold), where they can be more robust to outliers than Least Square.

3.2 The Properties of the Algorithm

Fuzziness

According to [Bauckhage, 2015], traditional K-Means clustering was rigorously established where the membership matrix U is binary such that each row of U contains a single 1 and c-1 elements that are 0. The rows of U sum up to 1 and its column sums indicate the number elements per cluster.

Differed from hard K-Means clustering, the proposed method relaxes each element of U into a nonnegative value less than 1 under the constraint conditions. Note that the proposed method is different from fuzzy C-Means clustering, because the latter also requires to choose an appropriate level of cluster fuzziness m ≥ 1 (mostly m=2), and the former presets m=1.

Robustness

It is well known that the quadratic loss function is not robust to outliers. To overcome this weakness, the quadratic loss function should be replaced by an insensitive one to outliers, e.g. `2↪1-norm and capped `1-norm. In this paper, we use the objective functions based on `2↪1-norm and capped `1-norm, respectively. Based on `2↪1-norm which is not squared and usually used to induce sparsity, outliers have less importance than the squared one. Based on the capped `1-norm, the loss function treats r equally if krk2 is bigger than ", which is more robust to outliers than the squared one.

Sparseness

During clustering, the proposed algorithm tries to minimize the robust residual term and consider the sparsity of memberships of each object being assigned to different clusters simultaneously. The importance of each part in the minimization process of (7) is balanced by the parameter γ.

It can be seen that the square of memberships of each object measures whether the object is assigned to a single cluster or several clusters. In the case of assigning to a single cluster, Pck=1 u2ik is equal to 1. In the case of assigning to several clusters, Pck=1 u2ik is a positive number and much smaller than 1. Minimization of the sum of memberships of each object is to assign each object to more clusters instead of a single cluster.

If the parameter γ is zero, the membership vector of each object is sparse (Only one element is nonzero and others are zero). When γ is greater than zero, the membership vectors are less sparse than that in case of γ being zero. The sparseness of the membership vectors is a progressive change when we tune γ. Along with the gradual increase of γ, membership vectors contain a growing number of nonzero elements. When γ reaches up to a large value, all elements of membership vectors are nonzero, and membership vectors are nonsparse at this time. Thus, the parameter γ controls the sparseness degree of the membership vectors. One of our goals is to find the reasonable sparseness of membership vectors to obtain more accurate clustering results.

3.3 The Optimization Procedure

In this paper, we want to find a set of highly accurate centroids to better group objects. An straightforward way is to use Least Square loss function. However, to provide better robustness, we go further to use `2↪1-norm and capped `1norm loss functions, respectively. Concretely, the objective values of capped `1-norm loss dose not increase any more if k ÷ k2 is larger than ". Therefore, `2↪1-norm loss is more robust than Least Square loss, but might be less robust than capped `1-norm. Thus, the objective function of our robust and sparse fuzzy K-Means clustering algorithms are formulated using different robust norms (`2↪1-norm and capped `1norm) as follows:

Although the norms are different to each other, both of them can be optimized by using the iterative re-weighted method proposed in [Nie et al., 2010; 2014b]. These two methods ((8) and (9)) extend FKM with robust norms and regularizations to reduce the effect of outliers and keep the memberships with proper sparsity.

Concretely, U, V and auxiliary variable sik are updated by following updating rules:

For the (8), auxiliary variable sik is defined as 1 2kxi-vkk2 . For the (9), auxiliary variable sik is defined as follows:

From two definitions of sik, it is obvious that when a sample is not outlier, namely, kxi-vkk2  ", this sample with lower reconstruction error has higher weight. At this moment, our two methods are equivalent. When a sample is a outlier, namely kxi-vkk2 > ", this sample with higher reconstruction error has lower weight. Nevertheless, we expect to enhance the outlier insensitiveness of our method, and even hope the weight of outlier to be 0. Thus, to provide better robustness, we go further to solve the problem of (9).

The (10) is convex separately with respect to U and V, thus we solve it by updating U and V alternately.

With V fixed, the objective function becomes:

For each xi, (12) can be separated into n subproblems:

where ui is the i-th line of matrix U and hik =sikkxi-vkk22 is an element of matrix H. After being simplified, (13) can be written as:

where ui is a variable to be optimized and the row vector ˜hi = -hi 2γ is a constant in this stage. We utilize the technique of [Huang et al., 2015] to solve (14) that updates the membership vector. It is the fact that the solution of (14) must be sparse.

With U fixed, the objective of (10) becomes:

which can be decomposed into c independent problems as follows:

Each iteration of (16) involves minimizing a quadratic objective function. Using the Lagrange multiplier method, the global optimum can be reached by taking derivatives and setting them to zeros. Thus, there is:

The whole algorithm of our method is listed in Algorithm 1. Because the proposed RSFKMmeets the conditions of the references [Nie et al., 2010; 2014b], it can be easily proved that Algorithm 1 is absolutely converged.

In addition, assuming that U(t) and V(t) are computed from the solution of the t-th iteration, we can update the nonnegative auxiliary variable sik according to (11) by the current V(t) when we solve (9). When we solve (8), we can update sik according to 1 2kxi-vkk2 with the current V(t) .

4 Experiments

4.1 Datasets

We evaluate the performance of the proposed method (RSFKM) on three benchmark datasets in terms of two standard

Algorithm 1 The algorithm of RSFKM method

Input:

Data matrix X, the number of clusters c, regularization parameter γ and threshold ".

Output:

Clustering indicator matrix U and Cluster centroid matrix V. Initialization:

Set t = 0. Initialize U, V and auxiliary variable s by U1 = 1, U ≥ 0, and sik =1 for i = 1↪ ▷ ▷ ▷ ↪ n; k = 1↪ ▷ ▷ ▷ ↪ c.

While not converge do

• 1: Solve U by (14);
• 2: Update V by (17);
• 3: Update sik by (11) if solve (9). Update sik using 1 2kxi-vkk2 if solve (8).

End While, return U, V.

clustering evaluation metrics, namely, Accuracy (ACC) and Normalized Mutual Information (NMI) [Cai et al., 2005]. Among those, two datasets are image datasets, COIL-20 1 and COIL-100 2 . The rest is the MNIST 3 database of handwritten digits. We provide here four smaller subsets (MINIST2K2K, MINIST-10K, MINIST-TEST and MINIST-ORIG) fromMINIST. Table 1 summarizes the characteristics of these datasets used in our experiments and Figure 1 shows some example images from different datasets.

4.2 Experiment Setup

Comparison Methods

We evaluate the performance of the proposed method on benchmark datasets. We compare our method RSFKM (with `2↪1-norm and capped `1-norm) with K-means (KM), fuzzy C-Means (FCM, m > 1), agglomerative fuzzy K-Means (AFKM), sparse fuzzy K-Means (SFKM). Concretely, KM and FCM are classic clustering methods. The difference of AFKM and SFKM is that they are derived from different cluster fuzziness m and different regularization terms. We compare with SFKM due to two reasons. First, it has close relation with the proposed method. Second, the comparison with SFKM can show the advantage of robustness in our method.

Parameter Discussion

There are two important parameters in RSFKM, namely regularization parameter γ and threshold value ". Each of them MINIST-ORIG 50▷46◦1▷94 48▷92 ◦0▷79 43▷29 ◦1▷34 51▷38 ◦1▷61 52▷23◦1▷23

1 http://www.cs.columbia.edu/CAVE/software/softlib/coil20.php

2 http://www.cs.columbia.edu/CAVE/software/softlib/coil100.php

3 http://yann.lecun.com/exdb/mnist/

Table 3: NMI(%◦std) of different methods on different benchmark datasets.

plays an important role in each algorithm and should be determined carefully.

For the regularization parameter γ, it puts a restriction on the minimum distance between a data point and a cluster center and prevents membership from having extreme values, 0 and 1. Large γ makes the regularization term to dominate the objective function, and thus makes uik to be approximately equal to 1c . Small γ makes the residual term to dominate the objective function, and thus makes uik to be sparse. The value of γ, therefore, should be chosen carefully to balance the residual term and the regularization term. In this paper, the optimal value of γ was set empirically using the grid search method in a range from [10-1 ↪ 101 ] every 0▷5 step.

For the threshold value ", it mainly controls the number of outliers and is related to the residuals of representations. If the residual of a sample to centroid is larger than ", it is regarded as outlier and not used to learn centroid matrix V since the corresponding sik is zero. If the residual of a sample to centroid is less than ", sik is nonzero. In order to minimize the objective function uiksikkxi-vkk22+u2ik , uik should be small, and there will be two extreme cases. The first case is that one membership value of the sample xi tends to 1 and others tend to 0, which makes the membership values too sparse and fi-

52.42◦1.12

nally degrades into a hard clustering. The second case is that all memberships of the sample xi become equally and their sum is 1, which makes the memberships not be sparse and finally degrades into the traditional FKM clustering. In order to avoid above two extreme cases, we need a tradeoff between the regularization parameter γ and the threshold value " in capped `1-norm. Here we select " in a range of [0↪ 3].

In our experiments, we tune γ and " appropriately using the grid search method based on different datasets. For different sets of (γ↪ "), we calculate average ACC and NMI by repeat clustering 10 times, and then report the best result for each method, respectively.

Intuitively, in Figure 2, we show some memberships of one sample on four methods KM, FCM, AFKM and RSFKM (with capped `1-norm) to demonstrate the appropriate sparseness of the proposed method.

4.3 Experiment Results

Table 2 and 3 summarize the results of all methods on the benchmark datasets. We bold the corresponding results if they are significant better than results from other methods. It can be observed that the proposed method (RSFKM) outperforms other methods on all datasets according to metrics of ACC and NMI.

In particular, our method RSFKM (whether with `2↪1-norm or with capped `1-norm) significantly gets a better result than K-Means, FCM, AFKM and SFKM on all datasets. It is obvious that compared with SFKM and RSFKM, both K-Means and FCM cannot obtain good performance during clustering, due to the lack of robust and sparse information. In addition, our method RSFKM (with `2↪1-norm or capped `1-norm) can achieve more robustness than SFKM on almost all datasets. Meanwhile we observe that SFKM has done much better than K-Means and FCM. It can be seen that adding the regularization term into the objective function is essentially necessary. Finally, although RSFKMs (with `2↪1-norm and capped `1norm) are all proposed by this paper, the robustness of them is different and usually depends on the different datasets. Note that the latter could get better results with proper parameters

(regularization parameter γ and the threshold " of the capped `1-norm).

In a word, the experimental results in Table 2 and 3 demonstrate that our method taking into account both the robustness of the residual term and the sparseness of membership values for each sample can achieve better performance comparing with other state-of-the-art clustering approaches.

Furthermore, we test the convergence of RSFKM on COIL-20, COIL-100 and MINIST datasets. The results are shown in Figure 3. (a)-(f) denote the convergence curves of RSFKMwith capped `1-norm. (g)-(l) denote the convergence curves of RSFKMwith `2↪1-norm. It is can be seen that RSFKM algorithm can absolutely converge with few iteration steps.

5 Conclusion

In this paper, we have proposed a novel method, called robust and sparse fuzzy K-Means clustering algorithm, to obtain a more accurate clustering result. The proposed method minimized the objective function to deal with the effect of outliers considering sparse membership values by a re-weighted method, which is the weighted sum of the fuzzy K-Means with robust norms (`2↪1-norm and capped `1-norm) and the sparse quadratic regularization. The effectiveness of our method was demonstrated by a number of experiments on three benchmark datasets. In addition, determination of the regularization parameter is an important problem, and we analyzed its change strategy and set it empirically under investigation.

Acknowledgments

This work was supported in part by the National Science Foundation of China under Grants 61522207 and 61473231.