Mining frequent geographic patterns with knowledge constraints

ABSTRACT

The large amount of patterns generated by frequent pattern mining algorithms has been extensively addressed in the last few years. In geographic pattern mining, besides the large amount of patterns, many are well known geographic domain associations. Existing algorithms do not warrant the elimination of all well known geographic dependences since no prior knowledge is used for this purpose. This paper presents a two step method for mining frequent geographic patterns without associations that are previously known as non-interesting. In the first step the input space is reduced as much as possible. This is as far as we know still the most efficient method to reduce frequent patterns. In the second step, all remaining geographic dependences that can only be eliminated during the frequent set generation are removed in an efficient way. Experiments show an elimination of more than 50% of the total number of frequent patterns, and which are exactly the less interesting.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 2: Appice, A., Ceci, M., Lanza, A., Francesca, L., and Malerba, D. Discovery of Spatial Association Rules in Geo-Referenced Census Data: A Relational Mining Approach. Intelligent Data Analysis 7(6), (2003), 542--566.
• 3: Bogorny, V., Engel, P., and Alvares, L.O. Towards the reduction of spatial joins for knowledge discovery in geographic databases using geo-ontologies and spatial integrity constraints. In ECML/PKDD Second Workshop on Knowledge Discovery and Ontologies (KDO'05) (October). Porto, Portugal, 2005, 51--58.
• 4: Bogorny, V., Engel, P., and Alvares, L.O. GeoARM: an interoperable framework to improve geographic data preprocessing and spatial association rule mining. In Proceedings of the 18th International Conference on Software Engineering and Knowledge Engineering (SEKE'06) (July). San Francisco, 2006, 79--84.
• 5: Bogorny, V., Camargo, S., Engel, P., and Alvares, L.O. Towards elimination of well known geographic domain patterns in spatial association rule mining. In Proceedings Of The 3th IEEE International Conference On Intelligent Systems (IEEE IS'06) (September 4-6). London, 2006 (To appear).
• 6: Francesco Bonchi , Fosca Giannotti , Alessio Mazzanti , Dino Pedreschi, ExAMiner: Optimized Level-wise Frequent Pattern Mining with Monotone Constraints, Proceedings of the Third IEEE International Conference on Data Mining, p.11, November 19-22, 2003
• 7: Elliot J. Chikofsky , James H. Cross II, Reverse Engineering and Design Recovery: A Taxonomy, IEEE Software, v.7 n.1, p.13-17, January 1990 [doi>10.1109/52.43044]
• 8: Eliseo Clementini , Paolino Di Felice , Krzysztof Koperski, Mining multiple-level spatial association rules for objects with a broad boundary, Data & Knowledge Engineering, v.34 n.3, p.251-270, Sept. 2000 [doi>10.1016/S0169-023X(00)00017-3]
• 9: Martin Ester , Alexander Frommelt , Hans-Peter Kriegel , Jöorg Sander, Spatial Data Mining: Database Primitives, Algorithms and Efficient DBMS Support, Data Mining and Knowledge Discovery, v.4 n.2-3, p.193-216, July 2000 [doi>10.1023/A:1009843930701]
• 10: Fayyad, U., Piatetsky-Shapiro, G., and Smyth, P. From data mining to discovery knowledge in databases. AI Magazine, 3(17), (1996) 37--54.
• 11: Jiawei Han , Jian Pei , Yiwen Yin , Runying Mao, Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach, Data Mining and Knowledge Discovery, v.8 n.1, p.53-87, January 2004 [doi>10.1023/B:DAMI.0000005258.31418.83]
• 12: Jiawei Han , Yongjian Fu, Discovery of Multiple-Level Association Rules from Large Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.420-431, September 11-15, 1995
• 13: Krzysztof Koperski , Jiawei Han, Discovery of Spatial Association Rules in Geographic Information Databases, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.47-66, August 06-09, 1995
• 14: Bing Liu , Wynne Hsu , Yiming Ma, Pruning and summarizing the discovered associations, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.125-134, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312216]
• 15: MCKearney, S., and Roberts, H. Reverse engineering databases for knowledge discovery. In Proceedings of the Second ACM-SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'96). AAAI Press. Oregon, 1996, 375--378.
• 16: Open GIS Consortium (1999). OpenGIS simple features specification for SQL. In URL: http://www.opengeospatial.org/docs/99-054.pdf
• 17: Nicolas Pasquier , Yves Bastide , Rafik Taouil , Lotfi Lakhal, Discovering Frequent Closed Itemsets for Association Rules, Proceeding of the 7th International Conference on Database Theory, p.398-416, January 10-12, 1999
• 18: Sylvie Servigne , Thierry Ubeda , Alain Puricelli , Robert Laurini, A Methodology for Spatial Consistency Improvement of Geographic Databases, Geoinformatica, v.4 n.1, p.7-34, March 2000 [doi>10.1023/A:1009824308542]
• 19: Shekhar, S., and Chawla, S. Spatial Databases: A Tour. Prentice Hall, Upper Saddle River, Nj, 2003.
• 20: Peretz Shoval , Nili Shreiber, Database reverse engineering: from the relational to the binary relationship model, Data & Knowledge Engineering, v.10 n.3, p.293-315, July 1993 [doi>10.1016/0169-023X(93)90033-L]
• 21: Ramakrishnan Srikant , Rakesh Agrawal, Mining Generalized Association Rules, Proceedings of the 21th International Conference on Very Large Data Bases, p.407-419, September 11-15, 1995
• 22: Jin Soung Yoo , Shashi Shekhar , Mete Celik, A Join-Less Approach for Co-Location Pattern Mining: A Summary of Results, Proceedings of the Fifth IEEE International Conference on Data Mining, p.813-816, November 27-30, 2005 [doi>10.1109/ICDM.2005.8]
• 23: Jin Soung Yoo , Shashi Shekhar , John Smith , Julius P. Kumquat, A partial join approach for mining co-location patterns, Proceedings of the 12th annual ACM international workshop on Geographic information systems, November 12-13, 2004, Washington DC, USA [doi>10.1145/1032222.1032258]
• 24: Mohammed J. Zaki, Generating non-redundant association rules, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.34-43, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347101]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms, Design

Keywords:
frequent pattern mining, geographic databases, semantic knowledge constraints, spatial association rules