Fuzzy clustering

Machine learning and data mining

Problems Classification Clustering Regression Anomaly detection Association rules Reinforcement learning Structured prediction Feature engineering Feature learning Online learning Semi-supervised learning Unsupervised learning Learning to rank Grammar induction
Supervised learning (classification • regression) Decision trees Ensembles (Bagging, Boosting, Random forest) k-NN Linear regression Naive Bayes Neural networks Logistic regression Perceptron Relevance vector machine (RVM) Support vector machine (SVM)
Clustering BIRCH Hierarchical k-means Expectation-maximization (EM) DBSCAN OPTICS Mean-shift
Dimensionality reduction Factor analysis CCA ICA LDA NMF PCA t-SNE
Structured prediction Graphical models (Bayes net, CRF, HMM)
Anomaly detection k-NN Local outlier factor
Neural nets Autoencoder Deep learning Multilayer perceptron RNN Restricted Boltzmann machine SOM Convolutional neural network
Reinforcement Learning Q-Learning SARSA Temporal Difference (TD)
Theory Bias-variance dilemma Computational learning theory Empirical risk minimization Occam learning PAC learning Statistical learning VC theory
Machine learning venues NIPS ICML ML JMLR ArXiv:cs.LG
Related articles List of datasets for machine learning research Outline of machine learning
Machine learning portal

Fuzzy clustering (also referred to as soft clustering) 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.^[1]

Comparison to hard clustering

In non-fuzzy clustering (also known as hard clustering), data is 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.

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,^[2] and improved by J.C. Bezdek in 1981.^[3]

General description

The fuzzy c-means algorithm is very similar to the k-means algorithm:

Choose a number of clusters.
Assign randomly to each point coefficients for being in the clusters.
Repeat until the algorithm has converged (that is, the coefficients' change between two iterations is no more than $\varepsilon$ , the given sensitivity threshold) :
- Compute the centroid for each cluster (shown below).
- For each 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 w_k(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:

$c_{k}={{\sum _{x}{w_{k}(x)}^{m}x} \over {\sum _{x}{w_{k}(x)}^{m}}}.$

Algorithm

The FCM algorithm attempts to partition a finite collection of $n$ elements $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$ cluster centres $C=\{{\mathbf {c}}_{1},...,{\mathbf {c}}_{c}\}$ and a partition matrix

$W=w_{{i,j}}\in [0,1],\;i=1,...,n,\;j=1,...,c$ , where each element, $w_{ij}$ , tells the degree to which element, $\mathbf {x} _{i}$ , belongs to cluster ${\mathbf {c}}_{j}$ .

The FCM aims to minimize an objective function:

{\underset {C}{\operatorname {arg\,min}}}\sum _{{i=1}}^{{n}}\sum _{{j=1}}^{{c}}w_{{ij}}^{m}\left\|{\mathbf {x}}_{i}-{\mathbf {c}}_{j}\right\|^{2},

where:

w_{{ij}}={\frac {1}{\sum _{{k=1}}^{{c}}\left({\frac {\left\|{\mathbf {x}}_{i}-{\mathbf {c}}_{j}\right\|}{\left\|{\mathbf {x}}_{i}-{\mathbf {c}}_{k}\right\|}}\right)^{{{\frac {2}{m-1}}}}}}.

Comparison to K-means clustering

K-means clustering also attempts to minimize the objective function shown above. This method differs from the k-means objective function by the addition of the membership values $w_{ij}$ and the fuzzifier, $m\in R$ , with $m\geq 1$ . The fuzzifier $m$ determines the level of cluster fuzziness. A large $m$ results in smaller membership values, $w_{ij}$ , and hence, fuzzier clusters. In the limit $m=1$ , the memberships, $w_{ij}$ , converge to 0 or 1, which implies a crisp partitioning. In the absence of experimentation or domain knowledge, $m$ is commonly set to 2. The algorithm minimizes intra-cluster variance as well, but has the same problems as k-means; the minimum is a local minimum, and the results depend on the initial choice of weights.

Related algorithms

Using a mixture of Gaussians along with the expectation-maximization algorithm is a more statistically formalized method which includes some of these ideas: partial membership in classes.

Another algorithm closely related to Fuzzy C-Means is Soft K-means.

Example

To better understand this principle, a classic example of mono-dimensional data is given below on an x axis.

This data set can be traditionally grouped into two clusters. By selecting a threshold on the x-axis, the data is separated into two clusters. The resulting clusters are labelled 'A' and 'B', as seen in the following image. Each point belonging to the data set would therefor have a membership coefficient of 1 or 0. This membership coefficient of each corresponding data point is represented by the inclusion of the y-axis.

In fuzzy clustering, each data point can have membership to multiple clusters. By relaxing the definition of membership coefficients from strictly 1 or 0, these values can range from any value from 1 to 0. The following image shows the data set from the previous clustering, but now fuzzy c-means clustering is applied. First, a new threshold value defining two clusters may be generated. Next, new membership coefficients for each data point are generated based on clusters centroids, as well as distance from each cluster centroid.

As one can see, the middle data point belongs to cluster A and cluster B. the value of 0.3 is this data point's membership coefficient for cluster A .^[4]

Applications

Clustering problems have applications in biology, medicine, psychology, economics, and many other disciplines.^[5]

Bioinformatics

In the field of bioinformatics, clustering is used for a number of applications. One use is as a pattern recognition technique to analyze gene expression data from microarrays or other technology.^[6] In this case, genes with similar expression patterns are grouped into the same cluster, and different clusters display distinct, well-separated patterns of expression. Use of clustering can provide insight into gene function and regulation.^[5] Because fuzzy clustering allows genes to belong to more than one cluster, it allows for the identification of genes that are conditionally co-regulated or co-expressed.^[7] For example, one gene may be acted on by more than one Transcription factor, and one gene may encode a protein that has more than one function. Thus, fuzzy clustering is more appropriate than hard clustering.

Image analysis

Fuzzy c-means has been a very important tool for image processing in clustering objects in an image. In the 70's, mathematicians introduced the spatial term into the FCM algorithm to improve the accuracy of clustering under noise.^[8] Alternatively, A fuzzy logic model can be described on fuzzy sets that are defined on three components of the HSL color space HSL and HSV; The membership functions aim to describe colors follow the human intuition of color identification.^[9]

Marketing

In marketing, customers can be grouped into fuzzy clusters based on their needs, brand choices, psycho-graphic profiles, or other marketing related partitions.^[10]

Image processing example

Image segmented by fuzzy clustering (top left) original (top right) clustered (bottom) membership map

Image segmentation using k-means clustering algorithms has long been used for pattern recognition, object detection, and medical imaging. However, due to real world limitations such as noise, shadowing, and variations in cameras, traditional hard clustering is often unable to reliably perform image processing tasks as stated above.^[11] Fuzzy clustering has been proposed as a more applicable algorithm in the performance to these tasks. Given is gray scale image that has undergone fuzzy clustering in Matlab.^[12] The original image is seen next to a clustered image. Colors are used to give a visual representation of the three distinct clusters used to identify the membership of each pixel. Below, a chart is given that defines the fuzzy membership coefficients of their corresponding intensity values.

Depending on the application for which the fuzzy clustering coefficients are to be used, different pre-processing techniques can be applied to RGB images. RGB to HCL conversion is common practice.^[13]

References

↑ "Fuzzy Clustering". reference.wolfram.com. Retrieved 2016-04-26.
↑ Dunn, J. C. (1973-01-01). "A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters". Journal of Cybernetics. 3 (3): 32–57. ISSN 0022-0280. doi:10.1080/01969727308546046.
↑ Bezdek, James C. (1981). Pattern Recognition with Fuzzy Objective Function Algorithms. ISBN 0-306-40671-3.
↑ "Clustering - Fuzzy C-means". home.deib.polimi.it. Retrieved 2017-05-01.
1 2 Ben-Dor, Amir; Shamir, Ron; Yakhini, Zohar (1999-10-01). "Clustering Gene Expression Patterns". Journal of Computational Biology. 6 (3-4): 281–297. ISSN 1066-5277. PMID 10582567. doi:10.1089/106652799318274.
↑ Valafar, Faramarz (2002-12-01). "Pattern Recognition Techniques in Microarray Data Analysis". Annals of the New York Academy of Sciences. 980 (1): 41–64. ISSN 1749-6632. doi:10.1111/j.1749-6632.2002.tb04888.x.
↑ Valafar F. Pattern recognition techniques in microarray data analysis. Annals of the New York Academy of Sciences. 2002 Dec 1;980(1):41-64.
↑ Ahmed, Mohamed N.; Yamany, Sameh M.; Mohamed, Nevin; Farag, Aly A.; Moriarty, Thomas (2002). "A Modified Fuzzy C-Means Algorithm for Bias Field Estimation and Segmentation of MRI Data" (PDF). IEEE Transactions on Medical Imaging. 21 (3): 193–199. PMID 11989844. doi:10.1109/42.996338 .
↑ Alireza, Kashani; Kashani, Amir; Milani, Nargess; Akhlaghi, Peyman; Khezri, Kaveh (2008). "Robust Color Classification Using Fuzzy Reasoning and Genetic Algorithms in RoboCup Soccer Leagues". Robocup. 5001: 548–555. doi:10.1007/978-3-540-68847-1_59
↑ "Download Limit Exceeded". citeseerx.ist.psu.edu. Retrieved 2016-04-26.
↑ Yang, Yong (2009). "Image segmentation based on fuzzy clustering with neighborhood information" (PDF). Optica Applicata. XXXIX.
↑ "Fuzzy Clustering - MATLAB & Simulink". www.mathworks.com. Retrieved 2017-05-03.
↑ Lecca, Paola (2011). Systemic Approaches in Bioinformatics and Computational Systems Biology. IGI Global. p. 9. ISBN 9781613504369.

External links

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.