TWI546686B - Progressive sequence data mining method and system with dynamic granularity and automatic labeling - Google Patents

Description

Progressive sequence data mining method and system with dynamic granularity and automatic labeling

A data exploration method, in particular, a progressive sequence data mining method and system with dynamic granularity and automatic labeling.

Previous exploration techniques for moving trajectory data used grids to describe geography. However, most of the prior art used fixed-size N×M grids to plan geospatial space. These techniques may encounter the following problems in practical applications: 1. The grid size and the cutting position of the grid are not easy to plan. If the grid is too large, some fine object movement information may be lost. If the grid is too small, the total number of grids will increase, and the latitude and longitude coordinates of the trajectory falling within the grid will be caused. Points become scarce, lose statistical significance, and thus lose some moving patterns; 2. Geospatial size and grid size directly determine the total number of grids, the total number of grids affects the computational complexity and the data analysis The required memory space; 3. The amount of data of the sequence data increases with time, so that the computational cost and time required for each exploration increase continuously, and eventually exceeds the upper limit of the load calculation of the hardware itself; and 4. Because of the trajectory Data mining technology has higher computational complexity and more prior art Half adopts the client/server model (client/servermodel), uploads the user's mobile track data to the server and performs the operation to return the result. However, in addition to increasing the cost of network communication, it increases the use. The risk of privacy exposure; 5. The exploration technology of the previous moving trajectory data is mostly calculated by the overall trajectory data, so when the moving habit of the object changes drastically, for example, the user suddenly moves or leaves the usual living circle in a short time. The results of the exploration are easily dominated by previous data, and it is not easy to quickly reflect the changes in behavior and affect the effectiveness of the exploration results.

In order to solve the problems existing in the prior art, the present invention provides a progressive sequence data mining method for dynamic granularity and automatic labeling, which comprises a first exploration stage and a second exploration stage, which establish a new accumulated important grid table and a A new cumulative probability tail tree, wherein the predicted sequence of data in the tail tree of the cumulative probability is generated in a moving track in a target space, wherein: the first exploration phase comprises the following steps: Step 1-1, New During the sampling period, the sequence data in the new sampling period is obtained, and the sequence data includes a plurality of basic data distributed in the target space; Step 1-2, performing a new grid hierarchy tree algorithm, according to a network Grid granularity, the target space is divided into a plurality of meshes, and each mesh corresponds to a mesh hierarchical tree node in the mesh hierarchical tree; steps 1-3, performing a mesh subdivision algorithm, according to each When the leaf node of a grid hierarchy tree corresponds to the number of the basic data contained in the grid is greater than a subdivision threshold, the grid is mesh-divided to make the grid order The leaf nodes of the layer tree correspondingly generate a plurality of child nodes, and the corresponding grid of the leaf nodes is defined as a candidate mesh; the new mesh hierarchical tree and the leaf nodes of the old accumulated mesh hierarchical tree having overlapping relationships and different granularities are adjusted a leaf node of the same granularity, and assigning the number of the basic data of the old leaf node to the plurality of newly generated leaf nodes, and allocating the number of the basic data of the leaf node to the plurality of leaf nodes; Step 1-4: Perform a mesh fusion algorithm, and determine, according to the number of the basic data recorded by the leaf nodes of the mesh tree, whether the candidate mesh corresponding to the leaf node is an important mesh Adjusting the size of the candidate mesh, and giving the important mesh label, all the important meshes form an important mesh table; the leaf nodes corresponding to the mesh that are not determined to be important mesh are performed with their sibling nodes Grid fusion; Step 1-5, generating the important grid label sequence data according to the important grid table, and expressing the important grid label sequence data in the sequence data in the new sampling period a time-order relationship between the important grid and the important grid; and steps 1-6, establishing a new probability tail tree in the new sampling period according to the important grid label sequence data, wherein the new probability tail tree Representing a set of the moving patterns presented by the important grid tag sequence data in the new sampling period; and each node in the probability tail tree represents a moving pattern, the moving pattern indicating that the sequence data passes through After the plurality of important meshes corresponding to the tag sequence included in the node, the conditional probability distribution of an important mesh is entered in the future; the second exploration phase includes the following steps: Step 2-1, merging the new mesh hierarchy The tree and the old accumulated grid hierarchy tree form a new accumulated grid hierarchy tree, and the new grid hierarchy tree and the corresponding grid of the same accumulated grid are included in the grid node of the same grid. Basic capital The number of materials, thereby forming the new accumulated grid hierarchy tree; step 2-2, repeating the calculation contents of steps 1-4, according to the grid corresponding to a leaf node in the newly accumulated grid hierarchy tree, the basic data is included a number, determining whether the grid corresponding to the node of the new accumulation tree is an important grid and giving the important grid label; Step 2-3, merging the new probability tail tree generated by the new sampling period And the old accumulated probability tail tree generated by the old accumulated sampling period, the new accumulated probability tail tree is generated, and the new accumulated probability tail tree represents the moving pattern set in the new accumulated sampling period.

It has the following advantages:

According to the above description, the advantages of the present invention are as follows:

1. By performing a dynamic mesh algorithm, the granularity of each important mesh is dynamically determined according to the number of the basic data included in each grid, so that the present invention has:

(1) Avoid the advantage that the mesh is too large to lose the more accurate moving pattern.

(2) Avoid the grid being too small and causing the total number of grids to rise.

(3) The number of the basic data contained in each grid is too small to lose the statistical significance.

2. Label only the mesh that is judged to be an important mesh, greatly reducing the number of nodes in the subsequent tail tree, and effectively reducing the resources and time required for the operation.

3. Since the trajectory mapping calculation of the prior art is too complicated, the calculation process must rely on uploading the moving trajectory data to the server end operation, thereby increasing the possibility of leakage of personal privacy data, and the present invention simplifies the information volume and reduces the amount through the foregoing. The advantages of computing resource requirements enable the algorithm of the present invention to perform operations on the user's personal device, reducing the risk of privacy exposure.

4. Since the movement trajectory data will be accumulated over time, the calculation and exploration of the overall sequence data in the prior art increases the cost of each data exploration, and eventually exceeds the upper limit of the hardware loadable operation. The present invention performs the exploration of the sequence data by using the new cumulative probability tail tree, so that the present invention only needs to perform operations on the important grid without recalculating the entire sequence data.

5. The present invention adjusts the time factor in the calculation process, so that the moving pattern of the present invention can be quickly adjusted according to the newly added sequence data. In the actual physical sense, if the target suddenly changes the previous habit, then The new accumulative probability tail tree can be quickly corrected by this time factor.

1 is a schematic diagram of the calculation steps of a preferred embodiment of the present invention.

2 is a schematic diagram of a data structure calculation step according to a preferred embodiment of the present invention.

FIG. 3 is a schematic diagram of a data structure calculation step according to a preferred embodiment of the present invention.

4 is a schematic diagram of a data structure calculation step according to a preferred embodiment of the present invention.

FIG. 5 is a schematic diagram of a data structure calculation step according to a preferred embodiment of the present invention.

FIG. 6 is a schematic diagram of a data structure calculation step according to a preferred embodiment of the present invention.

FIG. 7 is a schematic diagram of a data structure calculation step according to a preferred embodiment of the present invention.

FIG. 8 is a schematic diagram of a data structure calculation step according to a preferred embodiment of the present invention.

FIG. 9 is a schematic diagram of a data structure calculation step according to a preferred embodiment of the present invention.

FIG. 10 is a schematic diagram of a data structure calculation step according to a preferred embodiment of the present invention.

FIG. 11 is a schematic diagram of a data structure calculation step according to a preferred embodiment of the present invention.

The invention provides a progressive sequence data mining method and system with dynamic granularity and automatic labeling, which comprises two exploration stages. The invention establishes a new incremental grid table (Incremental mapping table) and a new cumulative probability through the two exploration stages. Incremental PST _DGAL , each node of the new cumulative probability tail tree stores a message of a Movement Pattern, all nodes representing a moving pattern in all of the sequence data. A probability tail tree represents a collection of all moving patterns in the sequence data.

Referring to FIG. 1 and FIG. 2, the sequence data (SequencesData) is sequentially composed of a plurality of the basic data (Data Element), and the order of the basic data may be time, space or any dependent order, for example, device coding. Sequence, sequence of ID access (Identification), sequence of access time, sequence of moving position, sequence of geographic coordinate position, gene sequence, stock trend data, commodity transaction record sequence, stylus sequence, key input sequence, symptom Sequence sequences, sequences of musical chords, and the like appear. The application of the sequence data analysis may be to analyze the commodity transaction record sequence to predict a better product promotion plan, or to analyze medical condition, species analysis, handwriting recognition analysis, music melody identification analysis or input word recognition analysis.

In the embodiment of the present invention, the sequence data is a latitude and longitude coordinate sequence data, and a new probability of calculating a new sampling period by using an important grid label sequence data (Labelsequences) is calculated by using the sequence data. Tail tree.

The first exploration phase (phase1) of the exploration phase is a dynamic granularity and auto-labeling (DGAL algorithm), and the second exploration phase (phase2) is the cumulative probability tail tree. Consolidation phase (incPST _DGAL (Incremental PST _DGAL Merge)).

The progressive sequence data mining method of the dynamic granularity and the automatic label can search the data of the individual sampling period and the accumulated exploration result in a loop operation in a single computing device, complete the calculation of the plurality of sampling periods, or according to different The sampling period is separately distributed to different sub-operating devices for decentralized operations, and then the operations are completed and then concentrated to a parent computing device for integration operations.

The first stage establishes an important mapping table in the new sampling period according to the sequence data in a new sampling period (the period (i)) and the important grid label sequence in the new sampling period. The new sampling period refers to the time period in which the data is acquired in the sequence data each time.

This first phase consists of the following steps:

Step 1-1: Obtain the sequence data in the new sampling period (period(i)). In the embodiment of the present invention, the sequence data is the Latitude and Longitude coordinate sequences, and the basic data may include information such as latitude and longitude and time.

Step 1-2, please refer to FIG. 3, FIG. 4 and FIG. 5, this step performs a new grid function tree (new GT algorithm), and the new grid level tree algorithm is used to establish the network in the new sampling period. The hierarchical tree, and the sequence data is counted by the grid hierarchy tree in the new sampling period.

The basic data in the sequence data is correspondingly distributed in a target space, According to a granularity, the target space is divided into a plurality of meshes, so that each of the meshes corresponds to a part of the target space, the meshes do not overlap each other, and all the meshes are collected. That is, the target space, and each grid corresponds to a grid hierarchy tree node in the grid hierarchy tree. In the embodiment of the present invention, the target space corresponds to an actual geospatial, and the sequence data is latitude and longitude coordinate sequence data distributed in the target space.

The mesh hierarchy tree node has the following relationship with the mesh granularity:

(1) According to k+1 different mesh granularities, the target space may have k+1 different cutting modes. Initially, the mesh hierarchical tree is a hierarchical tree with k+1 hierarchy.

(2) The grid level tree nodes of the same level in the grid hierarchy tree all correspond to the grid size of the same size.

(3) The mesh granularity corresponding to the upper hierarchical mesh tree node in the mesh hierarchical tree is greater than the mesh granularity corresponding to the lower hierarchical hierarchical hierarchical tree node.

(4) In the grid hierarchy tree, the grid hierarchy tree nodes without child nodes are called leaf nodes, and the nodes with the same parent node in the same hierarchy are sibling nodes, and the sibling nodes correspond to each other. The meshes are mutually brother meshes, and the mesh size of the sibling grid is the same.

(5) The grid corresponding to each leaf node in the new grid hierarchy tree is defined as a candidate grid, and the set of all the candidate grids is the target space.

If the value of a basic data belongs to a range of values corresponding to a grid, the basic data is included in the grid. For example, the latitude and longitude of a basic data is located in a grid. Geospatial, the grid contains the underlying material. The number of the basic data distributed in the candidate grid is statistically recorded in the grid level leaf node corresponding to the grid.

In the embodiment of the present invention, the 0th order (Level 0) of the grid hierarchy tree includes N ₀ ² nodes, corresponding to N ₀ ² grids. The mesh of the first-order hierarchical tree (Level 1) comprising N ₀ ² × d ² of the mesh of the hierarchical tree node, and the corresponding N ₀ ² × d ² meshes, the mesh hierarchy tree of order 2 (Level 2 a node containing N ₀ ² × d ⁴ corresponding to N ₀ ² × d ⁴ grids, and so on, the i-th order (Level i) of the grid hierarchy tree contains nodes of (2 ⁱ × N ₀ ) ² , Corresponding to (2 ⁱ × N ₀ ) ² grids, for ease of description, in the embodiment of the present invention, d=2 is taken as an example, but not limited thereto.

among them:

"N ₀ " indicates the ratio of the length of the target space of the rectangle to the width of the grid with the largest granularity, and the number of grids.

Equal to the number of points;

"i" indicates the class number.

"d" indicates the width ratio of the grid of the upper and lower levels.

Further, the new mesh hierarchy tree algorithm can be based on an accumulated grid hierarchy tree (incGT(1~i-1), incremental grid established in the old accumulated sampling period (period(1~i-1)). The number of hierarchical layers of the leaf nodes of the tree determines the number of hierarchical layers of the leaf nodes of the grid tree in the new sampling period (period(i)). In the initial sampling period (period(1)), a new grid hierarchy tree algorithm is established to establish a grid hierarchy tree to a base level, and the base hierarchy is a grid hierarchy tree. The largest class.

Continuing the sampling period (period(i>1)) after the initial sampling period, wherein the number of levels of the established hierarchical tree of the grid is not directly established to the basic level, but is referred to in the old accumulated sampling period. The grid hierarchy tree is created. In the embodiment of the present invention, a grid hierarchy tree having the same structure as the old accumulation sampling period is first established in a new sampling period, and is segmented to a next level for a grid-level leaf node corresponding to an important grid. Thereby, the speed of the calculation can be increased by reducing the number of nodes of the grid hierarchy tree.

Steps 1-3, please refer to FIG. 3 and FIG. 4, further, the new mesh hierarchy tree algorithm performs a mesh subdivision algorithm, and the leaf node corresponding to the leaf hierarchy tree of the old accumulated sampling period corresponds to the network. When the number of the basic data (Data Element) included in the cell is greater than a subdivision threshold, the mesh may be mesh-divided so that the leaf node correspondingly generates a plurality of child nodes.

For example, the grid corresponds to one of the grid level tree nodes of the 0th order (Level 0) of the grid hierarchy tree, and the subgrid corresponds to the grid hierarchy tree node of the first level (Level 1) of the grid hierarchy tree. analogy. When the grid is divided in the embodiment of the present invention, each of the grids are divided into d ² d ² smaller mesh size.

Steps 1-4, referring to FIG. 6 and FIG. 7, this step performs a grid fusion algorithm (gtMerge algorithm), and the grid fusion algorithm records the basic data according to the statistics of the leaf nodes of the grid hierarchy tree. The quantity, determining whether a candidate mesh is an important mesh and adjusting the size of the candidate mesh, giving each of the important mesh labels (σ), and forming the important mesh table according to the important mesh.

The mesh fusion algorithm dynamically determines a plurality of important grids for the number of the basic data distributed in the grid by the sequence data, so that the subsequent calculation process only performs calculation for a plurality of the important grids, thereby effectively improving the operation efficiency. .

The mesh fusion algorithm determines, according to the number of the basic data included in the candidate mesh, whether the candidate mesh meets the threshold of the important mesh, and the criterion for determining the candidate mesh as an important mesh comprises:

(1) On the grid hierarchy tree, the grid hierarchy tree node corresponding to the grid is a leaf node.

(2) The number of the basic data included in the candidate grid is greater than an important grid threshold (Cmin).

(3) A degree of disorder (e) of the amount of the base data of the candidate grid and its sibling grid is less than a chaos threshold (Emax). Among them, the degree of chaos is defined as follows:

"m" means: the number of sibling grids; "c _i " means that the i-th sibling grid contains the number of basic data; "p _i " means: the probability of the i-th grid, For example: the number of the four basic materials is 2, and the turbidity is calculated as follows:

On the grid hierarchy tree, the physical meaning of the leaf nodes is that their corresponding grids are the ones that may become important grids with the smallest granularity.

The sibling grid is a grid set that can be merged into a larger grid. When the chaotic degree of the sibling grid is lower than the physical value of the chaotic threshold, the number of the basic data of the sibling grid is quite different, and Uniform distribution is opposite, representing a more pronounced feature.

For example, in the embodiment of the present invention, the number of the basic data included in each candidate grid is greater than 2 (Cmin=2), and the chaos of the candidate grid and its sibling grid is less than 0.6 (ie, Emax= 0.6) (0.6 is the disorder when the 4 mesh data is evenly distributed), the candidate mesh is defined as an important mesh.

Further, the threshold number of the basic data to be included in each of the important grids may be specified according to user requirements, or may be converted by a user, or adjusted according to the overall computing resources of the system. In practical physical terms, the important grid may indicate that the target is extremely high in the grid or that it stays in the grid for a long time.

The mesh fusion algorithm uses a candidate mesh that is not determined to be an important mesh and its sibling mesh is not determined as an important mesh as a mesh fusion basis, so that the mesh and its neighboring brother meshes are both When the mesh fusion basis is met, the mesh fusion algorithm fuses the mesh. The mesh fusion system adds the number of the basic data corresponding to the grid and the leaf nodes of the sibling grid on the grid hierarchy tree, and stores the data on the parent node of the leaf node, and deletes the parent node. Child node, making the parent node a new leaf node.

Step 1-5, please refer to FIG. 7. This step generates the important mesh label sequence data according to the important grid table, and the important grid label sequence data is used to represent the sequence data in the new sampling period. The chronological relationship between the important mesh and the important mesh contained.

Step 1-6, please refer to FIG. 8. This step is based on the important grid tag sequence data, and a new probability tail tree (PST _DGAL ) is established in the new sampling period, where the new probability tail tree represents the new sampling period. A collection of the moving patterns presented by the important grid tag sequence data.

The new build rate tree construction process "build_PST" can refer to the formula set 7, but the probability tail tree construction method is not limited to this limit.

Each node in the probability tail tree has a corresponding label sequence, and the label sequence can be directly stored in the node or traversed from the root node to a branch through which the node passes. Can be combined to know.

In the embodiment of the present invention, the target space corresponds to an actual geographic space, and the sequence data is latitude and longitude coordinate trajectory data corresponding to the geographic space, and each node in the probability tail tree represents a moving pattern, the movement The pattern indicates the conditional probability distribution of the important mesh in the sequence after passing through the plurality of important meshes corresponding to the tag sequence included in the sequence.

For example, if the tag sequence of the mobile pattern represented by a node is s, s=ghi, and the conditional probability distribution stored by the node indicates the probability that the target may move toward a certain important mesh in the future. For example, the probability that the target will move toward the important grid "a" in the future should be "p(a|s)", which means that the important data "g", "h", "i" are sequentially passed through the sequence data. After that, the probability of further passing through the important grid "a". Through the establishment of the probability tail tree. Based on an important grid tag sequence data, the judgment in a moving pattern includes the following conditions: moving pattern judgment condition 1, p (s) > P _min moving pattern judgment condition 2 σ Σ _i , make

The code name of the above formula is as follows: "Σ _i " is the new important grid label set of the new sampling period; "s" is the label sequence of the moving pattern, s (s = s ₀ s ₁ ... s _l-1 , s _i Σ _1,i ) "p(s)" is the probability that the tag sequence s appears in the important grid tag sequence data; "p _min " is the threshold value of the probability of occurrence of the tag sequence s; "σ" is a tag variable, One of the labels of the new important grid label set, ie σ Σ _i ; "p(σ|s)" is the conditional probability of the future passing σ after the target passes s in the important grid tag sequence data; "γ" is the parent-child difference ratio parameter; "γ _min " is The minimum conditional probability parameter; and "suffix(s)" is the tail sequence of the tag sequence s, for example: suffix(ghi)=hi.

The judgment process of the moving pattern is as follows: Moving pattern judgment condition 1: The foregoing moving pattern judgment condition 1 is used to define a representative movement pattern, and p(s) indicates that the label sequence s is in the important grid. The probability of the occurrence of the tag sequence data, the greater the probability value, the more important the mobile pattern; the moving pattern judgment condition 2: further defined as long as there is a conditional probability p(σ|s) greater than γ _min , and the conditional probability The conditional probability p(σ|suffix(s)) corresponding to its parent node is γ times different, and the moving pattern represents a relatively special moving pattern.

Further, the establishment of the probability tail tree includes a hierarchical constraint (L _max ), which limits the maximum length of the label sequence of the mobile pattern, that is, the hierarchy constraint indicates the deepest level that the probability tail tree can establish, for example, If the level is limited to "3", the probability tail tree can be established up to layer 3. p(s)L _max

Referring to FIG. 1, the second stage operation process uses the old accumulated grid hierarchy tree (incGT(1~i-1)) of the old accumulated sampling period (period(1)~period(i-1)). The new mesh hierarchy tree (GT(i)) calculated in the new sampling period (period(i)) is combined to obtain the new one in the new accumulated sampling period (period(1)~period(i)). The accumulated grid level tree (incGT(1~i)), and the new accumulated grid level tree are calculated to correspond to the new accumulated important grid table (MT(1~i)). Combine the old cumulative probability tail tree (incPST _DGAL (1~i-1)) of the old accumulated sampling period with the new probability tail tree (PST _DGAL (i)) of the new sampling period to obtain a corresponding new cumulative sampling. A new cumulative probability tail tree of the period (1~i) (incPST _DGAL (1~i)).

The new accumulated probability tail tree represents the moving pattern set in the new accumulated sampling period, and predicts the trajectory of the target moving in the target space with the moving pattern set.

Further, the new cumulative probability tail tree is generated by fusing the new probability tail tree of the new sampling period and the old accumulated probability tail tree with the old sampling accumulation period. The new probability tail tree and the old accumulated probability tail tree can be respectively operated by different sub-operation devices, and then returned to the parent computing device to calculate the new cumulative probability tail tree.

Step 2-1, please refer to FIG. 10, in this step, a mesh hierarchical tree fusion algorithm (merge2GTs algorithm) is implemented, and the grid hierarchical tree algorithm is integrated into the old accumulated grid hierarchical tree calculated by the old accumulated sampling period. And the new grid hierarchy tree calculated in the new sampling period in the first stage operation, and the new accumulated grid hierarchy tree indicating the new accumulated sampling period is obtained.

The fusion of the new grid hierarchy tree and the old accumulation grid hierarchy tree is the number of the basic data included in the two grid-level leaf nodes corresponding to the same grid in the aggregate grid hierarchy tree. The new accumulated grid hierarchy tree is formed.

The new accumulated sampling period is the accumulation from the initial period to the new sampling period, so the old accumulated sampling period at the current time point is the new accumulated sampling period generated by the previous sampling point. For example, if the new sampling period of the current time point is the ith period, the old accumulated sampling period is the 1~i-1 period, and the new sampling period formed by the new sampling period and the old accumulated sampling period is the first 1~i period.

Further, if the number of new mesh layers is different from the level of the two-leaf node of the old accumulated mesh hierarchy and the mesh corresponding to the two leaf nodes has an overlapping relationship, the leaf node with a lower number of layers is segmented, so that The level of the newly generated leaf node is identical to the level of the node whose node number is higher, and the number of the basic data of the leaf node is The destination is assigned to the newly generated child node, and the total number of the base data corresponding to the leaf node is added.

For example, in FIG. 9, the grid of the hierarchy 0 number 5 of the new grid hierarchy tree overlaps with the grid of the old accumulation grid hierarchy tree hierarchy numbers 16, 17, 22, and 23, first new The grid of the grid level tree 0 is divided into 4 sub-grids 16, 17, 22 and 23, and then the grids of the hierarchical 1 of the old accumulated grid hierarchy are numbered 16, 17, 22 and 23 respectively. Adding, the new accumulated grid hierarchy tree is formed; wherein, when the number of the basic data of the leaf node is allocated to the newly generated leaf node, the grid granularity corresponding to the newly generated leaf node may be equally distributed.

Step 2-2. In this step, the content described in steps 1-3 to 1-5 is repeated, and the important grid and the adjustment candidate network are determined according to the number of the basic data included in the leaf nodes of the accumulated grid hierarchy tree. The grid size is given to the important grid labeling and the new accumulated vital grid table (MT(i)) corresponding to the new accumulated sampling period is formed according to the important grid.

Further, since the new mesh hierarchical tree and the old accumulated mesh hierarchical tree are merged in the second phase, the threshold value used for determining the important mesh may be correspondingly corrected. In the embodiment of the present invention, when the number of the basic data included in each of the mesh hierarchical tree nodes of the newly accumulated mesh hierarchical tree is greater than four, the grid corresponding to the node is an important mesh.

Step 2-3, as shown in FIG. 9, this step performs an implementation of an accumulation probability tail tree (build_incPST _DGAL ) algorithm, which combines the new accumulated probability tail tree generated in steps 1-5 and the old accumulated sampling period. The old cumulative probability tail tree computes a new cumulative probability tail tree (insPST _DGAL (1~i)), and the new accumulated probability tail tree represents the moving pattern set in the new accumulated sampling period.

The build probability tail tree algorithm executed in steps 1-6 performs probability calculation through the important grid tag sequence data, and the built-in cumulative probability tail tree (build_incPST _DGAL ) algorithm executed in this step The probability calculation is calculated based on the new probability tail tree generated in steps 1-5 and the old accumulated probability tail tree generated in the old accumulated sampling period, and the weight calculation is considered in the calculation process at the same time.

In the embodiment of the present invention, since the grid hierarchy tree algorithm dynamically adjusts the size of the important grid, the important grid size is different, and a grid matching problem is generated, so that the new probability tail tree and The fusion of the old cumulative probability tail tree cannot be completed by simply adding the conditional probability stored by the node with the same grid tag sequence data. The grid matching problem means that the number and size of the important grids corresponding to the same target space in each sampling period are different, and thus are generated in the new probability tail tree and the old cumulative probability tail tree. Nodes with the same sequence of tags actually correspond to meshes of different sizes or ranges. Therefore, in order to solve the mesh matching problem, when the new probability tail tree and the old accumulated probability tail tree are merged, a new cumulative probability (p(σ)) and a new cumulative condition probability (p(σ|s) are included. )), and the fusion estimate weight (W) of an overlapping tag sequence.

The calculation of the new cumulative probability p(σ) is calculated based on the set of new periodic overlapping labels and the overlapping set of old accumulated sampling periods, respectively, in an overlapping relationship with the label σ of the new accumulation period.

The calculation of the new cumulative conditional probability (p(σ|s)) is based on the new accumulated sampling The new sample period overlap label sequence set and the old accumulation sample period overlap label sequence set in which the periodic label sequence "s" and "sσ" have overlapping relationships, respectively.

Wherein, the new sampling period overlap label sequence set or the old accumulated overlap label sequence set is defined as follows: a label sequence s is given to one of the new accumulated sampling periods (s=s(s=s ₀ s ₁ ...s _l-1 , s _i Σ _1,i )), a new sampling period or an old accumulated sampling period label sequence q (q = q ₀ q ₁ ... q _l-1 , q _i Σ _i or, q _i Σ _1,i-1 ). If the following conditions are met, the tag sequence "q" of the new sampling period or the old accumulated sampling period is a new sampling period overlapping label sequence or an old accumulated overlapping label sequence of the label sequence "s": each of the label sequences q The grid corresponding to the label q _{i and} the grid corresponding to the s _i overlap partially or completely. The new cycle overlap tag sequence/old accumulation overlap tag sequence of the tag sequence s is referred to as a new cycle overlap tag sequence set/old accumulation overlap tag sequence set.

The fusion estimation weight calculation of the tag sequence of a new accumulated sampling period includes a new sampling period overlapping tag sequence and an estimated weight ( And the fusion estimation weight of the overlapped tag sequence with the old accumulated sampling period ( The calculation of the matching weights of the labels corresponding to the order is multiplied.

The new sampling period overlap label sequence fusion estimation weight calculation formula is as follows: The calculation formula of the fusion estimation weight of the overlapped label sequence of the old accumulated sampling period is as follows: Among them, the meaning of the formula of the calculation formula is as follows: "s": a sequence of labels of a new accumulated sampling period, s = s ₀ s ₁ ... s _l-1 , s _i Σ _1,i , the length of the label sequence is the number of labels in the sequence, ie |s|=1; the new important grid label set (Σ _i ): the label set of the important grid of the new sampling period; the old accumulation Important grid label set (Σ _1,i-1 ): the label set of the important grid of the old accumulated sampling period (period(1)~period(i-1)); and the new accumulated important grid label set (Σ _{1 , i} ): The set of labels for the important grid of the new cumulative sampling period (period(1)~period(1)).

Label matching type 1, single grid corresponds to a single grid: Please refer to FIG. 10, the grid corresponding to the first label is the same as the grid corresponding to the second label, and the probability of tail sampling is different in different sampling periods. The matching weight corresponding to this is "1", that is, ; tag matching type 2, multi-grid corresponding to a single grid: Please refer to FIG. 10, the grid corresponding to the first label and the grid corresponding to the second label partially overlap, and the mesh size corresponding to the first label Smaller, the matching weight corresponding to the probability tailing tree fusion operation in different sampling periods is "1", that is, And the label matching type 3, the single grid corresponds to the multi-grid: Please refer to FIG. 10, the grid corresponding to the first label and the grid corresponding to the second label partially overlap, and the mesh size corresponding to the first label Larger, the matching weight corresponding to the probabilistic tail-tree fusion operation in different sampling periods is "the important grid of the new accumulation period in which the grid corresponding to the second label overlaps with the grid corresponding to the first label. Granularity and ratio", ie ,among them, ... a label for the new accumulation period that overlaps σ _i , and σ _j { ... }.

Please refer to FIG. 11 , in which the label “g” in the new sampling period or the old accumulated sampling period and the label “e” in the new accumulated sampling period belong to the label matching type 1, and the fusion estimation weight is “1”.

The label "d" in the new sampling period or the old accumulated sampling period and the label "c" in the new accumulated sampling period belong to the label matching type 2, and the fusion estimation weight is "1".

The label "h" in the new sampling period or the old accumulated sampling period and the labels "g" and "f" of the new accumulated sampling period are label matching type 3, and the fusion estimation weight is " ", its expression is:

Further, the most basic calculation of the merged new probability tail tree and the old cumulative probability tail tree is the calculation of the new cumulative probability p(σ) and the new accumulated conditional probability (p(σ|s)).

The "build_incPSTDGAL" algorithm is one of the methods for the fusion of the new probability tail tree and the old cumulative probability tail tree in the present invention, and is not limited herein.

Please refer to "Formula Set 1" for the "build_incPSTDGAL" algorithm process.

As shown in FIG. 10, assuming that the data length of the old accumulated sampling period is 10, the probability of occurrence of bc and bcd in the old accumulated probability tail tree is respectively with The length of the new sampling period is 5, and the probability that the new probability tail tree predicts be and bef is And P ₂ (bef)=0.25, the calculation procedure of the conditional probability p(a|cd) of one of the nodes cd of the new accumulation period is referred to Equation Set 4.

Referring to FIG. 12, in the embodiment of the present invention, the probability of forming a track "nokjfb" (P("nokjfb")) is predicted by the accumulated probability tail tree, and the calculation formula is Refer to Equation 8.

In the embodiment of the present invention, an aging parameter is added to the operation of the new probability tail tree and the old cumulative probability tail tree fusion, and the label grid sequence data obtained by different sampling periods is weighted differently by the time factor. Adjust so that the results of the calculation can be adjusted according to user needs.

The application of the time factor may be: corresponding data capacity ratio, for example, 1/1 of the temporary data capacity of the newly added tag grid sequence data, and the weight of the new probability tail tree multiplication is 1 when the fusion is performed. /5; corresponding data generation time, for example, corresponding to the sudden change of mobile habits, in order to make the new accumulative probability tail tree quickly adjust, giving the new probability tail tree a higher weight value; for example, to keep the old accumulative probability tail The predicted result of the tree gives a higher weight value to the old cumulative probability tail tree; or the time factor can be set according to the user experience. The above is an example of the implementation of the time factor, but the actual application is not limited to this.

For the calculation formula of the new cumulative probability combined with a time factor parameter "α", please refer to Equation 5.

For the calculation formula of the new cumulative condition probability combined with the time factor parameter, please refer to Equation 6.

According to the above description, the advantages of the present invention are as follows:

1. By performing a dynamic mesh algorithm, the granularity of each important mesh is dynamically determined according to the number of the basic data included in each grid, so that the present invention has:

(1) Avoid the advantage that the mesh is too large to lose the more accurate moving pattern.

(2) Avoid the grid being too small and causing the total number of grids to rise.

(3) The number of the basic data contained in each grid is too small to lose the statistical significance.

2. Label only the mesh that is judged to be an important mesh, greatly reducing the number of nodes in the subsequent tail tree, and effectively reducing the resources and time required for the operation.

3. Since the trajectory mapping calculation of the prior art is too complicated, the calculation process must rely on uploading the moving trajectory data to the server end operation, thereby increasing the possibility of leakage of personal privacy data, and the present invention simplifies the information volume and reduces the amount through the foregoing. The advantages of computing resource requirements enable the algorithm of the present invention to perform operations on the user's personal device, reducing the risk of privacy exposure.

4. Since the movement trajectory data will be accumulated over time, the calculation and exploration of the overall sequence data in the prior art increases the cost of each data exploration, and eventually exceeds the upper limit of the hardware loadable operation. The present invention performs the exploration of the sequence data by using the new cumulative probability tail tree, so that the present invention only needs to perform operations on the important grid without recalculating the entire sequence data.

5. The present invention adjusts the time factor in the calculation process, so that the moving pattern of the present invention can be quickly adjusted according to the newly added sequence data. In the actual physical sense, if the target suddenly changes the previous habit, then The new accumulative probability tail tree can be quickly corrected by this time factor.

Formula set 1: "build_incPSTDGAL" algorithm process

In the "build_incPSTDGAL" algorithm, getProb(σ, T ₁ , MT ₁ , T ₂ , MT ₂ ) calculates the new cumulative probability p(σ). When calculating the new cumulative probability p(σ), T ₁ corresponds to the new one. The probability tail tree T _i , MT ₁ corresponds to the new cycle important grid table, T ₂ corresponds to the old cumulative probability tail tree T _{1, i-1} , MT ₂ corresponding to the old accumulated important grid table, the new cumulative probability Please refer to Equation 2 for the calculation formula. In the algorithm, getCProb(s, σ, T ₁ , MT ₁ , T ₂ , MT ₂ ) is the new cumulative probability p(σ|s) calculated. For the calculation formula of the new cumulative condition probability, please refer to Equation 3.

Formula 2: Calculation formula for the new cumulative probability

among them,

Equation (1) is " "

Equation (2) is " "

Formula 3: Formula for calculating the probability of a new cumulative condition

among them,

Equation (3) is " "

Equation (4) is " "

Equation (5) is " "

Equation (6) is " "

"s": A sequence of tags for a new accumulation cycle. The length of a tag sequence is the number of tags in the sequence, for example, the length of s=s ₀ s ₁ ... s _l-1 is represented by |s|, |s|=1; "cnt _i (n)/cnt _{1, i-1} (n)": the number of occurrences of the tag sequence of length n in the new individual cycle/old accumulation cycle, wherein the number of occurrences of the tag sequence of length n can be estimated from the total length L of the tag sequence data Or, estimated by L-n+1, the number of tag sequences in the tag sequence data seqNo may be separately recorded and estimated by L-seqNo(n-1).

"T _i /T _1,i-1 ": new probability tail tree / old cumulative probability tail tree.

" ”: The probability of occurrence of the new period overlap label sequence set q/old accumulated overlap label sequence set t is predicted by the new probability tail tree/old accumulation probability tail tree.

" (New Period Overlapping Label Sequence Set): A collection of new periodic overlapping label sequences for a new accumulated period of the label sequence s.

" (Old Accumulated Overlapping Tag Sequence Set): A collection of old accumulated overlapping tag sequences for a new accumulated cycle of the tag sequence s.

Formula set 4:

among them,

Equation (7) is " "

Equation (8) is " "

Equation (9) is " "

Equation (10) is " "

Formula 5:

among them,

Equation (11) is " "

Equation (12) is " "

Formula 6:

among them:

Equation (13) is " Cnt1,i-1(|sσ|)"

Equation (14) is " "

Equation (15) is " "

Equation (16) is " "

Formula 7: "build_PST" algorithm process

Formula 8:

Claims (7)

A progressive sequence data mining method for dynamic granularity and automatic labeling, comprising a first exploration stage and a second exploration stage, which establish a new accumulated important grid table and a new cumulative probability tail tree, with the cumulative probability tail The predicted sequence data in the tree is generated in a moving trajectory in a target space, wherein: the first exploration phase comprises the following steps: Step 1-1: obtaining the new sampling period in a new sampling period Sequence data, the sequence data includes a plurality of basic data distributed in the target space; Step 1-2, performing a new grid hierarchy tree algorithm, and the target space is divided into a plurality of networks according to a grid granularity a grid, and each grid corresponds to a grid hierarchy tree node in the grid hierarchy tree; steps 1-3, performing a grid subdivision algorithm, according to the network corresponding to the leaf nodes of each grid hierarchy tree When the number of the basic data included in the cell is greater than a subdivision threshold, the mesh is mesh-divided, so that the leaf nodes of the mesh hierarchical tree correspondingly generate a plurality of child nodes, and the mesh corresponding to the leaf nodes It is defined as a candidate mesh; mesh hierarchy tree and a new accumulation grid hierarchical tree old overlapping relationship and different particle sizes leaf nodes, leaf node is adjusted to the same particle size Pointing, and assigning the number of the basic data of the old leaf node to the plurality of newly generated leaf nodes, and allocating the number of the basic data of the leaf node to the plurality of leaf nodes; Step 1-4, performing a mesh fusion algorithm determines whether the candidate mesh corresponding to the leaf node is an important mesh and adjusts the candidate mesh according to the number of the basic data recorded by the leaf nodes of the mesh hierarchical tree. Size, and given the important grid label, all the important grids form an important grid table; the leaf nodes corresponding to the grid that are not determined to be important grids are mesh-fused with their sibling nodes; Step 1 -5, generating the important grid tag sequence data according to the important grid table, wherein the important grid tag sequence data is represented by the important mesh included in the sequence data and the important grid in the new sampling period a chronological relationship; and steps 1-6, establishing a new probability tail tree in the new sampling period based on the important grid tag sequence data, wherein the new probability tail tree represents the important in the new sampling period a set of the moving patterns presented by the tag sequence data; and each node in the probability tail tree represents a moving pattern, the moving pattern indicating a sequence of tags included in the sequence data passing through the node After a number of important grids, the future will enter a certain important The conditional probability distribution of the grid; and the second exploration stage comprises the following steps: Step 2-1: merging the new grid hierarchy tree with the old accumulation grid hierarchy tree to form a new cumulative grid hierarchy tree, and merging the new network And the number of the basic data included in the grid-level leaf node corresponding to the same grid in the grid-level tree and the old accumulated grid-level tree, thereby forming the new accumulated grid-level tree; step 2-2 The calculation content of the step 1-4 determines whether the grid corresponding to the node of the new accumulated hierarchical tree is the number according to the number of the basic data included in the grid corresponding to the leaf node in the new accumulated grid tree The important grid and the important grid label are given; Step 2-3, the new probability tail tree generated by the new sampling period and the old accumulated probability tail tree generated by the old accumulated sampling period are generated, and the new accumulated probability tail is generated. The tree is set, and the new cumulative probability tail tree represents the set of moving patterns in the new accumulated sampling period. For example, the dynamic granularity of the first application of the patent scope and the progressive sequence data mining method of the automatic label, the calculation of the overlapping node fusion estimated weight is based on the label sequence included in the two nodes, and the matching weights of the labels corresponding to each other are sequentially matched. Multiply, the matching weight of the tag is calculated according to the tag matching type of the tag, and includes the following three tag matching types: Label matching type 1. Single grid corresponds to a single grid: the grid corresponding to the two labels is the same, and the matching weight corresponding to the probability tailing tree fusion operation in different sampling periods is "1"; the label matching pattern 2. The multi-grid corresponds to a single grid: the grids corresponding to the two labels overlap, and the grid size corresponding to the first label is small, and the matching weight corresponding to the probabilistic tail-tree fusion operation of different sampling periods It is "1"; and the label matching type 3, the single grid corresponds to the multi-grid: the grid corresponding to the two labels overlaps partially, and the grid corresponding to the second label overlaps with the grid corresponding to the first label. The granularity and proportion of the important grid of the cycle. For example, in the dynamic granularity and automatic label progressive sequence data mining method of claim 2, the candidate grid determines that the criterion of the important grid includes: the number of the basic data included in the candidate grid is greater than an important The grid threshold; and the number of the basic data of the candidate grid and its sibling grid is less than a chaotic threshold. Such as the dynamic granularity of the patent application scope 3 and the progressive label data mining method of the automatic label, the candidate grid and the base of the sibling grid thereof When the amount of the underlying data is higher than the chaotic threshold, it can be merged into a larger grid. For example, in the method of claim 1, 2, 3 or 4, the dynamic granularity and the automatic label progressive sequence data mining method, a time factor is added to the operation of the new probability tail tree and the old cumulative probability tail tree fusion. The important grid label sequence data obtained by different time periods is adjusted by the time factor by different time weights. For example, in the fifth aspect of the patent application, the dynamic granularity and automatic label progressive sequence data mining method is established according to the structure of an old accumulated grid hierarchical tree established in the old accumulated sampling period. The new grid hierarchy tree in the new sampling period, and the important grid label sequence data is counted by the new grid hierarchy tree in the new sampling period. A progressive sequence data mining system with dynamic granularity and automatic labeling, wherein an arithmetic device performs a progressive sequence data mining method with dynamic granularity and automatic labeling according to any one of the foregoing claims 1 to 6 wherein the operation The device comprises at least one parent computing device and a plurality of sub-computing devices. The arithmetic algorithm is distributed to different sub-operating device operations according to different sampling periods, and then integrated into a parent computing device for integration operations.