我有100万个5维点,我需要将其分组为k群集,其中k << 100万.在每个星团中,没有两个点应该相距太远(例如,它们可以是具有指定半径的边界球).这意味着可能必须有许多大小为1的集群.
但!我需要运行时间远低于n ^ 2.n log n左右应该没问题.我正在进行这种聚类的原因是为了避免计算所有n个点的距离矩阵(这需要n ^ 2次或几个小时),而我只想计算簇之间的距离.
我尝试了pycluster k-means算法,但很快意识到它太慢了.我也试过以下贪婪的方法:
每个维度将空间切成20块.(所以总共有20 ^ 5件).我会根据它们的质心将簇存储在这些网格盒中.
对于每个点,检索r(最大边界球半径)内的网格框.如果有足够的群集,请将其添加到该群集,否则创建新群集.
但是,这似乎给了我比我想要的更多的集群.我也实现了两次类似的方法,它们给出了非常不同的答案.
是否有任何标准的聚类方法比n ^ 2时间快？概率算法没问题.
algorithm cluster-analysis machine-learning data-mining k-means