k-means处理大数据_k_means算法数据标准化处理? - CSDN
  • 使用 Spark MLlib 做 K-means 聚类分析

    千次阅读 2017-06-28 18:58:08
    本文将以聚类分析这个典型的机器学习问题为基础,向读者介绍如何使用 MLlib 提供的 K-means 算法对数据做聚类分析,我们还将通过分析源码,进一步加深读者对 MLlib K-means 算法的实现原理和使用方法的理解。...
    摘要: MLlib 是 Spark 生态系统里用来解决大数据机器学习问题的模块。本文将以聚类分析这个典型的机器学习问题为基础,向读者介绍如何使用 MLlib 提供的 K-means 算法对数据做聚类分析,我们还将通过分析源码,进一步加深读者对 MLlib K-means 算法的实现原理和使用方法的理解。

    引言

    提起机器学习 (Machine Learning),相信很多计算机从业者都会对这个技术方向感到兴奋。然而学习并使用机器学习算法来处理数据却是一项复杂的工作,需要充足的知识储备,如概率论,数理统计,数值逼近,最优化理论等。机器学习旨在使计算机具有人类一样的学习能力和模仿能力,这也是实现人工智能的核心思想和方法。传统的机器学习算法,由于技术和单机存储的限制,只能在少量数据上使用,随着 HDFS(Hadoop Distributed File System) 等分布式文件系统出现,存储海量数据已经成为可能。然而由于 MapReduce 自身的限制,使得使用 MapReduce 来实现分布式机器学习算法非常耗时和消耗磁盘容量。因为通常情况下机器学习算法参数学习的过程都是迭代计算的,即本次计算的结果要作为下一次迭代的输入,这个过程中,如果使用 MapReduce,我们只能把中间结果存储磁盘,然后在下一次计算的时候从新读取,这对于迭代 频发的算法显然是致命的性能瓶颈。Spark 立足于内存计算,天然的适应于迭代式计算,相信对于这点,读者通过前面几篇文章已经有了较为深入的了解。然而即便这样,对于普通开发者来说,实现一个分布式机器学习算法仍然是一件极具挑战的事情。MLlib 正是为了让基于海量数据的机器学习变得更加简单,它提供了常用机器学习算法的分布式实现,开发者只需要有 Spark 基础并且了解机器学习算法的原理,以及方法相关参数的含义,就可以轻松的通过调用相应的 API 来实现基于海量数据的机器学习过程。当然,原始数据 ETL,特征指标提取,调节参数并优化学习过程,这依然需要有足够的行业知识和数据敏感度,这往往也是经验的体现。本文的重点在于向读者介绍如何使用 MLlib 机器学习库提供的 K-means 算法做聚类分析,这是一个有意义的过程,相信会对读者特别是初学者有启发意义。

    Spark 机器学习库简介

    Spark 机器学习库提供了常用机器学习算法的实现,包括聚类,分类,回归,协同过滤,维度缩减等。使用 Spark 机器学习库来做机器学习工作,可以说是非常的简单,通常只需要在对原始数据进行处理后,然后直接调用相应的 API 就可以实现。但是要想选择合适的算法,高效准确地对数据进行分析,您可能还需要深入了解下算法原理,以及相应 Spark MLlib API 实现的参数的意义。

    需要提及的是,Spark 机器学习库从 1.2 版本以后被分为两个包,分别是:

    • spark.mllib

    Spark MLlib 历史比较长了,1.0 以前的版本中已经包含了,提供的算法实现都是基于原始的 RDD,从学习角度上来讲,其实比较容易上手。如果您已经有机器学习方面的经验,那么您只需要熟悉下 MLlib 的 API 就可以开始数据分析工作了。想要基于这个包提供的工具构建完整并且复杂的机器学习流水线是比较困难的。

    • spark.ml

    Spark ML Pipeline 从 Spark1.2 版本开始,目前已经从 Alpha 阶段毕业,成为可用并且较为稳定的新的机器学习库。ML Pipeline 弥补了原始 MLlib 库的不足,向用户提供了一个基于 DataFrame 的机器学习工作流式 API 套件,使用 ML Pipeline API,我们可以很方便的把数据处理,特征转换,正则化,以及多个机器学习算法联合起来,构建一个单一完整的机器学习流水线。显然,这种新的方式给我们提供了更灵活的方法,而且这也更符合机器学习过程的特点。

    从官方文档来看,Spark ML Pipeline 虽然是被推荐的机器学习方式,但是并不会在短期内替代原始的 MLlib 库,因为 MLlib 已经包含了丰富稳定的算法实现,并且部分 ML Pipeline 实现基于 MLlib。而且就笔者看来,并不是所有的机器学习过程都需要被构建成一个流水线,有时候原始数据格式整齐且完整,而且使用单一的算法就能实现目标,我们就没有必要把事情复杂化,采用最简单且容易理解的方式才是正确的选择。

    本文基于 Spark 1.5,向读者展示使用 MLlib API 进行聚类分析的过程。读者将会发现,使用 MLlib API 开发机器学习应用方式是比较简单的,相信本文可以使读者建立起信心并掌握基本方法,以便在后续的学习和工作中事半功倍。

    K-means 聚类算法原理

    聚类分析是一个无监督学习 (Unsupervised Learning) 过程, 一般是用来对数据对象按照其特征属性进行分组,经常被应用在客户分群,欺诈检测,图像分析等领域。K-means 应该是最有名并且最经常使用的聚类算法了,其原理比较容易理解,并且聚类效果良好,有着广泛的使用。

    和诸多机器学习算法一样,K-means 算法也是一个迭代式的算法,其主要步骤如下:

    • 第一步,选择 K 个点作为初始聚类中心。
    • 第二步,计算其余所有点到聚类中心的距离,并把每个点划分到离它最近的聚类中心所在的聚类中去。在这里,衡量距离一般有多个函数可以选择,最常用的是欧几里得距离 (Euclidean Distance), 也叫欧式距离。公式如下:

    Figure xxx. Requires a heading

    其中 C 代表中心点,X 代表任意一个非中心点。

    • 第三步,重新计算每个聚类中所有点的平均值,并将其作为新的聚类中心点。
    • 最后,重复 (二),(三) 步的过程,直至聚类中心不再发生改变,或者算法达到预定的迭代次数,又或聚类中心的改变小于预先设定的阀值。

    在实际应用中,K-means 算法有两个不得不面对并且克服的问题。

    1. 聚类个数 K 的选择。K 的选择是一个比较有学问和讲究的步骤,我们会在后文专门描述如何使用 Spark 提供的工具选择 K。
    2. 初始聚类中心点的选择。选择不同的聚类中心可能导致聚类结果的差异。

    Spark MLlib K-means 算法的实现在初始聚类点的选择上,借鉴了一个叫 K-means||的类 K-means++ 实现。K-means++ 算法在初始点选择上遵循一个基本原则: 初始聚类中心点相互之间的距离应该尽可能的远。基本步骤如下:

    • 第一步,从数据集 X 中随机选择一个点作为第一个初始点。
    • 第二步,计算数据集中所有点与最新选择的中心点的距离 D(x)。
    • 第三步,选择下一个中心点,使得最大。
    • 第四部,重复 (二),(三) 步过程,直到 K 个初始点选择完成。

     

    MLlib 的 K-means 实现

    Spark MLlib 中 K-means 算法的实现类 (KMeans.scala) 具有以下参数,具体如下。

    图 1. MLlib K-means 算法实现类预览

    图 1. MLlib K-means 算法实现类预览

    通过下面默认构造函数,我们可以看到这些可调参数具有以下初始值。

    图 2. MLlib K-means 算法参数初始值

    图 2. MLlib K-means 算法参数初始值

    参数的含义解释如下:

    • k 表示期望的聚类的个数。
    • maxInterations 表示方法单次运行最大的迭代次数。
    • runs 表示算法被运行的次数。K-means 算法不保证能返回全局最优的聚类结果,所以在目标数据集上多次跑 K-means 算法,有助于返回最佳聚类结果。
    • initializationMode 表示初始聚类中心点的选择方式, 目前支持随机选择或者 K-means||方式。默认是 K-means||。
    • initializationSteps表示 K-means||方法中的部数。
    • epsilon 表示 K-means 算法迭代收敛的阀值。
    • seed 表示集群初始化时的随机种子。

    通常应用时,我们都会先调用 KMeans.train 方法对数据集进行聚类训练,这个方法会返回 KMeansModel 类实例,然后我们也可以使用 KMeansModel.predict 方法对新的数据点进行所属聚类的预测,这是非常实用的功能。

    KMeans.train 方法有很多重载方法,这里我们选择参数最全的一个展示。

    图 3. KMeans.train 方法预览

    图 3. KMeans.train 方法预览

    KMeansModel.predict 方法接受不同的参数,可以是向量,或者 RDD,返回是入参所属的聚类的索引号。

    图 4. KMeansModel.predict 方法预览

    图 4. KMeansModel.predict 方法预览

     

    聚类测试数据集简介

    在本文中,我们所用到目标数据集是来自 UCI Machine Learning Repository 的 Wholesale customer Data Set。UCI 是一个关于机器学习测试数据的下载中心站点,里面包含了适用于做聚类,分群,回归等各种机器学习问题的数据集。

    Wholesale customer Data Set 是引用某批发经销商的客户在各种类别产品上的年消费数。为了方便处理,本文把原始的 CSV 格式转化成了两个文本文件,分别是训练用数据和测试用数据。

    图 5. 客户消费数据格式预览

    图 5. 客户消费数据格式预览

    读者可以从标题清楚的看到每一列代表的含义,当然读者也可以到 UCI 网站上去找到关于该数据集的更多信息。虽然 UCI 的数据可以自由获取并使用,但是我们还是在此声明,该数据集的版权属 UCI 以及其原始提供组织或公司所有。

     

    案例分析和编码实现

    本例中,我们将根据目标客户的消费数据,将每一列视为一个特征指标,对数据集进行聚类分析。代码实现步骤如下

    清单 1. 聚类分析实现类源码
    import org.apache.spark.{SparkContext, SparkConf}
    import org.apache.spark.mllib.clustering.{KMeans, KMeansModel}
    import org.apache.spark.mllib.linalg.Vectors
    object KMeansClustering {
     def main (args: Array[String]) {
     if (args.length < 5) {
    
        println("Usage:KMeansClustering trainingDataFilePath testDataFilePath numClusters
        numIterations runTimes")
     sys.exit(1)
     }
    
     val conf = new
        SparkConf().setAppName("Spark MLlib Exercise:K-Means Clustering")
     val sc = new SparkContext(conf)
    
       /**
     *Channel Region Fresh Milk Grocery Frozen Detergents_Paper Delicassen
     * 2 3
         12669 9656 7561 214 2674 1338
     * 2 3 7057 9810 9568 1762 3293 1776
     * 2 3 6353 8808
         7684 2405 3516 7844
     */
    
        val rawTrainingData = sc.textFile(args(0))
     val parsedTrainingData =
        rawTrainingData.filter(!isColumnNameLine(_)).map(line => {
    
        Vectors.dense(line.split("\t").map(_.trim).filter(!"".equals(_)).map(_.toDouble))
     }).cache()
    
        // Cluster the data into two classes using KMeans
    
        val numClusters = args(2).toInt
     val numIterations = args(3).toInt
     val runTimes =
        args(4).toInt
     var clusterIndex:Int = 0
     val clusters:KMeansModel =
        KMeans.train(parsedTrainingData, numClusters, numIterations,runTimes)
    
        println("Cluster Number:" + clusters.clusterCenters.length)
    
        println("Cluster Centers Information Overview:")
     clusters.clusterCenters.foreach(
        x => {
    
        println("Center Point of Cluster " + clusterIndex + ":")
    
        println(x)
     clusterIndex += 1
     })
    
        //begin to check which cluster each test data belongs to based on the clustering result
    
        val rawTestData = sc.textFile(args(1))
     val parsedTestData = rawTestData.map(line =>
        {
    
        Vectors.dense(line.split("\t").map(_.trim).filter(!"".equals(_)).map(_.toDouble))
    
        })
     parsedTestData.collect().foreach(testDataLine => {
     val predictedClusterIndex:
        Int = clusters.predict(testDataLine)
    
        println("The data " + testDataLine.toString + " belongs to cluster " +
        predictedClusterIndex)
     })
    
        println("Spark MLlib K-means clustering test finished.")
     }
    
     private def
        isColumnNameLine(line:String):Boolean = {
     if (line != null &&
        line.contains("Channel")) true
     else false
     }

    该示例程序接受五个入参,分别是

    • 训练数据集文件路径
    • 测试数据集文件路径
    • 聚类的个数
    • K-means 算法的迭代次数
    • K-means 算法 run 的次数

    运行示例程序

    和本系列其他文章一样,我们依然选择使用 HDFS 存储数据文件。运行程序之前,我们需要将前文提到的训练和测试数据集上传到 HDFS。

    图 6. 测试数据的 HDFS 目录

    图 6. 测试数据的 HDFS 目录

    清单 2. 示例程序运行命令
    ./spark-submit --class com.ibm.spark.exercise.mllib.KMeansClustering \
     --master spark://<spark_master_node_ip>:7077 \
     --num-executors 6 \
    --driver-memory 3g \
    --executor-memory 512m \
    --total-executor-cores 6 \
     /home/fams/spark_exercise-1.0.jar \
     hdfs://<hdfs_namenode_ip>:9000/user/fams/mllib/wholesale_customers_data_training.txt \
     hdfs://<hdfs_namenode_ip>:9000/user/fams/mllib/wholesale_customers_data_test.txt \
     8 30 3
    图 7. K-means 聚类示例程序运行结果

    图 7. K-means 聚类示例程序运行结果

     

    如何选择 K

    前面提到 K 的选择是 K-means 算法的关键,Spark MLlib 在 KMeansModel 类里提供了 computeCost 方法,该方法通过计算所有数据点到其最近的中心点的平方和来评估聚类的效果。一般来说,同样的迭代次数和算法跑的次数,这个值越小代表聚类的效果越好。但是在实际情况下,我们还要考虑到聚类结果的可解释性,不能一味的选择使 computeCost 结果值最小的那个 K。

    清单 3. K 选择示例代码片段
    val ks:Array[Int] = Array(3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)
    ks.foreach(cluster => {
     val model:KMeansModel = KMeans.train(parsedTrainingData, cluster,30,1)
     val ssd = model.computeCost(parsedTrainingData)
     println("sum of squared distances of points to their nearest center when k=" + cluster + " -> "+ ssd)
    })
    图 8. K 选择示例程序运行结果

    图 8. K 选择示例程序运行结果

    从上图的运行结果可以看到,当 K=9 时,cost 值有波动,但是后面又逐渐减小了,所以我们选择 8 这个临界点作为 K 的个数。当然可以多跑几次,找一个稳定的 K 值。理论上 K 的值越大,聚类的 cost 越小,极限情况下,每个点都是一个聚类,这时候 cost 是 0,但是显然这不是一个具有实际意义的聚类结果。

    展开全文
  • K-Means算法是常用的聚类算法,但其算法本身存在一定的问题,例如在大数据量下的计算时间过长就是一个重要问题。为此,Mini Batch K-Means,这个基于K-Means的变种聚类算法应运而生。 大数据量是什么量级?通过...

    K-Means算法是常用的聚类算法,但其算法本身存在一定的问题,例如在大数据量下的计算时间过长就是一个重要问题。为此,Mini Batch K-Means,这个基于K-Means的变种聚类算法应运而生。

    大数据量是什么量级?通过当样本量大于1万做聚类时,就需要考虑选用Mini Batch K-Means算法。但是,在选择算法时,除了算法效率(运行时间)外,算法运行的准确度也是选择算法的重要因素。Mini Batch K-Means算法的准确度如何?

    minibatchkmeans11

    上图是我们队3万的样本点分别使用K-Means和Mini Batch KMeans进行聚类的结果,由结果可知,在3万样本点的基础上,二者的运行时间相差2倍多,但聚类结果差异却很小(右侧粉红色的错误点)。

    因此,Mini Batch KMeans是一种能尽量保持聚类准确性下但能大幅度降低计算时间的聚类模型。

    K-Means的计算时间到底跟样本量之间是怎样的关系(用脚想也知道是样本量越大,计算时间越长),我们用一个实例来实验下。在下面的例子中,利用Python生成一个具有三个分类类别的样本类,其中的样本点(二维空间)的数量从100开始增长到1000000(步长为1000),我们用图例来看看计算时间与样本量的关系。(为了得到下面这幅图,我等了2个小时)结果如下:

    time_minibatchkmeans11

    从图中可以发现,在样本点为二维空间前提下,当数据量在2之下时,计算时间都可以接受(2秒以内);但是计算时间跟数据量基本成线性关系,计算1000000个样本聚类耗时近16秒。由此可以试想,如果你的观测点有更多维度(更多维度意味着需要更多的计算量),那么耗时将比上述场景大很多。

    回到本文的主体算法Mini Batch KMeans上来,应用Mini Batch KMeans能尽量在保持数据准确性的前提下降低运算时间,它是怎么做到的?

    Mini Batch KMeans使用了一个种叫做Mini Batch(分批处理)的方法对数据点之间的距离进行计算。Mini Batch的好处是计算过程中不必使用所有的数据样本,而是从不同类别的样本中抽取一部分样本来代表各自类型进行计算。由于计算样本量少,所以会相应的减少运行时间,但另一方面抽样也必然会带来准确度的下降。

    实际上,这种思路不仅应用于K-Means聚类,还广泛应用于梯度下降、深度网络等机器学习和深度学习算法。

    Mini Batch KMeans的使用方法非常简单,跟K-Means一样,在Python的机器学习库SKlearn中,通过fit方法训练数据,然后通过labels_ 属性获得每个样本点的聚类结果值。演示代码如下:

    1. #coding:utf-8
    2. import numpy as np
    3. from sklearn.cluster import MiniBatchKMeans
    4. from sklearn import datasets
    5. np.random.seed(5)
    6. iris = datasets.load_iris()
    7. X = iris.data
    8. clf = MiniBatchKMeans(n_clusters = 3)
    9. clf.fit(X)
    10. pre_clu = clf.labels_
    11. #将原始数据集X和聚类结果标签组合成新数据集并输出前10条
    12. new_X = np.column_stack((X, pre_clu))
    13. print new_X[:10]

    运行结果如下:

    1. array([[ 5.1,  3.5,  1.4,  0.2,  1. ],
    2.        [ 4.9,  3. ,  1.4,  0.2,  1. ],
    3.        [ 4.7,  3.2,  1.3,  0.2,  1. ],
    4.        [ 4.6,  3.1,  1.5,  0.2,  1. ],
    5.        [ 5. ,  3.6,  1.4,  0.2,  1. ],
    6.        [ 5.4,  3.9,  1.7,  0.4,  1. ],
    7.        [ 4.6,  3.4,  1.4,  0.3,  1. ],
    8.        [ 5. ,  3.4,  1.5,  0.2,  1. ],
    9.        [ 4.4,  2.9,  1.4,  0.2,  1. ],
    10.        [ 4.9,  3.1,  1.5,  0.1,  1. ]])

     

    应用场景,由于Mini Batch KMeans跟K-Means是极其相似的两种聚类算法,因此应用场景基本一致,具体请参考K均值(K-Means)

    其中,Mini Batch KMeans可配置的参数如下:

    1. class sklearn.cluster.MiniBatchKMeans(n_clusters=8, init='k-means++', max_iter=100, batch_size=100, verbose=0, compute_labels=True, random_state=None, tol=0.0, max_no_improvement=10, init_size=None, n_init=3, reassignment_ratio=0.01)

     


     

    尾巴

    默认情况下,无论是K-Means还是MiniBatchKMeans都是需要指定聚类数量,即算法里面的n_clusters参数值,但实际应用时发现不指定也是可以的。这并不意味着Python会“自动”帮你选择最佳类别数,而是已经预置了一个默认的类别8。如果你不去设置,它会默认分为8个类别。既然是通过Mini Batch进行抽样,那到底Mini Batch是什么?Mini Batch是原始数据集中的子集,这个子集是在每次训练迭代时抽取抽取的样本。这个值默认是100个,可以通过batch_size进行设置。

    展开全文
  • K-Means聚类算法的研究与改进

    万次阅读 2018-04-25 17:33:57
    Means聚类算法的研究与改进*1(华中师范大学 计算机学院,湖北 武汉 430079)摘 要:K-Means算法是基于划分的聚类算法中的一个典型算法,该算法有操作简单、采用误差平方和准则函数、对大数据集的处理上有较高的伸缩性...

    代码:https://github.com/dengsiying/K-Means-improvement.git

    K-Means聚类算法的研究与改进*

    1(华中师范大学 计算机学院,湖北 武汉  430079)

    摘 要:K-Means算法是基于划分的聚类算法中的一个典型算法,该算法有操作简单、采用误差平方和准则函数、对大数据集的处理上有较高的伸缩性和可压缩性的优点.但是该算法还存在着一些随机初始聚类中心导致算法不稳定的缺陷,本文研究了传统K-Means的算法的思想、原理及优缺点,并针对其对初始值依赖的缺陷,提出并研究了一种改进算法K-Means++,该算法对选取初始聚类中心的方法进行了改进.经过实验证明,K-Means++算法有效的提高了算法效率和稳定性,减少了算法开销.

    关键词:聚类算法,K-Means算法,数据挖掘

    Research and Improvement of K-Means Clustering Algorithm

    Abstract: K-Means algorithm is a typical algorithm based on partitioned clustering algorithm. It has the advantages of simple operation, error squared sum criteria function, high scalability and compressibility for processing large data sets advantage. However, there are still some shortcomings in this algorithm, such as stochastic initial clustering center, which results in instability of the algorithm. This paper studies the concept, principle, advantages and disadvantages of the traditional K-Means algorithm and proposes and studies the defects of the original K- An improved algorithm K-Means ++, which improves the method of selecting initial cluster centers. Experimental results show that the K-Means ++ algorithm effectively improves the efficiency and stability of the algorithm and reduces the cost of the algorithm.

    Key words: clustering algorithm, K-Means algorithm, data mining

    K-Means聚类算法是最为经典,同时也是使用最为广泛的一种基于划分的聚类算法,它属于基于距离的聚类算法.所谓基于距离的聚类算法是指采用距离作为相似性度量的评价指标,也就是说两个对象之间距离越近,则它们的相似性越大.这类算法的目标通常是将距离比较相近的对象组成簇,从而得到紧凑而独立的不同簇,因此将这种算法称为基于距离的聚类算法.K-Means聚类算法就是其中比较经典的一种算法,作为数据挖掘的重要分支,K-Means聚类算法具有算法简单、易于实现、易于扩展,并且能够处理大数据集的优点,但K-Means也有一些不可避免的缺点,比如对初值的比较敏感,不同的初始聚类中心会导致不同的聚类结果,使得算法不稳定,容易陷入局部最优的情况.本文针对K-Means算法的这个缺点提出一种改进算法,实验证明改进算法能够有效提高算法效率和稳定性,并且减少损失.

    本文第一节介绍了传统K-Means算法的原理、算法步骤及优缺点;第二节针对传统K-Means算法随机选取初始聚类中心的做法会导致算法的不稳定性的缺点提出了改进算法K-Means++,其主要思想是在选取初始中心聚类的时候遵循初始的聚类中心之间的距离应尽可能远的原则;第三节实现了K-Means和K-Means++算法,并将两个算法做了比较,实验证明K-Means++算法有效提高了算法的效率和稳定性,最后对本文进行了总结.

    1  传统K-Means算法

    1.1 K-Means算法原理

    K-means算法采用迭代更新的思想,该算法的目标是根据输入的参数k(k表示需要将数据对象聚成几簇),其基本思想为:首先指定需要划分的簇的个数k值,随机地选择k个初始数据对象作为初始聚类或簇的中心;然后计算其余的各个数据对象到这k个初始聚类中心的距离,并把数据对象划分到距离它最近的那个中心所在的簇类中;然后重新计算每个簇的中心作为下一次迭代的聚类中心.不断重复这个过程,直到各聚类中心不再变化时或者迭代达到规定的最大迭代次数时终止.迭代使得选取的聚类中心越来越接近真实的簇中心,所以聚类效果越来越好,最后把所有对象划分为k个簇.

    1.2 K-Means算法步骤

    K-Means算法步骤如下:


    1.3 K-Means算法优缺点

    K-means算法是解决聚类问题的经典算法,这种算法简单快速.当结构集是密集的,簇与簇之间区别明显时,聚类的结果比较好.在处理大量数据时,该算法具有较高的可伸缩性和高效性,它的时间复杂度为O (nkt),n是样本对象的个数,k是分类数目,t是算法的迭代次数.一般情况下,k<<n,t<<n.

    但是,目前传统的K-means算法也存在着许多缺点,有待于进一步优化.

    (1) K-Means聚类算法需要用户事先指定聚类的个数k.在很多时候,在对数据集进行聚类的时候,用户起初并不清楚数据集应该分为多少类合适,k值难以估计.

    (2) 对初始聚类中心敏感,选择不同的聚类中心会产生不同的聚类结果和不同的准确率.随机选取初始聚类中心的做法会导致算法的不稳定性,有可能陷入局部最优的情况.

    (3) 对噪声和孤立点数据敏感,K-Means算法将簇的质心看成聚类中心加入到下一轮计算当中,因此少量的该类数据都能够对平均值产生极大影响,导致结果的不稳定甚至错误.

    (4) 无法发现任意簇,一般只能发现球状簇.因为K-Means算法主要采用欧式距离函数度量数据对象之间的相似度,并且采用误差平方和作为准则函数,通常只能发现数据对象分布较均匀的球状簇.

    本文主要针对K-Means算法的第二个问题即初始值对聚类结果的影响进行分析和研究,考虑改进初始聚类中心的选择,从而减少K-Means算法对初始值的依赖性,提高算法效率.

    2  改进算法K-Means++

    2.1 K-Means++算法原理

    传统的K-means算法对初始聚类中心敏感,聚类结果随不同的初始聚类中心而波动.针对K-means聚类算法中随机选取初始聚类中心的缺陷,提出了一种新的基于数据分布选取初始聚类中心的K-Means++算法.

    K-Means++算法在整体思想上与K-Means算法相差不大,同样是采取迭代更新的思想.其主要改进在第一步选取k个初始聚类中心时,不再是在整个数据集中随机选取k个数据对象作为初始聚类中心,而是遵循初始的聚类中心之间的距离应尽可能远的原则选取k个初始聚类中心.K-Means++算法选取初始聚类中心的主要思想为:假设已经选取了n个初始聚类中心(0<n<k),则在选取第n+1个聚类中心时:距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心.在选取第一个聚类中心(n=1)时同样通过随机的方法.

    2.2 K-Means++算法步骤

    K-Means++算法步骤如下:


    综上所述即为K-Means++算法的完整步骤.

    3  改进算法K-Means++与K-Means算法的比较

    3.1 数据集 

    我们使用了一个简单的包含300个样本,每个样本具有两个属性的二维数据集,将其可视化如下图1所示,可以看到数据集大概分为3簇,因此我们将k值确定为3,在此基础上实K-Means算法和该改进后的K-Means++算法.

     

    1  数据集

    3.2 评估标准

    上文提到K-Means算法采用误差平方和准则函数,算法目标则是最优化该误差平方和准则函数,并且本文中实现算法时使用的停止条件为达到最大迭代次数.因此,我们使用误差平方和(SSE)作为算法的评估标准.

                                                 1

    其中dist表示每个点到它所属的簇的中心点的距离,SSE值即为所有样本点到它所属的簇的中心点的距离的平方和.在相同迭代次数的条件下,SSE值越小,则说明算法越好,损失越小.

    3.3 算法比较

    在数据集上分别使用K-Means算法和K-Means++算法,迭代次数与算法的SSE值的关系如下表1所示(保留小数点后两位).

     

    Table 1 .Comparison of two algorithms SSE value

    1 两种算法SSE值比较

    迭代次数

    K-Means算法SSE值

    K-Means++算法SSE值

    2

    872.47

    266.82

    3

    851.15

    266.66

    4

    690.14

    266.66

    6

    276.68

    266.66

    8

    266.66

    266.66

    10

    266.66

    266.66

     

    根据上表可以看出,传统K-Means算法在第8次迭代时收敛至全局最小值,此时的SSE值为266.66,而K-Means++算法在第3次迭代时就已经收敛至全局最小值,此时的SSE值也为266.66.因此可以证明改进后的K-Means++算法效率大大提升,能够在开销更小的情况下,快速而稳定的收敛至全局最小值,达到较好的聚类效果.

    迭代次数为4时,将两种算法的聚类结果可视化如下图2、图3所示.由两张结果图对比可以看出,K-Means++算法的聚类效果比K-Means算法更好,能够更清楚的将原始数据点按照距离相似性的远近分成了3簇,其中红色X标记为最后一次分类的样本中心点.

    另外,经过实验证明,迭代次数足够大并且实验次数足够多时,K-Means算法和K-Means++算法都能够收敛至全局最小值,最终也都能达到较好的聚类效果.但是K-Means算法选取初始聚类中心的随机导致了K-Means算法的不稳定性,在改进了选取初始聚类中心的方法以后,K-Means++算法能够更快的收敛,算法效果更好.

    综上,可以得到结论,改进后的K-Means++算法在一定程度上降低了传统K-Means算法对初始值的依赖,降低了算法的不稳定性,有效提高了算法效率,减少了算法开销.

     

    2 K-Means聚类效果(迭代次数4

     

    3 K-Means++ 聚类效果(迭代次数4

    4  小结

    K-Means聚类算法作为基于划分聚类算法的一个典型算法,在数据挖掘中被广泛应用,经常被用来作为预处理步骤.本文重点研究了K-Means算法的思想、原理及其优缺点,并针对传统K-Means算法随机选取初始聚类中心导致算法不稳定的缺点提出了改进算法K-Means++,K-Means++算法是基于数据分布选取初始聚类中心的改进算法,其主要思想是初始的聚类中心之间的距离应尽可能远的思想.本文也重点研究了K-Means++算法的思想与原理,其改进可以有效避免随机选取初始聚类中心的盲目性,实验证明改进后的K-Means++算法在稳定性和速度上都比传统K-Means算法有了较大的提升.

     

    References:

    [1] 王莉. 数据挖掘中聚类方法的研究[D].天津大学,2004.

    [2] 常彤.K-means算法及其改进研究现状[J].通讯世界,2017(19):289-290.

    [3] 陈伟,李红,王维.一种基于Python的K-means聚类算法分析[J].数字技术与应用,2017(10):118-119.

    [4] 张琳,陈燕,汲业,张金松.一种基于密度的K-means算法研究[J].计算机应用研究,2011,28(11):4071-4073+4085.

    [5] 李卫平.对k-means聚类算法的改进研究[J].中国西部科技,2010,9(24):49-50.

    [6] 夏长辉.一种改进的K-means聚类算法[J].信息与电脑(理论版),2017(14):40-42.

    [7] 孙佳,胡明,赵佳.K-means初始聚类中心选取优化算法[J].长春工业大学学报,2016,37(01):25-29.

    [8] David Arthur,Sergei Vassilvitskii. k-means++: The Advantages of Careful Seeding.symposium on discrete algorithms.2007.http://ilpubs.stanford.edu:8090/778/1/2006-13.pdf

     

     

    展开全文
  • 大数据十大经典算法之k-means

    千次阅读 2014-11-06 11:06:29
    处理流程: 1、为每个聚类确定一个初始聚类中心,这样就有k个初始聚类中心; 2、将样本按照最小距离原则分配到最邻近聚类 3、使用每个聚类中的样本均值作为新的聚类中心 4、重复步骤2直到聚类中心不再变化 5、...

    k均值算法基本思想:

    K均值算法是基于质心的技术。它以K为输入参数,把n个对象集合分为k个簇,使得簇内的相似度高,簇间的相似度低。


    处理流程:

    1、为每个聚类确定一个初始聚类中心,这样就有k个初始聚类中心;

    2、将样本按照最小距离原则分配到最邻近聚类

    3、使用每个聚类中的样本均值作为新的聚类中心

    4、重复步骤2直到聚类中心不再变化

    5、结束,得到K个聚类


    划分聚类方法对数据集进行聚类时的要点:

    1、选定某种距离作为数据样本间的相似性度量,通常选择欧氏距离。

    2、选择平价聚类性能的准则函数

    用误差平方和准则函数来评价聚类性能。

    3、相似度的计算分局一个簇中对象的平均值来进行


    K均值算法的优点:

    如果变量很大,K均值比层次聚类的计算速度较快(如果K很小);

    与层次聚类相比,K均值可以得到更紧密的簇,尤其是对于球状簇;

    对于大数据集,是可伸缩和高效率的;

    算法尝试找出使平方误差函数值最小的k个划分。当结果簇是密集的,而簇与簇之间区别明显的时候,效果较好。


    K均值算法缺点:

    最后结果受初始值的影响。解决办法是多次尝试取不同的初始值。

    可能发生距离簇中心m最近的样本集为空的情况,因此m得不到更新。这是一个必须处理的问题,但我们忽略该问题。

    不适合发现非凸面形状的簇,并对噪声和离群点数据较敏感,因为少量的这类数据能够对均值产生较大的影响。


    K均值算法的改进:

    样本预处理。计算样本对象量量之间的距离,筛掉与其他所有样本那的距离和最大的m个对象。

    初始聚类中心的选择。选用簇中位置最靠近中心的对象,这样可以避免孤立点的影响。

    K均值算法的变种:

    K众数(k-modes)算法,针对分类属性的度量和更新质心的问题而改进。

    EM(期望最大化)算法

    k-prototype算法

    这种算法不适合处理离散型属性,但是对于连续型具有较好的聚类效果。

    k均值算法用途:

    图像分割;

    衡量足球队的水平;

    下面给出代码:

    #include <iostream>
    #include <vector>
    //auther archersc
    //JLU
    namespace CS_LIB
    {
    using namespace std;
    class Kmean
    {
    public:
       //输入格式
       //数据数量N 维度D
       //以下N行,每行D个数据
       istream& loadData(istream& in);
       //输出格式
       //聚类的数量CN
       //中心维度CD
       //CN行,每行CD个数据
       //数据数量DN
       //数据维度DD
       //以下DN组,每组的第一行两个数值DB, DDis
       //第二行DD个数值
       //DB表示改数据属于一类,DDis表示距离改类的中心的距离
       ostream& saveData(ostream& out);
       //设置中心的数量
       void setCenterCount(const size_t count);
       size_t getCenterCount() const;
       //times最大迭代次数, maxE ,E(t)表示第t次迭代后的平方误差和,当|E(t+1) - E(t)| < maxE时终止
       void clustering(size_t times, double maxE);
    
    private:
       double calDistance(vector<double>& v1, vector<double>& v2);
    
    private:
       vector< vector<double> > m_Data;
       vector< vector<double> > m_Center;
       vector<double> m_Distance;
       vector<size_t> m_DataBelong;
       vector<size_t> m_DataBelongCount;
    };
    }
    #include "kmean.h"
    
    #include <ctime>
    #include <cmath>
    #include <cstdlib>
    //auther archersc
    //JLU
    
    namespace CS_LIB
    {
    template<class T>
    void swap(T& a, T& b)
    {
       T c = a;
       a = b;
       b = c;
    }
    
    istream& Kmean::loadData(istream& in)
    {
       if (!in){
        cout << "input error" << endl;
        return in;
       }
       size_t dCount, dDim;
       in >> dCount >> dDim;
       m_Data.resize(dCount);
       m_DataBelong.resize(dCount);
       m_Distance.resize(dCount);
       for (size_t i = 0; i < dCount; ++i){
        m_Data[i].resize(dDim);
        for (size_t j = 0; j < dDim; ++j){
         in >> m_Data[i][j];
        }
       }
       return in;
    }
    ostream& Kmean::saveData(ostream& out)
    {
       if (!out){
        cout << "output error" << endl;
        return out;
       }
       out << m_Center.size();
       if (m_Center.size() > 0)
        out << ' ' << m_Center[0].size();
       else
        out << ' ' << 0;
       out << endl << endl;
       for (size_t i = 0; i < m_Center.size(); ++i){
        for (size_t j = 0; j < m_Center[i].size(); ++j){
         out << m_Center[i][j] << ' ';
        }
        out << endl;
       }
       out << endl;
       out << m_Data.size();
       if (m_Data.size() > 0)
        out << ' ' << m_Data[0].size();
       else
        out << ' ' << 0;
       out << endl << endl;
       for (size_t i = 0; i < m_Data.size(); ++i){
        out << m_DataBelong[i] << ' ' << m_Distance[i] << endl;
        for (size_t j = 0; j < m_Data[i].size(); ++j){
         out << m_Data[i][j] << ' ';
        }
        out << endl << endl;
       }
       return out;
    }
    void Kmean::setCenterCount(const size_t count)
    {
       m_Center.resize(count);
       m_DataBelongCount.resize(count);
    }
    size_t Kmean::getCenterCount() const
    {
       return m_Center.size();
    }
    void Kmean::clustering(size_t times, double maxE)
    {
       srand((unsigned int)time(NULL));
       //随机从m_Data中选取m_Center.size()个不同的样本点作为初始中心。
       size_t *pos = new size_t[m_Data.size()];
       size_t i, j, t;
       for (i = 0; i < m_Data.size(); ++i){
        pos[i] = i;
       }
       for (i = 0; i < (m_Data.size() << 1); ++i){
        size_t s1 = rand() % m_Data.size();
        size_t s2 = rand() % m_Data.size();
        swap(pos[s1], pos[s2]);
       }
       for (i = 0; i < m_Center.size(); ++i){
        m_Center[i].resize(m_Data[pos[i]].size());
        for (j = 0; j < m_Data[pos[i]].size(); ++j){
         m_Center[i][j] = m_Data[pos[i]][j];
        }
       }
       delete []pos;
       double currE, lastE;
       for (t = 0; t < times; ++t){
        for (i = 0; i < m_Distance.size(); ++i)
         m_Distance[i] = LONG_MAX;
        for (i = 0; i < m_DataBelongCount.size(); ++i)
         m_DataBelongCount[i] = 0;
        currE = 0.0;
        for (i = 0; i < m_Data.size(); ++i){
         for (j = 0; j < m_Center.size(); ++j){
          double dis = calDistance(m_Data[i], m_Center[j]);
          if (dis < m_Distance[i]){
           m_Distance[i] = dis;
           m_DataBelong[i] = j;
          }
         }
         currE += m_Distance[i];
         m_DataBelongCount[m_DataBelong[i]]++;
        }
        cout << currE << endl;
        if (t == 0 || fabs(currE - lastE) > maxE)
         lastE = currE;
        else
         break;
        for (i = 0; i < m_Center.size(); ++i){
         for (j = 0; j < m_Center[i].size(); ++j)
          m_Center[i][j] = 0.0;
        
        }
        for (i = 0; i < m_DataBelong.size(); ++i){
         for (j = 0; j < m_Data[i].size(); ++j){
          m_Center[m_DataBelong[i]][j] += m_Data[i][j] / m_DataBelongCount[m_DataBelong[i]];
         }
        } 
       }
    }
    double Kmean::calDistance(vector<double>& v1, vector<double>& v2)
    {
       double result = 0.0;
       for (size_t i = 0; i < v1.size(); ++i){
        result += (v1[i] - v2[i]) * (v1[i] - v2[i]);
       }
       return pow(result, 1.0 / v1.size());
    //return sqrt(result);
    }
    }
    #include <iostream>
    #include <fstream>
    #include "kmean.h"
    using namespace std;
    using namespace CS_LIB;
    
    int main()
    {
    ifstream in("in.txt");
    ofstream out("out.txt");
    Kmean kmean;
    kmean.loadData(in);
    kmean.setCenterCount(4);
    kmean.clustering(1000, 0.000001);
    kmean.saveData(out);
    
    return 0;
    }
    



    展开全文
  • K-means原理、优化及应用

    万次阅读 多人点赞 2018-08-23 14:48:59
    K-Means算法是无监督的聚类算法,它实现起来比较简单,聚类效果也不错,因此...包括初始化优化K-Means++, 距离计算优化elkan K-Means算法和大数据情况下的优化Mini Batch K-Means算法。 1. K-Means原理初探  K-Me...
  • 一、k-means:在大数据的条件下,会耗费大量的时间和内存。 优化k-means的建议: 1、减少聚类的数目K。因为,每个样本都要跟类中心计算距离。 2、减少样本的特征维度。比如说,通过PCA等进行降维。 3、考察其他的...
  • K-Means聚类算法的4个步骤流程!

    万次阅读 2016-11-14 16:38:47
    聚类分析是我们数据挖掘中常用的算法,常常用于没有分类,但又有相关相似性的样本研究当中,包括了K-MeansK-中心点和系统聚类三种算法,各自有各自的特点和适用环境。今天我们大圣众包根据网络资源详细介绍下K-...
  • K-Means算法整理

    2019-09-06 22:00:01
    文章目录K-Means算法评价指标算法改进算法优缺点 K-Means算法 K-means是无监督学习算法。 K-Mean算法步骤: 首先随机选定k个样本点作为初始簇中心; 计算所有样本点到簇中心的距离; 每个样本点选择与它距离最近...
  • 文章目录6.5 算法优化学习目标1 Canopy算法配合初始聚类1.1 Canopy算法配合初始聚类实现流程1.2 Canopy算法的优缺点2 K-means++3 二分k-means4 k-medoids(k-中心聚类算法)5 Kernel k-means(了解)6 ISODATA(了解...
  • 本文转载自:k-means|endymecy 前言 k-meansk-means++以及k-means||算法分析 本文会介绍一般的k-means算法、k-means++算法以及基于k-means++算法的k-means||算法。在spark ml,已经实现了k-means算法以及k-...
  • 基于MapReduce的并行k-means聚类

    千次阅读 2017-06-03 10:52:28
    摘要:在许多应用上,数据聚类...在这篇文章中,我们提出一种基于MapReduce的并行k-means聚类算法,这是一种简单又强大的并行编程技术。实验结果表明所提出的算法可以大规模而且高效地在廉价的硬件上处理大型数据集。
  • k-means聚类算法过程与原理

    万次阅读 2018-08-15 20:05:44
    k-means算法(k-均值聚类算法)是一种基本的已知聚类类别数的划分算法。它是很典型的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。该算法认为簇是由距离靠近的...
  • K-means算法的基本原理

    2020-06-07 19:28:46
    K-means算法是一种典型的基于划分的聚类算法,该算法具有运算速度快,执行过程简单的优点,在很多大数据处理领域得到了广泛的应用。 K-means算法的思想 利用相似性度量方法来衡量数据集中所有数据之间的关系,将关系...
  • K-Means原理分析以及其变种算法

    千次阅读 2017-07-21 11:15:04
    K-Means到elkan K-Means,再到Mini Batch K-Means K-Means是最普通的聚类方法,应用面比较广。 elkan K-MeansK-Mean算法的变种,用于简化计算: elkan K-Means原理: 规律1.对于一个样本点X和两个质心O1和O2...
  • 数据挖掘 K-means聚类实现实例

    千次阅读 2018-10-18 18:05:42
    这学期正好上了数据挖掘这门课,本周的作业是实现 K-means的两个实例,分别是实现对waveform.data文件数据的聚类分析,还有一个就是对图像的 K-means 聚类分割。下面我分别对两个例子进行说明。 首先先来介绍一下...
  • K-means算法的实现原理和分析

    万次阅读 2017-07-08 17:36:21
    K-means算法是最为经典的基于划分的聚类方法,是十大经典数据挖掘算法之一。K-means算法的基本思想是:以空间中k个点为中心进行聚类,对最靠近他们的对象归类。通过迭代的方法,逐次更新各聚类中心的值,直至得到...
  • K-meansK-means++

    2019-08-14 16:10:21
    参考: https://blog.csdn.net/u013129109/article/details/80063111 https://blog.csdn.net/sorawa/article/details/6630729 ...原始k-means算法: 1. K-means算法优点...
  • k-means 优缺点:**  1.算法快速、简单;  2.对大数据集有较高的效率并且是可伸缩性的;  3.时间复杂度近于线性,而且适合挖掘大规模数据集。K-Means聚类算法的时间复杂度是O(n×k×t) ,其中n代表数据集中对象的...
  • 摘要在大数据算法中,聚类算法一般都是作为其他算法分析的基础,对数据进行聚类可以从整体上分析数据的一些特性。聚类有很多的算法,k-means是最简单最实用的一种算法。在这里对k-means算法的原理以及其背后的数学...
  • (精)广东工业大学 2018实时大数据分析——k-means算法实验报告 一、实验内容 给定国际通用UCI数据库中FISHERIRIS数据集,其meas集包含150个样本数据,每个数据含有莺尾属植物的4个属性,即萼片长度、萼片宽度、...
1 2 3 4 5 ... 20
收藏数 7,817
精华内容 3,126
关键字:

k-means处理大数据