← 返回刚才阅读的位置

知识卡片

结构图卡 · 9637.f · 生成模型:DeepSeek-V4.1-Flash

K均值与Lloyd迭代

理解等级:中级

K 均值把 n 个点划成 K 个互不相交的类 C1,…,CK,目标是最小化类内平方和 WCSS=Σk Σ_{p∈Ck} d(p,μk)²,μk 是第 k 类的中心(类内均值)。精确最小化是 NP-hard,计算量过大,实务用 Lloyd 算法近似:随机抽 K 个样本作初始中心;把每点分到最近的中心;用各类算术平均更新中心;重复直到收敛。复杂度 O(knml),k 为类数、n 为样本量、m 为维数、l 为迭代次数,因此能应付较大数据。优势是简洁快速,结果也容易解释;关键却在于初始中心的选择与距离公式,且必须由人给定 K——不合适的 K 会返回较差的划分。K 的选取可借助肘部法则(示例:画 WCSS 随 K 的曲线,取下降由陡变缓的拐点)。

结构图:

flowchart TD
  A["给定 K 与距离"] --> B["随机选 K 个初始中心"]
  B --> C["每点分到最近中心"]
  C --> D["用类均值更新中心"]
  D --> E{"中心是否不再移动"}
  E -- 否 --> C
  E -- 是 --> F["输出 K 个类"]
这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第8章 聚类分析 · 查看原书依据

      该算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式。缺点是需要一个输入参数,不合适的K 值可能返回较差的结果。

    参考来源

    - 位置:《大数据挖掘与统计机器学习》第8章 聚类分析(源文件:extracted/大数据挖掘与统计机器学习/_epub-src/OEBPS/Text/chapter10_0001.xhtml,8.1.3 K均值聚类) - 结论依据:原文给出类内平方和最小的目标、该问题为 NP-hard、Lloyd 四步迭代以及 O(knml)复杂度,并指出关键在于初始中心与距离公式、需要输入 K。 - 原始内容:该算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式。缺点是需要一个输入参数,不合适的K 值可能返回较差的结果。