接下来介绍BFR算法，BFR算法是k均值算法的一个变形，BFR算法的设计目的是为了在高维欧式空间中对数据进行聚类，BFR算法对簇的形状给出了一个非常强的假设，即它们必须满足以质心为期望的正态分布。一个簇的在不同维度的标准差可能不同，但是维度之间必须相互独立，如下图：
内存中除了输入组块之外还包括其他三种对象，废弃集、压缩集和留存集。
在书的原文中，几乎没有讲清楚废弃集和压缩集的区别，这里我找到了另一种解释，如图所示：
DS是废弃集、CS是压缩集、RS是留存集。字面意思是，废弃集中的所有点与质心足够接近，形成了一个簇，我们保存这个簇的简单概要信息；压缩集中的点相互接近，但并不接近任何一个已存在的质心，基本可以理解为没有质心，也不算做是簇，存放的也是这些点呃概要信息，因为不是簇，所以只是点集的概要而不是簇的概要；留存集就是即不能被分配给某个簇，也不会和其他点足够接近而被放到压缩集中，这些点会显式存在。
概括起来，如下图：
对于概要信息，我们用N-SUM-SUMSQ表示：
- 所表示的点的数目N
- 向量SUM：所有点在每一维的分量之和，即SUM[i]表示第i维上的分量和。
- 向量SUMSQ：所有点在每一维的分量的平方和。
我们的实际目标其实是将一系列点表示为它们的数目、质心和每一维的标准差。根据N-SUM-SUMSQ表示，我们可以得到：
- 第i维质心：SUM[i]/N
- 第i维的方差：SUMSQ[i]/N−SUM[i]^2/N^2
然后是BFR的数据处理过程：
- 首先找到所有『充分接近』某个簇质心的点加入到该簇中。加入新的点后，DS废弃集的调整计算通过N-SUM-SUMSQ表示很容易实现，直接加上这些新加入的点的Ns,SUMs,SUMSQs 值即可。
- 剩下得即是那些并不充分接近任一个簇质心的点。我们将这些点和之前的留存集中的点一起进行聚类（use any main-memory clustering algorithm)。将聚类的点概括表示并加入到压缩集CS中，剩余的单点簇则表示为点的留存集RS。
- 通过第二步后，现在我们有了新的迷你簇，它们和上一个块的数据处理后留下的压缩集迷你簇和留存集中间可能距离很近是可以合并的。因此这一步就是将这些迷你簇和以前的压缩集的迷你簇和以前的留存集进行合并。
（如果这是最后一块数据了，那么就将这些留存集的点和压缩集分配到距离最近的簇中，否则继续保留压缩集和留存集，等待和下一块的数据一起处理。） - 分配给一个簇或迷你簇的点，即不再留存集中的点会和分配结果一起写出到二级存储器中。
那怎么定义充分接近呢，我们利用马氏距离，马氏距离可以表示该点到该簇质心的概率，本质上是点到簇质心的距离，并在每维通过簇的标准差进行归一化。我们选择具有最短马氏距离，且马氏距离小于某个阈值的簇加入。 这一计算利用了最开始提到的BFR算法的前提假设：每个簇都是正态分布的点构成，且点的坐标和空间坐标保持一致。
接下来讨论另一个点分配类的大规模聚类算法CURE算法（Clustering Using Representatives），仍然假定运行在欧式空间下。BFR算法对簇的分布和形状都有很强的假设条件，因此在实际使用中有许多并不满足条件的聚类情况。而本节讨论的CURE算法不需要簇满足正态分布，更不需要符合轴平行，即对簇的形状没有任何假设。CURE算法使用一些代表点的集合来表示簇而不再是质心。
