聚类分析（Cluster analysis，亦称为群集分析）是对于统计数据分析的一门技术，在许多领域受到广泛套用，包括机器学习，数据挖掘，模式识别，图像分析以及生物信息。聚类分析是根据事物本身的特性研究个体的一种方法，目的在于将相似的事物归类。它的原则是同一类中的个体有较大的相似性，不同类的个体差异性很大。这种方法有三个特徵：

（1）适用于没有先验知识的分类。如果没有这些事先的经验或一些国际标準、国内标準、行业标準，分类便会显得随意和主观。这时只要设定比较完善的分类变数，就可以通过聚类分析法得到较为科学合理的类别；

（2）可以处理多个变数决定的分类。例如，要根据消费者购买量的大小进行分类比较容易，但如果在进行数据挖掘时，要求根据消费者的购买量、家庭收入、家庭支出、年龄等多个指标进行分类通常比较複杂，而聚类分析法可以解决这类问题；

（3）聚类分析法是一种探索性分析方法，能够分析事物的内在特点和规律，并根据相似性原则对事物进行分组，是数据挖掘中常用的一种技术。

搜寻是人工智慧的基本技术之一，指计算机找出从初始状态转化到目标状态的途径，根据给定条件求解一个问题正确答案的过程。一个有趣的例子是：3个驯兽员带着3只熊和1条船在左岸(初始状态)，要把人、熊、船都渡到右岸去(目标状态)，给定条件是人或熊都会划船、但船每次最多只能装载或两人或两熊或一人一熊、而且无论左岸或右岸都不允许出现熊多于人的情况(否则熊会伤人)，为顺利到达右岸而寻找正确解决这个问题的可靠方法的过程就叫搜寻。

搜寻要讲究策略方法，一个最佳搜寻的标準是：

(1)在问题有解的场合下能保证成功；

(2)必须花的搜寻工作量最少；

(3) 找到的途径是最短的 (捷径)；

(4)沿着找到的途径进行实际操作的费用最小。

针对一个实际分类搜寻问题时，一个好的聚类搜寻算法设计一般要考虑聚类的特点以及搜寻的要求。儘量使算法性能在各个方面达到最佳或者最佳。

很难对聚类方法提出一个简洁的分类，因为这些类别可能重叠，从而使得一种方法具有几类的特徵，儘管如此，对于各种不同的聚类方法提供一个相对有组织的描述依然是有用的，为聚类分析计算方法主要有如下几种：

划分法(partitioning methods)，给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K<N。而且这K个分组满足下列条件：

（1） 每一个分组至少包含一个数据纪录；

（2）每一个数据纪录属于且仅属于一个分组（注意：这个要求在某些模糊聚类算法中可以放宽）；

对于给定的K，算法首先给出一个初始的分组方法，以后通过反覆叠代的方法改变分组，使得每一次改进之后的分组方案都较前一次好，而所谓好的标準就是：同一分组中的记录越近越好，而不同分组中的纪录越远越好。

大部分划分方法是基于距离的。给定要构建的分区数k，划分方法首先创建一个初始化划分。然后，它採用一种叠代的重定位技术，通过把对象从一个组移动到另一个组来进行划分。一个好的划分的一般準备是：同一个簇中的对象儘可能相互接近或相关，而不同的簇中的对象儘可能远离或不同。还有许多评判划分质量的其他準则。传统的划分方法可以扩展到子空间聚类，而不是搜寻整个数据空间。当存在很多属性并且数据稀疏时，这是有用的。为了达到全局最优，基于划分的聚类可能需要穷举所有可能的划分，计算量极大。实际上，大多数套用都採用了流行的启发式方法，如k-均值和k-中心算法，渐近的提高聚类质量，逼近局部最优解。这些启发式聚类方法很适合发现中小规模的资料库中小规模的资料库中的球状簇。为了发现具有複杂形状的簇和对超大型数据集进行聚类，需要进一步扩展基于划分的方法。[1]

使用这个基本思想的算法有：K-MEANS算法、K-MEDOIDS算法、CLARANS算法；

层次法(hierarchical methods)，这种方法对给定的数据集进行层次似的分解，直到某种条件满足为止。具体又可分为“自底向上”和“自顶向下”两种方案。

例如，在“自底向上”方案中，初始时每一个数据纪录都组成一个单独的组，在接下来的叠代中，它把那些相互邻近的组合併成一个组，直到所有的记录组成一个分组或者某个条件满足为止。

层次聚类方法可以是基于距离的或基于密度或连通性的。层次聚类方法的一些扩展也考虑了子空间聚类。层次方法的缺陷在于，一旦一个步骤（合併或分裂）完成，它就不能被撤销。这个严格规定是有用的，因为不用担心不同选择的组合数目，它将产生较小的计算开销。然而这种技术不能更正错误的决定。已经提出了一些提高层次聚类质量的方法。[1]

代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等；

基于密度的方法(density-based methods)，基于密度的方法与其它方法的一个根本区别是：它不是基于各种各样的距离的，而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。

这个方法的指导思想就是，只要一个区域中的点的密度大过某个阈值，就把它加到与之相近的聚类中去。

代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等；

图论聚类方法解决的第一步是建立与问题相适应的图，图的节点对应于被分析数据的最小单元，图的边（或弧）对应于最小处理单元数据之间的相似性度量。因此，每一个最小处理单元数据之间都会有一个度量表达，这就确保了数据的局部特性比较易于处理。图论聚类法是以样本数据的局域连线特徵作为聚类的主要信息源，因而其主要优点是易于处理局部数据的特性。

基于格线的方法(grid-based methods)，这种方法首先将数据空间划分成为有限个单元（cell）的格线结构,所有的处理都是以单个的单元为对象的。这幺处理的一个突出的优点就是处理速度很快，通常这是与目标资料库中记录的个数无关的，它只与把数据空间分为多少个单元有关。

代表算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法；

基于模型的方法(model-based methods)，基于模型的方法给每一个聚类假定一个模型，然后去寻找能够很好的满足这个模型的数据集。这样一个模型可能是数据点在空间中的密度分布函式或者其它。它的一个潜在的假定就是：目标数据集是由一系列的机率分布所决定的。

数据聚类在工程设计、计算机网路及信息处理、机械故障诊断、雷达目标识别、资料库建立、人工智慧等许多领域具有广泛的套用前景。通过设计有效的聚类算法，通过计算机软体处理，对数据和信息进行聚类处理再作之后的研究和处理，既是信号与信息处理的关键一步，也是提高效率，减少运算开支的根本途径。多源语义特徵分层资料库是构建数位化信息系统的基础，多源语义特徵分层资料库将大量网路计算资源、存储资源与软体资源等多源信息资源进行多层次的虚拟化和抽象，统一调度，以网路服务的方式向用户提供按需服务的IT服务模式，多源语义特徵分层资料库进行大数据聚类，实现数据的分类识别。

多源语义特徵分层资料库中由于路由冲突，在链路负载较大的情况下，不能有效实现对大数据语义特徵的并行搜寻。提出一种基于增广链同态解析的链路分流方法避免路由冲突，实现增广链修复下大数据并行搜寻聚类。构建大数据聚类的语义相似度融合模型，基于跨层链路分流算法实现增广链路分流，进行语义本体模型构建，选择採用高阶贝塞尔函式累积量作为增广链修复检验统计量，确定节点数据包的置信度，确立置信区间，在进行缓冲区溢出修复时，进行功率谱幅度特徵提取，实现大数据的并行搜寻聚类，进行语义本体模型构建，为离群点新建一个簇，依次对每个文档的主题词集进行处理，将每个主题词自动添加入形式背景的属性集中，採用并行搜寻算法实现对语义大数据的最佳化聚类算法改进。仿真实验进行了性能验证，研究结果表明，採用本文算法能有效提高大数据聚类性能，聚类的切合度较好，误分率较低。