MinUS Tool

MinUS Tool

This is an experimental tool that can abstract users' profiles from the source data of their geographical trajectories and then use them to compare user similarity by virtue of different similarity measures. Below is the general workflow of the tool.

It consists of three main modules:

Managing datasets

Constructing user profiles

Measuring user similarity

Created with the Personal Edition of HelpNDoc: Full-featured multi-format Help generator


Managing datasets

MinUS Tool ››

Managing datasets

This module consists of two parts, which are basic operations of datasets and viewing statistic information.

1. Managing datasets

The tool is able to handle two types of datasets according to the different types of source data. Source data of the new dataset a user provides should be of one of the two types, GPS points and stay points. When adding a new dataset of some type, the tool will check if the source data of the dataset is in accord with the format requirements of that type. The output directory chosen when adding a new dataset must be empty.

The format requirements of datasets of the GPS point type are:

  • The input directory contains subfolders each of which is for one user and whose names are the users' three-digit numbered IDs, like 003.
  • In each user's subfolder there is one folder named "Trajectory", in which each file contains his GPS point trajectory in one day, or part of it.
  • The first eight characters of each filename are the date of the day, like 20081023025304.
  • The first six lines in each file are useless. Each line next, which consists of seven fields separated by ",", corresponds to one GPS point. The following explains what each field means.

Field 1: Latitude in decimal degrees

Field 2: Longitude in decimal degrees

Field 3: useless, can be set to anything

Field 4: Altitude in feet (-777 if not available)

Field 5: Date - number of days (with fractional part) that have passed since 12/30/1899

Field 6: Date as a string

Field 7: Time as a string

Note that field 5 and field 6&7 represent the same date/time. The tool only uses fields 1, 2 and 7.

Example:

39.906631,116.385564,0,492,40097.5864583333,2009-10-11,14:04:30

39.906554,116.385625,0,492,40097.5865162037,2009-10-11,14:04:35

The format requirements of datasets of the stay point type are:

  • The input directory contains files each of which is one user's stay point trajectories.
  • Each filename is the user's three-digit numbered ID, like 003.
  • Each line in each file, which consists of a number of fields separated by " ", is a stay point trajectory in one day.

The first field is the date whose format is "yyyyMMdd".

The second field is the number of stay points in the day.

The third field marks the type of the day. 1 stands for a weekday. 0 stands for a weekend.

Each group of three fields next belongs to one stay point.

The first field in a group is the arrival time of the point whose format means the number of seconds from the first second of the day.

The second field is the latitude of the point in decimal degrees.

The third field is the longitude of the point in decimal degrees.

Example:

20110308 3 1 42140 37.562414 126.93687299999999 46072 37.5485335 127.0378605 76845 37.535098 127.140947

20110319 2 0 0 37.5352175 127.140589 48518 37.535098 127.140947

If the dataset is added successfully, the tool will continue gathering users' statistics of GPS trajectories or stay point trajectories for the two types of datasets, respectively.

The name and output directory of an existing dataset can be changed. Users can choose whether to delete contents on disk as well while deleting a dataset.

All relevent information of datasets is stored in a file named "Datasets" in the direcory from which the tool is running.

Every four lines belong to a dataset, each of which has two fields like a key-value pair separated by ";".

Line 1: the dataset's name

Line 2: the dataset's type

Line 3: the pathname of the dataset's input directory

Line 4: the pathname of the dataset's output directory

Example:

Name;Geolife

Type;GPS

InputPath;C:\Documents and Settings\Ruipeng Lu\My Documents\workspace\data\GeolifeDataset

OutputPath;C:\Documents and Settings\Ruipeng Lu\My Documents\workspace\data\OutputGeolife

2. Viewing statistics

Users can view a dataset's general information, which includes its name, type, input directory, output directory, and the number of users it contains.

The tool also permits viewing statistics of users included in a dataset, which includes statistics of GPS point trajectories and possible statistics of stay points if already detected for a dataset of the GPS point type, or only statistics of stay points for a dataset of the stay point type. The list in the user interface allows multiple selection, so statistics of any number of users can be viewed at a time.

For datasets of GPS point type, statistics of GPS point trajectories and stay points are stored in a folder whose relative pathname is "\Stats\SourceDataAndStayPoints" in the dataset's output directory. A file named "SourceData" stores statistics of GPS point trajectories. Statistics of stay points obtained under a parameter setting used when detecting stay points are stored in a file whose filename is of the format like "StayPoints-200.0_30.0_200.0", in which "200.0_30.0_200.0" is the string of the parameter setting.

For datasets of stay point type, statistics of stay points are stored in a file named "StayPoints" in a folder named "Stats" which in turn is in the dataset's output directory.

Created with the Personal Edition of HelpNDoc: Easily create Help documents


Constructing user profiles

MinUS Tool ››

Constructing user profiles

For datasets of GPS point type this process is made up of three sequential steps, which are detecting stay points, generating RoIs and extracting frequent pattern sets, while for datasets of stay point type it only consists of the latter two steps. The intermediate results can be visualized on maps and viewed.

Ⅰ. The construction process

1. Detecting stay points

First you need to select a user in the list. Three parameters need setting before detecting stay points, which are the time interval threshold θt, the distance threshold θd and the threshold θm. A stay point stands for a geographic region, where a user stays over a time interval threshold θt and within a distance threshold θd. The first point and the last point of a GPS point trajectory are directly regarded as stay points. If the distances between them and other stay points are below a threshold θm, they are merged into one stay point by replacing them with the middle point of the line segment connecting them.

Briefly,

  • θt is the minimum time length that a continuous set of GPS points lasts to be a stay point. A typical value is 30 minutes.
  • θd is the maximum distance between the first point and the last point of a continuous set of GPS points for them to be a stay point. Typical values are like 100m, 150m and 200m.
  • θm is the maximum distance for the first stay point and the next point, or for the last stay point and the previous point of a stay point trajectory to be merged into one. A common practice is to make it take the same value as the distance threshold.

Statistics of stay points will be generated in course of detection. Users' files of stay point trajectories are stored in a subfolder in a folder named "StayPoints" which is in the dataset's output directory. This subfolder's name is a string of the parameter setting used when detecting the users' stay points, whose format is "θd_θt_θm", like "200.0_30.0_200.0".

2. Generating RoIs

First you need to select an item in the combo box, which stands for the parameter setting used when detecting stay points. Then select the users whom you want to cluster and form RoIs together in the list. It is meaningful to generate RoIs from multiple users' stay points only when all the stay points are detected using the same parameter setting. Three parameters need setting, which are the deletion percentage that refers to how many stay points at most will constitute outliers and then be deleted before proceeding to the clustering process, and the upper and lower bounds of a parameter K that will be used in the LOF algorithm of removing the outliers.

  • A typical value of the deletion percentage is 20 or 30.
  • Typical bounds of K are 5 and 35 when the number of stay points to be clustered is less than 1000, 10 and 50 when the number is between 1000 and 3000, 20 and 100 when the number is more than 3000. But these are not necessarily applicable. Different sets of stay points may require different bounds of K.

An RoI filename consists of two parts separated by "-". The first part is a string separated by "_" and concatenated with users who are involved in forming the RoI file. The second part is a string of the parameter setting used when forming the RoI file, which is of the format "the deletion percentage_lower bound_upper bound". An example is "003_004_017_030_068_113_151_160_163_164-30_5_35.txt".

For datasets of GPS point type, RoI files are placed in a subfolder in a folder named "RoIs" in the dataset's output directory. This subfolder's name is a string of the parameter setting used when detecting stay points which are clustered to form the RoI file, like "200.0_30.0_200.0". For datasets of stay point type, RoI files are placed directly in the folder named "RoIs".

In course of generating an RoI file, its statistics will be produced, which are the latitudes and longitudes of the lower-left and upper-right points of the bounding rectangle of all the RoIs in the file. For datasets of GPS point type, the file storing the statistics is placed in a subfolder in a folder named "RoIs" in the dataset's output directory. The format of the subfolder's name is the same as that of the subfolder mentioned in the last paragraph. For datasets of stay point type, the file is placed directly in the folder named "RoIs".

3. Extracting frequent pattern sets

After obtaining the RoI file, frequent pattern sets will be able to be extracted from stay point trajectories. Only the frequent patterns of those users who are involved in generating a RoI file can be extracted based on the file from the users' files of stay point trajectories used to generate the RoI file.

Parameters which need setting include the support value threshold, the time tolerance, the side length of a cell, the type of days taken into account and a usable RoI file.

  • The support value threshold specifies the minimum percentage of trajectories that contain a specific pattern for it to be a frequent pattern. It should be between 0 and 1. A typical value is 0.1.
  • The time tolerance is the maximum allowed time length that the transition time between two RoIs in a pattern can differ from the transition time between two points in a trajectory in order to let the trajectory contain the pattern. A typical value is 7200 seconds.
  • The side length of a cell which is a terminology used in course of trajectory pattern mining refers to the span of latitudes or longitudes a cell covers. A typical value is 0.02.
  • Choose a type of days in which stay point trajectories will be taken into account when extracting pattern sets. There are three types, which are "AllDays", "Weekend" and "Weekday".
  • Choose an RoI file you want to use by selecting an item in the combo box after selecting a user in the list. Its statistics which will be used when extracting pattern sets will be read from the statistics file automatically.

To illuminate where the consequent file storing a user's pattern sets will be placed, we take an example. The pattern set file of a user in a dataset of GPS point type will be placed in a folder whose relative pathname is "\PatternSets\200.0_30.0_200.0\009-30_5_35.txt\0.1_7200.0_0.02_AllDays" in the dataset's output directory. "200.0_30.0_200.0" is the string of the parameter setting used when detecting stay points. "009-30_5_35.txt" is the RoI filename. "0.1_7200.0_0.02_AllDays" is the string concatenated with parameters used when extracting pattern sets, whose format is "support value threshold_time tolerance_side length of a cell_type of days". For a dataset of stay point type, the directory "200.0_30.0_200.0" does not exist, and all other directories remain the same.

Ⅱ. Visualization and viewing files

In the midst of constructing a user's profile, we can visualize the intermediate results, like his GPS and stay point trajectories, and RoI files which he is involved in forming, by displaying them on maps. Any combination of the three types of intermediate results can be chose at a time and displayed together in the visualization panel. By clicking context menus an intermediate result can be visualized individually as well. A user's files that stores his intermediate results can also be opened and viewed via right-click menus of the list components in the visualization panel and those panels for steps of constructing user profiles.

Created with the Personal Edition of HelpNDoc: Free iPhone documentation generator


Measuring user similarity

MinUS Tool ››

Measuring user similarity

Ⅰ. Managing semantic files

First we introduce how to take semantics into account if we want to compare user similarity semantically. A region of interest (RoI) is a geographical region, which is deemed to provide several funtions, like "restaurant" and "supermarket". The possibilities of people utilizing its different functions at the RoI are different. So we use a probability distribution to represent the RoI's semantic information, in which each probability represents the possibility of people utilizing its corresponding funtion at the site. A file which stores all RoI IDs in an RoI file and their associated probability distributions is called a semantic file.

Each line in a semantic file includes an RoI ID, which appears in the first field, and its corresponding probability distribution. All the lines are arranged according to the RoI IDs in ascending order.

An example of the content in a semantic file is:

0 0.25 0.25 0.25 0.25

1 0.0 0.4 0.3 0.3

The tool provides two ways of adding a semantic file, which are to have the tool automatically generate one whose LS-vectors are normally distributed based on an RoI file, or to add an existing one manually. Each semantic file is only attached to one RoI file, so a semantic file can only be used when comparing users' pattern sets that are produced based on the RoI file to which the semantic file is attached to.

Ⅱ. Comparing users

The tool provides four user similarity measures, which are the MSTP-similarity measure and the improved MSTP-similarity measure, and CPS-based and Hausdorff distance based ones. To list the users' pattern sets which can be compared with each other, we need to specify three parameters successively for datasets of GPS point type, which are the parameter setting used when detecting stay points, the RoI file based on and the parameter setting when extracting these pattern sets, by selecting items from the three combo boxes from top to bottom. An arbitrary number of users can be chosen to be compared at a time. The result will be displayed in a table in which the gray value of each cell' background color is linearly proportional to the similarity value contained in the cell.

To clarify where a file storing the comparison results is placed, we take an example. The resultant file, whose filename is "002_003_004_007" after comparing users 002, 003, 004 and 007 of a dataset of GPS point type, is placed in a folder whose relative pathname is "\ComparisonResults\200.0_30.0_200.0\001_002_003_004_007_009_081_082_121_122-30_115_200.txt\0.1_7200.0_0.02_AllDays" in the dataset's output directory. "200.0_30.0_200.0" is the string of the parameter setting used when detecting stay points. "009-30_5_35.txt" is the RoI filename. "0.1_7200.0_0.02_AllDays" is the string concatenated with parameters used when extracting pattern sets. For a dataset of stay point type, the directory "200.0_30.0_200.0" does not exist, and all other directories remain the same.

If the comparison results for the users you are comparing already exist, they will be read from the file and then displayed in a table rather than calculated again.

Created with the Personal Edition of HelpNDoc: Easily create Web Help sites