江苏龙网

  1. 首页 > 资讯 > 科技 > >

CDA数据分析师Kmeans算法精简版(无for loop循环)( 四 )


将上面的符号解释完了后 ， 以下就是损失函数 。 这里是使用了求和嵌套了求和的公式 ， 并且也引入了刚才所提到了r_{nk}rnk? 。 这个损失函数其实很好理解 ， 在给定的k个中心点u_kuk?以及分配好了各个实例点属于哪一个簇之后 ， 计算各个实例点到各自的簇中心点的距离 ， 距离平方以下并且相加起来 ， 就是损失函数 。 这个公式其实也就是在算簇内误差和 。
C = \sum_{n=1}^N\sum_{k=1}^K r_{nk} (x_n - u_k)^2C=n=1∑N?k=1∑K?rnk?(xn??uk?)2
那怎么来最小化这个损失函数呢 ， 用的就是EM算法 ， 这个算法总体来说分2个步骤 ， Expectation和Maximization ， 对Kmeans来说M应该说是Minimization
Expection:
保持u_{k}uk?不变 ， 也就是各个簇的中心点的位置不变 ， 计算各个实例点到哪个u_{k}uk?最近 ， 将各个实例点划分到离各自最近的那个簇里面去 ， 从而使得整体SSE降低 。
Minimization:
保持当前实例点的簇的类别不变 ， 为了整体降低损失函数 ， 可以对每个簇内的损失函数公式做微分 。 由于当前我们的各个点的类别是不变的 ， 变的是u_{k}uk? ， 所以做的微分是基于u_{k}uk?的
\frac{d}{du_{k}}\sum_{k=1}^K r_{nk} (x_n - u_k)^2 = 0duk?d?k=1∑K?rnk?(xn??uk?)2=0
-2\sum_{k=1}^K r_{nk} (x_n - u_k) = 0?2k=1∑K?rnk?(xn??uk?)=0
u_{k} = \frac{\sum_{n} r_{nk} x_{n}}{\sum_{n} r_{nk}}uk?=∑n?rnk?∑n?rnk?xn??
得出来的u_{k}uk?其实就是在算各个簇内的新的中心点 ， 也就是对各个簇内所有的实例点的各个特征做平均数 。
这时候得到新的中心点u_{k}uk?, 紧接着再到E阶段 ， 保持u_{k}uk?更新簇类别 ， 再到M阶段 ， 保持簇类别不变更新u_{k}uk? ， 不断的迭代知道SSE不变位置 。 这个就是Kmeans的算法过程 。 下面将用plotly可视化 ， 动态展示Kmeans的过程 。
使用之前写好的函数 ， 然后将数据的中间过程通过plotly展示出来 。 因为代码比较长 ， 所以这里就不展示代码了 。 由于当前是一个markdown ， 这里放入一个gif图片用来展示最后的Kmeans中间过程 。
对于这个数据集来看的话 ， 我们的Kmeans算法可以使得每一个点最终可以找到各自的簇 ， 但是这个算法也是有缺陷的 ， 比如以下例子 。
假如说现在有4个簇的话 ， Kmeans算法不一定能使最后的SSE最小 。 对于2列的数据集来说 ， 我们取2组随机的质心点来做对比 。
第一组为设置seed为5的时候 ， 以下为演示的结果 。
从上面的动图可以看出一共用了8次迭代 ， 才收敛 。 那加入我们的seed为1的话 ， 随机的质心点的分布会变的很离谱 ， 会导致下面的结果 。 这里我们加快动画的速度 。
这里用34次 ， 数据才迭代收敛 ， 并且可以看出 ， 在迭代的过程中 ， 差点陷入了一个局部最小的一个情况 。 所以对于复杂的数据来说的话 ， 我们最后看到迭代的次数会明显的增加 。
假如说我们的数据集再变的集中一点 ， 其中的2个簇 ， 稍微近一点 ， 我们会看到以下的结果 。
? 所以在这次迭代的过程中 ， 我们明显看到其中有个质心点消失了 ， 原因就是因为由于点的分布的原因和初始质心点的原因 ， 最开始随机生成的一个离所有的点都最远的质心点 ， 由于它离所有的点都最远 ， 所以导致了在迭代的过程中 ， 没有任何一个点属于这个质心点 ， 最后导致这个点消失了 。 所以这个就是Kmeans算法的缺陷 ， 那怎么来优化这个算法了 ， 我们可以利用BiKmeans算法 。


推荐阅读


上一篇：游戏高色域144Hz电竞屏 机械革命蛟龙P760 AMD游戏本

下一篇：“骁龙”不仅是小小的芯片，而是你身边的互联生态