本章內容
- k均值聚類算法
- 對聚類得到的簇進行後處理
- 二分k均值聚類算法
- 對地理位置進行聚類
在2000年和2004年的美國總統大選中，候選人的得票數比較接近或者說非常接近。任一候選人得到的普選票數的最大百分比為50.7%，而最小百分比為47.9%。如果1%的選民將手中的選票投向另外的候選人，那麼選舉結果就會截然不同。實際上，如果妥善加以引導與吸引，少部分選民就會轉換立場。儘管這類選舉者占的比例較低，但當候選人的選票接近時，這些人的立場無疑會對選舉結果產生非常大的影響1。如何找出這類選民，以及如何在有限的預算下採取措施來吸引他們？答案就是聚類（Clustering）。
1. 對於微目標策略如何成功用於2004年的美國總統大選的細節，請參見 Fournier、Sosnik與Dowd合著的Applebee』s America（Simon & Schuster, 2006）一書。
接下來介紹如何通過聚類實現上述目標。首先，收集用戶的信息，可以同時收集用戶滿意或不滿意的信息，這是因為任何對用戶重要的內容都可能影響用戶的投票結果。然後，將這些信息輸入到某個聚類算法中。接著，對聚類結果中的每一個簇（最好選擇最大簇），精心構造能夠吸引該簇選民的消息。最後，開展競選活動並觀察上述做法是否有效。
聚類是一種無監督的學習，它將相似的對象歸到同一個簇中。它有點像全自動分類2。聚類方法幾乎可以應用於所有對象，簇內的對象越相似，聚類的效果越好。本章要學習一種稱為k-均值（K-mean）聚類的算法。之所以稱之為k均值是因為它可以發現k個不同的簇，且每個簇的中心採用簇中所含值的均值計算而成。下面會逐步介紹該算法的更多細節。
2. 這裡的自動意思是連類別體系都是自動構建的。——譯者注
在介紹k均值算法之前，先討論一下簇識別（cluster identification）。簇識別給出聚類結果的含義。假定有一些數據，現在將相似數據歸到一起，簇識別會告訴我們這些簇到底都是些什麼。聚類與分類的最大不同在於，分類的目標事先已知，而聚類則不一樣。因為其產生的結果與分類相同，而只是類別沒有預先定義，聚類有時也被稱為無監督分類（unsupervised classification）。
聚類分析試圖將相似對像歸入同一簇，將不相似對像歸到不同簇。相似這一概念取決於所選擇的相似度計算方法。前面章節已經介紹了不同的相似度計算方法，後續章節它們會繼續出現。到底使用哪種相似度計算方法取決於具體應用。
下面會構建k均值方法並觀察其實際效果。接下來還會討論簡單k均值算法中的一些缺陷。為了解決其中的一些缺陷，可以通過後處理來產生更好的簇。接著會給出一個更有效的稱為二分k均值（bisecting k-means）的聚類算法。本章的最後會給出一個實例，該實例應用二分k均值算法來尋找同時造訪多個夜生活熱點地區的最佳停車位。