本题要交的是题面规定的迭代结果，不是另找一种全局最优划分。初始中心取前 k 个样本。每一轮按曼哈顿距离把样本分到最近的簇，距离相同就留在编号更小的簇。非空簇对每一维单独取中位数：奇数个取排序后正中间一项，偶数个取正中间两项的算术平均；空簇中心保持不动。所有簇、所有维度上新旧坐标绝对差之和小于 10−4 就停止，否则继续，最多 100 轮。最后一轮的簇编号、更新后的中心，以及每个样本到所属中心的曼哈顿距离之和，就是输出的三部分。
中心要单独拷贝，不能和样本共用存储，否则更新中心时会改掉原始特征。分配时先算到 0 号中心的距离，只有严格更近才更换编号，这样并列会落到更小的编号。空簇把旧中心整行抄回去。变化量用双精度累加，再和 10−4 比较。inertia 用这一轮的编号和更新后的中心来算，距离仍然用曼哈顿距离。中心和 inertia 保留 6 位小数；数值为 0 时按正零输出，避免打出 −0.000000。
最多 T=100 轮。每轮分配要看每个样本到每个中心的每一维，时间 O(Tnkd)。每个簇的每一维排序一次，合计 O(Tdnlogn)。在 n≤5000、k≤100、d≤20 时，分配是主要开销。空间用于存放全部样本和 k 个中心，为 O(nd+kd)。
K-Median 按划分做聚类：样本之间用曼哈顿距离（L1），簇中心取该簇在每一维上的中位数，因此离群点不容易把中心拉偏。
给定 n 个样本，每个样本有 d 个浮点特征。请按下列固定流程把样本分成 k 个簇，并输出簇编号、最终中心和 inertia。
初始化：取下标 0 到 k-1 的样本作为 k 个簇的初始中心。
分配：把每个样本分到曼哈顿距离最近的中心。到多个中心的距离相同时，分到编号最小的簇。
更新：若某个簇在本轮分配后没有样本，则该簇中心保持不变；否则，用簇内样本在每一维上的中位数替换该簇中心。
重复分配与更新，直到中心变化量小于 tol，或迭代次数达到 max_iter。tol 固定为 10−4，max_iter 固定为 100。中心变化量是所有簇、所有维度上，新旧中心坐标绝对差的总和。
曼哈顿距离为
dist(x,y)=∑i∣xi−yi∣
一维中位数：将数值升序排列后，个数为奇数时取正中间的一项，个数为偶数时取正中间两项的算术平均（可以是浮点数）。例如 [1,3,5,9] 的中位数是 (3+5)/2=4。
第一行三个整数 n、d、k，依次为样本数、特征维数、簇数。
接下来 n 行，每行 d 个浮点数，表示一个样本的特征。
1≤n≤5000
1≤d≤20
1≤k≤min(100,n)
每个特征值都属于 [−104,104]。
第一行输出 n 个整数，为最后一轮分配得到的簇编号（从 0 到 k-1），相邻整数之间用一个空格分隔。
接下来 k 行，按簇编号从 0 到 k-1 输出本轮更新后的中心。每行 d 个浮点数，保留小数点后 6 位，相邻数之间用一个空格分隔。空簇输出被保留下来的中心。
最后一行输出 inertia，即每个样本到其所属簇中心的曼哈顿距离之和，保留小数点后 6 位。
输入
3 2 1
2 8
6 1
4 5
输出
0 0 0
4.000000 5.000000
11.000000
说明
k=1 时，初始中心就是样本 0，即 (2,8)。三个样本都分进簇 0。
第 1 维排序为 2,4,6，中位数是 4；第 2 维排序为 1,5,8，中位数是 5。新中心为 (4,5)。
再分配一次，中心不再变化，迭代停止。
inertia 为各样本到 (4,5) 的曼哈顿距离之和：
∣2−4∣+∣8−5∣=5，∣6−4∣+∣1−5∣=6，∣4−4∣+∣5−5∣=0，合计 11。
输入
4 2 2
1 1
4 2
5 5
8 8
输出
0 0 1 1
2.500000 1.500000
6.500000 6.500000
10.000000
说明
初始中心：簇 0 为 (1,1)，簇 1 为 (4,2)。
第 1 轮分配：
簇 0 只有一个样本，中心仍是 (1,1)。簇 1 的第 1 维为 4,5,8，中位数 5；第 2 维为 2,5,8，中位数 5。变化量为 ∣5−4∣+∣5−2∣=4。
第 2 轮，中心为 (1,1) 与 (5,5)：
簇 0 含 (1,1)、(4,2)，中位数为 ((1+4)/2,(1+2)/2)=(2.5,1.5)。簇 1 含 (5,5)、(8,8)，中位数为 (6.5,6.5)。变化量为 ∣2.5−1∣+∣1.5−1∣+∣6.5−5∣+∣6.5−5∣=5。
第 3 轮，中心为 (2.5,1.5) 与 (6.5,6.5)：
划分和中心都不再变化，迭代停止。簇编号为 0 0 1 1。
inertia：
∣1−2.5∣+∣1−1.5∣=2，∣4−2.5∣+∣2−1.5∣=2，∣5−6.5∣+∣5−6.5∣=3，∣8−6.5∣+∣8−6.5∣=3，合计 10。
© CodeFun2000 · 使用条款
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册