• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

Kmean计算优化

ml admin 4个月前 (03-13) 212次浏览 0个评论 扫描二维码

最近一些列的博客尽量使用口语化的方式来把问题说明白,一般情况下能把事情说的明明白白也可以变相的说明你对问题有一定的了解。

此处十一点四十多了码子有点困了。。。。continue

kmean 聚类被使用的机会还是很多,计算比较简单,实现也简单。简单的方法也容易排查问题,kmean 自身也有局限性,比如初始聚类中心点的选择对算法的影响以及聚类的个数 k 值的选择,面临大数据的时候算法计算的速度问题。

k 值的选择如果有一定的先验知识的话可以确定大概的值,初始中心点的选择可以考虑使用 kmean++算法或者 canopy 算法(此算法也存在参数的 tuning 的问题,但是也是一种思路),计算速度的问题也就是我们现在要聊的问题了。

这里所说的计算涉及到这一步,就是每一个观测点到聚类中心的距离计算,假设我们的聚类中心的个数比较多,每一次都要便利计算消耗的代价比较大,所以使用 KD 树数据结构来优化。

首先介绍一下 KD 树的构造过程

第一步:我们把 n 维特征的观测实例放到 n 维空间中,k-d tree 每次通过某种算法选择一个特征(坐标轴),以它的某一个值作为分界做超平面,把当前所有观测点分为两部分,然后对每一个部分使用同样的方法,直到达到某个条件为止。
上面的表述中,有几个地方下面将会详细说明:(1)选择特征(坐标轴)的方法  (2)以该特征的哪一个为界 (3)达到什么条件算法结束。

(1)选择特征的方法

计算当前观测点集合中每个特征的方差,选择方差最大的一个特征,然后画一个垂直于这个特征的超平面将所有观测点分为两个集合。

(2)以该特征的哪一个值为界 即垂直选择坐标轴的超平面的具体位置。

第一种是以各个点的方差的中值(median)为界。这样会使建好的树非常地平衡,会均匀地分开一个集合。这样做的问题是,如果点的分布非常不好地偏斜的,选择中值会造成连续相同方向的分割,形成细长的超矩形(hyperrectangles)。

替代的方法是计算这些点该坐标轴的平均值,选择距离这个平均值最近的点作为超平面与这个坐标轴的交点。这样这个树不会完美地平衡,但区域会倾向于正方地被划分,连续的分割更有可能在不同方向上发生。

(3)达到什么条件算法结束

实际中,不用指导叶子结点只包含两个点时才结束算法。你可以设定一个预先设定的最小值,当这个最小值达到时结束算法

关于 kd 树的构造可以参考这篇文章kd 树基本描述

ball tree

ball tree 与 kd 树的不一样的地方主要是使用圆来代替矩形了。

先看以下两个图

图 a 给出了圆形区域划分,图 b 示二叉树的基本描述,二叉树的每一个节点表示包含了多少个观察点,并且每一个节点会自带所有观测点的特征数据和数量,方便计算中心点。比如 a 图中最大的实线圆表示的就是根节点,这个节点包含了 16 个观测点,如果数据集就是上图描述出来的数据集,那么就可以说实线圆圈包含了所有的数据观测点。

kmeans 使用 ball tree

在 k-means 算法中使用 k-d tree 和 ball tree 效率更高,因为在此所有的观测点都是一起处理,而在 k 近邻中,测试的观测点单独处理。
首先,根据所有的观测点创建一个包含它们的 k-d tree 或者是 ball tree。
在 k-means 算法的每一次迭代中,设定的聚类中心集合为 C={Ci,i= 1,…,k},每个簇中心有一个对应其归属它的观测点集合,初始为空。从根结点开始遍历树,直到找到叶子结点为止,判断其中的观测点距离哪一个中心近,然后赋给那个中心。有可能在浏览一个内部结点时,它所包含的点完全包含在一个聚类的区域内。这时只需要直接把其下所有的观测点加入到该聚类中即可。
我们可以在每个簇的中心点保存一个向量,保存聚类中点各个坐标之和和点的个数。在计算其中心点时只需一除即可。

下面给出一个说明图,顺便安利一个软件 omnigraffle,画图神器

上面三个大圆圈表示三个聚类簇,小圆圈表示一个 balltree 的超圆,此时超圆上的观测点与最右边的聚类簇中心的最远距离 r1 比 r2,r3 都要小,则将其归入最右边的聚类簇。r2,r3 分别表示超圆观测点距离其他聚类簇中心的距离。


Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明Kmean 计算优化
喜欢 (0)
admin
关于作者:

您必须 登录 才能发表评论!