Adaptive path-delay testing is a testing methodology that reduces redundant test patterns based on the measured process condition of a die under test (DUT). To improve testing efficiency, process conditions are clustered into a limited number of clusters, each of which has a corresponding set of test patterns. The test pattern set of a cluster must include all potential timing critical paths of all process conditions in the cluster. Hence, high quality clustering is needed to minimize redundant test paths. In this paper, we propose a new clustering heuristic to minimize the expected number of redundant test paths in adaptive path delay testing. Our experimental results on randomly generated testcases show that the proposed clustering heuristic can reduce the expected number of test paths by up to 40% compared to the previous Greedy clustering algorithm of Uezono et al. [5]. Our new approach shows similar improvements for an industrial testcase obtained from the authors of [5].