本文从聚类数据量大入手，先将将全量数据集随机分成若干个子数据集，然后对每一个子数据集进行聚类算法。
其中，每个子数据集可以同等规模（数据量相等），也可以规模不相等。但是每个子数据集的K值和聚类算法要保持一致，因为不同的K值会导致质心个数不一致最终没办法合并，而聚类算法如果不相同会导致每个子数据集的类簇之间没有可比性。
1. 系统框架
图1 加权质心聚类在线学习方法框架图
本文将传统聚类的全量数据聚类分解成若干个子数据集进行子聚类，每个子聚类的数据样本不重叠，数据总量等于全量数据，每个子数据集数据量可以相等也可以不相等。对于每个子聚类采用相同的聚类算法进行计算，为保证子聚类最终质心可以合并，因此要保证每个子聚类的K值相同。
为了保证子聚类拥有相同K值，因此需要保证各个子集的数据分布是相似的，所以在整体数据采样生成子集数据集时采用随机采样的方式，具体做法可以使用Hive的rand()方法或python的StratifiedShuffleSplit（）方法实现随机采样。因为数据集要分割成若干个数据子集，因此随机采样需要满足随机无放回采样，即每个样本只能出现在一个子集中。
通过以上采样方式可以得到若干个分布相似的子数据集，对每个子集进行聚类足以保证每个子集的K值相等。
当前已经保证了各个子集的分布是相似的，因此各子集的最优K值也是相同的，因此只要随机取其中一个子集获取最优K值即可应用于其它各个子集。
为了实现算法自动计算并选取最优K值，相对于肘部法而言，我们采用更佳清晰
的Gap Statistic方法。Gap Statistic的定义为:
式1 子聚类最优K值选取
这里的Dk即是手肘法计算距离的公式：
式2 手肘法距离计算
这里
指的是
的期望。这个数值通常通过蒙特卡洛模拟产生，我们在样本里所在的矩形区域中（高维的话就是立方体区域）按照均匀分布随机地产生和原始样本数一样多的随机样本，并对这个随机样本做K-Means，从而得到一个Dk。如此往复多次，通常20次，我们可以得到20个logDk。对这20个数值求平均值，就得到了E(logDk)的近似值。最终可以计算Gap Statisitc。而Gap statistic取得最大值所对应的K就是最佳的K。
Gap Statistic的基本思路是：引入参考的测值，这个参考值可以有Monte Carlo采样的方法获得。
式3 Gap Statistic公式
B是sampling的次数。为了修正MC带来的误差，我们计算sk也即标准差来矫正Gap Statistic。
式4 Gap Statistic修正公式
选择满足
的最小的k作为最优的聚类个数。下图阐释了Gap Statistic的过程。
图2 Gap Statistic流程说明
因为K值通常跟数据量相关，当数据量太少时数据反应的分布不代表真实分布，此时聚类质心加权合并时会产生较大波动性。具体来说，当各个子集数据极少时，即便通过前面的随机不重复采样的方式获得子集数据，由于各子集数据样本较少，其各子集分布差异较大，同时由于总样本数目确定的情况下，子集样本数量极少时，子集个数会极大，这样导致各个子集的聚类质心相似性较低，即波动性较大。这种波动性给子集质心合并计算引起波动和误差，因此需要在拆分子集数据时选取合适的子集个数来避免较大波动。通常我们采用下面的公式计算子集个数：
式5 确定最优子集个数
N是全量样本个数，T是全量样本的计算时间复杂度，通常时间复杂度也可用N*N表示。n是计算机计算数据上限，t是计算机计算上限数据花费的时间记为时间上限，因此子数据集的样本个数
要小于计算机上限n，时间复杂度
要小于t。通常
是用户自定义的一个值，一般选取
=n即可；通常
使用
表示，一般选取
=t即可，其中X是子集计算时间控制因子，当X增大时表示可以承受子集计算花费更久的时间，这样M会减少，即子集个数会减少，因此每个子集的样本数会多一些；当X减少时表示期望子集计算花费更少的时间，这样M会增加，即子集个数会增加，因此每个子集的样本数会少一些。建议在进行子聚类之前可以根据计算资源实际情况确定子集个数，然后用最优K值进行子聚类，生成若干个子聚类的多组聚类质心。
2. 子聚类质心与全量数据聚类质心的转换
图3 质心合并仿照层次聚类的思想进行
基于层次聚类的思想我们对全量数据进行了若干个子聚类，于是我们可以得到若干组聚类质心，每组质心包含K个质心，每个质心是符合原始数据维度的数据。于是将一系列的聚类质心当做层次聚类的样本进行反向合并。
由于子聚类分配的样本空间大小不一致，因此得到的聚类质心的可信度不一样，甚至由于子聚类样本量差异太大时，导致质心合并偏离真实情况。而传统基于距离测算的聚类方式不可避免的默认每个特征维度和每个样本的权重一样。因此，本文引入子聚类加权质心合并的计算方式来避免数据不平衡问题导致的合并结果不理想的问题。
式6 子聚类质心加权合并公式
其中，I是全量数据切分的子数据集的个数，J是聚类质心序号，取值从1到K的自然数，
是第i个子集的第j个质心，
是最终合并后第j类的质心，计算方式是j类在每个子聚类中的质心与j类在每个子聚类中的数据量的加权和与全量数据的比例。
各个子集聚类后的质心存在差异，分别反映各子集数据的聚类结果，当数据总量和子集个数M变化时，可能引起各个子集数据样本数量有差异，尤其是当面对两个已知的数据样本数量差异很大的子集聚类结果时，较大波动影响最终质心合并的准确性，因此需要使用式2进行合并，最终取得Q即为全量数据聚类执行：
式7 子聚类质心加权合并公式
其中，Q1到Qk分别是全量数据对应的K个类别的质心，当每个类别的质心确定时，即可计算每一个样本到各个类别质心的距离，将距离样本最近的质心对应的类别当做该样本的类别即可可得到聚类结果j，如式8计算。
式8 确定样本类别计算公式
3. 子聚类与加权质心构成在线学习方案
引入子聚类解决了数据量大的问题，引入加权质心解决了子聚类合并成原始聚类结果的桥梁。但同时因为子聚类间相互独立，因此可以并行运算加快了运算速度，而子聚类合并计算复杂度是n(IK)与K值和子聚类个数线性相关，因此进一步减少计算量加快运算速度。当加权质心引入之后可以实现任意新增子聚类或新增数据与某个版本的聚类模型进行快速融合而不再依赖原来的历史全量数据，即实现大规模数据下的聚类在线学习方案。
例如：在物流行业中，全网每日产生运单数据巨大，当我们想通过运单的重量，流向，拖寄物类别，收发信息，运费信息，客户信息等对运单聚类，实现价值挖掘时，由于数据量巨大想要快速实现聚类并且可以实时在线上更新模型，就需要通过本文对全网运单随机采样分成若干个子数据集，对每一个子数据集就可以进行快速聚类，最终合并子集聚类质心得到全量数据聚类结果，当线上新产生运单时可以把新产生的数据当做一个子集进行聚类，再次将新子集的聚类质心与原全量数据的质心进行融合，以实现快速聚类且聚类可以在线学习而不是传统方式下的全量数据进行运算。
