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

摘要:本文介绍了京东成都研究院在实际项目中使用时间序列聚类算法时产生的疑惑和解决思路。京东选用了DTW作为时间序列的计算的方法,但在实际运行过程中,发现DTW的运算速度确实比较慢,目前正在实验提升它效率的方法。

时间序列和时间序列分析分别是什么?引用百度百科的解释:时间序列是指将某种现象某一个统计指标在不同时间上的各个数值,按时间先后顺序排列而形成的序列。而时间序列分析(Time series analysis)是一种动态数据处理的统计方法。该方法基于随机过程理论和数理统计学方法,研究随机数据序列所遵从的统计规律,以用于解决实际问题。

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

时间序列数据特征

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

  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。欢迎关注。

原文发布于微信公众号 - 人工智能头条(AI_Thinker)

原文发表时间:2015-06-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏企鹅号快讯

Yann LeCun:深度学习已死,可微分编程万岁!

昨天,Yann LeCun在Facebook个人主页上写到:深度学习已死,可微分编程万岁!这让不少人大吃一惊,莫非我们一直坚信的深度学习技术是假的“炒作概念”?...

2509
来自专栏新智元

DeepMind AI 关系推理超越人类:深度神经网络模块即插即用

【新智元导读】DeepMind 今天发表官博介绍了他们的两篇最新论文,称其都在理解“关系推理”这一挑战方面展示出了令人可喜的结果。一个是视觉互动网络 VIN,能...

59514
来自专栏AI科技评论

预热 | 英特尔通过预测变量实现策略性强化学习,夺冠 Doom 游戏竞赛(ICLR 2017)

AI科技评论按:ICLR 2017 将于4月24-26日在法国土伦举行,届时AI科技评论的编辑们也将前往法国带来一线报道。在这个深度学习会议举办之前,AI科技评...

3679
来自专栏机器之心

学界 | 学习一帧,为整段黑白视频上色:谷歌提出自监督视觉追踪模型

在谷歌最近提交的论文《Tracking Emerges by Colorizing Videos》中,研究人员引入了一种为灰度视频着色的卷积神经网络,但它只需要...

1243
来自专栏机器之心

CoNLL 2018 | 最佳论文揭晓:词嵌入获得的信息远比我们想象中的要多得多

昨日,CoNLL 公布了最佳论文,由来自西班牙巴斯克大学 IXA NLP 组的 Mikel Artetxe 等人获得。该论文展示了词嵌入模型能够捕获不同层面的信...

891
来自专栏人工智能头条

开发者成功使用机器学习的十大诀窍

1354
来自专栏大数据文摘

视频回放 | 80分钟公开课:机器学习之数学基础,从梯度分析到回归模型

1502
来自专栏机器之心

学界 | 批训练、注意力模型及其声纹分割应用,谷歌三篇论文揭示其声纹识别技术原理

5196
来自专栏ATYUN订阅号

每个机器学习项目必须经过的五个阶段

机器学习和预测分析在我们今天的生活中非常普遍。它几乎可以影响我们所做的一切,包括零售和批发定价,消费者习惯和行为,市场营销,娱乐,医药,物流,游戏,AI语音识别...

3955
来自专栏华章科技

揭开深度学习黑箱:希伯来大学计算机科学教授提出「信息瓶颈」

一个称为「信息瓶颈」的新想法有助于解释当今人工智能算法的黑箱问题——以及人类大脑的工作原理。

933

扫码关注云+社区

领取腾讯云代金券