Canopy聚类算法是一个将对象分组到类的简单、快速、精确地方法。每个对象用多维特征空间里的一个点来表示。这个算法使用一个快速近似距离度量和两个距离阈值 T1>T2来处理。基本的算法是,从一个点集合开始并且随机删除一个,创建一个包含这个点的Canopy,并在剩余的点集合上迭代。对于每个点,如果它的距离第一个点的距离小于T1,然后这个点就加入这个聚集中。除此之外,如果这个距离<T2,然后将这个点从这个集合中删除。这样非常靠近原点的点将避免所有的未来处理,不可以再做其它Canopy的中心。这个算法循环到初始集合为空为止,聚集一个集合的Canopies,每个可以包含一个或者多个点。每个点可以包含在多于一个的Canopy中。
Canopy算法其实本身也可以用于聚类,但它的结果可以为之后代价较高聚类提供帮助,其用在数据预处理上要比单纯拿来聚类更有帮助。Canopy聚类经常被用作更加严格的聚类技术的初始步骤,像是K均值聚类。建立canopies之后,可以删除那些包含数据点数目较少的canopy,往往这些canopy是包含孤立点的。
Canopy算法的步骤如下:
(1)将所有数据放进list中,选择两个距离,T1,T2,T1>T2
(2)While(list不为空)
{
随机选择一个节点做canopy的中心;并从list删除该点;
遍历list:
对于任何一条记录,计算其到各个canopy的距离;
如果距离<T2,则给此数据打上强标记,并从list删除这条记录;
如果距离<T1,则给此数据打上弱标记;
如果到任何canopy中心的距离都>T1,那么将这条记录作为一个新的canopy的中心,并从list中删除这个元素;
}
需要注意的是参数的调整:
当T1过大时,会使许多点属于多个Canopy,可能会造成各个簇的中心点间距离较近,各簇间区别不明显;
当T2过大时,增加强标记数据点的数量,会减少簇个个数;T2过小,会增加簇的个数,同时增加计算时间;
下面用Java来简单实现算法,考虑简单,点只用了二维。
代码托管https://github.com/fighting-one-piece/repository-data/tree/master/data_mining
public class CanopyBuilder { private double T1 = 8; private double T2 = 4; private List<Point> points = null; private List<Canopy> canopies = null; public CanopyBuilder() { init(); } public void init() { points = new ArrayList<Point>(); points.add(new Point(8.1, 8.1)); points.add(new Point(7.1, 7.1)); points.add(new Point(6.2, 6.2)); points.add(new Point(7.1, 7.1)); points.add(new Point(2.1, 2.1)); points.add(new Point(1.1, 1.1)); points.add(new Point(0.1, 0.1)); points.add(new Point(3.0, 3.0)); canopies = new ArrayList<Canopy>(); } //计算两点之间的曼哈顿距离 public double manhattanDistance(Point a, Point b) { return Math.abs(a.getX() - b.getX()) + Math.abs(a.getY() - b.getY()); } //计算两点之间的欧氏距离 public double euclideanDistance(Point a, Point b) { double sum = Math.pow(a.getX() - b.getX(), 2) + Math.pow(a.getY() - b.getY(), 2); return Math.sqrt(sum); } public void run() { while (points.size() > 0) { Iterator<Point> iterator = points.iterator(); while (iterator.hasNext()) { Point current = iterator.next(); System.out.println("current point: " + current); //取一个点做为初始canopy if (canopies.size() == 0) { Canopy canopy = new Canopy(); canopy.setCenter(current); canopy.getPoints().add(current); canopies.add(canopy); iterator.remove(); continue; } boolean isRemove = false; int index = 0; for (Canopy canopy : canopies) { Point center = canopy.getCenter(); System.out.println("center: " + center); double d = manhattanDistance(current, center); System.out.println("distance: " + d); //距离小于T1加入canopy,打上弱标记 if (d < T1) { current.setMark(Point.MARK_WEAK); canopy.getPoints().add(current); } else if (d > T1) { index++; } //距离小于T2则从列表中移除,打上强标记 if (d <= T2) { current.setMark(Point.MARK_STRONG); isRemove = true; } } //如果到所有canopy的距离都大于T1,生成新的canopy if (index == canopies.size()) { Canopy newCanopy = new Canopy(); newCanopy.setCenter(current); newCanopy.getPoints().add(current); canopies.add(newCanopy); isRemove = true; } if (isRemove) { iterator.remove(); } } } for (Canopy c : canopies) { System.out.println("old center: " + c.getCenter()); c.computeCenter(); System.out.println("new center: " + c.getCenter()); ShowUtils.print(c.getPoints()); } } public static void main(String[] args) { CanopyBuilder builder = new CanopyBuilder(); builder.run(); } }
Canopy类
public class Canopy { private Point center = null; private List<Point> points = null; public Point getCenter() { return center; } public void setCenter(Point center) { this.center = center; } public List<Point> getPoints() { if (null == points) { points = new ArrayList<Point>(); } return points; } public void setPoints(List<Point> points) { this.points = points; } public void computeCenter() { double x = 0.0; double y = 0.0; for (Point point : getPoints()) { x += point.getX(); y += point.getY(); } double z = getPoints().size(); setCenter(new Point(x / z, y / z)); } }
相关推荐
聚类分析是数据挖掘中的一个重要分支,主要用于发现数据集中的自然群体或类别,无需事先知道具体的分类信息。在这个数据挖掘作业中,我们将深入探讨聚类分析的概念、方法以及其在实际应用中的价值。 聚类分析的目标...
UCI(University of California, Irvine)机器学习仓库是数据挖掘和机器学习领域广泛使用的资源库,其中包含了众多经典的数据集,用于研究和教学目的。这个压缩包“UCI常用数据集-聚类、分类.zip”显然是针对聚类和...
基于密度方法,根据密度完成对象的聚类。 perl实现 OPTICS(Ordering Points To Identify the Clustering Structure):并不明确产生一个聚类,而是为自动交互的聚类分析计算出一个增强聚类顺序。。
K均值聚类(K-Means聚类)-聚类算法-聚类可视化-MATLAB代码 本代码详细图文介绍,请点击博客主页查找对应文章查看。可保证运行,运行失败或报错免费解决。 k均值聚类算法的基本概念和原理 k均值聚类算法(k-...
聚类技术是数据挖掘中的一个重要分支,主要目的是通过无监督学习方法将数据集中的对象自动分成多个类别,使得同一类别的对象相似度较高,而不同类别间的对象相似度较低。本课程件将深入探讨聚类技术的原理、方法以及...
1. 准备数据:在进行聚类分析之前,需要确保数据质量,剔除异常值,处理缺失值,以及选择合适的变量。 2. 选择聚类方法:SPSS提供了多种聚类算法,包括K-means聚类、分层聚类等。每种方法都有其适用场景和优缺点,...
数据挖掘考试题目-聚类.doc
聚类分析是数据挖掘领域中一种重要的无监督学习方法,主要用于探索性数据分析,它通过对数据集中的对象进行分组,形成由相似对象组成的簇,以揭示数据的内在结构和模式。在聚类分析中,数据对象被组织成若干个簇,...
1.数据挖掘方法与应用-聚类
复旦大学数据挖掘概念和技术-聚类分析 共26页.ppt
k-聚类是一种无监督学习方法,主要用于数据挖掘和机器学习领域,旨在将数据集中的对象分成不同的类别或簇,使得同一簇内的对象相似度较高,而不同簇间的对象相似度较低。在k-均值(k-means)算法中,“k”表示我们...
聚类分析是数据挖掘中一种常用的无监督学习方法,它通过将数据集中的样本划分为若干个类别或簇,使得同一类簇内的样本之间具有较高的相似性,而不同类簇间的样本差异性较大。K-means算法是最经典的聚类算法之一,因...
鸢尾花IRIS数据集-聚类分析机器学习
人工智能-项目实践-聚类-Chinese-whisper 聚类算法(由于涉及公司代码保护,只显示文档) 链接 https://github.com/ouprince/CW.git 说明 原版论文:《CW聚类算法.pdf》 作者翻译:《CW聚类算法论文翻译.doc》
机器学习-数据预处理-聚类-回归-单车数据集
MATLAB数据挖掘算法_回归算法_关联算法_聚类算法源代码.rar 一元回归 多元回归 逐步回归 Logistic回归 Apriori算法 FP-Growth算法 算法 相关系数法 K-means 层次聚类 神经网络聚类 模糊C均值聚类 高斯聚类