硬聚类和模糊聚类的结合——双层FCM快速算法

模糊c均值(FCM)聚类算法在模式识别领域中得到了广泛的应用,但FCM算法在大数据集的情况下需要大量的CPU时间,令用户感到十分不便,提高算法的速度是一个急待解决的问题。本文提出的双层FCM聚类算法是一种快速算法,它体现了硬聚类和模糊聚类的结合,以硬聚类的结果对模糊聚类的初始值进行指导,从而明显地缩短了迭代过程。双层FCM算法所用的CPU时间仅为FCM算法的十三分之一,因而具有很强的实用价值。     

Soft clustering – Fuzzy and rough approaches and their extensions and derivatives

Clustering is one of the most widely used approaches in data mining with real life applications in virtually any domain. The huge interest in clustering has led to a possibly three-digit number of algorithms with the k-means family probably the most widely used group of methods. Besides classic bivalent approaches, clustering algorithms belonging to the domain of soft computing have been proposed and successfully applied in the past four decades. Bezdek’s fuzzy c-means is a prominent example for such soft computing cluster algorithms with many effective real life applications. More recently, Lingras and West enriched this area by introducing rough k-means. In this article we compare k-means to fuzzy c-means and rough k-means as important representatives of soft clustering. On the basis of this comparison, we then survey important extensions and derivatives of these algorithms; our particular interest here is on hybrid clustering, merging fuzzy and rough concepts. We also give some examples where k-means, rough k-means, and fuzzy c-means have been used in studies.     

Kernel-based fuzzy clustering and fuzzy clustering: A comparative experimental study

In this study, we present a comprehensive comparative analysis of kernel-based fuzzy clustering and fuzzy clustering. Kernel based clustering has emerged as an interesting and quite visible alternative in fuzzy clustering, however, the effectiveness of this extension vis-à-vis some generic methods of fuzzy clustering has neither been discussed in a complete manner nor the performance of clustering quantified through a convincing comparative analysis. Our focal objective is to understand the performance gains and the importance of parameter selection for kernelized fuzzy clustering. Generic Fuzzy C-Means (FCM) and Gustafson–Kessel (GK) FCM are compared with two typical generalizations of kernel-based fuzzy clustering: one with prototypes located in the feature space (KFCM-F) and the other where the prototypes are distributed in the kernel space (KFCM-K). Both generalizations are studied when dealing with the Gaussian kernel while KFCM-K is also studied with the polynomial kernel. Two criteria are used in evaluating the performance of the clustering method and the resulting clusters, namely classification rate and reconstruction error. Through carefully selected experiments involving synthetic and Machine Learning repository (http://archive.ics.uci.edu/beta/) data sets, we demonstrate that the kernel-based FCM algorithms produce a marginal improvement over standard FCM and GK for most of the analyzed data sets. It has been observed that the kernel-based FCM algorithms are in a number of cases highly sensitive to the selection of specific values of the kernel parameters.     

Genetic algorithm-tuned entropy-based fuzzy C-means algorithm for obtaining distinct and compact clusters

A modified approach had been developed in this study by combining two well-known algorithms of clustering, namely fuzzy c-means algorithm and entropy-based algorithm. Fuzzy c-means algorithm is one of the most popular algorithms for fuzzy clustering. It could yield compact clusters but might not be able to generate distinct clusters. On the other hand, entropy-based algorithm could obtain distinct clusters, which might not be compact. However, the clusters need to be both distinct as well as compact. The present paper proposes a modified approach of clustering by combining the above two algorithms. A genetic algorithm was utilized for tuning of all three clustering algorithms separately. The proposed approach was found to yield both distinct as well as compact clusters on two data sets.     

Mixed fuzzy inter-cluster separation clustering algorithm

Based on inter-cluster separation clustering (ICSC) fuzzy inter-cluster separation clustering (FICSC) deals with all the distances between the cluster centers, maximizes these distances and obtains the better performances of clustering. However, FICSC is sensitive to noises the same as fuzzy c-means (FCM) clustering. Possibilistic type of FICSC is proposed to combine FICSC and possibilistic c-means (PCM) clustering. Mixed fuzzy inter-cluster separation clustering (MFICSC) is presented to extend possibilistic type of FICSC because possibilistic type of FICSC is sensitive to initial cluster centers and always generates coincident clusters. MFICSC can produce both fuzzy membership values and typicality values simultaneously. MFICSC shows good performances in dealing with noisy data and overcoming the problem of coincident clusters. The experimental results with data sets show that our proposed MFICSC holds better clustering accuracy, little clustering time and the exact cluster centers.     

On the use of divergence distance in fuzzy clustering

Clustering algorithms divide up a dataset into a set of classes/clusters, where similar data objects are assigned to the same cluster. When the boundary between clusters is ill defined, which yields situations where the same data object belongs to more than one class, the notion of fuzzy clustering becomes relevant. In this course, each datum belongs to a given class with some membership grade, between 0 and 1. The most prominent fuzzy clustering algorithm is the fuzzy c-means introduced by Bezdek (Pattern recognition with fuzzy objective function algorithms, 1981), a fuzzification of the k-means or ISODATA algorithm. On the other hand, several research issues have been raised regarding both the objective function to be minimized and the optimization constraints, which help to identify proper cluster shape (Jain et al., ACM Computing Survey 31(3):264–323, 1999). This paper addresses the issue of clustering by evaluating the distance of fuzzy sets in a feature space. Especially, the fuzzy clustering optimization problem is reformulated when the distance is rather given in terms of divergence distance, which builds a bridge to the notion of probabilistic distance. This leads to a modified fuzzy clustering, which implicitly involves the variance–covariance of input terms. The solution of the underlying optimization problem in terms of optimal solution is determined while the existence and uniqueness of the solution are demonstrated. The performances of the algorithm are assessed through two numerical applications. The former involves clustering of Gaussian membership functions and the latter tackles the well-known Iris dataset. Comparisons with standard fuzzy c-means (FCM) are evaluated and discussed.     

A tandem clustering process for multimodal datasets

Clustering multimodal datasets can be problematic when a conventional algorithm such as k-means is applied due to its implicit assumption of Gaussian distribution of the dataset. This paper proposes a tandem clustering process for multimodal data sets. The proposed method first divides the multimodal dataset into many small pre-clusters by applying k-means or fuzzy k-means algorithm. These pre-clusters are then clustered again by agglomerative hierarchical clustering method using Kullback–Leibler divergence as an initial measure of dissimilarity. Benchmark results show that the proposed approach is not only effective at extracting the multimodal clusters but also efficient in computational time and relatively robust at the presence of outliers.     

CL.E.KMODES: a modified <Emphasis Type="Italic">k</Emphasis>-modes clustering algorithm

In this paper we present a new method for clustering categorical data sets named CL.E.KMODES. The proposed method is a modified k-modes algorithm that incorporates a new four-step dissimilarity measure, which is based on elements of the methodological framework of the ELECTRE I multicriteria method. The four-step dissimilarity measure introduces an alternative and more accurate way of assigning objects to clusters. In particular, it compares each object with each mode, for every attribute that they have in common, and then chooses the most appropriate mode and its corresponding cluster for that object. Seven widely used data sets are tested to verify the robustness of the proposed method in six clustering evaluation measures.     

Mixed aleatory and epistemic uncertainty quantification using fuzzy set theory

This paper proposes algorithms to construct fuzzy probabilities to represent or model the mixed aleatory and epistemic uncertainty in a limited-size ensemble. Specifically, we discuss the possible requirements for the fuzzy probabilities in order to model the mixed types of uncertainty, and propose algorithms to construct fuzzy probabilities for both independent and dependent datasets. The effectiveness of the proposed algorithms is demonstrated using one-dimensional and high-dimensional examples. After that, we apply the proposed uncertainty representation technique to isocontour extraction, and demonstrate its applicability using examples with both structured and unstructured meshes.     

A fuzzy noise-rejection data partitioning algorithm

Fuzzy C-Means (FCM) and hard clustering are the most common tools for data partitioning. However, the presence of noisy observations in the data being partitioned may render these clustering algorithms unreliable. In this paper, we introduce a robust noise-rejection clustering algorithm based on a combination of techniques that treat the FCM pitfalls with an outliers exclusion criterion. Unlike the traditional FCM, the proposed clustering tool provides much efficient data partitioning capabilities in the presence of noise and outliers. At the conclusion of the theoretical development, we validate the effectiveness of the proposed noise-rejection data partitioning tool through various comparison studies with existing noise-rejection clustering approaches in the literature.     

Similarity,inclusion and entropy measures between type-2 fuzzy sets based on the Sugeno integral

Similarity measures of type-2 fuzzy sets are used to indicate the similarity degree between type-2 fuzzy sets. Inclusion measures for type-2 fuzzy sets are the degrees to which a type-2 fuzzy set is a subset of another type-2 fuzzy set. The entropy of type-2 fuzzy sets is the measure of fuzziness between type-2 fuzzy sets. Although several similarity, inclusion and entropy measures for type-2 fuzzy sets have been proposed in the literatures, no one has considered the use of the Sugeno integral to define those for type-2 fuzzy sets. In this paper, new similarity, inclusion and entropy measure formulas between type-2 fuzzy sets based on the Sugeno integral are proposed. Several examples are used to present the calculation and to compare these proposed measures with several existing methods for type-2 fuzzy sets. Numerical results show that the proposed measures are more reasonable than existing measures. On the other hand, measuring the similarity between type-2 fuzzy sets is important in clustering for type-2 fuzzy data. We finally use the proposed similarity measure with a robust clustering method for clustering the patterns of type-2 fuzzy sets.     

An new initialization method for fuzzy c-means algorithm

In this paper an initialization method for fuzzy c-means (FCM) algorithm is proposed in order to solve the two problems of clustering performance affected by initial cluster centers and lower computation speed for FCM. Grid and density are needed to extract approximate clustering center from sample space. Then, an initialization method for fuzzy c-means algorithm is proposed by using amount of approximate clustering centers to initialize classification number, and using approximate clustering centers to initialize initial clustering centers. Experiment shows that this method can improve clustering result and shorten clustering time validly.     

Some robust objectives of FCM for data analyzing

There are many data clustering techniques available to extract meaningful information from real world data, but the obtained clustering results of the available techniques, running time for the performance of clustering techniques in clustering real world data are highly important. This work is strongly felt that fuzzy clustering technique is suitable one to find meaningful information and appropriate groups into real world datasets. In fuzzy clustering the objective function controls the groups or clusters and computation parts of clustering. Hence researchers in fuzzy clustering algorithm aim is to minimize the objective function that usually has number of computation parts, like calculation of cluster prototypes, degree of membership for objects, computation part for updating and stopping algorithms. This paper introduces some new effective fuzzy objective functions with effective fuzzy parameters that can help to minimize the running time and to obtain strong meaningful information or clusters into the real world datasets. Further this paper tries to introduce new way for predicting membership, centres by minimizing the proposed new fuzzy objective functions. And experimental results of proposed algorithms are given to illustrate the effectiveness of proposed methods.     

Fitting semiparametric clustering models to dissimilarity data

The cluster analysis problem of partitioning a set of objects from dissimilarity data is here handled with the statistical model-based approach of fitting the “closest” classification matrix to the observed dissimilarities. A classification matrix represents a clustering structure expressed in terms of dissimilarities. In cluster analysis there is a lack of methodologies widely used to directly partition a set of objects from dissimilarity data. In real applications, a hierarchical clustering algorithm is applied on dissimilarities and subsequently a partition is chosen by visual inspection of the dendrogram. Alternatively, a “tandem analysis” is used by first applying a Multidimensional Scaling (MDS) algorithm and then by using a partitioning algorithm such as k-means applied on the dimensions specified by the MDS. However, neither the hierarchical clustering algorithms nor the tandem analysis is specifically defined to solve the statistical problem of fitting the closest partition to the observed dissimilarities. This lack of appropriate methodologies motivates this paper, in particular, the introduction and the study of three new object partitioning models for dissimilarity data, their estimation via least-squares and the introduction of three new fast algorithms.     

Fuzzy clustering using multiple Gaussian kernels with optimized-parameters

In this paper, we propose a new kernel-based fuzzy clustering algorithm which tries to find the best clustering results using optimal parameters of each kernel in each cluster. It is known that data with nonlinear relationships can be separated using one of the kernel-based fuzzy clustering methods. Two common fuzzy clustering approaches are: clustering with a single kernel and clustering with multiple kernels. While clustering with a single kernel doesn’t work well with “multiple-density” clusters, multiple kernel-based fuzzy clustering tries to find an optimal linear weighted combination of kernels with initial fixed (not necessarily the best) parameters. Our algorithm is an extension of the single kernel-based fuzzy c-means and the multiple kernel-based fuzzy clustering algorithms. In this algorithm, there is no need to give “good” parameters of each kernel and no need to give an initial “good” number of kernels. Every cluster will be characterized by a Gaussian kernel with optimal parameters. In order to show its effective clustering performance, we have compared it to other similar clustering algorithms using different databases and different clustering validity measures.     

Solution algorithms for a class of continuous linear programs with fuzzy valued objective functions

This paper discusses a class of continuous linear programs with fuzzy valued objective functions. A member of this class is called a fuzzy separated continuous linear program (FSCLP). Such problems have applications in a number of domains, including, production and inventory systems, communication networks, and pipeline systems for transportation. The discretization approach is used to construct two ordinary fuzzy linear programming problems, which give a lower and an upper bound on the optimal value of FSCLP. It is then shown how to construct an improved feasible solution for FSCLP starting from a nonoptimal one. This leads to the development of a class of algorithms based on a sequence of discrete approximations to FSCLP. Numerical examples in the context of continuous-time networks are presented to show the applicability of the proposed method.     

Numerical solution of hybrid fuzzy differential equations using improved predictor–corrector method

The hybrid fuzzy differential equations have a wide range of applications in science and engineering. This paper considers numerical solution for hybrid fuzzy differential equations. The improved predictor–corrector method is adapted and modified for solving the hybrid fuzzy differential equations. The proposed algorithm is illustrated by numerical examples and the results obtained using the scheme presented here agree well with the analytical solutions. The computer symbolic systems such as Maple and Mathematica allow us to perform complicated calculations of algorithm.     

Fuzzy clustering on LR-type fuzzy numbers with an application in Taiwanese tea evaluation

This paper presents a fuzzy clustering algorithm, called the alternative fuzzy c-numbers (AFCN) clustering algorithm, for LR-type fuzzy numbers based on an exponential-type distance function. On the basis of the gross error sensitivity and influence function, this exponential-type distance is claimed to be robust with respect to noise and outliers. Hence, the AFCN clustering algorithm is more robust than the fuzzy c-numbers (FCN) clustering algorithm presented by Yang and Ko (Fuzzy Sets and Systems 84 (1996) 49). Some numerical experiments were performed to assess the performance of FCN and AFCN. Numerical results clearly indicate AFCN to be superior in performance to FCN. Finally, we apply the FCN and AFCN algorithms to real data. The experimental results show the superiority of AFCN in Taiwanese tea evaluation.     

GEVA: geometric variability-based approaches for identifying patterns in data

This paper, arising from population studies, develops clustering algorithms for identifying patterns in data. Based on the concept of geometric variability, we have developed one polythetic-divisive and three agglomerative algorithms. The effectiveness of these procedures is shown by relating them to classical clustering algorithms. They are very general since they do not impose constraints on the type of data, so they are applicable to general (economics, ecological, genetics...) studies. Our major contributions include a rigorous formulation for novel clustering algorithms, and the discovery of new relationship between geometric variability and clustering. Finally, these novel procedures give a theoretical frame with an intuitive interpretation to some classical clustering methods to be applied with any type of data, including mixed data. These approaches are illustrated with real data on Drosophila chromosomal inversions.     

Principal component analysis for histogram-valued data

This paper introduces a principal component methodology for analysing histogram-valued data under the symbolic data domain. Currently, no comparable method exists for this type of data. The proposed method uses a symbolic covariance matrix to determine the principal component space. The resulting observations on principal component space are presented as polytopes for visualization. Numerical representation of the resulting polytopes via histogram-valued output is also presented. The necessary algorithms are included. The technique is illustrated on a weather data set.