Analysis Of Soft Partitional Clustering Algorithms Based On Jacobian Matrix

In this dissertation, we focus on two important problems in soft partitional cluster-ing analysis:parameter selection and convergence properties. Parameter selection is an important problem in soft partitional clustering application, because the effectiveness and accuracy of soft partitional clustering algorithm may heavily influenced by the parameter value. The soft partitional clustering algorithm can be understood better through conver-gence properties analysis, such as the self-annealing properties of the EM algorithm. In addition,convergence rate have great effect on the ability of soft partitional clustering al-gorithm to deal with big data. We propose a novel Jacobian matrix based soft partitional clustering algorithms analysis method, and focus on estimate the lower/upper bound of parameter value as well as the convergence properties analysis of soft partitional cluster-ing algorithm. Our main contributions are:(1) The first contribution of this dissertation is that we proposed a novel Jacobian ma-trix based soft partitional clustering algorithms analysis method. The unacceptable coincident clustering result is the fixed point of most soft partitional clustering al-gorithms.Usually,it is not expected to be outputted. Thus it can not be the stable point of these soft partitional clustering algorithms. Based on this assumption, a theoretical basis for sotf partitional clustering algorithms analysis is proposed. We rewrite the sotf partitional clustering algorithms as difference equation, and then discuss the parameter selection and the convergence properties of clustering algo-rithm with Jacobian matrix ananlysis. The soft partitional clustering algorithms should have objective function when we use the Hessian matrix analysis, however,our new method can be applied to any kind of soft partitional clustering algorithms which have iteration process.(2) We investigate theoretical behaviors of the Expectation Maximization(EM) and De-terministic Annealing Expectation Maximization(DA-EM) algorithms for gaussian mixture models with Jacobian matrix analysis. On one hand, we derive a gener-al Jacobian matrix of the DA-EM algorithm with respect to posterior probabilities.We then propose a theoretical lower bound for initialization of the annealing param-eter in the DA-EM algorithm. On the other hand, we give a theoretical analysis on the self-annealing behavior of the EM algorithm, that is, the coincident clustering result can be avoid as a stable fixed point of the EM algorithm for Gaussian mix-tures. It should be mentioned that since the DA-EM will become the EM when the annealing parameter is 1, according to the Jacobian matrix of the DA-EM, we can prove that the self-annealing property of the EM algorithm for Gaussian mixtures.(3) The Gustafson and Kessel (GK) clustering algorithm was the first important exten-sion to the fuzzy c-means (FCM) algorithm. Just like FCM algorithm and other soft partitional clustering algorithms, the fuzziness index m is a parameter in which the value will greatly influence the performance of the GK algorithm. However,there is no theoretical work on the parameter selection for the fuzziness index m of GK. We reveal the relation between the stable fixed points of the GK algorith-m and the data sets using Jacobian matrix analysis, and then provide a theoretical base for selecting the fuzziness index m in the GK algorithm. We also compute the corresponding convergence rate for different m value to explore the influence of m on the convergence rate. Some experimental results verify the effectiveness of our theoretical results.(4) The GK algorithm may heavily influenced by the parameter of fuzziness index. We propose a novel GK fuzzy clustering algorithm based on the deterministic anneal-ing approach for decreasing the effect of parameters. We first consider maximizing the Shannon' s entropy of membership functions to the GK objective function,and then use deterministic annealing to adjust the annealing parameter. We also mathematically provide a theoretical initialization lower bound for the annealing parameter of the proposed deterministic annealing GK (DA-GK) algorithm. Com-parisons between the DA-GK algorithm and other methods are made. The compu-tational complexity of the proposed method is also provided. Experimental results and comparisons actually verify theoretical results and also indicate the superiority and effectiveness of the proposed DA-GK algorithm.