Source-linked AI summary
A Comparative study Between Fuzzy Clustering Algorithm and Hard Clustering Algorithm
Dibya Jyoti Bora, Dr. Anil Kumar Gupta
TL;DR
Clustering requires methods that group similar data, but fuzzy and hard algorithms differ in how they assign membership. This paper experimentally compares FCM and K-means, concluding that K-means is faster and less complex, while FCM suits overlapping clusters.
Problem
The paper addresses the need to compare fuzzy and hard clustering approaches for grouping similar data into distinct clusters.
Method
The paper discusses FCM and K-means, then experimentally compares them using the Iris dataset and computational time and complexity.
Results
K-means is faster than FCM computationally and becomes less complex as the number of clusters increases relative to FCM.
Takeaways & Limitations
K-means is suitable for exclusive clustering, whereas FCM is suitable when data may partially belong to overlapping clusters.
Takeaways & Limitations
K-means is significantly sensitive to randomly selected initial cluster centers, although repeated runs can reduce this effect.
Abstract
from arXiv · showhide
Data clustering is an important area of data mining. This is an unsupervised study where data of similar types are put into one cluster while data of another types are put into different cluster. Fuzzy C means is a very important clustering technique based on fuzzy logic. Also we have some hard clustering techniques available like K-means among the popular ones. In this paper a comparative study is done between Fuzzy clustering algorithm and hard clustering algorithm
1. Introduction:
Data clustering divides data into groups with high within-cluster similarity and low between-cluster similarity. The introduction contrasts soft fuzzy clustering, which permits graded membership, with exclusive hard clustering.
- 1. Introduction:: Data clustering groups similar data elements into clusters characterized by high intra-cluster similarity and low inter-cluster similarity.
- 1. Introduction:: Soft clustering assigns each point membership degrees across two or more clusters, making it more natural when classes overlap.Boundary objects receive membership values between 0 and 1 rather than being forced into a single class.
- 1. Introduction:: Hard clustering assigns each datum exclusively to one cluster; Fuzzy C Means and K-means represent prominent soft and hard techniques, respectively.
2. Fuzzy C Means Clustering:
Fuzzy C-means (FCM) is an unsupervised clustering technique that assigns each data point a degree of membership in each cluster. It groups multidimensional data through iterative optimization of memberships and cluster centers.
- 2. Fuzzy C Means Clustering:: FCM assigns each data point a membership grade, enabling gradual rather than exclusive cluster membership.
- 2. Fuzzy C Means Clustering:: FCM groups multidimensional data into a specified number of clusters using fuzzy partitioning.
- 2. Fuzzy C Means Clustering:: The method minimizes an objective function parameterized by membership degrees, cluster centers, data points, dimensionality, and a norm-based similarity measure.
- 2. Fuzzy C Means Clustering:: Fuzzy partitioning iteratively updates memberships and cluster centers until a termination criterion is met, converging to a local minimum or saddle point.
3. Update U(k) , U(k+1)
The update step uses a membership matrix U to represent each datum’s degree of membership in cluster centers. Iteration stops when the change between U(k+1) and U(k) falls below the specified threshold.
- 3. Update U(k), U(k+1): The algorithm stops when || U(k+1) - U(k)|| is below the specified threshold; otherwise, it returns to step 2.
- 3. Update U(k), U(k+1): The membership matrix U contains values between 0 and 1 that quantify each datum’s membership in cluster centers.This matrix captures the fuzzy behavior of FCM through its membership function.
3. K-Means Algorithm:
K-Means is a hard clustering algorithm that partitions n objects into k clusters by optimizing similarity around cluster centroids. It iteratively assigns points to the nearest centroid and recomputes centroids, but is sensitive to their random initialization.
- K-Means Algorithm: K-Means partitions n objects into k clusters, seeking high intra-cluster and low inter-cluster similarity using one centroid per cluster.
- K-Means Algorithm: The algorithm selects k initial centroids, assigns each point to its closest centroid, recomputes cluster centroids, and repeats until centroids stop changing.
- K-Means Algorithm: K-Means is significantly sensitive to randomly selected initial cluster centers, so multiple runs can reduce this effect.
- K-Means Algorithm: The method is simple, widely adapted across problem domains, and suitable for randomly generated data points.
4. Experimental Results:
On the Iris dataset, K-Means required less computation time than Fuzzy C Means and had lower time-complexity growth as the number of clusters increased. K-Means achieved a best total distance sum of 57.2285 in 1.4531 seconds, while Fuzzy C Means reached an objective-function value of 4168.707061 in 4 seconds.
- Experimental Setup: The experiments used the four-dimensional Iris dataset containing samples from three Iris species, with four measured sepal and petal features.The K-Means experiment specified 4 clusters and 5 replicates, while the Fuzzy C Means experiment used the same dataset for comparison.
- K-Means: 57.2285 was the best total sum of distances reported for K-Means, with 1.4531 seconds of elapsed time.
- Fuzzy C Means: Fuzzy C Means used 4 clusters, a maximum of 100 iterations, exponent 2.0, and minimum improvement 1e-6, reaching an objective-function value of 4168.707061 at iteration 28.The total elapsed time was 4 seconds.
- Comparison of FCM and K-Means: K-Means was faster than Fuzzy C Means, requiring 1.4531 seconds versus 4 seconds in the experiments.
- Comparison of FCM and K-Means: K-Means had lower time-complexity growth than Fuzzy C Means as the number of clusters increased.The reported complexities are O(ncdi) for K-Means and O(ndc^2i) for Fuzzy C Means.
6. Conclusion:
The conclusion states that clustering algorithm choice depends on data type and application purpose: K-Means suits exclusive clustering, while FCM suits overlapping data. It also reports that K-Means outperforms FCM in computational time because FCM performs more fuzzy-logic calculations.
- 6. Conclusion:: K-Means is suitable for exclusive clustering tasks, whereas FCM is suitable for overlapping clustering tasks.The paper ties algorithm selection to the type of data and the purpose of the clustering application.
- 6. Conclusion:: Some data cannot be considered to belong exclusively to one cluster, motivating fuzzy clustering for cases involving overlapping membership.The passage notes that data properties may contribute to more than one cluster, although the supplied text is truncated.
- 6. Conclusion:: K-Means performs better than FCM in computational time because fuzzy clustering requires more fuzzy-logic-based calculations.The conclusion attributes FCM’s comparatively higher computational time to its additional fuzzy-logic calculations.