5 聚类之层次聚类基于划分的聚类（k、层次聚类1、层次聚类的原理及分类1）层次法（Hierarchicalmethods ）先计算样本之间的距离。
每次将距离最近的点合并到同一个类。
然后，再计算类与类之间的距离，将距离最近的类合并为一个大类。
不停的合并，直到合成了一个类。
其中类与类的距离的计算方法有：最短距离法，最长距离法，中间距离法，类平均法等。
比如最短距离法，将类与类的距离定义为类与类之间样本的最短距离。
层次聚类算法根据层次分解的顺序分为：自下底向上和自上向下，即凝聚的层次聚类算法和分裂的层次聚类算法agglomerative 和divisive ），也可以理解为自下而上法bottom-up ）和自上而下法（top-down ）。
自下而上法就是开始每个个体（object ）都是一个类，然后根据linkage 寻找同类，最后形成一个“类” 。
自上而下法就是反过来，开始所有个体都属于一个“类”，然后根据linkage 排除异己，劣之分，只是在实际应用的时候要根据数据特点以及你想要的“类”的个数，来考虑是自上而下更快还是自下而上更快。
最后每个个体都成为一个“类” 。
这两种路方法没有孰优孰至于根据Linkage 判断“类”的方法就是最短距离法、最长距离法、中间距离法、类平均法等等（其中类平均法往往被认为是最常用也最好用的方法，一方面因为其良好的单调性，另一方面因为其空间扩张/浓缩的程度适中）。
为弥补分解与合并的不足，层次合并经常要与其它聚类方法相结合，如循环定位。
2)Hierarchical methods 中比较新的算法有BIRCH( BalancedIterative Reducingand Clustering Using Hierarchies 利用层次方法的平衡迭代规约和聚类）主要是在数据量很大的时候使用，而且数据类型是numerical 。
首先利用树的结构对对象集进行划分，然后再利用其它聚类方法对这些聚类进行优化；ROCK ( AHierarchical ClusteringAlgorithm for Categorical Attributes )主要用在categorical 的数据类型上；Chameleon(A HierarchicalClustering AlgorithmUsing Dynamic Modeling )里用到的linkage 是kNN (k-nearest-neighbor)算法，并以此构建一个graph，Chameleon 的聚类效果被认为非常强大，比BIRCH 好用，但运算复杂度很高，0（22）。
2、层次聚类的流程凝聚型层次聚类的策略是先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。
绝大多数层次聚类属于凝聚型层次聚类， 它们只是在簇间相似度的定义上有所不同。
里给出采用最小距离的凝聚层次聚类算法流程：(1) 将每个对象看作一类，计算两两之间的最小距离；(2) 将距离最小的两个类合并成一个新类；(3) 重新计算新类与所有类之间的距离；(4) 重复 (2)、(3) ，直到所有类最后合并成一类。
聚类的效果如下图，黑色是噪音点：另外我们可以看出凝聚部极小问题或是很难选择初始点的问题。
合并的操作往往是 最终的，一旦合并两个簇之后就不会撤销。
当然其计算存储 的代价是昂贵的。
3、层次聚类的优缺点类成其它形状 缺点： 1，计算复杂度太高； 2，奇异值也能产生很大影响； 3，算法很可能聚类成链状 r 语言中使用 hclust(d,method = "complete", members=NULL) ：进行层次聚类。
d 为距离矩阵； method表示类的合并方法， single 最短距离法， complete的层次聚类并没有类似基本K 均值的全局目标函数， 没有局优点： 1，距离和规则的相似度容易定义，限制少；2，不需 要预先制定聚类数； 3，可以发现类的层次关系；4，可以聚最长距离法，median 中间距离法，mcquitty 相似法，average 类平均法，centroid重心法，ward离差平方和法；members为NULL 或d长度的矢量。
、划分聚类法k-means基于划分的方法(Partition-based methods):其原理简单来说就是，想象你有一堆散点需要聚类，想要的聚类效果就是“类内的点都足够近，类间的点都足够远” 。
首先你要确定这堆散点最后聚成几类，然后挑选几个点作为初始中心点，再然后依据预先定好的启发式算法( heuristicalgorithms )给数据点做迭代重置( iterativerelocation )，直到最后到达“类内的点都足够近，类间的点都足够远”的目标效果。
Partition-based methods 聚类多适用于中等体量的数据集，但数据集越大，越有可能陷入局部最小。
我们也不知道“中等”到底有多“中” ，所以不妨理解成，1、Kmeans 算法的原理k-means 算法以k 为参数，把n 个对象分成k 个簇，使簇内具有较高的相似度，而簇间的相似度较低。
k-means 算法的处理过程如下:首先，随机地选择k 个对象，每个对象初始地代表了一个簇的平均值或中心，即选择K 个初始质心;对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇;然后重新计算每个簇的平均值。
这个过程不断重复，直到准则函数收敛，直到质心不发生明显的变化。
通常，采用平方误差准则，误差的平方和SSE 作为全局的目标函数， 即 最小化每个点到最近质心的欧几里得距离的平方和。
此时， 簇的质心就是该簇内所有数据点的平均值。
选择 K 个点作为初始质心repeat将每个点指派到最近的质心，形成 K 个簇 重新计算每个簇的质心 until 簇不发生变化或达到最大迭代次数O(tKmn),其中，t 为迭代次数，K 为簇的数目，从上图中，我们可以看到， A, B, C, D, E 是五个在图中点 而灰色的点是我们的种子点，也就是我们用来找点群的点。
有两个种子点，所以 K=2 。
然后， K-Means 的算法如下：① 随机在图中取 K (这里K=2 )个种子点。
② 然后对图中的所有点求到这 K 个种子点的距离，假如点Pi 离种子点Si 最近，那么Pi 属于Si 点群。
(我们可以看到A,B 属于上面的种子点， C,D,E 属于下面中部的种子点) ③接下来，我们要移动种子点到属于他的“点群”的中心。
见图上的第三步)时间复杂度： m 为记录数， n 为维数空间复杂度：O((m+K)n) ，其中， K 为簇的数目， m 为记录 数， n 为维数 K-Means 算法的详细过程④然后重复第 2)和第 3)步，直到，种子点没有移动(我们可以看到图中的第四步上面的种子点聚合了 A,B,C ，下面 的种子点聚合了 D ， E )。
聚类的效果如下图，折线是历次循环时 3 个簇的质心的更新步骤及上面的聚类效果可以发现，该聚类算法将所有数据点 都进行了指派，不识别噪音点。
另外选择适当的初试质心是 基本 K 均值过程的关键。
2、 k 均值的优缺点及分类优点： 1，简单，易于理解和实现；2，时间复杂度低缺点： 1) kmeans 要手工输入类数目，对初始值的设置很敏感；所 以有了 k-means++、intelligent k-means 、genetic k-means ；2) k-means 对噪声和离群值非常敏感，所以有了 和 k-medians ； 3) k-means 只用于 numerical 类型数据， 不适用于 categorical 类型数据，所以 k-modes ；4) k-means 不能解决非凸(non-convex)数据，所以有了 kernel k-means 。
5) k-means 主要发现圆形或者球形簇， 不能识别非球形的簇。
3、 k-means 与 DBSCAN 的区别轨迹，黑点是初始质心：我们查看基本 K 均值算法实现k-medoidsk-means 聚类算法的初始点选择不稳定，是随机选取的，这就引起聚类结果的不稳定。
k-means属于动态聚类，往往聚出来的类有点圆形或者椭圆形。
kmeans对于圆形区域聚类效果较好，dbscan 基于密度，对于集中区域效果较好。
对于不规则形状，kmeans完全无法用，dbscan可以起到很好的效果。
4、k-means 注意问题1) K 如何确定K 是用户kmenas 算法首先选择K 个初始质心，其中指定的参数，即所期望的簇的个数。
这样做的前提是我们已经知道数据集中包含多少个簇，但很多情况下，我们并不知道数据的分布情况，实际上聚类就是我们发现数据分布的种手段。
如何有效的确定K 值，这里大致提供几种方法：①与层次聚类结合[2]经常会产生较好的聚类结果的一个有趣策略是，首先采用层次凝聚算法决定结果粗的数目，并找到一个初始聚类，然后用迭代重定位来改进该聚类。
②稳定性方法[3]稳定性方法对一个数据集进行2 次重采样产生2 个数据子集，再用相同的聚类算法对2 个数据子集进行聚类，产生2 个具有k 个聚类的聚类结果，计算2 个聚类结果的相似度的分布情况。
2个聚类结果具有高的相似度说明k个聚类反映了稳定的聚类结构，其相似度可以用来估计聚类个数。
采用次方法试探多个k，找到合适的k值。
③系统演化方法[3]系统演化方法将一个数据集视为伪热力学系统，当数据集被划分为K 个聚类时称系统处于状态K 。
系统由初始状态K=1 出发，经过分裂过程和合并过程，系统将演化到它的稳定平衡状态Ki ，所对应的聚类结构决定了最优类数系统演化方法能提供关Ki。
于所有聚类之间的相对边界距离或可分程度，适用于明显分离的聚类结构和轻微重叠的聚类结构。
④使用canopy 算法进行初始划分[4]基于CanopyMethod 的聚类算法将聚类过程分为两个阶段Stagel、聚类最耗费计算的地方是计算对象相似性的时候，CanopyMethod 在第一阶段选择简单、计算代价较低的方法计算对象相似性，将相似的对象放在一个子集中，这个子集被叫做Canopy，通过一系列计算得到若干Canopy，Canopy 之间可以是重叠的，但不会存在某个对象不属于任何Canopy 的情况，可以把这一阶段看做数据预处理；Stage2、在各个Canopy内使用传统的聚类方法（如K-means），不属于同一Canopy的对象之间不进行相似性计算。
从这个方法起码可以看出两点好处：首先，Canopy 不要太大且Canopy 之间重叠的不要太多的话会大大减少后续需要计算相似性的对象的个数；其次，类似于K-means 这样的聚类方法是需要人为指出K 的值的，通过Stagel得到的Canopy个数完全可以作为这个K 值，一定程度上减少了选择K 的盲目性。