用电负荷相关聚类算法总结（1）

聚类算法大致可以分为划分聚类方法、层次聚类方法、密度聚类方法、网格聚类方法、模型聚类方法等。近年来，量子聚类方法、谱聚类方法、粒度聚类方法、概率图聚类方法、同步聚类方法等也流行起来。

• 1.1 基于划分的聚类算法
  基于划分的聚类算法通过构造一个迭代过程来优化目标函数，当优化到目标函数的最小值或极小值时，可以得到数据集的一些不相交的子集，通常认为此时得到的每个子集就是一个聚类。
  多数基于划分的聚类算法都是非常高效的，但需要事先给定一个在聚类分析前难以确定下来的聚类数目。k-means 算法[5]和 FCM(FuzzyC Means)算法是该类型中最著名的两个算法。另外，k-中心点算法 PAM(PartitioningAround Medoid)和 CLARA(Clustering LARgeApplications)、k-模算法(聚类分类数据)和k-原型算法(聚类混合数据)[25]也属于这种类型的算法。基于划分的聚类算法优点是易于实现，聚类速度快。其时间复杂度与数据点数目n、数据的维度d 及预先设定的聚类数目k 成线性关系。缺点是优化函数是个NP难问题，要搜索到最小值，时间代价高，且易陷入局部最小值。
• 1.2 层次聚类算法
  层次聚类方法使用一个距离矩阵作为输入，经过聚类后得到一个反映该数据集分布状
  况的聚类层次结构图。层次聚类算法通常分为两种。第一种是凝聚的层次聚类算法，它首先把每个数据点看作是一个聚类，然后以一种自底向上的方式通过不断地选择最近邻居聚类对的合并操作，最终可以构造出一棵代表着该数据集聚类结构的层次树。第二种是分裂的层次聚类算法，它首先把所有的数据点看作是一个聚类，然后以一种以自顶向下的方式通过不断地选择最松散簇进行分裂操作，最终可以构造出一棵代表着该数据集聚类结构的层次树。尽管层次聚类方法的时间代价高于划分聚类方法，但多数层次聚类算法并不需要事先设定一个难以确定的聚类数目这个参数，而且这类方法可以获得一种具有多个粒度的多层次聚类结构，这是它区别于划分聚类方法的最大优点。
• 1.3 基于密度的聚类算法
  基于密度的聚类算法试图通过稀疏区域来划分高密度区域以发现明显的聚类和孤立点，主要用于空间型数据的聚类。代表性的是DBSCAN算法。
• 1.4 基于网格的聚类算法
  基于网格的聚类算法是一种基于网格的具有多分辨率的聚类方法。它首先将数据集的分布空间划分为若干个规则网格(如超矩形单元)或灵活的网格(如任意形状的多面体)，然后通过融合相连的带数据概要信息的网格来获得明显的聚类。这类算法的优点是处理时间与数据点的数目无关、与数据的输入顺序无关，可以处理任意类型的数据。其缺点是 处理时间与每个维度上所划分的单元数相关，一定程度上降低了聚类的质量和准确性。代表性算法是STING(STatistical INformation Grid)算法。
• 1.5 基于模型的聚类算法
  基于模型的聚类算法借助于一些统计模型来获得数据集的聚类分布信息。该方法假定数据集是由有限个概率分布模型共同作用生成的。在这种方法中，多变量的高斯分布混合模型应用最为广泛。其中，COBWEB 算法是一个常用的、简单的增量式概念聚类方法，它采用分类树的形式来表现层次聚类结果。
• 1.6 基于图的聚类算法
  采用图聚类方法进行聚类分析时，首先是建立与具体问题相适应的图。图的结点代表被分析数据的基层单元，图的边代表基层单元数据之间的相似性度量(或相异性度量)。通常，每个基层单元数据之间都会有一个度量表达，这样可以保持数据集的局部分布特性。图聚类方法是以数据集的局部连接特征作为聚类的主要信息源，因而易于处理局部数据的特性。Karypis 等提出的变色龙算法也可看作是一种图聚类算法。
• 1.7 其他聚类算法
  量子聚类方法借用了量子学理论，先是从源数据中创建一个基于空间尺度的概率函数，接着使用一些分析操作来获得一个根据极小值来确定聚类中心的势函数，最终通过调整尺度参数来搜索聚类结构。
  谱聚类(Spectral Clustering)方法通过源数据的相似度矩阵来计算特征值，进而可以发现明显的聚类区域。许多谱聚类算法都易于实现，其效果优于传统的聚类算法，如k-means，它们在许多应用中也都获得了成功的实现。用于图像划分的 Shi-Malik 算法就是基于谱聚类方法开发出来的。
  基于粒度的聚类方法，是从信息粒度角度上发展起来的一个新的聚类研究方向。目前这种聚类方法的研究还不太成熟，尤其是对粒度计算语义的研究还比较少。
  概率图聚类方法是近年来流行起来的一种聚类方法。最著名的概率图聚类方法要数2007 年发表在《Science》上面的 AP(AffinityPropagation)聚类算法。
  同步聚类算法——SynC (Synchronization Clustering)算法。该算法不仅可以在不知道数据集的任何分布情况下，通过动态的同步过程来发现它的内在结构，并能很好地处理孤立点，还能使用最小描述长度原理来实现自动聚类。
  由于基于网格的算法主要用于处理空间数据，而电力负荷曲线是一种时间序列，本文重点研究其他类型的聚类算法。

二、电力负荷聚类方法

目前的电力负荷曲线聚类的方法很多，比较流行的有Kmeans 聚类、小波分析、模糊C 均值聚类算法（FCM）、集成聚类算法、自组织特征映射神经网络（SOM）、极端学习机（ELM）、云模型等，同时还有一些在这些算法的基础上进行改进的算法。

• 1.1 聚类有效性

  聚类有效性研究是通过建立有效性指标，评价聚类质量并确定最佳聚类数的过程。典型的聚类有效性指标有误差平方和(sum of squared error，SSE) 、Calinski-Harabasz 指标(Calinski-HarabaszIndex，CHI)、Davies-Bouldi 指标(Davies-BouldinIndex，DBI)等。

  1）SSE 指标。

  误差平方和 SSE 指标ISSE 用一个子类到所在类簇的聚类中心的欧氏距离来表示，即：

d(ci , x)为向量间的欧氏距离。随着聚类数增多，ISSE会减小，SSE 曲线的拐点表示在该点后再增加聚类数时误差平方和的减小幅度很小，因此可以将SSE曲线的拐点作为最佳聚类数。 2）CHI 指标。 CHI 指标综合考虑类间的分散性(用B 表示)和类内的紧凑性(用W 表示)，其中：

式中：x 为所有对象的均值；wk,i 表示第i 个对象对第k 个类簇的隶属关系，即：

可见，ICHI 越大表示类簇间的分散性和类簇内的紧凑性越好。 3）DBI 指标。 DBI 指标的含义与CHI 类似，计算公式为：

其中：

式中：d(Xk)和d(Xj)为矩阵内部距离；d(ck, cj)为向量间的距离。IDBI 越小表示聚类效果越好。

• 1.2指标分析

3 种聚类有效性指标都可以正确地找到最佳聚类数。CHI 和DBI 曲线的极值点比SSE 曲 线的拐点更为直观；与CHI 相比，DBI 指标的计算公式更为简单且变化范围小，便于应用。因此，DBI适合作为电力负荷曲线聚类的有效性指标。

• 2、经典聚类算法比较 表 2 对上述各类算法进行汇总：

由图 2 可知，划分聚类的计算效率明显高于其他类型的算法。

由图3 可知，层次聚类的效果较好且波动性较小。此外，这两类算法都具有需要的输入参数较少的优点。 本文将划分聚类高效率和层次聚类高精度的特点相结合，提出负荷曲线的集成聚类算法。

• 3、集成聚类算法 集成聚类算法(ensemble clustering algorithm，EnsClust)的基本思想是：在原数据集的多个子集上重复进行划分聚类，对得到的聚类中心用层次聚类进行组合。集成聚类算法包括3 个步骤：bootstrap重采样、划分聚类、层次聚类。首先通过bootstrap 重采样得到原数据集的多个样本集，然后通过划分聚类减小每个样本集的数据规模，最后用层次聚类对划分聚类的结果进行组合。 3.1 算法流程如下：
  1）bootstrap 重采样。
  所谓 bootstrap 重采样就是对容量为n 的原始样本进行有放回的随机采样，抽取的随机样本容量为n，并保证每次抽样中各个体被抽取的概率相等。由于划分聚类稳定性较差且可能收敛到局部最优解，即不同的初始聚类中心或数据集的微小变动可能会导致不同的聚类结果。通过bootstrap 重采样，在多个样本集上进行聚类，可以降低初始聚类中心随机因素和原始数据集中离群点的影响，从而提高算法稳定性。
  2）划分聚类。
  在集成聚类算法中，划分聚类可看作对层次聚类的数据预处理步骤。若直接对原始数据集进行层次聚类，则需要计算所有对象两两之间的欧氏距离并存储该距离矩阵，时间和空间开销很大。划分聚类效率最高，用其输出的聚类中心表征原始数据集的结构，从而大幅缩减数据规模。和随机抽样相比，聚类中心包含原始数据集更多的信息并能消除噪声点和离群点的影响。
  3）层次聚类。
  在集成聚类算法中，层次聚类可看作是对样本集划分聚类的输出结果进行组合。为了解决划分聚类容易陷入局部最优解和受初始聚类中心影响较大的问题，采用聚类质量较好、稳定性较高的层次聚类算法对划分聚类输出的聚类中心进行组合，进而得到最终的聚类结果。
• 3.2 算法分析和实验结果

综合以上分析，集成聚类算法不仅具有较高的计算效率，而且聚类质量也比传统的划分聚类和层次聚类算法有所提高。

• 4、结合降维的集成聚类算法 4.1 负荷曲线降维

  当数据集规模较大时，采用集成聚类算法的计算时间还是较长，为了进一步提升聚类效率，有必要对数据集进行降维处理。降维的目的用维数较低的向量表示负荷曲线。降维一方面可以减小数据的存储空间，另一方面可以减少向量间欧氏距离的计算时间，提升算法效率。常用的降维算法包括sammon 映射、自组织映射、主成分分析等。 4.2 降维算法分类 1）sammon 映射。 sammon 映射(sammon mapping，SM)是一种非线性映射，算法的目标是最小化误差函数：

式中：d(xi,xj)为原始空间中对象i 和对象j 间的距离；d(yi,yj)为投影空间中两个对象的距离。sammon 映射用梯度下降法求解该优化问题。

2）自组织映射。

自组织映射(self-organizing map，SOM)神经网络可以实现对数据的非线性降维[20]。SOM 的输入层节点是高维向量的属性，输出层节点是低维向量的属性，输入层属性和输出层属性之间的相似性通过权向量表示。计算输入向量x(m)与权向量w(n)间的欧氏距离d(x(m), w(n))，将与x(m)最近的输出节点作为胜出节点，并更新其权向量：

式中η为学习率。同时更新其k 个近邻的权向量。

3）主成分分析。

主成分分析(principal component analysis，PCA)是线性降维算法。用原始变量的线性组合构造综合指标，使其尽可能多地反映原始变量的信息(用方差表达)。这些综合指标即为主成分。

式中：X 为归一化后的数据矩阵；cov(X)为协方差矩阵；V 的列向量为cov(X)的正交单位特征向量。将 X 降至L 维后的数据矩阵为：

4）特征提取。

特征提取(feature extraction，FE)法直接计算每条负荷曲线的特性指标，本文对每条负荷曲线提取4 个基本特性指标：最大负荷、最小负荷、平均负荷、负荷标准差。

4.3 降维结果分析

ORG 表示原始数据集，SM、SOM、PCA、FE分别表示sammon 映射、自组织映射、主成分分析和特征提取后的降维数据集。原始数据集是48 维，降维数据集是4 维。对降维数据集进行集成聚类。图10 为各种降维方法的计算时间，包括降维时间和聚类时间两部分。由图 10 可见，PCA 降维方法的计算时间最小，且数据集规模越大效果越明显。

各种降维方法的聚类结果的DBI 指标如图11 所示。由 DBI 的箱线图可知，主成分分析和sammon映射降维后的数据集聚类效果较好且与原始数据集的聚类效果相当，说明这两种降维方法可以最大程度地保留负荷数据集的信息。

综上所述，负荷曲线PCA 降维后的集成聚类精度很高。 5、结论

本文提出了结合降维技术的电力负荷曲线集成聚类算法。

1）聚类有效性指标SSE、CHI 和DBI 都可以正确地找到最佳聚类数。DBI 指标计算简便、曲线直观，适合作为负荷曲线聚类的有效性指标。

2）对于负荷曲线数据集，层次聚类算法精度最高，划分聚类算法效率最高，且随着数据集规模增大，各种算法的效率差异显著增大。

3）集成聚类算法结合了划分聚类高效率和层次聚类高精度的优点，聚类效率与划分聚类算法接近，聚类质量优于划分聚类与层次聚类。

4）对于负荷曲线降维，主成分分析的计算时间(包括降维时间和聚类时间)最短；主成分分析和sammon 映射降维后的数据集聚类效果最好。

5）对于海量高维的负荷曲线，可采用主成分分析对数据集降维，在此基础上应用集成聚类算法聚类并用DBI 有效性指标评估聚类结果。

Ⅱ 基于改进DTW算法的用电负荷聚类研究

一、背景知识：DTW算法

Dynamic Time Warping（DTW 动态时间规整）是一种衡量两个长度不同的时间序列的相似度的方法。应用也比较广，主要是在模板匹配中，比如说用在孤立词语音识别（识别两段语音是否表示同一个单词），手势识别，数据挖掘和信息检索等中。

在时间序列中，需要比较相似性的两段时间序列的长度可能并不相等，在语音识别领域表现为不同人的语速不同。因为语音信号具有相当大的随机性，即使同一个人在不同时刻发同一个音，也不可能具有完全的时间长度。而且同一个单词内的不同音素的发音速度也不同，比如有的人会把“A”这个音拖得很长，或者把“i”发的很短。在这些复杂情况下，使用传统的欧几里得距离无法有效地求的两个时间序列之间的距离（或者相似性）。

例如上图所示，实线和虚线分别是同一个词“pen”的两个语音波形（在y轴上拉开了，以便观察）。可以看到他们整体上的波形形状很相似，但在时间轴上却是不对齐的。例如在第20个时间点的时候，实线波形的a点会对应于虚线波形的b’点，这样传统的通过比较距离来计算相似性很明显不靠谱。因为很明显，实线的a点对应虚线的b点才是正确的。而在下图中，DTW就可以通过找到这两个波形对齐的点，这样计算它们的距离才是正确的。

也就是说，大部分情况下，两个序列整体上具有非常相似的形状，但是这些形状在x轴上并不是对齐的。所以我们在比较他们的相似度之前，需要将其中一个（或者两个）序列在时间轴下warping扭曲，以达到更好的对齐。而DTW就是实现这种warping扭曲的一种有效方法。DTW通过把时间序列进行延伸和缩短，来计算两个时间序列性之间的相似性。

如何才知道两个波形是对齐了呢？也就是说怎么样的warping才是正确的？直观上理解，当然是warping一个序列后可以与另一个序列重合recover。这个时候两个序列中所有对应点的距离之和是最小的。所以从直观上理解，warping的正确性一般指“feature to feature”的对齐。

动态时间规整DTW是一个典型的优化问题，它用满足一定条件的的时间规整函数W(n)描述测试模板和参考模板的时间对应关系，求解两模板匹配时累计距离最小所对应的规整函数。

假设我们有两个时间序列Q和C，他们的长度分别是n和m：（实际语音匹配运用中，一个序列为参考模板，一个序列为测试模板，序列中的每个点的值为语音序列中每一帧的特征值。例如语音序列Q共有n帧，第i帧的特征值（一个数或者一个向量）是qi。至于取什么特征，在这里不影响DTW的讨论。我们需要的是匹配这两个语音序列的相似性，以达到识别我们的测试语音是哪个词）

Q = q1, q2,…,qi,…, qn ; C = c1, c2,…, cj,…, cm ; 如果n=m，那么就用不着折腾了，直接计算两个序列的距离就好了。但如果n不等于m我们就需要对齐。最简单的对齐方式就是线性缩放了。把短的序列线性放大到和长序列一样的长度再比较，或者把长的线性缩短到和短序列一样的长度再比较。但是这样的计算没有考虑到语音中各个段在不同情况下的持续时间会产生或长或短的变化，因此识别效果不可能最佳。因此更多的是采用动态规划（dynamic programming）的方法。

为了对齐这两个序列，我们需要构造一个n x m的矩阵网格，矩阵元素(i, j)表示qi和cj两个点的距离d(qi, cj)（也就是序列Q的每一个点和C的每一个点之间的相似度，距离越小则相似度越高。这里先不管顺序），一般采用欧式距离，d(qi, cj)= (qi-cj)2（也可以理解为失真度）。每一个矩阵元素(i, j)表示点qi和cj的对齐。DP算法可以归结为寻找一条通过此网格中若干格点的路径，路径通过的格点即为两个序列进行计算的对齐的点。

哪条路径才是最好的呢？也就是刚才那个问题，怎么样的warping才是最好的。

我们把这条路径定义为warping path规整路径，并用W来表示，W的第k个元素定义为wk=(i,j)k，定义了序列Q和C的映射。这样我们有：

首先，这条路径不是随意选择的，需要满足以下几个约束：

1）边界条件：w1=(1, 1)和wK=(m, n)。任何一种语音的发音快慢都有可能变化，但是其各部分的先后次序不可能改变，因此所选的路径必定是从左下角出发，在右上角结束。

2）连续性：如果wk-1= (a’, b’)，那么对于路径的下一个点wk=(a, b)需要满足 (a-a’) <=1和 (b-b’) <=1。也就是不可能跨过某个点去匹配，只能和自己相邻的点对齐。这样可以保证Q和C中的每个坐标都在W中出现。 3）单调性：如果wk-1= (a’, b’)，那么对于路径的下一个点wk=(a, b)需要满足0<=(a-a’)和0<= (b-b’)。这限制W上面的点必须是随着时间单调进行的。以保证图B中的虚线不会相交。 结合连续性和单调性约束，每一个格点的路径就只有三个方向了。例如如果路径已经通过了格点(i, j)，那么下一个通过的格点只可能是下列三种情况之一：(i+1, j)，(i, j+1)或者(i+1, j+1)。

满足上面这些约束条件的路径可以有指数个，然后我们感兴趣的是使得下面的规整代价最小的路径：

分母中的K主要是用来对不同的长度的规整路径做补偿。我们的目的是或者说DTW的思想是把两个时间序列进行延伸和缩短，来得到两个时间序列性距离最短也就是最相似的那一个warping，这个最短的距离也就是这两个时间序列的最后的距离度量。在这里，我们要做的就是选择一个路径，使得最后得到的总的距离最小。 这里我们定义一个累加距离cumulative distances。从(0, 0)点开始匹配这两个序列Q和C，每到一个点，之前所有的点计算的距离都会累加。到达终点(n, m)后，这个累积距离就是我们上面说的最后的总的距离，也就是序列Q和C的相似度。 累积距离γ(i,j)可以按下面的方式表示，累积距离γ(i,j)为当前格点距离d(i,j)，也就是点qi和cj的欧式距离（相似性）与可以到达该点的最小的邻近元素的累积距离之和：

最佳路径是使得沿路径的积累距离达到最小值这条路径。这条路径可以通过动态规划（dynamic programming）算法得到。

二、基于DTW改进算法

1、概述

本文提出一种基于改进DTW算法的用电负荷聚类方法，针对原DTW算法时间复杂度高、存在恶性匹配的缺点，提出对DTW算法的搜索路径进行限制，控制在矩阵对角线附近，在限制不合理点对匹配的同时大大降低了搜索的复杂度，从O(N2)降至平均O(N)的水平；同时，引入曲线平移以在搜索范围内尽可能提升精度，改善时轴稍有偏移的相似曲线度量。最后选择K-Medoids算法进行聚类，对用户进行划分。

2、实现思路

动态时间规整（DTW）算法可以用来衡量时间序列相似度，但其局限性也非常明显。如图2-1所示，DTW在计算两时间序列匹配关系时，会遍历整个M*N矩阵寻找最优路径，时间复杂度高达O（N2），在处理大数据量时显得极为乏力；同时，DTW算法存在病态匹配现象，在许多场合下，比较时间序列相似度不允许进行大量曲线伸缩，否则可能会引入额外误差。例如对用电负荷进行聚类时，波动周期不同的用户显然具有不同的用电习惯，不应该通过伸缩对齐被误聚为一类，图2-2中的曲线会被DTW通过病态伸缩匹配，认为非常相似。

为此，论文提出了一种基于限制伸缩范围并引入曲线平移的改进DTW算法，实现对用户用电负荷进行相似度分析。越相似的曲线，其匹配路径越接近矩阵的对角线；反之通过伸缩才能对齐的曲线，其路径波动极大。为了限制曲线的病态匹配，我们提出将搜索范围限制在矩阵对角线附近。对于超出搜索范围的部分，引入曲线平移，在不超过伸缩范围的基础上尽可能搜索最相似的匹配，进一步改善计算结果。同时，由于限制了搜索范围，大大减少了相似度比较开销，可以将算法复杂度降至平均O(N)的水平。

该方法除了DTW的三个约束条件之外，还有另外两个约束条件：

约束四：搜索范围约束。矩阵的搜索范围代表了曲线的伸缩程度，越相似的曲线匹配路径就越贴近对角线。设路径搜索范围必须在距离矩阵对角线附近Limit 范围内，即曲线最大伸缩程度为Limit。

Pi=(xa,yb)，有|xa-yb|≤Limit

约束五：曲线平移约束。对于有明显平移相似性的时间序列X 和Y，允许对曲线进行平移，平移后重新计算距离矩阵和匹配路径。对于移出比较范围的曲线起点和终点，保持它们的最优匹配关系，计入距离矩阵的初始值D[0,0]。

3、 算法流程

4、 聚类算法的选择

为了对用户用电负荷进行聚类，已经通过改良的DTW算法衡量了用电曲线之间的距离。在此基础上，我们选择K-Medoids算法对用户进行聚类。

K-Medoids算法与K-means算法类似，都是通过随机选取质心、计算点与质心的距离、更新质心的迭代过程完成聚类。不同之处在于质心的产生方法：在K-means中质心选取当前cluster中所有数据点的平均值；而在K-medoids算法中，我们选取当前cluster 中到其他所有点距离之和最小的点作为新的质心。

L-K-Medoids算法对脏数据和异常数据不敏感，个别用电异常的用户不会影响整体聚类的结果；K-Medoids算法可以得到典型用电曲线，即每一簇的质心都是一个实际用户，可以真实反映本类用户用电特征，便于后续结合地理、经济等相关信息进行场景分析；同时，K-Medoids算法有易于解释的物理意义，每个向量代表着一条用户用电曲线，每两个向量之间的距离代表着不同用户的用电相似度，每次迭代可以视作用户的重新排队，每个质心都代表着一个典型的实际用户。

5、 实验评估

选取轮廓系数Silhouette Coefficient、误差平方和SSE以及Calinski-Harabaz Index作为评估指标。

轮廓系数结合内聚度和分离度因素，SI越接近1则聚类的效果越好，簇内更紧致，簇间更分离。公式定义如下，其中a是与它同类别的其它元素的平均距离，b是与它距离最近的不同类别中样本的平均距离。

误差平方和SSE衡量距离定义的合理性，比较聚类结果各点距离簇中心的误差。

Calinski-Harabaz Index则从协方差的角度评估数据，类别内部数据的协方差越小越好，类别之间的协方差越大越好，则其评分就会越高。公式定义如下：

其中m为训练集样本数，k为类别数，Bk为类别之间的协方差矩阵，Wk为类别内部数据的协方差矩阵，tr为矩阵的迹。

三、结论

本文提出了一种适合于衡量用户用电模式相似度的基于限制伸缩的改进DTW算法。引入搜索范围限制，规范了负荷序列的伸缩程度，避免了因恶意匹配造成的曲线周期改变，同时将运算复杂度提升至平均O（N）水平。通过引入序列平移，提升了算法对峰值出现时刻存在差异的相似用户的计算精度。

Canopy 算法

K-Means 、K-Medoids算法的一个不足之处是必须预先指定簇数K ，在许多实际应用中要设定一个合理的K值不是一件容易的事。此时，借助Canopy 算法可以完成簇数K 及初始簇中心的估计。Canopy 是一种聚类算法，依据参数T 1 和T 2 实现对象的粗略划分。下图显示一个典型的Canopy 聚类过程。

划分过程如下图：

Canopy 算法虽然运行速度较快，但是聚类过程精度较低，因此本文使用Cannopy 算法对数据初步并行聚类，获取K 个簇。然后把获得的K 个簇作为初始聚类个数利用用K-means 进行进一步聚类。也就是说Canopy 算法主要把聚类分为两个阶段。第一阶段为数据预处理阶段，使用简便计算方法将相似对象放入一个叫做Canopy 的子集中。第二阶段为聚类计算阶段，在各个子集中使用K-Means算法计算同一子集中所有数据向量的距离。 其中，T1和T2的值可以用交叉校验来确定。