Building a topic hierarchy using the bag-of-related-words representation

ABSTRACT

A simple and intuitive way to organize a huge document collection is by a topic hierarchy. Generally two steps are carried out to build a topic hierarchy automatically: 1) hierarchical document clustering and 2) cluster labeling. For both steps, a good textual document representation is essential. The bag-of-words is the common way to represent text collections. In this representation, each document is represented by a vector where each word in the document collection represents a dimension (feature). This approach has well known problems as the high dimensionality and sparsity of data. Besides, most of the concepts are composed by more than one word, as "document engineering" or "text mining". In this paper an approach called bag-of-related-words is proposed to generate features compounded by a set of related words with a dimensionality smaller than the bag-of-words. The features are extracted from each textual document of a collection using association rules. Different ways to map the document into transactions in order to allow the extraction of association rules and interest measures to prune the number of features are analyzed. To evaluate how much the proposed approach can aid the topic hierarchy building, we carried out an objective evaluation for the clustering structure, and a subjective evaluation for topic hierarchies. All the results were compared with the bag-of-words. The obtained results demonstrated that the proposed representation is better than the bag-of-words for the topic hierarchy building.

References

1. R. Agrawal and R. Srikant. Fast algorithms for mining association rules in large databases. In VLDB'94: International Conference on Very Large Data Bases, pages 487--499. Morgan Kaufmann Publishers Inc., 1994.
2. R. A. Baeza-Yates and B. A. Ribeiro-Neto. Modern Information Retrieval. ACM Press / Addison-Wesley, 1999.
3. J. Blanchard, F. Guillet, R. Gras, and H. Briand. Using information-theoretic measures to assess association rule interestingness. In ICDM'05: Internation Conference on Data Mining, pages 66--73, 2005.
4. M. F. Caropreso, S. Matwin, and F. Sebastiani. A learner-independent evaluation of the usefulness of statistical phrases for automated text categorization. Text databases & document management: theory & practice, pages 78--102, 2001.
5. A. L. C. Carvalho, E. S. Moura, and P. Calado. Using statistical features to find phrasal terms in text collections. Journal of Information and Data Management, 1(3):583--597, 2010.
6. A. Doucet and H. Ahonen-Myka. Non-contiguous word sequences for information retrieval. In MWE'04: Workshop on Multiword Expressions: Integrating Processing, MWE'04, pages 88--95. Association for Computational Linguistics, 2004.
7. L. Geng and H. J. Hamilton. Interestingness measures for data mining: A survey. ACM Computing Surveys, 38(3):9, 2006.
8. F. Guillet and H. J. Hamilton, editors. Quality Measures in Data Mining, volume 43 of Studies in Computational Intelligence. Springer, 2007.
9. V. Kashyap, C. Ramakrishnan, C. Thomas, and A. P. Sheth. Taxaminer: an experimentation framework for automated taxonomy bootstrapping. International Journal of Web and Grid Services, 1(2):240--266, 2005.
10. Y. Lie, H. T. Loh, and W. G. Lu. Deriving taxonomy from documents at sentence level. In A. H. do Prado and E. Ferneda, editors, Emerging Technologies of Text Mining: Techniques and Applications, chapter 5, pages 99--119. Information Science Reference, 1 edition, 2007.
11. P. D. McNicholas, T. B. Murphy, and M. O'Regan. Standardising the lift of an association rule. Computational Statistics & Data Analysis, 52(10):4712--4721, 2008.
12. D. Mladenic and M. Grobelnik. Word sequences as features in text-learning. In ERK'98: Electrotechnical and Computer Science Conference, pages 145--148, 1998.
13. M. F. Moura and S. O. Rezende. A simple method for labeling hierarchical document clusters. In IASTED'10: International Conference on Artificial Intelligence and Applications (IAI 2010), pages 363--371, 2010.
14. G. Salton. Automatic text processing: the transformation, analysis, and retrieval of information by computer. Addison-Wesley Longman Publishing Co., Inc., 1989.
15. F. F. Santos, V. O. de Carvalho, and S. O. Rezende. Selecting candidate labels for hierarchical document clusters using association rules. In Springer-Verlag, editor, MICAI'10: Mexican International Conference on Artificial Intelligence, 2010.
16. M. V. B. Soares, R. C. Prati, and M. C. Monard. PreTexT II: Descrição da reestruturação da ferramenta de pré-processamento de textos. Technical Report 333, ICMC-USP, 2008.
17. C.-M. Tan, Y.-F. Wang, and C.-D. Lee. The use of bigrams to enhance text categorization. Information Processing and Management, 38(4):529--546, 2002.
18. P.-N. Tan, V. Kumar, and J. Srivastava. Selecting the right interestingness measure for association patterns. In ACM SIGKDD'2002: International Conferenceon Knowledge Discovery and Data Mining, pages 32--41. ACM, 2002.
19. R. Tesar, V. Strnad, K. Jezek, and M. Poesio. Extending the single words-based document model: a comparison of bigrams and 2-itemsets. In DocEng'06: ACM Symposium on Document Engineering, pages 138--146, 2006.
20. J. Wu, H. Xiong, and J. Chen. Adapting the right measures for k-means clustering. In SIGKDD'09: Proceeding of the International Conference on Knowledge Discovery and Data Mining, pages 877--886. ACM, 2009.
21. Z. Yang, L. Zhang, J. Yan, and Z. Li. Using association features to enhance the performance of naíve bayes text classifier. In ICCIMA '03: International Conference on Computational Intelligence and Multimedia Applications, page 336. IEEE Computer Society, 2003.
22. X. Zhang and X. Zhu. A new type of feature - loose n-gram feature in text categorization. In IbPRIA'07: Iberian Conference on Pattern Recognition and Image Analysis, pages 378--385. Springer, 2007.
23. Y. Zhao and G. Karypis. Evaluation of hierarchical clustering algorithms for document datasets. In CIKM '02: International Conference on Information and Knowledge Management, pages 515--524. ACM Press, 2002.

Index Terms

• Information systems

  • Information retrieval

    • Retrieval tasks and goals

      • Clustering and classification

  • Information systems applications

    • Data mining

      • Clustering