精华内容
下载资源
问答
  • 提出一种进行时间序列模式挖掘的算法,用于对大型数据库的海量数据分析,从中挖掘出超过用户给定支持度和置信度的时间序列,从而为用户的决策支持和趋势预测提供依据。算法分为在数据中对于频繁项集的发现和频繁序列...
  • 时间序列数据挖掘

    千次阅读 2018-11-14 12:40:44
    时间序列是一种重要的高维数据类型,它是由客观对象的某个物理量在不同时间点的采样值按照...利用时间序列数据挖掘,可以获得数据中蕴含的与时间相关的有用信息,实现知识的提取[1]。时间序列数据本身所具备的高维...

    时间序列是一种重要的高维数据类型,它是由客观对象的某个物理量在不同时间点的采样值按照时间先后次序排列而组成的序列,在经济管理以及工程领域具有广泛应用。例如证券市场中股票的交易价格与交易量、外汇市场上的汇率、期货和黄金的交易价格以及各种类型的指数等,这些数据都形成一个持续不断的时间序列。利用时间序列数据挖掘,可以获得数据中蕴含的与时间相关的有用信息,实现知识的提取[1]。时间序列数据本身所具备的高维性、复杂性、动态性、高噪声特性以及容易达到大规模的特性,因此时间序列挖掘是数据挖掘研究中最具有挑战性的十大研究方向之一[2]。目前重点的研究内容包括时间序列的模式表示、时间序列的相似性度量和查询、时间序列的聚类、时间序列的异常检测、时间序列的分类、时间序列的预测等。

     由于时间序列数据本身所具备的高维性、复杂性、动态性、高噪声特性以及容易达到大规模的特性,直接在时间序列上进行数据挖掘不但在储存和计算上要花费高昂代价而且可能会影响算法的准确性和可靠性。时间序列的模式表示是一种对时间序列进行抽象和概括的特征表示方法,是在更高层次上对时间序列的重新描述[3, 4]。时间序列的模式表示具有压缩数据、保持时间序列基本形态的功能,并且具有一定的除噪能力。常用的时间序列模式表示方法主要包含:频域表示法、分段线性表示法、符号表示法以及主成分分析表示法等。频域表示的基本思想是将时间序列从时域通过傅里叶变换或小波变换映射到频域,用很少的低频系数来代表原来的时间序列数据,这种方法虽然数据浓缩的效率很高,但是对噪声敏感,而且不直观。分段线性表示法的基本思想是用K个直线段来近似代替原来的时间序列,这种方法能够实现数据压缩的目的,而且允许在时间轴上进行缩放,但实现过程较复杂,且要求事先给出直线段数K。K值的选择是一个关键因素,太小则丢失有用信息,太大又会产生过多的冗余信息。时间序列的符号化表示就是通过一些离散化方法将时间序列的连续实数值或者一段时间内的时间序列波形映射到有限的符号表上,将时间序列转换为有限符号的有序集合。符号化表示的优点在于可以利用许多字符串研究领域的成果,缺点在于如何选择合适的离散化算法,解释符号的意义,以及定义符号之间的相似性度量。主成分分析是一种常见的降维方法。在时间序列的模式表示中,通过对整个时间序列数据库的整体表示实现对整个时间序列数据库的特征提取和压缩。其优点在于计算精度高且对噪声数据的鲁棒性强,但由于在奇异值分解过程中涉及到特征值计算,计算开销较大。

    时间序列的相似性度量是时间序列数据挖掘的基础[5, 6]。时间序列由于其特定的形状特征, 使得目前常用的一些相似性度量和聚类方法失去了原有的优越性, 而几乎所有的时间序列挖掘算法都涉及到计算序列之间的相似性问题。目前,时间序列的相似性度量主要采用Lp范数(例如欧几里德距离)、动态时间弯曲距离、最长公共子序列、编辑距离、串匹配等。前两种相似性度量方法应用较为广泛。但是欧几里德距离不支持时间序列的线性漂移和时间弯曲,动态时间弯曲距离的计算量很大,不适合直接应用于海量时间序列的挖掘,从而限制了其在时间序列数据挖掘上的广泛应用。

    虽然各种聚类方法已经在数据挖掘领域中得到了较为深入的研究,但这些方法大多是针对关系数据库中的静态数据对象而提出的。然而在现实世界中越来越多的应用涉及到流数据和时间序列数据等随时间变化的复杂动态数据对象的聚类分析。由于时间序列数据与静态数据有着极大的不同,故对其进行聚类分析有着很大的复杂性。近年来,涌现出许多时间序列聚类方法[7],这些时间序列数据聚类方法大体上可以分为三种,即基于原始数据的聚类、基于特征的聚类和基于模型的聚类。其中后两种方法的核心思想是利用时间序列的模式表示方法把时间序列数据转化为静态的特征数据或者是模型参数,然后再直接应用静态数据的聚类方法来完成聚类任务。

    在对时间序列进行分析时, 经常希望能够发现这些时间序列在不同时间段的形态有何关联关系。这种关联关系一般表现为时间序列中频繁出现的变化模式和极少出现的变化模式。这种极少出现的变化模式称之为异常模式。在某些领域, 异常模式的发现对人们来说往往更有价值。例如, 医院可以从病人的心电图序列中发现异常模式从而进行诊断和治疗。按照异常的表现形式不同, 线性时间和空间上时间序列的异常主要可以分为点异常和模式异常两种, 它们都是用于发现一条时间序列上的异常情况的。模式异常是指在一条时间序列上与其他模式之间具有显著差异的模式。事实上, 点异常也可以认为是长度为1 的模式异常。目前已经提出多种时间序列异常检测方法,例如基于人工免疫系统的时间序列异常检测[9]、基于支持向量聚类的时间序列异常检测[9]以及后缀树和马尔可夫模型的时间序列异常检测[10]。

    时间序列分类是时间序列数据分析中的重要任务之一. 不同于时间序列分析中常用的算法与问题,时间序列分类是要把整个时间序列当作输入,其目的是要赋予这个序列某个离散标记。它比一般分类问题困难,主要在于要分类的时间序列数据不等长,这使得一般的分类算法不能直接应用。即使是等长的时间序列,由于不同序列在相同位置的数值一般不可直接比较,一般的分类算法依然还是不适合直接应用。为了解决这些难点,通常有两种方法:第一,定义合适的距离度量(最常用的距离度量是DTW距离),使得在此度量意义下相近的序列有相同的分类标签,这类方法属于领域无关的方法;第二,首先对时间序列建模(利用序列中前后数据的依赖关系建立模型),再用模型参数组成等长向量来表示每条序列,最后用一般的分类算法进行训练和分类,这类方法属于领域相关的方法。文[11]分析了两类方法,并且分别在不同的合成数据集和实际数据集上比较了领域无关和领域相关的两类方法。结果发现在训练数据较少时,使用领域相关的算法比较合适;另一方面,领域无关的算法受噪声的影响相对较少。

            预测是对尚未发生或目前还不明确的事物进行预先的估计和推测,是在现时对事物将要发生的结果进行探讨和研究,简单地说就是指从已知事件测定未知事件。进行预测的总原则是:认识事物的发展变化规律,利用规律的必然性进行科学预测。时间序列预测主要包括三种基本方法:内生时间序列预测技术;外生时间序列预测技术;主观时间序列预测技术。时间序列分析与预测在经济[12]、金融[13]、工程[14]等领域有着广泛的应用,研究成果也最为丰富,将另文讨论。

     

    参考文献

    1.        Keogh E, Kasetty S. On the need for time series data mining benchmarks: a survey and empirical demonstration.Data Mining and Knowledge Discovery, 2003, 7(4): 349-371.

    2.        Yang Qiang, Wu Xindong. 10 challenging problems in data mining research. International Journal of Information Technology & Decision Making, 2006, 5(4): 597-604.

    3.        Lin J, Keogh E, Lonardi S, Chiu B. A symbolic representation of time series, with implications for streaming algorithms. Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, 2003, Pages: 2 – 11.  

    4.        Gullo F, Ponti G, Tagarelli A, Greco S. A time series representation model for accurate and fast similarity detection, Pattern Recognition, 2009, 42(11): 2998-3014.

    5.        Gunopulos D, Das G. Time series similarity measures. KDD’00: Tutorial notes of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, 2000.

    6.        Literatures on Similarity-based Time Series Retrieval.http://www.cs.ust.hk/~leichen/readings/literaturesovertimeseries.htm

    7.        Liao T W. Clustering of time series data: a survey. Pattern Recognition, 2005, 38: 1857-1874

    8.        Dasgupta D, Forrest S. Novelty detection in time series data using ideas from immunology. In: Proceeding of the 5th International Conference on Intelligent Systems. 1996, Pages: 82- 87.

    9.        Ma J, Perkins S. Time-series Novelty Detection Using One-class Support Vector Machines. Procedding of International Joint Conference on Neural Networks, 2003.

    10.    Keogh E, Lonardi S. Finding surprising patterns in a time series database in linear time and space. Proceedings of the eighth ACM SIGKDD, 2002.

    11.    杨一鸣,潘嵘,潘嘉林,杨强,李磊. 时间序列分类问题的算法比较. 计算机学报,2007,30(8):1259-1265.

    12.   Clements M P(柯莱蒙兹),Hendry D F(韩德瑞),陆懋祖. 预测经济时间序列. 北京大学出版社,2008

    13.    Tsay R S(蔡瑞胸),潘家柱译. 金融时间序列分析. 机械工业出版社,2006

    14.  杨叔子.时间序列分析的工程应用(上下册).第二版.华中科技大学出版社,2007 

     

    展开全文
  • 时间序列频繁模式挖掘:GSP算法、SPADE算法

    万次阅读 热门讨论 2015-08-07 10:55:55
    什么是时间戳概念的频繁模式挖掘? 所谓时间戳(time-stamp)就是加入了时间序列的概念,即每次发生的时间都有时间先后的顺序,在前面讲解的Apriori算法中并没有加入此概念,虽然Apriori加入了先验性质以减少每轮遍历...

    本文核心理论依托于MOHAMMED J. ZAKI于Machine Learning, 42, 31–60, 2001发表的文章,由于国内暂时没有相应文献对SPADE算法做详细讲解,本人翻译原文后以通俗易懂的形式展现给读者。英文水平捉急,若有个别地方理解有误望批评指正。

    1.什么是时间戳概念的频繁模式挖掘?

    所谓时间戳(time-stamp)就是加入了时间序列的概念,即每次发生的时间都有时间先后的顺序,在前面讲解的Apriori算法中并没有加入此概念,虽然Apriori加入了先验性质以减少每轮遍历的次数,但是由于加入了“时间发生先后”的概念,导致时间复杂度大大增加,无疑需要一种新颖的办法解决该问题。

    2.GSP算法

    GSP算法是加入了垂直列表数据库和哈希树概念的Apriori算法,并且依旧使用连接步、剪枝步完成计算。其处理思路如下:
    原始数据

    上图是我们的原始数据,其中SID表示事件号,EID表示时间戳(即什么时候发生了该动作),我们可以看到,在一个事件内可以在多个时间发生动作,在一个时间点内也可以发生多个动作,诸如x->y这样的行为表示先发生了x,之后发生了y,之间隔了多长时间无所谓,但是一定要在一个SID中。
    如果假定支持度为2,那么1成员频繁序列有A、B、D、F四个成员,出现的次数如右图,以成员A为例,则表示A成员在SID=1~4这四个事件中都出现过,在计算2成员频繁序列中采用广度搜索的哈希树作为遍历手段,如下图所示:
    GSP哈希树

    我们可以看到,再加入时间戳概念后,遍历的复杂度大大提高,因为不光要考虑诸如AB这样的“同时发生”的概念,概要考虑A->B这样的先后次序发生概念,在本data中寻找2成员频繁项集一共需要(3*2)*4=24次,然后每次需要在遍历全部的data来判断该项目是否频繁,那么一共需要计算24*10=240次,几百次对计算机来说不成问题。最终计算结果如下图:
    GSP结果

    我可以看到,3成员频繁项集虽然看起来匹配的很轻松,但是依旧要遍历8次原始数据,一旦数据巨大,无疑这笔开销会异常恐怖,为了进一步提升效率,学者研发了SPADE算法。

    2.SPADE算法

    SPADE算法依旧使用传统的先验性质,即连接步+剪枝步的经典组合,思想跟GSP大致相同,其中寻找1成员和2成员频繁项集方法跟GSP完全形同,在之后的3成员及之后的频繁项计算中,采取了一种“作弊”的办法 (= -) ,该办法套用了三种屡试不爽的公式,如下:
    1.如果诸如成员PA,PD这样的形式出现在2频繁项集中,则能推导出PBD这样的三成员元素。
    2.如果出现诸如PB,P->A这样的形式出现在2频繁项集中,则能推导出PB->A这样的三成员元素。
    3.如果出现诸如P->A,P->F这样的形式出现在2频繁项集中,则能推导出P->AF或P->A->F或P->F->A这样的三成员元素。
    原文

    以上推推导出的三成员元素注意!仅仅是“有可能”是频繁的元素,至于是不是频繁的,还得去原始data中进一步遍历、判断。
    比如在本例中AB,AF是两个频繁的2成员项,那么有可能注意是“有可能”存在且仅存在ABF这样的3成员频繁项,经过10次计算遍历了一遍data发现ABF确实是频繁的。
    一个例子
    在本例中出现了一组奇葩,即D->F,F->A能推导出D->F->A,看似是非常成立的,但经过我的推导发现不一定成立,这怎么办。。。没办法,遇到这种情况只能遍历data。虽说采用SPADE的秘籍可以减少一定的计算次数,但是我觉得它的精髓在于减少I\O次数,毕竟I\O的时间相比计算的时间长的多得多,同时还能节省内存。
    大致思路就是这样,我还没写程序,确实有点难写,网上没有任何源码可供参考,我还是会努力写的,我写好会在下面粘出来。

    2015.10.20我终于写完了源码(python),下面粘下来:运行时间0.000791秒
    #coding:utf-8

    import itertools
    import datetime
    
    class GSP(object):
        def __init__(self):
            self.queue = []
    
    #----------------------------------------------------------#
    #                     计算freq1                            #
    #----------------------------------------------------------#
        def freq1(self, data, frequent_num):
            appear = ''
            freq1 = []
            appear_ele = []
            appear_ele2 = []
            for i in range(len(data)):
                appear = ''
                for j in range(len(data[i])):
                    appear += data[i][j]
                appear_ele += list(set(appear))
            # print(appear_ele)
            appear_ele2 = list(set(appear_ele))
            # print(appear_ele2)
            for item in appear_ele2:
                itmes = appear_ele.count(item)
                if itmes >= frequent_num:
                    freq1.append(item)
            print('频繁1项集为:%s' %freq1)
            return freq1
    
    #----------------------------------------------------------#
    #                     计算freq_more                        #
    #----------------------------------------------------------#
        def freq_more(self, data, freq1):
            queue = []#所有的备选序列放在这里面
            queue_new = []#最终结果在这里面
            top = 0 #这个是queue_new的队尾标号
            times = 3
            while True:
    
                if (queue_new == []): #为空则代表这是第一次遍历,python中的&&是and,||是or
                    for i in range(len(freq1)):
                        for j in range(i+1, len(freq1)):
                            item = freq1[i] + freq1[j]
                            queue.append(item)
                    for i in range(len(freq1)):
                        for j in range(len(freq1)):
                            if j != i:
                                item = freq1[i] +'->'+ freq1[j]
                                queue.append(item)#第一次遍历后全部可能出现的情况
                    for i in range(len(queue)):
                        freq_item = self.isFreq(queue[i], data)
                        if freq_item != 0:
                            queue_new.append(freq_item)
                    queue = []#清空queue(备选序列)
    
                if (queue_new != []): #后几次遍历时要把所有的情况写入空的queue中
                    if top == len(queue_new) - 1: #表示没有新加入元素,那么终止 while 循环
                        print('频繁多项集为:%s' %queue_new)
                        break
                    else:
                        demo_list = []#专门放'AB','BF','AF'这样的频繁序列,后面将他们合成为更多成员的备选频繁序列
                        for i in range(top, len(queue_new)):
                            if '->' not in queue_new[i]:
                                demo_list.append(queue_new[i])
                        demo_string = self.List_to_String(demo_list) #将列表中的元素拼接成字符串,诸如拼成'ABBFAF'
                        demo_ele = "".join(set(demo_string)) #删除串中的重复元素,输出'ABF'
                        if len(demo_ele) >= times:
                            if len(demo_ele) == times :#那么demo_ele是唯一的备选成员
                                queue.append(demo_ele)
                                times += 1
                            else: #否则对备选字母进行排列组合,比如'ABCDE',一共能排列出10钟情况,并把它们推入queue(待判断成员队列)
                                combin = self.Combinations(demo_ele, times)
                                for i in range(len(combin)):
                                    queue.append(combin[i])
                                times += 1
                        ###-----####至此已经把备选频繁寻列推入 queue ####-----###
    
                        queue = self.Make_time_queue(top, freq1, queue, queue_new)
    
                        ###-----#### 至此已经把 queue 放满了备选成员 ####-----###
    
                        top = len(queue_new)# 更新队尾指针 top 的位置
    
                        ###-----#### 检测 queue 中的备选序列是否频繁 ####-----###
                        for i in range(len(queue)):
                            freq_item = self.isFreq(queue[i], data) #---->> isFreq
                            if freq_item != 0: #如果这个成员是频繁的
                                queue_new.append(freq_item)
                        queue = []
    
        #将列表中的字母合并成字符串
        def List_to_String(self, list):
            demo_string = ''
    
            for i in range(len(list)):
                demo_string = demo_string + list[i]
            return demo_string
    
        #demo_ele是待排列的字符串, times是将它们排列成几个元素
        def Combinations(self, item, times):
            demo_list = []
            combin = []
            element = ''
    
            for i in range(1, len(item) +1):
                iter = itertools.combinations(item, i)
                demo_list.append(list(iter))
            demo_combin = demo_list[times -1]
            for i in range(len(demo_combin)):
                for j in range(len(demo_combin[0])):
                    element += demo_combin[i][j]
                combin.append(element)
                element = ''
            return combin
    
        #判断item是不是频繁的
        def isFreq(self, item, data):
            num = 0
    
            if '->' not in item:   #类似如'ABF'
                for i in range(len(data)):
                    for j in range(len(data[i])):
                        if self.isIn_Item(item, data, i, j) != 0:
                            num += 1
                if num >= 2:
                    return item
                else:
                    return 0
            else:                  #类似如‘D->B->A’
                item0 = item.split('->')
    
                for i in range(len(data)):
                    array = 0
                    j = 0
                    while True:
                        if array == len(item0) or j == len(data[i]):
                            break
                        if len(item0[array]) >= 2: #如果类似 'BA' 形式
                            if self.isIn_Item(item0[array], data, i, j) == 1:
                                array += 1
                                j += 1
                            else:
                                j += 1
                        else:
                            if item0[array] in data[i][j]:
                                array += 1
                                j += 1
                            else:
                                j += 1
                    if array == len(item0):
                        num += 1
                if num >= 2:
                    return item
                else:
                    return 0
    
        #判断 item 是否在 data[i][j]中
        def isIn_Item(self, item, data, i, j):
            demo_num = 0
    
            for k in range(len(item)):
                if item[k] in data[i][j]:
                    demo_num += 1
            if demo_num == len(item):
                return 1
            else:
                return 0
    
        #
        def isIn_Time(self, item0, data, i, j):
            num = 0
    
            item0_lenth = len(item0)
            if item0_lenth == 2:
                for m in range(j+1, len(data[i])):
                    if item0[1] in data[i][m]:
                        num += 1
            else:
                if item0[item0_lenth -2] in data[i][j]:
                    for m in range(j+1, len(data[i])):
                        if item0[item0_lenth -1] in data[i][m]:
                            num += 1
                            break
            return num
    
        #创造新的备选时间序列 
        def Make_time_queue(self, top, freq1, queue, queue_new):
            for i in range(top, len(queue_new)):
    #           for j in range(len(freq1)):
                if '->' not in queue_new[i]:
                    difference = self.Difference(queue_new[i], freq1)
                    for j in range(len(difference)):
                        queue.append(difference[j] + '->' +queue_new[i]) #诸如 'D->AB'
                        queue.append(queue_new[i] + '->' +difference[j]) #诸如 'AB->D'
                else:
                    difference = self.Difference(queue_new[i], freq1)
                    for j in range(len(difference)):
                        queue.append(queue_new[i] + '->' + difference[j]) #诸如'B->A' 扩展成 'B->A->D'
            return queue
    
        #寻找两个字符串中的不同字母,并提取出来
        def Difference(self, item, freq1):
            demo_list = []
    
            if '->' not in item:
                for i in range(len(freq1)):
                    if freq1[i] not in item:
                        demo_list.append(freq1[i])
            else:
                demo_item = item.split('->') #将诸如'A->B'拆分成 'A','B'
                demo_item_string = self.List_to_String(demo_item) #合并成'AB'
                for i in range(len(freq1)):
                    if freq1[i] not in demo_item_string:
                        demo_list.append(freq1[i])
            return demo_list
    
    
    #----------------------------------------------------------#
    #                          main                           #
    #----------------------------------------------------------#
    data = {0:['CD','ABC','ABF','ACDF'],
            1:['ABF','E'],
            2:['ABF'],
            3:['DGH','BF','AGH']}
    starttime = datetime.datetime.now()
    s = GSP()
    freq1 = s.freq1(data, 2)
    s.freq_more(data, freq1)
    endtime = datetime.datetime.now()
    print(endtime - starttime)
    
    展开全文
  • 首先了解一下 A->(EFG)->C 是个什么形式: 这里面被括号包覆的部分表示EFG是无序存在的,比如EFG,EGF,GEF,GFE他们都可以统一写成(EFG)的形式,假设这...导师没有跟我说明这种挖掘模式的意义何在,我大概想了一下可能

    首先了解一下 A->(EFG)->C 是个什么形式:

    这里面被括号包覆的部分表示EFG是无序存在的,比如EFG,EGF,GEF,GFE他们都可以统一写成(EFG)的形式,假设这四个项集都只在A~C的时间段内出现了一次,但是一旦把他们看成(EFG)的形式,那么他们就相当于出现了四次,如果min_sup<=4的话那(EFG)就可以被认为是频繁的。


    这种挖掘模式的意义:

    导师没有跟我说明这种挖掘模式的意义何在,我大概想了一下可能是这种情况:两位老师A、C发言之间有EFG三位学生在短时间内在多个时间点进行过频繁交流,但是他们说话的次序是乱序的。通过本模式就可以找出这三位同学很可能是技术伙伴或者是合伙人等等,但是依靠传统的模式他们的交流很可能就不是频繁的,也就找不出他们的关系了。

    当然这种形式也未必非得是在某两个事件A,C之间进行的,这并不重要,如何挖掘(EFG)模式才是关键。


    解决思路:

    1. 将A->(  )->C中 (  )里地部分全部挖掘出来(要标记A,C发生的时间点,在后面会减少时间复杂度)

    时间复杂度O(n)

    2.  将挖出来的含有非freq1元素的项集pop掉

    比如 A->KEF->C 中,如果K元素并不是freq1项集的成员,那么 A->KEF->C 这个项集就剪掉不要了

    3. 提取中间项:

    把“A-”>和“->C”去掉

    4. 假如现在提取出来了三个字符串:MEFG、EMFG、HEGF

    下面要做的跟Apriori做的就一样了,先去freq1项集,再找freq2.....,这里注意一下,找的项集是无序的

    比如:‘’EF’‘都出现在了这三个成员之中,只要是出现了,就记它的频度+1,最后跟min_sup比较一下就行了

    最终我提取出乱序freq-3项集有(min_sup=2):(EFG),(EFM),(FGM),(EGM)

    还可以提出一个freq-4项集:(EFGM)

    字母在括号内的顺序是可以打乱的,这个无所谓。


    关于时间复杂度:

    我大致估计了一下,不会超过常数倍O(n^2),与之前的GSP算法结合一下时间复杂度依旧常数倍O(n^2)的时间复杂度,可以接 受。


    代码实现:(完善中,敬请期待...)

    展开全文
  • 因此,本文提出了一种带时间间隔的序列模式挖掘算法,我们称其为I-PrefixSpan算法。 一、引言 带时间间隔的序列模式可以提供比传统序列模式更有价值的信息。我们以零售业务为例:在带时间间隔的序列模式的帮助下...

    序列模式挖掘,即是在序列数据库中挖掘出频繁子序列,是一个具有广泛应用的重要的数据挖掘问题。PrefixSpan 算法可以有效地挖掘出大规模数据的频繁子序列,然而,它并没有项集之间的时间间隔。因此,本文提出了一种带时间间隔的序列模式挖掘算法,我们称其为I-PrefixSpan算法。

    一、引言

    带时间间隔的序列模式可以提供比传统序列模式更有价值的信息。我们以零售业务为例:在带时间间隔的序列模式的帮助下,零售商不仅可以了解客户的习惯,兴趣和需求,还可以了解他们购物的时间。因此,带时间间隔的序列模式允许零售商在合适的时间向正确的客户提供正确的产品和正确的服务。带时间间隔的序列模式也可以从许多其他类型的数据中挖掘出来,例如警察部门的犯罪记录,旅行社的旅行者记录,医院的诊断记录以及任何其他商业记录。在所有这些情况下,如果可以挖掘出带时间间隔的序列模式,那么在决策时将会非常有用。

    比如,在电子商务的世界中,可以从日志中提取客户的购买行为。例如,在网上购买了产品A,客户在一周内返回购买产品B。这些时间间隔序列模式产生巨大的好处。最简单的应用,通过推送技术可以主动向客户发送所需的信息。无需浏览网站,客户可以获得全新的所需信息。因此,不仅客户体验到快速获得的正确信息的便利性,而且还增加了他们从该公司购买产品的可能性。

    二、I-PrefixSpan算法原理

    先看一下什么是时间间隔交易数据库和它的支持度的定义,举例如下:

    设定时间间隔集合 I T = { I 0 , I 1 , I 2 , I 3 } IT=\left \{ I_0,I_1,I_2,I_3\right \} IT={I0,I1,I2,I3},其中 I 0 : t = 0 , I 1 : 0 &lt; t ≤ 3 , I 2 : 3 &lt; t ≤ 6 , I 3 : 6 &lt; t ≤ ∞ I_0:t=0, I_1:0&lt;t\le3, I_2:3&lt;t\le6,I_3:6&lt;t\le\infty I0:t=0,I1:0<t3,I2:3<t6,I3:6<t。有一时间间隔的序列 ( b , I 1 , e , I 2 , c ) (b,I_1,e,I_2,c) (b,I1,e,I2,c)包括3项,因此该序列长度为3。我们称其为3时间间隔序列( 3-time-interval sequence)。我们可以看到, ( b , I 1 , e , I 2 , c ) (b,I_1,e,I_2,c) (b,I1,e,I2,c)是交易序号40的时间间隔子序列,同样,它也是交易序号10和30时间间隔子序列,因此,它的支持度为 0.75 0.75 0.75。如果设定最小支持度为0.5, ( b , I 1 , e , I 2 , c ) (b,I_1,e,I_2,c) (b,I1,e,I2,c)就是该交易数据库的频繁3时间间隔子序列

    接下来,我先介绍带时间间隔的前缀,投影,后缀,映射数据库等概念。形式化地介绍一下I-PrefixSpan算法。


    定义一
    给定一个交易序列 α = ( ( a 1 , t 1 ) , ( a 2 , t 2 ) , ( a 3 , t 3 ) , . . . , ( a n , t n ) ) \alpha=((a_1,t_1),(a_2,t_2),(a_3,t_3),...,(a_n,t_n)) α=((a1,t1),(a2,t2),(a3,t3),...,(an,tn))和一个时间间隔序列 β = ( b 1 , &amp; 1 , b 2 , &amp; 2 , . . . , b m − 1 , &amp; m − 1 , b m ) ( m ≤ n ) \beta=(b_1,\&amp;_1,b_2,\&amp;_2,...,b_{m-1},\&amp;_{m-1},b_m)(m\le n) β=(b1,&1,b2,&2,...,bm1,&m1,bm)(mn) β \beta β被称为 α \alpha α时间间隔前缀(time-interval prefix)当且仅当(1): b i = a i , 1 ≤ i ≤ m b_i=a_i,1\le i\le m bi=ai,1im;(2): t i − t i − 1 t_i-t_{i-1} titi1满足 &amp; i − 1 \&amp;_{i-1} &i1 1 ≤ i ≤ m − 1 1\le i\le m-1 1im1

    概念有点晦涩,举例如下:设定时间间隔集合 I T = { I 0 , I 1 , I 2 , I 3 } IT=\left \{ I_0,I_1,I_2,I_3\right \} IT={I0,I1,I2,I3},其中 I 0 : t = 0 , I 1 : 0 &lt; t ≤ 3 , I 2 : 3 &lt; t ≤ 6 , I 3 : 6 &lt; t ≤ ∞ I_0:t=0, I_1:0&lt;t\le3, I_2:3&lt;t\le6,I_3:6&lt;t\le\infty I0:t=0,I1:0<t3,I2:3<t6,I3:6<t β = ( b , I 0 , c , I 1 , a ) \beta=(b,I_0,c,I_1,a) β=(b,I0,c,I1,a) α = ( ( b , 1 ) , ( c , 1 ) , ( a , 3 ) , ( e , 5 ) , ( b , 7 ) , ( d , 7 ) , ( a , 11 ) ) \alpha=((b,1),(c,1),(a,3),(e,5),(b,7),(d,7),(a,11)) α=((b,1),(c,1),(a,3),(e,5),(b,7),(d,7),(a,11))时间间隔前缀


    定义二
    给定一个交易序列 α = ( ( a 1 , t 1 ) , ( a 2 , t 2 ) , ( a 3 , t 3 ) , . . . , ( a n , t n ) ) \alpha=((a_1,t_1),(a_2,t_2),(a_3,t_3),...,(a_n,t_n)) α=((a1,t1),(a2,t2),(a3,t3),...,(an,tn))和一个时间间隔序列 β = ( b 1 , &amp; 1 , b 2 , &amp; 2 , . . . , b s − 1 , &amp; s − 1 , b s ) ( s ≤ n ) \beta=(b_1,\&amp;_1,b_2,\&amp;_2,...,b_{s-1},\&amp;_{s-1},b_s)(s\le n) β=(b1,&1,b2,&2,...,bs1,&s1,bs)(sn),使得 β \beta β α \alpha α的时间间隔子序列。令 i 1 &lt; i 2 &lt; . . . &lt; i s i_1&lt;i_2&lt;...&lt;i_s i1<i2<...<is是与 β \beta β中元素匹配的 α \alpha α元素的索引。一个 α \alpha α的子序列 α ′ = ( ( a 1 ′ , t 1 ′ ) , ( a 2 ′ , t 2 ′ ) , ( a 3 ′ , t 3 ′ ) , . . . , ( a p ′ , t p ′ ) ) {\alpha}&#x27;=(({a_1}&#x27;,{t_1}&#x27;),({a_2}&#x27;,{t_2}&#x27;),({a_3}&#x27;,{t_3}&#x27;),...,({a_p}&#x27;,{t_p}&#x27;)) α=((a1,t1),(a2,t2),(a3,t3),...,(ap,tp)),其中 p = s + n − i s p=s+n-i_s p=s+nis被称为 α \alpha α相对于 β \beta β投影(projection)当且仅当(1): β \beta β α ′ {\alpha}&#x27; α时间间隔前缀;(2) α ′ {\alpha}&#x27; α的最后 n − i s n-i_s nis个元素与 α {\alpha} α的最后 n − i s n-i_s nis个元素完全相同。

    举例如下:如果 α = ( ( a , 1 ) , ( c , 3 ) , ( a , 4 ) , ( b , 4 ) , ( a , 6 ) , ( e , 6 ) , ( c , 10 ) ) \alpha=((a,1),(c,3),(a,4),(b,4),(a,6),(e,6),(c,10)) α=((a,1),(c,3),(a,4),(b,4),(a,6),(e,6),(c,10))被投影到 β = ( a ) \beta=(a) β=(a),则可以获得3个不同的映射,分别是 ( ( a , 1 ) , ( c , 3 ) , ( a , 4 ) , ( b , 4 ) , ( a , 6 ) , ( e , 6 ) , ( c , 10 ) ) ((a,1),(c,3),(a,4),(b,4),(a,6),(e,6),(c,10)) ((a,1),(c,3),(a,4),(b,4),(a,6),(e,6),(c,10)) ( ( a , 4 ) , ( b , 4 ) , ( a , 6 ) , ( e , 6 ) , ( c , 10 ) ) ((a,4),(b,4),(a,6),(e,6),(c,10)) ((a,4),(b,4),(a,6),(e,6),(c,10)) ( ( a , 6 ) , ( e , 6 ) , ( c , 10 ) ) ((a,6),(e,6),(c,10)) ((a,6),(e,6),(c,10)),值得注意的是,前缀 β \beta β α \alpha α中出现了3次,第一次出现在了位置1,第二次出现在了位置3,第三次出现在了位置5。对于位置1来说, α ′ = ( ( a , 1 ) , ( c , 3 ) , ( a , 4 ) , ( b , 4 ) , ( a , 6 ) , ( e , 6 ) , ( c , 10 ) ) {\alpha}&#x27;=((a,1),(c,3),(a,4),(b,4),(a,6),(e,6),(c,10)) α=((a,1),(c,3),(a,4),(b,4),(a,6),(e,6),(c,10)) α ′ {\alpha}&#x27; α的最后 6 6 6个元素与 α {\alpha} α的最后 6 6 6个元素完全相同。进一步地,对于位置3来说, α ′ = ( ( a , 4 ) , ( b , 4 ) , ( a , 6 ) , ( e , 6 ) , ( c , 10 ) ) {\alpha}&#x27;=((a,4),(b,4),(a,6),(e,6),(c,10)) α=((a,4),(b,4),(a,6),(e,6),(c,10)) α ′ {\alpha}&#x27; α的最后 4 4 4个元素与 α {\alpha} α的最后 4 4 4个元素完全相同。对于位置5来说, α ′ = ( ( a , 6 ) , ( e , 6 ) , ( c , 10 ) ) {\alpha}&#x27;=((a,6),(e,6),(c,10)) α=((a,6),(e,6),(c,10)) α ′ {\alpha}&#x27; α的最后 2 2 2个元素与 α {\alpha} α的最后 2 2 2个元素完全相同。

    上述示例表明,序列 α {\alpha} α相对于前缀 β \beta β进行投影的话,可能产生不止一个投影 α ′ {\alpha}&#x27; α。为了区分这些不同的投影,使用 [ S i d : P o s ] [Sid:Pos] [SidPos]附加到每个 α ′ {\alpha}&#x27; α,其中 S i d Sid Sid是交易序列的标识符, P o s Pos Pos是匹配 β \beta β的最后一个元素在 α {\alpha} α的位置。


    定义三
    α ′ = ( ( a 1 ′ , t 1 ′ ) , ( a 2 ′ , t 2 ′ ) , ( a 3 ′ , t 3 ′ ) , . . . , ( a p ′ , t p ′ ) ) {\alpha}&#x27;=(({a_1}&#x27;,{t_1}&#x27;),({a_2}&#x27;,{t_2}&#x27;),({a_3}&#x27;,{t_3}&#x27;),...,({a_p}&#x27;,{t_p}&#x27;)) α=((a1,t1),(a2,t2),(a3,t3),...,(ap,tp)) α \alpha α相对于时间间隔前缀 β = ( b 1 , &amp; 1 , b 2 , &amp; 2 , . . . , b s − 1 , &amp; s − 1 , b s ) \beta=(b_1,\&amp;_1,b_2,\&amp;_2,...,b_{s-1},\&amp;_{s-1},b_s) β=(b1,&1,b2,&2,...,bs1,&s1,bs)投影。我们称 γ = ( ( a s + 1 ′ , t s + 1 ′ ) , ( a s + 2 ′ , t s + 2 ′ ) , ( a s + 3 ′ , t s + 3 ′ ) , . . . , ( a p ′ , t p ′ ) ) \gamma=(({a_{s+1}}&#x27;,{t_{s+1}}&#x27;),({a_{s+2}}&#x27;,{t_{s+2}}&#x27;),({a_{s+3}}&#x27;,{t_{s+3}}&#x27;),...,({a_p}&#x27;,{t_p}&#x27;)) γ=((as+1,ts+1),(as+2,ts+2),(as+3,ts+3),...,(ap,tp)) α \alpha α相对于前缀 β \beta β后缀(postfix)。

    举例如下:从后缀的定义得知,我们直接从投影中移除前缀就可以得到后缀。 β = ( a ) \beta=(a) β=(a)的3个不同的投影 α ′ {\alpha}&#x27; α分别是 ( ( a , 1 ) , ( c , 3 ) , ( a , 4 ) , ( b , 4 ) , ( a , 6 ) , ( e , 6 ) , ( c , 10 ) ) ((a,1),(c,3),(a,4),(b,4),(a,6),(e,6),(c,10)) ((a,1),(c,3),(a,4),(b,4),(a,6),(e,6),(c,10)) ( ( a , 4 ) , ( b , 4 ) , ( a , 6 ) , ( e , 6 ) , ( c , 10 ) ) ((a,4),(b,4),(a,6),(e,6),(c,10)) ((a,4),(b,4),(a,6),(e,6),(c,10)) ( ( a , 6 ) , ( e , 6 ) , ( c , 10 ) ) ((a,6),(e,6),(c,10)) ((a,6),(e,6),(c,10))。因此,3个后缀分别是 ( ( c , 3 ) , ( a , 4 ) , ( b , 4 ) , ( a , 6 ) , ( e , 6 ) , ( c , 10 ) ) ((c,3),(a,4),(b,4),(a,6),(e,6),(c,10)) ((c,3),(a,4),(b,4),(a,6),(e,6),(c,10)) ( ( b , 4 ) , ( a , 6 ) , ( e , 6 ) , ( c , 10 ) ) ((b,4),(a,6),(e,6),(c,10)) ((b,4),(a,6),(e,6),(c,10)) ( ( e , 6 ) , ( c , 10 ) ) ((e,6),(c,10)) ((e,6),(c,10))

    最后, α \alpha α-映射数据库,我们用 S ∣ α S|_\alpha Sα表示,定义为交易数据库 S S S相对于 α \alpha α的后缀的集合。


    I-PrefixSpan算法最重要的一点在于,其包括了在 S ∣ α S|_\alpha Sα中的频繁项 b b b α \alpha α中的最后一项之间的时间间隔关系。在I-PrefixSpan,使用了一个数据结构表 T a b l e Table Table来具体解决这个问题。具体地,在交易数据库中, T a b l e Table Table的每一列代表每个频繁1项集(可以理解为每个sku),每一行代表时间间隔集合 I T = { I 0 , I 1 , I 2 , . . . , I r } IT=\left \{ I_0,I_1,I_2,...,I_r\right \} IT={I0,I1,I2,...,Ir}的每一项。 T a b l e Table Table的元素 T a b l e ( I i , b ) Table(I_i,b) Table(Ii,b)记录了 S ∣ α S|_\alpha Sα中满足商品 b b b α \alpha α的最后一项之间的时间差位于 I i I_i Ii内的那些交易的数量和

    顺序地处理 S ∣ α S|_\alpha Sα中的每个交易从而构建 T a b l e Table Table和那些频繁出现的元素。如果元素 T a b l e ( I i , b ) Table(I_i,b) Table(Ii,b)是一个频繁元素, ( I i , b ) (I_i,b) (Ii,b)可以加入到 α \alpha α中从而生成一个时间间隔序列模式 α ′ {\alpha}&#x27; α,然后可以构建 α ′ {\alpha}&#x27; α-映射数据库 S ∣ α ′ S|_{{\alpha}&#x27;} Sα,最终递归生成所有的频繁子序列。下图展示了I-PrefixSpan算法的流程:

    以上的讲述可能确实比较晦涩,抽象化的东西都是这样。接下来,我们实例化以上的内容。

    三、I-PrefixSpan算法举例

    A
    设定时间间隔集合 I T = { I 0 , I 1 , I 2 , I 3 } IT=\left \{ I_0,I_1,I_2,I_3\right \} IT={I0,I1,I2,I3},其中 I 0 : t = 0 , I 1 : 0 &lt; t ≤ 3 , I 2 : 3 &lt; t ≤ 6 , I 3 : 6 &lt; t ≤ ∞ I_0:t=0, I_1:0&lt;t\le3, I_2:3&lt;t\le6,I_3:6&lt;t\le\infty I0:t=0,I1:0<t3,I2:3<t6,I3:6<t。交易序列数据库还使用图1所示。最小支持度设定为2。在一开始, α = n u l l \alpha=null α=null,1频繁项集为 ( a ) , ( b ) , ( c ) , ( d ) , ( e ) (a),(b),(c),(d),(e) (a),(b),(c),(d),(e)。因为 f f f只出现了1次。把这5个频繁项集加入到 α = n u l l \alpha=null α=null后会生成5个不同的 α ′ {\alpha}&#x27; α,对于每个 α ′ {\alpha}&#x27; α该程序都会重新调用。我们现在只考虑一种情况 α ′ = ( a ) {\alpha}&#x27;=(a) α=(a),因此 I − P r e f i x S p a n ( ( a ) , 1 , S ∣ ( a ) ) I-PrefixSpan((a),1,S|_{(a)}) IPrefixSpan((a),1,S(a))被调用,则投影数据库 S ∣ ( a ) S|_{(a)} S(a)如下所示:
    [ 10 : 1 ] ( ( c , 3 ) , ( a , 4 ) , ( b , 4 ) , ( a , 6 ) , ( e , 6 ) , ( c , 10 ) ) [ 10 : 4 ] ( ( b , 4 ) , ( a , 6 ) , ( e , 6 ) , ( c , 10 ) ) [ 10 : 6 ] ( ( e , 6 ) , ( c , 10 ) ) [ 20 : 7 ] ( ( b , 7 ) , ( e , 7 ) , ( d , 9 ) , ( e , 9 ) , ( c , 14 ) , ( d , 14 ) ) [ 30 : 8 ] ( ( b , 8 ) , ( e , 11 ) , ( d , 13 ) , ( b , 16 ) , ( c , 16 ) , ( c , 20 ) ) \begin{aligned} [10:1]\\ &amp;((c,3),(a,4),(b,4),(a,6),(e,6),(c,10))\\ [10:4]\\ &amp;((b,4),(a,6),(e,6),(c,10)) \\ [10:6] \\ &amp;((e,6),(c,10)) \\ [20:7]\\ &amp;((b,7),(e,7),(d,9),(e,9),(c,14),(d,14)) \\ [30:8] \\ &amp;((b,8),(e,11),(d,13),(b,16),(c,16),(c,20)) \\ \end{aligned} [10:1][10:4][10:6][20:7][30:8]((c,3),(a,4),(b,4),(a,6),(e,6),(c,10))((b,4),(a,6),(e,6),(c,10))((e,6),(c,10))((b,7),(e,7),(d,9),(e,9),(c,14),(d,14))((b,8),(e,11),(d,13),(b,16),(c,16),(c,20))

    在程序中,如下图所示的 T a b l e Table Table会首先构造出来。上面我们提过:这个表构造的过程就是记录了 S ∣ α S|_\alpha Sα中满足商品 b b b α \alpha α的最后一项之间的时间差位于 I i I_i Ii内的那些交易的数量和。(注:这里的 α ′ {\alpha}&#x27; α就是上面那句话中的 α \alpha α), α ′ {\alpha}&#x27; α的最后一项是 ( a ) (a) (a) ( a ) (a) (a)在交易数据库中出现的位置分别是 [ 10 : 1 ] , [ 10 : 4 ] , [ 10 : 6 ] , [ 20 : 7 ] , [ 30 : 8 ] [10:1],[10:4],[10:6],[20:7],[30:8] [10:1],[10:4],[10:6],[20:7],[30:8],我们依次遍历 ( a ) (a) (a)的后缀,以 ( ( c , 3 ) , ( a , 4 ) , ( b , 4 ) , ( a , 6 ) , ( e , 6 ) , ( c , 10 ) ) ((c,3),(a,4),(b,4),(a,6),(e,6),(c,10)) ((c,3),(a,4),(b,4),(a,6),(e,6),(c,10))为例,计算下时间差,填入到对应的 I i I_i Ii中。就可以得到下表:
    注意:在一条记录里最多只能出现1个。例如,在 S i d = 10 Sid=10 Sid=10 ( a , I 1 , a ) (a,I_1,a) (a,I1,a)有两次,但是也只能算1条,因为这只是1个记录

    Tableabcde
    I 0 I_0 I003002
    I 1 I_1 I111113
    I 2 I_2 I210111
    I 3 I_3 I301310

    上表说明了频繁的元素是 ( I 0 , b ) , ( I 0 , e ) , ( I 1 , e ) , ( I 3 , c ) (I_0,b),(I_0,e),(I_1,e),(I_3,c) (I0,b),(I0,e),(I1,e),(I3,c)。将这些元素加入到 ( a ) (a) (a)的末尾,生成了4个不同的 α ′ {\alpha}&#x27; α,分别是 ( a , I 0 , b ) , ( a , I 0 , e ) , ( a , I 1 , e ) , ( a , I 3 , c ) (a,I_0,b),(a,I_0,e),(a,I_1,e),(a,I_3,c) (a,I0,b),(a,I0,e),(a,I1,e),(a,I3,c)。对于所有的新的不同的 α ′ {\alpha}&#x27; α,程序再一次被调用。

    B-1
    对于 ( a , I 0 , b ) (a,I_0,b) (a,I0,b),程序将会调用 I − P r e f i x S p a n ( ( a , I 0 , b ) , 2 , S ∣ ( a , I 0 , b ) ) I-PrefixSpan((a,I_0,b),2,S|_{(a,I_0,b)}) IPrefixSpan((a,I0,b),2,S(a,I0,b)),其投影数据库 S ∣ ( a , I 0 , b ) S|_{(a,I_0,b)} S(a,I0,b)如下所示:
    [ 10 : 4 ] ( ( a , 6 ) , ( e , 6 ) , ( c , 10 ) ) [ 20 : 7 ] ( ( e , 7 ) , ( d , 9 ) , ( e , 9 ) , ( c , 14 ) , ( d , 14 ) ) [ 30 : 8 ] ( ( e , 11 ) , ( d , 13 ) , ( b , 16 ) , ( c , 16 ) , ( c , 20 ) ) \begin{aligned} [10:4]\\ &amp;((a,6),(e,6),(c,10)) \\ [20:7]\\ &amp;((e,7),(d,9),(e,9),(c,14),(d,14)) \\ [30:8] \\ &amp;((e,11),(d,13),(b,16),(c,16),(c,20)) \\ \end{aligned} [10:4][20:7][30:8]((a,6),(e,6),(c,10))((e,7),(d,9),(e,9),(c,14),(d,14))((e,11),(d,13),(b,16),(c,16),(c,20))

    ( a , I 0 , b ) (a,I_0,b) (a,I0,b)出现了3次,其最后一项是 ( b ) (b) (b) ( b ) (b) (b)来自于投影数据库 S ∣ ( a ) S|_{(a)} S(a) [ 10 : 4 ] , [ 20 : 7 ] , [ 30 : 8 ] [10:4],[20:7],[30:8] [10:4],[20:7],[30:8],且 ( b ) (b) (b)出现的位置分别是 [ 10 : 4 ] , [ 20 : 7 ] , [ 30 : 8 ] [10:4],[20:7],[30:8] [10:4],[20:7],[30:8],故其投影数据库 S ∣ ( a , I 0 , b ) S|_{(a,I_0,b)} S(a,I0,b)如上所示。注意: S ∣ ( a , I 0 , b ) S|_{(a,I_0,b)} S(a,I0,b) S ∣ ( a ) S|_{(a)} S(a)中的 [ 10 : 4 ] , [ 20 : 7 ] , [ 30 : 8 ] [10:4],[20:7],[30:8] [10:4],[20:7],[30:8]中的 4 , 7 , 8 4,7,8 4,7,8的含义是完全不同的,前者代表了 b b b的位置,后者代表了 a a a的位置

    它对应的 T a b l e Table Table如下:

    Tableabcde
    I 0 I_0 I000001
    I 1 I_1 I110013
    I 2 I_2 I200110
    I 3 I_3 I301210

    这里有一个小trick,因此 a , d a,d a,d在第一个表从来没有频繁元素,因此在以后构造表时也无需再对 a , d a,d a,d进行计算了。上表仍然计算了 a , d a,d a,d是想说明这个问题。

    我们可以看到,频繁元素是 ( I 1 , e ) , ( I 3 , c ) (I_1,e),(I_3,c) (I1,e),(I3,c)。将这些元素加入到 ( a , I 0 , b ) (a,I_0,b) (a,I0,b)的末尾,生成了2个不同的 α ′ {\alpha}&#x27; α,分别是 ( a , I 0 , b , I 1 , e ) , ( a , I 0 , b , I 3 , c ) (a,I_0,b,I_1,e),(a,I_0,b,I_3,c) (a,I0,b,I1,e),(a,I0,b,I3,c)。对于所有的新的不同的 α ′ {\alpha}&#x27; α,程序再一次被调用。我们以 ( a , I 0 , b , I 1 , e ) (a,I_0,b,I_1,e) (a,I0,b,I1,e)举例。

    B-1-1
    对于 ( a , I 0 , b , I 1 , e ) (a,I_0,b,I_1,e) (a,I0,b,I1,e),程序将会调用 I − P r e f i x S p a n ( ( a , I 0 , b , I 1 , e ) , 3 , S ∣ ( a , I 0 , b , I 1 , e ) ) I-PrefixSpan((a,I_0,b,I_1,e),3,S|_{(a,I_0,b,I_1,e)}) IPrefixSpan((a,I0,b,I1,e),3,S(a,I0,b,I1,e)),其投影数据库 S ∣ ( a , I 0 , b , I 1 , e ) S|_{(a,I_0,b,I_1,e)} S(a,I0,b,I1,e)如下所示:
    [ 10 : 6 ] ( ( a , 6 ) , ( c , 10 ) ) [ 20 : 9 ] ( ( c , 14 ) , ( d , 14 ) ) [ 30 : 11 ] ( ( d , 13 ) , ( b , 16 ) , ( c , 16 ) , ( c , 20 ) ) \begin{aligned} [10:6]\\ &amp;((a,6),(c,10)) \\ [20:9]\\ &amp;((c,14),(d,14)) \\ [30:11] \\ &amp;((d,13),(b,16),(c,16),(c,20)) \\ \end{aligned} [10:6][20:9][30:11]((a,6),(c,10))((c,14),(d,14))((d,13),(b,16),(c,16),(c,20))

    ( a , I 0 , b , I 1 , e ) (a,I_0,b,I_1,e) (a,I0,b,I1,e)出现了3次,其最后一项是 ( e ) (e) (e) ( e ) (e) (e)来自于投影数据库 S ∣ ( a , I 0 , b ) S|_{(a,I_0,b)} S(a,I0,b) [ 10 : 4 ] , [ 20 : 7 ] , [ 30 : 8 ] [10:4],[20:7],[30:8] [10:4],[20:7],[30:8],且 ( e ) (e) (e)出现的位置分别是 [ 10 : 6 ] , [ 20 : 9 ] , [ 30 : 11 ] [10:6],[20:9],[30:11] [10:6],[20:9],[30:11],故其投影数据库 S ∣ ( a , I 0 , b , I 1 , e ) S|_{(a,I_0,b,I_1,e)} S(a,I0,b,I1,e)如上所示。

    它对应的 T a b l e Table Table如下:无 a , b , d a,b,d a,b,d

    Tablece
    I 0 I_0 I000
    I 1 I_1 I100
    I 2 I_2 I230
    I 3 I_3 I310

    我们可以看到,频繁元素是 ( I 2 , c ) (I_2,c) (I2,c)。将这些元素加入到 ( a , I 0 , b , I 1 , e ) (a,I_0,b,I_1,e) (a,I0,b,I1,e)的末尾,生成了 α ′ {\alpha}&#x27; α,是 ( a , I 0 , b , I 1 , e , I 2 , c ) (a,I_0,b,I_1,e,I_2,c) (a,I0,b,I1,e,I2,c)。对于所有 α ′ {\alpha}&#x27; α,程序再一次被调用。这里省略了下一步。

    B-2
    对于 ( a , I 0 , e ) ( a,I_0,e) (a,I0,e),程序将会调用 I − P r e f i x S p a n ( ( a , I 0 , e ) , 2 , S ∣ ( a , I 0 , e ) ) I-PrefixSpan(( a,I_0,e),2,S|_{( a,I_0,e)}) IPrefixSpan((a,I0,e),2,S(a,I0,e)),其投影数据库 S ∣ ( a , I 0 , e ) S|_{( a,I_0,e)} S(a,I0,e)如下所示:

    [ 10 : 6 ] ( ( c , 10 ) ) [ 20 : 7 ] ( ( b , 7 ) , ( d , 9 ) , ( e , 9 ) , ( c , 14 ) , ( d , 14 ) ) \begin{aligned} [10:6]\\ &amp;((c,10)) \\ [20:7]\\ &amp;((b,7),(d,9),(e,9),(c,14),(d,14)) \\ \end{aligned} [10:6][20:7]((c,10))((b,7),(d,9),(e,9),(c,14),(d,14))

    ( a , I 0 , e ) (a,I_0,e) (a,I0,e)出现了2次,其最后一项是 ( e ) (e) (e) ( e ) (e) (e)来自于投影数据库 S ∣ ( a ) S|_{(a)} S(a) [ 10 : 6 ] , [ 20 : 7 ] [10:6],[20:7] [10:6],[20:7],且 ( e ) (e) (e)出现的位置分别是 [ 10 : 6 ] , [ 20 : 7 ] [10:6],[20:7] [10:6],[20:7],故其投影数据库 S ∣ ( a , I 0 , e ) S|_{(a,I_0,e)} S(a,I0,e)如上所示。

    同理,它对应的 T a b l e Table Table如下:无 a , d a,d a,d

    Tablebce
    I 0 I_0 I0100
    I 1 I_1 I1001
    I 2 I_2 I2010
    I 3 I_3 I3010

    我们可以看到,表中没有频繁元素了,这个分支的递归结束。
    B-3
    对于 ( a , I 1 , e ) ( a,I_1,e) (a,I1,e),程序将会调用 I − P r e f i x S p a n ( ( a , I 1 , e ) , 2 , S ∣ ( a , I 1 , e ) ) I-PrefixSpan(( a,I_1,e),2,S|_{( a,I_1,e)}) IPrefixSpan((a,I1,e),2,S(a,I1,e)),其投影数据库 S ∣ ( a , I 1 , e ) S|_{( a,I_1,e)} S(a,I1,e)如下所示:
    [ 10 : 6 ] ( ( c , 10 ) ) [ 20 : 9 ] ( ( c , 14 ) , ( d , 14 ) ) [ 30 : 11 ] ( ( d , 13 ) , ( b , 16 ) , ( c , 16 ) , ( c , 20 ) ) \begin{aligned} [10:6]\\ &amp;((c,10)) \\ [20:9]\\ &amp;((c,14),(d,14)) \\ [30:11] \\ &amp;((d,13),(b,16),(c,16),(c,20)) \\ \end{aligned} [10:6][20:9][30:11]((c,10))((c,14),(d,14))((d,13),(b,16),(c,16),(c,20))

    ( a , I 1 , e ) ( a,I_1,e) (a,I1,e)出现了3次,其最后一项是 ( e ) (e) (e) ( e ) (e) (e)来自于投影数据库 S ∣ ( a ) S|_{(a)} S(a) [ 10 : 4 ] , [ 20 : 7 ] , [ 30 : 8 ] [10:4],[20:7],[30:8] [10:4],[20:7],[30:8],且 ( e ) (e) (e)出现的位置分别是 [ 10 : 6 ] , [ 20 : 9 ] , [ 30 : 11 ] [10:6],[20:9],[30:11] [10:6],[20:9],[30:11],故其投影数据库 S ∣ ( a , I 1 , e ) S|_{(a,I_1,e)} S(a,I1,e)如上所示。

    同理,它对应的 T a b l e Table Table如下:无 a , d a,d a,d

    Tablebce
    I 0 I_0 I0000
    I 1 I_1 I1000
    I 2 I_2 I2130
    I 3 I_3 I3010

    我们可以看到,频繁元素是 ( I 2 , c ) (I_2,c) (I2,c)。将这些元素加入到 ( a , I 1 , e ) (a,I_1,e) (a,I1,e)的末尾,生成了1个 α ′ {\alpha}&#x27; α,是 ( a , I 1 , e , I 2 , c ) (a,I_1,e,I_2,c) (a,I1,e,I2,c)。对于所有的新的不同的 α ′ {\alpha}&#x27; α,程序再一次被调用。这里,我们再扩展一步。

    B-3-1
    对于 ( a , I 1 , e , I 2 , c ) (a,I_1,e,I_2,c) (a,I1,e,I2,c),程序将会调用 I − P r e f i x S p a n ( ( a , I 1 , e , I 2 , c ) , 3 , S ∣ ( a , I 1 , e , I 2 , c ) ) I-PrefixSpan((a,I_1,e,I_2,c),3,S|_{(a,I_1,e,I_2,c)}) IPrefixSpan((a,I1,e,I2,c),3,S(a,I1,e,I2,c)),其投影数据库 S ∣ ( a , I 1 , e , I 2 , c ) S|_{(a,I_1,e,I_2,c)} S(a,I1,e,I2,c)如下所示:
    [ 10 : 10 ] [ 20 : 14 ] ( ( d , 14 ) ) [ 30 : 16 ] ( ( c , 20 ) ) \begin{aligned} [10:10]\\ &amp; \\ [20:14]\\ &amp;((d,14)) \\ [30:16] \\ &amp;((c,20)) \\ \end{aligned} [10:10][20:14][30:16]((d,14))((c,20))

    ( a , I 1 , e , I 2 , c ) (a,I_1,e,I_2,c) (a,I1,e,I2,c)出现了3次,其最后一项是 ( c ) (c) (c) ( c ) (c) (c)来自于投影数据库 S ∣ ( a , I 1 , e ) S|_{(a,I_1,e)} S(a,I1,e) [ 10 : 6 ] , [ 20 : 9 ] , [ 30 : 11 ] [10:6],[20:9],[30:11] [10:6],[20:9],[30:11],且 ( c ) (c) (c)出现的位置分别是 [ 10 : 10 ] , [ 20 : 14 ] , [ 30 : 16 ] [10:10],[20:14],[30:16] [10:10],[20:14],[30:16],故其投影数据库 S ∣ ( a , I 1 , e , I 2 , c ) S|_{(a,I_1,e,I_2,c)} S(a,I1,e,I2,c)如上所示。

    同理,它对应的 T a b l e Table Table如下:无 a , b , d , e a,b,d,e a,b,d,e

    Tablec
    I 0 I_0 I00
    I 1 I_1 I10
    I 2 I_2 I21
    I 3 I_3 I30

    我们可以看到,表中没有频繁元素了,这个分支的递归结束。
    B-4
    对于 ( a , I 3 , c ) (a,I_3,c) (a,I3,c),程序将会调用 I − P r e f i x S p a n ( ( a , I 3 , c ) , 2 , S ∣ ( a , I 3 , c ) ) I-PrefixSpan((a,I_3,c),2,S|_{(a,I_3,c)}) IPrefixSpan((a,I3,c),2,S(a,I3,c)),其投影数据库 S ∣ ( a , I 3 , c ) S|_{(a,I_3,c)} S(a,I3,c)如下所示:
    [ 10 : 10 ] [ 20 : 14 ] ( ( d , 14 ) ) [ 30 : 16 ] ( ( c , 20 ) ) \begin{aligned} [10:10]\\ &amp; \\ [20:14]\\ &amp;((d,14)) \\ [30:16] \\ &amp;((c,20)) \\ \end{aligned} [10:10][20:14][30:16]((d,14))((c,20))

    ( a , I 3 , c ) (a,I_3,c) (a,I3,c)出现了3次,其最后一项是 ( c ) (c) (c) ( c ) (c) (c)来自于投影数据库 S ∣ ( a ) S|_{(a)} S(a) [ 10 : 1 ] , [ 20 : 7 ] , [ 30 : 8 ] [10:1],[20:7],[30:8] [10:1],[20:7],[30:8],且 ( c ) (c) (c)出现的位置分别是 [ 10 : 10 ] , [ 20 : 14 ] , [ 30 : 16 ] [10:10],[20:14],[30:16] [10:10],[20:14],[30:16],故其投影数据库 S ∣ ( a , I 3 , c ) S|_{(a,I_3,c)} S(a,I3,c)如上所示。

    同理,它对应的 T a b l e Table Table如下:无 a , d a,d a,d

    Tablebce
    I 0 I_0 I0000
    I 1 I_1 I1000
    I 2 I_2 I2010
    I 3 I_3 I3000

    我们可以看到,表中没有频繁元素了,这个分支的递归结束。

    α ′ = ( a ) {\alpha}&#x27;=(a) α=(a)开头的所有的符合支持度的频繁子序列如下:
    ( a , I 0 , b ) ( a , I 0 , b , I 1 , e ) ( a , I 0 , b , I 1 , e , I 2 , c ) ( a , I 0 , b , I 3 , c ) ( a , I 0 , e ) ( a , I 1 , a ) ( a , I 1 , a , I 2 , c ) ( a , I 3 , c ) (a,I_0,b)\\ (a,I_0,b,I_1,e)\\ (a,I_0,b,I_1,e,I_2,c)\\ (a,I_0,b,I_3,c)\\ (a,I_0,e)\\ (a,I_1,a)\\ (a,I_1,a,I_2,c)\\ (a,I_3,c) (a,I0,b)(a,I0,b,I1,e)(a,I0,b,I1,e,I2,c)(a,I0,b,I3,c)(a,I0,e)(a,I1,a)(a,I1,a,I2,c)(a,I3,c)
    上述即是一个可以说明算法流程的例子。

    α ′ = ( b ) {\alpha}&#x27;=(b) α=(b), α ′ = ( c ) {\alpha}&#x27;=(c) α=(c), α ′ = ( d ) {\alpha}&#x27;=(d) α=(d), α ′ = ( e ) {\alpha}&#x27;=(e) α=(e)开头的带时间间隔的频繁子序列挖掘以上述的过程同理,这里省略。

    我们可以总结一下递归停止的条件:分支下不再存在频繁元素,即构造出的 T a b l e Table Table不再存在频繁元素,则递归结束。至于其它的停止条件我得再想想,感觉这个程序得实现还是有点难度的。

    另外,我感觉时间复杂度与时间间隔集合 T I TI TI的设定关系很大。

    参考文献

    【1】Discovering time-interval sequential patterns in sequence databases

    展开全文
  • 序列模式挖掘算法之PrefixSpan

    千次阅读 2019-06-19 09:47:47
    序列模式挖掘算法之PrefixSpanPrefixSpan 配套代码地址...序列模式挖掘简介 序列模式挖掘的基本概念 PrefixSpan的基本概念 PrefixSpan算法过程讲解 主要代码块展示和讲解 序列模式挖掘简介
  • 时间序列模式挖掘之I-PrefixSpan

    千次阅读 2019-06-19 09:47:32
    I-PrefixSpan & LIT-PrefixSpan用于路线推荐的算法 背景介绍 我们通过算法的名字可以知道,这两个算法是在PrefixSpan算法上...个性化推荐系统是建立在海量数据挖掘的基础上的一种智能平台向顾客提供个性化的信
  • 关联规则--Apriori算法部分讨论的关联模式概念都强调同时出现关系,而忽略数据中的序列信息(时间/空间):...注:1)序列模型=关联规则+时间/空间维度2)这里讨论的序列模式挖掘指的是时间维度上的挖掘。一、基本定义序...
  • 探讨了多变量时间序列模式挖掘在中医药临床疗效评价中的作用,在“十五”课题所取得的数据基础上,构建多变量疗效矩阵,用Frobenius范数作判定矩阵的相似关系,并转换为时间序列进行挖掘实验。实验结果与临床判定...
  • 序列模式挖掘:指挖掘相对时间或其他模式出现频率高的模式 序列模式挖掘的动机:大型连锁超市的交易数据有一系列的用户事物数据库。每一条记录包括用户的ID,事物发生的时间和事物涉及的项目。如果能够在其中挖掘...
  • 一般的加权顺序模式挖掘算法会忽略或没有充分利用时间和数据元素的时间间隔信息。 除了某些算法需要扫描数据库外时间或建立临时数据库。 为了解决这些问题,我们提出了一种基于内存的算法MITWCSpan(用于时间间隔...
  • 序列模式挖掘

    千次阅读 2016-05-04 22:34:39
    跟我们所熟知的关联规则挖掘不一样,序列模式挖掘的对象以及结果都是有序的,即数据集中的每个序列的条目在时间或空间上是有序排列的,输出的结果也是有序的。 举个简单的例子来说明,关联规则一个经典的应用是计算...
  • 这里写自定义目录标题大数据挖掘研究序列模式挖掘概念序列模式挖掘和关联规则挖掘的区别经典算法AprioriAll算法定义算法GSP算法FreeSpan算法PrefixSpan算法算法比较 大数据挖掘研究 (1)基于内存数据分解的方式:...
  • 背景在互联网产品中,用户行为分析,通常是指通过统计、分析用户在产品上的各种行为事件,挖掘、发现出有用的信息,为产品的设计,运营策略提供有意义的依据。通常,用户行为分析包含...
  • 频繁序列模式挖掘

    千次阅读 2015-01-20 00:33:26
    1.频繁序列模式挖掘 序列模式是频繁模式的一种特殊情况,它们的应用范围完全不一样!如: 购买物品 尿布、啤酒、可乐 面包、尿布、啤酒 上述购物清单是两个用户的购物清单,根据上面的清单,我们可以...
  • 摘 要提出一种多时间间隔的序列模式挖掘算法 依据挖掘的实际情况设置可变的时间区间 采用有效的剪枝策略分区间精确显示多时间间隔序列模式挖掘结果 实 验 证 明算法具有较高的挖掘性能
  • 基本的序列模式挖掘:主要包括一些经典算法,分为以下几类: 基于Apriori特性的算法:Apriori算法、AprioriSome算法、AprioriAll算法、DynamicSome算法等等 基于垂直格子的算法:SPADE算法 增量式序列模式挖掘:...
  • 数据挖掘-序列模式挖掘--GSP算法

    千次阅读 2020-05-03 18:14:52
    序列模式挖掘:指挖掘相对时间或其他模式出现频率高的模式 序列模式挖掘的动机:大型连锁超市的交易数据有一系列的用户事物数据库。每一条记录包括用户的ID,事物发生的时间和事物涉及的项目。如果能够在其中挖掘...
  • DMBIT:一种有效的序列模式挖掘算法,逄玉俊,宁嘉,大量候选序列模式支持度的计算所带来的时间消耗是序列模式挖掘主要问题之一,为此本文提出了一种有效的序列模式挖掘算法:DMBIT(D
  • 在综合分析近年来时间序列数据挖掘相关文献的基础上,讨论了时间序列数据挖掘的最新进展,对各种学术观点进行了比较归类,并预测了其发展趋势。内容涵盖了时间序列数据变换、相似性搜索、预测、分类、聚类、分割、...
  • 提出了一种采用分段线性方法的时间序列模式表示方法。采用分段线性表示方法对瓦斯浓度时间序列进行模式表示后可换来较小的存储和计算代价,只保留了时间序列的主要形态,去除了细节干扰,更能反映出时间序列的自身特征,...
  • 本文定义了序列x在其前缀序列y上的前缀序列的概念,并提出了一种基于前缀分析的序列模式挖掘算法PPrefixspan。 根据扫描序列数据库SD,获得所有1个长度的序列模式。 比较顺序模式的数量和最小支持数,如果前者小于...
  • 序列模式挖掘是由频繁项挖掘发展而来。 1 序言 序列模式(sequential pattern)挖掘最早由Agrawal等人提出,针对带有交易时间属性的交易数据库,获取频繁项目序列以发现某段时间内客户的购买活动规律。每一次交易...
  • 针对CloSpan算法分两个阶段挖掘闭合序列模式中第一阶段需要保持候选序列且未充分利用项的位置信息、存在对数据库重复扫描和计算大小的不足, 提出了posCloSpan算法。算法通过对二级索引结构进行检索实现向前剪枝, ...
  • 现有的时间序列异步周期模式挖掘方法是在获取1-pattern有效段及周期的基础上再以枚举法得到i-patterns,时间复杂度较高。为解决该问题,提出一种改进的异步周期模式挖掘方法。在时间序列符号化后,使用基于Sequitur...
  • 包含收益的多时间序列频繁模式挖掘模型,王水,王乐,现有的频繁模式挖掘模型不包含对时间序列的时间因素的考虑,也缺乏对模式中可变动
  • 移动序列模式挖掘和传统的序列模式挖掘是不同的 ,首先 ,前者需要考虑更多的时间因素 ;其次 ,移动序列模式中的项之间是连续的 ,因为关心移动用户的下一次移动情况。本文提出了一种挖掘移动序列模式的新技术 :聚类的...
  • 时间序列模式

    千次阅读 2020-04-10 15:31:24
    常用按时间顺序排列的一组随机变量来表示一个随机事件的时间序列,简记为;用或表示该随机序列的n个有序的观察值,称之为序列长度为n的观察值序列。 时间序列在各个领域中都非常常见,就餐饮企业而言,其销售预测...
  • 论文研究-基于共同机制的时间序列关联模式挖掘系统及其应用.pdf, 提出了一种针对不同时间序列间关联模式的发现方法,并阐述了以该方法为基础而构建的关联模式挖掘系统的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 24,400
精华内容 9,760
关键字:

时间序列模式挖掘