Fuzzy clustering (also referred to as soft clustering or soft k-means) is a form of clustering in which each data point can belong to more than one cluster. Clustering or cluster analysis involves assigning data points to clusters such that items in the same cluster are as similar as possible, while items belonging to different clusters are as dissimilar as possible. Clusters are identified via similarity measures. These similarity measures include distance, connectivity, and intensity. Different similarity measures may be chosen based on the data or the application.
Comparison to hard clustering In non-fuzzy clustering (also known as hard clustering), data are divided into distinct clusters, where each data point can only belong to exactly one cluster. In fuzzy clustering, data points can potentially belong to multiple clusters. For example, an apple can be red or green (hard clustering), but an apple can also be red AND green (fuzzy clustering). Here, the apple can be red to a certain degree as well as green to a certain degree. Instead of the apple belonging to green [green = 1] and not red [red = 0], the apple can belong to green [green = 0.5] and red [red = 0.5]. These value are normalized between 0 and 1; however, they do not represent probabilities, so the two values do not need to add up to 1.
Membership Membership grades are assigned to each of the data points (tags). These membership grades indicate the degree to which data points belong to each cluster. Thus, points on the edge of a cluster, with lower membership grades, may be in the cluster to a lesser degree than points in the center of cluster.
Fuzzy C-means clustering One of the most widely used fuzzy clustering algorithms is the Fuzzy C-means clustering (FCM) algorithm.
History Fuzzy c-means (FCM) clustering was developed by J.C. Dunn in 1973, and improved by J.C. Bezdek in 1981.
General description The fuzzy c-means algorithm is very similar to the k-means algorithm:
Choose a number of clusters. Assign coefficients randomly to each data point for being in the clusters. Repeat until the algorithm has converged (that is, the coefficients' change between two iterations is no more than ε {\displaystyle \varepsilon } , the given sensitivity threshold) : Compute the centroid for each cluster (shown below). For each data point, compute its coefficients of being in the clusters.
Centroid Any point x has a set of coefficients giving the degree of being in the kth cluster wk(x). With fuzzy c-means, the centroid of a cluster is the mean of all points, weighted by their degree of belonging to the cluster, or, mathematically,
c k = ∑ x w k ( x ) m x ∑ x w k ( x ) m , {\displaystyle c_{k}={{\sum _{x}{w_{k}(x)}^{m}x} \over {\sum _{x}{w_{k}(x)}^{m}}},}
where m is the hyper- parameter that controls how fuzzy the cluster will be (Where the fuzzier cluster means the cluster is less clear, and a data point can belong to multiple clusters at the same time.). The higher it is, the fuzzier the cluster will be in the end.
Algorithm The FCM algorithm attempts to partition a finite collection of n {\displaystyle n} elements
X = { x 1 , . . . , x n } {\displaystyle X=\{\mathbf {x} _{1},...,\mathbf {x} _{n}\}} into a collection of c fuzzy clusters with respect to some given criterion. Given a finite set of data, the algorithm returns a list of c {\displaystyle c} cluster centres C = { c 1 , . . . , c c } {\displaystyle C=\{\mathbf {c} _{1},...,\mathbf {c} _{c}\}} and a partition matrix
W = w i , j ∈ [ 0 , 1 ] , i = 1 , . . . , n , j = 1 , . . . , c {\displaystyle W=w_{i,j}\in [0,1],\;i=1,...,n,\;j=1,...,c} , where each element, w i j {\displaystyle w_{ij}} , tells the degree to which element, x i {\displaystyle \mathbf {x} _{i}} , belongs to cluster c j {\displaystyle \mathbf {c} _{j}} . The FCM aims to minimize an objective function:
… excerpt ends here. Continue reading the full article.
