知识卡片

普通读书笔记卡 · 3710.b.2.b

k均值最小化到最近中心的平方和

理解等级:中级

k均值的目标是在给定k下选择k个中心,使所有样本到各自最近中心的平方距离之和最小。目标同时取决于中心位置和由最近中心规则诱导的分组;优化的是全体样本成本。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第33章 机器学习算法 · 查看原书依据

      ,S(k)〉 is defined by the centers C and the nearest-center rule. See Exercise 33.1-1 for an alternative formulation based on pairwise interpoint distances. Is there a polynomial-time algorithm for the k-means problem? Probably not, because it is NP-hard [310].

    参考来源

    - 位置:《算法导论(第4版)》第33章《机器学习算法》(OEBPS/chapter033.xhtml,文本字符[10000,15000))。 - 结论依据:原文第33章导言和33.1节的学习任务、聚类定义、目标函数与局部最优说明;公式及图已核对。 - 原始内容:The k-means problem is then the following: given a set S of n points and a positive integer k , find a sequence C = 〈 c (1) , c (2) , …, c ( k ) 〉 of k center points minimizing the sum f ( S , C ) of the squared distance from each point to its nearest center, where In the second line, the k -clustering 〈 S (1) , S (2) ,…, S ( k ) 〉 is defined by the centers C and the nearest-center rule. See Exercise 33.1-1 for an alternative formulation based on pairwise interpoint distances. Is there a polynomial-time algorithm for the k -means problem? Probably not, because it is NP-hard [ 310 ].