K-means Algorithm
K均值聚类是一种无监督学习算法，主要用于数据挖掘和统计。此迭代方法旨在通过将每个点分配给具有最接近均值的聚类，将数据划分为 K 个聚类。换句话说，此方法会自动将类似的数据示例聚类在一起。
算法思想
算法解释
- Step 1：我们需要首先初始化质心 Centroids（表示聚类中心的点）位置
- Step 2：我们计算每个点到所有Centroids的距离，然后将其分配给最近的Centroid.
我们定义 $\mathcal{C} $ 作为质心Centroids的集合，计算每个点 x x x 分配给一个聚类cluster的准则是 a r g min c i ∈ C ( ∥ c i − x ∥ ) \mathrm {arg} \min_{c_i \in \mathcal{C} } (\| c_i - x \|) argci∈Cmin(∥ci−x∥). - Step 3: 我们通过取分配给该质心聚类的所有点的位置的平均值来更新质心的位置 c i = 1 ∣ S i ∣ ∑ x ∈ S i x c_i = \frac{1}{|\mathcal{S} _i|}\sum_{x \in \mathcal{S} _i} x ci=∣Si∣1x∈Si∑x S i \mathcal{S} _i Si 是第 i i i个聚类的点的集合， ∣ S i ∣ |\mathcal{S} _i| ∣Si∣ 第 i i i个聚类的点的个数。
- Step 4: 重复Step 2 和 Step 3，直到质心 Centroids 的位置不再发生改变。
算法应用
M 个 UAVs 和地面 K 个 Targets 的关联，以及 UAVs 圆形轨迹初始化.
- 圆形轨迹的中心：从K-means算法获得的每个聚类的质心代表UAV圆形轨迹的中心.
- 圆形轨迹的半径： r m = 1 ∣ S m ∣ ∑ w k ∈ S m ∥ w k − c m ∥ r_m= \frac{1}{|\mathcal{S} _m|}\sum_{w_k \in \mathcal{S} _m} \| w_k - c_m \| rm=∣Sm∣1wk∈Sm∑∥wk−cm∥
其他
- 可以直接从 ref [2] 中查看 Matlab 文档对 k-means 算法的解释，以及 kmeans(X,k) 函数的的使用。
- 可以直接从 ref [3] 中查看 Matlab 文档对其他“聚类分析”的介绍，其中包含最常使用的 “谱聚类”（对应函数：spectralcluster ） 和 “最近邻”。
- 关于谱聚类的轨迹初始化应用参考 ref [4,5]。
K-means 简单算法设计
matlab算法设计思路和代码
K-means和谱聚类的比较
[1] A. Bejaoui, K. Park and M. Alouini, “A QoS-Oriented Trajectory Optimization in Swarming Unmanned-Aerial-Vehicles Communications,” in IEEE Wireless Communications Letters, vol. 9, no. 6, pp. 791-794, June 2020, doi: 10.1109/LWC.2020.2970052. “参考附录 Appendix C”
[2] https://ww2.mathworks.cn/help/stats/kmeans.html#d123e19554
[3] https://ww2.mathworks.cn/help/stats/cluster-analysis.html?s_tid=CRUX_lftnav
[4] X. Wang, Z. Fei, J. A. Zhang, J. Huang and J. Yuan, “Constrained Utility Maximization in Dual-Functional Radar-Communication Multi-UAV Networks,” in IEEE Transactions on Communications, vol. 69, no. 4, pp. 2660-2672, April 2021, doi: 10.1109/TCOMM.2020.3044616.
[5] U. Luxburg, “A tutorial on spectral clustering,” Springer J. Stat. Comput., vol. 17, no. 4, pp. 395–416, Dec. 2007.
