k-means||：基于MapReduce的优化算法

为方便说明，下面回顾k-means算法的一些说明：

X=｛x1， …，xn｝是d维欧几里得空间中的一组点集，k是指定的簇数量。||xi—xj||代表xi和xj的欧几里得距离。对一个点x和一个点子集YX，距离d（x，Y） =Miny∈Y |x—y | |。对于点子集YX，其簇中心为

X=｛x1， …，xn｝是d维欧几里得空间中的一组点集，k是指定的簇数量。||xi—xj||代表xi和xj的欧几里得距离。对一个点x和一个点子集YX，距离d（x，Y） =Miny∈Y |x—y | |。对于点子集YX，其簇中心为

C= ｛c1， …， ck｝是一组点集，对于YX，我们定义Y对于C的损失是

C= ｛c1， …， ck｝是一组点集，对于YX，我们定义Y对于C的损失是

k-means聚类的目标是选取一组k个中心的C使得Φ（C）最小（简称为Φ）。将k-means聚类的最优解记为Φ*，找到Φ*是NP难问题［15］。如果φX（ C） ≤ αΦ* ，则称中心点集C是对k-means的α近似。第i个簇是数据集x中所有距离Ci比其他Cj更近的点的集合（j≠x）。

k-means算法的优势在于它很简单：随机地选取一些数据点（k个）作为初始簇中心点，重复地把每一个点分配给离它最近的中心（质心），再根据新的分配方案重新计算簇中心。这个过程被称为Lloyd迭代过程，这种局部搜索方法不断迭代直到连续两轮内解都没有改变才停止。

尽管数据集的规模不断增大，k-means算法依然流行^[5]。因为其简单迭代的性质，大规模数据下的k-means算法相对容易实现。对于给定的一组簇中心，每一个点都可以独立地判断出哪个簇中心离它最近，从而分配给相应的簇。通过计算这些点的均值即可得到最优的簇中心。事实上，并行化的k-means算法的实现已经可以很容易地得到了（例如，参见cwiki.apache.org/MAHOUT/k-means-clustering.html ）。然而，从理论上说，kmeans算法在效率和质量上都不是一个好的算法：运行时间在最差情况下是指数级的［8，9］，并且最终结果是局部最优解，有可能和全局最优解差别很大（即使进行了重复随机初始化）^[6]。

初始化的过程决定了k-means算法最终是否能取得好的结果。已有研究者关注初始化过程改进，即更好地初始化簇中心可以在结果和收敛性质上都大幅改善Lloyd迭代过程。在这一研究方向上的一个很大突破是由Ostro-vsky等［10］和Arthur and Vassilvitskii［7］提出的。他们提出了一种简单的方法，既可以在理论上保证结果的质量，又可以借助于初始化结果来改进Lloyd迭代过程的运行时间。这种被称为k-means++的算法只从数据集中均匀随机地选取第一个簇中心，随后的每一个簇中心都依照它对前一轮选择下总误差的贡献值，以一定的概率比例被选取。直观上，这一初始化算法的依据是：“一个好的聚类结果相对来说更分散，因此在选择新的簇中心时应当倾向于选择那些远离之前簇中心的点”。k-means++初始化可以证明是对最优解的O（logk）近似［7］，或者当已知数据是可以被很好地聚类时是线性近似于最优解的。对k-means++以及后续改进［11，12， 13］的实验评估结果表明，当不仅希望在理论上，而且是在实际应用中取得一个好的解时，初始化结果对Lloyd迭代过程由决定性的作用。

k-means++算法可以得到一组被证明和最优解十分接近的初始簇中心集合，然而，k-means++（初始化）算法最大的不足之处在于它固有的顺序迭代性质，这限制了它在大规模数据上的应用，因为必须在数据上迭代k轮才能得到好的初始簇中心集合。即，在Rd空间内对n个点进行k-聚类时，尽管该算法的总运行时间是O（nkd），和简单Lloyd迭代过程一样，但它并不是可以很显然地并行化的。某个点被选取为第i个簇中心的概率严格地依赖于之前i—1个簇中心的挑选（之前的选择决定了哪些点离目前的中心最远）。 kmeans++原始实现需要对数据迭代k次来挑选初始簇中心点集。这一缺陷在大规模数据的使用场景中更为严重。首先，当数据集增大，簇的数量也随之增大。例如，将上百万的数据点聚类到k=100或是k=1000是很常见的，而k-means++初始化在这些情形下非常慢。当算法的剩余部分（例如Lloyd迭代过程）都可以在并行化环境下运行，例如MapReduce［13］，这种速度的降低就更为不利了。很多应用都需要一个既可以和k-means++一样有理论保证，又可以有效并行化的算法。

算法的主要思想是以可控的方式一个接一个地选择簇中心，当前选好的簇中心点集会随机地影响对下一个中心选择（算法1）。 k-means++算法的优势在于该初始化过程本身就能确保对Φ*有（8logk）的近似期望（在此基础上进行Lloyd迭代过程只能改进结果，但不能得到保证）。从可扩展性的角度来看，k-means++有一个明显缺陷，那就是它固有的顺序迭代性质：下一个簇中心的选取依赖于当前中心点集。

k-means聚类的目标是选取一组k个中心的C使得Φ（C）最小（简称为Φ）。将k-means聚类的最优解记为Φ*，找到Φ*是NP难问题［15］。如果φX（ C） ≤ αΦ* ，则称中心点集C是对k-means的α近似。第i个簇是数据集x中所有距离Ci比其他Cj更近的点的集合（j≠x）。

k-means算法的优势在于它很简单：随机地选取一些数据点（k个）作为初始簇中心点，重复地把每一个点分配给离它最近的中心（质心），再根据新的分配方案重新计算簇中心。这个过程被称为Lloyd迭代过程，这种局部搜索方法不断迭代直到连续两轮内解都没有改变才停止。

尽管数据集的规模不断增大，k-means算法依然流行^[5]。因为其简单迭代的性质，大规模数据下的k-means算法相对容易实现。对于给定的一组簇中心，每一个点都可以独立地判断出哪个簇中心离它最近，从而分配给相应的簇。通过计算这些点的均值即可得到最优的簇中心。事实上，并行化的k-means算法的实现已经可以很容易地得到了（例如，参见cwiki.apache.org/MAHOUT/k-means-clustering.html ）。然而，从理论上说，kmeans算法在效率和质量上都不是一个好的算法：运行时间在最差情况下是指数级的［8，9］，并且最终结果是局部最优解，有可能和全局最优解差别很大（即使进行了重复随机初始化）^[6]。

初始化的过程决定了k-means算法最终是否能取得好的结果。已有研究者关注初始化过程改进，即更好地初始化簇中心可以在结果和收敛性质上都大幅改善Lloyd迭代过程。在这一研究方向上的一个很大突破是由Ostro-vsky等［10］和Arthur and Vassilvitskii［7］提出的。他们提出了一种简单的方法，既可以在理论上保证结果的质量，又可以借助于初始化结果来改进Lloyd迭代过程的运行时间。这种被称为k-means++的算法只从数据集中均匀随机地选取第一个簇中心，随后的每一个簇中心都依照它对前一轮选择下总误差的贡献值，以一定的概率比例被选取。直观上，这一初始化算法的依据是：“一个好的聚类结果相对来说更分散，因此在选择新的簇中心时应当倾向于选择那些远离之前簇中心的点”。k-means++初始化可以证明是对最优解的O（logk）近似［7］，或者当已知数据是可以被很好地聚类时是线性近似于最优解的。对k-means++以及后续改进［11，12， 13］的实验评估结果表明，当不仅希望在理论上，而且是在实际应用中取得一个好的解时，初始化结果对Lloyd迭代过程由决定性的作用。

k-means++算法可以得到一组被证明和最优解十分接近的初始簇中心集合，然而，k-means++（初始化）算法最大的不足之处在于它固有的顺序迭代性质，这限制了它在大规模数据上的应用，因为必须在数据上迭代k轮才能得到好的初始簇中心集合。即，在Rd空间内对n个点进行k-聚类时，尽管该算法的总运行时间是O（nkd），和简单Lloyd迭代过程一样，但它并不是可以很显然地并行化的。某个点被选取为第i个簇中心的概率严格地依赖于之前i—1个簇中心的挑选（之前的选择决定了哪些点离目前的中心最远）。 kmeans++原始实现需要对数据迭代k次来挑选初始簇中心点集。这一缺陷在大规模数据的使用场景中更为严重。首先，当数据集增大，簇的数量也随之增大。例如，将上百万的数据点聚类到k=100或是k=1000是很常见的，而k-means++初始化在这些情形下非常慢。当算法的剩余部分（例如Lloyd迭代过程）都可以在并行化环境下运行，例如MapReduce［13］，这种速度的降低就更为不利了。很多应用都需要一个既可以和k-means++一样有理论保证，又可以有效并行化的算法。(www.xing528.com)

算法的主要思想是以可控的方式一个接一个地选择簇中心，当前选好的簇中心点集会随机地影响对下一个中心选择（算法1）。 k-means++算法的优势在于该初始化过程本身就能确保对Φ*有（8logk）的近似期望（在此基础上进行Lloyd迭代过程只能改进结果，但不能得到保证）。从可扩展性的角度来看，k-means++有一个明显缺陷，那就是它固有的顺序迭代性质：下一个簇中心的选取依赖于当前中心点集。

本小节介绍一种并行化地实现算法k-means||，该算法大幅地减少了迭代过程，并且，该算法和主流的并行化k-means的一些工作不同，那些工作更关注于k-means初始化之后的阶段。文献［6］指出，算法k-means||可以在对数级别的迭代次数内取得接近最优的解，并且在实际应用中，常数级别的迭代次数已经足够。在真实大规模数据上的实验评估结果也表明了k-means||在顺序和并行两种处理过程下都比k-means++表现更好。

以下对算法的原理进行描述。可以很容易地把随机初始化和k-means++初始化认为是两种解决问题的方式。前者以一种特定的概率一次性选择k个中心，采用的概率分布是均匀分布。后者进行k轮迭代，每一轮都以非均匀分布的概率选择一个新的点（也就是在每一个簇中心选择好之后不断地更新）。相比随机初始化，可以证明k-means++在不断进行非均匀选择的过程中结果会越来越好。理想上，希望汲取两种方法的优势：发现一种既能减少迭代次数，每一轮都以非均匀地概率选择不止一个点，同时又能得到可以证明的近似保证。kmeans||算法正是根据这一想法，通过规定迭代次数和非均匀分布概率，找到了最佳情形（即两者的最佳取舍）。尽管以上想法看上去很简单，想要找到一种可证明的解决方法（就像k-means++）存在很多挑战，其中的一些在对算法的分析中有直接的显现。现在，对算法进行描述。

尽管k-means||算法很大程度上受到k-means++的启发，不同之处在于，k-means||算法采用了一个采样因子l = Ω（k）。在算法中，首先选取一个初始簇中心（均匀随机选择），然后计算选定后的初始聚类代价Ψ。接着进行logΨ轮迭代，在每一轮迭代中，对于当前的簇中心集C，以ld2 （x， C）/Φx（C）的概率选取每一个点。被选取的点加入到C，更新Φx（C）的值，结束该轮迭代。接下去会看到，每一轮迭代选取的点的期望数量是l，且迭代过程结束后，C中点的期望数量是llogΨ，通常要大于k。为了减少簇中心数量，算法第7步将权重赋给C中的每个点，第8步将这些带权重的点重新聚类得到k个中心。算法的细节在算法2中进行描述。

本小节介绍一种并行化地实现算法k-means||，该算法大幅地减少了迭代过程，并且，该算法和主流的并行化k-means的一些工作不同，那些工作更关注于k-means初始化之后的阶段。文献［6］指出，算法k-means||可以在对数级别的迭代次数内取得接近最优的解，并且在实际应用中，常数级别的迭代次数已经足够。在真实大规模数据上的实验评估结果也表明了k-means||在顺序和并行两种处理过程下都比k-means++表现更好。

以下对算法的原理进行描述。可以很容易地把随机初始化和k-means++初始化认为是两种解决问题的方式。前者以一种特定的概率一次性选择k个中心，采用的概率分布是均匀分布。后者进行k轮迭代，每一轮都以非均匀分布的概率选择一个新的点（也就是在每一个簇中心选择好之后不断地更新）。相比随机初始化，可以证明k-means++在不断进行非均匀选择的过程中结果会越来越好。理想上，希望汲取两种方法的优势：发现一种既能减少迭代次数，每一轮都以非均匀地概率选择不止一个点，同时又能得到可以证明的近似保证。kmeans||算法正是根据这一想法，通过规定迭代次数和非均匀分布概率，找到了最佳情形（即两者的最佳取舍）。尽管以上想法看上去很简单，想要找到一种可证明的解决方法（就像k-means++）存在很多挑战，其中的一些在对算法的分析中有直接的显现。现在，对算法进行描述。

尽管k-means||算法很大程度上受到k-means++的启发，不同之处在于，k-means||算法采用了一个采样因子l = Ω（k）。在算法中，首先选取一个初始簇中心（均匀随机选择），然后计算选定后的初始聚类代价Ψ。接着进行logΨ轮迭代，在每一轮迭代中，对于当前的簇中心集C，以ld2 （x， C）/Φx（C）的概率选取每一个点。被选取的点加入到C，更新Φx（C）的值，结束该轮迭代。接下去会看到，每一轮迭代选取的点的期望数量是l，且迭代过程结束后，C中点的期望数量是llogΨ，通常要大于k。为了减少簇中心数量，算法第7步将权重赋给C中的每个点，第8步将这些带权重的点重新聚类得到k个中心。算法的细节在算法2中进行描述。

请注意C的规模要比初始输入的点集规模小得多，因此，可以很快完成重新聚类的过程。例如，在MapReduce中，因为中心点的规模很小所以可以在单个机器上运行，任何已证明可以近似的算法（例如k-means++）都可以用来重新聚类成k个中心。算法2的一种MapReduce实现在后面讨论。

因为算法非常简单，并且可以很自然地并行化实现（在logΨ轮迭代内），最具挑战的部分就是要证明其具备近似保证（证明请参见原文［6］）。

请注意C的规模要比初始输入的点集规模小得多，因此，可以很快完成重新聚类的过程。例如，在MapReduce中，因为中心点的规模很小所以可以在单个机器上运行，任何已证明可以近似的算法（例如k-means++）都可以用来重新聚类成k个中心。算法2的一种MapReduce实现在后面讨论。

因为算法非常简单，并且可以很自然地并行化实现（在logΨ轮迭代内），最具挑战的部分就是要证明其具备近似保证（证明请参见原文［6］）。

下面讨论k-means||算法在MapReduce计算框架下的并行实现（假设读者已经熟悉MapReduce模型了，并推荐各位阅读文献［16］来了解更多细节）。正如之前提到的，Lloyd迭代可以很容易地在MapReduce下并行，因而，只需要关注算法2中的第1～7步。第4步在MapReduce下很简单：每一个mapper都可以独立取样。对于给定的一组簇中心集合C，第7步同样很简单。给定一组（小规模）簇中心集合C，很容易计算Φx（C）：每一个mapper在一组输入点的划分X′X上计算（C），然后reducer可以很容易地将所有mapper得到的值相加，计算出Φx（ C）。这就帮助了第2步的计算，并且更新了第3～6步迭代过程所需要用到的φx（C）。

下面讨论k-means||算法在MapReduce计算框架下的并行实现（假设读者已经熟悉MapReduce模型了，并推荐各位阅读文献［16］来了解更多细节）。正如之前提到的，Lloyd迭代可以很容易地在MapReduce下并行，因而，只需要关注算法2中的第1～7步。第4步在MapReduce下很简单：每一个mapper都可以独立取样。对于给定的一组簇中心集合C，第7步同样很简单。给定一组（小规模）簇中心集合C，很容易计算Φx（C）：每一个mapper在一组输入点的划分X′X上计算（C），然后reducer可以很容易地将所有mapper得到的值相加，计算出Φx（ C）。这就帮助了第2步的计算，并且更新了第3～6步迭代过程所需要用到的φx（C）。

请注意，这里默认假设了簇中心点集C足够小，可以存储在内存中或是在所有mapper中分布存储。在大多数实际应用中这一假设可以满足，就算没有这个假设，上述过程也是可以在MapReduce中实现的。每一个mapper都拥有一组子集X′ x和C′ C，它可以输出一组元祖＜x；argMinc∈Cd（ x，c）＞，其中x ∈X′是键。由此，reducer可以很容易地′计算出的（d， C）还有ΦX（C）。（注：在这一过程中减少mapper的中间输出数量是一个很值得研究的方向。）

请注意，这里默认假设了簇中心点集C足够小，可以存储在内存中或是在所有mapper中分布存储。在大多数实际应用中这一假设可以满足，就算没有这个假设，上述过程也是可以在MapReduce中实现的。每一个mapper都拥有一组子集X′ x和C′ C，它可以输出一组元祖＜x；argMinc∈Cd（ x，c）＞，其中x ∈X′是键。由此，reducer可以很容易地′计算出的（d， C）还有ΦX（C）。（注：在这一过程中减少mapper的中间输出数量是一个很值得研究的方向。）