层次聚类方法--BIRCH

姓名：梁祥        学号：17021210935

【嵌牛导读】：层次聚类方法作为一种能够在一定程度上将聚类过程显化的聚类方法，在很多时候都能大显身手，因此在这里介绍一下层次聚类方法的主要思想，并以BIRCH算法为例进行了详细分析。

【嵌牛鼻子】：层次聚类，BIRCH

【嵌牛提问】：层次聚类过程中，从头到脚与自下而上有区别吗？在聚类的过程中数据是怎么慢慢分散或者逐渐聚拢的呢？

【嵌牛正文】：

一、层次聚类

层次的聚类方法将数据对象组成一棵聚类的树。根据层次分解是底向上, 还是自顶向下形成, 层次的聚类方法可以进一步分为凝聚的(agglomerative)和分裂的(divisive)层次聚类。

凝聚的和分裂的层次聚类图示：

层次聚类的主要缺点：

不具有很好的可伸缩性：时间复杂性至少是平方级；合并和分裂的决定需要检查和估算大量的对象或簇；不能撤销已做的处理，聚类之间不能交换对象。如果某一步没有很好地选择合并或分裂的决定，可能会导致低质量的聚类结果。该算法的特点是能利用有限的内存资源完成对大数据集的高质量的聚类，同时通过单遍扫描数据集能最小化I/O代价。

二、 改进层次方法的聚类质量的方法:

将层次聚类和其他的聚类技术进行集成, 形成多阶段聚类。其中，BIRCH方法使用CF-tree对对象进行层次划分，然后采用其他的聚类算法对聚类结果进行求精。

2.1 两个重要的概念：

聚类特征（Clustering Feature，CF）

聚类特征树（Cluttering Feature Tree，CF树）

2.2 聚类特征

聚类特征(CF)是一个三元组，给出对象子类的信息的汇总描述。

设某个子类中有N个d维的点或对象，则该子类的CF定义如下：

其中，N表示数据点数目，LS表示全体数据的和，SS表示全体数据的平方和。从统计学的观点来看，聚类特征是对给定子类统计汇总: 子聚类的0阶, 1阶和 2阶矩。记录了计算聚类和有效利用存储的关键度量, 并有效地利用了存储,因为它汇总了关于子类的信息，而不是存储所有的对象。

2.3 聚类特征树

CF 树是高度平衡的树，它存储了层次聚类的聚类特征。树中的非叶节点有后代或“孩子”，非叶节点存储了其孩子的CF的总和，即汇总了关于其孩子的聚类信息。CF树有两个参数 ----影响CF树的大小：分支因子B，定义非树叶节点的孩子的最大个数；阈值T:，给出了存储在树的叶子节点中的子类的最大直径。

CF tree的结构类似于一棵B-树，它有3个参数：内部节点平衡因子B，叶节点平衡因子L，簇直径阈值T。树中每个Nlonleaf节点最多包含B个孩子节点，Leaf最多只能有L个MinCluster（初始划分子簇），而一个MinCluster的直径不能超过T。

CF树构造过程：

(1)从根节点开始，自上而下选择最近的孩子节点；

(2)到达叶子节点后，检查最近的元组CFi能否吸收此数据点；

    是，更新CF值；

    否，是否可以添加一个新的元组；

        是，添加一个新的元组；

        否则，分裂最远的一对元组，作为种子，按最近距离重新分配其它元组；

(3)更新每个非叶节点的CF信息，如果分裂节点，在父节点中插入新的元组，检查分裂，直到root。

算法起初，我们扫描数据库，拿到第一个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。

重建过程从旧树的叶子节点建造一个新树。这样，重建树的过程不需要重读所有的对象 ----建树只需读一次数据。在阶段三和四采用任何聚类算法，例如典型的划分方法。

2.3 BIRCH的性能

支持增量聚类：（1）因为它对每一个数据点的聚类的决策都是基于当前已经处理过的数据点，而不是基于全局的数据点。（2）线性可伸缩性: 计算复杂性O(n), 单遍扫描, 附加的扫描可以改善聚类质量。（3）具有较好的聚类质量。

2.4 缺点

（1）只能处理数值数据；（2）对数据的输入次序敏感；（3）CF树结点不总是对应于[用户考虑的]自然簇(参数B和T)；（4）簇非球形时效果不好(使用半径/直径控制簇边界).