精华内容
下载资源
问答
  • Kmeans聚类算法应用

    千次阅读 2019-11-06 16:55:17
    文章目录Kmeans聚类算法应用1. Kmeans聚类算法原理1.2 算法图示1.3 算法要点1.3.1 核心思想1.3.2 算法步骤图解1.3.3 算法实现步骤2. Kmeans分类算法Python实战2.1 需求2.2 python代码实现2.2.1 利用numpy手动实现...

    Kmeans聚类算法及应用

    1. Kmeans聚类算法原理

    K-means算法是集简单和经典于一身的基于距离的聚类算法

    采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。

    该算法认为类簇是由距离靠近的对象组成的,因此把得到紧凑且独立的簇作为最终目标。

    1.2 算法图示

    假设我们的n个样本点分布在图中所示的二维空间。

    从数据点的大致形状可以看出它们大致聚为三个cluster,其中两个紧凑一些,剩下那个松散一些,如图所示:

    在这里插入图片描述

    我们的目的是为这些数据分组,以便能区分出属于不同的簇的数据,给它们标上不同的颜色,如图:
    在这里插入图片描述

    1.3 算法要点

    1.3.1 核心思想

    通过迭代寻找k个类簇的一种划分方案,使得用这k个类簇的均值来代表相应各类样本时所得的总体误差最小。

    k个聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。

    k-means算法的基础是*最小误差平方和准则,

    其代价函数是:

    在这里插入图片描述

    ​ 式中,μc(i)表示第i个聚类的均值。

    各类簇内的样本越相似,其与该类均值间的误差平方越小,对所有类所得到的误差平方求和,即可验证分为k类时,各聚类是否是最优的。

    上式的代价函数无法用解析的方法最小化,只能有迭代的方法。

    1.3.2 算法步骤图解

    下图展示了对n个样本点进行K-means聚类的效果,这里k取2。

    在这里插入图片描述

    1.3.3 算法实现步骤

    k-means算法是将样本聚类成 k个簇(cluster),其中k是用户给定的,其求解过程非常直观简单,具体算法描述如下:

    1. 随机选取 k个聚类质心点

    2. 重复下面过程直到收敛 {

    对于每一个样例 i,计算其应该属于的类:

    在这里插入图片描述

    对于每一个类 j,重新计算该类的质心:

    在这里插入图片描述
    }

    2. Kmeans分类算法Python实战

    2.1 需求

    对给定的数据集进行聚类

    本案例采用二维数据集,共80个样本,有4个类。样例如下:

    testSet.txt

    xy
    -3.4536873.424321
    4.838138-1.151539
    -5.379713-3.362104
    0.9725642.924086
    -3.5679191.531611
    0.450614-3.302219
    -3.487105-1.724432
    2.6687591.594842

    2.2 python代码实现

    2.2.1 利用numpy手动实现

    from numpy import *
    import matplotlib.pyplot as plt
    # ##加载数据
    def loadDataSet(fileName):
        dataMat = []
        fr = open(fileName)
        for line in fr.readlines():
            curLine = line.strip().split("\t")
            #坐标点加入到list中
            dataMat.append([float(curLine[0]),float(curLine[1])])
        return dataMat
    # #随机选取k个点
    def randCent(dataSet,k):
        n = shape(dataSet)[1]
        centroids = mat(zeros((k,n)))
        for j in range(n):
            minJ = min(dataSet[:,j])
            maxJ = max(dataSet[:,j])
            rangeJ = float(maxJ-minJ)
            centroids[:,j] = minJ + rangeJ*random.rand(k,1)
        return centroids
    # ##计算欧式距离
    def distEclud(vecA,vecB):
        return sqrt(sum(power(vecA - vecB, 2)))
    
    def KMeans(dataSet,k,distMeans=distEclud,createCent=randCent):
        m = shape(dataMat)[0] ## m = 80个点
        clusterAssment = mat(zeros((m,2))) #存放属于哪一类,和距离质心的距离
        # 获取随机的质心
        centroids = createCent(dataSet,k)
        clusterChanged = True
        count = 0
        while clusterChanged:
            clusterChanged = False
            #循环每一个点
            for i in range(m):
                # 初始化为最大值
                minDist = inf
                minIndex = -1
                for j in range(k):
                    distJl = distMeans(dataSet[i,:],centroids[j,:])
                    if distJl < minDist:
                        minDist = distJl
                        minIndex = j
                if clusterAssment[i,0] != minIndex:
                    clusterChanged = True
                    clusterAssment[i,:] = minIndex,minDist**2
            ## 重新计算质心
            for cent in range(k):
                # #将矩阵转换成数组
                ptsInClust = dataSet[nonzero(clusterAssment[:,0].A == cent)[0]]
                # nonzero返回所有非0元素的坐标,也就是True的坐标
                centroids[cent] = mean(ptsInClust,axis=0)
            count+=1
        print("一共计算了",count,"次")
        return centroids,clusterAssment
    def show(dataSet,clusterAssment,centroids):
        count = 0
        colors = ['r','g','c','b']
        cantCount = 0
        for point in centroids:
            color = colors[cantCount]
            plt.scatter(point[0, 0], point[0, 1],color=color, marker='x', alpha=1)
            cantCount+=1
        for point in dataSet:
            index = clusterAssment[count,0]
            color = colors[int(index)]
            count+=1
            plt.scatter(point[0,0],point[0,1],color=color,marker='o',alpha=0.5)
        plt.show()
    dataMat = mat(loadDataSet("testSet.txt"))
    centroids,clusterAssment = KMeans(dataMat,4,distEclud,randCent)
    show(dataMat,clusterAssment,centroids)
    

    2.2.2 运行结果

    不同的类用不同的颜色来表示,其中的X是对应类的均值质心点。

    在这里插入图片描述

    3、Kmeans算法补充

    3.1 kmeans算法缺点

    k-means算法比较简单,但也有几个比较大的缺点:

    (1)k值的选择是用户指定的,不同的k得到的结果会有挺大的不同,如下图所示,左边是k=3的结果,这个就太稀疏了,蓝色的那个簇其实是可以再划分成两个簇的。而右图是k=5的结果,可以看到红色菱形和蓝色菱形这两个簇应该是可以合并成一个簇的:

    在这里插入图片描述

    (2)对k个初始质心的选择比较敏感,容易陷入局部最小值。例如,我们上面的算法运行的时候,有可能会得到不同的结果,如下面这两种情况。K-means也是收敛了,只是收敛到了局部最小值:

    在这里插入图片描述
    (3)存在局限性,如下面这种非球状的数据分布就搞不定了:

    在这里插入图片描述

    (4)数据集比较大的时候,收敛会比较慢。

    3.2 改良思路

    这些不足也已有了对应方法进行了某种程度上的改良

    问题(1)对k的选择可以先用一些算法分析数据的分布,如重心和密度等,然后选择合适的k

    问题(2),有人提出了另一个成为二分k均值(bisecting k-means)算法,它对初始的k个质心的选择就不太敏感

    from numpy import *
    import matplotlib.pyplot as plt
    # ##加载数据
    def loadDataSet(fileName):
        dataMat = []
        fr = open(fileName)
        for line in fr.readlines():
            curLine = line.strip().split("\t")
            #坐标点加入到list中
            dataMat.append([float(curLine[0]),float(curLine[1])])
        return dataMat
    # #随机选取k个点
    def randCent(dataSet,k):
        n = shape(dataSet)[1]
        centroids = mat(zeros((k,n)))
        for j in range(n):
            minJ = min(dataSet[:,j])
            maxJ = max(dataSet[:,j])
            rangeJ = float(maxJ-minJ)
            centroids[:,j] = minJ + rangeJ*random.rand(k,1)
        return centroids
    # ##计算欧式距离
    def distEclud(vecA,vecB):
        return sqrt(sum(power(vecA - vecB, 2)))
    
    def KMeans(dataSet,k,distMeans=distEclud,createCent=randCent):
        m = shape(dataSet)[0] ## m = 80个点
        clusterAssment = mat(zeros((m,2))) #存放属于哪一类,和距离质心的距离
        # 获取随机的质心
        centroids = createCent(dataSet,k)
        clusterChanged = True
        count = 0
        while clusterChanged:
            print("====================================")
            clusterChanged = False
            #循环每一个点
            for i in range(m):
                # 初始化为最大值
                minDist = inf
                minIndex = -1
                for j in range(k):
                    distJl = distMeans(dataSet[i,:],centroids[j,:])
                    if distJl < minDist:
                        minDist = distJl
                        minIndex = j
                ##如果是第一次是0就不用计算距离,最后剩下的就是0
                if clusterAssment[i,0] != minIndex:
                    clusterChanged = True
                    print(minIndex,minDist**2)
                    clusterAssment[i,:] = minIndex, minDist**2
            ## 重新计算质心
            for cent in range(k):
                # #将矩阵转换成数组
                ptsInClust = dataSet[nonzero(clusterAssment[:,0].A == cent)[0]]
                # nonzero返回所有非0元素的坐标,也就是True的坐标
                centroids[cent] = mean(ptsInClust,axis=0)
            count+=1
        print("一共计算了",count,"次")
        return centroids,clusterAssment
    def show(dataSet,clusterAssment,centroids):
        count = 0
        colors = ['r','g','c','b']
        cantCount = 0
        for point in centroids:
            color = colors[cantCount]
            plt.scatter(point[0, 0], point[0, 1],color=color, marker='x', alpha=1)
            cantCount+=1
        for point in dataSet:
            index = clusterAssment[count,0]
            color = colors[int(index)]
            count+=1
            plt.scatter(point[0,0],point[0,1],color=color,marker='o',alpha=0.5)
        plt.show()
    
    # 二分均值聚类    SSE误差平方和    nonzero判断非0或给定条件,返回两个数组,[0]为True的下标组
    def biKmeans(dataSet, k, distMeas=distEclud):
        m = shape(dataSet)[0]
        clusterAssment = mat(zeros((m, 2)))  # 保存数据点的信息(所属类、误差)
        centroid0 = mean(dataSet, axis=0)  # 根据数据集均值获得第一个簇中心点
        centList = [centroid0]  # 创建一个带有质心的 [列表],因为后面还会添加至k个质心
        for j in range(m):
            # 求得dataSet点与质心点的最小误差平方和
            clusterAssment[j, 1] = distMeas(mat(centroid0), dataSet[j,:]) ** 2
        while (len(centList) < k):
            lowestSSE = inf
            bestCentToSplit = -1
            bestClustAss = None
            bestNewCents = None
            # ##对于每个点切分之后,切分之后,判断最适合切分的哪一个中心点
            for i in range(len(centList)):
                ptsInCurrCluster = dataSet[nonzero(clusterAssment[:, 0].A == i)[0],:]  # 与上面kmeans一样获得属于该质心点的所有样本数据
                # 二分类
                centroidMat, splitClustAss = KMeans(ptsInCurrCluster, 2, distMeas)  # 返回中心点信息、该数据集聚类信息
                sseSplit = sum(splitClustAss[:, 1])  # 这是划分数据的SSE    加上未划分的 作为本次划分的总误差
                sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:, 0].A != i)[0], 1])  # 这是未划分的数据集的SSE
                if (sseSplit + sseNotSplit) < lowestSSE:  # 将划分与未划分的SSE求和与最小SSE相比较 确定是否划分
                    bestCentToSplit = i  # 得出当前最适合做划分的中心点
                    bestNewCents = centroidMat  # 划分后的两个新中心点
                    bestClustAss = splitClustAss.copy()  # 划分点的聚类信息
                    lowestSSE = sseSplit + sseNotSplit
            ## 将最符合切分的点返回到原数组中
            bestClustAss[nonzero(bestClustAss[:, 0].A == 1)[0], 0] = len(centList)  # 由于是二分,所有只有0,1两个簇编号,将属于1的所属信息转为下一个中心点
            bestClustAss[nonzero(bestClustAss[:, 0].A == 0)[0], 0] = bestCentToSplit  # 将属于0的所属信息替换用来聚类的中心点
            centList[bestCentToSplit] = bestNewCents[0, :].tolist()[0]  # 与上面两条替换信息相类似,这里是替换中心点信息,上面是替换数据点所属信息
            centList.append(bestNewCents[1, :].tolist()[0])
            clusterAssment[nonzero(clusterAssment[:, 0].A == bestCentToSplit)[0],:] = bestClustAss  # 替换部分用来聚类的数据的所属中心点与误差平方和 为新的数据
        return mat(centList), clusterAssment
    dataSet = mat(loadDataSet("testSet.txt"))
    centList, clusterAssment = biKmeans(dataSet,4,distEclud)
    # centList, clusterAssment = KMeans(dataSet,4)
    print(clusterAssment)
    # centList, clusterAssment = KMeans(dataSet,4)
    show(dataSet,clusterAssment,centList)
    
    

    在这里插入图片描述

    展开全文
  • 聚类算法是机器学习中的一种无监督学习算法,它在数据科学领域应用场景很广泛,比如基于用户购买行为、兴趣等来构建推荐系统。核心思想可以理解为,在给定的数据集中(数据集中的每个元素有可被观察...

    聚类算法是机器学习中的一种无监督学习算法,它在数据科学领域应用场景很广泛,比如基于用户购买行为、兴趣等来构建推荐系统。

    核心思想可以理解为,在给定的数据集中(数据集中的每个元素有可被观察的n个属性),使用聚类算法将数据集划分为k个子集,并且要求每个子集内部的元素之间的差异度尽可能低,而不同子集元素的差异度尽可能高。简而言之,就是通过聚类算法处理给定的数据集,将具有相同或类似的属性(特征)的数据划分为一组,并且不同组之间的属性相差会比较大。

    K-Means算法是聚类算法中应用比较广泛的一种聚类算法,比较容易理解且易于实现。

    "标准" K-Means算法

    KMeans算法的基本思想是随机给定K个初始簇中心,按照最邻近原则把待分类样本点分到各个簇。然后按平均法重新计算各个簇的质心,从而确定新的簇心。一直迭代,直到簇心的移动距离小于某个给定的值或者满足已定条件。主要分为4个步骤:

    1. 为要聚类的点寻找聚类中心,比如随机选择K个点作为初始聚类中心
    2. 计算每个点到聚类中心的距离,将每个点划分到离该点最近的聚类中去
    3. 计算每个聚类中所有点的坐标平均值,并将这个平均值作为新的聚类中心
    4. 反复执行第2步和第3步,直到聚类中心不再改变或者聚类次数达到设定迭代上限或者达到指定的容错范围

    示例图:

    KMeans算法在做聚类分析的过程中主要有两个难题:初始聚类中心的选择和聚类个数K的选择。

    Spark MLlib对KMeans的实现分析

    Spark MLlib针对"标准"KMeans的问题,在实现自己的KMeans上主要做了如下核心优化:

    1. 选择合适的初始中心点

    Spark MLlib在初始中心点的选择上,有两种算法:

    随机选择:依据给的种子seed,随机选择K个随机中心点
    k-means||:默认的算法

    val RANDOM = "random"
    val K_MEANS_PARALLEL = "k-means||"

    2. 计算样本属于哪一个中心点时对距离计算的优化

    假设中心点是(a1,b1),要计算的点是(a2,b2),那么Spark MLlib采取的计算方法是(记为lowerBoundOfSqDist):

    对比欧几里得距离(记为EuclideanDist):

    可轻易证明lowerBoundOfSqDist小于或等于EuclideanDist,并且计算lowerBoundOfSqDist很方便,只需处理中心点和要计算的点的L2范数。那么在实际处理中就分两种情况:

    • 当lowerBoundOfSqDist大于"最近距离"(之前计算好的,记为bestdistance),那么可以推导欧式距离也大于bestdistance,不需要计算欧式距离,省去了很多计算工作

    • 当lowerBoundOfSqDist小于bestdistance,则会调用fastSquaredDistance进行距离的快速计算

    关于fastSquaredDistance:

    首先计算一个精度:
    val precisionBound1 = 2.0 * EPSILON * sumSquaredNorm / (normDiff * normDiff + EPSILON)
    if (precisionBound1 < precision) {
       // 精度满足squared distance期望的精度
       // val sumSquaredNorm = norm1 * norm1 + norm2 * norm2
       // 2.0 * dot(v1, v2)为2(a1*a2 + b1*b2)可以利用之前计算的L2范数
       sqDist = sumSquaredNorm - 2.0 * dot(v1, v2)
    } else if (v1.isInstanceOf[SparseVector] || v2.isInstanceOf[SparseVector]) {
       val dotValue = dot(v1, v2)
       sqDist = math.max(sumSquaredNorm - 2.0 * dotValue, 0.0)
       val precisionBound2 = EPSILON * (sumSquaredNorm + 2.0 * math.abs(dotValue)) /
         (sqDist + EPSILON)
       if (precisionBound2 > precision) {
          sqDist = Vectors.sqdist(v1, v2)
       }
    } else {
      sqDist = Vectors.sqdist(v1, v2)
    }
    //精度不满足要求时,则进行Vectors.sqdist(v1, v2)的处理,即原始的距离计算

    Spark MLlib中KMeans相关源码分析

    基于mllib包下的KMeans相关源码涉及的类和方法(ml包下与下面略有不同,比如涉及到的fit方法):

    1. KMeans类和伴生对象

    2. train方法:根据设置的KMeans聚类参数,构建KMeans聚类,并执行run方法进行训练

    3. run方法:主要调用runAlgorithm方法进行聚类中心点等的核心计算,返回KMeansModel

    4. initialModel:可以直接设置KMeansModel作为初始化聚类中心选择,也支持随机和k-means || 生成中心点

    5. predict:预测样本属于哪个"类"

    6. computeCost:通过计算数据集中所有的点到最近中心点的平方和来衡量聚类效果。一般同样的迭代次数,cost值越小,说明聚类效果越好。

    注意:该方法在Spark 2.4.X版本已经过时,并且会在Spark 3.0.0被移除,具体取代方法可以查看ClusteringEvaluator

    主要看一下train和runAlgorithm的核心源码:
    def train(
          // 数据样本
          data: RDD[Vector],
          // 聚类数量
          k: Int,
          // 最大迭代次数
          maxIterations: Int,
          // 初始化中心,支持"random"或者"k-means||"
          initializationMode: String,
          // 初始化时的随机种子
          seed: Long): KMeansModel = {
      new KMeans().setK(k)
          .setMaxIterations(maxIterations)
          .setInitializationMode(initializationMode)
          .setSeed(seed)
          .run(data)
    }
    /**
       * Implementation of K-Means algorithm.
       */
      private def runAlgorithm( data: RDD[VectorWithNorm],
          instr: Option[Instrumentation]): KMeansModel = {
    
        val sc = data.sparkContext
    
        val initStartTime = System.nanoTime()
    
        val distanceMeasureInstance = DistanceMeasure.decodeFromString(this.distanceMeasure)
    
        val centers = initialModel match {
          case Some(kMeansCenters) =>
            kMeansCenters.clusterCenters.map(new VectorWithNorm(_))
          case None =>
            if (initializationMode == KMeans.RANDOM) {
              // random
              initRandom(data)
            } else {
              // k-means||
              initKMeansParallel(data, distanceMeasureInstance)
            }
        }
        val initTimeInSeconds = (System.nanoTime() - initStartTime) / 1e9
        logInfo(f"Initialization with $initializationMode took $initTimeInSeconds%.3f seconds.")
    
        var converged = false
        var cost = 0.0
        var iteration = 0
    
        val iterationStartTime = System.nanoTime()
    
        instr.foreach(_.logNumFeatures(centers.head.vector.size))
    
        // Execute iterations of Lloyd's algorithm until converged
        // Kmeans迭代执行,计算每个样本属于哪个中心点,中心点累加的样本值以及计数。然后根据中心点的所有样本数据进行中心点的更新,并且比较更新前的数值,根据两者距离判断是否完成
        //迭代次数小于最大迭代次数,并行计算的中心点还没有收敛
        while (iteration < maxIterations && !converged) {
          // 损失值累加器
          val costAccum = sc.doubleAccumulator
          // 广播中心点
          val bcCenters = sc.broadcast(centers)
    
          // Find the new centers
          val collected = data.mapPartitions { points =>
            // 当前聚类中心
            val thisCenters = bcCenters.value
            // 中心点的维度
            val dims = thisCenters.head.vector.size
    
            val sums = Array.fill(thisCenters.length)(Vectors.zeros(dims))
            val counts = Array.fill(thisCenters.length)(0L)
    
            points.foreach { point =>
              // 通过当前的聚类中心点,找出最近的聚类中心点
              // findClosest是为了计算bestDistance,参考上述Spark对距离计算的优化
              val (bestCenter, cost) = distanceMeasureInstance.findClosest(thisCenters, point)
              costAccum.add(cost)
              distanceMeasureInstance.updateClusterSum(point, sums(bestCenter))
              counts(bestCenter) += 1
            }
    
            counts.indices.filter(counts(_) > 0).map(j => (j, (sums(j), counts(j)))).iterator
          }.reduceByKey { case ((sum1, count1), (sum2, count2)) =>
            axpy(1.0, sum2, sum1)
            (sum1, count1 + count2)
          }.collectAsMap()
    
          if (iteration == 0) {
            instr.foreach(_.logNumExamples(collected.values.map(_._2).sum))
          }
    
          val newCenters = collected.mapValues { case (sum, count) =>
            distanceMeasureInstance.centroid(sum, count)
          }
    
          bcCenters.destroy(blocking = false)
    
          // Update the cluster centers and costs
          converged = true
          newCenters.foreach { case (j, newCenter) =>
            if (converged &&
              !distanceMeasureInstance.isCenterConverged(centers(j), newCenter, epsilon)) {
              // 距离大于,则说明中心点位置改变
              converged = false
            }
            // 更新中心点
            centers(j) = newCenter
          }
    
          cost = costAccum.value
          iteration += 1
        }
    
        val iterationTimeInSeconds = (System.nanoTime() - iterationStartTime) / 1e9
        logInfo(f"Iterations took $iterationTimeInSeconds%.3f seconds.")
    
        if (iteration == maxIterations) {
          logInfo(s"KMeans reached the max number of iterations: $maxIterations.")
        } else {
          logInfo(s"KMeans converged in $iteration iterations.")
        }
    
        logInfo(s"The cost is $cost.")
    
        new KMeansModel(centers.map(_.vector), distanceMeasure, cost, iteration)
      }

    Spark MLlib的KMeans应用示例

    1.准备数据

    诺丹姆吉本斯主教中学(Notre Dame-Bishop Gibbons School)      71     0       0    283047.0        13289.0
    海景基督高中(Ocean View Christian Academy)      45     0     0       276403.0       13289.0 
    卡弗里学院(Calvary Baptist Academy)        58       0       0       227567.0       13289.0
    ...

    2.示例代码

    //将加载的rdd数据,每一条变成一个向量,整个数据集变成矩阵
    val parsedata = rdd.map { case Row(schoolid, schoolname, locationid, school_type, zs, fee, byj) =>
       //"特征因子":学校位置id,学校类型,住宿方式,学费,备用金
       val features = Array[Double](locationid.toString.toDouble, school_type.toString.toDouble, zs.toString.toDouble, fee.toString.toDouble, byj.toString.toDouble)
        //将数组变成机器学习中的向量
        Vectors.dense(features)
      }.cache() //默认缓存到内存中,可以调用persist()指定缓存到哪
    
      //用kmeans对样本向量进行训练得到模型
      //聚类中心
      val numclusters = List(3, 6, 9)
      //指定最大迭代次数
      val numIters = List(10, 15, 20)
      var bestModel: Option[KMeansModel] = None
      var bestCluster = 0
      var bestIter = 0
      val bestRmse = Double.MaxValue
      for (c <- numclusters; i <- numIters) {
        val model = KMeans.train(parsedata, c, i)
        //集内均方差总和(WSSSE),一般可以通过增加类簇的个数 k 来减小误差,一般越小越好(有可能出现过拟合)
        val d = model.computeCost(parsedata)
        println("选择K:" + (c, i, d))
        if (d < bestRmse) {
          bestModel = Some(model)
          bestCluster = c
          bestIter = i
        }
      }
      println("best:" + (bestCluster, bestIter, bestModel.get.computeCost(parsedata)))
      //用模型对我们的数据进行预测
      val resrdd = df.map { case Row(schoolid, schoolname, locationid, school_type, zs, fee, byj) =>
      //提取到每一行的特征值
      val features = Array[Double](locationid.toString.toDouble, school_type.toString.toDouble, zs.toString.toDouble, fee.toString.toDouble, byj.toString.toDouble)
       //将特征值转换成特征向量
       val linevector = Vectors.dense(features)
       //将向量输入model中进行预测,得到预测值
       val prediction = bestModel.get.predict(linevector)
    
       //返回每一行结果((sid,sname),所属类别)
       ((schoolid.toString, schoolname.toString), prediction)
     }
    
     //中心点
     /*val centers: Array[linalg.Vector] = model.clusterCenters
     centers.foreach(println)*/
    
     //按照所属"类别"分组,并根据"类别"排序,然后保存到数据库
     // saveData2Mysql是封装好的保存数据到mysql的方法
     resrdd.groupBy(_._2).sortBy(_._1).foreachPartition(saveData2Mysql(_))

    上述示例只是一个简单的demo,实际应用中会更复杂,牵涉到数据的预处理,比如对数据进行量化、归一化,以及如何调参以获取最优训练模型。


    阿里巴巴开源大数据技术团队成立Apache Spark中国技术社区,定期推送精彩案例,技术专家直播,问答区近万人Spark技术同学在线提问答疑,只为营造纯粹的Spark氛围,欢迎钉钉扫码加入!

    对开源大数据和感兴趣的同学可以加小编微信(下图二维码,备注“进群”)进入技术交流微信群。
    Apache Spark技术交流社区公众号,微信扫一扫关注

    展开全文
  • 1. 写在前面如果想从事数据挖掘或者机器学习的工作,掌握常用的机器学习算法是非常有必要的,常见的机器学习算法:监督学习算法:逻辑回归,线性回归,决策树,朴素贝叶斯,K近邻,支持向量机,集成算法Adaboost等无...

    1. 写在前面

    如果想从事数据挖掘或者机器学习的工作,掌握常用的机器学习算法是非常有必要的,常见的机器学习算法:

    • 监督学习算法:逻辑回归,线性回归,决策树,朴素贝叶斯,K近邻,支持向量机,集成算法Adaboost等
    • 无监督算法:聚类,降维,关联规则, PageRank等

    为了详细的理解这些原理,曾经看过西瓜书,统计学习方法,机器学习实战等书,也听过一些机器学习的课程,但总感觉话语里比较深奥,读起来没有耐心,并且理论到处有,而实战最重要, 所以在这里想用最浅显易懂的语言写一个白话机器学习算法理论+实战系列

    个人认为,理解算法背后的idea和使用,要比看懂它的数学推导更加重要。idea会让你有一个直观的感受,从而明白算法的合理性,数学推导只是将这种合理性用更加严谨的语言表达出来而已,打个比方,一个梨很甜,用数学的语言可以表述为糖分含量90%,但只有亲自咬一口,你才能真正感觉到这个梨有多甜,也才能真正理解数学上的90%的糖分究竟是怎么样的。如果算法是个梨,本文的首要目的就是先带领大家咬一口。另外还有下面几个目的:

    • 检验自己对算法的理解程度,对算法理论做一个小总结
    • 能开心的学习这些算法的核心思想, 找到学习这些算法的兴趣,为深入的学习这些算法打一个基础。
    • 每一节课的理论都会放一个实战案例,能够真正的做到学以致用,既可以锻炼编程能力,又可以加深算法理论的把握程度。
    • 也想把之前所有的笔记和参考放在一块,方便以后查看时的方便。

    学习算法的过程,获得的不应该只有算法理论,还应该有乐趣和解决实际问题的能力!

    今天是白话机器学习算法理论+实战的第八篇 之KMeans聚类算法, 听到这个名字,你可别和第七篇K近邻算法搞混了,K-Means 是一种非监督学习,解决的是聚类问题,这里的K表示的是聚成K类。而之前的K近邻算法是监督学习算法,解决的是分类问题,这里的K表示的是K个邻居。相差十万八千里吧, 一条取经路呢。一定要区分开。这个算法也不是很难,前面说道,K近邻算法的原理可以用八个大字叫做“近朱者赤,近墨者黑”来总结,这里我依然放出八个大字:“人以类聚,物以群分”,形容KMeans最好不过了。

    通过今天的学习,掌握KMeans算法的工作原理,然后会使用sklearn实现KMeans聚类,最后我们来做一个实战项目:如何使用KMeans对图像进行分割? 下面我们开始吧。

    大纲如下:

    • KMeans聚类的工作原理(结合足球队等级划分谈一谈)
    • 20支亚洲足球队,你能划分出等级吗?(KMeans聚类应用)
    • KMeans聚类的实战:图像分割

    OK, let's go!

    2. K-Means的工作原理

    上面我们说过,K-Means 是一种非监督学习,解决的是聚类问题。K 代表的是 K 类,Means 代表的是中心,你可以理解这个算法的本质是确定 K 类的中心点,当你找到了这些中心点,也就完成了聚类。

    那么这里有两个问题:如何确定K类的中心点?如何把其他类划分到K个类中去?

    先别慌, 先和我考虑一个场景,假设我有 20 支亚洲足球队,想要将它们按照成绩划分成 3 个等级,可以怎样划分?

    元芳, 你怎么看?

    对亚洲足球队的水平,你可能也有自己的判断。比如一流的亚洲球队有谁?你可能会说伊朗或韩国。二流的亚洲球队呢?你可能说是中国。三流的亚洲球队呢?你可能会说越南。

    其实这些都是靠我们的经验来划分的,那么伊朗、中国、越南可以说是三个等级的典型代表,也就是我们每个类的中心点。

    所以回过头来,如何确定 K 类的中心点?一开始我们是可以随机指派的,当你确认了中心点后,就可以按照距离将其他足球队划分到不同的类别中。

    这也就是 K-Means 的中心思想,就是这么简单直接。

    你可能会问:如果一开始,选择一流球队是中国,二流球队是伊朗,三流球队是韩国,中心点选择错了怎么办?其实不用担心,K-Means 有自我纠正机制,在不断的迭代过程中,会纠正中心点。中心点在整个迭代过程中,并不是唯一的,只是你需要一个初始值,一般算法会随机设置初始的中心点。

    那下面就给出K-Means的工作原理,两步就搞定,就是那两个问题的解决:

    1. 选取 K 个点作为初始的类中心点,这些点一般都是从数据集中随机抽取的;
    2. 将每个点分配到最近的类中心点,这样就形成了 K 个类,然后重新计算每个类的中心点;(这个怎么算最近,一般是欧几里得距离公式, 那么怎么重新计算每个类的中心点, 每个维度的平均值就可以的)
    3. 重复第二步,直到类不发生变化,或者你也可以设置最大迭代次数,这样即使类中心点发生变化,但是只要达到最大迭代次数就会结束。

    什么?还不明白? 好吧,那直接看看亚洲球队聚类的例子吧

    3. 如何给亚洲球队做聚类

    对于机器来说需要数据才能判断类中心点,所以下面整理了 2015-2019 年亚洲球队的排名,如下表所示。

    我来说明一下数据概况。

    其中 2019 年国际足联的世界排名,2015 年亚洲杯排名均为实际排名。2018 年世界杯中,很多球队没有进入到决赛圈,所以只有进入到决赛圈的球队才有实际的排名。如果是亚洲区预选赛 12 强的球队,排名会设置为 40。如果没有进入亚洲区预选赛 12 强,球队排名会设置为 50。d467e4ae1f10104b893ec267311ede7a.png我们怎么做聚类呢?可以跟着我的思路走了:

    • 首先,针对上面的排名,我们需要做的就是数据规范化,你可以把这些值划分到[0,1]或者按照均值为 0,方差为 1 的正态分布进行规范化。我先把数值规范化到了[0,1]空间中,得到了下面的数值表:bbef88065ca22862cbec1bbad6782f5a.png如果我们随机选取中国、日本、韩国为三个类的中心点,我们就需要看下这些球队到中心点的距离。

    • 下面就是把其其他样本根据距离中心点的远近划分到这三个类中去,有关距离可以参考KNN那一篇博客。 常用的有欧氏距离,曼哈顿距离等。这里采用欧式距离。

    欧氏距离是最常用的距离计算方式,这里选择欧氏距离作为距离的标准,计算每个队伍分别到中国、日本、韩国的距离,然后根据距离远近来划分。我们看到大部分的队,会和中国队聚类到一起。这里我整理了距离的计算过程,比如中国和中国的欧氏距离为 0,中国和日本的欧式距离为 0.732003。如果按照中国、日本、韩国为 3 个分类的中心点,欧氏距离的计算结果如下表所示:94dda8c29d435432e74d30d7f5323319.png然后我们再重新计算这三个类的中心点,如何计算呢?最简单的方式就是取平均值,然后根据新的中心点按照距离远近重新分配球队的分类,再根据球队的分类更新中心点的位置。计算过程这里不展开,最后一直迭代(重复上述的计算过程:计算中心点和划分分类)到分类不再发生变化,可以得到以下的分类结果:5e4d683cc62eece24e292f838bd20179.png所以我们能看出来第一梯队有日本、韩国、伊朗、沙特、澳洲;第二梯队有中国、伊拉克、阿联酋、乌兹别克斯坦;第三梯队有卡塔尔、泰国、越南、阿曼、巴林、朝鲜、印尼、叙利亚、约旦、科威特和巴勒斯坦。

    这个就是KMeans进行聚类的过程了。简单点,就是反复两个过程:

    • 确定中心点
    • 把其他的点按照距中心点的远近归到相应的中心点

    上面这个也可以使用sklearn中的K-Means进行实战一下子,作为图像分割图像的准备期。

    4. KMeans聚类实战:如何使用KMeans对图像进行分割?

    还是老规矩,我们在实战之前,先看一下如何调用sklearn实现KMeans。

    4.1 如何使用sklearn中的KMeans算法

    sklearn 是 Python 的机器学习工具库,如果从功能上来划分,sklearn 可以实现分类、聚类、回归、降维、模型选择和预处理等功能。这里我们使用的是 sklearn 的聚类函数库,因此需要引用工具包,具体代码如下:

    from sklearn.cluster import KMeans

    当然 K-Means 只是 sklearn.cluster 中的一个聚类库,实际上包括 K-Means 在内,sklearn.cluster 一共提供了 9 种聚类方法,比如 Mean-shift,DBSCAN,Spectral clustering(谱聚类)等。这些聚类方法的原理和 K-Means 不同,这里不做介绍。

    我们看下 K-Means 如何创建:

    KMeans(n_clusters=8, init='k-means++', n_init=10, max_iter=300, tol=0.0001, precompute_distances='auto', verbose=0, random_state=None, copy_x=True, n_jobs=1, algorithm='auto')

    这些参数解释一下:

    • n_clusters: 即 K 值,一般需要多试一些 K 值来保证更好的聚类效果。你可以随机设置一些 K 值,然后选择聚类效果最好的作为最终的 K 值;max_iter:最大迭代次数,如果聚类很难收敛的话,设置最大迭代次数可以让我们及时得到反馈结果,否则程序运行时间会非常长;
    • n_init:初始化中心点的运算次数,默认是 10。程序是否能快速收敛和中心点的选择关系非常大,所以在中心点选择上多花一些时间,来争取整体时间上的快速收敛还是非常值得的。由于每一次中心点都是随机生成的,这样得到的结果就有好有坏,非常不确定,所以要运行 n_init 次, 取其中最好的作为初始的中心点。如果 K 值比较大的时候,你可以适当增大 n_init 这个值;
    • init:即初始值选择的方式,默认是采用优化过的 k-means++ 方式,你也可以自己指定中心点,或者采用 random 完全随机的方式。自己设置中心点一般是对于个性化的数据进行设置,很少采用。random 的方式则是完全随机的方式,一般推荐采用优化过的 k-means++ 方式;
    • algorithm:k-means 的实现算法,有“auto” “full”“elkan”三种。一般来说建议直接用默认的"auto"。简单说下这三个取值的区别,如果你选择"full"采用的是传统的 K-Means 算法,“auto”会根据数据的特点自动选择是选择“full”还是“elkan”。我们一般选择默认的取值,即“auto” 。

    在创建好 K-Means 类之后,就可以使用它的方法,最常用的是 fit 和 predict 这个两个函数。你可以单独使用 fit 函数和 predict 函数,也可以合并使用 fit_predict 函数。其中 fit(data) 可以对 data 数据进行 k-Means 聚类。predict(data) 可以针对 data 中的每个样本,计算最近的类。

    下面我们先跑一遍20支亚洲球队的聚类问题:数据集在这下载


    # coding: utf-8
    from sklearn.cluster import KMeans
    from sklearn import preprocessing
    import pandas as pd
    import numpy as np
    # 输入数据
    data = pd.read_csv('data.csv', encoding='gbk')
    train_x = data[["2019年国际排名","2018世界杯","2015亚洲杯"]]
    df = pd.DataFrame(train_x)
    kmeans = KMeans(n_clusters=3)
    # 规范化到[0,1]空间
    min_max_scaler=preprocessing.MinMaxScaler()
    train_x=min_max_scaler.fit_transform(train_x)
    # kmeans算法
    kmeans.fit(train_x)
    predict_y = kmeans.predict(train_x)
    # 合并聚类结果,插入到原数据中
    result = pd.concat((data,pd.DataFrame(predict_y)),axis=1)
    result.rename({0:u'聚类'},axis=1,inplace=True)
    print(result)

    运行结果如下:


    国家 2019年国际排名 2018世界杯 2015亚洲杯 聚类
    0 中国 73 40 7 2
    1 日本 60 15 5 0
    2 韩国 61 19 2 0
    3 伊朗 34 18 6 0
    4 沙特 67 26 10 0
    5 伊拉克 91 40 4 2
    6 卡塔尔 101 40 13 1
    7 阿联酋 81 40 6 2
    8 乌兹别克斯坦 88 40 8 2
    9 泰国 122 40 17 1
    10 越南 102 50 17 1
    11 阿曼 87 50 12 1
    12 巴林 116 50 11 1
    13 朝鲜 110 50 14 1
    14 印尼 164 50 17 1
    15 澳洲 40 30 1 0
    16 叙利亚 76 40 17 1
    17 约旦 118 50 9 1
    18 科威特 160 50 15 1
    19 巴勒斯坦 96 50 16 1

    4.2 如何用KMeans对图像进行分割?

    图像分割就是利用图像自身的信息,比如颜色、纹理、形状等特征进行划分,将图像分割成不同的区域,划分出来的每个区域就相当于是对图像中的像素进行了聚类。单个区域内的像素之间的相似度大,不同区域间的像素差异性大。这个特性正好符合聚类的特性,所以你可以把图像分割看成是将图像中的信息进行聚类。当然聚类只是分割图像的一种方式,除了聚类,我们还可以基于图像颜色的阈值进行分割,或者基于图像边缘的信息进行分割等。

    将微信开屏封面进行分割。

    我们现在用 K-Means 算法对微信页面进行分割。微信开屏图如下所示:b6c780b7fc59a7262ba6720215ad7827.png我们先设定下聚类的流程,聚类的流程和分类差不多,如图所示:17c74c71f7d143ab713f37631bc1f414.png在准备阶段里,我们需要对数据进行加载。因为处理的是图像信息,我们除了要获取图像数据以外,还需要获取图像的尺寸和通道数,然后基于图像中每个通道的数值进行数据规范化。这里我们需要定义个函数 load_data,来帮我们进行图像加载和数据规范化。代码如下:

    # 加载图像,并对数据进行规范化
    def load_data(filePath):
    # 读文件
    f = open(filePath,'rb')
    data = []
    # 得到图像的像素值
    img = image.open(f)
    # 得到图像尺寸
    width, height = img.size
    for x in range(width):
    for y in range(height):
    # 得到点(x,y)的三个通道值
    c1, c2, c3 = img.getpixel((x, y))
    data.append([c1, c2, c3])
    f.close()
    # 采用Min-Max规范化
    mm = preprocessing.MinMaxScaler()
    data = mm.fit_transform(data)
    return np.mat(data), width, height

    因为 jpg 格式的图像是三个通道 (R,G,B),也就是一个像素点具有 3 个特征值。这里我们用 c1、c2、c3 来获取平面坐标点 (x,y) 的三个特征值,特征值是在 0-255 之间。

    为了加快聚类的收敛,我们需要采用 Min-Max 规范化对数据进行规范化。我们定义的 load_data 函数返回的结果包括了针对 (R,G,B) 三个通道规范化的数据,以及图像的尺寸信息。在定义好 load_data 函数后,我们直接调用就可以得到相关信息,代码如下:

    # 加载图像,得到规范化的结果img,以及图像尺寸
    img, width, height = load_data('./weixin.jpg')

    假设我们想要对图像分割成 2 部分,在聚类阶段,我们可以将聚类数设置为 2,这样图像就自动聚成 2 类。代码如下:

    # 用K-Means对图像进行2聚类
    kmeans =KMeans(n_clusters=2)
    kmeans.fit(img)
    label = kmeans.predict(img)
    # 将图像聚类结果,转化成图像尺寸的矩阵
    label = label.reshape([width, height])
    # 创建个新图像pic_mark,用来保存图像聚类的结果,并设置不同的灰度值
    pic_mark = image.new("L", (width, height))
    for x in range(width):
    for y in range(height):
    # 根据类别设置图像灰度, 类别0 灰度值为255, 类别1 灰度值为127
    pic_mark.putpixel((x, y), int(256/(label[x][y]+1))-1)
    pic_mark.save("weixin_mark.jpg", "JPEG")

    代码中有一些参数,下面说一下这些参数的作用和设置方法:

    我们使用了 fit 和 predict 这两个函数来做数据的训练拟合和预测,因为传入的参数是一样的,我们可以同时进行 fit 和 predict 操作,这样我们可以直接使用 fit_predict(data) 得到聚类的结果。得到聚类的结果 label 后,实际上是一个一维的向量,我们需要把它转化成图像尺寸的矩阵。label 的聚类结果是从 0 开始统计的,当聚类数为 2 的时候,聚类的标识 label=0 或者 1。
    如果你想对图像聚类的结果进行可视化,直接看 0 和 1 是看不出来的,还需要将 0 和 1 转化为灰度值。灰度值一般是在 0-255 的范围内,我们可以将 label=0 设定为灰度值 255,label=1 设定为灰度值 127。具体方法是用 int(256/(label[x][y]+1))-1。可视化的时候,主要是通过设置图像的灰度值进行显示。所以我们把聚类 label=0 的像素点都统一设置灰度值为 255,把聚类 label=1 的像素点都统一设置灰度值为 127。原来图像的灰度值是在 0-255 之间,现在就只有 2 种颜色(也就是灰度为 255,和灰度 127)。

    有了这些灰度信息,我们就可以用 image.new 创建一个新的图像,用 putpixel 函数对新图像的点进行灰度值的设置,最后用 save 函数保存聚类的灰度图像。这样你就可以看到聚类的可视化结果了,如下图所示:47590d7f2b7fb02b67d8c3d5a8b750fe.png如果我们想要分割成 16 个部分,该如何对不同分类设置不同的颜色值呢?这里需要用到 skimage 工具包,它是图像处理工具包。你需要使用 pip install scikit-image 来进行安装。这段代码可以将聚类标识矩阵转化为不同颜色的矩阵:

    from skimage import color
    # 将聚类标识矩阵转化为不同颜色的矩阵
    label_color = (color.label2rgb(label)*255).astype(np.uint8)
    label_color = label_color.transpose(1,0,2)
    images = image.fromarray(label_color)
    images.save('weixin_mark_color.jpg')

    代码中,我使用 skimage 中的 label2rgb 函数来将 label 分类标识转化为颜色数值,因为我们的颜色值范围是[0,255],所以还需要乘以 255 进行转化,最后再转化为 np.uint8 类型。unit8 类型代表无符号整数,范围是 0-255 之间。

    得到颜色矩阵后,你可以把它输出出来,这时你发现输出的图像是颠倒的,原因可能是图像源拍摄的时候本身是倒置的。我们需要设置三维矩阵的转置,让第一维和第二维颠倒过来,也就是使用 transpose(1,0,2),将原来的 (0,1,2)顺序转化为 (1,0,2) 顺序,即第一维和第二维互换。

    最后我们使用 fromarray 函数,它可以通过矩阵来生成图片,并使用 save 进行保存。最后得到的分类标识颜色化图像是这样的:ebd73041e09db2c9d90cb83c97b10524.png刚才我们做的是聚类的可视化。如果我们想要看到对应的原图,可以将每个簇(即每个类别)的点的 RGB 值设置为该簇质心点的 RGB 值,也就是簇内的点的特征均为质心点的特征。

    我给出了完整的代码,代码中,我可以把范围为 0-255 的数值投射到 1-256 数值之间,方法是对每个数值进行加 1,你可以自己来运行下:

    # -*- coding: utf-8 -*-
    # 使用K-means对图像进行聚类,并显示聚类压缩后的图像
    import numpy as np
    import PIL.Image as image
    from sklearn.cluster import KMeans
    from sklearn import preprocessing
    import matplotlib.image as mpimg
    # 加载图像,并对数据进行规范化
    def load_data(filePath):
    # 读文件
    f = open(filePath,'rb')
    data = []
    # 得到图像的像素值
    img = image.open(f)
    # 得到图像尺寸
    width, height = img.size
    for x in range(width):
    for y in range(height):
    # 得到点(x,y)的三个通道值
    c1, c2, c3 = img.getpixel((x, y))
    data.append([(c1+1)/256.0, (c2+1)/256.0, (c3+1)/256.0])
    f.close()
    return np.mat(data), width, height
    # 加载图像,得到规范化的结果imgData,以及图像尺寸
    img, width, height = load_data('./weixin.jpg')
    # 用K-Means对图像进行16聚类
    kmeans =KMeans(n_clusters=16)
    label = kmeans.fit_predict(img)
    # 将图像聚类结果,转化成图像尺寸的矩阵
    label = label.reshape([width, height])
    # 创建个新图像img,用来保存图像聚类压缩后的结果
    img=image.new('RGB', (width, height))
    for x in range(width):
    for y in range(height):
    c1 = kmeans.cluster_centers_[label[x, y], 0]
    c2 = kmeans.cluster_centers_[label[x, y], 1]
    c3 = kmeans.cluster_centers_[label[x, y], 2]
    img.putpixel((x, y), (int(c1*256)-1, int(c2*256)-1, int(c3*256)-1))
    img.save('weixin_new.jpg')

    结果如下:51172397bfabd8bff9d4600762f83c9d.png你可以看到我没有用到 sklearn 自带的 MinMaxScaler,而是自己写了 Min-Max 规范化的公式。这样做的原因是我们知道 RGB 每个通道的数值在[0,255]之间,所以我们可以用每个通道的数值 +1/256,这样数值就会在[0,1]之间。

    对图像做了 Min-Max 空间变换之后,还可以对其进行反变换,还原出对应原图的通道值。对于点 (x,y),我们找到它们所属的簇 label[x,y],然后得到这个簇的质心特征,用 c1,c2,c3 表示:

    c1 = kmeans.cluster_centers_[label[x, y], 0]
    c2 = kmeans.cluster_centers_[label[x, y], 1]
    c3 = kmeans.cluster_centers_[label[x, y], 2]

    因为 c1, c2, c3 对应的是数据规范化的数值,因此我们还需要进行反变换,即:

    c1=int(c1*256)-1
    c2=int(c2*256)-1
    c3=int(c3*256)-1

    然后用 img.putpixel 设置点 (x,y) 反变换后得到的特征值。最后用 img.save 保存图像。

    5. 总结

    好了,写到这关于KMeans,就要结束了。下面快速的回顾一下:

    首先,通过足球队聚类的例子引出了KMeans聚类的工作原理,简单来说两步,你可以回忆回忆。

    然后,通过KMeans实现了对图像分割的实战,另外我们还学习了如何在 Python 中如何对图像进行读写,具体的代码如下,上文中也有相应代码,你也可以自己对应下:

    import PIL.Image as image
    # 得到图像的像素值
    img = image.open(f)
    # 得到图像尺寸
    width, height = img.size

    这里会使用 PIL 这个工具包,它的英文全称叫 Python Imaging Library,顾名思义,它是 Python 图像处理标准库。同时我们也使用到了 skimage 工具包(scikit-image),它也是图像处理工具包。用过 Matlab 的同学知道,Matlab 处理起图像来非常方便。skimage 可以和它相媲美,集成了很多图像处理函数,其中对不同分类标识显示不同的颜色。在 Python 中图像处理工具包,我们用的是 skimage 工具包。

    好了,KMeans的故事就到这里吧。

    参考:

    • http://note.youdao.com/noteshare?id=10dac8bb5d83358ffe73c792e1490a7b&sub=C7A3E74A1088435ABBE11AB91AC37194
    • https://time.geekbang.org/
    • 91bf50388acc47157a80bab0c9cef08f.png

    点个在看,么么哒!

    4b2e4f7ad525c7c821046d29a9a1c916.gif
    展开全文
  • 1. Kmeans聚类算法原理 1.1 概述 K-means算法是集简单和经典于一身的基于距离的聚类算法 采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。 该算法认为类簇是由距离靠近的对象组成的,...

     

    1. Kmeans聚类算法原理

    1.1 概述

    K-means算法是集简单和经典于一身的基于距离的聚类算法

    采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。

    该算法认为类簇是由距离靠近的对象组成的,因此把得到紧凑且独立的簇作为最终目标。

     

    1.2 算法图示

    假设我们的n个样本点分布在图中所示的二维空间。

    从数据点的大致形状可以看出它们大致聚为三个cluster,其中两个紧凑一些,剩下那个松散一些,如图所示:

     

    我们的目的是为这些数据分组,以便能区分出属于不同的簇的数据,给它们标上不同的颜色,如图:

     

    1.3 算法要点

    1.3.1 核心思想

    通过迭代寻找k个类簇的一种划分方案,使得用这k个类簇的均值来代表相应各类样本时所得的总体误差最小。

    k个聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。

     k-means算法的基础是最小误差平方和准则,

    其代价函数是:

        

           式中,μc(i)表示第i个聚类的均值。

    各类簇内的样本越相似,其与该类均值间的误差平方越小,对所有类所得到的误差平方求和,即可验证分为k类时,各聚类是否是最优的。

    上式的代价函数无法用解析的方法最小化,只能有迭代的方法。

     

    1.3.2 算法步骤图解

    下图展示了对n个样本点进行K-means聚类的效果,这里k取2。

     

    1.3.3 算法实现步骤

    k-means算法是将样本聚类成 k个簇(cluster),其中k是用户给定的,其求解过程非常直观简单,具体算法描述如下:

    1. 随机选取 k个聚类质心点
    2. 重复下面过程直到收敛  {

          对于每一个样例 i,计算其应该属于的类:

              

          对于每一个类 j,重新计算该类的质心:

                

      }

       

    其伪代码如下:

    ********************************************************************

    创建k个点作为初始的质心点(随机选择)

    当任意一个点的簇分配结果发生改变时

           对数据集中的每一个数据点

                  对每一个质心

                         计算质心与数据点的距离

                  将数据点分配到距离最近的簇

           对每一个簇,计算簇中所有点的均值,并将均值作为质心

     

    2. Kmeans分类算法Python实战

    2.1 需求

    对给定的数据集进行聚类

    本案例采用二维数据集,共80个样本,有4个类。样例如下:

    testSet.txt

    1.658985  4.285136

    -3.453687 3.424321

    4.838138     -1.151539

    -5.379713 -3.362104

    0.972564     2.924086

    -3.567919 1.531611

    0.450614   -3.302219

    -3.487105 -1.724432

    2.668759  1.594842

    -3.156485 3.191137

    3.165506  -3.999838

    -2.786837 -3.099354

    4.208187  2.984927

    -2.123337 2.943366

    0.704199  -0.479481

    -0.392370 -3.963704

    2.831667  1.574018

    -0.790153 3.343144

    2.943496  -3.357075

     

    2.2 python代码实现

    2.2.1 利用numpy手动实现

    from numpy import *

    #加载数据

    def loadDataSet(fileName):

        dataMat = []

        fr = open(fileName)

        for line in fr.readlines():

            curLine = line.strip().split('\t')

            fltLine = map(float, curLine)    #变成float类型

            dataMat.append(fltLine)

        return dataMat

     

    # 计算欧几里得距离

    def distEclud(vecA, vecB):

        return sqrt(sum(power(vecA - vecB, 2)))

     

    #构建聚簇中心,取k个(此例中为4)随机质心

    def randCent(dataSet, k):

        n = shape(dataSet)[1]

        centroids = mat(zeros((k,n)))   #每个质心有n个坐标值,总共要k个质心

        for j in range(n):

            minJ = min(dataSet[:,j])

            maxJ = max(dataSet[:,j])

            rangeJ = float(maxJ - minJ)

            centroids[:,j] = minJ + rangeJ * random.rand(k, 1)

        return centroids

     

    #k-means 聚类算法

    def kMeans(dataSet, k, distMeans =distEclud, createCent = randCent):

        m = shape(dataSet)[0]

        clusterAssment = mat(zeros((m,2)))    #用于存放该样本属于哪类及质心距离

        centroids = createCent(dataSet, k)

        clusterChanged = True

        while clusterChanged:

            clusterChanged = False;

            for i in range(m):

                minDist = inf; minIndex = -1;

                for j in range(k):

                    distJI = distMeans(centroids[j,:], dataSet[i,:])

                    if distJI < minDist:

                        minDist = distJI; minIndex = j

                if clusterAssment[i,0] != minIndex: clusterChanged = True;

                clusterAssment[i,:] = minIndex,minDist**2

            print centroids

            for cent in range(k):

                ptsInClust = dataSet[nonzero(clusterAssment[:,0].A == cent)[0]]   # 去第一列等于cent的所有列

                centroids[cent,:] = mean(ptsInClust, axis = 0)

        return centroids, clusterAssment

    2.2.2 利用scikili库实现

    Scikit-Learn是基于python的机器学习模块,基于BSD开源许可证。

    scikit-learn的基本功能主要被分为六个部分,分类,回归,聚类,数据降维,模型选择,数据预处理。包括SVM,决策树,GBDT,KNNKMEANS等等

    Kmeans在scikit包中即已有实现,只要将数据按照算法要求处理好,传入相应参数,即可直接调用其kmeans函数进行聚类

    #################################################

    # kmeans: k-means cluster

    #################################################

    from numpy import *

    import time

    import matplotlib.pyplot as plt

    ## step 1:加载数据

    print "step 1: load data..."

    dataSet = []

    fileIn = open('E:/Python/ml-data/kmeans/testSet.txt')

    for line in fileIn.readlines():

    lineArr = line.strip().split('\t')

    dataSet.append([float(lineArr[0]), float(lineArr[1])])

    ## step 2: 聚类

    print "step 2: clustering..."

    dataSet = mat(dataSet)

    k = 4

    centroids, clusterAssment = kmeans(dataSet, k)

    ## step 3:显示结果

    print "step 3: show the result..."

    showCluster(dataSet, k, centroids, clusterAssment)

    2.2.3 运行结果

    不同的类用不同的颜色来表示,其中的大菱形是对应类的均值质心点。

     

    1. Kmeans算法补充

    3.1 kmeans算法缺点

    k-means算法比较简单,但也有几个比较大的缺点:

     

    (1)k值的选择是用户指定的,不同的k得到的结果会有挺大的不同,如下图所示,左边是k=3的结果,这个就太稀疏了,蓝色的那个簇其实是可以再划分成两个簇的。而右图是k=5的结果,可以看到红色菱形和蓝色菱形这两个簇应该是可以合并成一个簇的:

    (2)对k个初始质心的选择比较敏感,容易陷入局部最小值。例如,我们上面的算法运行的时候,有可能会得到不同的结果,如下面这两种情况。K-means也是收敛了,只是收敛到了局部最小值:

     

     

    (3)存在局限性,如下面这种非球状的数据分布就搞不定了:

     

    (4)数据集比较大的时候,收敛会比较慢。

     

    3.2 改良思路

    k-means老早就出现在江湖了。所以以上的这些不足也已有了对应方法进行了某种程度上的改良。例如:

    • 问题(1)对k的选择可以先用一些算法分析数据的分布,如重心和密度等,然后选择合适的k
    • 问题(2),有人提出了另一个成为二分k均值(bisecting k-means)算法,它对初始的k个质心的选择就不太敏感
    展开全文
  • 4、线性回归的损失函数 5、机器学习:知道哪些传统机器学习模型 3、处理聚类问题常用算法 1、什么是DBSCAN 2、k-means算法流程 3、LDA的原理 4、介绍几种机器学习的算法,我就结合我的项目经理介绍了些RF, Kmeans等...
  • RFM模型多用于已知目标数据集,场景具有一定的局限性,本篇运用一个适用比较广泛的聚类算法——K-Means,它属于无监督机器学习,K-Means算法的思想很简单,对于给定的样本集,按照样本之间的距离大小,将样本集划分...
  • Kmeans 聚类算法

    2021-02-20 12:36:24
    KMeans算法属于无监督学习,解决聚类的问题 对于数据集D, 不需提供数据标记,大大减少工作量 数据集D必须是凸集,非凸数据集难以收敛 必须先指定聚类簇数k k-means优点 原理简单,实现容易,可解释性较强 聚类...
  • 聚类算法应用场景实例十则

    千次阅读 2017-06-15 07:03:58
    本文整理了10个天池、DataCastle、DataFountain等中出现的,可使用聚类算法处理的问题场景实例。 1 基于用户位置信息的商业选址  随着信息技术的快速发展,移动设备和移动互联网已经普及到千家万户。...
  • Spark自编程实现Kmeans聚类算法

    千次阅读 2018-11-28 23:33:08
    Spark实现 – Kmeans聚类算法 Kmeans简介 Kmeans是最常用的聚类算法,也是十大经典的数据挖掘算法之一。聚类的思想用一句话概括就是“物以类聚,人以群分”。kmeans算法作为最基础的算法之一,基本上每本数据挖掘的...
  • 1. 写在前面如果想从事数据挖掘或者机器学习的工作,掌握常用的机器学习算法是非常有必要的,常见的机器学习算法:监督学习算法:逻辑回归,线性回归,决策树,朴素贝叶斯,K近邻,支持向量机,集成算法Adaboost等无...
  • 基于Python的Kmeans聚类分析介绍及实践 这是一篇学习的总结笔记 参考自《从零开始学数据分析与挖掘》 [中]刘顺祥 著 完整代码及实践所用数据集等资料放置于:Github 聚类算法是依据已知的数据集,将高度相似的...
  • 基于RFM模型的K均值聚类算法实现模型介绍K 均值聚类原理聚类步骤导入库读取数据正确的代码...Kmeans聚类算法利用距远近的思想将目标数据聚为指定的k个簇,进而使样本呈现簇内差异小,簇间差异大的特征。 K 均值聚类原
  • 上文的层次聚类算法在数据挖掘中其实并不常用,因为只是适用于小数据。所以我们引出了K-Means聚类法,这种方法计算量比较小。能够理解K-Means的基本原理并将代码用于实际业务案例是本文的目标。下文将详细介绍如何...
  • 1. 写在前面如果想从事数据挖掘或者机器学习的工作,掌握常用的机器学习算法是非常有必要的,常见的机器学习算法:监督学习算法:逻辑回归,线性回归,决策树,朴素贝叶斯,K近邻,支持向量机,集成算法Adaboost等无...
  • 聚类算法及其应用

    千次阅读 2020-05-02 01:10:06
    1. 聚类算法都是无监督学习吗? 什么是聚类算法?聚类是一种机器学习技术,它涉及到数据点的分组。给定一组数据点,我们可以使用聚类算法将每个数据点划分为一个特定的组。理论上,同一组中的数据点应该具有相似的...
  • KMeans算法( 聚类分析)

    万次阅读 热门讨论 2019-11-21 21:03:04
    1 聚类分析相关概念 1.1 聚类与分类 分类其实是从特定的数据中挖掘模式,作出判断的过程。比如Gmail邮箱里有垃圾邮件分类器,一开始的时候可能什么都不过滤,在日常使用过程中,我人工对于每一封邮件点选“垃圾...
  • 针对高维数据聚类中K-means算法无法有效抑制噪声特征、实现不规则形状聚类的缺点,提出一种基于目标点特征选择和去除的改进K-均值聚类算法.该算法使用闵可夫斯基规度作为评价距离进行目标点的分类,增设权重调节参数...
  • R语言聚类分析-kmeans聚类分析实战

    万次阅读 多人点赞 2018-04-12 22:47:17
    聚类分析涉及的方法有层次聚类、kmeans聚类、密度聚类等,这里主要介绍最容易上手的kmeans聚类算法,上手就是王道!kmeans聚类原理:基于原型的、划分的距离技术,它试图发现用户指定个数(K)的簇。统计学原理请大家...
  • K-Means算法的十大应用场景

    千次阅读 2020-06-02 21:06:53
    K-means算法通常可以应用于维数、数值都很小且连续的数据集,比如:从随机分布的事物集合中将相同事物进行分组。 1.文档分类器 根据标签、主题和文档内容将文档分为多个不同的类别。这是一个非常标准且经典的K-means...
  • 本文对K-Means聚类分析进行了详细的讲解,包括对理论的简略说明和详细的SPSS操作过程,以及部分参考文献供大家参考学习。目录1. 什么是聚类分析2. K-Means步骤3. 初始中心点怎么确定4. K值怎么确定5. 理论小结6. ...
  • k-means聚类算法及其优化

    千次阅读 热门讨论 2021-05-14 20:26:36
    k-means聚类算法及其优化 在机器学习中有这样一种场景,需要对已知数据按照一定的关系归到不同的类别中(无监督) k-means是比较流行的聚类方法 其基本算法流程如下: 随机设置K个特征空间内的点作为初始的聚类中心...
  • 第十五章 Kmeans聚类01 Kmeans聚类的思想和原理模型介绍对于有监督的...Kmeans聚类算法利用距离远近的思想将目标数据聚为指定的k个簇,进而使样本呈现簇内差异小,簇间差异大的特征。聚类过程从数据中随机挑选个样本...
  • 1. 聚类1.1 什么是聚类?所谓聚类问题,就是给定一个...1.2 KMeans 聚类算法K-Means聚类算法主要分为如下几个步骤:从D中随机取k个元素,作为k个簇的各自的中心分别计算剩下的元素到k个簇中心的相异度,将这些元素分
  • 以下不作为机器学习/算法工程师的学习路径,只是汇总的校招机器学习/算法工程师面试考点(因为还有笔试考点,后面结合在一起给大家学习路径),后续会为大家更新10w+字数的机器学习/算法工程师校招面试题库,还有其他...
  • Kmeans聚类实例④——电商用户质量聚类分析(RFM)

    万次阅读 多人点赞 2019-06-15 18:59:38
    聚类通常分为以下步骤: ① 业务提出需求 ② 根据业务需求,找到核心的指标。有现成的模型的话(如RFM),可以直接按模型的指标,如果没有,先罗列出比较重要的指标 ...⑥ 根据聚类结果,结合业务场景提供建议 本篇...
  • 一、Kmeans模型
  • K-Means聚类算法--步骤+代码

    千次阅读 2020-09-29 14:57:01
    聚类和分类算法的最大区别在于,分类的目标类别为已知(监督学习),而聚类的目标类别是未知的(非监督)。K_Means算法(K_均值算法)就是无监督算法之一 1.原理 对于给定的样本集,按照样本之间的距离大小,将样本...
  • 机器学习聚类算法Kmeans与DBSCAN

    千次阅读 2018-04-16 20:46:36
    1. KMeans1.1 算法概述Kmeans是一种划分聚类的方法,基本K-Means算法的思想很简单,事先确定常数K,常数K意味着最终的聚类类别数,首先随机选定初始点为质心,并通过计算每一个样本与质心之间的相似度(这里为欧式...
  • 引言在数据分析中,我们常常想将看...分类与聚类是数据挖掘领域两大基础方法,分类被用于监督学习中而聚类算法属于无监督的。聚类算法主要是将相似的数据聚合在一起形成不同的组别,但是组与组之间相差很大。 在本次
  • means的应用场景sklearn实现K-means使用鸢尾花数据进行聚类聚类结果查看三个中心点使用K-means进行图片分割显示原图像RGB分布在RGB分布图中显示划分图像划分结果使用聚类进行预处理加载数据集一个简单的逻辑回归模型...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,330
精华内容 1,332
关键字:

kmeans聚类算法应用场景