CN106682051A - Method for finding out crowd movement behaviors - Google Patents

Abstract

The invention discloses a method for finding out crowd movement behaviors, which comprises the following steps: collecting a plurality of location data regarding a plurality of user devices; detecting a plurality of conventional patterns in the position data to generate a plurality of representative sequences, wherein each representative sequence comprises at least one line segment between a starting position point and an ending position point; and classifying the representative sequences into a plurality of sets according to a plurality of sequence distances among the representative sequences so as to find the moving behaviors of the crowd.

Description

A way to find out the movement behavior of crowds

technical field

The present invention relates to a method for finding out the movement behavior of crowds by collecting location data about user devices.

Background technique

For many companies and organizations, such as convenience store chains, mass transit companies, local governments, etc., knowing how people move within a city or between multiple cities can be important information. For these organizations, there are many important decisions that depend on information about where people are and where they come from and move to, such as setting new bus routes, building new transit stations, Open new storefronts, and build urban public facilities. Therefore, how to effectively find out the relevant information of the crowd's mobile behavior is one of the topics that the industry is currently working on.

Contents of the invention

The present invention relates to a method for finding crowd movement behavior and a non-transitory computer-readable medium for executing the method.

According to one embodiment of the present invention, a method for finding out the movement behavior of a crowd is proposed, the method includes: collecting a plurality of location data about a plurality of user devices; detecting a plurality of habitual patterns in the location data to generate a plurality of representative Sequences, wherein each representative sequence includes at least one segment, the at least one segment is between the start position point and the end position point; and according to a plurality of sequence distances between the representative sequences, the representative sequences are classified into multiple A collection to find out the crowd movement behavior.

In order to have a better understanding of the above and other aspects of the present invention, the implementation examples according to the present invention are specifically cited below, together with the accompanying drawings, for detailed description as follows:

Description of drawings

FIG. 1 is a schematic diagram of an example of payment activities performed by a smart card.

FIG. 2 is a flow chart of a method for finding crowd movement behavior according to an embodiment of the present invention.

FIG. 3 illustrates a schematic diagram of an example payment record related to location data and time captured from multiple user devices.

FIG. 4 illustrates a flow chart of collecting location data about a user device according to an embodiment of the invention.

FIG. 5A and FIG. 5B are schematic diagrams illustrating an example of marking the payment location with the closest reference location point according to an embodiment of the present invention.

FIG. 6 is a schematic diagram of sorted and simplified payment records according to an embodiment of the present invention.

FIG. 7 illustrates a flow chart of detecting common patterns in location data to generate a representative sequence according to an embodiment of the present invention.

FIG. 8 is a schematic diagram illustrating a conventional mode of aggregation according to an embodiment of the present invention.

FIG. 9 is a flow chart of calculating the sequence distance between representative sequences according to an embodiment of the present invention.

FIG. 10 is a flow chart of calculating a line segment distance between a first line segment and a second line segment according to an embodiment of the present invention.

FIG. 11 is a schematic diagram illustrating the line segment distance between two line segments according to an embodiment of the present invention.

FIG. 12 is a flow chart of calculating the parallel distance between the first line segment and the second line segment according to an embodiment of the present invention.

FIG. 13 is a schematic diagram illustrating the line segment distance between two line segments according to an embodiment of the present invention.

FIG. 14 shows a flow chart of calculating normalized angular distance, normalized vertical distance, and normalized parallel distance according to an embodiment of the present invention.

15A-15D are schematic diagrams illustrating various situations considering the maximum value of the vertical distance field according to an embodiment of the present invention.

FIG. 16 is a flow chart of determining the sequence distance between the first sequence and the second sequence according to an embodiment of the present invention.

17A-17C are schematic diagrams illustrating combinations of multiple images between two representative sequences according to an embodiment of the present invention.

FIG. 18 is a schematic diagram illustrating an example of an invalid mapping between two representative sequences.

FIG. 19 is a flow chart of calculating the image distance of an image combination according to an embodiment of the present invention.

FIG. 20 illustrates a flowchart for classifying representative sequences into sets according to an embodiment of the present invention.

FIG. 21 is a flow chart of finding out crowd movement behavior and finding out a typical sequence according to an embodiment of the present invention.

FIG. 22 is a flowchart illustrating a typical sequence for finding a target date type according to an embodiment of the present invention.

detailed description

In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with specific embodiments and with reference to the accompanying drawings.

In modern life, many people use smart cards to take public transportation, such as buses, trains, subways, etc. In addition, smart cards can also be used as electronic currency wallets to purchase items or pay expenses. For example, smart cards can pre-store funds in the card, Can be used for vending machines, entering and exiting parking lots, or entering and exiting train stations. FIG. 1 is a schematic diagram of an example of payment activities using a smart card. In this example, the smart card is a contactless smart card. Whenever a smart card is used, a payment record (Payment Log) or traffic record will be generated, and since vending machines or station gates can have static geographical information, it is possible to collect data about multiple users' smart cards when they are used. location data. Service providers who issue smart cards can collect these payment records to gain information about where people are and how people are moving.

FIG. 2 is a flow chart of a method for finding crowd movement behavior according to an embodiment of the present invention. The method for finding crowd movement behavior includes the following steps. Step S100, collecting location data about a plurality of user devices. Step S200 , detecting (Mining) frequent patterns in the location data to generate a plurality of representative sequences (Representative Sequences). Step S300, according to the sequence distance between the representative sequences, classify the representative sequences into clusters (Cluster), so as to find out the movement behavior of the crowd. Wherein each representative sequence includes at least one segment, and the at least one segment is between the start position point and the end position point. This method can be implemented by a software program, for example, the software program can be stored on a CD, and the software program can include a plurality of instructions related to the computer processor, and these instructions can be loaded by the computer processor to perform the above-mentioned method for finding out the movement behavior of the crowd . A detailed description of each step follows.

Step S100: Collect location data about a plurality of user devices. The user device may include a smart card, an electronic payment card, or a mobile device with payment capabilities. When these user devices are used for payment activities, relevant location data may be collected. For example, when a smart card is used to carry out payment activities at a payment terminal, a report can be uploaded to the central server, and this report can include the smart card's identity authentication (Identification, ID), payment amount, date and time, payment terminal Location. The method for finding out crowd movement behavior of the present invention is not limited to collecting location data when payment activities are performed, and the timing of collecting location data may also include: when the user device enters a station, when money is deposited into the user device, or when the user When a device is authenticated to enter a building. For ease of understanding, the following description will take location data collected during payment activities as an example, and payment records will represent the collected location data.

FIG. 3 illustrates a schematic diagram of an example payment record related to location data and time captured from multiple user devices. Payment records can be stored in the central server of the payment service provider. In this example, the payment record includes fields: uid, departure location, arrival location, date and time, payment amount, and transaction type. uid represents the ID of the user device, that is, the same uid corresponds to the same user device, that is, it may correspond to the same user, so it is possible to obtain information about where a person is, by collecting information about multiple user devices With location data, service providers can learn what common movement trajectories most people have. The transaction type can be purchase, transportation, money saving, or other types. For the transportation type, the payment activity may be performed at the destination station, and the departure location and arrival location record relevant traffic information, such as the departure location and arrival location. geographic coordinates. For transaction types other than transportation, the location of the payment activity can be recorded using the departure location field, and "-" can be used for the arrival location field.

In the above example, the recorded coordinates may be precise location data. In the payment record, there may be a large number of precise location coordinates of different locations due to the fact that a large number of stores use the payment service. For finding out the moving behavior of people of interest, precise location may not be needed, so the adjacent location can be regarded as a semantic region (Semantic Region), and a reference location point (Reference Location Point) can be selected to represent a Semantic region. Step S100 may include step S110 and step S120 , as shown in FIG. 4 , a flow chart of collecting location data about a user device according to an embodiment of the present invention.

Step S110: Select a plurality of reference position points. Examples of reference location points may include schools, chain convenience stores, and landscape locations determined by residential population. Step S120: Replace each location point in the location data with the closest reference location point to its geographic location. For each piece of payment data in the payment record, the original precise location point can be replaced by the closest reference location point. FIG. 5A and FIG. 5B are schematic diagrams illustrating an example of marking the payment location with the closest reference location point according to an embodiment of the present invention. Fig. 5A shows three pre-selected reference positions Ref_a, Ref_b, Ref_c with three triangles filled with different shades, and the original payment position with a hollow circle. Next, each payment location is replaced with the reference location point closest to the geographic location. As shown in FIG. 5B , the shadow filling state of each payment location changes to be the same as its corresponding reference location point. After marking the payment location with the closest reference location points, the geographic coordinates in the original payment record can be replaced by these reference location points. Step S110 and step S120 mentioned here are optional steps, that is, even if step S110 and step S120 are not executed, the original payment location is saved in the payment record, and the subsequent step S200 and step S300 can still be used for the original payment location. Pay location execution.

Step S200: Detect the usual patterns in the location data to generate a plurality of representative sequences. After data collection and the above-mentioned pre-processing stage, payment records can be converted into payment sequences (Sequence), each payment sequence includes a sequence of items (Item), representing the entire payment track of a specific user at a specific time, payment Items in the sequence may be reference points as shown in FIG. 5A and FIG. 5B , and an example payment sequence may be {id_677: Ref_h, Ref_c, Ref_c}. From multiple payment sequences, a sequential pattern detection (Sequential Pattern Mining) algorithm, such as PrefixSpan or Generalized Sequential Pattern (GSP) algorithm, can be used to find out the usual pattern in the payment sequence. After the sequential pattern detection, the representative sequence in a specific time and its corresponding support (Support Count) can be obtained. The support can represent the number of occurrences and can be calculated in the detection algorithm. Each representative sequence includes at least one segment between a start position point and an end position point. The start position point and the end position point may be precise positions or reference position points. For example, a piece of payment information corresponding to the traffic type in the payment record can be regarded as a segment between the departure location and the arrival location. An example of a representative sequence is <Ref_a, Ref_d, Ref_e>, which includes two line segments, one from Ref_a to Ref_d and the other from Ref_d to Ref_e.

In step S200, the payment records can be sorted according to uid and date and time, for example, the transactions corresponding to the same user device can be grouped together, and the transaction data corresponding to the user device can be sorted according to time order. In addition, each location point can be marked with the closest reference location point, as shown in FIG. 5B . FIG. 6 is a schematic diagram of sorted and simplified payment records according to an embodiment of the present invention. In this example, one transaction sequence can be formed for uid 604: <Ref_a, Ref_d, Ref_e>, and another transaction sequence can be formed for uid 677: <Ref_h, Ref_c, Ref_c>, and then can be applied to multiple transaction sequences A sequential pattern detection algorithm to find common patterns.

FIG. 7 illustrates a flow chart of detecting common patterns in location data to generate a representative sequence according to an embodiment of the present invention. Step S200 may include step S210, step S220, and step S230, and these steps are performed after pattern detection. Step S210, if there is a habitual pattern with only a single point, remove the habitual pattern. Step S220, in each usual mode, remove the same adjacent position points. Since it is a method to find out the moving behavior of the crowd, it will exclude those usual patterns that represent staying in place, such as <Ref_a> and <Ref_a, Ref_a>. In addition, common patterns that include at least two identical adjacent locations, such as <Ref_h, Ref_c, Ref_c>, will also exclude duplicate adjacent locations. The representative sequences obtained in this way will not include the same adjacent position points, and each line segment in each representative sequence represents the direction of the crowd's moving behavior.

Step S230, aggregate the habitual patterns of several days to generate a representative sequence. The collected payment records can be classified according to different time and different dates, because in different time segments, the trajectory of crowd movement behavior may be different. For example, the three time periods of 6:30am to 9:30am, 10:30am to 13:30am, and 4:30pm to 7:30pm may respectively correspond to different crowd activities. If it is necessary to accumulate statistical analysis for a specific time period over multiple days, the usual pattern of multiple days corresponding to this time period can be aggregated. FIG. 8 is a schematic diagram illustrating a conventional mode of aggregation according to an embodiment of the present invention. In this example, the representative sequences from 6:30am to 9:30am on all working days in May are aggregated, and the numbers in the table represent the support of the representative sequences. As shown in Figure 8, after the accumulation of the sequence <Ref_d, Ref_e> of each working day, the support degree of the generated sequence in May is 5750. The number 23/23 is the Occurrence Rate, which means that the sequence <Ref_d, Ref_e> appeared 23 times in 23 working days in May. By aggregating multi-day statistical data, it is possible to accurately find out the movement trend of most people.

Step S300, according to the sequence distance between the representative sequences, classify the representative sequences into sets, so as to find out the movement behavior of the crowd. After step S100 and step S200 are performed, the representative sequence of the crowd movement behavior has been found, and then similar representative sequences can be classified into sets to find the crowd movement behavior between large areas. Doing so is beneficial because most movement behavior of people of interest is about moving between two large areas rather than between two specific buildings. In step S300, the sequence distance between two representative sequences can be calculated to determine the degree of similarity between the two representative sequences. For example, a shorter sequence distance indicates that the two representative sequences have a higher degree of similarity (eg, closer geographically). Representative sequences can be classified into sets based on the sequence distances thus calculated.

The following illustrates an example of calculating sequence distance. A representative sequence can be regarded as a sequence of line segments. In this illustrative example, the representative sequence includes a first sequence Seq_a and a second sequence Seq_b. The first sequence Seq_a includes a first line segment L1 between the first start location point L1_s and the first end location point L1_e. The second sequence Seq_b includes a second line segment L2 between the second start location point L2_s and the second end location point L2_e. The sequence distance between the first sequence Seq_a and the second sequence Seq_b is determined according to the line segment distance between the first line segment L1 and the second line segment L2. The first line segment L1 has directionality (from the first starting point L1_s to the first end point L1_e), and the second line segment L2 also has directionality (from the second starting point L2_s to the second end point L1_e). Therefore, in the following description, the vector as well as represent the first line segment L1 and the second line segment L2 respectively.

FIG. 9 is a flow chart of calculating the sequence distance between representative sequences according to an embodiment of the present invention. The first sequence Seq_a and the second sequence Seq_b form a sequence pair among the representative sequences, and for each sequence pair, the step S300 (classifying the representative sequences into sets) may further include steps S310 and S320. Step S310, calculating the line segment distance between the first line segment L1 and the second line segment L2, where the line segment distance represents the closeness or similarity of the two line segments. Step S320, according to the line segment distance between the first line segment L1 and the second line segment L2, determine the sequence distance between the first sequence Seq_a and the second sequence Seq_b, in other words, the degree of similarity between the two representative sequences is It is determined according to the degree of similarity between the line segments of the two representative sequences.

FIG. 10 is a flow chart of calculating a line segment distance between a first line segment and a second line segment according to an embodiment of the present invention. Step S310 may include the following steps. Step S311 , calculating the angular distance d _θ (Angle Distance), the vertical distance d _⊥ (Perpendicular Distance), and the parallel distance d _|| (ParallelDistance) between the first line segment L1 and the second line segment L2. Step S312, according to the angular distance d _θ , the vertical distance d _⊥ , and the parallel distance d _|| , calculate the normalized angular distance Nd _θ , the normalized vertical distance Nd _⊥ , and the normalized parallel distance Nd _|| , where the normalized The values of the normalized angular distance Nd _θ , the normalized vertical distance Nd _⊥ , and the normalized parallel distance Nd _|| are in the same value range. Step S313 , according to the weighted sum of the normalized angular distance Nd _θ , the normalized vertical distance Nd _⊥ , and the normalized parallel distance Nd _|| , determine the line segment distance between the first line segment L1 and the second line segment L2 . An example is provided below to illustrate the calculation of the line segment distance between two line segments.

FIG. 11 is a schematic diagram illustrating the line segment distance between two line segments according to an embodiment of the present invention. The line segment distance is determined by three components: the angular distance d _θ , the vertical distance d _⊥ , and the parallel distance d _|| . The angular distance d _{θ is} related to and The angle between them is θ (0≤θ≤180°). For example, the included angle θ can be based on the formula calculation, where is the inner product (dot product) of two vectors,

and Represents the lengths of the two vectors. The angular distance d _θ can be calculated according to the following formula (1):

The angular distance d _θ represents the similarity of two vectors in the pointing direction, the smaller the angle θ is, the smaller the angular distance d _θ is. And when the angle θ is greater than 90°, it means that the two vectors are pointing in opposite directions substantially, then the angular distance d _θ at this time can be set as the maximum possible value of the angular distance domain (Domain), to indicate that the two vectors are in The directions are not similar.

FIG. 12 is a flow chart of calculating the parallel distance between the first line segment and the second line segment according to an embodiment of the present invention. Step S311 includes the following steps. Step S331 , project the second initial point L2_s on the extension line of the first line segment L1 to obtain a third initial projection point L3_s. Step S332 , project the second end point L2_e on the extension line of the first line segment L1 to obtain a third end projection point L3_e. Step S333, connecting the third initial projection point L3_s and the third end projection point L3_e to generate a third line segment L3, the third initial projection point L3_s, the third end projection point L3_e, and the third line segment L3 thus generated, It can be seen in Figure 11. Step S334 , subtracting the intersection of the first line segment L1 and the third line segment L3 from the union of the first line segment L1 and the third line segment L3 to determine the parallel distance d _|| . The parallel distance d _|| can be calculated according to the following formula (2):

d _|| ＝L1∪L3-L1∩L3 (2)

Since the third line segment L3 is formed by projecting the second line segment L2 onto the first line segment L1, the third line segment L3 is collinear with the first line segment L1. In the example shown in Fig. 11, the union of the first line segment L1 and the third line segment L3 is the length from the first starting position point L1_s to the first end position point L1_e, and the first line segment L1 and the third line segment The intersection of the line segment L3 is the length from the third starting position point L3_s to the third end position point L3_e. In this example, the second line L2 is projected onto the first line L1. In other embodiments, the first line segment L1 may also be projected onto the (extended) second line segment L2 to obtain the parallel distance d _|| ( Calculated values may vary). The parallel distance d _|| represents the degree of similarity between the equivalent parallel lengths of two line segments.

The vertical distance d _⊥ can be calculated according to the following formula (3):

Where l _⊥s is the Euclidean distance between the second starting point L2_s and the third starting point L3_s, l _⊥e is the distance between the second ending point L2_e and the third ending point L3_e Euclidean distance of . Equation (3) represents the Contraharmonic Mean of l _⊥s and l _⊥e .

FIG. 13 is a schematic diagram illustrating the line segment distance between two line segments according to an embodiment of the present invention. Similarly, the angular distance d _θ , the parallel distance d _|| , and the vertical distance d _⊥ can be calculated according to formulas (1), (2), and (3) respectively. In this example, the included angle θ is greater than 90°, so the angular distance d _θ is equal to As for the parallel distance d _|| , the union of the first line segment L1 and the third line segment L3 is the length from the first starting position point L1_s to the third end position point L3_e, and the first line segment L1 and the third line segment L3 The intersection of is the length from the third start point L3_s to the first end point L1_e.

As mentioned above, three components are considered simultaneously when calculating line segment distances. However, since the value ranges of these three components may vary greatly, it is not easy to obtain a meaningful combination based on these three components. In the method of the present invention, in step _S312 , the normalized angular distance _{Nd θ ,} the normalized parallel distance _{Nd ||} and the value of the normalized vertical distance Nd _⊥ are in the same value range, for example, [0, 1], [0, 1] represents an interval greater than or equal to 0 and less than or equal to 1. Since the values of these three normalization components are in the same value range, the linear combination of these three normalization components is meaningful for calculating the line segment distance between two line segments. In one embodiment, the line segment distance is the weighted sum of the normalized angular distance Nd _θ , the normalized parallel distance Nd _|| , and the normalized vertical distance Nd _⊥ , and the line segment distance can be calculated according to the following formula (4):

Line segment distance＝w ₁ ×Nd _θ +w ₂ ×ND _|| +w ₃ ×ND _⊥ where

For example, w1, w2, w3 could all be equal to to obtain the average of the normalized angular distance Nd _θ , the normalized parallel distance Nd _|| , and the normalized vertical distance Nd _⊥ .

FIG. 14 shows a flow chart of calculating normalized angular distance, normalized vertical distance, and normalized parallel distance according to an embodiment of the present invention. Step S312 may include the following steps. Step S341, dividing the angular distance d _θ by the maximum value of the angular distance domain to obtain the normalized angular distance Nd _θ . Step S342, dividing the vertical distance d _⊥ by the maximum value of the vertical distance field to obtain the normalized vertical distance Nd _⊥ . Step S343 , dividing the parallel distance d _|| by the maximum value of the parallel distance field to obtain the normalized parallel distance Nd _|| . Since the three normalized distances are all generated by dividing by the maximum values in the respective distance domains, the values of the three normalized distance components are all in the range [0, 1].

As shown in formula (1), the maximum value of the angular distance field is the length of the shorter one of the first line segment L1 and the second line segment L2 . As shown in formula (2), the maximum value of the parallel distance field is the union of the first line segment L1 and the third line segment L3. The maximum value of the vertical distance field is not easy to see directly from the formula (3), and its related calculation is explained as follows.

15A-15D are schematic diagrams illustrating various situations considering the maximum value of the vertical distance field according to an embodiment of the present invention. According to formula (3) and the geometric relationship between the first line segment L1 and the second line segment L2, the maximum value of the vertical distance domain occurs at perpendicular to Time. Therefore, in one embodiment, the second line segment L2 can be rotated around the second start point L2s or around the second end point L2e until it is perpendicular to the first line segment L1 The maximum value of the vertical distance field is the vertical distance between the first line segment L1 and the rotated second line segment. 15A-15D illustrate four possible rotation situations. The maximum value of the vertical distance field is the maximum vertical distance among the four possible situations, and the maximum value of the vertical distance field can be calculated according to the following formula (5):

Where l ₂ represents the length of the second line segment L2.

The line segment distance between two line segments can be obtained according to the above calculation procedure, and the sequence distance between two representative sequences can be determined according to the line segment distance between the line segments of the two representative sequences respectively. FIG. 16 is a flow chart of determining the sequence distance between the first sequence and the second sequence according to an embodiment of the present invention. Step S320 includes the following steps. Step S321, according to at least one segment in the first sequence Seq_a and at least one segment in the second sequence Seq_b, generate a plurality of mapping (Mapping) combinations between the first sequence Seq_a and the second sequence Seq_b. Step S322, calculating the image distance of each image combination. Step S333, using the minimum image distance in each image combination as the sequence distance between the first sequence Seq_a and the second sequence Seq_b.

The first sequence Seq_a may be a sequence formed by arranging a plurality of line segments in chronological order. For example, the first sequence Seq_a may include two line segments LineSega1 and LineSega2. The trajectory represented by the line segment LineSega1 is earlier than the trajectory represented by the line segment LineSega2. 17A-17C are schematic diagrams illustrating combinations of multiple images between two representative sequences according to an embodiment of the present invention. In this example, the second sequence Seq_b also includes two line segments LineSegb1 and LineSegb2 arranged in time order.

In FIG. 17A, the line segment Maps LineSegb1 to an empty line segment φ, the line segment LineSegb2 maps to the line segment LineSega1, and the line segment LineSega2 maps to an empty line segment φ. It is worth noting that the chronological order of each representative series still maintains the original chronological order. FIG. 17B and FIG. 17C show different image combinations respectively, and the time order of each representative sequence also maintains the original time order. FIG. 18 shows an example schematic diagram of an invalid mapping between two representative sequences. This mapping violates the chronological order because line segment LineSega2 (mapped to line segment LineSegb1) occurs later than line segment LineSega1 (mapped to line segment LineSegb2), whereas line segment LineSegb1 Occurs earlier than line segment LineSegb2. For each valid mapping combination (as shown in FIGS. 17A-17C ), a mapping distance can be calculated. The sequence distance between the first sequence Seq_a and the second sequence Seq_b may be the minimum image distance among all image combinations.

FIG. 19 is a flow chart of calculating the image distance of an image combination according to an embodiment of the present invention. Step S322 includes the following steps. Step S351 , according to time order, form a plurality of mapping pairs (Mapping Pairs) between at least one segment in the first sequence Seq_a and at least one segment in the second sequence Seq_b. Step S352, calculating the line segment distance of each mapping pair. Step S353, calculating the average value of the line segment distances of each mapping pair to obtain the mapping distance.

Please refer to FIG. 17A, the image combination in this example includes three image pairs: {φ, LineSegb1}, {LineSega1, LineSegb2}, and {LineSega2, φ}. The line segment distance of each image pair can be calculated according to the aforementioned line segment distance calculation method (including calculating three normal distance components, steps S311-S313 and formulas (1)-(5)). And the line segment distance between a real line segment and an empty line segment φ can be defined as 1 (the maximum possible value of the line segment distance field). The mapping distance of the mapping combination shown in FIG. 17A may be the average value of the line segment distances of the three mapping pairs. For example, the image distance for this image combination is equal to where Nd represents the line segment distance between two line segments. Similarly, there are two mapping pairs in Figure 17B, and the mapping distance may be the average of the line segment distances of these two mapping pairs.

As described above, the sequence distance between two representative sequences can be calculated. FIG. 20 illustrates a flowchart for classifying representative sequences into sets according to an embodiment of the present invention. Step S300 includes the following steps. Step S360, taking each representative sequence as a set. Step S370, calculating the set distance between each set pair, where the set pair is formed by two sets. Step S380, finding the first set and the second set with the minimum set distance. Step S390, if the minimum set distance is less than the distance threshold, merge the first set and the second set.

In this embodiment, an Agglomerative Hierarchical Clustering method can be applied. In the initial state, each representative sequence is regarded as a set. Then the set distance between each set pair (formed by two sets, and the initial state is two representative sequences) can be calculated, and the set distance can be calculated according to the method of step S351～step S353 (because in the initial state, namely Equivalent to calculating the sequence distance of two representative sequences). Find two sets with the minimum set distance, if the minimum set distance is less than the distance threshold, such as 0.3, then merge the two sets into a larger set. Then the process can go back to step S370 to repeatedly perform merging collection. After merging, some sets will have multiple representative sequences, and for a set pair formed by a set with multiple representative sequences, all representative sequence pairs in this set pair can be calculated (all paired links, All-PairLinkage) The average value of the sequence distances of is used as the set distance of the set pair, wherein the representative sequence pair is formed by a representative sequence in each of the two sets of the set pair. For example, set G1 has two representative sequences, set G2 has three representative sequences, then the set distance between set G1 and set G2 can be the average of the sequence distances of 2×3=6 representative sequence pairs value.

In one embodiment, a method for finding a typical sequence (Typical Sequence) is provided. FIG. 21 is a flow chart of finding out crowd movement behavior and finding out a typical sequence according to an embodiment of the present invention. Compared with the flowchart of FIG. 2 , FIG. 21 further includes step S410 and step S420 . Step S410, classify the date into multiple date types. For example, dates can be categorized as working days and holidays, and working days can be further categorized as the last working day before a single-day holiday, the last working day before at least a double-day holiday, the first business day and so on. Similarly, vacation days may be further classified as a single day off, the first off day of at least two days off days, the last off day of at least two day off days, and so on. Step S420, find out the typical sequence of the target date type according to the occurrence rate of the representative sequence in the target date type. As shown in Figure 8, after aggregating the data of several days, the occurrence rate of the representative sequence on a specific date type can be obtained, and according to the occurrence rate, the typical sequence of a specific date type can be found. For example, a typical sequence that might be found is a movement trajectory between two train stations on at least the last holiday of a double-day holiday.

FIG. 22 is a flowchart illustrating a typical sequence for finding a target date type according to an embodiment of the present invention. Step S420 includes the following steps. Step S421, calculating the first occurrence rate of the test representative sequence in the days belonging to the target date type. Step S422, calculating the second occurrence rate of the test representative sequence on days that do not belong to the target date type. Step S423, calculate statistical entropy (Entropy) according to the first occurrence rate and the second occurrence rate. In step S424, if the first occurrence rate is greater than the probability threshold and the statistical entropy is less than the entropy threshold, it is determined that the test representative sequence is a typical sequence.

The occurrence rate in step S421 can be obtained after step S230 is executed (as shown in FIG. 8 , the data of several days are aggregated). The following uses an example to illustrate the calculation performed in steps S421-S424. The target date type in this example is the first holiday that has at least two days off, denoted by class H. On the other hand, holidays that do not belong to class H are represented by class(all-H). Table 1 below lists two representative sequences and their corresponding occurrence rates.

Table I

The occurrence rate represents the number of times the sequence appears on these days. For example, the sequence R1 appears on 41 days in 56 days belonging to class H, and appears in 2 days in 128 days belonging to class (all-H). a day. In this example, the probability threshold Pth of step S424 is equal to 0.2, and the entropy threshold Sth is equal to 0.6. The statistical entropy of step S423 can be calculated according to the following formula (6):

where p _i is the probability that the sequence is in class i (6)

According to formula (6), the statistical entropy S1 of sequence R1 is equal to 0.1 A larger entropy value (larger disorder) means that the probability distribution is closer to a uniform distribution (Uniform Distribution), while a smaller entropy value means that the probability distribution is biased towards one end. In the above example, if the probability distribution is biased towards class H, then this sequence can be regarded as a typical sequence in class H dates. In step S424, since the first occurrence rate (41/56) is greater than the probability threshold Pth, and the statistical entropy S1=0.1 is less than the entropy threshold Sth, the sequence R1 can be determined as a typical sequence in class H dates. Similarly, the statistical entropy S2 of the sequence R2 can also be calculated according to formula (6), and S2=0.69 can be obtained. Since the statistical entropy S2 is greater than the entropy threshold Sth, the sequence R2 is not a typical sequence in class H dates. As shown in Table 1, the first occurrence rate (28/56) of the sequence R2 in the class H date is similar to the second occurrence rate (50/128) in the class (all-H) date, which means that the sequence R2 does not It does not appear in any particular date type, so sequence R2 is not a typical sequence. After finding multiple typical sequences of a date type, the multiple typical sequences can be further classified into sets, and the classification method can be shown in steps S360, S370, S380, and S390.

According to the method for finding out crowd movement behavior according to the embodiment of the present invention, the track of crowd movement behavior can be found by collecting location data captured from a user device, such as a smart card. The payment service provider who issues the smart card can estimate the number of cardholders in a specific geographical area based on the obtained crowd movement behavior trajectory, design a marketing and advertising plan accordingly, decide the location of a new store, and so on. The method of understanding the movement behavior of crowds can be applied at many levels and help to make important decisions. Furthermore, since the embodiment of the present invention can find out the typical sequence of a specific date type, the payment service provider can plan and organize activities belonging to different date types correspondingly according to the typical sequence of different date types.

In summary, although the present invention has been disclosed as above with preferred embodiments, it is not intended to limit the present invention. Those skilled in the art of the present invention can make various changes and modifications without departing from the spirit and scope of the present invention. Therefore, the scope of protection of the present invention should be determined by the scope of claims.

Claims (14)

1. a kind of method for finding out crowd's mobile behavior, including：

Collect the multiple position datas with regard to multiple user's sets；

The multiple usual pattern in those position datas is detected to produce multiple representative series, wherein the respectively representative series bag An at least line segment is included, an at least line segment is between source location set and end position point；And

According to the multiple sequence distances between those representative series, those representative series are categorized as into multiple set, to look for Go out crowd's mobile behavior.

2. the method for claim 1, wherein those representative series are further included：

First ray, including the first line segment, first line segment is put a little and the first end position point between in first start bit；And

Second sequence, including second line segment, the second line segment is between the second source location set and the second end position point；

Wherein the First ray and second sequence form the sequence pair in those representative series, for each sequence It is right, those representative series are categorized as to further include the step of those are gathered：

Calculate the line segment distance between first line segment and the second line segment；And

According to the line segment distance between first line segment and the second line segment, determine between the First ray and second sequence Sequence distance.

3. method as claimed in claim 2, wherein calculating the line segment distance between first line segment and the second line segment Step is further included：

Calculate angular distance between first line segment and the second line segment, vertical range and parallel distance；

According to the angular distance, the vertical range and the parallel distance, regular angular distance, regular vertical range and just are calculated Ruleization parallel distance, wherein the value of the regular angular distance, the regular vertical range and the regular parallel distance is identical Codomain in；And

According to the weighted sum of the regular angular distance, the regular vertical range and the regular parallel distance, determine this The line segment distance between one line segment and the second line segment.

4. method as claimed in claim 3, wherein calculating the parallel distance between first line segment and the second line segment Step is further included：

Second source location set is projected in into the extension line of first line segment, to obtain the 3rd initial subpoint；

By the second end position spot projection in the extension line of first line segment, to obtain the 3rd subpoint is terminated；

Connect the 3rd initial subpoint and the 3rd end subpoint, to produce the 3rd line segment；And

The union of first line segment and the 3rd line segment is deducted into the common factor of first line segment and the 3rd line segment, to determine that this is put down Row distance.

5. method as claimed in claim 4, wherein calculating the regular angular distance, the regular vertical range and this is regular The step of changing parallel distance further includes：

By the angular distance divided by angular distance delocalization maximum, to obtain the regular angular distance；

By the vertical range divided by vertical range domain maximum, to obtain the regular vertical range；And

By the parallel distance divided by parallel distance domain maximum, to obtain the regular parallel distance.

6. method as claimed in claim 5, the maximum of the wherein angular distance delocalization is that first line segment is worked as with the second line segment The length of middle shorter one, the maximum in the parallel distance domain is the union of first line segment and the 3rd line segment, this vertically away from The maximum of delocalization is the vertical range after first line segment and rotation between line segment, and line segment is by should wherein after the rotation Second line segment around second source location set or around the second end position point rotation, until perpendicular to first line segment with Obtain.

7. method as claimed in claim 2, wherein determining the sequence distance between the First ray and second sequence Step is further included：

According to an at least line segment in the middle of an at least line segment in the middle of the First ray and second sequence, the First ray with Multiple image combinations are produced between second sequence；

Calculate the image distance of the respectively image combination；And

With the minimum mapping distance in the middle of the respectively image combination, as the sequence between the First ray and second sequence away from From.

8. method as claimed in claim 7, wherein calculate the image of the respectively image combination apart from the step of further include：

According to time sequencing, in the middle of the First ray in the middle of an at least line segment and second sequence an at least line segment it Between, form multiple mappings right；

Calculate respectively the mapping to line segment distance；And

Calculate respectively the mapping to the line segment distance mean value, to obtain the mapping distance.

9. the method for claim 1, wherein those position datas are received when those user's sets are used for and pay activity Collection.

10. the method for claim 1, wherein the step of collecting those position datas with regard to those user's sets is more wrapped Include：

Select multiple reference position points；And

By each location point in those position datas, it is substituted by and immediate those reference bits in each location point geographical position Put a little one of them.

11. the method for claim 1, wherein detecting those the usual patterns in those position datas to produce those generations The step of table sequence, further includes：

Remove the usual pattern only in those usual patterns with single location point；

In the respectively usual pattern, identical adjacent position point is removed；And

By those usual Pattern Aggregations of a few days producing those representative series.

12. the method for claim 1, wherein the step of those representative series are categorized as into those set further includes：

Respectively the representative series will gather as one；

Select two set to be formed in gathering from place near the steps and gather right, calculate respectively aggregate distance of the set between；

Find out the first set with minimal set distance and second set；And

If the minimal set distance is less than apart from threshold value, merge the first set and the second set.

13. the method for claim 1, further include：

Multiple date types will be divided into the date；And

According to those representative series in the occurrence rate of target date type, the type sequence of the target date type is found out.

14. methods as claimed in claim 13, wherein the step of finding out the type sequence of the target date type further includes：

Calculate test representative series and belong to the first occurrence rate in type date target date；

The test representative series are calculated in non-the second occurrence rate belonged in type date target date；

According to first occurrence rate and second occurrence rate, counting statistics entropy；And

If first occurrence rate is more than probability threshold value, and the statistical entropy is less than entropy threshold value, determines the test representativeness sequence It is classified as the type sequence.