Cluster validity index for estimation of fuzzy clusters of different sizes and densities

Cluster validity indices are used for estimating the quality of partitions produced by clustering algorithms and for determining the number of clusters in data. Cluster validation is difficult task, because for the same data set more partitions exists regarding the level of details that fit natural groupings of a given data set. Even though several cluster validity indices exist, they are inefficient when clusters widely differ in density or size. We propose a clustering validity index that addresses these issues. It is based on compactness and overlap measures. The overlap measure, which indicates the degree of overlap between fuzzy clusters, is obtained by calculating the overlap rate of all data objects that belong strongly enough to two or more clusters. The compactness measure, which indicates the degree of similarity of data objects in a cluster, is calculated from membership values of data objects that are strongly enough associated to one cluster. We propose ratio and summation type of index using the same compactness and overlap measures. The maximal value of index denotes the optimal fuzzy partition that is expected to have a high compactness and a low degree of overlap among clusters. Testing many well-known previously formulated and proposed indices on well-known data sets showed the superior reliability and effectiveness of the proposed index in comparison to other indices especially when evaluating partitions with clusters that widely differ in size or density.     

On cluster validity index for estimation of the optimal number of fuzzy clusters

A new cluster validity index is proposed that determines the optimal partition and optimal number of clusters for fuzzy partitions obtained from the fuzzy c-means algorithm. The proposed validity index exploits an overlap measure and a separation measure between clusters. The overlap measure, which indicates the degree of overlap between fuzzy clusters, is obtained by computing an inter-cluster overlap. The separation measure, which indicates the isolation distance between fuzzy clusters, is obtained by computing a distance between fuzzy clusters. A good fuzzy partition is expected to have a low degree of overlap and a larger separation distance. Testing of the proposed index and nine previously formulated indexes on well-known data sets showed the superior effectiveness and reliability of the proposed index in comparison to other indexes.     

A cluster validity index for fuzzy clustering

A new cluster validity index is proposed for the validation of partitions of object data produced by the fuzzy c-means algorithm. The proposed validity index uses a variation measure and a separation measure between two fuzzy clusters. A good fuzzy partition is expected to have a low degree of variation and a large separation distance. Testing of the proposed index and nine previously formulated indices on well-known data sets shows the superior effectiveness and reliability of the proposed index in comparison to other indices and the robustness of the proposed index in noisy environments.     

Cluster validity index based on Jeffrey divergence

Cluster validity indexes are very important tools designed for two purposes: comparing the performance of clustering algorithms and determining the number of clusters that best fits the data. These indexes are in general constructed by combining a measure of compactness and a measure of separation. A classical measure of compactness is the variance. As for separation, the distance between cluster centers is used. However, such a distance does not always reflect the quality of the partition between clusters and sometimes gives misleading results. In this paper, we propose a new cluster validity index for which Jeffrey divergence is used to measure separation between clusters. Experimental results are conducted using different types of data and comparison with widely used cluster validity indexes demonstrates the outperformance of the proposed index.     

基于错误度量的模糊聚类有效性函数

聚类的错误主要表现为两种形式:将原属不同类的数据分到同一个聚类和将原属同一类的数据分到不同聚类。文中提出类内不一致性和类间重叠度两个指标分别度量聚类中出现这两类错误的程度。一个好的模糊分割中包含的聚类错误应尽可能少。同时,聚类紧致度应尽可能大。基于这两个错误度量指标和紧致性度量,提出一种有效性函数来判断模糊聚类的有效性。实验结果表明,提出的有效性函数能有效判断最佳聚类数并且有较好的鲁棒性。     

Toward the existence and uniqueness of solutions of second-order fuzzy volterra integro-differential equations with fuzzy kernel

Clustering analysis is the process of separating data according to some similarity measure. A cluster consists of data which are more similar to each other than to other clusters. The similarity of a datum to a certain cluster can be defined as the distance of that datum to the prototype of that cluster. Typically, the prototype of a cluster is a real vector that is called the center of that cluster. In this paper, the prototype of a cluster is generalized to be a complex vector (complex center). A new distance measure is introduced. New formulas for the fuzzy membership and the fuzzy covariance matrix are introduced. Cluster validity measures are used to assess the goodness of the partitions obtained by the complex centers compared those obtained by the real centers. The validity measures used in this paper are the partition coefficient, classification entropy, partition index, separation index, Xie and Beni’s index, and Dunn’s index. It is shown in this paper that clustering with complex prototypes will give better partitions of the data than using real prototypes.     

一种新的模糊聚类有效性指标

结合模糊聚类的类内紧致性和类间分离性信息,提出一种新的模糊聚类有效性指标。该指标能够确定由模糊C-均值算法（FCM）所得模糊划分的最优划分和最佳聚类数。在1个人造数据集和4个真实数据集上进行对比实验,结果表明该指标性能的优越性。     

一个新的模糊聚类有效性指标

提出一个新的模糊聚类有效性指标。该指标能确定由模糊C-均值算法(FCM)所得模糊划分的最优划分和最优聚类数,结合了模糊聚类的紧致性和分离性信息,用类内加权平方误差和计算紧致性,用类间相似度计算分离性。在3个人造数据集和3个真实数据集上进行对比实验,结果证明该指标的性能优于其他有效性指标。     

Model-based evaluation of clustering validation measures

A cluster operator takes a set of data points and partitions the points into clusters (subsets). As with any scientific model, the scientific content of a cluster operator lies in its ability to predict results. This ability is measured by its error rate relative to cluster formation. To estimate the error of a cluster operator, a sample of point sets is generated, the algorithm is applied to each point set and the clusters evaluated relative to the known partition according to the distributions, and then the errors are averaged over the point sets composing the sample. Many validity measures have been proposed for evaluating clustering results based on a single realization of the random-point-set process. In this paper we consider a number of proposed validity measures and we examine how well they correlate with error rates across a number of clustering algorithms and random-point-set models. Validity measures fall broadly into three classes: internal validation is based on calculating properties of the resulting clusters; relative validation is based on comparisons of partitions generated by the same algorithm with different parameters or different subsets of the data; and external validation compares the partition generated by the clustering algorithm and a given partition of the data. To quantify the degree of similarity between the validation indices and the clustering errors, we use Kendall's rank correlation between their values. Our results indicate that, overall, the performance of validity indices is highly variable. For complex models or when a clustering algorithm yields complex clusters, both the internal and relative indices fail to predict the error of the algorithm. Some external indices appear to perform well, whereas others do not. We conclude that one should not put much faith in a validity score unless there is evidence, either in terms of sufficient data for model estimation or prior model knowledge, that a validity measure is well-correlated to the error rate of the clustering algorithm.     

Robust validity index for a modified subtractive clustering algorithm

A novel robust validity index is proposed for subtractive clustering (SC) algorithm. Although the SC algorithm is a simple and fast data clustering method with robust properties against outliers and noise; it has two limitations. First, the cluster number generated by the SC algorithm is influenced by a given threshold. Second, the cluster centers obtained by SC are based on data that have the highest potential values but may not be the actual cluster centers. The validity index is a function as a measure of the fitness of a partition for a given data set. To solve the first problem, this study proposes a novel robust validity index that evaluates the fitness of a partition generated by SC algorithm in terms of three properties: compactness, separation and partition index. To solve the second problem, a modified algorithm based on distance relations between data and cluster centers is designed to ascertain the actual centers generated by the SC algorithm. Experiments confirm that the preferences of the proposed index outperform all others.     

基于模糊划分测度的聚类有效性指标

聚类有效性指标用于评价聚类结果的有效性。根据聚类的基本特性，提出了一个新的用于发现最优模糊划分的聚类有效性指标，该有效性指标采用模糊划分测度和信息熵两个重要因子来评价模糊聚类的有效性。其中，模糊划分测度用于评价聚类的类内紧致性与类间分离性，而信息熵则反映了模糊聚类划分结果的不确定性程度。实验结果表明，该聚类有效性指标能对模糊聚类结果的有效性进行正确的评价，特别是对于空间数据的聚类有效性评价，同其他有效性指标相比，它不仅能得到最优的模糊划分，而且对权重系数也是不敏感的。     

Centroid index: Cluster level similarity measure

In clustering algorithm, one of the main challenges is to solve the global allocation of the clusters instead of just local tuning of the partition borders. Despite this, all external cluster validity indexes calculate only point-level differences of two partitions without any direct information about how similar their cluster-level structures are. In this paper, we introduce a cluster level index called centroid index. The measure is intuitive, simple to implement, fast to compute and applicable in case of model mismatch as well. To a certain extent, we expect it to generalize other clustering models beyond the centroid-based k-means as well.     

Use of line based symmetry for developing cluster validity indices

From a dataset automatically identifying possible count of clusters is an important task of unsupervised classification. To address this issue, in the current paper, we have focused on the symmetry property of any cluster. Point and line symmetry are two important attributes of data partitions. Here we have proposed line symmetry versions of eight well-known validity indices: XB, PBM, FCM, PS, FS, K, SV, and DB indices to make them capable of identifying the accurate count of partitions from data sets containing clusters having line symmetric property. The global optimality of two of these newly developed indices is established mathematically. Eight artificially generated data sets of varying dimensions containing clusters of different convexities and shapes and three real-life data sets are used for the purpose of experiment. Initially, to obtain different partitions an existing genetic clustering technique which uses line symmetry property (GALS clustering) is applied on data sets varying the count of clusters. queryPlease check and confirm the edit in the following sentence: We have also provided a comparative study of our proposed line-symmetry-based cluster validity indices with their point-symmetry-based versions and original versions based on Euclidean distance. We have also provided a comparative study of our proposed line-symmetry-based cluster validity indices with their point-symmetry-based versions and original versions based on Euclidean distance. From the experimental results it is revealed that most of the line-symmetry-distance-based cluster validity indices perform better than their point symmetry and Euclidean-distance-based versions.     

Assessment of Microarray Data Clustering Results Based on a New Geometrical Index for Cluster Validity

A measurement of cluster quality is often needed for DNA microarray data analysis. In this paper, we introduce a new cluster validity index, which measures geometrical features of the data. The essential concept of this index is to evaluate the ratio between the squared total length of the data eigen-axes with respect to the between-cluster separation. We show that this cluster validity index works well for data that contain clusters closely distributed or with different sizes. We verify the method using three simulated data sets, two real world data sets and two microarray data sets. The experiment results show that the proposed index is superior to five other cluster validity indices, including partition coefficients (PC), General silhouette index (GS), Dunn’s index (DI), CH Index and I-Index. Also, we have given a theorem to show for what situations the proposed index works well.     

Novel Cluster Validity Index for FCM Algorithm

How to determine an appropriate number of clusters is very important when implementing a specific clustering algorithm, like c-means, fuzzy c-means （FCM）. In the literature, most cluster validity indices are originated from partition or geometrical property of the data set. In this paper, the authors developed a novel cluster validity index for FCM, based on the optimality test of FCM. Unlike the previous cluster validity indices, this novel cluster validity index is inherent in FCM itself. Comparison experiments show that the stability index can be used as cluster validity index for the fuzzy c-means.     

改进的GK聚类算法

针对传统GK聚类算法无法自动确定聚类数和对初始聚类中心比较敏感的缺陷,提出一种改进的GK聚类算法。该算法首先通过基于类间分离度和类内紧致性的权和的新有效性指标来确定最佳聚类数;然后,利用改进的熵聚类的思想来确定初始聚类中心;最后,根据判定出的聚类数和新的聚类中心进行聚类。实验结果表明,新指标能准确地判断出类间有交叠的数据集的最佳聚类数,且改进后的算法具有更高的聚类准确率。     

Validation indices for projective clustering

Cluster validation is a major issue in cluster analysis of data mining, which is the process of evaluating performance of clustering algorithms under varying input conditions. Many existing validity indices address clustering results of low-dimensional data. Within high-dimensional data, many of the dimensions are irrelevant, and the clusters usually only exist in some projected subspaces spanned by different combinations of dimensions. This paper presents a solution to the problem of cluster validation for projective clustering. We propose two new measurements for the intracluster compactness and intercluster separation of projected clusters. Based on these measurements and the conventional indices, three new cluster validity indices are presented. Combined with a fuzzy projective clustering algorithm, the new indices are used to determine the number of projected clusters in high-dimensional data. The suitability of our proposal has been demonstrated through an empirical study using synthetic and real-world datasets.     

A new validity index for crisp clusters

In this paper, a new cluster validity index which can be considered as a measure of the accuracy of the partitioning of data sets is proposed. The new index, called the STR index, is defined as the product of two components which determine changes of compactness and separability of clusters during a clustering process. The maximum value of this index identifies the best clustering scheme. Three popular algorithms have been applied as underlying clustering techniques, namely complete-linkage, expectation maximization and K-means algorithms. The performance of the new index is demonstrated for several artificial and real-life data sets. Moreover, this new index has been compared with other well-known indices, i.e., Dunn, Davies-Bouldin, PBM and Silhouette indices, taking into account the number of clusters in a data set as the comparison criterion. The results prove superiority of the new index as compared to the above-mentioned indices.     

Generalized Possibilistic Fuzzy C-Means with novel cluster validity indices for clustering noisy data

A generalized form of Possibilistic Fuzzy C-Means (PFCM) algorithm (GPFCM) is presented for clustering noisy data. A function of distance is used instead of the distance itself to damp noise contributions. It is shown that when the data are highly noisy, GPFCM finds accurate cluster centers but FCM (Fuzzy C-Means), PCM (Possibilistic C-Means), and PFCM algorithms fail. FCM, PCM, and PFCM yield inaccurate cluster centers when clusters are not of the same size or covariance norm is used, whereas GPFCM performs well for both of the cases even when the data are noisy. It is shown that generalized forms of FCM and PCM (GFCM and GPCM) are also more accurate than FCM and PCM. A measure is defined to evaluate performance of the clustering algorithms. It shows that average error of GPFCM and its simplified forms are about 80% smaller than those of FCM, PCM, and PFCM. However, GPFCM demands higher computational costs due to nonlinear updating equations. Three cluster validity indices are introduced to determine number of clusters in clean and noisy datasets. One of them considers compactness of the clusters; the other considers separation of the clusters, and the third one considers both separation and compactness. Performance of these indices is confirmed to be satisfactory using various examples of noisy datasets.     

A least biased fuzzy clustering method

A new operational definition of cluster is proposed, and a fuzzy clustering algorithm with minimal biases is formulated by making use of the maximum entropy principle to maximize the entropy of the centroids with respect to the data points (clustering entropy). The authors make no assumptions on the number of clusters or their initial positions. For each value of an adimensional scale parameter β', the clustering algorithm makes each data point iterate towards one of the cluster's centroids, so that both hard and fuzzy partitions are obtained. Since the clustering algorithm can make a multiscale analysis of the given data set one can obtain both hierarchy and partitioning type clustering. The relative stability with respect to β' of each cluster structure is defined as the measurement of cluster validity. The authors determine the specific value of β' which corresponds to the optimal positions of cluster centroids by minimizing the entropy of the data points with respect to the centroids (clustered entropy). Examples are given to show how this least biased method succeeds in getting perceptually correct clustering results