牛客网算法八股刷题系列(八)K-Means真题描述

文章列表

牛客网算法八股刷题系列——K-Means真题描述

题目描述
正确答案： $A\\mathcal A$
题目解析

题目描述

两个种子点 $A (- 1, 1), B (2, 1)$ ，其余样本点为 $(0, 0), (0, 2), (1, 1), (3, 2), (6, 0), (6, 2)$ 。利用 $K-Means\\text{K-Means}$ 算法，点群中心按坐标平均计算。最终：

种子点 $A$ 需要移动的次数；
种子点 $B$ 需要移动的次数；
属于种子点 $A$ 的样本点数(不含 $A$ )；
属于种子点 $B$ 的样本点数(不含 $B$ )；

分别是 $()(\\quad)$

$A2,2,3,3\\mathcal A \\quad 2,2,3,3$
$B1,1,3,3\\mathcal B \\quad 1,1,3,3$
$C1,1,2,4\\mathcal C \\quad 1,1,2,4$
$D2,2,2,4\\mathcal D \\quad 2,2,2,4$

正确答案： $A\\mathcal A$

题目解析

初始状态下，上述样本点(蓝色点)与种子点(橙色点)之间的位置关系表示如下：

针对种子点 $A,B\\mathcal A,\\mathcal B$ ，分别求出各自对应其他样本点的距离：

这里以‘欧式距离’计算点之间的距离信息,以 $A$ 与样本点 $a_1:(0,0)$ 之间距离为例,后续同理:
$DistA⇔a1=(−1−0)2+(1−0)2=2\\text{Dist}_{A \\Leftrightarrow a_1} = \\sqrt{(-1 -0)^2 + (1 - 0)^2} = \\sqrt{2}$
由于计算过程中不包含 $A, B$ 点，这里直接将它们视作‘虚拟样本’

$SamplePoint/InitialCenter\\text{SamplePoint/InitialCenter}$	$A$	$B$	$ClusterResult\\text{ClusterResult}$
$a_1:(0,0)$	$2\\sqrt{2}$	$3\\sqrt{3}$	$A$
$a_2:(0,2)$	$2\\sqrt{2}$	$5\\sqrt{5}$	$A$
$a_3:(1,1)$	$2$	$1$	$B$
$a_4:(3,2)$	$17\\sqrt{17}$	$2\\sqrt{2}$	$B$
$a_5:(6,0)$	$50\\sqrt{50}$	$17\\sqrt{17}$	$B$
$a_6:(6,2)$	$50\\sqrt{50}$	$17\\sqrt{17}$	$B$

至此，能够得到距离种子点 $A$ 近的样本点集合 $A_{near}$ 和距离种子点 $B$ 近的样本点集合 $B_{near}$ ：
${Anear:{a1,a2}Bnear:{a3,a4,a5,a6}\\begin{cases} A_{near}: \\{a_1,a_2\\} \\\\ B_{near}: \\{a_3,a_4,a_5,a_6\\} \\end{cases}$
新的点群中心坐标的计算结果表示如下：
${a1.x+a2.x2=0+02=0a1.y+a2.y2=0+22=1A1:(0,1){a3.x+a4.x+a5.x+a6.x4=1+3+6+64=4a3.y+a4.y+a5.y+a6.y4=1+2+0+24=1.25B1:(4,1.25)\\begin{aligned} & \\begin{cases} \\begin{aligned}\\frac{a_{1.x} + a_{2.x}}{2} = \\frac{0 + 0}{2} = 0\\end{aligned} \\\\ \\begin{aligned} \\frac{a_{1.y} + a_{2.y}}{2} = \\frac{0 + 2}{2} = 1 \\end{aligned} \\end{cases} \\quad A_1:(0,1) \\\\ & \\begin{cases} \\begin{aligned}\\frac{a_{3.x} + a_{4.x} + a_{5.x} + a_{6.x}} {4} = \\frac{1 + 3 + 6 + 6}{4} = 4\\end{aligned} \\\\ \\begin{aligned} \\frac{a_{3.y} + a_{4.y} + a_{5.y} + a_{6.y}}{4} = \\frac{1 + 2 + 0 + 2}{4} = 1.25 \\end{aligned} \\end{cases} \\quad B_1:(4,1.25) \\end{aligned}$
此时已经得到新的种子点 $A_1,B_1$ ，新的位置关系表示如下：
第一次迭代
重新执行上面的步骤：
针对种子点 $A_1,B_1$ ,分别求出各自对应其他样本点的距离：

$SamplePoint/InitialCenter\\text{SamplePoint/InitialCenter}$	$A_1$	$B_1$	$ClusterResult\\text{ClusterResult}$
$a_1:(0,0)$	$1$	$> 1$	$A_1$
$a_2:(0,2)$	$1$	$> 1$	$A_1$
$a_3:(1,1)$	$1$	$> 1$	$A_1$
$a_4:(3,2)$	$>54\\begin{aligned}>\\frac{5}{4}\\end{aligned}$	$54\\begin{aligned}\\frac{5}{4}\\end{aligned}$	$B_1$
$a_5:(6,0)$	$>894\\begin{aligned}>\\frac{\\sqrt{89}}{4}\\end{aligned}$	$894\\begin{aligned}\\frac{\\sqrt{89}}{4}\\end{aligned}$	$B_1$
$a_6:(6,2)$	$>734\\begin{aligned}>\\frac{\\sqrt{73}}{4}\\end{aligned}$	$734\\begin{aligned}\\frac{\\sqrt{73}}{4}\\end{aligned}$	$B_1$

能够得到距离种子点 $A_1$ 近的样本点集合 $A1⇒nearA_{1\\Rightarrow near}$ 和距离种子点 $B 1$ 近的样本点集合 $B1⇒nearB_{1 \\Rightarrow near}$ ：
${A1⇒near:{a1,a2,a3}B1⇒near:{a4,a5,a6}\\begin{cases} A_{1 \\Rightarrow near}: \\{a_1,a_2,a_3\\} \\\\ B_{1 \\Rightarrow near}: \\{a_4,a_5,a_6\\} \\end{cases}$
此时发现新集合 $A1⇒near,B1⇒nearA_{1 \\Rightarrow near},B_{1 \\Rightarrow near}$ 中的样本点与初始状态的集合 $A_{near},B_{near}$ 样本点存在差异，需要继续计算。新样本点的结果表示为
$A2:(13,1),B2:(5,43)A_2:(\\frac{1}{3},1),B_2:(5,\\frac{4}{3})$
对应图像结果表示如下：
第二次迭代

继续迭代。针对种子点 $A_2,B_2$ ,分别求出各自对应其他样本点的距离：

$SamplePoint/InitialCenter\\text{SamplePoint/InitialCenter}$	$A_2$	$B_2$	$ClusterResult\\text{ClusterResult}$
$a_1:(0,0)$	$103\\begin{aligned}\\frac{\\sqrt{10}}{3}\\end{aligned}$	$>103\\begin{aligned}>\\frac{\\sqrt{10}}{3}\\end{aligned}$	$A_2$
$a_2:(0,2)$	$103\\begin{aligned}\\frac{\\sqrt{10}}{3}\\end{aligned}$	$>103\\begin{aligned}>\\frac{\\sqrt{10}}{3}\\end{aligned}$	$A_2$
$a_3:(1,1)$	$23\\begin{aligned}\\frac{2}{3}\\end{aligned}$	$>23\\begin{aligned}>\\frac{2}{3}\\end{aligned}$	$A_2$
$a_4:(3,2)$	$>1023\\begin{aligned}>\\frac{10\\sqrt{2}}{3}\\end{aligned}$	$1023\\begin{aligned}\\frac{10\\sqrt{2}}{3}\\end{aligned}$	$B_2$
$a_5:(6,0)$	$>53\\begin{aligned}>\\frac{5}{3}\\end{aligned}$	$53\\begin{aligned}\\frac{5}{3}\\end{aligned}$	$B_2$
$a_6:(6,2)$	$>133\\begin{aligned}>\\frac{\\sqrt{13}}{3}\\end{aligned}$	$133\\begin{aligned}\\frac{\\sqrt{13}}{3}\\end{aligned}$	$B_2$

能够得到距离种子点 $A_2$ 近的样本点集合 $A2⇒nearA_{2 \\Rightarrow near}$ 和距离种子点 $B_2$ 近的样本点集合 $B2⇒nearB_{2 \\Rightarrow near}$ ：
${A2⇒near:{a1,a2,a3}B2⇒near:{a4,a5,a6}\\begin{cases} A_{2 \\Rightarrow near}: \\{a_1,a_2,a_3\\} \\\\ B_{2 \\Rightarrow near}: \\{a_4,a_5,a_6\\} \\end{cases}$
此时发现新集合 $A2⇒near,B2⇒nearA_{2 \\Rightarrow near},B_{2 \\Rightarrow near}$ 中的样本点与第一次迭代的集合 $A1⇒near,B1⇒nearA_{1 \\Rightarrow near},B_{1 \\Rightarrow near}$ 样本点相同，停止迭代。整个迭代过程中，种子点 $A, B$ 各移动两次，各种子点对应集合均包含 $3$ 个样本点。 $A\\mathcal A \\quad$ 选项正确。

牛客网算法八股刷题系列(八)K-Means真题描述

牛客网算法八股刷题系列——K-Means真题描述

题目描述

正确答案： $A\\mathcal A$

题目解析

公告

标签

牛客网算法八股刷题系列(八)K-Means真题描述

牛客网算法八股刷题系列——K-Means真题描述

题目描述

正确答案：A\\mathcal AA

题目解析

相关问题

公告

标签

正确答案： $A\\mathcal A$