Generalization of the Association Analysis Framework
National Science Foundation Award Number: IIS-0916439 (August 1, 2009 - July 31, 2012)
Personnel:
Vipin Kumar, PI
Department of Computer Science and Engineering
4-192, EE/CSci Building
University of Minnesota
Minneapolis, MN 55455
Phone (612) 625 0726
E-mail: kumar at cs.umn.edu URL: http://www.cs.umn.edu/~kumar
Michael Steinbach, co-PI
Department of Computer Science and Engineering
5-225C, EE/CSci Building
University of Minnesota
Minneapolis, MN 55455
Phone (612) 626-7503
E-mail: steinbac at cs.umn.edu URL: http://www-users.cs.umn.edu/~steinbac/
List of Supported Students:
Graduate student(s):
- Gang Fang
- Gowtham Atluri
- Rohit Gupta
- Sanjoy Dey
- Vanja Paunic
- Wen Wang
Undergraduate Students:
- Benjamin Oatley
- Xiaoye Liu
- Garima Sharma
- Matt Challou
Collaborators:
- Brian Van Ness , Professor, Department of Genetics, Cell Biology, and Development, University of Minnesota.
- Kelvin Lim, Professor, Department of Psychiatry, University of Minnesota.
- Angus MacDonald , Associate Professor of Psychology, University of Minnesota.
Project Activities and Findings:
The area of data mining known as association analysis seeks to find patterns that describe the
relationships among the binary attributes (variables) used to characterize a set of objects. The
iconic example is market basket data, where the objects are transactions consisting of sets of
items purchased by a customer, and the attributes are binary variables that indicate whether or not
an item was purchased by a particular customer. The patterns are either sets of items that are
frequently purchased together (frequent itemset patterns) or rules that capture the fact that the
purchase of one set of items often implies the purchase of a second set of items (association rule
patterns). A key strength of association pattern mining is that the potentially exponential nature of
the search can often be made tractable by using support based pruning of patterns, i.e.,
eliminating patterns supported by few transactions. Efforts to date have created a well-developed
conceptual (theoretical) foundation and an efficient set of algorithms. The framework that has
been created has been extended well beyond the original application to market basket data to
encompass new applications.
Despite the solid foundations of association analysis and the potential economic and
intellectual benefits of pattern discovery and its various applications, this group of techniques is
not widely used as a data analysis tool in most scientific and commercial domains. The reason is
that there are many areas, such as those involving continuous and dense data with labels, where
such techniques would be very useful, but cannot currently be easily and effectively applied. Our
work on this project aims to extend association analysis to be more widely applicable. Our focus
has been on biomedical data, although most of our work could be adapted to non-biological data
as well.
Publications:
- Gang Fang, Wen Wang, Benjamin Oatley, Brian Van Ness, Michael Steinbach and Vipin Kumar, Characterizing Discriminative Patterns , Manuscript, arXiv: 1102.4104, communicated Feb 2011.
- Gang Fang, Wen Wang, Vanja Paunic, Benjamin Oately, Majda Haznadar, Michael Steinbach, Brian Van Ness, Chad L. Myers and Vipin Kumar, Construction and Functional Analysis of Human Genetic Interaction Networks with Genome-wide Association Data .
- Gang Fang, Michael Steinbach, Chad L. Myers and Vipin Kumar, Integration of Differential Gene-combination Search and Gene Set Enrichment Analysis: A General Approach.
- Michael Steinbach, Haoyu Yu, Gang Fang, Vipin Kumar, Using Constraints to Generate and Explore Higher Order Discriminative Patterns, 15th Pacific-Asia Conference on Knowledge Discovery in Databases (PAKDD 2011) Shenzhen, China, pp. 338-350, May 24-27.
- Michael Steinbach, Haoyu Yu, and Vipin Kumar, Identification of Co-occurring Insertions in Cancer Genomes Using Association Analysis , International Journal of Data Mining and Bioinformatics special issue for 2nd International Workshop on Data Mining for Biomarker Discovery (DMBD 2010), to appear in 2011.
- Bonnie Westra, Sanjoy Dey, Gang Fang, Michael Steinbach, Kay Savik, Cristina Oancea and Vipin Kumar, Interpretable Predictive Models for Knowledge Discovery from Home Care Electronic Health Records, Journal of Healthcare Engineering, pp. 55-74, Volume 2, Number 1 / March 2011.
- Gowtham Atluri, Jeremy Bellay, Gaurav Pandey, Chad Myers, Vipin Kumar, Discovering Coherent Value Bicliques In Genetic Interaction Data , In Proceedings of 9th International Workshop on Data Mining in Bioinformatics (BIOKDD'10), held in conjunction with 16th ACM Conference on Knowledge Discovery and Data mining (KDD), Washington D.C, July 2010.
- Subspace Differential Coexpression Analysis: Problem Definition and a General Approach, Gang Fang, Rui Kuang, Gaurav Pandey, Michael Steinbach, Chad L. Myers, and Vipin Kumar, Proceedings of the 15th Pacific Symposium on Biocomputing (PSB), 15:145-156, 2010.
- Gang Fang, Gaurav Pandey, Wen Wang, Manish Gupta, Michael Steinbach, Vipin Kumar, Mining Low-Support Discriminative Patterns from Dense and High-Dimensional Data, IEEE Transactions on Knowledge and Data Engineering (TKDE), to appear. Available in vol. 99, no. PrePrints, 2010.
- Rohit Gupta, Smita Agrawal, Navneet Rao, Ze Tian, Rui Kuang, Vipin Kumar, Integrative Biomarker Discovery for Breast Cancer Metastasis from Gene Expression and Protein Interaction Data Using Error-tolerant Pattern Mining, In Proceedings of the International Conference on Bioinformatics and Computational Biology (BICoB), March 2010
- Rohit Gupta, Navneet Rao, Vipin Kumar, Discovery of Error-tolerant Biclusters from Noisy Gene Expression Data In Proceedings of 9th International Workshop on Data Mining in Bioinformatics (BIOKDD'10), held in conjunction with 16th ACM Conference on Knowledge Discovery and Data mining (KDD), Washington D.C, July 2010.
Contributions within discipline:
We have created a number of new algorithms for characterizing discriminative patterns, including creating and analyzing genetic interaction data sets from SNP data, and finding co-occurrence patterns among insertions in tumor genomes. Some of the techniques we developed were for data with class labels, while other techniques apply to unlabeled data. We also created novel approaches for analyzing the maximum discriminating power of discriminating patterns and incorporated Gene Set Enrichment Analysis into our analysis approach.
Contributions to Human Resource Development:
The project has provided partial support for 6 graduate students who are pursuing studies in computer science. It has also provided support for four undergraduate students.
Contributions to Resources for Research and Education:
Software for several of the algorithms has been made available via the web. This will allow other researchers to use these algorithms and to build on the techniques we have developed.
We presented a graduate level seminar course, Mining Biomedical Data Sets , that incorporated some of our work, in Spring 2011. More specifically, our work on discriminative patterns was presented in some detail and a number of projects selected by students were related to this topic.
Invited Talks:
Mining Scientific Data: Past, Present, and Future, Keynote Presentation at SIAM International Conference on Data Mining 2010, April 29 - May 1, 2010, Columbus, Ohio