基于雅克比矩阵的软划分聚类算法分析

发布时间：2018-04-01 21:41

本文选题：软划分聚类分析　切入点：雅克比矩阵　出处：《北京交通大学》2017年博士论文

【摘要】：本文主要研究软划分聚类算法分析中两个重要问题:参数选择和收敛性质分析。大部分软划分聚类算法中均存在参数选择问题,参数的选择直接影响聚类算法的速度和精度。讨论软划分聚类算法的收敛性质,例如EM算法的自退火性质,可以帮助我们更好的理解这些聚类算法。除此之外,聚类算法的收敛速率可能会影响算法处理大数据的能力。本文提出一种基于雅克比矩阵的软划分聚类算法分析框架,在此框架下对软划分聚类算法参数的上下界、算法的收敛性质以及收敛速率等问题进行了讨论。本文取得的主要研究成果如下:(1)本文提出了基于雅克比矩阵的软划分聚类算法分析框架。建立该软划分聚类算法分析框架的基本假设是:重合类是大部分软划分聚类算法的不动点,但为了避免聚类算法输出重合类结果,重合类不能是软划分聚类算法的稳定点。在这个基本假设下,我们将软划分聚类算法重写为差分方程形式,通过分析软划分聚类算法差分方程的雅克比矩阵,从而对聚类算法的参数选择和收敛性质分析等等问题进行讨论。与其他软划分聚类算法分析方法相比,基于雅克比矩阵的软划分聚类算法分析方法可以用于分析一般具有隶属度和聚类中心迭代更新过程的算法,而不要求聚类算法有明确的目标函数。(2)本文在基于雅克比矩阵的软划分聚类算法分析框架下,从理论上分析了基于混合高斯模型的最大期望(EM)算法和确定性退火最大期望(DA-EM)算法的性质。一方面,我们通过分析DA-EM算法差分方程的雅克比矩阵,提出了一种选择DA-EM算法确定性退火参数理论下界的方法。另一方面我们在基于雅克比矩阵的软划分聚类算法分析框架下证明了 EM算法具有自退火性质,也就是说重合类不是EM算法的稳定点。因为DA-EM模型在确定性退火参数等于1时等于EM模型,因此我们将EM算法作为DA-EM算法的一个特殊形式,利用DA-EM的雅克比矩阵对EM算法进行理论分析。(3)GK算法是在FCM的基础上改进的一种模糊聚类算法。与FCM算法等软划分聚类算法一样,GK聚类算法的结果也会受到模糊指数m参数值的影响,然而文献中缺乏对GK聚类算法的参数选择问题的讨论。我们在基于雅克比矩阵的软划分聚类算法分析框架下,建立GK聚类算法的稳定点和样本数据间的关系,从而给出选择模糊指数m的理论根据。同时,我们研究了模糊指数m的取值对聚类算法的收敛速率的影响。最后,我们通过实验证明了理论结果的正确性。(4)模糊指数m值会严重影响GK聚类算法的聚类结果。因此,本文我们提出了一种新的基于确定性退火机制的GK聚类算法,以减小参数选择对聚类结果的影响。我们在GK聚类算法的目标函数中加入隶属度的香农(信息)熵约束,并且用确定性退火机制调节退火参数。与此同时,我们分析了确定性退火GK(DA-GK)聚类算法退火参数取值理论下界。除此之外,我们比较了 DA-GK聚类算法和其他聚类算法的聚类结果,并分析了 DA-GK聚类算法的计算复杂度。实验结果表明DA-GK算法具备良好的聚类性能。
[Abstract]:This paper mainly studies the soft clustering algorithm in the analysis of two important issues: the analysis of parameter selection and convergence properties. The parameter selection problem exists in most soft clustering algorithm, parameter selection directly affects the speed and accuracy of clustering algorithm. Discuss the convergence properties of soft clustering algorithms such as EM algorithm, self annealing properties, can help we have a better understanding of the clustering algorithm. In addition, the convergence rate of the algorithm clustering algorithm may affect the ability to handle large data. This paper proposes an analysis framework of soft clustering algorithm based on Jacobian matrix, under this framework on the parameters of soft clustering algorithm to partition the upper and lower bounds, convergence and convergence rate of the algorithm are discussed. The main achievements of this dissertation are as follows: (1) framework is proposed in this thesis. Analysis of soft clustering algorithm based on Jacobian matrix The establishment of the soft clustering algorithm framework is the basic assumptions of coincidence is most soft clustering algorithm of the fixed point, but in order to avoid clustering algorithm output results coincide, coincidence classes can not be a stable soft clustering algorithm. In this basic assumption, we will soft clustering algorithm for rewriting difference through the analysis of difference equations, Jacobian matrix equations of soft clustering algorithm, clustering algorithm to parameter selection and convergence analysis and so on are discussed. Compared with other soft clustering algorithm analysis method, soft clustering algorithm of Jacobian matrix analysis method can be used to analyze the general membership degree and cluster center with iterative update process based on the algorithm without clustering algorithm has a clear objective function. (2) based on the analysis frame of soft clustering algorithm based on Jacobian matrix The plane, from the theoretical analysis of the mixed Gauss model based on expectation maximization (EM) algorithm and the deterministic annealing expectation maximization (DA-EM) algorithm. On the one hand, we analyze the difference of Jacobian matrix equation DA-EM algorithm, put forward a method to select the DA-EM algorithm of deterministic annealing parameter theory. On the other hand the lower bound in our framework it is proved that the EM algorithm with self annealing properties of soft clustering algorithm based on Jacobian matrix, i.e. stable point is not EM algorithm. Because the DA-EM model in the deterministic annealing parameter is equal to 1 is equal to the EM model, so we use EM algorithm as a special form of the DA-EM algorithm, the theory of analysis of the EM algorithm using the Jacobian matrix of DA-EM. (3) the GK algorithm is an improved fuzzy clustering algorithm based on FCM. As with the FCM algorithm and soft clustering algorithm, GK clustering The results will be fuzzy algorithm influence index m parameter, discuss the parameters of GK clustering algorithm is however lacking in the literature selection problem. In our analysis based on soft clustering algorithm of Jacobian matrix framework, stable relationship establishment of GK clustering algorithm and the sample data, which gives the fuzzy selection index m according to the theory. At the same time, we studied the influence of convergence rate of the value of the fuzzy clustering algorithm of the M index. Finally, we prove the correctness of the theoretical results through experiments. (4) the fuzzy index m value will seriously affect the clustering results of GK clustering algorithm. Therefore, in this paper, we propose a new GK clustering the algorithm based on deterministic annealing mechanism, in order to reduce the influence of parameters selection on the clustering results. The membership degree function we target in the GK clustering algorithm in Shannon (information entropy) constraints, and deterministic annealing The lighter adjusting annealing parameters. At the same time, we analyzed the deterministic annealing GK (DA-GK) clustering algorithm of annealing parameters theoretical bounds. Besides, we compare the clustering results of DA-GK clustering algorithm and other clustering algorithms, and analyzes the calculation of the DA-GK complexity of clustering algorithms. The experimental results show that the DA-GK algorithm has good clustering performance.

【学位授予单位】：北京交通大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP311.13

【参考文献】