[科普中国]-聚类搜索算法

定义

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

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

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

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

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

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

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

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

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

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

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

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

划分法划分法(partitioning methods)，给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K