JP6557192B2 - Clustering apparatus and clustering method - Google Patents

Description

  The present invention relates to a clustering apparatus and a clustering method.

  Conventionally, an analysis technique for moving object data is known. Conventional analysis techniques are classified into, for example, a technique that focuses on individual moving bodies and a technique that focuses on a plurality of moving bodies as a whole. Conventional analysis techniques are classified into a technique focused on a place where the moving body moves and a technique focused on a detailed trajectory of the moving body.

  As a technique focusing on individual moving bodies and places, for example, a technique for estimating a staying place using a staying time and POI (Point of interest) information at each passing point of the moving body is known. As a technique focused on the entire moving body and the place, for example, a technique for obtaining a high-density place through which a plurality of moving bodies have passed is known.

  Further, as a technique focusing on individual moving bodies and trajectories, for example, a technique is known in which a map is divided into meshes and a destination is predicted from transition probabilities between meshes based on detailed trajectories. As a technique focusing on the entire moving body and the trajectory, for example, a technique is known in which the trajectory of the moving body is applied to a multiple regression mixed normal distribution model and the trajectory included in the same model is detected as a common movement route.

Martin Ester, Hans-Peter Kriegel, Jorg Sander, and Xiaowei Xu: “A density-based algorithm for discovering clusters in large spatial databases with noise,” KDD, pp.226-231, 1996. Yusuke Kumagai, Ryota Imai, Tatsushi Matsubayashi: “Analysis of migratory behavior of foreign tourists using non-negative compound tensor factorization,” IBISML, 2015. Scott Gaffney, and Padhraic Smyth: “Trajectory Clustering with Mixtures of Regression Models,” KDD, pp.63-72, 1999. Jae-Gil Lee, Jiawei Han, Kyu-Young Whang: “Trajectory clustering: a partition-and-group framework,” SIGMOD, pp.593-604, 2007.

  However, the conventional technique has a problem in that it may not be possible to acquire analysis results focused on both the location and the locus from the moving body data. For example, in a technique for obtaining a place where the density of points is high, there is a case where an analysis result focused on a locus cannot be obtained. In addition, for example, in the technique of detecting a trajectory included in the same multiple regression mixed normal distribution model as a common movement route, there is a case where an analysis result focused on a place cannot be acquired.

  The clustering device of the present invention includes a dividing unit that divides a predetermined area into a plurality of areas by a plurality of patterns, and a moving direction of data points in the area for each of the plurality of areas for each of the plurality of patterns. Based on the angle between, calculate a value indicating the magnitude of the tendency of the data points in the area to intersect, classify the area where the value is greater than or equal to a predetermined value among the plurality of areas as a first area, A classifying unit that classifies a zone whose value is not equal to or greater than a predetermined value among the plurality of zones as a second zone, and a distance between the positions of the data points and the data for each zone classified as the first zone Clustering data points within an area using a first measure based on both angles between the direction of movement of the points, and for each of the areas classified as the second area, the distance between the positions of the data points And transfer of the data points A clustering unit for clustering data points in a zone using a second measure based on both angles between directions, and for each of the plurality of patterns, the number of zones based on the result of clustering by the clustering unit A calculator for calculating a first cost proportional to the size of the area, the number of data points in the area, the number of clusters and the number of data points not included in any cluster, and And a selection unit that selects a pattern having the smallest first cost as an optimal solution.

  The clustering method of the present invention is a clustering method executed by a clustering apparatus, wherein a predetermined area is divided into a plurality of areas by a plurality of patterns, and the plurality of areas for each of the plurality of patterns. For each of the above, a value indicating the magnitude of the tendency of the data points in the area to intersect is calculated based on the angle between the movement directions of the data points in the area. For each area classified into the first area, a classification process for classifying an area that is a first area, and classifying an area in which the value is not equal to or greater than a predetermined value among the plurality of areas as a second area; Clustering the data points in the area using a first measure based on both the distance between the positions of the data points and the angle between the movement directions of the data points, and are classified into the second area For each zone, a clustering step for clustering the data points in the zone using a second measure based on both the distance between the positions of the data points and the angle between the movement directions of the data points; For each pattern, based on the result of clustering in the clustering step, the number of areas, the size of the area, the number of data points in the area, the number of clusters and the number of data points not included in any cluster. The method includes a calculation step of calculating a proportional first cost, and a selection step of selecting a pattern having the smallest first cost among the plurality of patterns as an optimal solution.

  According to the present invention, it is possible to acquire an analysis result focusing on both a place and a locus from moving body data.

FIG. 1 is a diagram illustrating an example of the configuration of the clustering apparatus according to the first embodiment. FIG. 2 is a diagram illustrating an example of mobile object data input to the clustering apparatus. FIG. 3 is a diagram for explaining a direction calculation method. FIG. 4 is a diagram illustrating an example of the moving body data after conversion. FIG. 5 is an example of a diagram created based on mobile object data. FIG. 6 is a diagram for explaining processing of the clustering apparatus. FIG. 7 is a diagram illustrating an example of a division pattern. FIG. 8 is a diagram for explaining a tendency of a dense area cluster. FIG. 9 is a diagram for explaining the tendency of the common movement locus cluster. FIG. 10 is a diagram illustrating an example of the clustering result. FIG. 11 is a flowchart showing the flow of processing of the clustering apparatus according to the first embodiment. FIG. 12 is a diagram illustrating an example of a computer in which a clustering apparatus is realized by executing a program.

[Configuration of First Embodiment]
Hereinafter, embodiments of a clustering apparatus and a clustering method according to the present application will be described in detail with reference to the drawings. In addition, this invention is not limited by this embodiment. First, the configuration of the clustering apparatus according to the first embodiment will be described with reference to FIG. FIG. 1 is a diagram illustrating an example of the configuration of the clustering apparatus according to the first embodiment. As illustrated in FIG. 1, the clustering apparatus 10 includes an input unit 11, an output unit 12, a control unit 13, and a storage unit 14.

  The input unit 11 receives, for example, input of moving body data. The input unit 11 is an input device such as a mouse or a keyboard, for example. The output unit 12 outputs data by screen display or the like. The output unit 12 is a display device such as a display for displaying the result of clustering, for example.

  The control unit 13 controls the entire clustering apparatus 10. The control unit 13 is, for example, an electronic circuit such as a CPU (Central Processing Unit) or MPU (Micro Processing Unit), or an integrated circuit such as an ASIC (Application Specific Integrated Circuit) or an FPGA (Field Programmable Gate Array). The control unit 13 has an internal memory for storing programs and control data defining various processing procedures, and executes each process using the internal memory. The control unit 13 functions as various processing units when various programs are operated. For example, the control unit 13 includes a conversion unit 131, a division unit 132, a classification unit 133, a clustering unit 134, a calculation unit 135, and a selection unit 136.

  The storage unit 14 is a storage device such as a hard disk drive (HDD), a solid state drive (SSD), and an optical disk. The storage unit 14 may be a semiconductor memory capable of rewriting data, such as a RAM (Random Access Memory), a flash memory, and an NVSRAM (Non Volatile Static Random Access Memory). The storage unit 14 stores an OS (Operating System) executed by the clustering apparatus 10 and various programs. Furthermore, the memory | storage part 14 memorize | stores the various information used by execution of a program.

  The moving body data will be described with reference to FIG. FIG. 2 is a diagram illustrating an example of mobile object data input to the clustering apparatus. The moving object data is data including information on the position and moving direction of the moving object. The mobile data shown in FIG. 2 is a part of human flow data (reference URL: http://bdm.change-jp.com/?p=1705) of the human flow project at the University of Tokyo. Human flow data is flow data of people around each metropolitan area estimated from person trip survey data conducted in the national or local government. The human flow data includes attributes such as longitude and latitude of the position of each user at each time for each day. In this case, the user is a moving body.

  For example, in the data on the first line in FIG. 2, the user whose user ID is 1 was at a position where the latitude was 35.68384513 and the longitude was 139.88991337 at 2013/7/1 9:45:00. Is shown. The user ID is an ID for identifying the user.

  The conversion unit 131 converts the moving body data input to the clustering apparatus 10 into data in a predetermined format. For example, as illustrated in FIG. 3, the conversion unit 131 arranges input mobile body data in time series for each user, and calculates a direction based on changes in latitude and longitude. FIG. 3 is a diagram for explaining a direction calculation method.

  Here, the point id is an ID for identifying the position of the user at each time. For example, the latitude of the position of the data point with the point id 1 is 35.68384513 and the longitude is 139.88991337. Further, for example, the latitude of the position of the data point with the point id 2 is 35.683243287 and the longitude is 139.7735728. Even if the positions are the same, different points may be set when the users are different.

  For example, the conversion unit 131 calculates the direction at the position of the data point with the point id 1 for the user with the user ID 1 using the data in the first and second rows in FIG. 3. In addition, since the data in the subsequent position does not exist in the data on the third line in FIG. 3, the conversion unit 131 deletes the data on the third line in FIG. The direction at the position of the data point whose id is 3 is not calculated.

  FIG. 4 is a diagram illustrating an example of the moving body data after conversion. As shown in FIG. 4, the converted moving body data includes a point id, a latitude, a longitude, and a direction. Further, for example, as shown in FIG. 4, the direction is represented by an angle. For example, the latitude of the position of the data point with the point id 1 is 35.68384513, the longitude is 139.88991337, and the direction is π / 3.

  FIG. 5 is an example of a diagram created based on mobile object data. FIG. 5 is a plot of data corresponding to each point id included in the converted moving body data shown in FIG. 4 on a map. As shown in FIG. 5, the data corresponding to each point id of the moving object is represented by an arrow. The root position of the arrow in FIG. 5 corresponds to the latitude and longitude of each data, and the direction of the arrow corresponds to the direction of each data.

  Note that the mobile data conversion may be performed by a device other than the clustering device 10. When data suitable for clustering by the clustering device 10 is input, the conversion process by the conversion unit 131 may not be performed.

  The subsequent processing will be described with reference to FIG. FIG. 6 is a diagram for explaining processing of the clustering apparatus. The clustering apparatus 10 performs processing by iteration. First, the first iteration process will be described, and then the second and subsequent processes will be described. Note that the clustering apparatus 10 may perform only the first process.

[First time processing]
First, as illustrated in (1-1) in FIG. 6, the dividing unit 132 selects all the regions as regions to be analyzed among regions that are targets of moving body data. Hereinafter, the area selected by the dividing unit 132 is referred to as an area. Next, as illustrated in (1-2) of FIG. 6, the dividing unit 132 divides the area into a plurality of areas with a plurality of patterns. For example, as shown in FIG. 7, the dividing unit 132 divides the entire area into cells of a predetermined size and meshes it, and then divides an area with a predetermined latitude as a vertical line and a predetermined longitude as a horizontal line. FIG. 7 is a diagram illustrating an example of a division pattern. As illustrated in FIG. 7, the dividing unit 132 divides, for example, an area composed of 3 × 3 cells into four patterns.

  By the way, a crowded area is an area where there are facilities where many people gather, such as stations and shopping malls. On the other hand, the common movement locus is a route used by many people, such as a main road.

  Conventionally, the dense area has been determined based on, for example, the density at each passing point of the moving body. Conventionally, the common movement trajectory has been determined based on the similarity of the trajectory considering the moving direction of the moving object. As described above, the dense area and the common movement trajectory are determined on different scales such as density and direction. In the first embodiment, the clustering apparatus 10 regards a dense area and a common movement trajectory as a cluster, and generates a dense area cluster or a common movement trajectory cluster in a section using the same scale.

  As shown in FIG. 8, in a dense area cluster, the data points tend to intersect, that is, the distance between the data points is close and the data points move in various directions. FIG. 8 is a diagram for explaining a tendency of a dense area cluster. In the common movement locus cluster, the tendency of data points to intersect is small. That is, as shown in FIG. 9, in the common movement trajectory cluster, the data points tend to move in a certain direction. FIG. 9 is a diagram for explaining the tendency of the common movement locus cluster. The data point is data in which the position and moving direction of the moving object are defined. Details of the data points will be described later.

  Thus, it can be said that the distance between the data points and the moving direction of the data points are a scale common to both the dense area cluster and the common moving locus cluster. Further, it can be said that the dense area and the common movement trajectory cluster can be distinguished by the difference in movement direction tendency. Therefore, the classification unit 133 classifies the areas for each division pattern by the division unit 132 based on the moving direction of the data points. Specifically, for each of a plurality of patterns, the classification unit 133 determines the magnitude of the tendency of the data points in the area to intersect based on the angle between the movement directions of the data points in the area. Is calculated, and a zone having a value greater than or equal to a predetermined value among the plurality of zones is classified as a first zone, and a zone having a value not greater than or equal to the predetermined value among the plurality of zones is classified as a second zone. Here, the first area is a dense area area. The second area is a common movement locus area.

Here, of the moving body data, the moving body data for a certain user is represented by a series {p ₁ , p ₂ , each element having a position coordinate represented by latitude and longitude, and a moving direction represented by an angle. ,..., _Pn }. Here, the data point is each element of the series. The moving direction of the data point p _i is expressed as p _i → p _{i + 1} . Since the data points are identified at point id, when the data point is 1 id point 4 and _{p 1,} the position coordinates of _{p 1} is (35.68384513,139.8991337), movement of _{p 1} The direction p ₁ → p ₂ is π / 3.

The classification unit 133 calculates the angle θ generated by the moving direction for all pairs of data points in the area. The range of θ is 0 ≦ θ ≦ π. For example, the classification unit 133 represents the angle θ generated by the moving direction of p _i and p _j and the difference between p _i → p _{i + 1} and p _j → p _{j + 1 in} the range of 0 ≦ θ ≦ π. can do. For example, when p _i → p _{i + 1} −p _j → p _{j + 1} = π / 2, the classification unit 133 sets θ = π / 2. For example, when p _i → p _{i + 1} −p _j → p _{j + 1} = 3π / 2, the classification unit 133 sets θ = π / 2. For example, when p _i → p _{i + 1} −p _j → p _{j + 1} = −π / 3, the classification unit 133 sets θ = π / 3.

  Then, the classification unit 133 determines that, among the calculated θ, the number of θ that satisfies π / 4 ≦ θ ≦ 3π / 4 is greater than the number of θ that satisfies 0 ≦ θ <π / 4∨3π / 4 <θ ≦ π. A large area is classified as a first area, that is, a dense area. Further, the classification unit 133 includes the number of θs satisfying 0 ≦ θ <π / 4 ／ 3π / 4 <θ ≦ π among the calculated θs equal to or greater than the number of θs satisfying π / 4 ≦ θ ≦ 3π / 4. Is classified as a second area, that is, a common movement trajectory area.

  In other words, the classification unit 133 has a ratio of the number of pairs in which the difference between θ and π / 2 is 4 / π or less to the number of combinations of data points in which the difference between θ and π / 2 is larger than 4 / π. If it is greater than or equal to 1, the area is classified as a dense area area, and if the ratio is less than 1, the area is classified as a common movement trajectory area.

  In this way, the classification unit 133 calculates the ratio between the number of θs satisfying π / 4 ≦ θ ≦ 3π / 4 and the number of θs satisfying 0 ≦ θ <π / 4∨3π / 4 <θ ≦ π. The value indicates the magnitude of the tendency of the data points to intersect. That is, there are many intersecting data points in a dense area area, that is, an area where the number of θs satisfying π / 4 ≦ θ ≦ 3π / 4 is large.

  On the other hand, in a common movement trajectory area, that is, an area where the number of θ satisfying 0 ≦ θ <π / 4π3π / 4 <θ ≦ π is small, there are few data points intersecting and data points having the same moving direction, or There will be many data points with opposite directions of movement. In such a case, it is possible that a route having an up direction and a down direction exists in the area.

  The clustering unit 134 uses, for each area classified as the first area, a data point in the area using a first measure based on both the distance between the data point positions and the angle between the movement directions of the data points. For each zone classified as a second zone, using a second measure based on both the distance between the positions of the data points and the angle between the direction of movement of the data points. Perform clustering.

The clustering unit 134 calculates a first scale dist _D representing the relationship between the data points p _i and the data points p _j by the equation (1) for the first area, that is, the area classified as the dense area area, Based on dist _D , each data point in the area is clustered. Hereinafter, the first scale dist _D is referred to as a dense area distance. Where δ is a scale factor, θ is an angle generated by p _i → p _{i + 1} and p _j → p _{j + 1} , and ED (p _i , p _j ) is a Euclidean between the position coordinates of the data point p _i and the data point p _j. The distance is set, and the range of θ is 0 ≦ θ ≦ π.

In addition, the clustering unit 134 calculates a second scale dist _T representing the relationship between the data point p _i and the data point p _j by the expression (2) for the second area, that is, the area classified as the common movement locus area. Compute and cluster each data point in the area based on dist _T. Hereinafter, the second scale dist _T is referred to as a common movement trajectory distance. However, as in the equation (1), δ is a scale factor, θ is an angle generated by p _i → p _{i + 1} and p _j → p _{j + 1} , and ED (p _i , p _j ) is a data point p _i and a data point. Let Euclidean distance between the position coordinates of p _j . In the formula (2), the range of θ is set to 0 ≦ θ ≦ π / 2.

  From equation (1), the closer the Euclidean distance between the position coordinates of the two points is to 0 and the closer the angle generated by the moving direction is to π / 2, the closer the value of the dense area distance is to 1, which is the maximum value. Become. That is, the dense area distance is a measure proportional to the short distance between the positions of the two data points and the sine value of the angle between the moving directions.

  On the other hand, as the Euclidean distance between the position coordinates of the two points is closer to 0 and the angle generated according to the moving direction is closer to 0, the value of the common movement trajectory distance is set to 1 which is the maximum value. Get closer. That is, the common movement trajectory distance is a measure proportional to the short distance between the positions of the two data points and the cosine value of the angle between the movement directions.

For example, when the minimum distance threshold Min _dist and the minimum density threshold Min _density are given, the clustering unit 134 uses the dense area distance for the dense area area and uses the common movement locus distance for the common movement locus area. Thus, clustering can be performed by the density-based clustering method described in Non-Patent Document 1. Note that the clustering method of the clustering unit 134 is not limited to the above method, and can be any clustering method using a scale based on both the distance between the positions of the data points and the angle between the movement directions of the data points. . Further, the result of clustering by the clustering unit 134 is represented by which cluster each data point is included. At this time, there may be data points that are not included in any cluster, and such data points are referred to as noise.

  (1-3) in FIG. 6 represents a clustering result for each division pattern by the clustering unit 134. A region surrounded by a curve (1-3) in FIG. 6 indicates a cluster of a dense area. Moreover, the arrow of (1-3) of FIG. 6 has shown the cluster of the common movement locus | trajectory area. That is, the cluster of data points surrounded by the curves in the area surrounded by the thick line in each division pattern of (1-3) in FIG. 6 is a dense area cluster. A cluster of data points surrounded by arrows in the area surrounded by a thick line in each division pattern of (1-3) in FIG. 6 is a common movement locus cluster.

  The calculation unit 135 is included in the number of areas, the size of the area, the number of data points in the area, the number of clusters, and the number of clusters for each of the plurality of patterns based on the result of clustering by the clustering unit 134. Calculate a first cost proportional to the number of missing data points.

  The calculation unit 135 calculates the MDL cost as the first cost for each division pattern. The MDL cost is calculated by a method based on MDL (minimum description length) which is a model selection criterion. The MDL cost is a score for evaluating the clustering result of each divided pattern. Note that MDL is expressed by a combination of two cost functions as shown in Equation (3).

  For example, when MDL is used as a reference when selecting a compression model of data, Cost (H) is a cost for expressing the compression model H. At this time, the simpler the compression model, the smaller Cost (H). On the other hand, Cost (D | H) is the quality of the compression, that is, the cost for expressing the data D by the model H. That is, the higher the degree of matching between the data and the model assigned to the data, the smaller Cost (D | H). In MDL, the sum of these two costs is selected and the optimum data compression is achieved in which data is expressed with a small number of codes.

First, values included in Cost (H) used for calculation by the calculation unit 135 are defined as follows.
The number of the generated zone n: ^log * (n) number of cells in the bit each zone _{^{ni n c: Σ n i =}} 1 log * (n c) the number of bits _{n p} data points in each zone ni: Σ ⁿ _{i = 1} log ^* (n _p ) bits where log ^* (x) is the universal code length, log ^* (x) = log ₂ (2.865) + log ₂ (x) + log ₂ log ₂ (x) + …It can be expressed as.

Assuming that a set of clusters C = {c ₁ , c ₂ ,..., C _m } and K noises are generated in each section by clustering by the clustering unit 134, first, the calculation unit 135 first calculates the expression (4). The entropy code is calculated as shown in FIG.

Here, q _i in Equation (4) represents the occurrence probability of event i. As the number of events represented in the data set is larger and the probability of occurrence of each event is more equal, the minimum code for representing data becomes longer and the entropy code becomes larger. On the other hand, the smaller the number of events represented in the data set and the bias in the occurrence probability of each event, the shorter the minimum code for representing the data and the smaller the entropy code.

Therefore, calculation unit 135, the same type of clusters and individual noise generated regarded as a single event, the minimum code length cost for representing data points p _i in each area by the equation (5) calculate.

Here, | c _i | is the number of data points included in cluster c _i , m is the number of clusters, and k is the number of noises. The smaller the number of clusters generated in an area or the number of data points judged as noise, the smaller the value of E _pi . This contributes to representing the data points included in each area with one cluster with less noise.

Then, the calculation unit 135 sets the code length cost E _ni representing all the data points in the area to E _ni = n _p · E _pi , the number of the divided areas as n, and sets all the data points in the data area. The cost Cost (D | H) for expressing is calculated as Cost (D | H) = Σ ⁿ _{i = 1} E _ni .

The cost E _ni representing all the data points in each area indicates the need for subdivision for that area. An area with a large E _ni means that it is not appropriate to represent all the data points in the area by the estimated kind of cluster, and re-estimate the kind for the data points in the subdivision and subdivision areas By performing the above, a higher quality clustering result can be obtained.

As described above, the calculation unit 135 calculates the code length cost Cost (D, H) when the candidate solution Z = {{C, k} | {n, {n _c }, {n _p }} is given by the formula ( Calculate as in 6).

The selection unit 136 selects a pattern having the smallest first cost among the plurality of patterns as an optimal solution. That is, as shown in (1-4) of FIG. 6, Cost _t-1 (D, H) is set as the cost of the division pattern having the smallest first cost. A pattern surrounded by a broken line in (1-4) of FIG. 6 is an example of Cost _t-1 (D, H) determination. Note that t-1 indicates the number of iterations. Since what is described here is an initial iteration process, t−1 can be set to 1, for example.

[Second and subsequent processing]
So far, the first iteration process has been described. Here, the second and subsequent iteration processing will be described. For each area included in the previous optimal pattern, which is the pattern selected as the optimal solution by the selection unit 136, the calculation unit 135 is proportional to the number of clusters and the number of data points not included in any cluster. Compare costs. The second cost is the aforementioned E _ni . For example, in the second iteration process, the calculation unit 135 compares E _ni for each area of the pattern selected in the first process.

The dividing unit 132 further divides the area having the largest second cost into a plurality of areas with a plurality of patterns. For example, in the second iteration process, as shown in (2-2) of FIG. 6, the dividing unit 132 determines that the area where E _ni is the largest, that is, the left area of (2-1) of FIG. 6. Is further divided.

  For example, in the second iteration process, the clustering unit 134 further performs clustering as shown in (2-3) of FIG. Then, the calculation unit 135 further calculates Cost (D, H).

The selection unit 136 selects the pattern having the smaller first cost as the optimum solution from the present optimum pattern and the previous optimum pattern which are the patterns having the smallest first cost among the plurality of patterns, and selects the optimum pattern this time. When the optimal solution is selected, the optimal pattern is given to the dividing unit 132 this time, and further processing is executed. Hereinafter, the optimal solution in each iteration is referred to as a local optimal solution. For example, in the second iteration process, the selection unit 136 sets Cost _t (D, H) as the first cost of the t-th local optimum solution as shown in (2-4) of FIG. . A pattern surrounded by a broken line in (2-4) of FIG. 6 is an example of Cost _t (D, H) determination.

When Cost _t (D, H) is greater than Cost _t−1 (D, H), the selection unit 136 selects the t−1th local optimum solution. Then, the clustering apparatus 10 causes the output unit 12 to output the pattern selected by the selection unit 136 as the final optimal solution.

On the other hand, when Cost _t (D, H) is smaller than Cost _t−1 (D, H), the selection unit 136 selects the t-th local optimum solution. Then, the selection unit 136 gives the selected pattern to the division unit 132 and further executes processing.

  The above-described processing described by taking the first and second times as an example can be extended to the (t−1) th and tth times. That is, the clustering apparatus 10 compares the MDL cost of the local optimum solution selected in the t-th iteration and the t−1 iteration. When the cost of the t-th iteration is smaller than the cost of the (t-1) -th iteration, the clustering apparatus 10 holds the result of the t-th iteration and executes the (t + 1) -th iteration.

  On the other hand, when the cost of the t-th iteration is greater than the cost of the t-1 iteration, the clustering apparatus 10 sets the result of the t-1 iteration as the final optimal solution.

A clustering result by the clustering apparatus 10 will be described with reference to FIG. FIG. 10 is a diagram illustrating an example of the clustering result. In the example of FIG. 10, the above-described human flow data is used, the cell size is 200 m × 200 m, and the minimum distance threshold Min _dist is the distance between the data points of the top 25 among all the data points in the area. This is a clustering result when clustering is performed by setting the average of the average distance and the minimum density threshold Min _density to the average of the densities of all data points in the area.

  A region surrounded by a rectangle in FIG. 10 is an area divided by the dividing unit 132. A cluster of data points surrounded by a curve is a dense area cluster. The area surrounded by the dashed rectangle is a dense area. A cluster of data points surrounded by white arrows is a common movement trajectory cluster. An area surrounded by a solid rectangle is a common movement locus area. The gray arrow is noise.

  As shown in FIG. 10, the dense area cluster matched the landmark (Tokyo Dome, Iidabashi Station). In addition, the common movement trajectory cluster matched a road (such as a national road). By performing the output as shown in FIG. 10, it is possible to confirm where the people who were in the predetermined area at the predetermined date and time are gathered and where.

[Process of First Embodiment]
A processing flow of the clustering apparatus 10 will be described with reference to FIG. FIG. 11 is a flowchart showing the flow of processing of the clustering apparatus according to the first embodiment. As shown in FIG. 11, the dividing unit 132 determines the cell size and meshes the data area (step S101).

  Next, the dividing unit 132 selects an area to be analyzed, and divides the area with a plurality of patterns (step S102). The classifying unit 133 classifies the areas into a dense area area and a common movement locus area based on the angle of the data points in the moving direction (step S103). The clustering unit 134 performs clustering on the data points based on the distance between the positions of the data points and the angle of the movement direction between the data points in both the dense area area and the common movement trajectory area (step S104).

The calculation unit 135 calculates the MDL cost based on the result of clustering by the clustering unit 134, and determines the cost Cost _t (D, H) of the local optimum solution (step S105). Here, if Cost _t (D, H) ≦ Cost _t−1 (D, H) (step S106, Yes), the clustering apparatus 10 returns the process to step S102 and repeats the process. If Cost _t (D, H) ≦ Cost _t−1 (D, H) is not satisfied (step S106, No), the clustering apparatus 10 outputs the clustering result (step S107) and ends the process.

[Effect of the first embodiment]
The dividing unit 132 divides the predetermined area into a plurality of areas with a plurality of patterns. For each of a plurality of patterns, the classification unit 133 calculates a value indicating the magnitude of the tendency of the data points in the area to intersect based on the angle between the movement directions of the data points in the area. Then, an area having a value greater than or equal to a predetermined value among the plurality of areas is classified as a first area, and an area having a value not greater than the predetermined value among the plurality of areas is classified as a second area. In addition, the clustering unit 134 uses, for each of the areas classified as the first area, a first scale based on both the distance between the positions of the data points and the angle between the movement directions of the data points. Perform clustering of data points, and for each zone classified as a second zone, use a second measure based on both the distance between the data point locations and the angle between the data point movement directions, Cluster data points. Further, the calculation unit 135 calculates the number of areas, the size of the area, the number of data points in the area, the number of clusters, and any clusters based on the result of clustering by the clustering unit 134 for each of the plurality of patterns. A first cost proportional to the number of data points not included is calculated. In addition, the selection unit 136 selects a pattern having the smallest first cost among the plurality of patterns as an optimal solution.

  Thus, in the first embodiment, the dense area area and the common movement trajectory area are evaluated using the same measure of the distance between the positions of the data points and the angle between the movement directions of the data points. The dense area cluster and the common movement trajectory cluster can be simultaneously detected, and the analysis result focusing on both the place and the trajectory can be acquired from the moving body data.

  The calculation unit 135 calculates a second cost proportional to the number of clusters and the number of data points not included in any cluster for each area included in the pattern selected as the current local optimal solution by the selection unit 136. Compare The dividing unit 132 further divides the area having the largest second cost into a plurality of areas with a plurality of patterns. When the selection unit 136 selects the pattern having the smaller first cost as the optimal solution from the current local optimal solution and the previous local optimal solution, and selects the current local optimal solution as the optimal solution, the dividing unit The current local optimal solution is given to 132, and further processing is executed. In this way, it is possible to obtain a more accurate analysis result by repeating the processing until an optimal solution is found.

  The classification unit 133 determines the number of data points in which the difference between the angle between the moving directions and π / 2 is equal to or smaller than a predetermined value, and the data point where the difference between the angle between the moving directions and π / 2 is larger than the predetermined value. If the ratio to the number of combinations is greater than or equal to 1, the area is classified as a first area, and if the ratio is less than 1, the area is classified as a second area. Thereby, the difference in the movement tendency of the data points in the dense area and the common movement locus area can be reflected in the clustering.

  The clustering unit 134 uses, as a first scale, a distance proportional to the sine value of the angle between the two data points and the angle between the movement directions, and the distance between the two data points. , And a scale proportional to the cosine value of the angle between the moving directions is used as a second scale for clustering. This makes it possible to perform clustering in a manner adapted to the data points belonging to the dense area area and the common movement trajectory area while using the same measure of the distance between the positions of the data points and the angle of the movement direction of the data points. It becomes possible.

[System configuration, etc.]
Further, each component of each illustrated apparatus is functionally conceptual, and does not necessarily need to be physically configured as illustrated. In other words, the specific form of distribution / integration of each device is not limited to that shown in the figure, and all or a part thereof may be functionally or physically distributed or arbitrarily distributed in arbitrary units according to various loads or usage conditions. Can be integrated and configured. Furthermore, all or a part of each processing function performed in each device may be realized by a CPU and a program that is analyzed and executed by the CPU, or may be realized as hardware by wired logic.

  Also, among the processes described in this embodiment, all or part of the processes described as being performed automatically can be performed manually, or the processes described as being performed manually can be performed. All or a part can be automatically performed by a known method. In addition, the processing procedure, control procedure, specific name, and information including various data and parameters shown in the above-described document and drawings can be arbitrarily changed unless otherwise specified.

[program]
As an embodiment, the clustering apparatus 10 can be implemented by installing a clustering program for executing the above clustering as package software or online software on a desired computer. For example, the information processing apparatus can function as the clustering apparatus 10 by causing the information processing apparatus to execute the above clustering program. The information processing apparatus referred to here includes a desktop or notebook personal computer. In addition, the information processing apparatus includes mobile communication terminals such as smartphones, mobile phones and PHS (Personal Handyphone System), and slate terminals such as PDA (Personal Digital Assistant).

  The clustering apparatus 10 can also be implemented as a clustering server apparatus that uses a terminal device used by a user as a client and provides the client with the above-described service related to clustering. For example, the clustering server device is implemented as a server device that provides a clustering service that receives mobile data and outputs a clustering result. In this case, the clustering server device may be implemented as a Web server, or may be implemented as a cloud that provides the above-described clustering service by outsourcing.

  FIG. 12 is a diagram illustrating an example of a computer in which a clustering apparatus is realized by executing a program. The computer 1000 includes a memory 1010 and a CPU 1020, for example. The computer 1000 also includes a hard disk drive interface 1030, a disk drive interface 1040, a serial port interface 1050, a video adapter 1060, and a network interface 1070. These units are connected by a bus 1080.

  The memory 1010 includes a ROM (Read Only Memory) 1011 and a RAM 1012. The ROM 1011 stores a boot program such as BIOS (Basic Input Output System). The hard disk drive interface 1030 is connected to the hard disk drive 1090. The disk drive interface 1040 is connected to the disk drive 1100. For example, a removable storage medium such as a magnetic disk or an optical disk is inserted into the disk drive 1100. The serial port interface 1050 is connected to a mouse 1110 and a keyboard 1120, for example. The video adapter 1060 is connected to the display 1130, for example.

  The hard disk drive 1090 stores, for example, an OS 1091, an application program 1092, a program module 1093, and program data 1094. That is, a program that defines each process of the clustering apparatus 10 is implemented as a program module 1093 in which a code executable by a computer is described. The program module 1093 is stored in the hard disk drive 1090, for example. For example, a program module 1093 for executing processing similar to the functional configuration in the clustering apparatus 10 is stored in the hard disk drive 1090. Note that the hard disk drive 1090 may be replaced by an SSD.

  The setting data used in the processing of the above-described embodiment is stored as program data 1094 in, for example, the memory 1010 or the hard disk drive 1090. Then, the CPU 1020 reads the program module 1093 and the program data 1094 stored in the memory 1010 and the hard disk drive 1090 to the RAM 1012 and executes them as necessary.

  The program module 1093 and the program data 1094 are not limited to being stored in the hard disk drive 1090, but may be stored in, for example, a removable storage medium and read out by the CPU 1020 via the disk drive 1100 or the like. Alternatively, the program module 1093 and the program data 1094 may be stored in another computer connected via a network (LAN (Local Area Network), WAN (Wide Area Network), etc.). The program module 1093 and the program data 1094 may be read by the CPU 1020 from another computer via the network interface 1070.

DESCRIPTION OF SYMBOLS 10 Clustering apparatus 11 Input part 12 Output part 13 Control part 14 Storage part 131 Conversion part 132 Division part 133 Classification part 134 Clustering part 135 Calculation part 136 Selection part

Claims (4)

A dividing unit that divides a predetermined area into a plurality of areas in a plurality of patterns;
For each of the plurality of patterns, for each of the plurality of areas, a value indicating a magnitude of a tendency of data points in the area to intersect is calculated based on an angle between moving directions of the data points in the area, A classifying unit that classifies a zone where the value is equal to or greater than a predetermined value among a plurality of zones as a first zone, and classifies a zone where the value is not equal to or greater than a predetermined value among the plurality of zones as a second zone;
For each zone classified as the first zone, clustering of data points in the zone using a first measure based on both the distance between the positions of the data points and the angle between the movement directions of the data points. For each zone classified as the second zone, using a second measure based on both the distance between the positions of the data points and the angle between the movement directions of the data points, A clustering unit for clustering points;
For each of the plurality of patterns, based on the result of clustering by the clustering unit, the number of areas, the size of the area, the number of data points in the area, the number of clusters, and the data points not included in any cluster A calculator for calculating a first cost proportional to the number of
A selection unit that selects a pattern having the smallest first cost among the plurality of patterns as an optimal solution;
A clustering apparatus characterized by comprising: For each of the areas included in the previous optimal pattern, which is the pattern selected as the optimal solution by the selection unit, the calculation unit is proportional to the number of clusters and the number of data points not included in any cluster. Compare the costs of
The division unit further divides the area with the second highest cost into a plurality of areas in a plurality of patterns,
The selection unit selects, as an optimal solution, a pattern having a smaller first cost from the current optimal pattern and the previous optimal pattern that are the patterns having the smallest first cost among the plurality of patterns, The clustering device according to claim 1, wherein, when the current optimal pattern is selected as an optimal solution, the current optimal pattern is given to the dividing unit and further processing is executed. The classification unit is data having a difference between the angle between the moving direction and π / 2 that is greater than the predetermined value as the number of combinations of data points where the difference between the angle between the moving directions and π / 2 is a predetermined value or less. If the ratio to the number of point combinations is 1 or greater, classify the zone as the first zone, and if the ratio is less than 1, classify the zone as the second zone;
The clustering unit uses, as the first scale, a scale that is proportional to the short distance between the positions of the two data points and the sine value of the angle between the moving directions, and the short distance between the positions of the two data points. The clustering apparatus according to claim 1, wherein clustering is performed by using a scale that is proportional to a cosine value of an angle between movement directions as the second scale. A clustering method executed by a clustering apparatus,
A dividing step of dividing a predetermined area into a plurality of areas in a plurality of patterns;
For each of the plurality of patterns, for each of the plurality of areas, a value indicating a magnitude of a tendency of data points in the area to intersect is calculated based on an angle between moving directions of the data points in the area, A classifying step of classifying a zone where the value is equal to or greater than a predetermined value among a plurality of zones as a first zone, and classifying a zone where the value is not equal to or greater than a predetermined value among the plurality of zones as a second zone;
For each zone classified as the first zone, clustering of data points in the zone using a first measure based on both the distance between the positions of the data points and the angle between the movement directions of the data points. For each zone classified as the second zone, using a second measure based on both the distance between the positions of the data points and the angle between the movement directions of the data points, A clustering step for clustering points;
For each of the plurality of patterns, based on the result of clustering by the clustering step, the number of areas, the size of the area, the number of data points in the area, the number of clusters, and the data points not included in any cluster Calculating a first cost proportional to the number of
A selection step of selecting, as an optimal solution, a pattern having the smallest first cost among the plurality of patterns;
A clustering method characterized by including