京东研究院实战分享：时间序列用户生命周期的聚类方法

从百科的说明可以看出，时间序列不仅仅只是一个序列数据，而是一个受系统影响很大的序列数据，时间序列的数据本身存在于生活中的各个领域里，人们对时间序列的分析从很早以前就开始了，发展至今，在大数据环境下，采用数据挖掘的方法来表示数据内部规律也成为了分析时间序列的一种重要方向和趋势。

时间序列数据特征

然而时间序列有着两大主要特征，使得这种分析变得十分困难：

1. 非平稳性（nonstationarity，也译作不平稳性，非稳定性）：即时间序列变量无法呈现出一个长期趋势并最终趋于一个常数或是一个线性函数，也就是说，时间序列在每个时间周期里可能出现两种变化，一种是受整个系统变化的影响，另一种是随机的变化。
2. 波动幅度随时间变化（Time—varying Volatility）：即一个时间序列变量的方差随时间的变化而变化。

这种不确定性和各自间的相关性，使得有效分析时间序列变量十分困难，举例来说，每个人在不同的时间点产生的行为都是随机行为，但即将产生的行为或多或少又会受个人过去的行为习惯所影响，所以，假设当我们有这个人过去的全部行为数据时，首先希望通过某种方式刻画这个人过去的行为，并最终找到和这个人有类似行为习惯的人群。传统的划分方法很多，但都是通过某个行为来进行分类划分，而将所有相关行为放在时间序列上来进行整体观察，就用户生命周期而言，国内外都有很多人在研究这个方向，于是我们思考是否能找到一种方法在实际的项目过程得到应用，通过大量的数据来实践时间序列的聚类方法优劣性。

时间序列应用范围

时间序列在很多领域都有研究，但在电子商务领域的研究，近几年才逐渐兴起。我们项目中希望能够对有相似行为的人群做划分，但在实际中发现，由于人的很多行为是相互关联的，并且在时间的维度中还会发生变化，可能受过去的影响，也可能不受影响，所以，这一秒和下一秒都是不可确定的，导致从传统方法的聚类存在局限性。所以我们从长期趋势研究开始，发现消费的某些行为却可能是固定的，比如定期的购买，季节的变换，促销活动的影响等，这些都是和时间周期有关系的，但又不只是简单的消费数据表示，于是我们想到使用基于时间序列的聚类的方法来进行尝试，得到了一些新的效果。因为随着时间的变换，人是会不断改变的，每种行为可能和时间进行关联后会产生不同的结果，我们最后不仅能得到这个用户局部的行为规律，也可以看到TA在整体时间周期里的行为的规律，通过观察整体和局部，便能更好的刻画用户的生命周期。

时间序列聚类方法

关于时间序列聚类的方法，根据一些理论文献，简单总结如下：

1、传统静态数据的聚类方法有：基于划分的聚类、基于层次的聚类、基于密度的聚类、基于格网的聚类、基于模型的聚类；

2、时间序列聚类方法：大概有三种，一是基于形态特征，即形状变化，包括全局特征和局部特征；二是基于结构特征，即全局构造或内在变化机制，包括基本统计特征、时域特征和频域特征；三是基于模型特征，参数的的变化影响系统的变化，同时存在随机变化。

然而无论是分类、聚类还是关联规则挖掘，都需要解决时间序列的相似度问题，相似性搜索是时间序列数据挖掘的研究基础。由于时间序列存在各种复杂变形（如平移、伸缩、间断等） ，且变形时间和变形程度都无法预料，传统的欧氏距离已经无法胜任。经过一番调研后，目前，动态时间弯曲(DTW) 相似距离的稳定性已在国内外得到验证，于是我们打算采用DTW来尝试聚类分类。

欧式距离

我们定义两个时间序列长度为N的序列T和D的欧式距离如下：

欧式距离本身也是计算空间距离的，我们刚开始选用它来计算距离，但发现单独使用准确性不高。现在，我们来做一个简单的实验：

图1 三条序列曲线

首先，用Python来简单的画三条曲线，如图1所示。从图中可以明显的看出，ss1和ss2曲线是很相似（这里就是sin函数的不同区间变换），ss3和他们两个都有明显的不同。我们使用公式来计算ss1和ss2，ss1和ss3的距离，结果如下：

ss1 –> ss2 的欧式距离：26.959216038

ss1 –> ss3 的欧式距离：23.1892491903

从上面可以直观的发现ss1和ss2的距离值反而更大。这里只是直观的说明它本身对序列计算的问题，其实当发现时间序列的频率变化，时间扭曲的时候，单一的欧式距离公式的偏差是比较大的。

动态时间规整（Dynamic Time Warping）

动态时间规整现在应用的比较多的是在语音识别上，因为DTW本身是为了找到最优非线性时间序列之间的距离值。这个算法是基于动态规划（DP）的思想，解决了发音长短不一的模板匹配问题，简单来说，就是通过构建一个邻接矩阵，寻找最短路径和的算法。现在我们继续试验，定义两个时间序列长度为n的序列T和D：

我们需要先构建一个n x n的矩阵，其中i,j是ti和dj之间的欧式距离，我们想通过这个矩阵的最小累积距离的路径。然后确定对比两个时间序列之间的距离。我们叫这个路径为W：

其中每个元素代表了T和D点之间的距离，例如：

我们想找到距离最小的路径：

最佳路径是使用的动态规划递归函数，具体公式如下：

最后得到结果：

ss1 –> ss2 的DTW距离：17.9297184686

ss1 –> ss2 的DTW距离：21.5494948244

这个例子比较简单，仅供参考。而后我们团队经过更多其它真实的实验后，最后还是选用了DTW作为时间序列的计算的方法，但在实际运行过程中，发现DTW的运算速度确实比较慢，目前正在实验提升它效率的方法。经过一段时间的分析后，我们准备开始进行聚类。我们使用k近邻分类算法。根据经验，最理想的结果是当然是k = 1时的距离值，在该算法中，训练集和测试集分别采用的时间序列的周期集合数据集，在算法中，对测试集进行预测的每个时间序列，搜索是必须通过训练中的所有的点集，发现最相似的一点。

时间序列分析的未来展望

时间序列分析未来研究的一个重要源动力可能会是来自于“互网络+”电子商务等商业领域巨大数据量的数据。在全球竞争日益激烈的商业环境中，这些数据的可利用价值也会越来越大。然而，这些庞大的数据，本身的离散型和连续型的多元变量相混杂，传统和现有的数据处理方法远远不能对其进行有效的加工、清洗和处理。对这些数据进行综合分析的迫切性肯定会影响未来时间序列分析的研究方向。

笔者大胆地猜测，在未来，时间序列分析的研究可能会有以下几个方向发展：

1. 研究不同变量间动态关系生成的模型和算法将会大量出现，同时研究同一个时间周期内变量间自有的动态变化的方法也会逐渐出现，并且效果会越来越好；
2. 独立随机性事件和系统性事件对整体周期变化的影响的分析也会变得日益重要；
3. 数据挖掘技术的利用来分析时间序列也将日益引起各个领域研究者们的重视，对大量数据的使用，以及如何更有效地挖掘出有效的时间相关特征数据也是未来发展的趋势；
4. 基于神经网络的机器学习算法也将会应用到大量时间序列的分析中，未来会朝着人工智能这个方向快速地前进，例如，现在比较火热的深度学习算法，未来是不是也能应用到对时间序列的分析上来呢。

当然，真实的未来还需要时间本身来检验。

小结

本文只是简单介绍了在实际项目中使用时间序列聚类算法时产生的疑惑和解决思路，期间很多方法可能还是尝试和实验阶段，在细节上还有许多可改进的空间，目前DTW算法比较可靠，因为是二次规整，所以缺点就是运算特别慢，目前我们还在通过其他一些对他的优化方法提升速度，后续会继续对电子商务用户生命周期时间序列的挖掘方法进行研究和提升，如果大家有更多更好的方法的话，欢迎交流讨论。（责编/周建丁）

作者简介：黄靖锋，京东算法工程师。主要负责京东用户生命周期系统架构设计与实践应用，专注于高性能大数据计算与机器学习算法的应用。

黄靖锋

【预告】首届中国人工智能大会（CCAI 2015）将于7月26-27日在北京友谊宾馆召开。机器学习与模式识别、大数据的机遇与挑战、人工智能与认知科学、智能机器人四个主题专家云集。人工智能产品库将同步上线，预约咨询：QQ：1192936057。欢迎关注。

本文为ImapBox原创文章，未经允许不得转载，如需转载请联系market#csdn.net(#换成@)