Cost-based labeling of groups of mass spectra

ABSTRACT

We make two main contributions in this paper. First, we motivate and introduce a novel class of data mining problems that arise in labeling a group of mass spectra, specifically for analysis of atmospheric aerosols, but with natural applications to market-basket datasets. This builds upon other recent work in which we introduced the problem of labeling a single spectrum, and is motivated by the advent of a new generation of Aerosol Time-of-Flight Spectrometers, which are capable of generating mass spectra for hundreds of aerosol particles per minute. We also describe two algorithms for group labeling, which differ greatly in how they utilize a linear programming (LP) solver, and also differ greatly from algorithms for labeling a single spectrum.Our second contribution is to show how to automatically select between these two algorithms in a cost-based manner, analogous to how a query optimizer selects from a space of query plans. While the details are specific to the labeling problem, we believe that is a promising first step towards a general framework for cost-based data mining, and opens up an important direction for future search.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 2: A. Arning et al. A linear method for deviation detection in large databases. In ACM KDD, 1996.
• 3: P. Berkhin. Survey of clustering data mining techniques. Technical report, Accrue Software, San Jose, CA, 2002.
• 4: K. Doksun and P. Bickel. Mathematical Statistics, Chapter 6. Prentice Hall, 2001.
• 5: Chun-Hung Cheng , Ada Waichee Fu , Yi Zhang, Entropy-based subspace clustering for mining numerical data, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.84-93, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312199]
• 6: E. Gard et al. Real-time analysis of individual atmospheric aerosol particles: Design and performance of a portable ATOFMS. In Anal. Chem., pages 4083--4091, 1997.
• 7: Ingolf Geist, A framework for data mining and KDD, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain [doi>10.1145/508791.508887]
• 8: S. Guha , N. Mishra , R. Motwani , L. O'Callaghan, Clustering data streams, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.359, November 12-14, 2000
• 9: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.1-12, May 15-18, 2000, Dallas, Texas, United States
• 10: Z. Huang et al. Mass spectrum labeling: Theory and practice. CS Department, TR, UW-Madison, 2004.
• 11: Tomasz Imielinski , Heikki Mannila, A database perspective on knowledge discovery, Communications of the ACM, v.39 n.11, p.58-64, Nov. 1996 [doi>10.1145/240455.240472]
• 12: T. Johnson et al. The 3W model and algebra for unified data mining. In The VLDB Journal, 2000.
• 13: Jean B. Lasserre , Eduardo S. Zeron, On Counting Integral Points in a Convex Rational Polytope, Mathematics of Operations Research, v.28 n.4, p.853-870, November 2003 [doi>10.1287/moor.28.4.853.20518]
• 14: Jean B. Lasserre , Eduardo S. Zeron, A Laplace transform algorithm for the volume of a convex polytope, Journal of the ACM (JACM), v.48 n.6, p.1126-1140, November 2001 [doi>10.1145/504794.504796]
• 15: Jean B. Lasserre , Eduardo S. Zeron, On Counting Integral Points in a Convex Rational Polytope, Mathematics of Operations Research, v.28 n.4, p.853-870, November 2003 [doi>10.1287/moor.28.4.853.20518]
• 16: John McCarthy, Phenomenal data mining, Communications of the ACM, v.43 n.8, p.75-79, Aug. 2000 [doi>10.1145/345124.345152]
• 17: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 18: J. Nocedal and S. J. Wright. Numerical Optimization. Springer, 1999.
• 19: National Research Council. Research Priorities for Airborne Particulate Matter. Immediate Priorities and a Long-Range Research Portfolio. National Academy Press, 1998.
• 20: K. A. Prather et al. Real-time characterization of individual aerosol particles using time-of-flight mass spectrometry. In Anal. Chem., pages 1403--1407, 1994.
• 21: Olivia C. Rud, Data Mining, Cookbook: Modeling Data for Marketing, Risk and Customer Relationship Management, John Wiley & Sons, Inc., New York, NY, 2001
• 22: Ramakrishnan Srikant , Rakesh Agrawal, Mining quantitative association rules in large relational tables, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.1-12, June 04-06, 1996, Montreal, Quebec, Canada
• 23: D. Suess and K. A. Prather. Mass spectrometry of aerosols. In Chemical Reviews, pages 3007--3035, 1999.
• 24: Hannu Toivonen, Sampling Large Databases for Association Rules, Proceedings of the 22th International Conference on Very Large Data Bases, p.134-145, September 03-06, 1996
• 25: S. B. Yao, Approximating block accesses in database organizations, Communications of the ACM, v.20 n.4, p.260-261, April 1977 [doi>10.1145/359461.359475]
• 26: 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
• 27: W. Zhang and R. Korf. An average-case analysis of branch-and-bound with applications: Summary of results. In AAAI, 1992.
• 28: Rosa Meo , Giuseppe Psaila , Stefano Ceri, A Tightly-Coupled Architecture for Data Mining, Proceedings of the Fourteenth International Conference on Data Engineering, p.316-323, February 23-27, 1998
• 29: S. Sarawagi et al. Integrating mining with relational database systems. In ACM SIGMOD, 1998.