不确定时间序列中不确定频繁模式的确定方法

摘要

本发明提出了一种不确定时间序列中不确定频繁模式的确定方法，属于时间序列处理领域。该方法包括以下步骤：S1、选择不确定频繁模式的类型并设定次数阈值

说明书

技术领域

本发明涉及一种时间序列处理方法，尤其涉及一种不确定时间序列中不确 定频繁模式的确定方法。

背景技术

在通信领域，通常会产生大量非常长的不确定时间序列。例如在物联网通 信领域，主要的数据传感设备包括射频识别(RFID)传感器、红外线传感器、 全球定位系统、激光扫描器等，由于物联网部署环境中的不确定因素和数据传 感设备自身采集数据的误差，使得采集到的数据具有不确定性。

目前，大多数时间序列处理方法仅针对确定时间序列，提取确定时间序列 中频繁出现的子序列，只需要考虑子序列出现的次数，次数越多频繁程度越高。 然而，提取不确定时间序列中频繁出现的子序列，不仅需要考虑子序列出现的 次数，还需要考虑子序列出现的概率，因此现有的时间序列处理方法并不适用 于不确定时间序列。

发明内容

本发明旨在解决现有技术中存在的技术问题，特别创新地提出了一种不确 定时间序列中不确定频繁模式的确定方法，不仅考虑了频繁出现的子序列的出 现次数，还考虑了子序列出现的概率，可以精确确定不确定时间序列中不确定 频繁模式。

为了实现本发明的上述目的，本发明提供了一种不确定时间序列中不确定 频繁模式的确定方法，其特征在于包括以下步骤：

S1、选择不确定时间序列中不确定频繁模式的类型并设定不确定频繁模式 的次数阈值和概率阈值η，其中不确定频繁模式的类型包括最小出现模式和非 重叠出现模式，且为正整数，η为[0，1]之间的小数；

S2、根据不确定频繁模式的类型，计算各候选模式在不确定时间序列中的 有效实例：若不确定频繁模式的类型为最小出现模式，则该候选模式对应的有 效实例是指该候选模式在不确定时间序列的所有实例中不包括其他实例的实 例，若不确定频繁模式的类型为非重叠出现模式，则该候选模式对应的有效实 例是指该候选模式在不确定时间序列的所有实例中不相互重叠的实例；

确定各候选模式的类型：如果候选模式对应的任意两个有效实例可以相互 独立出现在不确定时间序列中则确定该候选模式为第一种候选模式；否则确定 该候选模式为第二种候选模式；

S3、针对第一种候选模式，采用动态规划技术计算第一种候选模式出现次 数X大于次数阈值的概率并且在时 判定该第一种候选模式为不确定频繁模式；

S4、针对第二种候选模式，采用状态空间压缩编码技术计算第二种候选模 式出现次数X大于次数阈值的概率并且在时判定该第二种候选模式为不确定频繁模式。

本发明不仅考虑了频繁出现的子序列的出现次数，还考虑了子序列出现的 概率，可以精确确定不确定时间序列中不确定频繁模式，此外，针对候选模式 的不同类型，采用不同的处理技术来确定不确定频繁模式，采用状态空间压缩 编码技术提高了计算效率。

在所述步骤S4中针对第二种候选模式，采用状态空间压缩编码技术与模糊 动态规划技术相结合的方式，判断该第二种候选模式是否为不确定频繁模式。 采用状态空间压缩编码技术与模糊动态规划技术相结合的方式，进一步提高了 计算效率。

在所述步骤S2中采用“前缀+频繁项”的模式，长度为N的候选模式=长度为 N-1的候选模式+长度为1的频繁项，由此依次确定各候选模式对应的有效实 例，提高了有效实例的确定效率，确定了有效实施例的相互关系。

所述步骤S4中采用状态空间压缩编码技术计算第二种候选模式出现次数X 大于次数阈值的概率的过程由以下步骤组成：

A-1、将不确定时间序列的实例分别由状态编码向量v表示，其中该状态编 码向量中包含用于表示对应不确定时间序列的实例中第二种候选模式出现的个 数的元素；

A-2、基于嵌入式马氏链模型，分别计算出不确定时间序列中每一实例出现 之后，当前不确定时间序列的实例中分别包括个第二种候选模式的实例出 现的概率，从而列出该状态编码向量对应的概率矩阵；

A-3、从时间点t1开始，根据公式计算出第二种候 选模式出现次数X大于不确定频繁模式的次数阈值的概率其中P_ti(X _α＝u)表示不确定时间序列中以ti为结束时间点的实例出现之后，当前不确定时 间序列的实例中包含有u个第二种候选模式的实例出现的概率；

A-4、将该概率与不确定频繁模式的概率阈值η进行比较：在 时判定该第二候选模式为不确定频繁模式。

所述步骤S4中采用状态空间压缩编码技术与模糊动态规划技术相结合的方 式，计算第二种候选模式大于次数阈值的概率的过程由 以下步骤组成：

B-1、基于模糊动态规划技术，根据公式 计算出在t_i时刻，第二种候选 模式在不确定时间序列的子序列[t_i，t_n]内的模糊概率，其中第u个实例Occ_u在t_i个 时刻开始，P_u为Occ_u的独立存在概率，P′_u为Occ_u的模糊存在概率，表示在t_i-1时刻，不确定时间序列所包含的实例数量不少于j-1的概率上限， 表示在t_i-1时刻，不确定时间序列所包含的实例数量不少于j的概率上 限；

B-2、基于状态空间压缩编码技术，将不确定时间序列的实例分别由状态编 码向量v表示，其中该状态编码向量中包含用于表示对应不确定时间序列的实 例中第二种候选模式出现的个数的元素；

基于嵌入式马氏链模型，分别计算出不确定时间序列中每一实例出现之后， 当前不确定时间序列的实例中分别包括个第二种候选模式的实例出现的概 率，从而列出该状态编码向量对应的概率矩阵，在该概率矩阵中由P_ti(X_α＝u)表 示不确定时间序列中以ti为开始时间点的实例出现之后，当前不确定时间序列 的实例中包含有u个第二种候选模式的实例出现的概率；

B-3、根据公式计算概率的上限值如果则确定该第二种候选模式不是不确定频繁模 式，否则表示该第二种候选模式可能是不确定频繁模式，转入步骤B-4，其中 表示第二种候选模式在不确定时间序列的子序列[t_i，t_n]内模糊概率的 累计值，X=u且u≥j；

B-4、从时间点t1开始，根据公式计算出第二种候 选模式出现次数X大于不确定频繁模式的次数阈值的概率

B-5、将该概率与不确定频繁模式的概率阈值η进行比较：在 时判定该第二候选模式为不确定频繁模式。

综上所述，由于采用了上述技术方案，本发明的有益效果是：

1、本发明不仅考虑了频繁出现的子序列的出现次数，还考虑了子序列出现 的概率，可以精确确定不确定时间序列中不确定频繁模式，此外，针对候选模 式的不同类型，采用不同的处理技术来确定不确定频繁模式，采用状态空间压 缩编码技术提高了计算效率；

2、采用状态空间压缩编码技术与模糊动态规划技术相结合的方式，进一步 提高了计算效率；

3、采用“前缀+频繁项”的模式，长度为N的候选模式=长度为N-1的候选模 式+长度为1的频繁项，由此依次确定各候选模式对应的有效实例，提高了有 效实例的确定效率，确定了有效实施例的相互关系。

本发明的附加方面和优点将在下面的描述中部分给出，部分将从下面的描 述中变得明显，或通过本发明的实践了解到。

附图说明

本发明的上述和/或附加的方面和优点从结合下面附图对实施例的描述中将 变得明显和容易理解，其中：

图1是第一不确定时间序列的示意图；

图2是第一不确定时间序列的原子模型示意图；

图3是第二不确定时间序列的示意图；

图4是第二不确定时间序列的集合模型示意图；

图5是第三不确定时间序列的示意图；

图6是第三不确定时间序列的实例示意图；

图7是本发明的流程图；

图8是第二种候选模式在不确定时间序列中可能出现的位置分布图。

具体实施方式

下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自 始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元 件。下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，而不能 理解为对本发明的限制。

在本发明的描述中，除非另有规定和限定，需要说明的是，术语“安装”、“相 连”、“连接”应做广义理解，例如，可以是机械连接或电连接，也可以是两个元 件内部的连通，可以是直接相连，也可以通过中间媒介间接相连，对于本领域 的普通技术人员而言，可以根据具体情况理解上述术语的具体含义。

如图1所示，该不确定时间序列中TagID表示监测的目标，A、B和C表示 目标所处的位置(即事件)，t1、t2、t3和t4表示不同的时间点，每一位置后的 数值表示传感器监测到该目标TagID在该位置出现的概率。例如， {(A.0.6)(B.0.4).t₁}表示在t1时间，目标TagID在A、B两个位置出现的概率分别 为0.6和0.4。

由于提取不确定时间序列中频繁出现的子序列，不仅需要考虑子序列出现 的次数，还需要考虑子序列出现的概率，因此设定X为子序列的出现次数，P() 为概率函数，为次数阈值且η为概率阈值，如果子序列的出现次数X大于的概率大于η(即)则将该子序列称为不确定频繁模式。

本发明定义了不确定时间序列的原子模型、集合模型、实例、最小出现模 式和非重叠出现模式，并且将不确定时间序列中模式定义为不确定时间序列的 子序列。

不确定时间序列的原子模型是指在某个时间只出现一个符号(即在某个时 间目标只出现在一个位置)，且出现概率之和小于1。第一不确定时间序列如图 1所示，第一不确定时间序列的原子模型如图2所示，诸如在pw1中t1、t2、 t3和t4时间下目标所处的位置分别为A、A、B和C，由此可见在t1、t2、t3 和t4时间下目标均只出现在一个位置。

不确定时间序列的集合模型是指在某个时间可以出现多个符号(即在某个 时间目标可以出现在多个位置处)，且各符号(位置)之间相互独立，出现概率 之和可以大于1。第二不确定时间序列如图3所示，第二不确定时间序列的集合 模型如图4所示，诸如在pw3中t1时间下目标所处的位置为A，t2时间下目标 所处的位置为A和B，t3时间下目标所处的位置为B，t4时间下目标所处的位 置为C，由此可见在t2时间下目标可以出现在多个位置处。

实例是指不确定时间序列中所有可能存在组合的一种，图2和图4分别给 出了图1、图2中不确定时间序列的所有实例。由于不确定频繁模式实质上是一 个不确定子时间序列，因此，一个不确定频繁模式也与多个实例相对应，一般 用频繁模式的实例所在的时间间隔表示一个实例。针对不确定时间序列，图6 是图5所示第三不确定时间序列的两个实例，其包含了时间t1～t9下事件的组 合；以图6中第二个实例为例，针对模式A->B，包含了事件A和B，其中包含 有事件A的时间有t1、t3、t6和t7，包含有事件B的时间有t4，同时包含事件 A和B的时间有t2和t8，则该模式A->B的实例包括(t1，t2)，(t1，t4)，(t2，t4)，(t3， t4)，(t6，t8)，(t7，t8)等。

在不确定时间序列的任何一个实例中，若模式为最小出现模式，则该模式 对应的有效实例是指不包括该模式在不确定时间序列的所有实例中不包括其他 实例的实例。以图6中第二实例S2为例，如果A->B为最小出现模式，则其对 应的实例之间不相互包含，由于模式A->B的实例(t1，t2)，(t1，t4)，(t2，t4)，(t3， t4)，(t6，t8)，(t7，t8)中(t1，t4)和(t2，t4)均包含有实例(t1，t2)，实例(t6，t8)包含有(t7， t8)，因此最小出现模式A->B的有效实例包括(t1，t2)，(t3，t4)和(t7，t8)。

在不确定时间序列的任何一个实例中，若模式为非重叠出现模式，则该模 式对应的有效实例是指该模式在不确定时间序列的所有实例中不相互重叠的实 例。以图6中第二实例S2为例，如果A->B为非重叠出现模式，则其对应的实 例之间不相互重叠，由于模式A->B的实例(t1，t2)，(t1，t4)，(t2，t4)，(t3，t4)，(t6， t8)，(t7，t8)中(t1，t2)分别与(t1，t4)、(t2，t4)重叠，(t6，t8)与(t7，t8)重叠，因此非重 叠出现模式A->B的有效实例包括(t1，t2)，(t3，t4)，(t6，t8)。

如图7所示，该不确定时间序列中不确定频繁模式的确定方法中：

步骤一、确定不确定频繁模式的类型并设置出现次数阈值和概率阈值η， 其中该不确定频繁模式的类型包括最小出现模式和非重叠出现模式，且为正 整数，η为[0，1]之间的小数。

步骤二、根据不确定频繁模式的类型，计算各候选模式在不确定时间序列 中所有可能的有效实例：若候选模式为最小出现模式，则该候选模式对应的有 效实例是指该候选模式在不确定时间序列的所有实例中不包括其他实例的实 例，若候选模式为非重叠出现模式，则该候选模式对应的有效实例是指该候选 模式在不确定时间序列的所有实例中不相互重叠的实例；

确定各候选模式的类型：如果候选模式对应的任意两个有效实例可以相互 独立出现在不确定时间序列中则确定该候选模式为第一种候选模式；否则确定 该候选模式为第二种候选模式。

在本发明的第一实施例中，采用“前缀+频繁项”的模式，长度为N的候选模 式=长度为N-1的候选模式+长度为1的频繁项，由此依次确定各候选模式对应 的有效实例。具体的步骤为：设定与该候选模式对应的长度为N的前缀有效实 例prefix₁和长度为1的频繁项freqItem，将不确定时间序列中前缀实例prefix₁之后的时间序列作为投影序列Seq_l=[startPos，endPos]＝[i，n]，其中[startPos， endPos]表示投影序列的时间区间；

遍历投影序列Seq_l中每一时间可能出现的事件，如果频繁项freqItem出现 在投影序列Seq_l的时间区间[startPos，endPos]内，则由投影序列Seq_l的前缀实例 prefix_l和频繁项freqItem生成长度为N+1的新前缀有效实例prefix_l’ ＝prefix_l+freqItem。

步骤三、针对第一种候选模式，采用动态规划技术计算第一种候选模式出 现次数X大于次数阈值a的概率并且在时判定该第一种候选模式为不确定频繁模式。由于动态规划技术为本领域普通 技术人员公知技术，因而在此不予累述。

步骤四、针对第二种候选模式，采用状态空间压缩编码技术计算第二种候 选模式出现次数X大于次数阈值a的概率并且在时判定该第二种候选模式为不确定频繁模式。

在本发明的第一实施例中，如图5～6所示，不确定时间序列包括9个时间， 设定由三个元素组成的模式A->B->C为第二种候选模式(以非重叠出现模式为 例)，则对该模式A->B->C进行状态编码，如下图所示，模式A->B->C的状态 编码为3，A->B的状态编码为2，A的状态编码为1，无元素出现时状态编码为 0。

  状态编码   元素   0   未出现   1   A   2   A->B   3   A->B->C

以图5所示不确定时间序列为例，模式A->B->C若为非重叠频繁模式，则 其在不确定时间序列中可能出现的有效实例有两个，分别为t1->t2->t3， t6->t8->t9，因此采用长度为2的向量v=(v1，v2)来表示不确定时间序列的实 例包含模式A->B->C的情况。诸如针对图6所示的不确定时间序列的实例S1， 在有效实例t1->t2->t3和t6->t8->t9对应时间下均包含模式A->B->C，因此v1 和v2的取值均为3，采用向量v=(3，3)来表示不确定时间序列的实例S1包 含模式A->B->C的情况；针对图6所示的不确定时间序列的实例S2，在有效实 例t1->t2->t3对应时间下包含模式A->B->C，在有效实例t6->t8->t9对应时间下 仅包含A，因此v1的取值为3，v2的取值为1，采用向量v=(3，1)来表示不 确定时间序列的实例S2包含模式A->B->C的情况。

以图5所示不确定时间序列中实例S1的子序列[t₁，t₅]为例，子序列[t₁，t₅]在有 效实例t1->t2->t3对应时间下包含模式A->B->C，在有效实例t6->t8->t9对应时 间下模式A->B->C中三个元素均未出现，因此v1’的取值为3，v2’的取值为0， 采用向量v₁(t₁，t₅)=<3，0>来表示子序列[t₁，t₅]包含模式A->B->C的情况。

利用上述编码方案，计算候选模式在不确定时间序列中出现概率时，可以 极大压缩需要考虑的不确定时间序列的实例数量。例如，图6所示不确定时间 序列中实例S1的子序列[t₁，t₅]对应于32个实例，当计算模式A->B->C在这些实 例中出现的概率时，可以将这些实例压缩为四个状态编码向量：v₁₀＝<0，0>， v₁₁＝<1，0>，v₁₂＝<2，0>，v₁₃＝<3，0>。

由于在计算第二种候选模式的累计概率时仅关心候选模式是否在 时间序列中出现以及出现的个数，因此上述实例可以进一步压缩为两个状态编 码向量m₁₀＝(0，<0，0>)，m₁₁＝(1，<0，0>)，其中m₁₀对应v₁₀，v₁₁，v₁₂(不存在候选模式)， m₁₁对应v₁₃(存在一个候选模式)。

在状态编码的支持下，基于嵌入马氏模型(Embedded Markov Chain：EMC) 可以计算出概率P(X>a)。图8表示了第二种候选模式在不确定时间序列中可能 出现的位置分布，表示第个出现的实例，与图8对应，在不确定时间序 列的各子序列中第二种候选模式出现次数的概率分布如下表所示：

其中列表示第个出现的实例，行u对应于每一实例出现之后，当前不确 定时间序列中包含有u个第二种候选模式的实例，矩阵元素即表 示第个实例(以tj为结束时间点)出现之后，当前不确定时间序列的实例中包 含有u个第二种候选模式的实例出现概率。

综上所述，采用状态空间压缩编码技术计算概率从而判断该第二 种候选模式是否为不确定频繁模式的过程具体由以下步骤组成：

第一步、将不确定时间序列的实例分别由状态编码向量v表示，其中该状 态编码向量中包含用于表示对应不确定时间序列的实例中第二种候选模式出现 的个数的元素。

第二步、基于嵌入式马氏链模型，分别计算出不确定时间序列中每一实例 出现之后，当前不确定时间序列的实例中分别包括个第二种候选模式的实 例出现的概率，从而列出该状态编码向量对应的概率矩阵。

第三步、从时间点t1开始，根据公式计算出第二种 候选模式出现次数X大于不确定频繁模式的次数阈值的概率其中 P_ti(X_α＝u)表示不确定时间序列中以ti为结束时间点的实例出现之后，当前不确 定时间序列的实例中包含有u个第二种候选模式的实例出现的概率。

第四步、将该概率与不确定频繁模式的概率阈值η进行比较：在 时判定该第二候选模式为不确定频繁模式。

为了进一步提高计算效率，针对第二种候选模式，还可以采用状态空间压 缩编码技术与模糊动态规划技术相结合的方式，判断该第二种候选模式是否为 不确定频繁模式。

在本发明的第二实施例中，如图6～7所示，如果模式A->B->A为最小出现 模式，则该模式在图7所示不确定时间序列中的两个有效实例Occ1=(t1->t2->3) 和Occ2=(t3->t4->t6)相互关联(在t3时刻重叠)。

以上两个实例分别独立存在的概率为和 然而当Occ1已经出现时，Occ2出现的概率为很显然P＇₂≥P₂。我们将P＇₂称为Occ2的模糊存在概率，之所以称为模糊，是因为 如果Occ1不存在，Occ2则不能以P＇₂概率存在于时间序列中。

由于已知第二种候选模式在不确定时间序列中的所有实例，因此可以直接 求出每个实例的独立存在概率和模糊存在概率。模糊动态规划可以得到的上限，如下表所示：

综上所述，采用状态空间压缩编码技术与模糊动态规划技术相结合的方式， 判断该第二种候选模式是否为不确定频繁模式的过程由以下步骤组成：

第一步、基于模糊动态规划技术，根据公式 计算出在t_i时刻，第二种候选 模式在不确定时间序列的子序列[t_i，t_n]内的模糊概率，其中第u个实例Occ_u在t_i个 时刻开始，P_u为Occ_u的独立存在概率，P′_u为Occ_u的模糊存在概率，表示在t_i-1时刻，不确定时间序列所包含的实例数量不少于j-1的概率上限， 表示在t_i-1时刻，不确定时间序列所包含的实例数量不少于j的概率上 限。

第二步、基于状态空间压缩编码技术，将不确定时间序列的实例分别由状 态编码向量v表示，其中该状态编码向量中包含用于表示对应不确定时间序列 的实例中第二种候选模式出现的个数的元素；

基于嵌入式马氏链模型，分别计算出不确定时间序列中每一实例出现之后， 当前不确定时间序列的实例中分别包括个第二种候选模式的实例出现的概 率，从而列出该状态编码向量对应的概率矩阵，在该概率矩阵中由P_ti(X_α＝u)表 示不确定时间序列中以ti为开始时间点的实例出现之后，当前不确定时间序列 的实例中包含有u个第二种候选模式的实例出现的概率。

第三步、在根据公式计算概率 的上限值从最后一个实例结束的时间t_n开始，从后向前反向 扫描不确定时间序列，直到第一个实例出现的时间结束：如果则确 定该第二种候选模式不是不确定频繁模式，否则表示该第二种候选模式可能是 不确定频繁模式，转入步骤第四步，其中表示第二种候选模式在不确 定时间序列的子序列[t_i，t_n]内模糊概率的累计值，X=u且u≥j。

从公式可以看出，模糊动态规划 采用的是分而治之的策略，将分解为两种情况：一种是第u个实例出 现并且t_i-1时间之前存在的实例个数不少于j-1；另一种是第u个实例不出现并且 t_i-1时间之前存在的实例个数不少于j。因为在计算 之前已经得到，所以可以通过查询上述表格中矩阵元素获得。

第四步、从时间点t1开始，根据公式计算出第二种 候选模式出现次数X大于不确定频繁模式的次数阈值的概率

第五步、将该概率与不确定频繁模式的概率阈值η进行比较：在 时判定该第二候选模式为不确定频繁模式。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具 体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结 构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中， 对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描述的具 体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适 的方式结合。

尽管已经示出和描述了本发明的实施例，本领域的普通技术人员可以理解： 在不脱离本发明的原理和宗旨的情况下可以对这些实施例进行多种变化、修改、 替换和变型，本发明的范围由权利要求及其等同物限定。