This paper presents a novel pheromone update strategy for improving the clustering results of ant colony optimization (ACO). The proposed algorithm is motivated by the observation that most of the ACOs only keep track of the promising foraging information, which has the potential to lead to better solutions than all the other search directions in the pheromone table. This eventually makes the search converge to particular search directions in later iterations because the pheromone values on good routing paths will be reinforced. As such, the breadth of search (diversity) will be reduced, thus limiting the clustering results of ACO. The proposed algorithm adds a second pheromone table to ACO for recording the unpromising foraging information that is worse than all the other search directions and using a novel construction method to explore the new search directions. In other words, by leveraging the strengths of diversification and intensification, the proposed algorithm can find better solutions than traditional ACO. To evaluate the performance of the proposed algorithm, we use it to solve the data clustering problem. Our experimental results indicate that the proposed algorithm can significantly improve the quality of ant colony optimization.