



@book {2249,
	title = {Monitoring incremental histogram distribution for change detection in data streams},
	series = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)Lect. Notes Comput. Sci.},
	volume = {5840 LNCS},
	year = {2010},
	note = {Conference code: 81882Cited By (since 1996): 1Export Date: 21 November 2012Source: Scopusdoi: 10.1007/978-3-642-12519-5_2Language of Original Document: EnglishCorrespondence Address: Sebasti{\~a}o, R.; LIAAD, INESC Porto, L.A. Rua de Ceuta, 118, 6, Porto 4050-190, Portugal; email: raquel@liaad.up.ptReferences: Ayres-De-Campos, D., Sousa, P., Costa, A., Bernardes, J., Omniview-SisPorto{\textregistered} 3.5 - A central fetal monitoring station with online alerts based on computerized cardiotocogram+ST event analysis (2008) J. Perinat. Med., 36, pp. 260-264;Ayres-De-Campos, D., Bernardes, J., Garrido, A., Marques-De-{\'S}a, J., Pereira-Leite, L., SisPorto 2.0: A program for automated analysis of cardiotocograms (2000) J. Matern Fetal Med., 9, pp. 311-318; 
Barba{\'r}a, D., Requirements for clustering data streams (2002) SIGKDD Explorations (Special Issue on Online, Interactive and Anytime Data Mining), 3 (2), pp. 23-27; 
Berthold, M., Hand, D., (1999) Intelligent Data Analysis-An Introduction., , Springer, Heidelberg; 
Breiman, L., (1993) Classification and Regression Trees., , Chapman \& Hall, Boca Raton; 
Bock, R.K., Savicky, P., (2007) MAGIC Gamma Telescope Benchmark, , http://archive.ics.uci.edu/ml/datasets.html; 
Chabert, M., Ruiz, D., Tourneret, J.-Y., Optimal wavelet for abrupt change detection in multiplicative noise (2004) IEEE International Conference on Acoustics Speech and Signal Processing, pp. 1089-1092. , May 2004; 
Cormode, G., Garofalakis, M., Sketching probabilistic data streams (2007) Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data, pp. 281-292. , June 2007; 
Correa, M., De, J., Raḿirez, M., Bielza, C., Pamies, J., Alique, J.R., Prediction of surface quality using probabilistic models (2007) 7th Congress of the Colombian Association of Automatic, Cali, Colombia, , March 21-24 Spanish; 
Dasu, T., Krishnan, S., Venkatasubramanian, S., Yi, K., An information-theoretic approach to detecting changes in multi-dimensional data streams (2006) Interface 2006, , Pasadena, CA Report; 
Gama, J., Medas, P., Castillo, G., Rodrigues, P.P., Learning with drift detection (2004) LNCS (LNAI), 3171, pp. 286-295. , Bazzan, A.L.C., Labidi, S. (eds.) Springer, Heidelberg SBIA 2004; 
Gama, J., Pinto, C., Discretization from data streams: Applications to histograms and data mining (2006) Proceedings of the 2006 ACM Symposium on Applied Computing, pp. 662-667; 
Goncalves, H., Bernardes, J., Paula Rocha, J.A., Linear and nonlinear analysis of heart rate patterns associated with fetal behavioral states in the antepartum period (2007) Early Human Development, 83 (9), pp. 585-591; 
Guha, S., Koudas, N., Woo, J., (2004) REHIST: Relative Error Histogram Construction Algorithms, pp. 300-311. , Proceedings of the VLDB Conference; 
Guha, S., Harb, B., Wavelet synopsis for data streams: Minimizing non-euclidean error (2005) Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, pp. 88-97. , August 2005; 
Guha, S., Koudas, N., Shim, K., Approximation and streaming algorithms for histogram construction problems (2006) ACM Transactions on Database Systems (TODS), 31 (1), pp. 396-438; 
Hulten, G., Spencer, L., Domingos, P., Mining time-changing data streams (2001) Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining ACM SIGKDD 2001, pp. 97-106. , ACM Press, New York; 
Jagadish, H.V., Koudas, N., Muthukrishnan, S., Poosala, V., Sevcik, K.C., Suel, T., Optimal histograms with quality guarantees (1998) Proc. of the VLDB Conference, pp. 275-286; 
Karras, P., Sacharidis, D., Mamoulis, N., Exploiting Duality in Summarization with Deterministic Guarantees. Approximating a Data Stream for Querying and Estimation: Algorithms and Performance Evaluation (2007) Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 380-389; 
Kifer, D., Ben-David, S., Gehrke, J., (2004) Detecting Change in Data Streams, pp. 180-191. , VLDB 2004: Proceedings of the 30th International Conference on Very Large Data Bases Morgan Kaufmann Publishers Inc., San Francisco; 
Klinkenberg, R., Renz, I., Adaptive information filtering: Learning in the presence of concept drifts (1998) Learning for Text Categorization, pp. 33-40. , AAAI Press, Menlo Park; 
Klinkenberg, R., Joachims, T., Detecting concept drift with support vector ma-chines (2000) Proceedings of ICML 2000, 17th International Conference on Machine Learning, Stanford, US, pp. 487-494. , Morgan Kaufmann Publishers, San Francisco; 
Klinkenberg, R., Learning drifting concepts: Example selection vs. example weight-ing (2004) Intelligent Data Analysis, 8 (3), pp. 281-300; 
Maloof, M., Michalski, R., Selecting examples for partial memory learning (2000) Machine Learning, 41, pp. 27-52; 
Pestana, D.D., Velosa, S.F., Introdu̧c̃a{\`o}a Probabilidade{\`e}a Estat̀istica (2002) Funda̧c̃ao Calouste Gulbenkian; 
Pinto, C., Gama, J., Incremental discretization, application to data with concept drift (2007) Proceedings of the 2007 ACM Symposium on Applied Computing, pp. 467-468. , March 2007; 
Sebastiao, R., Gama, J., Change detection in learning histograms from data streams (2007) Proceedings of Portuguese Conference on Artificial Intelligence, Guimar̃aes, Portugal, , December; 
Spinosa, E.J., Carvalho, A., Gama, J., OLINDDA: A cluster-based approach for detecting novelty and concept drift in data streams (2007) Proceedings of the 2007 ACM Symposium on Applied Computing, March 2007, pp. 448-452; 
Widmer, G., Kubat, M., Learning in the presence of concept drift and hidden contexts (1996) Machine Learning, 23, pp. 69-101
},
	month = {2010///},
	pages = {25 - 42},
	address = {Las Vegas, NV},
	abstract = {Histograms are a common technique for density estimation and they have been widely used as a tool in exploratory data analysis. Learning histograms from static and stationary data is a well known topic. Nevertheless, very few works discuss this problem when we have a continuous flow of data generated from dynamic environments. The scope of this paper is to detect changes from high-speed time-changing data streams. To address this problem, we construct histograms able to process examples once at the rate they arrive. The main goal of this work is continuously maintain a histogram consistent with the current status of the nature. We study strategies to detect changes in the distribution generating examples, and adapt the histogram to the most recent data by forgetting outdated data. We use the Partition Incremental Discretization algorithm that was designed to learn histograms from high-speed data streams. We present a method to detect whenever a change in the distribution generating examples occurs. The base idea consists of monitoring distributions from two different time windows: the reference window, reflecting the distribution observed in the past; and the current window which receives the most recent data. The current window is cumulative and can have a fixed or an adaptive step depending on the distance between distributions. We compared both distributions using Kullback-Leibler divergence, defining a threshold for change detection decision based on the asymmetry of this measure. We evaluated our algorithm with controlled artificial data sets and compare the proposed approach with nonparametric tests. We also present results with real word data sets from industrial and medical domains. Those results suggest that an adaptive window{\textquoteright}s step exhibit high probability in change detection and faster detection rates, with few false positives alarms. {\textcopyright} 2010 Springer-Verlag Berlin Heidelberg.},
	keywords = {Adaptive Cumulative Windows, Change detection, Data communication systems, Data reduction, Data stream, Data streams, Graphic methods, Learning histograms, Learning systems, Machine learning, Machine-learning, Monitoring, Monitoring data distribution, Sensors, signal detection, Statistical methods},
	isbn = {03029743 (ISSN); 3642125182 (ISBN); 9783642125188 (ISBN)},
	url = {http://www.scopus.com/inward/record.url?eid=2-s2.0-77957913416\&partnerID=40\&md5=ec0810650dda3c604d494473a9ffd649},
	author = {Sebasti{\~a}o, R. and Gama, J. and Rodrigues, P.P. and Bernardes, J.}
}
