今天爱分享给大家带来k-means算法的优化方法【详细讲解】，希望能够帮助到大家。
（一）kd tree
kd树是一种对k维空间中的实例点进行存储一遍对其进行快速检索的树形树形结构。kd树是一种二叉树，表示对k维空间的一种划分。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间进行划分，构成一系列的k维超巨型区域。kd树的每个节点对应于一个k维超矩形区域。利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。
说明：
△ 选择切分轴（即特征）的方法：坐标轴的维度=节点的深度（mod k）+1
△ 选择切分点的方法：观测点在选定坐标轴上的中位数。（这样会使建立的树非常的平衡）
△ 算法结束的条件：每个区域只包含两个观测点存在时划分结束。
kd树的搜索（给定一个目标点，搜索其最近邻）：首先找到包含目标点的叶节点；然后从该叶节点出发，依次退回到父节点；不断查找与目标节点最邻近的节点，当确定不可能存在更近的节点为止，这样的搜索就被限制在空间的局部区域上，效率大大提高。
kd树的优点：可以递增更新。
kd树的缺点： 矩形并不是用到这里最好的方式。偏斜的数据集会造成我们想要保持树的平衡与保持区域的正方形特性的冲突。另外，矩形甚至是正方形并不是用在这里最完美的形状，由于它的角。如果图中的圆再大一些，即黑点距离目标点点再远一些，圆就会与左上角的矩形相交，需要多检查一个区域的点，而且那个区域是当前区域双亲结点的兄弟结点的子结点。 为了解决这一问题，我们引入了ball tree。
（二）ball tree
ball tree在划分的时候使用的是超球面而不是超矩形，使用球面可能会造成球面间的重叠，但是却没有关系。图2所示就是一个2维平面包含了16个观测实例的图，图3所示是其对应的ball tree，其中节点中的数字表示包含的观测点数。
树中的每个结点对应一个圆，结点的数字表示该区域保含的观测点数，但不一定就是图中该区域囊括的点数，因为有重叠的情况，并且一个观测点只能属于一个区域。实际的 ball tree 的结点保存圆心和半径。叶子结点保存它包含的观测点。
ball tree的搜索：先自上而下找到包含 target 的叶子结点，从此结点中找到离它最近的 观测点。这个距离就是最近邻的距离的上界。检查它的兄弟结点中是否包含比这个上界更小的观测点。方法是：如果目标点距离兄弟结点的圆心的距离大于这个圆的圆心加上前面的上界的值，则这个兄弟结点不可能包含所要的观测点（如图4）。否则，检查这个兄弟结点是否包含符合条件的观测点。
