模式更新装置、更新方法及非瞬时性计算机可读记录介质与流程

1.本公开涉及模式更新装置、模式更新方法以及非瞬时性计算机可读记录介质。

背景技术：

2.h.cao et al.,mining frequent spatio-temporal sequential patterns,ieee international conference on data mining(icdm),2005(以下记载为cao et al.)以及f.giannotti et al.,efficient mining of temporally annotated sequences,siam international conference on data mining(sdm),2006(以下记载为giannotti et al.)公开了如下方法：将多个行程(trip)(道路线路列(road link sequences))作为输入，通过批(batch)处理提取频繁出现的模式(pattern)。
3.cao et al.以及giannotti et al.所记载的方法仅提供将多个行程(道路线路列)作为输入来通过批处理提取频繁出现的模式的技术，每当输入新的行程(道路线路列)时，都需要进行模式的提取。另外，所提取出的模式多数情况下能够通过前缀等进行汇集，但在简单的方法中需要与模式数
×
模式长度相应地进行匹配(matching)。在此，模式(pattern)是指行程(trip)中的特定行驶地点的组，模式长度是指模式中的特定行驶地点的数量。

技术实现要素：

4.本公开的目的在于提供减轻了模式的提取以及更新所需的处理负荷的模式更新装置、模式更新方法以及非瞬时性记录介质。
5.第1技术方案的模式更新装置包括：存储器；和处理器，其连接于所述存储器，所述处理器从多个路径信息中提取频繁出现的模式，将所提取出的模式作为预定的数据结构来进行保存，相对于所保存的预定的数据结构，对新取得的路径信息进行对照，通过基于对照来对所保存的所述预定的数据结构进行更新，从而对在包含新取得的路径信息的全部路径信息中频繁出现的模式进行更新。
6.第1技术方案的模式更新装置的处理器从多个路径信息中提取频繁出现的模式，将所提取出的模式作为预定的数据结构来进行保存，相对于所保存的预定的数据结构，对新取得的路径信息进行对照，通过基于对照来对所保存的预定的数据结构进行更新，从而对在包含新取得的路径信息的全部路径信息中频繁出现的模式进行更新。根据第1技术方案的模式更新装置，通过使频繁出现的模式适合于预定的数据结构并对其信息保存，相对于所保存的模式，对照路径信息，基于对照结果来对模式进行更新，从而能够减轻对模式进行更新时的处理负荷。根据第1技术方案的模式更新装置，通过基于数据结构来对新的路径信息进行对照，能够使对照以及频度的更新简化。
7.第2技术方案的模式更新装置中，所述处理器构成为：提取超过了设定次数的路径信息来作为频繁出现的模式，所述设定次数被设定为了比希望取得的频繁出现模式的出现频度少。
8.根据第2技术方案的模式更新装置，通过基于模式的最小出现频度和所对照的路径信息的数量来提取频繁出现的模式，能够具有余裕地提取模式。
9.第3技术方案的模式更新装置中，所述处理器构成为：使通过对照而新成为了频繁出现的模式的模式适合于所述数据结构，并对其进行保存。
10.根据第3技术方案的模式更新装置，能够将通过对照而新成为了频繁出现的模式的模式作为对照对象。
11.第4技术方案的模式更新装置中，所述数据结构是在树结构中对共同前缀进行汇集，在边缘保持了出现次数的数据结构。
12.根据第4技术方案的模式更新装置，通过数据结构为在树结构中对共同前缀进行汇集，在边缘保持了出现次数的数据结构，能够简化数据结构。
13.第5技术方案的模式更新方法中，通过处理器，从多个路径信息中提取频繁出现的模式，将所提取出的模式作为预定的数据结构来进行保存，相对于所保存的预定的数据结构，对新取得的路径信息进行对照，通过基于对照来对所保存的所述预定的数据结构进行更新，从而对在包含新取得的路径信息的全部路径信息中频繁出现的模式进行更新。
14.第6技术方案的模式更新方法中，通过所述处理器，提取超过了设定次数的路径信息来作为频繁出现的模式，所述设定次数被设定为比希望取得的频繁出现模式的出现频度少。
15.第7技术方案的模式更新方法中，通过所述处理器，使通过对照而新成为频繁出现的模式的模式适合于所述数据结构，并对其进行保存。
16.第8技术方案的模式更新方法中，所述数据结构是在树结构中对共同前缀进行汇集，在边缘保持了出现次数的数据结构。
17.第9技术方案的计算机可读取非瞬时性记录介质保存有程序，所述程序使计算机执行如下处理：从多个路径信息中提取频繁出现的模式，将所提取出的模式作为预定的数据结构来进行保存，对于所保存的预定的数据结构，对新取得的路径信息进行对照，通过基于对照来对所保存的所述预定的数据结构进行更新，从而对在包含新取得的路径信息的全部路径信息中频繁出现的模式进行更新。
18.第10技术方案的计算机可读取非瞬时性记录介质提取超过了设定次数的路径信息来作为频繁出现的模式，所述设定次数被设定为比希望取得的频繁出现模式的出现频度少。
19.第11技术方案的计算机可读取非瞬时性记录介质使通过对照而新成为了频繁出现的模式的模式适合于所述数据结构，并对其进行保存。
20.第12技术方案的计算机可读取非瞬时性记录介质中，所述数据结构是在树结构中对共同前缀进行汇集，在边缘保持了出现次数的数据结构。
21.发明的效果
22.根据本公开，能够提供一种模式更新装置、模式更新方法以及非瞬时性的计算机可读记录介质，其通过从车辆的行驶数据的位置信息中提取频繁出现的路径信息的模式，在取得了新的位置信息时高效地进行与模式的匹配，对频繁出现的模式进行更新，从而减轻了处理负荷。
附图说明
23.图1是表示公开的技术的实施方式涉及的模式更新装置的一个例子的构成的图。
24.图2是表示保存部保存的模式的数据结构的例子的图。
25.图3是表示由对照部进行的对照和由更新部进行的更新的例子的图。
26.图4是表示由对照部进行的对照和由更新部进行的更新的例子的图。
27.图5是表示由对照部进行的对照和由更新部进行的更新的例子的图。
28.图6是表示由对照部进行的对照和由更新部进行的更新的例子的图。
29.图7是表示由对照部进行的对照和由更新部进行的更新的例子的图。
30.图8是表示由模式更新装置进行的模式更新处理的流程的流程图。
具体实施方式
31.以下，参照附图对本公开的实施方式的一个例子进行说明。此外，在各附图中对同一或者等效的构成要素以及部分赋予同一参照标号。另外，为了便于说明，附图的尺寸比率有时会被夸大而与实际的比率不同。
32.图1是表示本实施方式涉及的模式更新装置的构成的图。图1所示的模式更新装置10是如下装置：从车辆的行驶数据的位置信息中提取频繁出现的轨迹的模式，在取得了新的位置信息时高效地进行与模式的匹配，对频繁出现的模式进行更新。
33.模式更新装置10具有作为硬件处理器的一个例子的cpu(central processing unit，中央处理单元)11、rom(read only memory，只读存储器)12、ram(random access memory，随机访问存储器)13以及储存器(storage)14。
34.cpu11是中央运算处理单元，执行各种程序，对各部进行控制。即，cpu11从rom12或者储存器14读出程序，将ram13作为工作区域来执行程序。cpu11按照记录于rom12或者储存器14的程序，进行上述各构成的控制以及各种运算处理。在本实施方式中，在rom12或者储存器14中保存有执行用于对模式进行更新的模式更新处理的模式更新程序。
35.rom12保存各种程序以及各种数据。ram13作为工作区域暂时性地存储程序或者数据。储存器14由hdd(hard disk drive，硬盘驱动器)、ssd(solid state drive，固态硬盘驱动器)或者闪速存储器等的存储装置构成，保存包括操作系统的各种程序以及各种数据。
36.在执行上述的模式更新程序时，模式更新装置10使用上述的硬件资源来实现各种功能。对模式更新装置10实现的功能构成进行说明。
37.如图1所示，模式更新装置10通过cpu11读出并执行存储于rom12或者储存器14的解析程序，从而以cpu11具有提取部101、保存部102、对照部103以及更新部104的方式发挥功能。
38.提取部101从预先取得的多个路径信息中提取频繁出现的模式。路径信息例如可以保存于储存器14。例如，提取部101也可以提取超过了设定次数的路径信息来作为频繁出现模式，该设定次数被设定为比希望取得的频繁出现模式的出现频度少。
39.详细而言，提取部101从多个车辆行驶数据的位置信息中提取频繁出现的模式。位置信息例如是指gps的纬度、经度的序列(行程)。通过将纬度、经度关联于例如预先定义的离散的道路线路，对于各行程得到如以下那样的道路线路列的表现。在行程1的例子中，意味着从道路a通过道路b，进一步通过了道路c这一情况。将各个道路线路也称为节点
(node)。
40.行程1：a
→b→c41.行程2：a
→b→c→d42.行程3：a
→b→d→c→d43.提取部101对于这样的行程的表现，例如使用下述文献1、2中提出的序列模式挖掘(sequential pattern mining)的方法等，提取频繁出现的轨迹的模式。此时，用户指定全部行程数m中的模式出现的最小频度m以及在后述的对照部103中与所提取出的模式进行匹配的行程的个数n，提取部101仅提取出现次数为(m－n)以上的模式。另外，作为条件，也可以由用户指定其比例r(＝(m－n)/m)。
44.(文献1)
45.·
j.pei et al.,prefixspan:mining sequential patterns efficiently by prefix-projected pattern growth.in proceedings of international conference on data engineering(icde),2001.
46.(文献2)
47.·
r.srikant and r.agrawal,mining sequential patterns:generalizations and performance improvements.in proceedings of the 5th international conference on extending database technology advances in database technology(edbt),1996.
48.此外，在对照部103中对出现频度m的模式进行对照时，在提取部101中将为了制作树结构而预先提取的模式的出现次数设为了(m－n)的理由是，为了使频繁出现的模式的提取具有余裕。例如在希望得到出现频度m＝10的频繁出现模式的情况下，在将新追加的行程的数量n设为了n＝4时，仅用最初在提取部101中出现了m－n＝6次以上的行程制作树结构。通过提取部101这样进行提取，新的行程相对于出现频度6的模式的对照结果是，在n(＝4)个全部一致了的情况下，能得到出现频度为10的频繁出现模式。
49.保存部102将提取部101提取出的模式作为预定的数据结构来进行保存。预定的数据结构例如既可以是在上述文献1、2中列举出的数据结构，也可以是在树结构中汇集共同前缀，在边缘保持了出现次数的数据结构。此外，保存部102的功能也可以为储存器14所具备。
50.图2是表示保存部102保存的模式的数据结构的例子的图。图2是针对以下的模式而保存着的例子。
51.模式1：a
→
b(频度＝4)
52.模式2：a
→b→
c(频度＝3)
53.模式3：a
→
c(频度＝3)
54.模式4：a
→
d(频度＝4)
55.模式5：e
→
d(频度＝4)
56.模式6：e
→
f(频度＝3)
57.对照部103将模式更新装置10新取得的路径信息，相对于保存部102所保存了的预定的数据结构进行对照。
58.更新部104基于由对照部103实现的路径信息的对照，对保存部102所保存了的预
定的数据结构进行更新，由此对在包含模式更新装置10新取得的路径信息的全部路径信息中频繁出现的模式进行更新。更新部104也可以使通过对照部103的对照而新成为了频繁出现的模式的模式适合于预定的数据结构，并使之保存于保存部102。
59.反复进行由对照部103进行的对照和由更新部104进行的更新，直到变为没有所取得的路径信息。
60.图3～图7是表示由对照部103进行的对照和由更新部104进行的更新的例子的图。图3是新取得了a
→b→
c这一行程的情况下的对照例。
61.首先，起点为节点a，因此，对照部103首先对节点a进行对照。并且，如图3所示，更新部104将节点a的出现次数从5增加为6。
62.下一节点为节点b，因此，对照部103对从节点a向节点b的路径进行对照。并且，如图4所示，更新部104将从节点a向节点b的路径的出现次数从4增加为5。
63.下一节点为节点c，因此，对照部103对从节点b向节点c的路径进行对照。并且，如图5所示，更新部104将从节点a经由节点b而到达节点c的路径的出现次数从3增加为4。
64.a
→b→
c这一行程也可以认为途中的节点b是起点。首先，起点为节点b，因此，对照部103首先对节点b进行对照。并且，如图6所示，更新部104将节点b的出现次数从4增加为5。
65.下一节点为节点c，因此，对照部103对从节点b向节点c的路径进行对照。并且，如图7所示，更新部104将到达节点c的路径的出现次数从3增加为4。
66.如图3～图7所示，更新部104在使相应的模式的路径的出现次数增加一个的同时，新追加成为用户所指定的最小频度m或最小比例r以上的模式。
67.在未出现于模式的新模式出现了的情况下，对照部103在对照时暂时停留于途中的节点。例如在出现了a
→z→
b这一行程的情况下，停留在作为从节点a起的子节点的节点z，在到达了更前方的节点b时对a
→
b的频度进行更新。在该情况下，当a
→
z超过了频度的阈值时，登记为新的模式。
68.在对照部103对a
→b→
c这一行程进行对照，更新部104对频度进行更新的情况下，对照具有a
→b→
c的情况和b
→
c的情况这两个模式，但b
→
c的频度的更新仅为一次。另外，保存部102也可以对将节点a作为了起点的b
→
c这一模式和将节点b作为了起点的b
→
c模式进行区别而作为其他信息进行保持。
69.在新出现了如行程a
→b→c→
a这样的模式的情况下，保存部102也可以因新出现终点的节点a而保存模式。
70.模式更新装置10通过具有图1所示的构成，从车辆的行驶数据的位置信息(gps等)中提取频繁出现的轨迹的模式，在取得了新的位置信息时高效地进行与模式的匹配，对频繁出现的模式进行更新。模式更新装置10通过高效进行与模式的匹配，对频繁出现的模式进行更新，从而能够减轻处理负荷。
71.接着，对模式更新装置10的作用进行说明。
72.图8是表示由模式更新装置10实现的模式更新处理的流程的流程图。通过cpu11从rom12或者储存器14读出模式更新程序，并展开到ram13来执行，从而进行模式更新处理。
73.cpu11从预先取得的多个路径信息中提取频繁出现的模式(步骤s101)。路径信息例如可以保存于储存器14。例如，cpu11也可以提取超过了设定次数的路径信息来作为频繁出现模式，该设定次数被设定为比希望取得的频繁出现模式的出现频度少。
74.接着步骤s101，cpu11将在步骤s101中提取出的模式作为预定的数据结构来进行保存(步骤s102)。预定的数据结构例如既可以是在上述文献1、2中列举出的数据结构，也可以是在树结构中对共同前缀进行汇集，在边缘保持了出现次数的数据结构。
75.接着步骤s102，cpu11开始读入新的轨迹的处理。首先，cpu11设定新读入的模式的数量n，将变量n设定为0(步骤s103)。
76.接着步骤s103，cpu11判断变量n是否为与所提取出的模式进行匹配的行程的个数n以下(步骤s104)。
77.步骤s104的判断结果，若n≤n(步骤s104；是)，则接下来cpu11相对于在步骤s102中保存的预定的数据结构，根据模式更新装置10新取得了的路径信息对模式进行对照(步骤s105)。
78.接着步骤s105，cpu11基于在步骤s105中的对照，对在步骤s102中保存了的预定的数据结构进行更新，由此对在包含模式更新装置10新取得的路径信息的全部路径信息中频繁出现的模式进行更新(步骤s106)。
79.接着步骤s106，cpu11判断是否仍然存在读入的行程(步骤s107)。若仍然存在读入的行程(步骤s107；是)，则cpu11接着对变量n增加一个(步骤s108)，返回步骤s104的判断。若没有读入的行程(步骤s107；否)，则cpu11结束一序列的处理。
80.另一方面，步骤s104的判断结果是，若n＞n(步骤s104；否)，则cpu11返回步骤s101。
81.模式更新装置10通过执行图4所示的一系列处理，从车辆的行驶数据的位置信息(gps等)中提取频繁出现的轨迹的模式，在取得了新的位置信息时高效地进行与模式的匹配，对频繁出现的模式进行更新。模式更新装置10通过高效地进行与模式的匹配，对频繁出现的模式进行更新，能够减轻处理负荷。
82.虽然在模式更新装置10的内部设置有储存器14，但本公开并不限定于该例。
83.此外，也可以由cpu以外的各种处理器执行在上述各实施方式中cpu对软件(程序)进行了读入并执行的模式更新处理。作为该情况下的处理器，可例示fpga(field－programmable gate array，现场可编程门阵列)等的能够在制造后改变电路结构的pld(programmable logic device，可编程逻辑器件)以及asic(application specific integrated circuit，专用集成电路)等的作为具有为了执行特定处理而专用地设计的电路结构的处理器的专用电路等。另外，对于模式更新处理，既可以用这些各种处理器中的一个进行执行，也可以用同种或者不同种的两个以上的处理器的组合(例如多个fpga以及cpu与fpga的组合等)进行执行。另外，这些各种处理器的硬件的构造更详细而言，为使半导体元件等电路元件进行了组合后的电路。
84.另外，在上述各实施方式中，对模式更新处理的程序预先存储(安装)于rom或者储存器的技术方案进行了说明，但不限定于此。程序也可以以记录于cd－rom(compact disk read only memory，光盘只读存储器)、dvd－rom(digital versatile disk read only memory，数字多功能光盘只读存储器)以及usb(universal serial bus，通用串行总线)存储器等非瞬时性(non－transitory)记录介质的方式被提供。另外，程序也可以是经由网络被从外部装置下载的方式。

技术特征：

1.一种模式更新装置，包括：存储器；和处理器，其连接于所述存储器，所述处理器构成为：从多个路径信息中提取频繁出现的模式，将所提取出的模式作为预定的数据结构而保存，将新取得的路径信息与所保存的预定的数据结构进行对照，基于对照，对所保存的所述预定的数据结构进行更新，由此对在包含新取得的路径信息的全部路径信息中频繁出现的模式进行更新。2.根据权利要求1所述的模式更新装置，所述处理器构成为：提取超过了设定次数的路径信息来作为频繁出现的模式，所述设定次数被设定为比希望取得的频繁出现模式的出现频度少。3.根据权利要求1所述的模式更新装置，所述处理器构成为：使通过对照而新成为了频繁出现的模式的模式适合于所述数据结构而保存。4.根据权利要求1所述的模式更新装置，所述数据结构是在树结构中对共同前缀进行汇集，在边缘保持了出现次数的数据结构。5.一种模式更新方法，通过处理器，从多个路径信息中提取频繁出现的模式，将所提取出的模式作为预定的数据结构而保存，将新取得的路径信息与所保存的预定的数据结构进行对照，基于对照，对所保存的所述预定的数据结构进行更新，由此对在包含新取得的路径信息的全部路径信息中频繁出现的模式进行更新。6.根据权利要求5所述的模式更新方法，通过所述处理器，提取超过了设定次数的路径信息来作为频繁出现的模式，所述设定次数被设定为比希望取得的频繁出现模式的出现频度少。7.根据权利要求5所述的模式更新方法，通过所述处理器，使通过对照而新成为了频繁出现的模式的模式适合于所述数据结构而保存。8.根据权利要求5所述的模式更新方法，所述数据结构是在树结构中对共同前缀进行汇集，在边缘保持了出现次数的数据结构。9.一种计算机可读取非瞬时性记录介质，保存有程序，所述程序使计算机执行如下处理：从多个路径信息中提取频繁出现的模式，将所提取出的模式作为预定的数据结构而保存，将新取得的路径信息与所保存的预定的数据结构进行对照，
基于对照，对所保存的所述预定的数据结构进行更新，由此对在包含新取得的路径信息的全部路径信息中频繁出现的模式进行更新。10.根据权利要求9所述的计算机可读取非瞬时性记录介质，提取超过了设定次数的路径信息来作为频繁出现的模式，所述设定次数被设定为比希望取得的频繁出现模式的出现频度少。11.根据权利要求9所述的计算机可读取非瞬时性记录介质，使通过对照而新成为了频繁出现的模式的模式适合于所述数据结构而保存。12.根据权利要求9所述的计算机可读取非瞬时性记录介质，所述数据结构是在树结构中对共同前缀进行汇集，在边缘保持了出现次数的数据结构。

技术总结

提供一种模式更新装置、模式更新方法以及非瞬时性的计算机可读记录介质。模式更新装置从多个路径信息提取频繁出现的模式，将所提取出的模式作为预定的数据结构来进行保存，相对于所保存的预定的数据结构，对新取得的路径信息进行对照，通过基于对照来对所保存的所述预定的数据结构进行更新，从而对在包含新取得的路径信息的全部路径信息中频繁出现的模式进行更新。行更新。行更新。