research-article

Pattern change discovery between high dimensional data sets

Authors:

Zhongfei Zhang,

Bo LongAuthors Info & Claims

CIKM '11: Proceedings of the 20th ACM international conference on Information and knowledge management

Pages 1097 - 1106

https://doi.org/10.1145/2063576.2063735

Published: 24 October 2011 Publication History

Abstract

This paper investigates the general problem of pattern change discovery between high-dimensional data sets. Current methods either mainly focus on magnitude change detection of low-dimensional data sets or are under supervised frameworks. In this paper, the notion of the principal angles between the subspaces is introduced to measure the subspace difference between two high-dimensional data sets. Principal angles bear a property to isolate subspace change from the magnitude change. To address the challenge of directly computing the principal angles, we elect to use matrix factorization to serve as a statistical framework and develop the principle of the dominant subspace mapping to transfer the principal angle based detection to a matrix factorization problem. We show how matrix factorization can be naturally embedded into the likelihood ratio test based on the linear models. The proposed method is of an unsupervised nature and addresses the statistical significance of the pattern changes between high-dimensional data sets. We have showcased the different applications of this solution in several specific real-world applications to demonstrate the power and effectiveness of this method.

References

[1]

A. Banerjee, S. Merugu, I.S.Dhillon, and J.Ghosh. Clustering with Bregman divergence. Journal of Machine Learning Research, 6:1705--1749, 2005.

Digital Library

[2]

A. Bifet, G. Holmes, B. Pfahringer, R. Kirkby, and R. Gavaldà. New ensemble methods for evolving data streams. In KDD '09, pages 139--148, 2009.

Digital Library

[3]

Y. Chi, B. Tseng, and J. Tatemura. Eigen-trend: trend analysis in the blogosphere based on singular value decomposition. In CIKM, pages 68--77, 2006.

Digital Library

[4]

C. Ding, T. Li, and M. Jordan. Nonnegative matrix factorization for combinatorial optimization: Spectral clustering, graph matching, and clique finding. In ICDM, pages 183--192, 2008.

Digital Library

[5]

A. Dries and U. Rückert. Adaptive concept drift detection. Statistical Analysis and Data Mining, 2(5--6):311--327, 2009.

Digital Library

[6]

R. Ge, M. Ester, B. Gao, Z. Hu, B. Bhattacharya, and B. Ben-Moshe. Joint cluster analysis of attribute data and relationship data: The connected k-center problem algorithms and applications. Trans. on Knowledge discovery from Data, 2:1--35, 2008.

Digital Library

[7]

G. H. Golub and C. F. V. Loan. Matrix computation. The Johns Hopkins University Press, Baltimore and London, 1996.

[8]

G. Gordon. Generalized² linear² models. In NIPS, 2002.

[9]

D. He and D.Parker. Topic dynamics: An alternative model of 'bursts' in streams of topics. In KDD, pages 443--452, 2010.

Digital Library

[10]

S. Hido, T. Ide, H. Kashima, H. Kubo, and H. Matsuzawa. Unsupervised change analysis using supervised learning. In Advances in Knowledge Discovery and Data Mining, pages 148--159. Springer Berlin / Heidelberg, 2008.

Digital Library

[11]

G. Hulten, L. Spencer, and P. Domingos. Mining time-changing data streams. In KDD, pages 97--106, 2001.

Digital Library

[12]

D. Kifer, S. Ben-David, and J. Gehrke. Detecting change in data streams. In VLDB, pages 180--191, 2004.

Digital Library

[13]

R. Klinkenberg. Learning drifting concepts: Example selection vs. example weighting. Intelligent Data Analysis, 8(3):697--717, 2004.

Digital Library

[14]

K. Lang. http://people.csail.mit.edu/jrennie/20newsgroups/.

[15]

L.Chen and A.Roy. Event detection from flickr data through wavelet-based spatial analysis. In CIKM, pages 523--532, 2009.

Digital Library

[16]

D. Lee and H. Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 401:788--791, 1999.

[17]

D. Lee and H. Seung. Algorithms for non-negative matrix factorization. In NIPS, pages 556--562, 2000.

Digital Library

[18]

B. Long, Z. Zhang, and P. Yu. Co-clustering by block value decomposition. In KDD, 2005.

Digital Library

[19]

B. Long, Z. Zhang, and P. Yu. Unsupervised learning on k-partite graphs. In KDD, pages 317--326, 2006.

Digital Library

[20]

P. Miettinen. Matrix Decomposition Methods for Data Mining: Computational Complexity and Algorithms. Helsinki University Print, 2009.

[21]

K. Nishida and K. Yamauchi. Detecting concept drift using statistical testing. In Proceedings of the 10th international conference on Discovery science, DS'07, pages 264--269, Berlin, Heidelberg, 2007. Springer-Verlag.

Digital Library

[22]

D. Preston, P. Protopapas, and C. Brodley. Event discovery in time series. In SDM, pages 61--72, 2009.

[23]

G. Seber and A. Lee. Linear Regression Analysis. Wiley, 2003.

[24]

A. P. Singh and G. Gordon. A unified view of matrix factorization models. In ECML PKDD, 2008.

Digital Library

[25]

X. Song, M. Wu, C. Jermaine, and S. Ranka. Statistical change detection for multi-dimensional data. In KDD, 2007.

Digital Library

[26]

A. Tsymbal. The problem of concept drift: Definitions and related work. Technical report, 2004.

[27]

M. van Leeuwen and A. Siebes. Streamkrimp: Detecting change in data streams. In ECML, 2008.

Digital Library

[28]

V. N. Vapnik. Statistical Learning Theory. John Wiley & sons, 1998.

[29]

J. Vreeken, M. Leeuwen, and A. Siebes. Characterising the difference. In KDD '07, pages 226--235, 2007.

Digital Library

[30]

H. Wang, W. Fan, P. Yu, and J. Han. Mining concept-drifting data streams using ensemble classifiers. In KDD '03, pages 226--235, 2003.

Digital Library

[31]

P. Zhang, X. Zhu, and Y. Shi. Categorizing and mining concept drifting data streams. In KDD '08, pages 812--820, 2008.

Digital Library

Cited By

Sprint GCook DSchmitter-Edgecombe M(2017)Unsupervised Detection and Analysis of Changes in Everyday Physical Activity DataAdvances in Biomedical Informatics10.1007/978-3-319-67513-8_6(97-122)Online publication date: 20-Oct-2017
https://doi.org/10.1007/978-3-319-67513-8_6
Sprint GCook DSchmitter-Edgecombe M(2016)Unsupervised detection and analysis of changes in everyday physical activity dataJournal of Biomedical Informatics10.1016/j.jbi.2016.07.02063:C(54-65)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1016/j.jbi.2016.07.020
Kravvaris DKermanindis KChorianopoulos K(2015)Ranking educational videos: The impact of social presence2015 IEEE 9th International Conference on Research Challenges in Information Science (RCIS)10.1109/RCIS.2015.7128895(342-350)Online publication date: May-2015
https://doi.org/10.1109/RCIS.2015.7128895
Show More Cited By

Index Terms

Pattern change discovery between high dimensional data sets
1. Information systems
  1. Information retrieval

Recommendations

Kernel Grassmannian distances and discriminant analysis for face recognition from image sets

We address the problem of face recognition from image sets, where subject-specific subspaces instead of image vectors are compared. Previous methods based on Grassmannian subspace distances mainly take linear subspaces as input. The non-linearity exists ...
Enhanced algorithm for high-dimensional data classification

Graphical abstractIllustration of the decision hyperplanes generated by TSSVM, MCVSVM, and LMLP on an artificial dataset. Display Omitted HighlightsIn the case of the singularity of the within-class scatter matrix, the drawbacks of both MCVSVM and LMLP ...
Constrained discriminant neighborhood embedding for high dimensional data feature extraction

When handling pattern classification problem such as face recognition and digital handwriting identification, image data is always represented to high dimensional vectors, from which discriminant features are extracted using dimensionality reduction ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '11: Proceedings of the 20th ACM international conference on Information and knowledge management

October 2011

2712 pages

ISBN:9781450307178

DOI:10.1145/2063576

Editors:
Bettina Berendt,
Arjen de Vries,
Wenfei Fan,
Craig Macdonald
University of Glasgow, UK
,
Iadh Ounis
University of Glasgow, UK
,
Ian Ruthven
University of Strathclyde, UK

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 October 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CIKM '11

Sponsor:

CIKM '11: International Conference on Information and Knowledge Management

October 24 - 28, 2011

Glasgow, Scotland, UK

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
217
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sprint GCook DSchmitter-Edgecombe M(2017)Unsupervised Detection and Analysis of Changes in Everyday Physical Activity DataAdvances in Biomedical Informatics10.1007/978-3-319-67513-8_6(97-122)Online publication date: 20-Oct-2017
https://doi.org/10.1007/978-3-319-67513-8_6
Sprint GCook DSchmitter-Edgecombe M(2016)Unsupervised detection and analysis of changes in everyday physical activity dataJournal of Biomedical Informatics10.1016/j.jbi.2016.07.02063:C(54-65)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1016/j.jbi.2016.07.020
Kravvaris DKermanindis KChorianopoulos K(2015)Ranking educational videos: The impact of social presence2015 IEEE 9th International Conference on Research Challenges in Information Science (RCIS)10.1109/RCIS.2015.7128895(342-350)Online publication date: May-2015
https://doi.org/10.1109/RCIS.2015.7128895
Chen YZhang JCai DLiu WHe X(2013)Nonnegative Local Coordinate Factorization for Image RepresentationIEEE Transactions on Image Processing10.1109/TIP.2012.222435722:3(969-979)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1109/TIP.2012.2224357

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten