• KMeans
    • 1. 算法介绍
    • Mini-batch KMeans
    • 2. 分布式实现 on Angel
      • 模型存储
      • 模型更新
      • 算法逻辑
    • 3. 运行 & 性能
      • 参数
      • 性能
    • 4. 参考文献

    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算法预测任务:
    3. ```java
    4. ./bin/angel-submit \
    5.     --action.type=predict \
    6.     --angel.app.submit.class=com.tencent.angel.ml.clustering.kmeans.KMeansRunner  \
    7.     --ml.model.class.name=com.tencent.angel.ml.clustering.kmeans.KMeansModel \
    8.     --angel.predict.data.path=$predictdata \
    9.     --angel.load.model.path=$modelout \
    10.     --angel.predict.out.path=$predictout \
    11.     --angel.output.path.deleteonexist=true \
    12.     --angel.log.path=$logpath \
    13.     --ml.data.type=libsvm \
    14.     --ml.model.type=T_DOUBLE_DENSE \
    15.     --ml.kmeans.center.num=$centerNum \
    16.     --ml.feature.index.range=$featureNum \
    17.     --ml.feature.num=$featureNum \
    18.     --angel.workergroup.number=4 \
    19.     --angel.worker.memory.mb=5000  \
    20.     --angel.worker.task.number=1 \
    21.     --angel.ps.number=4 \
    22.     --angel.ps.memory.mb=5000 \
    23.     --angel.psagent.cache.sync.timeinterval.ms=500 \
    24.     --angel.job.name=kmeans_predict
    25. ```

    性能

    • 数据：街景号码图像数据集，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.