一种高效的聚类算法

在样本数多，样本维度高，k-means等聚类就会很低效，甚至失效。

在这样的情形下，k-means cluster往往行不通。失效通常表现为。1. 大量样本聚拢在少数核心周围。2.属于这个核心下的样本数随着迭代进行剧烈变化。

比较好坏情形，我发现根本原因是因为失效情形下，样本和聚类核心的距离方差太大。

再仔细想想，其实质点像有一本书说的：平均人其实是不存在的，这个概念在 "精英日课"中也有讲到。对若干个体的测量值取平均，真正接近这个平均值的个体是几乎没有的。其中的关键是高维度，低维情形下建立相关性是容易的，但高维情形下建立强的相关性很难。这是这个世界真实又普遍的情况，因而也注定了k-means 聚类算法在真实逻辑层面是广泛无效的。

换句话说k-means对样本维度取平均值得出的聚类核心会偏离真实数据分布。聚类算法的下一次迭代中，大量样本会远离这个不真实分布，导致核心周围的样本点个数快速跌至0. k-means出现的大量样本聚拢在少数不真实核心周围，不是因为这几个核心更接近真实分布，而是因为其它所有核心都更差。

而少数核心则病态地聚拢大量周边样本，让聚类失去意义。 这样的聚类核心样本查询命中率就会很低。

我想到个好办法： 办法是通过机器学习的办法，让聚类核心尽可能贴近真实分布。这个办法甚至连全部样本都不需要用到，就可以完成聚类。经测试，这个方法训练收敛速度非常快，聚类效率非常好。学习出的聚类核心的查询命中率非常高。

整个学习过程中，只用到部分样本。不同迭代轮中核心用到的样本都是不一样的。但是测试表明每个核心相应的类别的样本数比较快就稳定下来了。

粘一段部署的代码。需要根据样本规模合理调整epoch和 data_skip_spped

kernel_num=300
cluster_vecs=[random.choice(elements) for i in range(kernel_num)]

epoch=10
data_skip_spped=50
learning_rate=0.001
for i in range(epoch):
    for fi in range(i,len(elements),data_skip_spped):
        vec=elements[fi]
        cosine_distance=np.dot(cluster_vecs,vec)
        kernel_index=np.argmax(cosine_distance)
        kernel=cluster_vecs[kernel_index]
        new_kernel=kernel+learning_rate*(vec-kernel)
        new_kernel=new_kernel/np.sqrt(np.sum(new_kernel*new_kernel))
        cluster_vecs[kernel_index]=new_kernel
           

注1. 样本要先打乱。打乱后分布遵守的是 独立同分布，iid.所以呢，接下来解决起来就简单了。

注2. 聚类不应追求类别样本数的均匀（低方差），因为正态分布才是事物原本更常见的样子。