毕业论文——基于C4.5算法的空间分类应用探究.doc

1、 本 科 毕 业 设 计（论文） 题 目： 基于 C4.5算法的空间分类应用探究 学生姓名： 学 号： 专业班级：地理信息系统 指导教师： 20 年 6 月 20日中国石油大学（华东）本科毕 业设计 (论文 ) 基于 C4.5算法的空间分类应用探究 摘 要 随着大数据时代的到来，通过数据挖掘获取海量数据背后的知识变得尤为重要。而空间数据是大数据的基础使得空间数据挖掘意义更为突出。其中空间分类是空间数据挖掘近年来较活跃的一个分支。 本文基于决策树算法中的 C4.5 算法，以 94年美国部分人口收入数据为例进行了空间分类应用研究。 C4.5 算法采用信息增益率作为选择分支属性的标准，分类得到一组判

2、断个人年收入是否大于 5万美金的规则用于预测人口收入，并得到不同因素对收入影响力的排序。其中工作周数、年龄、学历和性别对于收入的影响，提醒我们需要进一步促进就业，普及高等教育，消除性别歧视以及给年轻人创造更多的机会。 将分类结果与空间信息相关联后直观地展示到地图上，可以看到各行业的人口收入在各地区间的一些差异，有利于进一步挖掘空间知识，指导各地区乃至国家的经济部署。 关键词 ：空间数据挖掘；空间分类； C4.5 算法；人口收入 中国石油大学（华东）本科毕 业设计 (论文 ) Research and Application of Spatial Classification Based on

3、C4.5 Algorithm Abstract Along with the Big Data era, seizing the knowledge behind the huge data by data mining is very important. According to the knowledge people can forecast the unknown information from the known data attributes. Spatial data is the basis of the Big Data. So spatial data mining b

4、ecomes extremely significant. Spatial classification is a hot direction of spatial data mining. The thesis chose the census income data in 1994 from U.S. Census Bureau for classification based on C4.5 algorithm. C4.5 algorithm uses information gainratio to select the attributes for classification. T

5、he algorithm produced a set of rules which can judge and predict if the personal annual income is beyond 50,000$. According to the rules, the thesis got the different degrees of these attributes influential power on income. The influences of attributes like work-weeks, age, sex and education give us

6、 the suggestions that we should still promote employment, education, reduce sexism and create more opportunities for young people. The classification results can be related to the spatial data and showed on the Map. And we can find the differences of census income from different industries in variou

7、s areas. Spatial knowledge can be found more easily to be used for guiding the plan of economy in these areas even the country. Keywords： spatial data mining; Spatial Classification; C4.5 Algorithm; census income 中国石油大学（华东）本科毕 业设计 (论文 ) 目 录 第 1 章 引言 . 1 1.1 研究背景 . 1 1.2 研究意义 . 2 第 2 章 空间数据挖掘 . 4 2.1

8、 数据挖掘 . 4 2.2 空间数据挖掘 . 5 2.2.1 空间聚类 . 5 2.2.2 空间分类 . 6 2.2.3 空间关联规则 . 7 2.2.4 空间趋势预测 . 7 第 3 章 决策树分类算法 . 8 3.1 决策树算法综述 . 8 3.2 C4.5 分类算法原理 . 9 第 4 章 数据预处理 . 11 4.1 数据来源 . 11 4.2 数据属性值的选取与特殊样本的剔除 . 11 4.3 数据缺失值处理与字符串的数值化 . 12 第 5 章 决策树 分类 结果 与 讨论 . 15 5.1 决策树分类结果 . 15 5.2 分类结果的讨论 . 19 第 6 章 结论 . 25 致

9、 谢 . 27 参考文献 . 28 附 录 . 29 附录 A 按工种分类各区域人口收入分布表 . 29 附录 B C4.5 决策树算法流程图 . 30 第 1 章 引言 1 第 1章 引言 1.1 研究背景 随着计算机网络与移动通讯技术的高速发展，人类所拥有的数据正在经历着爆炸式的增长，大数据时代已经不可阻挡地到来了。面对大数据 ，人们迫切需要获取海量数据背后的重要信息和知识，发现数据中存在的关系和规则，并根据现有数据对未来的发展做出预测。其中空间数据是大数据的基础，约 80%的数据与空间位置有关 1。 因此对于空间数据进行挖掘具有十分重要的意义。 数据挖掘技术综合了人工智能、数据库系统、专

10、家系统、统计学、机器学习、信息科学和可视化等多个学科领域，经过近 20 年的研究和改进已经形成了一套较为完整的理论体系和技术体系。数据挖掘是指从大量的、模糊的、随机的、有噪声的、不完全的数据中，提取隐藏在其中的、人们事先不知道的但又是有用的信息和知识 的过程。 空间数据挖掘即指以空间知识为主的数据挖掘。这里的空间知识主要指空间的关联、特征、分类及聚类等规则和异常检测 2。它是计算机技术、数据库应用技术和管理决策支持技术等发展到一定阶段、多学科交叉的新兴边缘学科，汇集了来自机器学习、模式识别、数据库、空间统计学、人工智能以及地理信息系统等各学科的成果 3。 空间数据挖掘的方法主要有空间聚类，空间

11、分类，空间关联规则以及空间趋势预测等等。而决策树算法（ Decision Tree Algorithm）是用于分类和预测的主要算法，它通常从一组无规则的事例推理出 以决策树形式表达的分类规则，利用自顶向下的递归方式，不断在决策树内部节点进行属性值比较，根据不同属性判断是否从该节点向下分支，并在决策树的叶结点得到结论。所以，从根节点到叶结点对应着一条分类规则，一整棵树就对应了一组表达式规则。决策树算法的一个最大优点就是它在学习过程中不需要获取很多背景知识，只要训练样本能用属性加结论的方式表达出来，就能用决策树算法进行学习。 决策树分类算法里 C4.5 算法是空间数据挖掘中最常用、最经典的分类算法

12、之一，能够以图形化的形式展示挖掘结果，从而方便使用者快速做出决定或预测。决策树分 类算法在各行业都有广泛应用，如自然地理综合区划、灾害风险区划、农业区划、交通管理、流行病预测、人口统计以及客户资源管理（ CRM）系统等。 第 1 章 引言 2 1.2 研究意义 数据挖掘是现代数据研究领域的重要技术，是能够给使用者带来收益的一项技术手段，其无论在商业领域还是在研究领域中都占有非常重要的地位，对该项技术的研究也就无可厚非的成为了各领域关注的重点，其重要性和意义如下： (1)数据挖掘可以提升信息服务层次； (2)数据挖掘可以提升政府、企业以及研究机构对信息的把握程度； (3)数据挖掘为决策提供可靠的

13、技术支持。 其中空间 数据挖掘中的空间分类算法是属于预测式数据挖掘的一种数据分析方法，其目的是根据重要样本数据集找出能准确描述并区分数据类或概念的模型，以便依据实体的属性值及其它约束条件将其划分到某个数据类别中去。分类是已知现存的类别，要建立类别的描述规则，并对新例的观察值判别归类，在机器学习中这种分类被称为有指导学习或有监督学习。分类对象通常表示为数据库表或者文件中的记录，分类工作包括向数据库中添加一个新列，并给出某种分类代码。分类工作首先要对所要处理的数据进行合理的分析处理，有一个清晰定义的类，还要有一系列已分类实例。分类似 乎是人类的规则，为了理解并与周围环境交互，人们每天都在归类、分类

14、以及分级。分类包括考察一类新出现的对象的特征，并归类到已定义类中。因此空间分类的意义有： （ 1）以空间对象的方位、距离或形态和连通关系把它们映射到有意义的的不同类别； （ 2）通过空间分类解决区划问题，可将分到同一类的地区划到一个区域； （ 3）通过空间分类解决预测问题，可利用分类准则预测未知的分类结果。 本文以居民的收入数据为例进行分类研究。居民收入水平的高低直接影响其生活质量的好坏，收入分配是否均匀关系到社会的和谐与稳定 。对居民的收入情况进行调查统计，对人口收入数据进行分类发掘人口收入数据中对收入影响较显著的因素，根据这些因素的变化来预测某地区的收入变化，或者改善相应环境以提高人口收入

15、对于一个国家或地区具有十分重要的意义。同时，在分类过程中选取一定的空间属性信息进行关联，从数据中挖掘空间信息，直观地展示到地图上，有利于发现收入及相关因素在空间分布上可能存在的不均衡，根据收入的差距可划分不同区域（区划参考），从而对于一个地区或国家下一步的投资发展提供一定的决策参考。 本课题主要以美国人口普查局 1994 年间的人口与收入数据为训 练样本，使用 C 4.5第 1 章 引言 3 算法进行决策树分析，将可能影响人口收入的一些空间属性，比如研究对象的父母的出生国，本人的出生国、国籍，本人是否有从乡村向大都市区迁移以及现在的住址位于美国的哪个区域，哪个州等等空间数据，以及其他对于收入影

16、响较为明显的非空间属性，如年龄、性别、学历、一年中工作的周数等作为分类的依据，通过 C4.5 算法寻找影响力较强的因素，理解 C4.5 算法相对于 ID3 算法的改进。通过对分类的结果进行分析，并展示到空间上，我们可能发掘出一定的空间知识，并可以对人口的收入情况进行预测。找到哪些因素对个人年收入大 于 5 万美金呈现正相关关系，可以用于指导人们提高个人收入，以及发现社会中导致收入差距存在的一些影响因素，缩小收入差距，促进收入分配的公平。第 2 章 空间数据挖掘 4 第 2章 空间数据挖掘 2.1 数据挖掘 数据挖掘是新兴的一门技术学科，起源于 1989 年于底特律（美国）举行的第一届KDD（从

17、数据库中发现知识）国际学术会议。 1994 年在加拿大举行的地理信息系统国际会议上，李德仁院士第一次提出了从地理信息系统数据库中发现知识的理念，也就是 KDG英文名称即： knowledge discovery from GIS。第一届知识发现与数据挖掘（ knowledge discovery and data mining）的国际会议于 1995 年在加拿大召开。数据库中的数据在会议上被形象地比喻成了矿床，由此诞生崭新的数据挖掘学科（ DM, data mining, 又译作数据发掘、数据开采或数据采掘等）。 数据挖掘技术综合了人工智能、统计学、数据库系统、专家系统、机器学习、信息科学和可

18、视化等多个学科领域，经过近 20 年的研究和改进已经形成了一套较为完整的理论体系和技术体系。数据挖掘是指从大量的、模糊的、随机的、有噪声的、不完全的数据中，提取隐藏在其中的、人们事先不知 道的但又是有用的信息和知识的过程。这些信息和知识能够以概念、规律、规则和模型等形式表达 4。数据挖掘涉及数据、信息和知识三个基础概念，这三个概念如同几何上线、面、立体之间的关系，其中数据是原始的未解释的符号或信号，比如 0、 1；信息则是有一定解释或意义的数据，例如 SOS；而知识是综合信息形成的观点及普适性的理论，信息与数据相连，知识则同时与数据和信息相关。 通过数据挖掘一般可以得到以下结果： （ 1） 从

19、数据中形成模型； （ 2） 从数据中派生出新数据； （ 3） 从数据中获取知识与规律，达到更充分利用数据的目的 数据挖掘可以分为两种类 型：数据驱动和模型驱动。数据驱动方法是基于已有数据里面说发现的模式而创建的模型，这种新式模型必须在被确认正确之前进行检验，模型的建立过程是交互的，最终模型一般由新发现的信息和历史经验结合来完成 5。与之相反，模型驱动的数据挖掘要求用户根据可利用的数据建立的模型或者历史经验，估计模型参数，然后也要检验模型是否有效，模型的主要用途是描述和预测。数据挖掘中的知第 2 章 空间数据挖掘 5 识发现要依靠这样两种方法的协同作用，数据驱动与模型驱动在数据挖掘过程中的关系如

20、图 2-1所示。 图 2-1 数据驱动和模型驱动的数据挖掘过程（据 Gahegan et al.， 2001） 2.2 空间数据挖掘 空间数据挖掘即指以空间知识为主的数据挖掘。这里的空间知识主要指空间的关联、特征、分类及聚类等规则和异常检测 2。它是计算机技术、管理决策支持技术以及数据库应用技术等发展到一定阶段的新兴边缘学科，汇集了来自数据库、空间统计学、机器学习、模式识别、人工智能以及 GIS 等各学科的成果 3。空间数据具有高维的数据结构，包含了拓扑、方位、距离等信息。空间数据挖掘是为了解决“空间数据爆炸但知识贫乏”的现象而不断发展起来的。它的研究对象主要有 Spatial Databas

21、e 或 Spatial Data Warehouse。空间数据挖掘与传统的地学数据分析相比，更强调在隐含未知情况下对空间数据本身进行分析并挖掘规律，空间知识分析工具获得的信息会更概括和精炼 6。 2.2.1 空间聚类 空间聚类分析是指通过空间对象的相似特征，将它们聚成一类，目的是发现研究对象在空间上的相连、相邻和共生等关系。由于空间聚类通常是对图形直接聚类，导致聚类形状复杂、数据量大，因此采用经典的多元统计分析的方法就显得速度慢、效率低，这对空间聚类算法提出了更高要求，以下对于常用的一些聚类算法基于六个 指标进行了比较，比较结果见表 2-1： 第 2 章 空间数据挖掘 6 表 2-1 聚类算法

22、比较 2.2.2 空间分类 空间分类是指通过空间对象的方位、距离或形态和连通关系把它们映射到有意义的的不同类别。很多区划问题和空间预测问题都可以通过空间分类来实现，例如自然地理综合区划、灾害风险区划和农业区划以及流行病趋势预测等课题。 空间分类作为最近较为活跃的一个分支也属于空间挖掘领域。其中决策树分类技术是迄今为止发展最为成熟的一种概念学习方法。它产生于上个世纪的六十年代，前身为由 Hunt 等人在研究人类概念建模的时候所建立的学习系统，到了上世 纪的七十年代， J Ross Quinlan 提出了 ID3 算法，此算法旨在减少树的深度。然而忽略了叶子数目的研究。1975 年和 1984 年

23、，分别有人提出 CHAID（ Chi-squared Automatic Interaction Detection）和 CART（ Classification and Regression Tree，亦称 BFOS）算法。 1986年， J.C.Schlimmer 提出 ID4 算法。 1988 年， P.E.Utgoff 提出 ID5R 算法。 1993 年， Quinlan本人以 ID3 算法为基础研究出 C4.5/C5.0 算法， C4.5 算法在 ID3 算法的基础上进行了改进，对于预测变量的缺值处理、剪枝技术、派生规则等方面作了较大的改进，既适合于分类问题，又适合于回归问题。 决策树分类算法的优点如下：（ 1）分类精度高；（ 2）生成的模型简单；（ 3）对噪声数据有特别好的鲁棒性。因而成为目前应用极其广泛的归纳推理算法之一，在数据挖掘理论中受到了广泛的关注。 而决策树分类算法中的 C4.5 算法是空间数据挖掘中最常用、最经典的分类算法之一，能够以图形化的形式展示挖掘结果，从而方便使用者快速做出决定或预测。决策树