BIRCH聚类算法
BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies)天生就是为处理超大规模(至少要让你的内存容不下)的数据集而设计的,它可以在任何给定的内存下运行。关于BIRCH的更多特点先不介绍,我先讲一下算法的完整实现细节,对算法的实现过程搞清楚后再去看别人对该算法的评价才会感受深刻。 你不需要具备B树的相关知识,我接下来会讲得很清楚。 BIRCH算法的过程就是要把待分类的数据插入一棵树中,并且原始数据都在叶子节点上。这棵树看起来是这个样子: 在这棵树中有3种类型的节点:Nonleaf、Leaf、MinCluster,Root可能是一种Nonleaf,也可能是一种Leaf。所有的Leaf放入一个双向链表中。每一个节点都包含一个CF值,CF是一个三元组,其中data point instance的个数,和是与数据点同维度的向量,是线性和,是平方和。比如有一个MinCluster里包含3个数据点(1,2,3),(4,5,6),(7,8,9),则 N=3, =(1+4+7,2+5+8,3+6+9)=(12,15,18), =(1+16+49,4+25+64,9+36+81)。 就拿这个MinCluster为例,我们可以计算它的 簇中心 簇半径 簇直径 我们还可以计算两个簇之间的距离,当然你也可以使用D0,D1,D3等等,不过在这里我们使用D2。 有意思的是簇中心、簇半径、簇直径以及两簇之间的距离D0到D3都可以由CF来计算,比如 簇直径 簇间距离,这里的N,LS和SS是指两簇合并后大簇的N,LS和SS。所谓两簇合并只需要两个对应的CF相加那可 CF1 + CF2 = (N1 + N2 , LS1 + LS2, SS1 + SS2) 每个节点的CF值就是其所有孩子节点CF值之和,以每个节点为根节点的子树都可以看成 是一个簇。 Nonleaf、Leaf、MinCluster都是有大小限制的,Nonleaf的孩子节点不能超过B个,Leaf最多只能有L个MinCluster,而一个MinCluster的直径不能超过T。 算法起初,我们扫描数据库,拿到第一个data point instance--(1,2,3),我们创建一个空的Leaf和MinCluster,把点(1,2,3)的id值放入Mincluster,更新MinCluster的CF值为(1,(1,2,3),(1,4,9)),把MinCluster作为Leaf的一个孩子,更新Leaf的CF值为(1,(1,2,3),(1,4,9))。实际上只要往树中放入一个CF(这里我们用CF作为Nonleaf、Leaf、MinCluster的统称),就要更新从Root到该叶子节点的路径上所有节点的CF值。 当又有一个数据点要插入树中时,把这个点封装为一个MinCluster(这样它就有了一个CF值),把新到的数据点记为CF_new,我们拿到树的根节点的各个孩子节点的CF值,根据D2来找到CF_new与哪个节点最近,就把CF_new加入那个子树上面去。这是一个递归的过程。递归的终止点是要把CF_new加入到一个MinCluster中,如果加入之后MinCluster的直径没有超过T,则直接加入,否则譔CF_new要单独作为一个簇,成为MinCluster的兄弟结点。插入之后注意更新该节点及其所有祖先节点的CF值。 插入新节点后,可能有些节点的孩子数大于了B(或L),此时该节点要分裂。对于Leaf,它现在有L+1个MinCluster,我们要新创建一个Leaf,使它作为原Leaf的兄弟结点,同时注意每新创建一个Leaf都要把它插入到双向链表中。L+1个MinCluster要分到这两个Leaf中,怎么分呢?找出这L+1个MinCluster中距离最远的两个Cluster(根据D2),剩下的Cluster看离哪个近就跟谁站在一起。分好后更新两个Leaf的CF值,其祖先节点的CF值没有变化,不需要更新。这可能导致祖先节点的递归分裂,因为Leaf分裂后恰好其父节点的孩子数超过了B。Nonleaf的分裂方法与Leaf的相似,只不过产生新的Nonleaf后不需要把它放入一个双向链表中。如果是树的根节点要分裂,则树的高度加1。
- 1
- 蟹蛛2023-07-25作者对BIRCH聚类算法进行了良好的整合和概括,为读者提供了全面而实用的学习资料。
- 王佛伟2023-07-25这篇文件以简洁清晰的语言,介绍了BIRCH聚类算法的原理和应用,对初学者来说很友好。
- 今年也要加油呀2023-07-25文中提供的案例研究充分展示了BIRCH聚类算法在大数据处理中的高效性和准确性。
- 空城大大叔2023-07-25作者对BIRCH聚类算法的优点和局限进行了客观的评述,让人对其在实际应用中的表现有了更清晰的认识。
- 销号le2023-07-25本文系统地介绍了BIRCH聚类算法的算法流程和核心思想,使读者能够轻松理解并运用到实际项目中。
- 粉丝: 161
- 资源: 24
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 【全年行事历】行政部全年活动计划表- A公司.xls
- 【全年行事历】活动复盘表.xlsx
- 【全年行事历】活动推广进度表.xlsx
- 【全年行事历】旅游团建行程安排表-XX山.xlsx
- 【全年行事历】旅行团建活动方案.pptx
- 【全年行事历】某公司团建活动方案-【户外烧烤】.doc.baiduyun.uploading.cfg
- 【全年行事历】企业文化年度活动计划表.xlsx
- 【全年行事历】年度员工关怀计划表.xlsx
- 【全年行事历】年度行政活动计划表.xlsx
- 【全年行事历】企业团队建设活动策划.pptx
- 【全年行事历】全年活动计划.xls
- 【全年行事历】团队建设企业文化行事历——工作计划.xlsx
- 【全年行事历】企业员工夏季团建活动策划一天.pptx
- 【全年行事历】团建费用分析.xlsx
- 【全年行事历】团建行程安排及出行清单.xlsx
- 【全年行事历】团建活动采购预算清单.xlsx