System and computer readable medium for finding crowd movements

• US 10,417,648 B2
• Filed: 11/09/2015
• Issued: 09/17/2019
• Est. Priority Date: 11/09/2015
• Status: Active Grant

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Wang, En-Tzu, Wu, Tai-Ting, Kao, Chi-Chun, Wang, Chao-Chih, Kuo, I-Hong
• Primary Examiner(s): Pham, Hung Q
• Application Number:
  US14/936,674
• Publication Number:
  US 20170132305A1
• Time in Patent Office: 1,408 Days
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

A method for finding crowd movements is provided. The method includes: collecting location data associated with multiple user devices, mining frequent patterns in the location data to generate multiple representative sequences, and grouping the representative sequences into clusters to find crowd movements according to sequence distances between the representative sequences. Each representative sequence includes at least one line segment between a starting location point and an end location point.

Claims

1. A crowd movements information system, comprising:

a processor that performs the following steps, the steps comprising;

collecting a plurality of location data associated with a plurality of user devices of a crowd, according to logs of the plurality of user devices;

mining a plurality of frequent patterns in the plurality of location data to generate a plurality of representative sequences regarding information on movements of the crowd, wherein each representative sequence comprises a plurality of sequences and each sequence comprises at least one line segment between a starting location point and an end location point, wherein each at least one line segment in each of the plurality of representative sequences is a directional line segment indicating movement direction of the crowd;

for each sequence pair of the plurality of sequences;

calculating an angle distance, a perpendicular distance, and a parallel distance between a first line segment of a first sequence and a second line segment of a second sequence;

dividing the angle distance by a maximum value in a domain of angle distance to obtain a normalized angle distance;

dividing the perpendicular distance by a maximum value in a domain of perpendicular distance to obtain a normalized perpendicular distance;

dividing the parallel distance by a maximum value in a domain of parallel distance to obtain a normalized parallel distance; and

determining a segment distance between the first line segment and the second line segment according to a weighted sum of the normalized angle distance, the normalized perpendicular distance, and the normalized parallel distance, and determining a sequence distance between the first sequence and the second sequence according to the segment distance, wherein a similarity between the first and second sequences is determined by the processor according to the segment distance between the first and second line segments; and

grouping the plurality of representative sequences into a plurality of clusters to find a plurality of moving trajectories of the crowd according to a plurality of said sequence distances between the plurality of sequences of each of the plurality of representative sequences.

2. The system according to claim 1, wherein the plurality of representative sequences further comprises:

the first sequence among the plurality of representative sequences, comprising the first line segment between a first start location point and a first end location point; and

the second sequence among the plurality of representative sequences, comprising the second line segment between a second start location point and a second end location point.

3. The system according to claim 2, wherein the calculating the parallel distance between the first line segment and the second line segment further comprises:

projecting the second start location point on an extended line of the first line segment to obtain a third start projection point;

projecting the second end location point on the extended line of the first line segment to obtain a third end projection point;

generating a third line segment by connecting the third start projection point to the third end projection point; and

determining the parallel distance by subtracting an intersection of the first line segment and the third line segment from an union of the first line segment and the third line segment.

4. The system according to claim 3, wherein the maximum value in the domain of angle distance is a length of a shorter of the first line segment and the second line segment, the maximum value in the domain of parallel distance is the union of the first line segment and the third line segment, and the maximum value in the domain of perpendicular distance is a perpendicular distance between the first line segment and a rotated line segment, wherein the rotated line segment is obtained by rotating the second line segment around the second start location point or the second end location point until the second line segment is perpendicular to the first line segment.

5. The system according to claim 2, wherein the determining the sequence distance between the first sequence and the second sequence further comprises:

generating a plurality of mapping combinations between the first sequence and the second sequence according to the at least one line segment in the first sequence and the at least one line segment in the second sequence;

calculating a mapping distance of each mapping combination; and

determining the sequence distance between the first sequence and the second sequence to be a minimum mapping distance among all of the plurality of mapping combinations.

6. The system according to claim 5, wherein the calculating the mapping distance of each mapping combination further comprises:

forming a plurality of mapping pairs between the at least one line segment in the first sequence and the at least one line segment in the second sequence according to a chronological order;

calculating a segment distance in each mapping pair; and

averaging segment distances of all the plurality of mapping pairs to obtain the mapping distance.

7. The system according to claim 1, wherein the collecting the plurality of location data associated with the plurality of user devices further comprises:

selecting a plurality of reference location points; and

replacing each location point in the plurality of location data with one of the plurality of reference location points that is geospatially closest to the each location point in the plurality of location data.

8. The system according to claim 1, wherein the mining the plurality of frequent patterns in the plurality of location data to generate the plurality of representative sequences further comprises:

removing a frequent pattern of the plurality of frequent patterns if the frequent pattern of the plurality of frequent patterns has only one location point;

removing identical adjacent location points in each frequent pattern; and

aggregating the plurality of frequent patterns in a time period over a number of days to generate the plurality of representative sequences.

9. The system according to claim 1, wherein the grouping the plurality of representative sequences into the plurality of clusters comprises:

making each representative sequence one cluster;

calculating a cluster distance between each cluster pair that is formed by two clusters selected among the plurality of clusters;

finding a first cluster and a second cluster having a minimum cluster distance; and

merging the first cluster and the second cluster if the minimum cluster distance is smaller than a distance threshold;

wherein the cluster distance of said cluster pair is calculated by averaging all the sequence distances between all pairs of representative sequences in said cluster pair, wherein a pair of representative sequences is formed by two representative sequences in the two respective clusters that form said cluster pair.

10. The system according to claim 1, further comprising:

classifying days into a plurality of day types; and

finding a typical sequence for a target day type according to occurrence rates of the plurality of representative sequences in the target day type, wherein the finding the typical sequence for the target day type comprises;

calculating a first occurrence rate of a test representative sequence in days belonging to the target day type;

calculating a second occurrence rate of the test representative sequence in days not belonging to the target day type;

calculating a statistical entropy according to the first occurrence rate and the second occurrence rate; and

determining the test representative sequence to be the typical sequence if the first occurrence rate is larger than a probability threshold and the statistical entropy is smaller than an entropy threshold.

11. The system according to claim 1, wherein the plurality of location data is collected when the plurality of user devices are used for payment activity.

12. A non-transitory computer readable medium with instructions stored thereon for finding crowd movement, that when executed on a processor, perform the steps comprising:

collecting a plurality of location data associated with a plurality of user devices of a crowd, according to logs of the plurality of user devices;

mining a plurality of frequent patterns in the plurality of location data to generate a plurality of representative sequences regarding information on movements of the crowd, wherein each representative sequence comprises a plurality of sequences and each sequence comprises at least one line segment between a starting location point and an end location point, wherein each at least one line segment in each of the plurality of representative sequences is a directional line segment indicating movement direction of the crowd;

for each sequence pair of the plurality of sequences;

calculating an angle distance, a perpendicular distance, and a parallel distance between a first line segment of a first sequence and a second line segment of a second sequence;

dividing the angle distance by a maximum value in a domain of angle distance to obtain a normalized angle distance;

dividing the perpendicular distance by a maximum value in a domain of perpendicular distance to obtain a normalized perpendicular distance;

dividing the parallel distance by a maximum value in a domain of parallel distance to obtain a normalized parallel distance; and

determining a segment distance between the first line segment and the second line segment according to a weighted sum of the normalized angle distance, the normalized perpendicular distance, and the normalized parallel distance, and determining a sequence distance between the first sequence and the second sequence according to the segment distance, wherein a similarity between the first and second sequences is determined by the processor according to the segment distance between the first and second line segments; and

grouping the plurality of representative sequences into a plurality of clusters to find a plurality of moving trajectories of the crowd according to a plurality of said sequence distances between the plurality of sequences of each of the plurality of representative sequences.

13. The non-transitory computer readable medium according to claim 12, wherein the plurality of representative sequences further comprises:

the first sequence among the plurality of representative sequences, comprising the first line segment between a first start location point and a first end location point; and

the second sequence among the plurality of representative sequences, comprising the second line segment between a second start location point and a second end location point.

14. The non-transitory computer readable medium according to claim 13, wherein the calculating the parallel distance between the first line segment and the second line segment further comprises:

projecting the second start location point on an extended line of the first line segment to obtain a third start projection point;

projecting the second end location point on the extended line of the first line segment to obtain a third end projection point;

generating a third line segment by connecting the third start projection point to the third end projection point; and

determining the parallel distance by subtracting an intersection of the first line segment and the third line segment from an union of the first line segment and the third line segment.

15. The non-transitory computer readable medium according to claim 14, wherein the maximum value in the domain of angle distance is a length of a shorter of the first line segment and the second line segment, the maximum value in the domain of parallel distance is the union of the first line segment and the third line segment, and the maximum value in the domain of perpendicular distance is a perpendicular distance between the first line segment and a rotated line segment, wherein the rotated line segment is obtained by rotating the second line segment around the second start location point or the second end location point until the second line segment is perpendicular to the first line segment.

16. The non-transitory computer readable medium according to claim 13, wherein the determining the sequence distance between the first sequence and the second sequence further comprises:

generating a plurality of mapping combinations between the first sequence and the second sequence according to the at least one line segment in the first sequence and the at least one line segment in the second sequence;

calculating a mapping distance of each mapping combination; and

determining the sequence distance between the first sequence and the second sequence to be a minimum mapping distance among all of the plurality of mapping combinations.

17. The non-transitory computer readable medium according to claim 16, wherein the calculating the mapping distance of each mapping combination further comprises:

forming a plurality of mapping pairs between the at least one line segment in the first sequence and the at least one line segment in the second sequence according to a chronological order;

calculating a segment distance in each mapping pair; and

averaging segment distances of all the plurality of mapping pairs to obtain the mapping distance.

18. The non-transitory computer readable medium according to claim 12, wherein the collecting the plurality of location data associated with the plurality of user devices further comprises:

selecting a plurality of reference location points; and

replacing each location point in the plurality of location data with one of the plurality of reference location points that is geospatially closest to the each location point in the plurality of location data.

19. The non-transitory computer readable medium according to claim 12, wherein the mining the plurality of frequent patterns in the plurality of location data to generate the representative sequences further comprises:

removing a frequent pattern of the plurality of frequent patterns if the frequent pattern of the plurality of frequent patterns has only one location point;

removing identical adjacent location points in each frequent pattern; and

aggregating the plurality of frequent patterns in a time period over a number of days to generate the plurality of representative sequences.

20. The non-transitory computer readable medium according to claim 12, wherein the grouping the plurality of representative sequences into the plurality of clusters comprises:

making each representative sequence one cluster;

calculating a cluster distance between each cluster pair that is formed by two clusters selected among the plurality of clusters;

finding a first cluster and a second cluster having a minimum cluster distance; and

merging the first cluster and the second cluster if the minimum cluster distance is smaller than a distance threshold;

wherein the cluster distance of said cluster pair is calculated by averaging all the sequence distances between all pairs of representative sequences in the cluster pair, wherein a pair of representative sequences is formed by two representative sequences in the two respective clusters that form said cluster pair.

21. The non-transitory computer readable medium according to claim 12, further comprising:

classifying days into a plurality of day types; and

finding a typical sequence for a target day type according to occurrence rates of the plurality of representative sequences in the target day type, wherein the finding the typical sequence for the target day type comprises;

calculating a first occurrence rate of a test representative sequence in days belonging to the target day type;

calculating a second occurrence rate of the test representative sequence in days not belonging to the target day type;

calculating a statistical entropy according to the first occurrence rate and the second occurrence rate; and

determining the test representative sequence to be the typical sequence if the first occurrence rate is larger than a probability threshold and the statistical entropy is smaller than an entropy threshold.

22. The non-transitory computer readable medium according to claim 12, wherein the plurality of location data is collected when the plurality of user devices are used for payment activity.