基于计算智能技术的聚类分析研究与应用

【摘要】 聚类属于无监督学习，是将数据集中的数据对象分成多个簇或者类，使得在同一个簇中对象相似度高，而在不同簇中对象的相似度低，因此，对空间数据对象的聚类可通过基于聚类目标函数的优化问题来解决。从这一思路出发，将自适应能力及鲁棒性较高的计算智能技术应用于聚类分析，产生了很多基于计算智能技术的聚类分析模型。基于计算智能的聚类分析成功解决了数据的聚类问题，对处理目标的特性有良好的适应能力，弥补了传统聚类方法的不足，取得了良好的效果。计算智能方法主要包括神经网络、模糊控制、进化计算、混沌科学、免疫计算、DNA计算及群体智能等。近年来，神经网络、模糊逻辑和进化计算三个方向的研究成为热点。自组织映射（SOM）是最有代表性的神经网络聚类方法；遗传算法、进化策略、免疫规划、克隆学说、蚁群系统、微粒群优化、文化算法等进化计算已成功应用到聚类分析中；另外，在传统聚类分析中引入模糊集概念，产生了模糊聚类算法；根据计算智能技术的优缺点，将一些计算智能方法融合起来应用于聚类分析，提高了聚类的能力。论文将神经网络、遗传算法等计算智能技术用于聚类分析，构造聚类分析模型，研究该模型的定义及优化方法的特点和不足，改进或提出相应的解决方法；另外，针对模型在聚类分析中的应用研究并结合离散Morse的相关理论和方法，研究离散Morse理论在聚类分析中实现的关键技术和方法，并提出基于Morse理论的聚类分析模型以适应具体应用的要求。通过实验，验证了模型的有效性和可行性。本文的主要研究内容如下：1.针对传统SOM网络模型用于聚类分析时竞争层神经元个数须预先指定的缺点，给出了在训练过程中动态确定网络结构和单元数目的解决方案，提出一种新的动态自组织特征映射模型，并给出模型的训练算法。此算法初始只有一个根结点。在网络训练过程中不断产生新结点。新的结点可在任意位置根据需要自动生成。当训练算法结束时，根据得到的树形结构确定聚类的数目。算法中通过扩展因子控制网络的生长，实现了不同层次的聚类。算法采用两阶段的训练思想。当算法的生长阶段完成后，利用模糊C-聚类的思想，对生长阶段产生的粗聚类结果做细化处理，从而提高最终聚类结果的精度和算法的收敛速度。通过UCI数据集来验证该模型的有效性和优越性，并对其聚类的有效性进行对比分析。2.介绍了谱聚类技术及相关概念，对谱聚类算法进行研究及分析，提出一种自动确定聚类数目的谱聚类算法。为了解决CLARANS算法易收敛于局部最优及面对大数据集聚类效率不高的问题，结合遗传算法易于找到全局最优值的特点，将遗传算法和CLARANS算法相结合，提出基于GA的聚类分析模型，并通过选择合适的适应值函数，达到聚类的目的。通过实验证明了新算法的的优越性3.介绍了离散Morse理论的基本原理及相关概念，提出一种构建离散Morse函数求最优解的算法，并证明了构建的函数是最优的离散Morse函数，同时构建了一种基于离散Morse理论的优化模型，实验的结果证明了该模型的有效性。这是一个全新的尝试。4.把基于离散Morse理论的优化模型应用于聚类分析，提出一种基于离散Morse优化模型的密度聚类算法。聚类后的结果运用层次聚类的思想进行优化，可以通过参数的调整来控制聚类簇的数目，达到聚类效果。实验证明新算法的可行性及有效性。本文的创新点总结如下：1.提出一种新的动态SOM模型。该模型采用新的生长阈值函数，训练算法采用两阶段思想。实验在UCI数据集上进行，通过与SOM模型、FCM算法及TreeGNG对比验证了该模型的有效性和优越性。2.提出一种基于GA的自动谱聚类算法GA-ISC。通过改进的谱聚类算法ISC-CLARANS达到自动产生聚类结果的目的。引入GA提高CLARANS算法的执行效率。实验分别在人工数据集及UCI数据集上进行。实验证明ISC-CLARANS算法正确、有效。通过GA-ISC与ISC-CLARANS算法的聚类结果比较，验证了GA-ISC算法的高效性。3.提出一种基于离散Morse理论的优化模型，该模型通过在单纯复形上构造离散Morse函数来实现。实验结果证明了该模型的正确性及有效性。4.提出一种新的基于离散Morse优化的聚类模型。该模型在离散曲面上进行。聚类后的结果运用层次聚类的思想进行优化。实验在人工数据集及UCI数据集上进行，通过与DBSCAN算法的聚类结果比较，验证了新模型的高效性及优越性。 

第 1 章 绪论

1.1 研究课题的背景和意义
随着信息时代的不断发展以及网络的普及，形式多样的数据急剧膨胀。要想在这浩如烟海的数据世界中找到所需的信息，强有力的数据分析工具尤为重要。人们非常需要一种强有力的能够发现数据之间内在关系的、隐含的信息和知识的工具。为迎合这种需要而产生并迅速发展起来的数据挖掘技术引起了信息科学领域的普遍关注[1]。其中聚类分析作为数据挖掘的一种强有力的分析工具，得到了迅猛的发展和成功的应用，已在科学数据探测、图像处理、模式识别、医疗诊断、计算生物学、文档检索以及 Web 分析等领域起着非常重要的作用。聚类分析的经典方法主要可归纳为[2,3,4]：划分方法、层次方法、基于密度的方法、基于网格的方法、基于模型的方法以及基于计算智能的神经网络法、进化计算法、模糊法等[5,6]，以及目前受到关注的半监督聚类方法[7]。而近来新出现的聚类集成方法已迅速成为聚类分析的新兴研究热点。聚类集成的目的是融合来自多个聚类算法的结果以得到更高质量和鲁棒性的聚类结果。基于图论的方法[8]，这是新近发展较快的方法之一，它是利用图论和图形学的原理实现聚类的方法。与传统算法相比，该算法可以处理更为复杂的簇结构如非凸结构，并能收敛于全局最优解。
 

1.1.1 聚类分析介绍及意义

聚类是从数据集中发现一些自然的分组（簇），使得簇内的相似度大，簇间的相似度小[17]。聚类技术已被应用于多个领域如模式识别、机器学习等。聚类问题可这样表述：在d维空间dR中，给定n个样本点和整数k的值，找到k个点的集合，其中k个点称为中心，使得n中的每个数据点与其最近的中心的欧氏距离的平方根（SSE）之和最小。1 1( )'( )jnkij j ij jj iSSE x x x x ，其中11jnj ijijx xn    为第j个簇的中心，ijx是第j个簇中的第i个数据点，且1,2,...ii  n，j  1,2,...k。目前存在如下几类聚类算法：（1）划分方法：给定包含n个样本点的数据集，划分方法：数据集划分为k个不相交的子集，每个子集均代表一个簇且k  n。代表算法为 K-Means 算法、K-Medoids 算法和 EM 算法、PAM 算法、CLARANS 算法等。K-Means 算法是基于划分方法的典型算法。用簇中对象的平均值来表示该簇；K-Medoids 算法中，每个簇用接近聚类中心的一个对象来表示；EM 算法以另一种形式对 K-Means 算法进行了扩展。它不把对象分配给一个确定的簇，而是根据对象与簇之间的隶属关系发生的概率来分配对象。新的平均值基于加权的度量值来计算。PAM 算法是基于 K-Medoids 算法的思想。该算法中对所有可能的对象对进行分析，每个对中的一个对象看作是中心点，而另一个不是。一个对象被能产生最大平方-误差值减少的对象替代，在一次迭代中产生的最佳对象的集合成为下次迭代的中心点。此算法的时间复杂度为2O ( k ( n  k) )，当 n 和 k 较大时，其计算代价非常高。比较适合处理较小规模的数据集。CLARA 算法则可处理较大的数据集。该算法选取整个数据集中的小部分样本，采用 PAM 算法选择中心点进行聚类。该算法的执行效率比 PAM 要高，但其聚类的质量主要取决于选取的小部分样本。

第 2 章 基于神经网络的聚类算法研究

2.1 引言
神经网络技术用于聚类分析起源于 Kohonen 在 1981 年提出的自组织特征映射神经网络（SOM）。SOM 神经网络是一种无监督的聚类方法。该网络可分为输入层和输出层。输出层的神经元互相连接，，每个输出神经元连接到所有输入神经元，通过若干个单元竞争当前对象来实现聚类。虽然 SOM 网络能够模拟人脑的处理过程，输出保持了输入对象的拓扑结构，有利于在二维或者三维空间中可视化高维数据。但当 SOM 网络应用于聚类分析时，由于该模型本身的缺点及应用环境的变化，在应用过程中主要存在以下问题：1）SOM 网络结构的难以确定由于传统 SOM 网络模型用于聚类分析时竞争层神经元个数须预先指定，因此大大限制了网络的结构及其收敛速度。当在聚类过程中采用该模型时，由于数据间的聚类关系不确定，若输出层神经元个数M过多则会降低学习的速度，增加计算量。若M的个数过少，则可能产生粗的聚类结果，把两种或两种以上模式相近的簇归为一类，不能得到期望的聚类结果。因此，多种在训练过程中动态确定网络结构和单元数目的算法应运而生。

2.2 基于 SOM 网络的聚类分析模型
当外界输入不同的样本到 SOM 网络时，初始，输入样本引起输出兴奋细山东师范大学博士学位论文28胞的位置各不相同，但经过自组织后形成一些细胞群，他们分别反映了输入样本的特征。这些细胞群在二维输出空间是一个平面区域，样本自学习后，在输出神经元层中排列成一张二维的映射图，功能相同的神经元靠得比较近，功能不相同的神经元分得比较开，这个映射过程通过无指导的竞争学习算法来实现，因此称为自组织特征映射。SOM 属于无监督学习网络。当输入矢量X属于两个不同类别时，则相应的输出y的值应能够反映输入矢量X的特征。如果矢量X在矢量空间中具有随机分布，此分布有一个变化最大的方向，则特征就是指大体上是该矢量在此方向上的投影。当X属于不同的类时，相应的输出值y会有一个明显的差异，则聚类的功能就可完成。如果输入矢量是一个在空间中具有纯均匀分布的随机矢量，则算法失效；只有当输入矢量的分布具有某种特征时，才能通过神经元的自组织学习来发现这些特征，并且用输出函数y来描述这种特征。

第 3 章 基于遗传优化的谱聚类算法研究
3.1 引言................................................................43
3.2 谱聚类算法的介绍....................................................44
3.3 改进的谱聚类算法 ...................................................54
3.4 基于遗传算法的谱聚类方法.............................................57
3.5 小结.................................................................63

第 4 章 基于 Morse 优化模型的聚类算法研究

4.1 引言
Morse 理论作为一个强有力的工具应用于计算拓扑学、计算机图形学、几何建模等领域。该理论最初用于研究光滑流形的结构。近年来，Forman 将理论推广到离散结构如单纯复形中，取得了更广范围的应用。在流形上定义一个 Morse 函数，则可通过产生的临界单元得出该流形的拓扑结构信息。因此，如何在单元复形上定义最优离散 Morse 函数是一个关键问题。而最优则是指由此产生的临界单元最少。Forman 证明了这是一个MAX  SNP问题。Thomas 在 2 维流形上提出一种线性算法使得总能达到最优。受 Forman[88][115]的离散 Morse 理论的启发，本文尝试在 3 维及以上离散空间K 对任意给定的 f :K   R进行优化分析构造最优离散 Morse 函数，产生尽可能少的临界单元，从而得到函数的最优值或接近最优值。根据上述思想构建了一种基于离散 Morse 理论的优化模型，解决了离散 Morse 理论的优化问题，并把这一优化模型应用于聚类分析，提出一种基于离散 Morse 优化模型的聚类算法。算法采用基于核密度估计的层次聚类的思想，根据离散 Morse 优化模型得到密度函数的极值，同时根据构造的离散梯度向量场得到以极值点为聚类中心的数据集的初始划分，然后通过临界单元的抵消算法对初始聚类进行合并产生不同层次的划分模式。实验分别在人工数据集和 UCI 数据库中的Iris数据集和Haberman 's Survival数据集上进行。理论分析和仿真实验结果显示，该算法能够发现任意形状、大小和密度的聚类，能较好划分数据点重叠区域的聚类形状，证明了新算法的可行性及有效性。

结论
基于计算智能的聚类分析模型对处理目标的特性有良好的适应能力，弥补了传统聚类算法的缺点及不足，取得了良好的效果。本文中有针对性的选取了计算智能方法中的人工神经网络、遗传算法、离散 Morse 理论应用于聚类分析，构造聚类分析模型，研究该模型的定义及优化方法的特点和不足，改进或提出相应的解决方法。离散 Morse 理论是一种新的计算智能技术，本文在研究其理论的基础上，成功把该技术应用到聚类分析中。本文针对模型在聚类分析中的应用研究并结合离散 Morse 的相关理论和方法，研究离散 Morse 理论在聚类分析中实现的关键技术和方法，并提出基于 Morse 理论的密度聚类分析模型以适应具体应用的要求，同时对提出的聚类分析模型进行推广，使其具有更为普遍的适用性。根据该模型的特点，采用面向对象技术搭建实验平台，以验证所提方法或策略的有效性。
现将论文取得的一些研究成果总结如下：1. 阐述了传统的 SOM 网络聚类分析模型，给出了 SOM 网络聚类模型的特点，研究及分析了 SOM 网络用于聚类分析时竞争层神经元个数需提前给出及网络结构的固定化等问题。针对传统 SOM 网络聚类分析模型，介绍了有代表性的动态网络聚类分析模型—TreeGNG 动态网络聚类分析模型。本论文借鉴了 TreeGNG 网络训练算法中树形结构的构造思想，结合神经网络中两步聚类的方法，提出一种新的动态模糊自组织神经网络聚类模型 DSOM-FCM（dynamic self-organizing map-fuzzy C-means）。DSOM-FCM 是基于初始只有一个根结点的树形结构模型。在网络训练过程中不断产生新结点。新的结点可在任意位置根据需要自动生成。当训练算法结束时，根据得到的树形结构确定聚类的数目。

参考文献（略）