Effects of Different Pre-processing Strategies:A Comparative Study on Decisision Tree Algorithms

摘要

信息技术的增殖和普及极大地丰富了收集数据的途径，使大规模的数据存储成为可能。随着可用数据在规模和复杂性上的不断增长，人与人之间直接的数据分析被间接的自动数据处理不断增强。以往数据挖掘技术主要是由相对复杂的、拥有良好技术背景的“专家”用户所使用，与此不同的是，目前越来越多更加“幼稚”的用户开始使用这些技术来进行决策。这必然需要制定一些规则来指导数据分析师或管理人员根据数据的性质决定使用哪些特定的算法。对数据与处理阶段所使用的不同策略带来的影响的理解有助于制定最佳做法，同时增加模型的价值和精确度。通常来说，数据挖掘技术可以用来对描述性任务进行预测，即基于其他属性的预测值来确定特定属性的预测值，或者派生出一些用于总结数据内部潜在关系的模式。数据挖掘技术是一个嵌入在数据库中的模式自动发现过程。它是一个跨学科技术，融合了统计分析、数据库系统、机器学习、模式识别、神经网络、模糊系统以及其他“软计算”技术。凭借其将数据转换成信息的能力，近些年数据挖掘技术几乎被应用于生活的各个方面，例如商务，市场营销，医疗，电信，银行，基建公司，教育等。
　　 核心数据挖掘技术由此可以用于预测性建模，包括分类（当目标类是数字时，可以看成回归）和聚类、关联分析和异常检测。分类和预测是两种形式的数据分析方法，可用于帮助提取模型以描述重要数据类或预测未来的数据趋势，使我们更好地理解数据。一般而言，分类用来预测分类标签，预测模型用来于此连续值型函数。在各种现有的分类算法中，使用归纳学习机制的决策树仍然是目前最流行、最实用和有效的方法。决策树对于构建分类或数据勘探而言确实是首选工具，主要是因为一些因素的影响:1）决策树是简单易懂，并进行简要说明后，因为他们可以很容易地理解;2）决策树在这个意义上没有假设的空间分布和分类结构的非参数;3）能够与缺失值处理的数据集，以及定性数据;4)决策树可以同时处理数值和分类数据，其它技术通常专门用于分析只有一个变量的数据集类型。例如，关系规则只能应用于名义变量，而类神经网络只于数值变量共事。5）他们产生更好的精度，并无疑是强大的，即使当他们的假设是有点违反了真实模型产生的数据，他们仍旧表现良好。虽然各种各样的决策树算法已经被开发出来，常见的决策树算法的基本实现的基础上只是几个算法，本文称之为“传统”的算法，包括ID3，其继任者的C4.5车和CHAID。然而，它对考虑的概率计算方法，因为它使用卡方统计量来确定最佳分裂属性，因此，通常使用的统计软件包，例如STATISTICA。这里被称为传统的方法，以巩固存在一些决策树算法的改进和实现较为先进的这些基本决定树实现。这些领先的方法已确定与传统的算法克服一些特定的缺点。
　　 本文旨在重点分析在预加工过程中不同的策略对决策树算法性能的影响，从而开改进价值及模型精度的最佳方式。这可以通过对其表现进行调查，根据现有数据类型、数据分布、数据丢失现象、如何处理这样的数据集以发展为同一分类、采用不同的离散化数据的策略带来的影响、不同特征降维技术、效率和可扩展性问题等等，从而开展比较评估分析。
　　 本文进行了比较评估分析实验，并对最前沿的分类和预测算法进行了调查和简要讨论。对有关分类和预测以及构建分类器的一些重大问题进行了认定和处理，得出以下主要成果:1.简单的决策树可以被用来模仿其他分类器的性能，并有相当不错的表现，使其成为初始用户或者数据探索的早期阶段的不二选择。2.由于其简单、执行时间短、与负载呈线性比例关系、相对较小规模的树便可以提高其可理解性等性能，将ID3与正确的预加工方法想结合可以成为用于探索新的数据的重要工具。3.另一方面，离散化确实能影响到所得模型的性能，因此它总是需要通过类分布来完成。4.离散也可以用于克服在使用C4.5中对信息分割的需要，从而处理许多相应的分割值。因此，在完成缺失值的离散化和更换基础上，ID3可以轻易被用于估计C4.5算法的性能。5.所有传统的树算法似乎在性能方面都遵循相同的模式，这表明任一传统方法是其他算法运行的代表。因此，如果一个较低的性能被登记在一种算法里，那么其他高级的算法也应该被整理。6.不同决策树算法的性能，在准确度方面都是与属性数量以及分类属性值相互独立的。7.当数据足够大时，通过属性约简技术可以实现近似并在技术选择上具有更大的灵活性。8.丢失数据的替代应根据给定属性的模态值（对整个数据集而言），与所在类无关。
　　 在本研究领域未来的发展方向主要有两点。第一，在该领域的研究应着眼于开发一些概念，可以在不同决策树算法的运用中提供指导，并考虑到数据集所包含的数据类型，依据目前属性或者实例数量得出的分布及规模。第二，可以开展更多的实验来调查预处理、数据清理以及替换缺失值的性能，在建立在不替换基础上的统计方法并通过使用数据集中的所有类的模态属性值来完成有机会获得更好的表现。

目录

声明

Abstract

摘要

Table of Contents

List of Figures

List of Tables

Chapter One Introduction

1．1 Background

1．2 Statement of the problem

1．3 The aim and objectives of the study

1．4 Outline of the thesis

Chapter Two Literature Review

2．1 Classification and Prediction

2．2 Decision Tree Induction

2．3 Merits and Demerits of Decision Trees

2．4 Decision Tree Algorithms

2．5 Related work

2．6 Discussion

2．7 Summary

Chapter Three Methodology

3．1 Supervised vs Unsupervised Discretization

3．2 Dealing with Missing Values

3．3 Dealing with Attribute Selection and Reduction

3．4 Type and Distribution of Data

3．5 Effects of Increased Workload

3．6 Accuracy Evaluation

3．7 Summary

Chapter Four Results and Analysis

4．1 Preamble

4．2 Experiments and Results of Discretization

4．3 Experiments and Results for Missing Values

4．4 Experiments on Attribute Selection and Reduction

4．5 Experiments on Type and Distribution of Data

4．6 Experiments on Effects of Increased Workload

4．7 Experiments on Performance of the Algorithms Based on Accuracy

4，8 Results Analysis

4．9 Further Experiments Based on Kenya Population Census Data

4．10 Summary

Chapter Five Conclusion and Future Work

References

Acknowledgement

Publications

Appendix Summarized Kenyan Population Census Data Collumn Abrreviations-Collumn Names