大数据算法k-means 论坛_k-means聚类算法数据挖掘 - CSDN
  • K均值算法是基于质心的技术。它以K为输入参数,把n个对象集合分为k个簇,使得簇内的相似度高,簇间的相似度低。 处理流程: 1、为每个聚类确定一个初始聚类中心,这样就有k个初始聚类中心; 2、将样本按照最小...

    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算法k-means++算法以及基于k-means++算法k-means||算法。在spark ml,已经实现了k-means算法以及k-means||算法。 本文首先会介绍这三个算法的原理,然后在了解原理的基础上分析spark中...

    本文转载自:k-means|endymecy

    前言

    k-means、k-means++以及k-means||算法分析

    本文会介绍一般的k-means算法、k-means++算法以及基于k-means++算法的k-means||算法。在spark ml,已经实现了k-means算法以及k-means||算法。
    本文首先会介绍这三个算法的原理,然后在了解原理的基础上分析spark中的实现代码。

    一、k-means算法原理分析

    k-means算法是聚类分析中使用最广泛的算法之一。它把n个对象根据它们的属性分为k个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。

    k-means算法的基本过程如下所示:

    • (1) 任意选择k个初始中心c1,c2,...,ck

    • (2) 计算X中的每个对象与这些中心对象的距离;并根据最小距离重新对相应对象进行划分;

    • (3) 重新计算每个中心对象Ci的值

    这里写图片描述

    • (4) 计算标准测度函数,当满足一定条件,如函数收敛时,则算法终止;如果条件不满足则重复步骤(2),(3)

    1.1 k-means算法的缺点

    k-means算法虽然简单快速,但是存在下面的缺点:

    • 聚类中心的个数K需要事先给定,但在实际中K值的选定是非常困难的,很多时候我们并不知道给定的数据集应该分成多少个类别才最合适。

    • k-means算法需要随机地确定初始聚类中心,不同的初始聚类中心可能导致完全不同的聚类结果。
      第一个缺陷我们很难在k-means算法以及其改进算法中解决,但是我们可以通过k-means++算法来解决第二个缺陷。


    二、k-means++算法原理分析

    k-means++算法选择初始聚类中心的基本原则是:初始的聚类中心之间的相互距离要尽可能的远。它选择初始聚类中心的步骤是:

    • (1) 从输入的数据点集合中随机选择一个点作为第一个聚类中心c1

    • (2) 对于数据集中的每一个点x,计算它与最近聚类中心(指已选择的聚类中心)的距离D(x),并根据概率选择新的聚类中心ci

    • (3) 重复过程(2)直到找到k个聚类中心。

        第(2)步中,依次计算每个数据点与最近的种子点(聚类中心)的距离,依次得到D(1)、D(2)、...、D(n)构成的集合D,其中n表示数据集的大小。在D中,为了避免噪声,不能直接选取值最大的元素,应该选择值较大的元素,然后将其对应的数据点作为种子点。 如何选择值较大的元素呢,下面是spark中实现的思路。

    • 求所有的距离和Sum(D(x))

    • 取一个随机值,用权重的方式来取计算下一个“种子点”。这个算法的实现是,先用Sum(D(x))乘以随机值Random得到值r,然后用currSum += D(x),直到其currSum > r,此时的点就是下一个“种子点”。

        为什么用这样的方式呢?我们换一种比较好理解的方式来说明。把集合D中的每个元素D(x)想象为一根线L(x),线的长度就是元素的值。将这些线依次按照L(1)、L(2)、...、L(n)的顺序连接起来,组成长线LL(1)、L(2)、…、L(n)称为L的子线。 根据概率的相关知识,如果我们在L上随机选择一个点,那么这个点所在的子线很有可能是比较长的子线,而这个子线对应的数据点就可以作为种子点。

    2.1 k-means++算法的缺点

      虽然k-means++算法可以确定地初始化聚类中心,但是从可扩展性来看,它存在一个缺点,那就是它内在的有序性特性:下一个中心点的选择依赖于已经选择的中心点。 针对这种缺陷,k-means||算法提供了解决方法。


    三、k-means||算法原理分析

    k-means||算法是在k-means++算法的基础上做的改进,和k-means++算法不同的是,它采用了一个采样因子l,并且l=A(k),在spark的实现中l=2k,。这个算法首先如k-means++算法一样,随机选择一个初始中心, 然后计算选定初始中心确定之后的初始花费ψ(指与最近中心点的距离)。之后处理log(ψ)次迭代,在每次迭代中,给定当前中心集,通过概率ld2(x,C)/ϕX(C)来 抽样x,将选定的x添加到初始化中心集中,并且更新ϕX(C)。该算法的步骤如下图所示:

    这里写图片描述

      第1步随机初始化一个中心点,第2-6步计算出满足概率条件的多个候选中心点C,候选中心点的个数可能大于k个,所以通过第7-8步来处理。第7步给C中所有点赋予一个权重值wx ,这个权重值表示距离x点最近的点的个数。 第8步使用本地k-means++算法聚类出这些候选点的k个聚类中心。在spark的源码中,迭代次数是人为设定的,默认是5。

      该算法与k-means++算法不同的地方是它每次迭代都会抽样出多个中心点而不是一个中心点,且每次迭代不互相依赖,这样我们可以并行的处理这个迭代过程。由于该过程产生出来的中心点的数量远远小于输入数据点的数量, 所以第8步可以通过本地k-means++算法很快的找出k个初始化中心点。何为本地k-means++算法?就是运行在单个机器节点上的k-means++

      下面我们详细分析上述三个算法的代码实现。


    四、源代码分析

    spark中,org.apache.spark.mllib.clustering.KMeans文件实现了k-means算法以及k-means||算法,org.apache.spark.mllib.clustering.LocalKMeans文件实现了k-means++算法。 在分步骤分析spark中的源码之前我们先来了解KMeans类中参数的含义。

    class KMeans private (
        private var k: Int,//聚类个数
        private var maxIterations: Int,//迭代次数
        private var runs: Int,//运行kmeans算法的次数
        private var initializationMode: String,//初始化模式
        private var initializationSteps: Int,//初始化步数
        private var epsilon: Double,//判断kmeans算法是否收敛的阈值
        private var seed: Long)

      在上面的定义中,k表示聚类的个数,maxIterations表示最大的迭代次数,runs表示运行KMeans算法的次数,在spark 2.0。0开始,该参数已经不起作用了。为了更清楚的理解算法我们可以认为它为1initializationMode表示初始化模式,有两种选择:随机初始化和通过k-means||初始化,默认是通过k-means||初始化initializationSteps表示通过k-means||初始化时的迭代步骤,默认是5,这是spark实现与第三章的算法步骤不一样的地方,这里迭代次数人为指定, 而第三章的算法是根据距离得到的迭代次数,为log(phi)epsilon是判断算法是否已经收敛的阈值。

      下面将分步骤分析k-means算法、k-means||算法的实现过程。

    4.1 处理数据,转换为VectorWithNorm集。

    //求向量的二范式,返回double值
    val norms = data.map(Vectors.norm(_, 2.0))
    norms.persist()
    val zippedData = data.zip(norms).map { case (v, norm) =>
       new VectorWithNorm(v, norm)
    }

    4.2 初始化中心点。

      初始化中心点根据initializationMode的值来判断,如果initializationMode等于KMeans.RANDOM,那么随机初始化k个中心点,否则使用k-means||初始化k个中心点。

    val centers = initialModel match {
          case Some(kMeansCenters) => {
            Array(kMeansCenters.clusterCenters.map(s => new VectorWithNorm(s)))
          }
          case None => {
            if (initializationMode == KMeans.RANDOM) {
              initRandom(data)
            } else {
              initKMeansParallel(data)
            }
          }
        }

    (1)随机初始化中心点。

      随机初始化k个中心点很简单,具体代码如下:

    private def initRandom(data: RDD[VectorWithNorm])
      : Array[Array[VectorWithNorm]] = {
        //采样固定大小为k的子集
        //这里run表示我们运行的KMeans算法的次数,默认为1,以后将停止提供该参数
        val sample = data.takeSample(true, runs * k, new XORShiftRandom(this.seed).nextInt()).toSeq
        //选取k个初始化中心点
        Array.tabulate(runs)(r => sample.slice(r * k, (r + 1) * k).map { v =>
          new VectorWithNorm(Vectors.dense(v.vector.toArray), v.norm)
        }.toArray)
      }

    (2)通过k-means||初始化中心点。

    相比于随机初始化中心点,通过k-means||初始化k个中心点会麻烦很多,它需要依赖第三章的原理来实现。它的实现方法是initKMeansParallel。 下面按照第三章的实现步骤来分析。

    • 第一步,我们要随机初始化第一个中心点。
    //初始化第一个中心点
    val seed = new XORShiftRandom(this.seed).nextInt()
    val sample = data.takeSample(true, runs, seed).toSeq
    val newCenters = Array.tabulate(runs)(r => ArrayBuffer(sample(r).toDense))
    • 第二步,通过已知的中心点,循环迭代求得其它的中心点。
    var step = 0
    while (step < initializationSteps) {
        val bcNewCenters = data.context.broadcast(newCenters)
        val preCosts = costs
        //每个点距离最近中心的代价
        costs = data.zip(preCosts).map { case (point, cost) =>
              Array.tabulate(runs) { r =>
                //pointCost获得与最近中心点的距离
                //并与前一次迭代的距离对比取更小的那个
                math.min(KMeans.pointCost(bcNewCenters.value(r), point), cost(r))
              }
            }.persist(StorageLevel.MEMORY_AND_DISK)
        //所有点的代价和
        val sumCosts = costs.aggregate(new Array[Double](runs))(
              //分区内迭代
              seqOp = (s, v) => {
                // s += v
                var r = 0
                while (r < runs) {
                  s(r) += v(r)
                  r += 1
                }
                s
              },
              //分区间合并
              combOp = (s0, s1) => {
                // s0 += s1
                var r = 0
                while (r < runs) {
                  s0(r) += s1(r)
                  r += 1
                }
                s0
              }
            )
        //选择满足概率条件的点
        val chosen = data.zip(costs).mapPartitionsWithIndex { (index, pointsWithCosts) =>
            val rand = new XORShiftRandom(seed ^ (step << 16) ^ index)
            pointsWithCosts.flatMap { case (p, c) =>
              val rs = (0 until runs).filter { r =>
                //此处设置l=2k
                rand.nextDouble() < 2.0 * c(r) * k / sumCosts(r)
              }
              if (rs.length > 0) Some(p, rs) else None
            }
          }.collect()
          mergeNewCenters()
          chosen.foreach { case (p, rs) =>
            rs.foreach(newCenters(_) += p.toDense)
          }
          step += 1
    }

    在这段代码中,我们并没有选择使用log(pha)的大小作为迭代的次数,而是直接使用了人为确定的initializationSteps,这是与论文中不一致的地方。 在迭代内部我们使用概率公式:

    这里写图片描述

    来计算满足要求的点,其中,l=2k。公式的实现如代码rand.nextDouble() < 2.0 * c(r) * k / sumCosts(r)sumCosts表示所有点距离它所属类别的中心点的欧式距离之和。 上述代码通过aggregate方法并行计算获得该值。

    • 第三步,求最终的k个点。

    通过以上步骤求得的候选中心点的个数可能会多于k个,这样怎么办呢?我们给每个中心点赋一个权重,权重值是数据集中属于该中心点所在类别的数据点的个数。 然后我们使用本地k-means++来得到这k个初始化点。具体的实现代码如下:

    val bcCenters = data.context.broadcast(centers)
        //计算权重值,即各中心点所在类别的个数
        val weightMap = data.flatMap { p =>
          Iterator.tabulate(runs) { r =>
            ((r, KMeans.findClosest(bcCenters.value(r), p)._1), 1.0)
          }
        }.reduceByKey(_ + _).collectAsMap()
        //最终的初始化中心
        val finalCenters = (0 until runs).par.map { r =>
          val myCenters = centers(r).toArray
          val myWeights = (0 until myCenters.length).map(i => weightMap.getOrElse((r, i), 0.0)).toArray
          LocalKMeans.kMeansPlusPlus(r, myCenters, myWeights, k, 30)
        }

    上述代码的关键点时通过本地k-means++算法求最终的初始化点。它是通过LocalKMeans.kMeansPlusPlus来实现的。它使用k-means++来处理。

    // 初始化一个中心点
    centers(0) = pickWeighted(rand, points, weights).toDense
    //
    for (i <- 1 until k) {
          // 根据概率比例选择下一个中心点
          val curCenters = centers.view.take(i)
          //每个点的权重与距离的乘积和
          val sum = points.view.zip(weights).map { case (p, w) =>
            w * KMeans.pointCost(curCenters, p)
          }.sum
          //取随机值
          val r = rand.nextDouble() * sum
          var cumulativeScore = 0.0
          var j = 0
          //寻找概率最大的点
          while (j < points.length && cumulativeScore < r) {
            cumulativeScore += weights(j) * KMeans.pointCost(curCenters, points(j))
            j += 1
          }
          if (j == 0) {
            centers(i) = points(0).toDense
          } else {
            centers(i) = points(j - 1).toDense
          }
    }

    上述代码中,points指的是候选的中心点,weights指这些点相应地权重。寻找概率最大的点的方式就是第二章提到的方式。初始化k个中心点后, 就可以通过一般的k-means流程来求最终的k个中心点了。具体的过程4.3会讲到。

    4.3 确定数据点所属类别

    找到中心点后,我们就需要根据距离确定数据点的聚类,即数据点和哪个中心点最近。具体代码如下:

      // 找到每个聚类中包含的点距离中心点的距离和以及这些点的个数
          val totalContribs = data.mapPartitions { points =>
            val thisActiveCenters = bcActiveCenters.value
            val runs = thisActiveCenters.length
            val k = thisActiveCenters(0).length
            val dims = thisActiveCenters(0)(0).vector.size
    
            val sums = Array.fill(runs, k)(Vectors.zeros(dims))
            val counts = Array.fill(runs, k)(0L)
    
            points.foreach { point =>
              (0 until runs).foreach { i =>
                //找到离给定点最近的中心以及相应的欧几里得距离
                val (bestCenter, cost) = KMeans.findClosest(thisActiveCenters(i), point)
                costAccums(i) += cost
                //距离和
                val sum = sums(i)(bestCenter)
                //y += a * x
                axpy(1.0, point.vector, sum)
                //点数量
                counts(i)(bestCenter) += 1
              }
            }
    
            val contribs = for (i <- 0 until runs; j <- 0 until k) yield {
              ((i, j), (sums(i)(j), counts(i)(j)))
            }
            contribs.iterator
          }.reduceByKey(mergeContribs).collectAsMap()

    4.4 重新确定中心点

    找到类别中包含的数据点以及它们距离中心点的距离,我们可以重新计算中心点。代码如下:

    //更新中心点
    for ((run, i) <- activeRuns.zipWithIndex) {
        var changed = false
        var j = 0
        while (j < k) {
            val (sum, count) = totalContribs((i, j))
            if (count != 0) {
    
                //x = a * x,求平均距离即sum/count
                scal(1.0 / count, sum)
    
                val newCenter = new VectorWithNorm(sum)
                //如果新旧两个中心点的欧式距离大于阈值
                if (KMeans.fastSquaredDistance(newCenter, centers(run)(j)) > epsilon * epsilon) {
                  changed = true
                }
                centers(run)(j) = newCenter
            }
            j += 1
        }
        if (!changed) {
            active(run) = false
            logInfo("Run " + run + " finished in " + (iteration + 1) + " iterations")
        }
        costs(run) = costAccums(i).value
    }

    本文转载自:k-means|endymecy

    展开全文
  • 文章目录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(了解...

    6.5 算法优化

    学习目标

    • 知道k-means算法的优缺点
    • 知道canopy、K-means++、二分K-means、K-medoids的优化原理
    • 了解kernel K-means、ISODATA、Mini-batch K-means的优化原理

    k-means算法小结

    优点:

    ​ 1.原理简单(靠近中心点),实现容易

    ​ 2.聚类效果中上(依赖K的选择)

    ​ 3.空间复杂度o(N),时间复杂度o(I_K_N)

    N为样本点个数,K为中心点个数,I为迭代次数
    

    缺点:

    ​ 1.对离群点,噪声敏感 (中心点易偏移)

    ​ 2.很难发现大小差别很大的簇及进行增量计算

    ​ 3.结果不一定是全局最优,只能保证局部最优(与K的个数及初值选取有关)

    1 Canopy算法配合初始聚类

    1.1 Canopy算法配合初始聚类实现流程

    在这里插入图片描述

    1.2 Canopy算法的优缺点

    优点:

    ​ 1.Kmeans对噪声抗干扰较弱,通过Canopy对比,将较小的NumPoint的Cluster直接去掉有利于抗干扰。

    ​ 2.Canopy选择出来的每个Canopy的centerPoint作为K会更精确。

    ​ 3.只是针对每个Canopy的内做Kmeans聚类,减少相似计算的数量。

    缺点:

    ​ 1.算法中 T1、T2的确定问题 ,依旧可能落入局部最优解

    2 K-means++

    在这里插入图片描述

    其中:

    在这里插入图片描述

    为方便后面表示,把其记为A

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    kmeans++目的,让选择的质心尽可能的分散

    如下图中,如果第一个质心选择在圆心,那么最优可能选择到的下一个点在P(A)这个区域(根据颜色进行划分)

    在这里插入图片描述

    3 二分k-means

    实现流程:

    • 1.所有点作为一个簇

    • 2.将该簇一分为二

    • 3.选择能最大限度降低聚类代价函数(也就是误差平方和)的簇划分为两个簇。

    • 4.以此进行下去,直到簇的数目等于用户给定的数目k为止。

    在这里插入图片描述

    隐含的一个原则

    因为聚类的误差平方和能够衡量聚类性能,该值越小表示数据点越接近于他们的质心,聚类效果就越好。所以需要对误差平方和最大的簇进行再一次划分,因为误差平方和越大,表示该簇聚类效果越不好,越有可能是多个簇被当成了一个簇,所以我们首先需要对这个簇进行划分。

    二分K均值算法可以加速K-means算法的执行速度,因为它的相似度计算少了并且不受初始化问题的影响,因为这里不存在随机点的选取,且每一步都保证了误差最小

    4 k-medoids(k-中心聚类算法)

    K-medoids和K-means是有区别的,不一样的地方在于中心点的选取

    • K-means中,将中心点取为当前cluster中所有数据点的平均值,对异常点很敏感!

    • K-medoids中,将从当前cluster 中选取到其他所有(当前cluster中的)点的距离之和最小的点作为中心点。

    在这里插入图片描述

    算法流程:

    ( 1 )总体n个样本点中任意选取k个点作为medoids

    ( 2 )按照与medoids最近的原则,将剩余的n-k个点分配到当前最佳的medoids代表的类中

    ( 3 )对于第i个类中除对应medoids点外的所有其他点,按顺序计算当其为新的medoids时,代价函数的值,遍历所有可能,选取代价函数最小时对应的点作为新的medoids

    ( 4 )重复2-3的过程,直到所有的medoids点不再发生变化或已达到设定的最大迭代次数

    ( 5 )产出最终确定的k个类

    k-medoids对噪声鲁棒性好。

    例:当一个cluster样本点只有少数几个,如(1,1)(1,2)(2,1)(1000,1000)。其中(1000,1000)是噪声。如果按照k-means质心大致会处在(1,1)(1000,1000)中间,这显然不是我们想要的。这时k-medoids就可以避免这种情况,他会在(1,1)(1,2)(2,1)(1000,1000)中选出一个样本点使cluster的绝对误差最小,计算可知一定会在前三个点中选取。

    k-medoids只能对小样本起作用,样本大,速度就太慢了,当样本多的时候,少数几个噪音对k-means的质心影响也没有想象中的那么重,所以k-means的应用明显比k-medoids多。

    5 Kernel k-means(了解)

    kernel k-means实际上,就是将每个样本进行一个投射到高维空间的处理,然后再将处理后的数据使用普通的k-means算法思想进行聚类。

    在这里插入图片描述

    6 ISODATA(了解)

    类别数目随着聚类过程而变化;

    对类别数会进行合并,分裂,

    “合并”:(当聚类结果某一类中样本数太少,或两个类间的距离太近时)

    “分裂”:(当聚类结果中某一类的类内方差太大,将该类进行分裂)

    7 Mini Batch K-Means(了解)

    适合大数据的聚类算法

    大数据量是什么量级?通常当样本量大于1万做聚类时,就需要考虑选用Mini Batch K-Means算法。

    Mini Batch KMeans使用了Mini Batch(分批处理)的方法对数据点之间的距离进行计算。

    Mini Batch计算过程中不必使用所有的数据样本,而是从不同类别的样本中抽取一部分样本来代表各自类型进行计算。由于计算样本量少,所以会相应的减少运行时间,但另一方面抽样也必然会带来准确度的下降。

    该算法的迭代步骤有两步:

    (1)从数据集中随机抽取一些数据形成小批量,把他们分配给最近的质心

    (2)更新质心

    ​ 与Kmeans相比,数据的更新在每一个小的样本集上。对于每一个小批量,通过计算平均值得到更新质心,并把小批量里的数据分配给该质心,随着迭代次数的增加,这些质心的变化是逐渐减小的,直到质心稳定或者达到指定的迭代次数,停止计算。

    8 小结

    • k-means算法优缺点总结【知道】

      • 优点:
        • ​ 1.原理简单(靠近中心点),实现容易
        • ​ 2.聚类效果中上(依赖K的选择)
        • ​ 3.空间复杂度o(N),时间复杂度o(I_K_N)
      • 缺点:
        • ​ 1.对离群点,噪声敏感 (中心点易偏移)
        • ​ 2.很难发现大小差别很大的簇及进行增量计算
        • ​ 3.结果不一定是全局最优,只能保证局部最优(与K的个数及初值选取有关)
    • 优化方法【知道】

    优化方法

    思路

    Canopy+kmeans

    Canopy粗聚类配合kmeans

    kmeans++

    距离越远越容易成为新的质心

    二分k-means

    拆除SSE最大的簇

    k-medoids

    和kmeans选取中心点的方式不同

    kernel kmeans

    映射到高维空间

    ISODATA

    动态聚类,可以更改K值大小

    Mini-batch K-Means

    大数据集分批聚类

    展开全文
  • K-Means算法是无监督的聚类算法,它实现起来比较简单,聚类效果也不错,因此...包括初始化优化K-Means++, 距离计算优化elkan K-Means算法大数据情况下的优化Mini Batch K-Means算法。 1. K-Means原理初探  K-Me...

     K-Means算法是无监督的聚类算法,它实现起来比较简单,聚类效果也不错,因此应用很广泛。K-Means算法有大量的变体,本文就从最传统的K-Means算法讲起,在其基础上讲述K-Means的优化变体方法。包括初始化优化K-Means++, 距离计算优化elkan K-Means算法和大数据情况下的优化Mini Batch K-Means算法。

    1. K-Means原理初探

        K-Means算法的思想很简单,对于给定的样本集,按照样本之间的距离大小,将样本集划分为K个簇。让簇内的点尽量紧密的连在一起,而让簇间的距离尽量的大。

        如果用数据表达式表示,假设簇划分为(C1,C2,...Ck)(C1,C2,...Ck),则我们的目标是最小化平方误差E:

    E=∑i=1k∑x∈Ci||x−μi||22E=∑i=1k∑x∈Ci||x−μi||22

        其中μiμi是簇CiCi的均值向量,有时也称为质心,表达式为:

    μi=1|Ci|∑x∈Cixμi=1|Ci|∑x∈Cix

        如果我们想直接求上式的最小值并不容易,这是一个NP难的问题,因此只能采用启发式的迭代方法。

        K-Means采用的启发式方式很简单,用下面一组图就可以形象的描述。

      上图a表达了初始的数据集,假设k=2。在图b中,我们随机选择了两个k类所对应的类别质心,即图中的红色质心和蓝色质心,然后分别求样本中所有点到这两个质心的距离,并标记每个样本的类别为和该样本距离最小的质心的类别,如图c所示,经过计算样本和红色质心和蓝色质心的距离,我们得到了所有样本点的第一轮迭代后的类别。此时我们对我们当前标记为红色和蓝色的点分别求其新的质心,如图4所示,新的红色质心和蓝色质心的位置已经发生了变动。图e和图f重复了我们在图c和图d的过程,即将所有点的类别标记为距离最近的质心的类别并求新的质心。最终我们得到的两个类别如图f。

            当然在实际K-Mean算法中,我们一般会多次运行图c和图d,才能达到最终的比较优的类别。

     

    2. 传统K-Means算法流程

    算法步骤:

    1.(随机)选择K个聚类的初始中心;

    2.对任意一个样本点,求其到K个聚类中心的距离,将样本点归类到距离最小的中心的聚类,如此迭代n次;

    3.每次迭代过程中,利用均值等方法更新各个聚类的中心点(质心);

    4.对K个聚类中心,利用2,3步迭代更新后,如果位置点变化很小(可以设置阈值),则认为达到稳定状态,迭代结束,对不同的聚类块和聚类中心可选择不同的颜色标注。

    优点 
    1)原理比较简单,实现也是很容易,收敛速度快。 
    2)聚类效果较优。 
    3)算法的可解释度比较强。 
    4)主要需要调参的参数仅仅是簇数k。

    缺点 
    1)K值的选取不好把握 
    2)对于不是凸的数据集比较难收敛 
    3)如果各隐含类别的数据不平衡,比如各隐含类别的数据量严重失衡,或者各隐含类别的方差不同,则聚类效果不佳。 
    4) 最终结果和初始点的选择有关,容易陷入局部最优。
    5) 对噪音和异常点比较的敏感。

    3. K-Means初始化优化K-Means++

           k个初始化的质心的位置选择对最后的聚类结果和运行时间都有很大的影响,因此需要选择合适的k个质心。如果仅仅是完全随机的选择,有可能导致算法收敛很慢。K-Means++算法就是对K-Means随机初始化质心的方法的优化。

        K-Means++的对于初始化质心的优化策略也很简单,如下:

        a)  从输入的数据点集合中随机选择一个点作为第一个聚类中心μ1
          b) 对于数据集中的每一个点xi,计算它与已选择的聚类中心中最近聚类中心的距离D(xi)=argmin||xi−μr||^2……r=1,2,...kselected

        c) 选择下一个新的数据点作为新的聚类中心,选择的原则是:D(x)较大的点,被选取作为聚类中心的概率较大
        d) 重复b和c直到选择出k个聚类质心
        e) 利用这k个质心来作为初始化质心去运行标准的K-Means算法

    K-Means++对初始聚类中心点的选取做了优化,简要来说就是使初始聚类中心点尽可能的分散开来,这样可以有效的减少迭代次数,加快运算速度。

    4. K-Means距离计算优化elkan K-Means

      在传统的K-Means算法中,我们在每轮迭代时,要计算所有的样本点到所有的质心的距离,这样会比较的耗时。那么,对于距离的计算有没有能够简化的地方呢?elkan K-Means算法就是从这块入手加以改进。它的目标是减少不必要的距离的计算。那么哪些距离不需要计算呢?

      elkan K-Means利用了两边之和大于等于第三边,以及两边之差小于第三边的三角形性质,来减少距离的计算。

      第一种规律是对于一个样本点xx和两个质心μj1,μj2。如果我们预先计算出了这两个质心之间的距离D(j1,j2),则如果计算发现2D(x,j1)≤D(j1,j2),我们立即就可以知道D(x,j1)≤D(x,j2)。此时我们不需要再计算D(x,j2),也就是说省了一步距离计算。

       第二种规律是对于一个样本点x和两个质心μj1,μj2。我们可以得到D(x,j2)≥max{0,D(x,j1)−D(j1,j2)}。这个从三角形的性质也很容易得到。

      利用上边的两个规律,elkan K-Means比起传统的K-Means迭代速度有很大的提高。但是如果我们的样本的特征是稀疏的,有缺失值的话,这个方法就不使用了,此时某些距离无法计算,则不能使用该算法。

          个人理解,第一个规律简单有效,很容易理解,但是第二个规律对简化运算量的意义不是很大。

    5. 大样本优化Mini Batch K-Means

      在统的K-Means算法中,要计算所有的样本点到所有的质心的距离。如果样本量非常大,比如达到10万以上,特征有100以上,此时用传统的K-Means算法非常的耗时,就算加上elkan K-Means优化也依旧。在大数据时代,这样的场景越来越多。此时Mini Batch K-Means应运而生。

      顾名思义,Mini Batch,也就是用样本集中的一部分的样本来做传统的K-Means,这样可以避免样本量太大时的计算难题,算法收敛速度大大加快。当然此时的代价就是我们的聚类的精确度也会有一些降低。一般来说这个降低的幅度在可以接受的范围之内。

      在Mini Batch K-Means中,我们会选择一个合适的批样本大小batch size,我们仅仅用batch size个样本来做K-Means聚类。那么这batch size个样本怎么来的?一般是通过无放回的随机采样得到的。

      为了增加算法的准确性,我们一般会多跑几次Mini Batch K-Means算法,用得到不同的随机采样集来得到聚类簇,选择其中最优的聚类簇。

    该算法的迭代步骤有两步:

    1:从数据集中随机抽取一些数据形成小批量,把他们分配给最近的质心

    2:更新质心

    与K均值算法相比,数据的更新是在每一个小的样本集上。对于每一个小批量,通过计算平均值得到更新质心,并把小批量里的数据分配给该质心,随着迭代次数的增加,这些质心的变化是逐渐减小的,直到质心稳定或者达到指定的迭代次数,停止计算

    Mini Batch K-Means比K-Means有更快的 收敛速度,但同时也降低了聚类的效果,但是在实际项目中却表现得不明显。个人理解,Mini Batch K-Means通过小样本的实验,可以初步预测聚类中心的位置,对n次Mini Batch K-Means的聚类结果取均值作为大样本实验初始聚类中心的位置,也能够减少运算量,加快聚类速度。

    下边给出显示上边这副图的代码,也是对K-Means和Mini Batch K-Means算法的一个比较:

    import time
     
    import numpy as np
    import matplotlib.pyplot as plt
     
    from sklearn.cluster import MiniBatchKMeans, KMeans
    from sklearn.metrics.pairwise import pairwise_distances_argmin
    from sklearn.datasets.samples_generator import make_blobs
     
    ##############################################################################
    # Generate sample data
    np.random.seed(0)
     
    batch_size = 45
    centers = [[1, 1], [-1, -1], [1, -1]] #初始化三个中心
    n_clusters = len(centers)       #聚类的数目为3
    #产生3000组两维的数据,以上边三个点为中心,以(-10,10)为边界,数据集的标准差是0.7
    X, labels_true = make_blobs(n_samples=3000, centers=centers, cluster_std=0.7)
     
    ##############################################################################
    # Compute clustering with Means
     
    k_means = KMeans(init='k-means++', n_clusters=3, n_init=10)
    t0 = time.time() #当前时间
    k_means.fit(X)
    #使用K-Means 对 3000数据集训练算法的时间消耗
    t_batch = time.time() - t0
     
    ##############################################################################
    # Compute clustering with MiniBatchKMeans
     
    mbk = MiniBatchKMeans(init='k-means++', n_clusters=3, batch_size=batch_size,
                          n_init=10, max_no_improvement=10, verbose=0)
    t0 = time.time()
    mbk.fit(X)
    #使用MiniBatchKMeans 对 3000数据集训练算法的时间消耗
    t_mini_batch = time.time() - t0
     
    ##############################################################################
    # Plot result
     
    #创建一个绘图对象, 并设置对象的宽度和高度, 如果不创建直接调用plot, Matplotlib会直接创建一个绘图对象
    '''
    当绘图对象中有多个轴的时候,可以通过工具栏中的Configure Subplots按钮,
    交互式地调节轴之间的间距和轴与边框之间的距离。
    如果希望在程序中调节的话,可以调用subplots_adjust函数,
    它有left, right, bottom, top, wspace, hspace等几个关键字参数,
    这些参数的值都是0到1之间的小数,它们是以绘图区域的宽高为1进行正规化之后的坐标或者长度。
    '''
    fig = plt.figure(figsize=(8, 3))
    fig.subplots_adjust(left=0.02, right=0.98, bottom=0.05, top=0.9)
    colors = ['#4EACC5', '#FF9C34', '#4E9A06']
     
    # We want to have the same colors for the same cluster from the
    # MiniBatchKMeans and the KMeans algorithm. Let's pair the cluster centers per
    # closest one.
    k_means_cluster_centers = np.sort(k_means.cluster_centers_, axis=0)
    mbk_means_cluster_centers = np.sort(mbk.cluster_centers_, axis=0)
    k_means_labels = pairwise_distances_argmin(X, k_means_cluster_centers)
    mbk_means_labels = pairwise_distances_argmin(X, mbk_means_cluster_centers)
    order = pairwise_distances_argmin(k_means_cluster_centers,
                                      mbk_means_cluster_centers)
     
    # KMeans
    ax = fig.add_subplot(1, 3, 1) #add_subplot  图像分给为 一行三列,第一块
    for k, col in zip(range(n_clusters), colors):
        my_members = k_means_labels == k
        cluster_center = k_means_cluster_centers[k]
        ax.plot(X[my_members, 0], X[my_members, 1], 'w',
                markerfacecolor=col, marker='.')
        ax.plot(cluster_center[0], cluster_center[1], 'o', markerfacecolor=col,
                markeredgecolor='k', markersize=6)
    ax.set_title('KMeans')
    ax.set_xticks(())
    ax.set_yticks(())
    plt.text(-3.5, 1.8,  'train time: %.2fs\ninertia: %f' % (
        t_batch, k_means.inertia_))
     
    # MiniBatchKMeans
    ax = fig.add_subplot(1, 3, 2)#add_subplot  图像分给为 一行三列,第二块
    for k, col in zip(range(n_clusters), colors):
        my_members = mbk_means_labels == order[k]
        cluster_center = mbk_means_cluster_centers[order[k]]
        ax.plot(X[my_members, 0], X[my_members, 1], 'w',
                markerfacecolor=col, marker='.')
        ax.plot(cluster_center[0], cluster_center[1], 'o', markerfacecolor=col,
                markeredgecolor='k', markersize=6)
    ax.set_title('MiniBatchKMeans')
    ax.set_xticks(())
    ax.set_yticks(())
    plt.text(-3.5, 1.8, 'train time: %.2fs\ninertia: %f' %
             (t_mini_batch, mbk.inertia_))
     
    # Initialise the different array to all False
    different = (mbk_means_labels == 4)
    ax = fig.add_subplot(1, 3, 3)#add_subplot  图像分给为 一行三列,第三块
     
    for k in range(n_clusters):
        different += ((k_means_labels == k) != (mbk_means_labels == order[k]))
     
    identic = np.logical_not(different)
    ax.plot(X[identic, 0], X[identic, 1], 'w',
            markerfacecolor='#bbbbbb', marker='.')
    ax.plot(X[different, 0], X[different, 1], 'w',
            markerfacecolor='m', marker='.')
    ax.set_title('Difference')
    ax.set_xticks(())
    ax.set_yticks(())
     
    plt.show()

    运行结果如下:

     

    6. K-Means与KNN

        初学者很容易把K-Means和KNN搞混,两者其实差别还是很大的。

        K-Means是无监督学习的聚类算法,没有样本输出;而KNN是监督学习的分类算法,有对应的类别输出。KNN基本不需要训练,对测试集里面的点,只需要找到在训练集中最近的k个点,用这最近的k个点的类别来决定测试点的类别。而K-Means则有明显的训练过程,找到k个类别的最佳质心,从而决定样本的簇类别。

        当然,两者也有一些相似点,两个算法都包含一个过程,即找出和某一个点最近的点。两者都利用了最近邻(nearest neighbors)的思想。

    列个表格对比一下特点:

    KNN

    K-Means

    1.KNN是分类算法 

     

    2.监督学习 

    3.喂给它的数据集是带label的数据,已经是完全正确的数据

    1.K-Means是聚类算法 

     

    2.非监督学习 

    3.喂给它的数据集是无label的数据,是杂乱无章的,经过聚类后才变得有点顺序,先无序,后有序

    没有明显的前期训练过程,属于memory-based learning 有明显的前期训练过程
    K的含义:来了一个样本x,要给它分类,即求出它的y,就从数据集中,在x附近找离它最近的K个数据点,这K个数据点,类别c占的个数最多,就把x的label设为c K的含义:K是人工固定好的数字,假设数据集合可以分为K个簇,由于是依靠人工定好,需要一点先验知识
       
    相似点:都包含这样的过程,给定一个点,在数据集中找离它最近的点。即二者都用到了NN(Nears Neighbor)算法,一般用KD树来实现NN。

     

    7.应用实例

    这是官网的一个例子,详细参见:http://scikit-learn.org/stable/auto_examples/cluster/plot_color_quantization.html#sphx-glr-auto-examples-cluster-plot-color-quantization-py

    执行夏宫(中国)图像的逐像素矢量量化(VQ),将显示图像所需的颜色数量从96,615种独特颜色减少到64,同时保持整体外观质量。

    在该示例中,像素在3D空间中表示,并且K均值用于找到64个颜色簇。在图像处理文献中,从K-means(聚类中心)获得的码本被称为调色板。使用单个字节,可以寻址多达256种颜色,而RGB编码每个像素需要3个字节。例如,GIF文件格式使用这样的调色板。

    为了比较,还示出了使用随机码本(随机拾取的颜色)的量化图像。

     

    print(__doc__)
    import numpy as np
    import matplotlib.pyplot as plt
    from sklearn.cluster import KMeans
    from sklearn.metrics import pairwise_distances_argmin
    from sklearn.datasets import load_sample_image
    from sklearn.utils import shuffle
    from time import time

    n_colors = 64

    # Load the Summer Palace photo
    china = load_sample_image("china.jpg")

    # Convert to floats instead of the default 8 bits integer coding. Dividing by
    # 255 is important so that plt.imshow behaves works well on float data (need to
    # be in the range [0-1])
    china = np.array(china, dtype=np.float64) / 255

    # Load Image and transform to a 2D numpy array.
    w, h, d = original_shape = tuple(china.shape)
    assert d == 3
    image_array = np.reshape(china, (w * h, d))

    print("Fitting model on a small sub-sample of the data")
    t0 = time()
    image_array_sample = shuffle(image_array, random_state=0)[:1000]
    kmeans = KMeans(n_clusters=n_colors, random_state=0).fit(image_array_sample)
    print("done in %0.3fs." % (time() - t0))

    # Get labels for all points
    print("Predicting color indices on the full image (k-means)")
    t0 = time()
    labels = kmeans.predict(image_array)
    print("done in %0.3fs." % (time() - t0))


    codebook_random = shuffle(image_array, random_state=0)[:n_colors + 1]
    print("Predicting color indices on the full image (random)")
    t0 = time()
    labels_random = pairwise_distances_argmin(codebook_random,
                                              image_array,
                                              axis=0)
    print("done in %0.3fs." % (time() - t0))


    def recreate_image(codebook, labels, w, h):
        """Recreate the (compressed) image from the code book & labels"""
        d = codebook.shape[1]
        image = np.zeros((w, h, d))
        label_idx = 0
        for i in range(w):
            for j in range(h):
                image[i][j] = codebook[labels[label_idx]]
                label_idx += 1
        return image

    # Display all results, alongside original image
    plt.figure(1)
    plt.clf()
    ax = plt.axes([0, 0, 1, 1])
    plt.axis('off')
    plt.title('Original image (96,615 colors)')
    plt.imshow(china)

    plt.figure(2)
    plt.clf()
    ax = plt.axes([0, 0, 1, 1])
    plt.axis('off')
    plt.title('Quantized image (64 colors, K-Means)')
    plt.imshow(recreate_image(kmeans.cluster_centers_, labels, w, h))

    plt.figure(3)
    plt.clf()
    ax = plt.axes([0, 0, 1, 1])
    plt.axis('off')
    plt.title('Quantized image (64 colors, Random)')
    plt.imshow(recreate_image(codebook_random, labels_random, w, h))
    plt.show()

    第二个例子:

    实例说明:利用sklearn.datasets.make_blobs产生1500条两维的数据集进行不同情况下的聚类示例,参见网址:https://blog.csdn.net/gamer_gyt/article/details/51244850

    代码如下

    import numpy as np      #科学计算包
    import matplotlib.pyplot as plt      #python画图包
     
    from sklearn.cluster import KMeans       #导入K-means算法包
    from sklearn.datasets import make_blobs
     
    plt.figure(figsize=(12, 12))
     
    """
    make_blobs函数是为聚类产生数据集
    产生一个数据集和相应的标签
    n_samples:表示数据样本点个数,默认值100
    n_features:表示数据的维度,默认值是2
    centers:产生数据的中心点,默认值3
    cluster_std:数据集的标准差,浮点数或者浮点数序列,默认值1.0
    center_box:中心确定之后的数据边界,默认值(-10.0, 10.0)
    shuffle :洗乱,默认值是True
    random_state:官网解释是随机生成器的种子
    更多参数即使请参考:http://scikit-learn.org/dev/modules/generated/sklearn.datasets.make_blobs.html#sklearn.datasets.make_blobs
    """
    n_samples = 1500
    random_state = 170
    X, y = make_blobs(n_samples=n_samples, random_state=random_state)
     
     
    # Incorrect number of clusters
    y_pred = KMeans(n_clusters=2, random_state=random_state).fit_predict(X)
     
    plt.subplot(221)  #在2图里添加子图1
    plt.scatter(X[:, 0], X[:, 1], c=y_pred) #scatter绘制散点
    plt.title("Incorrect Number of Blobs")   #加标题
     
    # Anisotropicly distributed data
    transformation = [[ 0.60834549, -0.63667341], [-0.40887718, 0.85253229]]
    X_aniso = np.dot(X, transformation)    #返回的是乘积的形式
    y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_aniso)
     
    plt.subplot(222)#在2图里添加子图2
    plt.scatter(X_aniso[:, 0], X_aniso[:, 1], c=y_pred)
    plt.title("Anisotropicly Distributed Blobs")
     
    # Different variance
    X_varied, y_varied = make_blobs(n_samples=n_samples,
                                    cluster_std=[1.0, 2.5, 0.5],
                                    random_state=random_state)
    y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_varied)
     
    plt.subplot(223)#在2图里添加子图3
    plt.scatter(X_varied[:, 0], X_varied[:, 1], c=y_pred)
    plt.title("Unequal Variance")
     
    # Unevenly sized blobs
    X_filtered = np.vstack((X[y == 0][:500], X[y == 1][:100], X[y == 2][:10]))
    y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_filtered)
     
    plt.subplot(224)#在2图里添加子图4
    plt.scatter(X_filtered[:, 0], X_filtered[:, 1], c=y_pred)
    plt.title("Unevenly Sized Blobs")
     
    plt.show() #显示图</span>

     

    参考网址:

    https://www.cnblogs.com/pinard/p/6164214.html

    https://blog.csdn.net/sinat_35512245/article/details/55051306

    https://en.wikipedia.org/wiki/K-means_clustering

    http://scikit-learn.org/stable/auto_examples/cluster/plot_color_quantization.html#sphx-glr-auto-examples-cluster-plot-color-quantization-py

     

    展开全文
  • 标准的K-means算法kmeans 算法是实际应用中最为常用的聚类算法.Kmeans 算法的原理简单,实现起来不是很复杂,实际中使用效果也不一般. kmeans 算法的步骤一般如下: 1.随机挑选k个初始聚类中心 2.计算数据集中每...
  • K-Means算法是无监督的聚类算法,它实现起来比较简单,聚类效果也不错,因此...包括初始化优化K-Means++, 距离计算优化elkan K-Means算法大数据情况下的优化Mini Batch K-Means算法。 1. K-Means原理初探  K
  • 摘要在大数据算法中,聚类算法一般都是作为其他算法分析的基础,对数据进行聚类可以从整体上分析数据的一些特性。聚类有很多的算法,k-means是最简单最实用的一种算法。在这里对k-means算法的原理以及其背后的数学...
  • 一、k-means:在大数据的条件下,会耗费大量的时间和内存。 优化k-means的建议: 1、减少聚类的数目K。因为,每个样本都要跟类中心计算距离。 2、减少样本的特征维度。比如说,通过PCA等进行降维。 3、考察其他的...
  • 聚类分析是我们数据挖掘中常用的算法,常常用于没有分类,但又有相关相似性的样本研究当中,包括了K-MeansK-中心点和系统聚类三种算法,各自有各自的特点和适用环境。今天我们大圣众包根据网络资源详细介绍下K-...
  • K-Means算法是常用的聚类算法,但其算法本身存在一定的问题,例如在大数据量下的计算时间过长就是一个重要问题。为此,Mini Batch K-Means,这个基于K-Means的变种聚类算法应运而生。 大数据量是什么量级?通过...
  • K-means算法的基本原理

    2020-06-07 19:28:46
    K-means算法的基本原理 K-means算法的概念 K-means算法是一种典型的基于划分的聚类算法,该算法具有运算速度快,执行过程简单的优点,在很多大数据处理领域得到了广泛的应用。 K-means算法的思想 利用相似性度量方法...
  • K-means算法是很典型的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。该算法认为簇是由距离靠近的对象组成的,因此把得到紧凑且独立的簇作为最终目标。 对于聚类...
  • K-Means聚类算法原理   K-Means算法是无监督的聚类算法,它实现起来比较简单,聚类效果也不错...包括初始化优化K-Means++, 距离计算优化elkan K-Means算法大数据情况下的优化Mini Batch K-Means算法。 1. K-...
  • k-means算法k-均值聚类算法)是一种基本的已知聚类类别数的划分算法。它是很典型的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。该算法认为簇是由距离靠近的...
  • K-Means算法整理

    2019-09-06 22:00:01
    文章目录K-Means算法评价指标算法改进算法优缺点 K-Means算法 K-means是无监督学习算法K-Mean算法步骤: 首先随机选定k个样本点作为初始簇中心; 计算所有样本点到簇中心的距离; 每个样本点选择与它距离最近...
  • K-Means到elkan K-Means,再到Mini Batch K-Means K-Means是最普通的聚类方法,应用面比较广。 elkan K-MeansK-Mean算法的变种,用于简化计算: elkan K-Means原理: 规律1.对于一个样本点X和两个质心O1和O2...
  • K-means算法 (无监督算法,聚类算法) 1-1 基本流程 一、概念: 二、主要特点: 三、算法流程: kmeans作用:去除奇异值 小结: 1-2 算法效果衡量标准 一、K值确定: 二、轮廓系数: 三、Canopy算法配合初始...
  • 一种改进的K-means算法

    2020-07-29 14:20:20
    这是一个基于matlab语言的K-means算法的改进程序,代码完整易懂,里面包含有实际的数据集,能有利于对K-means算法感兴趣的研究学者或者开发人员
  • K-means算法是最为经典的基于划分的聚类方法,是十大经典数据挖掘算法之一。K-means算法的基本思想是:以空间中k个点为中心进行聚类,对最靠近他们的对象归类。通过迭代的方法,逐次更新各聚类中心的值,直至得到...
1 2 3 4 5 ... 20
收藏数 8,031
精华内容 3,212
关键字:

大数据算法k-means 论坛