JP7776064B2 - Periodic neighborhood pattern detection device, periodic neighborhood pattern detection program, and periodic neighborhood pattern detection method - Google Patents

Description

The present invention relates to a periodic neighborhood pattern detection device, a periodic neighborhood pattern detection program, and a periodic neighborhood pattern detection method.

Mining periodic patterns is an important model in data mining with many real-world applications. It discovers all patterns occurring at regular intervals in data. A classic use case is market basket analysis, analyzing how regularly a set of items is purchased by customers. An example of a periodic pattern is a pattern of bat and ball combinations that 5% of customers purchase at least once every hour. The predicted behavior of customer purchases can be useful for users in product recommendations and inventory management.

R. Uday Kiran; C. Saideep; Koji Zettsu; Masashi Toyoda; Masaru Kitsuregawa; P. Krishna Reddy, : Discovering Partial Periodic Spatial Patterns in Spatiotemporal Databases, 9-12 Dec. 2019, 2019 IEEE International Conference on Big Data (Big Data) Kiran, R.U., Shang, H., Toyoda, M., Kitsuregawa, M.: Discovering partial periodic itemsets in temporal databases. In: SSDBM. pp. 30:1{30:6 (2017) Gowtham Atluri, Anuj Karpatne, Vipin Kumar, : Spatio-Temporal Data Mining: A Survey of Problems and Methods, ACM Computing Surveys, Vol. 1, No. 1, Article. Publication date: November 2017. Nikos Mamoulis, Huiping Cao, George Kolliso, Marios Hadjieleftheriou, Yufei Tao, David W. Cheung, : Mining, indexing, and querying historical spatiotemporal data, Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Seattle, Washington, USA, August 22-25, 2004

However, the widespread adoption and successful industrial application of periodic pattern models to find periodic patterns has the following problem: the basic model of periodic patterns considers the temporal occurrence information of items in the data, but does not consider the spatial characteristics of the items in the data. As a result, the periodic pattern model cannot discover interesting periodic patterns of multiple items that are close to each other in a coordinate system (hereinafter referred to as periodic neighborhood patterns).

Therefore, the object of the first aspect of this embodiment is to provide a periodic neighborhood pattern detection device, a periodic neighborhood pattern detection program, and a periodic neighborhood pattern detection method for detecting periodic neighborhood patterns.

A first aspect of the present embodiment is a system including a processor and a memory accessed by the processor, wherein the processor:
extracting patterns including specific items, which are items having predetermined attributes for each timestamp, from a plurality of items each having coordinate information, and generating a time database in which the timestamps are associated with patterns including the specific items;
From a plurality of patterns to be determined including all combinations of a plurality of specific items in the time database,
(1) determining whether the maximum distance between specific items in the pattern to be determined is equal to or less than a reference distance;
(2) determining whether the periodic support of the pattern to be determined is equal to or greater than a reference periodic support value;
(3) performing a process of detecting periodic neighborhood patterns that satisfy a relative periodic support determination of whether the relative periodic support of the target pattern is equal to or greater than a reference relative periodic support value;
the periodic support is the number of short inter-occurrence times equal to or less than a reference inter-occurrence time among the inter-occurrence times between adjacent timestamps at which the pattern to be determined occurs in the temporal database, or the number of short inter-occurrence times normalized by the number of occurrence times between adjacent timestamps in the temporal database;
The relative periodic support is the number of short inter-occurrence times normalized by the minimum number of occurrences in the temporal database of items included in the pattern being determined.

According to the first aspect, periodic neighborhood patterns can be detected.

FIG. 1 illustrates an example of the configuration of a periodic neighborhood pattern detection device. FIG. 4 is a flowchart illustrating an outline of processing of a PNP detection model in the present embodiment. FIG. 3 is a flowchart showing the process of step S4 in FIG. 2. FIG. 4 is a flowchart showing the process of step S14 in FIG. 3. 10 is a diagram showing a spatial database SD and specific examples and formulas of neighborhood items Ni _j . FIG. FIG. 10 is a diagram showing a specific example of the time database TDB of Table_3. FIG. 10 is a diagram showing a specific example of an inter-occurrence time. FIG. 8 is a diagram showing an example in which all combinations of items a, b, c, d, e, f, and g in the temporal database TDB of FIG. 7 are sorted in descending order of the number of items. FIG. 4 is a diagram showing a specific example of process S10 in FIG. 3. FIG. 10 is a diagram illustrating an example of an enumeration tree of item patterns (patterns to be determined) in the time database TDB_1. FIG. 1 shows an example of the distribution and three classes of data generated by a real-world application.

This embodiment is a model for detecting periodic neighborhood patterns (hereinafter referred to as PNPs: Periodic Neighborhood Patterns) that exist in spatiotemporal databases. Before describing the model for detecting PNPs, we will explain an application that motivates finding PNPs in spatiotemporal databases.

Air pollution is a major factor in many cardiorespiratory problems experienced by people living in Japan. To address air pollution, the Ministry of the Environment has launched the Atmospheric Environmental Regional Observation System (AEROS). This system consists of multiple air pollution measurement sensors located throughout Japan. The data generated by these sensors is a spatiotemporal database. PNP generated from this spatiotemporal database provides useful information about locations or areas where people are regularly exposed to unhealthy levels of pollution. This information can be very useful to ecologists when devising environmental and public health policies. In general, data generated by sensors and other devices in IoT devices naturally exists as a spatiotemporal database. In this embodiment, both the spatial and temporal characteristics of the sensors (hereinafter referred to as items) are taken into account to detect combination patterns of interesting items in such a database.

Figure 1 shows an example configuration of a periodic neighborhood pattern detection device. The PNP detection device 1 is a supercomputer, server, personal computer, tablet terminal, smartphone, etc. The PNP detection device 1 has a processor 10, main memory 12, external interface 14, storage 20, and a bus 16 connecting these. The external interface 14 allows connection to multiple items 32, such as IoT sensors, that send measurement data to the PNP detection device 1, and multiple client terminals 30 that request PNP detection from the PNP detection device 1.

Storage 20 stores a PNP detection program 21 and a spatiotemporal database 22. The spatiotemporal database 22 includes, for example, a spatial database (Spatial DB) 23 and a temporal database (Temporal DB) 25. A neighbors database (Neighbors DB) 24 may also be stored in the storage. These databases will be described in more detail later.

[Outline of PNP detection model]
2 is a flowchart showing the general processing of the PNP detection model in this embodiment. The PNP detection model is a processor 10 that executes a PNP detection program 21. The processor 10 executes the PNP detection program 21 and generates a spatiotemporal database 22 from a database 26 (S1 to S3). The database 26 contains, for example, data measured by multiple air pollution measurement sensors located throughout Japan, and the measurement data has attribute information such as the location information of the sensor that made the measurement and the time information of the measurement. Hereinafter, sensors will be referred to as items.

First, the processor generates a spatial database (SD), which is one of the spatiotemporal databases 22, from the database 26 (S1). The spatial database SD contains position information for each item (sensor). A specific example of the spatial database (Table_1) will be described later. Furthermore, the processor extracts nearby items _Nij that correspond to a certain item _ij and a nearby item whose position (coordinates) is close to the item ij. A specific example (Table_2) will be described later.

Next, the processor extracts from the database 26 all transactions that contain items for which a predetermined value has been detected for each timestamp, and generates a temporal database (TDB) (S3). Here, an item for which a predetermined value, such as a dangerous contamination value, has been detected is referred to as a specific item that has reached a predetermined state or has a predetermined attribute. A specific example of a temporal database (Table 3) will be described later.

The processor then detects pattern X, which is a combination of items that satisfies the following conditions, from specific items in the temporal database TDB. This detected pattern X is a periodic neighborhood pattern. The conditions are as follows:

Condition (1) is that the periodic support of the pattern is greater than or equal to the reference value minPS. Here, support represents frequency or relative frequency. Condition (2) is that the relative periodic support of the pattern is greater than or equal to the reference value minRPS. Periodic support and relative periodic support will be explained in detail later. Condition (3) is that the maximum distance between any pair of items in the pattern is less than or equal to the reference distance maxDist. In other words, all items in the pattern are located near each other.

Below, we will explain the terms used in Figure 2, and then provide a detailed description of the periodic neighborhood pattern detection model used in this embodiment.

[Spatial database SD, neighboring items Ni _j , temporal database TDB]
Next, the spatial database SD, the neighborhood items NB, and the time database TDB will be explained. Figure 5 shows specific examples and formulas of the spatial database SD and the neighborhood items Ni _j .

Definition 1: A spatial database
First, let I be a geometric or spatial collection of items.

Let Pi _j be the set of coordinates of item i _j , which is an element of set I of items.

This spatial database SD is a collection of items and their associated spatial information (item i _j , coordinate Pi _j ) as follows:

The above concept of a spatial database SD allows us to understand that items can also be of geometric form, such as points, lines, and polygons.

S = {abcdefg} is a set of sensors (items) that measure air pollution on the Earth's surface. The spatial database of these items is shown in Table_1.

Definition 2: A neighborhood distance function
Given a distance function Dist(), two items i _p and i _q of elements of set I are said to be neighbors of each other if the following is satisfied:

where maxDist is a user-specified maximum distance threshold. Dist() is a distance function with the commutative property. Examples of distance functions with this property are the Euclidean distance and the Geodic distance functions. Let Ni _j be the set of all neighbors of item i _j of an element of I.

If Euclidean distance is the distance function mentioned above, then the distance between items a and c, i.e., Dist(a,c) = 1.414. If the user-specified threshold is maxDist = 1.5, then items a and c are neighbors of each other because Dist(a,c) = < maxDist. Similarly, items d and e are neighbors of item a. Therefore, Na = {cde}. A list of neighboring items for each item in Table_1 is shown in Table_2 in Figure 5.

Definition 3: Neighborhood pattern
Let X be a subset of an item set I. If X contains k items, it is called a k-pattern. A pattern X in the spatial database SD is called a neighborhood pattern if the maximum distance between any pair of items in X is less than or equal to a user-specified threshold, maxDist. That is, X is a neighborhood pattern if the following is true:

The set of items a and c, i.e., ac, is a pattern, and this pattern contains two items. Therefore, it is a two-pattern pattern. Pattern ac is called a neighborhood pattern because its distance is less than or equal to maxDist. Conversely, abc, a proper subset of ac, is not a neighborhood pattern because the maximum value of the distances between the three pairs of items (distance between ab, distance between ac, distance between bc) is greater than maxDist.

Definition 4: A temporal database
6 is a diagram showing a specific example of the time database TDB of Table_3. The time database TDB is a set of transactions having a transaction ID t _tid , a timestamp ts, and an item pattern Y. The transactions t _tid are as follows:

The time database TDB is a set of transactions ordered by timestamp ts, as follows:

A hypothetical temporal database generated by the sensors (items) in Table_1 is shown in Table_3. The first transaction in this table provides information that stations a, c, and d recorded dangerous amounts of air pollution at each timestamp. Similar information is generated for the remaining transactions in Table_3. The size of the temporal database is m = |TDB| = 14.

Definition 5: The support of pattern X
A pattern X is said to occur in transaction t _tid if X is contained in pattern Y such that (X=subset containing Y), and the timestamp of this transaction is ts ^X _tid .

Let TS ^X below be referred to as the set of all timestamps at which pattern X occurs (appears) in the database.

The support of pattern X in the TDB is denoted as sup(X), which represents the number of transactions that contain pattern X in the TDB. That is,
sup(X) = |TS ^X |
The support of X is also expressed as a percentage of the data size, i.e., sup(X) = |TS ^X |*100/|TDB|.

In Table_3, the neighborhood pattern ac appears in transactions with timestamps 1, 3, 4, 12, 13, 15, and 16. Therefore,
TS ^ac = {1, 3, 4, 12, 13, 15, 16}
The support of ac is sup(ac) = |TS ^X | = 7
In Table_3, TSa, TSc, TSac, sup(a), sup(c), and sup(ac) are as follows:

Definition 6: A periodic occurrence of pattern X
Hereinafter, this will be referred to as any two consecutive timestamps in TS ^X.

The time difference between ts ^x _k and ts ^x _j is called an inter-arrival time of X, and is denoted as iat ^X. That is, it is as follows.
iat ^X = ts ^x _k - ts ^x _j
Let the following be the set of all inter-occurrence times of pattern X in the TDB:

Pattern X is said to be periodic if its inter-occurrence time is less than or equal to a user-specified maximum inter-occurrence time (maxIAT). That is,

This will be explained using a specific example. Figure 7 shows a specific example of inter-occurrence time. In the spatial pattern ac, transactions with timestamps ts of 1 and 3 appeared consecutively. The time difference between these two timestamps is the inter-occurrence time of ac. In other words,
iat ^ac ₁ = 3 - 1 = 2
iat ^ac ₂ = 4 - 3 = 1
iat ^ac ₃ = 12 - 4 = 8
iat ^ac ₄ = 13 - 12 = 1
iat ^ac ₅ = 15 - 13 = 2
iat ^ac ₆ = 16 - 15 = 1
Therefore, the set of all inter-occurrence times of ac in Table_3 is:
IAT ^ac = {2, 1, 8, 1, 2, 1}
In the above, when the user-specific maxITA = 2, iat ^ac ₁ , iat ^ac ₂ , iat ^ac ₄ , iat ^ac ₅ , iat ^ac ₆ are considered to be periodic occurrences (appearances) of ac in the data. On the other hand, since iat ^ac ₃ is not equal to or less than the user-specific maxITA, iat ^ac ₃ is not considered to be a periodic occurrence (appearance) of ac in the data.

Definition 7: Periodic-support of pattern X
Let IIAT ^X be the set of all inter-occurrence times (short inter-occurrence times) with a value less than or equal to maxIAT.

The above means that if there exists an element iat ^X _k of IAT ^X that satisfies iat ^X _k =<maxIAT, then it is an element iat ^X of IIAT ^X with a short inter-occurrence time.

The periodic support of pattern X is denoted as PS(X) below.

where |TDB| - 1 is the maximum number of inter-occurrence times of a certain pattern contained in the time database TDB. For example, in the example shown in Figure 7, IIAT ^ac = {2, 1, 1, 2, 1}, so |IIAT ^ac | = 5 and |TDB| = 13, and PS(ac) = 5 or 5/13 = 0.385 (38.5%) as follows.

The periodic support of pattern X is difficult to determine in real-world applications unless it is normalized. Normalized periodic support is divided by (database size - 1). That is, normalized periodic support is the ratio of the number of short inter-occurrence times |IIAT ^X | of pattern X to the number of inter-occurrence times of all transactions in the temporal database (|TDB| - 1). However, if the support (number of occurrences) sup(X) of pattern X is several times smaller than the temporal database size |TDB|, the normalized periodic support is not useful. In other words, it does not satisfy the null invariance property. Therefore, we normalize the periodic support of pattern X, |IIAT ^X |, by the number of inter-occurrence times of the items and call this measure relative periodic support as follows:

Definition 8: Relative Periodic-support of pattern X (RPS(X))
The relative cyclic support RPS(X) of pattern X is:

Here, the denominator represents the total number of inter-occurrence times for the least frequently occurring item in pattern X. If pattern X is a pattern of items a and c, the denominator is the number of inter-occurrence times for items a and c, which occur the least frequently (least frequently).

For the specific example in Figure 7, the RPS(ac) for patterns a and c are as follows:

Since the relative periodic support measure normalizes the periodic support of a pattern by the number of items, such a measure can help users effectively detect frequently and rarely occurring items. Furthermore, this measure satisfies the null invariant property. This property means that null transactions, which are transactions that do not contain the target pattern, do not change the interestingness of the pattern in the database. For example, RPS(ac) will remain the same even if someone maliciously adds millions of fake transactions that do not contain the pattern ac.

Definition 9: Periodic neighborhood pattern X (PNP)
A neighborhood pattern X is called a periodic neighborhood pattern if it satisfies the following:
PS(X) >= minPS and RPS(X) >= minRPS
where minPS and minRPS are the user-specified minimum periodic support and minimum relative periodic support. For periodic support PS(X), the minPS constraint can be used to filter out noisy patterns (or patterns with very few periodic occurrences) in the data.

To illustrate this concrete example, if a user-specified minPS is minPS = 2.8% (i.e., the pattern must occur periodically at least twice within the temporal database) and minRPS = 60% (i.e., the pattern must occur at least 60% of the times the least frequently occurring item in the pattern occurs), then pattern ac is called a periodic neighborhood pattern because PS(ac) >= minPS and RPS(ac) >= minRPS. This pattern ac provides useful information that people living near sensors a and c are periodically exposed to high levels of air pollution. As such, such information may be very useful to users, such as environmentalists and policy makers, for formulating appropriate policies to reduce air pollution.

PS(X) ≥ minPS is the ratio of the number of short inter-occurrence times |IIAT ^X | of pattern X less than maxIAT to the number of inter-occurrence times of all transactions in the database (|TDB| - 1), which filters out noise that occurs very rarely in the database. On the other hand, RPS(X) ≥ minRPS is the ratio of the number of short inter-occurrence times |IIAT ^X | to the support of the minimum frequent item in the pattern, which detects patterns that contain frequent and rare items in the database.

Given a set of items I, a spatial database SD, a temporal database TDB, a maximum inter-occurrence time maxIAT, a minimum periodic support minPS, a minimum relative periodic support minRPS, and a maximum distance maxDist, a periodic neighborhood pattern PNP can be detected by finding all patterns in the temporal database TDB that satisfy the following three constraints:
(i) The distance between all items in the pattern is less than or equal to maxDist.
(ii) The periodic support PS of the pattern is greater than or equal to minPS.
(iii) The relative periodic support RPS of the pattern is greater than or equal to minRPS.

The PNPs generated by the model of this embodiment satisfy the null invariance property and the convertible anti-monotonic property, which are described in the following non-patent literature:
Pei, J., Han, J.: Can we push more constraints into frequent pattern mining? In:
SIGKDD. pp. 350-354 (2000)
Tan, PN, Kumar, V., Srivastava, J.: Selecting the right interestingness measure for association patterns. In: SIGKDD. pp. 32{41 (2002)
The time between occurrences of a pattern may be expressed as a percentage of the difference ts _max - ts _min between the maximum timestamp ts _max and the minimum timestamp ts _min .

Now that various terms have been explained above, the periodic neighborhood pattern detection model of this embodiment will be described in detail. An overview of the periodic neighborhood pattern detection model has already been explained in Figure 2. The processor 10 in Figure 1 executes a periodic neighborhood pattern (PNP) mining (detection) program 21 to detect periodic neighborhood patterns in a spatiotemporal database 22. The processor that executes the PNP detection program is the periodic neighborhood pattern detection model.

3 is a flowchart showing the process of step S4 in FIG. 2. The processor of the PNP detection model
(1) Scan the temporal database TDB and sort all items in TDB in descending order of item support sup(item);
(2) Delete items whose periodic support PS(item) is PS(item) < minPS from the items in the time database;
(3) An enumeration tree of combination patterns of the remaining items is generated (S10).

FIG. 8 shows an example of all combinations of items a, b, c, d, e, f, and g in the temporal database TDB shown in FIG. 7 sorted in descending order of the number of items. Each transaction in the temporal database TDB contains a pattern of sensors (items) that measured air pollution at a predetermined concentration or higher. FIG. 8 shows all combinations of elements (items) in set I (items a, b, c, d, e, f, and g) included in this pattern, sorted in descending order of the number of elements. In this case, the number of patterns is as large as 2 ⁿ -1 (n is the number of items). Therefore, the number of patterns to be judged in the PNP detection process S4 increases, reducing the efficiency of the PNP detection process.

Figure 9 shows a specific example of process S10 in Figure 3. The processor (1) scans the time database TDB, sorts all items in the TDB in descending order of item support sup(item), and generates a management table 40 of item support sup(item) and periodic support PS(item) (S10(1)). In the management table 40, items I in the time database TDB are sorted in descending order of support sup(item) and Sup.

Therefore, the processor (2) deletes items whose cyclic support PS(item) is PS(item) < minPS( _item ) from the items in the temporal database (S10(2)). If minPS( _item) = 2 is set, items f and g are deleted. Items with low cyclic support PS(item) do not satisfy the above-mentioned constraint (ii) and are not judged as PNP. Therefore, deleting these items at this point can significantly reduce the number of patterns to be judged. For example, minPS( _item) = < minPS(X) (denormalized) is set.

This pre-determination PS(item)<minPS _item can significantly reduce the number of patterns to be determined from ²ⁿ -1 to ^2m -1 (where m is the number of items after deletion) by performing the pre-determination only n times (the number of items), thereby improving the efficiency of the PNP determination process.In the example of Figure 8, the number of items is reduced from 6 to 4, so the number of patterns to be determined is reduced from ^26-1 =64 to ^24-1 =16.

Next, the processor generates a virtual time database TDB_1 for each transaction pattern, with the remaining items sorted in ascending order . Furthermore, the processor generates an enumeration tree of patterns with the items sorted in ascending order in this virtual time database TDB_1 (S10(3)).

10 is a diagram showing an example of an enumeration tree of item patterns (patterns to be determined) in the temporal database TDB_1. The enumeration tree of patterns to be determined has a null node with no items as its root node, and its child nodes are nodes e, b, c, d, and a, which are patterns of one item. Its child nodes are nodes eb, ec, ed, ea, bc, bd, ba, cd, ca, and da, which are patterns of two items. Its child nodes are nodes ebc..., which are patterns of three items. Its child nodes are nodes ebca,..., which are patterns of four items. Its child nodes are nodes ebcda,..., which are patterns of five items. As described above, the enumeration tree of patterns to be determined is generated in ascending order of items I in the management table 40.

The PNP detection model scans the nodes of the enumeration tree depth-first and determines whether the item pattern at each node satisfies the three PNP constraints (S11 in Figure 3). The depth-first scan order is null node, e, eb, ebc, ebcd, ebcda, ebca... In other words, the processor prioritizes patterns that combine items with fewer sup(item)s to determine PNP.

The PNP detection model determines whether pattern X of the node being evaluated is (i) a neighborhood pattern (S13), (ii) whether the periodic support PS(X) is greater than or equal to the reference value minPS, and (iii) whether the relative periodic support RPS(X) is greater than or equal to the reference value minRPS (S14). If all three of these determinations are true (YES in S13 and S14), the PNP detection model determines that pattern X of the node being evaluated is PNP (S15). If any of these three determinations is false (NO in S13, NO in S14), the PNP detection model does not determine that pattern X of the node being evaluated is PNP.

The PNP detection model extracts the pattern X of the next node to be determined as follows:
(1) If both S13 and S14 are YES, extract the pattern X of the next node based on the depth-first algorithm.
(2) If either S13 or S14 is NO, the depth-first algorithm stops advancing to the next node, and pattern X of the node next to the parent node of the node that has already been evaluated is extracted. The reason why the depth-first search can be stopped is as follows: For the evaluation S13, the maximum inter-item distance does not decrease as the number of items in the pattern to be evaluated increases. For the evaluation S14, the number of short inter-occurrence times |IIAT ^X | in the numerators of PS(X) and RPS(X) does not increase as the number of items in the pattern to be evaluated increases. Furthermore, the denominator of PS(X) (|TDB| -1) and the denominator of RPS(X) (sup(e) for patterns containing e) are both constant. The above property that allows the search to be stopped is called the convertible ant-monotonic property.

According to (2) above, there is no need to determine whether the patterns of all nodes in the enumeration tree are PNP or not, so the PNP detection process can be carried out efficiently. Furthermore, according to (2), the search for the PNP detection process can be completed quickly. The reasons for this are as follows:

For example, for a pattern in a tree whose root node is the node of item e, the cyclic support PS(X) and relative cyclic support RPS(X) are as follows:
PS(X) = |IIAT ^X | or |IIAT ^X |/(|TDB|-1)
RPS(X) = |IIAT ^X |/(sup(e)-1)
As mentioned above, the denominators of both are constant. Also, in a depth-first algorithm, items with fewer sup(item) are prioritized as the number of pattern items increases. Therefore, the numerator |IIAT ^X | decreases as the number of items increases, and the initial rate of decrease is the fastest. As a result, the search within a subtree with a certain item as the root node stops early.

4 is a flowchart of the process S14 in FIG. 3. The processor, which is a PNP detection model, generates a set IAT ^X of times i at between timestamps ts of consecutive transactions tid that include pattern X in the time database TDB (inter-occurrence times i at) (S21). Next, the processor generates a set IITA ^X (a set of short inter-occurrence times) of only the inter-occurrence times i at ^X _X that are less than maxIAT among the elements i at of the inter-occurrence time set IATX.

7 shows a specific example of an inter-occurrence time set IAT ^ac of a transaction including pattern ac and a short inter-occurrence time set IIAT ^ac . In this case, maxIAT=2 is set.

Therefore, the processor calculates the ratio of the number |IITA ^X | of short inter-occurrence time sets IITA ^X to the maximum number of inter-occurrence times ita in the temporal database TDB (|TDB|-1) as the cyclic support PS(X) of pattern X (S23). Alternatively, PS(X) = |IITA ^X | may be used. Furthermore, the processor calculates the ratio of the number |IITA ^X | of short inter-occurrence time sets IITA ^X to the minimum number of occurrences of all items in pattern X (min(all sup(item))) as the relative cyclic support RPS(X) of pattern X (S24).

Figure 7 shows the formulas for the periodic support PS(X) and relative periodic support RPS(X) of pattern X, as well as specific examples of PS(ac) and RPS(ac) of pattern ac. As mentioned above, periodic support PS(X) is the ratio of the number of elements in the short inter-occurrence time set IITA ^X to the total number of transactions in the temporal database TDB. On the other hand, relative periodic support RPS(X) is the ratio of the number of elements in the short inter-occurrence time set to the minimum number of occurrences of items in pattern X.

The processor then determines whether the periodic support PS(X) is greater than or equal to the reference value minPS and whether the relative periodic support RPS(X) is greater than or equal to the reference value minRPS (S25). In the example of Figure 7, when minPS = 2 and minRPS = 60%, the periodic support PS(ac) = 5 and the relative periodic support RPS(ac) = 71.4%, so the processor determines that pattern ac satisfies both conditions. As a result, the processor detects pattern ac as a periodic neighborhood pattern.

[PS(X) >= minPS, RPS(X) >= minRPS]
Figure 11 shows an example of the distribution of data generated by a real-world application and three classes. The vertical axis shows the support of an item, and the horizontal axis shows the number of items sorted based on the support.

Data generated by real-world applications has an exponential distribution of item support, as shown in Figure 11. Thus, items in a real-world database can be roughly categorized into three classes: frequent items, rare items, and infrequent/noisy items. Figure 11 shows the distribution and classification of items in a fictitious or imaginary application. The classification of frequent, rare, and infrequent/noisy items is subjective, depending on the user and the application.

In many real-world applications, users are interested in finding knowledge about frequent and rare items. However, finding knowledge about rare items is very difficult because they occur only a small number of times in the database. The goal of relative periodicity support is to discover knowledge about frequent and rare items.

The cyclical support measure is absolute because it determines the interest of a pattern without considering the support of the items. This measure states that patterns with higher cyclical support are more interesting than patterns with relatively low cyclical support. Thus, this measure favors items that occur frequently. Because cyclical patterns often have low cyclical support values, this cyclical support measure often prunes (excludes) cyclical patterns that contain rare items.

Example 1:
In the temporal database TDB shown in Figures 6 and 7, item a is a frequent item, while item c is a rare item. The periodic support PS(ac) of pattern ac is 5/19 = 26%. The periodic support indicates that pattern ac is an uninteresting pattern because its periodic support PS(ac) is less than 50%. The periodic support measure is problematic because it does not consider the number of items supported within the pattern.

The relative periodic support measure in this embodiment determines the interestingness of a pattern by taking into account the support count of items in the pattern. If a pattern contains only frequent items, the relative periodic support measure ensures that the pattern has high periodic support. If a pattern contains rare items, the relative periodic support measure ensures that the pattern may have relatively low periodic support.

In the temporal database Table_3 in Figure 6, the top two most frequent items a and d have support sup(a) = 11 and sup(d) = 9. If minRPS = 60%, then pattern a can be a periodic neighborhood pattern PNP if:
PS(ad)/(sup(d)-1) >= 60/100
Therefore, the periodic support PS(ad) is:
PS(ad) >= 60*(sup(d)-1)/100 = (60*8)/100 = 4.8
On the other hand, item e has low frequency sup(e) = 4. Pattern ae can be PNP if:
PS(ae)/(sup(e)-1) >= 60/100
Therefore, the periodic support PS(ae) is:
PS(ae) >= 60*(sup(e)-1)/100 = (60*3)/100 = 2
Thus, the measure of relative periodic support ensures that patterns containing frequent items should occur more periodically in the data, while patterns containing rare items may occur less periodically in the data.

Example 2:
If an item occurs n times, there are n-1 inter-occurrence times. In the temporal database TDB shown in Figures 6 and 7, item a occurs 11 times. This means that item a has 10 inter-occurrence times. Similarly, item c occurs 8 times in the TDB, resulting in 7 inter-occurrence times. The maximum number of times that both items a and c can occur in the TDB is minimum(11,8) = 8. This means that the maximum number of inter-occurrence times that can exist in pattern ac is 8 - 1 = 7. In terms of relative periodic support, out of the 7 inter-occurrence times for item c, item a periodically occurs with item c for 5 inter-occurrence times. If all inter-occurrence times are short inter-occurrence times, the relative periodic support for pattern ac is 5/7 = 71.4%, which is 71.4% of the inter-occurrence times. This means that item a periodically occurs with item c in the temporal database. Therefore, pattern ac is a pattern of interest to the user.

The cyclical support measure considers all transactions in a temporal database to determine whether a pattern is interesting. On the other hand, the relative cyclical support measure considers only transactions that contain any of the pattern's items to determine whether a pattern is interesting. Relative cyclical support does not consider transactions that do not contain any of the pattern's items (null transactions). This is why it is called the null-invariant property, and it is very useful in real-world applications.

In step S14 of Figure 3, the processor, which is a PNP detection model, determines whether PS(X) >= minPS and RPS(X) >= minPS(X). The former means that the number or percentage of short inter-occurrence times of pattern X is greater than or equal to minPS, eliminating noise-like patterns with a small number of short inter-occurrence times. On the other hand, the latter is the ratio of the number of short inter-occurrence times of pattern X to the number of occurrences of the least frequent item. The number of occurrences of the least frequent item of pattern X, which is the denominator of RPS(X), corresponds to the maximum possible number of short inter-occurrence times of pattern X. Therefore, RPS(X) indicates the ratio of the actual number of inter-occurrence times to the maximum possible number of short inter-occurrence times of pattern X.

For pattern X, there exists a pattern X that does not satisfy PS(X) >= minPS, but does satisfy RPS(X) >= minPS(X). This pattern contains very infrequent, noise-like items. Therefore, even if RPS(X) >= minPS(X), this pattern X is uninteresting. A pattern that satisfies both PS(X) >= minPS and RPS(X) >= minPS(X) is an interesting pattern. RPS(X) >= minPS(X) is used to filter out uninteresting patterns that contain frequently occurring items with low periodic support.

[Other examples of spatiotemporal databases]
In the above embodiment, a spatiotemporal database of a sensor that measures dangerous values of air pollution has been described as an example. Another example is a spatiotemporal database of a sensor that periodically identifies areas with low rainfall and drought conditions. The PNP detection model can also be applied to a spatiotemporal database of a sensor that detects pollen levels, a sensor that detects the number of people outside, and so on.

As explained above, according to this embodiment, the PNP detection model detects as interesting periodic neighborhood patterns (PNPs) in the spatio-temporal database patterns that satisfy all of the following: the maximum distance between all item pairs in the pattern is equal to or greater than a reference distance, the periodic support of the pattern is equal to or greater than a reference periodic support value, and the relative periodic support of the pattern is equal to or greater than a reference relative periodic support value. This makes it possible to detect combinations of items that are located nearby and periodically enter a specific state with a high frequency.

SD: Spatial Database
Dist: Neighborhood distance function
X: Pattern, Neighborhood Pattern
TDB: Time database | TDB |: Number of transactions in the time database
TS ^X : A set of timestamps for pattern X
iat, IAT: Inter-occurrence time
sup(X): Support (frequency) of pattern X
IAT ^X : Set of inter-occurrence times iat of pattern X | IAT ^X |: Number of inter-occurrence times in the set of inter-occurrence times iat of pattern X | IIAT ^X |: Number of short inter-occurrence times in the set of inter-occurrence times iat (short inter-occurrence times) less than maxIAT of pattern X
PS(X): Periodic support of pattern X, |IIAT ^X | or |IIAT ^X |/(|TDB|-1)
RPS(X): Relative cyclic support of pattern X, |IIAT ^X |/(min sup(item) of items in X)
PNP: Periodic Neighborhood Pattern

Claims (5)

a processor;
a memory accessed by the processor;
the processor:
extracting patterns including specific items, which are items having predetermined attributes for each timestamp, from a plurality of items each having coordinate information, and generating a time database in which the timestamps are associated with patterns including the specific items;
From a plurality of patterns to be determined including all combinations of a plurality of specific items in the time database,
(1) The pattern to be judged is a neighboring pattern in which the maximum distance between specific items in the pattern to be judged is equal to or less than a reference distance;
(2) the periodic support of the pattern to be determined is equal to or greater than a reference periodic support ;
(3) the relative periodic support of the pattern to be judged is equal to or greater than a reference relative periodic support;
and performing a process to detect periodic neighborhood patterns that satisfy
the periodic support is the number of inter-occurrence times between adjacent timestamps at which the pattern to be determined occurs in the temporal database that are equal to or less than a reference inter-occurrence time, or the number of inter-occurrence times that are equal to or less than the reference inter-occurrence time normalized by the number of occurrence times between adjacent timestamps in the temporal database;
A periodic neighborhood pattern detection device, wherein the relative periodic support is the number of inter- occurrence times less than the reference inter-occurrence time normalized by the number of inter-occurrence times of a specific item that has occurred the smallest number of times in the temporal database among the specific items included in the pattern to be determined. The process of detecting the periodic neighborhood pattern includes:
generating an enumeration tree having the plurality of patterns to be determined from the specific items in the time database, the enumeration tree having a null root node and a plurality of child nodes in which the number of the specific items increases in a depth direction;
searching for patterns to be determined in a plurality of child nodes of the enumeration tree from the root node using a depth-first algorithm to determine whether or not the patterns are periodic neighborhood patterns;
2. The periodic neighborhood pattern detection device according to claim 1, wherein once it is determined that the pattern to be determined is not the periodic neighborhood pattern, the search for the next child node of the child node is stopped, and a determination is made as to whether the pattern to be determined of the next node of the parent node of the child node is the periodic neighborhood pattern. The processor further includes, in the process of detecting the periodic neighborhood pattern,
generating a reduced time database by removing from the specific items in the time database those specific items whose cyclic support is less than a second reference cyclic support ;
3. The apparatus for detecting periodic neighborhood patterns according to claim 2, wherein an enumeration tree is generated having a plurality of patterns to be determined having the specific items remaining in the reduced temporal database in an order sorted in ascending order of support in the temporal database for the specific items remaining in the reduced temporal database. extracting patterns including specific items, which are items having predetermined attributes for each timestamp, from a plurality of items each having coordinate information, and generating a time database in which the timestamps are associated with patterns including the specific items;
From a plurality of patterns to be determined including all combinations of a plurality of specific items in the time database,
(1) The pattern to be judged is a neighboring pattern in which the maximum distance between specific items in the pattern to be judged is equal to or less than a reference distance;
(2) the periodic support of the pattern to be determined is equal to or greater than a reference periodic support ;
(3) the relative periodic support of the pattern to be judged is equal to or greater than a reference relative periodic support;
detecting a periodic neighborhood pattern satisfying
the periodic support is the number of inter-occurrence times between adjacent timestamps at which the pattern to be determined occurs in the temporal database that are equal to or less than a reference inter-occurrence time, or the number of inter-occurrence times that are equal to or less than the reference inter-occurrence time normalized by the number of occurrence times between adjacent timestamps in the temporal database;
A periodic neighborhood pattern detection program, wherein the relative periodic support is the number of inter- occurrence times that are less than the reference inter-occurrence time, normalized by the number of inter-occurrence times of a specific item that has occurred the smallest number of times in the time database among the specific items included in the pattern to be determined. extracting patterns including specific items, which are items having predetermined attributes for each timestamp, from a plurality of items each having coordinate information, and generating a time database in which the timestamps are associated with patterns including the specific items;
From a plurality of patterns to be determined including all combinations of a plurality of specific items in the time database,
(1) The pattern to be judged is a neighboring pattern in which the maximum distance between specific items in the pattern to be judged is equal to or less than a reference distance;
(2) the periodic support of the pattern to be determined is equal to or greater than a reference periodic support ;
(3) the relative periodic support of the pattern to be judged is equal to or greater than a reference relative periodic support;
detecting a periodic neighborhood pattern satisfying
the periodic support is the number of inter-occurrence times between adjacent timestamps at which the pattern to be determined occurs in the temporal database that are equal to or less than a reference inter-occurrence time, or the number of inter-occurrence times that are equal to or less than the reference inter-occurrence time normalized by the number of occurrence times between adjacent timestamps in the temporal database;
A periodic neighborhood pattern detection method, wherein the relative periodic support is the number of inter- occurrence times less than the reference inter-occurrence time normalized by the number of inter-occurrence times of a specific item that has occurred the smallest number of times in the temporal database among the specific items included in the pattern to be determined.