nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Modification of the k-MXT Algorithm and Its Application to the Geotagged Data Clustering

verfasst von : Anastasia Stepanova, Sergei V. Mironov, Sergei Sidorov, Alexey Faizliev

Erschienen in: Machine Learning, Optimization, and Data Science

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The paper considers the problem of detection of the most attractive city sights using datasets with geotagged photographs. We form a graph on the basis of the geotagged spot coordinates and rewrite the problem as the problem of graph clustering. In this paper, we propose a modification of the k-MXT algorithm, which we called the k-MXT-W algorithm and which uses window functions. We compare the proposed algorithm with k-Means and k-MXT algorithms on simulated data using ARI, one of the most common metrics for assessing clustering quality. In this paper we also use the k-MXT-W algorithm to find the most popular places in St. Petersburg (Russia) and we compare the performance of the proposed algorithm with the k-MXT algorithm on real-world data using the modularity metric that does not require knowledge of true clustering.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel A Structural Theorem for Center-Based Clustering in High-Dimensional Euclidean Space

Nächstes Kapitel CoPASample: A Heuristics Based Covariance Preserving Data Augmentation

Béjar, J.: K-means vs mini batch k-means: a comparison. Technical report, Universitat Politècnica de Catalunya (2013)

Bottou, L., Bengio, Y.: Convergence properties of the k-means algorithms. In: Advances in Neural Information Processing System (NIPS 1994), pp. 585–592 (1994)

Brandes, U., et al.: On modularity clustering. IEEE Trans. Knowl. Data Eng. 20(2), 172–188 (2008). https://doi.org/10.1109/TKDE.2007.190689CrossRef

Clauset, A., Newman, M.E.J., Moore, C.: Finding community structure in very large networks. Phys. Rev. E 70(6), 066111 (2004). https://doi.org/10.1103/PhysRevE.70.066111CrossRef

Cooper, C., Vu, N.: An experimental study of the k-MXT algorithm with applications to clustering geo-tagged data. In: Bonato, A., Prałat, P., Raigorodskii, A. (eds.) WAW 2018. LNCS, vol. 10836, pp. 145–169. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-92871-5_10CrossRef

Emmons, S., Kobourov, S., Gallant, M., Börner, K.: Analysis of network clustering algorithms and cluster quality metrics at scale. Public Libr. Sci. 11(7), e0159161 (2016). https://doi.org/10.1371/journal.pone.0159161CrossRef

Ester, M., Kriegel, H.P., Sander, J., Xu, X.: A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise. In: Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, KDD 1996, pp. 226–231. AAAI Press (1996)

Hubert, L., Arabie, P.: Comparing partitions. J. Classif. 2(1), 193–218 (1985). https://doi.org/10.1007/BF01908075CrossRefMATH

Lloyd, S.: Least squares quantization in PCM. IEEE Trans. Inf. Theory 28(2), 129–137 (1982). https://doi.org/10.1109/tit.1982.1056489MathSciNetCrossRefMATH

10.

Macqueen, J.: Some methods for classification and analysis of multivariate observations. In: 5th Berkeley Symposium on Mathematical Statistics and Probability, pp. 281–297 (1967)

11.

Miasnikof, P., Shestopaloff, A.Y., Bonner, A.J., Lawryshyn, Y.: A statistical performance analysis of graph clustering algorithms. In: Bonato, A., Prałat, P., Raigorodskii, A. (eds.) WAW 2018. LNCS, vol. 10836, pp. 170–184. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-92871-5_11CrossRef

12.

Newman, M.E.J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69(2), 026113 (2004). https://doi.org/10.1103/PhysRevE.69.026113CrossRef

13.

Oku, K., Hattori, F., Kawagoe, K.: Tweet-mapping method for tourist spots based on now-tweets and spot-photos. Procedia Comput. Sci. 60, 1318–1327 (2015). https://doi.org/10.1016/j.procs.2015.08.202CrossRef

14.

Prokhorenkova, L.O., Prałat, P., Raigorodskii, A.: Modularity in several random graph models. Electron. Notes Discrete Math. 61, 947–953 (2017). https://doi.org/10.1016/j.endm.2017.07.058CrossRefMATH

15.

Prokhorenkova, L.O., Raigorodskii, A., Pralat, P.: Modularity of complex networks models. Internet Math. (2017). https://doi.org/10.24166/im.12.2017

16.

Rand, W.M.: Objective criteria for the evaluation of clustering methods. J. Am. Stat. Assoc. 66(336), 846–850 (1971). https://doi.org/10.2307/2284239CrossRef

17.

Rodriguez, M.Z., et al.: Clustering algorithms: a comparative approach. PLoS ONE 14(1), e0210236 (2019). https://doi.org/10.1371/journal.pone.0210236CrossRef

18.

Rousseeuw, P.J.: Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. J. Comput. Appl. Math. 20, 53–65 (1987). https://doi.org/10.1016/0377-0427(87)90125-7CrossRefMATH

19.

Sculley, D.: Web-scale k-means clustering. In: Proceedings of the 19th International Conference on World Wide Web - WWW 2010, pp. 1177–1178. ACM Press (2010). https://doi.org/10.1145/1772690.1772862

20.

Spielman, D.A., Teng, S.H.: A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM J. Comput. 42, 1–26 (2013). https://doi.org/10.1137/080744888MathSciNetCrossRefMATH

21.

Steinhaus, H.: Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci. 4(12), 801–804 (1956)MathSciNetMATH

22.

Stepanova, A., Mironov, S., Korobov, E., Sidorov, S.: The clusterization of geo-tagged data for finding city sights with use of a modification of k-MXT algorithm (2019). https://doi.org/10.2991/cmdm-18.2019.4

23.

Vinh, N.X., Epps, J., Bailey, J.: Information theoretic measures for clusterings comparison: variants, properties, normalization and correction for chance. J. Mach. Learn. Res. 11, 2837–2854 (2010)MathSciNetMATH

24.

Zhang, T., Ramakrishnan, R., Livny, M.: BIRCH: an efficient data clustering method for very large databases. SIGMOD Rec. 25(2), 103–114 (1996). https://doi.org/10.1145/235968.233324CrossRef

Titel: Modification of the k-MXT Algorithm and Its Application to the Geotagged Data Clustering
verfasst von: Anastasia Stepanova
Sergei V. Mironov
Sergei Sidorov
Alexey Faizliev
Verlag: Springer International Publishing
Buch: Machine Learning, Optimization, and Data Science
Print ISBN: 978-3-030-37598-0

Electronic ISBN: 978-3-030-37599-7

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-37599-7_25

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"