0 引言

聚类是一种重要的数据分析技术, 旨在将数据集划分成不同的子集, 并且同一个子集中的数据具有较高相似度.聚类在许多领域都受到广泛应用, 包括机器学习、数据挖掘、模式识别、信息检索等.经过研究者多年的研究, 众多聚类性能高效的聚类算法相继被提出, 包括基于划分的聚类^[1]、层次聚类^[1]、密度聚类^[2]、模糊聚类^[3]等.

聚类具有广泛的应用背景, 在分布式数据管理系统中, 集群中每台计算机负责的数据分块可以由聚类算法来决定, 聚类使处于相同计算节点中的数据具有较高的相似性, 降低了集群中计算机之间由于大量通信造成的性能消耗.然而, 传统聚类算法通常未对簇可包含的数据点数目上限或者下限做出限定, 所以生成的数据块平衡性往往较差, 容易出现某些数据块过大或者过小情形, 往往会降低分布式数据管理系统的整体性能.因此, 如何在聚类过程中进一步约束簇的平衡性, 将所有簇的大小约束在一定的阈值范围内, 这具有重要的应用价值.

目前, 已提出的平衡约束聚类方法普遍存在以下两点不足: ①算法的复杂度普遍较高.由于许多平衡约束聚类方法是基于$K$-Means进行的改进, $K$-Means计算$K$个合适中心点的过程是一种典型的NP-Hard过程, 若要在多项式时间内求得较好的聚类中心点, 需要对聚类过程采用一定的加速策略, 否则会出现算法的运行时间过长, 多项式时间内取得的聚类结果质量不高的情况.近些年提出的2种平衡约束聚类算法Balanced $K$-Means(BKM)^[4]与BCLS^[5]的时间复杂度分别为$O(tn^{3})$与$O(tn^{2})$, 其中$t$为算法的迭代次数, 在较大规模数据集上聚类的效率有待进一步提升. ②簇可包含数据点数目不支持用户自定义.簇可包含数据点数目上限的不可控将导致聚类结果的平衡度不可预测, 在已提出的平衡聚类算法中, 只有极少数的平衡聚类算法支持用户自定义簇中最多可包含的数据点个数.由于在实际应用场景中的应用需求具有复杂性特点, 一种聚类算法若只能产生绝对平衡或者聚类结果的平衡度不可控, 算法的通用性将会降低.因此, 平衡约束聚类对簇平衡度的约束程度应支持用户自定义, 满足不同应用场景下的实际需要.

针对上述的现有平衡约束聚类算法普遍存在的问题, 本文提出了一种基于$K$-Means的平衡约束聚类算法.该算法对$K$-Means中数据点的分配策略进行了改进, 当数据点尝试加入至某个簇时, 首先检查该簇中数据点个数是否已经达到用户先前设置的上限, 若簇中数据点个数还未达到上限, 将数据点直接加入到簇中.若簇中数据点个数已经达到上限, 则将该数据点与簇中心点的距离和簇边界点与中心点的距离相比较:若该待加入数据点更靠近簇中心点则将簇当前的边界点踢除, 将该数据点加入簇中; 若簇当前的边界点更靠近中心点, 则数据点尝试加入其他簇.

本文的主要贡献包括:

(1) 提出了一种基于$K$-Means的平衡约束聚类算法, 该算法具有简单、快速的特点;

(2) 提出的平衡约束聚类算法可以约束每个簇最多可包含的数据点个数, 同时支持用户自定义数据点数目上限, 算法具有一定的通用性;

(3) 在6个UCI真实数据集上与其他聚类算法进行比较了三项聚类评价指标(包括一项平衡性), 实验结果表明本文提出的平衡约束聚类算法相比其他平衡约束聚类算法更加高效, 而且能够保证聚类结果的平衡性.

1 相关工作

根据数据划分的方式将现有的平衡约束聚类方法分为2类:硬平衡划分方法与软平衡划分方法.两者的区别在于算法是否对划分出的数据块规模进行严格控制.在所有的平衡划分方法中, 绝大多数算法划分数据都是通过聚类来实现.硬划分方法由于方法的局限性, 总体数量不多, 在Bradley等^[6]提出的方法中, 通过对每个簇中元素个数设置下限来避免在算法执行过程中产生过小簇. Malinen等^[4]对Bradley等的工作提出了改进, 在聚类开始阶段先构造一个由$N$个数据点以及$N$个slot构成的二部图, 将$N$个slot进行$K$等分形成$K$个组, 在数据点分配阶段, 使用匈牙利算法^[7]将$N$个数据点分配到$N$个slot中, slot中的每个组即对应结果中的一个簇, 该方法仅仅适用于有硬划分需求的应用场景.

相较于硬划分方法而言, 软数据划分方法仅将划分后的数据块平衡性列为一个较重要的约束指标, 最终的平衡性可能非常靠近硬划分的理想状态但很难真正达到.具体措施是通过设置Loss function中的正则化参数来约束结果的平衡性.在WU等^[8]提出的方法中, 首先将数据块分为若干个RSG, 随后根据定义的Loss function将不同的RSG进行合并, 合并在一起的RSG将被分配至相同的节点计算机. Banerjee等^[9]设计了一个由三个步骤组成的平衡聚类算法, 在数据点分配阶段将每个簇中已有数据个数纳入数据点加入簇的代价计算公式中, 另外算法基于stable marriage problems问题的思路解决点分配中的稳定性问题.在Banerjee等^[10]另一个工作中实现了用户可以预先自定义设置簇的平衡度. Liu等^[5]的工作中, 在Loss function中引入对簇平衡性惩罚因子来约束聚类结果的平衡性, 并使用增广拉格朗日乘子加速算法收敛.

2 问题定义

给定数据集$T=\{x_{i}\vert i=1, 2, 3, \cdots, N\}$, 其中$N$为数据集中数据个数, 目标数据块数目为$K$.平衡约束聚类将根据预先定义的距离将数据集$T$平衡地划分为$K$个簇, 每个簇都具有一个中心点, 共有$K$个中心点, 记为${C=}\{\mu _j {\vert }j=1, 2, 3, \cdots , {K}\}$, 聚类结果中所有的簇信息存储在$cd={\{}d_{1}, d_{2, \cdots , }d_{K}{\}}$中, $d_{i}={\{}x_{i}\vert i=1, 2, 3, {\cdots}, g{\}}$表示第$i$个簇中所有的数据点. $t(d_{i})$表示第$i$个簇可包含的数据点个数阈值, 如式(1)所示, 其中, $\tau$为簇中数据点个数上限.

$ \label{eq1} t\left( {d_i } \right)=\vert \vert d_i \vert \vert \le \tau, i=1, 2, 3, \cdots, {K}. $

(1)

平衡约束聚类的任务在于所有簇在满足上限阈值的情况下, 数据集中所有的点到其所在的簇平均代价最低, Loss Function如公式(2)所示.

$ \begin{array}{l} MSE(x_1 , \cdots, x_N , \mu _1 , \cdots, \mu _K )=\frac{1}{N}\sum\limits_{i=1}^N {\phi (x_i , \mu _{{\rm e}^{(i)}} )} , \\ \quad \quad \quad \vert \vert d_i \vert \vert \mbox{ }\le \tau, i=1, 2, 3, \cdots, {K}. \end{array} $

(2)

其中$\phi (x_i , \mu _{{\rm e}^{(i)}} )$用于计算数据点$x_i $分配至簇$\mbox{e}^{(i)}$产生的损失值, $\mu _K $表示第$K$个簇的中心, e$^{(i)}$表示$T$中第$i$个数据点被分配到的簇.

3 基于$K$-Means的平衡约束聚类算法

在$K$-Means算法的每次迭代过程中, 每个数据点首先计算至$K$个簇中心点的距离, 随后直接加入与其最接近的簇中.在此过程中, 并没有考虑每个簇中已有的数据点个数, 同时也没有考虑簇中已存在的数据点距离中心点的距离与待加入点与中心点之间距离的大小关系.假设在$K$-Means每次迭代中仅对簇包含的数据点个数上限进行限制, 我们发现这样进行聚类会发生严重的"错分配"问题.

假设在$K$-Means聚类的每次迭代过程中对簇包含的数据点个数上限进行了限制, $K$-Means的思路是将所有数据点分配到最近簇, 由于算法每次随机从数据集的剩下点中选取出一个数据点对其分配簇.若此时即将被分配新数据点的簇中已有数据点个数还未达到上限, 因为不会破坏簇的平衡性, 数据点可以成功加入到最近的簇中.若此时某个簇中的数据点总数已达到所设定的上限, 则其他的数据点将无法加入到簇中, 即使当前待加入的点比簇中所有的点距离中心点都要近.因此, 若不对分配规则进行进一步修改可能会造成严重的聚类错误.

针对上述分析的平衡约束聚类中可能出现的问题, 我们提出了一种基于$K$-Means的平衡约束聚类算法, 该算法不仅简单、高效, 同时支持用户自定义簇中可包含的数据点总数上限, 满足不同应用场景下的数据平衡划分需求.

本文提出的平衡约束聚类算法首先计算出每个数据点与$K$个簇中心点的距离, 接着对$K$个簇按照由近到远排序得到$\mbox{STC}=\{\gamma _j \vert j=1, 2, 3, \cdots , {K}\}$.首先尝试加入簇$\gamma _1 $, 当尝试将点加入簇$\gamma _j $中时, 若$\vert \vert d_{\gamma _j } \vert \vert \le \tau $, 将$x_{i}$加入到簇$\gamma _j $中, 否则进一步判断簇$\gamma _j $.簇$\gamma _j $的边界点与中心点的距离记为$radius_{\gamma _j } $, 若$radius_{\gamma _j } $大于$x_{i}$与簇$\gamma _j $中心点的距离, 将$x_{i}$加入簇$\gamma _j $, 踢除边界点z, 重新分配点z的簇(边界点即为簇中与中心点距离最远的点); 否则使用相同策略考虑加入簇$\gamma _{j{+}1} $, 直至成功添加进某个簇.

$ \left\{ {{\begin{array}{*{20}c} {x_i 分配至簇\gamma _j , \quad\vert \vert d_{\gamma _j } \vert \vert\le\tau } \hfill \\ {进一步判断簇\gamma _j , \quad\vert \vert d_{\gamma _j } \vert \vert >\tau } \hfill \\ \end{array} }} \right., $

(3)

$ \left\{ {{\begin{array}{*{20}c} {x_i分配至簇\gamma _j\mbox{并移除簇 }\gamma _j 的边界点, \quad radius_{\gamma _j } >d(\mu _{\gamma _j } , x_i )} \hfill \\ {尝试加入簇\gamma _{j{+}1} , \quad radius_{\gamma _j } \le d(\mu _{\gamma _j } , x_i )} \hfill \\ \end{array} }} \right.. $

(4)

上述的平衡约束聚类的过程如算法1所示.

在算法1中, AddtoNearestCluster($x_{i})$函数表示将数据点$x_{i}$分配至合适的簇, CS$_{j}$存储第$j$个簇中已有的数据点及其距离中心点的距离.算法1首先在数据集中随机确定$K$个数据点作为聚类初始点, 随后对数据集中$N$个数据分别使用AddtoNearestCluster函数将每个数据点加入到合适的簇. AddtoNearestCluster函数的参数为数据集中的每一个数据点$x_{i}$, AddtoNearestCluster函数首先计算$x_{i}$与每个簇中心点的距离, 按照由近到远排序后存入STC={$\gamma _j \vert j=1, 2, 3, \cdots, K$}中.然后, 按照由近到远顺序尝试加入到SC中的某一个簇中.如果$\gamma _j $簇中当前数据点个数未达到所设上限$\tau $, 则将数据点$x_{i}$直接加入到簇中.若簇$\gamma _j $中数据点个数已达到上限, 则比较簇$\gamma _j $当前边界节点离中心点的距离与$x_{i}$离簇$\gamma _j $中心点的距离.若$x_{i}$离中心点更近, 则将簇$\gamma _j $当前边界节点踢除, 点$x_{i}$加入簇$\gamma _j $.若$x_{i}$离中心点更远, 则运用相同的策略尝试将$x_{i}$加入到簇$\gamma _{j{+}1} $中, 直到$x_{i}$成功添加至某个簇.其中, 对于算法迭代过程中被从簇中踢除的边界点, 也使用AddtoNearestCluster函数对其重新分配簇.算法直到簇中心不发生变化或达到最大迭代次数停止迭代.

4 时间复杂度分析

本文提出的基于$K$-Means的平衡约束聚类算法通过对$K$-Means中的数据点分配策略进行修改, 每个数据点首先计算与$K$个中心点的距离, 复杂度为$O(K)$, 若簇还未满则直接添加进簇中, 该过程与$K$-Means相同.若簇中数据点个数已经到达上限, 随后将其与中心点的距离与簇边界点与中心点的距离相比较, 此处的时间复杂度为$O$(1), 若满足添加条件则加入该簇, 被踢出的点使用同样的方法重新分配簇.若不满足添加条件则继续尝试其他簇.最差情况为所有的点都需要尝试$K$次才能添加到合适的簇中, 因此时间复杂度最差的情况下为$O(tk^{2}n)$, 其中$t$为算法的迭代次数.

5 实验

本节我们将提出的平衡聚类算法与其他5种聚类算法相比较, 分别是K-Means(KM)^[1]、Fuzzy C-means(FCM)^[3]、Spectral Clustering(SC)^[11]、Balanced $K$-Means^[4]和BCLS^[5].其中KM和SC都是被广泛使用的经典聚类算法, FCM是一种非常高效的模糊聚类算法, Balanced $K$-Means与BCLS是据我们所知两种效果较好的平衡约束聚类算法, Balanced $K$-Means是一种基于$K$-Means的硬平衡约束聚类算法, BCLS是一种在目标函数优化基础上提出的平衡约束聚类算法.

5.1 实验设置

数据集与预处理本实验选取了6个UCI真实数据集, 分别是Wine、Lonosphere、Iris、Cryotherapy、User Model和Vechicel.为了更好地测试每个算法的平衡聚类性能, 将所有数据集中每种类别的数据个数删减至相同, 即在平衡的数据集下聚类测试聚类结果的平衡度, 这与文献[5]中的实验设置类似.调整后的每个数据集信息如下: Wine中数据总数144, 包含3类; Lonosphere中数据总数252, 包含2类; Iris中数据总数150, 包含3类; Cryotherapy中数据总数84, 包含2类; User Model中数据总数200, 包含4类; Vechial中数据总数796, 包含4类.本实验中每个簇可以包含的数据点个数上限设置为$\frac{N}{K}$.

评价体系    本文使用平衡约束聚类常用的三种评价方法对提出的方法进行评估.

(1) 准确率(Accuracy, ACC)^[12].该指标衡量数据所有数据元素在聚类后的标签相较于先验知识中真实标签的准确率, 如式(5)所示.

$ \label{eq5} {\rm ACC=}\frac{\sum\limits_{i=1}^{N} \delta ( s_{i} , {\rm map}(r_{i} ))} {N}. $

(5)

其中, $N$为数据集中元素总数, 若$s_{i}$=map$(r_{i})$, $\delta$函数值为1, 否则为0. map为一个映射函数, 将聚类结果的数据标签映射至原数据集中相应的标签, $s_i$为先验知识中数据的原始标签.

(2) 归一化互信息(Normalized Mutual Information, NMI)^[13], 用于评价聚类结果与数据集原分布近似程度, 如式(6)所示.

$ \label{eq6} {\rm NMI}(X, Y) =\frac{I(X, Y)}{\sqrt {{H(X)H(Y)}} }. $

(6)

其中, $I(X, Y)$表示分布$X$与$Y$的互信息, $H(X)$表示分布$X$的信息熵.

(3) 标准信息熵(Normalized Entropy, $N_{\rm entro}$)^[5], 用于衡量簇之间的平衡度, 值越接近1表示所有簇之间越平衡, 计算公式如式(7)所示.

$ {N}_{{\rm entro}}{=-}\frac{{1}}{{\rm log}_2 { c}}\sum\limits_{{ k=1}}^{c} {\frac{{r}_{k}}{{ N}}{\rm log}_2 } \frac{{r}_{k} }{{N}}. $

(7)

其中, $r_{k}$表示第$K$个簇中的数据点个数.

5.2 实验结果与分析

实验中每个算法的聚类结果质量及其平衡性如表 1所示.

由表 1可知, 本文提出的平衡约束聚类算法的聚类表现整体优于其他5种聚类算法, 在保证了聚类结果平衡性的同时聚类结果也具有较高的质量.在表 1的6种聚类算法中, BKM、BCLS和本文提出的平衡约束聚类算法结果的平衡性效果较好.其中, 在Lonosphere、Iris、User Model、Vechicle数据集上本文提出的聚类算法的表现均优于BCLS; 在Wine、Cryotherapy、User Model、Vechicle数据集上本文所提出的算法表现均优于BKM. BKM作为一种基于匈牙利分配的硬平衡聚类算法, 其聚类结果可以保证绝对均衡的效果, 但对提高聚类结果质量未采取进一步措施, 因此除标准信息熵以外的评价指标略低; BCLS通过优化代价函数来达到平衡约束的目的, 其聚类结果的平衡性往往较难达到绝对均衡, 而其他聚类评价指标的表现略好.同时, 由图 1可知本文提出的平衡约束聚类算法相较其他算法具有较高的时间性能.本文提出的平衡约束聚类算法针对平衡约束的特点对$K$-Means进行了改进, 当簇中数据点个数达到上限时, 新数据点通过试探性地尝试与簇边界点交换位置, 因此不仅保证了结果的簇与$K$-Means一样具有较好的内聚性, 同时约束了簇的平衡性.

6 结论

平衡约束聚类是分布式数据管理中数据划分常用的技术, 在实际应用中通常要求划分后的数据块能够尽可能平衡, 从而提高分布式数据管理系统的整体性能.本文提出了一种基于$K$-Means的平衡约束聚类算法, 该算法对$K$-Means中每个簇包含的数据点个数上限进行设置, 并更改了分配策略, 每个簇将与其最近的有限个点加入簇中.该算法具有较低的时间复杂度并且支持用户自定义簇中可包含的数据点个数上限, 满足了不同应用场景下的平衡约束聚类需求.在6个UCI真实数据集上实施的对比实验结果表明, 我们提出的平衡约束聚类算法不仅比其他平衡聚类算法高效, 而且能够保证聚类结果的平衡性.在之后的工作中, 我们可能会将提出的平衡约束聚类算法应用于分布式RDF数据管理系统集群计算机的数据分配.