论文部分内容阅读
本文主要研究软划分聚类算法分析中两个重要问题:参数选择和收敛性质分析。大部分软划分聚类算法中均存在参数选择问题,参数的选择直接影响聚类算法的速度和精度。讨论软划分聚类算法的收敛性质,例如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算法具备良好的聚类性能。