博文
FEKM: fast and extract out-of-core k-means clustering
||
Kmeans的时间复杂度是O(m)（《数据挖掘导论》，m是数据规模）。但是，算法在每次迭代过程中需要计算每个点到各个质心的距离，于是距离函数需要被计算km次，k是质心个数，而计算欧氏距离的过程如果看成是求一个n次多项式的函数值的过程，就算运用秦九韶算法也需要n次乘法和n次加法。当数据规模很大甚至作为核外数据集时，这显然是不能接受的。
前人的许多研究都围绕近似展开，以牺牲准确度为代价来加速算法。这篇文章提出的FEKM算法，可通过对样本实施原KM算法，得到k个质心，然后将这k个质心位移到正确的位置上，使得最终结果和直接对整个数据集实施KM算法得到的k个质心一样。如此不仅提高了算法效率，而且并不在准确度上作出让步。
1，主要思想
1，KM算法是一种迭代算法，每次迭代都更新质心的值和各个质心所辖的簇中的数据点，所以质心初始值的选定非常关键（考虑选定两个质心初值时，两个质心都距离数据集的所有点非常远，则每次迭代时数据点都会选择较近的一个质心作为自己所属簇的质心，于是最终结果是聚类得到一个空簇和一个包含所有数据点的簇）。
2，可以合理地认为，每次使得质心发生位移的，往往是那些边界点（boundary points，即在各个簇之间跳变的点）。因为质心值的更新是通过求该簇所有点的均值得到的，只要某些点依然归属于该簇，就不会对结果造成影响。所以，如果仅仅找出并考虑边界点，可以大大优化算法的效率。
2，具体解决方案
于是关键问题变成了以下三个：如何运用样本集的聚类结果；如何判断边界点；如何用边界点更新质心。
显然算法的目的是找到k个簇的质心，样本集产生的k个质心则作为FEKM迭代之前质心的初值。
边界点的特点在于到两个或两个以上质心的距离比较接近，如此才可能在后面某次迭代时被另一簇吸引。而那些距离一个质心远远比距其他质心更近的点，我们称之为稳定点（stable points）。那么如何量化“远近”这种概念呢？算法引进了置信度$\delta ij$，满足$d(c_{ij},s_{ij}) \leq \delta ij$，其中$d(\cdot)$是距离函数，$c_{ij}$是在样本集上运行KM算法时，第i次迭代后的质心j，$s_{ij}$表示FEKM对C进行迭代时，在第i次迭代后的质心j。
显然置信度必须很小，并且，与簇和数据点都相关。确切的说，$\delta$和第i次迭代前簇中数据点的均值以及当前的质心有关。
于是，边界点定义为满足$0 \leq |d(s_{il},p)- d(s_{ij},p)| \leq \delta _{ij}+delta _{il}$的点p。相似的，稳定点定义为满足$|d(s_{il},p)- d(s_{ij},p)| > \delta _{ij}+delta _{il}$
而在找出边界点的情况下，运用边界点来更新质心也并不困难。在更新质点时考虑边界点的可能动向即可，而稳定点不必再参与计算。
于是问题变成了：合理的置信度怎样设置才是合理的？文章提出了下面的计算公式：
$\delta_{ij}=f\times\left ( \frac{\sum_{p=1}^{N}(X_p-X_c)}{N} \right )^{1/2}=\left( \frac{\sum_{p=1}^{N}X_p}{N}-X_c \right )^{1/2}$
f是一个需要根据实验确定的参数。$X_p$是在第i次迭代被指派到簇j的点，$X_c$是该簇当前的质心，N是该簇的大小。对于一个固定的f，置信度和簇中数据点的均值到质心的距离成正比。这就保证了对于密度大的簇，置信度取得一个很小的值，而密度小的簇的置信度取得较大的值。如果某时刻某个置信度过大的，边界点将过多，某次迭代过程中质心或将发生很大的位移，导致质心偏移到了簇外，则说明边界点的选取是不合适的，需要修改f，再次遍历数据点，选取新的边界点。
为了选定合适的f，文章中的实验对边界点作出了两点限制：1，边界点数量小于数据集规模的20%；2，不可超出内存大小。两个条件一旦不满足，则减小f的值；实验发现f=0.05是合适的。
至此，置信度的确定问题也讨论完毕。
于是FEKM的大体流程是：
1，抽样并对样本集实施KM聚类，得到k个质心C={c1,c2,...,ck}；
迭代：
2，将数据集中所有点指派到距离自己最近的质心所辖的簇中，并标记是否是边界点；
3，更新质心。
4，直到收敛则终止，否则重复2。
3，理论证明
1，考虑第i次迭代，变化点（the changing points）是指分别将样本质心和k-means质心作为质心时有两个不同的归属的数据点。
2，设第i次迭代中对于质心j，($1 \leq j \leq k$)，$d(s_{ij}, c_{ij}) \leq \delta _{ij}$，则分别将样本质心和k-means质心作为质心时，稳定点的归属簇不变，而剩余的点则是边界点。
3，如果FEKM在第i迭代计算正确，并且在本次迭代中满足$\forall j,1 \leq j \leq k, d(s_{ij},c_{ij})<\delta_{ij}$，则FEKM在第i+1次迭代中的计算也是正确的。（所谓正确，即质心向正确的方向位移了。）
4，设$\forall i,j,1 \leq i \leq m,1 \leq j \leq k, d(s_{ij},c_{ij})<\delta_{ij}$成立，而在第m+1次迭代该条件不成立，那么k-means的质心将由FEKM通过m+1次迭代准确地计算出来。
4，实验比较
分别在人造数据集和真实数据上，主要通过实验比较了FEKM和KM。
1，不管初始化是好是坏，在效率上FEKM的效率超过KM的2倍；
2，二者效率上的差别主要在迭代次数上，FEKM的迭代次数基本在1或2之间，而KM的迭代次数从2到8次不等。
3，样本集的大小对算法效率有一定影响，但影响不太大。
4，另外，实验中比较了两个不同的收敛条件：1，质点的位移极小；2，设定一个很大的迭代次数。比较了这两个收敛条件下的迭代次数。发现后一个条件在初始化不合适的情况下是有用的，但显然需要过多的迭代次数。
Q：
1：对于那些通过估计聚类结果来加快KM的算法，是否也需要与FEKM进行比较？
2：FEKM不仅将数据点聚类，还得到了质心的精确解，在不关系质心而只需要聚类的情形下，莫非不适用？比如谱聚类的最后需要将U矩阵前k列的各行实施聚类，是不关系质心的，或者说此时质心没有实质的意义。
3，在2中的情形下，是否有效率上高于FEKM的算法？毕竟这松弛了对计算结果的要求。
https://blog.sciencenet.cn/blog-799581-641833.html
上一篇：Naive Bayes和贝叶斯网络
下一篇：When is nearest neighbor meaningful
扫一扫，分享此博文