Topic taxonomy adaptation for group profiling

ABSTRACT

A topic taxonomy is an effective representation that describes salient features of virtual groups or online communities. A topic taxonomy consists of topic nodes. Each internal node is defined by its vertical path (i.e., ancestor and child nodes) and its horizonal list of attributes (or terms). In a text-dominant environment, a topic taxonomy can be used to flexibly describe a group's interests with varying granularity. However, the stagnant nature of a taxonomy may fail to timely capture the dynamic change of a group's interest. This article addresses the problem of how to adapt a topic taxonomy to the accumulated data that reflects the change of a group's interest to achieve dynamic group profiling. We first discuss the issues related to topic taxonomy. We next formulate taxonomy adaptation as an optimization problem to find the taxonomy that best fits the data. We then present a viable algorithm that can efficiently accomplish taxonomy adaptation. We conduct extensive experiments to evaluate our approach's efficacy for group profiling, compare the approach with some alternatives, and study its performance for dynamic group profiling. While pointing out various applications of taxonomy adaption, we suggest some future work that can take advantage of burgeoning Web 2.0 services for online targeted marketing, counterterrorism in connecting dots, and community tracking.

REFERENCES

• 1: Gediminas Adomavicius , Alexander Tuzhilin, Using Data Mining Methods to Build Customer Profiles, Computer, v.34 n.2, p.74-82, February 2001
• 2: Charu C. Aggarwal , Stephen C. Gates , Philip S. Yu, On the merits of building categorization systems by supervised clustering, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.352-356, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312279]
• 3: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, ACM SIGMOD Record, v.22 n.2, p.207-216, June 1, 1993
• 4: Airoldi, E. M., Fienberg, S. E., Joutard, C., and Love, T. M. 2006. Discovering latent patterns with hierarchical Bayesian mixed-membership models. Tech. Rep. CMU-ML-06-101, School of Computer Science, Carnegie Mellon University, Philadelphia, PA.
• 5: James Allan, Introduction to topic detection and tracking, Topic detection and tracking: event-based information organization, Kluwer Academic Publishers, Norwell, MA, 2002
• 6: Blei, D., Griffiths, T. L., Jordan, M. I., and Tenenbaum, J. B. 2003. Hierarchical topic models and the nested Chinese restaurant process. In Advances in Neural Information Processing Systems 16, S. Thrun et al., eds. MIT Press, Cambridge, MA.
• 7: David M. Blei , John D. Lafferty, Dynamic topic models, Proceedings of the 23rd international conference on Machine learning, p.113-120, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143859]
• 8: David M. Blei , Andrew Y. Ng , Michael I. Jordan, Latent dirichlet allocation, The Journal of Machine Learning Research, 3, p.993-1022, 3/1/2003
• 9: Bounsaythip, C. and Rinta-Runsala, E. 2001. Overview of data mining for customer behavior modeling. http://virtual.vtt.fi/inf/julkaisut/muut/2001/customerprofiling.pdf.
• 10: Lijuan Cai , Thomas Hofmann, Hierarchical document categorization with support vector machines, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031186]
• 11: Nicolò Cesa-Bianchi , Claudio Gentile , Luca Zaniboni, Hierarchical classification: combining Bayes with SVM, Proceedings of the 23rd international conference on Machine learning, p.177-184, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143867]
• 12: Nicolò Cesa-Bianchi , Claudio Gentile , Luca Zaniboni, Incremental Algorithms for Hierarchical Classification, The Journal of Machine Learning Research, 7, p.31-54, 12/1/2006
• 13: Deepayan Chakrabarti , Ravi Kumar , Andrew Tomkins, Evolutionary clustering, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150467]
• 14: Soumen Chakrabarti , Byron Dom , Rakesh Agrawal , Prabhakar Raghavan, Scalable feature selection, classification and signature generation for organizing large text databases into hierarchical topic taxonomies, The VLDB Journal — The International Journal on Very Large Data Bases, v.7 n.3, p.163-178, August 1998 [doi>10.1007/s007780050061]
• 15: Chen, M.-C., Chiu, A.-L., and Chang, H.-H. 2005. Mining changes in customer behavior in retail marketing. Expert Syst. Appl. 28, 773--781.
• 16: Shui-Lung Chuang , Lee-Feng Chien, A practical web-based approach to generating topic hierarchy for text segments, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031193]
• 17: Ofer Dekel , Joseph Keshet , Yoram Singer, Large margin hierarchical classification, Proceedings of the twenty-first international conference on Machine learning, p.27, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015374]
• 18: Dhillon, I. S., Fan, J., and Guan, Y. 2001. Efficient clustering of very large document collections. In Data Mining for Scientific and Engineering Applications. Kluwer Academic.
• 19: Susan Dumais , Hao Chen, Hierarchical classification of Web content, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.256-263, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345593]
• 20: George Forman, An extensive empirical study of feature selection metrics for text classification, The Journal of Machine Learning Research, 3, 3/1/2003
• 21: Stephen C. Gates , Wilfried Teiken , Keh-Shin F. Cheng, Taxonomies by the numbers: building high-performance taxonomies, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099703]
• 22: Daniel Gruhl , R. Guha , David Liben-Nowell , Andrew Tomkins, Information diffusion through blogspace, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988739]
• 23: Thomas Hofmann, The Cluster-Abstraction Model: Unsupervised Learning of Topic Hierarchies from Text Data, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.682-687, July 31-August 06, 1999
• 24: Hwang, F. and Richards, D. 1992. The Steiner tree problem. Ann. Discrete Math. 53.
• 25: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 26: Daphne Koller , Mehran Sahami, Hierarchically Classifying Documents Using Very Few Words, Proceedings of the Fourteenth International Conference on Machine Learning, p.170-178, July 08-12, 1997
• 27: Li, T. and Zhu, S. 2005. Hierarchical document classification using automatically generated hierarchy. In SIAM International Data Mining Conference, Newport Beach, CA.
• 28: Huan Liu , Hiroshi Motoda, Computational Methods of Feature Selection (Chapman & Hall/Crc Data Mining and Knowledge Discovery Series), Chapman & Hall/CRC, 2007
• 29: Huan Liu , Lei Yu, Toward Integrating Feature Selection Algorithms for Classification and Clustering, IEEE Transactions on Knowledge and Data Engineering, v.17 n.4, p.491-502, April 2005 [doi>10.1109/TKDE.2005.66]
• 30: Tie-Yan Liu , Yiming Yang , Hao Wan , Hua-Jun Zeng , Zheng Chen , Wei-Ying Ma, Support vector machines classification with a very large-scale taxonomy, ACM SIGKDD Explorations Newsletter, v.7 n.1, p.36-43, June 2005 [doi>10.1145/1089815.1089821]
• 31: McCallum, A. and Nigam, K. 1998. A comparison of event models for naive Bayes text classification. In AAAI-98 Workshop on Learning for Text Categorization.
• 32: Andrew McCallum , Ronald Rosenfeld , Tom M. Mitchell , Andrew Y. Ng, Improving Text Classification by Shrinkage in a Hierarchy of Classes, Proceedings of the Fifteenth International Conference on Machine Learning, p.359-367, July 24-27, 1998
• 33: Kunal Punera , Suju Rajan , Joydeep Ghosh, Automatically learning document taxonomies for hierarchical classification, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062843]
• 34: Juho Rousu , Craig Saunders , Sandor Szedmak , John Shawe-Taylor, Learning hierarchical multi-category text classification models, Proceedings of the 22nd international conference on Machine learning, p.744-751, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102445]
• 35: Miguel E. Ruiz , Padmini Srinivasan, Hierarchical neural networks for text categorization (poster abstract), Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.281-282, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312700]
• 36: Segal, E., Koller, D., and Ormoneit, D. 2001. Probabilistic abstraction hierarchies. In Advances in Neural Information Processing Systems 14. MIT Press, Vancouver, British Columbia, Canada, 913--920.
• 37: Michael J. Shaw , Chandrasekar Subramaniam , Gek Woo Tan , Michael E. Welge, Knowledge management and data mining for marketing, Decision Support Systems, v.31 n.1, p.127-137, May 1, 2001 [doi>10.1016/S0167-9236(00)00123-8]
• 38: Aixin Sun , Ee-Peng Lim, Hierarchical Text Classification and Evaluation, Proceedings of the 2001 IEEE International Conference on Data Mining, p.521-528, November 29-December 02, 2001
• 39: Lei Tang , Huan Liu, Bias Analysis in Text Classification for Highly Skewed Data, Proceedings of the Fifth IEEE International Conference on Data Mining, p.781-784, November 27-30, 2005 [doi>10.1109/ICDM.2005.34]
• 40: Lei Tang , Jianping Zhang , Huan Liu, Acclimatizing taxonomic semantics for hierarchical content classification from semantics to data-driven taxonomy, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150446]
• 41: Kristina Toutanova , Francine Chen , Kris Popat , Thomas Hofmann, Text classification in a hierarchical mixture model for small training sets, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502604]
• 42: Ioannis Tsochantaridis , Thomas Hofmann , Thorsten Joachims , Yasemin Altun, Support vector machine learning for interdependent and structured output spaces, Proceedings of the twenty-first international conference on Machine learning, p.104, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015341]
• 43: Sriharsha Veeramachaneni , Diego Sona , Paolo Avesani, Hierarchical Dirichlet model for document classification, Proceedings of the 22nd international conference on Machine learning, p.928-935, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102468]
• 44: Ke Wang , Senqiang Zhou , Shiang Chen Liew, Building Hierarchical Classifiers Using Class Proximity, Proceedings of the 25th International Conference on Very Large Data Bases, p.363-374, September 07-10, 1999
• 45: Andreas S. Weigend , Erik D. Wiener , Jan O. Pedersen, Exploiting Hierarchy in Text Categorization, Information Retrieval, v.1 n.3, p.193-216, October 1999 [doi>10.1023/A:1009983522080]
• 46: Wahyu Wibowo , Hugh E. Williams, Strategies for minimising errors in hierarchical web categorisation, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584878]
• 47: Yiming Yang , Jan O. Pedersen, A Comparative Study on Feature Selection in Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.412-420, July 08-12, 1997
• 48: Yiming Yang , Jian Zhang , Bryan Kisiel, A scalability analysis of classifiers in text categorization, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860455]
• 49: Li Zhang , ShiXia Liu , Yue Pan , LiPing Yang, InfoAnalyzer: a computer-aided tool for building enterprise taxonomies, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031263]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing
          Subjects: Text analysis

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

General Terms:
Algorithms, Experimentation, Management

Keywords:
Topic taxonomy, dynamic profiling, group interest, taxonomy adjustment, text hierarchical classification