Research on KDT-DBSCAN-based Personal Semantic Location Acquisition

摘要

With the development of science and technology in recent years, the planning and construction of smart cities have entered a new era. Among them, smart city safety management is the foundation that supports the stable development of the entire city, and location-based services are one of its important technical support. The popularity of GPS-equipped devices provides a large amount of data for trajectory mining. Discovering personal semantic locations by mining these data is an application based on location services. Personal semantic locations are frequently visited by individual users and have significant semantic meaning to users (such as home, work place, etc.). The discovery of the user's personal semantic location involves obtaining the physical location and semantics. At present, related research mostly uses clustering algorithms to obtain the physical location, of which the DBSCAN algorithm is the most commonly used. When the traditional DBSCAN algorithm determines whether a sample belongs to a certain cluster, it will generate a large number of repeated calculations, which will reduce the program operation efficiency. In order to solve this problem, this paper proposes an improved DBSCAN algorithm KDT-DBSCAN. The algorithm uses a k-d tree to screen samples that need to be calculated. By excluding samples that do not need to be calculated, the purpose of improving the calculation efficiency can be achieved. In the problem of semantic location recognition, this paper pre-defines the daily behavior patterns of people, and identifies the location semantics based on the temporal characteristics of the samples in each category. When calculating the distance between samples, the algorithm proposed here is 8.8 times more efficient than the traditional algorithm.