加载中…
个人资料
renhuyy
renhuyy
  • 博客等级:
  • 博客积分:0
  • 博客访问:101,451
  • 关注人气:110
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

Birch算法

(2011-01-13 21:30:45)
标签:

数据挖掘

聚类

birch

分类: 聚类

    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-树画出来:

Birch算法

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

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

  Birch算法
从第二条记录起就具有一般性了,插入第二条记录时,用该条记录创建一个临时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算法
    Birch算法也有不足的地方,第一,它对输入数据的先后顺序敏感,第二,每个CFNode将各条记录的数据相同的部分合并了,不能还原成原来的记录了。但是我们还是很方便求出每个簇的平均值等信息。




0

阅读 评论 收藏 转载 喜欢 打印举报/Report
前一篇:kmeans算法源码
后一篇:Birch算法源码
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    < 前一篇kmeans算法源码
    后一篇 >Birch算法源码
      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有