Dynamic Agent Based Clustering Algorithms And Their Quantization

Cluster analysis is a main branch of Pattern Recognition, which is widely used in many fields such as pattern analysis, data mining, information retrieval and image segmen-tation. In these fields, however, there is usually little priori knowledge available about the data. In response to these restrictions, clustering methodology come into being, which is particularly appropriate for the investigation of interrelationships between unlabeled data points. In other words, Cluster analysis is the formal study of algorithms and methods for grouping or classifying unlabeled data points, and its task is to find the inherent structure of a given collection of unlabeled data points and group them into meaningful clusters. In the typical clustering algorithms, data points for clustering are fixed in their positions, and they are grouped by designing different functions to find the clustering centers or bound-aries. In recent years, however, a new idea has emerged in clustering algorithms that some researchers begin to consider data points as movable agents or the like. They move in space according to some simple rules and form clusters automatically.In addition, Quantum Computation is an extremely exciting and rapidly growing field. More recently, an increasing number of researchers with different backgrounds, ranging from physics, computer sciences and information theory to mathematics and philosophy, are involved in researching properties of quantum-based computation. During the last decade, a series of significant breakthroughs have been made. One was that Peter Shor surprised the world by proposing a polynomial-time quantum algorithm for integer factor-ization in 1994, while in the classical world the best-known classical factoring algorithm works in exponential time. Three years later, Lov Grover proved that a quantum computer could search an unsorted database in the square root of the time. These successes make us realize that powerful quantum computers can figure out solutions faster and better than the best known classical counterparts, or even solve certain problems that classical computer cannot solve efficiently. Furthermore, it is more important that they offer a new way to find potentially dramatic algorithmic speed-ups.This thesis consists of two main parts:(1) Clustering algorithms in the classical world. Inspired by the new idea that data points for clustering themselves can move according to some simple rules and form clusters automatically, we investigate an algorithm based on the modified model of random walks, an algorithm based upon Flocking on a complex net-work and an algorithm based upon games on evolving network. (2) Clustering algorithms in the quantum world. Encouraged by the successes of Quantum Computation, we com-bine the quantum computation with the problem of data clustering, and present clustering algorithms based on quantum walks and quantum games, which also are the quantization of two previous classical algorithms. Next, the main contents are outlined below:(1) A Clustering Algorithm Based on the Modified Model of Random Walk. A ran-dom walk is a special class of random processes. In this chapter, a modified model of random walk is proposed, and then two clustering algorithms based on it are established. In the algorithms, data points are considered as not only vertexes of a graph but also parti-cles which can move in space according to the prespecified rules, so that the shape of the graph is changed over time. Further, each data point may be also viewed as a local control subsystem, whose controller adjusts its transition probabilities and identifies the transition direction in the next moment. As they move in space, data points that belong to the same class collect gradually and locate at a same place, whereas those that belong to different classes are away from one another. Finally, when the convergence is reached, some separate clusters are formed automatically.(2) A Clustering Algorithm Based Upon Flocking on Complex Network. Complex network is a new topology to describe networks in the real world. In this chapter, data points for clustering are regarded as movable agents in space and the relationship among them is represented by a time-varying complex network after long-range links are added for each data point. Thus, we extend the original flocking model to a complex network, and investigate a clustering algorithm based on it. Not only dose the structure of the complex network give a new topology for data clustering, but also it is more important that these long-range links in the network provide some hidden information that cannot be perceived directly by agents, and also accelerate the rate of convergence of the algorithm. As a result, data points gather together automatically and establish some separate flocks, each of which corresponds to a cluster, when the convergence is reached.(3) A Clustering Algorithm Based Upon Games on an Evolving Network. Evolution-ary game theory stems from the researches in biology which are to analyze the conflict and cooperation between animals or plants. In this chapter, a clustering algorithm based upon games on an evolving network is presented, where data points for clustering are viewed as players who can make decisions in games. In the algorithm, each player hopes to max-imize his payoff, so he removes edges connecting to neighbors with small payoffs, and creates new edges to neighbors with higher payoffs by observing his neighbors' payoffs in his neighborhood. During players adjusting their edges, some strategies are spread in the network. In the end, evolutionarily stable strategies emerge in the network, and then data points with the same evolutionarily stable strategy are collected as a cluster, so the number of evolutionarily stable strategies indicates the number of clusters.(4) A Clustering Algorithm Based on Quantum Walks. Quantum walks (QWs) are an analogy of classical random walks. In this paper, we combine the QW with the problem of data clustering in order to establish a QW based clustering algorithm. QWs differ from classical random walks in that their evolution is unitary and reversible, so different classical paths can interfere with each other, which also produces totally different distribution from the classical random walk and offer a way to obtain better results. Next, two clustering al-gorithms base on one dimensional QW are established firstly, and then a high-dimensional QW based algorithm is constructed after the one dimensional QW is extended to a high dimensional space. Finally, the effects of parameters are discussed.(5) A Clustering Algorithm Based on Quantum Games. Quantum game is an anal-ogy of a classical game. In this chapter, a clustering algorithm based on quantum games is proposed, where data points are regarded as players who are permitted to use quantum strategies. Each player plays 2×2 entangled quantum games against his neighbors re-spectively, in which two players interact with each other implicitly thanks to the quantum entanglement. As such, new results that differ from the classical game will be achieved. Further, the total payoffs and the rates of convergence of algorithms are discussed and an-alyzed in two cases of strategies, two payoff matrixes and two link-removing-and-rewiring functions.