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来简单实现算法,考虑简单,点只用了二维。
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类
[java] view plain copy
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));
}
}
数据分析咨询请扫描二维码
若不方便扫码,搜微信号:CDAshujufenxi
你是否被统计学复杂的理论和晦涩的公式劝退过?别担心,“山有木兮:统计学极简入门(Python)” 将为你一一化解这些难题。课程 ...
2025-03-31在电商、零售、甚至内容付费业务中,你真的了解你的客户吗? 有些客户下了一两次单就消失了,有些人每个月都回购,有些人曾经是 ...
2025-03-31在数字化浪潮中,数据驱动决策已成为企业发展的核心竞争力,数据分析人才的需求持续飙升。世界经济论坛发布的《未来就业报告》, ...
2025-03-28你有没有遇到过这样的情况?流量进来了,转化率却不高,辛辛苦苦拉来的用户,最后大部分都悄无声息地离开了,这时候漏斗分析就非 ...
2025-03-27TensorFlow Datasets(TFDS)是一个用于下载、管理和预处理机器学习数据集的库。它提供了易于使用的API,允许用户从现有集合中 ...
2025-03-26"不谋全局者,不足谋一域。"在数据驱动的商业时代,战略级数据分析能力已成为职场核心竞争力。《CDA二级教材:商业策略数据分析 ...
2025-03-26当你在某宝刷到【猜你喜欢】时,当抖音精准推来你的梦中情猫时,当美团外卖弹窗刚好是你想吃的火锅店…… 恭喜你,你正在被用户 ...
2025-03-26当面试官问起随机森林时,他到底在考察什么? ""请解释随机森林的原理""——这是数据分析岗位面试中的经典问题。但你可能不知道 ...
2025-03-25在数字化浪潮席卷的当下,数据俨然成为企业的命脉,贯穿于业务运作的各个环节。从线上到线下,从平台的交易数据,到门店的运营 ...
2025-03-25在互联网和移动应用领域,DAU(日活跃用户数)是一个耳熟能详的指标。无论是产品经理、运营,还是数据分析师,DAU都是衡量产品 ...
2025-03-24ABtest做的好,产品优化效果差不了!可见ABtest在评估优化策略的效果方面地位还是很高的,那么如何在业务中应用ABtest? 结合企业 ...
2025-03-21在企业数据分析中,指标体系是至关重要的工具。不仅帮助企业统一数据标准、提升数据质量,还能为业务决策提供有力支持。本文将围 ...
2025-03-20解锁数据分析师高薪密码,CDA 脱产就业班助你逆袭! 在数字化浪潮中,数据驱动决策已成为企业发展的核心竞争力,数据分析人才的 ...
2025-03-19在 MySQL 数据库中,查询一张表但是不包含某个字段可以通过以下两种方法实现:使用 SELECT 子句以明确指定想要的字段,或者使 ...
2025-03-17在当今数字化时代,数据成为企业发展的关键驱动力,而用户画像作为数据分析的重要成果,改变了企业理解用户、开展业务的方式。无 ...
2025-03-172025年是智能体(AI Agent)的元年,大模型和智能体的发展比较迅猛。感觉年初的deepseek刚火没多久,这几天Manus又成为媒体头条 ...
2025-03-14以下的文章内容来源于柯家媛老师的专栏,如果您想阅读专栏《小白必备的数据思维课》,点击下方链接 https://edu.cda.cn/goods/sh ...
2025-03-13以下的文章内容来源于刘静老师的专栏,如果您想阅读专栏《10大业务分析模型突破业务瓶颈》,点击下方链接 https://edu.cda.cn/go ...
2025-03-12以下的文章内容来源于柯家媛老师的专栏,如果您想阅读专栏《小白必备的数据思维课》,点击下方链接 https://edu.cda.cn/goods/sh ...
2025-03-11随着数字化转型的加速,企业积累了海量数据,如何从这些数据中挖掘有价值的信息,成为企业提升竞争力的关键。CDA认证考试体系应 ...
2025-03-10