Higher order mining

ABSTRACT

The value of knowledge obtainable by analysing large quantities of data is widely acknowledged. However, so-called primary or raw data may not always be available for knowledge discovery for several reasons. First, cooperating institutions that are interested in sharing knowledge may not be willing (or allowed) to disclose their primary data. Second, data in the form of streams are only temporarily available for processing. If stored at all, stream data are maintained in the form of synopses or derived, abstract representations of the original data. Finally, even for non-stream data, there are limits on the computation speed to be achieved -- such limits are set by hardware and firmware technologies. This problem can only be partially solved through parallelization and increased processing power. Ultimately, in many cases data must be summarized to be processed efficiently.

In the light of these observations, we anticipate the need for defining and practising data mining without the luxury of primary data. To that end, we formally introduce the paradigm of Higher Order Mining as a form of data mining that is applied over non-primary, derived data or patterns. Although Higher Order Mining is a new paradigm, there are already research advances on knowledge discovery methods from patterns rather than data. We discuss them and organize them under the light of the new paradigm. We show that the HOM paradigm reveals further potential for knowledge discovery, including the delivery of rules and patterns with semantics that are closer to human intuition and are thus more appropriate for human inspection.

REFERENCES

• 1: Charu C. Aggarwal, On Change Diagnosis in Evolving Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.17 n.5, p.587-600, May 2005 [doi>10.1109/TKDE.2005.78]
• 2: C. C. Aggarwal and P. S. Yu. A Framework for Clustering Massive Text and Categorical Data Streams. In Proceedings of the SIAM conference on Data Mining 2006, April 2006.
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 4: Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States
• 5: Shipra Agrawal , Jayant R. Haritsa, A Framework for High-Accuracy Privacy-Preserving Mining, Proceedings of the 21st International Conference on Data Engineering, p.193-204, April 05-08, 2005 [doi>10.1109/ICDE.2005.8]
• 6: Maria-Luiza Antonie , Osmar R. Zaïane, An associative classifier based on positive and negative rules, Proceedings of the 9th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13, 2004, Paris, France [doi>10.1145/1008694.1008705]
• 7: W.-H. Au and K. C. Chan. Mining changes in association rules: a fuzzy approach. Fuzzy Sets and Systems, 149(1):87--104, 2005.
• 8: S. Baron, M. Spiliopoulou, and O. Günther. Efficient monitoring of patterns in data mining environments. In Proc. of 7th East-European Conf. on Advances in Databases and Inf. Sys. (ADBIS'03), LNCS, pages 253--265. Springer, Sept. 2003.
• 9: Ilaria Bartolini , Paolo Ciaccia , Irene Ntoutsi , Marco Patella , Yannis Theodoridis, A unified and flexible framework for comparing simple and complex patterns, Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, p.496-499, September 20-24, 2004, Pisa, Italy
• 10: Francesco Bonchi , Fosca Giannotti , Claudio Lucchese , Salvatore Orlando , Raffaele Perego , Roberto Trasarti, ConQueSt: a Constraint-based Querying System for Exploratory Pattern Discovery, Proceedings of the 22nd International Conference on Data Engineering, p.159, April 03-07, 2006 [doi>10.1109/ICDE.2006.42]
• 11: Paul S. Bradley , Usama M. Fayyad, Refining Initial Points for K-Means Clustering, Proceedings of the Fifteenth International Conference on Machine Learning, p.91-99, July 24-27, 1998
• 12: T. Calders, B. Goethals, and A. Prado. Integrating pattern mining in relational databases. In International Conference Principles of Data Mining and Knowledge Discovery, PKDD'06, pages 454--461. Springer, 2006.
• 13: Michelangelo Ceci , Annalisa Appice , Donato Malerba, Spatial associative classification at different levels of granularity: a probabilistic approach, Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, p.99-111, September 20-24, 2004, Pisa, Italy
• 14: Aaron Ceglar , John F. Roddick, Association mining, ACM Computing Surveys (CSUR), v.38 n.2, p.5-es, 2006 [doi>10.1145/1132956.1132958]
• 15: Soumen Chakrabarti , Sunita Sarawagi , Byron Dom, Mining Surprising Patterns Using Temporal Description Length, Proceedings of the 24rd International Conference on Very Large Data Bases, p.606-617, August 24-27, 1998
• 16: David Wai-Lok Cheung , Jiawei Han , Vincent Ng , C. Y. Wong, Maintenance of Discovered Association Rules in Large Databases: An Incremental Updating Technique, Proceedings of the Twelfth International Conference on Data Engineering, p.106-114, February 26-March 01, 1996
• 17: E. Christodoulou, T. Dalamagas, and T. Sellis. Navimoz: Mining navigational patterns in portal catalogs. In 2nd International Workshop on Pattern Representation and Management (PaRMa'06), Munich, Germany, 2006.
• 18: Proceedings of the IEEE international conference on Privacy, security and data mining, December 2002
• 19: James O. Coplien , Douglas C. Schmidt, Pattern languages of program design, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995
• 20: G. Das, K.-I. Lin, H. Mannila, G. Renganathan, and P. Smyth. Rule discovery from time series. In 4th International Conference on Knowledge Discovery and Data Mining (KDD-98). AAAI Press, 1998.
• 21: V. Estivill-Castro, L. Brankovic, and D. Dowe. Privacy in data mining. Privacy - Law and Policy Reporter, 6 (3):33--35, 1999.
• 22: Wei Fan, Systematic data selection to mine concept-drifting data streams, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014069]
• 23: Douglas H. Fisher, Knowledge Acquisition Via Incremental Conceptual Clustering, Machine Learning, v.2 n.2, p.139-172, September 1987 [doi>10.1023/A:1022852608280]
• 24: Alex A. Freitas, Understanding the crucial differences between classification and discovery of association rules: a position paper, ACM SIGKDD Explorations Newsletter, v.2 n.1, p.65-69, June, 2000 [doi>10.1145/360402.360423]
• 25: A. Fu, M. H. Wong, S. C. Sze, W. C. Wong, W. L. Wong, and W. K. Yu. Finding fuzzy sets for the mining of fuzzy association rules for numerical attributes. In 1st International Symposium on Intelligent Data Engineering and Learning (IDEAL98), pages 263--268, Shatin, Hong Kong, China, 1998.
• 26: Mohamed Medhat Gaber , Arkady Zaslavsky , Shonali Krishnaswamy, Mining data streams: a review, ACM SIGMOD Record, v.34 n.2, June 2005 [doi>10.1145/1083784.1083789]
• 27: Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, CACTUS—clustering categorical data using summaries, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.73-83, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312201]
• 28: Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, A framework for measuring changes in data characteristics, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.126-137, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303989]
• 29: Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, DEMON: Mining and Monitoring Evolving Data, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.50-63, January 2001 [doi>10.1109/69.908980]
• 30: J. Gehrke, editor. Special Issue on Privacy and Security, volume 4 of SigKDD Explorations. ACM, 2002.
• 31: Liqiang Geng , Howard J. Hamilton, Interestingness measures for data mining: A survey, ACM Computing Surveys (CSUR), v.38 n.3, p.9-es, 2006 [doi>10.1145/1132960.1132963]
• 32: Sudipto Guha , Adam Meyerson , Nina Mishra , Rajeev Motwani , Liadan O'Callaghan, Clustering Data Streams: Theory and Practice, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.515-528, March 2003 [doi>10.1109/TKDE.2003.1198387]
• 33: G. K. Gupta, A. Strehl, and J. Ghosh. Distance based clustering of association rules. In Intelligent Engineering Systems Through Artificial Neural Networks, ANNIE 1999, pages 759--764, St. Louis, Missouri, USA, 1999. ASME.
• 34: Attila Gyenesei, Fuzzy Partitioning of Quantitative Attribute Domains by a Cluster Goodness Index, Turku Centre for Computer Science, 2000
• 35: Sherri K. Harms , Jitender S. Deogun , Tsegaye Tadesse, Discovering Sequential Association Rules with Constraints and Time Lags in Multiple Sequences, Proceedings of the 13th International Symposium on Foundations of Intelligent Systems, p.432-441, June 27-29, 2002
• 36: P. Kalnis, N. Mamoulis, and S. Bakiras. On discovering moving clusters in spatio-temporal data. In 9th International Symposium on Spatial and Temporal Databases (SSTD2005), volume 3633 of LNCS, page 364381, Angra dos Reis, 2005. Springer.
• 37: Murat Kantarcioglu , Chris Clifton, Privacy-Preserving Distributed Mining of Association Rules on Horizontally Partitioned Data, IEEE Transactions on Knowledge and Data Engineering, v.16 n.9, p.1026-1037, September 2004 [doi>10.1109/TKDE.2004.45]
• 38: Murat Kantarcioǧlu , Jiashun Jin , Chris Clifton, When do data mining results violate privacy?, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014126]
• 39: Eamonn Keogh , Stefano Lonardi , Chotirat Ann Ratanamahatana, Towards parameter-free data mining, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014077]
• 40: Mika Klemettinen , Heikki Mannila , Pirjo Ronkainen , Hannu Toivonen , A. Inkeri Verkamo, Finding interesting rules from large sets of discovered association rules, Proceedings of the third international conference on Information and knowledge management, p.401-407, November 29-December 02, 1994, Gaithersburg, Maryland, United States [doi>10.1145/191246.191314]
• 41: George J. Klir , Bo Yuan, Fuzzy sets and fuzzy logic: theory and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 42: S. Lee and D. Cheung. Maintenance of discovered association rules: When to update? In R. Ng, editor, ACM SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery (DMKD'97), Tucson, AZ, USA, 1997. ACM.
• 43: S. D. Lee , David W. Cheung , Ben Kao, Is Sampling Useful in Data Mining? A Case in the Maintenance of Discovered Association Rules, Data Mining and Knowledge Discovery, v.2 n.3, p.233-262, September 1998 [doi>10.1023/A:1009703019684]
• 44: Brian Lent , Arun N. Swami , Jennifer Widom, Clustering Association Rules, Proceedings of the Thirteenth International Conference on Data Engineering, p.220-231, April 07-11, 1997
• 45: Shenzhi Li , Tianhao Wu , William M. Pottenger, Distributed higher order association rule mining using information extracted from textual data, ACM SIGKDD Explorations Newsletter, v.7 n.1, p.26-35, June 2005 [doi>10.1145/1089815.1089820]
• 46: Tao Li , Shenghuo Zhu , Mitsunori Ogihara, A new distributed data mining model based on similarity, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952618]
• 47: Wenmin Li , Jiawei Han , Jian Pei, CMAR: Accurate and Efficient Classification Based on Multiple Class-Association Rules, Proceedings of the 2001 IEEE International Conference on Data Mining, p.369-376, November 29-December 02, 2001
• 48: B. Liu, W. Hsu, and Y. Ma. Intergrating classification and association rule mining. In 4th International Conference on Knowledge Discovery and Data Mining, KDD-98, pages 80--86, New York City, 1998. AAAI Press.
• 49: A. Maddalena and B. Catania. Towards an interoperable solution for pattern management. In 3rd Int. Workshop on Database Interoperability INTERDB'07 (in conjunction with VLDB'07), Vienna, Austria, Sept. 2007.
• 50: Qiaozhu Mei , ChengXiang Zhai, Discovering evolutionary theme patterns from text: an exploration of temporal text mining, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081895]
• 51: R. Meo and G. Psaila. An xml-based database for knowledge discovery. In 2nd International Workshop on Pattern Representation and Management (PaRMa'06), Munich, Germany, 2006.
• 52: R. J. Miller , Y. Yang, Association rules over interval data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.452-461, May 11-15, 1997, Tucson, Arizona, United States
• 53: D. Mladenic, W. F. Eddy, and S. Ziolko. Exploratory analysis of retail sales of billions of items. Computer Science and Statistics, 33, 2001.
• 54: C. H. Mooney and J. F. Roddick. Mining itemsets - an approach to longitudinal and incremental association rule mining. In A. Zanasi, C. Brebbia, N. Ebecken, and P. Melli, editors, Data Mining III - 3rd International Conference on Data Mining Methods and Databases, pages 93--102, Bologna, Italy, 2002. WIT Press.
• 55: Daniel B. Neill , Andrew W. Moore , Maheshkumar Sabhnani , Kenny Daniel, Detection of emerging space-time clusters, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081897]
• 56: M. Pazzani, S. Mani, and W. R. Shankle. Beyond concise and colorful: learning intelligible rules. In D. Heckerman, H. Mannila, D. Pregibon, and R. Uthurusamy, editors, Third International Conference on Knowledge Discovery and Data Mining, page 235238, Newport Beach, CA, USA, 1997. AAAI Press.
• 57: W. Perrizo and A. Denton. Framework unifying association rule mining, clustering and classification. In International Conference on Computer Science, Software Engineering, Information Technology, e-Business, and Applications (CSITeA03), Rio de Janeiro, Brazil, 2003.
• 58: William M. Pottenger , Shenzhi Li , Christopher D. Janneck, Distributed higher-order text mining: theory and practice, Proceedings of the 2006 international conference on Digital government research, May 21-24, 2006, San Diego, California [doi>10.1145/1146598.1146742]
• 59: A. Prodromidis, P. Chan, and S. Stolfo. Meta-learning in distributed data mining systems: Issues and approaches. In H. Kargupta and P. Chan, editors, Advances in Distributed and Parallel Knowledge Discovery. AAAI press, 2000.
• 60: John F. Roddick , Peter Fule, SemGrAM: integrating semantic graphs into association rule mining, Proceedings of the sixth Australasian conference on Data mining and analytics, December 03-04, 2007, Gold Coast, Australia
• 61: John F. Roddick , Myra Spiliopoulou, A Survey of Temporal Knowledge Discovery Paradigms and Methods, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.750-767, July 2002 [doi>10.1109/TKDE.2002.1019212]
• 62: Boris Rozenberg , Ehud Gudes, Association rules mining in vertically partitioned databases, Data & Knowledge Engineering, v.59 n.2, p.378-396, November 2006 [doi>10.1016/j.datak.2005.09.001]
• 63: M. Spiliopoulou and J. F. Roddick. Higher order mining: Modelling and mining the results of knowledge discovery. In N. Ebecken and C. Brebbia, editors, Data Mining II - 2nd International Conference on Data Mining Methods and Databases, pages 309--320, Cambridge, UK, 2000. WIT Press.
• 64: Myra Spiliopoulou , Irene Ntoutsi , Yannis Theodoridis , Rene Schult, MONIC: modeling and monitoring cluster transitions, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150491]
• 65: S. Thomas, S. Bodagala, K. Alsabti, and S. Ranka. An efficient algorithm for the incremental updation of association rules. In 3rd International Conference on Knowledge Discovery and Data Mining (KDD 97), pages 263--266, New Port Beach, CA, USA, 1997. ACM Press.
• 66: H. Toivonen, M. Klemettinen, P. Ronkainen, K. Hatonen, and H. Mannila. Pruning and grouping of discovered association rules. In ECML-95 Workshop on Statistics, Machine Learning, and Knowledge Discovery in Databases, pages 47--52, Heraklion, Greece, 1995.
• 67: Alexander Tuzhilin , Gediminas Adomavicius, Handling very large numbers of association rules in the analysis of microarray data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775104]
• 68: Jaideep Vaidya , Chris Clifton, Privacy preserving association rule mining in vertically partitioned data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775142]
• 69: K. Wahlstrom, J. F. Roddick, R. Sarre, V. Estivill-Castro, and D. de Vries. Legal and technical issues of privacy preservation in data mining. In J. Wang, editor, Encyclopedia of Data Warehousing and Mining. IGI Publishing, 2nd edition, 2008.
• 70: Ke Wang , Senqiang Zhou , Yu He, Growing decision trees on support-less association rules, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.265-269, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347147]
• 71: Wei Wang , Jiong Yang , Richard R. Muntz, TAR: Temporal Association Rules on Evolving Numerical Attributes, Proceedings of the 17th International Conference on Data Engineering, p.283-292, April 02-06, 2001
• 72: Jef Wijsen , Robert Meersman, On the Complexity of Mining Quantitative Association Rules, Data Mining and Knowledge Discovery, v.2 n.3, p.263-281, September 1998 [doi>10.1023/A:1009755120593]
• 73: Hui Yang , Srinivasan Parthasarathy , Sameep Mehta, A generalized framework for mining spatio-temporal patterns in scientific data, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081962]
• 74: X. Yin and J. Han. CPAR: Classification based on predictive association rules. In SIAM Conference on Data Mining, SDM'03, pages 369--376, San Francisco, California, USA, 2003. SIAM.
• 75: C. Zhang, M. Liu, W. Nie, and S. Zhang. Identifying global exceptional patterns in multi-database mining. IEEE Computational Intelligence Bulletin, 3(1):19--24, 2004.
• 76: S. Zhang, X. Wu, and C. Zhang. Multi-database mining. IEEE Computational Intelligence Bulletin, 2(1): 5--13, 2003.
• 77: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
      I.2.6 Learning
          Subjects: Knowledge acquisition

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory

Keywords:
higher order mining, mining data synopses, mining derived data, mining patterns, rule semantics