Canopy聚类算法

摘要:
1、 该概念不同于传统的聚类算法(如K-means)。Canopy集群的最大特点是它不需要预先指定k值(即集群的数量)。在获得k值后,使用k-means进一步“Canopy+k-means的混合聚类方法分为以下两个步骤:Canopy聚类在第一阶段选择一种简单且低成本的方法来计算对象相似度。

一、概念    

与传统的聚类算法(比如K-means)不同,Canopy聚类最大的特点是不需要事先指定k值(即clustering的个数),因此具有很大的实际应用价值。与其他聚类算法相比,Canopy聚类虽然精度较低,但其在速度上有很大优势,因此可以使用Canopy聚类先对数据进行“粗”聚类,得到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划分完成后,类似于下图:

image

三、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聚类算法》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇ASP公共翻页代码SAS | 逻辑库和SAS数据集下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

《逆向工程核心原理》笔记第一章到第十一章

第一章/第二章 分析Hello World!程序 OD基本命令 Restart Ctrl+F2 重新开始调试 Step Into F7 执行语句会进入函数内部 Step Over F8 执行语句不会进入函数内部 Execute till Return Ctrl+F9 一直在函数代码内部运行,直到遇到retn跳出 (跳出该命令函数) OD中右边注释中的红...

String.Format使用方法

1、作为參数   名称 说明   Format(String, Object) 将指定的 String 中的格式项替换为指定的 Object 实例的值的文本等效项。   Format(String, array<>[]()[]) 将指定 String 中的格式项替换为指定数组中对应 Object 实例的值的文本等效项。  ...

基于Selenium2+Java的UI自动化(7)- 模拟键盘鼠标操作

webdriver提供Actions类,来模拟鼠标点击、悬浮、拖拽、键盘输入等操作; 一、鼠标双击、右击 selenium模拟鼠标单击是用WebElement.click(); 方法,但是双击、右击,需要使用Actions类来模拟; package com.automation.actions; import org.openqa.selenium...

聚类之k-means附代码

   import osimport sys as sys#reload(sys)#sys.setdefaultencoding('utf-8')from sklearn.cluster import KMeansfrom sklearn import feature_extractionfrom sklearn.feature_extraction....

OC语言·笔记二

1. 属性(Property)和实例变量(instance variable) 1.1 当定义一个属性时,本质上是在干什么(编译器在帮我们干什么): 1) 生成实例变量用来保存属性的值 2) 生成访问器(setter和getter方法)用于修改和访问属性的值 1.2 实际开发中知道的事: 1) 只读属性:只能读取值,不能修改值。这种属性只生成getter方...

ehcache 使用

引用 :http://blog.sina.com.cn/s/blog_46d5caa40100ka9z.html 在开发高并发量,高性能的网站应用系统时,缓存Cache起到了非常重要的作用。本文主要介绍EHCache的使用,以及使用EHCache的实践经验。笔者使用过多种基于Java的开源Cache组件,其中包括OSCache、JBossCache、EHC...