题目描述

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

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

分别是$()$

$\mathcal{A}2,2,3,3$
$\mathcal{B}1,1,3,3$
$\mathcal{C}1,1,2,4$
$\mathcal{D}2,2,2,4$

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

题目解析

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

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

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

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

至此，能够得到距离种子点$A$近的样本点集合$A_{near}$和距离种子点$B$近的样本点集合$B_{near}$：
{ A n e a r : { a 1 , a 2 } B n e a r : { a 3 , a 4 , a 5 , a 6 } \begin{cases} A_{near}: \{a_1,a_2\} \\ B_{near}: \{a_3,a_4,a_5,a_6\} \end{cases} {Anear​:{a1​,a2​}Bnear​:{a3​,a4​,a5​,a6​}​
新的点群中心坐标的计算结果表示如下：
$$\begin{array}{rl}& \{\begin{array}{l}\begin{array}{r}\frac{a_{1.x}+a_{2.x}}{2}=\frac{0+0}{2}=0\end{array}\\ \begin{array}{r}\frac{a_{1.y}+a_{2.y}}{2}=\frac{0+2}{2}=1\end{array}\end{array}{A}_1:(0,1)\\ & \{\begin{array}{l}\begin{array}{r}\frac{a_{3.x}+a_{4.x}+a_{5.x}+a_{6.x}}{4}=\frac{1+3+6+6}{4}=4\end{array}\\ \begin{array}{r}\frac{a_{3.y}+a_{4.y}+a_{5.y}+a_{6.y}}{4}=\frac{1+2+0+2}{4}=1.25\end{array}\end{array}{B}_1:(4,1.25)\end{array}$$
此时已经得到新的种子点$A_1,B_1$，新的位置关系表示如下：

重新执行上面的步骤：
针对种子点$A_1,B_1$,分别求出各自对应其他样本点的距离：

$\text{SamplePoint/InitialCenter}$	$A_1$	$B_1$	$\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)$	$\begin{array}{r}>\frac{5}{4}\end{array}$	$\begin{array}{r}\frac{5}{4}\end{array}$	$B_1$
$a_5:(6,0)$	$\begin{array}{r}>\frac{\sqrt{89}}{4}\end{array}$	$\begin{array}{r}\frac{\sqrt{89}}{4}\end{array}$	$B_1$
$a_6:(6,2)$	$\begin{array}{r}>\frac{\sqrt{73}}{4}\end{array}$	$\begin{array}{r}\frac{\sqrt{73}}{4}\end{array}$	$B_1$

能够得到距离种子点$A_1$近的样本点集合$A_{1\Rightarrow near}$和距离种子点$B1$近的样本点集合$B_{1\Rightarrow near}$：
{ A 1 ⇒ n e a r : { a 1 , a 2 , a 3 } B 1 ⇒ n e a r : { a 4 , a 5 , a 6 } \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​:{a1​,a2​,a3​}B1⇒near​:{a4​,a5​,a6​}​
此时发现新集合$A_{1\Rightarrow near},B_{1\Rightarrow near}$中的样本点与初始状态的集合$A_{near},B_{near}$样本点存在差异，需要继续计算。新样本点的结果表示为
$$A_2:(\frac{1}{3},1),B_2:(5,\frac{4}{3})$$
对应图像结果表示如下：

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

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

能够得到距离种子点$A_2$近的样本点集合$A_{2\Rightarrow near}$和距离种子点$B_2$近的样本点集合$B_{2\Rightarrow near}$：
{ A 2 ⇒ n e a r : { a 1 , a 2 , a 3 } B 2 ⇒ n e a r : { a 4 , a 5 , a 6 } \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​:{a1​,a2​,a3​}B2⇒near​:{a4​,a5​,a6​}​
此时发现新集合$A_{2\Rightarrow near},B_{2\Rightarrow near}$中的样本点与第一次迭代的集合$A_{1\Rightarrow near},B_{1\Rightarrow near}$样本点相同，停止迭代。整个迭代过程中，种子点$A,B$各移动两次，各种子点对应集合均包含$3$个样本点。$\mathcal{A}$ 选项正确。