分布式空间数据共位模式挖掘：基于Map-Reduce的实验研究

沙特国王大学学报从分布式空间数据Sandipan Maiti R.B.V.Subramanyam印度瓦朗加尔理工学院计算机科学工程系阿提奇莱因福奥文章历史记录：2018年4月16日收到2018年7月5日修订2018年8月17日接受在线发售2018年8月19日保留字：空间数据协同定位模式Map-Reduce计算邻居关系决策系统A B S T R A C T空间数据集中的共位模式是指空间数据集中位置相近的不同对象的有趣集合。我们保持相似的对象在一个实体集，并保持没有两个对象在一个colocation模式属于一个实体集。位置邻近度是基于欧几里德距离度量的。然而，在事务数据集中挖掘模式的算法并不直接适用于空间数据集挖掘共址模式。传统的方法不适用于分布式时态数据，许多生成空间数据集的应用本质上是分布式的。在本文中，提出了一种基于Map-Reduce的方法来找到所有的co-location模式分布在节点上的空间数据集。该方法是一种模块化的方法，由四个算法组成。在第一种方法中的前三个算法，并提出了一个算法的动态数据集，本文包含了另一种方法的co-location模式集，也更新在增量的方式（而不是从头开始），每当发生某些变化的数据集。在更大的数据集上的实验结果也被提出。©2018作者制作和主办：Elsevier B.V.代表沙特国王大学这是一CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍空间数据集包含有关对象的信息。相似的对象可以被分组到一个实体集中。应用程序可能需要识别和推荐经常共处一地的对象的集合。一个人进入一个城市想要识别一个位置，该位置靠近他的工作场所并且具有其他设施，诸如住宿的旅馆、医疗的医院、娱乐的电影院、书店、购物中心、礼拜场所等。需要识别那些感兴趣的并且非常接近的对象，条件是没有两个对象属于相同的实体集。这些对象形成称为共址模式的模式。Huang et al.（2004），Shekhar and Huang（2001）提出了一种从空间数据中寻找同位模式的方法。该方法将空间数据集中存储在一个系统中，并将协同定位模式挖掘算法集中执行。相反，现在的自治系统正在收集空间数据（Xindong等人，2014年）。结构*通讯作者。电子邮件地址：sandibit@gmail.com（新加坡）Maiti）。沙特国王大学负责同行审查因为这些数据彼此不同，数据的大小如此之大，以至于无法存储在一个单一的系统中（Labrinidad和Jagadish，2012）。在某些领域中，数 据 对 象 在 本 质 上 是 移 动 的 （ Barua 和 Sander ， 2014; Barua 和Sander，2011）。物体特征的数据许多应用程序希望从以各种格式收集和存储在不同系统中的数据中提取有意义的知识（Xindong例如，2014年）。最近的需求促使我们提出了一个分布式框架。本文提出了一种从自然分布的空间数据集中发现协同定位模式的分布式方法。空间物体在自然界中是运动我们感兴趣的任何对象（有生命的或无生命的）可以改变它们的地理位置，或者可以包括新的对象，或者先前的对象可以从我们感兴趣的区域消失。自治系统将持续收集有关对象的数据。每当新收集的数据与时间戳一起被包括时，协同定位模式也可以改变。本文还提出了一种方法，用于确定的变化，在共址模式方面的变化收集的数据。空间数据正在通过自治系统以连续的方式收集这种空间数据可以是1）非常大的量，如果我们有相对巨大的ROI，2）数据的结构将根据系统中涉及的收集代理而变化，3）数据收集本质上是连续空间数据可以被识别为https://doi.org/10.1016/j.jksuci.2018.08.0101319-1578/©2018作者。制作和主办：Elsevier B.V.代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comS. Maiti，R.B.V.Subramanyam/沙特国王大学学报10652 ≤ ≤ ≤ ≤大数据关于这几点，是指大数据VVV的定义。该方法计算对象之间的紧密接近度，根据对象的特征将其分组，并从分布式数据中发现各种大小的协同定位模式。我们使用Map-Reduce架构设计了这个分布式协同定位模式挖掘框架。该框架还能够根据共址模式的变化来处理时变空间数据。根据我们的例子，旅馆，医院，电影院，书店，购物中心，崇拜宫殿分别标记为L，H，C，B，M，W。 实体的对象集可以表示为{Hi}，{Mj}，{Wk}等，其中Hi共址模式挖掘问题的挑战在于：1）定义对象之间的邻近度量关系; 2）找到满足所定义的邻近关系的所有对象集合; 3）将属于不同实体集合的对象形成对象集合;4）找到数据集中频繁出现的实体集合;5）发现模式随时间的变化 空间数据集是对象的集合，如{O 1，O 2，. ......这是什么？ O k}和实体为{E 1，E 2，En}，其中每个对象OjE i|1我n和1JK.空间数据集具有大量的数据对象（Rajaraman和Ullman，2011），由属性集定义，经度和纬度作为强制属性来表示对象的实际位置1.1. 论文结构在本文中，第2节介绍了一个广泛的文献综述，第3节介绍了一个寻找同位模式的框架，第3.1节解释了所有算法，第3.2时间模式挖掘算法，第3.3节用一个例子评估了所提出的方法，第4节用一组合成数据集、标准数据集“GDELT”和两个实时数据集进行了实验2. 相关工作用于发现对象之间的交互的方法可以被归类为1）找到对象集合之间的关联规则（Agrawal和Srikant，1994），以及2）找到协同定位模式（Huang等人，2004; Shekhar和Huang，2001年7月）。关联规则A？B提供了当从超市购买了集合A时关于购买集合B的信息。关联规则挖掘算法从第一阶段的交易数据集中找到顾客经常购买的所有项目集F，其中F≠S，其中S是超市中可用的项目集。类似地，协同定位模式C给出了关于在地理空间中经常被发现在一起的对象集合的信息。 共址模式C=E，其中E是在特定位置可以找到的所有实体的集合。本文研究了Agrawal和Srikant（1994）提出的从跨数据集中寻找频繁项集的算法.该算法在第一阶段寻找频繁项集，在第二阶段从频繁项集产生关联规则。Han et al.（2004）提出了一种方法，没有候选生成的所有项集。该方法将构造频繁模式树，用于存储压缩形式的数据，并使用递归FP-Growth算法挖掘频繁模式树，以找到所有的频繁项集。协 同 定 位 模 式 挖 掘 问 题 由 Shekhar 和 Huang （ 2001 ） ，Morimoto（2001）提出，并在2004年得到扩展。（2004年）。他们提出了一种类似Apriori的候选生成和测试方法，用于从空间数据集中找到协同定位模式空间数据集包含有关数据对象的信息，如对象ID，经度，纬度和属性。这里的经度，纬度物体在地理空间中的实际位置。该方法的开销主要体现在以下几个方面：1）候选模式的生成方法; 2）用于计算模式出现次数的数据库扫描;Yoo和Shekhar（2004）提出了一种部分连接方法，以减少候选生成的开销。在2008年，Yoo和Shekhar（2008）Jin Songs提出了一种用于采矿共址模式的无连接方法。该方法大大降低了基于Apriori的协同定位模式挖掘方法的开销.Sajib Barua等人Barua和Sander（2014）在2014年提出了统计上显著的同位和隔离模式挖掘。作者将客体之间的相互作用定义为1）正相互作用（聚合）和2）负相互作用（抑制）。协同定位模式表示对象之间的积极互动，定义为实体的子集，其对象经常被发现而隔离模式代表负面的相互作用，定义为实体的子集，其对象经常被发现彼此相距甚远。全球定位系统（GPS）的最新发展和广泛使用正在整合任何事件、物体等的位置并将它们与地理位置和时间一起存储在数据集中。许多自治系统正在收集数据，如学校，医院，购物中心，政府大楼等的位置，有些人对动物及其运动感兴趣像学校、医院这样的物体的位置没有规律地变化，但是动物的位置变化非常频繁。这种类型的空间数据通常非常大。为了获得一些令人兴奋的知识，我们需要有效地处理这些大量的数据。我们提出了一种可扩展的方法，使用Map-Reduce分布式计算范式（Jacobs，2009）来处理大量的大数据是指由多个自主源生成的数量巨大、结构复杂且不断增长的数据集（Xindong等人，2014; Rajaraman和Ullman，2011; Wu等人，2005年）。空间数据也是由这种自主来源产生的。实体之间的关系随着时间而变化。由于一些空间物体在自然界中是移动的，这些数据是随时间记录的。我们感兴趣的是发现实体之间的这些不断演变的关系。大数据框架定义了架构（Chang et al.，2009; Gillick等人，2006），用于以分布式方式存储数据，获取所存储的数据，最后，处理数据以进行知识提取。Hadoop MapReduce计算架构提供了一种以分布式方式处理数据的方法（Labrinidad和Jagadish，2012; Ranger等人， 2007年）。Yoo等人（2014）提出了一种基于MR的并行算法，用于挖掘协同定位模式。作者提出了四个MR轮来寻找结果。Garaeva等人（2017）提出了一种改进的协同定位挖掘算法，使用FP-Growth代替ApacheSpark环境中的候选生成和测试方法。Kaur（2018）提出了一种使用张量概念降低大数据维度的方法，以促进集群节点之间的最佳数据传输。Aujla等人（2018）还展示了在节点之间采用软件定义网络通信的改进。下表1列出了一项重要的、关键的文献综述。2.1. 贡献1) 处理海量空间数据的框架;2）计算相邻关系的分布式方法; 3）无连接操作的同位挖掘方法;该方法还能够I）发现分离模式和II）处理时空数据。1066S. Maiti，R.B.V.Subramanyam/沙特国王大学学报ð;Þ¼iE2Ci表1一些相关文献。作者贡献R. 阿格拉瓦尔河Srikant于1994年提出了一种在大数据集中挖掘关联规则的算法S. Shekhar等人2001年提出合用同一地点采矿概念，2004年有所改善Jin Songyoo et al.2004年提出的部分加入办法和加入-在2008年，一种并行算法在2014年，用于挖掘协同定位模式。Sajib Barua等人合用同一地点的拟议统计意义2014年的隔离模式Xindong Wu et al.提出了改善数据用于处理大数据的挖掘算法。3. 该方法在本节中，我们定义了一个改进的基于MR的分布式算法框架，该算法用于从新添加的数据段中挖掘协同定位模式的变化并对实验结果进行了详细的讨论我们使用前面的例子来说明这个模型。Ei是唯一标识，其中E是空间特征或实体，i用于唯一标识对象例如，M3表示实体M的实例，并且它是空间数据集中M的第三个如果两个实例具有空间邻域关系，则它们通过边连接。共址模式是在（p，cp）下彼此相关的空间实体的子集（Huang等人，2004年）。P是表示流行率测量的数字，CP是测量一致性概率的数字。该协同定位模式被表示为实体的集合C，如C{E1，E3，E5}。这些实体在（p，cp）下相互关联。条件概率（CP）的规则E i？Ej定义如下：cally表示数据集中实体出现的总次数。上述进程将结果存储在单独的文件中，这些文件将输入到名为Process1的下一个进程。这将找到大小为2的协同定位模式，并修改结构化数据.最后，进程2将找到大小为k的协同定位模式，并在每次迭代中修改结构。优先级进程2采用由进程1修改的结构，但从下一次迭代开始，它采用由同一进程在前一次迭代中修改的结构。计数表对于Process 2和Process 1的所有迭代保持相同。该迭代继续进行，直到过程2不能找到大小为（k + 1）的任何候选协同定位模式的点。最后，通过所有Map-Reduce轮产生的o/p的总结将给出所有频繁的co-location模式。时间数据具有带有收集的数据的时间戳标签。 在图1中提出的模型，与固定的时间窗口。对于具有较低时间戳的数据集（早期数据），可以针对特定的R接近度度量、距离阈值（R）和用户定义的最小支持（d）找到频繁的协同定位模式。处理具有更大时间戳的最近数据集，将在阶段1完成但是阶段2可以由时间模式挖掘算法代替，该算法在下一节中解释，只要R-接近度、R、d保持不变。对于这三个约束条件的变化，整个过程（两个阶段）必须对整个收集的数据执行新的测量，相对于时间interval.3.1. 比较与文献中的其他并行算法相比，1）该模型能够在一轮MR中从空间数据生成邻域结构，2）计数特征也使用In-Mapper-Combiner MR算法创建，3）邻域结构由Process 1修改，由Process 2引用并在Process 2的每次迭代中修改。3）详细O/P为cp E E在Ei[Ej]的实例中E i的无区别性也与Process 1和Process 2的结构一起修改。4）可否─i;jnoofinancesofEi使用团属性代替连接方法生成双日期模式5)候选人的修剪也是通过引用实现的-实体Ei参与共址集合C ={E1，En}是定义如下：cp C EnoofdestinstinstancesofEi participatesinCnoofinancesofEi共址模式的总体参与等于cpC;E i中的最小值。能够被注明为cpCminfcpC;Eig关系R-邻近邻域（Huang等人， 2004）是同位模式挖掘中的一个重要概念。这种度量给出了对象之间的相似性的概念相邻关系R可以使用空间关系、度量关系或两者的组合来定义本文将地理距离定义为R-邻近度.先前定义的p反映了这种邻域关系。作为一个例子，如果集合C满足关系R（通过满足p）并且C中的元素形成团，则将其视为候选模式如果来自集合C的对象之间的所有成对距离小于最小阈值，则C将被记为共位模式。相反，C可以被注意为分离模式。图 1显示了用于处理大量空间数据的拟议模型的概述。标记为空间数据的椭圆形单元是一些自治系统收集的非结构化原始数据的来源。我们集中在具有经度、纬度作为属性的对象矩形是进程。第一个过程称为创建结构是重要的过程，结构化的数据。计数特征过程查找每个实体的计数，该计数基于将所有频繁项集环到上一级。3.2. MR算法在本节中，我们将介绍一个分布式协同定位挖掘算法。这些算法的设计是基于标准Hadoop Map-Reduce（MR）（Gillick等人，2006;Jacobs，2009）计算架构。MR计算架构设计用于处理大量数据。这种体系结构将数据分布到小块中，以促进并行数据处理。Mapper和Reducer是两个小的逻辑块，它们将在不同的节点中并行处理小块数据。首先，数据将在不同的节点上由Mapper逻辑处理并输出将被写入一个名为HDFS（Hadoop分布式文件系统）的平台。在完成所有映射过程之后。Hadoop主节点将对生成的中间数据执行排序和洗牌操作，并将在reducer进程之间划分和分发此排序的数据块。其次，Reducer将从HDFS中获取数据块，并根据逻辑在不同的节点上同时处理它，以产生预期格式的结果。当所有映射器完成其任务时，还原器阶段开始。我们已经提出了1）用于从分布式空间数据中提取协同定位模式的算法框架，其具有如图1所示的基于MR的四个子算法。2)还提出了一种捕捉模式变化的算法。本节介绍了所有子算法以及详细说明。S. Maiti，R.B.V.Subramanyam/沙特国王大学学报1067←←←←←←←←←←←←创建结构空间数据结构计数表过程1协同定位模式{2}改进结构Stage1计数特征详细O/P计数表进程2协同定位模式{k}改良结构第2阶段Fig. 1. 拟议模型的框图。算法1是MR算法，用于处理计数特征，将计数属于数据集中找到的任何特征的对象的数量。整个数据将是自然分布的，因此映射器将在不同的节点中获取单独的块作为输入，并计算为任何特征（实体）找到的对象的数量。每个映射器都将在HDFS中写入他们的发现。Reducer将对一个特定的键进行总计操作，该键将是一个实体。如在示例数据集中，实体H具有四个对象，并且实体M具有五个对象。算法1. 计数特征的MR算法输入：数据文件输出：计数表将写入O/P文件变量：ENT []null;C []0;Enull;Count0;1.过程映射器（键=数据文件;值= 0）2.对于数据文件中的所有对象O;3.E实体类型为O;4.如果E存在于ENT中，则5.C[E] C[E]+ 1;6.其他7.在ENT和C[E]1中加入E8.end if9.端10.对于i 1，ENT.大小11.int[i]，int [i]，int [i]12.端13. 结束程序14. 手术减速器（键=ENT;值=[c]）15.对于特定ENT16.对于c，在[c]中17.Count=Count+c;18.端19.int count（count，Count）;20.端21. 结束程序创建结构过程还将空间数据文件作为输入，以及R-邻近距离定义和距离阈值（R）。算法2是针对流程创建结构演示相应的MR算法，将非结构化数据转换为定义的键值结构，以减轻后续MR流程对数据的可访问性。映射器将接受由自主系统收集或生成的原始数据。它会找到成对的满足R的对象。此输出将写入分布式文件系统和reducer进程将接受具有相同键的数据块。Hadoop的中间进程会将数据按照键进行分块，这样reducer就可以得到对应于一个键的所有值。reducer将从该值集生成一个列表，该列表将是与I/P键一起写入O/P的值部分。非结构化的空间数据已被转换为（键，值）结构的MR过程。算法2.创建结构输入的MR算法：数据文件输出：定义的结构将写入O/P文件变量：D 0.0。R-邻近（Oi，Oj）;AList空1.过程映射器（键=数据文件;值= 0）2.对于所有对象Oi，块3.对于块中的所有对象Oj4.如果实体类型（Oi）5.D←R-邻近（Oi，Oj）;6.如果D≤R，则7.return（Oi，Oj）;8.end if9.end if10.端11. 端12. 结束程序13. Procedure Reducer（key = Oi; value=[Oj]）14. 对于特定键Oi15.对于所有Oje [Oj]16.在AList中添加Oj;17.端18.return（key）;19.AListnull;20. 端21. 结束程序3.3. 例如我们指的是图。 2.解释输出过程的结构。连接的点表示R-邻近邻域。创建结构和计数特征过程读取数据以构建如图右侧所示的定义的结构和计数表。 二、此结构显示特定点的邻居列表计数表提供有关数据中存在的对象类型（实体）的对象总数的信息。1068S. Maiti，R.B.V.Subramanyam/沙特国王大学学报←←←←←←--←2←2←←←←图二.实例数据上的相邻关系（R-接近度）。图1中的过程1生成大小= 2的频繁共址模式。算法3介绍了Process 1的Mapper算法。 它接受结构数据并生成一对对象作为键值对。算法3. Process1的映射器算法输入：结构化数据;变量：Knull;Vnull;1. 过程映射器（键=结构化数据;值= 0）2. 对于所有行输入键3.K←行的第一部分（键）;4.V←剩余部分（值）;5.对于所有对象Oi2V6.如果对象类型（Oi）>对象类型（K）7.int i（i，i）;8.end if9.端10. 端11. 结束程序进程2生成从size = 3开始的所有频繁模式。算法4是Process 2的Mapper算法，生成候选算法（续）7.如果对象类型（Pi的第K个对象）>对象类型（Pj的第K个对象）8.V←Pi + Pj的第K个对象;9.否则VPj + Pi的第K个对象;10.end if11.end if12.end if13.emit（Pi，V的前两个对象）;14.Vnull;15. 端16. 端17. 结束程序算法5从分布式文件系统读取由算法3和算法4它从一个键的对象集合中找到实体集合。从这个转换的值集中找到具有合理支持的频繁共址模式并打印为O/P。该算法还修改了结构，该结构将由后续的Process2轮访问。算法5. Process 1和Process 2的Reducer算法通过阅读详细的O/P和mod，由算法5编写的固定结构，它是process1和process2的公共Reducer进程。算法4. Process2的Mapper算法输入：详细O/P变量：K 0;Vnull;1. 过程映射器（键=详细O/P;值= 0）2. K←键中图案的大小3. 对于key中的所有模式Pi，4.对于key中的所有下一个模式Pj，5.如果P i的前（K 1）个对象== Pj然后6.如果邻域（Pi的第K个对象，Pj的第K个对象）为真，则输入：由Process 1的Mapper生成的键值对，过程2.输出：所有共址模式。变量：CT[] 0;mapPnull;Temp 0; setETnull;1. 程序缩减器（键=对象集;值= [对象集]）2. CT[]计数表;3. 对于所有对象集[对象集]4.ET（实体集）对象集;5.如果ETP的键，则6.ET+的值=对象集;7.其他8.P+= ET;9.ET+的值=对象集;10.end ifS. Maiti，R.B.V.Subramanyam/沙特国王大学学报1069≥←←2←63←≥63⊂22←2←2←←←≥← ←←←←←←←←←2≥←≥算法（续）11. 端12. 对于P的所有ET2密钥13.ET的温度←cp14.如果Temp d，则15.int n（n，n）;16.end if17. 端18. 对于结构中的所有行19.如果长度（结构的值部分）≤长度（ET），则算法（续）3. k←模式2MLP的大小;4. LT2←DT2中大小= 2的频繁模式5. 对于所有P2MLP6.如果ChkSubset（LT2，P）为真，则7.如果P个用户的cp阈值，则8.MCP加P;9.intn（P）;10.对于所有xtemp11.如果BK x，则20.删除线;21.end if22. 端23. 结束程序3.4. 时态模式挖掘算法算法6是一个时空数据的同位模式挖掘算法，它可以代替进程2。最近收集的数据可以通过比较时间戳来识别。以下四个程序将生成(i)下一级候选和（ii）前一级候选，连同给定模式的检查子集和超集包含到模式列表这些程序已被用于时态模式挖掘算法中过程KeyGen（）接收模式列表，其中模式长度为k，生成长度为（k+ 1）的所有可能的候选模式。过程BackKeyGen（）接受长度为k的模式并生成长度为（k- 1）的候选模式。12.BK加x;13.end if14.端15.否则iMP加P;16.end if17.end if18. 端19. while（flag）20.对于PImp21.int n= int n（n）;22.对于y2温度23.如果ChkSubset（LT2，y）cpofyd，则24.如果BK y，则25.BKaddy;26.end if27.else ifiBK y then28.iBKaddy;29.end if30.end if31.端32. temp= KeyGen（BK）;flag← false;33. 对于所有x2温度过程ChkSubset（）返回true，如果所有2个长度模式生成从接收到的模式中产生，在2长度模式的列表中可用。过程ChkSuperset（）返回true，如果接收到的模式是接收到的模式列表中的任何模式.提出的时态模式挖掘算法以早期的挖掘结果和第1阶段的O/P为参考，这是大小= 2的频繁模式。它的目的是找到最近数据集的最大模式。具有最大长度的模式可以从早期的挖掘结果中找到，这在最近的数据中更有可能是频繁的。根据Apriori性质，频繁模式的所有子模式都是频繁模式.当最大模式的长度为k时，该算法将产生一个长度为k-1的频繁模式子集，并通过迭代的方式产生新的k长频繁模式。它还检查生成k+ 1长度的频繁最大模式等，一些有希望的非频繁模式对于生成长度为k的最大模式也很重要，因此我们将它们保留到检查过程。算法6.时态模式挖掘算法。输入：DT2←带有时间戳（T2）的数据文件，CL←前一个时间戳（T1）输出：所有共址模式。变量：列表MLP←null，MCP←null，iMP← null。列出LT2大小= 2的频繁模式。列表BKnull;列出iBK无 效 ;1. process Temporal Patterns（）2. MLP←最大长度模式CL。34.如果MCP xiMP63x35.如果ChkSubset（LT2，x）cpofx d，则36.MCPaddx;37.elseiMPaddx;flagtrue;38.end if39.end if40.端41. 端42. end while43. 对于所有xBK44.如果ChkSuperset（MCP，x）！= true则45.MCPaddx;46.end if47. 端48. while（flag）49. BK iBK;iBKnull;flagfalse;50.对于所有xBK51.如果length（x）大于3，则52.TempBackKeyGen（x）53.对于所有Ytemp54.如果ChkSuperset（MCP，y）！= true则55.如果ChkSubset（LT2，y）cpofyd，则56.MCP加Y;57.其他58.标志true;iBKaddy;59.end if60.end if61.端62.end if63.端64. end while1070S. Maiti，R.B.V.Subramanyam/沙特国王大学学报≥3.5. 实例评价模型本文通过一个实例说明了该模型和时态挖掘算法的工作过程。 进程1将从该结构化数据中找到一些对象对，如（B1，L2）、（B2，L1）、（B2，M4）、（B2，H1）、（B3，L3）、（B3，M1）等。共-将从这些对中找到关于CP和D的大小为2的位置模式，CP和D描述了这些实体集合一起出现的频率。从这个例子中，我们可以发现一些实体集合一起出现为（B，L），（C，W），（M，H）等。过程2开始向前寻找大小为3的候选对象集合。对于该示例，可以找到以下候选（B3，L3，M1）、（M2，W3，C2）、（B2，H1，L1）、（B2，H1，M4）、（B2，L1，M4）、(H1、L1、M4）。进程2可以找到（B，L，M）作为大小为3的频繁共址模式，其中cp= 40% >d，定义为30%。我们已经从数据集中找到了所有常见的协同定位模式。提出的算法6从早期挖掘结果中找到最大长度模式。作为示例，考虑实体集合E = {A，B，C，D，E，F}并且集合s1={ABCDE，ABCDF}是最大长度模式的集合。如果ChkSubset（）对于s1中 的 所 有 元 素 返 回 true ， 则 BackKeyGen （ ） 将 产 生 s2={BCDE ，ACDE，ABDE，ABCE，ABCD，BCDF，ACDF，ABDF ， ABCF} 。 KeyGen （ ） 将 生 成 s3={ABCEF ， ABDEF ，ACDEF，BCDEF}。如果模式EF在最近的数据中不频繁，则s3的任何否则，如果s3是频繁的，则所有成员。由于s1和s3的所有元素都是频繁的，因此可以生成ABCDEF并声明为频繁的。如果CE在最近的数据中是不频繁的，则算法6找到{ABCDF，ABDEF}作为最大频率模式。在我们提出的方法中，我们定义了共址模式w.r.tR-邻近测度和条件概率。如果对象之间的距离小于R，并且cp也大于d，则这组特征被称为共定位模式。类似地，如果物体之间的距离大于R并且cp也大于d，则这组特征被称为分离模式。4. 实验评价为了进行性能分析，我们实现了这个模型，用于提取有关频繁共址模式的知识。该提出的系统将接受空间数据，并且该模型中的所有过程在阶段1中计算数据单次以找到长度为2的协同定位模式，而过程2将计算迭代方式以向前找到长度为3的模式，直到它不能找到相对于早期模式更大尺寸的任何模式时4.1. 实验装置我们已经在一个有8个处理器，512 GB RAM和3.6 TB硬盘的系统上实验了这个模型，每个处理器有8个核心。此服务器运行CentOS和StandardHadoop 2.7框架。我们正在运行8个虚拟机，它们充当数据节点，其中一个充当主节点。4.2. 合成数据集这是一个系统生成的数据集，遵循真实数据集的数据结构。我们根据以下要求生成数据集：1）实体集的大小，2）数据点的总数和3）指定的区域，这些点位于何处。我们已经展示了对我们提出的模型的详细评估，合成数据集共有30个点，其中有4个实体作为示例。我们还展示了大数据变量的详细性能评估。4.2.1. 用合成数据解释模型第一步：我们提出的方法将在读取数据集后创建两个结构，命名为1）计数表和2）结构。表2示出了1）计数表，其中{A，B，C，D}表示 Ei以及它们的出现值，2）结构示出了对象Oj的一组邻域。步骤2：计数表、结构被输入到过程1，如图2所示。过程1将产生1）长度= 2的共址模式，2）修改的结构和3）对象的详细成对关联。表3显示了Process 1的o/p。尺寸为2的共位模式，支持（0AB具有0.37支撑，AC具有0.4支撑等等。步骤3：流程2将在流程1完成后启动，i/p1）计数表，2）修改结构，3）第一次详细的过程1的o/p。长度为3的协同定位模式将由过程2以迭代方式生成。表4显示了从我们的合成数据集中发现的协同定位模式。4.2.2. 性能分析此模型的性能以执行时间（分钟）和资源利用率（活动节点数）相对于数据大小（点数）的形式呈现。合成数据已生成，与25个实体与一个定义的ROI。由于空间数据是自然分布的，我们还在数据节点之间分布了合成数据，例如20 k点在一个节点中，40 k点在两个节点中，60 k点在两个节点中。是在三个节点上，80 k，100 k是在四个节点上。实验结果如图所示。3.第三章。表3过程1的O/P。AB0.375A4[b2、c8、b8、c9、d4]AC0.4A5[d3、b1、b2、d4、c8、b7、c9]AD0.3750.375A8[d4、c9、c8、b2]BC0.8B1[c10、d4、c1、c4、a5、d3]BD0.75B3[c1、c3、c4、c10、d3]CD0.8b5b6b7B8[c1、c2、d2][c6，d1][c4、c8、c9、d3、d4] [c3、d3]尺寸2的图案改良结构表2从数据集中提取的计数表一8A1[c5]B1[c1、c4、c10、d3、d4]C1[d2，d3]B8A2[c5、c7]B2[c8、c9]C2[d2]C10A3[c5、c7]B3[c1、c3、c4、c10、d3]C3[d3]D4A4[b2、b8、c8、c9、d4]B4[c1、c4、c10]C4[d3]A5[b1、b2、b7、c8、c9、d3、d4]B5[c1、c2、d2]C6[d1]A6[c7]B6[c6，d1]C8[d3，d4]A7[c5、c7]B7[c4、c8、c9、d3、d4]C9[d4]计数表a8结构[b2、c8、c9、d4]B8[c3，d3]C10[d2]S. Maiti，R.B.V.Subramanyam/沙特国王大学学报1071表4所有频繁的共址模式。AB0.375BC0.8ABC0.375AC0.4BD0.75Abd0.375AD0.375CD0.8ACD0.375BCD0.375见图4。 GDELT数据集的实验结果。图三. 试验结果在第一个直方图中，非常清楚的是，计数功能的执行时间差异（图中的p1）。 3 w.r.t数据大小非常小。而创建结构需要很长时间，增量很大。大号的。我们提出的模型的Process1消耗的时间相对较少，比创建结构的执行时间增量较小。流程2是一个迭代过程，比其他过程消耗更长的时间，并且随着数据量的增加而增加。第二个直方图显示了一个进程使用的资源总数（活动节点数）与数据大小。由于数据已经分布在数据节点上，因此它们必须参与所有流程。根据图3。P1和P3需要20k个点的单个资源，P2和P4需要两个资源。这里所需的两个资源表示需要一个额外的节点。同样，可以分析其他综合数据集的资源需求。时间模式挖掘算法将取代stage2，如前所述。由于该过程可以在单个节点中执行，因此图3中的P4的资源需求将减少到1。此外，时间模式挖掘的执行时间相对于提出的同位模式挖掘的第2阶段变化较小，因此该模型的性能也得到了提高。我们取20k点作为流大小。Temporal挖掘过程需要花费几分钟的时间来产生预期的大小为20 k的初始数据的执行时间是20.1 M，但对于下一个20 k执行时间是13.5 M而不是24.2 M，如图3的第三个图所示。3.第三章。4.3. GDELT实验我们的两种方法都是在标准数据集“全球事件、语言和音调数据库”（GDELT）上运行的它是一个实时开放的数据集，记录了来自世界各国的100多种语言的世界它拥有自1979年以来的大量数据，有85，836，060条记录，所有操作都是131074119791989 1999年200910095908580757019791989 1999年20091，4 1，5 2，3 4，52015105020K 40K 60K 80K 100K数据大小P1 P2 P3 P48642020K 40K 60K 80K 100K数据大小P1 P2 P3 P4带TPM的MR模型80K 100K60K数据大20K 40K353025201510时间# Active Node执行时间支持支持1072S. Maiti，R.B.V.Subramanyam/沙特国王大学学报图五. 树木的分布。见图6。 不同年龄的手杖分布。分为5种动作类型和263个CAMEO代码。我们已经考虑将GeoType作为我 们 实 验 的 实 体 。 还 有 另 外 两 个 属 性 ， 分 别 称 为 “GeoLat” 和“GeoLong”，表示特定实体的实际地理位置。我们的协同定位模式挖掘算法发现的事件，这是发现发生在附近。我们已通过将总数据与事件发生年份分离，对GDELT数据集进行了预处理。我们发现，（Type1，Type4 ），（Type1，Type5），（ Type4 ， Type5 ） ， （ Type2 ， Type3 ） ， （ Type1 ， Type4 ，Type5）是同位事件，具有高支持率，大于70%。图4第二部分显示了每年支助百分比的变化。图的第一部分。 4显示了一个不常见的模式（类型2，类型5）。4.4. 真实数据集4.4.1. 兰辛伍兹点数据这一数据来自于对美国密歇根州克林顿县兰辛森林中19.6亩宏基地块的调查。D.J. Gerrard进行了这项研究（Perry等人，2006年）。该数据集包含2146棵树的位置及其植物学分类。图5显示了相应地命名为黑橡树（1 3 5）、山核桃（7 0 3）、枫树（5 1 4）、白橡树（3 4 6）和山楂树（4 4 8）的种类的分布。发现（枫木，杂木）、（白橡木，杂木）、（山核桃木，白橡木）、（黑橡木，杂木）为共位模式，（黑橡木，枫木）、（山核桃木，枫木）为分离模式。4.4.2. Bramble Canes数据黑莓灌木被称为荆棘。Bramble手杖数据由Diggle（2003）收集和分析。该数据集有823条手杖记录，由3列（x，y，age）定义，其中（x，y）给出手杖的位置，年龄对它们进行分类。一共有359根手杖10.90.80.70.60.50.40.30.20.10年龄=0年龄=1年0 0.2 0.4 0.6 0.8