CluStream算法优缺点 优点： 提出了两阶段聚类框架，算法能适应数据流快速、有序无限、单遍扫描的特点。能够发掘数据流潜在的演化特性。 缺点： 1、不能发现任意形状的簇； 2、不能很好地识别离群点； 3、对高维数据聚类质量下降；

数据流聚类相关知识以及Stream、CluStream、Birch算法的讲解

为初学者提供BIRCH算法的基本知识，原理、优缺点介绍。

层次聚类方法的改进--BIRCH BIRCH（利用层次方法的平衡迭代归约和聚类）是一个综合的层次聚类方法，它用聚类特征和聚类特征树（CF）来概括聚类描述。该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。CF树是一个具有两个参数分支因子B和阂值T的高度平衡树，存储了层次聚类的聚类特征。分支因子定义了每个非叶节点孩子的最大数目，而阈值给出了存储在树的叶子节点中的子聚类的最大直径。 BIRCH算法的工作过程包括两个阶段： 阶段一：BIRCH扫描数据库，建立一个初始存放于内存的CF树，它可以被看作数据的多层压缩，试图保留数据内在的聚类结构。随着对象的插入，CF树被动态地构造，不要求所有的数据读入内存，而可在外存上逐个读入数据项。因此，BIRTH方法对增量或动态聚类也非常有效。 阶段二：BIRCH采用某个聚类算法对CF树的叶结点进行聚类。在这个阶段可以执行任何聚类算法，例如典型的划分方法。 BIRCH算法试图利用可用的资源来生成最好的聚类结果。通过一次扫描就可以进行较好的聚类，故该算法的计算复杂度是O(n)，n是对象的数目。

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。

基于层次的聚类算法（以BIRCH算法为例） 算法形式化描述 输入：包含N个对象的数据集合D 输出：簇集合。

针对传统的BIRCH算法用直径来控制聚类的边界，对非球形聚类效果不佳，甚至会把非球状的簇分割为不同簇这一缺点，对BIRCH算法进行改进，改进算法首先建立多棵CF树，每棵CF树代表一个簇，并结合DBSCAN算法的密度可达的思想。该算法能对任意形状的簇进行准确的聚类。实验表明，算法能通过一次扫描进行有效聚类，时间复杂度与BIRCH算法相同，对大规模数据集具有较高的处理速度，实现了动态聚类，并可以准确地对任意形状的簇进行聚类并发现噪声点。

基于层次的聚类算法（以BIRCH算法为例） 输入：包含N个对象的数据集合D 输出：簇集合。

采用matlab工具箱将聚类算法中的层次算法：Birch实现

BIRCH层次聚类算法，里面包括数据集，可直接测试。这种算法效率高，可伸缩，缺点是聚类效果相比其他算法来说略差，不过其思想值得借鉴