LIN Peng_DistributedKmeans_2018

标题：Distributed Consensus-Based K-Means Algorithm in switching multi-agent networks
作者：LIN Peng ·WANG Yinghui ·QI Hongsheng ·HONG Yiguang
机构：Journal of Systems Science and Complexity volume
引用：Lin P, Wang Y, Qi H, et al. Distributed consensus-based k-means algorithm in switching multi-Agent networks[J]. Journal of Systems Science and Complexity, 2018, 31: 1128-1145.

研究问题Research Question

科学问题Science Question

• 许多聚类算法，如$K-means$等，基本上都是集中式的。然而，快速增多的数据和大规模网络所带来的挑战，使得不得不在网络上的不同智能体之间存储和处理数据。例如，在网络监控、无线传感器网络或分布式数据库中，数据便是分布在网络上的。

研究核心Core of the research

• 本文讨论了在交换式多智能体网络中基于$K-means$算法的分布式聚类设计，适用于数据分散存储且数据无法被所有智能体都获得的情况。

• 作者提出了一种分布式情况下基于共识的算法，即基于双时钟共识的$K-means$算法（$DCKA$）。

• 在温和的连接条件下，作者证明了$DCKA$的收敛性，以保证聚类问题的分布式解决方案，即使网络拓扑结构是时变的。

研究意义Research significance

• 由于可扩展性、鲁棒性和低成本性，多智能体网络中的分布式算法近年来备受关注。但智能体很难在大规模网络中直接获取所有信息，网络中的每个智能体只能基于与邻居之间的信息交换或局部测量来实现全局目标。为了保证所有智能体都为同一个目标工作，基于共识的算法在分布式控制、估计和优化领域得到了普及。

• 网络连通性在实现多智能体协调和使分布式算法/方法适合或有效处理大数据或复杂网络结构方面发挥着至关重要的作用。

• 近年来，机器学习由于在知识发现、模式识别和数据挖掘中的各种应用引起了越来越多的研究关注。 数据聚类是用于数据分析的无监督机器学习问题之一，自从提出有效地将数据划分为小的集群以来，它也被大量研究并广泛应用于许多领域。基于数据之间的相似性，分区聚类算法（与分层算法相反）成为重要的研究课题，部分原因是这些算法可以同步获得所有聚类，而不需要分层结构。例如，$K-means$算法是最流行的分区聚类算法之一，以其简单性和快速收敛速度而闻名。

现有算法的不足Shortcomings of existing algorithm

• 大多数现有的分布式 $K-means$算法都是针对固定拓扑提出的，并且是在仿真的基础上进行分析，该类算法在链路故障或交换网络连接的情况下可能会失败。

结论Conclusion

• 本文讨论了多智能体网络的$K-means$聚类问题，并针对数据存储在不同智能体或所有智能体不可用的情况，提供了一种全分布式算法。

• 作者提出了一种基于双时钟共识的$K-means$聚类算法（$DCKA$）来解决聚类问题，通过使智能体在没有全局信息的情况下在共同连接的拓扑结构上达成共识。此外，作者还给出了该算法的收敛性分析，并通过使用各种真实的聚类数据集提供实例，以证明所提出的分布式算法的有效性。

---

理论与方法Theory and Method

图论

• $\mathcal{G}=(\mathcal{V}, \mathcal{E})$，表示一个在$N$个智能体之间共享拓扑的图

  • $\mathcal{V}={1,2, \cdots, N}$，表示智能体的集合

  • $\mathcal{E} \subset \mathcal{V} \times \mathcal{V}$，表示智能体之间的通信链路的集合

    • 如果智能体$i$可以直接从智能体$h$接收信息，则存在从$h$到$i$的有向边，记为$(h, i) \in \mathcal{E}$

    • 将智能体$i$的一度邻居表示为$\mathcal{N}_{i}=\{h \mid(h, i) \in \mathcal{E}\}$

    • 若$(h, i) \in \mathcal{E}$且$(i, h) \in \mathcal{E}$，则称图$\mathcal{G}$为无向图

• 一条长度为$p$的有向路径是一个非空图 $\mathcal{P}=\left(\mathcal{V}_{p}, \mathcal{E}_{p}\right)$ ，形式为 $\mathcal{V}_{p}=\left\{i_{1}, i_{2}, \cdots, i_{p+1}\right\} \subseteq \mathcal{V}$，$\mathcal{E}_{p}=\left\{\left(i_{1}, i_{2}\right),\left(i_{2}, i_{3}\right), \cdots,\left(i_{p}, i_{p+1}\right)\right\} \subseteq \mathcal{E}_{p}$，其中$i*{k} s$都是不同的

• 如果对于任意对$i, h \in \mathcal{V}$，图$\mathcal{G}$存在有向边，则称图$\mathcal{G}$是强连通的

• 图$\mathcal{G}(s)=(\mathcal{V}, \mathcal{E}(s))$表示在时间上智能体之间的时变通信拓扑，$\mathcal{G}(s)$的邻接矩阵记为$A(s) \in \mathcal{R}^{N \times N}$，其元素定义如下：

  1. $a_{i, h}(s)>0$，表示$(h, i) \in \mathcal{E}(s)$，同时也包括智能体$i$本身即$a_{i, i}(s)>0$

  2. $a_{i, h}(s)=0$，表示智能体$h$没有与智能体$i$直接连通

集中式聚类

• 集中式$K-means$算法（$CKA$）是一种两步骤（分配步骤和细化步骤）的迭代方法。

• 用$C(t)=\left\{c_{1}(t), c_{2}(t), \cdots, c_{K}(t)\right\}$表示时间$t$时的$K$个中心点，集中式聚类算法通过$K$个随机中心点$C(0)$或仅有一个随机中心点的$K-means++$算法来进行。

• 在划分步骤中，每个数据点$y^j_i$被分配到可以由最近的中心点代表的聚类中，即

  $$\theta_{i, k}^{j}(t+1)=\underset{\theta \in \mathcal{D}}{\arg \min } \sum_{i=1}^{N} \sum_{j=1}^{ m_{i} } \sum_{k=1}^{K} \theta_{i, k}^{j}\left|y_{i}^{j}-c_{k}(t)\right|^{2}$$

  换句话说，即

  $$\theta_{i, k}^{j}(t+1)=\left\{\begin{array}{ll}1, & \text { if } y_{i}^{j} \in \text { Cluster } k \\ 0, & \text { if } y_{i}^{j} \notin \text { Cluster } k .\end{array}\right.$$

  $\sum_{i=1}^{N} \sum_{j=1}^{m_{i}} \theta_{i, k}^{j}(t+1)$和$\sum_{i=1}^{N} \sum_{j=1}^{m_{i}} \theta_{i, k}^{j}(t+1) y_{i}^{j}$分别代表了数据点的大小和数据点的总和，这些数据点在时间$t+1$时属于第$k$个集群。

  为了简单起见，定义：

  $$m_{k}(t+1)=\sum_{i=1}^{N} \sum_{j=1}^{m_{i}} \theta_{i, k}^{j}(t+1),\\u_{k}(t+1)=\sum_{i=1}^{N} \sum_{j=1}^{m_{i}} \theta_{i, k}^{j}(t+1) y_{i}^{j}$$

• 在细化步骤中，$K$个中心点被每个集群中的新中心点所更新，即

  $$c_{k}(t+1)=\frac{\sum_{i=1}^{N} \sum_{j=1}^{m_{i}} \theta_{i, k}^{j}(t+1) y_{i}^{j}}{\sum_{i=1}^{N} \sum_{j=1}^{m_{i}} \theta_{i, k}^{j}(t+1)}=\frac{u_{k}(t+1)}{m_{k}(t+1)}, \quad k=1,2, \cdots, K$$

• 集中式聚类算法保证了获得局部最优解。

• 在集中式聚类算法中，算法需要得知全局或集中的信息。

  但如果数据点在空间上分布或有不同的智能体收集，集中式的形式可能就不再适用了。

假设

时变网络又称为联合连通网络

假设一

• 假设图$\mathcal{G}(s)=(\mathcal{V}, \mathcal{E}(s))$的加权邻接矩阵$A(s)$满足：

  1. $A(s)$是双随机的

     随机矩阵：每一项均为非负的并且每行的和均为1的方阵
     双随机矩阵：每一列的和均为1的随机矩阵

  2. 对于所有的 $i \in \mathcal{V}$，有 $a_{i, i}(s) \geq \varepsilon$ 且 $a_{i, h}(s) \geq \varepsilon \ if\ (h, i) \in \mathcal{E}(s)$ ，其中 $\varepsilon$ 是一个正标量

假设二

• 若图$\mathcal{G}(s)=(\mathcal{V}, \mathcal{E}(s))$是联合连通的，则$(\mathcal{V}, \mathcal{E}(s)\cup \mathcal{E}(s+1) \cup \cdots \cup \mathcal{E}(s+\tau-1))$对于所有的$s \geq 0$和某个整数$\tau>0$是强连通的

• 该假设确保了尽管网络拓扑正在切换并且可能不会在每个时刻都连接，每个代理$i$在每个$\tau$周期内至少可以从所有邻居那获取信息一次，

• 在以上两个假设的前提下，对于所有的$i,\ h$和所有的$s_{1} \geq s_{2}$，有

$$\left|\left[\varphi\left(s_{1}: s_{2}\right)\right]_{i, h}-\frac{1}{N}\right| \leq \zeta^{-2} \varrho^{s_{1}-s_{2}+1}$$

• 其中，$\zeta=1-\frac{\varepsilon}{4 N^{2}}，\varrho=\zeta^{1 / \tau}$，$\varphi\left(s_{1}: s_{2}\right)$是一个由$\varphi\left(s_{1}: s_{2}\right)=A\left(s_{2}\right) A\left(s_{2}+1\right) \cdots A\left(s_{1}\right)$定义的转移概率矩阵，$\varphi\left(s_{1}: s_{1}\right)=A\left(s_{1}\right)$

  转移概率矩阵（跃迁矩阵）

  • 定义：矩阵各元素都是非负的，且各行元素值和为1，各元素用概率表示，在一定条件下是互相转移的。$P^{(k)}$表示$k$步转移概率矩阵

  • 特征：

    1. $0≤P_{ij}≤1$

    2. $\displaystyle \sum_{j=1}^{n} P_{ij}=1$，即矩阵中每一行的转移概率之和为1

  • 有转移概率组成的矩阵称为转移概率矩阵，即构成转移概率矩阵的元素是转移概率

  马尔可夫过程

  • 马尔可夫性（无后效性）

    在过程或系统在时刻$t_0$所处的状态为已知的条件下，过程在时刻$t>t_0$所处状态的条件分布，与过程在时刻$t_0$之前的状态无关的特性

    即过程“将来”的情况与“过去”的情况是无关的

  • 马尔可夫过程的定义

    具有马尔可夫性的随机过程称为马尔可夫过程

    用分布函数表述马尔可夫过程：

    待补充……

分布式聚类

相关说明

• 对于每个智能体$i \in \mathcal{V}$，训练集$Y_{i}=\left[y_{i}^{1}, y_{i}^{2}, \cdots, y_{i}^{m_{i}}\right] \in \mathcal{R}^{n \times m_{i}}$是可获得的，其中，$n$是数据的维度，$m_i$是数据的大小，$Y=\left[Y_{1}, Y_{2}, \cdots, Y_{N}\right]$为整个数据集。

• 智能体$i$的目的是根据$K-means$的聚类准则将数据集$Y_i$划分成$K$个集群$\left[Y_{i}^{1}, Y_{i}^{2}, \cdots, Y_{i}^{K}\right]$。

• 智能体$i$所获得的表示集群的$K$个中心点可能并不属于数据集。

• 令$c_k$表示第$k$个质心，$C=\left\{c_{1}, c_{2}, \cdots, c_{K}\right\}$是$K$个中心点的集合。

• 智能体$i$的$K-means$聚类问题，可表述如下：

  $$\min *{\theta \in \mathcal{D}*{i}, C} f_{i}\left(Y_{i}, C, \theta_{i}\right)=\sum_{j=1}^{m_{i}} \sum_{k=1}^{K} \theta_{i, k}^{j}\left|y_{i}^{j}-c_{k}\right|^{2}$$

  其中，

  $$\begin{aligned} \mathcal{D}_{i}=\left\{\theta_{i, k}^{j}:\right.& \sum_{k=1}^{K} \theta_{i, k}^{j}=1, j=1,2, \cdots, m_{i} \\ &\left.\theta_{i, k}^{j}=\{0,1\}, k=1,2, \cdots, K, j=1,2, \cdots, m_{i}\right\} \end{aligned}$$

  而$\theta_{i}=\left\{\theta_{i k}^{j}, k=1,2, \cdots, K, j=1,2, \cdots, m_{i}\right\}$，且数据点之间的相似性通过欧几里得范数来衡量

  范数

  L1范数：向量中各个元素绝对值之和

  $$\|\mathbf{x}\|_1=\sum_{i=1}^n|x_i|$$

  L2范数（欧几里得范数/欧氏距离/L2距离）：向量元素的平方和再开方

  $$\|\mathbf{x}\|_2=\sqrt{\sum_{i=1}^nx_i^2}$$

• 在分布式聚类学习中，智能体的目的是将数据集$Y$划分成$K$个集群 $\left[Y^{1}, Y^{2}, \cdots, Y^{K}\right]$ 并且最小化数据点和聚类中心点之间的距离平方和

• 所有智能体所得到的$K$个中心点应该是相互一致的（不太懂是什么意思）

• 分布式$K-means$聚类问题，可表达如下：

  $$\min *{\theta \in \mathcal{D}, C} F(Y, C, \theta)=\sum*{i=1}^{N} f_{i}\left(Y_{i}, C, \theta_{i}\right)（4）$$

• 假设每个智能体都“知道”$K$值，若未知，则可使用文献[31]中提出的方法来估计$K$值

基于双时钟共识的K-Means算法

• 为了解决问题（4），定义$C_i(t)$为中心点的集合，这些中心点是由智能体$i$在时间$t$获得的。根据集中式$K-means$聚类算法，给定$C_i(t)$，$θ_i(t+1)$可以通过以下公式进行分配

  $$\theta_{i, k}^{j}(t+1)=\underset{\theta_{i} \in \mathcal{D}*{i}}{\arg \min } \sum*{i=1}^{m_{i}} \sum_{k=1}^{K} \theta_{i, k}^{j}\left|y_{i}^{j}-c_{i, k}(t)\right|^{2}$$

  即

  $$\theta_{i, k}^{j}(t+1)=\left\{\begin{array}{ll}1, & \text { if } y_{i}^{j} \in \text { Cluster } k \\ 0, & \text { if } y_{i}^{j} \notin \text { Cluster } k\end{array}\right.（9）$$

  显然，$\sum_{j=1}^{m_{i}} \theta_{i, k}^{j}(t+1)$代表在时间$t+1$的第$k$个集群中属于智能体$i$的数据大小，表示为

  $$m_{i, k}(t+1)=\sum_{j=1}^{m_{i}} \theta_{i, k}^{j}(t+1)（10）$$

  设$M_i(t+1)$作为$m_{i,1}(t+1)$的集合，那么一个新的局部求和$u_{i,k}(t + 1)$可以通过以下方式得到

  $$u_{i, k}(t+1)=\sum_{j=1}^{m_{i}} \theta_{i, k}^{j}(t+1) y_{i}^{j}（11）$$

  因此，全局中心点被重写如下：

  $$c_{k}(t+1)=\frac{\sum_{i=1}^{N} u_{i, k}(t+1)}{\sum_{i=1}^{N} m_{i, k}(t+1)}, \quad k=1,2, \cdots, K（12）$$

  表示为$x_{i, k}(0, t)=\operatorname{col}\left\{x_{i, k}^{1}(0, t), x_{i, k}^{2}(0, t)\right\}$，其中，

  $$\left\{\begin{array}{l}x_{i, k}^{1}(0, t)=u_{i, k}(t) \\ x_{i, k}^{2}(0, t)=m_{i, k}(t)\end{array}\right.（13）$$

  在算法的每次迭代中，智能体$i$通过以下三个步骤更新其中心点：

  1. 本地$K-means$步骤

     智能体$i$根据（9）、（10）和（11）分别计算$θ^{j}*{i,k}(t + 1)$、$m*{i,k}(t + 1)$和$u_{i,k}(t + 1)$。

  2. 共识步骤

     在一个信息共享拓扑$\mathcal{G}(s)=(\mathcal{V}, \mathcal{E}(s))$上，该拓扑是随时间变化的，并满足假设2.1和2.2，代理$i$根据以下公式与它的一度邻居$h$交换信息，直到达成共识

     $$x_{i, k}(s+1, t+1)=\sum_{h \in \mathcal{N}*{i}(s)} a*{i, h}(s) x_{h, k}(s, t+1), \quad k=1,2, \cdots, K$$

     在共同连接的拓扑结构上，共识步骤的停止时间用$S$表示。

  3. 本地更新步骤

     智能体$i$根据以下方式更新$c_{i,k}(t + 1)$：

     $$c_{i, k}(t+1)=\frac{x_{i, k}^{1}(S, t+1)}{x_{i, k}^{2}(S, t+1)}, \quad k=1,2, \cdots, K$$

• 综上，基于双时钟共识的$K-Means$算法（$DCKA$）的伪代码如下所示：

  

• 与现有的算法不同，$DCKA$有两个时钟。

  在共识步骤中，智能体$i$与它的一度邻居智能体$h$交换信息，直到在某个容许范围内达成共识，这对于固定时间的本地步骤的时钟$t+1$很容易实现，并且可以适应全局通信拓扑不可用的情况。

• 即使链路故障/恢复程序或节能政策导致网络拓扑联合连接地切换，共识步骤中的共识率仍然是指数级的。

DCKA的收敛性分析

• 假设$\bar{x}_{k}(0, t+1)=\operatorname{col}\left\{x_{k}^{1}(0, t+1), x_{k}^{2}(0, t+1)\right\}$，其中

  $$\left\{\begin{array}{l}\bar{x}_{k}^{1}(0, t+1)=\frac{1}{N} \sum_{i=1}^{N} x_{i, k}^{1}(0, t+1)=\frac{\sum_{i=1}^{N} u_{i, k}(t+1)}{N}, \\ \bar{x}_{k}^{2}(0, t+1)=\frac{1}{N} \sum_{i=1}^{N} x_{i, k}^{2}(0, t+1)=\frac{\sum_{i=1}^{N} m_{i, k}(t+1)}{N} .\end{array}\right.$$

  由（12）中的$c_k(t+1)$的定义可得，$c_{k}(t+1)=\frac{\bar{x}*{k}^{1}(0, t+1)}{\bar{x}*{k}^{2}(0, t+1)}$，

  定义$\widehat{c}_{i, k}(s, t+1)$如下：

  $$\widehat{c}*{i, k}(s, t+1)=\frac{x*{i, k}^{1}(s, t+1)}{x_{i, k}^{2}(s, t+1)}, \quad k=1,2, \cdots, K,$$

  即为智能体$i$在共识步骤的时间$s$对$c_k(t+1)$的估计

• 鉴于$CKA$可以获得局部最优解，如果能够首先证明当s → ∞时，$\widehat{c}*{i, k}(s, t+1)$收敛于$c_k(t + 1 )$，然后证明存在一个$S$，使得$\widehat{c}*{i, k}(S, t+1)$和$c_k(t + 1)$之间的误差对$θ^j_{i,k}(t + 2 )$没有影响，那么结论就成立了。证明如下：

  1. 证明当$s → ∞$时，$\widehat{c}_{i, k}(S, t+1)$收敛于$c_k(t + 1)$。

     对于所有的$s≥0$。有

     $$\begin{aligned} x_{i, k}^{1}(s, t+1) &=\sum_{h=1}^{N}[\varphi(s-1: 0)]_{i, h} x_{h, k}^{1}(0, t+1) \\ x_{i, k}^{2}(s, t+1) &=\sum_{h=1}^{N}[\varphi(s-1: 0)]_{i, h} x_{h, k}^{2}(0, t+1) \end{aligned}$$

     设

     $$\xi_{i, k}^{1}(s, t+1)=x_{i, k}^{1}(s, t+1)-\bar{x}_{k}^{1}(0, t+1)=\sum_{h=1}^{N}\left([\varphi(s-1: 0)]_{i, h}-\frac{1}{N}\right) x_{h, k}^{1}(0, t+1),\\\xi_{i, k}^{2}(s, t+1)=x_{i, k}^{2}(s, t+1)-\bar{x}_{k}^{2}(0, t+1)=\sum_{h=1}^{N}\left([\varphi(s-1: 0)]_{i, h}-\frac{1}{N}\right) x_{h, k}^{2}(0, t+1) .$$

     由于在假设2.1和2.2的前提下，$DCKA$实现了分布式聚类问题（4）的局部最优解，可得：

     $$\begin{aligned}\left\|\xi_{i, k}^{1}(s, t+1)\right\| & \leq \sum_{h=1}^{N}\left|[\varphi(s-1: 0)]_{i, h}-\frac{1}{N}\right|\left\|x_{h, k}^{1}(0, t+1)\right\| \\ & \leq N \zeta^{-2} \varrho^{s} \max _{h}\left\|x_{h, k}^{1}(0, t+1)\right\| （18）\\\left\|\xi_{i, k}^{2}(s, t+1)\right\| & \leq \sum_{h=1}^{N}\left|[\varphi(s-1: 0)]_{i, h}-\frac{1}{N}\right|\left\|x_{h, k}^{2}(0, t+1)\right\| \\ & \leq N \zeta^{-2} \varrho^{s} \max _{h}\left\|x_{h, k}^{2}(0, t+1)\right\| （19）\end{aligned}$$

     因此

     $$\begin{aligned} &\left\|\widehat{c}_{i, k}(s, t+1)-c_{k}(t+1)\right\| \\=&\left\|\frac{x_{i, k}^{1}(s, t+1)}{x_{i, k}^{2}(s, t+1)}-\frac{\bar{x}_{k}^{1}(0, t+1)}{\bar{x}_{k}^{2}(0, t+1)}\right\| \\=&\left\|\frac{\bar{x}_{k}^{1}(0, t+1)+\xi_{i, k}^{1}(s, t+1)}{\bar{x}_{k}^{2}(0, t+1)+\xi_{i, k}^{2}(s, t+1)}-\frac{\bar{x}_{k}^{1}(0, t+1)}{\bar{x}_{k}^{2}(0, t+1)}\right\| \\=&\left\|\frac{\xi_{i, k}^{1}(s, t+1) \bar{x}_{k}^{2}(0, t+1)-\xi_{i, k}^{2}(s, t+1) \bar{x}_{k}^{1}(0, t+1)}{\left[\bar{x}_{k}^{2}(0, t+1)+\xi_{i, k}^{2}(s, t+1)\right] \bar{x}_{k}^{2}(0, t+1)}\right\| \\ \leq & \frac{\left\|\xi_{i, k}^{1}(s, t+1)\right\|\left\|\bar{x}_{k}^{2}(0, t+1)\right\|+\left\|\xi_{i, k}^{2}(s, t+1)\right\|\left\|\bar{x}_{k}^{1}(0, t+1)\right\|}{\left\|\bar{x}_{k}^{2}(0, t+1)\right\|^{2}} . \end{aligned}$$

     表示为

     $$\sigma_{k}(t+1)=\max \left\{\frac{\max _{h}\left\|x_{h, k}^{1}(0, t+1)\right\|}{\left\|\bar{x}_{k}^{2}(0, t+1)\right\|}, \frac{\left\|\bar{x}_{k}^{1}(0, t+1)\right\| \max _{h}\left\|x_{h, k}^{2}(0, t+1)\right\|}{\left\|\bar{x}_{k}^{2}(0, t+1)\right\|^{2}}\right\}$$

     根据（18）可得

     $$\left|\widehat{c}*{i, k}(s, t+1)-c*{k}(t+1)\right| \leq 2 N \zeta^{-2} \varrho^{s} \sigma_{k}(t+1)$$

     因此，对于任意$\forall \delta>0$，存在一个$S=\log *{\rho}\left(\frac{\zeta^{2} \delta}{2 N \sigma*{k}(t+1)}\right)$，对于任意的$s≥S$，有

     $$\left|\widehat{c}*{i, k}(s, t+1)-c*{k}(t+1)\right| \leq \delta$$

     其中，$\zeta=1-\frac{\varepsilon}{4 N^{2}}, \varrho=\zeta^{1 / \tau}$。换句话说，当s→S时，$\widehat{c}_{i, k}(S, t+1)$收敛于$c_k(t + 1)$。

  2. 证明$\widehat{c}*{i, k}(S, t+1)$和$c_k(t + 1)$之间的误差对$θ^j*{i,k}(t + 2 )$没有影响。

     因为$\theta$是由每个集群的中心点决定的，所以将 $\theta(t+1)$ 表示为 $\theta[C(t)]$ 。若给定中心点 $C(t+1)$ ，取

     $$\delta(t+1)=\min _{1 \leq i \leq N 1 \leq k \leq K} \min *{1 \leq k} \delta*{i, k}(t+1)$$

     其中，

     $$\delta_{i, k}(t+1)=\min _{y \in Y_{i}^{k} k^{\prime} \neq k}\left\{\frac{1}{2}\left(\left\|y-c_{k^{\prime}}(t+1)\right\|^{2}-\left\|y-c_{k}(t+1)\right\|^{2}\right)\right\}$$

     对于任意的$c_{i, k} \in \mathbb{B}\left(c_{k}(t+1), \delta(t+1)\right)$，有$\theta\left[\left\{C_{i}\right\}_{i=1}^{N}\right]=\theta[C(t+1)]$，其中$C_{i}=\left\{c_{i, k}\right\}_{k=1}^{K}$

     对于$\delta(t+1)$，如果选择$S \geq \log _{\rho}\left(\frac{\zeta^{2} \delta(t+1)}{2 N \sigma(t+1)}\right)$，其中

     $$\sigma(t+1)=\max *{k} \sigma*{k}(t+1)$$

     则对于所有$i=1,2, \cdots, N$和$k=1,2, \cdots, K$，有$\widehat{c}*{i, k}(S, t+1) \in \mathbb{B}\left(c*{k}(t+1), \delta(t+1)\right)$

     换句话说，如果$S \geq \log *{\rho}\left(\frac{\zeta^{2} \delta(t+1)}{2 N \sigma(t+1)}\right)$，有$\theta\left[\left\{C_{i}(t+1)\right\}_{i=1}^{N}\right]=\theta[C(t+1)]$。因此，$DCKA$和$CKA$在下一次迭代中应该得到相同的$θ^j*{i,k}(t + 2)$，即$\widehat{c}*{i, k}(S, t+1)$和$c_k(t + 1)$之间的误差对$θ^j*{i,k}(t + 2 )$没有影响。

DCKA的通信和计算复杂性分析

• 定义$T$为$DCKA$的最大迭代次数，$M=\sum_{i=1}^{N}$为所有智能体中数据点的总数，$N_l$为通信网络中的平均链接数。

• 当通信网络的拓扑结构被假定为联合连接时，$N_l$可以比网络全程保持连接时小很多。

• 通信复杂性

  • $DCKA$的通信复杂性与集群、迭代、网络链接等密切相关。在$DCKA$的一个循环共识步骤中，每个智能体向其一度邻居发送关于集群$k$的$x_{i,k}(s, t)$。

  • 用$N_b$表示发送$x_{i,k}(s, t)$的字节数，则在$S$个循环中，通信消耗为2$N_lKSN_b$。因此，总的通信消耗为$2N_lKSTN_b∼O(ST)$。

• 计算复杂性

  • $DCKA$的时间复杂度取决于数据集的大小、网络中智能体的数量、集群的数量以及相关的因素。

  • 网络中的智能体需要大小为$O(NK)$的空间来存储$K$个中心点，大小为$O(MK)$的空间来存储$θ$的值，大小为$O(NK)$的空间用于共识步骤。因此，总的空间复杂性为$O((2N + M)K)$。

  • 每次迭代，本地$K-means$步骤的时间复杂度为$O(KM)$，共识步骤为$O(NKS)$，本地更新步骤为$O(NK)$。因此，$DCKA$的总时间复杂度为$O(T K(M+NS+N))$。此外，当数据集$Y$的大小非常大时，$DCKA$的总时间复杂性为$O(T KM)$。

在$DCKA$中，所考虑的网络中的智能体与它们的一度邻居分享它们的信息以获得相同的$K$中心点。由于所有智能体中所有中心点的共识和中心点的更新完全分开，$DCKA$继承了$CKA$的收敛率。智能体之间的通信拓扑结构被假定为联合连接的。网络中的每个智能体在每个$τ$期间至少与它的一度邻居通信一次。联合连接适用于智能体之间链接的故障，也适用于通信成本的降低。

---

实验Experiment

实验一

• 该实验基于一个合成数据集，其中聚类数据对应于二维空间中的$K=9$个不同的高斯分布。

  • 假设这9个不同的高斯分布具有不同的平均值，分别用$w_{1}=(0,0)^{\mathrm{T}},w_{2}=(0,3)^{\mathrm{T}}, w_{3}=(0,-3)^{\mathrm{T}}$ , $w_{4}=(3,0)^{\mathrm{T}},w_{5}=(-3,0)^{\mathrm{T}}, w_{6}=(3,-3)^{\mathrm{T}}, w_{7}=(3,3)^{\mathrm{T}}, w_{8}=(-3,3)^{\mathrm{T}}$ 和 $w_{9}=(-3,-3)^{\mathrm{T}}$ 表示，它们共享相同的协方差矩阵 $\Sigma=0.64 I_{2}$ ，其中 $I_2$ 是一个二维的特征矩阵。

  • 假设网络中有五个智能体。每个智能体$i$都可以访问一个大小为900的部分数据集$Y_i$，每个高斯分布有100个数据点，这些数据都是随机生成的。

  • 每个智能体$i$的目标是用部分数据集$Y_i$找到相同的九个集群中心点。为了衡量所提出的算法的聚类性能，距离的平方之和（$SSD$）定义如下：

    $$\mathrm{SSD}=F\left(Y, C_{Y}\right)=\sum_{i=1}^{N} \sum_{j=1}^{m_{i}} \sum_{k=1}^{K} \theta_{i, k}^{j}\left\|y_{i}^{j}-c_{i, k}\right\|^{2}$$

    其中$C_Y={ { c_i,k } }$，$Y=\cup_{i=1}^{5} Y_{i}$。智能体$i$的初始聚类中心点$c_{i,k}(0), k=1, 2\dots, 9$, 是从部分数据集$Y_i$中随机选择的。

  • 在$DCKA$中，假设通信拓扑结构是联合连接的。在时间$s=2n$时，通信拓扑结构假定为图(b)，在时间$s=2n+1$时，为图 ( c ) ，$n=1, 2,\dots$。

    

  • 首先，研究了$DCKA$与$CKA$相比的$SSD$，结果如下图所示。结果表明两种算法的$SSD$是一样的，都是5028.54。

    

    下图更直观地显示了聚类的结果，中心点 $c_{1}=(0.0946,0.0449)^{\mathrm{T}}, c_{2}=(-0.0336,3.0507)^{\mathrm{T}}$ , $c_{3}=(-0.024,-3.0223)^{\mathrm{T}}, c_{4}=(2.9454,-0.0521)^{\mathrm{T}}, c_{5}=(-3.0908,0.013)^{\mathrm{T}}, c_{6}=(3.0551,-3.058)^{\mathrm{T}}$ , $c_{7}=(3.0144,3.0049)^{\mathrm{T}}, c_{8}=(-2.9562,3.0391)^{\mathrm{T}}$ 。图中的五边形是由 $CKA$ 得到的中心点，其它的则是由 $DCKA$ 得到的中心点。下图表明，尽管智能体之间的通信拓扑结构发生了变化，但 $DCKA$ 的表现与$CKA$一样好。

    

  • 接下来，研究所提出的算法$DCKA$的共识性能。下图显示了每个智能体$i$的$DCKA$的性能$x^2_{i,1}(s, t)$。可以发现，在共识步骤中，$x^2_{i,1}(s, t)$可以快速达到$\bar{x}*{1}^{2}(0, t)=\frac{\sum*{i=1}^{N} m_{i 1}(t)}{N}$。事实上，收敛率是指数级的。

    

    考虑$DCKA$在不同的$K$值下的行为，如下图所示，尽管$K$值不同，但$DCKA$的表现仍与$CKA$一样好。

    

    由于$DCKA$和$CKA$的聚类结果都与初始中心点的选择有关，因此为了测试算法，模拟了100次不同$K$值的蒙特卡洛运行。其结果如下图显示。由下图可知，$DCKA$和$CKA$都有相同的最小$SSD$。然而，由于$DCKA$初始中心点的多样性，$DCKA$在$SSDs$的平均值和标准偏差上优于$CKA$。这是因为$CKA$必须用$K$个中心点随机初始化，而对于$DCKA$，每个智能体是根据它们的部分数据集$Y_i，i=1, 2,\dots , 5$，用$K$个中心点进行初始化。 因此，$DCKA$通常可以得到比$CKA$更好的结果。

    

  • 最后，研究了$DCKA$与$DKM$算法相比的通信和计算消耗。

    在通信拓扑结构选择为（a）的情况下，$DKM$算法也可以应用于解决聚类问题。下图显示了$K=9$时的$SSD$值，其中，$DKM$中的参数被假定为$η=10$。在$DKM$中，大约需要30次迭代来完成聚类任务，其收敛速度很慢，智能体需要与它们的邻居通信30次左右，总的通信消耗为210$N_b$。然而，$DCKA$的通信成本只有大约150$N_b$，比$DKM$的通信成本低得多。尽管如此，网络中$DKM$算法的智能体仍需要对4500个数据点进行约30次处理，而$DCKA$的代理只需要对整个数据集进行约5次处理。

    

实验二

• 在本实验中，选择了$Birch1$、$Birch2$和$Birch3$作为实验数据集。每个数据集由100000个实体组成，这些实体都是二维向量，真实聚类数都是$K=100$。考虑一个有20个智能体的网络。对于$DCKA$，每个智能体可以随机获得5000个数据点，形成自己的部分数据集$Y_i$，而$CKA$则是在整个数据集 $Y={ { Y_i } }^N_{i=1}$ 上进行。

• 在$DCKA$中，假设智能体的时间变化的通信拓扑是联合连通的。在时间$s = 3n,\ s = 3n + 1$和 $s = 3n + 2$，$n = 1, 2,\dots$时，拓扑结构分别如下图（b）、（c）、（d）所示，而（a）图为它们的联合。

  

• 作者模拟了60次不同$K$值的蒙特卡洛运行，以测试两种算法在这些数据集上的$SSD$性能，其结果分别如下图所示。在这三个数据集中，$DCKA$在$SSD$的平均值和标准差上都优于$CKA$，而当$K=80$和100时，$CKA$只在$Birch3$的$SSD$最小值上优于$DCKA$。结果显示，与$CKA$相比，$DCKA$对初始化不那么敏感，通常可以得到很好的结果。

  在$Birch1(×10^{13})$上运行60次蒙特卡洛的结果：

  

  在$Birch2(×10^{11})$上运行60次蒙特卡洛的结果：

  

  在$Birch3(×10^{13})$上运行60次蒙特卡洛的结果：