层次聚类算法层次聚类算法通过计算两类数据点间的相似性对所有数据点中最为相似的两个数据点进行组合并反复迭代这一过程。简单的说层次聚类的合并算法是通过计算每一个类别的数据点与所有数据点之间的距离来确定它们之间的相似性距离越小相似度越高。并将距离最近的两个数据点或类别进行组合生成聚类树。假设有N个待聚类的样本对于层次聚类来说基本步骤就是1初始化把每个样本归为一类计算每两个类之间的距离也就是样本与样本之间的相似度2寻找各个类之间最近的两个类把他们归为一类这样类的总数就少了一个3重新计算新生成的这个类与各个旧类之间的相似度4重复2和3直到所有样本点都归为一类结束。合成聚类整个聚类过程其实是建立了一棵树在建立的过程中可以通过在第二步上设置一个阈值当最近的两个类的距离大于这个阈值则认为迭代可以终止。另外关键的一步就是第三步如何判断两个类之间的相似度有不少种方法。距离计算方法两个点点集的相似通过欧式距离计算得出数据点与点集间的距离计算方式将数据点B与数据点C进行组合后重新计算各类别数据点间的距离矩阵。数据点间的距离计算方式与之前的方法一样。这里需要说明的是点集(B,C)与其他数据点间的计算方法。当我们计算(B,C)到A的距离时需要分别计算B到A和C到A的距离均值。数据点与点集距离计算公式两个组合数据点间的距离计算方式计算两个组合数据点间距离的方法有三种分别为Single LinkageComplete Linkage和Average Linkage。在开始计算之前我们先来介绍下这三种计算方法以及各自的优缺点。Single LinkageSingle Linkage的计算方法是将两个数据点集中距离最近的两个数据点间的距离作为这两个点集的距离。这种方法容易受到极端值的影响。两个很不相似的点集可能由于其中的某个极端的数据点距离较近而组合在一起。Complete LinkageComplete Linkage的计算方法与Single Linkage相反将两个点集中距离最远的两个数据点间的距离作为这两个点集的距离。Complete Linkage的问题也与Single Linkage相反两个相似的组合数据点可能由于其中的极端值距离较远而无法组合在一起。Average LinkageAverage Linkage的计算方法是计算两个点集中的每个数据点与其他所有数据点的距离。将所有距离的均值作为两个点集间的距离。这种方法计算量比较大但结果比前两种方法更合理。这种聚类的方法描述起来比较简单但是计算复杂度比较高为了寻找距离最近/远和均值都需要对所有的距离计算个遍需要用到双重循环每次迭代都只能合并两个子类这是非常慢的。两个点点集的相似通过jaccard距离计算得出可以将点集按照一定的变换方式将原始的数据映射的{01}或者{012}这些空间中以{01}空间为例所有的点集中包含的数据只有0,1jaccard distance定义如下主要就是计算两个点集的相似性的如果两个点集完全独立那么J距离为1如果两个点集非常相近那么J距离趋近于0。然后我们就可以直接通过最后的J距离判断这两个点集是否进行融合。值得一提的是因为这里映射的空间是{0,1}空间我们知道在计算中的最原始的计数是二进制如果直接进行0和1的比较操作速度是非常快的。Brief描述子的提出也就是基于这方面的考虑。部分参考http://www.jianshu.com/p/785bb19386db但该链接文章中有部分错误。参考文献[1]Toldo R, Fusiello A. Robust Multiple Structures Estimation with J-Linkage[C]// European Conference on Computer Vision. Springer-Verlag, 2008:537-547.