文摘

找到灵活的周期模式在时间序列数据库中重要的是由于不规则发生的重要事件,这使得它棘手或计算密集型的大型数据集。基于先验的存在各种解决方案,投影,树,和其他技术开采这些模式。然而,常数大小树结构的存在,即,suffix tree, with extra information in memory throughout the mining process, redundant and invalid pattern generation, limited types of mined flexible periodic patterns, and repeated traversal over tree data structure for pattern discovery, results in unacceptable space and time complexity. In order to overcome these issues, we introduce an efficient approach called HOVA-FPPM based on Apriori approach with hashed occurrence vectors to find all types of flexible periodic patterns. We do not rely on complex tree structure rather manage necessary information in a hash table for efficient lookup during the mining process. We measured the performance of our proposed approach and compared the results with the baseline approach, i.e., FPPM. The results show that our approach requires lesser time and space, regardless of the data size or period value.

1。介绍

数据挖掘可以让我们发现有用的信息从数据,否则是很难发现的。数据挖掘的过程涉及到各种任务,包括分类、聚类,挖掘模式,和其他几个人1]。模式挖掘是数据挖掘的一个分支,它集中在一个给定的数据集内发现有用的模式(2]。它发现一项或一组物品出现超过某个阈值设定的用户。一个典型的例子会经常一起买了物品的模式。是常见的企业存储事务,包含类型和名称的项目,在他们的数据库中。这些交易的数据用于矿山经常一起买了物品的模式(3]。传统上,这些模式帮助商店在决定哪些物品是一起为客户要求的地方。

时间序列数据集是常见的这些日子里,有一些应用程序的领域,比如经济学、社会科学、流行病学、医学、物理科学,例如,测量一个人的心率每分钟后,读数的空气温度或风力每小时后,股票利率中期和结束每一天,等等。从时间序列数据挖掘模式通常被称为周期模式挖掘(4- - - - - -7]。周期模式挖掘过程中通常归类为象征,序列(部分),和完整的周期模式(段)8- - - - - -11]。象征周期性发生在只有一个事件,重新出现在特定时间后的时间序列。序列周期性复发的多个符号在特定的时期。完整的周期性重复的数据是在一个给定的时期。最近,研究重点已转向灵活的周期模式挖掘(9,12- - - - - -15]。灵活的模式挖掘背后的想法是发现一组不一定一起出现的事件,但这些事件伴随着定期随机事件在他们之间,即。,{事件_小鬼、事件_unimp、事件_小鬼、事件_小鬼}。灵活性指的存在不规则之间发生的重要事件频繁发生的事件在不同的时间段。让我们考虑银行交易的例子(12表示为{一个,b,c,d}在数百万金额为0 - 5、5 - 10 - 15,分别和≥15。给定一组事务{abd,accd,广告,abbccd}和经理感兴趣的事务有较低的分析模式一个和更高的d金额。我们观察到没有确切数字之间的事务类型一个和d。这种情况下可以正式表示为一个{}d,在那里^{0 0}显示的灵活性选项的数量(事务类型)在采矿和考虑我们认为这是一个灵活的模式挖掘问题。

使用后缀树(前缀单词查找树或单词查找树)中数据结构普遍最先进的方法对灵活的周期模式挖掘。拉希德et al。9]构造后缀树从时间序列数据到我的灵活的周期模式。同样,钱德et al。12]介绍了一种改进的基于后缀树的数据结构的方法。存在内存中的线性时间算法构造后缀树(16和修剪策略建议12];然而,重复遍历在这样一个树结构使得整个挖掘过程计算密集型的。我们看到各种冗余(不必要的)模式保存大量的时间,整个挖掘过程和树的大小保持不变。在我们的理解,更好的策略是需要时间和空间效率的同时保持必要的信息和生产相同的模式。

在本文中,我们引入一个有效的策略基于散列发生向量和先验的方法,它不依赖于后缀树的数据结构(9,12在哈希表),而有效的查找,我从时间序列数据周期模式不妥协的结果。我们的方法包括时间序列数据的离散化,周期性检测和模式挖掘模块。我们保持独特的可变长周期模式及其发生向量作为一个哈希表键值对,其中键表示模式和发生向量存储作为相应的值。我们使用离散事件的向量来计算算术上出现周期性的基础模式。拟议的周期性检测算法与现有的算法不同的去除冗余矢量值和计算周期性发生的模式在同一水平在一个通过。我们裁缝增量模式挖掘过程在哈希表中使用发生了向量的现有模式,探索新的模式和更新一次哈希表模式发现在每个级别。我们工作的贡献如下。(我)我们建议HOVA-FPPM简化灵活的周期模式挖掘过程通过一个有效的键-值对数据结构。(2)我们保持必要的信息(模式及其发生向量)和计算效率(通过基本的算术发生向量,减少冗余和无效的模式)显著提高时间和空间复杂性的方法。(3)我们的方法需要单程发现象征,部分和完整的周期模式在任何周期性水平。(iv)真实数据集和基线算法综合性能分析显示我们的方法的运行时间效率和空间效率,同时保持相同的精度。

剩下的纸是组织如下。其次是预赛部分的讨论相关工作。拟议的方法讨论了算法的详细解释。随后,我们大纲提出的方法的实验分析与基线相比在真实数据集的方法。我们还提供一个详细的讨论。最后,我们得出结论本文及其未来的发展方向。

2。文献综述

在本节中,我们简要讨论各种方法的上下文中周期性开采,采矿领域的模式。模式挖掘还有其他分支学科根据开采模式的类型,如频繁项集(3),序列模式(8,11,17,18)、高实用程序模式(19- - - - - -22),周期模式(23- - - - - -25),以及灵活的周期模式(9,12,26]。钱德et al。12)最近提出的一种算法,在时间序列中发现灵活的周期模式通过使用后缀树的数据结构。在他们的方法中,他们首先做了一个后缀树的时间序列,然后使用后缀树和我不同长度的模式。

在一个广泛的文献回顾周期模式挖掘算法,我们注意到,所有这些算法可以根据他们使用的方法是分类的算法解决方案(指频繁模式挖掘的分类图1)。例如,一些算法使用先验的方法来查找模式越来越长,而其他人使用一个树状结构,以避免内存需求和挖掘模式。每种方法都有自己的优缺点。因此,而不是分类算法基于模式他们挖掘的类型,我们将它们分组基于他们的基本方法。关键方法是先验的,树为基础,基于投影等等。另一类包含算法遵循一种常见的方法。

2.1。Apriori-Based方法

早期作品基于先验的方法无法我的所有类型的模式。然而,一些重要的特性,介绍了单调和anti-monotone,后来,帮助提高挖掘算法的性能(17,18]。最新的算法能够检测所有类型的灵活的周期模式提出了由Nishi et al。19]。算法使用Apriori-based方法我使用发生向量所有有效的模式。算法由矿业特色长度模式然后搬到两个模式等等。插入”的发现模式是灵活的”作为特殊字符。按照作者的说法,他们的算法能够找到一些有趣的模式是不可能与先前的算法。他们还声称,它发现所有类型的周期模式;然而,矿业战略是需要大量的计算,因为生成大量的过度模式。

2.2。基于树的方法

许多研究人员利用中的一个重要概念称为“封闭模式”的背景下,周期模式挖掘,减少了搜索空间对矿业冗余模式(20.,21,23]。大多数这些算法涉及的使用树结构进行模式挖掘,最终减少了时间和空间的复杂性减少数量的模式树的大小减少。研究趋势转向挖掘不同类型的模式被称为高实用程序模式(24- - - - - -26]。拉希德et al。9)提出了一个算法,发现灵活的周期模式在时间序列数据库中使用后缀树。在这种方法中,后缀树的创建时间序列数据,然后使用各种长度的开采模式。虽然作者使用一个技术生成模式逐步从一个长度模式两种模式等等,与其他算法不同,他们没有完全遵循先验的方法使过度和所有可能的组合。后缀树的组合允许他们出现在后缀树的事件。他们的方法是模式的另一个区别方面没有做出灵活的过程,相反,它不断将重要事件符号与每一个连续开采模式希望成为一个模式树的深度。最近,钱德et al。12]介绍了另一个有效的方法在同一方向灵活模式挖掘使用修剪后缀树。

2.3。Projection-Based技术

在这个范畴,与其他方法不同的是,研究人员使用投影数据库挖掘的模式与多个修剪技术。他们引入了灵活的周期模式挖掘的概念在关闭模式挖掘的领域(14,27]。例如,Akther et al。14)提出了一个算法来挖掘关闭灵活的模式,这是一个改进之前提交论文灵活的封闭模式(27]。有一些其他作品上发现封闭的模式使用投影数据库和树结构28- - - - - -30.]。

2.4。其他方法

有其他方法在文学模式挖掘,包括动态时间扭曲(31日),信息增益(32),和操纵位图表示的数据33,34]。动态时间规整算法(31日)用矩阵经插入或删除的时间维度的数据噪音。经算法不能够检测所有类型的周期模式;然而,处理噪声数据使其突出的其他方法。在另一个工作,作者提出了一个扩展的版本信息增益测量(32检测周期。它侧重于灵活模式挖掘与差距惩罚,但它只工作了象征和部分周期模式。另一项研究[35)检测部分周期模式,目的是消除需要知道开采前的时间长度。艾尔斯等人,Lucchese et al。33,34]在长序列模式挖掘。数据表示位图的深度优先搜索策略用于我的长序列模式。

很明显从上面的讨论,现有方法使用复杂的数据结构模式挖掘过程或产生过度冗余或无效的模式。例如,在Apriori-based方法,过度的一代的冗余的或无效的模式可以减少时间和空间效率。过度的影响模式生成树,projection-based方法导致复杂的树形结构,进而增加内存使用以及遍历的次数。与一个有效的方法模式生成策略和高效的重复遍历数据有可能克服上述现有研究的局限性。

2.5。预赛

在本节中,我们解释了现有的术语来理解问题及其解决方案。

定义1。(周期性)。在一个时间序列T,T= {一个₀,一个₁,一个₂,一个₃、……_n},n事件,发现多少次事件重新出现在指定的时间内被称为周期性的事件。
例如,在时间序列T= {abdbc abdba abdac acdca}基于日常活动安排在办公室个人工作,如图2、事件”一个“5个周期的价值。这意味着如果T分为5块长度。”一个“总是出现在同一个地方在这些碎片。换句话说,总是会有四个事件在两个事件之间的“一个”。然而,如果我们观察周期值3和分裂T块长度3。”一个“不会被认为是周期性的,因为“一个每两个事件”后没有出现。

定义2。(完美的周期性)。在一个时间序列T,T= {一个₀,一个₁,一个₂,一个₃、…一个_n},n事件,一个事件重复性在指定的时间内,整个时间序列被称为完美的周期性。
完美的周期性用PP和定义如下: 例如,在时间序列T= {abdbc abdba abdac acdca},PP(5 0 19日”abd”)= 结果在4,意思是“abd“必须在时间序列中出现4次为了拥有完美的周期性。然而,它有一个实际的3的周期性数据。

定义3。(周期模式)。当一个模式在一个特定时期内反复发生的时间和满足阈值的支持,我们称之为周期模式。
例如,在时间序列T= {abdbc abdba abdac acdca},模式”abd”是周期的支持3值5当阈值支持值是3。简而言之,事件或一系列事件将被视为一个周期模式是否满足给定的最小支持度阈值的时间价值。这个不应被混淆的支持措施。例如,考虑事件”ca”的时间序列T。如果我们观察的事件T我们注意到,“ca”共3次,这意味着它满足阈值考虑整个时间序列的支持。然而,“ca如果我们看看“只出现一次T与一段时间的价值5如果我们从索引0开始T。

定义4。(灵活的周期模式(FPP))。任何周期模式,它包含“不在乎”事件被称为灵活的周期模式。
例如,在时间序列T= {abdbc abdba abdac acdca},模式”一个 d”是一个周期模式支持下4和5价值。这意味着事件”一个“和事件”d”发生后每4值和它们之间的一个随机事件。我灵活的周期模式很难通过规律挖掘方法由于出现的重要事件。

定义5。(发生向量)。发生一个向量是一个列表代表一个独特的元素的索引位置(事件)的数据。每一个独特的元素(事件)发生有一个向量。
例如,在时间序列T= {abdbc abdba abdac acdca},发生向量的元素”一个”是[0、5、9、10、13、15、19),代表的索引位置出现的事件”一个“在T。

定义6。(差分向量)。一双发生的向量,向量生成模式的区别及其频率计数。
不同向量的目标是获得一个模式及其频率。是计算比较第一次出现向量的每个值和第二次发生的每一个值向量。对于一个给定的事务在图3,模式ab发生三次。产生这种模式,我们需要计算的差别一个−b出现的,它提供了我们三个值−1图4在一个表题为“差异。“同样,模式一个 b出现了两次;因此,我们发现−5两倍的价值。向量可以积极或消极的区别。一个负值表示一个元素出现在另一个元素,即,一个出现在b而计算的区别一个−b。一个积极的价值差异表示说一个出现后b。

定义7。(信心)。模式的信心是比实际的周期性和完美的周期性,见以下方程: 例如,在时间序列T= {abdbc abdba abdac acdca},完美的周期性的模式”abd“是4和实际的周期是3。因此,这种模式的信心是75%,即。、自信(5 0”abd”)= 3/4。

3所示。HOVA-FPPM:散列发生向量和先验的方法灵活的周期模式挖掘

HOVA-FPPM的目的是为了克服现有方法的局限性,通过消除复杂的数据结构,比如后缀树的需要,通过Apriori-like方法在发生向量中维护一个哈希表我灵活的周期模式。它帮助我们不仅减少空间需求,也为了避免临时模式调用有限的周期性检测模块,最终降低了整体采矿过程的时间要求。在以下章节中,我们讨论我们的策略的组件和算法进行模式挖掘。

3.1。组件HOVA-FPPM策略

所涉及的关键部件我们建议的方法是离散化的,事件的查找表结构,周期性检测和模式挖掘如图5。

3.1.1。离散化

离散化过程将从数据系列每个独特的元素转换为一个简化的唯一元素。离散化过程的唯一目的是让模式挖掘的过程更容易,因为它是容易处理的一系列数据具有独特的人物比使用一系列字母数字产品id。例如,如果我们有一个数据系列t= {asyt2345、kgjhu6789 enhy4521, enhy4521}包含产品id,然后离散化使我们的输入t= {一个,b,c,c}。一旦我们执行在实际时间序列数据离散化,然后它会产生相同的数据的简化表示。

3.1.2。事件表结构

事件表包含所有独特的事件及其发生向量。发生向量具有重要意义,因为他们持有每一个独特的元素的索引位置的输入数据。他们是更重要的,因为我们的算法在很大程度上依赖于发生向量。每个输入数据都有自己的独特的元素发生向量。发生向量中的值是该元素的索引位置位于输入数据。例如,如果我们有一个输入数据t= {abcdabddabccabdc},然后发生向量一个= (0、4、8、12),b= (1、5、9、13),c= (2、10、11、15)d= (3、6、7、14)。扫描输入数据时发生向量计算一次。在扫描过程中,当我们找到一个元素事件表中不存在,那么我们将它添加到我们的hashing-based事件表并分配相应的列表。如果事件表中的元素已经存在,那么我们将当前索引位置添加到其发生向量。

3.1.3。周期性的检测

一旦我们经历了输入数据,我们应该发生在数据向量的所有元素。现在我们计算每个元素的周期性通过向量元素及其发生周期性检测算法。我们周期性检测算法与FPPM相比略有修改的12周期性检测算法。最初的周期性检测算法经过特定事件的发生向量n次了。然后让另一个迭代n−1 *和比较所有的值n−1的值发生向量检查他们的周期性。最后,发生向量的周期性检测算法返回一个列表的时期的事件是周期性的,在每个起点都有单独的列表。例如,输出的周期性检测算法一个=(0、4、8、12)将起始位置0 =[0、4、8、12],[0,8],[0,12],起始位置4 =[4、8、12],[4,12],起始位置8 = (8、12)。我们可以看到,发生向量[0、4、8、12]位置0开始和发生向量(4、8、12)起始位置4冗余,因为双方都指向同一个发生向量。采矿和返回等冗余矢量是不必要的,因为superperiodic发生煤矿发生suboccurrence向量在逐次迭代的下一个起点。我们不计算这种冗余向量修改发生周期性检测算法,而剩下的步骤仍然完好无损。

3.1.4。模式挖掘

我们提出战略的模式挖掘模块减少所需的时间,从而发现灵活的周期模式与其同行相比。采矿过程是基于先验的方法,涉及到基本的算术运算中出现向量,即。,差异向量。发生向量以及事件管理有效地使用键值和固有的哈希策略提供快速查找时间效率。模式枚举一步是引导通过独特的事件和极性差别向量的值,而频率帮助决定是否频繁模式给定阈值。

3.2。插图HOVA-FPPM的一个例子

我们说明我们的过程模式挖掘算法的帮助下一个玩具的例子。对于这个例子,我们假设数据T= {abccabdcacdcabdc}50%的信心阈值和最大允许3无关紧要的事件。采矿过程的行为同样对所有数据集的大小。过程数据的说明3,4,6没有反映出完整模式和组合由于空间限制。离散化过程之后,我们的数据应该在上面给出的形式。

因为我们已经通过数据一次,离散化,我们有发生向量中的独特元素数据。独特的元素一个,b,c,d。所有这些独特的元素的出现向量可用,如图4。我们的采矿过程经过每个独特的元素及其发生向量开采模式。首先,我们考虑的元素一个其向量检查周期。它是周期时间的长度4和8;因此,我们认为这是一个长度开采模式。

两个长度模式,我们比较发生发生的一个长度开采模式向量的向量我们事件表中所有其他不同的元素。生成所有可能的模式涉及的元素ab,交流,广告,英航,ca,达。我们的算法的工作方式让我们我的模式从所有元素参与一次迭代,几乎一半的计算迭代。我们执行不同操作之间发生的向量元素,一个是开采模式一个其次是b,如图5。我们首先发生向量的值进行比较一个发生向量的元素的值b。我们重复这个过程的所有值出现的向量一个。因此,我们维持每个位置的差值的列表。

操作的区别揭示与频率相关的重要信息,位置,和发生的模式。在每个差别向量,我们有积极的和消极的价值观。因为我们的表现”一个−b”操作,负数给我们的位置之间的区别一个和b,而积极的之间的距离差值表示b和一个。例如,如果我们有4个值一个发生向量和我们的不同之处在于1的值b发生矢量,然后给我们3的区别。差值是正的,所以我们知道这是之间的距离b和一个。在这个特殊的例子中,b发生之前一个。

如果我们发现1正值4次差分向量通过不同的操作,我们可以得出这样的结论:b发生了4次一个距离为1。1的频率值4告诉我们这种模式的信心,距离1揭示了事件之间的距离b和一个和积极的迹象显示b发生之前一个实例。因此,从这个操作是开采模式英航频率的4。如果我们假设距离值为2,那么它的意思一个发生在距离2后的价值b,导致生成的模式b 一个。

重复上述过程连续所有模式从数据挖掘(参见图没有冗余和不必要的计算6三个长度模式)。我们得到单独的差别向量差分操作后,我们计算所有独特的数字检查的频率是否频繁模式。模式的方向是通过数字的极性决定的,也就是说,ab或英航模式。告诉我们有多少其他事件的区别两个事件之间。以来最大允许重要事件限制是3,任意数量大于3代不考虑模式。我们能够根据这些差别向量生成下一个层次模式。在当前的场景中,模式ab和b 一个与发生向量[0、4、12]和[1,5],分别是唯一的开采模式。重要的是要注意,我们并没有执行任何显式迭代模式有关b和一个因为我们已经开采这些模式。因此,当我们从我的模式b元素,我们不比较其发生向量一个元素,而与c元素。这个过程涉及相同并生成模式交流和ca。同样,在接下来的迭代中,我们所做的不是我的模式ca当你考虑c和一个元素。通过这种方式,我们能够减少计算特别是当我们有大量的独特元素。我们有一个哈希表类似于原来但包括可变长度模式及其发生向量。为下一个层次模式,我们把ab和b 一个模式及其发生向量计算向量的区别。剩下的过程是一样的,一个长度的元素(算法1)。

3.3。算法

在本节中,我们讨论我们的算法的细节(参见算法1)对矿业灵活的周期模式。这个算法的前提是数据的离散化,并执行最初为每个数据集的独特元素。需要一个独特的元素及其发生矢量,哈希表包含所有独特的元素,最大模式长度和前一键作为输入。前面的键引用列表,已经开采活动。保持这些信息是至关重要的,因为正如我们前面所讨论的,一旦我们从挖掘模式一个,我们希望逆模式。前面的键列表可以防止我们再次开采模式。其余的输入是自解释的。算法的输出是一个列表的开采模式。我们的算法所涉及的主要业务如下。(我)离散化的事件,通过时间序列数据和计算总出现,发生向量,和最大长度为整个时间序列模式。我们也对哈希值相同的通过。(2)找到的差异发生了向量的每一个独特的事件。(3)使两个长度对频繁对超过用户给定阈值的支持。(iv)添加重要象征对于每个模式的基础上出现的差异。(v)找到每个连续事件的发生差异向量。(vi)差异数最高的频繁的事件值被认为是连续的水平。(七)添加重要象征对于每个模式的基础上出现的差异。(八)下一个层次的重复模式。

在随后的段落中,我们解释我们的算法的步骤。在1号线,我们初始化一个空列表保存开采模式,和第2行生成一个事件,我们必须我的列表。第2行调用slice_events函数,采用哈希表和之前的键作为输入和切割前散列向量及其发生的关键。它帮助我们减少开采时间。重复构造线4 - 6扫描整个哈希表及其发生向量比较事件的发生。第7行计算的不同元素,8和9行执行一个检查值和最大模式长度的差异。在这个阶段,我们消除任何差异大于最大允许skippable无关紧要的事件。

因为我们希望不同模式不同的极性差异值,我们需要不同的模式名称使部分。我们执行的操作一个−b这意味着第二个元素在不同操作更大如果差异的结果是正的;因此,我们对10岁和23行执行检查。这些部分实现模式根据极性的差异值。第11行是一个检查和关键尺寸的差别。它是很重要的,因为我们所有的开采模式是由模式的第一个元素的索引。这意味着如果我们有一个模式美国广播公司,那么这种模式将有相同的起始位置一个元素。如果我们有和我4模式从这个长度,那么我们需要考虑当前元素的起始位置关键尺寸。在这种情况下,模式美国广播公司有一个关键尺寸3。任何元素,不是3步骤的起始位置之前,目前的模式将使其无效的模式,这是在第11行执行。第12行计算的差异从当前关键下一个关键的考虑和给我们星数,我们会添加我的这种模式。13和14行是一个简单的检查最大skippable事件,继续行动,分别。第15行调用一个函数,返回一个字符串,其中包含的恒星数量我们已经从第12行。线16新模式,和第17行插入发生矢量值。第18行保存新生成的模式的模式列表。行20−22但single-length事件执行相同的操作。线23−35类似于上面提到的这部分矿山相反的模式。36−38行发送新开采模式以及完整的哈希表下一个层次生成函数,它适用于长度超过2模式。 We did not check for periodicity of the newly generated patterns in this function yet. It is because we send these to the next level function, which automatically checks the periodicity itself. Once the patterns are mined and returned, the return list will have all the mined patterns related to the specific event that was passed on to our algorithm function. This whole process will be repeated for every individual unique element.

3.4。复杂性分析

我们讨论这两种方法的算法复杂度基于他们的关键步骤。基线的方法包括三个步骤,其中包括后缀树建设、周期性检查,对挖掘和模式生成。FPPM算法的作者声称修剪后缀树建设时间复杂度相同后缀树收缩,即,O(n),n时间序列的大小。周期性检测依赖于发生周期模式的矢量和长度,也就是说,O(k n^ 2),k的最大长度是周期模式和n是时间序列的大小。模式一代涉及levelwise修剪后缀树的遍历扎根在相应的事件。的平均深度遍历是由梯子因素为每个节点计算开采前一步。的整体复杂性模式生成步骤是对数棵子树中的节点的数量在一个特定的事件,例如,O(米 日志(n)^ 2),n子树的节点的数目吗米的子树的数量。

另一方面,该方法包括事件表的建设、周期性检测和模式挖掘。事件表结构扫描输入数据并生成事件发生与相应的向量,线性时间复杂度O(n)。周期性检测算法仍然是一样的基线方法那么这个模块的复杂性。然而,我们的方法在确定偏离周期性连续模式早期的迭代和避免它。整体复杂性是一样的基线方法同时最小化的总数计算。提出的方法有优势模式挖掘阶段,我们明确避免后缀树的遍历哈希键-值对的快速查找模式,即。从对数尺度不变的时间。我们过程可用的频繁模式集和他们发生向量生成模式下一个层次;因此,复杂性取决于总数的模式p发生和相关向量,例如,O(k h(p)^ 2),k模式和的长度吗h(p)代表哈希模式。我们没有引入一个新的离散化策略,这对这两种方法是相似的,所以我们忽略了它在我们的复杂性分析。

3.5。实验

在本节中,我们进行实验评估的效率,我们建议的方法对基线的方法,即。,FPPM。在实验分析,我们专注于两种算法的时间和空间效率(HOVA-FPPM和基线)不同时期价值和数据大小。因为我们使用相同的设置/参数(即。,confidence 60% and support 50% inspired from baseline approach) during our experiments, obtained results are justified as per our claim in this article to prove the superiority of the proposed approach. However, we understand that different values of these parameters will affect the mining results. For instance, increasing the support threshold will reduce the number of mined patterns. We assume that both algorithms produce the same results (no difference in result accuracy), rather, have different requirements for time and space during execution.

我们简要地讨论一下我们的实验中使用的数据集和描述结果随后讨论。

3.5.1。数据集和系统

在我们的实验中,我们使用两个数据集即糖尿病和自行车共享数据集。数据集都公开在伦敦大学学院机器学习库使用相同的名字。糖尿病数据集包含总共大约8000条记录。它包含记录相关的糖尿病患者和他们的健康结果。总共20独特的代码使用整个数据集来计算患者的健康。所有这些20码代表为病人测量。这些代码将一个值为每个病人以及病人的日期列代表时间历史记录。另一方面,自行车共享数据集有一个总记录17000(大约)小时的自行车共享和730条记录每天自行车一样,不过水平。系统的规范用于实验是一个i5 - 3320 m 2.6 GHz处理器与10 8 GB RAM和Windows操作系统。在Python中实现的算法。

3.6。基于时间和空间性能

我们分析该算法的性能基线的方法,即。FPPM,通过测量执行时间和内存空间使用。

3.6.1。基于不同的数据大小的性能

我们试图理解算法的性能方面与基线方法通过不同大小的数据。如果我们看看我们的算法(图的性能7),很明显,我们的算法优于FPPM在时间和空间的需求。值得注意的是,时差算法很重要比的空间差异。这是由于这一事实可以大大提高模式更多的数据的数量。的输出(开采模式)的两个算法是相同的。因为我们的算法不依赖于后缀树状数据结构,我们不需要分配的内存和数据存储在一个树。在我们的算法中,内存需求增加的模式。数据集在考虑并不大;因此,空间需求没有增长的算法。相比之下,几乎FPPM算法的内存需求增加线性增长的数据。

操作。基于不同期间的表现价值

现在我们看一下数据从不同的时间价值的角度来看(见图8)。这种分析有助于我们发现变化的周期值的影响,同时保持数据大小固定的算法。模式挖掘的数据来自所有起始位置。正如我们所看到的,我们提出的算法的时间性能明显优于FPPM。然而,空间需求开始忙FPPM在不同时期的价值观。这是因为,我们的算法随着时间而增长的空间需求与FPPM不同,办公空间的需求是固定的。

3.6.3。性能分析自行车共享数据集

我们还执行第二个实验数据集,即。,b我ke sharing dataset, which is comparatively bigger than the first one. It contains 17000 rows of data containing hourly updates of bike sharing information. We performed experiments on this dataset to understand the scalability aspect of both algorithms. Figure9描述了两种算法的时间性能最多6000行数据。该算法优于FPPM削减时间到几乎一半FPPM所需的方法。我们进行这些实验与之前相同的设置,即。,confidence 60% and period value was ≤6, and we only varied the data size.

空间分配给两种算法的结果是很有趣的在不同数据集的情况下,如图9。实验的设置是相同的自行车共享数据集。很明显,FPPM相当稳定的空间需求和增加缓慢的输入数据集的大小。然而,我们建议的方法有一个非常变量空间分配。同样值得注意的是,使用的空间FPPM不会改变,至少值得注意的是,在采矿过程中,使用的空间分配FPPM之初当后缀树生成算法。另一方面,数据显示在图9包含的最大空间分配给我们的算法在挖掘过程中。这是因为我们的算法在采矿过程中动态改变空间,通常取决于每个迭代模式的数量。这就解释了在开采过程中使用不稳定的空间,我们建议的方法。根据我们的观察,新模式生成的数量没有直接成正比的数据添加到输入数据集的新行。

4所示。讨论

我们的讨论围绕选择的相关问题。在这些问题中,我们旨在分析先验的方法的效果在灵活的周期模式生成不同起始位置来确定影响因素无效或冗余模式的生成和理解不同数据集之间的关系长度和结果的准确性。

4.1。先验的方法的效果在灵活的周期模式生成不同起始位置

为了分析推测的方法的影响,我们进行了两个具有不同属性的数据集和实验结果FPPM性能相比,这是一个基于树的方法灵活的周期模式挖掘。根据我们所知,没有其他算法的目的是我与变量起始位置,同时使用一个灵活的周期模式Apriori-based方法。我们已经讨论了,可以我的模式从事件的发生向量不使用一个树结构来简化过程。根据实验和分析的结果,我们得出的结论是,先验的方法更好,(i)开采模式的可用空间不是问题,(2)没有严格限制使用的空间。Apriori-based方法不断发生记忆向量和模式,可以根据数据和独特的元素波动的数据。

有突出的积极作用的先验的方法在矿山模式所需的时间,因为它缺乏树遍历过程。现有Apriori-based算法,能够挖掘灵活的周期模式,是昂贵的在时间和空间上的要求。我们克服的过度时间需求Apriori-based方法通过引入一个有效的算法来挖掘模式。我们实现这一目标通过调整算法利用模式的生成过程,可以从多个通过生成模式。因此,我们的算法是我能够ab和它的逆矩阵模式在一个通过。模式生成过程也依赖于发生向量生成必要的模式,这减少了冗余和无效的模式。

4.2。影响因素的生成无效的或冗余模式

为了确定影响因素的生成无效的或冗余模式,我们首先分析了后缀树FPPM及其影响的行为模式。我们实现这一目标通过运行FPPM不同数据规模和不同的独特的价值观。专注于后缀树的原因是FPPM采矿过程的工作方式。FPPM矿山模式级别,级别从根节点通过访问每个直系后代节点。我们使用数据集的不同规模和数量的惟一值的大小来改变后缀树分析对算法的性能和冗余模式。不同数据规模增加后缀树的深度,而大独特的元素总数增加了后缀树的宽度。后缀树的宽度对冗余模式一代没有显著的影响;然而,更多的冗余模式生成的数据长度的增加更多的树的深度。自FPPM拥有每个分支的冗余模式,冗余模式的成本高很多更深入的后缀树。另一方面,更为独特的价值观并不影响的性能冗余模式代因为FPPM使模式在短时间内记忆。 One of the possible reasons is that the shallow tree allows FPPM to switch to a newer branch and discard the previous nonfrequent patterns.

4.3。不同数据集的长度和结果的准确性

从我们的实验,很明显有一个不同的数据大小之间的关系和结果的准确性。获得的结果有33 - 50%精度达到较低的限制更大的数据集。它证明了算法生成大型模式基于最初生成模式。任何不匹配模式开始时导致的减少增加准确性。经过仔细观察,据透露,无与伦比的模式是由两种算法。任何无与伦比的模式在降低初始阶段的结果的准确性在连续的阶段。然而,在极少数情况下,在后期阶段生成的模式匹配。它表明,为了提高算法的准确性,在初始阶段生成的模式需要更多的关注。如果两种算法的初始模式是相似的,那么它将增加开采模式的准确性明显因为两种算法使用初始模式生成下一阶段模式。

5。结论和未来的发展方向

我们提出了一个有效的策略,即。,HOVA-FPPM, to mine flexible periodic patterns from time series database without using complex data structures. We identified the limitations of tree-based approaches and discovered various factors that cause the redundant or invalid pattern generation during the mining process. We surpassed those issues with the help of hashing-based data structure while minimizing the number of redundant and invalid patterns through manipulation of occurrence vectors. The proposed solution outperformed the baseline algorithm in terms of time needed to mine the same patterns. We empirically justified that Apriori-based approaches are effective for the mining process without excessive pattern generation. For small dataset, our algorithm is space efficient compared with the FPPM. On a larger dataset, the space requirement of our strategy fluctuates due to incremental growth of accumulated data in hash table in contrast to baseline approach. We aim to improve the space complexity of our proposed algorithm on vary large datasets as an extension to this work. The analysis of combining hashing strategy with tree-like structure is another aspect to discover in future.

数据可用性

本研究中使用的数据集可以自由下载伦敦大学机器学习库(糖尿病:https://archive.ics.uci.edu/ml/datasets/diabetes;自行车共享:https://archive.ics.uci.edu/ml/datasets/bike +分享+数据集)。然而,作者愿意共享数据集用于请求。

的利益冲突

作者宣称没有利益冲突有关的出版。

作者的贡献

MFJ只负责数据管理,软件开发,并初步报告。WN草稿准备处理,项目管理和资金收购。MFJ和KUK负责概念化的理念,方法,和正式的分析。WN KUK审查和编辑了手稿。

确认

这项研究部分由院长职大学伊斯兰研究Madinah(年)、沙特阿拉伯(Tamayuz-1计划1439 - 1440学年啊;研究项目数量:24/40)。