※ 引述《jizzer5566 (陈雅姿噗滋)》之铭言：
: 假设在一个二维的空间有许多点
: 每个点有三种属性的其中一种 分别是A或B或C属性
: 我想借由点与点的距离来做分群
: 希望在同一群里面都是相同属性
: 假设我分10群 取10个中心点
: 某1中心点为B属性
: 那该群内的每个点我都预测为B属性
: 再以 猜对的点数/全部点数 算正确率
: 我想请问一下
: 如果将分群数提升为20群甚至30群后
: 正确率反而下降了 是合理的吗
: 其原因可能有哪些？
你讲的比较像是 kNN，不是 k-means
kNN 是 supervised learning 方法，而 k-means 则是 unsupervised learning
一般的分群是归属于 unsupervised learning
k-means 是个非常简单的方群法，主要就是两个步骤
Given initial cluster centers
1. Assignment Step
把每一个资料点 assign 到离它最近的那个群下
2. Re-estimate Cluster centers
利用 Step 1. 的 assignment 结果，重新计算群中心
Step 1 & 2 可以迭代的运算下去，最后会收敛下来
Given data points (x_1,...,x_N), the goal is to assign these points to
K clusters, where \mu_k is the center of the kth cluster.
k-means 基本上就是在解 minimize
J = \sum_{i=1}^N \sum_{k=1}^K || x_i - \mu_k||^2
(bbs 上面没办法打数学公式，上面是 latex 的东西，希望没打错)
的问题。上面两个步骤也可以对应到 EM algorithm 的 E-step 跟 M-step 上
K-means 的 K 是要由使用者给定的。有论文在探讨如何自动决定 K (群数)
当 K=N 的时候，上面的 objective function 会是最佳，不过那通常不会是
我们要的 solution.
KNN 就是一个很简单的 supervised learning 方法了，所以你会有 training
data with label information. 在 classification 阶段，每一个 testing
data 去找周围最近的 K 个 training data，看看这 K 个 training data 大多
是哪一个类别，那这个 testing data 就被分类到那个类别去。
所以说，kNN 很容易受到 distance metric 的影响; 这几年有一些论文是用
metric learning 来学 kNN 的 distance metric。通常这部份做下去就是变成
optimization 问题了，需要有 linear programming, convex programming,
Semidefinite programming (SDP) 等等的基础了。:)