cft.java~42~

Birch

package clustering_feature_tree;
/**
 * <p>Title: </p>
 *
 * <p>Description: </p>
 *
 * <p>Copyright: Copyright (c) 2006</p>
 *
 * <p>Company: </p>
 *
 * @author not attributable
 * @version 1.0
 */
public class CFT {
    private int B;
    private int T;
    private int r;//半径
    private int vector;
    private node root;
    public void create_B_tree(){
        node r=new node(vector,B);
        r.child_(B);
        root=r;
        node c=new node(vector,T);
        r.n=1;r.child[0]=c;
        c.n=0;c.leaf=true;
    }
    public void B_tree_insert(double point[]){
        node r=root;
        if(r.n==B){
            node s=new node(vector,B);
            s.child_(B);
            root=s;
            s.leaf=false;
            s.n=1;
            s.child[0]=r;
            this.split(s,0,r);
            this.insert_nonfull(s,point);
        }
        else{
            this.insert_nonfull(r,point);
        }
    }
    public void insert_nonfull(node x,double[] point){
        int pos;
        double radius;
        double[] tempLS;
        double tempSS;
        int pos2;
        int pos3;
        double[] point_0;
        if(x.leaf){
            point_0=new double[T];
            pos=this.picknearest(point,x.LS,x.n);
            tempLS=MathsExtend.getNewAverVector(point,x.LS[pos],x.num[pos]);
            tempSS=MathsExtend.getNewMean(point,x.SS[pos],x.num[pos]);
            radius=MathsExtend.calRadius(tempSS*(x.num[pos]+1),tempLS);
            if(MathsExtend.calDistance(point,point_0)<radius){
                if(x.n<T){
                    pos=x.n;
                    this.renovate_insertpoint(x, x.n, point, 0, 1);
                    x.n++;
                }
            }
            else{
                if (radius < r) {
                    this.renovate_insertpoint(x, pos, tempLS, tempSS,
                                              x.num[pos] + 1);
                } else {
                    this.renovate_insertpoint(x, x.n, point, 0, 1);
                    x.n++;
                }
            }
        }
        else{
            pos2=this.picknearest(point,x.LS,x.n);
            tempLS=MathsExtend.getNewAverVector(point,x.LS[pos2],x.num[pos2]);
            tempSS=MathsExtend.getNewMean(point,x.SS[pos2],x.num[pos2]);
            this.renovate_insertpoint(x,pos2,tempLS,tempSS,x.num[pos2]+1);
            pos3=pos2;
            int tempB_T;
            if(x.child[pos2].leaf){
                tempB_T=T;
            }
            else{
                tempB_T=B;
            }
            if(x.child[pos2].n==tempB_T){
                this.split(x,pos2,x.child[pos2]);
                pos3=MathsExtend.compareDistance(point,x.LS[pos2],x.LS[x.n-1]);
                if(pos3==0){
                    pos3=pos2;
                }
                else{
                    pos3=x.n-1;
                }
            }
            this.insert_nonfull(x.child[pos3],point);
        }
    }
    private void renovate_insertpoint(node x,int pos2,double[] LS,double SS,int num){//在插入一个节点后，更新节点的各个信息
        for(int i=0;i<LS.length;i++){                                                  //SS LS都是计算好的，这个方法只是赋值
            x.LS[pos2][i]=LS[i];
        }
        x.SS[pos2]=SS;
        x.num[pos2]=num;
    }
    public void split(node x,int p,node y){ //p是从0开始计的
        int[] pos=new int[2];
        int B_T;
        node z=new node();
        z.leaf=y.leaf;
        z.n=0;

        x.n++;
        this.ls_0(x.LS[p]);
        x.SS[p]=0;
        x.num[p]=0;
        this.ls_0(x.LS[x.n]);
        x.SS[x.n]=0;
        x.num[x.n]=0;

        pos=pickfarthest(y);
        y.n=0;
        boolean tempchild=z.leaf;
        if(!z.leaf){
            z. value_B_or_T_and_vector(vector, B);
            z.child_(B);
            B_T=B;
        }
        else{
            z.value_B_or_T_and_vector(vector, T);
            B_T=T;
        }
        node temp=(node)y.clone();
        y=new node(vector,B_T);
        if(tempchild==true){
            y.child_(B);
        }
        else{
            y.leaf=true;
        }
        y.SS[0]=temp.SS[pos[0]];
        this.LS_xTOy(y.LS[0],temp.LS[pos[0]]);

        y.n++;
        y.num[0]=temp.num[pos[0]];

        renovateLS(x.LS[p],0,y.LS[0],y.num[0]);
        renovateSS(x.SS[p],0,y.SS[0],y.num[0]);
        x.num[p]+= y.num[0];

        z.SS[0]=temp.SS[pos[1]];
        this.LS_xTOy(z.LS[0],temp.LS[pos[1]]);
        z.n++;
        z.num[0]=temp.num[pos[1]];

        renovateLS(x.LS[x.n-1],0,z.LS[0],z.num[0]);
        renovateSS(x.SS[x.n-1], 0,z.SS[0],z.num[0]);
        x.num[x.n]+= z.num[0];

        if(temp.leaf=false){
                   y.child[0] = temp.child[pos[0]];
                   z.child[0]=temp.child[pos[1]];
        }

        int indicator;
        for(int i= 0;i<B_T;i++){ //except //pos[0] et pos[1]{
            if(i==pos[0]||i==pos[1]){
                continue;
            }
            indicator = MathsExtend.compareDistance(temp.LS[i],temp.LS[pos[0]],temp.LS[pos[1]]);
            if (indicator==0) {
                y.SS[y.n] = temp.SS[i];
                this.LS_xTOy(z.LS[y.n],temp.LS[i]);
                if(temp.leaf=false){
                    y.child[y.n] = temp.child[i];
                }
                y.num[y.n] = temp.num[i];
                renovateLS(x.LS[p],x.num[p], y.LS[y.n],y.num[y.n]);
                renovateSS(x.SS[p],x.num[p], y.SS[y.n],y.num[y.n]);
                x.num[p] += y.num[y.n];
                y.n++;
            } else {
                z.SS[z.n] = temp.SS[i];
                this.LS_xTOy(z.LS[z.n],temp.LS[i]);
                if(temp.leaf=false){
                    z.child[z.n] = temp.child[i];
                }
                z.num[z.n] = temp.num[i];
                renovateLS(x.LS[x.n-1], x.num[x.n-1],z.LS[z.n],z.num[z.n]);
                renovateSS(x.SS[x.n-1], x.num[x.n-1],z.SS[z.n],z.num[z.n]);
                x.num[x.n-1] += z.num[z.n];
                z.n++;
            }
        }
    }
    private void renovateLS(double[] LSx,int numx,double[] LSy,int numy){//修改x中的LS
        for(int i=0;i<LSx.length;i++){
            LSx[i]=((double)numx/(numx+numy))*LSx[i]+((double)numy/(numx+numy))*LSy[i];
        }
    }

    private void renovateSS(double SSx,int numx,double SSy,int numy){
        SSx=((double)numx/(numx+numy))*SSx+((double)numy/(numx+numy))*SSy;
    }

    private void LS_xTOy(double[] LSx,double[] LSy){
        for(int i=0;i<LSx.length;i++){
            LSy[i]=LSx[i];
        }
    }
    private int picknearest(double[] point,double[][] LS,int n){
        int pos2=0;
        double distance=999999999;
        double temp;
        for(int i=0;i<n;i++){
            temp=MathsExtend.calDistance(point,LS[i]);
            if(temp<distance){
                distance=temp;
                pos2=i;
            }
        }
        return pos2;
    }
    private int[] pickfarthest(node y){
        int[] pos2=new int[2];
        double distance=0;
        double temp;
        pos2[0]=0;
        pos2[1]=1;
        for(int i=0;i<y.n-1;i++){
            for(int j=i+1;j<y.n;j++){
                temp=MathsExtend.calDistance(y.LS[i],y.LS[j]);
                if(temp>distance){
                    distance=temp;
                    pos2[0]=i;
                    pos2[1]=j;
                }
            }
        }
        return pos2;
    }
    public CFT(int B,int T,int r,int vector) {
        this.B=B;
        this.T=T;
        this.r=r;
        this.vector=vector;
    }
    private void ls_0(double[] ls){
        for(int i=0;i<ls.length;i++){
            ls[i]=0;
        }
    }
}