正在加载中...

展开本页目录
算法教程KMedoids-K-中心点

KMedoids-K-中心点

No.123 · 在线教程

K-Medoids 是一类与 K-Means 密切相关的划分式聚类方法。二者都需要预先给定聚类数 K，也都通过“样本分配 + 中心更新”的方式迭代优化；但 K-Medoids 的中心不是簇均值，而是簇内某个真实样本点（medoid，中心点）。因此，当数据中存在异常值或距离度量不…

返回教程目录 算法详情 下载方式 购买授权

KMedoids-K-中心点

1. 方法概述

K-Medoids 是一类与 K-Means 密切相关的划分式聚类方法。二者都需要预先给定聚类数 \(K\)，也都通过“样本分配 + 中心更新”的方式迭代优化；但 K-Medoids 的中心不是簇均值，而是簇内某个真实样本点（medoid，中心点）。因此，当数据中存在异常值或距离度量不适合均值中心时，K-Medoids 往往比 K-Means 更稳健。

本项目中的 KMedoids-K-中心点 模块并不是直接调用 sklearn_extra.cluster.KMedoids 或其他现成实现，而是自写了一套 PAM（Partitioning Around Medoids）风格流程，核心步骤包括：

  1. 读取首列为样本 ID、其余列为数值特征的数据；
  2. 对特征执行可选的 z-score 标准化；
  3. 基于 euclidean 或 manhattan 计算样本两两距离矩阵；
  4. 以 random 或 kpp 初始化中心点；
  5. 使用 PAM 交换搜索不断尝试“用非中心点替换某个中心点”，以降低总距离代价；
  6. 输出聚类标签、中心点样本、簇规模、评价指标、距离矩阵与散点图。

设共有 \(n\) 个样本、\(p\) 个选中特征。记原始特征矩阵为

$$ X=(x_{ij})_{n\times p},\quad i=1,2,\ldots,n,\ j=1,2,\ldots,p \tag{1} $$

其中程序约定第 1 列必须为样本 ID/对象名称列，不参与距离计算；用户可在“特征选择”页从第 2 列开始勾选参与聚类的特征列。

2. 数据要求与预处理

2.1 数据约束

根据 upload_widget.py、indicators_widget.py 与 data_validator.py 的实现，模块对输入数据的真实要求如下：

  1. 数据不能为空；
  2. 至少包含两列，即样本 ID 和至少一个特征列；
  3. 第 1 列样本 ID 必须唯一；
  4. 第 2 列及以后必须为数值型；
  5. 特征列不能包含空值；
  6. 至少选择 1 个特征列；
  7. 开始计算时还要求聚类数满足 \(2\le K<n\)。

与 KMeans-K-均值聚类 不同，本模块没有 label_col 机制，样本标识固定来自首列。

2.2 标准化

若勾选 standardize=True，则程序对每个特征执行

$$ z_{ij}=\frac{x_{ij}-\mu_j}{\sigma_j} \tag{2} $$

其中 \(\mu_j\) 与 \(\sigma_j\) 分别为第 \(j\) 个特征的均值与总体标准差。若 \(\sigma_j=0\)，代码会把该标准差置为 1，以避免除零。

若未勾选标准化，则直接令

$$ z_{ij}=x_{ij} \tag{3} $$

记处理后特征矩阵为

$$ Z=(z_{ij})_{n\times p} \tag{4} $$

2.3 符号说明

符号 含义
\(n\) 样本数量
\(p\) 特征维数
\(K\) 聚类数 n_clusters
\(z_i\) 第 \(i\) 个样本的预处理后特征向量
\(d_{ij}\) 样本 \(i,j\) 之间的距离
\(M=\{m_1,\ldots,m_K\}\) 当前中心点索引集合
\(y_i\) 第 \(i\) 个样本的聚类标签
\(C(M)\) 当前中心点集合对应的总代价
\(\mathrm{SSE}\) 基于到中心点距离平方定义的误差指标

3. 核心数学模型

3.1 距离矩阵

程序先在处理后矩阵 \(Z\) 上计算样本两两距离矩阵

$$ D=(d_{ij})_{n\times n} \tag{5} $$

其中当前仅支持两种距离度量：

  1. euclidean
  2. manhattan

若选择 euclidean，则

$$ d_{ij}=\|z_i-z_j\|_2 \tag{6} $$

若选择 manhattan，代码内部会将其映射为 scipy.spatial.distance.cdist 的 cityblock，即

$$ d_{ij}=\|z_i-z_j\|_1=\sum_{r=1}^{p}|z_{ir}-z_{jr}| \tag{7} $$

3.2 中心点目标函数

K-Medoids 与 K-Means 的关键差别在于：它优化的是“样本到中心点样本的距离和”，而不是到均值中心的平方误差。对给定中心点集合 \(M\)，当前实现的总代价函数为

$$ C(M)=\sum_{i=1}^{n}\min_{m\in M} d_{im} \tag{8} $$

代码中的 total_cost 就是式(8) 的数值。

3.3 样本分配

当中心点索引集合 \(M=\{m_1,\ldots,m_K\}\) 给定时，样本 \(i\) 被分配到最近中心点所属的簇：

$$ y_i=\arg\min_{1\le k\le K} d_{i\,m_k} \tag{9} $$

因此，当前实现输出的簇标签是从 0 开始编号的整数标签。

3.4 初始化方式

当前实现支持两种初始化方式：

  1. random：从 \(n\) 个样本中无放回随机抽取 \(K\) 个样本作为初始中心点；
  2. kpp：采用一种 k-medoids++ 风格初始化。

对 kpp 初始化，若已选中心点集合为 \(M_t\)，则每个候选样本 \(i\) 到当前中心点集合的最近距离为

$$ \delta_i=\min_{m\in M_t} d_{im} \tag{10} $$

若 \(\sum_i \delta_i>0\)，则以下述概率抽取下一个中心点：

$$ P(i)=\frac{\delta_i}{\sum_{j=1}^{n}\delta_j} \tag{11} $$

若总距离为 0，代码会退化为均匀随机抽样。若抽样结果出现已选中心点，当前实现会跳过该次追加，最后再从剩余样本中补齐到 \(K\) 个中心点。

3.5 PAM 交换优化

初始化后，程序采用 PAM 风格的交换搜索。设当前中心点集合为 \(M\)，若考虑把其中某个中心点 \(m\in M\) 替换为某个非中心点 \(h\notin M\)，则得到新集合

$$ M'=(M\backslash\{m\})\cup\{h\} \tag{12} $$

若新代价满足

$$ C(M')<C(M) \tag{13} $$

则接受该替换，并立即结束当前外层扫描，进入下一轮迭代。这意味着当前实现采用的是“首次改进（first improvement）”策略，而不是在全部候选交换中寻找全局最优交换。

3.6 停止条件

程序最多执行 max_iter 轮 PAM 外层迭代。若某一轮中不存在任何可降低总代价的交换，则提前停止。设第 \(t\) 轮中心点集合为 \(M^{(t)}\)，则停止条件可写为

$$ \forall m\in M^{(t)},\ \forall h\notin M^{(t)},\quad C\!\left((M^{(t)}\backslash\{m\})\cup\{h\}\right)\ge C(M^{(t)}) \tag{14} $$

项目最终输出的 n_iter 记录了实际执行的迭代轮数。

4. 评价指标

4.1 总代价 total_cost

当前实现优化的主目标就是式(8) 定义的总代价：

$$ \mathrm{TotalCost}=C(M)=\sum_{i=1}^{n}\min_{m\in M} d_{im} \tag{15} $$

该值越小，说明样本整体距离各自中心点越近。

4.2 SSE

虽然 PAM 优化的不是平方误差，但代码仍额外输出一个 SSE 指标，其定义为样本到所属中心点距离的平方和：

$$ \mathrm{SSE}=\sum_{i=1}^{n}d_{i\,m_{y_i}}^2 \tag{16} $$

它主要用于辅助比较聚类紧凑性，但需要注意：这不是当前实现真正被优化的主目标。

4.3 Silhouette

程序还实现了一个自写轮廓系数函数。对样本 \(i\)，若记同簇平均距离为 \(a_i\)，到最近其他簇的平均距离为 \(b_i\)，则

$$ s_i=\frac{b_i-a_i}{\max(a_i,b_i)} \tag{17} $$

整体轮廓系数为

$$ \mathrm{Silhouette}=\frac{1}{n}\sum_{i=1}^{n}s_i \tag{18} $$

当前实现的一个重要工程细节是：当样本量 \(n>500\) 时，程序会随机抽取 500 个样本来近似计算轮廓系数，而不是使用全样本距离矩阵。因此，大样本场景下该指标是抽样近似值。

5. 算法流程

结合当前项目代码，KMedoids-K-中心点 的实际流程如下：

  1. 读取 .xlsx、.xls 或 .csv 文件；CSV 会依次尝试 utf-8-sig、utf-8、gbk 编码。
  2. 校验数据结构：首列样本 ID 唯一，其余列必须是无空值数值列。
  3. 在“特征选择”页从第 2 列开始勾选参与聚类的特征。
  4. 在“方法设置”页配置 n_clusters、max_iter、metric、init_method、random_state 与是否标准化。
  5. 若启用标准化，则按式(2) 对特征矩阵进行 z-score 标准化。
  6. 计算成对距离矩阵 \(D\)。
  7. 按 random 或 kpp 生成初始中心点。
  8. 进入 PAM 交换优化：不断尝试“中心点-非中心点”替换，只要总代价下降就接受。
  9. 输出聚类标签表、中心点样本表、簇规模表以及评价指标。
  10. 若特征维数不少于 2，则基于处理后数据前两维绘制散点图 scatter.png。
  11. 导出 Excel 结果文件和复现脚本。

6. 关键参数说明

6.1 n_clusters

聚类数，界面允许范围为 2 到 200，默认值为 3。当前实现要求严格满足

$$ 2\le K<n \tag{19} $$

因此当样本数为 \(n\) 时，n_clusters 不能等于 \(n\)。

6.2 max_iter

PAM 外层最大迭代轮数，默认值为 100。该值越大，越有机会继续通过交换降低总代价，但计算时间也会更长。

6.3 metric

当前仅支持：

  1. euclidean
  2. manhattan

其中 manhattan 在内部实际对应 cityblock 距离。

6.4 init_method

当前支持：

  1. random
  2. kpp

kpp 用于提高初始中心点的离散程度，通常比纯随机初始化更稳定。

6.5 standardize

是否执行 z-score 标准化，默认勾选。若不同特征量纲差异显著，建议保持开启。

6.6 random_state

随机种子默认值为 42，主要作用于中心点初始化阶段。需要注意：大样本下轮廓系数的 500 样本抽样使用的是 np.random.choice，代码中没有复用该随机种子，因此该近似轮廓系数并不完全受 random_state 控制。

7. 输出结果与导出说明

7.1 结果对象

当前代码返回的主要结果包括：

  1. raw_data：原始输入数据（样本 ID + 选中特征）；
  2. processed_data：标准化后的特征矩阵；
  3. final_results：每个样本的聚类标签与是否为中心点；
  4. medoids：中心点样本表，包含原始特征值、中心点索引和簇编号；
  5. cluster_sizes：各簇样本规模；
  6. step_results.metrics：SSE、Silhouette、total_cost、n_iter；
  7. step_results.medoid_ids：中心点对应的样本 ID；
  8. step_results.distance_matrix：用于展示和导出的距离矩阵；
  9. charts.scatter：二维散点图。

7.2 Excel 工作表

根据 save_results() 的实现，导出的 Excel 文件包含：

  1. 原始数据
  2. 处理后数据
  3. 聚类结果
  4. 中心点
  5. 聚类规模
  6. 评价指标
  7. Charts
  8. 距离矩阵
  9. 距离矩阵说明（仅在距离矩阵被截断时存在）

7.3 距离矩阵导出上限

项目设置了

$$ \texttt{MAX\_DISTANCE\_MATRIX\_EXPORT}=300 \tag{20} $$

因此：

  1. 若 \(n\le 300\)，则导出完整 \(n\times n\) 距离矩阵；
  2. 若 \(n>300\)，则只导出前 \(300\times 300\) 的显示矩阵；
  3. 同时会在 距离矩阵说明 工作表中写明原始矩阵规模与截断说明。

这是当前模块非常明确的工程限制，论文或报告中若引用距离矩阵截图，应注意它可能并不是全量矩阵。

8. 论文写作建议

8.1 方法描述模板

“本文采用 K-Medoids 方法对样本进行聚类分析。首先对选定数值特征进行标准化处理，并基于欧氏距离或曼哈顿距离构造样本间距离矩阵；随后采用 PAM 交换优化策略，在给定聚类数 \(K\) 的条件下迭代搜索一组代表性中心点样本，使样本到其所属中心点的总距离最小。与 K-Means 不同，K-Medoids 的中心点始终对应真实样本，因此对异常值具有更强稳健性。最终输出样本聚类标签、中心点样本、簇规模以及 SSE、轮廓系数等指标。”

8.2 结果解释模板

结果部分可写为：若 total_cost 较小，说明样本到中心点的整体贴近程度较好；若 Silhouette 较高，则表明各簇之间分离较好且簇内相对紧凑。若需要解释各簇的代表对象，应优先使用 中心点 工作表中的 medoid 样本，而不是自行计算均值中心。

8.3 图表题注模板

  • 图 1 K-Medoids 聚类散点图。
  • 表 1 K-Medoids 中心点样本及对应簇编号。
  • 表 2 K-Medoids 聚类规模与评价指标。

9. 实现说明与注意事项

  1. K-Medoids 需要完整距离矩阵，样本量较大时其时间和空间开销会明显高于 K-Means。
  2. 当前实现采用首次改进式 PAM 交换，而不是穷举所有交换后再选最优交换，因此结果受初始化影响。
  3. medoids 表中的中心点是原始样本，这正是 K-Medoids 与 K-Means 的关键差别。
  4. 当样本量超过 300 时，Excel 中的距离矩阵只是截断展示版，不应用它代替全量矩阵做严格复核。
  5. 当前模块只支持 euclidean 和 manhattan 两种距离；若研究问题依赖其他专门距离，应谨慎解释结果。

10. 单篇终审补充

10.1 图题与表题对齐建议

当前 KMedoids 模块的真实工作簿包含：

  • 原始数据
  • 处理后数据
  • 聚类结果
  • 中心点
  • 聚类规模
  • 评价指标
  • Charts
  • 距离矩阵
  • 距离矩阵说明（仅在截断导出时存在）

其中 中心点 是这篇文档最应该在论文中单独强调的结果页，因为当前实现导出的中心点对应真实样本，而不是均值中心。若正文需要比较 K-Means 与 K-Medoids，最直接的证据就是这一页。

图文件保存到结果目录下的 KMedoids_plots_<suffix>/ 子目录，当前真实图名为：

  • scatter.png

因此图题建议写成“K-Medoids 聚类散点图”或“K-Medoids 最终聚类分布图”。不要写成“中心点路径图”或“轮廓系数曲线”，因为当前程序只导出这一张聚类散点图。

10.2 终审说明

这篇文档最需要避免的泛化，是把 中心点 理解成聚类均值。当前 medoids 的含义是“被算法选中的代表样本”，它与 Centers_Original 这类均值中心口径完全不同，因此论文结果解释应写“代表样本”或“中心对象”，而不是“均值中心”。

另外，Charts 表中的路径当前写入的是 resolve() 后的绝对路径，而 repro 脚本的输入文件则已经统一为 repro_inputs/... 相对路径。这意味着“图表索引路径”和“repro 输入路径”在当前模块里不是同一种路径口径，文档里需要分别说明，避免混写成“全部都已相对化”。

10.3 全量强化补充

本篇终审补充绑定的真实算法目录为 具体的算法3/聚类与降维/KMedoids-K-中心点，本次采用的代表性结果目录为 具体的算法3/聚类与降维/KMedoids-K-中心点/results/KMedoids-K-中心点分析结果_20260313_013453_enhanced。

当前目录中真实存在两份工作簿：

  • kmedoids_export.xlsx
  • kmedoids_repro.xlsx

两者实测工作表一致，均为：

  • 原始数据
  • 处理后数据
  • 聚类结果
  • 中心点
  • 聚类规模
  • 评价指标
  • 距离矩阵

这里要用真实磁盘口径纠正一个容易被泛化的写法：这一轮结果目录里并没有单独的 Charts 或 距离矩阵说明 工作表。当前代表性目录保存的是一套主导出结果和一套 repro 再生产物，两者都只有上述 7 张表。因此论文若引用本轮证据，应把 中心点、聚类规模、评价指标、距离矩阵 作为主表，不要把其他历史目录里出现过的页名直接套写到这一轮。

当前目录中的真实图文件也分成两套：

  • 具体的算法3/聚类与降维/KMedoids-K-中心点/results/KMedoids-K-中心点分析结果_20260313_013453_enhanced/KMedoids_plots_kmedoids_export/scatter.png
  • 具体的算法3/聚类与降维/KMedoids-K-中心点/results/KMedoids-K-中心点分析结果_20260313_013453_enhanced/KMedoids_plots_kmedoids_repro/scatter.png

这说明当前磁盘同时保留了主结果散点图和 repro 重跑散点图。两张图图义相同，都是最终聚类分布散点图；区别只在于所属结果批次，不应混写成不同类型图。

复现实物方面，该目录实际包含：

  • 具体的算法3/聚类与降维/KMedoids-K-中心点/results/KMedoids-K-中心点分析结果_20260313_013453_enhanced/repro_kmedoids_k_中心点.py
  • 具体的算法3/聚类与降维/KMedoids-K-中心点/results/KMedoids-K-中心点分析结果_20260313_013453_enhanced/repro_inputs/kmedoids_k_中心点_repro_data.csv

脚本中明确写成 INPUT_FILE = 'repro_inputs/kmedoids_k_中心点_repro_data.csv'、OUTPUT_DIR = '.'、OUTPUT_FILE = 'kmedoids_repro.xlsx'。因此这一轮的真实复现口径是“结果目录内部输入副本 + 同目录 repro 输出工作簿与图目录”，而不是依赖算法根目录 uploads/ 的外部文件。

11. 软件实现核查补充（2026-07）

  • 当前主结果目录应写作 具体的算法3/聚类与降维/KMedoids-K-中心点/results/KMedoids-K-中心点分析结果_20260313_013453_enhanced。
  • 正文应围绕 中心点、聚类规模、评价指标、距离矩阵 来写。
  • 图证应对应主结果与 repro 的 scatter.png，并把主导出与复现重跑区分开。
  • 复现脚本应按 repro_kmedoids_k_中心点.py + repro_inputs/kmedoids_k_中心点_repro_data.csv 的口径说明。