# 高级聚类

##### FuzzyKmeans

```package kmeans;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
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 {
double len = 0;
double vector = 0;
int size=0;
try {
File f = new File(path);
String word;
String line="";
String[] outline=new String[210];
double[] vectors = null;
int count=0;
if(count%100000==0){
}
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);
String line="";
List<String> center=new ArrayList<String>();
if(wordMap.containsKey(line)){
}
}
br.close();
return center;
}
}```

```package kmeans;
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.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("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();

List<String> center=new ArrayList<String>();
if(point_path!=null){
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);
for (int i = 0; i < cArray.length; i++) {
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代价。

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）

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

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

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

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

######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树的例子如图所示：

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

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

BIRCH算法流程如下图所示：

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

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

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

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;```

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

1007 篇文章105 人订阅

0 条评论

## 相关文章

25030

8020

26140

20030

62510

28290

54750

31770

45330

### Q111 Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth. The minimum depth is the number of ...

26940