Abstract
Clustering is an unsupervised procedure that divides a set of objects into homogeneous groups. Two types of clustering are possible, Hard clustering and Soft clustering/Fuzzy clustering. Hard clustering is not feasible for complex datasets that contain uncertainty and overlapping clusters, whereas fuzzy clustering efficiently handles it. FCM is sensitive to the initial values and challenging to cluster nonlinear data. A new approach is implemented here with the Fuzzy c-Means (FCM) clustering algorithm to improve the performance. The Kernel function ensures the linear separability of complex clusters by projecting the feature space into a higher dimension and not subject to the initial values. The Kernel-based FCM (KFCM) optimized the clustering. The relevant features are considered for clustering, and it improves the validity of clusters. The irrelevant features blur the clusters and reduce the quality. Silhouette index (SI) and Davies-Bouldin index (DBI) have been used as the evaluation function. The experiments are conducted on two benchmark datasets and one artificial dataset. The result justifies Kernel-based FCM, and the superiority of features reduced Kernel-based FCM clustering over other traditional fuzzy clustering techniques.
Introduction
The rapid growth of the digital world contributes to the exponential growth of data in the contemporary scenario. In the early days of digitization, the data was produced by computers, which later moved on to different platforms and to different formats such as image, audio, video. Retrieving relevant information from this vast data is very difficult. Data Clustering is one of the standard data mining techniques and has been widely used in Big Data research. Clustering is used to break down the data into associated components to make patterns and order visible. Typically, a cluster is interpreted as a group of related data points around a core known as a centroid. Vast volumes of data are extensively analyzed to derive valuable information in the form of new interactions, trends, or clusters to appropriate a user’s decision.
Clustering is an unsupervised classification, which does not require an assumption about category labels that identify objects with a prior identifier. It separates data points into homogeneous groups so that data points in the same group are as identical as possible and data points are as dissimilar as possible in separate groupings. The classification demands human interaction to choose the criteria and unsupervised clustering that handpick the clustering criteria itself.
The clusters with well-defined boundaries are considered hard clusters, and those without a well-defined boundary are soft or fuzzy clusters. In hard clustering algorithms, each data point of the data set is assigned to one and only one cluster, and in fuzzy clustering, the data points are assigned to more than one cluster with different membership values [1]. The performance of the hard clustering algorithm, such as the k-means algorithm, depends on the initial values of centroids and gives no guarantee for an optimum solution. Clustering plays a vital role in identifying the underlying pattern structure since big data involves too much uncertainty, and fuzzy clustering is one of the easiest ways to catch uncertainty [2].
Most conventional clustering algorithms use centres and basic distance measurements in the original space and only cluster data into spherical or elliptical shapes [3] without recognizing the irregular shape. Hard clustering investigates only the distance between data patterns and is not adequate for finding clusters with complicated internal structures. Clusters found using such techniques cannot be easily described. The Fuzzy clustering algorithms should be capable of identifying clusters with non-spherical or random shapes and some points in one cluster, which essentially be closer to other points in other clusters than the points in their clusters [4].
For complex datasets where there are overlapping clusters, hard allocation of points to clusters is not feasible. A fuzzy clustering algorithm can be used for such overlapping clusters [5]. Fuzzy clustering is a sophisticated data processing strategy that is unlabeled, involves outliers and has irregular patterns. Fuzzy clustering algorithms are better to deal with discrimination of similar structures, data set in n-dimensional spaces than hard clustering [6]. It is more valuable for unlabeled data and the outliers of the dataset [7]. Hard clustering such as the k-means and Ward’s clustering lack the precision for image processing and machine learning methods than FCM clustering [6]. FCM algorithm is sensitive to the noise and isolated data and initial clustering centre. It is a local hill-climbing algorithm, which is easy to converge to a local maximum [8]. The kernel function is used to figure out the data points, which cannot be linearly separated from original space to high dimensional space. This results in the new space giving better performance [9].
Literature review
Zadeh introduced the fuzzy sets in 1965. Zadeh introduced the grade of membership. In a crisp set, the data points have the membership either 0 or 1. In fuzzy sets, membership for each object varies from 0 to 1 [5]. Fuzzy c-Means (FCM) is an improvised version of the traditional c-means/k-means algorithm for data classification. The FCM is more flexible than k_means in partitioning the objects. FCM is the most commonly used fuzzy clustering method, allowing one data to belong to more than one cluster. This method is developed by J. Dunn in 1973 [10] and improved by James C Bezdek in 1981. In 1996, Pal proposed the fuzzy possibilistic c-means (FPCM) model and algorithm that generated both membership and possibilities when clustering unlabeled data. FPCM resolved the defect of FCM, i.e. noise sensitivity defect, and conquers the coincident cluster problem of PCM [11]. Fuzzy clustering technique is used to determine the policies and plans in the enlarged cases of coronavirus [12].
Zhang and Chen initiated a novel clustering algorithm called the kernel fuzzy c-means algorithm. It is resilient to outliers and noise and also tolerates clusters of varying sizes [13]. Timothy C Havens extended the FCM to massive data by implementing sampling techniques followed by non-iteration extension and kernel methods [14]. Telmo M. Silva Filho combined a metaheuristic optimization, like particle swarm optimization, with a traditional clustering, FCM, to improve the accuracy. FCM applied in different realms like image segmentation [15, 16], detection and correction of insufficient data in the analysis of power system load data [17], mode-seeking framework [18]. Zhang Siqing proposed a clustering protocol based on fuzzy logic for Multi-hop WSN to extend the life of wireless sensor networks (WSNs) and lessen energy consumption [19]. The possibilistic fuzzy c-means algorithm used in the sphere detects the earthquake and releases a warning alarm [20]. The Isolation forest method is used to find the outliers in the databases. P. Karczmare and others enriched the Isolation Forest on the base of Fuzzy c-means [21].
Ding and Fu launched a kernel-oriented fuzzy c-means clustering algorithm, the GAKFCM clustering algorithm, which used the adaptive genetic algorithm to optimize the initial clustering centre and improve the performance of the FCM by using the KFCM algorithm. It is oriented to optimise the genetic algorithm juxtaposed with the enhanced genetic algorithm and the kernel technique [8]. C Jiang and others proposed an FCM based on a Simulated annealing algorithm and kernel technology that outperformed conventional FCM and resolved the three defects: discoveries of outliers, an unknown number of clusters, and an unbalanced process of clustering [22]. FCM is responsive to the initial cluster centres and easy to converge to local optimization. Wang, Zhang and Xiao introduced a Fruit Fly Optimization KFCM clustering algorithm based on the fruit fly algorithm. This algorithm optimises the initial clustering centre and then categorises data using the kernel-based fuzzy c-means clustering algorithm [23].
The adaptive kernel-based fuzzy C-means clustering with spatial constraints model, presented by Guang Hu and Zhenbin Du has increased the efficiency of image segmentation [24]. Wenke Zang and others established a kernel-based intuitionistic fuzzy C-means clustering using the improved multi-objective artificial immune algorithm (KIFCM-IMOIA). The KIFCM-IMOIA uses the kernel trick and the intuitionistic fuzzy entropy (IFE) which improves the robustness to noises [25]. M. Giri and S. Majumder developed a new eigenvalue-based technique for spectrum sensing. That paper used kernel based Fuzzy C means clustering to cluster the test vectors [26]. Webiao Qiao and Zhe Yang introduced kernel-based fuzzy C-means into dolphin swarm algorithm [27].
Fuzzy clustering
Fuzzy clustering is more flexible than hard clustering in that each object may have membership in more than one cluster [14]. In hard clustering, the data points have the membership of either 0 or 1. The membership of each object in different clusters in the fuzzy clustering is varying from 0 to 1 [5]. In fuzzy clustering, the degree of membership of an object 1
where
Fuzzy c-Means clustering
Fuzzy c-Means is the most commonly used fuzzy-based clustering algorithm, a modification of the c-means clustering technique. FCM divides the data samples into C fuzzy clusters. The cost function of FCM is minimized as a result of calculating the cluster centre. The cost function of the FCM is as follows:
Where
The FCM partition of dataset
[t] Fuzzy c-Means algorithm Input:
Update the cluster center
The cluster centre is initialized randomly. The corresponding membership values are evaluated using Eq. (2) and updated the cluster centres using Eq. (3). FCM algorithm stopped when the change from the previous cluster centre to the new cluster centre has reached the target value. The convergence speed of the FCM algorithm is greatly influenced by the initial value, mainly in the case of a large number of clusters and easy to fall into local optimization [30]. The steps (2) to (4) are iterated till the algorithm terminates. The estimation of the modified membership function is a consequence of the objective function being minimized. The centroid is calculated with FCM as the mean of all points, weighted by their degree of cluster membership. FCM transfers the cluster centres within a data set to the correct position through iteratively reviewing the cluster centres and the membership grades for each data point. In the end, a hard classification is reached by assigning each data point exclusively to the class with the highest membership value. The performance of the FCM depends on the initial cluster centres.
Kernel Methods enables researchers to examine nonlinear relations with the same competence as linear algorithms. A kernel-based FCM is proposed to simplify FCM clustering, to resolve some of the problems in the FCM clustering algorithm. The weakness of fuzzy c-means is its sensitivity to the prototypes [6] and ease to fall into local optimum [8]. In many clusters, the convergence speed is subjective to the initial value [30]. Kernel clustering algorithm does not rely on the initialization of the clusters. It discovers nonlinearly separable clusters and finds optimal solutions due to its search procedure and incremental nature [31]. The kernel approach project data into higher dimensional space is an efficient way to solve the problem of FCM. Kernelization is an effective mathematical technique that helps one to carry out tacit calculations on the data set, thereby allowing a clustering process to removing clusters of nonlinear separating hypersurfaces [20, 21, 32].
Experiments and analysis
This section illustrates the experiments conducted on FCM and KFCM to validate the analysis. In the first experiment, FCM and FCM using kernel trick is evaluated. In the second experiment, are used only the relevant features of a dataset for clustering. A complete program was created using the Python programming language to find the optimal result value for the FCM and KFCM algorithms.
FCM with kernel function and feature selection
The FCM effectiveness is limited mainly to spherical clusters. The kernel function attempts to address this problem by mapping data with a nonlinear relationship to appropriate feature space. The kernel tricks are used for the data analysis problems such as classification, clustering, categorization. The kernel function transforms the features to a higher dimension. It repeats until the changes of the cluster converge to the fixed value. It changes any linear model into a non-linear model by replacing the initial features with the higher features. Thus the projection of the dataset turns from the initial representation space to a higher-dimensional space. Since it is an implicit feature expansion it needs the inner products between all pairs of data. The result shows that while applying the kernel function, the optimal clusters are defined. The kernel FCM method outperforms the traditional FCM method.
[h] FCM with Kernel Function (KFCM) Input:
Algorithm 2 illustrates FCM Clustering with Kernel Function which is denoted as KFCM. The KFCM algorithm accepts dataset
[t]
Validity measures
SI value of FCM and Linear Kernel FCM on IRIS dataset without feature selection.
SI value of FCM and Linear Kernel FCM on Fruits dataset without feature selection.
SI value of FCM and Linear Kernel FCM on Wine dataset without feature selection.
DBI value of FCM and Linear Kernel FCM on IRIS dataset without feature selection.
DBI value of FCM and Linear Kernel FCM on Fruits dataset without feature selection.
DBI value of FCM and Linear Kernel FCM on Wine dataset without feature selection.
Unsupervised clustering is found without any cluster labels. Therefore, the inter-cluster distance and the interspace between the data points in a cluster is used to evaluate the clusters. In this paper, two clustering metrics are used to measure the consistency of clustering: the Silhouette Index (SI) and Davies-Bouldin index (DBI). Silhouette index displays a measure of intra-cluster distance and inter-cluster difference [33]. The range of SI is 1 to
The performance of FCM and Kernel FCM is evaluated effectively using three test data sets. The benchmark datasets IRIS and Wine were taken from the UCI machine learning repository, and the other dataset, Fruits, is an artificial dataset. The IRIS is a two-dimensional dataset, which consists of 150 samples with four features. The four features of IRIS are the length and width of sepals and petals of three species of Iris. The dataset WINE with 13 features and consists of 179 samples. The dataset is multivariate and attributes characteristics are integer and real. It provides information on the chemical analysis of different wines. The amounts of 13 ingredients are identified in each of the three varieties of wines. The dataset Fruits contain 70 images of different coloured fruits. The image file cannot be used directly for clustering. Preprocessing of data is conducted on the dataset and converts each sample to the corresponding combination of Red, Green, and Blue. Then the dataset becomes a two-dimensional dataset with Red, Green, and Blue values corresponding to the image as the attributes of the dataset Fruits.
Results
SI value of FCM and Linear Kernel FCM on IRIS dataset with feature selection.
SI value of FCM and Linear Kernel FCM on Fruits dataset with feature selection.
SI value of FCM and Linear Kernel FCM on Wine dataset with feature selection.
DBI value of FCM and Linear Kernel FCM on IRIS dataset with feature selection.
DBI value of FCM and Linear Kernel FCM on Fruits dataset with feature selection.
DBI value of FCM and Linear Kernel FCM on Wine dataset with feature selection.
This section summarises the findings of the experiments performed. In this section, the results demonstrations the efficacy of KFCM over FCM and the importance of feature selection in clustering.
Table 1 shows the Silhouette index (SI) and Davies-Bouldin index (DBI) values of the FCM cluster. The SI is varying with the number of clusters. The highest value of the SI is considered an optimal cluster. The smallest values of the DBI are measured as better clusters. As per the values of SI and DBI, cluster two is optimal in the IRIS dataset. From Table 1, it is understood that cluster two has the highest SI value and cluster three has the smallest DBI value for the Fruits dataset. There is an inconsistency about the optimal partition. Among the clusters of dataset WINE, cluster two is optimal because of the highest SI and small DBI value.
SI and DBI value of FCM clustering with whole features
SI and DBI value of Linear Kernel FCM with whole features
SI and DBI value of FCM clustering with the selected number of features
SI and DBI value of Linear Kernel FCM with the selected number of features
The kernel trick is applied to the datasets, and the results illustrate in Table 2. In the Linear kernel dot product of the data points is evaluated. The values of SI are increased for the datasets IRIS and Fruits. In the case of dataset Fruits, while applying FCM, according to SI, cluster two is better, and by DBI, cluster three is better. This inconsistency is changed while using Kernel Trick. The result shows that cluster three is better than two. It indicates that the clustering implemented by Kernel Trick is more optimal than the traditional FCM. The result of the Wine dataset is not changed. It means the algorithms FCM and Linear Kernel FCM (LKFCM) have the same effect on this dataset.
Figures 1, 2 and 3 demonstrates the comparison study of the SI value of the FCM algorithm and Linear Kernel FCM (LKFCM) Clustering. Figures 4, 5 and 6 shows the DBI value of the FCM algorithm and Linear Kernel FCM (LKFCM) Clustering algorithm. The exclusive features of the datasets are used in this section.
In the second section, only the relevant features are considered for clustering. All the features are not equally significant for clustering. Some features are essential, while some others are less important. The feature selection approach aims to select a small subset of features that maximize relevance to the target and minimize redundancy. Most clustering algorithms do not apply feature selection or the relation between the features. The same dataset is implemented here with fewer but relevant features. The similarity is distance-dependent, so there are at least a few characteristics on which the points are identical to each other for a pair of data points in a cluster. Various methods of clustering presume that all characteristics are equally relevant for clustering. This is one of the causes that most clustering algorithms may not perform well in high dimensional data. The time required to cluster high dimensional data is more than the time required for low dimensional data.
A significant feature helps to create better clusters, while an insignificant one does not help for the same and blurring the clusters can negatively affect the clustering algorithms. Unimportant features are considered noisy or obsolete and may be omitted to reduce the data size for more effective clustering. The reduction of features reduces the time for clustering. Pearson’s correlation coefficient between the variables is considered for the feature selection. Pearson’s correlation coefficient gives the measures of linear correlation between two variables. According to the correlation coefficient, features are selected for the clustering.
Tables 3 and 4 illustrate the experimental result of feature reduced, FCM and Linear Kernel-based FCM. The selected features are three from four of IRIS, two from three of Fruits, eight from thirteen of Wine. The experiment results are better than the results of clustering without feature selection in IRIS and Fruits datasets. The resultant SI value of the feature reduced, IRIS and Fruits is greater than the traditional FCM and simple Linear Kernel-based FCM. Furthermore, the DBI value is smaller than the result of the simple FCM and simple Kernel-based FCM. The Wine dataset has less value of SI and a greater value of DBI than the simple FCM and Kernel-based FCM without feature selection. The correlation coefficient between the variables is significantly less in the Wine dataset. So as the number of relevant features reduces the quality will also be decreased.
Figures 7, 8, 9 Illustrates the SI value of FCM and Linear Kernel FCM (LKFCM) Clustering applied on the datasets IRIS, Fruits, Wine, respectively. Figures 10, 11, 12 shows the DBI value of the same.
The paper proposes the FCM clustering and a Kernel based FCM algorithm for clustering the data. The contributions of this paper are as follows. Primarily, a comparison study of FCM and Kernel-based FCM is performed. Secondly, the selected features are used for clustering. The experiments have been conducted on two benchmarking datasets and one artificial dataset. The results show that the Kernel-based FCM has better optimization than simple FCM, and the use of selected features for clustering improves the result of clustering. The evaluation is performed in terms of two validity metrics, the SI and DBI. Another possible extension of the topic would be to solve the problem that FCM is sensitive to the initial cluster centroids. Further study on this topic will also include the multiple kernel functions for clustering in real-world problems.
