Article

A framework for ontology-driven subspace clustering

Authors:

Jiong YangAuthors Info & Claims

KDD '04: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining

Pages 623 - 628

https://doi.org/10.1145/1014052.1014130

Published: 22 August 2004 Publication History

Abstract

Traditional clustering is a descriptive task that seeks to identify homogeneous groups of objects based on the values of their attributes. While domain knowledge is always the best way to justify clustering, few clustering algorithms have ever take domain knowledge into consideration. In this paper, the domain knowledge is represented by hierarchical ontology. We develop a framework by directly incorporating domain knowledge into clustering process, yielding a set of clusters with strong ontology implication. During the clustering process, ontology information is utilized to efficiently prune the exponential search space of the subspace clustering algorithms. Meanwhile, the algorithm generates automatical interpretation of the clustering result by mapping the natural hierarchical organized subspace clusters with significant categorical enrichment onto the ontology hierarchy. Our experiments on a set of gene expression data using gene ontology demonstrate that our pruning technique driven by ontology significantly improve the clustering performance with minimal degradation of the cluster quality. Meanwhile, many hierarchical organizations of gene clusters corresponding to a sub-hierarchies in gene ontology were also successfully captured.

References

[1]

C. C. Aggarwal, C. Procopiuc, J. Wolf, P. S. Yu, and J. S. Park. Fast algorithms for projected clustering. In SIGMOD, 1999.]]

Digital Library

[2]

C. C. Aggarwal and P. S. Yu. Finding generalized projected clusters in high dimensional spaces. In SIGMOD, pages 70--81, 2000.]]

Digital Library

[3]

R. Agrawal, J. Gehrke, D. Gunopulos, and P. Raghavan. Automatic subspace clustering of high dimensional data for data mining applications. In SIGMOD, 1998.]]

Digital Library

[4]

A. Ben-Dor, B. Chor, R.Karp, and Z.Yakhini. Discovering Local Structure in Gene Expression Data: The Order-Preserving Submatrix Problem. In RECOMB 2002.]]

Digital Library

[5]

K. Beyer, J. Goldstein, R. Ramakrishnan, and U. Shaft. When is nearest neighbors meaningful. In Proc. of the Int. Conf. Database Theories, pages 217--235, 1999.]]

Digital Library

[6]

C. H. Cheng, A. W. Fu, and Y. Zhang. Entropy-based subspace clustering for mining numerical data. In SIGKDD, pages 84--93, 1999.]]

Digital Library

[7]

Y. Cheng and G. Church. Biclustering of expression data. In Proc. of 8th International Conference on Intelligent System for Molecular Biology, 2000.]]

Digital Library

[8]

I. S. Dhillon, Co-Clustering Documents and Words Using Bipartite Spectral Graph Partitioning. In SIGKDD, 2001.]]

Digital Library

[9]

M. Ester, H. Kriegel, J. Sander, and X. Xu. A density-bsed algorithm for discovering clusters in large spatial databases with noise. In SIGKDD, pages 226--231, 1996.]]

[10]

Gene Ontology Consortium, www.geneontology.org.]]

[11]

H.V. Jagadish, J. Madar, and R. Ng. Semantic compression and pattern extraction with fasicicles. In VLDB, pages 186--196, 1999.]]

Digital Library

[12]

J.Liu and W.Wang. Flexible clustering by tendency in high dimensional spaces. Technical Report TR03-009, Computer Science Department, UNC-CH, 2003.]]

[13]

P.T. Spellman, G.Sherlock, M.Q.Zhang, V.R.Lyer, K.Anders, M.B.Eisen, P.O.Brown, D.Botstein, and Futcher. Comprehensive identification of cell cycle-regulated genes of the yeast sacccharomyces cerevisiae by microaray hybidization. Molecular Biology of the Cell, 9:3273--3297, 1998.]]

[14]

S.Tavazoie, Jason D.Hughes, M.J.Campbell, R.J.Cho, G.M.Church. Systematic determination of genetic network architecture, Nature Genetics, 22: 281--285, 1999.]]

[15]

S. Tavazoie, J. Hughes, M. Campbell, R. Cho, and G. Church. Yeast microarry data set. In http://arep.med.harvard.edu/biclustering/yeast.matrix, 2000.]]

[16]

H. Wang, W. Wang, J. Yang, and P. Yu. Clustering by pattern similarity in large data sets, in SIGMOD, pp. 394-405, 2002.]]

Digital Library

Cited By

Patel AJain S(2021)A Partition Based Framework for Large Scale Ontology MatchingRecent Patents on Engineering10.2174/187221211366619021114141514:3(488-501)Online publication date: 19-Jan-2021
https://doi.org/10.2174/1872212113666190211141415
Sirichanya CKraisak K(2021)Semantic data mining in the information age: A systematic reviewInternational Journal of Intelligent Systems10.1002/int.2244336:8(3880-3916)Online publication date: 2-May-2021
https://doi.org/10.1002/int.22443
Paul AShill P(2018)Incorporating gene ontology into fuzzy relational clustering of microarray gene expression dataBiosystems10.1016/j.biosystems.2017.09.017163(1-10)Online publication date: Jan-2018
https://doi.org/10.1016/j.biosystems.2017.09.017
Show More Cited By

Index Terms

A framework for ontology-driven subspace clustering
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Subspace clustering for high dimensional data: a review
Special issue on learning from imbalanced datasets

Subspace clustering is an extension of traditional clustering that seeks to find clusters in different subspaces within a dataset. Often in high dimensional data, many dimensions are irrelevant and can mask existing clusters in noisy data. Feature ...
Connectedness-based subspace clustering

An algorithm for density-based subspace clustering of given data is proposed here. Unlike the existing density-based subspace clustering algorithms which find clusters using spatial proximity, existence of common high-density regions is the condition ...
Subspace clustering using affinity propagation

This paper proposes a subspace clustering algorithm by introducing attribute weights in the affinity propagation algorithm. A new step is introduced to the affinity propagation process to iteratively update the attribute weights based on the current ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '04: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining

August 2004

874 pages

ISBN:1581138881

DOI:10.1145/1014052

General Chairs:
Won Kim
Cyber Database Solutions
,
Ronny Kohavi
Amazon.com
,
Program Chairs:
Johannes Gehrke
Cornell University
,
William DuMouchel
AT&T Labs Research

Copyright © 2004 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: 22 August 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

KDD04

Sponsor:

KDD04: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 22 - 25, 2004

WA, Seattle, USA

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
1,088
Total Downloads

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

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Patel AJain S(2021)A Partition Based Framework for Large Scale Ontology MatchingRecent Patents on Engineering10.2174/187221211366619021114141514:3(488-501)Online publication date: 19-Jan-2021
https://doi.org/10.2174/1872212113666190211141415
Sirichanya CKraisak K(2021)Semantic data mining in the information age: A systematic reviewInternational Journal of Intelligent Systems10.1002/int.2244336:8(3880-3916)Online publication date: 2-May-2021
https://doi.org/10.1002/int.22443
Paul AShill P(2018)Incorporating gene ontology into fuzzy relational clustering of microarray gene expression dataBiosystems10.1016/j.biosystems.2017.09.017163(1-10)Online publication date: Jan-2018
https://doi.org/10.1016/j.biosystems.2017.09.017
Chopra PKang JHong S(2013)Comparative meta-analysis between human and mouse cancer microarray data reveals critical pathwaysInternational Journal of Data Mining and Bioinformatics10.1504/IJDMB.2013.0560898:3(349-365)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1504/IJDMB.2013.056089
Bruno GFiori A(2013)MicroClAnJournal of Parallel and Distributed Computing10.1016/j.jpdc.2012.09.00873:3(360-370)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1016/j.jpdc.2012.09.008
Phukhachee TManeewongvatana S(2013)Identification of K-Tolerance Regulatory Modules in Time Series Gene Expression Data Using a Biclustering AlgorithmProceedings of the 9th International Conference on Active Media Technology - Volume 821010.1007/978-3-319-02750-0_15(146-155)Online publication date: 29-Oct-2013
https://dl.acm.org/doi/10.1007/978-3-319-02750-0_15
Bruno GFiori A(2013)Spread of Evaluation Measures for Microarray ClusteringBiological Knowledge Discovery Handbook10.1002/9781118617151.ch24(569-590)Online publication date: 27-Dec-2013
https://doi.org/10.1002/9781118617151.ch24
Peng WSun TRevankar SLi T(2012)Mining the “Voice of the Customer” for Business PrioritizationACM Transactions on Intelligent Systems and Technology10.1145/2089094.20891143:2(1-17)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1145/2089094.2089114
Madeira STeixeira MSa-Correia IOliveira A(2010)Identification of Regulatory Modules in Time Series Gene Expression Data Using a Linear Time Biclustering AlgorithmIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2008.347:1(153-165)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1109/TCBB.2008.34
Jain A(2010)Data clusteringPattern Recognition Letters10.1016/j.patrec.2009.09.01131:8(651-666)Online publication date: 1-Jun-2010
https://dl.acm.org/doi/10.1016/j.patrec.2009.09.011
Show More Cited By

View Options

Get Access

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.

Media

Figures

Other

Tables

View Table of Contents