A Global Optimization RLT-based Approach for Solving the Fuzzy Clustering Problem

The field of cluster analysis is primarily concerned with the partitioning of data points into different clusters so as to optimize a certain criterion. Rapid advances in technology have made it possible to address clustering problems via optimization theory. In this paper, we present a global optimization algorithm to solve the fuzzy clustering problem, where each data point is to be assigned to (possibly) several clusters, with a membership grade assigned to each data point that reflects the likelihood of the data point belonging to that cluster. The fuzzy clustering problem is formulated as a nonlinear program, for which a tight linear programming relaxation is constructed via the Reformulation-Linearization Technique (RLT) in concert with additional valid inequalities. This construct is embedded within a specialized branch-and-bound (B&B) algorithm to solve the problem to global optimality. Computational experience is reported using several standard data sets from the literature as well as using synthetically generated larger problem instances. The results validate the robustness of the proposed algorithmic procedure and exhibit its dominance over the popular fuzzy c-means algorithmic technique and the commercial global optimizer BARON.     

土壤分类的模糊集成算法与应用

土壤是一个多性状的连续体,其分类的首选方法是模糊聚类分析.但是模糊聚类分析中现有的基于模糊等价关系的动态聚类法和模糊c-均值法各有利弊,采用其中一种方法聚类肯定存在不足.为此集成两种聚类方法的优点,避其缺点,提出了用基于模糊等价关系的动态聚类方法和方差分析方法确定聚类数目和初始聚类中心,再用模糊c-均值法决定最终分类结果的集成算法,并将其应用到松花江流域土壤分类中,得到了较为切合实际的分类结果.     

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.     

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.     

基于微分进化算法的FCM图像分割算法

为提高模糊C均值(FCM)算法的自动化程度,提出基于微分进化算法的FCM图像分割算法(DEFCM),利用微分进化算法全局性和鲁棒性的特点自动确定分类数和初始聚类中心,再将其作为模糊c均值聚类的初始聚类中心,弥补FCM算法的不足.实验表明该算法不仅能够正确地对图像分类,而且能获得较好的图像分割效果和质量.     

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

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

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.     

Density based fuzzy c-means clustering of non-convex patterns

We propose a new technique to perform unsupervised data classification (clustering) based on density induced metric and non-smooth optimization. Our goal is to automatically recognize multidimensional clusters of non-convex shape. We present a modification of the fuzzy c-means algorithm, which uses the data induced metric, defined with the help of Delaunay triangulation. We detail computation of the distances in such a metric using graph algorithms. To find optimal positions of cluster prototypes we employ the discrete gradient method of non-smooth optimization. The new clustering method is capable to identify non-convex overlapped d-dimensional clusters.     

模糊蚁群算法及其在TSP中的应用

在传统蚁群算法的基础上加入了使用模糊规则表更新信息素的策略,提出了一种新的算法——模糊蚁群算法.算法结合了模糊控制中输入输出的模糊化处理和蚁群寻优的特点,为实际问题提供了新的解决手段.文中将模糊蚁群算法应用于TSP问题,通过对中国31个省会城市等实例数据进行的测试,验证表明了新算法具有良好的有效性和鲁棒性.     

On fuzzy cluster validity indices

Cluster analysis aims at identifying groups of similar objects, and helps to discover distribution of patterns and interesting correlations in large data sets. Especially, fuzzy clustering has been widely studied and applied in a variety of key areas and fuzzy cluster validation plays a very important role in fuzzy clustering. This paper introduces the fundamental concepts of cluster validity, and presents a review of fuzzy cluster validity indices available in the literature. We conducted extensive comparisons of the mentioned indices in conjunction with the Fuzzy C-Means clustering algorithm on a number of widely used data sets, and make a simple analysis of the experimental results.     

A modified rough c-means clustering algorithm based on hybrid imbalanced measure of distance and density

Traditional c-means clustering partitions a group of objects into a number of non-overlapping sets. Rough sets provide more flexible and objective representation than classical sets with hard partition and fuzzy sets with subjective membership function for a given dataset. Rough c-means clustering and its extensions were introduced and successfully applied in many real life applications in recent years. Each cluster is represented by a reasonable pair of lower and upper approximations. However, the most available algorithms pay no attention to the influence of the imbalanced spatial distribution within a cluster. The limitation of the mean iterative calculation function, with the same weight for all the data objects in a lower or upper approximation, is analyzed. A hybrid imbalanced measure of distance and density for the rough c-means clustering is defined, and a modified rough c-means clustering algorithm is presented in this paper. To evaluate the proposed algorithm, it has been applied to several real world data sets from UCI. The validity of this algorithm is demonstrated by the results of comparative experiments.     

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.     

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.     

模糊人工蜂群算法的多选择多维背包问题求解

针对传统人工蜂群算法早熟收敛问题,基于模糊化处理和蜂群寻优的特点,提出一种模糊人工蜂群算法。将模糊输入输出机制引入到算法中来保持蜜源访问概率的动态更新。根据算法计算过程中的不同阶段对蜜源访问概率有效调整,避免算法陷入局部极值。通过对多选择多维背包问题的仿真实验和与其他算法的比较,表明本算法可行有效,有良好的鲁棒性。     

A modified fuzzy clustering for documents retrieval: application to document categorization

The paper advocates the use of a new fuzzy-based clustering algorithm for document categorization. Each document/datum will be represented as a fuzzy set. In this respect, the fuzzy clustering algorithm, will be constrained additionally in order to cluster fuzzy sets. Then, one needs to find a metric measure in order to detect the overlapping between documents and the cluster prototype (category). In this respect, we use one of the interclass probabilistic reparability measures known as Bhattacharyya distance, which will be incorporated in the general scheme of the fuzzy c-means algorithm for measuring the overlapping between fuzzy sets. This enables the introduction of fuzziness in the document clustering in the sense that it allows a single document to belong to more than one category. This is in line with semantic multiple interpretations conveyed by single words, which support multiple membership to several classes. Performances of the algorithms will be illustrated using a case study from the construction sector.     

Fuzzy system reliability analysis by the use of Tω (the weakest t-norm) on fuzzy number arithmetic operations

In general, the sup-min convolution has been used for fuzzy arithmetic to analyze fuzzy system reliability, where the reliability of each system component is represented by fuzzy numbers. It is well known that T_ω-based addition preserves the shape of L-R type fuzzy numbers. In this paper, we show T_ω-based multiplication also preserves the shape of L-R type fuzzy numbers. We then apply T_ω-based arithmetic operations to fuzzy system reliability analysis. In fact, we show that we can simplify fuzzy arithmetic operations and even get the exact solutions for L-R type fuzzy system reliability, while others [Singer, Fuzzy Sets Syst. 34 (1990) 145; Cheng and Mon, Fuzzy Sets Syst. 56 (1993) 29; Chen, Fuzzy Sets Syst. 64 (1994) 31] have got the approximate solutions using sup-min convolution for evaluating fuzzy system reliability.     

A Global Optimization RLT-based Approach for Solving the Hard Clustering Problem

The field of cluster analysis is primarily concerned with the sorting of data points into different clusters so as to optimize a certain criterion. Rapid advances in technology have made it possible to address clustering problems via optimization theory. In this paper, we present a global optimization algorithm to solve the hard clustering problem, where each data point is to be assigned to exactly one cluster. The hard clustering problem is formulated as a nonlinear program, for which a tight linear programming relaxation is constructed via the Reformulation-Linearization Technique (RLT) in concert with additional valid inequalities that serve to defeat the inherent symmetry in the problem. This construct is embedded within a specialized branch-and-bound algorithm to solve the problem to global optimality. Pertinent implementation issues that can enhance the efficiency of the branch-and-bound algorithm are also discussed. Computational experience is reported using several standard data sets found in the literature as well as using synthetically generated larger problem instances. The results validate the robustness of the proposed algorithmic procedure and exhibit its dominance over the popular k-means clustering technique. Finally, a heuristic procedure to obtain a good quality solution at a relative ease of computational effort is also described.     

A fuzzy adaptive network approach to parameter estimation in cases where independent variables come from an exponential distribution

In a regression analysis, it is assumed that the observations come from a single class in a data cluster and the simple functional relationship between the dependent and independent variables can be expressed using the general model; Y=f(X)+ε. However; a data cluster may consist of a combination of observations that have different distributions that are derived from different clusters. When faced with issues of estimating a regression model for fuzzy inputs that have been derived from different distributions, this regression model has been termed the ‘switching regression model’ and it is expressed with . Here l_i indicates the class number of each independent variable and p is indicative of the number of independent variables [J.R. Jang, ANFIS: Adaptive-network-based fuzzy inference system, IEEE Transaction on Systems, Man and Cybernetics 23 (3) (1993) 665–685; M. Michel, Fuzzy clustering and switching regression models using ambiguity and distance rejects, Fuzzy Sets and Systems 122 (2001) 363–399; E.Q. Richard, A new approach to estimating switching regressions, Journal of the American Statistical Association 67 (338) (1972) 306–310].In this study, adaptive networks have been used to construct a model that has been formed by gathering obtained models. There are methods that suggest the class numbers of independent variables heuristically. Alternatively, in defining the optimal class number of independent variables, the use of suggested validity criterion for fuzzy clustering has been aimed. In the case that independent variables have an exponential distribution, an algorithm has been suggested for defining the unknown parameter of the switching regression model and for obtaining the estimated values after obtaining an optimal membership function, which is suitable for exponential distribution.     

Online identification of Takagi–Sugeno fuzzy models based on self-adaptive hierarchical particle swarm optimization algorithm

This paper presents an approach for online learning of Takagi–Sugeno (T-S) fuzzy models. A novel learning algorithm based on a Hierarchical Particle Swarm Optimization (HPSO) is introduced to automatically extract all fuzzy logic system (FLS)’s parameters of a T–S fuzzy model. During online operation, both the consequent parameters of the T–S fuzzy model and the PSO inertia weight are continually updated when new data becomes available. By applying this concept to the learning algorithm, a new type T–S fuzzy modeling approach is constructed where the proposed HPSO algorithm includes an adaptive procedure and becomes a self-adaptive HPSO (S-AHPSO) algorithm usable in real-time processes. To improve the computational time of the proposed HPSO, particles positions are initialized by using an efficient unsupervised fuzzy clustering algorithm (UFCA). The UFCA combines the K-nearest neighbour and fuzzy C-means methods into a fuzzy modeling method for partitioning of the input–output data and identifying the antecedent parameters of the fuzzy system, enhancing the HPSO’s tuning. The approach is applied to identify the dynamical behavior of the dissolved oxygen concentration in an activated sludge reactor within a wastewater treatment plant. The results show that the proposed approach can identify nonlinear systems satisfactorily, and reveal superior performance of the proposed methods when compared with other state of the art methods. Moreover, the methodologies proposed in this paper can be involved in wider applications in a number of fields such as model predictive control, direct controller design, unsupervised clustering, motion detection, and robotics.