A consensus based approach to constrained clustering of software requirements

ABSTRACT

Managing large-scale software projects involves a number of activities such as viewpoint extraction, feature detection, and requirements management, all of which require a human analyst to perform the arduous task of organizing requirements into meaningful topics and themes. Automating these tasks through the use of data mining techniques such as clustering could potentially increase both the efficiency of performing the tasks and the reliability of the results. Unfortunately, the unique characteristics of this domain, such as high dimensional, sparse, noisy data sets, resulting from short and ambiguous expressions of need, as well as the need for the interactive engagement of stakeholders at various stages of the process, present difficult challenges for standard clustering algorithms. In this paper, we propose a semi-supervised clustering framework, based on a combination of consensus-based and constrained clustering techniques, which can effectively handle these challenges. Specifically, we provide a probabilistic analysis for informative constraint generation based on a co-association matrix, and utilize consensus clustering to combine multiple constrained partitions in order to generate high-quality, robust clusters. Our approach is validated through a series of experiments on six well-studied TREC data sets and on two sets of user requirements.

REFERENCES

• 1: Banerjee, A. and Ghosh, J. 2002. Frequency sensitive competitive learning for clustering on high-dimensional hyperspheres. In Proc. IEEE Int. Joint Conf. on Neural Networks (Honolulu, Hawaii, May 2002), pp. 1590--1595.
• 2: Sugato Basu , Arindam Banerjee , Raymond J. Mooney, Semi-supervised Clustering by Seeding, Proceedings of the Nineteenth International Conference on Machine Learning, p.27-34, July 08-12, 2002
• 3: Basu, S., Banerjee, A., and Mooney, R. J. 2004. Active semisupervision for pairwise constrained clustering. In Proc. of the 4th SIAM International Conference on Data Mining (Orlando, FL, 2004), pp. 333--344.
• 4: Sugato Basu , Mikhail Bilenko , Raymond J. Mooney, A probabilistic framework for semi-supervised clustering, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014062]
• 5: Bennett, K. P., Bradley, P. S. and Demiriz, 2000. A. Constrained K-Means Clustering. Microsoft Technical Report, May 2000.
• 6: Mikhail Bilenko , Sugato Basu , Raymond J. Mooney, Integrating constraints and metric learning in semi-supervised clustering, Proceedings of the twenty-first international conference on Machine learning, p.11, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015360]
• 7: Castro-Herrera, C., Duan, C., Cleland-Huang, J. and Mobasher, B. 2008. Using Data Mining and Recommender Systems to Facilitate Large-Scale, Open, and Inclusive Requirements Elicitation Processes, Short Paper, IEEE Conf. on Requirements Eng., (Barcelona, Spain, Sept. 2008).
• 8: Jane Cleland-Huang , Bamshad Mobasher, Using data mining and recommender systems to scale up the requirements process, Proceedings of the 2nd international workshop on Ultra-large-scale software-intensive systems, p.3-6, May 10-11, 2008, Leipzig, Germany [doi>10.1145/1370700.1370702]
• 9: Cohn, D., Caruana R., and McCallum, A. 2003. Semi-supervised clustering with user feedback. Technical Report TR2003-1892, Cornell University, 2003.
• 10: Davidson, I. and Ravi, S. S. 2005. Hierarchical clustering with constraints: theory and practice. In: Proc. 9th European principles and practice of KDD (PKDD'05). Porto, Portugal pp 59--70.
• 11: Davidson I. and Ravi S. S. 2006. Identifying and Generating Easy Sets of Constraints For Clustering, 21st AAAI Conference, 2006.
• 12: Davidson I., Wagstaff, K., and Basu, S. 2006. Measuring Constraint-Set Utility for Partitional Clustering Algorithms, In Proceeding of ECML/PKDD, 2006.
• 13: Ian Davidson , S. S. Ravi, Intractability and clustering with constraints, Proceedings of the 24th international conference on Machine learning, p.201-208, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273522]
• 14: Chuan Duan , Jane Cleland-Huang, Clustering support for automated tracing, Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, November 05-09, 2007, Atlanta, Georgia, USA [doi>10.1145/1321631.1321668]
• 15: Duan, C., Clustering and its Application in Requirements Engineering, Technical Report #08-001, School of Computing, (DePaul University, February, 2008).
• 16: Fern, X. Z. and Brodley, C. E. 2003. Random projection for high dimensional data clustering: A cluster ensemble approach. In Proc. of ICML'03, Washington, DC (2003) 186--193.
• 17: Xiaoli Zhang Fern , Carla E. Brodley, Solving cluster ensemble problems by bipartite graph partitioning, Proceedings of the twenty-first international conference on Machine learning, p.36, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015414]
• 18: Ana L. N. Fred , Anil K. Jain, Combining Multiple Clusterings Using Evidence Accumulation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.6, p.835-850, June 2005 [doi>10.1109/TPAMI.2005.113]
• 19: Derek Greene , Pádraig Cunningham, Constraint Selection by Committee: An Ensemble Approach to Identifying Informative Constraints for Semi-supervised Clustering, Proceedings of the 18th European conference on Machine Learning, September 17-21, 2007, Warsaw, Poland [doi>10.1007/978-3-540-74958-5_16]
• 20: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 21: Tao Li , Chris Ding , Michael I. Jordan, Solving Consensus and Semi-supervised Clustering Problems Using Nonnegative Matrix Factorization, Proceedings of the 2007 Seventh IEEE International Conference on Data Mining, p.577-582, October 28-31, 2007 [doi>10.1109/ICDM.2007.98]
• 22: Alexander Strehl , Joydeep Ghosh, Cluster ensembles --- a knowledge reuse framework for combining multiple partitions, The Journal of Machine Learning Research, 3, p.583-617, 3/1/2003
• 23: Wei Tang , Hui Xiong , Shi Zhong , Jie Wu, Enhancing semi-supervised clustering: a feature projection perspective, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281268]
• 24: Alexander Topchy , Anil K. Jain , William Punch, Combining Multiple Weak Clusterings, Proceedings of the Third IEEE International Conference on Data Mining, p.331, November 19-22, 2003
• 25: Kiri Wagstaff , Claire Cardie , Seth Rogers , Stefan Schrödl, Constrained K-means Clustering with Background Knowledge, Proceedings of the Eighteenth International Conference on Machine Learning, p.577-584, June 28-July 01, 2001

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

General Terms:
Documentation, Management

Keywords:
clustering, requirements