{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T16:11:05Z","timestamp":1778602265505,"version":"3.51.4"},"reference-count":53,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2017,12,1]],"date-time":"2017-12-01T00:00:00Z","timestamp":1512086400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Rapidly growing Global Positioning System (GPS) data plays an important role in trajectory and their applications (e.g., GPS-enabled smart devices). In order to employ K-means to mine the better origins and destinations (OD) behind the GPS data and overcome its shortcomings including slowness of convergence, sensitivity to initial seeds selection, and getting stuck in a local optimum, this paper proposes and focuses on a novel niche genetic algorithm (NGA) with density and noise for K-means clustering (NoiseClust). In NoiseClust, an improved noise method and K-means++ are proposed to produce the initial population and capture higher quality seeds that can automatically determine the proper number of clusters, and also handle the different sizes and shapes of genes. A density-based method is presented to divide the number of niches, with its aim to maintain population diversity. Adaptive probabilities of crossover and mutation are also employed to prevent the convergence to a local optimum. Finally, the centers (the best chromosome) are obtained and then fed into the K-means as initial seeds to generate even higher quality clustering results by allowing the initial seeds to readjust as needed. Experimental results based on taxi GPS data sets demonstrate that NoiseClust has high performance and effectiveness, and easily mine the city\u2019s situations in four taxi GPS data sets.<\/jats:p>","DOI":"10.3390\/ijgi6120392","type":"journal-article","created":{"date-parts":[[2017,12,1]],"date-time":"2017-12-01T12:30:16Z","timestamp":1512131416000},"page":"392","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":27,"title":["An Automatic K-Means Clustering Algorithm of GPS Data Combining a Novel Niche Genetic Algorithm with Noise and Density"],"prefix":"10.3390","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9349-7487","authenticated-orcid":false,"given":"Xiangbing","family":"Zhou","sequence":"first","affiliation":[{"name":"Key Lab of Earth Exploration &amp; Information Techniques of Ministry Education, Chengdu University of Technology, Chengdu 610059, China"},{"name":"School of Information and Engineering, Sichuan Tourism University, Chengdu 610100, China"},{"name":"School of Mathematics and Computer Science, Aba Teachers University, Wenchuan 623002, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianggang","family":"Gu","sequence":"additional","affiliation":[{"name":"School of Physics and Electronic Information, China West Normal University, Nanchong 637000, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shaopeng","family":"Shen","sequence":"additional","affiliation":[{"name":"School of Mathematics and Computer Science, Aba Teachers University, Wenchuan 623002, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hongjiang","family":"Ma","sequence":"additional","affiliation":[{"name":"School of Computer Science, Chengdu University of Information Technology, Chengdu 610225, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fang","family":"Miao","sequence":"additional","affiliation":[{"name":"Key Lab of Earth Exploration &amp; Information Techniques of Ministry Education, Chengdu University of Technology, Chengdu 610059, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hua","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Information and Engineering, Sichuan Tourism University, Chengdu 610100, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Huaming","family":"Gong","sequence":"additional","affiliation":[{"name":"School of Mathematics and Computer Science, Aba Teachers University, Wenchuan 623002, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,12,1]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/s00778-011-0262-6","article-title":"Clustering and aggregating clues of trajectories for mining trajectory patterns and routes","volume":"24","author":"Hung","year":"2015","journal-title":"VLDB J."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/j.eswa.2015.08.048","article-title":"Time-evolving od matrix estimation using high-speed gps data streams","volume":"44","author":"Gama","year":"2016","journal-title":"Expert Syst. Appl."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"811","DOI":"10.1007\/s12650-016-0357-7","article-title":"Exploring OD patterns of interested region based on taxi trajectories","volume":"19","author":"Lu","year":"2016","journal-title":"J. Vis."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"2149","DOI":"10.1109\/TVCG.2013.226","article-title":"Visual exploration of big spatio-temporal urban data: A study of New York city taxi trips","volume":"19","author":"Ferreira","year":"2013","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.datak.2007.10.008","article-title":"A conceptual view on trajectories","volume":"65","author":"Spaccapietra","year":"2008","journal-title":"Data Knowl. Eng."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Luo, T., Zheng, X., Xu, G., Fu, K., and Ren, W. (2017). An improved DBSCAN algorithm to detect stops in individual trajectories. ISPRS Int. J. Geo-Inf., 6.","DOI":"10.3390\/ijgi6030063"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/s10707-006-0007-7","article-title":"Algorithms for nearest neighbor search on moving object trajectories","volume":"11","author":"Frentzos","year":"2007","journal-title":"Geoinformatica"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/s10844-006-9953-7","article-title":"Time-focused clustering of trajectories of moving objects","volume":"27","author":"Nanni","year":"2006","journal-title":"J. Intell. Inf. Syst."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1016\/j.ins.2015.08.054","article-title":"Decoclu: Density consensus clustering approach for public transport data","volume":"328","author":"Fiori","year":"2016","journal-title":"Inf. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1142","DOI":"10.1016\/j.neucom.2015.08.071","article-title":"The discovery of personally semantic places based on trajectory data mining","volume":"173","author":"Lv","year":"2016","journal-title":"Neurocomputing"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Lee, J.-G., Han, J., and Whang, K.-Y. (2007, January 11\u201314). Trajectory clustering: A partition-and-group framework. Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data, Beijing, China.","DOI":"10.1145\/1247480.1247546"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/s00382-007-0235-z","article-title":"Probabilistic clustering of extratropical cyclones using regression mixture models","volume":"29","author":"Gaffney","year":"2007","journal-title":"Clim. Dyn."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1109\/TNN.2005.845141","article-title":"Survey of clustering algorithms","volume":"16","author":"Xu","year":"2005","journal-title":"IEEE. Trans. Neural Netw."},{"key":"ref_14","unstructured":"Han, J., Pei, J., and Kamber, M. (2011). Data Mining: Concepts and Techniques, Elsevier."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1016\/j.patrec.2009.09.011","article-title":"Data clustering: 50 years beyond K-means","volume":"31","author":"Jain","year":"2010","journal-title":"Pattern Recognit. Lett."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/j.knosys.2014.08.011","article-title":"A hybrid clustering technique combining a novel genetic algorithm with K-means","volume":"71","author":"Rahman","year":"2014","journal-title":"Knowl. Based Syst."},{"key":"ref_17","first-page":"81","article-title":"Means-type algorithm: A generalized convergence theorem and characterization of local optimality","volume":"1","author":"Sclim","year":"1984","journal-title":"IEEE. Trans. Pattern Anal. Mach. Intell"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/s10462-011-9210-5","article-title":"A survey: Hybrid evolutionary algorithms for cluster analysis","volume":"36","author":"Ramakrishnan","year":"2011","journal-title":"Artif. Intell. Rev."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1016\/j.eswa.2012.07.021","article-title":"A comparative study of efficient initialization methods for the K-means clustering algorithm","volume":"40","author":"Celebi","year":"2013","journal-title":"Expert Syst. Appl."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1210","DOI":"10.1016\/j.patcog.2008.11.006","article-title":"A genetic algorithm with gene rearrangement for K-means clustering","volume":"42","author":"Chang","year":"2009","journal-title":"Pattern Recognit."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"9695","DOI":"10.1016\/j.eswa.2012.02.149","article-title":"A new grouping genetic algorithm for clustering problems","volume":"39","year":"2012","journal-title":"Expert Syst. Appl."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1267","DOI":"10.1016\/j.amc.2011.06.007","article-title":"Automatic clustering using genetic algorithms","volume":"218","author":"Liu","year":"2011","journal-title":"Appl. Math. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1109\/TSMCC.2008.2007252","article-title":"A survey of evolutionary algorithms for clustering","volume":"39","author":"Hruschka","year":"2009","journal-title":"IEEE. Trans. Syst. Man Cybern. Part C"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"McCallum, A., Nigam, K., and Ungar, L.H. (2000, January 20\u201323). Efficient clustering of high-dimensional data sets with application to reference matching. Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Boston, MA, USA.","DOI":"10.1145\/347090.347123"},{"key":"ref_25","unstructured":"Arthur, D., and Vassilvitskii, S. (2007, January 7\u20139). K-means++: The advantages of careful seeding. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.swevo.2016.06.004","article-title":"A comprehensive survey of traditional, merge-split and evolutionary approaches proposed for determination of cluster number","volume":"32","author":"Hancer","year":"2017","journal-title":"Swarm Evolut. Comput."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1109\/4235.735432","article-title":"Fitness sharing and niching methods revisited","volume":"2","author":"Sareni","year":"1998","journal-title":"IEEE. Trans. Evolut. Comput."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"2744","DOI":"10.1016\/j.patcog.2009.04.018","article-title":"Towards improving fuzzy clustering using support vector machine: Application to gene expression data","volume":"42","author":"Mukhopadhyay","year":"2009","journal-title":"Pattern Recognit."},{"key":"ref_29","unstructured":"Goldberg, D.E., and Richardson, J. (1987, January 28\u201331). Genetic algorithms with sharing for multimodal function optimization. Proceedings of the Second International Conference on Genetic Algorithms: Genetic Algorithms and Their Applications, Cambridge, MA, USA."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1109\/3477.764879","article-title":"Genetic K-means algorithm","volume":"29","author":"Krishna","year":"1999","journal-title":"IEEE. Trans. Syst. Man Cybern. Part B"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1016\/j.patcog.2003.06.005","article-title":"Validity index for crisp and fuzzy clusters","volume":"37","author":"Pakhira","year":"2004","journal-title":"Pattern Recognit."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1109\/TPAMI.1979.4766909","article-title":"A cluster separation measure","volume":"2","author":"Davies","year":"1979","journal-title":"IEEE. Trans. Pattern Anal."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1016\/j.physa.2015.06.032","article-title":"Uncovering urban human mobility from large scale taxi GPS data","volume":"438","author":"Tang","year":"2015","journal-title":"Phys. A Stat. Mech. Appl."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1016\/j.neucom.2008.11.032","article-title":"Extracting road information from recorded GPS data using snap-drift neural network","volume":"73","author":"Ekpenyong","year":"2009","journal-title":"Neurocomputing"},{"key":"ref_35","unstructured":"(2017, November 26). Taxi-GPS Data Sets. Available online: https:\/\/github.com\/bigdata002\/Location-data-sets."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/S0377-2217(00)00305-2","article-title":"The noising methods: A generalization of some metaheuristics","volume":"135","author":"Charon","year":"2001","journal-title":"Eur. J. Oper. Res."},{"key":"ref_37","unstructured":"Rahman, A., and Islam, Z. (2011, January 1\u20132). Seed-detective: A novel clustering technique using high quality seed for K-means on categorical and numerical attributes. Proceedings of the Ninth Australasian Data Mining Conference, Ballarat, Australia."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0167-6377(93)90023-A","article-title":"The noising method: A new method for combinatorial optimization","volume":"14","author":"Charon","year":"1993","journal-title":"Oper. Res. Lett."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0305-0548(99)00045-3","article-title":"A hybrid heuristic to solve a task allocation problem","volume":"27","author":"Chen","year":"2000","journal-title":"Comput. Oper. Res."},{"key":"ref_40","unstructured":"Hudry, O. (2006). Noising Methods for a Clique Partitioning Problem, Elsevier."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/s00500-008-0386-9","article-title":"A niching genetic K-means algorithm and its applications to gene expression data","volume":"14","author":"Sheng","year":"2010","journal-title":"Soft Comput."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/S0020-0255(02)00208-6","article-title":"An evolutionary technique based on K-means algorithm for optimal clustering in RN","volume":"146","author":"Bandyopadhyay","year":"2002","journal-title":"Inf. Sci."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Palma, A.T., Bogorny, V., Kuijpers, B., and Alvares, L.O. (2008, January 16\u201320). A clustering-based approach for discovering interesting places in trajectories. Proceedings of the ACM Symposium on Applied Computing, Fortaleza, Brazil.","DOI":"10.1145\/1363686.1363886"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/S0142-0615(02)00027-3","article-title":"A niched pareto genetic algorithm for multiobjective environmental\/economic dispatch","volume":"25","author":"Abido","year":"2003","journal-title":"Int. J. Electr. Rower Energy Syst."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"1346","DOI":"10.1016\/j.patcog.2009.10.020","article-title":"A robust dynamic niching genetic algorithm with niche migration for automatic clustering problem","volume":"43","author":"Chang","year":"2010","journal-title":"Pattern Recognit."},{"key":"ref_46","unstructured":"Deb, K., and Goldberg, D.E. (1989, January 6\u20139). An investigation of niche and species formation in genetic function optimization. Proceedings of the 3rd International Conference on Genetic Algorithms, Washington DC, USA."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.neucom.2011.11.001","article-title":"A two-stage genetic algorithm for automatic clustering","volume":"81","author":"He","year":"2012","journal-title":"Neurocomputing"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF01897163","article-title":"A study of standardization of variables in cluster analysis","volume":"5","author":"Milligan","year":"1988","journal-title":"J. Classif."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1023\/A:1012801612483","article-title":"On clustering validation techniques","volume":"17","author":"Halkidi","year":"2001","journal-title":"J. Intell. Inf. Syst."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0377-0427(87)90125-7","article-title":"Silhouettes: A graphical aid to the interpretation and validation of cluster analysis","volume":"20","author":"Rousseeuw","year":"1987","journal-title":"J. Comput. Appl. Math."},{"key":"ref_51","unstructured":"Duda, R.O., Hart, P.E., and Stork, D.G. (2012). Pattern Classification, John Wiley & Sons."},{"key":"ref_52","unstructured":"Hollander, M., Wolfe, D.A., and Chicken, E. (2013). Nonparametric Statistical Methods, John Wiley & Sons."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"908","DOI":"10.1198\/016214504000001583","article-title":"Rank-sum tests for clustered data","volume":"100","author":"Datta","year":"2005","journal-title":"J. Am. Stat. Assoc."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/6\/12\/392\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:52:19Z","timestamp":1760208739000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/6\/12\/392"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,1]]},"references-count":53,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2017,12]]}},"alternative-id":["ijgi6120392"],"URL":"https:\/\/doi.org\/10.3390\/ijgi6120392","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,1]]}}}