【作者】 孙登第；

【导师】 罗斌；

【作者基本信息】 安徽大学 ， 计算机应用技术， 2012， 博士

【摘要】 随着计算机技术与人工智能理论的发展,模式识别的理论与方法研究已经取得很大进展,并已广泛应用于声音和语言识别、文字识别、指纹识别、图像分析等领域。近年来,网络数据的分析和处理成为模式识别的重要研究内容。面对网络这种新型、动态的大规模关系数据,随机图及其所衍生出的复杂网络理论受到越来越多的关注。研究表明,随机图可以更好地模拟现实的关系数据,在分类、聚类、匹配等模式识别经典问题中都显示出明显优势与发展潜力。本文立足于一种重要的随机图模型——随机点积图,重点研究了随机点积图在自动图像标注、多社团属性关系传播、网络攻击检测等多个模式识别新兴热点问题中的应用,并从理论上对随机点积图在保持模长归一化的约束下进行了进一步的推广。随机点积图是近年来新提出的一种点-边随机图模型,它通过对节点的随机赋值,依照点积规则计算节点之间的连接概率,从而通过节点的随机性体现出边的随机性,形成随机图。随机点积图具有聚类性、传递性、度幂律性等多种重要性质,可以很好地拟合现实存在的各种图结构和网络。本文从概率期望的角度证明了随机点积图的传递性,将在一维空间中的证明过程推广到高维空间中；传统的传递性质只涉及节点连通时的情况,本文提出了在随机点积图中节点不连通时边概率的传递性,并给予证明。对于随机点积图的求解问题,本文研究了随机点积图对关联图的模拟,并给出求解方法。该解法从关联图的加权邻接矩阵出发,将关联图的随机点积化问题转化成了矩阵范数逼近问题,通过对加权邻接矩阵的谱分解得到节点的赋值。图像标注是基于内容的图像检索的重要和具有挑战性的课题。随着数字图像数据量呈爆炸性增长,如何有效检索海量的图像数据是个人与商业搜索引擎都迫切需要考虑的问题。自动图像标注能提供更符合人类检索习惯的文本输入查询方式,是图像检索中的一项关键技术。本文提出了一种基于随机点积图的图像标注算法,该算法首先构造了一个融合了底层特征间、标注词间以及图像与标注词间的相似关系的关联图,再利用随机点积图对该关联图进行重构,挖据出图像的底层特征间和标注词间隐藏的相似关系,并形成状态转移概率,结合重启式随机游走,最终实现自动图像标注。基于随机点积图的图像标注算法将基本标注阶段与标注改善阶段结合起来,从整体进行关联图的随机点积重构,并实现自动标注。在多个通用图像库上的实验证明,该方法可以有效提高图像标注精度,尤其在图像库较小时,具有明显优势。近年来社会网络的研究取得了高速发展,其应用也越来越普及。与传统的模式识别不同,网络分析侧重个体之间相互联系的分析和挖掘,所以从模式识别的角度来看,网络分析也称为“链接识别”(Link recognition)或者“链接分析”(Link analysis)。在网络中,个体与个体之间围绕共同的兴趣和话题相互联系形成不同的社团。当前,社团已经成为了解网络结构、功能和增长机制的重要工具。由于不同社团中存在的数据关系大不相同,社团之间属性关系的传播已成模式识别中一个挑战性的问题。本文提出了一种基于随机点积图的多社团属性关系传播算法。该方法从已知属性关系的社团入手,结合目标社团中的个体特征,用随机点积图对当前属性关系不断演化,挖掘出目标社团中隐藏的属性关系。该方法可以同时实现对社团中成员的划分与属性关系的跨社团传递。通过在多个实际社会网络数据库的实验表明,该方法可以准确揭示社团中隐藏的属性关系。数据降维与嵌入是模式识别中的重要研究问题。对于关系数据,随机点积图可以将图中的节点嵌入到向量空间中。关系数据经过核函数形成的相似矩阵往往具有相同的对角元,基于这一重要性质,本文提出一种改进的随机点积图模型——保持模长归一化的随机点积图,它可以将图嵌入到一个球面空间中。此外,对于归一化的特征数据,现有的降维方法都没有考虑数据的归一化性质,将保持模长归一化的随机点积图模型用于这类数据的降维中,则降维后的特征数据依然是模长归一化的。在这种随机点积图模型的解空间中,欧氏距离与夹角余弦是等价的。本文从理论上给出了该模型的求解方法与收敛性分析。在多个真实数据库上的聚类实验表明,该模型可以得到更具可分性的节点嵌入结果。随着互联网技术的发展,大规模的动态网络通过计算机和其他设备将人类连接起来,这种大规模网络已经成为人们获取信息和知识的重要来源。为增强网络用户的安全性,网络攻击行为检测成为模式识别在网络分析中亟待解决的新问题。本文提出了一种新的基于保持模长归一化随机点积图的网络攻击检测方法,根据待测网络拓扑结构的随机点积图谱空间坐标识别欺骗或攻击。本文从理论上证明了攻击者与普通节点分别落在谱空间的不同区域中。保持模长归一化随机点积图将节点的谱坐标合理分布于球面空间中,并在该球面空间中识别攻击行为,尤其可以探测出在原始网络拓扑结构中难以识别的协同攻击。与现有基于拓扑的攻击检测方法相比较,对于各种形式的协同攻击,本文方法可以显著提高攻击检测的有效性及效率。更多还原

【Abstract】 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.更多还原