Base Station Location Analysis Based On Near Grid DBSCAN Algorithm And Smallest Enclosing Disk Model

Location-based service is one of the most important features of mobile Internet, inrecent years, applications related to location-based service gets popular, and users get thesurrounding service by uploading their location information. The location informationreflects the characteristics of human behavior, their interests and social relationships, it ismeaningful for the personalized recommendation. However, the uncertainty of the locationinformation brought outliers; On the other hand, localization service such as therecommending contents under the station which people often stay are more acceptable topublic, because of the focus on the privacy safety of location information, it is extremelydifficulty to obtain the base station’s location information.Based on the above background, this dissertation presents the research on outliersdetecting technology based on the location-data and the base station location modeling, toprovide decision-making support for user portrait and personalized service. The main workas follows:(1) Summarizing the outlier detection technology which is existed and analyzing theadvantages, disadvantages and applicable scope of the technology, focusing on analyzingthe density-based clustering algorithm-DBSCAN. Proposing an improved algorithm whichcalled near grid DBSCAN (NGID-DBSCAN) with meshing technique to narrowneighborhood scanning range in order to improve the time complexity of algorithm, and itsperformance is verified by the simulation experiment. Using the improved densityclustering method for detecting the base station outliers, and compare with the advantagesand disadvantages of data visualization method.(2) Researching the algorithm for solving the smallest enclosing disk of plane pointsets, and consider the four-point circle problem in farthest point priority for incrementalalgorithm, reducing the number of enumeration to improve performance by introducing thesmallest enclosing disk lemma in the algorithm implementation process which convers thefour-point circle problem to three-point circle problem. (3) Coming up with an idea that converts base station location analysis tomathematical modeling of a large number of the user’s location, and instead of solving thelocation of base station by solving the centre of smallest enclosing disk, which are verifiedeffective. Taking into account of time complexity, analyzing when the point sets forma cluster can use central point to instead of smallest enclosing disk’s center.The near grid DBSCAN algorithm with the smallest enclosing disk model proposed inthis dissertation have the effect in checking out the known error data and supplementfollow-up location information of base station.