Top

Journal of Intelligent Information Systems

Published in:

01-06-2014

Mining regional co-location patterns with kNNG

Authors: Feng Qian, Kevin Chiew, Qinming He, Hao Huang

Published in: Journal of Intelligent Information Systems | Issue 3/2014

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Spatial co-location pattern mining discovers the subsets of features of which the events are frequently located together in geographic space. The current research on this topic adopts a distance threshold that has limitations in spatial data sets with various magnitudes of neighborhood distances, especially for mining of regional co-location patterns. In this paper, we propose a hierarchical co-location mining framework accounting for both variety of neighborhood distances and spatial heterogeneity. By adopting k-nearest neighbor graph (kNNG) instead of distance threshold, we propose “distance variation coefficient” as a new measure to drive the mining operations and determine an individual neighborhood relationship graph for each region. The proposed mining algorithm outputs a set of regions with each of them an individual set of regional co-location patterns. The experimental results on both synthetic and real world data sets show that our framework is effective to discover these regional co-location patterns.

previous article Producing efficient retrievability ranks of documents using normalized retrievability scoring function

next article A new particle swarm feature selection method for classification

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

As a direction of our future study we may consider the continuous type of data sets.

Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules. In Proceedings of the 20th international conference on very large data bases, 12–15 Sept. (pp. 487–499). Santiago de Chile, Chile.

Arge, L., Procopiuc, O., Ramaswamy, S., Suel, T., Vitter, J.S. (1998). Scalable sweeping-based spatial join. In Proceedings of the 24th international conference on very large data bases, 24–27 Aug. (pp. 570–581). New York, USA.

Banerjee, A., & Ghosh, J. (2006). Scalable clustering algorithms with balancing constraints. Data Mining and Knowledge Discovery, 13(3), 365–395.CrossRefMathSciNet

Brito, M.R., Chavez, E.L., Quiroz, A.J., Yukich, J.E. (1997). Connectivity of the mutual k-nearest-neighbor graph in clustering and outlier detection. Statistics and Probability Letters, 35(1), 33–42.CrossRefMATHMathSciNet

Celik, M., Kang, J.M., Shekhar, S. (2007). Zonal co-location pattern discovery with dynamic parameters. In Proceedings of IEEE international conference on data mining, 28–31 Oct. (pp. 433–438). Omaha, USA.

Celik, M., Shekhar, S., Rogers, J.P., Shine, J.A., Yoo, J.S. (2006). Mixed-drove spatio-temporal co-occurrence pattern mining: A summary of results. In Proceedings of the 6th international conference on data mining, 18–22 Dec. (pp. 119–128). Hong Kong, China.

Digital Chart of the World. (2013). http://www.princeton.edu/~geolib/gis/dcw.html. Accessed 05 Oct 2013.

Ding, C., & He, X. (2004). K-nearest-neighbor consistency in data clustering: Incorporating local information into global optimization. In Proceedings of the ACM symposium on applied computing, 14–17 March (pp. 584–589). Nicosia, Cyprus.

Eick, C.F., Parmar, R., Ding, W., Stepinski, T.F., Nicot, J.P. (2008). Finding regional co-location patterns for sets of continuous variables in spatial datasets. In Proceedings of the 16th ACM SIGSPATIAL international conference on advances in geographic information systems, 5–7 Nov. (pp. 1–110). Irvine, USA.

Friedman, J.H., Bentley, J.L., Finkel, R.A. (1977). An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software, 3, 290–226.

Ge, R., Ester, M., Jin, W., Davidson, I. (2007). Constraint-driven clustering. In Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining, 12–15 Aug. (pp. 320–329). San Jose, USA.

Han, E.H., Karypis, G., Kumar, V. (1999). Chameleon: hierarchical clustering using dynamic modeling. IEEE Computer, 32(8), 68–75.CrossRef

Huang, Y., Pei, J., Xiong, H. (2006). Mining co-location patterns with rare events from spatial data sets. GeoInformatica, 10(3), 239–260.CrossRef

Huang, Y., Shekhar, S., Xiong, H. (2004). Discovering colocation patterns from spatial datasets: a general approach. IEEE Transactions on Knowledge and Data Engineering, 16(12), 1472–1485.CrossRef

Huang, Y., Zhang, P., Zhang, C. (2008). On the relationships between clustering and spatial co-location pattern mining. International Journal on Artificial Intelligence Tools, 17(1), 55–70.CrossRef

Jin, R., Goswami, A., Agrawal, G. (2006). Fast and exact out-of-core and distributed k-means clustering. Knowledge and Information Systems, 10(1), 17–40.CrossRef

Lin, Z., & Lim, S.J. (2009). Optimal candidate generation in spatial co-location mining. In Proceedings of the 2009 ACM symposium on applied computing, 9–12 March (pp. 1441–1445). Hawaii, USA.

Miller, H.J., & Han, J. (2009). Geographic data mining and knowledge discovery. New York: CRC Press.

Müller, E., Günnemann, S., Färber, I., Seidl, T. (2012). Discovering multiple clustering solutions: Grouping objects in different views of the data. In Proceeds of the 28th international conference on data engineering, 1–5 Apr. (pp. 1207–1210). Washington DC, USA.

Munro, R., Chawla, S., Sun, P. (2003). Complex spatial relationships. In Proceedings of the 3rd IEEE international conference on data mining, 19–22 Dec. (pp. 227–234). Melbourne, USA.

Park, K., Shen, C., Hao, Z., Kim, J. (2011). Efficiently learning a distance metric for large margin nearest neighbor classification. In Proceedings of the 25th AAAI conference on artificial intelligence, 7–11 Aug. (pp. 453–458). San Francisco, USA.

Qian, F., He, Q., Chiew, K., He, J. (2012). Spatial co-location pattern discovery without thresholds. Knowledge and Information Systems, 33(2), 419–445.CrossRef

Qian, F., He, Q., He, J. (2009a). Mining spread patterns of spatio-temporal co-occurrences over zones. In Proceedings of the international conference on computational science and its applications, 29 June–2 July (pp. 686–701). Seoul, Korea.

Qian, F., Yin, L., He, Q., He, J. (2009b). Mining spatio-temporal co-location patterns with weighted sliding window. In Proceedings of IEEE international conference on intelligent computing and intelligent systems, 20–22 Nov. (pp. 181–185). Shanghai, China.

Samet, H. (1990). The design and analysis of spatial data structures. Boston: Addison Wesley.

Shaw, B., Huang, B.C., Jebara, T. (2011). Learning a distance metric from a network. In Proceeds of the 25th conference on neural information processing systems, 12–14 Dec. (pp. 1899–1907). Granada, Spain.

Shekhar, S., & Huang, Y. (2001). Discovering spatial co-location patterns: A summary of results. In Proceedings of the 7th international symposium on spatial and temporal databases, 12–15 July (pp. 236–256). Redondo Beach, USA.

Sheng, C., Hsu, W., Lee, M.L., Tung, A.K.H. (2008). Discovering spatial interaction patterns. In Proceedings of the 13th international conference on database systems for advanced applications, 19–21 March (pp. 95–109). New Delhi, India.

Slonim, N., Atwal, G.S., Tkačik, G., Bialek, W. (2005). Information-based clustering. Proceedings of the National Academy of Sciences of the United States of America, 102(51), 18297–18302.CrossRefMATHMathSciNet

Wang, J. (2006). Spatial analysis. Beijing: Science Press.

Wang, L., Zhou, L., Lu, J., Yip, J. (2009). An order-clique-based approach for mining maximal co-locations. Information Sciences, 179(19), 3370–3382.CrossRefMATH

Wu, X., Kumar, V., Quinlan, J.R., Ghosh, J., Yang, Q., Motoda, H., McLachlan, G., Ng, A., Liu, B., Yu, P., Zhou, Z., Steinbach, M., Hand, D., Steinberg, D. (2008). Top 10 algorithms in data mining. Knowledge and Information Systems, 14(1), 1–37.CrossRef

Xiao, X., Xie, X., Luo, Q., Ma, W.Y. (2008). Density based co-location pattern discovery. In Proceedings of the 16th ACM SIGSPATIAL international conference on advances in geographic information systems, 5–7 Nov. (pp. 1–10). Irvine, USA.

Xiong, H., Shekhar, S., Huang, Y., Kumar, V., Ma, X., Yoo, J.S. (2004). A framework for discovering co-location patterns in data sets with extended spatial objects. In Proceedings of the fourth SIAM international conference on data mining, 22–24 Apr. (vol. 89, p. 78). Lake Buena, USA.

Yoo, J.S., & Shekhar, S. (2006). A joinless approach for mining spatial colocation patterns. IEEE Transactions on Knowledge and Data Engineering, 18(10), 1323–1337.CrossRef

Yoo, J.S., Shekhar, S., Kim, S., Celik, M. (2006). Discovery of co-evolving spatial event sets. In Proceedings of the 6th SIAM international conference on data mining, 20–22 Nov. (pp. 306–315). Bethesda, USA.

Yoo, J.S., & Bow, M. (2012). Mining spatial colocation patterns: a different framework. Data Mining and Knowledge Discovery, 24(1), 1384–5810.CrossRefMathSciNet

Zhang, X., Mamoulis, N., Cheung, D.W., Shou, Y. (2004). Fast mining of spatial collocations. In Proceedings of the tenth ACM SIGKDD international conference on knowledge discovery and data mining, 22–25 Aug. (pp. 384–393). Seattle, USA.

Title: Mining regional co-location patterns with kNNG
Authors: Feng Qian
Kevin Chiew
Qinming He
Hao Huang
Publication date: 01-06-2014
Publisher: Springer US
Published in: Journal of Intelligent Information Systems / Issue 3/2014
Print ISSN: 0925-9902
Electronic ISSN: 1573-7675
DOI: https://doi.org/10.1007/s10844-013-0280-5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2014

Token list based information search in a multi-dimensional massive database

Dream sentiment analysis using second order soft co-occurrences (SOSCO) and time course representations

TS-stream: clustering time series on data streams

Producing efficient retrievability ranks of documents using normalized retrievability scoring function

In-memory, distributed content-based recommender system

SMOL: a systemic methodology for ontology learning from heterogeneous sources

Premium Partner