Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Many applications in surveillance, monitoring, scientific discovery, and data cleaning require the identification of anomalies. Although many methods have been developed to identify statistically significant anomalies, a more difficult task is to identify anomalies that are both interesting and statistically significant. Category detection is an emerging area of machine learning that can help address this issue using a "human-in-the-loop" approach. In this interactive setting, the algorithm asks the user to label a query data point under an existing category or declare the query data point to belong to a previously undiscovered category. The goal of category detection is to bring to the user's attention a representative data point from each category in the data in as few queries as possible. In a data set with imbalanced categories, the main challenge is in identifying the rare categories or anomalies; hence, the task is often referred to as rare category detection. We present a new approach to rare category detection based on hierarchical mean shift. In our approach, a hierarchy is created by repeatedly applying mean shift with an increasing bandwidth on the data. This hierarchy allows us to identify anomalies in the data set at different scales, which are then posed as queries to the user. The main advantage of this methodology over existing approaches is that it does not require any knowledge of the dataset properties such as the total number of categories or the prior probabilities of the categories. Results on real-world data sets show that our hierarchical mean shift approach performs consistently better than previous techniques.

REFERENCES

• 1: Mikhail Bilenko , Sugato Basu , Raymond J. Mooney, Integrating constraints and metric learning in semi-supervised clustering, Proceedings of the twenty-first international conference on Machine learning, p.11, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015360]
• 2: Yizong Cheng, Mean Shift, Mode Seeking, and Clustering, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.8, p.790-799, August 1995 [doi>10.1109/34.400568]
• 3: Dorin Comaniciu , Peter Meer, Mean Shift: A Robust Approach Toward Feature Space Analysis, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.5, p.603-619, May 2002 [doi>10.1109/34.1000236]
• 4: Daniel Dementhon. Spatio-temporal segmentation of video by hierarchical mean shift analysis. In SMVP 2002 (Statistical Methods in Video Processing Workshop), 2002.
• 5: Shai Fine , Yishay Mansour, Active sampling for multiple output identification, Machine Learning, v.69 n.2-3, p.213-228, December 2007 [doi>10.1007/s10994-007-5026-6]
• 6: K. Fukunaga and L. Hostetler. The estimation of the gradient of a density function, with applications in pattern recognition. Information Theory, IEEE Transactions on, 21(1):32--40, 1975.
• 7: Bogdan Georgescu , Ilan Shimshoni , Peter Meer, Mean Shift Based Clustering in High Dimensions: A Texture Classification Example, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.456, October 13-16, 2003
• 8: Jingrui He and Jaime Carbonell. Nearest-neighbor-based active learning for rare category detection. In J.C. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems 20, pages 633--640. MIT Press, Cambridge, MA, 2008.
• 9: M. Chris Jones, James S. Marron, and Simon J. Sheather. A brief survey of bandwidth selection for density estimation. Journal of American Statistical Association, 91(433):401--407, March 1996.
• 10: Andrew Moore Kan Deng. Multiresolution instance-based learning. In Proceedings of the Twelfth International Joint Conference on Artificial Intellingence, pages 1233--1239, San Francisco, 1995. Morgan Kaufmann.
• 11: Ashish Kapoor, Kristen Grauman, Raquel Urtasun, and Trevor Darrell. Active learning with gaussian processes for object categorization. In Computer Vision, 2007. ICCV 2007. IEEE 11th International Conference on, pages 1--8, 2007.
• 12: Yee Leung , Jiang-She Zhang , Zong-Ben Xu, Clustering by Scale-Space Filtering, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.12, p.1396-1410, December 2000 [doi>10.1109/34.895974]
• 13: Wendy L. Martinez , Angel R. Martinez, Exploratory Data Analysis with MATLAB (Computer Science and Data Analysis), Chapman & Hall/CRC, 2004
• 14: C.L. Blake D.J. Newman and C.J. Merz. UCI repository of machine learning databases, 1998.
• 15: Dan Pelleg and Andrew Moore. Active learning for anomaly and rare-category detection. In Advances in Neural Information Processing Systems 18, December 2004.
• 16: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 17: Alexander S. Szalay, The sloan digital sky survey, Computing in Science and Engineering, v.1 n.2, p.54-62, March-April 1999 [doi>10.1109/5992.753047]
• 18: Ping Wang, Dongryeol Lee, Alexander Gray, and James Rehg. Fast mean shift with accurate and stable convergence. In In Proceedings of AISTATS 2007, 2007.
• 19: Eric P. Xing, Andrew Y. Ng, Michael I. Jordan, and Stuart Russell. Distance metric learning, with application to clustering with side-information. In Advances in Neural Information Processing Systems 15, pages 505--512. MIT Press, 2003.
• 20: Changjiang Yang , Ramani Duraiswami , Nail A. Gumerov , Larry Davis, Improved Fast Gauss Transform and Efficient Kernel Density Estimation, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.464, October 13-16, 2003
• 21: Liu Yang , Rong Jin , Rahul Sukthankar , Yi Liu, An efficient algorithm for local distance metric learning, Proceedings of the 21st national conference on Artificial intelligence, p.543-548, July 16-20, 2006, Boston, Massachusetts

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Nonparametric statistics

General Terms:
Algorithms, Experimentation, Performance

Keywords:
anomaly detection, category detection, clustering, mean shift