文章來源：加米谷大資料
k-means 算法是一種基于劃分的聚類算法，它以 k 為參數，把 n 個資料對象分成 k 個簇，使簇内具有較高的相似度，而簇間的相似度較低。
1. 基本思想
k-means 算法是根據給定的 n 個資料對象的資料集，建構 k 個劃分聚類的方法，每個劃分聚類即為一個簇。該方法将資料劃分為 n 個簇，每個簇至少有一個資料對象，每個資料對象必須屬于而且隻能屬于一個簇。同時要滿足同一簇中的資料對象相似度高，不同簇中的資料對象相似度較小。聚類相似度是利用各簇中對象的均值來進行計算的。
k-means 算法的處理流程如下。首先，随機地選擇 k 個資料對象，每個資料對象代表一個簇中心，即選擇 k 個初始中心；對剩餘的每個對象，根據其與各簇中心的相似度（距離），将它賦給與其最相似的簇中心對應的簇；然後重新計算每個簇中所有對象的平均值，作為新的簇中心。
不斷重複以上這個過程，直到準則函數收斂，也就是簇中心不發生明顯的變化。通常采用均方差作為準則函數，即最小化每個點到最近簇中心的距離的平方和。
新的簇中心計算方法是計算該簇中所有對象的平均值，也就是分别對所有對象的各個次元的值求平均值，進而得到簇的中心點。例如，一個簇包括以下 3 個資料對象 {(6,4,8),(8,2,2),(4,6,2)}，則這個簇的中心點就是 ((6+8+4)/3,(4+2+6)/3,(8+2+2)/3)=(6,4,4)。
k-means 算法使用距離來描述兩個資料對象之間的相似度。距離函數有明式距離、歐氏距離、馬式距離和蘭氏距離，最常用的是歐氏距離。
k-means 算法是當準則函數達到最優或者達到最大的疊代次數時即可終止。當采用歐氏距離時，準則函數一般為最小化資料對象到其簇中心的距離的平方和，即
。
其中，k 是簇的個數，
是第 i 個簇的中心點，dist(
,x)為 X 到
的距離。
2. Spark MLlib 中的 k-means 算法
Spark MLlib 中的 k-means 算法的實作類 KMeans 具有以下參數。
class KMeans private (
private var k: int,
private var maxiterations: Int,
private var runs: Int,
private var initializationMode String
private var initializationStep: Int,
private var epsilon: Double,
private var seed: Long) extends: Serializable with Logging
1）MLlib 的 k-means 構造函數
使用預設值構造 MLlib 的 k-means 執行個體的接口如下。
{k: 2,maxIterations: 20,runs: 1, initializationMode: KMeans.K_MEANS_PARALLEL,InitializationSteps: 5,epsilon: le-4,seed:random}。
參數的含義解釋如下。
通常應用時，都會先調用 KMeans.train 方法對資料集進行聚類訓練，這個方法會傳回 KMeansModel 類執行個體，然後可以使用 KMeansModel.predict 方法對新的資料對象進行所屬聚類的預測。
2）MLlib 中的 k-means 訓練函數
MLlib 中的 k-means 訓練函數 KMeans.train 方法有很多重載方法，這裡以參數最全的一個 來進行說明。KMeans.train 方法如下。
def train(
data:RDD[Vector],
k:Int
maxIterations:Int
runs:Int
initializationMode: String,
seed: Long): KMeansModel = {
new KMeans().setK(k) -
.setMaxIterations(maxIterations)
.setRuns(runs)
.setInitializatinMode(initializationMode)
.setSeed(seed)
.run(data)
}
)
方法中各個參數的含義與構造函數相同，這裡不再重複。
3）MLlib 中的 k-means 的預測函數
MLlib 中的 k-means 的預測函數 KMeansModel.predict 方法接收不同格式的資料輸入參數，可以是向量或者 RDD，傳回的是輸入參數所屬的聚類的索引号。KMeansModel.predict 方法的 API 如下。
def predict(point:Vector):Int
def predict(points:RDD[Vector]):RDD[int]
第一種預測方法隻能接收一個點，并傳回其所在的簇的索引值；第二個預測方法可以接收一組點，并把每個點所在簇的值以 RDD 方式傳回。
3. MLlib 中的 k-means 算法執行個體
執行個體：導入訓練資料集，使用 k-means 算法将資料聚類到兩個簇當中，所需的簇個數會作為參數傳遞到算法中，然後計算簇内均方差總和（WSSSE），可以通過增加簇的個數 k 來減小誤差。
本執行個體使用 k-means 算法進行聚類的步驟如下。
①裝載資料，資料以文本檔案的方式進行存放。
②将資料集聚類，設定類的個數為 2 和疊代次數為 20，進行模型訓練形成資料模型。
③列印資料模型的中心點。
④使用誤差平方之和來評估資料模型。
⑤使用模型測試單點資料。
⑥進行交叉評估 1 時，傳回結果；進行交叉評估 2 時，傳回資料集和結果。
該執行個體使用的資料存放在 kmeans_data.txt 文檔中，提供了 6 個點的空間位置坐标，資料如下所示。
0.0 0.0 0.0
0.1 0.1 0.1
0.2 0.2 0.2
9.0 9.0 9.0
9.1 9.1 9.1
9.2 9.2 9.2
每行資料描述了一個點，每個點有 3 個數字描述了其在三維空間的坐标值。将資料的每一列視為一個特征名額，對資料集進行聚類分析。實作的代碼如下所示。
import org.apache.log4j.{Level,Logger}
import org.apache.spark.{SparkConf,SparkContext}
import org.apache.spark.mllib.clustering.KMeans
import org.apache.spark.mllib.linalg.Vectors
object Kmeans {
def main(args: Array[String]) {
//設定運作環境
val conf = new SparkConf().setAppName("Kmeans").setMaster("local[4]")
val sc = new SparkContext(conf)
//裝載資料集
val data = sc.textFile("/home/hadoop/exercise/kmeans_data.txt", 1)
val parsedData = data.map(s => Vectors.dense(s.split('').map(_.toDouble)))
//将資料集聚類，設定類的個數為2，疊代次數為 20，進行模型訓練形成資料模型
val numClusters = 2
val numIterations = 20
val model = KMeans.train(parsedData,numClusters, numIterations)
//列印資料模型的中心點
printIn("Cluster centers:")
for (c <- model.clustercenters) {
printIn ("" + c.toString)
}
//使用誤差平方之和來評估資料模型
val cost = model.computeCost(parsedData)
printIn("Within Set Sum of Squared Errors = " + cost)
//使用模型測試單點資料
printIn("Vectors 0.2 0.2 0.2 is belongs to clusters:" + model.predict(Vectors.dense("0.2 0.2 0.2".split('').map(_.toDouble))))
printIn("Vectors 0.25 0.25 0.25 is belongs to clusters:" + model.predict(Vectors.dense("0.25 0.25 0.25".split('')).map(_.toDouble))))
printIn("Vectors 8 8 8 is belongs to clusters:" +model.predict(Vectors.dense("8 8 8".split(' ').map(_.toDouble))))
//交叉評估 1，隻傳回結果
val testdata = data.map(s => Vectors.dense(s.split('').map(_.toDouble)))
val result1 = model.predict(testdata)
result1.saveAsTextFile ("/home/hadoop/upload/class8/result_kmeans1")
//交叉評估 2，傳回資料集和結果
val result2 = data.map {
line =>
val linevectore = Vectors.dense(line.split('').map(_.toDouble))
val prediction = model.predict(linevectore) line + " " + prediction
}.saveAsTextFile("/home/hadoop/upload/class8/result_kmeans2")
sc.stop ()
}
}
運作代碼後，在運作視窗中可以看到計算出的資料模型，以及找出的兩個簇中心點：(9.1, 9.1, 9.1) 和 (0.1, 0.1, 0.1)；并使用模型對測試點進行分類，可求出它們分别屬于簇 1、1、0。
同時，在 /home/hadoop/spark/mllib/exercise 目錄中有兩個輸出目錄：result_kmeansl 和 result_kmeans2。在交叉評估 1 中隻輸出了 6 個點分别屬于簇 0、0、0、1、1、1；在交叉評估 2 中輸出了資料集和每個點所屬的簇。
4. 算法優缺點
k-means 聚類算法是一種經典算法，該算法簡單高效，易于了解和實作；算法的時間複雜度低，為O(tkm)，其中，r 為疊代次數，k 為簇的數目，m 為記錄數，n 為維數，并且 t<<m k<<n。
k-means 算法也有許多不足的地方。
- 需要人為事先确定簇的個數，k 的選擇往往會是一個比較困難的問題。
- 對初始值的設定很敏感，算法的結果與初始值的選擇有關。
- 對噪聲和異常資料非常敏感。如果某個異常值具有很大的數值，則會嚴重影響資料分布。
- 不能解決非凸形狀的資料分布聚類問題。
- 主要用于發現圓形或者球形簇，不能識别非球形的簇。