Utilizing cluster quality in hierarchical clustering for analogy-based software effort estimation
Abstract
Analogy-based software effort estimation is one of the most popular estimation methods. It is built upon the principle of case-based reasoning (CBR) based on the k-th similar projects completed in the past. Therefore the determination of the k value is crucial to the prediction performance. Various research have been carried out to use a single and fixed k value for experiments, and it is known that dynamically allocated k values in an experiment will produce the optimized performance. This paper proposes an interesting technique based on hierarchical clustering to produce a range for k through various cluster quality criteria. We find that complete linkage clustering is more suitable for large datasets while single linkage clustering is suitable for small datasets. The method searches for optimized k values based on the proposed heuristic optimization technique, which have the advantages of easy computation and optimized for the dataset being investigated. Datasets from the PROMISE repository have been used to evaluate the proposed technique. The results of the experiments show that the proposed method is able to determine an optimized set of k values for analogy-based prediction, and to give estimates that outperformed traditional models based on a fixed k value. The implication is significant in that the analogy-based model will be optimized according the dataset being used, without the need to ask an expert to determining a single, fixed k value. optimal in previous studies [1]. However, determining the best value of k for each testing case is time consuming. We propose to use hierarchical clustering with specific cluster quality criteria to determine the value of k efficiently and automatically. For a suitable clustering algorithm, we studied and compared complete-linkage, single-linkage, and averagelinkage hierarchical clustering algorithms for determining an appropriate value of k based on the size of the cluster in which the testing case that belongs to. For the stopping condition of the clustering algorithms, we adopted five cluster quality criteria. Each has its own merits and preference in producing clusters with certain characteristics (e.g., smal