i Ti uOttawa L’Université canadienne Canada’s university a FACULTE DES ETUDES SUPERIEURES peng FACULTY OF GRADUATE AND ET POSTOCTORALES uOttawa POSDOCTORAL STUDIES L’Université canadienne Canada’s university Svetlana Kiritchenko AUTEUR DE LA THESE / AUTHOR OF THESIS Ph. (Computer Science) GRADE / DEGREE School of Information Technology and Engineering FACULTE, ECOLE, DEPARTEMENT / FACULTY, SCHOOL, DEPARTMENT Hierarchical Text Categorization and its Application to Bioinformatics TITRE DE LA THESE / TITLE OF THESIS Stan Matwin DIRECTEUR (DIRECTRICE) DE LA THESE / THESIS SUPERVISOR Fazel Famili CO-DIRECTEUR (CO-DIRECTRICE) DE LA THESE / THESIS CO-SUPERVISOR EXAMINATEURS (EXAMINATRICES) DE LA THESE / THESIS EXAMINERS Nathalie Japkowicz John Oommen Hagit Shatkay Marcel Turcotte Gary W. Slater LE DOYEN DE LA FACULTE DES ETUDES SUPERIEURES ET POSTDOCTORALES / DEAN OF THE FACULTY OF GRADUATE AND POSTDOCORAL STUDIES Hierarchical Text Categorization and Its Application to Bioinformatics by Svetlana Kiritchenko Thesis submitted to the Faculty of Graduate and Postdoctoral Studies In partial fulfillment of the requirements For the Ph. degree in Computer Science School of Information Technology and Engineering Faculty of Engineering University of Ottawa ivi Library and Bibliotheque et Archives Canada Archives Canada Published Heritage Direction du Branch Patrimoine de l'édition 395 Wellington Street 395, rue Wellington Ottawa ON K1A 0N4 Ottawa ON K1A 0N4 Canada Canada Your file Votre référence ISBN: 978-0-494-15026-9 Our file Notre référence ISBN: 978-0-494-15026-9 NOTICE: AVIS: The author has granted a non- L'auteur a accordé une licence non exclusive exclusive license allowing Library permettant a la Bibliotheque et Archives and Archives Canada to reproduce, Canada de reproduire, publier, archiver, publish, archive, preserve, conserve, sauvegarder, conserver, transmettre au public communicate to the public by par télécommunication ou par I'Internet, préter, telecommunication or on the Internet, distribuer et vendre des théses partout dans loan, distribute and sell theses le monde, a des fins commerciales ou autres, worldwide, for commercial or non- sur support microforme, papier, électronique commercial purposes, in microform, et/ou autres formats.
paper, electronic and/or any other formats. The author retains copyright L'auteur conserve la propriété du droit d'auteur ownership and moral rights in et des droits moraux qui protége cette these. Neither the thesis Ni la thése ni des extraits substantiels de nor substantial extracts from it celle-ci ne doivent être imprimés ou autrement may be printed or otherwise reproduits sans son autorisation. reproduced without the author's permission.
In compliance with the Canadian Conformément a la loi canadienne Privacy Act some supporting sur la protection de la vie privée, forms may have been removed quelques formulaires secondaires from this thesis. ont été enlevés de cette these. While these forms may be included Bien que ces formulaires in the document page count, aient inclus dans la pagination, their removal does not represent il n'y aura aucun contenu manquant. any loss of content from the thesis.
Canada © Svetlana Kiritchenko, Ottawa, Canada, 2006 Abstract In a hierarchical categorization problem, categories are partially ordered to form a hier- archy. In this dissertation, we explore two main aspects of hierarchical categorization: learning algorithms and performance evaluation. We introduce the notion of consistent hierarchical classification that makes classification results more comprehensible and easily interpretable for end-users. Among the previously introduced hierarchical learning algo- rithms, only a local top-down approach produces consistent classification.
The present work extends this algorithm to the general case of DAG class hierarchies and possible internal class assignments. In addition, a new global hierarchical approach aimed at performing consistent classification is proposed. This is a general framework of convert- ing a conventional “flat” learning algorithm into a hierarchical one. An extensive set of experiments on real and synthetic data indicate that the proposed approach significantly outperforms the corresponding “flat” as well as the local top-down method.
For eval- uation purposes, we use a novel hierarchical evaluation measure that is superior to the existing hierarchical and non-hierarchical evaluation techniques according to a number of formal criteria. Also, this dissertation presents the first endeavor of applying the hierarchical text categorization techniques to the tasks of bioinformatics. Three bioinformatics problems are addressed. The objective of the first task, indexing biomedical articles with Medi- cal Subject Headings (MeSH), is to associate documents with biomedical concepts from the specialized vocabulary of MeSH.
In the second application, we tackle a challeng- ing problem of gene functional annotation from biomedical literature. Our experiments demonstrate a considerable advantage of hierarchical text categorization techniques over the “flat” method on these two tasks. In the third application, our goal is to enrich the analysis of plain experimental data with biological knowledge. In particular, we incorpo- rate the functional information on genes directly into the clustering process of microarray data with the outcome of an improved biological relevance and value of clustering results.
ii Acknowledgements First, I wish to express my sincere gratitude to my supervisors, Pr. Stan Matwin and Pr. I am indebted to Stan who has taught me what it means to be a researcher and has provided support, encouragement, and valuable criticism through all these years. I thank Fazel for introducing me to the exciting science of bioinformatics, for generously sharing his knowledge and expertise in this area, and for giving professional advice.
I would also like to thank the members of my committee, Pr. Nathalie Japkowicz, Pr. John Oommen, and Pr. Marcel Turcotte, for their thoughtful comments and insightful discussions that help me considerably improve this dissertation.
My very special thanks go to Pr. Richard Nock from the Université Antilles-Guyane who contributed several ideas on hierarchical learning. Working with Richard was a very stimulating and fun experience. In fact, this one-month collaboration became a turning point in my research.
Also, I had a privilege to work with many wonderful people from the National Re- search Council of Canada (NRC). In particular, I would like to thank the Integrated Reasoning group at the Institute for Information Technology and especially the BioMiner team for their professional and friendly support and help with my research. I have also greatly benefited from the motivating discussions with outstanding biologists at the In- stitute for Biological Sciences (IBS) and the Biotechnology Research Institute (BRI), es- pecially Dr. Roy Walker, Brandon Smith, Dr.
Maureen O’Connor, Dr. Anne Lenferink, and Dr. Grateful acknowledgments are made for AmikaNow! Corporation, its president Dr. Suhayya Abu-Hakima and the whole team of great professionals for their interest in my work, support and cooperation.
My fellow students from the University of Ottawa, Fernanda Caropreso, Marina Sokolova, Magda Widlak, Vivi Nastase, Anna Kazantseva, Jelber Sayyad, Quintin Ar- mour, helped me in many different ways providing much needed support, advice, and friendship. Thanks are also due to the researchers from all over the world, who generously made their software available for the present research: Erin Allwein, Robert Schapire, and Yoram Singer (BoosTexter), Ross Quinlan (C4.5), Amanda Clare (multi-label and hier- archical extensions to C4. Last, but not least, Ï am very grateful to my family, my parents who always believed in me and encouraged through all the way, and my husband, Misha, who made everything possible to help me make it this far. ili The financial support during the course of my graduate work was provided by Natural Sciences and Engineering Research Council of Canada (NSERC), Communications and Information Technology Ontario (CITO), the Government of Ontario, the University of Ottawa, AmikaNow! Corporation, and National Research Council of Canada (NRC).
iv Contents 1 Introduction FfCƠO‹HW{N›0© 1. HH HH ng nà k kg N kg 1.2 Hierarchical text categorization .1 Hierarchical text categorization .2 Hierarchical text categorization in bioinformatics. RẶ&ä Specifics of hierarchical text categorization 11 2.1 Hierarchies: ontologies, taxonomies, thesauri .4 Multi-class categorization .9 Multi-label categorization ©.ee 16 Previous work 3.1 Document representation and feature selection .1 Hierarchical global feature selection.2 Hierarchical local feature selection.1 Global approaches to hierarchical text learning.2 Local approaches to hierarchical text learning. Q Q n ạ gà g ki kg kg va 3.5 Text learning in bioinfiormatiCS.3 Named entity recognition.4 Entity relationship detection.6 Gene expression analysis .7 Creating/maintaining knowledge databases.
peeKia 53 4 Hierarchical learning algorithms 55 4.1 Generalized hierarchical local approach. 56 4,2 New hierarchical global approach .MH, a boosting algorithm for multi-class multi-label classification. ce eee ene 62 4.2 Finding high-quality thresholds for multi-label AdaBoost.3 Other global hierarchical approaches. 79 Hierarchical evaluation measure 80 5.1 Desired properties of a hierarchical evaluation measure .2 New hierarchical evaluation measure .3 Probabilistic interpretation of precision and recall .4 Properties of the new hierarchical measure .1 Satisfying all requirements for a hierarchical evaluation measure.
kg g k k gà kg va 93 5. ch ng kg kg KV nt 93 5.44 Consistency and discriminancy .5 Allowing a trade-off between classification precision and classifica- tion depth. ee 101 Experimental results 102 6. Quà và và 104 6.
Quy g g k k kg Kia 104 6. c Q Q HQ ng kg va 105 6. c Q Q Q HQ HQ ng vn kg kg 106 6. cv cà vn kg k KV VN KV va 107 6.
“flat” learning algorithms .2 Hierarchical global vs. ng cv kg kg V kg VN Và 114 7 Hierarchical text categorization in bioinformatics 116 7.1 Indexing of biomedical literature with Medical Subject Headings.2 Medical Subject Headings (MeSH). kg kg k NV kg Kia 121 7.2 Functional annotation of genes from biomedical literature. gu kg ki ke kg va 125 7.3 Genomic databases as the source of training data .3 Gene expression analysis in the presence of background knowledge .1 K-means clustering algorithm .2 K-means enriched with functional information.
ng gà va 143 7. 148 8 Conclusions and future work 150 Appendix A 153 Appendix B 162 Vil Glossary 167 Bibliography 172 viii List of Tables 3.1 Main functions for determining feature relevancy in the feature selection PLOCESS.KV KV kia 3.3 Main functions for measuring distance in the clustering process.1 UCI datasets used in the experiments.MH with different thresholding strategies on UCI data after 25 iterations.MH with different thresholding strategies on UCI data after 200 iterations.1 Characteristics of the “flat” and existing hierarchical evaluation measures.3 The degree of consistency and discriminancy for hF-measure over “flat” F- measure for uniform class distribution, 100 examples per class, and random classifiers, 2. ng ga gà k k k k k ko 5.4 The degree of consistency and discriminancy for hF-measure over “flat” F-measure for uniform class distribution, 1000 examples per class, and random classifiers.0 The degree of consistency and discriminancy for hF-measure over “flat” F-measure for imbalanced class distribution (5:1), 100 examples per class, and random classifiers.6 The degree of consistency and discriminancy for hF-measure over “flat” F- measure for imbalanced class distribution (10:1), 100 examples per class, and random classifiers.7 The degree of consistency and discriminancy for hF-measure over “flat” F-measure for imbalanced leaf class distribution (10:1), 100 examples per class, and random classifiers.8 The degree of consistency and discriminancy for hF-measure over “flat” F-measure for uniform class distribution, 100 examples per class, and “re- alistic” classification results (correct prediction is twice as probable as 12a E6.9 The degree of consistency and discriminancy for hF-measure over “flat” F-measure for uniform class distribution, 100 examples per class, and “re- alistic” classification results (correct prediction is 5 times as probable as incorrect one).1 Characteristics of the text corpora used in the experiments.2 Comparative characteristics of the three learning algorithms: hierarchical local, hierarchical global, and “ñat”.3 Performance of the hierarchical local and “flat” AdaBoost.MH on real text corpora and synthetic data. HQ eee eee 6.4 Performance of the hierarchical global and “flat” AdaBoost.MH on real text corpora and synthetic data.5 Performance of the hierarchical local and global AdaBoost.MH on real text corpora and synthetic data.
ee ee vo 7.1 MeSH hierarchical trees.2 Characteristics of the OHSUMED data.3 Performance of the “flat”, hierarchical local, and hierarchical global Ad- aBoost.MH on the OHSUMED data.4 GO annotations for yeast genes contained in file gene_association.5 Information on yeast genes from the SGD database.6 Training set formed from the information on yeast genes from the SGD 371212. kia ii ặHHAaA.7 Characteristics of the MEDLINEdata .