基于随机点积图理论的模式识别方法研究

发布时间：2018-05-02 06:34

本文选题：模式识别 + 随机点积图　；参考：《安徽大学》2012年博士论文

【摘要】：随着计算机技术与人工智能理论的发展,模式识别的理论与方法研究已经取得很大进展,并已广泛应用于声音和语言识别、文字识别、指纹识别、图像分析等领域。近年来,网络数据的分析和处理成为模式识别的重要研究内容。面对网络这种新型、动态的大规模关系数据,随机图及其所衍生出的复杂网络理论受到越来越多的关注。研究表明,随机图可以更好地模拟现实的关系数据,在分类、聚类、匹配等模式识别经典问题中都显示出明显优势与发展潜力。本文立足于一种重要的随机图模型——随机点积图,重点研究了随机点积图在自动图像标注、多社团属性关系传播、网络攻击检测等多个模式识别新兴热点问题中的应用,并从理论上对随机点积图在保持模长归一化的约束下进行了进一步的推广。随机点积图是近年来新提出的一种点-边随机图模型,它通过对节点的随机赋值,依照点积规则计算节点之间的连接概率,从而通过节点的随机性体现出边的随机性,形成随机图。随机点积图具有聚类性、传递性、度幂律性等多种重要性质,可以很好地拟合现实存在的各种图结构和网络。本文从概率期望的角度证明了随机点积图的传递性,将在一维空间中的证明过程推广到高维空间中；传统的传递性质只涉及节点连通时的情况,本文提出了在随机点积图中节点不连通时边概率的传递性,并给予证明。对于随机点积图的求解问题,本文研究了随机点积图对关联图的模拟,并给出求解方法。该解法从关联图的加权邻接矩阵出发,将关联图的随机点积化问题转化成了矩阵范数逼近问题,通过对加权邻接矩阵的谱分解得到节点的赋值。图像标注是基于内容的图像检索的重要和具有挑战性的课题。随着数字图像数据量呈爆炸性增长,如何有效检索海量的图像数据是个人与商业搜索引擎都迫切需要考虑的问题。自动图像标注能提供更符合人类检索习惯的文本输入查询方式,是图像检索中的一项关键技术。本文提出了一种基于随机点积图的图像标注算法,该算法首先构造了一个融合了底层特征间、标注词间以及图像与标注词间的相似关系的关联图,再利用随机点积图对该关联图进行重构,挖据出图像的底层特征间和标注词间隐藏的相似关系,并形成状态转移概率,结合重启式随机游走,最终实现自动图像标注。基于随机点积图的图像标注算法将基本标注阶段与标注改善阶段结合起来,从整体进行关联图的随机点积重构,并实现自动标注。在多个通用图像库上的实验证明,该方法可以有效提高图像标注精度,尤其在图像库较小时,具有明显优势。近年来社会网络的研究取得了高速发展,其应用也越来越普及。与传统的模式识别不同,网络分析侧重个体之间相互联系的分析和挖掘,所以从模式识别的角度来看,网络分析也称为“链接识别”(Link recognition)或者“链接分析”(Link analysis)。在网络中,个体与个体之间围绕共同的兴趣和话题相互联系形成不同的社团。当前,社团已经成为了解网络结构、功能和增长机制的重要工具。由于不同社团中存在的数据关系大不相同,社团之间属性关系的传播已成模式识别中一个挑战性的问题。本文提出了一种基于随机点积图的多社团属性关系传播算法。该方法从已知属性关系的社团入手,结合目标社团中的个体特征,用随机点积图对当前属性关系不断演化,挖掘出目标社团中隐藏的属性关系。该方法可以同时实现对社团中成员的划分与属性关系的跨社团传递。通过在多个实际社会网络数据库的实验表明,该方法可以准确揭示社团中隐藏的属性关系。数据降维与嵌入是模式识别中的重要研究问题。对于关系数据,随机点积图可以将图中的节点嵌入到向量空间中。关系数据经过核函数形成的相似矩阵往往具有相同的对角元,基于这一重要性质,本文提出一种改进的随机点积图模型——保持模长归一化的随机点积图,它可以将图嵌入到一个球面空间中。此外,对于归一化的特征数据,现有的降维方法都没有考虑数据的归一化性质,将保持模长归一化的随机点积图模型用于这类数据的降维中,则降维后的特征数据依然是模长归一化的。在这种随机点积图模型的解空间中,欧氏距离与夹角余弦是等价的。本文从理论上给出了该模型的求解方法与收敛性分析。在多个真实数据库上的聚类实验表明,该模型可以得到更具可分性的节点嵌入结果。随着互联网技术的发展,大规模的动态网络通过计算机和其他设备将人类连接起来,这种大规模网络已经成为人们获取信息和知识的重要来源。为增强网络用户的安全性,网络攻击行为检测成为模式识别在网络分析中亟待解决的新问题。本文提出了一种新的基于保持模长归一化随机点积图的网络攻击检测方法,根据待测网络拓扑结构的随机点积图谱空间坐标识别欺骗或攻击。本文从理论上证明了攻击者与普通节点分别落在谱空间的不同区域中。保持模长归一化随机点积图将节点的谱坐标合理分布于球面空间中,并在该球面空间中识别攻击行为,尤其可以探测出在原始网络拓扑结构中难以识别的协同攻击。与现有基于拓扑的攻击检测方法相比较,对于各种形式的协同攻击,本文方法可以显著提高攻击检测的有效性及效率。
[Abstract]:With the development of computer technology and artificial intelligence theory, the research of pattern recognition theory and method has made great progress, and has been widely used in the fields of voice and language recognition, word recognition, fingerprint recognition, image analysis and so on. In recent years, the analysis and management of network data has become an important research content of pattern recognition. A new type of dynamic large-scale relational data, random graph and the complex network theory derived from it have attracted more and more attention.
The research shows that the random graph can better simulate the real relational data and show obvious advantages and development potential in the classification, clustering, matching and other classic problems. This paper is based on an important random graph model, random dot product graph, and focuses on the automatic image annotation and multi community attribute relationship. The applications of many new hot issues such as propagation, network attack detection and so on are identified, and the stochastic point product graph is further extended under the constraint of maintaining the normalization of the model length.
Random dot product graph (random dot product graph) is a new model of point edge random graph in recent years. Through the random assignment of nodes, it calculates the connection probability between nodes according to the rule of point product. By the randomness of nodes, it embodies the randomness of the edges and forms random graphs. The random dot product graphs have many important properties, such as clustering, transitivity, power law and so on. In this paper, the transitivity of random dot product graphs is proved from the perspective of probability expectation, and the proof process in one dimension space is extended to the high dimensional space. The traditional transitive property only involves the case of node connectivity. This paper proposes the node disconnection in the random dot product graph. In order to solve the problem of the random dot product graph, this paper studies the simulation of the random dot product graph and gives the solution method. From the weighted adjacency matrix of the association graph, the problem of the random point accumulation of the correlation graph is transformed into the approximation problem of the matrix norm, and the weighted adjacency moment is used. The spectral decomposition of the matrix results in the assignment of the nodes.
Image annotation is an important and challenging topic in content based image retrieval. With the explosive growth of digital image data, how to effectively retrieve massive image data is an urgent problem for both individual and commercial search engines. Automatic image annotation can provide text input which is more in line with human retrieval habits. It is a key technology in image retrieval. In this paper, an image annotation algorithm based on random dot product graph is proposed. The algorithm first constructs an association graph which combines the underlying features, annotated words, and the similarity relation between the image and the annotation words, and then reconstructs the association graph by random dot product graph. The similarity relation between the underlying feature and the annotation of the image is hidden, and the state transfer probability is formed, and the automatic image annotation is achieved by combining the restart random walk. The image annotation algorithm based on the random dot product graph combines the basic annotation stage with the annotation improvement stage, and reconstructs the random point product of the association graph from the whole, and it is real. This method can effectively improve the accuracy of the image annotation, especially in the small image library, which has obvious advantages.
In recent years, the research of social network has been developing rapidly and its application is becoming more and more popular. Unlike traditional pattern recognition, network analysis focuses on the analysis and mining of interrelationships among individuals, so from the perspective of pattern recognition, network analysis is also called "Link recognition" or "Link ana". Lysis). In the network, individuals and individuals are connected around common interests and topics to form different associations. At present, the community has become an important tool to understand the structure, function and growth mechanism of the network. Because the data relations in different societies are very different, the propagation of attribute relations among groups has become one of the pattern recognition. This paper proposes a multi community attribute relation propagation algorithm based on random dot product graph. This method starts with the community of the known attribute relations and combines the individual characteristics of the target community, and evolves the current attribute relation with the random dot product graph, and excavates the hidden attribute relation in the target community. At the same time, the relationship between the division and property of the members of the community is transferred across societies. Through the experiments in a number of real social network databases, it is shown that this method can accurately reveal the hidden attribute relationship in the community.
The data reduction and embedding of data is an important research problem in pattern recognition. For relational data, random dot product graphs can be embedded into the vector space. The similarity matrix formed by the relational data through kernel function often has the same diagonal element. Based on this important property, an improved random dot product graph model is proposed in this paper. In addition, for the normalized feature data, the existing dimensionality reduction methods do not take into account the normalization of the data, and the random dot product graph model, which maintains the normalization of the model length, is used in the dimensionality reduction of this kind of data, and the feature data after the dimensionality reduction is dependent. In the solution space of this random dot product graph model, the Euclidean distance is equivalent to the angle cosine. In this paper, the solution method and convergence analysis of the model are given in theory. The clustering experiments on multiple real databases show that the model can get more separable node embedding results.
With the development of Internet technology, large scale dynamic networks connect people through computers and other devices. This large-scale network has become an important source for people to obtain information and knowledge. In order to enhance the security of network users, network attack behavior detection has become a new question to be solved in network analysis. In this paper, a new network attack detection method based on the maintenance model length normalized random dot product graph is proposed, which identifies the deception or attack according to the spatial coordinates of the random dot product Atlas of the network topology. This paper theoretically proves that the attacker and the common node fall in the different regions of the spectral space respectively. The random point product graph distributes the spectral coordinates of the nodes in the spherical space reasonably and identifies the attack behavior in the spherical space, especially the cooperative attack which is difficult to identify in the original network topology. Compared with the existing topology based attack detection methods, this method can be significant for various forms of cooperative attack. Improve the effectiveness and efficiency of attack detection.

【学位授予单位】：安徽大学
【学位级别】：博士
【学位授予年份】：2012
【分类号】：TP391.41

【相似文献】