K_Means 初始点选取
KMeans算法本身思想比较简单，但是合理的确定K值和K个初始类簇中心点对于聚类效果的好坏有很大的影响。
1. 确定K个初始类簇中心点
最简单的确定初始类簇中心点的方法是随机选择K个点作为初始的类簇中心点，但是该方法在有些情况下的效果较差，如下(下图中的数据是用五个二元正态高斯分布生成的，颜色代表聚类效果)：
《大数据》一书中提到K个初始类簇点的选取还有两种方法：1)选择彼此距离尽可能远的K个点 2)先对数据用层次聚类算法或者Canopy算法进行聚类，得到K个簇之后，从每个类簇中选择一个点，该点可以是该类簇的中心点，或者是距离类簇中心点最近的那个点。
1) 选择批次距离尽可能远的K个点
首先随机选择一个点作为第一个初始类簇中心点，然后选择距离该点最远的那个点作为第二个初始类簇中心点，然后再选择距离前两个点的最近距离最大的点作为第三个初始类簇的中心点，以此类推，直至选出K个初始类簇中心点。
该方法经过我测试效果很好，用该方法确定初始类簇点之后运行KMeans得到的结果全部都能完美区分五个类簇：
2) 选用层次聚类或者Canopy算法进行初始聚类，然后利用这些类簇的中心点作为
KMeans算法初始类簇中心点。
常用的层次聚类算法有BIRCH和ROCK，在此不作介绍，下面简单介绍一下Canopy算法，主要摘自Mahout的Wiki：
首先定义两个距离T1和T2，T1>T2.从初始的点的集合S中随机移除一个点P，然后对于还在S中的每个点I，计算该点I与点P的距离，如果距离小于T1，则将点I加入到点P所代表的Canopy中，如果距离小于T2，则将点I从集合S中移除，并将点I加入到点P所代表的Canopy中。迭代完一次之后，重新从集合S中随机选择一个点作为新的点P，然后重复执行以上步骤。
Canopy算法执行完毕后会得到很多Canopy，可以认为每个Canopy都是一个Cluster，与KMeans等硬划分算法不同，Canopy的聚类结果中每个点有可能属于多个Canopy。我们可以选择距离每个Canopy的中心点最近的那个数据点，或者直接选择每个Canopy的中心点作为KMeans的初始K个类簇中心点。
K-d tree总结一
k-d树（k-dimensional树的简称），是一种分割k维数据空间的数据结构。主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。
应用背景
SIFT算法中做特征点匹配的时候就会利用到k-d树。而特征点匹配实际上就是一个通过距离函数在高维矢量之间进行相似性检索的问题。针对如何快速而准确地找到查询点的
近邻，现在提出了很多高维空间索引结构和近似查询的算法，k-d树就是其中一种。
索引结构中相似性查询有两种基本的方式：一种是范围查询（range searches），另一种是K近邻查询（K-neighbor searches）。范围查询就是给定查询点和查询距离的阈值，从数据集中找出所有与查询点距离小于阈值的数据；K近邻查询是给定查询点及正整数K，从数据集中找到距离查询点最近的K个数据，当K=1时，就是最近邻查询（nearest neighbor searches）。
特征匹配算子大致可以分为两类。一类是线性扫描法，即将数据集中的点与查询点逐一进行距离比较，也就是穷举，缺点很明显，就是没有利用数据集本身蕴含的任何结构信息，搜索效率较低，第二类是建立数据索引，然后再进行快速匹配。因为实际数据一般都会呈现出簇状的聚类形态，通过设计有效的索引结构可以大大加快检索的速度。索引树属于第二类，其基本思想就是对搜索空间进行层次划分。根据划分的空间是否有混叠可以分为Clipping和Overlapping两种。前者划分空间没有重叠，其代表就是k-d树；后者划分空间相互有交叠，其代表为R树。（这里只介绍k-d树）
1.实例
先以一个简单直观的实例来介绍k-d树算法。假设有6个二维数据点（{2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，数据点位于二维空间内（如图2中黑点所示）。k-d树算法就是要确定图2中这些分割空间的分割线（多维空间即为分割平面，一般为超平面）。下面就要通过一步步展示k-d树是如何确定这些分割线的。
k-d树算法可以分为两大部分，一部分是有关k-d树本身这种数据结构建立的算法，另一部分是在建立的k-d树上如何进行最邻近查找的算法。
2.构造kd树
kd树是一种对k维空间中的实例点进行存储以便对其进行快速搜索的树形数据结构。kd树是二叉树，表示对k维空间的一个划分。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间进行切分，构成一系列的k维超矩形区域。kd树的每一个节点对应于一个k维超矩形区域。k-d树是一个二叉树，每个节点表示一个空间范围。下表给出的是k-d树每个节点中主要包含的数据结构。
从上面对k-d树节点的数据类型的描述可以看出构建k-d树是一个逐级展开的递归过程。下面给出的是构建k-d树的伪码。
以上述举的实例来看，过程如下：
由于此例简单，数据维度只有2维，所以可以简单地给x，y两个方向轴编号为0,1，也即split={0,1}。
（1）确定split域的首先该取的值。分别计算x，y方向上数据的方差得知x方向上的方差最大，所以split域值首先取0，也就是x轴方向；
（ 2）确定Node-data的域值。根据x轴方向的值2,5,9,4,8,7排序选出中值为7，所以Node-data = （7,2）。这样，该节点的分割超平面就是通过（7,2）并垂直于split = 0（x轴）的直线x = 7；
（3）确定左子空间和右子空间。分割超平面x = 7将整个空间分为两部分，如下图所示。x <= 7的部分为左子空间，包含3个节点{（2,3），（5,4），（4,7）}；另一部分为右子空间，包含2个节点{（9,6），（8,1）}。
如算法所述，k-d树的构建是一个递归的过程。然后对左子空间和右子空间内的数据重复根节点的过程就可以得到下一级子节点（5,4）和（9,6）（也就是左右子空间的'根'节点），同时将空间和数据集进一步细分。如此反复直到空间中只包含一个数据点，如下图所示。最后生成的k-d树如下图所示。
3.搜索kd树
在k-d树中进行数据的查找也是特征匹配的重要环节，其目的是检索在k-d树中与查询点距离最近的数据点。这里先以一个简单的实例来描述最邻近查找的基本思路。
星号表示要查询的点（2.1,3.1）。通过二叉搜索，顺着搜索路径很快就能找到最邻近的近似点，也就是叶子节点（2,3）。而找到的叶子节点并不一定就是最邻近的，最邻近肯定距离查询点更近，应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻，还需要进行'回溯'操作：算法沿搜索路径反向查找是否有距离查询点更近的数据点。此例中先从（7,2）点开始进行二叉查找，然后到达（5,4），最后到达（2,3），此时搜索路径中的节点为小于（7,2）和（5,4），大于（2,3），首先以（2,3）作为当前最近邻点，计算其到查询点（2.1,3.1）的距离为0.1414，然后回溯到其父节点（5,4），并判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点。以（2.1,3.1）为圆心，以0.1414为半径画圆，如下图所示。发现该圆并不和超平面y = 4交割，因此不用进入（5,4）节点右子空间中去搜索。
再回溯到（7,2），以（2.1,3.1）为圆心，以0.1414为半径的圆更不会与x = 7超平面交割，因此不用进入（7,2）右子空间进行查找。至此，搜索路径中的节点已经全部回溯完，结束整个搜索，返回最近邻点（2,3），最近距离为0.1414。
一个复杂点了例子如查找点为（2，4.5）。同样先进行二叉查找，先从（7,2）查
找到（5,4）节点，在进行查找时是由y = 4为分割超平面的，由于查找点为y值为4.5，因此进入右子空间查找到（4,7），形成搜索路径<（7,2），（5,4），（4,7）>，取（4,7）为当前最近邻点，计算其与目标查找点的距离为3.202。然后回溯到（5,4），计算其与查找点之间的距离为3.041。以（2，4.5）为圆心，以3.041为半径作圆，如下图左所示。可见该圆和y = 4超平面交割，所以需要进入（5,4）左子空间进行查找。此时需将（2,3）节点加入搜索路径中得<（7,2），（2,3）>。回溯至（2,3）叶子节点，（2,3）距离（2,4.5）比（5,4）要近，所以最近邻点更新为（2，3），最近距离更新为1.5。回溯至（7,2），以（2,4.5）为圆心1.5为半径作圆，并不和x = 7分割超平面交割，如下图右所示。至此，搜索路径回溯完。返回最近邻点（2,3），最近距离1.5。
当维数较大时，直接利用k-d树快速检索的性能急剧下降。假设数据集的维数为D，一般来说要求数据的规模N满足条件：N远大于2的D次方，才能达到高效的搜索。
上述两次实例表明，当查询点的邻域与分割超平面两侧空间交割时，需要查找另一侧子空间，导致检索过程复杂，效率下降。研究表明N个节点的K维k-d树搜索过程时间复杂度为：tworst=O（kN1-1/k）。
后记
以上为了介绍方便，讨论的是二维情形。像实际的应用中，如SIFT特征矢量128维，SURF特征矢量64维，维度都比较大，直接利用k-d树快速检索（维数不超过20）的性能急剧下降。假设数据集的维数为D，一般来说要求数据的规模N满足N»2D，才能达到高效的搜索。所以这就引出了一系列对k-d树算法的改进。有待进一步研究学习。
k-d tree总结二
k 维的 k-d树
由于三维以上我们无法想象了，但根据低维的情况不难想到，kk 维的 k-d树 的每一层也需要确定一个维度，来对 kk 维空间上的点进行划分。
建树
在构造 1 维 BST 树时，一个 1 维数据根据其与树的根结点进行大小比较，来决定是划分到左子树还是右子树。
同理，我们也可以按照这样的方式，将一个 kk 维数据与 k-d树 的根结点进行比较，只不过不是对 kk 维数据进行整体的比较，而是选择某一个维度 D_iDi，然后比较两个数据在该维度 D_iDi 上的大小关系，即每次选择一个维度 D_iDi 来对 kk 维数据进行划分，相当于用一个垂直于该维度 D_iDi 的超平面将 kk 维数据空间一分为二，平面一边的所有 kk 维数据在 D_iDi 维度上的值小于平面另一边的所有 kk 维数据对应维度上的值。
也就是说，我们每选择一个维度进行如上的划分，就会将 kk 维数据空间划分为两个部
分，如果我们继续分别对这两个子 kk 维空间进行如上的划分，又会得到新的子空间，对新的子空间又继续划分，重复以上过程直到每个子空间都不能再划分为止。以上就是构造 k-d树 的过程。
那么如果是二维特殊情况，就变得非常好理解了，通俗的来说就是通过过已有点的横线，竖线来划分二维平面。
上述过程中涉及到两个重要的问题：
1. 每次对子空间的划分时，怎样确定在哪个维度上进行划分？
2. 在某个维度上进行划分时，怎样确保在这一维度上的划分得到的两个子集合的数量尽量相等，即左子树和右子树中的结点个数尽量相等？
对于第一个问题，有很多种方法可以选择划分维度（axis-aligned splitting planes），所以有很多种创建 k-d树 的方法。 最典型的方法如下：
随着树的深度轮流选择维度来划分。例如，在二维空间中根节点以 x 轴划分，其子节点皆以 y 轴划分，其孙节点又以 x 轴划分，其曾孙节点则皆为 y 轴划分，依此类推。
另外的划分方法还有最大方差法（max invarince），在这里不做介绍。
而对于第二个问题，也是在 BST 中会遇到的一个问题。在 BST 中，我们是将数据的中位数作为根节点，然后再左右递归下去建树，这样可以得到一棵平衡的二叉搜索树。
同样，在 k-d树 中，若在维度 D_iDi 上进行划分时，根节点就应该选择该维度 D_iD
i 上所有数据的中位数，这样递归子树的大小就基本相同了。对给定范围 内的元素进行重
新布置。使得 位置的值就是所有元素第 k 小的值。并把所有不大于 的值放到 的前面。把所有不小于 的值放到nth后面（不一定有序）。复杂度是 O(n)O(n) 的。
所以建树的总复杂度为：O(n\\log n)O(nlogn)。
插入
与二叉搜索树的插入很像，二叉搜索树是单纯比较值，而 k-d树 是与当前结点比较在 D_iDi 维度上的值，来决定到底要在左子树还是在右子树插入。比较简单，复杂度：O(\\log n)O(logn)。要注意的是插入以后要记得维护走过的节点子树覆盖的矩形区域。
查找
最近点
构建好一棵 k-d树 后，下面给出利用二维 k-d树寻找距离点 PP 最近的点：
1设定答案 初始值 \\infty∞
2 将点 PP 从根结点开始，先用根节点代表的点更新答案。由于根节点的左右儿子各代表一个矩形区域，而两个区域都有可能存在距离点 PP 最近的点，我们优先选择距离点 PP 最近的矩形递归查询。
3 然后以 PP 为圆心， 为半径画圆（曼哈顿距离就是矩形），如果与之前未递归的矩形相交，则递归下去，否则不可能有更优答案。
事实上就是搜索加剪枝，可以证明：单次查询的复杂度一般是 O(\\log n)O(logn)，最坏 O(\\sqrt n)O(√n) 的。
k 远点
k最近点很好查询，k 远点也是不难的，我们维护一个小根堆，初始向堆里面放入 kk 个 -\\infty−∞，然后之前的与 比较就变成了与堆顶比较。
k-d tree 总结三
k-d树(k-dimensional tree)是一种空间数据分割结构，对于组织在d维空间的数据进行搜索，典型的应用如范围搜索(Range Search)和最邻近搜索(Nearest Search)。这两个术语有没有感觉很熟悉，在机器学习Clustering算法中经常用到这两个功能，如DBSCAN、OPTICS等算法。
在使用Range Query和Nearest Search过程中，如果使用遍历的方法也能完成数据空间的搜索功能，缺点很明显：穷举遍历会造成性能下降。穷举法对于数据集合本身的结构信息没有使用，大大浪费了数据的特性；如果能预先根据数据特点建立索引，能在查询过程中快速匹配，就能够加快数据检索的速度。k-d树的算法目的是对高维空间索引数据进行结果和近似查询，如快速的找到查询数据点的近邻；查找符合查询条件的范围(Range)等。
k-d树的查询有两种基本方式：
K-Neighbor Search：给定数据点及正整数K，从数据集合中查找到距离查询点最近
的K个数据，kNN(K-Nearest Neighbor)算法对这种查询索引树数据结构是极其重要的。
Range Query：给定查询点和查询距离阀值，从数据集合中找到所有距离查询点小于阀值的数据点。
k-d树是一种特殊的二叉树，其中每个数据节点都是k维(k-dimensional)数据。其中每个非叶子节点都是对数据点在一个维度上一个划分：二维空间的划分是线，超过二维划分是一个超平面。如果你还是不熟悉的话，可以将K维数据缩减为1维数据，这样的话k-d树就收缩为1维平衡二叉树。再将1维数据扩张为k维，将每个非叶子节点看做是在多维数据中其中一维数据的划分，在这个维度上的数据点按照左小右大划分到子节点上。
k-d树的主要操作有：构建和查询。构建是预处理操作，将数据点构建成k-d树，方便后来的数据进行查询；查询时即时操作，在生成的k-d树中查找符合条件的数据点。
在k-d树构建过程中，depth为偶数按照x轴划分，depth为奇数的话从y轴划分，wiki上的划分是按照纬度依次划分，我们这里的举例是二维空间数据。划分是指选择从数据空间中选择一个维度，再对该纬度上的数据进行操作。这个操作比较简单，就是在该维度上对数据排序，选择中间点为锚点(Axis)，将数据划分为锚点左(P1)右(P2)，然后再重复迭代树的构建过程。
构建k-d树过程中有三个过程需要注意：
数据纬度选择：在上面中根据深度选择数据的纬度，这个其实并不好，通常的做法是将数据点按照纬度进行方差计算，选择方差最大的那个纬度进行纬度划分。方差越大，说明纬度分散性越好，越有利于数据划分。
数据纬度排序：将数据点在选定的纬度上进行排序，注意这个排序是数据点中的一个维度，在Python中很好实现。
数据划分：排序后将数据集合进行划分，分为Left和Right，在后面迭代计算(我为什么要写这个呢？如果优先考虑内存使用的话，这个该怎么做)。
聚类距离计算
2.2距离计算方法
两个点的相似通过欧式距离计算：
欧式距离计算公式
数据点与组合数据点间的距离计算方式：
将数据点B与数据点C进行组合后，重新计算各类别数据点间的距离矩阵。数据点间的距离计算方式与之前的方法一样。这里需要说明的是组合数据点(B,C)与其他数据点间的计算方法。当我们计算(B,C)到A的距离时，需要分别计算B到A和C到A的距离均值。
数据点与组合数据距离计算公式
两个组合数据点间的距离计算方式：
计算两个组合数据点间距离的方法有三种，分别为Single Linkage，Complete Linkage和Average Linkage。在开始计算之前，我们先来介绍下这三种计算方法以及各自的优缺点。
Single Linkage
Single Linkage的计算方法是将两个组合数据点中距离最近的两个数据点间的距离作为这两个组合数据点的距离。这种方法容易受到极端值的影响。两个很相似的组合数据点可能由于其中的某个极端的数据点距离较近而组合在一起。
Complete Linkage
Complete Linkage的计算方法与Single Linkage相反，将两个组合数据点中距离最远的两个数据点间的距离作为这两个组合数据点的距离。Complete Linkage的问题也与Single Linkage相反，两个不相似的组合数据点可能由于其中的极端值距离较远而无法组合在一起。
Average Linkage
Average Linkage的计算方法是计算两个组合数据点中的每个数据点与其他所有数据点的距离。将所有距离的均值作为两个组合数据点间的距离。这种方法计算量比较大，但结果比前两种方法更合理。
我们使用Average Linkage计算组合数据点间的距离。下面是计算组合数据点(A,F)到(B,C)的距离，这里分别计算了(A,F)和(B,C)两两间距离的均值。
这种聚类的方法描述起来比较简单，但是计算复杂度比较高，为了寻找距离最近/远和均值，都需要对所有的距离计算个遍，需要用到双重循环，每次迭代都只能合并两个子类，这是非常慢的。
因篇幅问题不能全部显示，请点此查看更多更全内容