数据挖掘笔记-聚类-Canopy-原理与简单实现

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));  
        }  
    }