Abstract
In many application areas, it is important to detect outliers. Traditional engineering approach to outlier detection is that we start with some ”normal” values x 1,...,x n , compute the sample average E, the sample standard variation σ, and then mark a value x as an outlier if x is outside the k 0-sigma interval [E − k 0·σ,E + k 0·σ] (for some pre-selected parameter k 0). In real life, we often have only interval ranges \([{\underline x}_i,{\overline x}_i]\) for the normal values x 1,...,x n . In this case, we only have intervals of possible values for the bounds E-k 0·σ and E+k 0·σ. We can therefore identify outliers as values that are outside all k 0-sigma intervals. In this paper, we analyze the computational complexity of these outlier detection problems, and provide efficient algorithms that solve some of these problems (under reasonable conditions).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Devore, J., Peck, R.: Statistics: the Exploration and Analysis of Data. Duxbury, California (1999)
Ferregut, C., Osegueda, R.A., Nuñez, A. (eds.): Proceedings of the International Workshop on Intelligent NDE Sciences for Aging and Futuristic Aircraft, El Paso, TX, September 30-October 2 (1997)
Ferson, S., Ginzburg, L., Kreinovich, V., Longpré, L., Aviles, M.: Computing Variance for Interval Data is NP-Hard. ACM SIGACT News 33(2), 108–118 (2002)
Ferson, S., Ginzburg, L., Kreinovich, V., Aviles, M.: Exact Bounds on Sample Variance of Interval Data. In: Extended Abstracts of the 2002 SIAM Workshop on Validated Computing, Toronto, Canada, pp. 67–69 (2002)
Goodchild, M., Gopal, S.: Accuracy of Spatial Databases. Taylor & Francis, London (1989)
Gros, X.E.: NDT Data Fusion. J. Wiley, London (1997)
Kosheleva, O., Cabrera, S., Osegueda, R., Nazarian, S., George, D.L., George, M.J., Kreinovich, V., Worden, K.: Case study of non-linear inverse problems: mammography and non-destructive evaluation. In: Mohamad-Djafari, A. (ed.) Bayesian Inference for Inverse Problems, Proceedings of the SPIE/International Society for Optical Engineering, San Diego, CA, vol. 3459, pp. 128–135 (1998)
Kreinovich, V., Lakeyev, A., Rohn, J., Kahl, P.: Computational complexity and feasibility of data processing and interval computations. Kluwer, Dordrecht (1997)
McCain, M., William, C.: Integrating Quality Assurance into the GIS Project Life Cycle. In: Proceedings of the 1998 ESRI Users Conference, http://www.dogcreek.com/html/documents.html
Osegueda, R., Kreinovich, V., Potluri, L., Aló, R.: Non-Destructive Testing of Aerospace Structures: Granularity and Data Mining Approach. In: Proceedings of FUZZ-IEEE 2002, Honolulu, Hawaii, May 12-17, vol. 1, pp. 685–689 (2002)
Osegueda, R.A., Seelam, S.R., Holguin, A.C., Kreinovich, V., Tao, C.-W.: Statistical and Dempster-Shafer Techniques in Testing Structural Integrity of Aerospace Structures. International Journal of Uncertainty, Fuzziness, Knowledge-Based Systems (IJUFKS) 9, 749–758 (2001)
Rabinovich, S.: Measurement Errors: Theory and Practice. American Institute of Physics, New York (1993)
Scott, L.: Identification of GIS Attribute Error Using Exploratory Data Analysis. Professional Geographer 46, 378–386 (1994)
Vavasis, S.A.: Nonlinear optimization: complexity issues. Oxford University Press, N.Y. (1991)
Wadsworth Jr., H.M. (ed.): Handbook of statistical methods for engineers and scientists. McGraw-Hill Publishing Co., N.Y (1990)
Wen, Q., Gates, A.Q., Beck, J., Kreinovich, V., Keller, G.R.: Towards automatic detection of erroneous measurement results in a gravity database. In: Proceedings of the 2001 IEEE Systems, Man, and Cybernetics Conference, Tucson, Arizona, October 7-10, pp. 2170–2175 (2001)
Worden, K., Osegueda, R., Ferregut, C., Nazarian, S., George, D.L., George, M.J., Kreinovich, V., Kosheleva, O., Cabrera, C.: Interval Methods in Non- Destructive Testing of Material Structures. Reliable Computing 7, 341–352 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kreinovich, V., Longpré, L., Patangay, P., Ferson, S., Ginzburg, L. (2004). Outlier Detection under Interval Uncertainty: Algorithmic Solvability and Computational Complexity. In: Lirkov, I., Margenov, S., Waśniewski, J., Yalamov, P. (eds) Large-Scale Scientific Computing. LSSC 2003. Lecture Notes in Computer Science, vol 2907. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24588-9_26
Download citation
DOI: https://doi.org/10.1007/978-3-540-24588-9_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21090-0
Online ISBN: 978-3-540-24588-9
eBook Packages: Springer Book Archive