本文共 1912 字,大约阅读时间需要 6 分钟。
kmeans是最简单的聚类算法之一,kmeans一般在数据分析前期使用,选取适当的k,将数据分类后,然后分类研究不同聚类下数据的特点。
时间复杂度:O(I*n*k*m)
空间复杂度:O(n*m)
其中m为每个元素字段个数,n为数据量,I为跌打个数。一般I,k,m均可认为是常量,
所以时间和空间复杂度可以简化为:O(n),即线性的。
从kmeans的算法可以发现,设目标函数SSE如下:
SSE(,,…,) =
SSE其实是一个严格的坐标下降(Coordinate Decendet)过程,采用欧式距离作为变量之间的聚类函数。每次朝一个变量 Ci 的方向找到最优解;目标函数SSE求偏倒数,并令其偏导数等于0,可得:
Ci =
其中 m 是 Ci 所在的簇的元素的个数.
我们由公式Ci发现,当前聚类的均值就是当前方向的最优解(最小值),这与kmeans的每一次迭代过程一样。所以,这样保证SSE每一次迭代时,都会减小,最终使SSE收敛。
由于SSE是一个非凸函数(non-convex function),所以SSE并不能保证找到全局最优解,只能确保局部最优解。但是可以重复执行几次kmeans,选取SSE最小的一次作为最终的聚类结果。
计算最近的邻居之间的距离,通常用欧氏距离来,有时也用曼哈顿距离,请对比下这两种距离的差别?
欧氏距离虽然很有用,但也有明显的缺点。它将样品的不同属性(即各指标或各变量量纲)之间的差别等同看待,这一点有时不能满足实际要求。例如,在教育研究中,经常遇到对人的分析和判别,个体的不同属性对于区分个体有着不同的重要性。因此,欧氏距离适用于向量各分量的度量标准统一的情况。
如果各数据之间量纲的不相同,该如何比较?
由于数据之间量纲的不相同,不方便比较。举个例子,比如游戏用户的在线时长和活跃天数,前者单位是秒,数值一般都是几千,而后者单位是天,数值一般在个位或十位,如果用这两个变量来表征用户的活跃情况,显然活跃天数的作用基本上可以忽略。所以,需要将数据统一放到0~1的范围,将其转化为无量纲的纯数值,便于不同单位或量级的指标能够进行 比较 和 加权。
具体计算方法如下:
其中属于A。
通常使用轮廓系数(Silhouette Coefficient),用于评估聚类的效果。轮廓系数结合了聚类的凝聚度(Cohesion)和分离度(Separation)。该值处于-1~1之间,值越大,表示聚类效果越好。具体计算方法如下:
从上面的公式,不难发现若s_i小于0,说明x_i与其簇内元素的平均距离小于最近的其他簇,表示聚类效果不好。如果a_i趋于0,或者b_i足够大,那么s_i趋近与1,说明聚类效果比较好。
曼哈顿距离,我们可以定义曼哈顿距离的正式意义为L1-距离或城市区块距离,也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上,坐标(x1, y1)的点P1与坐标(x2, y2)的点P2的曼哈顿距离为:
要注意的是,曼哈顿距离依赖座标系统的转度,而非系统在座标轴上的平移或映射。当坐标轴变动时,点间的距离就会不同。
通俗来讲,想象你在曼哈顿要从一个十字路口开车到另外一个十字路口,驾驶距离是两点间的直线距离吗?显然不是,除非你能穿越大楼。而实际驾驶距离就是这个“曼哈顿距离”,这也是曼哈顿距离名称的来源, 同时,曼哈顿距离也称为城市街区距离(City Block distance)。
曼哈顿距离和欧式距离一般用途不同,无相互替代性。
马氏距离和余弦相似度可参考下面:
[1]马氏距离及其几何解释
[2]欧氏距离和余弦相似度的区别是什么?转载地址:http://knfgi.baihongyu.com/