【作者】 陈红梅；

【导师】 刘惟一；

【作者基本信息】 云南大学 ， 通信与信息系统， 2012， 博士

【摘要】 随着数据采集和处理技术的进步,人们对数据不确定性的认识逐步深入,对不确定性数据的研究也广泛开展。数据不确定性的引入,对数据建模、数据管理和数据挖掘,都提出了新挑战。不确定性数据挖掘不是传统数据挖掘的简单扩展,而是正在蓬勃发展的新研究方向,还有许多有待解决的问题。分类在数据挖掘中是一个重要的研究方向,在现实生活中也是一个普遍存在的问题,具有广泛的应用领域。面对不确定性数据,分类也得到了新发展。本文针对两个层面的不确定性数据——已知概率分布的不确定性数据和缺失概率分布的不确定性数据,研究了三种基本分类方法——最近邻分类、朴素贝叶斯分类和基本决策树分类。本文的研究在一定程度上丰富和发展了不确定性数据挖掘的理论和技术,增强和扩大了不确定性数据及其分类的应用范围。本文的主要工作和贡献如下：(1)研究了已知概率分布的不确定性数据的最近邻分类。对于值不确定性连续对象的最近邻分类,所提方法有效地降低了计算复杂度；对于值不确定性离散对象的最近邻分类,所提方法有效地提高了分类准确率①对于值不确定性连续对象,定义对象之间的距离为期望距离,采用期望平方距离评估期望距离,并推导了有效计算期望平方距离的公式。在某些条件下,期望平方距离具有与期望距离同样的分类准确率,并有效地降低了计算复杂度。②对于值不确定性离散对象,从语义的角度,采用序信息或概念层次树等,定义对象之间的距离为期望语义距离,并通过索引和剪枝计算期望语义距离。如果可以较好地定义语义距离,期望语义距离可以有效地提高分类准确率,而计算复杂度却没有明显地增加。由于期望距离、期望平方距离和期望语义距离适用于确定性对象,所以值不确定性对象的最近邻分类扩展了确定性对象的最近邻分类。(2)研究了缺失概率分布的不确定性数据的朴素贝叶斯分类。基于区间概率理论,将点概率参数的朴素贝叶斯分类扩展到区间概率参数的朴素贝叶斯分类,既可以处理值不确定性离散对象,也可以处理确定性离散对象。①从概率势的角度,定义了值不确定性离散对象的区间概率,并证明了它是区间概率理论中的F-概率。②基于区间概率理论,定义了值不确定性离散对象的条件区间概率(直观概念和规范概念)、独立与直观概念的条件独立,并采用区间概率表达直观概念以便有效计算直观概念。③采用直观概念作为后验区间概率和条件区间概率,采用规范概念重构联合区间概率,进而计算后验区间概率,提出了值不确定性离散对象的朴素贝叶斯分类,将点概率参数的朴素贝叶斯分类扩展到区间概率参数的朴素贝叶斯分类。由于确定性离散对象是值不确定性离散对象的特例,而区间概率理论一般化了经典概率论,因此,值不确定性离散对象的朴素贝叶斯分类可以处理确定性离散对象。(3)研究了缺失概率分布的不确定性数据的基本决策树分类。基于可达概率区间,将以0-1划分对象的基本决策树扩展到以概率区间分配对象的基本决策树,不仅可以处理值不确定性离散对象,而且可以处理确定性离散对象。①从区间概率和条件区间概率直观概念的角度,定义了值不确定性离散对象的概率区间和条件概率区间,并证明了它们是可达概率区间。②基于可达概率区间,定义了值不确定性离散对象的熵区间和条件熵区间,采用可达概率区间的熵的最大值作为熵区间的上界,熵的一个下界作为熵区间的下界,并给出了求解熵区间的上界和下界的方法。③采用二叉树结构和属性值集合测试以及采用条件熵区间作为属性选择度量,提出了值不确定性离散对象的基本决策树分类,将以0-1划分对象的基本决策树扩展到以概率区间分配对象的基本决策树。由于经典概率是可达概率区间的特例,而确定性离散对象是值不确定性离散对象的特例,因此,值不确定性离散对象的基本决策树分类可以处理确定性离散对象。更多还原

【Abstract】 The study of uncertain data has attracted many attentions with the rapid development in uncertain data gathering and processing. Uncertainty challenges data modeling, data management and data mining. Uncertain data mining is a new research direction and is more challenging than traditional data mining due to the underlying uncertainty in data. On the other hand, classification is an important task in data mining, and can be applied in various fields.Therefore,it is desirable to develop effective and efficient classification methods over uncertain data.In this thesis, three kinds of basic classification methods,which are the nearest neighbor classification, the naive Bayesian classification and the basic decision tree classification, over two levels of uncertain data, which are uncertain data with exact confidence values/probabilities and uncertain data missing confidence values/probabilities, are investigated. The results in this thesis are helpful to enrich the theory and technologies of uncertain data mining, and to enlarge the application fields of classification over uncertain data.The main contributions of this thesis can be summarized as follows:(1)The nearest neighbor classification over uncertain data with exact probabilities is studied. The presented methods reduce the time complexity of the nearest neighbor classification over value-uncertain continuous objects,and improve the accuracy of the nearest neighbor classification over value-uncertain discrete objects.①For value-uncertain continuous objects,the expected distances between objects are defined, the expected squared distances are adopted to evaluate the expected distances, and a formula to effectively compute the expected squared distances is given in order to reduce the time complexity. Under certain conditions, the accuracy of the expected squared distances is the same with that of the expected distances, with the lower time complexity.②For value-uncertain discrete objects,in order to improve the accuracy, the expected semantic distances between objects are defined by the orders or the concept hierarchy trees from semantic point of view, and the strategies of indexing and pruning are used to effectively compute the expected semantic distances.The accuracy of the expected semantic distances can be improved if the semantic distances can be defined reasonably, with the accepted time complexity.The nearest neighbor classification over value-uncertain objects can be used to classify certain objects because the expected distances, the expected squared distances and the expected semantic distances can be immediately applied to certain objects.(2) The naive Bayesian classification over uncertain data missing probabilities is studied. Based on the theory of interval probability, the naive Bayesian classification is extended to the naive Bayesian classification with interval probability parameters which can handle both value-uncertain discrete objects and certain discrete objects.①The interval probabilities of value-uncertain discrete objects are defined from probabilistic cardinality point of view, and it is proven that the interval probabilities are F-probabilities in the theory of interval probability.②Based on the theory of interval probability, the conditional interval probabilities, including the intuitive concept and the canonical concept, of value-uncertain discrete objects are defined, and the independence and the conditional independence of the intuitive concept are defined. Further, a formula to effectively compute the intuitive concept is given.③The naive Bayesian classification with interval probability parameters over value-uncertain discrete objects is presented, in which the intuitive concept is used as the posterior interval probability and the conditional interval probability, and the canonical concept is used to reconstruct the joint interval probability in order to compute the posterior interval probability.The naive Bayesian classification with interval probability parameters can handle both value-uncertain discrete objects and certain discrete objects because certain discrete objects are special cases of value-uncertain discrete objects, and the theory of interval probability generalizes the theory of classic probability.(3)The basic decision tree classification over uncertain data missing probabilities is studied. Based on the reachable probability intervals, the basic decision tree classification is extended to handle both value-uncertain discrete objects and certain discrete objects, which assigns objects to the branches with probability intervals.①The probability intervals and the conditional probability intervals of value-uncertain discrete objects are defined from the interval probabilities and the intuitive concept of the conditional interval probabilities point of view, and it is proven that the probability intervals and the conditional probability intervals are the reachable probability intervals.②Based on the reachable probability intervals,the entropy intervals and the conditional entropy intervals of value-uncertain discrete objects are defined.The upper bound of the entropy interval is the maximum of the entropies of the reachable probability intervals and the lower bound is the lower bound of the entropies.A method to compute the upper and the lower bounds of the entropy interval is given.③The basic decision tree classification over value-uncertain discrete objects is presented, in which the binary decision and the test based on the set are adopted, and the conditional entropy intervals are used to select the best attribute.The classic probability is a special case of the reachable probability interval and certain discrete objects are special cases of value-uncertain discrete objects,so the presented basic decision tree classification can handle both value-uncertain discrete objects and certain discrete objects.更多还原