Clustering Algorithm Based On Quantum Game

As a core technology of information systems, database technology has achieved rapid development in the new century, coupled with advances in storage technology, people can store vast amounts of data. Therefore, the size of data accumulated in all walks of life is explosive growing from GB to TB and then PB.In the context of "data explosion", the effective data processing to obtain useful information becomes critical. Data mining emerged to solve the present issue:"data explosion but lack of knowledge".Nevertheless, thanks to the increase of data size and data complexity, traditional clustering algorithms encountered serious challenges. In the face of high-dimensional data, mass data, unstructured data, etc, traditional data mining algorithms are at their wits’ end. On the other hand, by virtue of unique quantum features like quantum superposition, quantum entanglement, etc, quantum computing can naturally achieve parallel computing, thereby, classic algorithm can achieve acceleration. Recent years, quantum computing’s application in data mining has been widely concerned and researched.This thesis does extensive research on quantum clustering algorithm proposed previously, based on these, this thesis prospective blends quantum computing and game theory, and applies quantum game to clustering algorithm. The main work of this thesis is as following:（1）This thesis introduces research progress of quantum computing and data mining, and makes critical discussion and analysis about the quantum game, then elaborated expounds the application status of the quantum game clustering algorithm. （2）A clustering algorithm named QGC_G（quantum game clustering algorithm based on grid） is proposed where data points are regarded as players. By embeding distance function into payoff matrix, similar data points can get more payoff, clusters will be formed in that way. In addition, a rule about merging grid is designed to simplify the game. Simulations show the clustering quality of QGC_G is superior to K-means etc. At last, several parameters QGC_G are discussed and some recommendations about parameters selection are provided.（3）This thesis extends QGC_G to the situation that three players participate in at the sane time. The traditional Prisoner’s Dilemma payoff matrix has been improved, and a clustering algorithms based on quantum tri-Prisoner’s Dilemma game, named QGC₃PD has been proposed. Simulation result shows QGC₃PD has a better clustering performance on some high-dimensional data sets.