Pattern Recognition Based On Random Dot Product Graph Model

With the rapid development of computer technology and artificial intelligence theory, pattern recognition accordingly has been widely used in many fields, such as sound and language recognition, character recognition, fingerprint identification, image analysis and so on. In recent years, web data analyzing and processing becomes an important research topic of pattern recognition. Web data are dynamical and large scale relational data. To deal with web data, the random graph and it's derivatives:complex network have been paid more and more attentions by researchers.In many classic problems of pattern recognition, such as classification, clustering and matching, random graph has apparent advantages and development potential. This dissertation focuses on a new important kind of random graph:random dot product graph, and mainly researches the application of random dot product graph in automatic image annotation, relational communication between communities and web attack detection. Moreover, the random dot product graph is extended theoretically with normalized constraint and some useful results are obtained.Random dot product graph is a kind of vertex-edge random graph, in which a vector of attributes is assigned to each vertex, such that the probability of an edge is equal to the dot product of the vectors. Random dot product graph have some excellent properties, such as clustering, transitivity, power-law degree, and can fit to real-world graph very well. In this dissertation, we prove the transitivity of random dot product graph from a probabilities perspective; extend the property from one dimensional space to higher dimensional space. Only the connectivity situation is involved in the traditional transitivity, here we also proposed the transitivity when the nodes are not connected in the random dot product graph and prove it theoretically. Moreover, the relational graph fitting with random dot product graph also is studied. We convert this fitting to a Frobenius norm approximation problem, and acquire the node vectors by the eigen-decomposition of the weighted adjacency matrix. Automatic image annotation is an important and challenging work in content-based image retrieval. With the number of digital images increases explosively, image retrieval in large-scale database has became an urgent problem to be solved for individual and commercial search engine. Automatic image annotation can provide query methods based on text input, which conforms to the human retrieval habit more sensibly. In order to overcome the semantic gap between low-level features and high-level semantic concept of image, a novel image annotation approach based on Random Dot Product Graph is proposed in this dissertation. In our approach, the relation between images and words are used to construct relational graph of image annotations. Then, we reconstruct the graph with Random Dot Product Graph, find the unobserved relevance in incompletely observed graph and transform the random graph into the probabilities of state transition. Combined with Random Walk with Restart (RWR), the final annotations are chosen. This new method incorporates the two sub-processes, i.e., basic image annotation and annotation refinement, and reduces the influence of the scale of database. Experiments conducted on three standard databases demonstrate that our approach outperforms the existing image annotation techniques.In recent years, due to high-speed development and widespread application, web data analysis has become a focal problem. Different from the traditional pattern recognition, web data analysis focus on mining the relation among individual. So from the point of view of pattern recognition, web data analysis is also called link recognition or link analysis. One web feature that has been emphasized in recent work is community structure, the gathering of vertices into groups such that there is a higher density of interrelationship within groups than between them. The attributed relation propagation of multi-communities has become an extremely important tool for understanding the structure and the functioning of the network, and its growth mechanisms. This dissertation proposes a novel and efficient approach, based on random dot product graph, to exploit attributed relation while considering the community transition for large scale social network. Starting with the known attributed relation and initial classification results, the proposed approach evolve the hidden attributed relation in target community with random dot product graph. Particularly, the proposed approach is capable of simultaneously improving the classification results and propagating the concept affinities to target community, which preserves the consistency and smoothness of the attributed relation over multi-communities. We conduct extensive experiments to improve annotation results of videos from TRECVID2005-2007data sets. Results show consistent and significant performance gain over various methods.Dimensinality reduction and embedding is important topics in pattern recognition as well. For relational data, random dot product graph can be used to embed the graph nodes into vector space. However, for most of the relation data, the kernelized similarity matrices have constant diagonal elements. Based on this characteristic, in this dissertation, we propose to employ a normalization preserved random dot product graph to embed graph data, which corresponds to embedding them on a unit spherical surface. Moreover, for normalized vector data, existing methods do not utilize the fact that the data is normalized. We also use the improved random dot product graph to deal with this normalized vector data, which preserves the normalization of original vector data. In the normalization preserved random dot product graph, the Euclidean distance is equivalent to the cosine similarity. Thus data structures best described in the cosine similarity and data structure best captured by the Euclidean distance can both be effectively detected in our approach. We provide the theoretical analysis, derive the computational algorithm, and evaluate the angular embedding on several datasets. Experiments on data clustering demonstrate that our method can provide a more discriminative subspace.In recent decades, we have witnessed a global dynamical network that links humans through the use of computers and other devices. People communicate and interact spontaneously in a cyber space, create content and share knowledge over this large-scale networks. In large-scale and dynamic networks, each participant is vulnerable to various attacks. Thus, attack detection techniques need to be developed for enhancing security. In this dissertation, we propose a novel framework that detects web attack based on the normalization preserved random dot product graph. This method exploits the spherical spectral space of underlying network topology to identify frauds or attacks. Our theoretical results showed that attackers locate in a different region of the spectral space from regular users. By identifying attacking patterns in graph spherical spectral spaces, we can detect various collaborative attacks that are hard to be identified from the original topological structures. We compare our detection approach with the traditional topology based detection approach. Evaluation results show that our approach significantly improves both effectiveness and efficiency in detecting various collaborative attacks.