适合大数据的聚类算法Mini Batch K-Means

发表于由

K-Means算法是常用的聚类算法，但其算法本身存在一定的问题，例如在大数据量下的计算时间过长就是一个重要问题。为此，Mini Batch K-Means，这个基于K-Means的变种聚类算法应运而生。

大数据量是什么量级？通过当样本量大于1万做聚类时，就需要考虑选用Mini Batch K-Means算法。但是，在选择算法时，除了算法效率（运行时间）外，算法运行的准确度也是选择算法的重要因素。Mini Batch K-Means算法的准确度如何？

minibatchkmeans11

上图是我们队3万的样本点分别使用K-Means和Mini Batch KMeans进行聚类的结果，由结果可知，在3万样本点的基础上，二者的运行时间相差2倍多，但聚类结果差异却很小（右侧粉红色的错误点）。

因此，Mini Batch KMeans是一种能尽量保持聚类准确性下但能大幅度降低计算时间的聚类模型。

K-Means的计算时间到底跟样本量之间是怎样的关系（用脚想也知道是样本量越大，计算时间越长），我们用一个实例来实验下。在下面的例子中，利用Python生成一个具有三个分类类别的样本类，其中的样本点（二维空间）的数量从100开始增长到1000000（步长为1000），我们用图例来看看计算时间与样本量的关系。（为了得到下面这幅图，我等了2个小时）结果如下：

time_minibatchkmeans11

从图中可以发现，在样本点为二维空间前提下，当数据量在2之下时，计算时间都可以接受（2秒以内）；但是计算时间跟数据量基本成线性关系，计算1000000个样本聚类耗时近16秒。由此可以试想，如果你的观测点有更多维度（更多维度意味着需要更多的计算量），那么耗时将比上述场景大很多。

回到本文的主体算法Mini Batch KMeans上来，应用Mini Batch KMeans能尽量在保持数据准确性的前提下降低运算时间，它是怎么做到的？

Mini Batch KMeans使用了一个种叫做Mini Batch（分批处理）的方法对数据点之间的距离进行计算。Mini Batch的好处是计算过程中不必使用所有的数据样本，而是从不同类别的样本中抽取一部分样本来代表各自类型进行计算。由于计算样本量少，所以会相应的减少运行时间，但另一方面抽样也必然会带来准确度的下降。

实际上，这种思路不仅应用于K-Means聚类，还广泛应用于梯度下降、深度网络等机器学习和深度学习算法。

Mini Batch KMeans的使用方法非常简单，跟K-Means一样，在Python的机器学习库SKlearn中，通过fit方法训练数据，然后通过labels_ 属性获得每个样本点的聚类结果值。演示代码如下：

  1. #coding:utf-8
  2. import numpy as np
  3. from sklearn.cluster import MiniBatchKMeans
  4. from sklearn import datasets
  6. np.random.seed(5)
  7. iris = datasets.load_iris()
  8. X = iris.data
  9. clf = MiniBatchKMeans(n_clusters = 3)
  10. clf.fit(X)
  11. pre_clu = clf.labels_
  13. #将原始数据集X和聚类结果标签组合成新数据集并输出前10条
  14. new_X = np.column_stack((X, pre_clu))
  15. print new_X[:10]

运行结果如下：

  1. array([[ 5.1,  3.5,  1.4,  0.2,  1. ],
  2.        [ 4.9,  3. ,  1.4,  0.2,  1. ],
  3.        [ 4.7,  3.2,  1.3,  0.2,  1. ],
  4.        [ 4.6,  3.1,  1.5,  0.2,  1. ],
  5.        [ 5. ,  3.6,  1.4,  0.2,  1. ],
  6.        [ 5.4,  3.9,  1.7,  0.4,  1. ],
  7.        [ 4.6,  3.4,  1.4,  0.3,  1. ],
  8.        [ 5. ,  3.4,  1.5,  0.2,  1. ],
  9.        [ 4.4,  2.9,  1.4,  0.2,  1. ],
  10.        [ 4.9,  3.1,  1.5,  0.1,  1. ]])

 

应用场景，由于Mini Batch KMeans跟K-Means是极其相似的两种聚类算法，因此应用场景基本一致，具体请参考K均值(K-Means)

其中，Mini Batch KMeans可配置的参数如下：

  1. class sklearn.cluster.MiniBatchKMeans(n_clusters=8, init=’k-means++’, max_iter=100, batch_size=100, verbose=0, compute_labels=True, random_state=None, tol=0.0, max_no_improvement=10, init_size=None, n_init=3, reassignment_ratio=0.01)

 

 

尾巴

默认情况下，无论是K-Means还是MiniBatchKMeans都是需要指定聚类数量，即算法里面的n_clusters参数值，但实际应用时发现不指定也是可以的。这并不意味着Python会“自动”帮你选择最佳类别数，而是已经预置了一个默认的类别8。如果你不去设置，它会默认分为8个类别。既然是通过Mini Batch进行抽样，那到底Mini Batch是什么？Mini Batch是原始数据集中的子集，这个子集是在每次训练迭代时抽取抽取的样本。这个值默认是100个，可以通过batch_size进行设置。


====================【好书推荐，我为自己代言】====================

《Python数据分析与数据化运营》第二版上市啦！

50+数据流工作知识点
14个数据分析与挖掘主题
8个综合性运营分析案例
涵盖会员、商品、流量、内容4大主题
360°把脉运营问题并贴合数据场景落地


本书主要基于Python实现，其中主要用到的计算库是numpy、pandas和sklearn，其他相关库还包括：
  • 标准库：re、time、datetime、json、 base64、os、sys、cPickle、tarfile
  • Python调用R的rpy2
  • 统计分析：Statsmodels
  • 中文处理：结巴分词
  • 文本挖掘：Gensim
  • 数据挖掘和算法：XGboost、gplearn、TPOT
  • 爬虫和解析：requests、Beautiful Soup、xml
  • 图像处理：OpenCV和PIL/Pollow
  • 数据读取：xlrd、pymongo、pymysql
  • 数据预处理：imblearn
  • 展示美化类：Matplotlib、pyecharts、graphviz、prettytable、wordcloud、mpl_toolkits、pydotplus
如果你对以下内容感兴趣，那么本书将值得一看：
  • KMeans聚类的自动K均值的确立方法
  • 基于软方法的多分类模型组合评估模型的应用
  • 基于自动下探（下钻、细分）的应用
  • 基于增量学习的多项式贝叶斯分类
  • pipeline管道技术的应用
  • 基于超参数的自动参数值的优化方法
  • 特征自动选择
  • 文本分类、文本主题挖掘
  • 基于自动时间序列ARIMA的P、D、Q的调整
  • python决策树规则输出
  • 基于自定义图像的文本标签云
  • 非结构化数据，例如图像、音频、文本等处理
  • 对象持久化处理
  • 如何使用Python调用R实现数据挖掘
  • 自动化学习：增加了对于自动化数据挖掘与机器学习的理论、流程、知识和应用库介绍，并基于TPOT做自动化回归和分类学习案例演示
有关这本书的写作感受、详细内容介绍、附件（含数据和代）下载、关键知识和方法以及完整书稿目录，请访问《Python数据分析与数据化运营》第二版出版了！要购买此书，可以去京东、当当和天猫等查看。

《适合大数据的聚类算法Mini Batch K-Means》上有1个想法

  1. Pingback引用通告： 谱聚类Spectral clustering(SC) | 数据常青藤

发表评论

电子邮件地址不会被公开。 必填项已用*标注