大型工件扫描
全局坐标自动拼接 实时扫描预览
XTOM点云预处理精确匹配重叠面自动融合
5.2 聚类法理论基础
聚类[42]（Cluster）：相似文档的分组表达方式。在向量空间模型中，用户可以通过比较查询向量和聚类的中心进行检索，并在聚类中进一步检索以找到最相似的文档。
向量空间模型[43]（Vector Space Model ）：文档和查询的一种表达方式，将它们转换为向量。向量的特征一般是对应文档或查询中处理过的单词（取过词根并且删除了stopword）。这些向量被赋予权重以强调那些与语义相关的词目，这在检索中很有用。在检索中比较查询向量和文档向量，并将最接近的文档作为相关文档返回给用户。
聚类法主要有5种：分层次聚类法（最短距离法）、最简单的聚类方法、最大距离样本、K-平均聚类法（距离平方和最小聚类法）、叠代自组织（ISODATA）聚类法。下面分别讲述这几种方法的基本原理。
5.2.1 层次聚类法
层次聚类[44]，就是把所有的记录按层次进行聚类，可以分为两种：凝聚的方式和分割的方式，取决于聚类层次结构的形成是自顶向下的还是自底向上的。
凝聚的方式：这是一种至底向上的方法，将每一条记录看作一个类，然后根据一些规则将他们聚合成越来越大的类，直到满足一些预先设定的条件。大多数的层次聚类方法属于这一类。
分割的方式：这种自顶向下的方法是一个与凝聚的方式相反的过程，将整个数据库作为一个大的类，然后按照一些规则将这个类分成小的类，直到满足一些预定的条件，例如类的数目到了预定值，最近的两个类之间的最小距离大于设定值。
有N个样本的集合 ，若想要聚成K个类(K事先给定)，凝聚方式层次聚类法的算法流程如下：
（1） k=N, ={ }, i=1,2,...,N；
（2） if k=K then END；
（3） 找到 与 之间的距离d( , )最小的一对；
（4） 和 合成一个类 , 并计算新的 的中心；
（5） 去除 , k=k-1. goto （2）。
其中类间距离d ( , )有如下几种计算方法：
类中心间距：，其中，是属于的样本；
靠得最近的样本：；
离得最远的样本：；
类间平均距离：。
5.2.2 类间聚类法(最简单的聚类方法)
相似性尺度（距离）阈值，不需要事先给定K。其算法流程如下：
（1）有N 个样本， ={ , , ..., }，给定一个阈值T；
（2）任取一个样本，例如 ，把 作为第一个类的中心， = ；
（3）然后依次取 （i=2,3,...,N），计算 与 的距离 ；
（4）若 ≤T，则判定 属于 为中心的那个类；
（5）若 >T，则把 作为新的类中心 ；
（6）然后对剩下的样本 分别计算与 ， 的距离， , ；
（7）若其中较小者≤T，则判定 属于较小的那一类，
否则，就把作为新的一个类的中心；
（8）如此，重复上述步骤，直至对全体样本做完处理。
特点：不需要事先决定类数。适用于类内距离小，类间距离大的情况,如图 5 1。否则结果与取样本的顺序有关，亦与T 相关。
图 5 1最简单聚类法原理图
5.2.3 最大距离样本法
最大距离样本法取尽可能离得远的样本做中心。有N 个样本， ={ , , ..., }，其算法流程如下：
（1） 任取一个样本，例如 ，把 作为第一个类的中心， = ；
（2） 从集合 中找出到 距离最大的样本作为 ；
（3） 对 中剩余样本 ，分别计算到 ， 的距离。令其中较小的那个为 ；
（4） 计算， ，若其值大于某一计算值或给定阈值，则取此 为新的类中心。计算值可取：大于等于 和 间距离的n/m倍（0.5 n/m<1）；
（5） 重复上述步骤，直到再也找不到符合条件的新的类中心；
（6） 把剩余样本分配到离它最近的那个中心所属的类。
5.2.4 k-means聚类
k-means聚类[45-47]，就是把大量的n维数据样本聚集成 个类，使同一类中样本的相似性最大，而不同类中样本的相似性最小。聚类算法是在预先不知道目标数据库到底有多少类的情况下,希望将所有的纪录组成不同的类或者说聚类，并且使得在这种分类情况下，以某种度量为标准的相似性，在同一聚类之间最小化，而在不同聚类之间最大化。如图 5 2，其算法流程如下：
（1） 假设要聚成k个类，首先确定k个类的初始中心： , ,…, ；
（2） 在第k次迭代中，样本集{Z}用如下方法分类：对所有i=1,2,…,K， ，若 ，则 ；
（3） 令由（2）得到的 的新的类中心为 ，令公式(5-1）最小，j=1,2,…,k，则有公式（52）， 的样本；
(5-1)
(5-2)
（4）对于所有的j=1,2,…,k，若 ，则终止。否则转到（2）。
初始k值的选择：最初选择哪些样本作为中心，将对迭代产生影响，所以需要多次迭代，多次修正。
图 5 2 k-means聚类原理图
5.2.5 迭代自组织（ISODATA）聚类法
迭代自组织聚类法[48]（Iterative Self-Organizing Data Analysis Technology Algorithm），基本思想是给定一些初始参数，然后不停的迭代，直至满足目的为止。其算法流程如下：
（1）首先给定一些参数：K ：期望分类个数的大致范围；
：一个类内的最少样本数；
：关于类内分散程度的参数；
：关于类间距离（最小）的参数；
L ：每次叠代允许合并的类数；
I ：允许叠代的最大次数；
（2）适当选取类中心{ , , ..., }， ：类数；
（3）分配样本。如果有{i=1,2,..., } ，
则， j =1,2,..., ；
（4）如果 类样本数 ，则取消 类。 , goto （3）；
（5）重新计算各类中心： ；
（6）计算类 内平均距离： ；
（7）对全体样本求类内距离平均值： ；
（8）[1]如果叠代次数≥I，则转向（12)（合并）；
[2]若 ，则转向（9）（分裂）；
[3]若偶数次叠代或 ，则转向（12）（合并）；
（9）计算各类中各分量的标准差： 为Z ∈ 的第i 个分量， 为 的第i 个分量， 为第j类第i个分量标准差；
（10）找到各类的标准差最大的分量： ；
（11）分裂：条件1: 且 且 ，
条件2： 且 ，
如满足两条件之一则分裂 ；
[1]建立 和 ，两个新的类中心 ,其中 和 是沿着 轴，在原来的 位置上，分别加上和减去一个数k （ ），k是经验值；
[2]goto（3）(分配样本)；
（12）计算所有各类中心的相互距离：；
（13）对于比 小的 ，按从小到大排队，假定为： ；
（14）按 的顺序，把 对应的 和 合并， ；
计算时的，，若至少其中一个是在本次迭代中合并取得类中心，则越过此项；
(15) 若叠代次数≥I，或参数无改变，则终止，
否则goto (3)，需要时可返回（1）修改参数。
