# Generalized Fuzzy C-Means Clustering with Improved Fuzzy Partitions and Shadowed Sets

Authors: Seyed Mohsen Zabihi; Mohammad-R Akbarzadeh-T
Journal: ISRN Artificial Intelligence
 (2012)

---

## Abstract

Clustering involves grouping data points together according to some measure of similarity. Clustering is one of the most significant unsupervised learning problems and do not need any labeled data. There are many clustering algorithms, among which fuzzy c-means (FCM) is one of the most popular approaches. FCM has an objective function based on Euclidean distance. Some improved versions of FCM with rather different objective functions are proposed in recent years. Generalized Improved fuzzy partitions FCM (GIFP-FCM) is one of them, which usesLp norm distance measure and competitive learning and outperforms the previous algorithms in this field. In this paper, we present a novel FCM clustering method with improved fuzzy partitions that utilizes shadowed sets and try to improve GIFP-FCM in noisy data sets. It enhances the efficiency of GIFP-FCM and improves the clustering results by correctly eliminating most outliers during steps of clustering. We name the novel fuzzy clustering method shadowed set-based GIFP-FCM (SGIFP-FCM). Several experiments on vessel segmentation in retinal images of DRIVE database illustrate the efficiency of the proposed method.


---

## Body

## 1. Introduction

One of the first mental activities of humans is clustering, where the goal is to find data structures and assign similar data to a group (cluster). Actually it tries to put unlabeled data into groups so that data points in a group are more similar to each other compared to those in other groups. It means that the goal is to maximize the intraclass likeness while minimizing the intercluster similarity.Clustering has been used in diverse areas like machine vision and pattern recognition as well as in medical applications. There is a wide array of clustering algorithms [1–8]. But they can be generally classified to some groups as listed below:(i)
exclusive clustering: one data point to belong to one cluster. No Overlapping (K-means, any linear classifier belongs to this kind),(ii)
overlapping clustering: data can be in two or more clusters (fuzzy C-means),(iii)
hierarchical clustering,(iv)
probabilistic clustering (model based).Among the above, overlapping clustering or partition-based clustering methods that group objects with some membership degrees are often used to handle noisy and uncertain data and hence can have a good utility in many practical applications.Probabilistic and fuzzy clustering are two kinds of overlapping clustering methods when we consider the uncertainty in data. Actually, crisp clustering can be considered as a special type of these two clustering methods. FCM [9] is the most popular one among the other presented fuzzy clustering methods. It goes without saying that the later proposed fuzzy clustering methods are based on FCM in general. FCM and its derived methods cluster data according to an objective function and several constraints. For instance, the summation of all the memberships of each data point to all clusters must be one.A novel presentation of constraining the membership functions can be seen in [10]. In addition, a new FCM algorithm is also presented in [10], which is based on improved fuzzy partitions, named IFP-FCM. This algorithm is driven by crisp membership degrees, so it may seem resistant to noise and outliers. However, the fuzziness index m [10] is fixed and cannot be changed. Since the clusters in a data set have different densities, the performance of FCM may significantly depend on the choice of fuzziness index. Therefore, a good value of this parameter should be adopted to be consequent on the data distribution in data set [11]. So, another objective function should be introduced so that adjusts m. In [12] GIFP-FCM is proposed that does not restrict m to a fixed value. There is a parameter in this algorithm (α) that connects it to FCM and IFP-FCM. We can say briefly that this algorithm has the benefit of IFP-FCM and also generalizes it because of the various values that m can get.In the paper, we present a novel Shadowed set-based Generalized Improved fuzzy partitions FCM (SGIFP-FCM). This new algorithm uses shadowed sets and the most important idea of the proposed method is to improve performance of GIFP-FCM in the stage of determining new cluster centers at each iteration. This is accomplished by removing the outliers and unsuitable data that have negative effects on structure of clusters. We will see that it improves the results of clustering in noisy systems and also it decreases the time of clustering in comparison with GIFP-FCM and the previous methods.Clustering methods are often used in image processing applications such as in image segmentation [7]. To investigate the proficiency and utility of the presented method, the algorithm is applied here to vessel extraction of retinal images. These images are often used in medical applications to diagnosis of some diseases such as diabetes. The proposed approach is compared against other competing clustering algorithms on this database as well as an artificial dataset.Some fuzzy clustering algorithms are briefly reviewed in Section2. Section 3 describes the proposed algorithm (SGIFP-FCM) in detail. Section 4 shows experimental results of our work. Finally, conclusion is brought in Section 5.


## 2. Previous Fuzzy Clustering Algorithms

Many areas such as pattern recognition and machine vision utilize fuzzy clustering in solving their problems. A great number of fuzzy clustering algorithms are there, and it is noticeable that most of them use distance criteria. One of these algorithms that is so common and popular is FCM [13]. Reverse distance is used in FCM to fuzzy memberships.In FCM, each feature vector can belong to every cluster with a coefficient between zero and one. Finally, algorithms label each data point (feature vector) based on the maximum coefficient of this data point over all clusters.The fuzzy membership matrix and the cluster centers are computed by minimizing the following partition formula:(1)Jf(C,m)=∑i=1c∑k=1n(ui,k)mdi,ksubjectto∑i=1cui,k=1.In this equation,n denotes the number of data, c the number of clusters, ui,k the fuzzy membership of the kth data point to the ith cluster, di,k the Euclidean distance between the data point and the cluster center, and m∈(1,∞) a fuzzy weighting factor that defines the degree of fuzziness of the results. The data class becomes fuzzier and less discriminating with increasing m. In general, m=2 is chosen (it is mentioned that this value of m does not produce optimal solution for all problems).The constraint in (1) implies that each point must entirely distribute its membership among all the clusters. The cluster centers (centroids) are determined as the fuzzy-weighted center of gravity of the data X,(2)vi=∑k=1n(ui,k)mxk∑k=1n(ui,k)m,i=1,2,…,c.Sinceui,k affects the computation of the cluster center vi, the data with a high membership will influence the prototype location more than points with a low membership. For the fuzzy C-means algorithm, distance di,k is defined as follows:(3)(di,k)2=‖xk-vi‖2.The cluster centersvi represent the typical values of that cluster, whereas the ui,k component of the membership matrix denotes the extent to which the data point xk is similar to its prototype. The minimization of the partition functional (1) will give the following expression for the membership:(4)ui,k=1∑j=1C(di,k/dj,k)1/(m-1).Equation (4) is determined in an iterative way since the distance di,k depends on membership ui,k.The procedure to calculate the FCM is as follows.(1)
Opt for the number of clustersc, 2≤c<n; Choose m, 1≤m<∞. Initialize U(0).(2)
Calculate the cluster centersvi using  (2).(3)
Calculate new partition matrixU(1) using  (4).(4)
CompareU(j) and U(j+1). If the variation of the membership degree uk,i, calculated with an appropriate norm, is smaller than a given threshold, terminate the algorithm, in other respects go back to step (2).FCM clustering has a shortcoming in producing membership functions. For instance, these functions are not bounded and do not have to decay rapidly, so cannot be understood locally. Distances to the Voronoi cell of the cluster instead of using distances to the cluster prototypes are applied in IFP-FCM method [10] by changing FCM’s objective function. Objective function of IFP-FCM can be seen below:(5)JIFP-FCM=∑i=1c∑j=1nuij2d2(xi,vi)-∑j=1naj∑i=1c(uij-12)2.In this equationaj is a rewarding parameter. IFP-FCM seems more resistance to outliers and even noise.Fuzzy indexm is equal to 2 in many cases for FCM and IFP-FCM. Despite the fact that this parameter is required to be various or in different values for optimal or near-to-optimal results, fuzziness index mshould be flexible and generalized. To do that, another objective function is necessary accordingly.For that reason, GIFP-FCM clustering approach was presented in [12]. It is based on the rival-penalized competitive learning (RPCL) concept [14]:(6)JGIFP-FCM=∑i=1c∑j=1nuijmd2(xi,vi)+∑j=1naj∑i=1cuij(1-uijm-1).It is clear that the new objective function uses the opinion of RPCL that for minimizing, only a specifieduij gets the maximum reward and the other ukj (rivals) get the minimum reward.Authors in [12] showed that GIFP-FCM can convert to FCM or IFP-FCM with choosing proper values for some parameters and also it converges quicker rather than the other two clustering algorithms that we discussed before, but computational complexity of GIFP-FCM is the same as theirs. Fuzziness index m in IFP-FCM was equal to 2, whereas this parameter can be changed in GIFP-FCM properly.


## 3. The Proposed Method

In this section, we briefly describe shadowed sets and then try to propose our new clustering algorithm, SGIFP-FCM.


### 3.1. Shadowed Sets

Suppose that A is a fuzzy set inX which is an interval-valued one and maps element of X into 0,1, and the unit interval [0,1]. Shadowed set B can be defined by this fuzzy set A so that B is a mapping B:X→{0,1,[0,1]}, where 0,1, and [0,1] illustrate complete exclusion from B, complete inclusion in B, and complete ignorance, respectively. Shadowed sets have some characteristics. For example, they are isomorphic with a three-valued logic. Shadowed sets and logic have similar operations. (For more details you can refer to [15, 16]).Figure1 depicts a fuzzy set and also its shadowed set.Figure 1
Fuzzy set A and its shadowed set (B).


### 3.2. Creating a Shadowed Set

Pedrycz in [17] presented the way of creating a shadowed set from a fuzzy set. Two threshold of α and β should be defined at first as follows: α∈[0,0.5] and β∈[0.5,1]; next, low membership grades and high membership grades should be changed to 0 and 1, respectively. At last, memberships are converted to some grades between α and β in [0,1]. Figure 2 shows this trend for a unimodal fuzzy set.Figure 2
Constructing of a shadowed set B.In Fact, the thresholdsα and 1-α are proper choices, since the threshold α is an essential part in process of constructing a shadowed set. So, finding such an optimal threshold is of utmost importance. Pedrycz considers the balance of uncertainty for this issue. The balance of uncertainty can be preserved by recompensing the changes of membership grades to zero and one for by creating the shadowed set that “absorb” the former elimination of partial membership at low and high ranges of membership.According to Figure2, the balance equation for fuzzy set with discrete membership function is defined as(7)Ω1+Ω2=Ω3,Ω1=∑ui≤αui,Ω2=∑ui≥1-α(1-ui),Ω3=card{ui∣α<ui<1-α}.It is better to change the above problem to (8) so that find the optimal value of parameter α(8)MinimizeQ(α)=|Ω1+Ω2-Ω3|.


### 3.3. Applying Shadowed Sets to GIFP-FCM

As we saw, clusters centers are modified in each iteration of the clustering algorithm and in addition to this, all data are participated in computation of each cluster center that increases time complexity of the algorithm. For decreasing the time of algorithm and improve the efficiency, we use shadowed sets to remove unsuitable data, outliers, and also data in borders before determining centers of clusters. We show partitions matrix withU=(uij)c×n and each row of this matrix describes a cluster. We should compute optimal threshold αi (i=1,2,…,c) for each row and then can remove outliers. αi (i=1,2,…,c) can be computed with solving the below optimization problem:(9)MinimizeQ(α)=|Ωi1+Ωi2+Ωi3|,
where(10)Ωi1=∑j:uij≤αiuij,Ωi2=∑j:uij≥1-αi(1-uij),Ωi3=card{uij∣αi<uij<1-αi,j=1,2,…,n}.


### 3.4. SGIFP-FCM Algorithm

Now we can summarize our proposed algorithm (S FIFP-FCM) in some steps as follows.Step 1.
Set the number of clusters (c is between 1 and n) and also choose proper values for threshold of stopping algorithm (ε), parameter α′ in [0, 1) that determines the rate of rewarding, number of iterations and fuzziness index m, and initial values of uij.Step 2.
Compute the optimum valueα for each row of partition matrix using (9). If uij<α, it does not have any role in determining cluster center.Step 3.
Compute clusters centers(vi(l+1)) using
(11)vi(l+1)=∑j:uij≥αuijmxj∑j:uij≥αuijm(i=1,2,…,c).Step 4.
Compute membership functionsuij(l+1) using
(12)uij=1∑k=1c(d2(xj,vi)-α′min⁡1≤a≤cd2(xj,va)d2(xj,vk)-α′min⁡1≤a≤cd2(xj,va))1/(m-1).Step 5.
If the terminating condition is satisfied, the algorithm is finished, otherwise increase iteration number and go back to Step2.


## 3.1. Shadowed Sets

Suppose that A is a fuzzy set inX which is an interval-valued one and maps element of X into 0,1, and the unit interval [0,1]. Shadowed set B can be defined by this fuzzy set A so that B is a mapping B:X→{0,1,[0,1]}, where 0,1, and [0,1] illustrate complete exclusion from B, complete inclusion in B, and complete ignorance, respectively. Shadowed sets have some characteristics. For example, they are isomorphic with a three-valued logic. Shadowed sets and logic have similar operations. (For more details you can refer to [15, 16]).Figure1 depicts a fuzzy set and also its shadowed set.Figure 1
Fuzzy set A and its shadowed set (B).


## 3.2. Creating a Shadowed Set

Pedrycz in [17] presented the way of creating a shadowed set from a fuzzy set. Two threshold of α and β should be defined at first as follows: α∈[0,0.5] and β∈[0.5,1]; next, low membership grades and high membership grades should be changed to 0 and 1, respectively. At last, memberships are converted to some grades between α and β in [0,1]. Figure 2 shows this trend for a unimodal fuzzy set.Figure 2
Constructing of a shadowed set B.In Fact, the thresholdsα and 1-α are proper choices, since the threshold α is an essential part in process of constructing a shadowed set. So, finding such an optimal threshold is of utmost importance. Pedrycz considers the balance of uncertainty for this issue. The balance of uncertainty can be preserved by recompensing the changes of membership grades to zero and one for by creating the shadowed set that “absorb” the former elimination of partial membership at low and high ranges of membership.According to Figure2, the balance equation for fuzzy set with discrete membership function is defined as(7)Ω1+Ω2=Ω3,Ω1=∑ui≤αui,Ω2=∑ui≥1-α(1-ui),Ω3=card{ui∣α<ui<1-α}.It is better to change the above problem to (8) so that find the optimal value of parameter α(8)MinimizeQ(α)=|Ω1+Ω2-Ω3|.


## 3.3. Applying Shadowed Sets to GIFP-FCM

As we saw, clusters centers are modified in each iteration of the clustering algorithm and in addition to this, all data are participated in computation of each cluster center that increases time complexity of the algorithm. For decreasing the time of algorithm and improve the efficiency, we use shadowed sets to remove unsuitable data, outliers, and also data in borders before determining centers of clusters. We show partitions matrix withU=(uij)c×n and each row of this matrix describes a cluster. We should compute optimal threshold αi (i=1,2,…,c) for each row and then can remove outliers. αi (i=1,2,…,c) can be computed with solving the below optimization problem:(9)MinimizeQ(α)=|Ωi1+Ωi2+Ωi3|,
where(10)Ωi1=∑j:uij≤αiuij,Ωi2=∑j:uij≥1-αi(1-uij),Ωi3=card{uij∣αi<uij<1-αi,j=1,2,…,n}.


## 3.4. SGIFP-FCM Algorithm

Now we can summarize our proposed algorithm (S FIFP-FCM) in some steps as follows.Step 1.
Set the number of clusters (c is between 1 and n) and also choose proper values for threshold of stopping algorithm (ε), parameter α′ in [0, 1) that determines the rate of rewarding, number of iterations and fuzziness index m, and initial values of uij.Step 2.
Compute the optimum valueα for each row of partition matrix using (9). If uij<α, it does not have any role in determining cluster center.Step 3.
Compute clusters centers(vi(l+1)) using
(11)vi(l+1)=∑j:uij≥αuijmxj∑j:uij≥αuijm(i=1,2,…,c).Step 4.
Compute membership functionsuij(l+1) using
(12)uij=1∑k=1c(d2(xj,vi)-α′min⁡1≤a≤cd2(xj,va)d2(xj,vk)-α′min⁡1≤a≤cd2(xj,va))1/(m-1).Step 5.
If the terminating condition is satisfied, the algorithm is finished, otherwise increase iteration number and go back to Step2.


## 4. Results

In the first experiment, we create a random and artificial data set with three clusters or groups of data as it is shown in Figure3. We can observe the results of these data clustering with three algorithms of FCM, GIFP-FCM, and SGIFP-FCM in Figure 4. Almost FCM and SGIFP-FCM depict similar results and detect the three clusters correctly, but in GIFP-FCM contrary to SGIFP-FCM all data are participated in determining centers and then could not cluster data exactly. This is because of the effects of outliers and data in borders of clusters on determining centers, which are removed in SGIFP-FCM.Figure 3
Data set of the first experiment with three clusters.Clustering results of data set in Figure3. with methods of (a) FCM, (b) GIFP-FCM, and (c) SGIFP-FCM.
(a)(b)(c)In Figure4, clusters are distinguished with different colors and centers of clusters are specified with “+”. Values of parameters α and m are supposed to be 2 and 0.9, respectively.In the second experiment, we use retinal images of DRIVE database [18]. We want to detect vessels in these images using clustering methods. For this purpose, we first extract some features for each pixel of the processed image and then we get these feature vectors to clustering algorithm to label the pixels as vessels or nonvessels or clearly divide the pixels into two clusters of vessels and nonvessels. There are many feature extraction methods. We use LBP (Local Binary Patterns) method for feature extraction [19]. The features vector of each pixel is composed of gray level intensity, variance, and LBP value in three local windows around the central pixel [20].Sample of a segmented retina image using the proposed algorithm (SGIFP-FCM) is presented in Figure5 along with manually segmented version of the image.Clustering result, (a) segmentation using SGIFP-FCM, and (b) manually segmented image.
(a)(b)To evaluate the algorithm, we calculated true positive ratio (TPR) and False Positive Ratio (FPR). TPR is number of pixels of resulting image, which are correctly clustered as vessel (according image generated by human expert) to total number of pixels of human-expert generated image that are labeled as vessel. FPR is the number of pixel of resulting image, which are incorrectly clustered as vessel to total number of pixel of human-expert generated image that are labeled as background.Table1 compares performance of retina vessel extraction with SGIFP-FCM and GIFP-FCM versus 2nd human observer with regard to the TPR, FPR, and time of clustering.Table 1
Comparison of SGIFP-FCM and in retina vessel extraction.
AlgorithmTPRFPRTime(S)2nd human observer0.77610.0275—SGIFP-FCM0.69440.0292.76GIFP-FCM0.68210.0323.41The results in Table1 are average results of 20 test images of DRIVE database.As we see in Table1, performance of SGIFP-FCM is better than GIFP not only in extracted vessels but also in time consuming.


## 5. Conclusion

In this paper, we present a Generalized Fuzzy C-Means Clustering With Improved Fuzzy Partitions and Shadowed sets (SGIFP-FCM). As is illustrated, this new algorithm improves the previous clustering algorithms such as GIFP-FCM in noisy data sets. In the proposed algorithm, the effects of outliers and noisy data are reduced in determining clusters centers using shadowed sets. Finally this new algorithm is tested on several experiments. Performance of this method is evaluated on image segmentation application (retina images) and because there are many noises in these images this algorithm presented better results than GIFP-FCM algorithm.



---

*Source: 929085-2012-01-18.xml*