數據挖掘筆記-聚類-Canopy-原理與簡單實現

Canopy聚類算法是一個將對象分組到類的簡單、快速、精確地方法。每個對象用多維特征空間里的一個點來表示。這個算法使用一個快速近似距離度量和兩個距離閾值 T1>T2來處理?；镜乃惴ㄊ?，從一個點集合開始并且隨機刪除一個，創建一個包含這個點的Canopy，并在剩余的點集合上迭代。對于每個點，如果它的距離第一個點的距離小于T1，然后這個點就加入這個聚集中。除此之外，如果這個距離<T2，然后將這個點從這個集合中刪除。這樣非?？拷c的點將避免所有的未來處理，不可以再做其它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));  
        }  
    }