※ 引述《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) 等等的基礎了。:)