Presentation
An Evaluation of a Hierarchical Clustering Method Using Quantum Annealing
SessionResearch Poster Session
Event Type
Research Poster
Pre-Recorded
TimeTuesday, June 23rd3pm - 3:05pm
LocationAnalog 1
DescriptionCurrently, the demand for clustering algorithms has been increasing, especially in machine learning. The hierarchical agglomerative clustering algorithm (HAC) is widely used when the number of clusters is unknown. However, the execution time of the HAC tends to be long. Since the HAC can be partially transformed into the combinatorial optimization problems, quantum annealing (QA) has a possibility to accelerate the HAC. This poster quantitatively compares the HAC performances of three ways, QA, simulated annealing (SA), and the greedy algorithm, in terms of the execution time and the quality. For comparison, this poster also evaluates the K-means algorithm, one of the non-hierarchical clustering algorithms, on a CPU, a GPU, and a vector processor. The experimental results indicate that the quality of the HAC using QA becomes the highest. This is because QA can search the whole solution space in a short time by quantum fluctuations. On the other hand, SA cannot improve the quality by increasing the annealing time to explore the search space. The greedy algorithm falls a local optimum and cannot find the best solution. Furthermore, it is observed that the K-means on digital computers is effective when the number of clusters is known. These results suggest that the combination of the hierarchical clustering on a QA machine and non-hierarchical clustering on a digital computer can be the promising approach to large-scale clustering.
Poster PDF