知识卡片
k均值最小化到最近中心的平方和
k均值的目标是在给定k下选择k个中心,使所有样本到各自最近中心的平方距离之和最小。目标同时取决于中心位置和由最近中心规则诱导的分组;优化的是全体样本成本。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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 ].