FuzzyKmeans

传送门

在对数据进行聚类时，最常用的方法应该是kmeans，但是kmean只能保证每一条待聚类的数据划分到一个类别，针对一条数据可以被划分到多个类别的情况无法处理。为此，人们提出了FuzzyKmeans聚类方法，该方法衡量的是每一条数据属于某个类别的概率，既然是概率就不再是非1即0的情况，这样就能保证一条数据可以被划分到多个类别。

对应FuzzyKmeans的聚类过程如下：

其中dij这个参数衡量的是该条数据i到类别j中心点的距离，uij就是数据i属于类别j的概率。

求得概率之后，需要更新某个类别的中心点，这时就按照(4)式更新，也就是用属于该类的概率与数据原先的值加以计算

至于结束条件一种是达到设定的迭代次数，一种是满足第四步的条件，即两个类别的中心点距离小于一个值。

最重要的应该是m值的选择，当每条数据距离各个类别中心点距离比较接近时，建议1/(m-1)值较大，因为这样在指数运算后距离就能有较大差异了，此时m接近于1. 如果距离本来就有很大差异，1/(m-1)就可以取值小一些，一般来说m取1.5，这样就足够了。

最后要注意迭代次数不宜过多，一般两次足够，因为考虑的是概率，如果迭代次数过多，中心点偏移较大，很可能得到数据到各个类别的概率都相差不大。

下面用JAVA实现的FuzzyKmeans，每一条数据都是一个200维的向量，使用时可以指定初始中心点，中心点的向量需要从待聚类数据中查找得到。

首先是处理输入的类：

package kmeans;  
import java.io.BufferedReader;  
import java.io.File;  
import java.io.FileInputStream;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.ArrayList;  
import java.util.HashMap;  
import java.util.List;  
  
  
  
public class Word2VEC {  
      
    private HashMap<String, double[]> wordMap = new HashMap<String, double[]>();  
  
    public void loadVectorFile(String path) throws IOException {  
        BufferedReader br = null;  
        double len = 0;  
        double vector = 0;  
        int size=0;  
        try {  
            File f = new File(path);  
            br = new BufferedReader(new InputStreamReader(new FileInputStream(f), "UTF-8"));  
            String word;  
            String line="";  
            String[] outline=new String[210];  
            double[] vectors = null;  
            int count=0;  
            while((line=br.readLine())!=null){  
                if(count%100000==0){  
                    System.out.println("read: "+count);  
                }  
                count++;  
                outline=line.split(",");  
                size=outline.length-1;  
                word = outline[0];  
                vectors = new double[size];  
                len = 0;  
                for (int j = 0; j < size; j++) {  
                    vector = Float.parseFloat(outline[j+1]);  
                    len += vector * vector;  
                    vectors[j] = (double) vector;  
                }  
                len = Math.sqrt(len);  
                for (int j = 0; j < size; j++) {  
                    vectors[j] /= len;  
                }  
                wordMap.put(word, vectors);  
            }  
        }   
        finally {  
            System.out.println("total word: "+wordMap.size()+" vector dimensions: "+size);  
            br.close();  
        }  
    }  
  
    public HashMap<String, double[]> getWordMap() {  
        return wordMap;  
    }  
      
    //calculate how many center point in the samples  
    public List<String> loadPointFile(String point_path) throws IOException{  
        File f = new File(point_path);  
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(f), "UTF-8"));  
        String line="";  
        List<String> center=new ArrayList<String>();  
        while((line=br.readLine())!=null){  
            if(wordMap.containsKey(line)){  
                center.add(line);  
            }  
        }  
        br.close();  
        return center;  
    }  
}

然后是聚类的类：

package kmeans;  
import java.io.BufferedReader;  
import java.io.BufferedWriter;  
import java.io.File;  
import java.io.FileInputStream;  
import java.io.FileNotFoundException;  
import java.io.FileOutputStream;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.io.OutputStreamWriter;  
import java.util.ArrayList;  
import java.util.Collections;  
import java.util.HashMap;  
import java.util.Iterator;  
import java.util.List;  
import java.util.Map;  
import java.util.Map.Entry;  
  
  
  
  
  
  
import org.apache.commons.cli.CommandLine;  
import org.apache.commons.cli.CommandLineParser;  
import org.apache.commons.cli.HelpFormatter;  
import org.apache.commons.cli.Options;  
import org.apache.commons.cli.ParseException;  
import org.apache.commons.cli.PosixParser;  
  
public class FuzzyKmeans {  
        private HashMap<String, double[]> wordMap = null;  
        private int iter;  
        private Classes[] cArray = null;  
        public static HashMap<Integer,String> wordcenter=new HashMap<Integer,String>();  
          
        //total 659624 words each is a 200 vector  
        //args[0] is the word vectors csv file  
        //args[1] is the output file   
        //args[2] is the cluster number  
        //args[3] is the iterator number  
        public static void main(String[] args) throws IOException, ParseException {  
              
            String source_path;  
            String output_path;  
            int cluster_num = 10;  
            int iterator_num = 10;  
            double m=1.5;  
      
              
            String point_path = null;  
              
             Options options = new Options();    
             options.addOption("h", false, "help"); //参数不可用  
             options.addOption("i", true, "input file path"); //参数可用       
             options.addOption("o", true, "output file path"); //参数可用   
             options.addOption("c", true, "cluster number, default 10"); //参数可用   
             options.addOption("x", true, "iterator number, default 10"); //参数可用   
             options.addOption("p", true, "the center point"); //参数可用  
             options.addOption("m", true, "the parameter for fuzzy kmeans"); //参数可用  
               
             CommandLineParser parser = new PosixParser();    
             CommandLine cmd = parser.parse(options, args);    
         
             if (cmd.hasOption("i"))    
             {    
                source_path = cmd.getOptionValue("i");    
             }else{  
                 HelpFormatter formatter = new HelpFormatter();    
                 formatter.printHelp( "help", options );   
                 return;  
             }  
               
             if (cmd.hasOption("o"))    
             {    
                 output_path = cmd.getOptionValue("o");    
             }else{  
                 HelpFormatter formatter = new HelpFormatter();    
                 formatter.printHelp( "help", options );   
                 return;  
             }  
         
             if (cmd.hasOption("c"))    
             {    
                 cluster_num = Integer.parseInt(cmd.getOptionValue("c"));    
             }  
             if (cmd.hasOption("m"))    
             {    
                 m = Double.parseDouble(cmd.getOptionValue("m"));    
             }  
               
             if (cmd.hasOption("x"))    
             {    
                 iterator_num = Integer.parseInt(cmd.getOptionValue("x"));    
             }  
             if (cmd.hasOption("p"))    
             {    
                 point_path = cmd.getOptionValue("p");    
             }  
               
             if (cmd.hasOption("h"))    
             {    
                 HelpFormatter formatter = new HelpFormatter();    
                 formatter.printHelp( "help", options );   
             }  
               
            Word2VEC vec = new Word2VEC();  
            vec.loadVectorFile(source_path);  
            System.out.println("load data ok!");  
              
              
            List<String> center=new ArrayList<String>();  
            if(point_path!=null){  
                center=vec.loadPointFile(point_path);  
                if(cluster_num<center.size()){  
                    cluster_num=center.size();  
                }  
                  
            }  
              
              
            FuzzyKmeans fuzzyKmeans = new FuzzyKmeans(vec.getWordMap(), cluster_num,iterator_num);  
            Classes[] explain = fuzzyKmeans.explain(point_path,m,center);  
              
            File fw = new File(output_path);  
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(fw), "UTF-8"));  
              
            for (int i = 0; i < explain.length; i++) {  
                List<Entry<String, Double>> result=explain[i].getMember();  
                StringBuffer buf = new StringBuffer();  
                for (int j = 0; j < result.size(); j++) {  
                    buf.append(i+"\t"+wordcenter.get(i)+"\t"+result.get(j).getKey()+"\t"+String.format("%.6f", result.get(j).getValue())+"\n");  
                }  
                bw.write(buf.toString());  
                bw.flush();  
            }  
            bw.close();  
              
            for(int i=0;i<wordcenter.size();i++){  
                System.out.println(i+"\t"+wordcenter.get(i));  
            }  
        }  
  
        public FuzzyKmeans(HashMap<String, double[]> wordMap, int clcn, int iter) {  
            this.wordMap = wordMap;  
            this.iter = iter;  
            cArray = new Classes[clcn];  
        }  
  
        public Classes[] explain(String point_path,double m,List<String> center) throws IOException, FileNotFoundException {  
            Iterator<Entry<String, double[]>> iterator = wordMap.entrySet().iterator();  
            //cluster number is the same as the center point number  
            if(cArray.length==center.size()){  
                String word="";  
                for (int i = 0; i < cArray.length; i++) {  
                    word=center.get(i);  
                    cArray[i] = new Classes(i, wordMap.get(word));  
                    wordcenter.put(i, word);  
                    System.out.println(new String(word.getBytes("UTF-8")));  
                }  
            }  
              
            else{  
                if(point_path==null){  
                    for (int i = 0; i < cArray.length; i++) {  
                        Entry<String, double[]> next = iterator.next();  
                        cArray[i] = new Classes(i, next.getValue());  
                    }  
                }  
                else{  
                    String word="";  
                    File f = new File(point_path);  
                    BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(f), "UTF-8"));  
                    for (int i = 0; i < cArray.length; i++) {  
                        word=br.readLine();  
                        if(wordMap.containsKey(word)){  
                            cArray[i] = new Classes(i, wordMap.get(word));  
                            wordcenter.put(i, word);  
                            System.out.println(new String(word.getBytes("UTF-8")));  
                        }  
                        else{  
                            Entry<String, double[]> next = iterator.next();  
                            cArray[i] = new Classes(i, next.getValue());  
                            wordcenter.put(i, next.getKey());  
                        }  
                    }  
                    br.close();  
                }  
            }  
              
              
              
            iterator = wordMap.entrySet().iterator();  
            HashMap<Integer,String> num_wordmap=new HashMap<Integer,String>();  
            HashMap<Integer,double[]> num_vecmap=new HashMap<Integer,double[]>();  
            //put word to the map  
            int count=0;  
            while (iterator.hasNext()) {  
                Entry<String, double[]> next = iterator.next();  
                num_wordmap.put(count, next.getKey());  
                num_vecmap.put(count, next.getValue());  
                count++;  
            }  
              
              
            //begin iterator step  
            for (int i = 0; i < iter; i++) {   
                for (Classes classes : cArray) {  
                    classes.clean();  
                }  
                  
                double u[][]=new double[cArray.length][count];  
                  
                int cnt = 0;  
                int num=0;  
                  
                while (num<count) {  
                    if(cnt % 10000 ==0)  
                    {  
                        System.out.println("Iter: "+i+"\tword:"+(cnt));  
                    }  
                      
                    double tempScore;  
                    double d_sum=0;  
                    double temp_sum=0;  
                    int newid=0;  
                    int flag=0;  
                      
                    //calculate the total distances  
                    for (Classes classes : cArray) {  
                         tempScore = classes.distance(num_vecmap.get(num));  
                         if(tempScore==0.0){  
                             flag=1;  
                             newid=classes.id;  
                             break;  
                         }  
                         temp_sum=Math.pow(1/tempScore, 1/(m-1));  
                         d_sum+=temp_sum;  
                    }  
                    if(flag==1){  
                         for (Classes classes : cArray) {  
                             u[classes.id][num]=0;  
                             cArray[classes.id].putValue(num_wordmap.get(num), 0);  
                         }  
                         u[newid][num]=1;  
                         cArray[newid].putValue(num_wordmap.get(num), 1);  
                          
                    }  
                    else{  
                        //cArray is the cluster center point  
                        for (Classes classes : cArray) {  
                            //calculate the distance between the point and the center  
                            tempScore = classes.distance(num_vecmap.get(num));  
                            u[classes.id][num]=1/(Math.pow(tempScore,1/(m-1))*d_sum);  
//                          System.out.println(num+" to "+classes.id+" distances:" +tempScore);  
                            //put the num and its probability  
                            cArray[classes.id].putValue(num_wordmap.get(num), u[classes.id][num]);  
                        }  
                    }  
                    cnt++;  
                    num++;  
                      
                      
                  
                }  
                System.out.println("Iter:"+i+"\tfinished\tword:"+(cnt));  
                for (Classes classes : cArray) {  
                    classes.updateCenter(num_vecmap,u,count,m);    
                }  
                System.out.println("iter " + i + " ok!");  
            }  
            return cArray;  
        }  
  
          
        public static class Classes {  
            private int id;  
            private double[] center;  
            public Classes(int id, double[] center) {  
                this.id = id;  
                this.center = center.clone();  
            }  
            Map<String, Double> values = new HashMap<String,Double>();  
            //calculate the distance between point and center  
            public double distance(double[] value) {  
                double sum = 0;  
                for (int i = 0; i < value.length; i++) {  
                    sum += (center[i] - value[i])*(center[i] - value[i]) ;  
                }  
                return sum ;  
            }  
              
            //put word and its probability  
            public void putValue(String word, double score) {  
                values.put(word, score);  
            }  
  
            public void updateCenter(HashMap<Integer, double[]> num_vecmap,double[][] u,int count,double m) {  
                for (int i = 0; i < center.length; i++) {  
                    center[i] = 0;  
                }  
                double[] value = null;  
                  
                for(int j=0;j<count;j++){  
                    value = num_vecmap.get(j);  
                    for (int i = 0; i < value.length; i++) {  
                            center[i] +=Math.pow(u[id][j],m) *value[i];  
                    }  
                }  
                double sum=0;  
                for(int j=0;j<count;j++){  
                    sum+=Math.pow(u[id][j],m);  
                }  
                  
                for (int i = 0; i < center.length; i++) {  
                    center[i] = center[i] / sum;  
                }  
            }  
  
            public void clean() {  
                values.clear();  
            }  
  
  
              
            public List<Entry<String, Double>> getMember() {  
                List<Map.Entry<String, Double>> arrayList = new ArrayList<Map.Entry<String, Double>>(  
                    values.entrySet());  
                int count=arrayList.size();  
                if(count<=0){  
                    return Collections.emptyList() ;  
                }  
                return arrayList;  
            }  
        }  
}

#####BIRCH算法

######算法概念
传送
BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies）全称是：利用层次方法的平衡迭代规约和聚类。BIRCH算法是1996年由Tian Zhang提出来的，参考文献1。首先，BIRCH是一种聚类算法，它最大的特点是能利用有限的内存资源完成对大数据集的高质量的聚类，同时通过单遍扫描数据集能最小化I/O代价。

首先解释一下什么是聚类，从统计学的观点来看，聚类就是给定一个包含N个数据点的数据集和一个距离度量函数F（例如计算簇内每两个数据点之间的平均距离的函数），要求将这个数据集划分为K个簇（或者不给出数量K，由算法自动发现最佳的簇数量），最后的结果是找到一种对于数据集的最佳划分，使得距离度量函数F的值最小。从机器学习的角度来看，聚类是一种非监督的学习算法，通过将数据集聚成n个簇，使得簇内点之间距离最小化，簇之间的距离最大化。

BIRCH算法特点：

• BIRCH试图利用可用的资源来生成最好的聚类结果，给定有限的主存，一个重要的考虑是最小化I/O时间。

• BIRCH采用了一种多阶段聚类技术：数据集的单边扫描产生了一个基本的聚类，一或多遍的额外扫描可以进一步改进聚类质量。

• BIRCH是一种增量的聚类方法，因为它对每一个数据点的聚类的决策都是基于当前已经处理过的数据点，而不是基于全局的数据点。

• 如果簇不是球形的，BIRCH不能很好的工作，因为它用了半径或直径的概念来控制聚类的边界。

  BIRCH算法中引入了两个概念：聚类特征和聚类特征树，以下分别介绍。

######1.1 聚类特征（CF）
CF是BIRCH增量聚类算法的核心，CF树中得节点都是由CF组成，一个CF是一个三元组，这个三元组就代表了簇的所有信息。给定N个d维的数据点{x1,x2,….,xn}，CF定义如下：

CF=（N，LS，SS）

其中，N是子类中节点的数目，LS是N个节点的线性和，SS是N个节点的平方和。

CF有个特性，即可以求和，具体说明如下：CF1=（n1,LS1,SS1），CF2=（n2,LS2,SS2），则CF1+CF2=（n1+n2, LS1+LS2, SS1+SS2）。

例如：

假设簇C1中有三个数据点：（2,3），（4,5），（5,6），则CF1={3，（2+4+5,3+5+6），（2^2+4^2+5^2,3^2+5^2+6^2）}={3，（11,14），（45,70）}，同样的，簇C2的CF2={4，（40,42），（100,101）}，那么，由簇C1和簇C2合并而来的簇C3的聚类特征CF3计算如下：

CF3={3+4,（11+40,14+42），（45+100,70+101）}={7，（51,56），（145,171）}

另外在介绍两个概念：簇的质心和簇的半径。假如一个簇中包含n个数据点：{Xi}，i=1,2,3…n.，则质心C和半径R计算公式如下：

C=(X1+X2+…+Xn)/n，（这里X1+X2+…+Xn是向量加）

R=(|X1-C|^2+|X2-C|^2+…+|Xn-C|^2)/n

其中，簇半径表示簇中所有点到簇质心的平均距离。CF中存储的是簇中所有数据点的特性的统计和，所以当我们把一个数据点加入某个簇的时候，那么这个数据点的详细特征，例如属性值，就丢失了，由于这个特征，BIRCH聚类可以在很大程度上对数据集进行压缩。

######1.2 聚类特征树（CF tree）
CF tree的结构类似于一棵B-树，它有两个参数：内部节点平衡因子B，叶节点平衡因子L，簇半径阈值T。树中每个节点最多包含B个孩子节点，记为（CFi，CHILDi），1<=i<=B，CFi是这个节点中的第i个聚类特征，CHILDi指向节点的第i个孩子节点，对应于这个节点的第i个聚类特征。例如，一棵高度为3，B为6，L为5的一棵CF树的例子如图所示：

棵CF树是一个数据集的压缩表示，叶子节点的每一个输入都代表一个簇C，簇C中包含若干个数据点，并且原始数据集中越密集的区域，簇C中包含的数据点越多，越稀疏的区域，簇C中包含的数据点越少，簇C的半径小于等于T。随着数据点的加入，CF树被动态的构建，插入过程有点类似于B-树。加入算法表示如下：

(1)从根节点开始，自上而下选择最近的孩子节点  
(2)到达叶子节点后，检查最近的元组CFi能否吸收此数据点  
    是，更新CF值  
    否，是否可以添加一个新的元组  
        是，添加一个新的元组  
        否则，分裂最远的一对元组，作为种子，按最近距离重新分配其它元组  
(3)更新每个非叶节点的CF信息，如果分裂节点，在父节点中插入新的元组，检查分裂，直到root

计算节点之间的距离函数有多种选择，常见的有欧几里得距离函数和曼哈顿距离函数，具体公式如下：

构建CF树的过程中，一个重要的参数是簇半径阈值T，因为它决定了CF tree的规模，从而让CF tree适应当前内存的大小。如果T太小，那么簇的数量将会非常的大，从而导致树节点数量也会增大，这样可能会导致所有数据点还没有扫描完之前内存就不够用了。

######2.算法流程

BIRCH算法流程如下图所示：

整个算法的实现分为四个阶段：

（1）扫描所有数据，建立初始化的CF树，把稠密数据分成簇，稀疏数据作为孤立点对待
（2）这个阶段是可选的，阶段3的全局或半全局聚类算法有着输入范围的要求，以达到速度与质量的要求，所以此阶段在阶段1的基础上，建立一个更小的CF树
（3）补救由于输入顺序和页面大小带来的分裂，使用全局/半全局算法对全部叶节点进行聚类
（4）这个阶段也是可选的，把阶段3的中心点作为种子，将数据点重新分配到最近的种子上，保证重复数据分到同一个簇中，同时添加簇标签

######3.算法实现

BIRCH算法的发明者于1996年完成了BIRCH算法的实现，是用c++语言实现的，已在solaris下编译通过。

另外算法的实现也可参考：http://blog.sina.com.cn/s/blog_6e85bf420100om1i.html

参考文献：

1.BIRCH:An Efficient Data Clustering Method for Very Large Databases

######4. 源码解读
传送

Birch算法全称是利用层次方法的平衡迭代约减和聚类(Balanced Iterative Reducing and Clustering Using Hierarchis)。该算法的优点是：第一，只需要一次访问数据库，速度快。第二，相似数据在很大程度上得到压缩，节省了存储空间。第三，不需要大量递归运算。一个聚类有了这三个优点，不优秀都难了。它是Wisconsin-Madison大学Tian Zhang博士于1996年提出的聚类算法，采用B-树的思想实现（有点遗憾，要是这个算法也是韩佳炜老师发明的就好啦）。

Birch算法虽然采用B-树实现但是它又不是一个完全的B-树，因为第一，它的所有元素全部保存在叶子节点中，第二，在一个BTNode中的关键字间并没有大小关系，第三，当一个BTNode中的关键字个数大于指定数时，不需要将第(M+1)/2个关键字移到上一层节点中去，而是之间分裂成两个BTNode，再在上层中对应的BTNode中加个关键字。现在假定读者知道B-树的原理。先说明几个结构体：

//维信息，相同值会合并起来
//要按data排序，方便后面计算距离
typedef struct AttNode
{
 //值
 string data;
 //具有该值的记录数目
 unsigned int count;
 //该维上下一个不同取值
 AttNode *next; 
}*AttTree;

//记录信息，也即是簇信息
typedef struct CFNode
{
 //记录条数
 unsigned int count;
 //属性数组
 //每个AttNode指针带头结点，方便合并两个CFNode
 AttNode *atts[attNum];
}*CFTree;

//B-树
typedef struct BTNode
{
 //已有CF数目
 int keyNum;
 //0号单元未用
    //要是模仿B-树的话，应该是M+1，但是为了方便分裂就变成M+2了
 //注意keys的第1位和ptr的0位对应，keys的第2位和ptr的1位对应，以此类推
 CFTree keys[M+2];
 BTNode *parent;
 BTNode *ptr[M+2];
}*BTree;
//叶子结构体，用于将B-树的叶子节点连起来
typedef struct BLeafNode
{
 BTree leaf;
 BLeafNode *next;
}*BLeafTree;
//beginLeaft保存起始叶子节点的位置
BLeafTree beginLeaf;

下面把这颗类B-树画出来

图中一个BTNode最多包含4个CFNode，每个CFNode就相当于一个簇，而每个BTNode里面的所有CFNode相当于一个大簇。当插入一个新纪录时，是从底往上修改的，所以叶子节点是等深的，用BLeafNode将所有叶子节点窜连起来，方便挖掘这颗B-树。还是用例子说明吧。

先插入第一条记录，用该纪录创建一个CFNode，再用该CFNode创建一个BTNode作为根节点。图如下：

从第二条记录起就具有一般性了，插入第二条记录时，用该条记录创建一个临时CFNode，记cft,然后从根节点开始，看cft和根节点的哪个CFNode距离最近（当然目前只有一个CFNode),根据这个CFNode找到它的子BTNode（当然这里没有），一直这样下去，直到叶子节点（当然这里根节点也就是叶子节点）。假如cft和找到的最近的BTNode，记bt,的最近的那个CFNode，记cfp的距离是d,如果d小于给定的阈值minDis，则将cft和cfp合并，然后从该叶子节点向上跟新各个BTNode的信息直到跟节点，跟新的方法是将cft的信息合并到父节点的各个CFNode中（具体看代码吧）。如果d大于给定的阈值，但是bt的CFNode小于给定的阈值M，则将cft作为bt的一个新CFNode，然后依然从该叶子节点向上跟新各个BTNode的信息直到跟节点。如果bt的cfp大于给定的阈值M，则只能将bt分裂成两个BTNode,然后将原BTNode也就是bt所对应的父节点，记r，的对应的CFNode分裂成两个CFNode,如果那时r中的CFNode数目也大于M则继续向上分裂，否则向上跟新。这里有很多细节问题，也不好描叙，直接看代码吧。

下面讲下这么处理字符型数据。下面是以前做的笔记。

Birch算法也有不足的地方，第一，它对输入数据的先后顺序敏感，第二，每个CFNode将各条记录的数据相同的部分合并了，不能还原成原来的记录了。但是我们还是很方便求出每个簇的平均值等信息。

Brich算法源码

// birchSelf.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<vector>
#include<string>
#include<iostream>
#include<cmath>
#include<ctime>
//以下两个头文件调用sort给vector排序
#include<algorithm>
#include<functional>

using namespace std;

//birch算法，用B-树实现,可以求非数字类型距离
//是以维为单位计算距离
//但是它又不是一个完全的B-树，因为第一，它的所有元素全部保存在叶子节点中，
//第二，在一个BTNode中的关键字间并没有大小关系
//第三，当一个BTNode中的关键字个数大于制定数时，不需要将第(M+1)/2个关键字移到上一层节点中去，
//而是之间分裂成两个BTNode，再在上层中对应的BTNode中加个关键字

//属性数目
const int attNum = 8;
//分支因子，叶节点和非叶节点相同
//相当于B-树的介数
const int M = 5;
//新的一条记录和CF的最近距离
const double minDis = 5;
//每个簇的记录的最小数，如果小于这个数就做一场数据处理
const double minClusters = 20;
//true：表示字符型,false：表示数字型
const bool charType = false;


//维信息，相同值会合并起来
//要按data排序，方便后面计算距离
typedef struct AttNode
{
 //值
 string data;
 //具有该值的记录数目
 unsigned int count;
 //该维上下一个不同取值
 AttNode *next; 
}*AttTree;

//记录信息，也即是簇信息
typedef struct CFNode
{
 //记录条数
 unsigned int count;
 //属性数组
 //每个AttNode指针带头结点，方便合并两个CFNode
 AttNode *atts[attNum];
}*CFTree;

//B-树
typedef struct BTNode
{
 //已有CF数目
 int keyNum;
 //0号单元未用
    //要是模仿B-树的话，应该是M+1，但是为了方便分裂就变成M+2了
 //注意keys的第1位和ptr的0位对应，keys的第2位和ptr的1位对应，以此类推
 CFTree keys[M+2];
 BTNode *parent;
 BTNode *ptr[M+2];
}*BTree;

//全局变量root，保存B-树的根结点
BTree root;

//叶子结构体，用于将B-树的叶子节点连起来
typedef struct BLeafNode
{
 BTree leaf;
 BLeafNode *next;
}*BLeafTree;
//beginLeaft保存起始叶子节点的位置
BLeafTree beginLeaf;

//通过一条记录创建一个CF
CFTree createCF(vector<string> data)
{
 //if(NULL == data)
  //return NULL;
 int i;
 AttTree att = NULL;
 CFTree cft = new CFNode();
 cft->count = 1;
 for(i = 0; i < data.size(); i++)
 {
  att = new AttNode();
  //每个att都带头结点
  cft->atts[i] = att;
  att = new AttNode();
  att->count = 1;
  att->data = data[i];
  att->next = NULL;
        cft->atts[i]->next = att;
 }

 return cft;
}

//创建一个空的CF，方便mergeCF函数
CFTree createCF()
{
 int i;
 AttTree att = NULL;
 CFTree cft = new CFNode();
 cft->count = 0;
 for(i = 0; i < attNum; i++)
 {
  att = new AttNode();
  att->next = NULL;
  //每个att都带头结点
  cft->atts[i] = att;
 }

 return cft;
}

 

//计算两个CF间的距离
//两个簇间的距离，如果是数字型的好很好求，就是两个簇的簇中心距离，但是对于非数字型的（既字符型）
//簇中心是不好（无法）求出来的。那么就得用另外一种方式表示。现有簇A，簇B，簇的记录的数目分别是
//M，N（M>=1，N>=1）。以第一维属性为列。集合S是A，B的取值。遍历 ,距离是 ，其中A 中的个数是ai，
//B中的个数是bi，0<=ai<=M,0<=bi<=N，则0<= <=1，取0等情况好理解，取1的情况是要么 =1并且 =0，要么相反。
//假如是前者，簇A取值只有一种情况就是i，而簇B又没有取i这种情况，那么可知 (S减去i的补集)全是簇B要取的值，
//假如为j,k,l。则dj= = ,dk= = ,dl= = ,且：dj+dk+dl =1，此时A，B没有一条数据重合，当遍历所有后，
//有di+dj+dk+dl=2，那么最终结果是1，这也是两个簇间最大的距离。若两个簇在各个值处按比例重合（ =0），
//则等于0。考虑各维情况。设空有L维，则用d= 一般x取2，即欧式距离,m表示维数。这里 0<=di<=1，可知0<=d<=1。
//上面这短话是从birch_蒋盛益.doc复制过来的，里面有些图片，无法显示，还是直接去看那个doc吧。
//同一维的的AttNode中的值已经递增排序，
double getDistance(CFTree a,CFTree b)
{
 double d,k = 0;
 int i,j;
 AttTree aa, ba;
 //字符型
    if(charType == true)
 {
  //距离是一维一维计算的
  for(i = 0; i < attNum; i++)
  {
   //跳过头结点
   aa = a->atts[i]->next;
   ba = b->atts[i]->next;
   d = 0;
   //同一维的的AttNode中的值已经递增排序
   while(NULL != aa && NULL != ba)
   {
    if( aa->data == ba->data)
    {
     d += abs(((double)aa->count)/a->count - ((double)ba->count)/b->count);
     aa = aa->next;
     ba = ba->next;
    }
    else if( aa->data < ba->data)
    {
     d += ((double)aa->count)/a->count;
     aa = aa->next;
    }
    else
    {
     d += ((double)ba->count)/b->count;
     ba = ba->next;
    }
   }
   while(NULL != aa)
   {
    d += ((double)aa->count)/a->count;
    aa = aa->next;
   }
   while(NULL != ba)
   {
    d += ((double)ba->count)/b->count;
    ba = ba->next;
   }

   k += pow(d/2,2);
  }
 }
 else
 {
  //数字型
  double d1,d2;
  for(i=0; i < attNum; i++)
  {
   //跳过头结点
   aa = a->atts[i]->next;
   ba = b->atts[i]->next;
   d1 = 0;
   //获得该维的平均值
   while(NULL != aa)
   {
    d1 += atoi(aa->data.c_str()) * aa->count;
    aa = aa->next;
   }
   d1 = d1/a->count;
   d2 = 0;
   //获得该维的平均值
   while(NULL != ba)
   {
    d2 += atoi(ba->data.c_str()) * ba->count;
    ba = ba->next;
   }
   d2 = d2/b->count;
   //
   k += pow(d1-d2,2);
  }
 }

 return sqrt(k/attNum);
}

//在B-树（root是跟节点)中找到离cft最近的那个CF和BTree，分别保存在cfp和bt中，然后返回距离
double getMinCF(BTree root, CFTree cft, CFTree &cfp, BTree &bt)
{
 if(NULL == root || NULL == cft)
  return NULL;
 double b,d;
 int i,j;
 BTree t = root;
    //先访问完整个BTree，找到最近的那个关键字，再在这个关键字的下一层节点中查找，直到叶子节点
 while(NULL != t)
 {
  bt = t;
  d = 10000;
  for(i = 1; i <= t->keyNum; i++)
  {
   b = getDistance(t->keys[i], cft);
   if( b < d)
   {
    d = b;
    j = i;
    cfp = t->keys[i];
   }
  }
  t = t->ptr[j-1];
 }

 return d; 
}

//将b合并到a中
void mergeCF(CFTree &a, CFTree b)
{
 //一维一维的合并
 int i;
 AttTree aa,ba,p,t;
 a->count += b->count;
 for(i = 0; i < attNum; i++)
 {
  aa = a->atts[i]->next;
  ba = b->atts[i]->next;
  //保存头结点，方便把ba插入到aa前面去
  t = a->atts[i]; 
 
  //同一维的AttNode中的值已经递增排序，
  while( NULL != aa && NULL != ba)
  {
   if(aa->data == ba->data)
   {
    aa->count += ba->count;
    t = aa;
    aa = aa->next;
    ba = ba->next;
   }
   else if( aa->data < ba->data)
   {
    t = aa;
    aa = aa->next;
   }
   else
   {
    //要将ba插入到aa前面去，即插在t的后面
    p = new AttNode();
    p->count = ba->count;
    p->data = ba->data;
    p->next = aa;
    t->next = p;
    t = p;

    ba = ba->next;
   }
  }
  //ba还有剩余
  while(NULL != ba)
  {
   //要将ba添加到aa的后面
   p = new AttNode();
   p->count = ba->count;
   p->data = ba->data;
   p->next = NULL;
   t->next = p;
   t = p;

   ba = ba->next;
  }

 }
}

//更新BTree中ptr指针等于a的那个CF,把b添加到那个CF中
//a的父节点不为空
void updateBTree(BTree a, CFTree b)
{
 int i;
 BTree t = a->parent;
 for(i = 1; i <= t->keyNum; i++)
 {
  if(t->ptr[i-1] == a)
  {
   mergeCF(t->keys[i], b);
   break;
  }
 }
 if( NULL != t->parent)
 {
  updateBTree(t,b);
 }
}

//释放节点a的资源
void freeBTree(BTree a)
{
 delete a;
}

//a分离成两个BTree，至到根节点
void apartBTree(BTree a, CFTree b,bool isFirst)
{
 CFTree p,q;
 BTree c,d,r;
 int i,j,k,l;
 double d1,d2 = 0;

 //选两个相距最远的CFTree,保存在k,l中
 for(i = 1; i < a->keyNum; i++)
  for(j = i+1; j <= a->keyNum; j++)
  {
   d1 = getDistance(a->keys[i],a->keys[j]);
   if( d2 < d1)
   {
    d2 = d1;
    k = i;
    l = j;
   }
  }
 //以k,l生成两个BTree
 c = new BTNode();
 d = new BTNode();
 c->keyNum = 1;
 p = createCF();
 mergeCF(p,a->keys[k]);
 c->keys[1] = p;
 c->ptr[0] = a->ptr[k-1];
 if(NULL != a->ptr[k-1])
 {
  a->ptr[k-1]->parent = c;
 }
 d->keyNum = 1;
 p = createCF();
 mergeCF(p,a->keys[l]);
 d->keys[1] = p;
 d->ptr[0] = a->ptr[l-1];
 if(NULL != a->ptr[l-1])
 {
  a->ptr[l-1]->parent = d;
 }
 
 //静态变量，因为只有第一次分裂时需要调整叶子节点，以后分裂都不是在叶子节点上了
 if(isFirst)
 {
  BLeafTree t1,t2,t3;
  //找到指向a的叶子节点指针，保存在t1中
  for(t1 = beginLeaf; t1->leaf != a; t1 = t1->next);
  //将叶子节点重新穿起来
  t2 = t1->next;
  t1->leaf = c;
  t3 = new BLeafNode();
  t3->leaf = d;
  t3->next = t2;
  t1->next = t3;
 }

 //再将a中剩下的CF分配到离它近的c或者d中,既k或者l中
 for(i = 1; i <= a->keyNum; i++)
 {
  if(i == k || i == l)
   continue;
  d1 = getDistance(a->keys[k],a->keys[i]);
  d2 = getDistance(a->keys[l],a->keys[i]);

  //将a->keys[i]添加到c中
  if( d1 <= d2)
  {
   c->keyNum++;
   c->keys[c->keyNum] = a->keys[i];
   c->ptr[c->keyNum-1] = a->ptr[i-1];
   if(NULL != a->ptr[i-1])
   {
    a->ptr[i-1]->parent = c;
   }
  }
  //将a->keys[i]添加到d中
  else
  {
   d->keyNum++;
   d->keys[d->keyNum] = a->keys[i];
   d->ptr[d->keyNum-1] = a->ptr[i-1];
   if(NULL != a->ptr[i-1])
   {
    a->ptr[i-1]->parent = d;
   }
  }   
 }
 
 //更新a的父节点
 //如果a没有父节点，即a就是父节点，则创建新的父节点，停止更新下去
 if( NULL == a->parent)
 {
  //创建新的父节点r，它两个关键字
  r = new BTNode();
  r->keyNum = 2;
  r->parent = NULL;
  r->ptr[0] = c;
  c->parent = r;
  r->ptr[1] = d;
  d->parent = r;
  //将c中所有CF合并到p中，再将p作为r的一个关键字
  p = createCF();
  for(i = 1; i <= c->keyNum; i++)
  {
   mergeCF(p,c->keys[i]);
  }
  r->keys[1] = p;
  //将d中所有CF合并到p中，再将p作为r的一个关键字
  p = createCF();
  for(i = 1; i <= d->keyNum; i++)
  {
   mergeCF(p,d->keys[i]);
  }
  r->keys[2] = p;

  //重新指定根节点
  root = r;
  
  //释放a的资源
  freeBTree(a);

  return;
 }
 //a有父节点
 //获得父节点
 r = a->parent;
 //找到a在c中关键字的位置
 for(i = 1; i <= r->keyNum; i++)
 {
  if( a == r->ptr[i-1])
   break;
 }
 //将该关键字删除，根据c,d创建两个新的关键字
 //具体做法是将从第i位关键字开始的所有关键字和对应的ptr指针后移一维，
 //再在原第i和i+1位放入新的关键字和新的ptr指针
 r->keyNum++;
 for(j = r->keyNum; j > i+1; j--)
 {
  r->keys[j] = r->keys[j-1];
  r->ptr[j-1] = r->ptr[j-2];
 }
 //将c中所有CF合并到p中，再将p作为r的一个关键字
 p = createCF();
 for(j = 1; j <= c->keyNum; j++)
 {
  mergeCF(p,c->keys[j]);
 }
 r->keys[i] = p;
 r->ptr[i-1] = c;
 c->parent = r;
 //将d中所有CF合并到p中，再将p作为r的一个关键字
 p = createCF();
 for(j = 1; j <= d->keyNum; j++)
 {
  mergeCF(p,d->keys[j]);
 }
 r->keys[i+1] = p;
 r->ptr[i] = d;
 d->parent = r;

 //释放a的资源
 freeBTree(a);

 //如果c中的关键字个数大于M则递归
 if(r->keyNum > M)
 {
  apartBTree(r,b,false);
 }
 //此时，又要更新r节点了
 else if(NULL != r->parent)
 {
  updateBTree(r,b);
 }
 //否则停止更新
}

//按层显示树信息,root是根节点
void displayBTree(BTree root, int n)
{
 int i,j,k;
 BTree t,p;
 t = root;
 j = 0;
 for(i = 1; i <= t->keyNum; i++)
 {
  j += t->keys[i]->count;
 }
 if(n != j)
 {
  cout << "j=" << j << ",n=" << n << ",";
 }
 if(NULL != t->ptr[0])
 {
  for(i = 0; i < t->keyNum; i++)
  {
   p = t->ptr[i];
   displayBTree(p,t->keys[i+1]->count);
  }
 }
}

//创建B-树
void createBTree()
{
 //临时变量
 CFTree cft,cfp;
 AttTree att;
 BTree bt,t;
 int i,j,k;
 double d;
 //读文件，每条记录保存在data里面
 vector<string> data;
    bool isFirst = true;
 char str[30];
 char ch;
 FILE *infile;
 //const char *FileName= "mushroom.data";
 const char *FileName= "chr10.cns5.txt";
 if(!(infile=fopen(FileName,"r")))
 {
  printf("数据文件不存在！\n");
  exit(0);
 }
 //保存记录条数
 k = 0;
 while(!feof(infile))
 {
  data.clear();
  //renhu:一条记录
  //保存维数
  i = 0;
        while(!feof(infile) && i<attNum)
  {
   j=0;
   //renhu:该条记录的一个维上的值
   do
   {
    ch=getc(infile);
    str[j++]=ch;
   }while(ch!=',' && ch!='\n' && !feof(infile) );
   str[j-1]='\0';
   data.push_back(str);
   i++;
  }
  k++;
 
  //第一条记录要特殊处理
  if(isFirst)
  {
   //用第零条记录创建一个CF
   cft = createCF(data);
   
   //创建根节点
   root = new BTNode();
   root->keyNum = 1;
   root->keys[1] = cft;
   root->parent = NULL;

   //构造叶子节点信息
   beginLeaf = new BLeafNode();
   beginLeaf->leaf = root;
   beginLeaf->next = NULL;

   isFirst = false;
   continue;
  }

  //if(k == 100000)
  // break;
  displayBTree(root, k-1);
  //离最近CF的距离
  d = 1000000;
  //把每条记录当做一个CF讨论
  cft = createCF(data);
  //cfp保存最近的CF,bt保存最近的BTree
  d = getMinCF(root, cft, cfp, bt);
  //下面分3种情况讨论
  //直接把cfp合并到cft，然后从bt的父节点起更新
  if(d <= minDis)
  {
   //将cft合并到cfp中
   mergeCF(cfp, cft);
   if( NULL != bt->parent)
   {
    updateBTree(bt, cft);
   }   
  }
  //把cft作为一个新的CF放在bt中，然后从bt的父节点起更新
  else if( bt->keyNum < M)
  {
   bt->keyNum += 1;
   bt->keys[bt->keyNum] = cft;   
   if( NULL != bt->parent)
   {
    updateBTree(bt, cft);
   }   
  }
  //把cft作为一个新的CF放在bt中，然后从bt起分裂至根节点
  else
  {
   bt->keyNum += 1;
   bt->keys[bt->keyNum] = cft; 
   apartBTree(bt, cft,true);
  }
 }

 cout << "完成了！"<< endl;
}

//每个CF作为一个簇挖掘
void miningByCF()
{
 BLeafTree ltemp = beginLeaf;
 BTree ttemp = NULL;
 CFTree ctemp = NULL;
 AttTree atemp = NULL;
 int btNum =0;
 int cfNum = 0;
 int sum = 0;
 do
 {
  ttemp = ltemp->leaf;
  cout << "第 " << ++btNum << " 个BTNode，有 " << ttemp->keyNum << " 个簇。" << endl;
  cfNum = 0;
  for(int i=1; i <= ttemp->keyNum; i++)
  {
   ctemp = ttemp->keys[i];
   sum += ctemp->count;
   cout << "第 " << ++cfNum << " 个簇有 " << ctemp->count << " 条记录，" << endl;
   if(ctemp->count < minClusters)
   {
    cout << "这个簇数据太少，属于异常簇，请注意" << endl;
   }
   for(int j=0; j < attNum; j++)
   {
    cout << "第 " << j+1 << " 维属性有中取" << endl;
    atemp = ctemp->atts[j]->next;
    while(atemp != NULL)
    {
     cout << "值为 " << atemp->data << "有 " << atemp->count << "次，在该簇中的比例是 " << (double)atemp->count/ctemp->count << endl;
     atemp = atemp->next;
    }
   }
  }
 }while(ltemp=ltemp->next);
 cout << "共有 " << sum << " 条记录" << endl;
}
void getHeuristicThreshold()
{
}
int _tmain(int argc, _TCHAR* argv[])
{
 time_t timeBegin,timeEnd,timeCost;
 time(&timeBegin);
    cout  << "开始创建B-树的时间是：" << ctime(&timeBegin) << endl;
 createBTree();

 miningByCF();
 time(&timeEnd);
 cout << "完成创建B-树的时间是：" << ctime(&timeEnd) << "耗时：" << timeEnd -timeBegin << "秒" << endl;
  
 
 return 0;
}

注：这几个博客的作者都是机器学习的，他们的文章也不错
Rocchio算法 http://blog.csdn.net/sulliy/article/details/6670980
http://blog.csdn.net/sulliy/article/category/852041
面向对象设计模式 http://blog.sina.com.cn/s/articlelist_1610791280_4_1.html
各种数据挖掘算法和搜索算法
http://blog.sina.com.cn/s/articlelist_1610791280_3_1.html