Abstract:
A method for detecting an abnormal transition pattern from a transition pattern includes: first extracting an episode pattern with an appearance frequency greater than or equal to a first frequency from an episode pattern represented with a description form so as to include a first transition pattern and a second transition pattern differing in an order of a part of items from the first transition pattern to have a complementary relation thereto; second extracting a third transition pattern with an appearance frequency greater than or equal to a second frequency from the transition pattern; and specifying a transition pattern other than the third transition pattern from transition patterns included in the extracted episode pattern, and determining an abnormal transition pattern based on the transition pattern specified in the specifying when the third transition pattern includes a fourth transition pattern corresponding to the extracted episode pattern in the first extracting.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
       [0001]    This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2012-126438, filed on Jun. 1, 2012, the entire contents of which are incorporated herein by reference. 
       FIELD 
       [0002]    A certain aspect of embodiments described herein relates to a method and an apparatus for detecting an abnormal transition pattern. 
       BACKGROUND 
       [0003]    Various methods have been conventionally studied to detect trajectory data different from the others from large quantities of trajectory data in traffic field, or to detect a trail pattern different from the others from a great deal of operation trail logs in BPM (Business Process Management) field. 
         [0004]    The above described detection may be achieved by a method that represents trajectory data or tail log with sequential data that defines an order of items, and detects abnormal sequential data based on appearance frequencies of sequential patterns that are combinations of items appearing in the sequential data as disclosed in R. Agrawal and R. Srikant, Mining Sequential Patterns, IEEE &#39;95 (Non-Patent Document 1). 
       SUMMARY 
       [0005]    According to an aspect of the present invention, there is provided a method for detecting an abnormal transition pattern from a transition pattern representing an order of items, the method including: first extracting an episode pattern with an appearance frequency greater than or equal to a first frequency from an episode pattern represented with a description form so as to include a first transition pattern and a second transition pattern, the second transition pattern differing in an order of a part of items from the first transition pattern to have a complementary relation to the first transition pattern; second extracting a third transition pattern with an appearance frequency greater than or equal to a second frequency from the transition pattern; and specifying a transition pattern other than the third transition pattern extracted in the second extracting from transition patterns included in the episode pattern extracted in the first extracting, and determining an abnormal transition pattern based on the specified transition pattern when the third transition pattern extracted in the second extracting includes a fourth transition pattern corresponding to the episode pattern extracted in the first extracting. 
         [0006]    According to an aspect of the present invention, there is provided a computer readable medium storing a program causing a computer to execute a process for detecting an abnormal transition pattern from a transition pattern representing an order of items, the process including: extracting an episode pattern with an appearance frequency greater than or equal to a first frequency from an episode pattern represented with a description form so as to include a first transition pattern and a second transition pattern, the second transition pattern differing in an order of a part of items from the first transition pattern to have a complementary relation to the first transition pattern; extracting a third transition pattern with an appearance frequency greater than or equal to a second frequency from the transition pattern; and specifying a transition pattern other than the third transition pattern extracted in the second extracting from transition patterns included in the episode pattern extracted in the first extracting, and determining an abnormal transition pattern based on the specified transition pattern when the third transition pattern extracted in the second extracting includes a fourth transition pattern corresponding to the episode pattern extracted in the first extracting. 
         [0007]    According to an aspect of the present invention, there is provided an apparatus for detecting an abnormal transition pattern from a transition pattern representing an order of items, the apparatus including: a first extracting unit that extracts an episode pattern with an appearance frequency greater than or equal to a first frequency from an episode pattern represented with a description form so as to include a first transition pattern and a second transition pattern, the second transition pattern differing in an order of a part of items from the first transition pattern to have a complementary relation to the first transition pattern; a second extracting unit that extracts a third transition pattern with an appearance frequency greater than or equal to a second frequency from the transition pattern; and a determination unit that specifies a transition pattern other than the third transition pattern extracted by the second extracting unit from transition patterns included in the episode pattern extracted by the first extracting unit and determines an abnormal transition pattern based on the specified transition pattern when the third transition pattern extracted by the second extracting unit includes a fourth transition pattern corresponding to the episode pattern extracted by the first extracting unit. 
         [0008]    The object and advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the claims. It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory and are not restrictive of the invention, as claimed. 
     
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         [0009]      FIG. 1  schematically illustrates a configuration of an information processing system in accordance with an embodiment; 
           [0010]      FIG. 2  is a diagram illustrating a set T of trajectory data. 
           [0011]      FIG. 3  is a diagram that plots positional data Pos in  FIG. 2  on a coordinate plane and connects the positional data Pos in order of acquisition time; 
           [0012]      FIG. 4  illustrates a hardware configuration of a server; 
           [0013]      FIG. 5  is a functional block diagram of the server; 
           [0014]      FIG. 6A  illustrates a state where a region (region R to be analyzed) including the whole of the set T of trajectory data is divided with a mesh granularity d, and  FIG. 6B  is a diagram illustrating a set S of sequential data; 
           [0015]      FIG. 7  is a flowchart illustrating a sequence of a process executed by the server; 
           [0016]      FIG. 8  is a flowchart illustrating a sequential data generating process (step S 12 ) executed by a sequential data generating unit; 
           [0017]      FIG. 9  is a flowchart illustrating a frequency mining process (step S 14 ) executed by a frequency mining unit; 
           [0018]      FIG. 10A  and  FIG. 10B  are diagrams illustrating episode patterns to be processed in the embodiment; 
           [0019]      FIG. 11A  through  FIG. 11C  are diagrams for explaining the process executed by the frequency mining unit; 
           [0020]      FIG. 12  is a flowchart illustrating a low-frequency sequence extraction process (step S 16 ) executed by a low-frequency sequence extracting unit; 
           [0021]      FIG. 13A  through  FIG. 13C  are diagrams for explaining the process executed by the low-frequency sequence extracting unit; 
           [0022]      FIG. 14  is a flowchart illustrating an abnormal trajectory determination process (step S 18 ) executed by an abnormal trajectory determination unit; and 
           [0023]      FIG. 15A  and  FIG. 15B  are diagrams for explaining the process executed by the abnormal trajectory determination unit. 
       
    
    
     DESCRIPTION OF EMBODIMENTS 
       [0024]    The method of Non-Patent Document 1 first detects a sequential pattern with a high appearance frequency, and checks appearance frequencies of sequential patterns having a different order of the items included in the sequential pattern with a high appearance frequency. Then, sequential data including a sequential pattern with a lower appearance frequency among the sequential patterns having the different order of the items is decided as abnormal data. 
         [0025]    However, the method of Non-Patent Document 1 needs to check even a disinterested sequential pattern, and thus is inefficient because appearance frequencies of all sequential patterns having a different order of items in each sequential data are to be checked. 
         [0026]    Hereinafter, a description will be given of an embodiment with reference to  FIG. 1  through  FIG. 15B .  FIG. 1  schematically illustrates a configuration of an information processing system  100  in accordance with the embodiment. 
         [0027]    As illustrated in  FIG. 1 , the information processing system  100  includes in-vehicle devices  10 , a user terminal  20 , and a server  30 . The in-vehicle devices  10 , the user terminal  20 , and the server  30  are connected to a network  80  such as the Internet. 
         [0028]    The in-vehicle device  10  is a device mounted in a vehicle such as a taxi and includes a GPS module and a communication device. The in-vehicle device  10  acquires positional data of the vehicle at predetermined time intervals with the GPS module, and transmits the acquired positional data to the user terminal  20  with the communication device. The positional data has four attributes (time, ID, latitude, longitude). 
         [0029]    The user terminal  20  is a terminal such as a PC (Personal computer) placed in, for example, a taxi company, and collects positional data of vehicles transmitted from the in-vehicle devices  10 . The user terminal  20  then organizes the positional data of the vehicles, creates a set T of trajectory data illustrated in  FIG. 2 , and transmits it to the server  30 . The set T of trajectory data in  FIG. 2  has fields for an ID and positional data Pos (latitude, longitude). The field for the ID stores an ID of trajectory (corresponding to an ID of the vehicle for example). The field for the positional data Pos (latitude, longitude) stores information about latitude and longitude in order of acquisition time.  FIG. 3  plots the positional data Pos in  FIG. 2  on a coordinate plane, and connects the positional data Pos in order of acquisition time. 
         [0030]    Back to  FIG. 1 , the server  30  executes a process for determining an abnormal trajectory from the set T of trajectory data transmitted from the user terminal  20  based on the request from the user terminal  20 . The server  30  outputs the processing results to the user terminal  20 . The present embodiment describes trajectory of a small number of vehicles (e.g. one vehicle) that passes locations X 1 , X 2 , and X 3  in order of, for example, X 1 →X 3 →X 2  although a large number of vehicles pass the locations in order of X 1 →X 2 →X 3  as an “abnormal trajectory”. 
         [0031]      FIG. 4  illustrates a hardware configuration of the server  30 . As illustrated in  FIG. 4 , the server  30  includes a CPU  90 , a ROM  92 , a RAM  94 , a storing unit (HDD (Hard Disk Drive) in this embodiment)  96 , and a portable storage medium drive  99 , and each of them is connected to a bus  98 . The server  30  achieves a function of each unit in  FIG. 5  by executing, by the CPU  90 , a program (abnormal transition pattern detection program) stored in the ROM  92  or the HDD  96 , or a program (abnormal transition pattern detection program) read out from a portable storage medium  91  by the portable storage medium drive  99 . 
         [0032]      FIG. 5  illustrates a functional block diagram of the server  30 . As illustrated in  FIG. 5 , the execution of the program by the CPU  90  allows the server  30  to function as a data acquisition unit  32 , a sequential data generating unit  34 , a frequency mining unit  36 , a low-frequency sequence extracting unit  38 , an abnormal trajectory determination unit  40 , and an output unit  42 . 
         [0033]    The data acquisition unit  32  acquires the set T of trajectory data transmitted from the user terminal  20 , and transmits it to the sequential data generating unit  34 . 
         [0034]    The sequential data generating unit  34  divides a region (region R to be analyzed) that includes the whole of the set T of trajectory data with a mesh granularity d as illustrated in  FIG. 6A . In addition, the sequential data generating unit  34  assigns an ID (mesh ID=A, B, C . . . ) to each mesh, and converts data included in the set T of trajectory data into sequential data represented with the mesh IDs in accordance with given conversion rules (see  FIG. 6B ). A set of sequential data after conversion is described as a set S. 
         [0035]    The frequency mining unit  36  performs frequent episode mining and frequent sequential pattern mining to the set S of sequential data. The frequent episode mining extracts an episode pattern with an appearance frequency greater than or equal to a given threshold value in the set S of sequential data from episode patterns (described as A→{B, C}) including a transition pattern (hereinafter, referred to as “sequential pattern”) having an order of items such as A→B→C (A, B, and C are exemplary items) and a sequential pattern having a complementary relationship thereto, which has a partly different order of the items, such as A→C→B, from the order A→B→C of the transition pattern. The frequent sequential pattern mining extracts a sequential pattern with an appearance frequency greater than or equal to a given threshold value in the set S of sequential data from sequential patterns having a given order such as A→B→C. 
         [0036]    The low-frequency sequence extracting unit  38  extracts a low-frequency sequential pattern k c  based on processing results of the frequency mining unit  36 . The low-frequency sequential pattern k c  means a sequential pattern (order of mesh IDs) included in abnormal sequential data. When the episode pattern (e.g. A→{B, C}) extracted by the frequent episode mining includes the sequential pattern (e.g. A→B→C) extracted by the frequent sequential pattern mining, the low-frequency sequence extracting unit  38  extracts a sequential pattern (e.g. A→C→B) that is other than the extracted sequential pattern and satisfies a given condition in sequential patterns included in the extracted episode pattern as the low-frequency sequential pattern k c . 
         [0037]    The abnormal trajectory determination unit  40  extracts sequential data that matches the low-frequency sequential pattern k c  extracted by the low-frequency sequence extracting unit  38 , in other words, sequential data that includes the extracted low-frequency sequential pattern k c  from the set S of sequential data, and decides it as the abnormal trajectory. In addition, the abnormal trajectory determination unit  40  extracts sequential data including a normal sequential pattern corresponding to the low-frequency sequential pattern k c  from the set S of sequential data, and decides it as a normal trajectory. 
         [0038]    The output unit  42  outputs the abnormal trajectory and the normal trajectory decided in the abnormal trajectory determination unit  40  to the user terminal  20 . 
         [0039]    A detail description will now be given of a process of the server  30  of the present embodiment with reference to  FIG. 7  through  FIG. 15B .  FIG. 7  is a flowchart illustrating a sequence of the process of the server  30 . The process illustrated in  FIG. 7  starts when the user terminal  20  sends the set T of trajectory data to the data acquisition unit  32 . 
         [0040]    In the process illustrated in  FIG. 7 , the data acquisition unit  32  acquires the set T of trajectory data, and transmits the acquired set T to the sequential data generating unit  34  at step S 10 . At step S 12 , the sequential data generating unit  34  then performs a sequential data generating process. Next, at step S 14 , the frequency mining unit  36  performs a frequency mining process. At step S 16 , the low-frequency sequence extracting unit  38  then performs a low-frequency sequence extraction process, and at step S 18 , the abnormal trajectory determination unit  40  performs an abnormal trajectory determination process. At step S 20 , the output unit  42  outputs a determination result from an abnormal trajectory determination process to the user terminal  20 . 
         [0041]    A detail description will now be given of processes from steps S 12  through S 18 . 
       (Step S 12 : Sequential Data Generating Process) 
       [0042]    A description will first be given of the sequential data generating process (step S 12 ) by the sequential data generating unit  34 . At step S 12 , the process along the flowchart illustrated in  FIG. 8  is executed. In the process illustrated in  FIG. 8 , at step S 30 , the sequential data generating unit  34  initializes the set S of sequential data. 
         [0043]    At step S 32 , the sequential data generating unit  34  then divides the region R to be analyzed with a mesh granularity d as illustrated in  FIG. 6A . The sequential data generating unit  34  assigns an ID to each of the divided meshes (mesh ID=A, B, C . . . ). 
         [0044]    At step S 34 , the sequential data generating unit  34  determines whether the set T of trajectory data is empty. When the determination is Y, i.e. all trajectory data included in the set T is processed, the sequential data generating unit  34  ends the entire process in  FIG. 8 . 
         [0045]    On the other hand, when the determination at step S 34  is N, the process moves to step S 36 . At step S 36 , the sequential data generating unit  34  extracts one piece of trajectory data t from the set T of trajectory data. For example, the sequential data generating unit  34  extracts trajectory data t 1  at the first line from the set T of trajectory data in  FIG. 2 . 
         [0046]    At step S 38 , the sequential data generating unit  34  initializes s and p pre . Here, s represents sequential data, and p pre  means positional data previous to the focused positional data that is extracted at step S 44 . 
         [0047]    Then, at step S 40 , the sequential data generating unit  34  determines whether the positional data Pos illustrated in  FIG. 2  is empty. When the determination is N, the process moves to step S 44 . 
         [0048]    At step S 44 , the sequential data generating unit  34  extracts leading positional data p from the positional data Pos. For example, the sequential data generating unit  34  extracts leading positional data (36.25, 137.55) in the trajectory data t 1  (p 1  in  FIG. 6A ). 
         [0049]    At step S 46 , the sequential data generating unit  34  then determines whether positional data is stored in p pre . Here, p pre  is initialized at step S 38 , and thus the determination is N, and the process moves to step S 48 . 
         [0050]    At step S 48 , the sequential data generating unit  34  stores the positional data (p 1 ) in p pre . Then, the process goes back to step S 40 . 
         [0051]    Back to step S 40 , the sequential data generating unit  34  determines whether the positional data Pos illustrated in  FIG. 2  is empty. When the determination is N, the process moves to step S 44 , and the sequential data generating unit  34  extracts leading positional data p from the positional data Pos. For example, the sequential data generating unit  34  extracts the second positional data (36.08, 137.71) in the trajectory data t 1  (p 2  in  FIG. 6A ). 
         [0052]    Then, at step S 46 , the sequential data generating unit  34  determines whether positional data is stored in p pre . Here, since the positional data p 1  is stored in p pre  at the previous step S 48 , the determination becomes Y, and the process moves to step S 50 . 
         [0053]    At step S 50 , the sequential data generating unit  34  connects sequentially mesh IDs of the meshes intersecting with a straight line connecting p pre  (=p 1 ) and the positional data p (=p 2 ) to s. However, the mesh ID that is the same as the mesh ID of the mesh intersecting with the right end of s (last connected ID) is not connected so that the same mesh ID is not continuously output. Here, the straight line connecting the positional data p 1  and p 2  intersects with the mesh having a mesh ID of A, and thus, “A” is connected to s. 
         [0054]    Step S 44 , S 46 , and S 50  are then repeated to convert the trajectory data t 1  into t 1 =ADEHI. When one piece of trajectory data is converted, the determination at step S 40  becomes Y, the process moves to step S 42 , the sequential data generating unit  34  stores the sequential data s in the set S of sequential data (see  FIG. 6B ), and the process goes back to step S 34 . 
         [0055]    Step S 36  through S 50  are repeated until the determination at step S 34  becomes Y, and when the set T becomes empty, i.e. when the determination at step S 34  becomes Y, the process illustrated in  FIG. 8  ends. The above process allows the sequential data of the trajectory data t 1  through t 8  to be stored in the set S of sequential data as illustrated in  FIG. 6B . 
       (Step S 14 : Frequency Mining Process) 
       [0056]    A description will now be given of the frequency mining process (step S 14 ) by the frequency mining unit  36 . As step S 14 , the process is executed along a flowchart illustrated in  FIG. 9 . 
         [0057]    In the process illustrated in  FIG. 9 , at step S 60 , the frequency mining unit  36  initializes J freq  and K freq  that are sets of execution results. 
         [0058]    At step S 62 , the frequency mining unit  36  then sets a threshold value (first frequency) to γ=2α+β, specifies 3 as a pattern size (the number of items), specifies a sector or inverse thereof as a form, and executes the frequent episode mining. The frequency mining unit  36  stores the execution result in J freq . 
         [0059]    Here, the episode pattern with a pattern size of 3 and a form of sector (or inverse thereof) is an episode pattern illustrated in  FIG. 10A  or  FIG. 10B . More specifically, as illustrated in  FIG. 10A , the episode pattern that includes two patterns (A→B→C, A→C→B), each including three items A, B, and C, both having A at the head, and the order of preceding B and C being arbitrary, is described as an sectorial episode pattern A→{B, C}. In addition, as illustrated in  FIG. 10B , the episode pattern that includes two patterns, each including three items A, B, and C, both having C at the end, and the order of A and B being arbitrary, (A→B→C, B→A→C) is described as an inverse sectorial episode pattern {A, B}→C. 
         [0060]    At step S 62 , the frequency mining unit  36  mines an episode pattern that can be represented with as A→{B, C} and has an appearance frequency greater than or equal to the threshold value γ (=2α+β) in the set T of sequential data illustrated in  FIG. 11A . 
         [0061]    Here, α represents the threshold value for an appearance frequency with which the sequential pattern is to be decided as an abnormal sequential pattern from sequential patterns represented with as A→B→C, A→C→B, or the like (pattern with a determined order). In addition, β represents the threshold value for a difference between appearance frequencies of a sequential pattern (e.g. A→B→C) to be decided as an abnormal sequential pattern and a sequential pattern (e.g. A→C→B) having a complementary relationship to the sequential pattern, i.e. a sequential pattern included in the same episode pattern. When α is set to 1 and β is set to 2, the threshold value γ used at step S 62  is 4 (γ=2.1+2=4). 
         [0062]      FIG. 11B  illustrates results of the frequent episode mining executed with a threshold value γ of 4. In the present example, A→{E, I}, which is indicated by a bold frame in  FIG. 11B , is extracted as the episode pattern with an appearance frequency greater than or equal to the threshold value γ=4. 
         [0063]    Back to  FIG. 9 , at step S 64 , the frequency mining unit  36  sets a threshold value (second frequency) to δ=α+β, specifies 3 as a pattern size, and executes the frequent sequential pattern mining. In this case, the frequency mining unit  36  extracts a sequential pattern with an appearance frequency greater than or equal to the threshold value δ=3 from sequential patterns represented with as “A→B→C” and the like in the set S of sequential data. The frequency mining unit  36  stores execution results in K freq . 
         [0064]    In this case, when α is 1 and β is 2, the threshold value δ becomes 3 (δ=1+2=3). 
         [0065]      FIG. 11C  illustrates results of the frequent sequential pattern mining that sets the threshold value δ to 3 at step S 64 . In the present example, A→E→I, A→F→I, and H→F→C, which are indicated by a bold frame in  FIG. 11C , are extracted as a sequential pattern with an appearance frequency greater than or equal to the threshold value δ=3. 
       (Step S 16 : Low-Frequency Sequence Extraction Process) 
       [0066]    A description will now be given of the low-frequency sequence extraction process (step S 16 ) by the low-frequency sequence extracting unit  38 . At step S 16 , the process is executed along the flowchart illustrated in  FIG. 12 . 
         [0067]    In the process in  FIG. 12 , at step S 70 , the low-frequency sequence extracting unit  38  initializes a set C of complementary sequential pattern pairs. At step S 72 , the low-frequency sequence extracting unit  38  then determines whether all episode patterns in the set J freq , which is a set of results of the frequent episode mining, are processed. When the determination is N, the process moves to step S 74 . 
         [0068]    At step S 74 , the low-frequency sequence extracting unit  38  extracts one episode pattern j from the set J freq  of the execution results of the frequent episode mining. Here, the episode pattern A→{E, I} with an appearance frequency greater than or equal to the threshold value γ=4, which is indicated with a solid line arrow in  FIG. 13A , is extracted from the execution results of the frequent episode mining. 
         [0069]    At step S 76 , the low-frequency sequence extracting unit  38  then determines whether all sequential patterns in the set K freq , which is a set of execution results of the frequent sequential pattern mining, are processed. When the determination is N, the process moves to step S 78 . 
         [0070]    At step S 78 , the low-frequency sequence extracting unit  38  extracts one sequential pattern k from the set K freq  of the execution results of the frequent sequential pattern mining. For example, the low-frequency sequence extracting unit  38  extracts A→E→I indicated with a dashed line arrow in  FIG. 13B . 
         [0071]    At step S 80 , the low-frequency sequence extracting unit  38  determines whether the patterns k c  and k obtained from j and k form a complementary sequential pattern pair. Here, the low-frequency sequence extracting unit  38  decides a sequential pattern other than the sequential pattern k as k c  in the sequential patterns included in the episode pattern j based on the episode pattern j and the sequential pattern k. As described above, when the episode pattern j is A→{E, I} and the sequential pattern k is A→E→I, obtained as the sequential pattern k c  is A→I→E. Then, the low-frequency sequence extracting unit  38  compares the sequential patterns k and k c , and determines whether the sequential pattern k: A→E→I and the sequential pattern k c : A→I→E form a complementary sequential pattern pair. In the above example, the sequential pattern k: A→E→I and the sequential pattern k c : A→I→E form a complementary sequential pattern pair, and thus the determination at step S 80  becomes Y, and the process moves to step S 82 . 
         [0072]    When A→F→I is extracted as the sequential pattern k at step S 78  for example, the pattern k c  can not be obtained from the episode pattern j and the sequential pattern k at step S 80 . In such a case, the determination at step S 80  becomes N, and the process goes back to step S 78 . 
         [0073]    When the determination at step S 80  is Y and the process goes to step S 82 , the low-frequency sequence extracting unit  38  determines whether the frequency of the sequential pattern k c  is greater than or equal to α (=1) and the difference between frequencies of k and k c  is greater than or equal to β (=2). When the determination at step S 82  is N, the process goes back to step S 72 , but when the determination is Y, the process goes to step S 84 . In a case of the sequential pattern k c : A→I→E, the determination becomes Y because the appearance frequency is 1 as illustrated in  FIG. 13B , and the process goes to step S 84 . 
         [0074]    At step S 84 , the low-frequency sequence extracting unit  38  stores the complementary sequential pattern pair (k, k c ) in C (see  FIG. 13C ), and the process goes back to step S 72 . 
         [0075]    The process and determination after step S 72  are repeated until the determination at step S 72  becomes N, and the process in  FIG. 12  ends when the determination at step S 72  becomes N. The remaining sequential patterns A→F→I and H→F→C illustrated in  FIG. 13B  do not generate the sequential pattern k c  with the episode pattern A→{E, I}, and thus the complementary sequential pattern pair (k, k c ) is not stored in C based on these remaining sequential patterns. 
       (Step S 18 : Abnormal Trajectory Determination Process) 
       [0076]    A description will now be given of the abnormal trajectory determination process (step S 18 ) by the abnormal trajectory determination unit  40 . At step S 18 , the process is executed along the flowchart illustrated in  FIG. 14 . 
         [0077]    In the process illustrated in  FIG. 14 , at step S 102 , the abnormal trajectory determination unit  40  initializes a set A. At step S 104 , the abnormal trajectory determination unit  40  then determines whether all data in C (the complementary sequential pattern pairs stored by the process in  FIG. 12 ) is processed. When the determination is N, the process goes to step S 106 . 
         [0078]    At step S 106 , the abnormal trajectory determination unit  40  extracts one complementary sequential pattern pair (k, k c ) from C. Here, assume that the abnormal trajectory determination unit  40  extracts (k, k c )=(A→E→I, A→I→E) illustrated in  FIG. 13C . 
         [0079]    At step S 108 , the abnormal trajectory determination unit  40  determines whether all data in the set T of trajectory data ( FIG. 2 ) is processed. When the determination is N, the process goes to step S 112 . 
         [0080]    At step S 112 , the abnormal trajectory determination unit  40  extracts one piece of trajectory data t from the set T. Here, the trajectory data t 1  is extracted for example. 
         [0081]    At step S 114 , the abnormal trajectory determination unit  40  then initializes ID normal  and ID abnormal . At step S 116 , the abnormal trajectory determination unit  40  determines whether the trajectory data t passes all the regions with the mesh IDs of the sequential pattern k included in the complementary sequential pattern pair (k, k c ) in the order. When the determination is Y, the process goes to step S 118 , the abnormal trajectory determination unit  40  stores t in ID normal , and the process moves to step S 120 . On the other hand, when the determination at step S 116  is N, the process skips step S 118 , and moves to step S 120 . 
         [0082]    At step S 120 , the abnormal trajectory determination unit  40  determines whether the trajectory data t passes all the regions with the mesh IDs of the sequential pattern k c  included in the complementary sequential pattern pair (k, k c ) in the order. When the determination is Y, the process moves to step S 122 , and the abnormal trajectory determination unit  40  stores t in ID abnormal , and goes back to step S 108 . On the other hand, when the determination at step S 120  is N, the process skips step S 122  and goes back to step S 108 . 
         [0083]    In the present embodiment, the trajectory data t 1  is t 1 =ADEHI and passes all the regions with the mesh IDs of the pattern pair k=A→E→I in the order thereof, and thus t 1  is stored in ID normal  at step S 118 . 
         [0084]    When the process goes back to step S 108 , the abnormal trajectory determination unit  40  determines whether all data in the set T of trajectory data ( FIG. 2 ) is processed. When the determination is Y, the process moves to step S 110 , and the abnormal trajectory determination unit  40  stores (ID normal , ID abnormal ) in the set A. The process then goes back to step S 104 . In the present embodiment, each of the trajectory data t 1  through t 8  is determined whether it includes the sequential pattern k or k c  as illustrated in  FIG. 15A . In this case, t 1 , t 2 , and t 3  indicated with bold solid lines on the coordinate plane in  FIG. 15A  are stored in ID normal  in the set A (see  FIG. 15B ). In addition, t 4  indicated with a bold dashed line on the coordinate plane in  FIG. 15A  is stored in ID abnormal  in the set A (see  FIG. 15B ). 
         [0085]    Back to  FIG. 14 , at step S 104 , the abnormal trajectory determination unit  40  determines whether all data in the set C (the complementary sequential pattern pairs stored by the process in  FIG. 12 ) is processed as described above. When the determination is N, the process after step S 106  are executed as described above. On the other hand, when the determination at step S 104  is Y, the process of  FIG. 14  ends. 
         [0086]    The output unit  42  outputs the set A of pairs of a normal trajectory and an abnormal trajectory illustrated in  FIG. 15B  to the user terminal  20  (step S 20  in  FIG. 7 ). 
         [0087]    Here, a description will be given of the reason why the threshold value γ for the frequent episode mining is set to γ=2α+β and the threshold value δ for the frequent sequential pattern mining is set to δ=α+β. 
         [0088]    When the complementary sequential pattern pair (k, k c ) exists, both the sequential patterns k and k c  have appearance frequencies greater than or equal to α. In addition, when k represents the sequential pattern with a higher appearance frequency between the sequential patterns k and k c , the difference between appearance frequencies of the sequential patterns k and k c  is greater than or equal to β, and thus α+β is proper for the threshold value (δ). 
         [0089]    In addition, when the number of trajectory data that matches the sequential pattern k is represented with |k|, the number of trajectory data that matches the sequential pattern k c  is represented with |k c |, and the number of trajectory data that matches the episode pattern j corresponding to the sequential patterns k and k c  is represented with |j|, |j|≧|k|+|k c | holds true when the complementary sequential pattern pair is formed. Moreover, the k c  is a pattern with a frequency greater than or equal to α. Therefore, γ=2α+β is proper for the threshold value (γ) used for the frequent episode mining. 
         [0090]    The threshold values γ and δ determined as described above allow the frequent episode mining and the frequent sequential pattern mining to be executed properly. That is to say, suppressed is a detection omission of (k, k c ) caused by making the threshold values greater than the above described values and the occurrence of the extra process caused by making the threshold values less than the above described values. When the threshold values γ and δ are determined as described above, step S 82  in  FIG. 12  can be omitted. In this case, when the determination at step S 80  becomes Y, the process may directly go to step S 84 . 
         [0091]    As described above, the present embodiment demonstrates that the frequency mining unit  36  extracts an episode pattern with an appearance frequency greater than or equal to the threshold value γ by the frequent episode mining and extracts a sequential pattern with an appearance frequency greater than or equal to the threshold value δ by the frequent sequential pattern mining in the set S of sequential data. The low-frequency sequence extracting unit  38  specifies, when a sequential pattern corresponding to the extracted episode pattern is extracted, a sequential pattern other the extracted sequential pattern from sequential patterns included in the episode pattern, and decides an abnormal sequential pattern from the specified sequential pattern. The above process allows the present embodiment to reduce the calculation amount and calculation time for deciding the abnormal sequential pattern because the use of the frequent episode mining and the frequent sequential pattern mining enables to narrow sequential patterns that may be the abnormal sequential pattern, i.e. to exclude the disinterested sequential pattern. Therefore, the present embodiment can improve the efficiency of the process. 
         [0092]    Here, a description will be given of a case where only the frequent sequential pattern mining is used (comparison example: Patent Document 1). In the comparison example, assume that the frequent sequential pattern mining extracts a sequential pattern of A→E→I as a high-frequency sequential pattern (see  FIG. 6A ,  FIG. 6B , and the like). In this case, the server  30  needs to examine frequencies of all sequential patterns with different orders from A→E→I (A→I→E, I→A→E, I→E→A, E→A→I, E→I→A), and to extract even a low-frequency sequential pattern when it has an appearance frequency, for example, greater than or equal to 1. As described above, the comparison example is inefficient in the calculation amount and the calculation time because sequential patterns to be examined increase, but the method of the present embodiment can reduce the calculation amount and the calculation time. 
         [0093]    In addition, the present embodiment does not process an episode pattern with an appearance frequency less than or equal to the threshold value 3 illustrated in  FIG. 13A  at all, and thus is efficient from this aspect. 
         [0094]    In addition, the present embodiment determines the episode pattern extracted by the frequent episode mining to have an appearance frequency greater than or equal to γ (=2α+β), and determines the episode pattern extracted by the frequent sequential pattern mining to have an appearance frequency of greater than or equal to δ (=α+β). This enables to properly narrow sequential patterns that may be an abnormal sequential pattern. 
         [0095]    The above described embodiment describes a sectorial episode pattern illustrated in  FIG. 10A  as an example, but does not intend to suggest any limitation, and an inverse sectorial episode pattern illustrated in  FIG. 10B  may be used. 
         [0096]    The above described embodiment demonstrates that the output unit  42  outputs a pair of the normal trajectory and the abnormal trajectory to the user terminal  20 , but does not intend to suggest any limitation, and the output unit  42  may output only the information about the abnormal trajectory to the user terminal  20 . 
         [0097]    The above embodiment adopts the information processing system  100  to traffic field, but does not intend to suggest any limitation, and the information processing system  100  may be adopted to detect abnormal trail data in BPM (Business Process Management) field. For example, when the business process usually flows as “issue→check→approval by department chief→approval by manager→order”, the information processing system of the above described embodiment can be used to detect a trail pattern that has a flow of “issue→check→approval by manager→approval by department chief→order”. 
         [0098]    The above described embodiment demonstrates that the server  30  executes the process in  FIG. 7 , but does not intend to suggest any limitation, and the user terminal  20  may execute the process in  FIG. 7 . 
         [0099]    The above described processing function can be achieved by a computer. In that case, a program in which the process of the function that the processing device is to have is written is provided. The execution of the program by the computer allows the above described processing function to be achieved on the computer. The program in which the process is written may be stored in a computer readable storage medium (however, transitory storage medium, e.g. carrier, is excluded). 
         [0100]    The program is distributed by selling a portable storage medium such as a DVD (Digital Versatile Disc) and a CD-ROM (Compact Disc Read Only Memory) in which the program is stored. In addition, the program may be stored in a storage medium in a server computer, and transferred to other computers from the server computer through the network. 
         [0101]    The computer executing the program stores the program stored in a portable storage medium or the program transferred from the server computer in the storage device thereof. The computer then reads out the program from the storage device thereof and executes the process following the program. The computer may directly read out the program from the portable storage medium, and execute the process following the program. The computer may execute the process following the program every time when the program is transferred from the server computer. 
         [0102]    All examples and conditional language recited herein are intended for pedagogical purposes to aid the reader in understanding the invention and the concepts contributed by the inventor to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions, nor does the organization of such examples in the specification relate to a showing of the superiority and inferiority of the invention. Although the embodiments of the present invention have been described in detail, it should be understood that the various change, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention.