k均值算法_k均值算法及其优缺点 - CSDN
精华内容
参与话题
  • k-均值算法及其实现

    2017-04-16 20:30:17
     K均值算法也称为C-均值算法,是根据函数准则进行分类的聚类算法,基于使聚类准则最小化。所使用的聚类准则 函数为模式集中每一个样本点到该类聚类中心的距离平方和。聚类中心的选择应使得距离平方和最小。  ...

    k-均值算法及其实现

    1.1 算法描述

         K均值算法也称为C-均值算法,是根据函数准则进行分类的聚类算法,基于使聚类准则最小化。所使用的聚类准则

    函数为模式集中每一个样本点到该类聚类中心的距离平方和。聚类中心的选择应使得距离平方和最小。

         假设共有N个模式样本,算法执行步骤如下:

          (1) 任选K个初始聚类中心Z1(1),Z2(1),...,Zk(1),K<N。括号中为第几次迭代。一般选择前K个样本作为初始聚类中心。

          (2) 使用欧几里得公式计算其余样本点到初始聚类中心的距离,基于欧几里得最小距离为其余样本分配聚类中

                    心,并将迭代次数加1。

                    

                    其中X为模式集,Sj为第j个聚类集,小写k为迭代次数,大写K为聚类中心个数,Dj(k)为到聚类中心的距 

                    离。

          (3) 计算各个聚类中心的新向量值作为新的聚类中心。

          (4) 如果,则继续步骤(2),否则,算法收敛,计算结束。

    1.2 算法实现

          算法实现效果如下图1所示。


    图1 50个点使用k-均值聚为两类的算法实现效果

    1.3 代码如下:

    本代码使用了OpenGL图形程序接口,需要使用glut库,具体使用方法请自行查找相关文档,此处不再介绍。
    /*
    k-均值算法,聚为两类
    */
    #define N1  50
    #define R 2.0f
    #define Pi 3.1415926f
    #include <stdio.h>
    #include <vector>
    #include <time.h>
    #include <GL/glut.h>
    
    //模式结构体
    struct Pattern
    {
    	float x1,x2;//x1,x2表示特征
    };
    //定义初始聚类中心A,B以及初始数据w1
    int p,q;
    Pattern w1[N1],w2[N1],w3[N1];
    void init()
    {
    	glClearColor(1.0f,1.0f,1.0f,1.0f);
    	glClear(GL_COLOR_BUFFER_BIT);
    }
    void display()
    {
    	//画点
    	glPointSize(10.0);
    	glBegin(GL_POINTS);
    	for(int i = 0;i < p; i++)
    	{
    		glColor3f(1.0,0.0,0.0);
    		glVertex2f(w2[i].x1,w2[i].x2);
    	}
    	glEnd();
    	glFlush();
    
    	for (int i = 0; i < q; i++)
    	{
    		glBegin(GL_LINE_LOOP);
    		for(int j = 0;j < q; j++)
    		{
    			glColor3f(0.0,0.0,1.0);
    			glVertex2f(w3[i].x1+R*cos(2*Pi/q*j),w3[i].x2+R*sin(2*Pi/q*j));
    		}
    		glEnd();
    		glFlush();
    	}
    }
    int main(int argc,char *argv[])
    {
    	Pattern A,B,C,D,E,F;//定义初始聚类中心A,B
    	Pattern distance[N1];
    	//产生随机数的种子
    	printf("这是K-均值算法的初始点数据\n");
    	srand((unsigned)time(NULL));
    	for (int i = 0; i < N1; i++)
    	{
    		w1[i].x1=rand()%100;
    		w1[i].x2=rand()%100;
    		//打印随机产生的点
    		printf("%.3f %.3f\n",w1[i].x1,w1[i].x2);
    	}
    	//执行k-均值算法更新,赋值初始聚类中心
    	A.x1=w1[0].x1;
    	A.x2=w1[0].x2;
    	B.x1=w1[1].x1;
    	B.x2=w1[1].x2;
    	int m,n;
    	E.x1=A.x1;E.x2=A.x2;
    	F.x1=B.x1;F.x2=B.x2;
    	int temp =0;
    	while(true)
    	{
    		temp++;
    		m=0;
    		n=0;
    		p=0;
    		q=0;
    		C.x1=0;
    		C.x2=0;
    		D.x1=0;
    		D.x2=0;
    		for(int j = 0;j < N1;j++)
    			//计算各样本距离聚类中心的距离
    		{
    			distance[j].x1=sqrt((w1[j].x1-E.x1)*(w1[j].x1-E.x1)+(w1[j].x2-E.x2)*(w1[j].x2-E.x2));
    			distance[j].x2=sqrt((w1[j].x1-F.x1)*(w1[j].x1-F.x1)+(w1[j].x2-F.x2)*(w1[j].x2-F.x2));
    			if(distance[j].x1<distance[j].x2)
    			{
    				m++;
    				w2[p].x1=w1[j].x1;
    				w2[p].x2=w1[j].x2;
    				C.x1+=w2[p].x1;
    				C.x2+=w2[p].x2;
    				p++;	
    				}
    				else
    				{
    					n++;
    					w3[q].x1=w1[j].x1;
    					w3[q].x2=w1[j].x2;
    					D.x1+=w3[q].x1;
    					D.x2+=w3[q].x2;
    					q++;
    				}
    		}
    		C.x1=(float)C.x1/m;
    		C.x2=(float)C.x2/m;
    		D.x1=(float)D.x1/n;
    		D.x2=(float)D.x2/n;
    		if(E.x1 != C.x1 || E.x2 != C.x2 || F.x1 != D.x1 || F.x2 != D.x2)
    		{
    			E.x1=C.x1;E.x2=C.x2;
    			F.x1=D.x1;F.x2=D.x2;
    		}
    		else
    		{
    			printf("第1类点的个数为:");
    			printf("%d\n",m);
    			printf("第2类点的个数为:");
    			printf("%d\n",n);
    			printf("最终的聚类中心为:\n");
    			printf("%f,%f\n",C.x1,C.x2);
    			printf("%f,%f\n",D.x1,D.x2);
    			break;
    		}
    	}
    	
    	glutInit(&argc,argv);//初始化glut
    	glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);//设置显示属性为RGB颜色,单缓冲
    	glutInitWindowSize(400,400);//设置窗口大小
    	glutInitWindowPosition(200,100);//设置窗口位置
    	glutCreateWindow("k-均值算法的设计");//生成窗口
    	init();
    	gluOrtho2D(-10,100,-10,100);
    	glutDisplayFunc(display);//显示回调
    	glutMainLoop();
    	system("pause");
    	return 0;
    }




    展开全文
  • K-均值算法简介

    千次阅读 2015-04-14 15:28:13
    本文名为K-均值算法简介,除包含算法内容以外,还包含了K-均值算法的来源、关于K-均值算法的不同视角,以及应用和优缺点方面的内容。

    前段时间把en.wikipedia.org里关于K-means clustering算法的条目翻译了一下,搬到了zh.wikipedia.org里的条目“K-平均算法”下。

    后来组内讨论的时候又重新整理了一下要用的内容,放到博客上来吧。
    因为打算写一篇K-均值算法下自学习距离度量(distance metric)的文章,还需要有K-均值算法的内容作为铺垫。

    本文名为K-均值算法简介,除包含算法内容以外,还包含了K-均值算法的来源、关于K-均值算法的不同视角,以及应用和优缺点方面的内容。

    一、算法描述

    已知观测集 这里写图片描述,其中每个观测都是一个这里写图片描述维实向量, 这里写图片描述-均值聚类要把这这里写图片描述个观测划分到这里写图片描述个集合中这里写图片描述,使得组内平方和(WCSS within-cluster sum of squares)最小。换句话说,它的目标是找到使得满足下式

    这里写图片描述

    其中这里写图片描述这里写图片描述中所有点的均值。
    注:这个问题本身是NP-难的,所以出现了K-均值这样的启发式算法来求解。

    1.1初始化
    通常使用的初始化方法有Forgy随机划分(Random Partition)方法:
    (1)Forgy方法随机地从数据集中选择 个观测点作为初始的均值点;
    (2)随机划分方法则随机地为每一观测指定所属聚类,然后运行“更新(Update)”步骤,计算随机分配的各聚类的图心,作为初始的均值点。

    特点:Forgy方法易于使得初始均值点散开,随机划分方法则把均值点都放到靠近数据集中心的地方。
    适用性:随机划分方法一般更适用于K-调和均值和模糊K-均值算法;Forgy方法更适用于期望-最大化(EM)算法和标准K-均值算法。

    K-均值是一个启发式算法,无法保证收敛到全局最优解,并且聚类的结果会依赖于初始的聚类。又因为算法的运行速度通常很快,所以一般都以不同的起始状态运行多次来得到更好的结果。

    1.2运行时
    已知初始的这里写图片描述个均值点这里写图片描述 ,算法的按照下面两个步骤交替进行:
    分配(Assignment)
    将每个观测分配到聚类中,使得组内平方和(WCSS)达到最小。

    这里写图片描述

    因为这一平方和就是平方后的欧氏距离,所以很把观测点分配到离它最近的均值点即可:
    这里写图片描述

    (数学上,这意味依照由这些均值点生成的Voronoi图来划分上述观测点)
    其中每个这里写图片描述都只被分配到一个确定的聚类这里写图片描述中(在理论上它可能被分配到2个或者更多的聚类中)。

    更新(Update)
    计算上步得到的聚类中,每一聚类观测点的图心,作为新的均值点。

    这里写图片描述

    因为算术平均是最小平方估计,所以这一步同样减小了目标函数组内平方和(WCSS)的值。

    这一算法将在对于观测的分配不再变化时收敛。由于交替进行的两个步骤都会减小目标函数WCSS的值,并且分配方案只有有限种,所以算法一定会收敛于某一(局部)最优解。
    注意:使用这一算法无法保证得到全局最优解。

    算法为把观测点分配到距离最近的聚类。
    目标函数是组内平方和(WCSS),而且按照“最小平方和”来分配观测,确实是等价于按照最小欧氏距离来分配观测的。
    如果使用不同的距离函数来代替(平方)欧氏距离,可能使得算法无法收敛。然而,使用不同的距离函数,也能得到K-均值聚类的其他变体,如球体K-均值算法和K-中心点算法。

    二、算法思想[1]

    算法的思想可以追溯到1957年,术语“K-均值”在1967年被首次使用。不过,标准算法其实是由Stuart Lloyd在1957年,作为一种脉冲编码调制技术提出的(但1982年才被AT&T实验室公开出版)。在1965年,E.W.Forgy发表了本质上相同的方法,所以这一算法有时被称为Lloyd-Forgy方法。

    下面是问题原型:

    脉冲编码调制就是把一个时间连续,取值连续的模拟信号变换成时间离散,取值离散的数字信号后在信道中传输。即对模拟信号先抽样,再对样值幅度量化,编码的过程。
    给定一些要处理的信号,那些量化之后的值应该与……
    It has long been realized that in pulse-code modulation(PCM), with a given ensemble of signals to handle, the quantum values should be spaced more closely in the voltage regions where the signal amplitude is more likely to fall.
    也就是说,这其实是一个聚类问题:对于整个电压轴,需要找出这里写图片描述个离散的电压值,使得信号围绕这这里写图片描述个电压值的分布成为这里写图片描述个聚类。(原始文献中的讨论就视这里写图片描述为预先设定的值)

    三、视角

    3.1 可视为期望-最大化算法的特例
    “分配”—即—“期望”
    “更新”—即—“最大化”
    可以看到,这一算法实际上是广义期望-最大化算法(GEM)的一个变体。

    3.2 可视为空间划分的Voronoi图
    链接到网页[3]。

    3.3 与其它统计机器学习方法的关系

    K-均值问题很容易就能一般化为高斯混合模型,另一个K-均值算法的推广则是K-SVD算法。后者把数据点视为“编码本向量”的稀疏线性组合,而K-均值对应于使用单编码本向量的特殊情形。

    此外,K-均值算法还与下列方法有一定联系

    (1)Mean Shift 聚类
    基本的Mean Shift聚类要维护一个与输入数据集规模大小相同的数据点集。初始时,这一集合就是输入集的副本。然后对于每一个点,用一定距离范围内的所有点的均值来迭代地替换它。与之对比,K-均值把这样的迭代更新限制在(通常比输入数据集小得多的)K个点上,而更新这些点时,则利用了输入集中与之相近的所有点的均值。
    还有一种与K-均值类似的Mean shift算法,即似然Mean shift,对于迭代变化的集合,用一定距离内在输入集中所有点的均值来更新集合里的点。

    (2)主成分分析(PCA)
    有研究表明,K-均值的放松形式解(由聚类指示向量表示),可由主成分分析中的主成分给出。
    且主成分分析中,主方向张成的子空间与聚类图心空间是等价的。不过,主成分分析是K-均值聚类的有效放松形式并不是一个新的结果,并且还有研究结果直接给出了关于“聚类图心子空间是由主成分方向张成的”这一论述的反例。

    (3)独立成分分析(ICA)
    在稀疏假设下以及输入数据经过白化处理后,K-均值得到的解就是独立成分分析的解。这一结果对于解释K-均值在特征学习方面的成功应用很有帮助。

    (4)双向过滤
    K-均值算法隐含地假设输入数据的顺序不影响结果。双向过滤与K-均值算法和Mean shift算法类似之处在于它同样维护着一个迭代更新的数据集(亦是被均值更新)。
    然而,双向过滤限制了均值的计算只包含了在输入数据中顺序相近的点,这使得双向过滤能够被应用在空间安排非常重要的图像去噪等问题中。

    四、应用与优缺点

    K-均值算法在向量量化、聚类分析、特征学习、计算机视觉等领域都有应用,也经常作为其他算法的预处理步骤使用。

    使K-均值算法效率高的两个关键特点同时也常被视为它最大的缺陷:
    (1)聚类数目k是一个输入参数。选择不恰当的k值可能会导致糟糕的聚类结果。这也是为什么要进行特征检查来决定数据集的聚类数目了。
    (2)收敛到局部最优解,可能导致与直觉相反的错误结果。

    K-均值算法的一个重要的局限性在于它的聚类模型:
    这一模型的基本思想在于:得到相互分离的球状聚类,在这些聚类中,均值点趋向收敛于聚类中心。 一般会希望得到的聚类大小大致相当,这样把每个观测都分配到离它最近的均值点对应的聚类就是正确的分配方案。

    五、其他[2]

    • K-均值算法的变体
    • 复杂度

    参考文献
    [1]STUART P. LLOYD.Least Squares Quantization in PCM[J].IEEE TRANSACTIONSON INFORMATION THEORY, 1982, IT-28(2):129-138.
    [2]维基百科.K-平均算法[EB/OL].2015[2015-4-8].http://zh.wikipedia.org/zh/K%E5%B9%B3%E5%9D%87%E7%AE%97%E6%B3%95.
    [3]VoronoiDiagram[EB/OL].[2015-4-8].
    http://www.csie.ntnu.edu.tw/~u91029/VoronoiDiagram.html.

    展开全文
  • k均值算法——python实现

    千次阅读 2018-07-05 14:55:43
    无监督学习中应用最多的就是聚类,其中k均值算法就是典型的聚类算法,下面是一段从文本中读取30数据,然后进行聚类的过程,包括输出读取的数据集、随机选择的K个初始均值向量、30行数据各自所属的类别以及最后的聚类...

    无监督学习中应用最多的就是聚类,其中k均值算法就是典型的聚类算法,下面是一段从文本中读取30数据,然后进行聚类的过程,包括输出读取的数据集、随机选择的K个初始均值向量、30行数据各自所属的类别以及最后的聚类中心,因为每次是随机选择K个初始均值向量,所以每次运行结果不一样的。

    如果各位需要全部引用的话,请标注来源,具体的数据集需要的话,可以找我要。
    import numpy as np
    import math
    # 读取文件
    def load_dataset(file_name):
        data_list = []
        fr=open(file_name,encoding='utf-8-sig')
        lines = fr.readlines()
        for line in lines:
            pas_line = line.strip().split("\t")
            flt_line = list(map(eval, pas_line))
            data_list.append(flt_line)
        return np.array(data_list)
    # 路径输入及函数调用后打印
    data_set = load_dataset(r"F:\test\1.txt")
    print(data_set)
    # 计算两个向量之间的欧氏距离
    def dist_eclud(vecA, vecB):
        vec_square = []
        for element in vecA - vecB:
            element = element ** 2
            vec_square.append(element)
        return sum(vec_square) ** 0.5
    
    # 构建k个随机质心
    def rand_cent(data_set, k):
        n = data_set.shape[1]
        # n = data_set.shape 这时n的值为(30,2)即第0轴有30行,第1轴两列。所以要按照上面形式的话,n值为2
        centroids = np.zeros((k, n))
        for j in range(n):
            # 找每一列的最小值,对于此数据集是0.243和0.042
            min_j = float(min(data_set[:,j]))
            # print(min_j)
            # 找到数据集每一维的最小和最大值。然后得到每一维(每一列)的取值范围。
            # 用0到1之间的随机数和取值范围相乘,再用最小值加上该乘积,就可以得到在每一维取值范围内的随机数。
            range_j = float(max(data_set[:,j])) - min_j
            # print(range_j)即0.531和0.447,np.random.rand(k, 1))生成3*1的数组
            centroids[:,j] = (min_j + range_j * np.random.rand(k, 1))[:,0]
            # print(np.random.rand(k, 1))
            # print( np.random.rand(k, 1)[:,0])
        print("随机选择的初始均值向量为:\n",centroids)
        return centroids
    
    def Kmeans(data_set, k):
        # m值为30
        m = data_set.shape[0]
        # 初始化为30*2的全为0的数组,注意里面是元组
        cluster_assment = np.zeros((m, 2))
        # 调用后找到了随机的初始均值向量
        centroids = rand_cent(data_set, k)
        cluster_changed = True
        while cluster_changed:
            cluster_changed = False
            # 从0到29的有序序列依次取出元素赋给i
            for i in range(m):
                min_dist = np.inf; min_index = -1
                # print(min_dist)
                # 初始均值向量就k个,即3个
                for j in range(k):
                    # 初始均值向量数组中取出每行两列元素与数据集中的所有行两列的元素计算距离
                    dist_ji = dist_eclud(centroids[j,:], data_set[i,:])
                    # 如果距离最小则标上当时的均值向量的行标记
                    if dist_ji < min_dist:
                        min_dist = dist_ji; min_index = j
                if cluster_assment[i,0] != min_index:
                    cluster_changed = True
                # 所属类以及欧氏距离平方
                cluster_assment[i,:] = min_index, min_dist**2
            # 计算新均值向量
            for cent in range(k):
                # 这是在求每次分别属于某个类别的数据,然后再以此为基础计算新的均值向量
                pts_inclust = data_set[np.nonzero(list(map(lambda x:x==cent, cluster_assment[:,0])))]
                # print(pts_inclust)
                # 按列求平均值,即新的均值向量
                centroids[cent,:] = np.mean(pts_inclust, axis=0)
        return centroids, cluster_assment
    # 首先初始化样本点的簇分配矩阵(cluster_assment),有30行2列,第一列为该样本点的簇分配索引,第二列为该样本点到该簇质心的欧氏距离。
    # 当任意一个点的簇分配发生变化时,迭代执行以下操作:遍历每个样本点,计算样本点i到各个质心的距离,找到最小距离,
    # 将该质心所在簇编号分配给该样本点。遍历完所有样本点后,重新计算每个簇的质心。直到所有样本点的簇分配都不再发生变化时迭代停止。
    # 最后返回质心和样本点的簇分配矩阵
    my_centroids, my_cluster = Kmeans(data_set, 3)
    print("30行数据各自所属类别为:\n",my_cluster[:,0])
    print("聚类中心为:\n",my_centroids)


    展开全文
  • k-means 算法缺点① 在 K-means 算法K 是事先给定的,这个 K 值的选定是非常难以估计的。很多时候,事先并不知道给定的数据集应该分成多少个类别才最合适。这也是 K-means 算法的一个不足。有...

    以下内容摘自百度百科。


    K-means算法是硬聚类算法,是典型的基于原型的目标函数聚类方法的代表,

    它是数据点到原型的某种距离作为优化的目标函数,

    利用函数求极值的方法得到迭代运算的调整规则。


    k-means 算法缺点
    ① 在 K-means 算法中 K 是事先给定的,这个 K 值的选定是非常难以估计的。很多时候,事先并不知道给定的数据集应该分成多少个类别才最合适。这也是 K-means 算法的一个不足。有的算法是通过类的自动合并和分裂,得到较为合理的类型数目 K,例如 ISODATA 算法。关于 K-means 算法中聚类数目K 值的确定在文献中,是根据方差分析理论,应用混合 F统计量来确定最佳分类数,并应用了模糊划分熵来验证最佳分类数的正确性。在文献中,使用了一种结合全协方差矩阵的 RPCL 算法,并逐步删除那些只包含少量训练数据的类。而文献中使用的是一种称为次胜者受罚的竞争学习规则,来自动决定类的适当数目。它的思想是:对每个输入而言,不仅竞争获胜单元的权值被修正以适应输入值,而且对次胜单元采用惩罚的方法使之远离输入值。
    ② 在 K-means 算法中,首先需要根据初始聚类中心来确定一个初始划分,然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响,一旦初始值选择的不好,可能无法得到有效的聚类结果,这也成为 K-means算法的一个主要问题。对于该问题的解决,许多算法采用遗传算法(GA),例如文献 中采用遗传算法(GA)进行初始化,以内部聚类准则作为评价指标。
    ③ 从 K-means 算法框架可以看出,该算法需要不断地进行样本分类调整,不断地计算调整后的新的聚类中心,因此当数据量非常大时,算法的时间开销是非常大的。所以需要对算法的时间复杂度进行分析、改进,提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑,通过一定的相似性准则来去掉聚类中心的侯选集。而在文献中,使用的 K-means 算法是对样本数据进行聚类,无论是初始点的选择还是一次迭代完成时对数据的调整,都是建立在随机选取的样本数据的基础之上,这样可以提高算法的收敛速度。


    K-means算法以欧式距离作为相似度测度,它是求对应某一初始聚类中心向量V最优分类,

    使得评价指标J最小。算法采用误差平方和准则函数作为聚类准则函数。


    n是待聚类的样本个数,

    c是类别数(猜,or根据经验,先验知识确定),

    u是聚类中心。


    先放一个我写的一个最简单的K-means算法。效果明显不是很好……

    %% K-means聚类
    % 作者:qcy
    
    % 【问题】 现在的问题是:sigma大的时候,反而可以分开,sigma小的时候,分类要分错!
    
    clear;
    close all;
    clc
    
    %% 产生N个样本,每个样本的特征2维(平面上的点)
    N = 1000;
    % randn('seed',1);
    m_pattern = [];
    sigma = 0.2;
    % 数据本身就是4类
    % 中心
    init_m1_center_x = 0;
    init_m1_center_y = 0;
    init_m2_center_x = 0;
    init_m2_center_y = 1;
    init_m3_center_x = 1;
    init_m3_center_y = 1;
    init_m4_center_x = 1;
    init_m4_center_y = 0;
    
    % 第1类
    for k = 1 : N/4
        m_pattern(k).category = 0; % 初始化为第0类,即还没有分类
        m_pattern(k).feature = [sigma * randn(1,1) + init_m1_center_x; ...
            sigma * randn(1,1) + init_m1_center_y];
    end
    
    % 第2类
    for k = N/4 +1 : N/2
        m_pattern(k).category = 0; % 初始化为第0类,即还没有分类
        m_pattern(k).feature = [sigma * randn(1,1) + init_m2_center_x; ...
            sigma * randn(1,1) + init_m2_center_y];
    end
    
    % 第3类
    for k = N/2 +1 : 3*N/4
        m_pattern(k).category = 0; % 初始化为第0类,即还没有分类
        m_pattern(k).feature = [sigma * randn(1,1) + init_m3_center_x; ...
            sigma * randn(1,1) + init_m3_center_y];
    end
    
    % 第4类
    for k = 3*N/4 +1 : N
        m_pattern(k).category = 0; % 初始化为第0类,即还没有分类
        m_pattern(k).feature = [sigma * randn(1,1) + init_m4_center_x; ...
            sigma * randn(1,1) + init_m4_center_y];
    end
    
    % rand('seed',1); % 伪随机打乱
    m_pattern = m_pattern(randperm(length(m_pattern)));
    
    % 画图
    x_row = zeros(N,1);
    x_col = zeros(N,1);
    for k = 1 : N
        x_row(k) = m_pattern(k).feature(1);
        x_col(k) = m_pattern(k).feature(2);
    end
    
    figure(1);
    scatter(x_row,x_col,10,'ko');
    axis([-0.5 1.5 -0.5 1.5]);
    axis square
    grid on;
    title('原始数据');
    
    % 保存数据
    save m_pattern.mat m_pattern
    
    %% K均值聚类
    
    for k = 1:N
        m_pattern(k).dist2center = inf;
    end
    
    % 先验知识:认为有4类
    MAX_CNETER_NUMBER = 4; 
    MAX_ITER_NUMBER = 1000; % 最大迭代次数
    
    % Begin.
    % 1. 随机挑4个样本,作为聚类中心
    % 在这里,就用前4个
    for k = 1:MAX_CNETER_NUMBER
        m_pattern(k).category = k;
        m_center(k).feature = m_pattern(k).feature;
        m_center(k).new_feature = inf(size(m_pattern(k).feature));
        m_center(k).patternNum = 0; % 这里先设为0,后面统计的时候再累加
        m_center(k).index = k;
    end
    
    n_iter = 1;
    my_eps = 1e-6; % 聚类中心的前后变化的距离,如果不超过my_eps,就算收敛
    isConverge = 0;
    center_offset_dist = 1; % 相邻两次迭代,聚类中心移动的距离之和
    
    % 循环条件:
    % (1). 当前迭代次数 < 最大允许的迭代次数
    % (2). 聚类中心还没有收敛
    
    while (n_iter < MAX_ITER_NUMBER) && (center_offset_dist > my_eps)
        
        % 每个聚类中心所拥有的样本数置为0
        for k = 1:MAX_CNETER_NUMBER
            m_center(k).patternNum = 0;
    
        end
    
        % 把每一个点分到距离最近的聚类中心
        for k = 1:N
            feature_temp = m_pattern(k).feature;
            % 与每一个聚类中心进行距离比较
            dist_min = inf;
            idx_dist_min = 0; % 离哪个聚类最近 --> 最小欧式距离判决
            for k_center = 1:MAX_CNETER_NUMBER
                dist = norm(feature_temp - m_center(k_center).feature);
                if dist_min > dist
                    dist_min = dist;
                    idx_dist_min = k_center;
                end
            end
            
            m_pattern(k).category = idx_dist_min; % 归类
            % 属于 idx_dist_min 这一类的样本总数 + 1
            m_center(idx_dist_min).patternNum = m_center(idx_dist_min).patternNum + 1;
        end
        
        % 计算新的聚类中心
        for k = 1:MAX_CNETER_NUMBER
            feature_temp_sum = [0;0];
            for k_pattern = 1:N
                m_pattern_temp = m_pattern(k_pattern);
                if m_pattern_temp.category == k
                    feature_temp_sum = feature_temp_sum + m_pattern_temp.feature;
                end
            end
            m_center(k).new_feature = feature_temp_sum / m_center(k).patternNum;
        end
        
        % 计算聚类中心改变了多少
        center_offset_dist = 0;
        for k = 1:MAX_CNETER_NUMBER
            center_offset_dist = center_offset_dist + ...
                norm(m_center(k).new_feature - m_center(k).feature);
        end
        
        for k = 1:MAX_CNETER_NUMBER  % 上一次的feature需要改一下
            m_center(k).feature = m_center(k).new_feature;
            
        end
          
        n_iter = n_iter + 1;
    end
    
    if n_iter == MAX_ITER_NUMBER
        fprintf('超过最大迭代次数\n');
    end
    
    
    %% 聚类后画图
    figure(2);hold on;
    grid on;
    axis([-0.5 1.5 -0.5 1.5]);
    axis square
    title('聚类后');
    
    % 分好类的模式
    m_modes_count = [1 1 1 1];
    for k = 1 : N
        m_pattern_temp = m_pattern(k);
        category = m_pattern_temp.category;
        feature = m_pattern_temp.feature;
        
        if category == 1
            x1_row(m_modes_count(category)) = m_pattern_temp.feature(1);
            x1_col(m_modes_count(category)) = m_pattern_temp.feature(2);
            m_modes_count(category) = m_modes_count(category) + 1;
        elseif category == 2
            x2_row(m_modes_count(category)) = m_pattern_temp.feature(1);
            x2_col(m_modes_count(category)) = m_pattern_temp.feature(2);
            m_modes_count(category) = m_modes_count(category) + 1;
        elseif category ==3
            x3_row(m_modes_count(category)) = m_pattern_temp.feature(1);
            x3_col(m_modes_count(category)) = m_pattern_temp.feature(2);
            m_modes_count(category) = m_modes_count(category) + 1;
        else
            x4_row(m_modes_count(category)) = m_pattern_temp.feature(1);
            x4_col(m_modes_count(category)) = m_pattern_temp.feature(2);
            m_modes_count(category) = m_modes_count(category) + 1;
        end
    end
    
    scatter(x1_row,x1_col,10,'ro');
    scatter(x2_row,x2_col,10,'go');
    scatter(x3_row,x3_col,10,'bo');
    scatter(x4_row,x4_col,10,'mo');
    


    我只算了一次,聚类中心的初值是用的最开始的几个点,有可能根本就不收敛了,也没有多次尝试去计算。



    方差小了,反而还出问题了!-_-!

    据说是因为初值没有取好…哎…………

    所以似乎应该要试很多个初值…


    Matlab有自带的kmeans函数,效果非常好…

    %% K-means聚类
    % 调用matlab自带的kmeans函数
    % qcy
    % 时间:2016年6月16日21:05:19
    
    clear;
    close all;
    clc
    
    %% 产生N个样本,每个样本的特征2维(平面上的点)
    N = 1000;
    % randn('seed',1);
    m_pattern = [];
    sigma = 0.2;
    % 数据本身就是4类
    % 中心
    init_m1_center_x = 0;
    init_m1_center_y = 0;
    init_m2_center_x = 0;
    init_m2_center_y = 1;
    init_m3_center_x = 1;
    init_m3_center_y = 1;
    init_m4_center_x = 1;
    init_m4_center_y = 0;
    
    % 第1类
    for k = 1 : N/4
        m_pattern(k).category = 0; % 初始化为第0类,即还没有分类
        m_pattern(k).feature = [sigma * randn(1,1) + init_m1_center_x; ...
            sigma * randn(1,1) + init_m1_center_y];
    end
    
    % 第2类
    for k = N/4 +1 : N/2
        m_pattern(k).category = 0; % 初始化为第0类,即还没有分类
        m_pattern(k).feature = [sigma * randn(1,1) + init_m2_center_x; ...
            sigma * randn(1,1) + init_m2_center_y];
    end
    
    % 第3类
    for k = N/2 +1 : 3*N/4
        m_pattern(k).category = 0; % 初始化为第0类,即还没有分类
        m_pattern(k).feature = [sigma * randn(1,1) + init_m3_center_x; ...
            sigma * randn(1,1) + init_m3_center_y];
    end
    
    % 第4类
    for k = 3*N/4 +1 : N
        m_pattern(k).category = 0; % 初始化为第0类,即还没有分类
        m_pattern(k).feature = [sigma * randn(1,1) + init_m4_center_x; ...
            sigma * randn(1,1) + init_m4_center_y];
    end
    
    % rand('seed',1); % 伪随机打乱
    m_pattern = m_pattern(randperm(length(m_pattern)));
    
    % 画图
    x_row = zeros(N,1);
    x_col = zeros(N,1);
    for k = 1 : N
        x_row(k) = m_pattern(k).feature(1);
        x_col(k) = m_pattern(k).feature(2);
    end
    
    figure(1);
    scatter(x_row,x_col,10,'ko');
    axis([-0.5 1.5 -0.5 1.5]);
    axis square
    grid on;
    title('原始数据');
    
    % 保存数据
    save m_pattern.mat m_pattern
    
    %% K均值聚类
    
    MAX_CNETER_NUMBER = 4;  
    opts = statset('Display','final');
    for k = 1:N
        X(k,:) = m_pattern(k).feature;
    end
    [idx,Center] = kmeans(X,MAX_CNETER_NUMBER,'Distance','cityblock',...
        'Replicates',5,'Options',opts);
    
    figure;
    plot(X(idx==1,1),X(idx==1,2),'r.','MarkerSize',12)
    hold on;grid on;
    plot(X(idx==2,1),X(idx==2,2),'b.','MarkerSize',12)
    plot(X(idx==3,1),X(idx==3,2),'g.','MarkerSize',12)
    plot(X(idx==4,1),X(idx==4,2),'m.','MarkerSize',12)
    plot(Center(:,1),Center(:,2),'kx',...
         'MarkerSize',15,'LineWidth',3)
    legend('Cluster 1','Cluster 2','Cluster 3','Cluster 4','Centroids',...
           'Location','NW')
    title 'Cluster Assignments and Centroids'
    hold off
    axis([-0.5 1.5 -0.5 1.5]);
    axis square
    

    Matlab自带的kmeans,运行速度极快,估计用了并行?或者直接用C写的也有非常有可能…


    另外,网上还有一段,写得很好很好很好!

    1. 用空间换了时间;(e.g. 最小距离判别的时候,直接把一个点repmat,和四个中心相减…不像我还用了个for去一个一个比……别人一次性比完了!)

    2. 用空间换了简单的思维;

    3. 一开始多次随机地选择聚类中心,外层有个大循环,并把每次循环找出来的4个聚类中心都保存起来,最后去评价“哪个最好”;

    4. 评价哪次循环找到的几个聚类中心最好,依据的是

    a. 聚类后的每一类的所有样本点到该类的聚类中心的距离之和;

    b. 把每一类算出来的距离之和再加起来,求个总误差

    找到总误差最小的那次循环所找到的聚类中心,就是这N次大循环中,效果最好的一次聚类中心……

    主函数。

    clear;
    close all;
    clc
    
    
    %% 产生N个样本,每个样本的特征2维(平面上的点)
    N = 1000;
    % randn('seed',1);
    m_pattern = [];
    sigma = 0.1;
    % 数据本身就是4类
    % 中心
    init_m1_center_x = 0;
    init_m1_center_y = 0;
    init_m2_center_x = 0;
    init_m2_center_y = 1;
    init_m3_center_x = 1;
    init_m3_center_y = 1;
    init_m4_center_x = 1;
    init_m4_center_y = 0;
    
    % 第1类
    for k = 1 : N/4
        m_pattern(k).category = 0; % 初始化为第0类,即还没有分类
        m_pattern(k).feature = [sigma * randn(1,1) + init_m1_center_x; ...
            sigma * randn(1,1) + init_m1_center_y];
    end
    
    % 第2类
    for k = N/4 +1 : N/2
        m_pattern(k).category = 0; % 初始化为第0类,即还没有分类
        m_pattern(k).feature = [sigma * randn(1,1) + init_m2_center_x; ...
            sigma * randn(1,1) + init_m2_center_y];
    end
    
    % 第3类
    for k = N/2 +1 : 3*N/4
        m_pattern(k).category = 0; % 初始化为第0类,即还没有分类
        m_pattern(k).feature = [sigma * randn(1,1) + init_m3_center_x; ...
            sigma * randn(1,1) + init_m3_center_y];
    end
    
    % 第4类
    for k = 3*N/4 +1 : N
        m_pattern(k).category = 0; % 初始化为第0类,即还没有分类
        m_pattern(k).feature = [sigma * randn(1,1) + init_m4_center_x; ...
            sigma * randn(1,1) + init_m4_center_y];
    end
    
    % rand('seed',1); % 伪随机打乱
    m_pattern = m_pattern(randperm(length(m_pattern)));
    
    % 画图
    x_row = zeros(N,1);
    x_col = zeros(N,1);
    for k = 1 : N
        x_row(k) = m_pattern(k).feature(1);
        x_col(k) = m_pattern(k).feature(2);
    end
    
    figure(1);
    scatter(x_row,x_col,10,'ko');
    axis([-0.5 1.5 -0.5 1.5]);
    axis square
    grid on;
    title('原始数据');
    
    % 保存数据
    save m_pattern.mat m_pattern
    
    %% K均值聚类
    
    MAX_CNETER_NUMBER = 4;  
    opts = statset('Display','final');
    for k = 1:N
        X(:,k) = m_pattern(k).feature;
    end
     [best_Label best_Center best_ind label] = KM(X,MAX_CNETER_NUMBER,'KMeans');
    
     for k = 1:N
         m_pattern(k).category = best_Label(k);
     end
     
     
    %% 聚类后画图
    figure(2);hold on;
    grid on;
    axis([-0.5 1.5 -0.5 1.5]);
    axis square
    title('聚类后');
    
    % 分好类的模式
    m_modes_count = [1 1 1 1];
    for k = 1 : N
        m_pattern_temp = m_pattern(k);
        category = m_pattern_temp.category;
        feature = m_pattern_temp.feature;
        
        if category == 1
            x1_row(m_modes_count(category)) = m_pattern_temp.feature(1);
            x1_col(m_modes_count(category)) = m_pattern_temp.feature(2);
            m_modes_count(category) = m_modes_count(category) + 1;
        elseif category == 2
            x2_row(m_modes_count(category)) = m_pattern_temp.feature(1);
            x2_col(m_modes_count(category)) = m_pattern_temp.feature(2);
            m_modes_count(category) = m_modes_count(category) + 1;
        elseif category ==3
            x3_row(m_modes_count(category)) = m_pattern_temp.feature(1);
            x3_col(m_modes_count(category)) = m_pattern_temp.feature(2);
            m_modes_count(category) = m_modes_count(category) + 1;
        else
            x4_row(m_modes_count(category)) = m_pattern_temp.feature(1);
            x4_col(m_modes_count(category)) = m_pattern_temp.feature(2);
            m_modes_count(category) = m_modes_count(category) + 1;
        end
    end
    
    scatter(x1_row,x1_col,10,'ro');
    scatter(x2_row,x2_col,10,'go');
    scatter(x3_row,x3_col,10,'bo');
    scatter(x4_row,x4_col,10,'mo');
    
    KM函数。

    function [best_Label best_Center best_ind label] = KM(P,K,method)
    %%%%-----------------------------------------------------------------------
    %   Version 1.0 
    %   Author: feitengli@foxmail.com   from DUT
    %   CreateTime: 2012-11-29
    %%%------------------------------------------------------------------------
    %KM   K-Means Clustering or K-Medoids Clustering
    %    P is an d-by-N data matrix 
    %    K is the clustering number
    %    method = KMeans    :K-Means Clustering
    %           = KMedoids  :K-Medoids Clustering
    %References:
    %        1.The Elements of Statistical Learning 2nd Chapter14.3.6&&14.3.10
    %%%%-----------------------------------------------------------------------
    
    [d N] = size(P); 
    %% 本算法要求数据矩阵P的每列代表一个数据点,如果不是 需要转置矩阵
    if d > N
        ButtonName = questdlg('数据维数小于点的个数,是否转置矩阵',...
                              'MATLAB quest','Yes','No','Yes');
        if  strcmp(ButtonName, 'Yes')
            P = P';
            [d N] = size(P); 
    %     else
    %         return
        end
    end
        
    %% 选取初始点 方法2 
    max_Initial = max(20,N/(5*K));
    label = zeros(max_Initial,N);
    center = zeros(d,K,max_Initial);
    C = zeros(1,N);
    %% 主循环
    for initial_Case = 1:max_Initial
        
        pointK = Initial_center(P,K);    
        iter = 0;
    %     max_iter = 1;
        max_iter = 1e+3;
        % xK = pointK;
        disp(['------------KM进行第 ' num2str(initial_Case) ' 次重新选择初始中心-----------'])
        %% 每次初始化K个中心点后,进行的循环
        while iter < max_iter
            iter = iter+1;
            if mod(iter,50)==0
                disp(['  内部循环进行第 ' num2str(iter) ' 次迭代'])
            end
            %%%根据数据矩阵P中每个点到中心点的距离(最小)确定所属分类
            for i = 1:N
                dert = repmat(P(:,i),1,K)-pointK;
                distK = sqrt(diag(dert'*dert));
                [~,j] = min(distK);
                C(i) = j;
            end
            %%%重新计算K个中心点  
            xK_ = zeros(d,K);
            for i = 1:K
                Pi = P(:,find(C==i));
                Nk = size(Pi,2);
                % K-Means K-Medoids唯一不同的地方:选择中心点的方式
                switch lower(method)
                    case 'kmeans'  
                        xK_(:,i) = sum(Pi,2)/Nk;
                    case 'kmedoids'
                        Dx2 = zeros(1,Nk);
                        for t=1:Nk
                           dx = Pi - Pi(:,t)*ones(1,Nk);
                           Dx2(t) = sum(sqrt(sum(dx.*dx,1)),2);
                        end
                        [~,min_ind] = min(Dx2);
                        xK_(:,i) = Pi(:,min_ind);
                    otherwise
                        errordlg('请输入正确的方法:kmeans-OR-kmedoids','MATLAB error');
                end
            end
            
            % 判断是否达到结束条件
            if xK_==pointK   % & iter>50  %【qcy批注】 我认为,当二者之差小于某个Eps时,认为收敛
                disp(['###迭代 ' num2str(iter) ' 次得到收敛的解'])
                label(initial_Case,:) = C;
                center(:,:,initial_Case) = xK_;
              % plot_Graph(C);
                break
            end
            
            pointK = xK_;
            %xK = xK_;
        end
        if iter == max_iter
             disp('###达到内部最大迭代次数1000,未得到收敛的解') 
             label(initial_Case,:) = C;
             center(:,:,initial_Case) = xK_;
            % plot_Graph(C);
             % break
        end
        
    end
    
    %%%%增加对聚类结果最优性的比较  
    %距离差
     dist_N = zeros(max_Initial,K);
     for initial_Case=1:max_Initial     
         for k=1:K
             tem = find(label(initial_Case,:)==k);
             dx = P(:,tem)-center(:,k,initial_Case)*ones(1,size(tem,2));
             dxk = sqrt(sum(dx.*dx,1));
             dist_N(initial_Case,k) = sum(dxk);       
             % dist_N(initial_Case,k) = dxk;   
         end     
     end
     
     %%%%对于max_Initial次初始化中心点得到的分类错误
     %%%%取错误最小的情况的Label作为最终分类
     dist_N_sum = sum(dist_N,2); %求K类总的误差
     [~,best_ind] = min(dist_N_sum);
     best_Label = label(best_ind,:); 
     best_Center = center(:,:,best_ind);
    
    Initial_center初始化聚类中心的函数

    function center = Initial_center(X,K)  
            N = size(X,2);
            rnd_Idx = randperm(N);  
            center = X(:,rnd_Idx(1:K));  
    end   

    效果非常爽啊……


    【补充一些东西】

    1. K-means聚类,除了一开始要指定多少类,其他的“几乎都是盲的”,所谓的非监督嘛……

    2. 实验室的卢老板,用K-means解决了方型QAM调制时,星座点歪了,怎么判决的问题,还发表了一篇PJ的文章。祝贺祝贺。

    求卢老板以后带飞。

    展开全文
  • 机器学习(九):k-均值k-means)

    万次阅读 2020-09-03 16:37:34
        k均值(k-means)是一种聚类算法,其工作流程如下:随机选择k个点作为初始质心(质心即簇中所有点的中心),然后将数据集中的每个点分配到一个簇中,具体来讲,为每个点找距其最近的质心,并将其分配给该...
  • K均值聚类的理解和实现

    万次阅读 2018-10-27 15:39:15
    2. K均值的基本理论 2.1 K均值的原理和实现 2.2 K均值的缺点 2.3 K均值改进 3. 算法实现 3.1 获取样本 3.2 协方差逆阵方根的计算方法 3.3 聚类实验 3.3.1 一般的K均值聚类 3.3.2 基于马氏距离...
  • KMeans 算法(一)

    万次阅读 多人点赞 2019-03-11 23:06:32
    K-means算法,也称为K-平均或者K-均值,一般作为掌握聚类算法的第一个算法。 这里的K为常数,需事先设定,通俗地说该算法是将没有标注的 M 个样本通过迭代的方式聚集成K个簇。 在对样本进行聚集的过程往往是以样本...
  • 聚类k-means算法详解

    万次阅读 2020-06-15 11:03:54
    前言 俗话说:“物以类聚,人以群分”,在自然科学和社会科学中,存在着大量的分类问题。所谓类,通俗地说,就是指相似元素的集合。 而对于分类问题,我们通常不会提供x与y这样的映射关系,对于这种用机器自动找出...
  • K均值算法

    2018-10-18 09:55:32
    K均值算法,即K-means,主要分为两步: 确定簇标记 移动簇中心 输入:K(簇的个数),训练集{x1,x2,…xm} 首先,初始化K个簇中心点 μ1,μ2,…μK; Repeat{ 确定各样本点簇标记 for i=1 to m xi的簇标记:= 与xi...
  • Kmeans算法详解及MATLAB实现

    万次阅读 多人点赞 2016-04-26 21:39:37
    首先要来了解的一个概念就是聚类,简单地说就是把相似的东西分到一组,同 Classification (分类)不同,对于一个 classifier ,通常需要你告诉它“这个东西被分为某某类”这样一些例子,理想情况下,一个 classifier ...
  • k-means聚类算法原理与参数调优详解

    万次阅读 2019-05-16 08:31:07
    k-means算法原理 K-means中心思想:事先确定常数K,常数K意味着最终的聚类类别数,首先随机选定初始点为质心,并通过计算每一个样本与质心之间的相似度(这里为欧式距离),将样本点归到最相似的类中,接着,重新计算...
  • 我的K均值算法的matlab实现

    万次阅读 多人点赞 2020-10-01 01:36:51
    这是我的第一篇博客; K-Means算法过程,略; 这是一次课程的任务2333,...我的K均值算法以iris.data为例(附在文末); 数据集:Iris数据集 (http://archive.ics.uci.edu/ml/datasets/Iris) 数据描述:Iris数...
  • k-means算法优缺点

    千次阅读 2018-04-10 20:37:20
    K-Means的主要优点: 1)原理简单,容易实现 2)可解释度较强 K-Means的主要缺点: 1)K值的选取困难 2)局部最优 3)对噪音和异常点敏感 4)需样本存在均值(限定数据种类) 5)聚类效果依赖于聚类中心的初始化 6...
  • k均值聚类 支持向量机,逻辑回归,决策树等经典的机器学习算法主要用于分类问题,即根据一些已经给定的类别的样本,训练某种分类器,使得他能够对类别未知的样本进行分类。 与分类问题不同,聚类是事先并不知道...
  • 均值漂移(Meanshift)算法

    万次阅读 2017-03-18 14:26:55
    均值漂移(Meanshift) 1.均值漂移的基本概念:沿着密度上升方向寻找聚簇点 设想在一个有N个样本点的特征空间 初始确定一个中心点center,计算在设置的半径为D的圆形空间内所有的点(xi)与中心点center的向量 计算...
  • K-means(K-均值)聚类算法

    千次阅读 2017-08-31 10:35:01
    划分方法聚类分析最简单、最基本的版本是划分,它把对象组织成多个互斥的簇。这一方法,要求每个对象...大部分的划分算法都是基于距离的。(这个应该也很好理解吧,我们在前面应该提到过不止一次,这里说的距离实际上是
  • k-均值聚类简介

    千次阅读 2018-02-07 09:47:38
    k-均值聚类简介
  • k-means聚类算法过程与原理

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

    万次阅读 多人点赞 2017-09-23 09:25:51
    K-means算法是最简单的一种聚类算法算法的目的是使各个样本与所在类均值的误差平方和达到最小(这也是评价K-means算法最后聚类效果的评价标准)
  • 机器学习中的K-means算法原理与R语言实例

    万次阅读 多人点赞 2020-02-23 11:53:14
    聚类是将相似对象归到同一个簇中的方法,这有点像全自动分类。簇内的对象越相似,聚类的效果越好。支持向量机、神经网络所讨论的分类问题都是有监督的学习方式,...其中,K均值(K-means)是最基本、最简单的聚类算法
1 2 3 4 5 ... 20
收藏数 50,768
精华内容 20,307
关键字:

k均值算法