{'fraction_non_alphanumeric': 0.02884759853758702, 'fraction_numerical': 0.008664296088546101, 'mean_word_length': 4.642271828200056, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Trajectory Pattern Mining Using Sequential Pattern Mining and K-Means for Predicting Future Location

Sequential pattern mining is a method used to find patterns while concerning the sequence of an item set. Sequential pattern mining can be used to find trajectory patterns in moving object data. To implement it in the real life, the spatial attribute of the data needs to be generalized/grouped. In this paper, K-Means is used to group the spatial attribute. In order to group the spatial attribute, the temporal attribute is also considered to see how the patterns are related to time. The resulting trajectory patterns are then used to visualize the habit of the moving object. Therefore, trajectory patterns are used as the reference in this paper to predict the future location of the object. Predicting the future location of the object is performed using the movement history of the object. Result of this research is trajectory pattern which repeat at certain time duration according to its data characteristics.


Introduction
Lately, people use cell phone to support almost all of their activities. Therefore, it is normal that the cell phone usage in this era is growing very rapidly. In the year of 2000, Indonesian mobile phone users were about 3.6 million. In 2012, that number increased significantly, reaching a total of 280 million [1]. Cell phone service provider always keep a record every time its user communicates with other users, e.g. when the user make a phone call or send a text message. That data is called Calls Details Record (CDR).
Meanwhile, Location Based Service (LBS) is a service that provides information about a place [2]. LBS can be easily accessed using mobile devices. An example of a system applying LBS is Global Positioning System (GPS). GPS can be used on a vehicle, cell phone, and even animal to find its position at a time. So, using GPS can generate data containing the location of an object. An example of the data is path traversed by a taxi, the migration of animals, and the location of a plane. Spatio-temporal database is a database managing the spatial attribute that changes over time [3]. A moving object data is an example. CDR and GPS data are another example because the data describes the location of an object at a time. A set of locations in a period of time can show the movement of the object from time to time.
Pattern recognition is a technique to classify or to describe object based on its quantitative characteristics or its main property. Pattern that can be recognized form moving object data includes repetitive pattern, relationship pattern, and frequent trajectory pattern [4]. Repetitive pattern is a pattern formed from an object doing some movement periodically. An example is a bird that every day is flying from its nest to look for food. Relationship pattern is a trajectory pattern resulting from a collection of objects that is moving and each has a relation with each other. Frequent trajectory pattern is a pattern which is the trend of the movement of all objects. Frequent trajectory pattern mining can be applied in both CDR and GPS data to see the habit of the moving object. This habit can be represented as trajectory pattern. The discovered trajectory patterns are then can be used to predict the future location of an object. In more advanced development, the discovered trajectory patterns can be utilized to know which road segment is often passed by. So, it can be used to give recommendation which road segment needs restoration or to give new routes recommendation. For example, from the trajectory patterns discovered, it is known that movement from location A to location B is quite crowded and the road segment is narrow. From that, the possible recommendation is to improve the road segment from location A to location B.

Sequential pattern mining
Item is the basic value for numerous data mining problems. It can be considered as objects bought by customer, location visited by bus, etc. Item set is a set of items that are grouped by timestamp. Meanwhile, data sequence is a sequence of item set associated to an object [5]. On Table 1, data sequence for object C2 is "(Camcorder, MiniDV) (DVD Rec, DVD-R) (Video Soft)". It means that the customer bought camcorder and miniDV on the same day, then bought DVD recorder and DVD-R on the next day, and bought video software some days later.
Sequential pattern can be found in a data sequence. For example, "(MiniDV) (Video Soft)" can be found in C2, but "(DVD Rec) (Camcorder)" cannot be found in C2 because it is not in the right order (Camcorder came first). In sequential pattern mining, user has to define the minimum support value. The minimum support value is the minimum number of data sequence that satisfies the sequential patterns so the sequential pattern can be categorized as a frequent pattern. For example, from Table 1, there are four customers in four days. If the value of minimum support is 50% of total customers, then sequence pattern has to be found in minimum two data sequences. A sequential pattern mining performed on the data will find three patterns: • S1: "(Camcorder, MiniDV) (DVD Rec, DVD-R)"  Pattern S1 can be found at data sequence C2 and C4, pattern S2 can be found at C2 and C3, and pattern S3 can be found at C1 and C2.

K-Means
Clustering or cluster analysis is the process of grouping set of objects into clusters. The objects grouped in a cluster will have a high similarity with each other and are different with objects from the other clusters [6]. The higher the similarity and the higher the differences, the better the cluster is. Prototype-based clustering is a type of clustering. On prototype-based clustering, a cluster is a set of objects with higher similarity to its prototype than to other prototypes [7]. K-Means is an example of prototype-based clustering. The first step of implementing K-Means is choosing the initial K centroid, with K is the number of cluster defined by the user. Each object is assigned to a cluster with the closest centroid. After the assigning process is done, each cluster centroid is then updated based on the objects in the cluster.
These steps are repeated until there are no object moving to other cluster, or in another word, the process will continue until the centroid value doesn't change anymore.
Example of applying K-Means algorithm in clustering object can be seen at Figure 1. On Figure 1 (a), three objects are assigned as the initial centroids. Each object aside from the three before are then assigned to the closest cluster (based on the distance to centroids). On Figure 1, objects are represented in difference shapes, which are: triangle, square, and circle. After the objects are clustered, centroids value is updated and then the objects are clustered again based on the distance to the new centroids. On Figure 1

Related Work
Spatial or spatio-temporal data clustering have been developed by Tork in 2012 using K-Means algorithm. Spatial data clustering method have the same concept like normal clustering. The differences are only on the data type [8]. Data shown in Figure 2 is a sample of simple data (containing no spatial data). Each point is represented in <x,y> form in a 2-D space. It doesn't have any information about the spatial or temporal data of the points. Using this definition, spatial clustering can be simplified into two dimensional vector, like <x,y>, but its values are replaced with spatial value, e.g. longitude and latitude. Spatio-temporal data clustering is very much the same with with spatial data clustering. The differences between spatio-temporal data clustering and spatial data clustering lies in the distance calculation. For example, take a look at the K-Means distance calculation algorithm. The first step is to change spatio-temporal data into three dimensional vector <x,y,t>. Tuple <x,y> is the spatial attribute, and t is the temporal attribute [8]. Using the new three dimensional vector <x,y,t>, spatiotemporal distance (using Euclidean distance) can be calculated as: Trajectory pattern mining using sequential pattern mining method has been developed by Chung et al. in 2002. The steps are as follow.
1) Make some adjustment to the data representation and arrange the database.
3) Moving sequence/trajectory extraction. On this step, user have to define the maximum duration between each movement. 4) Trajectory pattern mining from moving sequence/trajectory data. Fk represents pattern-k obtained from data. Ck represents pattern candidate. Ck is self-join from Fk-1, ..., Fk-1 * Fk-1. The support value is calculated by checking if the trajectory data satisfies the pattern candidate. If the support value is less than the minimum value, pattern candidate is not assigned as frequent trajectory pattern.

Trajectory Pattern Mining
Trajectory pattern mining consists of several steps which are: data pre-processing, clustering the spatial attribute, data adjustment, and pattern mining. On the pattern mining step, a model of the spatial attribute cluster and trajectory pattern are gained. The result is used as reference to predict the future location.

Data preprocessing
Data preprocessing is a must before the trajectory pattern mining is performed. It consists of two steps. The first step is to cleanse the data and the second step is to generate additional attribute from temporal attribute. The cleansing is done by changing the time attribute into datetime attribute. Datetime is an attribute formed by joining the time attribute and the date attribute. Another adjustment is done to the attribute at each record to fit its definition. The last adjustment is handling the incomplete record or empty record. In the incomplete record case, if the missing attribute is the spatial or the temporal attribute, then the record won't be used in the calculation. This is because trajectory pattern mining can't be done without it. For clustering step, we need an additional attribute which represents the temporal attribute. The temporal attribute is in datetime type. As it is, temporal attribute is unique and it would be harder to find the pattern. For clustering step, temporal attribute is derived to get a new attribute. A new derived temporal attribute is needed in order to enhance the quality of the trajectory pattern. To simplify the pattern mining, the temporal attribute is changed into two types of hour unit. The first type, called the daily type, only uses the hour attribute from the original datetime. The second type, the weekly type uses the date and the hour attribute from the datetime. The steps to change the temporal value into weekly type are as follow.
1) Change the date into day. For example, for June 14th 2016 is Tuesday.
2) Change the day value into dayOfWeek (see Table 2).
3) The new temporal value, the weekly type is calculated with the formula (2) below. ‫ݐ‬ ௪௬ = ሺ݀ܽ‫ܹ݂ܱ݇݁݁ݕ‬ * 24ሻ ‫ݎݑ‪ℎ‬‬ (2) dayOfWeek is multiplied by 24 because there are 24 hours in a day.

Spatial clustering
There are two experiments performed to cluster the data. In the first experiment, data clustering only involves spatial attribute. K-Means algorithm is chosen because it uses the same mechanism to cluster spatial data only and spatial with temporal attribute. In the first experiment, the spatial attribute has latitude and longitude values. Formula (3) is used as distance calculation function in K-Means for spatial data clustering.
In the second experiment, the data clustered are spatial attribute (latitude and longitude) and temporal attribute (which value had been changed into daily or weekly). Formula (1) is used as distance calculation function for the second K-Means experiment. Spatial attribute (x,y) and temporal attribute (t) each has different unit, but using distance calculation function (see Formula 1), both attributes are considered as equal. Normalization of attribute is done to balance the spatial and temporal attributes. With normalization, there are no specific attribute that would affect the cluster arrangement greatly. The result from data clustering step is a data clustering model. This model is used to define test data cluster before it is used later for predicting future location.

Generating trajectory data
The trajectory data is generated from clustered data. Object id, datetime, and spatial cluster are the attributes used in this step. Spatial attribute is no longer used because it has been replaced by the spatial cluster. In detail, trajectory data is generated from set of spatial clusters with the same object id in a certain time range. Set of trajectory data can be generated using these following steps.
1) Define the maximum movement duration from one location to the next location.
2) Calculate time differences between location L and last location in trajectory T.
3) If the time difference is less than or equal with maximum movement duration, then L is the next location of trajectory T. 4) If the time difference is more than the maximum movement duration, then L is the first location of a new trajectory.

Trajectory pattern mining
Temporal pattern mining, which was developed by Chung et al., 2002, is used for trajectory pattern mining. Temporal pattern mining is sequential pattern mining for moving object data. Temporal pattern mining is chosen because trajectory pattern can be recognized even though there is a missing point in the data. Data used in pattern mining are the data that have been generated into trajectory data. Some examples of generated trajectory data are <A B C D>, <A E C D>, and <B C D A>. The result of pattern mining using temporal pattern mining for the example trajectory data above can be seen at Table 3. Table 3. Examples of trajectory pattern obtained from trajectory data.

Location Prediction
Location prediction is initiated with data pre-processing. Data pre-processing is performed by clustering spatial attribute using clustering model produced in trajectory pattern mining step. After the data is clustered, trajectory data is generated using the same steps used in trajectory pattern mining. Location prediction is done with the following steps. 1) Each trajectory pattern is divided into two parts, the first part is called route and the second part is called nextStep. The route is a set of spatial cluster from the first cluster to n-1 spatial cluster from the trajectory pattern. nextStep is the last spatial cluster from trajectory pattern. For example, for trajectory pattern <S1 S2 S3 S4 … Sn-1 Sn>, the value of route is <S1 S2 S3 S4 … Sn-1> and the value of nextStep is <Sn>. 2) Testing is performed to measure the similarity between test data and route. If route is a sequence pattern from test data, the prediction of future location is the nextStep of its route. 3) Similarity value of test data and route can be measured by two type of pattern quality functions, value and density. Value type is the value of support from trajectory pattern, while support value is the number of trajectory data which satisfies trajectory pattern [10]. Meanwhile, value of density type is obtained using Formula 4.
If there is more than one route which satisfies the test data, then a route with the highest value of pattern quality will be chosen. Table 4 shows the examples of trajectory patterns. For example, <C D A D B C> is the test data to be predicted. In Table 5, examples of the similarity calculation between test data and trajectory pattern from Table 4 are shown. The prediction result using value type of pattern quality calculation is <A>, while the prediction result using density-typed pattern quality is <D>.

Experimental Result
In trajectory pattern mining, the value of some variables which will determine the trajectory pattern needs to be determined. The purpose of the experiment is to determine the best combination from the value of variables which would yield the best accuracy. Experiment is done using two datasets. The first dataset is CDR data, and the second dataset is taxi GPS data. Each dataset is divided into two parts, 80% of data as train data, and 20% of data as test data. Variables which values are needed to be determined are: 1) Number of K-Means cluster.
3) Pattern quality calculation function. 4) Minimum support value for trajectory pattern. Experiment is done by trajectory pattern mining on train data using every possible combination of variables value. The evaluation of experiment result is done by calculating accuracy from location prediction of test data.

Experiment using CDR data
The CDR data used for experiment is CDR data from mobile phone users in Bali and its surrounding areas. The characteristics of CDR data are as follow.
1) Number  Table 6. Temporal attribute usage in clustering greatly determines accuracy result of location prediction. Weekly type temporal attribute usage in clustering resulted in higher accuracy than daily type and no type. Average accuracy value for weekly type is 98,96%, while average accuracy value for daily type is 50,44% and for no type is 55,60%. Average accuracy value for weekly type is higher, that means that trajectory pattern in CDR data is unique for each day in a week (repeated every week).
Average accuracy value of location prediction based on minimum support value is shown in Figure  3. The higher the minimum support value, the smaller the average of accuracy value is. This is because higher minimum support value will cause more pattern candidates did not satisfy the minimum value. : July 1 st 2013 -July 7 th 2013 Taxi GPS data type is different with the general moving object data type. Taxi GPS data contains a set of spatial points which are passed in taxi trip. In other words, one record of taxi GPS data represents one trajectory, not only one spatial point. One spatial point in taxi GPS data is recorded every 15 seconds in every taxi trip. Variables value that are used in the experiment using taxi GPS data are as follow. Based on the experimental result, the 3 best variable configurations can be seen in Table 7. Based on experimental result using taxi GPS data, temporal attribute usage in clustering really determines the accuracy of location prediction. Daily type temporal attribute usage in clustering has higher average accuracy value than weekly type and no type. Average accuracy for daily type is 99,586%, while the average accuracy value for weekly type is 34,296% and the average accuracy value for no type is 41,833%. Average accuracy value for daily type is higher, that means the trajectory pattern in taxi GPS data is repeated every day.
The effect of minimum support value in this experiment, is same as the effect of minimum support value in CDR data experiment. The higher minimum support value, the smaller average of accuracy value.

Conclusion and Future Works
In this research, trajectory pattern mining and future location prediction has been developed using sequential pattern mining method. Trajectory pattern mining and future location prediction has been tested using CDR data and taxi GPS data. Based on the experiment result, the best accuracy for location prediction using CDR data is 99,437% and the best accuracy using taxi GPS data is 99,712%. K-Means algorithm is used for spatial data clustering. Clustering is done twice, using only the spatial attribute and spatial and temporal attribute. Temporal attribute usage in clustering highly affects the accuracy of trajectory pattern mining. Using temporal attribute, time characteristic of trajectory pattern can be recognized. Based on experiment result of trajectory pattern mining and future location prediction, trajectory pattern of CDR data is repeated every week. Meanwhile, the trajectory pattern of taxi GPS data is repeated every day.
For future research of trajectory pattern mining, spatial clustering can be done using region/area concept. For example, spatial attribute is clustered based on administrative region.