计算机工程与应用2012，48
数据挖掘的重要任务之一就是发现大型数据中的积聚现象，并加以定量化描述。聚类分析就是按照某种相似性度量，具有相似特征的样本归为一类，使得类内差异相似度较小，而类间差异较大。迄今为止。聚类还没有一个学术界公认的定义。这里给出Everitt[1]在1974 年关于聚类所下的定义：一个类簇内的实体是相似的，不同类簇的实体是不相似的；一个类簇是测试空间中点的会聚，同一类簇的任意两个点间的距离小于不同类簇的任意两个点间的距离；类簇可以描述为一个包含密度相对较高的点集的多维空间中的连通区域，它们借助包含密度相对较低的点集的区域与其他区域（类簇）相分离。
聚类算法的目的是寻找数据中潜在的自然分组结构和感兴趣的关系。聚类分析则是用数学方法研究和处理所给对象的分类以及各类之间的亲疏程度，是在对数据不作任何假设的条件下进行分析的工具。
3.1 传统聚类方法
3.1.1 基于划分的聚类方法
Macqueen[4]提出的k-平均方法是解决聚类问题的一种经典方法。它的主要优点是算法简单、快速。缺点是对不同的k 值可能会导致不同的聚类结果。其次，该方法不能发现非凸面的簇，或大小差别很大的簇。而且对“噪声”和孤立点很敏感，因为少量的该类数据能对平均值产生极大的影响。Kaufman和Roussseeuw 提出的PAM（Partitioning Around Medoid）和CLARA（Clustering Large Applications）[5]算法中，每个类用接近该类中心的对象来表示，因此称之为k-中心点方法。k-中心点方法可以看做是k-平均方法的改进方法，因为中心点不像平均值那么容易被极端数据影响，所以当存在噪声和孤立点数据时，k-中心点方法比k-平均方法更强壮。
为了对大规模的数据集进行聚类，以及处理复杂的聚类，基于划分的方法有了很多改进算法。Huang提出k-模（k-modes）[6]方法，它扩展了k-平均方法，用模来代替类的平均值，Lauritzen 提出EM（ExpectationMaximization）[7]算法不把对象分配给一个确定的簇，而是根据对象与簇之间隶属关系发生的概率来分配
对象。Ng 和Han 提出的CLARANS（Clustering Large Application based upon Randomized Search）[8]算法将采样技术与PAM结合起来，不考虑整个数据集合，而是随机地选择实际数据的一小部分作为数据样本，适用于大规模数据的聚类分析。Ester，Kriegel 和Xu采用高效的空间存取方法R*树和聚焦技术，进一
步改进了CLARANS的性能[9]。FREM（Fast and Robust EM）算法[10]改进了EM算法的性能，使其更适合大规模数据的聚类问题。
3.1.2 基于层次的聚类方法
层次方法对样本集合进行合并或者分裂，直到满足某一个终止条件，聚类结果将样本组成一棵聚类树。根据层次分解是自底向上还是自顶向下，层次聚类方法可以分为凝聚（agglomerative）和分裂（division）两大类，前者是由单个样本开始，逐渐合并较小的样本集，最终形成一个包含所有样本的簇，或达到某个终止条件；后者先将所有样本看作一个簇，然后逐渐细分为越来越小的簇，直到最后每个对象都自成一个簇，或达到某个终止条件。
基本的层次聚类方法是Kaufman 和Rousseeuw提出的凝聚方法和分裂方法，其缺点是合并点或分裂点选择的困难，可伸缩性差。Zhang 提出的BIRCH
（Balanced Iterative Reducing and Clustering using Hierarchies）[11]是一种综合的方法，首先建立存放于内存的CF（Cluster Feature）树，再采用某个聚类算法对CF树的叶结点进行聚类。Guha 提出的CURE（Clustering Using Representatives）[12]方法不用单个中心或对象来代表一个类，而是选择数据空间中固定数目的具有代表性的点代表一个类，可以识别复杂形状和大小不同的类，而且能很好地过滤孤立点。Guha在CURE方法的基础上，又提出了适用于分类数据的ROCK方法[13]。文献[14]对ROCK算法进行了进一步分析，首先指出在ROCK 算法主要缺点是：（1）衡量两个数据点是否为邻居的相似度阈值θ需要预先静
态指定，该阈值对聚类质量影响很大，在对数据集没有充分了解的前提下给出恰当的阈值是困难的。（2）在ROCK算法中，相似度函数sim 仅被用于最初邻居的
判断上，只考虑相似与否，而未考虑相似程度，使算法对θ值过于敏感。（3）ROCK还要求用户事先选定聚类簇数k。这些缺陷或者影响聚类效果，或使算法不
便使用。然后结合上述缺点给出一种基于动态近邻选择模型的聚类算法DNNS，通过优选近邻来提高聚类质量。
层次聚类算法优点在于算法能够得到不同粒度上的多层次聚类结构，但存在下述缺点：（1）会经常遇到合并或分裂点选择的困难，如果合并或分裂的决定不好，则可能导致聚类质量下降。（2）由于合并或分裂的决定需要检查和估算大量的样本或簇，使得这类算法伸缩性不理想。（3）算法时间复杂度高，为O(n2 lg n)~O(n3) 。
3.1.3 基于网格的聚类方法
基于网格的方法把对象空间量化为有限数目的单元，形成一个网格结构，每一维上分割点的位置信息存储在数组中，分割线贯穿整个空间，所有的聚类操作都在这个网格结构（即量化空间）上进行。这种方法的主要优点是它的处理速度很快，其处理速度独立于数据对象的数目，只与量化空间中每一维的单元数目有关，但其效率的提高是以聚类结果的精确性为代价的。但是所有的网格聚类算法都存在量化尺度的问题，通常是先从小单元开始寻找聚类，再逐渐增大单元的体积，重复这个过程，直到发现满意的聚类为止。
Wang 提出的STING[15]（Statistical Information Grid）和STING+[16]是基于网格的多分辨率方法。Sheikholeslami等提出的Wavecluster[17]也是一个多分辨率的聚类方法。它首先通过在数据空间上强加一个多维网格结构来汇总数据，然后采用一种小波变换来变换原特征空间，在变换后的空间中找到密集区域。Yu Dantong[18]提出一种改进的小波变换聚类方法Wavecluster +，可处理复杂的图像数据聚类问题。
Agrawal 等提出的CLIQUE[19]（Clustering In Quest）和文献[20]中的方法均是综合了基于密度和网格方法的聚类方法，用于聚类高维数据。文献[21]中的方法
是适合于大规模数据的网格方法。这些方法对数据的输入顺序不敏感，无需假设任何规范的数据分布，对数据的维数和规模有良好的可伸缩性；但此类方法由于方法大大简化，聚类结果的精确性一般较低。
3.1.4 基于密度的聚类方法
基于密度的聚类方法主要思想是：以空间中的一个样本为中心，单位体积内的样本个数称为该点的密度，从直观上看，簇内样本的密度较大，簇间样本的密度较小。该算法根据空间密度的差异，将簇看作是样本空间中被低密度区域分割开的高密度样本区域。只要邻近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。各个密度算法的差异主要在于如何定义高密度区和低密度区。基于密度的聚类算法的主要缺点是从样本集中获得的密度图很不均匀，往往会形成很多虚的极值，从而产生伪聚类。整体来看，多数基于密度的聚类方法对参数都很敏感，参数设置的细微不同可能导致差别很大的聚类结果。
Ester 等提出了DBSCAN[22]（Density-Based Spatial Clustering of Applications with Noise）。该算法将具有足够高密度的区域划分为类，并可以在带有
“噪声”的空间数据中发现任意形状的类。周水庚[23]等在不同方面对DBSCAN 算法进行改进，提高了DBSCAN 算法的执行效率。Ankerst 等提出的OPTICS[
24]（Ordering Points to Identify the Clustering Structure）算法是一种基于类排序方法。它克服了DBSCAN参数设置复杂的缺点。赵艳厂[25]从样本分
布等密度线图的思想出发，提出一种等密度线聚类算法；Hinneburg[26]提出的DENCLUE 方法、裴继法[27]等提出的方法均为基于密度分布函数的方法；文
献[28]中的聚类方法则是基于密度和距离的综合方法；文献[29]将数据空间划分成多个体积相等的矩形单元格，然后基于单元格定义了密度、簇等概念，对
单元格建立了一种基于空间划分的空间索引结构（SPTree，空间划分树），通过空间划分树SP-Tree 来寻找密集单元和密集单元的连通区域形成聚类；文献[30]
考虑到样本空间分布的不均匀性，通过距离变化率刻画空间局部密度变化，并用来度量邻近目标间空间局部密度变化情况；文献[22]针对高维空间水平数据分布的聚类问题，通过引入局部密度聚类和密度吸引子，给出了一种局部分布式密度聚类算法DBDC算法。
3.1.5 基于模型的聚类方法
基于模型的方法为每一类假定存在一个模型，寻找数据对给定模型的最佳拟合。基于模型的方法通过建立反映样本空间分布的密度函数定位聚类，试图优化给定的数据和某些数据模型之间的适应性。基于模型的方法主要有两类：统计学方法和神经网络方法。
统计学方法中常用方法包括Fisher 提出的COBWEB[31]，Gennari 等提出的CLASSIT[32]，及Cheeseman等提出的AutoClass[33]，Pizzuti Clara 等提出的P-AutoClass[34]等。神经网络方法中有D.E.Rumelhart 提出的竞争学习[35] （Competitive Learning），采用若干个单元的层次结构，它们以一种“胜者为王（winner-take-all）”的方式对系统当前处理的对象进行竞争。Kohonen提出的学习矢量量化[36] （Learning Vector Quantization，LVQ）。这是一种自适应数据聚类方法，它基于对具有期望类别信息数据的训练。文献[37]提出在特定的条件下更新获胜单元和第二单元（下一个最接近的向量），以便更有效地利用训练数据。Kohonen[38]提出自组织特征映射（Self-Organizing Feature Map，SOFM），SOM算法将高维空间的数据转化到二维空间，并且在二维空间中很好地保持了输入数据之间的相似性，其能够根据数据的分布逐步收敛到最佳的类别划分。与其他聚类方法相比，SOM 聚类的优点在于：可以实现实时学习，算法具有自稳定性和自
学习性，无需外界给出评价函数，抗噪音能力强。
SOM 文本聚类算法的实质就是发现能够有效划分文档集合的神经元集合。文献[39]通过压缩神经元的特征集合，仅选择与神经元代表的文档类相关的特征构造神经元的特征向量，从而减少了聚类时间。同时由于选取的特征能够将映射到不同神经元的文档类进行有效区分，避免了无关特征的干扰，因而提升了聚类的精度。
3.2 数据挖掘领域中的聚类方法新发展
但是由于每一种方法都有缺陷，再加上实际问题的复杂性和数据的多样性，使得无论哪一种方法都只能解决某一类问题。近年来，随着人工智能、机器学习、模式识别和数据挖掘等领域中传统方法的不断发展以及各种新方法和新技术的涌现，数据挖掘中的聚类分析方法得到了长足的发展。整体来看，主要围绕样本的相似性度量、样本归属关系、样本数据的前期处理、高维样本聚类、增量样本聚类等几个方面展开研究。
3.2.1 基于样本归属关系的聚类
3.2.1.1 基于粒度的聚类算法（Granular Clustering）
从表面上看，聚类和分类有很大的差异——聚类是无导师的学习，而分类是有导师的学习。更进一步地说，聚类的目的是发现样本点之间最本质的抱团性质的一种客观反映；分类在这一点上却不大相同。分类需要一个训练样本集，由领域专家指明哪些样本属于一类，哪些样本数据属于另一类，但是分类的这种先验知识却常常是纯粹主观的。如果从信息粒度的角度来看的话，就会发现聚类和分类有很大的相通之处：聚类操作实际上是在一个统一粒度下进行计算的；分类操作是在不同粒度下进行计
算的[40]，所以说在粒度原理下，聚类和分类是相通的，很多分类的方法也可以用在聚类方法中。文献[41]基于粗糙集理论，分析等价关系与粒度之间的关系，根据数据对象之间的相对相似性形成初始等价关系和等价类，每个等价类对应一个粒度。引入等价关系隶属度因子γ来度量等价关系间隶属关系，并控制聚类的规模，通过迭代计算聚类的有效性，得到优化的聚类结果。
3.2.1.2 不确定聚类算法（Uncertainty Clustering）
（1）模糊聚类（Fuzzy Clustering）在实践中大多数对象没有严格的属性，它们的类属和形态存在着中介性，适合软划分。由于模糊聚类分析具有描述样本类属中间性的优点，能客观地反映现实世界，成为当今聚类分析研究的主流。
1969 年，Ruspini[42]首次将模糊集理论应用到聚类分析中，提出了模糊聚类算法是基于模糊数学理论的一种非监督学习方法。模糊聚类一经提出，就得到了学术界极大关注，模糊聚类是一个很大的聚类“家族”，关于模糊聚类的研究十分活跃，下面从目标函数、隶属度函数和聚类准则函数等三个方面综述其发展。
在目标函数研究方面，Krishnapuram放弃了FCM的可能性约束条件，构造了一个新的目标函数，提出了可能性C-均值聚类（PCM1）[43]，PCM1 能够聚类包含噪声或野值点的数据，PCM1 使噪声数据具有很小的隶属度值，因而噪声对聚类的影响可以忽略。但是PCM1 对初始聚类中心很敏感，常常会导致一致性聚类结果。PCM1 重视了典型性思想，从而减少了噪声对聚类的影响，但它忽略了模糊隶属度，模糊隶属度可以使类中心和数据紧密联系在一起。为了克服FCM对噪声数据敏感和PCM1 产生一致性聚类的缺点，Pal 等在FCM和PCM的基础上提出了可能性模糊C-均值聚类（PFCM）[44]。Krishnapuram 提出一种新的PCM（PCM2）以聚类数据集中彼此靠近的、包含噪声的数据[45]。但是PCM2 同样对初始聚类中心很敏感，也会导致一致性聚类结果，同时PCM2 非常依赖参数，为了解决这个缺点Yang 和Wu 提出了可能性聚类算法（PCA）[46]。但是PCA 仅仅解决了PCM2 的参数问题，它没有解决PCM2 对初始聚类中心很敏感，易导致一致性聚类结果的缺点。同时PFCM同样依赖参数，需要事先运行FCM来计算参数。文献[47]在综合PFCM和PCA的基础上给出了另一个PFCM，从一定程度上解决PFCM对参数依赖的同时又没有像PCA易导致一致性聚类结果那样的缺点。
在隶属度函数研究方面，文献[48]提出了一种改进模糊分割的聚类算法IFP-FCM，通过引入隶属度约束函数，得到意义更趋明晰的隶属度迭代公式，使得新算法对噪声和例外点具有更好的鲁棒性。但文献[48]引入隶属度约束函数后，其算法的模糊指数m限定为2，没有解决模糊指数m的一般化问题，此新算法的聚类效果受到约束。在FCM算法中，m的选择严重影响着算法的表现，正如Bezdek[49]指出：当m=1 时，FCM算法退化为HCM算法，当m趋向于无穷时，FCM算法得到的各个类的中心几乎都退化成数据的重心，显然在上述两种情形之下，FCM算法的表现都不能令人满意。文献[49]给出了一个新的隶属度约束惩罚项，推导出一般化的改进模糊划分的FCM聚类算法GIFP-FCM，解决了IFP-FCM算法模糊指数m一般化问题；同时从竞争学习的角度并利用Voronoi 距离对GIFP-FCM 算法的快速收敛性和鲁棒性进行了合理解释；对模糊程度系数α 的意义做了很好的阐明，使得FCM算法和IFP-FCM 算法分别成为GIFP-FCM算法在α 等于0 和α 趋于1 时的特例。文献[50]提出了不确定隶属的概念，给出了两个基于相对隶属程度的判断准则参数，设计出一种新的基于隶属关系不确定的可能性模糊聚类新算法，该算法将迭代过程中数据集对聚类簇隶属的可能性与不确定性关系引入目标函数中，达到明显的优化聚类结果的功效。
在聚类准则函数聚类研究方面，在划分聚类方法中，一般都是对聚类样本同等对待，但实际上，不同的样本对聚类结果有不同的贡献，因此通过修改准则函数提出了加权的聚类算法，从而实现对不同形状分布样本的聚类的目的。文献[51]对模糊C-均值聚类算法中加权指数m进行了深入研究。文献[52]对聚类有效性函数FP（u，c）进行了研究，指出FP（u，c）作为FCM 算法的聚类有效性函数是不合适的。文献[53]提出了自动变量加权C均值算法，从而能够合理地选择变量及每个变量的贡献大小；文献[54]讨论了模糊属性C均值聚类算法，提出了基于模糊度m的Bezdek 型模糊属性C均值聚类算法；文献[55]应用拉普拉斯加权调整了HCM和FCM算法的目标函数，通过计算样本与聚类中心的距离获得合理的权系数，能够很好地描述数据邻域结构，并能够利用不同样本影响的差异性；文献[56]将PBMF、XB、PE 和PC
等模糊聚类有效性指标集成为模糊权和有效性函数（FWSVF），提高了算法的通用性。
（2）粗糙聚类（Rough Clustering）
不确定聚类另外一种就是粗糙聚类，从粗糙集与聚类算法的耦合来看，可以把粗糙聚类分为两类：强耦合粗糙聚类和弱耦合粗糙聚类。所谓弱耦合粗糙聚类，就是粗糙集扮演着数据预处理等角色，最主要的应用就是用粗糙集的属性约简理论对进行聚类的样本数据进行降维，所谓的强耦合是指利用粗糙集的上、下近似理论对聚类算法上、下近似处理。强耦合中，Lingras P[57]把粗糙集引入到聚类问题中，提出了粗糙聚类算法，文献[58]进一步进行了研究，提出了自适应粗糙聚类；在弱耦合中，关于属性约简有很多文献，此处不再列出。
3.2.1.3 球壳聚类（Spherical Shell Clustering）
球壳聚类其实是模糊聚类的衍生，模糊聚类的原型由点逐步扩展到线、面、球壳、椭圆壳、矩形壳和多边形壳[59]。其中球壳聚类是其中研究最为活跃的一种。所谓球壳聚类就是样本数据的分布呈球壳状的聚类问题，可以采用球壳作为聚类原型，定义目标函数，并推导出球壳聚类的迭代算法。模糊壳聚类方法依赖于人脑事先给出确定的聚类壳数，并且对原型初始化要求较高，这是因为目标函数的局部极值点很多，容易陷入局部极值点。文献[60]提出一种基于量子测量的球壳聚类方法。该算法将聚类样本集分别视为可测量的环境量子系综和刺激量子系综，每个样本视为宏观系综中的一个微观量子叠加态。刺激量子系综依概率在具体微观态上进行塌缩产生刺激引起无意识的注意，并产生球壳面算符。
3.2.1.4 基于熵的聚类（Clustering based on Entropy）
在物理学中，熵用来描述原子分布的无序程度。当某一系统越有序、越确定时，该系统的热熵越小；在信息论中，信息熵是一个信源发出某一消息所含信息量的度量，当某一信源发出的消息越确定时，该信源的信息熵越小；数据点的分布类似于原子的分布，当聚类的划分越合理，数据点在某一聚类上的归属越确定时，该聚类的信息熵值越小。在聚类分析中，由于在分组前数据点对某一聚类的归属在主观划分上是依赖于用户所选取的算法的，当用户采取不同的算法时，数据点的归属性就不同，而客观上来讲，数据点对某一聚类的归属又是确定的。因此，如果在主观上找到尽可能确定的数据点归属，即求得信息熵值最小的聚类结果，那么聚类的目的就达到了，这就是基于熵的聚类算法。文献[61]给出了一种以熵为评价准则的聚类算法，通过非参数估计法估计密度函数，再利用类内熵和类间熵进行聚类和确定聚类的数目。这种算法不需要用户输入与聚类有关的参数，能根据数据分布的特性自动获取要聚类的数目，并能发现任意形状和任意大小的聚类。
3.2.2 基于样本数据预处理的聚类
3.2.2.1 核聚类算法（Kernel Clustering）
目前比较经典的聚类算法只能对一些经典分布的样本奏效。它们没有对样本的特征进行优化，而是直接利用样本的特征进行聚类。为了解决这个问题，SCHOLKOPF B 通过把核方法引入到聚类算法中，提出了一种核聚类方法[62]，所谓的核聚类就是把核方法和聚类算法进行耦合，通过把输入空间的数据利用Mercer 核非线性映射到高维特征空间，增加了数据点的线性可分概率，即扩大数据类之间的差异，在高维特征空间达到线性可聚的目的。ZHANG Rong[63]、Girolamim[64]、张莉[65]等人分别发表论文，对核聚类算法进行了进一步讨论。文献[66]把核聚类推广到模糊聚类算法，模糊核聚类算法是FCM的核化版本，一定程度上克服了对数据内在形状分布的依赖，能对不同形状分布数据正确聚类，而且克服了对噪声及野值数据的敏感，增强了算法鲁棒性。但KFCM与K-均值和FCM一样，其聚类性能具有依赖于聚类中心初始值的缺点。为了降低对噪声的敏感程度，文献[67]在映射得到的高维特征空间中采用粗糙聚类的方法，把样本分别划到相应聚类中心的上、下近似中，上、下近似中的样本按照一定的比例来共同决定新的聚类中心，从而进一步丰富了核聚类算法。针对模糊核聚类对初始值敏感、易陷入局部最优的缺点，文献[68]提出了基于粒子群优化的模糊核聚类方法，该方法根据聚类准则设计适应度函数，利用粒子群优化算法对聚类中心进行优化，在迭代优化过程中设计了梯度下降法加快算法的收敛速度，并引入变异机制增强粒子群的多样性。
3.2.2.2 基于概念的聚类（Concept Clustering）
张明卫[69]等提出了一种基于概念的数据聚类模型，该模型从描述数据样本的数据本身出发，首先在预处理后的数据集上提取基本概念，再对这些概念进行概化，形成表示聚类结果的高层概念，最后基于这些高层概念进行样本划分，从而完成整个聚类过程。该模型能够在保证聚类准确性的基础上，很大程度地减少要处理的数据量，提高原算法的可伸缩性。另外，该模型基于概念进行知识的发现与分析，能够提高聚类结果的可解释性，便于与用户交互。
3.2.3 基于样本相似性度量的聚类
3.2.3.1 谱聚类算法（Spectral Clustering）
BUHMANN J M[70]提出了谱聚类算法，该类方法建立在谱图理论基础之上，并利用数据的相似矩阵的特征向量进行聚类，使得算法与数据点的维数无关，而仅与数据点的个数有关，因而统称为谱聚类方法。谱聚类算法是一种基于两点间相似关系的方法，这使得该方法适用于非测度空间。与其他方法相比，该方法不仅思想简单、易于实现、不易陷入局部最优解，而且具有识别非凸分布的聚类能力，非常适合于许多实际应用问题。文献[71]针对谱聚类对分析尺度的选择敏感的问题，给出了一种基于密度敏感的相似性度量，它可以放大不同高密度区域内数据点间距离，同时缩短同一高密度区域内数据点间距离，最终有效描述数据的实际聚类分布；文献[72]
认为在聚类搜索过程中充分利用先验信息会显著提高聚类算法的性能。因此通过讨论数据集本身固有的先验信息——空间一致性先验信息，设计出一种基于密度敏感的距离测度的方法。
3.2.3.2 仿射聚类（Affinity Propagation clustering，AP）
仿射聚类是2007 年Science 报道的一个全新聚类算法[73]，其优势体现在处理类数很多的情况时运算速度快。AP算法通过一个迭代循环不断进行证据的搜集和传递（亦称为消息传递）以产生m个高质量的类代表和对应的聚类，同时聚类的能量函数也得到了最小化，将各数据点分配给最近的类代表所属的类，则找到的m个聚类即是聚类结果。针对仿射聚类中存在的两个问题：（1）很难确定偏向参数取何值能够使算法产生最优的聚类结果；（2）当震荡发生后算法不能自动消除震荡并收敛。为了解决这两个问题，文献[74]提出了自适应仿射传播聚类方法，即自适应扫描偏向参数空间来搜索聚类个数空间以寻找最优聚类结果、自适应调整阻尼因子来消除震荡以及当调整阻尼因子方法失效时的自适应逃离震荡技术，与原算法相比，自适应仿射传播聚类方法性能更优，能够自动消除震荡和寻找最优聚类结果。
3.2.3.3 本体聚类（Ontology clustering）
文献[75]提出了一种基于语义的Ontology 相似性计算方法，该方法不仅考虑概念本身的相似性，还考虑了属性集合和相关概念集合的相似性，通过概念基本相似性极限控制属性集合相似性计算的可能性，通过语义半径控制相关概念集合的范围。将基于语义的Ontology 相似性方法和凝聚层次聚类算法相结合实现了基于语义的Ontology聚类。
3.2.3.4 混合属性聚类（Hybrid data orientation clustering）
在实际数据聚类中，需要处理的数据除数值型属性外，还包括文本、图像等符号型属性的混合型数据。这些算法在进行不同属性的数据处理时，都要进行相关转换，或者全部转换成数值型数据，或者全部转换成符号型数据进行处理，数据聚类精度在进行转换时受到影响。面向混合型数据的聚类方法就是解决这类聚类问题的。CBL（Clustering Based on Lattice）算法是以格论为基础，利用格论中简单元组和超级元组的概念，对数据进行格的划分，以非距离的格关系作为聚类相似度的衡量方法，文献[76]在分析CBL 算法的基础上，利用格论中简单元组及超级元组将对象属性转化为格模型，以对象间格覆盖数来衡量类间相似度，根据高覆盖数高相似度的原则选择聚类中心进行聚类。
3.2.3.5 基于双重距离的聚类（Clustering Based on Dual Distance）
传统聚类方法大都是基于空间位置或非空间属性的相似性来进行聚类，分裂了空间要素固有的二重特性，从而导致了许多实际应用中空间聚类结果难以同时满足空间位置毗邻和非空间属性相近。然而，兼顾两者特性的空间聚类方法又存在算法复杂、结果不确定以及不易扩展等问题。文献[77]通过引入直接可达和相连概念，提出了一种基于双重距离的空间聚类方法，并给出了基于双重距离空间聚类的算法。
3.2.3.6 基于流形距离的迭代优化聚类（Clustering Based on Manifold Distance）
针对传统欧氏距离测度描述复杂结构的数据分布会失效的问题，文献[78]引入能有效反映样本集固有的全局一致性信息的流形距离作为样本间相似度度量测度，并设计了反映类内相似度大、类间相似度小的聚类目标的准则函数，把数据聚类转化成准则函数优化问题，提出了一种迭代优化的聚类算法。
3.2.4 基于样本更新策略的聚类
增量聚类的研究主要有两个思路：（1）将所有的数据进行迭代，即从第一个数据到最后一个数据进行迭代运算，其优点是精度高，不足之处是不能利用前一次聚类的结果，浪费资源。（2）利用上一次聚类的结果，每次将一个数据点划分到已有簇中，即新增的数据点被划入中心离它最近的簇中并将中心移向新增的数据点，优点是不需要每次对所有数据进行重新聚类，缺点是泛化能力弱，监测不出孤立点。
3.2.4.1 数据流增量聚类（Data Stream Clustering）
数据流的聚类问题是典型的增量聚类问题，这些数据具有实时性、连续性、顺序性的动态流式数据。
数据流聚类的基本任务就是对当前数据进行聚类的同时，随着新数据的不断流入，动态调整和更新聚类结果以真实反映数据流的聚类形态。Guha于2000年提出了针对数据流聚类的算法LOCALSEARCH[79]，算法基于分治思想采用一个不断迭代的过程实现在有限空间、时间下对数据流的k-means 聚类。目前主要是把一些传统的聚类算法应用到数据流聚类问题当中来。
3.2.4.2 基于群体智能的增量聚类
研究者从生物的智能行为中受到启发，建立了各种模型，用来求解复杂的科学问题，目前主流的一些群体智能算法及其在增量聚类中的应用情况。
基于遗传算法的增量聚类、基于PSO算法的增量聚类、基于蚁群算法的增量聚类、基于人工免疫系统的增量聚类。
3.2.5 基于样本高维性的聚类
由于高维数据存在的普遍性，使得对高维数据的聚类已经成为近几年研究的一个热点。高维数据聚类的特点是：（1）随着维数增长，聚类的时间和空间复杂度迅速上升从而导致算法的性能下降。（2）高维数据集中存在大量无关的属性，并且在这些不相关的维上十分稀疏，这就使得在所有维中存在簇的可能性几乎为零，所以传统的聚类算法不适合对高维数据进行聚类。（3）距离函数难于定义，聚类操作的基础是数据对象之间相似性的度量，相似度高的对象归为一类。但在高维情况下距离函数失效，因此必须通过重新定义合适的距离函数或相似性度量函数以避开“维度效应”的影响。对于高维数据而言，针对高维数据的稀疏性、空空间和维灾等特征，
目前主要有两个研究思路：一个是通过选维、降维技术去除与数据簇不相关的维，然后再使用聚类算法对转换后的数据进行聚类，这里给出目前最新的投影寻踪法。另一类是子空间聚类，该类算法从数据集中找不同子空间中的簇，这里给出基本算法。
3.2.5.1 投影寻踪聚类（Projection Pursuit Clustering）
多因素聚类问题涉及不同属性的多个指标，是复杂的非线性分类问题。多因素聚类分析是典型的高维数据分析问题，投影寻踪（Projection Pursuit，PP）是一种有效的处理高维数据样本的统计方法。
所谓投影寻踪就是将高维数据向低维空间投影，通过低维投影空间来分析高维数据特征。投影寻踪聚模型就是根据投影寻踪思想建立的一种聚类模型，充分体现了投影寻踪处理高维数据的优势[80]。然而，一方面，投影寻踪聚类模型中的惟一参数——密度窗宽还是依靠经验或试算来确定，缺乏理论依据。
另一方面，对于没有参照标准的聚类问题，投影寻踪聚类模型并不能直接输出明确的聚类结果，只能输出样本的投影特征值序列，文献[81]结合动态聚类思想，建立了投影寻踪动态聚类模型。针对多因素聚类问题的高维复杂性，利用线性投影技术将其转换为关于投影特征值的线性聚类问题；根据动态聚类思想构建新的投影指标，对投影特征值序列进行动态聚类，进而在低维空间实现高维数据样本的聚类分析。
3.2.5.2 子空间聚类（Subspace Clustering）
从查询子空间的方式上，子空间聚类算法可以分成两种主要类别：自上而下的子空间查询方法和自下而上的子空间查询方法。自上而下的子空间查询方法首先在整个维上初始化一系列近似的簇，这时每个维赋予相似的权值。接着每个维相对于不同的类赋予不同的权值，将这些更新的权值使用于下一个循环来重新生成簇。大部分自上而下的方法都需要输入一些参数，例如：簇的数量、子空间大小等。这些参数往往在事先是不知道的，不同的输入参数往往会得到不同结果。自下而上的子空间查询方式使用了关联规则方法中的先验性质，这种类型的查询方法首先将每个维作为单独的项进行考虑，然后依次合并维并判断其子空间的优劣。陈黎飞[82]在高维空间中用概率模型定义来描述投影聚类，提出了基于模型的模糊投影算法发现不同投影子空间中类相互重叠的边缘部分。Song[83]提出了一种基于聚类的特征选择方法。
3.2.6 与其他学科的融合聚类
3.2.6.1 量子聚类算法（Quantum Clustering，QC）
量子力学是一门研究粒子在能量场中分布的科学[84]，聚类是研究样本在尺度空间中的分布情况，可见，量子力学研究的粒子在空间中的分布，同聚类研究样本在尺度空间中的分布情况是等价的。对于样本分布已知时的聚类，对于量子力学而言，描述粒子分布的波函数是已知的，聚类过程相当于：在波函数已知时，采用薛定锷方程求解势能函数，而这个势能函数将最终决定粒子的分布。
3.2.6.2 球壳聚类（Spherical Shell Clustering）
球壳聚类其实是模糊聚类的衍生，模糊聚类的原型由点逐步扩展到线、面、球壳、椭圆壳、矩形壳和多边形壳[59]。其中球壳聚类是其中研究最为活跃的一种。所谓球壳聚类就是样本数据的分布呈球壳状的聚类问题，可以采用球壳作为聚类原型，定义目标函数，并推导出球壳聚类的迭代算法。模糊壳聚类方法依赖于人脑事先给出确定的聚类壳数，并且对原型初始化要求较高，文献[60]提出一种基于量子测量的球壳聚类方法。该算法将聚类样本集分别视为可测量的环境量子系综和刺激量子系综，每个样本视为宏观系综中的一个微观量子叠加态。刺激量子系综依概率在具体微观态上进行塌缩产生刺激引起无意识的注意，并产生球壳面算符。球壳面算符通过对环境量子系综进行有意识的测量并得到平均测量值来验证球壳面的有效性，同时可以得到壳面上的样本集。
3.2.6.3 聚类集成（Clustering Ensemble）
聚类集成[85]是基于集成思想的一种新的聚类算法，利用（经过选择的）多个聚类结果找到一个新的数据（或对象）划分，这个划分在最大程度上共享了所有输入的聚类结果对数据（或对象）集的聚类信息。聚类集成可以分为两个阶段：聚类成员个体生成阶段和对聚类成员个体结果进行集成阶段。
3.2.6.4 基于随机游动的聚类（Random Walk clustering）
随机游动在计算机、物理、生物等领域都有广泛的应用。文献[86]提出一种基于改进的随机游动模型的聚类算法，在算法中，数据集中的样本点根据改进的随机游动模型，生成有权无向图G（V，E，d），其中每个样本点对应图G的一个顶点，并且假设每个顶点为可以在空间中移动的Agent。随后计算每个顶点向其邻集中顶点转移的概率，在随机选定邻集中的一个顶点作为转移方向后，移动一个单位距离。在所有样本点不断随机游动的过程中，同类的样本点就会逐渐聚集到一起，而不同类的样本点相互远离，最后使得聚类自动形成。
