多属性单一趋势结构时序数据的聚类模型

吴明辉，许爱强，孙伟超，裘璐光

（1.海军航空工程学院科研部，山东 烟台264001；2.中国人民解放军92957部队，浙江 舟山316000）

0 引 言

为解决 “数据丰富而知识贫乏”的矛盾［1］，利用现代智能技术对时序数据进行数据挖掘，以获得更多隐藏在数据背后的知识和信息［2，3］。

文献 ［3］对时序数据的趋势结构进行了定义，并对子序列单一趋势结构 （非降k－时间子序列）的数据挖掘进行了研究。实际研究中，存在着整个时序数据为单一趋势结构的情况，例如，能够反映设备健康状况的多参数监测时序数据，在理想情况下，只要不对设备进行维修，这些时序数据所反映的设备健康状态应是非升趋势的。通过对设备从正常态到故障态的整个时序数据进行聚类分析，可以明确设备健康状态等级，为设备的健康状态判定和维修决策提供依据。

本文针对多属性单一趋势结构时序数据的特点，建立了加权相似度度量的权值优化模型，并利用改进粒子群的方法进行了模型求解；在此基础上，为克服模糊C均值（fuzzy C－means，FCM）聚类算法的初始中心敏感等问题，利用免疫遗传算法对FCM聚类算法进行了改进，构建了一种针对多属性单一趋势结构时序数据的聚类模型。

1 时序数据的趋势结构

文献 ［3］给出的是单属性时序数据趋势结构的定义，具有一定的局限性，借鉴其思想，本文给出了多属性时序数据的趋势结构定义。

定义1 给定一个多属性时序数据X＝ ｛Xt｜t＝1，…，n；Xt∈Rp｝，t是时间标识，p是属性维数。如果存在映射 yt＝f（Xt），yt∈R，且 有 yt＋1≥yt（或 yt＋1≤yt），则：

（1）如果t＝j，j＋1，…，j＋k （j≥1，j＋k≤n），称X＝ ｛X︱t＝j，j＋1，…，j＋k；Xt∈Rp｝为关于映射f（Xt）的非降 （非升）k－时间子序列；

（2）如果t＝1，…，n，称X＝ ｛X︱t＝1，…，n；Xt∈Rp｝为关于映射f（Xt）的非降 （非升）时间序列，即整个序列为单一趋势结构的时序数据。

2 加权相似度度量

2.1 加权相似度度量的确立

数据聚类分析建立在相似度度量的基础上［4］，相似度反映了数据间的结构关系，根据聚类需求采用不同的相似度度量能够产生不同的聚类结果。基于距离的相似度度量是较常用的一种相似度度量方法，例如欧氏距离、马氏距离等，但数据结构固定，忽略了不同属性的影响程度，泛化能力差。通过加权距离的方式可以较好的解决上述问题，但权值的确立是一个难点问题。

属性权值影响数据的空间结构，由于扰动、噪声和属性本身的特性致使各属性呈现出非单调性和随机性，单一趋势结构时序数据的所有属性却又决定了对象整体特性的单调性。因此，本文认为通过合理的加权距离应能较好的拟合这种属性随机性和整体单调性的时序数据的相似度。不失一般性，以初始时刻X1为基准点，建立如下时序空间到加权距离空间的映射，即其它样本点与基准点的加权相似度度量

建立函数

则加权值的确立转换成如下最优化问题

目标函数反映了加权距离对单一趋势结构时序数据的拟合程度。

2.2 基于改进PSO的权值计算

粒子群算法 （particle swarm optimization，PSO）是一种基于群体群智能方法的启发式演化计算方法，是一种具有竞争力的优化问题求解算法［5－7］。PSO在处理约束优化问题时，常用的方法有惩罚函数法［6］、外点法［7］等，主要用于解决多约束条件优化问题的求解，但这些方法普遍存在搜索效率低、外加参数设置缺乏依据等问题。式 （3）权值优化模型的约束条件简单有限，本文对标准PSO算法 （带惯性因子）进行了改进，利用约束条件对粒子各属性的飞行速度进行动态设定，使算法搜索空间限定在可行域内。标准PSO算法的粒子更新公式为

ω是惯性因子，起到平衡局部和全局搜索能力的作用，为提高早期全局搜索能力和后期局部搜索能力，ω可按随迭代次数呈线性减少的方式进行设定［8］；pik为第i个粒子经历的最佳位置，pgk为群体经历的最佳位置；c1和c2为学习因子，使粒子具有自我总结和向群体中优秀粒子学习的能力；r1和r2为 ［0，1］之间的随机数，用以保持群体的多样性；由于没有机制控制速度v，因此需要对其最小、最大值进行设定，在标准PSO中速度v的范围是固定不变的，本文利用约束条件对速度v进行以下动态设置

在进行下一代粒子更新时，式 （5）是对第1个属性速度最大值的限定，式 （6）是对第2～p－1个属性速度最大值的限定，而第p个属性的速度不是按照式 （4）而是按照式 （7）的方式进行更新，通过式 （5）～式 （7）可满足约束条件

式 （8）是对各属性最小速度的限定，通过该式可满足约束条件

ε1和ε2是取值范围为 （0，1］的参量，可以在可行域内控制最大、最小速度更新的范围。

模型停止准则通过目标函数的收敛程度或更新代数来确定，假定目标函数连续3代相邻差值小于给定误差μ或更新代数大于Imax，则模型停止运行。通过式 （4）～式（8）可完成式 （3）权值优化模型的求解。

3 改进FCM的加权聚类模型

聚类是数据挖掘中的一类重要技术，是分析数据并从中发现有用信息的一种有效手段。目前，聚类方法主要包括划分方法、层次方法、基于密度的方法和基于网格的方法等几类［9］。模糊C－均值 （FCM）是一种基于划分的传统聚类方法，具有较强的局部搜索能力，并以其简单、快速的特点而被广泛应用［10］。

3.1 FCM聚类方法

设给定数据样本为D＝ ｛di︱di＝RN｝，i＝1，…，n，N为样本维数；c（2≤c≤n－1）为分类数，V＝ ｛vj︱vj∈Rp，j＝1，…，c｝为聚类中心；U＝ ｛uijuij∈ ［0，1］；i＝1，…，n；j＝1，…，c｝为模糊分类矩阵，uij表示第i个样本属于第j类的隶属度；FCM算法可表示成以下最优化问题

按照上式不断更新聚类中心和聚类隶属度，使目标函数Jb收敛到最小值。FCM算法具有较强的局部搜索能力，但对初值敏感，且是基于梯度下降的算法，不可避免地陷于局部极小值。

3.2 基于FCM的免疫遗传聚类方法

针对FCM算法初值敏感的问题，本文通过引入遗传机制的方式对FCM算法进行改进，将FCM的目标函数作为搜索因子，利用交叉、变异等遗传操作提高算法全局搜索能力，发挥遗传算法的并行机制，提高算法的运行效率。

另外，为克服遗传算法的 “早熟”收敛问题，本文在遗传选择操作中借鉴免疫机理，通过引入个体浓度算子，使个体浓度算子和个体适应度来共同决定个体的选择概率，在使得适应度高的个体得到以留的同时，抑制个体浓度大的个体被选择，保证进化群体中个体的多样性，降低 “早熟”收敛的可能性。整个聚类算法的设计步骤如下：

步骤1 个体编码。采用基于聚类中心的编码方式［11］，数据类型为浮点数，即每个个体编码是长度为c×P个基因位的浮点数串，c是选定的c个聚类中心，P是属性维数。

步骤2 个体适应度函数。以FCM算法目标函数Jb为搜索因子，设置第i个个体适应度函数为

步骤3 选择操作。通过引入免疫算子的选择操作概率为

步骤4 交叉操作。为保证交叉操作的局部搜索能力和全局一致性，参考文献 ［12］的方法，对参与交叉操作的个体进行基于最邻近法则的基因位匹配，即对待进行交叉操作的两个个体，以其中一个为基准，对另一个体的基因进行重新排序，使两个个体对应基因位之间的加权距离最小，然后再以一定概率Pc进行单点交叉操作。

步骤5 变异操作。以一定的变异概率Pm进行基因位的变异操作，操作方法是对该基因位值在属性范围内进行随机变异，例如待变异基因位值为d，变异后用d’代替，d’＝dmin＋γ （dmax－dmin），γ为 （0，1）范围的随机数，dmax和dmin是该基因位所代表属性的最大值和最小值。

模型停止也是通过目标函数的收敛程度或更新代数来确定，假定目标函数连续3代相邻差值小于给定误差ε及更新代数大于Tmax。

4 实例验证

状态监测是实现设备故障预测及健康管理的一个重要手段，通过合理选择设备参数，并对这些参数进行在线或离线周期性监测，可以获取用于判断设备健康状态的信息。设备从初始态 （完好态）到故障态的多参数状态监测数据是表征设备健康状态不断降低的一系列多属性单一趋势结构的时序数据，通过对这些数据进行聚类分析，可以明确不同监测数据下设备所处的健康等级，为设备的维修决策提供信息输入。

动调陀螺仪是一种机电一体化的精密航空惯性敏感设备，其健康状态对飞行器的飞控、导航等均会产生重要的影响。本文选用某机载用动调陀螺仪为研究对象，选取振动、温度、随机漂移、电机功率、电源电压等5个运行参量作为监测对象，获得了4个该型动调陀螺仪从正常态到故障态5个选定参量的时序检测数据，共763组，规范化后，对其进行健康状态划分，验证本文所提出聚类模型。

4.1 属性权值确定

对粒子群进行初始化和参数设定，参照文献 ［13］对PSO参数设定的相关论述，设定种群规模为N＝40，惯性权重从ωmax＝0.9线性减小到ωmin＝0.4最大迭代次数Imax＝100，学习因子c1＝c2＝2，速度控制因子ε1＝ε2＝0.8，由于式 （3）的目标函数值是正整数，因此要求误差μ＝0。利用以上规范化后的时序数据，分别采用本文提出的改进PSO （标记为PSO－v）、文献 ［6］采用外点法处理约束条件的PSO （标记为PSO－o）及文献 ［7］使用惩罚函数处理约束条件的PSO （标记为PSO－c）对式 （1）～式（3）所构建的约束优化模型进行求解，各算法运行5次后的目标函数值及运行时间见表1，各算法最佳运行结果的更新曲线如图1所示。

表1 各算法运行结果比照

图1 各算法最佳运行结果更新曲线

运行结果表明，在没有权重分配时，目标函数值为323，而采用不同方法对权重进行分配后，目标函数值都有明显的下降，这充分说明了采用加权处理的必要性。而本文所提的改进PSO方法无论是收敛精度还是收敛速度上都具有明显的优势，这主要得益于粒子的搜索空间一直保持在可行域内，而其它两种方法都不可避免的在非可行域里搜索。但需要说明的是，本文改进的PSO方法是将约束条件转化成对搜索域的限定，而对于复杂多约束条件的优化问题其搜索域的限定具有一定的难度。

通过本文改进PSO方法获得振动、温度、随机漂移、电机功率、电源电压5个参量的权重值依次为：ω1＝0.412、ω2＝0.174、ω3＝0.247、ω4＝0.102、ω5＝0.065。剩余31个对趋势结构具有破坏性的数据样本 （可能是测量误差导致），作为无效样本剔除。

4.2 聚类结果分析

对该型动调陀螺仪的健康状态划分成5类，分别表示“健康、亚健康、合格、异常和故障”［14］，即置聚类数c＝5。对以上数据进行规范化后，设模糊控制权重b＝2，群体规模N＝80，选择控制因子α＝0.75，交叉概率Pc＝0.8，变异概率Pm＝0.005，误差ε＝1×10－5，最大进化代数Tmax＝100。结合上述权重计算结果，利用本文所提的加权FCM的免疫遗传聚类方法 （标记为IGA－FCM＋）与加权FCM聚类方法 （标记为FCM＋）及加权FCM的遗传聚类方法 （标记为GA－FCM＋）进行比较分析。各聚类算法目标函数的最优值及运行时间见表2，目标函数Jb随进化代数G的进化趋势如图2所示。

表2 各聚类算法的运行结果

图2 各算法目标函数随进化代数的进化趋势曲线

结果表明本文所提的加权FCM免疫遗传聚类方法具有较高的收敛精度，单纯的加权FCM聚类方法虽然收敛速度较快，但收敛精度较差，易陷入局部点，而对选择操作未经改进的加权FCM遗传聚类方法在收敛精度和收敛速度上都不如本文所提的方法。通过聚类分析，可以明确各个监测数据所描述的设备健康状态情况，为设备的健康状态评估提供数据支撑。

5 结束语

本文针对一类特殊的时序数据开展聚类分析研究。首先，给出了单一趋势结构时序数据的定义，针对单一趋势结构时序数据的特点，确立了加权相似度度量的权值优化模型，并利用改进的PSO算法对模型进行了求解；其次，针对传统FCM聚类方法的易陷局部点等问题，提出了加权IGA－FCM的聚类方法；最后，通过对动调陀螺仪进行健康状态聚类的实例，验证了本文所提权值优化模型及其求解方法和聚类方法的有效性。

［1］LI Hailin，GUO Chonghui.Survey of feature representations and similarity measurements in time series data mining ［J］.Application Research of Computers，2013，30 （5）：1285－1291（in Chinese）.［李海林，郭崇慧.时间序列数据挖掘中特征表示与相似性度量研究综述 ［J］.计算机应用研究，2013，30（5）：1285－1291.］

［2］WANG Xiaofeng.Application of time series data mining in the medical field ［J］.Software Guide，2011，10 （5）：123－124（in Chinese）.［王晓锋.时间序列数据挖掘在医疗领域的应用［J］.软件导刊，2011，10 （5）：123－124.］

［3］WANG Yong，ZHANG Xinzheng.Time series data mining technique based on varying series ［J］.Journal of Nanjing University of Aeronautics ＆ Astronautics，2006，38 （7）：54－57（in Chinese）.［王勇，张新政.基于变化序列的时序数据挖掘技术 ［J］.南京航空航天大学学报，2006，38 （7）：54－57.］

［4］DONG Xiaoli，GU Chengkui，WANG Zheng’ou.Research on shape－based time series similarity measure ［J］.Journal of Electronics ＆Information Technology，2007，29 （5）：1228－1232（in Chinese）.［董晓莉，顾成奎，王正欧.基于形态的时间序列相似性度量 ［J］.电子与信息学报，2007，29 （5）：1228－1232.］

［5］LUO Jinyan.Particle swarm optimization to nonlinear constrained optimization problem ［J］.Journal of Wenzhou University （Natural Sciences），2012，33 （1）：1－5 （in Chinese）.［罗金炎.一种求解非线性约束优化问题的粒子群优化算法［J］.温州大学学报 （自然科学版），2012，33 （1）：1－5.］

［6］LIU Wei，CAI Qianfeng，LIU Hailin.A new particle swarm algorithm for solving constrained optimization ［J］.Computer Applications and Software，2008，25 （8）：254－256 （in Chinese）. ［刘伟，蔡前凤，刘海林.一种求解约束优化问题的新粒子群算法［J］.计算机应用与软件，2008，25 （8）：254－256.］

［7］LU Haiyan，CHEN Weiqi.Self－adaptive velocity particle swarm optimization for solving constrained optimization problem［J］.Journal of Global Optimization，2008，41 （3）：427－445.

［8］GAO Liqun，LI Ruoping，ZOU Dexuan.A global particle swarm optimization algorithm ［J］.Journal of Northeastern University （Natural Science），2011，32 （11）：1538－1541 （in Chinese）.［高立群，李若平，邹德旋.全局粒子群优化算法［J］.东 北 大 学 学 报 （自 然 科 学 版），2011，32 （11）：1538－1541.］

［9］XU Wenjie，LIU Xiyu.Clustering analysis based on modified immune genetic algorithm and its application ［J］.Journal of Computer Science，2008，35 （1）：204－210 （in Chinese）.［许文杰，刘希玉.基于改进免疫遗传算法的聚类分析研究与应用［J］.计算机科学，2008，35 （1）：204－210.］

［10］LIU Ruijie，ZHANG Jinbo，LIU Rui.Fuzzy C－means clustering algorithm ［J］.Journal of Chongqing Institute of Technology （Natural Science），2008，22 （2）：139－141 （in Chinese）.［刘蕊洁，张金波，刘锐.模糊C均值聚类算法 ［J］.重庆工学院学报 （自然科学版），2008，22 （2）：139－141.］

［11］SITU Ying.Parameters setting of PID controller based on new immune genetic algorithm ［J］.Computer Engineering and Design，2009，30 （10）：2461－2463 （in Chinese）.［司徒莹.基于免疫遗传新算法的PID参数整定 ［J］.计算机工程与设计，2009，30 （10）：2461－2463.］

［12］XU Jianing，ZHANG Liwen，XU Suli，et al.Research on K－means clustering algorithm based on improved genetic algorithm ［J］.Microcomputer Applications，2010，31 （4）：11－15（in Chinese）.［徐家宁，张立文，徐素莉，等.改进遗传算法的K－均值聚类算法研究 ［J］.微计算机应用，2010，31（4）：11－15.］

［13］LI Xiangyong，TIAN Peng，KONG Min.A new particle swarm optimization for solving constrained optimization problems ［J］.Journal of Systems ＆ Management，2007，16（2）：120－129 （in Chinese）. ［李相勇，田澎，孔民.解约束优化问题的新粒子群算法 ［J］.系统管理学报，2007，16（2）：120－129.］

［14］WANG Yankai，LIAO Mingfu.Study on grading of health condition of aerospace propulsion system ［J］.Journal of Aerospace Power，2008，23 （5）：939－945 （in Chinese）.［王俨剀，廖明夫.航空发动机健康等级综合评价方法 ［J］.航空动力学报，2008，23 （5）：939－945.］