分析2019Neurocomputing 1区论文Multivariate time series clustering based on common principal component analysis
论文来源：https://www.researchgate.net/publication/332536648_Multivariate_time_series_clustering_based_on_common_principal_component_analysis
论文作者：中国华侨大学 Hailin Li
论文代码：在实验部分只提到使用MATLAB2010，但尚未见公开
论文语言风格比较适合Chinese，共PDF20页，可一天读完，在此做下阅读分析和感悟。
一、论文总体框架
一共分为5个部分，
1、Introduction：介绍一元时序数据和多元时序数据的各自常用方法，分析DTW的困境，列举基于传统方法之上需要继续研究的3个问题，最后阐述本文所解决的问题以及算法思路。
2、Preliminaries：简要介绍PCA，涉及到协方差矩阵和奇异值分解。需要了解主成分分析法，作者提出的算法也是基于此。
3、 MTS clustering based on CPCA：本文的一个核心部分，可以分为这几个部分，第一是提出要融合DTW和PCA的特点（PCA关注变量之间的关系，DTW关注序列（MTS）的值）；第二是对问题的描述；第三是算法描述，画出框架图；第四是时间复杂度分析。
4、Experimental evaluation，作者分为了三个部分：数据库、算法结果对比展示和时间consumption对比
1. Introduction
第一段：研究背景、对象和价值。引出时序数据
时序数据在股票交易、经融市场、医疗和工程等领域随处可见，对于获取有价值的信息和知识来说是一个重要数据。时序数据根据变量的多少可以分为UTS和MTS。时序性时这种数据与其他数据的不同之处。在时序数据融合领域，最有价值的任务就是降维、相似性度量、分类、聚类分析、模式发掘和可视化。
第二段：介绍目前的研究现状，DTW的困境和原因。主要介绍一元时序数据
大部分的相关工作都集中在在一元时序数据的模式识别上，尤其是基于DTW的一元时序数据的聚类研究。DTW是衡量两个序列相似性的常用方法，但时间复杂度是一个制约因素，并且DTW很难和k-means方法融合到一起去。其中重要的一个原因就是计算每个类的中心序列。文献[10,13]提出了一种DBA方法，在某种程度上DBA可以计算时序的中心序列，但初始化和序列长度选取的不同都会为最后中心序列的形式带来不同的结果。而且每一次循环必须计算每一个序列和中心序列的DTW距离，这也将会消耗更多的时间。另外k-shape和k-ms方法也可以用于UTS，但他们不适用于MTS。
第三段：介绍多元时序数据，PCA的研究现状。
1、介绍PCA。PCA是一个普遍的方法，将MTS转换到一个新的坐标空间中，在新的坐标空间中进行相似度的测量。
2、介绍不同的人对PCA的改进研究
3、其他的降维方法及其对应的测度设计也被用于MTS中
第四段：总结时序聚类中需要研究的问题
1、DTW可以考虑形状以及值的不同，但计算耗费大量的时间，并且中心序列难以设计和计算
2、PCA及其相应的改进方法都忽略了原始值的比较
3、随着MTS长度和维度的增加。目前方法的有效性需要进一步改进。
第五段：阐述本文方法的motivation（4个方面）
(1) Due to the high dimensionality of MTS, the dimensionality reduction is proposed to validly integrate into the clustering process. Moreover, a good clustering results can be obtained in the lower reduced dimensions. （把降维整合到聚类中，低维得到的效果更好）
(2) When the length of MTS is very long and the volume of MTS dataset is very large, we hope to design a fast clustering method for MTS data whose computation speed is better than those methods based on DTW. （速度快）
(3) In the process of clustering analysis, the values and relationship among variables of MTS should be taken into consideration. （聚类中，考虑变量的值和关系）
(4) It is well known that K-Means is a simple and effective clustering method, of which the time complexity is linear to the number of MTS, and it is usually suitable for dynamic clustering and online clustering. The design of the proposed method is expected to reach the effects of K-Means（达到k-means的效果）
第六段：阐述本文的算法思想
1、本文的工作主要受k-means启发
2、算法主要包含两个阶段，构建投影空间和成员重新分配。
3、使用CPCA来构建投影空间，将原始的MTS投影到新的空间中，并进行回构，以计算误差。利用误差最小的原则进行成员重新分配。
4、实验效果好
第七段：章节安排
2. Preliminaries
分两部分，（以后在详细介绍吧，以后的以后了。。。）
1、介绍Common principal component analysis
2、介绍投影和回构，如何计算误差
二、总结
1、论文要解决的问题是序列的聚类问题，需要区别于一个整长序列的分割。算法的输入样本数据为：
，任意一个
是一个任意长度的子序列，每个子序列长度都可以不等，但有相同的维度（m个variables）。需要将N个子序列划分到K类中。
2、作者提出本文算法（Mc2PCA）类似k-means，主要分两步，计算误差和样本reassign
3、文中强调算法兼顾变量之间的relationship以及变量值的相似性，it is very important for MTS data mining in the two aspects, the original values and the relationships of variables. 这一点可以从作者构建的算法中的误差来理解。
3、文中的一个创新是error的计算。传统的k-means算法是用样本点欧拉距离或其他范数形式来表示Loss，作者在构建error时利用PCA算法将高维数据X转换到低维，再将低维数据转换回去，得到Y，X和Y肯定是不同的，作者使用此error作为算法对样本assignment的指导，使得总体的Error最小化。
4、具体算法理解（理解不对的地方欢迎评论指正）：
a.首先将样本初始化到K个类中（文中一共测试13种数据库，每个数据库的K值提前给出）。
b.计算公共空间的投影轴，每一类有一个独立的投影轴（掌握PCA算法协方差矩阵的奇异值分解、特征值以及特征向量，作者将其表达为projection axes只一种比较好的描述）
c.序列重构（可以理解为再将低维空间投影回去，
，但此时投影回去的Y包含了该类所有元素的部分信息）
d.利用X与Y的误差指导样本进行分类，当两次改变都比较stable时停止。
算法伪代码及结果：
5、利用其它算法作为对比，13中数据库，有7个效果比较好，两个效果不太理想，主要原因是原始数据并不是高维的，这也体现算法主要是针对高维数据。高维数据才有各维度变量之间的relationship。
6、文中13中数据库可以找到，有几个在UCI数据中，没有仔细去找
http://archive.ics.uci.edu/ml/datasets.php
三、个人感悟
1、本文章在构建误差上的方法比较有创意，在此之前还未遇见这种方式。
2、需掌握基本的知识PCA和DTW
3、算法思路确实很像k-means方法，后期可以尝试代码实现【目前未完成，具体算法效果不知如何】
4、缺少一种理论性的证明支撑，即此方法构建的error对precision的提高是否有理论依据
5、可以作为英文文献阅读的锻炼，文中很多写作方式也值得借鉴