BIRCH层次聚类优化算法(平衡迭代规约聚类树

大家好，欢迎来到IT知识分享网。

BIRCH算法(平衡迭代削减聚类法)：聚类特征使用3元组进行一个簇的相关信息，通过构建满足分枝因子和簇直径限制的聚类特征树来求聚类，聚类特征树其实是一个具有两个参数分枝因子和类直径的高度平衡树；分枝因子规定了树的每个节点的子女的最多个数，而类直径体现了对这一类点的距离范围；非叶子节点为它子女的最大特征值；聚类特征树的构建可以是动态过程的，可以随时根据数据对模型进行更新操作。

优缺点：

              1） 节约内存，所有的样本都在磁盘上，CF Tree仅仅存了CF节点和对应的指针。

　　　　2 )   聚类速度快，只需要一遍扫描训练集就可以建立CF Tree，CF Tree的增删改都很快。

　　　　3 )   可以识别噪音点，还可以对数据集进行初步分类的预处理。

只适合分布呈凸形或者球形的数据集、需要给定聚类个数和簇之间的相关参数；

节点的CF有限制可能导致，最终的聚类结果与真实值不太一致

BIRCH算法底层是构建一个类似于平衡B+树，一般将它称之为聚类特征树(Clustering Feature Tree，简称CF Tree)。这颗树的每一个节点是由若干个聚类特征(Clustering Feature，简称CF)组成。CF是一个三元组（N,LS,SS) N表示在这个CF表示的集合中表示的样本数量，LS是这些所有样本各个特征属性值的和，NS表示各个属性的平方和

假定簇C1中有两个点（1，2，3），（3，2，1），簇C2有三个点（1，1，2），（2，2，1），（2，1，2），簇3由C1和C2构成，则：CF1=（2，（1+3，2+2，3+1），（ 1^2+3^2，2^2+2^2,3^2+1^2））=（2，（4，4，4），（10，8，10））

CF2=（3，（1+2+2，1+2+1，2+1+2），（1^2+2^2+2^2,1^2+2^2+1^2,2^2+1^2+2^2 ））=（3，（5，4，5），（9，6，9））

因此得到CF3为：

CF3=（2+3，（4+5，4+4，4+5），（10+9，8+6，10+9））=（5，（9，8，9），（19，14，19））

 CF树构造中是不断插入对象（簇）的过程，首先需要定义参数：分支因子B和阈值T，这些分支因子不能单纯理解为数据点，而是一个子簇，B则是定义了非叶节点子女是最大数目，阈值T是限定叶子节点中字簇的最大直径。且CF随B的变大而减小。

  识别合适的叶节点：从根节点开始逐层下降，查找最近的孩子节点，直至也节点。

  修改叶节点：被修改的叶节点和插入的对象Enf合并后的节点数与B比较，合并后的簇直径与阈值T比较，是否分裂。

  修改叶节点的路径：将Enf插入到节点（簇）中，到达叶节点的路径上的每个节点的CF信息需要进行更新。

  每分裂后随后便有一个合并步。

BIRCH聚类树的构建实际上就是插入一个样本点，且BIRCH聚类树不依赖k值的给定，但是给定k值最好，不给定k值，最终的CF-TREE的叶子节点数就是簇的数目。BIRCH算法适合大规模数据集，与Mini-Batch K-Means算法相比，BIRCH更加适合类别较多的情况（k值比较大的情况）。但是如果特征维度超过20~30的时候，尽量不要使用birch算法，降维或者其他方法再使用都可以。