学位论文 > 优秀研究生学位论文题录展示

An Expectation Maximization Application for Decision Tree Classifiers on Datasets with Missing Values

作　者: Emmanuel Kayitaba 阿玛尼
导　师: 李宏
学　校: 中南大学
专　业: 计算机应用技术
关键词: 丢失数据填充决策树分类器最大期望值算法贝叶斯网络
分类号: TP311.13
类　型: 硕士论文
年　份: 2010年
下　载: 15次
引　用: 0次
阅　读: 论文下载

内容摘要

大量的丢失数据是数据挖掘、机器学习等实际应用中普遍存在并亟待解决的问题。丢失数据有很多原因造成,其中包括测量的失误,存储失败,数据丢失,数据装载等等。在之前的政治调查中,大约平均有半数的被调查者们不回答调查问题中的一个或一个以上的问题。在被观察数据丢失的可能性与数据值和其他变量没有相互关系的前提下,数据的丢失应当是随机的。在调查中,如果一个人因为自己生病了就遗漏数据,那他的数据将有可能会完全的随机丢失。如果收入少的人比收入多的人更愿意爆出他们的收入数据的话,个人收入数据将不会随机丢失。在一个假设,假如已婚的人比单身的人更容易说出他们的年龄的话,这样调查的数据将不会随机丢失,因为这样的丢失有婚姻状态矫正。只有在符合丢失不依赖于数据值的前提下,数据的丢失才会有随机性。随机丢失是建立在一个假设的基础上,即丢失值不是随机的分布于所有的观察值中问,而是随机的分布于一个或几个样本之中。非随机丢失,亦即不可忽略丢失,则是最有问题的丢失形式。这种丢失也在丢失值不随机分布于观察值之间时发生,但是这种丢失不能通过模型中的众多变量来预测。非随机丢失即区别于完全随机丢失和随机丢失之外。数据非随机丢失的情况,通常比较麻烦处理。得到一个没有偏差的参数估计值的唯一办法是建立丢失模型：即建立一个含有丢失数据的模型,之后将模型演化成一个更大使用范围的模型。针对数据集中数据丢失的问题,一些经典方法无法完满的解决实际问题。首先想到的也是最常见的方法即简单的忽略那些丢失的数据,仅仅分析剩下的数据,这种方法被称之为成列删除方法。这种方法会导致可用于分析的样本大量减少,有时候,假设丢失数据的随机性会导致无偏差估计。不幸的是,即使当数据完全随机丢失的情况下,这种方法就没有那么有效。当数据不是完全随机丢失时,得到的数据将有偏差(例如,当公司中收入低的人都选择不报他们的收入时,则统计到的数据将偏高)。另一种同样不佳的算法是成对删除方法。由于成对删除方法是在不同数据集的基础上通过使用不同的样本和标准差建立模型参数设置,因此很有可能产生不相关矩阵,导致妥协和停止分析。因此成对删除的方法仅适用于只存在少数丢失数据的情况。然而,成列删除方法和成对删除方法对数据分析会造成很大的损害。另外一种方法是通过剩余数据对丢失数据进行估计的填补方法。该方法通过已建数据集中可用信息替换丢失的数据。填补方法可以分为单一填补方法和多重填补方法,其中,单一填补方法只需用填补值替换丢失值而多重填补方法每个丢失数据都需要用n个可能值替换。其中，平均丢失数据填允法是最简单的方法。在这种方法中,丢失值被特定属性的平均值代替。然而这种方法不能用于绝对值数据的统计,而只能用于同列数据之间(即只能用于同性质的数据间)而非同一行数据之间。在hot-deck丢失数据填充法中,丢失数据则被类似情况中的数据或数据库中的记录代替。也即是说,在两个相似的记录中,如果其中一个记录数据有所丢失,我们可以依照另一个记录填充前一个数据。而在cold-deck丢失数据填充法中,我们则可以用外部数据的特定单个值来代替丢失值,而非用现有的数据值。假如在一个属性中丢了n个数据,那在所有的丢失情况下我们填入相同的值。在kNN丢失数据填允法中,如名字所示,一个个例中的丢失值将被k个附近的数据中的相似值填充。最近最相似的的数据将通过缩小欧氏距离来找到。本文探讨了解决数据丢失的优化算法,即基于最大期望值和贝叶斯网络填充丢失数据的算法,通过使用决策树分类器提高分类精度。通过实验分析,基于最大期望值和贝叶斯网络的填充算法可以满足我们的研究目标。期望最大值算法是解决有丢失数据或隐藏数据存在的情况下的一种行之有效的迭代法。在最大可能估计法中,我们希望得到相似模型参数的估计值。期望最大值算法的每一个迭代都包含了两个过程：期望阶段和最大化阶段。在期望阶段,丢失数据可以通过已有数据和现有模型参数的估计值来估计得到。正如其名,这种方法是通过有条件的期望得到。在放大阶段,似然函数是在丢失数据已知的前提下被放大的。从期望阶段得到的丢失数据的估计被实际丢失的数据取代。由于算法使可能性在每一次迭代后增加,算法必定收敛。朴素贝叶斯算法建立在一个假设上：即一个性质的的出现(或丢失)和其他性质的出现(丢失)无关。这种假设叫作群体条件无关性,被用来简化算法中的计算,所以叫“朴素贝叶斯算法”。每一个训练实例都能增加/减少一个假设正确的可能性,这样之前的知识就可以和观察到的数据结合起来。即使当贝叶斯方法难处理的情况下,其仍然能够提供一个最有的相对于其他方法更有效的最优决策标准。朴素贝叶斯预测要求每一个条件概率不为零。朴素贝叶斯分类法则需要一个较小的训练实例数量来估计分类所需的参数(平均值和变量变化)。在变量独立的假设下,只有各个类别中变化的变量需要确定,而非整个矩阵。另外,朴素贝叶斯算法在大多数情况下结果较好,且是比较容易实现的方法。我们通过实验方法对多个UCI数据集进行的分析与比较得出,基于最大期望的贝叶斯网络算法优于其他三种经典算法(Mean算法,朴素贝叶斯算法,kNN算法),并且有着更高的分类准确率。这不仅体现在单个算法的比较上,在三种算法同时作用时也同样如此。我们的算法在对四个原始数据集(听觉,威斯康辛乳腺癌,肝炎,蘑菇)的天然丢失数据的填允上优于其他三种算法,而在威斯康辛乳腺癌这一数据集中达到了96.14%的最高精度。本文通过选取8种丢失数据集进行丢失率和精确率的比较来证明该算法在性能上优于其他三种算法。

全文目录

Abstract  4-6
摘要  6-10
Table of Contents  10-12
List of Abbreviations  12-13
List of Figures  13-14
List of Tables  14-15
Chapter 1 Introduction  15-19
  1.1 Motivation  15
  1.2 Research Objectives  15
  1.3 Introduction to Data Classification  15-16
  1.4. Classification Techniques  16-17
  1.5 Introduction to the Missingness of Data  17
  1.6 Expectation Maximization Algorithm  17
  1.7 Structure of the Thesis  17-19
Chapter 2 Data Missingness and Supervised Classification Techniques  19-28
  2.1 Missing Completely At Random(MCAR)  19
  2.2 Missing At Random(MAR)  19-20
  2.3 Missing Not at Random(MNAR)  20-21
  2.4 Supervised Classification Techniques  21-28
    2.4.1 Naive Bayes Classification  21-23
    2.4.2 Decision Trees  23-27
      2.4.2.1 Steps in Mining with Decision Trees  24-25
      2.4.2.2 Attribute Selection  25-26
      2.4.2.3 Advantages of Decision Trees  26
      2.4.2.4 Applications of Decision Trees  26-27
    2.4.3 Lazy Learning Classification  27-28
      2.4.3.1 Introduction to Lazy Learning  27
      2.4.3.2 Instance-based typical approaches  27-28
Chapter 3 EM-Based Bayesian Network Imputation  28-38
  3.1 Problem Statement  28-29
  3.2 Data Imputation Methods  29-30
    3.2.1 Mean Imputation  29-30
    3.2.2 Hot Deck Imputation  30
    3.2.3 Cold Deck Imputation  30
    3.2.4 K -Nearest Neighbour Imputation  30
  3.3 The Expectation Maximization algorithm  30-31
  3.4 Theory of Our Algorithm  31-33
  3.5. Our Expectation Maximization Bayesian Network Imputation Algorithm  33-38
    3.5.1 Introduction  33-34
    3.5.2 Symbol Definition  34-35
    3.5.3 Algorithm Description and Analysis  35-36
    3.5.4 Pseudocode of EBN Imputation Algorithm  36-38
Chapter 4:Experimental Design and Analysis of Results  38-48
  4.1 Implementing the EBN Algorithm  38
  4.2. Methodological experimental approach  38-39
  4.3 Selection and Setup of Training and Testing Datasets  39-40
    4.3.1 Choosing UCI Repository Datasets and other Datasets  39-40
    4.3.2 Introduction of different missing rates  40
  4.4 EBN Evaluation  40-46
    4.4.1 Evaluating EBN using the Four Original Datasets  41-43
    4.4.2 Evaluating EBN using Different Missingness of Data Rates  43-46
  4.5 Discussions  46-48
Chapter 5 Conclusion and Future Work  48-50
  5.1 Conclusion and Contribution  48-49
  5.2 Future Work  49-50
Acknowledgment  50-51
References  51-56
Appendix:List of publication and achievements  56

An Expectation Maximization Application for Decision Tree Classifiers on Datasets with Missing Values

内容摘要

全文目录

相似论文