当前位置: 首页 > news >正文

对时序数据进行分类与聚类

我在最近的工作中遇到了一个问题,问题是我需要根据银行账户在一定时间内的使用信息对该账户在未来的一段时间是否会被销户进行预测。这是一个双元值的分类问题,只有两种可能,即会被销户和不会被销户。针对这个问题一般来说有两种解决策略。

  1. 提取时间序列的统计学特征值,例如最大值,最小值,均值等。然后利目前常用的算法根据提取的特征进行分类,例如Naive Bayes, SVMs 等。
  2. k-NN方法。针对想要预测的时间序列,在训练集中找一个跟它最相似的另外一个序列,然后利用找到的序列的输出值作为原序列的预测值。

下面我会使用这两种算法,运行并对比结果,然后找到最合适的算法。

找到相似数据

针对这个问题,一般会使用欧氏距离寻找相似,但这种方法存在很多问题。如下文给出的示例。如图所示,有三个时间序列:


很明显,序列ts1和ts2的相似度更高,ts3和其他两个相比的差异性更大。为了验证结果,可以通过编程求得这三个序列之间的欧氏距离d(ts1, ts2)和d(ts1,ts3)。下面编写一个计算欧氏距离的函数:

def euclid_dist(t1,t2):return sqrt(sum((t1-t2)**2))

通过计算,结果是d(ts1,ts2)=26.9,d(ts1,ts3)=23.2。很明显,与我们直觉判断相悖。这就是利用欧氏距离标准来判定相似性存在的问题。为了解决这个问题,引入另一个方法——DTW。

动态时间规整(Dynamic Time Warping, DTW)

DTW可以针对两个时间序列找到最优的非线定位(non-linear alignment)。定位之间的欧氏距离不太容易受到时间轴方向上的失真所造成的负面相似性测量的影响。但是我们也必须为这种方法付出代价,即DTW是所有用到的时间序列的数据数量的二次方。

DTW的工作方式如下。我们可以引入两个时间序列Q和C,这两个时间序列都拥有n个数据点,Q=q_1, q_2, \cdots, q_n和C=c_1, c_2, \cdots, c_n。首先我们用这两个时间序列去构造一个n\times n的矩阵,这个矩阵中的第i,j^{th}项代表的是数据点q_i和c_j之间的欧氏距离。我们需要通过这个矩阵找到一个变量,通过该变量可以使所有的欧氏距离和最小。这个变量可以决定两个时间序列之间的最优非线性定位。需要注意的是,对于其中一个时间序列上的数据点,它是有可能映射到另一条时间序列上的多个数据点。

我们可以把这个变量记作W,W = w_1,w_2,\cdots,w_n。其中每一个W代表的都是Q中的第i个点与C中的第j个点之间的距离,即w_k=(q_i-c_j)^2。

因为我们需要找到这个变量的最小值,即W^*=argmin_W(\sqrt{\sum_{k=1}^{K}w_k}),为了找到这个值我们需要通过动态的方法,特别是接下来的这个递归函数。\gamma(i,j)=d(q_i,c_j)+min(\gamma(i-1,j-1),\gamma(i-1,j),\gamma(i,j-1))。该算法可以通过以下的Python代码实现。

def DTWDistance(s1, s2):DTW={}for i in range(len(s1)):DTW[(i, -1)] = float('inf')for i in range(len(s2)):DTW[(-1, i)] = float('inf')DTW[(-1, -1)] = 0for i in range(len(s1)):for j in range(len(s2)):dist= (s1[i]-s2[j])**2DTW[(i, j)] = dist + min(DTW[(i-1, j)],DTW[(i, j-1)], DTW[(i-1, j-1)])return sqrt(DTW[len(s1)-1, len(s2)-1])

通过DTW计算,DTWDistance(ts1,ts2)=17.9,DTWDDistance(ts1,ts3)=21.5。正如我们所看到的,该结果与只利用欧氏距离算法得到的结果截然不同。现在,这个结果就符合我们的主观腿断了,即ts2相比于ts3与ts1更为相似。

提高DTW算法计算速度

DTW的复杂度O(nm)是与两个时间序列的数据数量正相关的。如果两个时间序列都含有大量数据,那么这种方法的计算时间会非常长。因此我们需要通过一些方法去提高计算速度。第一种方法是强制执行局部性约束。这种方法假设当i和j相距太远,则q_i和c_j不需要匹配。这个阈值则由一个给定的窗口大小w决定。这种方法可以提高窗口内循环的速度。详细代码如下:

def DTWDistance(s1, s2, w):DTW={}w = max(w, abs(len(s1)-len(s2)))for i in range(-1,len(s1)): for j in range(-1,len(s2)):DTW[(i, j)] = float('inf')DTW[(-1, -1)] = 0for i in range(len(s1)):for j in range(max(0, i-w), min(len(s2), i+w)):dist= (s1[i]-s2[j])**2DTW[(i, j)] = dist + min(DTW[(i-1, j)],DTW[(i, j-1)], DTW[(i-1, j-1)])return sqrt(DTW[len(s1)-1, len(s2)-1])

另一种方法是使用LB Keogh下界方法DTW的边界。
LBKeogh(Q,C)=\sum_{i=1}^{n}(c_i-U_i)^2I(c_i>U_i)+(c_i-L_i)^2I(c_i < U_i)
U_i和L_i是时间序列Q的上下边界,U_i=max(q_{i-r}:q_{i+r}),L_i=min(q_{i-r}:q_{i+r})。其中r是可达到的边界,I(\cdot)是指示函数。该方法可以通过以下代码实现。

def LB_Keogh(s1,s2,r):LB_sum=0for ind,i in enumerate(s1):lower_bound=min(s2[(ind-r if ind-r>=0 else 0):(ind+r)])upper_bound=max(s2[(ind-r if ind-r>=0 else 0):(ind+r)])if i>upper_bound:LB_sum=LB_sum+(i-upper_bound)**2elif i<lower_bound:LB_sum=LB_sum+(i-lower_bound)**2return sqrt(LB_sum)

LB Keogh小界方法是线性的,而DTW则是复杂的二次方形式,这使得它在处理大量时间序列的时候非常有利。

分类与聚类

现在我们有了可靠的方法去判断两个时间序列是否相似,截下来便可以使用k-NN算法进行分类。根据经验,最优解一般出现在k=1的时候。下面就利用DTW欧氏距离的1-NN算法。在该算法中,train是时间序列示例的训练集,其中时间序列所属的类被附加到时间序列的末尾。test是相应的测试集,它所属于的类别就是我们想要预测的结果。在该算法中,对于测试集中的每一个时间序列,每一遍搜索必须遍历训练集中的所有点,从而可以找到最多的相似点。考虑到DTW算法是二次方的,计算过程会耗费非常长时间。我们可以通过LB Keogh下界方法来提高分类算法的计算速度。计算机运行LB Keogh的速度会比运行DTW的速度快很多。另外,当LBKeogh(Q,C)\leq DTW(Q,C)时,我们可以消除那些比当前最相似的时间序列不可能更相似的时间序列。这样,我们就可以消除很多不必要的DTW计算过程。

from sklearn.metrics import classification_reportdef knn(train,test,w):preds=[]for ind,i in enumerate(test):min_dist=float('inf')closest_seq=[]#print indfor j in train:if LB_Keogh(i[:-1],j[:-1],5)<min_dist:dist=DTWDistance(i[:-1],j[:-1],w)if dist<min_dist:min_dist=distclosest_seq=jpreds.append(closest_seq[-1])return classification_report(test[:,-1],preds)

下面测试一批数据。设置窗口大小为4。另外,尽管这里使用了LB Keogh下界方法和局部性约束,计算过程仍然需要几分钟。

train = np.genfromtxt('datasets/train.csv', delimiter='\t')
test = np.genfromtxt('datasets/test.csv', delimiter='\t')
print knn(train,test,4)

运行结果如下

这种方法也可用于k-mean聚类。在这种算法中,簇的数量设置为apriori,相似的时间序列会被放在一起。

import randomdef k_means_clust(data,num_clust,num_iter,w=5):centroids=random.sample(data,num_clust)counter=0for n in range(num_iter):counter+=1print counterassignments={}#assign data points to clustersfor ind,i in enumerate(data):min_dist=float('inf')closest_clust=Nonefor c_ind,j in enumerate(centroids):if LB_Keogh(i,j,5)<min_dist:cur_dist=DTWDistance(i,j,w)if cur_dist<min_dist:min_dist=cur_distclosest_clust=c_indif closest_clust in assignments:assignments[closest_clust].append(ind)else:assignments[closest_clust]=[]#recalculate centroids of clustersfor key in assignments:clust_sum=0for k in assignments[key]:clust_sum=clust_sum+data[k]centroids[key]=[m/len(assignments[key]) for m in clust_sum]return centroids

再用这种算法测试一下数据:

train = np.genfromtxt('datasets/train.csv', delimiter='\t')
test = np.genfromtxt('datasets/test.csv', delimiter='\t')
data=np.vstack((train[:,:-1],test[:,:-1]))import matplotlib.pylab as pltcentroids=k_means_clust(data,4,10,4)
for i in centroids:plt.plot(i)plt.show()

结果如图

代码

所有用到的代码都可以在my gitHub repo找到。

转载:https://www.cnblogs.com/think90/articles/11975242.html

相关文章:

对时序数据进行分类与聚类

我在最近的工作中遇到了一个问题&#xff0c;问题是我需要根据银行账户在一定时间内的使用信息对该账户在未来的一段时间是否会被销户进行预测。这是一个双元值的分类问题&#xff0c;只有两种可能&#xff0c;即会被销户和不会被销户。针对这个问题一般来说有两种解决策略。 …...

Win10如何找回图片查看器

近期有小伙伴反映在将Win10升级之后发现电脑自带的图片查看器没有了&#xff0c;这是怎么回事&#xff0c;该怎么找回呢&#xff0c;下面小编就给大家详细介绍一下Win10找回图片查看器的方法&#xff0c;有需要的小伙伴快来和小编一起阅读看看吧。 win10找回windows照片查看器…...

【脑机接口】基于运动想象的康复指导在脑卒中偏瘫患者中的应用

【摘要】 目的 探讨运动想象康复指导对脑卒中偏瘫患者的康复效果及意义。 方法 将 60例脑卒中偏瘫患者随机分为观察组(n31)和对照组(n29)&#xff0c;对照组的康复训练指导采用讲解示范法&#xff0c;观察组采用运动想象法 。比较两组 患者 的运 动功能 、日常生活 活动能力及 …...

vue-cli中vuex下$store”未在实例上定义

这里写目录标题 一、版本的问题二、vuex中的代码 一、版本的问题 vuex版本不对&#xff0c;获取不到store&#xff0c;vue默认vue3版本&#xff0c;vuex默认vuex4版本&#xff0c;vuex4只能在vue3中使用&#xff0c;在vue2中能使用vuex3,那么不能默认下载最新的版本 npm instal…...

AutoSAR配置与实践(实践篇)12.1 BSW WatchDog功能的配置和实现

AutoSAR配置与实践(实践篇)12.1 BSW WatchDog功能的配置和实现 BSW WatchDog功能的配置和实现一、Wdg监控需求二、WdgM状态管理原理2.1 WdgM状态管理中的配置项和层次关系2.2 SE 本地状态(Local Status)管理2.3 全局状态(Global Status)管理三、Alive/ Deadline/ Program Flo…...

【UI自动化测试】Jenkins配置

前一段时间帮助团队搭建了UI自动化环境&#xff0c;这里将Jenkins环境的一些配置分享给大家。 背景&#xff1a; 团队下半年的目标之一是实现自动化测试&#xff0c;这里要吐槽一下&#xff0c;之前开发的测试平台了&#xff0c;最初的目的是用来做接口自动化测试和性能测试&…...

C#使用DataTable的Select方法来选择特定的字段

在C#中&#xff0c;可以使用DataTable的Select方法来选择特定的字段。要选择特定的字段&#xff0c;可以使用Select方法的参数来指定要返回的列的名称&#xff0c;然后将结果存储在一个新的DataTable中。以下是一个示例&#xff1a; using System; using System.Data; class …...

总结梳理HTTP状态码

前端开发中和后端联调时总会遇到一些状态码的问题&#xff0c;本文用于介绍一些常见的状态码&#xff0c;以及遇到这些状态码应该如何进行排查。 400 Bad Request - 请求无效。 表示客户端发送的请求存在语法错误&#xff0c;服务器无法理解或处理该请求的语法或参数。这通常…...

MySQL 8.0(winx64)安装笔记

一、背景 从MySQL 5.6到5.7&#xff0c;再到8.0&#xff0c;版本的跳跃不可谓不大。安装、配置的差别也不可谓不大&#xff0c;特此备忘。 二、过程 &#xff08;1&#xff09;获取MySQL 8.0社区版&#xff08;MySQL Community Server&#xff09;   从 官网 字样 “MySQL …...

vue封装wangEditor

components下面创建WangEditor.vue <template><div><toolbarstyle"border-bottom: 1px solid #ccc":editor"editor":defaultConfig"toolbarConfig":mode"mode"/><editorstyle"height: 500px; overflow-y: …...

【Spring Boot 源码学习】深入 FilteringSpringBootCondition

走近 AutoConfigurationImportFilter 引言往期内容主要内容1. match 方法2. ClassNameFilter 枚举类3. filter 方法 总结 引言 前两篇博文笔者带大家从源码深入了解了 Spring Boot 的自动装配流程&#xff0c;其中自动配置过滤的实现由于篇幅限制&#xff0c;还未深入分析。 …...

docker 笔记6:高级篇 DockerFile解析

目录 1.是什么&#xff1f; 2.构建三步骤 3.DockerFile构建过程解析 3.1 Dockerfile内容基础知识 3.2Docker执行Dockerfile的大致流程 总结 4.DockerFile常用保留字指令 5.案例&#xff1a;自定义镜像 5.1 要求&#xff1a; Centos7镜像具备vimifconfigjdk8 5.2编写 5…...

微信小程序navigateTo进入页面后返回原来的页面需要携带数据回来

需求 如图&#xff1a;点击评论后会通过wx.navigateTo进入到评论页面&#xff0c;评论完返回count给原页面&#xff0c;重新赋值实现数量动态变化&#xff0c;不然要刷新这个页面才会更新最新的评论数量。 实现方式&#xff1a; 在评论页面通过wx.setStorageSync(‘data’…...

Python照片压缩教程详解

介绍 在日常的编程工作中&#xff0c;我们经常需要处理图像&#xff0c;例如上传、下载、显示、编辑等。有时候&#xff0c;我们需要对图像进行压缩&#xff0c;以减少占用的空间和带宽&#xff0c;提高加载速度和用户体验。那么&#xff0c;如何用Python来实现图像压缩呢&…...

软路由的负载均衡设置:优化网络性能和带宽利用率

在现代网络环境中&#xff0c;提升网络性能和最大化带宽利用率至关重要。通过合理配置软路由IP的负载均衡设置&#xff0c;可以有效地实现这一目标&#xff0c;并提高整体稳定性与效果。本文将详细介绍如何进行软路由IP的负载均衡设置&#xff0c;从而优化网络表现、增加带宽利…...

CH06_第一组重构(上)

提取函数&#xff08;Extract Function |106&#xff09; 曾用名&#xff1a;提炼函数&#xff08;Extract Function&#xff09; 反向重构&#xff1a;内联函数&#xff08;115&#xff09; 示例代码 function printOwing(invoice) {printBanner();let outstanding calcul…...

RHCSA-VMware Workstation Pro-Linux基础配置命令

1.代码命令 1.查看本机IP地址&#xff1a; ip addr 或者 ip a [foxbogon ~]$ ip addre [foxbogon ~]$ ip a 1&#xff1a;<Loopback,U,LOWER-UP> 为环回2网卡 2: ens160: <BROADCAST,MULTICAST,UP,LOWER_UP>为虚拟机自身网卡 2.测试网络联通性&#xff1a; [f…...

YOLO-NAS详细教程-姿势估计实现

姿势估计是一项计算机视觉任务,涉及估计图像或视频中物体或人的位置和方向。它通常涉及识别特定的关键点或身体部位(例如关节),并确定它们的相对位置和方向。姿势估计有许多应用,包括机器人、增强现实、人机交互和运动分析。 自上而下和自下而上是姿态估计中两种常用的方法…...

【扩散模型 李宏毅B站教学以及基础代码运用】

李宏毅教学视频&#xff1a; Link1 B站DDPM公式推导以及代码实现&#xff1a; Link2 这个视频里面有论文里面的公式推导&#xff0c;并且1小时10分开始讲解实例代码。 文章目录 扩散模型概念&#xff1a;Diffusion Model工作原理&#xff1a;影像生成模型本质上的共同目标B站…...

SpringBoot隐藏文件

1.设置 2.输入file Types 3.点击忽略文件或者文件夹 4.成功...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...