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 条评论
登录 后参与评论

相关文章

来自专栏深度学习自然语言处理

详解机器学习之感知机理论与实践

阅读大概需要5分钟 上期回顾 详解机器学习之the Learning Problem 导读 本章讲的是让他机器学习说yes/no,目录分为: 感知机假设集合 ...

34412
来自专栏IT派

机器学习实战之Python3实现决策树算法

导语:今天这篇文章也是我们的志愿编辑写出来的文章哦,稳重介绍了如何在python3中实现自己的决策树算法并画出来!另外,小编Tom邀请你一起搞事情! 预备知识:...

3585
来自专栏PPV课数据科学社区

【学习】R语言与机器学习学习笔记(2)决策树算法

算法二:决策树算法 决策树定义 首先,我们来谈谈什么是决策树。我们还是以鸢尾花为例子来说明这个问题。 观察上图,我们判决鸢尾花的思...

3299
来自专栏绿巨人专栏

机器学习中的基本数学知识

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

基于Xgboost + LR + Keras 建模评估用户信用状态

项目背景 拍拍贷“魔镜风控系统”基于400多个数据维度来对当前用户的信用状态进行评估,通过历史数据每个借款人的性别、年龄、籍贯、学历信息、通讯方式、网站登录...

3094
来自专栏暢的专栏

一篇文章搞懂柏林噪声算法,附代码讲解 [ 译 ]

柏林噪声是一个非常强大算法,经常用于程序生成随机内容,在游戏和其他像电影等多媒体领域广泛应用。本文以一种通俗简单的方式介绍Ken Perlin的改进版柏林噪声算...

2.4K2
来自专栏机器学习算法全栈工程师

Isolation Forest算法原理详解

作者:章华燕 编辑:栾志勇 前言 随着机器学习近年来的流行,尤其是深度学习的火热。机器学习算法在很多领域的应用越来越普遍。最近,作者在一家广告公司做广告...

4428
来自专栏算法channel

机器学习|聚类算法之DBSCAN

DBSCAN,全称:Density-Based Spatial Clustering of Applications with Noise,是一个比较有代表性的...

3299
来自专栏数据科学学习手札

(数据科学学习手札23)决策树分类原理详解&Python与R实现

  作为机器学习中可解释性非常好的一种算法,决策树(Decision Tree)是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的...

3687
来自专栏ATYUN订阅号

【学术】机器学习优化函数的直观介绍

AiTechYun 编辑:yuxiangyu 优化是机器学习的研究人员最感兴趣的领域之一。在本文中,我想从简单的函数优化开始介绍,然后讨论找到只能找到局部最小值...

3326

扫描关注云+社区