k-means聚类算法简介

< 上一页聚类分析简介 DBSCAN聚类算法下一页 >
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}。

参数的含义解释如下。
名称 说明
k 表示期望的聚类的个数。
maxIterations 表示方法单次运行的最大迭代次数。
runs 表示算法被运行的次数。k-means 算法不保证能返回全局最优的聚类结果,所以在目标数据集上多次跑 k-means 算法,有助于返回最佳聚类结果。
initializationMode 表示初始聚类中心点的选择方式,目前支持随机选择或者 K_MEANS_PARALLEL 方式,默认是 K_MEANS_PARALLEL。
initializationsteps 表示 K_MEANS_PARALLEL 方法中的步数。
epsilon 表示 k-means 算法迭代收敛的阈值。
seed 表示集群初始化时的随机种子。

通常应用时,都会先调用 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 的选择往往会是一个比较困难的问题。
  • 对初始值的设置很敏感,算法的结果与初始值的选择有关。
  • 对噪声和异常数据非常敏感。如果某个异常值具有很大的数值,则会严重影响数据分布。
  • 不能解决非凸形状的数据分布聚类问题。
  • 主要用于发现圆形或者球形簇,不能识别非球形的簇。
< 上一页聚类分析简介 DBSCAN聚类算法下一页 >