KMeans

KMeans是一种简单的聚类算法,将数据集划分为多个簇,K为簇的个数。传统的KMeans算法,有一定的性能瓶颈,通过PS实现的KMeans,在准确率一致的情况下,性能更佳。

1. 算法介绍

每个样本被划分到距离最近的簇。每个簇所有样本的几何中心为这个簇的簇心,样本到簇心的距离为样本到簇的距离。Kmeans算法一般以迭代的方式训练,如下所示:

kmeans

其中:xi代表第i个样本,ci代表与第i个样本距离最近的簇,miu_i代表第j个簇的簇心。

Mini-batch KMeans

“Web-Scale K-Means Clustering”[1]提出一种在朴素KMeans算法基础上改进的KMeans算法,用mini-batch方法训练,每次迭代选择一个mini-batch的样本更新簇心,如下所示:

mini_batch_kmeans

2. 分布式实现 on Angel

模型存储

Angel实现的KMeans算法将K个簇心以及每个簇心的样本计数存储在ParameterServer上,其中K个簇心用一个K×N维的矩阵表示,簇心的样本计数用一个K×1的向量表示,K为簇心的个数,N为数据的维度,即特征的个数。

模型更新

KMeans on Angel以迭代的方式训练,每次训练使用上文提到的mini-batch KMeans算法更新簇心。

算法逻辑

KMeans on Angel的算法流程如下图所示:

KMeans_on_Angel

3. 运行 & 性能

参数

  • 输入格式

    • ml.data.type:支持”dense”、”libsvm”、”dummy”三种数据格式,具体参考:Angel数据格式
  • 输入输出参数

    • ml.feature.index.range:特征向量的维度
    • ml.data.type: 支持”dummy”、”libsvm”两种数据格式
    • angel.train.data.path:训练数据的输入路径
    • angel.predict.data.path:预测数据的输入路径
    • angel.save.model.path:训练完成后,模型的保存路径
    • angel.predict.out.path:预测结果存储路径
    • angel.log.path:log文件保存路径
  • 算法参数

    • ml.epoch.num: 迭代次数
    • ml.minibatch.size:每次迭代选择mini-batch的样本个数
    • ml.kmeans.center.num:K值,即簇的个数
    • ml.kmeans.c:学习速率参数
  • 资源参数

    • angel.workergroup.number:Worker个数
    • angel.worker.memory.mb:Worker申请内存大小
    • angel.worker.task.number:每个Worker上的task的个数,默认为1
    • angel.ps.number:PS个数
    • angel.ps.memory.mb:PS申请内存大小
  • 提交命令
    *向Yarn集群提交Kmeans算法训练任务:

    1. ./bin/angel-submit \
    2. --action.type=train \
    3. --angel.app.submit.class=com.tencent.angel.ml.clustering.kmeans.KMeansRunner \
    4. --ml.model.class.name=com.tencent.angel.ml.clustering.kmeans.KMeansModel \
    5. --angel.train.data.path=$traindata \
    6. --angel.save.model.path=$modelout \
    7. --angel.output.path.deleteonexist=true \
    8. --angel.log.path=$logpath \
    9. --ml.data.type=libsvm \
    10. --ml.model.type=T_DOUBLE_DENSE \
    11. --ml.kmeans.center.num=$centerNum \
    12. --ml.kmeans.c=0.15 \
    13. --ml.epoch.num=10 \
    14. --ml.feature.index.range=$featureNum \
    15. --ml.feature.num=$featureNum \
    16. --angel.workergroup.number=4 \
    17. --angel.worker.memory.mb=5000 \
    18. --angel.worker.task.number=1 \
    19. --angel.ps.number=4 \
    20. --angel.ps.memory.mb=5000 \
    21. --angel.job.name=kmeans_train

    *向Yarn集群提交Kmeans算法增量训练任务:

    1. ./bin/angel-submit \
    2. --action.type=inctrain \
    3. --angel.app.submit.class=com.tencent.angel.ml.clustering.kmeans.KMeansRunner \
    4. --ml.model.class.name=com.tencent.angel.ml.clustering.kmeans.KMeansModel \
    5. --angel.train.data.path=$traindata \
    6. --angel.load.model.path=$modelout \
    7. --angel.save.model.path=$modelout \
    8. --angel.output.path.deleteonexist=true \
    9. --angel.log.path=$logpath \
    10. --ml.data.type=libsvm \
    11. --ml.model.type=T_DOUBLE_DENSE \
    12. --ml.kmeans.center.num=$centerNum \
    13. --ml.kmeans.c=0.15 \
    14. --ml.epoch.num=10 \
    15. --ml.feature.index.range=$featureNum \
    16. --ml.feature.num=$featureNum \
    17. --angel.workergroup.number=4 \
    18. --angel.worker.memory.mb=5000 \
    19. --angel.worker.task.number=1 \
    20. --angel.ps.number=4 \
    21. --angel.ps.memory.mb=5000 \
    22. --angel.job.name=kmeans_inctrain
  1. *向Yarn集群提交Kmeans算法预测任务:
  2. ```java
  3. ./bin/angel-submit \
  4. --action.type=predict \
  5. --angel.app.submit.class=com.tencent.angel.ml.clustering.kmeans.KMeansRunner \
  6. --ml.model.class.name=com.tencent.angel.ml.clustering.kmeans.KMeansModel \
  7. --angel.predict.data.path=$predictdata \
  8. --angel.load.model.path=$modelout \
  9. --angel.predict.out.path=$predictout \
  10. --angel.output.path.deleteonexist=true \
  11. --angel.log.path=$logpath \
  12. --ml.data.type=libsvm \
  13. --ml.model.type=T_DOUBLE_DENSE \
  14. --ml.kmeans.center.num=$centerNum \
  15. --ml.feature.index.range=$featureNum \
  16. --ml.feature.num=$featureNum \
  17. --angel.workergroup.number=4 \
  18. --angel.worker.memory.mb=5000 \
  19. --angel.worker.task.number=1 \
  20. --angel.ps.number=4 \
  21. --angel.ps.memory.mb=5000 \
  22. --angel.psagent.cache.sync.timeinterval.ms=500 \
  23. --angel.job.name=kmeans_predict
  24. ```

性能

  • 数据:街景号码图像数据集,3×10^3 特征,7×10^4 样本
  • 资源:
    • Angel:executor:4个,5G内存,1个task;ps:4个,5G内存
  • 迭代100次时间:
    • Angel:45min

4. 参考文献

[1] Sculley D. Web-scale k-means clustering[C]// International Conference on World Wide Web, WWW 2010, Raleigh, North Carolina, Usa, April. DBLP, 2010:1177-1178.