Sử dụng domain knowledge cho text mining - Aynur Dayanik

USING DOMAIN KNOWLEDGE FOR TEXT MINING BY AYNUR DAYANIK A dissertation submitted to the Graduate School—New Brunswick Rutgers, The State University of New Jersey in partial fulfillment of the requirements for the degree of Doctor of Philosophy Graduate Program in Computer Science Written under the direction of Craig Nevill-Manning and approved by \ucd—_— wh — New Brunswick, New Jersey May, 2006 UMI Number: 3240205 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted. Also, if unauthorized copyright material had to be removed, a note will indicate the deletion.

® UMI UMI Microform 3240205 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P.

Box 1346 Ann Arbor, MI 48106-1346 ABSTRACT OF THE DISSERTATION Using Domain Knowledge for Text Mining by Aynur Dayanik Dissertation Director: Craig Nevill-Manning Text mining concerns the automated analysis of textual data to store, retrieve, organize and extract useful information from textual data. Text mining systems usually rely on document collections or training data prepared for a particular application. However, in practice, external knowledge is also available in external databases, reference books, web pages and many other sources. This thesis concerns the use of external knowledge for text mining to improve the performance of text mining systems.

First we focus on using domain knowledge for clustering and text retrieval for bioin- formatics. We describe a method for clustering biological data by exploiting the inter- linked structure of biological data. By constructing a network of biological sequences, structures and literature with pairwise relationships, we infer clusters of related articles, sequences and structures by graph partitioning. The resulting clusters exhibit strong topicality, as measured by both a quantitative and qualitative manual evaluation on several biological domains.

We also present one application of our approach to the problem of finding scientific papers that describe functions of particular genes. Finally, we study incorporating domain knowledge for text classification. We pro- pose combining domain knowledge with training examples in a Bayesian framework. Domain knowledge is used to specify a prior distribution for parameters of a logistic ii regression model, and labeled training data is used to find the mode of the poste- rior distribution.

We show experimentally on three text categorization data sets that this approach can produce effective classifiers, particularly when little training data is available. iii Acknowledgements I thank my advisor Craig Nevill-Manning for his guidance, motivation, and support. I also thank Casimir Kulikowski, David Madigan and David D. Lewis, the other members of my dissertation committee, for their time to read this thesis, and for their insightful comments.

I am particularly grateful to David Lewis and David Madigan for their guid- ance and invaluable feedback on the text categorization and Bayesian logistic regression part of the thesis. I am grateful to Fred Roberts and Paul Kantor for extending me an opportunity to work at DIMACS in the last two years and providing financial support for me. My special thanks goes to Alex Genkin, Vladimir Menkov, Dmitriy Fradkin, Suhrid Balakrishnan and Andrei Anghelescu for collaborations at DIMACS. My special gratitude goes to Michael Grigoriadis, who has been very helpful with his comforting advices in the early years of my graduate studies at Rutgers.

I thank Haym Hirsh, Casimir Kulikowski and Ilya Muchnik for supervising me on independent research projects, which were sources of invaluable experience for me. My deepest thanks and gratitude go to my husband, Savas, and my parents who have constantly supported me. The material in Part I is based upon work supported by the National Science Foun- dation under Grant No. I thank David Synder for evaluating the sample clusters in this part, and for his helpful comments.

The work in Part II was supported under funds provided by the KD-D group for a project at DIMACS on Monitoring Message Streams, funded through National Science Foundation grant EIA-0087022 to Rutgers University. The views expressed in this thesis are those of the author, and do not necessarily represent the views of the sponsoring agency. iv Table of Contents Abstract 2. ee ii Acknowledgements.

eee es iv List of Tables. 0 ee ix List of Figures. Q Q Q Q LH Q HH ng gà và Q a k va xvii 1. Information Retrieval for Bioinflormatlqs.ẼẶ es 3 I Using Domain Knowledge for Genomics Information Retrieval 5 2.

Q Q Q nu ng gà k k k ki v Kia 6 2. HQ HQ kg KV 7 2. Biological Data Types and Their Relationships. Sequence-Sequence Relationships.

Structure-Structure Relationships. Literature-Literature Relationships. Structure-Sequence Relationships. Sequence-Literature Relationships.

Structure-Literature Relatonships. A Network of Literature, Sequences, and Structures. Clustering in Relational Biological Data. rà ga g và va 14 3.

Constructing the Graph. The BioIR System 2. Q Q Q gà gà và và 20 3. Identifying Descriptive Terms From Abstracts.

Experimental Results and Discussion.1, Evaluation of Overall Clustering Quality.00 eee ee ee 23 3. Correlation between Clusters and Go Categories - Go Term As- signment to Clusters. Analysis of Abstracts by Descriptive Keywords. HQ HQ HH ng kg kg kh à IA 33 3.

Partitioning a Graph of Sequences, Structures and Abstracts for In- formation Retrieval. eee ee es 36 4. cv kg cv n v kg V k kg k Kia 36 4.2, Ad Hoc Retrieval Task. ee ee ee es 37 4.

Q Q HQ HQ n kg cv kg TK k kia 39 4. Constructing the Graph. HQ nu ee 46 4. Experiment Using MG.

Experiment Using Clusters. eek kia 4ï Experimentl. Q Q Q Q Q HQ v kY Kia 48 vì Experiment 2. c Q Q ng Q nu cv nà KV kg kà va 49 Domain Expert AnaÌyslS.

“(đ((Á 55 II Using Domain Knowledge for Text Classification 56 5. Text Categorization and Bayesian Logistic Regression. Bayesian Logistic Regression. Choice of Hyperparameter.

Using Domain Knowledge for Text Classification. ee kg kg 64 6. Incorporating Domain Knowledge. No Domain Knowledge.

Using Domain Knowledge as Examples. Priors From Domain Knowledge. 67 Variance-Setting Methods .0+005 69 Mode-Setting Methods. ee ee 70 Choice of (DKRW, Hyperparameter) Pair.

ee ee ee es 72 6. Alternate Supervised Learning Approaches to Text Classification 72 6.ee 73 TREC Genomics Track Biomedical Journal Articles. Q Q Q Q Q LH Quà kia 81 6. eee ee le 84 Text Representation for Bio Articles.

84 vii Text Representation for ModApte .00 02 eee 84 Text Representation for RCVl-v2. 1ã ăãa da 85 Text Processing for Prior Knowledge Documents. ce ee es 86 6. eee ee ee 89 6.

LH HH HQ ng an k kg kg kg v. Experiments on Large Training Set§S. 91 Comparing Bayesian Logistic Regression with SVMs. 91 Effectiveness with Full Training Sets and Domain Knowledge.

Experiments on Small Training Sets. 93 Training Data: 500 Random Examples. 93 Training Data: 5 Positive and 100 Random Examples. 96 Training Data: 5 Positive and 5 Random Examples.

98 Training Data: 5 Positive and their 5 Closest Negative Examples 100 Summary and Discussion of Small Training Set Experiments. Q Q Q LH HQ HQ ung k k kg kia 105 7. Bio Articles Collection Abstract vs. Full Text Representation.

Multiple Runs for Small Training Sets. Effectiveness of Cross-Validation in Choosing DKRW Values. Conclusions and Future Work. a ia II HMII AI.

128 Vita ee 135 vili List of Tables 3. Entropy and purity values for SWISS-PROT and PDB clusterings using PROSITE and SCOP classifications as references, respectively. Some of the PDB structures in p53 cluster 1674. The SCOP classification of the PDB structures are displayed to show that they are indeed related 3.

Evaluation of sample clusters by the domain expert. Scores range from 1 to 10, where 10 means all of the objects are relevant, and 1 means none of them are relevant. GO assignments of the sample clusters. In the Go term column, the Go annotation types are shown in parentheses: BP, MF and CC stand for biological_process, molecular_function and cellular.component, respec- tively.

a is the number of the particular category SWISS-PROT sequences in the cluster, n denotes the number of SWISS-PROT sequences in the cluster, and A is the actual number of the particular Go category SWISS- PROT sequences. we La aaaagaaÁI. The most significant words extracted from the MEDLINE abstracts in each cluster; sorted in ascending order of p-value. The extracted words within each sample cluster are highly topically related.

The twenty most significant Go categories extracted from the MEDLINE abstracts in each cluster; sorted in ascending order of p-value. Although only link structure of the biological databases is used to infer clusters, the individual abstracts within each cluster are highly topically related. Mean average precision results. These results were obtained as follows.

Experiment 1 formed queries by concatenating gene names and symbols from the LocusLink entries. Experiment 2 formed queries by concate- nating not only gene names and symbols from the LocusLink entries but also their variations, and filtered out the abstracts with the incorrect organisms from the result sets as described in the text. NIST supplied statistics are also shown to compare the results with those of the TREC 2003 Genomics track participants. MeSH headings used to map MEDLINE abstracts to organisms.

Summary of tested methods for incorporating domain knowledge into learning. CpKRw is a constant specifying the relative weight given domain knowledge. Full text biomedical journal articles data set ("Bio Articles”). Training sets of various sizes were drawn from the training population of 3742 articles, and classifiers were evaluated on the test set of 4175 articles.

The development set was set aside for tuning, but was not used in the experiments reported here. Category counts in the Bio Articles data for MeSH headings in A11 hi- erarchy. These category counts are computed on all 11,880 documents in our Bio Articles set. Note that since the MeSH “Tumor Cells, Cul- tured” was combined with the MeSH “Cell Line, Tumor” in November 2004, we assumed that 1329 documents associated with “Tumor Cells, Cultured” had in fact the MeSH heading “Cell Line, Tumor”.

Therefore, the corresponding numbers of articles should be adjusted accordingly. RCV1 A-B Regions data set. Small training sets of various sizes were drawn from the training population of 264,569 documents. The training set of 23,149 documents were used in large training set experiments in Section 6.

Classifiers were evaluated on the test set of 120,076 docu- ments. The development set was set aside for tuning, but was not used in the experiments reported here. Contingency table summarizes the relationship between the system clas- sifications (Retrieved/Not Retrieved) and the expert judgments (Rele- vant /Not Relevant) for a binary text categorization problem. The number of documents in the training populations.

The type of domain knowledge and the number of domain knowledge texts (total DK entries column) for computing the IDF weights in defin- ing the priors. Comparing Bayesian logistic regression (Laplace and Gaussian priors) with SVMs on three text categorization test collections using large train- ing sets and with no domain knowledge. Logistic regression models used a hyperparameter tuned by 10,2 cross-validation. Macroaveraged results for SVMs on three text categorization test collec- tions using large training sets with No DK vs.

Macroaveraged results for Bayesian logistic regression with Laplace prior on three text categorization test collections using large training sets. Results are shown for logistic regression models trained with no domain knowledge (No DK), with domain knowledge as positive examples (DK Examples), and by using domain knowledge to derive prior distribution parameters for domain knowledge features.