不确定性数据中图模型的构建

【作者】 张伟；

【导师】 刘惟一；

【作者基本信息】 云南大学 ， 计算机应用技术， 2012， 硕士

【摘要】 近年来,随着数据采集和处理等相关领域,比如金融,军事,财务,通讯等方面的发展,不确定性数据的重要性渐渐为人们所认同。在不确定性数据的研究领域,所面对的挑战可归结为：需要一种有效的机制来表达不确定性数据中元组间的复杂关系,需要一种有效的方法支持不确定性数据上的查询和世系分析,需要一种适应不确定性数据的推理方法。亦即,考虑到不确定性数的特性,从不确定性数据中发现不确定性知识,并将其以某种结构存储下来,以支持关于不确定性数据的一系列操作,如查询处理,世系分析,决策支持等操作。而本文的目的正是将不确定性数据中所蕴含的概率知识以贝叶斯网这一重要的概率图模型保存下来。考虑到贝叶斯网有成熟的理论背景和大量应用,及强大的概率知识表达能力,所以将贝叶斯网应用到不确定性数据领域是自然而然的。贝叶斯网的依赖分析方法是一个重要和有效的贝叶斯网结构学习方法。本文实践的重点正是将依赖分析方法引入不确定性数据的贝叶斯网结构学习。在实际应用中,以本文方法学出的贝叶斯网是以x-relation的属性为结点,而每一属性相应取值即为该结点所对应的随机变量的取值。x-relation属性间概率依赖的关系就通过贝叶斯网结点间的有向边记录下来。为将贝叶斯网引入不确定性数据研究领域,本文的主要工作可归结为以下几方面：●贝叶斯网相关理论和方法要求所处理的数据,必须满足蕴含作为其来源的概率空间中所有样本事件的前提要求。而对于不确定性数据,因为数据缺失或其它原因,并不能满足这一要求。为此,本文提出一个通过缩小不确定性数据来源的概率空间的转化方法,使其满足贝叶斯网的前提要求。●由于不确定性数据是内部关联的数据,本文提出一个相适应的概率计算框架,以有效进行相关概率值的计算,包括条件独立测试的计算。●依赖模型是展开贝叶斯网相关讨论的前件。通过平移确定数据上依赖模型的定义到不确定性数据,本文给出与不确定性数据相适应的依赖模型定义。●考虑到不确定性数据的特性,如数据缺失和数据内部关联等,不能将传统的贝叶斯网学习方法直接作用于不确定性数据。经替换传统贝叶斯网学习方法中一部分构成要素,本文给出适应用于不确定性数据的贝叶斯网学习方法。更多还原

【Abstract】 In recent years, the importance of uncertain data has been recognized with the rapid development in data gathering and processing in various fields, including economy, military, logistic, finance and telecommunication, etc.In the realm of uncertain data, the challenges aroused from studying uncertain data can be summarized as follows:a helpful mechanism to represent the correlation in uncertain data, an efficient method to support query and analyze lineages on uncertain data, and an approach to make reasoning on uncertain data. Namely, considering the property of uncertain data, to discovery uncertain knowledge represented as a probabilistic graphical model and implied in uncertain data can further accelerate the operations, such as query processing, lineage analysis, decision making, etc.The main idea of this paper is try to discover probabilistic knowledge implied in uncertain data with Bayesian Network(BN) that is a typical Probabilistic Graphical Model(PGM). It is natural to adopt BN to the realm of uncertain data, since BN has great success to represent the uncertain knowledge of traditional certain data considering BN related theories and applications.Dependency analysis is an important and representative method for learning a BN from traditional certain data. In this paper, the BN learned from uncertain data, has nodes that are the columns of the x-relation, and the states of each node that are the set of all possible values from the corresponding columns. The probabilistic dependency relationships in the x-relation are depicted by directed edges between nodes.For introducing BN to uncertain data, contributions in this paper can be summarized as follows:●Theories and methods related to BN require that inputs data must imply all sample data from the Probability Space(PS), from which these data are observed. However, as some data is missing, uncertain data cannot always satisfy this requirement with BN. In this paper, a method of converting uncertain data to satisfy this requirement is presented by decreasing the size of original PS. ●As uncertain data are correlated, a corresponding probability-calculating framework is given, for obtaining the probabilities concerned in the Cl-testes while learning the BN from uncertain data.●As Dependency Model(DM) is the prerequisite for discussing BN, a DM implied in uncertain data is presented by mapping original definitions of DM to the realm of uncertain data.●Considering the properties of uncertain data, like data missing and data correlating, etc, it is not right to apply traditional BN learning method to uncertain data directly. By replacing critical components of traditional BN learning method, a sound and feasible BN learning method for uncertain data is give.更多还原