您现在的位置是:主页 > 免费资料大全 > 挑子学习笔记:BIRCH层次聚类

http://spiderturk.com/tz/116.html

挑子学习笔记:BIRCH层次聚类

时间:2019-08-14 00:41  来源:未知  阅读次数: 复制分享 我要评论

  转载请标明出处:

  本文是“挑子”在进修BIRCH算法过程中的笔记摘录,文中不乏一些小我理解,不妥之处望多加斧正。

  BIRCH利用聚类特征归纳综合描述各簇的消息,其定义如下:

  按照上述定义有如下定理:

  CF树是等高树,有三个参数:枝均衡因子$\beta$(branch factor)、叶均衡因子$\lambda$(leaf factor)和空间阈值$\tau$(threshold)。CF树由根节点(root node)、枝节点(branch node)和叶节点(leaf node)形成(如图 1所示),非叶节点(nonleaf node)中包含不多于$\beta$个形如$[\vec{CF}_i, child_i] $的元项(entry),此中$\vec{CF}_i $暗示该节点上第$i$个子簇的聚类特征消息,指针$child_i $指向该节点的第$i$个子节点。叶节点中包含不多于$\lambda$个形如$[\vec{CF}_i] $的元项,此外每个叶节点中都包含指针$prev$指向前一个叶节点和指针$next$指向后一个叶节点。每个节点都代表一个由各元项中聚类特征对应子簇(sub-cluster)归并而成的簇。空间阈值$\tau$用于限制叶节点的子簇的大小,即所有叶节点的各元项对应子簇的直径$\delta$或半径$\rho$不得大于$\tau$。

  图 1:聚类特征树

  图 1中各节点及其元项代表的簇间的关系如图 2所示。节点1代表的簇中包含了当前所无数据点,该簇分成了6个部门:别离是$\vec{CF}_6 $、$\vec{CF}_7 $、$\vec{CF}_8 $、$\vec{CF}_9 $、$\vec{CF}_{10} $和$\vec{CF}_{11} $对应的小簇。CF树上分歧条理的节点及其包含数据点的范畴由分歧颜色暗示。需要申明的是,CF树上不保留任何数据点,仅有树的布局消息以及相关的聚类特征消息,因而CF树能够达到压缩数据的结果。

  图 2:聚类特征树(图 1)对应的簇划分

  CF树的发展由一根空树起头,是逐一插入一系列簇[b]的聚类特征到CF树的过程,方式步调如下:

  步调1(初始化):初始化CF树为空树,置树高度$H=0 $,设置枝均衡因子$\beta $、叶均衡因子$\lambda $和空间阈值$\tau $的值,从半径$\rho $和直径$\delta $当选择一个作为簇漫衍大小的统计量,记为$\varsigma $,从$d_0 \sim d_4 $当选择一个作为簇间距离的怀抱,记为$d $;

  考虑到偏斜数据可能对聚类精度或者CF树节点空间操纵率形成影响,在步调4中添加树枝精修步调,以降低偏斜数据的影响,“补葺路径上树枝树枝精修”步调如下:

  图 3:簇$C $的空间位置示企图

  图 4:CF树的插入与修剪

  当所无数据点都插入到CF树上,即CF树发展完毕后,所有叶元项对应的子簇,将作为根本的最小簇,完成后续的聚类过程。

  BIRCH算法对CF树进行瘦身次要有两个方面的需求:1)在将数据点插入到CF树的过程中(见第3节“CF树的发展”),用于存储CF树节点及其相关消息的内存无限,导致部门数据点发展构成的CF树占满了所有内存,因而需要对CF树进行瘦身(同时添加空间阈值$\tau $)以将余下数据点插入到CF树上;2)CF树发展完毕后,叶元项对应的子簇太小,影响到后续聚类的速度和质量,需要对CF树进行瘦身,以添加叶节点子簇的尺寸,减小叶节点子簇的数量。

  3、在完成路径$\tilde P^c $中所有叶元项的转移后,$\tilde P^c $上的节点将全数成为空节点,此外路径$\tilde P^c $上也可能由于没有插入元项,会连结本来新建的空节点,因而能够删除空节点及路径,以释放空间;

  BIRCH算法的流程分为以下4个阶段:

  1、在内存中建立CF树;

  2、对第1阶段中的CF树进行瘦身(可选步调);

  3、以CF树叶元项对应的子簇为根本,实现数据点的聚类;

  4、对第3阶段的聚类成果进行精修(可选步调)。

  本末节是BIRCH算法的第一阶段,次要使命是在设定内存的限制下,将数据库中的数据对象(数据点)逐一地插入到CF树上,当CF树建立完毕,这棵CF树将包含了数据库的所有聚类特征消息,完成数据压缩。该阶段的具体过程如下:

  若是数据库$\mathfrak D $中没有未被插入的数据点,对潜在离群点进行处置,确定真正的离群点(离群点处置方式可参考后文),本阶段竣事,输出CF树;

  若是内存溢出,添加空间阈值$\tau $(空间阈值的设置方式见后文),并对CF树$\mathcal T $进行瘦身操作,在瘦身之后,将CF树$\mathcal T $中叶节点的稀少元项作为离群点,从CF树$\mathcal T $中临时移至别处(离群点处置方式可参考后文),完毕后,从数据库$\mathfrak D $拔取下一个数据点,反复本步调;

  不然,从数据库$\mathfrak D $拔取下一个数据点,反复本步调。

  5.2 进一步瘦身CF树

  起首,此阶段并非需要。该阶段的次要使命是:当第1阶段中输出的叶元项对应的簇尺寸偏小,与第3阶段当选用的聚类方式不婚配时,需要对第1阶段的输出CF树进行瘦身,以添加用当前续聚类的簇的尺寸。瘦身方式与第4节中方式无异。

  该阶段的聚类能够间接利用现无方法,如k-means和凝结法等,聚类的对象是第1阶段或第2阶段输出的CF树上叶元项对应的所有子簇。

  假设由第1阶段或第2阶段输出的子簇共$M$个:$\{ C_m \}_{m=1,...,M} $,这些子簇的聚类特征都在CF树的建立中获得计较,记为$\{ \vec{CF}_m \}_{m=1,...,M} $,由于聚类特征十分便于怀抱簇的漫衍怀抱和簇间的距离,因而可借助现无方法或者方式思惟,基于聚类特征的计较,对上述$M $个子簇进行二度聚类。如选用的是凝结法,便是逐渐归并上述$M $个子簇中距离比来的2个,直到将所有子簇归并成一个大簇。

  此阶段并非需要。该阶段的实施以第3阶段的输出簇为对象,方式十分简单:以第3阶段的输出簇的核心为种子,以距离比来为原则,从头将数据库$\mathfrak D $中的数据点分布到响应簇中,若有需要可进一步识别和剔除离群点。

  在将数据库中数据点插入到CF树的过程中,一般会给一个较小的空间阈值$\tau $,当内存溢出时,再逐渐添加空间阈值$\tau $,对CF树进行修身,再插入后续数据点。

  假设当前的空间阈值是$\tau_c $,已插入到CF树上的数据点个数为$N_c $,当前CF树的叶元项的个数为$\epsilon_l $,根节点元项对应簇的平均半径为$\bar r_c $.

  找出密度最高的叶节点,寻找方式能够采用贪婪法:从CF树按路径次序逐层找出包含数据点最多的节点,直至叶节点。找到密度最高叶节点后,计较该叶节点中距离比来的两个元项之间的距离$d_{\min} $.

  BIRCH算法预留出必然空间用于潜在离群点的收受接管。在每次对当前CF树进行瘦身之后,需要搜刮叶节点中的稀少子簇,作为离群点放入收受接管空间中。此处的稀少子簇暗示簇内数据点数量远远少于所有簇平均数据点数的叶节点子簇。放入收受接管空间后,需要同步剔除CF树上的相关路径及节点。

  当收受接管空间溢出时,逐一测验考试将潜在离群点插入到现有CF树中,若是某个潜在离群点能够在不添加CF树节点数量的前提下被某个叶元项接收,该潜在离群点将从收受接管空间中取出;不然继续留在收受接管空间中。

  在数据库中所无数据点都被实施插入CF树的操作后,扫描所有潜在离群点,并测验考试插入到CF树中,若是仍未能插入CF树中,能够确定为真正离群点,得以删除。

  [a]不失一般性,可设各数据点为D维列向量,即 。

  [b]一个数据点也能够看作是一个单点的簇。