k-means pyspark_streaming k-means 和 k-means - CSDN
  • K-means 步骤 关键步骤 聚类个数K的选择 初始聚类中心点的选择 MLlib的K-means实现 参数 Spark_K-Means_PythonK-means步骤 选择K个点作为初始聚类中心 计算其余所有点到聚类中心的距离,并把每个点划分到离它最近的...

    K-means

    优缺点

    优点:容易实现
    缺点:可能收敛到局部最小值,在大规模数据集上收敛较慢
    

    步骤

    1. 选择K个点作为初始聚类中心
    2. 计算其余所有点到聚类中心的距离,并把每个点划分到离它最近的聚类中心所在的聚类中去。计算距离常用欧几里得距离公式,也叫欧氏距离。查看距离的计算方法
    3. 重新计算每个聚类中所有点的平均值,并将其作为新的聚类中心点。
    4. 重复2、3步,直到聚类中心不再发生改变,或者算法达到预定的迭代次数,又或聚类中心的改变小于预先设定的阈值

    使用后处理来提高聚类性能

    局部最小值指结果还可以但并非最好结果,全局最小值是可能的最好结果
    一种用于度量聚类效果的指标是SSE(误差平方和)。SSE值越小表示数据点越接近它们的质心。
    后处理方法:将具有最大SSE值的簇划分成为两个簇;合并最近的质心,或者合并两个使得SSE增幅最小的质心。
    

    二分K-Means算法

    1. 将所有点作为一个簇,然后将该簇一分为二;
    2. 之后选择其中一个簇继续进行划分,选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE的值。
    3. 不断重复SSE的划分过程,直到得到用户指定的簇数目为止。
    

    Spark实现KMeans

    关键步骤

    聚类个数K的选择

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

    初始聚类中心点的选择

    Spark MLlib K-means算法的实现在初始聚类点的选择上,借鉴了K-means||的类K-means++实现。K-means++算法在初始点选择上遵循一个基本原则:初始聚类中心点相互之间的距离应该尽可能的远。基本步骤如下:
    1. 从数据集中随机选择一个点作为第一个初始点
    2. 计算数据集中所有点与最新选择的中心点的距离D(x)
    3. 选择下一个中心点,使得
    

    这里写图片描述

    最大
    4. 重复2、3步,直到K个初始点选择完成
    

    MLlib的K-means实现

    1. 读取训练数据,调用KMeans.train方法对数据集进行聚类训练,方法返回KMeansModel实例
    2. 使用KMeansModel.predict方法对新的数据点进行所属聚类的预测
    3. 均方差(MSE),就是对各个实际存在评分的项,pow(预测评分-实际评分,2)的值进行累加,再除以项数。而均方根差(RMSE)就是MSE开根号。MSE/RMSE值越小说明预测结果越准确

    参数

    参数 含义
    k 所需簇的数量。请注意,可以返回少于k个集群,例如,如果有少于k个不同的集群点
    maxIterations 运行的最大迭代次数。
    initializationMode 通过k-means ||指定随机初始化或初始化。
    initializationSteps 确定k-means ||中的步数算法。
    epsilon 确定我们认为k均值收敛的距离阈值。
    initialModel 用于初始化的可选集群中心集。如果提供此参数,则仅执行一次运行。

    Spark_K-Means_Python

    from __future__ import print_function
    
    from numpy import array
    from math import  sqrt
    
    from pyspark import SparkContext
    
    from pyspark.mllib.clustering import KMeans, KMeansModel
    
    if __name__ == "__main__":
        sc = SparkContext(appName="KmeansExample")
    
        # Load and parse the data
        data = sc.textFile("kmeans_data.txt")
        parsedData = data.map(lambda line:array([float(x) for x in line.split(' ')]))
    
        # Build the Model(cluster the data)
        clusters = KMeans.train(parsedData, 2, maxIterations=10, initializationMode="random")
        print(clusters.clusterCenters)
    
        print(clusters.predict([0.2, 0.2, 0.2]))
    
        # Evaluate clustering by computing Within Set Sum of Squared Errors
        def error(point):
            center = clusters.centers[clusters.predict(point)]
            return sqrt(sum([x**2 for x in (point - center)]))
    
        WSSSE = parsedData.map(lambda point: error(point)).reduce(lambda x, y: x + y)
        print("Within Set Sum of Squared Error = " + str(WSSSE))
    展开全文
  • 对文本进行聚类,文本预处理-->构造特征向量-->聚类,压缩包内含有实验用语料
  • K-means在文本聚类中的尝试 K-means算法是无监督的聚类算法。它的算法思想是:先随机选取K个对象作为初始的聚类中心。然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心。聚类...

    K-means在文本聚类中的尝试

    K-means算法是无监督的聚类算法。它的算法思想是:先随机选取K个对象作为初始的聚类中心。然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。一旦全部对象都被分配了,每个聚类的聚类中心会根据聚类中现有的对象被重新计算。

    K-means算法的关键点在于:

    • 初始k个聚类中心的选择
    • 距离的计算方式

    我想讨论的是:在关键词聚类的任务当中,距离的计算方式的选择,对聚类效果的影响。


    具体任务

    我爬取了司法相关的法律文章,包括:

    • 法律
    • 法律法规
    • 法律解读
    • 行政法规
    • 部门规章
    • 地方政府规章

    首先对于这些文章我使用了LTP进行分词,对每个词计算它的TFIDF值,然后根据TFIDF值大小选取了每篇文章的前10个关键词得到关键词词袋。

    任务的目的是将同一类关键词划分在一起,得到司法文章某一类的共性,从而得到司法文章的全部类别特性。

    我把这个任务视为一个聚类任务。因为虽然我们事先已经对文章有了“预分类”,但是文章的关键词可能是多个类别所共有的,换言之,关键词词袋不同于“预分类”文章,并不具有类别特性,仍需要我们根据关键词的特性将同一类关键词划分在同一簇中。


    关键词向量化

    我对关键词向量化的方式是词向量概率模型,做法是将关键词映射到6维实数向量,6个维度分别对应----法律,法律法规,法律解读,部门规章,行政法规,地方政府规章。对于关键词w(w属于关键词词袋),他的第i维的值xi是它在i维中出现的tfidf值的和,于是w = {x0,x1,x2,x3,x4,x5}

    向量化后的关键词词袋,就可以应用k-means算法进行聚类了,但由于我之前没有NLP的经验,使用k-means算法对关键词聚类的过程中走了弯路。


    欧式距离

    欧式距离是K-means在网上流传性比较广的实现方式,尽管我不知道它是否在学术上流传广泛。

    应用欧式距离进行k-means聚类,问题在于:文本的预处理以及向量化过程导致使用欧式距离难以得到良好效果。
    具体而言,为了得到文章的关键词,不能简单的使用概率模型,不得不使用TF-IDF(逆向文本率)剔除文本共性,得到文章的关键词;但词向量化过程,由于剔除了文本共性,得到的词向量(欧式距离中更好的表述是“词点”),绝大多数都是诸如{1,0,0,0,0,0}只在某一维度上拥有非0值。最终导致,使用欧式距离,绝大多数“词点”集中在{0,0,0,0,0,0}“原点”附近。


    余弦相似度

    因为欧式距离难以实现聚类效果,所以我把目光转向了在其他文章博客中多次提到但没有人拿来实现的余弦相似度K-means。
    为了少走弯路,我查阅了基于余弦距离选取初始簇中心的文本聚类研究论文。
    论文的贡献在于:

    • 1、探索余弦相似度与欧氏距离的关系, 在此基础上给出一种余弦距离, 通过余弦距离的优良性质, 使改进算法思想得以运用到余弦K-means算法中。
    • 2、余弦K-means及其拓展算法的簇内中心点仍是簇内各坐标的和的均值, 与欧氏K-means的簇内中心点的计算方法相同
    • 3、将欧氏距离的距离远即可当初始点的思想迁移应用于余弦K-means算法, 即依次寻找余弦距离相隔最远的K个点。

    在1中,作者证明了余弦相似度、欧氏距离,以及作者提出的余弦距离在函数上的关系,作为作者改进K-means算法的基础。
    在这里插入图片描述
    作者在文章中给出了改进后的算法在公开数据集20newsgroup (20NG) 新闻组数据集上的实验数据
    在这里插入图片描述
    可见改进后的算法效果得到了提升。

    有了上述论文的理论支持,我部分实现了作者的改进Kmeans算法(没有采用余弦距离,采用了余弦相似度,但中心点和初始点选择参考了作者的实现)。同一簇内的向量基本具有相同的方向,我又根据簇内向量在中心向量上的投影的大小,将簇内向量进行重要性排序,最终利用了词向量方向和距离的特性,得到了较好的聚类效果。

    http://xueshu.baidu.com/usercenter/paper/show?paperid=40a3ae181b554a498725b6815daf3e18&site=xueshu_se

    展开全文
  • SparkMLlib实现K-means

    2018-11-15 22:29:15
    SparkMLlib实现K-means 引言 之前写过一篇关于kmeans的博客,里面详细的介绍了关于***K-means***的的详细描述,用python是实现的,并且在最后附带数据,了解更改关于K-means的内容详看...

    SparkMLlib实现K-means

    引言

    之前写过一篇关于kmeans的博客,里面详细的介绍了关于K-means的的详细描述,用python是实现的,并且在最后附带数据,了解更改关于K-means的内容详看K-means

    今天用scala语言中的spark,使用MLlib库来实现

    依赖

    <!--mllib依赖,我用的是scala是2.11, spark是2.2.0-->
    <dependency>
        <groupId>org.apache.spark</groupId>
        <artifactId>spark-mllib_2.10</artifactId>
        <version>1.6.0</version>
    </dependency>
    

    注意

    和python相比,一样是调函数调参,但喂给model的数据类型和python不同,python中的SKLearing库使用的是矩阵或者是DataFrame,在spark里边要求的data是RDD[Vector]类型

    /**
     * Trains a k-means model using specified parameters and the default values for unspecified.
     * 源码中最简单的训练函数要求的是传递三个参数,分别是数据集、族数、迭代次数
     */
    def train(
          data: RDD[Vector],
          k: Int,
          maxIterations: Int): KMeansModel = {
        train(data, k, maxIterations, 1, K_MEANS_PARALLEL)
      }
    

    代码

    import org.apache.spark.{SparkConf, SparkContext}
    import org.apache.spark.mllib.clustering.KMeans
    import org.apache.spark.mllib.linalg
    import org.apache.spark.mllib.linalg.Vectors
    import org.apache.spark.rdd.RDD
    
    
    object Kmeans {
      def main(args: Array[String]): Unit = {
        //模板代码,指定两个线程模拟在hadoop端的分布式
        val conf = new SparkConf().setAppName("Kmeans").setMaster("local[2]")
        val sc = new SparkContext(conf)
    
        //加载数据
        val data = sc.textFile("F:/mllib/kmeans/trainsdata")
        //将数据切分成标志格式,并封装成linalg.Vector类型
        val parsedData: RDD[linalg.Vector] = data.map(s => Vectors.dense(s.split(' ').map(_.toDouble)))
    
        //迭代次数1000次、类簇的个数2个,进行模型训练形成数据模型
        val numClusters = 4
        val numIterations = 1000
          
        //进行训练
        val model = KMeans.train(parsedData, numClusters, numIterations)
    
        //打印数据模型的中心点
        println("四个中心的点:")
        for (point <- model.clusterCenters) {
          println("  " + point.toString)
        }
    
        //使用误差平方之和来评估数据模型,统计聚类错误的样本比例
        val cost = model.computeCost(parsedData)
        println("聚类错误的样本比例 = " + cost)
    
        //对部分点做预测分类
       println("点(-3 -3)所属族:" + model.predict(Vectors.dense("-3 -3".split(' ').map(_.toDouble))))
        println("点(-2 3)所属族:" + model.predict(Vectors.dense("-2 3".split(' ').map(_.toDouble))))
        println("点(3 3)所属族:" + model.predict(Vectors.dense("3 3".split(' ').map(_.toDouble))))
        
        sc.stop()
      }
    }
    

    运行结果

    四个中心的点:
      [-2.4615431500000002,2.78737555]
      [-3.3823704500000007,-2.9473363000000004]
      [2.6265298999999995,3.10868015]
      [2.80293085,-2.7315146]
    聚类错误的样本比例 = 149.95430467642632
    点(-3 -3)所属族:1
    点(-2 3)所属族:0
    点(3 3)所属族:2
    

    在这里插入图片描述

    展开全文
  • * K-Means是最为经典的基于划分的聚类方法,是十大经典数据挖掘算法之一。 * 给定数据样本集Sample和应该划分的类数K,对样本数据Sample进行聚类,最终形成K个聚类。 * 其相似的度量是某条数据与中心点的“距离”...
    /**
      * K-Means是最为经典的基于划分的聚类方法,是十大经典数据挖掘算法之一。
      * 给定数据样本集Sample和应该划分的类数K,对样本数据Sample进行聚类,最终形成K个聚类。
      * 其相似的度量是某条数据与中心点的“距离”。
      * 这里所说的距离是欧式距离,它是一个通常采用的距离定义,它是在m维空间中两个点之间的真实距离。
      * 对于K-Means算法,它的执行过程可分为以下4步:
      * 1)选择K个点作为初始中心
      * 2)将每个点指派到最近的中心形成K个簇(聚类)
      * 3)重新计算每个簇的中心
      * 4)重复2~3步,直至中心不再发生变化。
      *
      * 实现思路如下:
      * 1.设置日志级别
      * 2.设置运行环境
      * 3.加载数据集
      * 4.将数据集聚类,聚成两个类,进行20次迭代计算,形成数据模型
      * 5.在控制台打印数据模型的两个中心点
      * 6.使用误差平方之和来评估数据模型
      * 7.使用模型测试单点数据
      * 8.交叉评估1,只返回结果
      * 9.交叉评估2,返回数据集和结果。
      */
    kmeans_data.txt中的数据:
    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
    
    import org.apache.log4j.{Level, Logger}
    import org.apache.spark.mllib.clustering.KMeans
    import org.apache.spark.mllib.linalg.Vectors
    import org.apache.spark.{SparkConf, SparkContext}
    
    object KmeansDemo {
      def main(args: Array[String]): Unit = {
        //设置日志级别
        Logger.getLogger("org").setLevel(Level.WARN)
        //设置运行环境
        val conf = new SparkConf().setAppName("Kmeans").setMaster("local[2]")
        val sc = new SparkContext(conf)
    
        //加载数据
        val data = sc.textFile("kmeans_data.txt")
        val parseData = data.map(s => Vectors.dense(s.split(" ").map(_.toDouble)))
    
        //将数据集聚类,2个类,20次迭代,形成数据模型
        val numClusters = 2
        val numIterations = 20
        val model = KMeans.train(parseData, numClusters, numIterations)
    
        //数据模型的中心点
        println("Cluster centers:")
        for (c <- model.clusterCenters) {
          println(" " + c.toString)
        }
    
        //使用误差平方之和评估数据模型
        //为此返回K-means代价(点到其最近中心距离的平方之和),根据给定的数据建立模型。
        val cost = model.computeCost(parseData)
        println("Within Set Sum of Squared Errors=" + cost)
    
        //使用模型测试单点数据
        println("Vectros 0.3 0.3 0.3 is belongs to clusters:"
          + model.predict(Vectors.dense(("0.3 0.3 0.3").split(" ").map(_.toDouble))))
        println("Vectros 0.35 0.35 0.35 is belongs to clusters:"
          + model.predict(Vectors.dense(("0.35 0.35 0.35").split(" ").map(_.toDouble))))
        println("Vectros 7 7 7 is belongs to clusters:"
          + model.predict(Vectors.dense(("7 7 7").split(" ").map(_.toDouble))))
    
        //交叉评估1,只返回结果
        val testData=data.map(x=>Vectors.dense(x.split(" ").map(_.toDouble)))
        val result1=model.predict(testData)
        result1.saveAsTextFile("result1")
    
        //交叉评估2,返回数据集和结果
        val result2=data.map{
          line=>
            val lineVector=Vectors.dense(line.split(" ").map(_.toDouble))
            val prediction=model.predict(lineVector)
            line+" "+prediction
        }.saveAsTextFile("result2")
    
        sc.stop()
      }
    }

    运行结果如下:

    展开全文
  • spark平台 mllib K-Means聚类算法 python版本 实现 K-Means 聚类算法可以认为是机器学习比较简单算法,无监督学习。 把自然界的各类人、物属性向量化,来划分k类。 迭代来求k类的中心点。 直接上spark自带...
  • 【[2020.6] 数据挖掘:基于Spark框架的K-Means聚类2】在Iris数据集上借助pyspark实现K-Means聚类Iris(鸢尾花)数据集Iris数据集简介Iris数据集下载和处理基于pypark的K-Means 聚类实验与参数分析Spark组件MLlib[^2]...
  • 实验 Spark ML Bisecting k-means聚类算法使用,实验文档
  • 【数据挖掘:基于Spark框架的K-Means聚类1 [2020.6]】Win10下配置Spark环境+Anaconda安装pyspark,超详细Spark框架介绍Win10下Anaconda安装pyspark如何插入一段漂亮的代码片 Spark框架介绍 Spark框架的介绍离不开...
  • 介绍k-means算法原理比较简单,与上之前提到的C4.5算法不同,C4.5属性分类算法(有监督的),而k-means算法属于聚类算法(无监督的),两者有着本质的区别。 具体的算法描述如下: 1、随机选取 k个聚类质心点 2、...
  • 本文是个人学习笔记,内容主要基于K-means聚类模型KMeans对手写体数据集进行聚类分组。无监督学习(Unsupervised Learning)着重于发现数据本身的分布特点,发现数据的“群落”,寻找“离群”的样本。K-means算法:...
  • MLlib中K-means流程

    2017-02-22 19:24:12
    MLlib的聚类算法有K均值算法,LDA算法,二分K均值算法,高斯混合模型等等。以K均值为例。 MLlib中K-means流程如下: 第一步,选择K个点作为初始聚类中心。 第二步,计算其余所有点到聚类中心的距离,并把每个点...
  • 1 k值的选择 手肘法 手肘法的核心指标是SSE(sum of the squared errors,误差平方和), 其中,Ci是第i个簇,p是Ci中的样本点,mi是Ci的质心(Ci中所有样本的均值),SSE是所有样本的聚类误差,代表了聚类效果的...
  • Spark-K-Means算法

    2016-06-20 23:28:54
    机器学习算法大体分为三类:监督学习(supervised learning)、无监督学习(unsupervised learning)和半监督学习(semi-supervised learning)。...常用的算法有决策树,支持向量机SVM,朴素贝叶斯分类器,K-
  • K均值(K-means)算法 算法介绍: K-means是一个常用的聚类算法来将数据点按预定的簇数进行聚集。K-means算法的基本思想是:以空间中k个点为中心进行聚类,对最靠近他们的对象归类。通过迭代的方法,逐次更新各...
  • Spark实现K-Means算法

    2019-08-06 05:41:50
    K-Means算法是一种基于距离的聚类算法,采用迭代的方法,计算出K个聚类中心,把若干个点聚成K类。 MLlib实现K-Means算法的原理是,运行多个K-Means算法,每个称为run,返回最好的那个聚类的类簇中心。初始的类簇...
  • 来源,官网spark1.6.1版本
  • 一、朴素贝叶斯 1、基本原理 这个算法的名字已经解释了这个算法所做的事情,朴素和贝叶斯。 朴素的意思是说,这个算法将样本中的每个特征都当作独立的,互不关联的个体。 贝叶斯概率相信大家都知道,即是用几个...
  • Spark K-Means

    2019-07-20 02:03:43
    K-MeansK均值) 介绍 K-Means是被应用的最广泛的基于划分的聚类算法,是一种硬聚类算法,属于典型的局域原型的目标函数聚类的代表。算法首先随机选择k个对象,每个对象初始地代表一个簇的平均值或者中心。对于...
  • [Spark_mllib]K-Means

    2017-12-26 09:33:58
    K-means 优缺点 步骤 使用后处理来提高聚类性能 二分K-Means算法 Spark实现KMeans 关键步骤 聚类个数K的选择 初始聚类中心点的选择 MLlib的K-means实现 参数 Spark_K-Means_Python K-means优缺点优点:容易实现 缺点...
1 2 3 4 5 ... 20
收藏数 401
精华内容 160
关键字:

k-means pyspark