Python数据分析笔记:聚类算法之K均值

我们之前接触的所有机器学习算法都有一个共同特点,那就是分类器会接受2个向量:一个是训练样本的特征向量X,一个是样本实际所属的类型向量Y。由于训练数据必须指定其真实分类结果,因此这种机器学习统称为有监督学习

然而有时候,我们只有训练样本的特征,而对其类型一无所知。这种情况,我们只能让算法尝试在训练数据中寻找其内部的结构,试图将其类别挖掘出来。这种方式叫做无监督学习。由于这种方式通常是将样本中相似的样本聚集在一起,所以又叫聚类算法

下面我们介绍一个最常用的聚类算法:K均值聚类算法(K-Means)。

1、K均值聚类

K-Means算法思想简单,效果却很好,是最有名的聚类算法。聚类算法的步骤如下:

1:初始化K个样本作为初始聚类中心;

2:计算每个样本点到K个中心的距离,选择最近的中心作为其分类,直到所有样本点分类完毕;

3:分别计算K个类中所有样本的质心,作为新的中心点,完成一轮迭代。

通常的迭代结束条件为新的质心与之前的质心偏移值小于一个给定阈值。

下面给一个简单的例子来加深理解。如下图有4个样本点,坐标分别为A(-1,-1),B(1,-1),C(-1,1),D(1,1)。现在要将他们聚成2类,指定A、B作为初始聚类中心(聚类中心A0, B0),指定阈值0.1。K-Means迭代过程如下:

step 1.1:计算各样本距离聚类中心的距离:

样本A:d(A,A0) = 0; d(A,B0) = 2;因此样本A属于A0所在类;

样本B:d(B,A0) = 2; d(B,B0) = 0;因此样本B属于B0所在类;

样本C:d(C,A0) = 2; d(C,B0) = 2.8;;因此样本C属于A0所在类;

样本C:d(D,A0) = 2.8; d(D,B0) = 2;;因此样本C属于B0所在类;

step 1.2:全部样本分类完毕,现在计算A0类(包含样本AC)和B0类(包含样本BD)的新的聚类中心:

A1 = (-1, 0); B1 = (1,0);

step 1.3:计算聚类中心的偏移值是否满足终止条件:

|A1-A0| = |(-1,0)-(-1,-1) | = |(0,1)| = 1 >0.1,因此继续迭代。

此时的状态如下图所示:

step 2.1:计算各样本距离聚类中心的距离:

样本A:d(A,A1) = 1; d(A,B1) = 2.2;因此样本A属于A1所在类;

样本B:d(B,A1) = 2.2; d(B,B1) = 1;因此样本B属于B1所在类;

样本C:d(C,A1) = 1; d(C,B1) = 2.2;;因此样本C属于A1所在类;

样本D:d(D,A1) = 2.2; d(D,B1) = 1;;因此样本C属于B1所在类;

step 2.2:全部样本分类完毕,现在计算A1类(包含样本AC)和B1类(包含样本BD)的新的聚类中心:

A2 = (-1, 0); B2 = (1,0);

step 2.3:计算聚类中心的偏移值是否满足终止条件:

|A2-A1| = |B2-B1| = 0 <0.1,因此迭代终止。

2、测试数据

下面这个测试数据有点类似SNS中的好友关系,假设是10个来自2个不同的圈子的同学的SNS聊天记录。显然,同一个圈子内的同学会有更密切的关系和互动。

数据如下所示,每一行代表一个好友关系。如第一行表示同学0与同学1的亲密程度为9(越高表示联系越密切)。

显然,这个数据中并没有告知我们这10个同学分别属于哪个圈子。因此我们的目标是使用K-Means聚类算法,将他们聚成2类。

[plain] view plaincopy

  1. 0 1 9
  2. 0 2 5
  3. 0 3 6
  4. 0 4 3
  5. 1 2 8
  6. ......

这个例子设计的很简单。我们使用上一篇文章中提到的关系矩阵,将其可视化出来,会看到如下结果:

这是个上三角矩阵,因为这个数据中认为好友关系是对称的。上图其实很快能发现,0,1,2,3,4用户紧密联系在一起,而5,6,7,8,9组成了另外一个圈子。

下面我们看看K-Means算法能否找出这个答案。

3、代码与分析

K-Means算法的Python代码如下:

[python] view plaincopy

  1. # -*- coding: utf-8 -*-
  2. from matplotlib import pyplot
  3. import scipy as sp
  4. import numpy as np
  5. from sklearn import svm
  6. import matplotlib.pyplot as plt
  7. from sklearn.cluster import KMeans
  8. from scipy import sparse
  9. #数据读入
  10. data = np.loadtxt('2.txt')
  11. x_p = data[:, :2] # 取前2列
  12. y_p = data[:, 2] # 取前2列
  13. x = (sparse.csc_matrix((data[:,2], x_p.T)).astype(float))[:, :].todense()
  14. nUser = x.shape[0]
  15. #可视化矩阵
  16. pyplot.imshow(x, interpolation='nearest')
  17. pyplot.xlabel('用户')
  18. pyplot.ylabel('用户')
  19. pyplot.xticks(range(nUser))
  20. pyplot.yticks(range(nUser))
  21. pyplot.show()
  22. #使用默认的K-Means算法
  23. num_clusters = 2
  24. clf = KMeans(n_clusters=num_clusters, n_init=1, verbose=1)
  25. clf.fit(x)
  26. print(clf.labels_)
  27. #指定用户0与用户5作为初始化聚类中心
  28. init = np.vstack([ x[0], x[5] ])
  29. clf = KMeans(n_clusters=2, init=init)
  30. clf.fit(x)
  31. print(clf.labels_)

输出结果如下:

Initialization complete Iteration 0, inertia 581.000 Iteration 1, inertia 417.643 Converged at iteration 1 [0 0 1 1 1 1 1 1 1]

[0 0 0 0 1 1 1 1 1]

可以看到,使用默认的K-Means算法将使用随机的初始值,因此每次执行的结果都不一样。

上面的输出中将0,1用户聚类到一起,效果并不理想。然而,如果我们可以确定用户0与用户5是有很大区别的,就可以指定用户0和用户5作为K-Means聚类算法的初始值。可以看到和我们的预期完全一致,这样效果就非常好了。

由于K-Means毕竟是无监督学习,在很多情况下自然无法与有监督学习的算法进行同样标准的比较。但其不需要监督的特性,广泛应用与社交图谱(如本例)、相似性匹配(如搜索相似的新闻、帖子)等引用场景。

原文发布于微信公众号 - 大数据挖掘DT数据分析(datadw)

原文发表时间:2015-11-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法channel

深度学习|卷积神经网络(CNN)介绍(前篇)

01 — 回顾 以上推送了神经网络相关的介绍性内容和相关的基础理论,包括: 神经网络的基本结构:输入层,隐含层,输出层; 批随机梯度下降算法(mini-batc...

4189
来自专栏量化投资与机器学习

Matlab编程之——卷积神经网络CNN代码解析

这这是之前我共享的一个深度学习工具包,这是解释代码的一部分,具体的一些细节还还望大家根据自己的能力去做,慢慢去理解。不急昂! 源代码我公布出来希望大家学习交流,...

25010
来自专栏大数据文摘

辨别真假数据科学家必备手册:深度学习45个基础问题(附答案)

2428
来自专栏机器之心

教程 | 无需反向传播的深度学习:DeepMind的合成梯度

选自GitHub 作者:iamtrask 机器之心编译 参与:王宇欣、Ellen Han 在这篇博文中,我们将从起点(从零开始)学习 DeepMind 最近提...

28310
来自专栏ATYUN订阅号

【行业】2018年你应该知道的十大机器学习算法

本文简要介绍一些最常用的机器学习算法,没有代码,没有抽象理论,只有图片和一些如何使用它们的例子。

984
来自专栏计算机视觉life

OpenCV学习入门(三):kmeans原理及代码

Kmeans是一种非监督的聚类方法,是最常用的聚类技术之一。kmeans尝试找到数据的自然类别,通过用户设定的类别个数K,它可以快速的找到“好的”类别中心,“好...

1725
来自专栏https://www.cnblogs.com/L

【神经网络篇】--基于数据集cifa10的经典模型实例

最终,在cifar-10数据集上,通过一个短时间小迭代的训练,可以达到大致73%的准确率,持续增加max_steps,可以期望准确率逐渐增加 如果max_ste...

511
来自专栏技术小站

吴恩达深度学习笔记2.1 二分分类

 binary:二进制  discret:离散的,不连续的   vector:向量    matrice:矩阵   pixel:像素 intensity:强度 ...

561
来自专栏深度学习

循环神经网络

循环神经网络的神经网络体系结构,它针对的不是自然语言数据,而是处理连续的时间数据,如股票市场价格。在本文结束之时,你将能够对时间序列数据中的模式进行建模,以对未...

3708
来自专栏YoungGy

风格转换简介

风格转换 优化问题 综述 损失函数 训练 例子 代码 网络转换 结构 训练 参考 风格转换,是把一张图片转化成同内容但包含某风格的新图片。本文将介绍如何让机器学...

2745

扫描关注云+社区