Canopy聚类算法分析

Canopy聚类算法是可以并行运行的算法,数据并行意味着可以多线程进行,加快聚类速度,开源ML库Mahout使用。

一、概念

与传统的聚类算法(比如 K-means )不同,Canopy 聚类最大的特点是不需要事先指定 k 值( 即 clustering 的个数),因此具有很大的实际应用价值。与其他聚类算法相比,Canopy聚类虽然精度较低,但其在速度上有很大优势,因此可以使用 Canopy 聚类先对数据进行“粗”聚类,(摘自于Mahout一书:Canopy算法是一种快速地聚类技术,只需一次遍历数据科技得到结果,无法给出精确的簇结果,但能给出最优的簇数量。可为K均值算法优化超参数..K....)得到 k 值后再使用 K-means 进行进一步“细”聚类。这种Canopy + K-means的混合聚类方式分为以下两步:

Step1、聚类最耗费计算的地方是计算对象相似性的时候,Canopy 聚类在第一阶段选择简单、计算代价较低的方法计算对象相似性,将相似的对象放在一个子集中,这个子集被叫做Canopy ,通过一系列计算得到若干Canopy,Canopy 之间可以是重叠的,但不会存在某个对象不属于任何Canopy的情况,可以把这一阶段看做数据预处理;

Step2、在各个Canopy 内使用传统的聚类方法(如K-means),不属于同一Canopy 的对象之间不进行相似性计算。

从这个方法起码可以看出两点好处:首先,Canopy 不要太大且Canopy 之间重叠的不要太多的话会大大减少后续需要计算相似性的对象的个数;其次,类似于K-means这样的聚类方法是需要人为指出K的值的,通过Stage1得到的Canopy 个数完全可以作为这个K值,一定程度上减少了选择K的盲目性。

二、聚类精度

对传统聚类来说,例如K-means、Expectation-Maximization、Greedy Agglomerative Clustering,某个对象与Cluster的相似性是该点到Cluster中心的距离,那么聚类精度能够被很好保证的条件是:

对于每个Cluster都存在一个Canopy,它包含所有属于这个Cluster的元素。

如果这种相似性的度量为当前点与某个Cluster中离的最近的点的距离,那么聚类精度能够被很好保证的条件是:

对于每个Cluster都存在若干个Canopy,这些Canopy之间由Cluster中的元素连接(重叠的部分包含Cluster中的元素)。

数据集的Canopy划分完成后,类似于下图:

三、Canopy算法流程

(1)将数据集向量化得到一个list后放入内存,选择两个距离阈值:T1和T2,其中T1 > T2,对应上图,实线圈为T1,虚线圈为T2,T1和T2的值可以用交叉校验来确定;

(2)从list中任取一点P,用低计算成本方法快速计算点P与所有Canopy之间的距离(如果当前不存在Canopy,则把点P作为一个Canopy),如果点P与某个Canopy距离在T1以内,则将点P加入到这个Canopy;

(3)如果点P曾经与某个Canopy的距离在T2以内,则需要把点P从list中删除,这一步是认为点P此时与这个Canopy已经够近了,因此它不可以再做其它Canopy的中心了;

(4)重复步骤2、3,直到list为空结束。

注意:Canopy聚类不要求指定簇中心的个数,中心的个数仅仅依赖于举例度量,T1和T2的选择。

Python代码:

[python] view plaincopy

  1. #-*- coding:utf-8 -*-
  2. '''''
  3. '''
  4. import numpy as np
  5. import matplotlib as nlp
  6. #The first op
  7. import scipy as sp
  8. import scipy.sparse.linalg
  9. import time
  10. from Old_regression import crossValidation
  11. #使用K均值
  12. import kMeans as km
  13. def canopyClustering(datalist):
  14. state =[];
  15. #交叉验证获取T1和T2;
  16. T1,T2 = crossValidation(datalist);
  17. #canopy 预聚类
  18. canopybins= canopy(datalist, T1 , T2);
  19. #使用K均值聚类
  20. k =len(canopybins);
  21. createCent = [canopy[0] for canopy in canopybins];#获取canopybins中心
  22. dataSet = datalist;
  23. centroids, clusterAssment =km.kMeans(dataSet, k, distMeas=distEclud, createCent);
  24. return clusterAssment;
  25. #得到一个list后放入内存,选择两个距离阈值:T1和T2,其中T1 > T2
  26. #Canopy聚类不要求指定簇中心的个数,中心的个数仅仅依赖于举例度量,T1和T2的选择。
  27. def canopy(datalist, T1 , T2):
  28. #state = [];datalist = [];
  29. #初始化第一个canopy元素
  30. canopyInit = datalist.pop();
  31. canopyCenter= calCanopyCenter([canopyInit] );
  32. canopyC = [canopyInit];#建立第一个canopy
  33. canopybins = [];
  34. canopybins.append([canopyCenter,canopyC ] );
  35. while not(len(datalist) ==0 ):
  36. PointNow =datalist[len(datalist)-1 ];#PointNow =datalist.pop();
  37. counter = 0;
  38. for canopy in canopybins:
  39. dis =calDis(PointNow, canopy[0]);
  40. #如果点P与某个Canopy距离在T1以内,则将点P加入到这个Canopy;
  41. if dis<T1:
  42. canopy[1].append(PointNow);
  43. counter +=1;
  44. #break;
  45. if dis<T2:
  46. #点P曾经与某个Canopy的距离在T2以内,则需要把点P从list中删除,
  47. #这一步是认为点P此时与这个Canopy已经够近了,因此它不可以再做其它Canopy的中心了
  48. if not(counter ==0):#保证必须率属于一个canopy
  49. del list[len(datalist)-1 ];
  50. break;
  51. else:#建立一个新的Canopy
  52. canopyC = [PointNow];
  53. canopyCenter= PointNow;
  54. canopybins.append([canopyCenter,canopyC ] );
  55. return canopybins;
  56. def calDis(va,vb):
  57. dis =0;
  58. for i in range(len(va) ):
  59. dis += va[i]*va[i]+ vb[i]*vb[i];
  60. return dis;
  61. #计算canopy中心
  62. def calCanopyCenter(datalist):
  63. center =datalist[0];
  64. for i in len(range(center) ):
  65. center[i]=0;
  66. for data in datalist:
  67. center +=data;
  68. center /= len(center);
  69. return center;

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

原文发表时间:2015-07-26

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

教程 | 用数据做酷的事!手把手教你搭建问答系统

选自TowardsDataScience 作者:Priya Dwivedi 机器之心编译 参与:Pedro、路 本文介绍了如何基于 SQuAD 数据集搭建问答系...

29870
来自专栏AI科技大本营的专栏

从Word Embedding到Bert模型——自然语言处理预训练技术发展史

作者简介:张俊林,中国中文信息学会理事,目前在新浪微博 AI Lab 担任资深算法专家。在此之前,张俊林曾经在阿里巴巴任资深技术专家,以及在百度和用友担任技术经...

15820
来自专栏机器之心

专栏 | 阿里IJCAI 2017 Workshop论文:使用深度强化学习方法求解一类新型三维装箱问题

机器之心专栏 阿里菜鸟物流人工智能部 据机器之心了解,阿里巴巴有 11 篇论文入选如今正在墨尔本进行的 IJCAI 2017 大会,其中 6 篇来自阿里巴巴-浙...

1.1K60
来自专栏专知

CMU2018春季课程:神经网络自然语言处理课程(附PPT和代码)

【导读】我们之前介绍了一系列卡耐基梅隆大学的课程,今天,我们又带来了CMU 2018春季最新的课程“Neural Networks for NLP”介绍,该课程...

66080
来自专栏iOSDevLog

ML任务

11120
来自专栏机器之心

重磅 | Facebook提出全新CNN机器翻译:准确度超越谷歌而且还快九倍(已开源)

选自code.facebook 作者:Jonas Gehring、Michael Auli、David Grangier、Denis Yarats、Yann N...

38780
来自专栏机器学习算法与Python学习

GBDT入门教程之原理、所解决的问题、应用场景讲解

GBDT (Gradient Boosting Decision Tree) 又叫 MART (Multiple Additive Regression Tr...

50150
来自专栏大数据挖掘DT机器学习

GBDT迭代决策树入门教程

GBDT(Gradient Boosting Decision Tree) 又叫 MART(Multiple Additive Regression Tree)...

82750
来自专栏专知

用于神经网络机器翻译的全并行文本生成

在过去的几年里,神经网络为文本分类和问题回答等自然语言任务的准确性和质量带来了快速的提高。深度学习导致的令人印象深刻的结果的一个领域是需要机器生成自然语言文本的...

30850
来自专栏新智元

对抗神经机器翻译:GAN+NMT 模型,中国研究者显著提升机翻质量

【新智元导读】中山大学、中国科技大学、微软亚洲研究院与广东省信息安全技术重点实验室合作,提出了一种新的“对抗神经机器翻译”(Adversarial-NMT) 模...

674200

扫码关注云+社区

领取腾讯云代金券