Indexing density models for incremental learning and anytime classification on data streams

ABSTRACT

Classification of streaming data faces three basic challenges: it has to deal with huge amounts of data, the varying time between two stream data items must be used best possible (anytime classification) and additional training data must be incrementally learned (anytime learning) for applying the classifier consistently to fast data streams. In this work, we propose a novel index-based technique that can handle all three of the above challenges using the established Bayes classifier on effective kernel density estimators. Our novel Bayes tree automatically generates (adapted efficiently to the individual object to be classified) a hierarchy of mixture densities that represent kernel density estimators at successively coarser levels. Our probability density queries together with novel classification improvement strategies provide the necessary information for very effective classification at any point of interruption. Moreover, we propose a novel evaluation method for anytime classification using Poisson streams and demonstrate the anytime learning performance of the Bayes tree.

REFERENCES

• 1: D. Andre and P. Stone. Physiological data modeling contest (ICML-2004): http://www.cs.utexas.edu/users/pstone/workshops/2004icml/, 2004.
• 2: T. Bayes. An essay towards solving a problem in the doctrine of chances. Philosophical Transactions of the Royal Society, 53:370--418, 1763.
• 3: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 4: C. Böhm, A. Pryakhin, and M. Schubert. The Gauss-Tree: Efficient Object Identification in Databases of Probabilistic Feature Vectors. ICDE, 2006.
• 5: Jack S. Breese , Eric Horvitz, Ideal reformulation of belief networks, Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence, p.129-144, July 27-29, 1990
• 6: Christopher J. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, v.2 n.2, p.121-167, June 1998 [doi>10.1023/A:1009715923555]
• 7: Yongqiang Cao , Jianhong Wu, Projective ART for clustering data sets in high dimensional spaces, Neural Networks, v.15 n.1, p.105-120, January 2002 [doi>10.1016/S0893-6080(01)00108-3]
• 8: K. Crammer, J. S. Kandola, and Y. Singer. Online classification on a budget. In NIPS, 2003.
• 9: Dennis DeCoste, Anytime Interval-Valued Outputs for Kernel Machines: Fast Support Vector Machine Classification via Distance Geometry, Proceedings of the Nineteenth International Conference on Machine Learning, p.99-106, July 08-12, 2002
• 10: Pedro Domingos , Geoff Hulten, Mining high-speed data streams, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.71-80, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347107]
• 11: P. Domingos and G. Hulten. Learning from infinite data in finite time. In NIPS, pages 673--680, 2001.
• 12: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 13: Saher Esmeir , Shaul Markovitch, Interruptible anytime algorithms for iterative improvement of decision trees, Proceedings of the 1st international workshop on Utility-based data mining, p.78-85, August 21-21, 2005, Chicago, Illinois [doi>10.1145/1089827.1089837]
• 14: A. G. Gray and A. W. Moore. Nonparametric density estimation: Toward computational tractability. In SDM, 2003.
• 15: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 16: T. Hastie, R. Tibshirani, and J. H. Friedman. Datasets for "The Elements of Statistical Learning": http://www-stat.stanford.edu/~tibs/elemstatlearn/.
• 17: T. Hastie, R. Tibshirani, and J. H. Friedman. The Elements of Statistical Learning. Springer, 2002.
• 18: S. Hettich and S. Bay. The UCI KDD archive http://kdd.ics.uci.edu, 1999.
• 19: Geoff Hulten , Pedro Domingos, Mining complex models from arbitrarily large databases in constant time, 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.775124]
• 20: M. Jordan and R. Jacobs. Hierarchical Mixtures of Experts and the EM Algorithm. Graphical Models: Foundations of Neural Computation, 2001.
• 21: Philipp Kranen , David Kensche , Saim Kim , Nadine Zimmermann , Emmanuel Müller , Christoph Quix , Xiang Li , Thomas Gries , Thomas Seidl , Matthias Jarke , Steffen Leonhardt, Mobile Mining and Information Management in HealthNet Scenarios, Proceedings of the The Ninth International Conference on Mobile Data Management, p.215-216, April 27-30, 2008 [doi>10.1109/MDM.2008.12]
• 22: Chao-Lin Liu , Michael P. Wellman, On state-space abstraction for anytime evaluation of Bayesian networks, ACM SIGART Bulletin, v.7 n.2, p.50-57, April 1996 [doi>10.1145/242587.242601]
• 23: Kary Myers , Michael J. Kearns , Satinder P. Singh , Marilyn A. Walker, A Boosting Approach to Topic Spotting on Subdialogues, Proceedings of the Seventeenth International Conference on Machine Learning, p.655-662, June 29-July 02, 2000
• 24: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 25: T. Seidl. Nearest Neighbor Classification / Liu L., Özsu M. T. (eds.): Encyclopedia of Database Systems. (to appear). Springer, 2009.
• 26: Thomas Seidl , Hans-Peter Kriegel, Optimal multi-step k-nearest neighbor search, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.154-165, June 01-04, 1998, Seattle, Washington, United States
• 27: L. Silva, J. M. de Sa, and L. Alexandre. Neural network classification using shannonŠs entropy. In ESANN, 2005.
• 28: B. Silverman. Density Estimation for Statistics and Data Analysis. 1986.
• 29: W. Nick Street , YongSeog Kim, A streaming ensemble algorithm (SEA) for large-scale classification, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.377-382, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502568]
• 30: Ken Ueno , Xiaopeng Xi , Eamonn Keogh , Dah-Jye Lee, Anytime Classification Using the Nearest Neighbor Algorithm with Applications to Stream Mining, Proceedings of the Sixth International Conference on Data Mining, p.623-632, December 18-22, 2006 [doi>10.1109/ICDM.2006.21]
• 31: W. Wahlster. Verbmobil: Foundations of Speech-To-Speech Translation. Springer, 2000.
• 32: Haixun Wang , Wei Fan , Philip S. Yu , Jiawei Han, Mining concept-drifting data streams using ensemble classifiers, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956778]
• 33: Gerhard Widmer , Miroslav Kubat, Learning in the presence of concept drift and hidden contexts, Machine Learning, v.23 n.1, p.69-101, April 1996 [doi>10.1023/A:1018046501280]
• 34: Ying Yang , Geoff Webb , Kevin Korb , Kai Ming Ting, Classifying under computational resource constraints: anytime classification using probabilistic estimators, Machine Learning, v.69 n.1, p.35-53, October 2007 [doi>10.1007/s/109994-007-5020-z]
• 35: Tian Zhang , Raghu Ramakrishnan , Miron Livny, Fast density estimation using CF-kernel for very large databases, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.312-316, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312266]
• 36: S. Zilberstein. Using anytime algorithms in intelligent systems. The AI magazine, 17(3):73--83, 1996.