函数型数据的分步系统聚类算法

郭均鹏，王梅南，高成菊，戴 晖

（天津大学 管理与经济学部，天津 300072）

在传统技术条件下，人们能观测和记录到的数据往往是离散和有限的。然而，现实世界的数据却更加复杂和多变，很多情况下，需要根据收集到的有限离散数据探索其内在变化规律，如人体生长曲线、气温变化、PH值变化等。在处理点数据的过程中发现，当观测的时间点十分密集时，数据在数据空间内会体现出一定的函数特征。针对此类数据而言，传统点数据的处理方法已不能满足其分析要求。将具有函数特征的数据看作一个整体进行研究，即函数型数据［1-4］，对函数型数据进行研究分析的方法就称为函数型数据分析。函数型数据最早由Ramsay［1-3］提出，近年来，越来越多的学者开始关注和重视函数型数据的研究。

聚类分析作为一种统计分析方法，被广泛应用于数学、计算机科学、生物学、经济学等许多领域，关于聚类的研究已取得了大量有意义的成果［5-8］，但现有聚类算法大多是针对点数据进行的聚类，针对函数型数据聚类的研究还相对较少。Abraham［9］将样本数据拟合为B样条函数，并用k-means（k均值）方法对函数型数据进行聚类。Chiou［10］在最大程度划分函数型数据的条件下，运用FFT（Forward Functional Testing）模型确定聚类数，并在此基础上进行聚类。Liu［11］提出同步校准和聚类的方法，改进了函数型数据分析先校准再进行聚类的传统模式。王劼［12］定义了一种函数型数据距离，并在此基础上对函数型数据进行聚类。陈晓锋［13］将Pearson相似系数引入到函数型数据聚类分析中，利用基函数展开对函数型数据进行聚类，研究了欧式距离无法刻画的曲线间的形态差异。Hebrail［14］运用动态规划方法，在确定各类样本数的前提下，用探索分析算法对函数型数据进行聚类。Sangalli［15］提出了一种新k均值算法，可以有效处理振幅和阶段变量，在对未校准函数型数据进行校准的同时对其进行聚类。Jank［16］以蒙特卡洛EM算法为基础，提出上升EM和遗传上升EM算法，并对网站拍卖数据库生成的函数型数据进行了验证。

现有函数型数据聚类算法大多以数据间的实际距离作为聚类标准，聚类结果能够在距离上接近，但不能保证同一类中的数据也具有相似的形态特征。考虑到导函数可以很好地反映数据的内在特征，本文首次将导函数距离引入函数型数据的聚类算法中，将实际距离与导函数距离相结合作为聚类标准，使聚类结果不仅能够在距离上接近，而且可以保证同类数据具有相似的形态特征，基于此，设计了函数型数据的分步系统聚类算法。具体而言，首先根据实际距离对函数型数据进行系统聚类，得到在距离上接近的若干个新类；然后，在此基础上，根据导函数的距离对每一个新类中的数据进行进一步聚类，得到在距离上接近且具有相似形态特征的新类。此外，作为此算法的一个重要应用，在上述研究的基础上，本文还提出了一种基于本文算法的函数型数据预测方法，并进行了实例研究。

1 函数型数据的生成

函数型数据是以函数为表现形式的一种数据，它将函数看作一个整体，而非一系列单独的个体。其表现形式为光滑的曲线xi（t），i=1，2，…，n，其中，t为类似时间的一类变量，n为函数型数据的个数。然而，现实世界搜集到的数据往往是离散的点数据，要进行函数型数据分析，首先要通过拟合将离散的点数据生成为函数型数据。假设第i条曲线是由一系列离散的观测数据yi1，yi2，…，yin得到，第1步就是将这些值转化为函数xi（t）。如果观测到的数据是准确的，则该过程称为插值；如果观测数据存在误差，则该过程称为平滑。

1.1 基函数

函数型数据拟合最常用的方法是基函数拟合。基函数是一系列具有一定性质的独立函数φi（i=1，2，…，K）的集合，通过线性组合表示函数，其形式为，其中φk是K个已知的基函数。B样条基是对非周期性数据进行拟合最常用的样条函数系统［9］，本文采用B样条基对函数型数据进行拟合。

样条函数空间。将给定区间［a，b］划分为N个子区间［xi—1，xi］，i=1，2，…，N，其中a=x0＜x1＜…＜xN=b。由下面递推公式所得到的Bi，k（t）即称为该划分上的k阶B样条基函数：

1.2 函数平滑

根据数据特征选择合适的基函数系统后，需要计算系数向量，从而得到函数型数据［6］：

式中：向量C表示系数矩阵ck；向量Φ表示矩阵φk（t）。在此，通过最小化代价函数来计算C的估计值：

为求其解，令等式右边导数为0：2ΦΦ′—2Φ′y=0，即可求得C的估计值。

1.3 函数校准

函数型数据与点数据不同，其变化包括振幅和相位两方面。函数型数据校准的目的是将所有曲线中存在错位的自变量t移动到同一标准，从而只对振幅的变化进行分析即可。通过曲线的校准，能够使不同曲线的特征在自变量相近的地方体现出来。

如图1所示，函数型数据x1（t）与x2（t）虽然具有相同的函数特征，但是在每个时间点t的取值不同。为了方便比较，就要去除干扰项，该过程就是函数型数据的校准。

函数型数据校准最简单也是最常用的方法是时间轴t平移。设n个函数型数据xi（t），i=1，2，…，n，在区间［t1，t2］上有意义，同时在区间外也是有意义的。定义平移变量δi，令（t）=xi（t+δi），通过求下式的最小化确定平移量δi：

图1 函数型数据的校准

本文算法在利用函数距离进行聚类得到初步聚类结果的基础上，采用函数型数据的导函数距离对函数型数据进行二次聚类，即充分考查函数型数据的内部特征，根据函数型数据的内在变化规律对新类进行进一步划分，无形中起到了校准的效果，因此，无须提前进行校准处理。

2 函数型数据的分步系统聚类算法

基本思想：设有n个样品，每个样品测得p项指标，在初始时将n个样品各自看成一类。首先，根据函数型数据的实际距离，采用自底向上聚类算法对数据进行初步聚类；然后，计算函数型数据的导函数及导函数之间的距离，根据函数型数据的导函数距离对每一类中的数据进行进一步聚类，得到在距离上接近且同类数据具有相似形态特征的精细划分。

2.1 定义距离

在聚类的过程中，函数型数据的实际距离用函数间的距离进行度量，数据内在特征的相似性用导函数距离进行度量。

首先定义聚类过程中的距离，设函数型数据xi（t），i=1，2，…，n在区间［t1，t2］上可积，x′i（t），i=1，2，…，n是其导函数。

函数型数据x1（t）、x2（t）在区间［t1，t2］上的距离定义为［12］

函数型数据的导函数x′1（t）、x′2（t）在区间［t1，t2］上的距离定义为［12］

函数型数据xi（t），i=1，2，…，n的均值函数定义为［12］

2.2 聚类过程

首先将记录到的点数据拟合为函数型数据，然后针对函数型数据进行分步系统聚类。聚类算法的步骤如下：

（1）聚类。首先，根据函数型数据的实际距离对数据进行第1步聚类。

①利用式（4）计算n个函数型数据两两之间的距离，得到数据之间的距离矩阵D（0）；

②令s表示迭代次数，k表示类的个数。初始值：s=1，k=n，n个样品各自构成一类，第i类记为Gi=｛xi（t）｝（i=1，2，…，n）。此时的类间距离就是样品间的距离；

③根据计算得到的距离矩阵D（s），合并类间距离最小的两类形成一个新类。新类的中心由均值式（6）表示。令k=n—s；

④s=s+1。更新新生成的类的数据对象，由式（4）计算新的类中心与其他类之间的距离；

⑤迭代计算③和④，直到得到最佳分类个数k′。

通过第1步聚类，将原始数据划分为k′个新类，得到基于实际距离的聚类结果，同类中的数据能够在距离上接近，但不能保证具有相似的形态特征。

（2）聚类。将第1步聚类生成的k′个类看做k′组新原始数据，针对每组新原始数据逐一进行进一步聚类。

针对每组新原始数据，计算其中函数型数据的导函数x′i（t），并利用式（5）计算导函数两两之间的距离，得到导函数距离矩阵和，根据导函数距离，重复第1次聚类中的5个步骤进行第2次聚类，根据形态差异进行更深入的划分。

本文算法将实际距离和导函数距离相结合，在不同层次上进行聚类，在考虑函数型数据实际距离的同时，兼顾了函数型数据本身的内在变化规律。利用该算法进行聚类，同类函数型数据不仅在实际距离上接近，而且具有相似的变化特征。

3 基于随机模拟的算法评价

为了对本文算法的有效性进行检验，用Matlab［17］进行模拟实验。主要思想是：构造已知划分的函数型数据，用本文算法进行聚类分析，将生成的分类与真实分类进行比较，对算法的有效性进行分析。

3.1 随机数的生成

函数型数据随机数的生成和传统点数据的生成过程不同，需要对点数据进行拟合。这就要求点数据的生成是随机的，从而保证的函数型数据具有随机性。这里假设所有数据的变量取值范围相同，并且在相同的时间间隔内取值，即x坐标相同。

本文生成随机函数型数据的主要方法是先随机生成3个具有明显划分的函数型数据，以此为中心扩充为4类函数型数据。

（1）生成区间中点的随机点数据集，拟合生成原始函数型数据曲线。首先随机生成一个包含150个二维实数数据的点数据集作为区间数据集的中点，这150个实数点由3类相互独立的数据集组成，其中每一类各包含50个点，此即初始类别划分情况。数据集中每个点由一个确定的变量x和一个服从标准正态分布的y轴坐标确定，3个数据集中的点根据以下参数分别随机产生：

将生成的3个点数据集表示为（a1j，a2j，a3j，…，a50j），j=1，2，3。

通过前面描述的函数型数据的生成方法将3个数据集分别拟合为函数型数据，如图2所示。

图2 原始函数型数据曲线

由图2可以很明显地看出，由于均值方差的不同，3个函数型数据的取值和形态变化都有很大的差异。

（2）产生随机区间数据集，随机产生3组函数型数据集。以3个数据集中的点为中心，横坐标不变，纵坐标延y轴方向扩充为区间数［yij—r，yij+r］，其中r=1，在y轴方向可得到以下3个区间数据集：

对于每个区间数据集（j=1），从每个区间数内随机选取1个点数据，组成一个新的点数据集，重复6次，可以得到6个新点数据集，记为（b1，t，b2，t，…，b50，t），t=1，2，…，6。同样地，对于后面2个区间数据集（j=2，3）重复上述步骤，也各得到6个新的点数据集。最终得到3×6个点数据集，共3类。利用前文描述的函数型数据生成方法将3个数据集分别拟合为函数型数据。

（3）选取第1步生成的点数据集（a1，2，a2，2，…，a50，2），并进行如下变化：

其中，mi=i×0.1，i=1，2，…，6。可以生成6个点数据集，其中每个数据集中包含50个点数据。由于这6个点数据集通过平移得到，故具有相同的形态特征。同样，根据得到的6个点数据集生成6个函数型数据。

通过上述步骤，共得到4×6个数据点集，分为4类，并根据这些数据点集生成4×6个函数型数据，如图3所示。

图3 模拟实验构造出的函数型数据

由图3可见，对于前3类而言，同一类中的数据在实际距离上都很接近，第4类同第2类在距离上也很接近，但与第2类不同的是，第4类中的数据都具有相同的变化特征。

3.2 聚类

对构造好的函数型数据分别利用本文算法和传统算法进行聚类，将聚类结果与真实分类进行对比，并对两种算法的有效性和精确度进行比较。

对比算法的基本步骤：将n个函数型数据看做n个原始分类，计算n个原始分类两两之间的距离，合并类间距离最小的两类形成一个新类，此时新原始分类变为n—1个；计算n—1个新分类两两之间的距离，合并类间距离最小的两类再次形成一个新类，由此，新原始分类变为n—2个；依次迭代进行，直到得到期望的最佳分类个数。

分别利用本文算法和传统算法进行聚类，聚类结果如图4、5所示。

图4 本文算法聚类结果

图5 对比算法聚类结果

3.3 评价指标

CR指数（Corrected Rand Index）是用来衡量同一数据集的2个不同划分之间差异的指标，最早由Hubert等［18］提出，其定义如下：

设 有n个 样 品，U=｛u1，…，ui，…，uR｝，V=｛υ1，…，υj，…，υC｝是这同一组样品的2个不同的划分，分别包含R类和C类，则指数

CR指数取值在［—1，1］之间，其值越接近于1，表示U和V两种划分越趋于一致；反之，其值接近0或为负时说明两种划分差异较大。CR指数是一种外部评价指标，即通过对比聚类结果和原始给定正确的类别信息来衡量聚类性能的优劣，其计算结果不受聚类分析算法所选择距离度量的影响，较为公正客观，但只能应用于标准先验聚类划分已知的情况。在随机模拟中，通常令U为原始先验划分，V为通过聚类分析得到的划分结果，因此，可以利用CR指数反映它们之间的差距，指数越接近于1，表明聚类结果越接近于真实的划分，对应的聚类算法则更有效。

3.4 聚类结果分析

用CR指数衡量聚类结果，并将聚类结果与先验类别对比，形成聚类正确率，结果如表1所示。

表1 聚类结果对比

由表1可以看出，本文算法聚类结果24条曲线中仅有1条划分错误，准确率达到95.8%，而对比算法准确率仅为75%，因此，本文算法的聚类结果与实际结果更接近，要优于传统聚类算法。通过CR指数也可以看出，本文算法在对数据进行深入挖掘时，更能充分利用函数型数据的信息对数据进行有效的划分。

4 实例应用

4.1 聚类分析

为验证本文算法在实际应用中的有效性，选取40个国家1970～2010年的人均GDP数据，运用本文分步系统聚类算法对其进行聚类分析。首先，根据原始数据生成函数型数据［19］，如图6所示。

对40个国家按实际距离进行第1步聚类，聚类结果如图7所示。

图6 各国人均GDP曲线

图7 第1步聚类结果

由图7可见，第1步聚类将40个国家分为A、B、C等3类。A类为澳大利亚、丹麦、加拿大、美国。B类为奥地利、比利时、芬兰、法国、德国、意大利、日本、荷兰。C类为阿富汗、阿尔巴尼亚、阿尔及利亚、巴林、孟加拉共和国、不丹等。

A类属于发达国家，经济发展比较稳定，1970～2010年人均GDP一直处于世界前列；B类也属于发达国家，但与A类不同的是，这些国家在70年代人均GDP较低，但发展较快，GDP水平快速提高，有的甚至超过了A类国家，实际划分也将这些国家划分到发达国家的行列；C类国家比较多，进行进一步聚类可以得到更精确的结果，但是第3类国家人均GDP都比较低，继续用实际距离进行聚类意义不大。

运用本文算法的第2步进行聚类，即根据导函数距离进行聚类，结果如图8所示。

第2步聚类将C类又分为C1和C2两类。C1为阿富汗、阿尔巴尼亚、孟加拉共和国、不丹、中国、布基纳法索等。C2为阿尔及利亚、巴林、不丹、保加利亚、哥伦比亚、埃及、加纳、圭亚那、肯尼亚等。

由图8可见，C1类国家虽然仍属于不发达国家，但经济发展十分迅速，而C2类国家的经济发展十分缓慢。

图8 最终聚类结果

4.2 基于分步系统聚类算法的函数型数据补齐方法

作为本文分步系统聚类算法的一个重要应用，本文还提出了一种基于本文算法的函数型数据补齐方法。其基本思想是：首先，利用本文算法对函数型数据进行聚类，找到与目标函数型数据距离接近、形态特征相似的若干个同类；然后，利用同类中已知函数型数据的均值对目标函数型数据中的缺失数据进行补齐。该数据补齐方法根据数据变化特征和均值对缺失数据进行补齐，是时间和空间两方面的有效结合，不仅可以保证补齐数据在距离上与实际数据相接近，而且可以保证与原始数据保持相似的变化规律。且其将同类中所有已知函数型数据引入算法中来，能有效减少“噪声”的影响。

以4.1节中数据为例，假设圭亚那2000～2010年的人均GDP数据未知，圭亚那属于C2类国家，因此，利用C2类中其他国家2000～2010年的人均GDP均值对圭亚那的人均GDP进行补齐，实验结果如图9所示。

图9 数据补齐

由图9可见，预测结果曲线与实际值曲线不仅在距离上接近，而且具有相同的变化特征，表明该方法能够对函数型数据中的缺失值进行有效地补齐。由于实验条件的限制，本文算法收集到的数据有限，数据量较小，实验中未能取得非常精确的结果，就统计学意义上而言不够恰当，但本部分实验的主要目的是为了更好地描述本文提出的函数型数据补齐方法，而不在于得到精确地数据结果，在以后的研究应用或实际应用中应选择大数据进行实验，以得到更加精确的实验结果。

5 结语

在对传统聚类算法研究的基础上，根据函数型数据的特点，将导函数距离引入函数型数据的聚类中来，将实际距离和导函数距离相结合作为聚类标准，提出了基于函数型数据实际距离和导函数距离的分步系统聚类算法，使聚类结果不仅能够在距离上接近，而且可以保证同类数据具有相似的形态特征。利用随机模拟对算法的有效性进行了检验，并针对40个国家41年的人均GDP数据进行了实例研究，模拟实验和实例研究结果均表明，该算法能够对函数型数据进行有效聚类。最后，在此基础上，提出了一种基于函数型数据分步系统聚类算法的数据补齐方法，实例研究结果表明，该方法能够对函数型数据进行有效地补齐。