k均值算法 机器学习_机器学习k均值算法 - CSDN
  • 机器学习K均值(K-Means)算法

    千次阅读 2018-11-17 21:09:36
    K均值(K-Means)算法是无监督的聚类方法,实现起来比较简单,聚类效果也比较好,因此应用很广泛。K-Means算法针对不同应用场景,有不同方面的改进。我们从最传统的K-Means算法讲起,然后在此基础上介绍初始化质心优化...

    1.K-Means简介

    K均值(K-Means)算法是无监督的聚类方法,实现起来比较简单,聚类效果也比较好,因此应用很广泛。K-Means算法针对不同应用场景,有不同方面的改进。我们从最传统的K-Means算法讲起,然后在此基础上介绍初始化质心优化K-Means++算法,距离计算优化Elkan K-Means算法和大样本情况下Mini Batch K-Means算法。

    K-Means算法的思想很简单,对于给定的样本集,按照样本之间的距离大小,将样本集划分为K个簇。让簇内的点尽可能紧密的连在一起,而让簇间的距离尽量的大,下面我们引入K-Means目标函数。

    假设样本集输入变量为(x1,x2,x3,…,xm),样本集划分为K个簇(C1,C2,C3,…,Ck),则我们的目标是最小化平方误差E。
    E=i=1kxCixμi2 E=\sum _{i=1}^{k} \sum _{x \in C_i}||x-\mu _i||^2
    其中μi是簇Ci的均值向量,也可称作质心,表达式为
    μi=1CixCix \mu _i=\frac{1}{|C_i|}\sum _{x \in C_i}x
    如果直接求解上述最小值的话,那么为NP Hard问题,因此K-Means算法采用启发式的迭代方法。下面我们通过一个简单聚类来介绍K-Means算法迭代过程。

    • 如图(a)所示:表示初始化数据集。
    • 如图(b)所示:假设K=2,随机选择两个点作为类别质心,分别为图中的红色质心和蓝色质心。
    • 如图©所示:分别求样本点xi到这两个质心的距离,并标记每个样本点的类别为距离质心最近的类别。划分得到两个簇C1和C2,完成一次迭代。
    • 如图(d)所示:对标记为红色的点和蓝色的点分别求新的质心。
    • 如图(e)所示:重复图©(d)过程,标记每个样本点的类别为距离质心最近的类别,重新划分得到两个簇C1和C2。
    • 如图(f)所示:直到质心不再改变后完成迭代,最终得到两个簇C1和C2。
      01

    2.K-Means算法流程

    假设输入样本集D=x1,x2,,xmD={x_1,x_2,…,x_m},聚类簇数为K,最大迭代次数为N。输出的簇划分为C=C1,C2,,CmC={C_1,C_2,…,C_m}

    • 从数据集D中随机选择K个样本作为初始的质心向量$ \mu={ \mu_1,\mu_2,\mu_3,…,\mu_k }$。

    • 迭代n=1,2,,Nn=1,2,…,N

      • 划分初始化簇Ct=; t=1,2,,kC_t=\varnothing ;\ t=1,2,…,k
      • 对于i=1,2,,mi=1,2,…,m,计算样本xix_i和各个质心向量μj( j=1,2,,k)\mu_j(\ j=1,2,…,k)的距离dijd_{ij}。将xix_i标记为最小的dijd_{ij}所对应的类别λi\lambda_i,此时更新Cλi=CλixiC_{\lambda i}=C_{\lambda i} \cup{x_i}

      dij=xiμj2 d_{ij}=||x_i-\mu_j||^2

      • 对于j=1,2,,kj=1,2,…,k,对CjC_j中所有样本点重新计算新的质心。

      μj=1CjxCjx \mu_j=\frac{1}{|C_j|}\sum_{x\in C_j}x

      • 如果K个质心向量都不再发生变化,则结束迭代。
    • 输出K个划分簇CCC={C1,C2,C3,,Ck}C=\{C_1,C_2,C_3,…,C_k \}

    对于K-Means算法,首先要注意K值的选择和K个初始化质心的选择。

    • **对于K值的选择:**我们可以通过对数据的先验经验选择合适的K值,如果没有先验条件的话,还可以通过交叉验证选择合适的K值。
    • **对于K个初始化质心:**由于我们采用启发式迭代方法,K个初始化质心的位置选择对最后的聚类结果和运行时间都有较大的影响,最好选择的K个质心不要离得太近。

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

    如果是完全随机的选择, 算法的收敛可能很慢。我们在此介绍K-Means++算法,针对随机初始化质心进行优化,具体算法流程如下所示。

    • 从输入的数据点集合中随机选择一个点作为第一个聚类中心μ1。
    • 对于数据集中的每个点xi,计算与他最近的聚类中心距离。

    D(x)=argminr=1kselectedxiμr2 D(x)=\arg \min_{r=1}^{k_{selected}}||x_i-\mu_r||^2

    • 选择一个数据点作为新的聚类中心,其中D(x)较大的点被选作新的聚类中心的概率较大。
    • 重复上述两步,直到选择出K个聚类中心。然后利用这K个质心来作为初始化质心去运行传统K-Means算法。

    4.距离计算优化Elkan K-Means算法

    传统K-Means算法中,我们每次迭代时都要计算所有样本点到所有质心之间的距离,那么有没有什么方法来减少计算次数呢? Elkan K-Means算法提出利用两边之和大于第三边、两边之差小于第三边的三角形特性来减少距离的计算。

    • 对于一个样本点xx和两个质心μj1,μj2\mu_{j1},\mu_{j2},如果我们预先计算出这两个质心之间的距离D(j1,j2)D(j_1,j_2),如果发现2D(x,j1)D(j1,j2)2D(x,j_1)≤D(j_1,j_2),那么我们便能得到D(x,j1)D(x,j2)D(x,j_1)≤D(x,j_2)。此时我们不再计算D(x,j2)D(x,j_2),也就节省了一步距离计算。
    • 对于一个样本点xx和两个质心μj1,μj2μ_{j1},μ_{j2},我们能够得到D(x,j2)max0,D(x,j1)D(j1,j2)D(x,j_2)≥max{0,D(x,j_1)−D(j_1,j_2)}

    Elkan K-Means迭代速度比传统K-Means算法迭代速度有较大提高,但如果我们的样本特征是稀疏的,或者有缺失值的话,此种方法便不再使用。

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

    传统的K-Means算法中需要计算所有样本点到所有质心的距离,计算复杂度较高。如果样本量非常大的情况下,比如数据量达到10万,特征在100以上,此时用传统K-Means算法非常耗时。故此针对大样本情况下采用Mini Batch K-Means算法。

    Mini Batch K-Means采用无放回随机采样的方法从样本集中选取部分数据,然后用选取的数据进行传统的K-Means算法训练。然后进行迭代并更新质心,直到质心稳定或达到指定的迭代次数。

    Mini Batch K-Means可以避免样本量太大带来的计算问题,算法收敛速度也能够加快,当然带来的代价就是我们的聚类精确度降低。为增加算法的准确性,我们可以多训练几次Mini Batch K-Means算法,用不同的随机采样集来得到聚类簇,选择其中最优的聚类簇。

    6.Sklearn实现K-Means算法

    我们经常需要通过改变参数来让模型达到聚类结果,具体参数设置可参考sklearn官方教程

    from sklearn.cluster import KMeans
    from sklearn.datasets import load_iris
    import matplotlib.pyplot as plt
    
    #load iris
    iris=load_iris()
    X=iris.data[:,:2]
    print(X.shape)
    #150,2
    
    #plot data
    plt.figure()
    plt.scatter(X[:,0],X[:,1],c='blue',
                marker='o',label='point')
    plt.legend(loc=2)
    plt.show()
    

    02

    # fit data
    kmeans=KMeans(n_clusters=3)
    kmeans.fit(X)
    label_pred=kmeans.labels_
    
    #plot answer
    plt.figure()
    x0 = X[label_pred == 0]
    x1 = X[label_pred == 1]
    x2 = X[label_pred == 2]
    plt.scatter(x0[:, 0], x0[:, 1], c = "red",
                marker='o', label='label0')
    plt.scatter(x1[:, 0], x1[:, 1], c = "green",
                marker='*', label='label1')
    plt.scatter(x2[:, 0], x2[:, 1], c = "blue",
                marker='+', label='label2')
    plt.legend(loc=2)
    plt.show()
    

    03

    7.K-Means算法优缺点

    7.1优点

    • 聚类效果较优。

    • 原理简单,实现容易,收敛速度快。

    • 需要调整的参数较少,通常只需要调整簇数K。

    7.2缺点

    • K值选取不好把握。
    • 对噪音和异常点比较敏感。
    • 采用迭代方法,得到的结果是局部最优。
    • 如果各隐含类别的数据不平衡,则聚类效果不佳。

    8.推广

    更多内容请关注公众号谓之小一,若有疑问可在公众号后台提问,随时回答,欢迎关注,内容转载请注明出处。
    推广

    参考

    展开全文
  • 机器学习-聚类(K均值算法)

    千次阅读 2018-08-01 16:00:44
    采用K均值算法进行聚类,首先需要做的是确定K的个数,一般来讲,有以下几种方法: 1、按需选择 简单地说就是按照建模的需求和目的来选择聚类的个数。比如说,一个游戏公司想把所有玩家做聚类分析,分成顶级、高级...

    一,介绍

    采用K均值算法进行聚类,首先需要做的是确定K的个数,一般来讲,有以下几种方法:

    1、按需选择

    简单地说就是按照建模的需求和目的来选择聚类的个数。比如说,一个游戏公司想把所有玩家做聚类分析,分成顶级、高级、中级、菜鸟四类,那么K=4;如果房地产公司想把当地的商品房分成高中低三档,那么K=3。按需选择虽然合理,但是未必能保证在做K-Means时能够得到清晰的分界线。

    2、观察法

    就是用肉眼看,看这些点大概聚成几堆。这个方法虽然简单,但是同时也模棱两可。

    左上角是原始点。右上角分成了两类。左下角是三类,左下角是四类。至于K到底是选3还是选4,可能每个人都有不同的选择。

    观察法的另一个缺陷就是:原始数据维数要低,一般是两维(平面散点)或者三维(立体散点),否则人类肉眼则无法观察。对于高维数据,我们通常利用PCA降维,然后再进行肉眼观察。

    3、手肘法

    手肘法本质上也是一种间接的观察法。我们将得到K个聚类的中心点Mi, i=1,2,⋯,K。以及每个原始点所对应的聚类Ci,i=1,2,⋯,K。我们通常采用所有样本点到它所在的聚类的中心点的距离的和作为模型的度量,记为DK。

        

    这里距离可以采用欧式距离。
    对于不同的K,最后我们会得到不同的中心点和聚类,所有会有不同的度量。

    我们把上面的例子用不同的K去计算,会得到不同的结果。把K作为横坐标,DK作为纵坐标,我们可以得到下面的折线。

    很显然K越大,距离和越小。但是我们注意到K=3是一个拐点,就像是我们的肘部一样,K=1到3下降很快,K=3之后趋于平稳。手肘法认为这个拐点就是最佳的K。

    手肘法是一个经验方法,而且肉眼观察也因人而异,特别是遇到模棱两可的时候。相比于直接观察法,手肘法的一个优点是,适用于高维的样本数据。有时候人们也会把手肘法用于不同的度量上,如组内方差组间方差比。

    4、Gap Statistic方法

    这里我们要继续使用上面的DK。Gap Statistic的定义为:

        

    这里E(logDk)指的是logDk的期望。这个数值通常通过蒙特卡洛模拟产生,我们在样本里所在的矩形区域中(高维的话就是立方体区域)按照均匀分布随机地产生和原始样本数一样多的随机样本,并对这个随机样本做聚类,从而得到一个DK。如此往复多次,通常20次,我们可以得到20个logDK。对这20个数值求平均值,就得到了E(logDK)的近似值。最终可以计算Gap Statisitc。而Gap statistic取得最大值所对应的K就是最佳的K。

    用上图的例子,我们计算了K=1,2,..9对应的Gap Statisitc. 

    确定好K的个数后,算法开始,算法流程如下:

    1,确定K个聚类的中心;

    2,计算每个点与各个中心的距离,选择距离最近的中心成为其分类,公式如下:

                                                                                          

    3,更新聚类的中心;

    4,重复上述步骤直到结束

    二,代码

    数据如下:

    0.697   0.46
    0.774  0.376
    0.634  0.264
    0.608  0.318
    0.556  0.215
    0.403  0.237
    0.481  0.149
    0.437  0.211
    0.666  0.091
    0.243  0.267
    0.245  0.057
    0.343  0.099
    0.639  0.161
    0.657  0.198
    0.36   0.37
    0.593  0.042
    0.719  0.103
    0.359  0.188
    0.339  0.241
    0.282  0.257
    0.748  0.232
    0.714  0.346
    0.483  0.312
    0.478  0.437
    0.525  0.369
    0.751  0.489
    0.532  0.472
    0.473  0.376
    0.725  0.445
    0.446  0.459
    

    python代码:

    import matplotlib.pyplot as plt
    from numpy import *
    import random
    
    def loadDataSet(filename):
        fr = open(filename)
        numberOfLines = len(fr.readlines())
        returnMat = zeros((numberOfLines, 2))
        classLabelVector = ['密度','含糖率']
        fr = open(filename)
        index = 0
        for line in fr.readlines():
            line = line.strip().split('\t')
            returnMat[index, :] = line[0:2]
            index += 1
        return returnMat, classLabelVector
    
    # 欧几里得距离
    def edistance(v1, v2):
        result=0.0
        for i in range(len(v1)):
            result +=(v1[i]-v2[i])**2
        return sqrt(result)
    
    # 特征值归一化
    def autoNorm(dataSet):
        minVals = dataSet.min(0)            # 获取特征值最小值
        maxVals = dataSet.max(0)            # 获取特征值最大值
        ranges = maxVals - minVals
        m = dataSet.shape[0]
        normDataSet = dataSet - tile(minVals, (m,1))
        normDataSet = normDataSet/tile(ranges, (m,1))   #归一化
        return normDataSet, ranges, minVals
    
    def kcluster(rows, distance=edistance, k=3):
        normDataSet, ranges, minVals = autoNorm(rows)   # 归一化数据到0-1之间
        count = normDataSet.shape[0]                        # 数据总数
        randinfo = random.sample(range(0, count), k)
        clusters = [normDataSet[randinfo[i]] for i in range(len(randinfo))]  # 随机选取k个值作为聚类中心
    
        lastmatches = None
        for t in range(100):
            bestmatches = [[] for i in range(k)]
    
            # 寻找最近中心
            for j in range(count):
                row = normDataSet[j]
                bestmatch = 0
                for i in range(k):
                    d = distance(row,clusters[i])
                    if d < distance(row,clusters[bestmatch]): bestmatch = i
                bestmatches[bestmatch].append(j)
    
            # 如果没有变化则认为最佳,退出循环
            if bestmatches == lastmatches: break
            lastmatches = bestmatches
    
            # 移动聚类的中心
            for i in range(k):
                avgs = [0.0] * len(normDataSet[0])
                if len(bestmatches[i]) > 0:
                    for rowid in bestmatches[i]:
                        for m in range(len(normDataSet[rowid])):
                            avgs[m] += normDataSet[rowid][m]
                    for j in range(len(avgs)):
                        avgs[j] /= len(bestmatches[i])
                    clusters[i] = avgs
    
        return bestmatches
    
    def plot(dataMat, labelMat,bestmatches):
        xcord = [];ycord = []
        sumx1=0.0;sumy1=0.0;sumx2=0.0;sumy2=0.0;sumx3=0.0;sumy3=0.0
        midx = [];midy=[]
        for i in range(len(dataMat)):
            xcord.append(float(dataMat[i][0]));ycord.append(float(dataMat[i][1]))
        for i in range(len(bestmatches)):
            for j in bestmatches[i]:
                if(i==0):
                    plt.scatter(xcord[j], ycord[j], color='red')
                    sumx1+=xcord[j]
                    sumy1+=ycord[j]
                if(i == 1):
                    plt.scatter(xcord[j], ycord[j], color='green')
                    sumx2 += xcord[j]
                    sumy2 += ycord[j]
                if (i == 2):
                    plt.scatter(xcord[j], ycord[j], color='black')
                    sumx3 += xcord[j]
                    sumy3 += ycord[j]
        midx.append(sumx1/len(bestmatches[0]))
        midx.append(sumx2 / len(bestmatches[1]))
        midx.append(sumx3 / len(bestmatches[2]))
        midy.append(sumy1 / len(bestmatches[0]))
        midy.append(sumy2 / len(bestmatches[1]))
        midy.append(sumy3 / len(bestmatches[2]))
        plt.scatter(midx,midy, marker = '+',color='blue')
        plt.xlabel(labelMat[0]);plt.ylabel(labelMat[1])
        plt.xlim((0, 1))
        plt.ylim((0, 1))
        plt.show()
    
    if __name__=='__main__':
        dataMat, labelMat = loadDataSet('watermelon4.0.txt')
        bestmatches = kcluster(dataMat)
        plot(dataMat, labelMat,bestmatches)
    结果:

    展开全文
  • 机器学习实战》系列博客是博主阅读《机器学习实战》这本书的笔记,包含对其中算法的理解和算法的Python代码实现 另外博主这里有机器学习实战这本书的所有算法源代码和算法所用到的源文件,有需要的留言 ...

     

    ============================================================================================
    《机器学习实战》系列博客是博主阅读《机器学习实战》这本书的笔记,包含对其中算法的理解和算法的Python代码实现
     
    另外博主这里有机器学习实战这本书的所有算法源代码和算法所用到的源文件,有需要的留言
    ============================================================================================

     

    Scikit-learn 实现的K-Means 算法请参考 :点击阅读

    二分K-Means算法请参考:点击阅读

            机器学习中有两类的大问题,一个是分类,一个是聚类。分类是根据一些给定的已知类别标号的样本,训练某种学习机器,使它能够对未知类别的样本进行分类。这属于supervised learning(监督学习)。而聚类指事先并不知道任何样本的类别标号,希望通过某种算法来把一组未知类别的样本划分成若干类别,这在机器学习中被称作 unsupervised learning (无监督学习)。在本文中,我们关注其中一个比较简单的聚类算法:k-means算法。 

            k-means算法是一种很常见的聚类算法,它的基本思想是:通过迭代寻找k个聚类的一种划分方案,使得用这k个聚类的均值来代表相应各类样本时所得的总体误差最小。

    其Python实现的代码如下:

    #encoding:utf-8
    from numpy import *
    
    def loadDataSet(filename):
    	dataMat = []          #创建元祖
    	fr = open(filename)
    	for line in fr.readlines():
    		curLine = line.strip().split("\t")
    		fltLine = map(float,curLine) #使用map函数将curLine里的数全部转换为float型
    		dataMat.append(fltLine)
    	return dataMat
    
    def distEclud(vecA,vecB):          #计算两个向量的欧式距离
    	return sqrt(sum(power(vecA-vecB,2)))
    
    def randCent(dataSet,k):            #位给定数据集构建一个包含k个随机质心的集合
    	n = shape(dataSet)[1]   #shape函数此时返回的是dataSet元祖的列数
    	centroids = mat(zeros((k,n)))       #mat函数创建k行n列的矩阵,centroids存放簇中心
    	for j in range(n):
    		minJ = min(dataSet[:,j])           #第j列的最小值
    		rangeJ = float(max(dataSet[:,j]) - minJ)
    		centroids[:,j] = minJ + rangeJ * random.rand(k,1)  #random.rand(k,1)产生shape(k,1)的矩阵
    	return centroids
    
    def kMeans(dataSet,k,disMeas = distEclud,createCent = randCent):
    	m = shape(dataSet)[0] #shape函数此时返回的是dataSet元祖的行数
    	clusterAssment = mat(zeros((m,2)))      #创建一个m行2列的矩阵,第一列存放索引值,第二列存放误差,误差用来评价聚类效果
    	centroids = createCent(dataSet,k)  #创建k个质心,调用createCent()函数
    	clusterChanged =True #标志变量,若为true则继续迭代
    	print "质心位置更新过程变化:"
    	while clusterChanged:
    		clusterChanged = False
    		for i in range(m):
    			minDist = inf #inf为正无穷大
    			minIndex = -1  #创建索引
    			for j in range(k):
    				#寻找最近的质心
    				disJI = disMeas(centroids[j,:],dataSet[i,:]) #计算每个点到质心的欧氏距离
    				if disJI(array([0, 0, 1]), array([0, 2, 0]))
    				#print array(nonzero(b2))
    				#=>[[0, 0, 1],[0, 2, 0]]
    				centroids[cent,:] = mean(ptsInClust,axis=0)  #计算所有点的均值,选项axis=0表示沿矩阵的列方向进行均值计算
    	return centroids,clusterAssment  #返回所有的类质心与点分配结果
    	
    
    datMat = mat(loadDataSet('data.txt'))
    myCentroids,clustAssing = kMeans(datMat,2)
    print "最终质心:\n",myCentroids
    print "索引值和均值:\n",clustAssing
    (array([0, 0, 1]), array([0, 2, 0]))
    				#print array(nonzero(b2))
    				#=>[[0, 0, 1],[0, 2, 0]]
    				centroids[cent,:] = mean(ptsInClust,axis=0)  #计算所有点的均值,选项axis=0表示沿矩阵的列方向进行均值计算
    	return centroids,clusterAssment  #返回所有的类质心与点分配结果
    	
    
    datMat = mat(loadDataSet('data.txt'))
    myCentroids,clustAssing = kMeans(datMat,2)
    print "最终质心:\n",myCentroids
    print "索引值和均值:\n",clustAssing
    

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

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

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

    4)数据库比较大的时候,收敛会比较慢.

     

      K均值聚类中簇的值k是用户预先定义的一个参数,那么用户如何才能知道k的选择是否正确?如何才能知道生成的簇比较好?在计算的过程中保留了每个点的误差,即该点到簇质心的距离平方值,下面将讨论利用该误差来评价聚类质量好坏的方法,引入度量聚类效果的指标SSE(sum of squared Error,误差平方和),SSE值越小,越接近于他们的质心,聚类效果也越好,有一种可以肯定减小SSE值得方法是增加k的数目,但这个违背了聚类的目标,聚类的目标是在保持簇数目不变的情况下提高簇的质量。

    接下来要讨论的是利用簇划分技术得到更好的聚类效果——二分K-均值算法


    搜索与推荐Wiki

    扫一扫 关注微信公众号!号主 专注于搜索和推荐系统,尝试使用算法去更好的服务于用户,包括但不局限于机器学习,深度学习,强化学习,自然语言理解,知识图谱,还不定时分享技术,资料,思考等文章!


                                 【技术服务】,详情点击查看:https://mp.weixin.qq.com/s/PtX9ukKRBmazAWARprGIAg


    外包服务

    展开全文
  • 9.4 试编程实现k均值算法,设置三组不同的k值、三组不同初始中心点,在西瓜数据集4.0上进行试验比较,并讨论什么样的初始中心有利于取得好结果。 K-means算法:初始随机的中心点不同会导致算法的迭代次数与最终结果...

    9.4 试编程实现k均值算法,设置三组不同的k值、三组不同初始中心点,在西瓜数据集4.0上进行试验比较,并讨论什么样的初始中心有利于取得好结果。

    K-means算法:初始随机的中心点不同会导致算法的迭代次数与最终结果有很大的不同。一般来说,初始的中心点越集中且越靠近边缘,则会使得迭代次数更多。初始中心点越分散,迭代次数越少,结果越好。

    K=3的结果:


    代码可以在MATLAB中和Ocatve中执行:

    x = xlsread('E:\machine_learning\Machine-Learning-ZhouZhiHua\9.4\watermelon4.0.xlsx', 'Sheet1', 'A1:B30');
    [m,n]=size(x);    %m表示行、n表示列
    k=3;%设置k值,即要聚类的个数
    u=x(randperm(m,k),:);  %随机均值
    while 1
      c=zeros(k,30);    %将各类集合清空
      nums=zeros(k,1);  
      %对所有样本遍历,选择最近的集合
      for i=1:m
        mind=100000;   %存放最短的距离
        minl=0;        %x的族标记
        for j=1:k 
          d=norm(x(i,:)-u(j,:));   %计算样本x到各均值向量的距离
          if(d<mind)
          mind=d;
          minl=j;
          end
         end
         nums(minl)=nums(minl)+1;   %相应族的聚类个数
         c(minl,nums(minl))=i;      %
       end
       %计算两次均值差异,并更新均值
       up=zeros(k,2);
       for i=1:k
         for j=1:nums(i)
           up(i,:)=up(i,:)+x(c(i,j),:);
          end
          up(i,:)=up(i,:)/nums(i);
       end
       %迭代结束的条件
       delta_u=norm(up-u);
       if(delta_u<0.001)
          break;
        else
           u=up;
       end
    end
    
    %各类使用不同的符号绘制
    ch='o*+.>';
    
    for i=1:k
      %绘制类中的点
      plot(x(c(i,1:nums(i)),1),x(c(i,1:nums(i)),2),ch(i));
      hold on;
      tc=x(c(i,1:nums(i)),:);       %同族样本所有数据
      %计算类凸包并画线
      %chl=convhull(tc(:,1),tc(:,2));   %Octave中convhull(x,y)必须有两个参数
      %在Matlab中使用
      chl=convhull(tc);
      line(tc(chl,1),tc(chl,2))
      hold on;
    end
    
    xlabel('密度');
    ylabel('含糖率');
    title('K-means'); 

    源码和数据集下载地址:https://github.com/Microstrong0305/Machine-Learning-ZhouZhiHua

    接下来在测试一下

    k=2


    k=4



    展开全文
  • K-均值算法试图将一系列样本分割成K个不同的类簇(其中K是模型的输入参数),其形式化的目标函数称为类簇内的方差和(within cluster sum of squared errors,WCSS)。K-均值聚类的目的是最小化所有类簇中的方差之和...
  • 机器学习算法与Python实践之(六)二分k均值聚类

    万次阅读 多人点赞 2014-04-22 12:44:42
    机器学习算法与Python实践之(六)二分k均值聚类zouxy09@qq.comhttp://blog.csdn.net/zouxy09 机器学习算法与Python实践这个系列主要是参考《机器学习实战》这本书。因为自己想学习Python,然后也想对一些机器学习...
  • 根据之前博文中k-均值算法表述,编写代码,对k-均值算法有个清晰认识 问题:将图中数据分成3组。 下图是整个k-均值算法的流程  1,首先选择 K 个随机的点,称为聚类中心(cluster centroids);  2,对于...
  • 机器学习&数据挖掘笔记_16(常见面试之机器学习算法思想简单梳理) K-Means Clustering 斯坦福大学公开课 :机器学习课程 简介 K-均值是最普及的聚类算法算法接受一个未标记的数据集,然后将数据集聚类成不同的组...
  • 聚类算法之k均值算法+实例程序

    千次阅读 2018-07-22 15:48:05
    看完周志华老师的《机器学习》中关于聚类算法k均值算法的介绍,根据书上的介绍,自己用MATLAB编了程序,并与网上找的程序作了比较,比网上的运行更快一些。 数据采用《机器学习》书P202页的西瓜数据集,根据P203的...
  • 二分K均值算法 算法介绍: 二分K均值算法是一种层次聚类算法,使用自顶向下的逼近:所有的观察值开始是一个簇,递归地向下一个层级分裂。分裂依据为选择能最大程度降低聚类代价函数(也就是误差平方和)的簇划分为...
  • 支持向量机,逻辑回归,决策树等经典的机器学习算法主要用于分类问题,即根据一些已经给定的类别的样本,训练某种分类器,使得他能够对类别未知的样本进行分类。 与分类问题不同,聚类是事先并不知道任何样本标签的...
  • 机器学习算法与Python实践之(五)k均值聚类(k-means)zouxy09@qq.comhttp://blog.csdn.net/zouxy09 机器学习算法与Python实践这个系列主要是参考《机器学习实战》这本书。因为自己想学习Python,然后也想对一些...
  • K-均值算法简介

    千次阅读 2015-04-14 15:28:13
    本文名为K-均值算法简介,除包含算法内容以外,还包含了K-均值算法的来源、关于K-均值算法的不同视角,以及应用和优缺点方面的内容。
  • 机器学习(2): K-means (k均值) 聚类算法 小结

    千次阅读 多人点赞 2019-07-23 10:49:49
    2 k-means算法流程 3 利用k-means 对数据进行聚类 4利用K-means进行图像分割 5 小结 参考资料 1 聚类简介 在无监督学习中,训练样本的标记信息是未知的,我们的目标是通过对无标记训练样本的学习来解释数据的...
  • 聚类算法包括:K均值聚类(K-Means)、层次聚类(Hierarchical Clustering)和混合高斯模型(Gaussian Mixture Model)。K均值聚类(K-Means)算法的核心思想是:对于给定的样本集,按照样本之间的距离大小,将样本集划分为K...
  • ==================================================...《机器学习实战》系列博客是博主阅读《机器学习实战》这本书的笔记也包含一些其他python实现的机器学习算法 算法实现均采用python github 源码同步:https...
  • k 均值算法k-means)

    千次阅读 2020-03-04 08:14:59
    k-means 聚类算法,属于无监督学习算法。也就是说样本中却没有给定y,只有特征x。聚类的目的是找到每个样本x潜在的类别y,并将同类别y的样本x放在一起。k-means 算法实际上是一种最大期望算法(EM 算法)。 1. k-...
  • 机器学习k均值聚类

    2017-02-23 10:58:06
    k均值K-means)聚类算法是一种经典的非监督型机器学习算法算法简单快速。一. 算法步骤(1)首先确定聚类的个数K,初始化K个质心,可以随机定位,也可以和现有数据点重合(2)对剩余的每个数据测量其到每个质心的...
  • 一、引言聚类是一种无监督学习二、K均值聚类算法2.1 算法过程:随机确定K个初始点为质心(簇个数k由用户给定)然后将数据集中的每个点寻找距其最近的质心,分配到对应的簇中,完成后,每个簇的质心更新为该簇所有点的...
  • K均值K-Means)算法是一种无监督的聚类学习算法,他尝试找到样本数据的自然类别,分类是K由用户自己定义,K均值在不需要任何其他先验知识的情况下,依据算法的迭代规则,把样本划分为K类。K均值是最常用的聚类技术...
1 2 3 4 5 ... 20
收藏数 40,111
精华内容 16,044
关键字:

k均值算法 机器学习