[科普中国]-无监督量子聚类算法

无监督量子聚类算法是一种自动学习方式，并不需要对学习样本做类别标记。许多领域，包括数据分析，数据挖掘，图像分割，统计学，机器学习都使用了聚类算法

介绍聚类(clustering)是一个将数据集划分为若干组或类的过程，并使得同一组内的数据对象具有较高的相似度，而不同组中的数据对象是不相似的，根据学习的不同可将聚类算法分为两大类：有监督聚类和无监督聚类。有监督聚类必须对所有的学习样本做类别标记，通常需要大量的学习样本。

算法层次聚类层次聚类是一种最常使用的非监督聚类方法。它将一组元素的距离矩阵转化成系统树状的层次分类。它的定义：对于给定的刀个样本，首先将有所有样本分成n类，每类正好包含有一个样本；其次将样本分成n-1类，接着分成n-2类，直到所有的样本都被分成一类为止。我们称聚类数目C=n-k+1对应层次结构的第k层，对层次结构的任意一层及其该层中的任意两个样本，如果它们在该层中属于同一个类，而且在更高的层次一直属于同一类，那么这样的序列则称为“层次聚类”。层次聚类可以分成两种类型：自下而上的分类和自上而下的分类。

(1)自下而上聚合层次聚类方法。这种自下而上策略就是最初将每个对象(自身)作为一个聚类；然后将这些原子聚类进行聚合以构造越来越大的聚类，直到所有对象均聚合为一个聚类，或满足一定终止条件为止。大多数层次聚类方法都属于这类方法，但它们在聚类内部对象间距离定义描述方面有所不同。

(2)自上而下分解层次聚类方法。这种自上而下策略的做法与自下而上策略做法相反。它首先将所有对象看成一个聚类的内容；将其不断分解以使其变成越来越小但个数越来越多的小聚类，直到所有对象均独自构成一个聚类，或满足一定终止条件(如：一个聚类数阂值，或两个最近聚类的最短距离阈值)为止。

层次聚类方法的优点在于使用者不必设定参数，并且结果是确定性的。但经常会遇到如何选择合并或分解点的问题。这种决策非常关键，因为在对一组对象进行合并或分解之后，聚类进程将在此基础上继续进行合并或分解，这样就既无法回到先前的(聚类)状态；也不能进行聚类间的对象交换。因此如果所做出的合并或分解决策(在某一点上)不合适，就会导致聚类结果质量较差。此外由于在作出合并或分解决策前需要对许多对象或聚类进行分析评估，因此使得该类方法的可扩展性也较差。

划分聚类划分法是最基本的聚类方法之一。给定一个包含刀个数据对象的数据集，一个划分方法构建数据后的k个划分，每个划分表示一个聚簇，并且k≤n。同时满足如下要求：(1)每个组至少包含一个对象；

(2)每个对象必须属于且只属于一个组。到初始的k个划分集合之后，它采用迭代重定位技术，试图通过将对象从一个簇移到另一个簇来改进划分的质量。一个好的划分规则是：在同一个类中的对象之间尽可能“接近"或相关，而不同类中的对象之间尽可能“远离"或不同。有代表性的划分方法包括K-means、K-medoidsLARA (Clustering CLARge Application)、CLARANS(ClusteringLarge Application based upon RANdomized Search)、 MFCM、EM(ExpectationMaximization)等。

这些方法在处理数据类是球状，大小接近且类与类之间明显分开的数据可以达到很好的分类效果。但对于数据类是非球状，或者大小相差大的类它们却不能胜任。这几种划分方法尽管在中心的初始选择、相异度的计算和计算聚类平均值的策略上各有不同，但有一点是共同的，即都以平方误差(简称方差)作为准则函数，都试着找出使得方差最小的k个划分。

C均值聚类算法K均值聚类，即众所周知的c均值聚类，是由J．B．Macoueen提出的，是将所有样本分成c组样本群聚，并能找到这些群聚中心点位置的技术。

其它划分聚类算法K-modes通过用模来替换聚类均值、采用新差异性计算方法来处理符号量，以及利用基于频率对各聚类模进行更新方法，从而将K-means算法的应用范围从数值量扩展到符号量。将K．means算法和K-modes算法结合到一起，就可以对采用数值量和符号量描述对象进行聚类分析，从而构成了K．prototypes算法。而EM(期望最大化)算法又从多个方面对K．means算法进行了扩展。其中包括：它根据描述聚类所属程度的概率权值，将每个对象归类为一个聚类，不是将一个对象仅归类为一个聚类(所拥有)；也就是说在各聚类之间的边界并不是非常严格。因此可以根据概率权值计算相应的聚类均值。此外通过识别数据中所存在的三种类型区域，即可压缩区域、必须存入内存区域和可以丢弃区域，来改善K．means算法的可扩展性。若一个对象归属某个聚类的隶属值是不确定的，那它就是可丢弃的；若一个对象不是可丢弃的且属于一个更紧密的子聚类，那么它就是可压缩的。利用一个被称为是聚类特征的数据结构来对所压缩或所丢弃数据进行综合(summarize)，若一个对象既不是可以丢弃的，也不是可以压缩的，那它就需要保持在内存里(在聚类过程中)。为实现可扩展性，循环聚类算法仅需对可压缩和可丢弃数据的聚类特征以及须保持在内存中的对象进行分析处理即可。CLARNS算法(随机搜索聚类算法)。划分方法中最早提出的一些算法对小数据集非常有效，但是对大的数据集没有良好的处理能力。PAM、CLERA是基于K均值的算法，能处理较大的数据集1。

CLARNS是CLARA算法的一个改进算法。CLAR A算法不考虑整个数据集，而是随机的选择实际数据集中的一小部分作为样本，然后用PAM方法从样本中选出中心点，而选出的中心点很可能和整个数据集合中选出的相似。重复以上方法，最后返回最好的聚类结果。CLAR_NS不像CLARA那样每个阶段选取一个固定样本，它在搜索的每一步随机的选取一个样本，在替换了一个中心点后得到的聚类结果被称为当前聚类结果的邻居，搜索的邻居点数目由用户定义一个限制参数。如果找到一个比当前结果更好的邻居，则把中心点移到该邻居节点上，否则把该点作为局部最小量。然后，再随机选择一个点来寻找另一个局部最小量。算法的时间复杂度约是O(nz)，n是对象的数目。

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所