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

这篇具有很好参考价值的文章主要介绍了对时序数据进行分类与聚类。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

  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)] = 0

    for i in range(len(s1)):
        for j in range(len(s2)):
            dist= (s1[i]-s2[j])**2
            DTW[(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)] = 0

    for i in range(len(s1)):
        for j in range(max(0, i-w), min(len(s2), i+w)):
            dist= (s1[i]-s2[j])**2
            DTW[(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=0
    for 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)**2
        elif i<lower_bound:
            LB_sum=LB_sum+(i-lower_bound)**2

    return 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_report

def knn(train,test,w):
    preds=[]
    for ind,i in enumerate(test):
        min_dist=float('inf')
        closest_seq=[]
        #print ind
        for 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=dist
                    closest_seq=j
        preds.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 random

def k_means_clust(data,num_clust,num_iter,w=5):
    centroids=random.sample(data,num_clust)
    counter=0
    for n in range(num_iter):
        counter+=1
        print counter
        assignments={}
        #assign data points to clusters
        for ind,i in enumerate(data):
            min_dist=float('inf')
            closest_clust=None
            for 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_dist
                        closest_clust=c_ind
            if closest_clust in assignments:
                assignments[closest_clust].append(ind)
            else:
                assignments[closest_clust]=[]

        #recalculate centroids of clusters
        for key in assignments:
            clust_sum=0
            for 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 plt

centroids=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文章来源地址https://www.toymoban.com/news/detail-699250.html

到了这里,关于对时序数据进行分类与聚类的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据挖掘18大算法实现以及其他相关经典DM算法:决策分类,聚类,链接挖掘,关联挖掘,模式挖掘、图算法,搜索算法等

    【机器学习入门与实践】入门必看系列,含数据挖掘项目实战:模型融合、特征优化、特征降维、探索性分析等,实战带你掌握机器学习数据挖掘 专栏详细介绍:【机器学习入门与实践】合集入门必看系列,含数据挖掘项目实战:数据融合、特征优化、特征降维、探索性分析

    2024年02月09日
    浏览(44)
  • 基于决策树、随机森林和层次聚类对帕尔默企鹅数据分析

    作者:i阿极 作者简介:数据分析领域优质创作者、多项比赛获奖者:博主个人首页 😊😊😊如果觉得文章不错或能帮助到你学习,可以点赞👍收藏📁评论📒+关注哦!👍👍👍 📜📜📜如果有小伙伴需要数据集和学习交流,文章下方有交流学习区!一起学习进步!💪 大家

    2024年02月03日
    浏览(40)
  • 【数据挖掘实战】——舆情分析:对微博文本进行情绪分类

    🤵‍♂️ 个人主页:@Lingxw_w的个人主页 ✍🏻作者简介:计算机科学与技术研究生在读 🐋 希望大家多多支持,我们一起进步!😄 如果文章对你有帮助的话, 欢迎评论 💬点赞👍🏻 收藏 📂加关注+   目录 一、背景介绍 二、比赛任务

    2024年02月08日
    浏览(41)
  • 【数据挖掘】基于粒子群算法优化支持向量机PSO-SVM对葡萄酒数据集进行分类

    PSO是粒子群优化算法(Particle Swarm Optimization)的英文缩写,是一种基于种群的随机优化技术,由Eberhart和Kennedy于1995年提出。粒子群算法是模仿昆虫、兽群、鸟群和鱼群等的群集行为,这些群体按照一种合作的方法寻找食物,群体中的每个成员通过学习它自身的经验和其他成员

    2024年02月02日
    浏览(55)
  • 利用python对b站某GPT-4解说视频的近万条弹幕进行爬取、数据挖掘、数据分析、弹幕数量预测及情绪分类

             目录 一、利用Python爬取弹幕  二、利用几行代码直接生成词云 三、将弹幕属性和内容放入mysql当中  四、分析弹幕在视频各节点的数量 1、分析视频各个片段出现的弹幕数量 2、分析视频各大章节出现的弹幕数量 3.分析视频各小节出现的弹幕数量 五、分析弹幕数

    2024年02月11日
    浏览(39)
  • 回归与聚类——性能评估(二)

    回归当中的数据大小不一致,是否会导致结果影响较大。所以需要做标准化处理。 数据分割与标准化处理 回归预测 线性回归的算法效果评估 均方误差(Mean Squared Error)MSE)评价机制: 注:y^i为预测值,y-为真实值 sklearn.metrics.mean_squared_error(y_true, y_pred) 均方误差回归损失 y_true:

    2024年04月27日
    浏览(43)
  • 机器学习——回归与聚类算法

    不仅是自变量是一次方的是线性模型, 参数是一次方 的也是线性模型,比如: 总结: 线性关系的一定是线性模型,线性模型的不一定是线性关系。  求解模型中的w,使得损失最小。 正规方程 理解:X为特征值矩阵,Y为目标值矩阵,直接求到最好的结果(矩阵求导得极值再

    2023年04月25日
    浏览(40)
  • 数据挖掘题目:根据规则模板和信息表找出R中的所有强关联规则,基于信息增益、利用判定树进行归纳分类,计算信息熵的代码

    S∈R,P(S,x )∧ Q(S,y )== Gpa(S,w ) [ s, c ] 其中,P,Q ∈{ Major, Status ,Age }. Major Status Age Gpa Count Arts Graduate Old Good 50 Arts Graduate Old Excellent 150 Arts Undergraduate Young Good 150 Appl_ science Undergraduate Young Excellent Science Undergraduate Young Good 100 解答: 样本总数为500,最小支持数为5

    2024年02月06日
    浏览(48)
  • 数据挖掘(6)聚类分析

    无指导的,数据集中类别未知 类的特征: 类不是事先给定的,而是根据数据的 相似性、距离 划分的 聚类的数目和结构都没有事先假定。 挖掘有价值的客户: 找到客户的黄金客户 ATM的安装位置 原则: 组内数据有较高相似度、不同组数据不相似 相似性的度量(统计学角度): Q型

    2024年02月07日
    浏览(51)
  • 天猫订单之数据分析与挖掘——聚类分析

    Windows: Windows10 Python: Python3.9 本次案例项目主要是采用Pandas和Numpy对天猫订单数据集进行处理、挖掘、分类和聚类分析,最终利用数据可视化工具Matplotlib展示各地区在天猫平台的消费情况。 1.1 聚类分组 以属性收货地址作为聚类分组的基点,统计每个省份/市/自治区的订单总

    2024年02月06日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包