一种函数型模糊聚类算法及其应用

杨梦玲

摘要：针对已有模糊聚类算法（FCM）提出一种函数型模糊聚类算法，旨在解决海量数据的模糊聚类问题。为此，在利用B-样条基底进行曲线拟合、曲线距离度量界定的基础上，构造模糊聚类算法的目标函数，提出函数型模糊曲线聚类算法。模拟及实例表明：本文曲线聚类算法具有更好的聚类效果。

关键词：曲线拟合;模糊聚类;B-样条;距离度量

中图分类号：TP311.1 文献标志码：A 文章编号：1008-4657（2019）05-0018-08

0 引言

信息技术的发展，数据来源越来越广泛。数据采集密集化程度也越来越高。随之出现一种具有明显曲线特征的数据类型，如脑电信号数据、基因序列数据、股票分时成交价数据、环境污染物浓度数据等，就具有这样的特征。相关文献称之为函数型数据（Functional Data）[1]。

实际数据采集中，获取的数据通常为离散数据，无法直接获取函数型数据。针对离散数据可以通过传统多元统计方法分析。但是传统的多元统计方法无法分析数据的函数型特征，同时也需要处理高维问题。因此，基于传统统计分析方法往往无法取得较好的分析结果。针对函数型数据的曲线特征，人们提出很多分析方法，包括函数型主成分[2]、函数型聚类分析[3]等。这类方法在函数型数据分析中发挥着重要的作用。

从方法角度来看，目前函数型数据分析方法大致分为两类：一类是原始数据法[4]，原始数据法是一种高维数据分析方法，该类方法直接针对离散样本点进行聚类。尽管能取得一定结果，但是没有考虑到数据的函数型特征。因此无法深入挖掘数据的潜在特征且计算成本大。第二类是投影方法[5-6]，通过有限维基底函数逼近曲线，将无限维问题转化为有限维问题进行分析。根据基底函数系数的处理方式不同，又可将投影方法分为滤波法和自适应法。滤波法将基底函数对应系数设定为固定参数，分曲线拟合和聚类分析两步展开[6-7]。自适应法是将基底函数对应的系数作为随机变量处理，将曲线拟合和聚类分析纳入一个目标函数，采用类似最大期望（Expectation-Maximization）算法，同时进行优化[8-9]。此外，还有基于距离的聚类方法，如K-means聚类算法和分层聚类算法。这类算法考虑利用特殊距离或构造“曲线距离”等进行聚类，如果距离可以用离散的样本点形成的曲线构造，则该类算法与原始聚类算法等价，如果聚类可以用有限基底进行逼近，则该类算法与自适应算法等价。

从聚类结果来看，函数型数据分析方法大致可以分为“硬”聚类和“软”聚类两种。“硬”聚类将聚类结果分为是（1）和否（0）;“软”聚类考虑到了聚类的隶属度问题，将聚类结果分为[0，1]，和硬聚类相比较，能够获得更丰富的聚类信息，但是聚类时间冗长[10]。

自1973年Dunn[11]提出了模糊C均值（Fuzzy C-Means，FCM）聚类算法，在聚类、图象分割、形状分析、医疗诊断、特征选择等领域具有广泛的应用。将函数型数据应用到FCM聚类算法具有重要的实际意义。近些年关于函数型FCM算法的研究很多，如核函数与FCM结合的聚类算法[12]、自适应FCM聚类算法[13]、以及基于投影的FCM聚類算法[14]等，验证出函数型FCM算法具有较好的聚类效果。还有学者指出[15]，通过子空间聚类，可以在降低数据维度的同时最大化原始空间的聚类信息。

结合函数型数据和降维思想，本文提出一种改进函数型FCM聚类方法，在FCM聚类算法的基础上利用B-样条基底逼近原始离散数据，对FCM聚类算法进行改进，并在此基础上加入投影算子，以达到降低维度的目的。与函数型K-means聚类算法在模拟和实证上进行对比分析，本文改进方法具有较好的聚类效果。

1 改进函数型FCM聚类算法

该部分从以下三个方面进行阐述：第一，利用B-样条基底近似原始数据，在一定假设条件下对拟合曲线进行截断，从而将观测到的原始离散数据生成为函数型数据。第二，基于上述基于距离的聚类算法，定义曲线之间的“距离”，并通过楚列斯基分解（Cholesky Decomposition）得到适用于本文非正交基函数的曲线距离，将曲线距离转化为传统欧氏距离。第三，将构造的距离作为曲线亲疏的度量，构建函数型FCM聚类算法目标函数，实现函数型FCM聚类。

1.1 构建B-样条基底

经过上述转化，将曲线聚类问题转化为利用计算特征向量的问题，利用降维及模糊聚类方法完成聚类。

利用计算机对函数型FCM算法进行编程，直到目标函数（11）达到最小。算法流程如下：

Input：xkk=1，2，…，N，u，m max iterate

Initialize：randomly choose initialvii=1，2，…，c

Forj≠i

Repeat

Use （12） fix U to solve V

Use（13）fix V to solve U

Until convergence.

2 模拟分析与实证

为验证聚类效果，在这一部分对本文算法进行模拟和实证分析。并与函数型K-means聚类算法进行比较。其中模拟部分为带有标签的数据，评价指标选择错判率和兰德指数（Rand Index），实例部分为无标签数据集，评价指标选择戴维森堡丁指数（Davies-Bouldin Index）。比较结果表明本文算法在聚类精确度方面优于后者聚类算法。

2.1 随机模拟试验

利用R软件rnorm（）函数生成均值和方差分别为（1，1）、（2，2）、（3，3）、（4，4）的4类高斯分布数据，每一类产生600组服从对应均值和方差的随机数，共计600*4个数据。为避免生成随机数数值大小相近，数据生成过程中统一为每一类数据乘以倍数3并分别为每一类加上常数5、7、9、11。同时考虑到数据的简洁性，在编程过程中对数据取整。数据生成后利用构造的B-样条基底，将离散数据点转化为曲线，构造的曲线距离及提出的算法进行聚类分析。考虑到模拟数据来自4类不同参数下生成的数据，为便于比较，在利用本文算法进行聚类时聚为4类且设定数据的区间长度为12。分别利用本文算法和K-means聚类算法进行聚类分析，如图1所示。

图1中横坐标表示设定的聚类区间长度为[0，12]，纵坐标表示模拟数据数值，每一类具有不同的颜色和形状。图1（a）、（b）表示两种聚类算法的类中心曲线，图1（c）、（d）表示聚类曲线。图1聚类结果表明：不同类别数据存在一定差异，这种差异来自整体水平即均值以及类别数据波动性即方差。图1（a）、（b）不同的类中心曲线以及（c）、（d）聚类曲线不同颜色曲线的分布情况来看，本文算法具有较好的类别区分型能。不同颜色的曲线差异较为明显。进一步，为便于比较聚类效果，在生成数据过程中对每一类数据加入类别标签。与原始类别进行比较，计算两种方法的错判率（错误分类个数/总个数*100%）和兰德指数[20]。

兰德指数计算公式如下

其中TP表示应该被聚为一类的数据被正确聚为一类，TN表示不应该被聚在一類的数据未被聚为一类，FP表示不应该聚在一类的两类数据被聚为一类，FN表示应该被聚为一类的数据未被聚为一类。

根据上述描述，得到下表1、2。

表1中，通过两种聚类方法得到的类别标签与模拟数据原始类别标签进行对比，发现本文方法正确分类的个数多于K-means聚类方法。因此相应错判率低于K-means聚类方法。

表2中，将模拟数据量从600不断增加到2 400，检验两种聚类算法聚类效果的兰德指数逐渐提高。通过两种算法的对比，本文算法的兰德指数相较于函数型K-means有所提升。

2.2 应用举例

空气质量与人们的生活息息相关，近几年关于空气质量方面的研究也很多，包括省市县空气质量污染聚类问题[21]，也包括珠三角、京津冀地区空气污染与相关因素的分析[22-23]等。本文数据采用兰州市NO2浓度（μg·m-3）小时数据，因兰州地理位置较为特殊，地处黄土高原、青藏高原和蒙古高原三大高原的交汇地带，两边地势高，中间地势低，且气候干燥，植被覆盖少等原因使得兰州市空气质量问题十分严重[24]。因此，准确分析兰州市空气质量问题具有十分重要的实际意义。

实证数据来自兰州市铁路设计院站点采集的NO2小时浓度数据，采集时间为2013年6月1日～10月14日。除删去66个缺失值外共得到128*24个NO2小时浓度数据。基于B-样条基底拟合原始离散数据点，构造函数型曲线。利用R软件进行编程，实现曲线的聚类分析。由于实例数据为无标签数据。为检验两种聚类算法的聚类效果，本文引入无类别标签的戴维森堡丁指数[25]（Davies-Bouldin Index）作为评价指标，该指数计算公式如下

其中C-i和C-j表示任意i类和j类的类内平均距离。wi和wj表示i类和j类的类中心。DB越小意味着类内距离越小且类间距离越大。考虑类别个数为3、4、5、6类的情形下，戴维森保丁指数的变化情况。如下表3所示：

表3中，随着类别个数的增加，戴维森保丁指数在逐渐下降，说明类别个数的增加会使得类内间距越小且类间间距越大。表明不同类的聚类曲线差异性越大，类别区分度越发明显。综合比较两种聚类算法，本文算法在实例应用中聚类效果相比于K-means聚类算法较好。

进一步，分别画出本文算法与函数型K-means算法的类中心曲线以及聚类效果曲线。两种算法均采用相同的B-样条基底和节点设计。得到两类聚类结果。考虑论文篇幅，仅对4类聚类效果进行展示，如图2所示。

与图1类似，图2中横坐标表示时间，纵坐标表示实例数据数值。每一类具有不同的颜色和形状，从图2（a）、（b）类中心聚类结果表明，本文算法中不同类别的类中心曲线未出现类中心曲线交叉的情形。说明本文算法具有较好的类别区分性能。图2（c）、（d）中显示一天中在6：00-10：00和17：00-21：00两个区间段内NO2浓度逐渐上升并达到顶峰，这与实际中早高峰和晚高峰的情况相吻合，且夜间21：00-次日5：00仍存在较高浓度，这种明显的趋势为政府污染治理提供一定依据，如错峰出行等。

3 结论

聚类分析是函数型数据探索分析的重要部分，函数型曲线聚类方法在现今数据密集化程度不断提高的时代值得探讨。基于FCM聚类算法，提出一种函数型FCM聚类算法。在构建B-样条基底、定义曲线距离之后，对本文算法进行理论推导，并利用R语言对算法进行实现。为验证本文模型的聚类效果，在模拟和实例部分与函数型K-means聚类算法进行比较，模拟和实例结果表明，本文的曲线聚类算法有助于提高聚类效果。与此同时，实例的应用对兰州市空气质量监测的预测以及污染物来源分析也有一定辅助作用。

参考文献：

[1]Ramsay J O.When the Data are Functions[J].Psychometrika.1982，47（4）：379-396.

[2]Ramsay J O，Silverman B W.Functional Data Analysis[M].2ed.New York：Springer，2005：1-18.

[3]Ferraty F，Vieu P.Nonparametric Functional Data Analysis：Theory and Practice[M].New York：Springer，2006：11-18.

[4]Bouveyron C，Brunet-Saumard C.Model-based Clustering of High-dimensional Data：A Review[J].Computational Statistics & Data Analysis.2014，71（1）：52-78.

[5]Abraham C，Cornillon P A，Matzner-Lber E，et al.Unsupervised Curve Clustering Using B-splines[J].Scandinavian Journal of Statistics.2003，30（3）：581-595.

[6]黄恒君.基于B-样条基底展开的曲线聚类方法[J].统计与信息论坛.2013，28（9）：3-8.

[7]Kayano M，Dozono K，Konishi S.Functional Cluster Analysis Via Orthonormalized Gaussian Basis Expansions and Its Application[J].Journal of Classification.2010，27（2）：211-230.

[8]Jacques J，Preda C.Funclust：A Curves Clustering Method Using Functional Random Variables Density Approximation[J].Neurocomputing.2013，112（10）：164-171.

[9]Jacques J，Preda C.Model-based Clustering for Multivariate Functional Data[J].Computational Statistics & Data Analysis.2014，71（3）：92-106.

[10]谢维信，刘健庄.硬聚类和模糊聚类的结合——双层FCM快速算法[J].模糊系统与数学.1992（2）：77-85.

[11]Dunn J C.A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-separated Clusters[J].Journal of Cybernetics.1973，3（3）：32-57.

[12]Sridevi P.Identification of Suitable Membership and Kernel Function for FCM Based FSVM Classifier Model[J].Cluster Computing，2018（6）：1-10.

[13]林甲祥，吳丽萍，巫建伟，等.基于样本与特征双加权的自适应FCM聚类算法[J].黑龙江大学自然科学学报.2018，35（2）：244-252.

[14]Kiani M，Andreu-Perez J，Papageorgiou E I.Improved Estimation of Effective Brain Connectivity in Functional Neuroimaging through Higher Order Fuzzy Cognitive Maps[C]//2017 IEEE International Conference on Fuzzy Systems （FUZZ-IEEE）.IEEE，2017：1-6.

[15]Bezdek J C，Ehrlich R，Full W.FCM：The Fuzzy C-means Clustering Algorithm[J].Computers & Geosciences.1984，10（2）：191-203.

[16]Yamamoto M.Clustering of Functional Data in a Low-dimensional Subspace[J].Advances in Data Analysis & Classification.2012，6（3）：219-247.

[17]Rice J A，Silverman B W.Estimating the Mean and Covariance Structure Nonparametrically When the Data are Curves[J].Journal of the Royal Statistical Society.1991，53（1）：233-243.

[18]De Leeuw J，Young F W，Takane Y.Additive Structure in Qualitative Data：An Alternating Least Squares Method with Optimal Scaling Features[J].Psychometrika，1976，41（4）：471-503.

[19]Birman M S，Solomjak M Z.Spectral Theory of Self-adjoint Operators in Hilbert Space[M].New York，NY，USA：D.Reidel Publishing Co.，Inc.，1986：18-59.

[20]Jain A K，Dubes R C.Algorithms for Clustering Data[J].Technometrics.1988，32（2）：227-229.

[21]郦少将.基于函数型聚类的浙江省空气污染时空特征分析[J].河南教育学院学报（自然科学版）.2018，27（1）：19-24.

[22]周学思，廖志恒，王萌，等.2013—2016年珠海地区臭氧浓度特征及其与气象因素的关系[J].环境科学学报.2019，39（1）：143-153.

[23]梁银双，刘黎明，卢媛.基于函数型数据聚类的京津冀空气污染特征分析[J].调研世界.2017（5）：43.

[24]祁斌，王式功，刘宇，等.兰州市空气污染气象条件综合分析[J].陕西气象.2001（6）：27-30.

[25]Davies D L，Bouldin D W.A Cluster Separation Measure[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1979（2）：224-227.

[责任编辑：郑笔耕]