空间数据挖掘算法课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《空间数据挖掘算法课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 空间 数据 挖掘 算法 课件
- 资源描述:
-
1、空间数据挖掘算法 数据挖掘数据挖掘数据库越来越大数据库越来越大有价值的知识有价值的知识可怕的数据可怕的数据数据爆炸,知识贫乏数据爆炸,知识贫乏 苦恼:淹没在数据中;不能制定合适的决策!数据数据n模式模式n趋势趋势n事实事实n关系关系n模型模型n关联规则关联规则n序列序列n目标市场目标市场n资金分配资金分配n贸易选择贸易选择n在哪儿做广告在哪儿做广告n销售的地理位置销售的地理位置n金融金融n经济经济n政府政府nPOS.n人口统计人口统计n生命周期生命周期一、概念和术语一、概念和术语1.1 1.1 数据挖掘数据挖掘 /知识发现知识发现(1)数据挖掘数据挖掘是从存放在数据集中的大量数据挖掘出有趣知识
2、的过程。(2)数据挖掘,又称为数据库中知识发现数据库中知识发现(Knowledge Discovery in Databases)或知识发现知识发现,它是一个从大量数据中抽取挖掘出未知的、有价值的模式或规律等知识的非平凡过程,它与数据仓库有着密切的联系。(3)广义的数据挖掘是指知识发现的全过程;狭义的数据挖掘是指统计分析、机器学习等发现数据模式的智能方法,即偏重于模型和算法。(4)数据库查询系统和专家系统不是不是数据挖掘!在小规模数据上的统计分析和机器学习过程也不应算作数据挖掘。1.2 1.2 机器学习机器学习(1)对于某类任务T和性能度量P,如果一个计算机程序在T上以P衡量的性能随着经验E而
3、自我完善,那么这个计算机程序被称为在从经验E学习。(2)机器学习是知识发现的一种方法,是指一个系统通过执行某种过程而改进它处理某一问题的能力。1.3 1.3 数据挖掘的对象数据挖掘的对象(1)关系型数据库、事务型数据库、面向对象的数据库;(2)数据仓库/多维数据库;(3)空间数据(如地图信息)(4)工程数据(如建筑、集成电路的信息)(5)文本和多媒体数据(如文本、图象、音频、视频数据)(6)时间相关的数据(如历史数据或股票交换数据)(7)万维网(如半结构化的HTML,结构化的XML以及其他网络信息)1.4 1.4 数据挖掘的步骤数据挖掘的步骤(1)数据清理(消除噪音或不一致数据,补缺);(2)
4、数据集成(多种数据源可以组合在一起);(3)数据选择(从数据库中提取相关的数据);(4)数据变换(变换成适合挖掘的形式);(5)数据挖掘(使用智能方法提取数据模式);(6)模式评估(识别提供知识的真正有趣模式);(7)知识表示(可视化和知识表示技术)。1.6 1.6 数据分类的基本过程数据分类的基本过程(1)第一步:对一个类别已经确定的数据集创建模型。用于创建模型的数据集称为训练集,训练集中单个元组称为训练样本。训练集中每一个元组都属于一个确定的类别,类别用类标号标识。(2)第二步:使用创建的模型将类别未知的元组归入某个或某几个类中。1.6 1.6 支持数据挖掘的关键技术支持数据挖掘的关键技术
5、(1)数据库/数据仓库/OLAP(2)数学/统计(回归分析:多元回归、自回归;判别分析:Bayes判别、Fisher判别、非参数判别;主成分分析、相关性分析;模糊集;粗糙集)(3)机器学习(聚类分析;关联规则;决策树;范例推理;贝叶斯网络;神经网络;支持向量机;遗传算法)(4)可视化:将数据、知识和规则转化为图形表现的形式。二、决策树分类概述二、决策树分类概述决策树学习是归纳推理算法。它是一种逼近离散函数的方法,且对噪声数据有很好的健壮性。在这种方法中学习到的知识被表示为决策树,决策树也能再被表示为多个if-then的规则,以提高可读性。决策树提供了一种展示类似在什么条件下会得到什么值这类规则
6、的方法。比如,在贷款申请中,要对申请的风险大小做出判断,右图是为了解决这个问题而建立的一棵决策树,从中我们可以看到决策树的基本组成部分:决策节点、分支和叶子。决策树中最上面的节点称为根节点,是整个决策树的开始。本例中根节点是“收入¥40,000”,对此问题的不同回答产生了“是”和“否”两个分支。决策树的每个节点子节点的个数与决策树在用的算法有关。如CART算法得到的决策树每个节点有两个分支,这种树称为二叉树。允许节点含有多于两个子节点的树称为多叉树。每个分支要么是一个新的决策节点,要么是树的结尾,称为叶子。在沿着决策树从上到下遍历的过程中,在每个节点都会遇到一个问题,对每个节点上问题的不同回答
7、导致不同的分支,最后会到达一个叶子节点。这个过程就是利用决策树进行分类的过程,利用几个变量(每个变量对应一个问题)来判断所属的类别(最后每个叶子会对应一个类别)。例子:例子:假如负责借贷的银行官员利用上面这棵决策树来决定支持哪些贷款和拒绝哪些贷款,那么他就可以用贷款申请表来运行这棵决策树,用决策树来判断风险的大小。“年收入¥40,00”和“高负债”的用户被认为是“高风险”,同时“收入5年”的申请,则被认为“低风险”而建议贷款给他/她。到现在为止我们所讨论的例子都是非常简单的,树也容易理解,当然实际中应用的决策树可能非常复杂。假定我们利用历史数据建立了一个包含几百个属性、输出的类有十几种的决策树
8、,这样的一棵树对人来说可能太复杂了,但每一条从根结点到叶子节点的路径所描述的含义仍然是可以理解的。决策树的这种易理解性对数据挖掘的使用者来说是一个显著的优点。然而决策树的这种明确性可能带来误导。比如,决策树每个节点对应分割的定义都是非常明确毫不含糊的,但在实际生活中这种明确可能带来麻烦(凭什么说年收入¥40,001的人具有较小的信用风险而¥40,000的人就没有)。建立一颗决策树可能只要对数据库进行几遍扫描之后就能完成,这也意味着需要的计算资源较少,而且可以很容易的处理包含很多预测变量的情况,因此决策树模型可以建立得很快,并适合应用到大量的数据上。对最终要拿给人看的决策树来说,在建立过程中让其
9、生长的太“枝繁叶茂”是没有必要的,这样既降低了树的可理解性和可用性,同时也使决策树本身对历史数据的依赖性增大,也就是说这是这棵决策树对此历史数据可能非常准确,一旦应用到新的数据时准确性却急剧下降,我们称这种情况为训练过度。为了使得到的决策树所蕴含的规则具有普遍意义,必须防止训练过度,同时也减少了训练的时间。因此我们需要有一种方法能让我们在适当的时候停止树的生长。常用的方法是设定决策树的最大高度(层数)来限制树的生长。还有一种方法是设定每个节点必须包含的最少记录数,当节点中记录的个数小于这个数值时就停止分割。与设置停止增长条件相对应的是在树建立好之后对其进行修剪。先允许树尽量生长,然后再把树修剪
10、到较小的尺寸,当然在修剪的同时要求尽量保持决策树的准确度尽量不要下降太多。基本决策树算法就是一个贪心算法。它采用自上而下、分而制之的递归方式来构造一个决策树。通常,决策树是一种自顶向下增长树的贪婪算法,在每个结点选取能最好地分类样例的属性。继续这个过程直到这棵树能完美分类训练样例,或所有的属性都使用过了。“信息增益”用于衡量属性的价值。熵(entropy)是一种度量信息增益的指标,它描述了样本的纯度(purity)。下面是熵的定义:Entropy=-Pilog2Pi通常的分割算法在决定怎么在一个节点进行分割时,都只考察一个预测变量,即节点用于分割的问题只与一个变量有关。这样生成的决策树在有些本
11、应很明确的情况下可能变得复杂而且意义含混,为此目前新提出的一些算法开始在一个节点同时用多个变量来决定分割的方法。比如以前的决策树中可能只能出现类似“收入¥35,000”的判断,现在则可以用“收入¥35,000或抵押150,000”这样的问题。注意点:注意点:(1)避免过度拟合,应该适度剪枝;(2)连续值的离散化;(3)处理缺失值的方法:最常见值、按概率分配;(4)处理权重不同的属性常用实现算法:常用实现算法:CART、ID3、ASSISTANT、C4.5聚类技术将数据元组视为对象。它将对象划分为聚类,使在一个聚类中的对象“类似”,但与其它聚类中的对象“不类似”。系统聚类是根据多种地学要素对地理
12、实体进行划分类别的方法,对不同的要素划分类别往往反映不同目标的等级序列,如土地分等定级、水土流失强度分级等。系统聚类的步骤一般是根据实体间的相似程度,逐步合并若干类别,其相似程度由距离或者相似系数定义。进行类别合并的准则是使得类间差异最大,而类内差异最小。通常,类似性基于距离,用对象在空间中的“接近”程度定义。聚类的“质量”可以用“直径”表示;而直径是一个聚类中两个任意对象的最大距离。质心距离是聚类质量的另一种度量,它定义为由聚类质心(表示“平均对象”,或聚类空间中的平均点)到每个聚类对象的平均距离。三、三、聚类分析聚类分析绝大多数应用采用了以下两个比较流行的基于划分的方法,这些基于划分的聚类
13、方法对在中小规模的数据库中发现球状簇很适用。(1)k-means算法,在该算法中,每个簇用该簇中对象的平均值来表示。(2)k-medoids算法,在该算法中,每个簇用接近聚类中心的一个对象来表示。聚类分析方法聚类分析方法基于层次的方法:层次的方法对给定数据集合进行层次的分解。根据层次的分解如何形成,层次的方法可以被分为凝聚或分裂方法。(Chameleon,CURE,BIRCH)基于密度的方法:只要临近区域的密度超过某个阈值,就继续聚类。避免仅生成球状聚类。(DBSCAN,OPTICS,DENCLUE)基于网格的方法:基于网格的方法把对象空间量化为有限数目的单元,所有的聚类操作都在这个量化的空间
14、上进行。这种方法的主要优点是它的处理速度很快。(STING,CLIQUE,WaveCluster)基于模型的方法:为每个簇假设一个模型,发现数据对模型的最好匹配。(COBWEB,CLASSIT,AutoClass)四、主成分分析四、主成分分析地理问题往往涉及大量相互关联的自然和社会要素,众多的要素常常给模型的构造带来很大困难,同时也增加了运算的复杂性。为使用户易于理解和解决现有存储容量不足的问题,有必要减少某些数据而保留最必要的信息。由于地理变量中许多变量通常都是相关联的,就有可能按这些关联关系进行数学处理达到简化数据的目的。主成分分析主成分分析是通过数理统计分析,求得各要素间线性关系的实质上
15、有意义的表达式,将众多要素的信息压缩表达为若干具有代表性的合成变量,这就克服了变量选择时的冗余和相关,然后选择信息最丰富的少数因子进行各种聚类分析,构造应用模型。设有n个采样点,每个采样点有m个变量,采样数据集合X的矩阵表示为:若将原始数据转换为一组新的特征变量,即主成分 。主成分是将原变量 的线性组合且具有正交特性:其中 按方差比例依次称为原变量的第一、第二、和第p主成分。实际操作时,往往挑选几个方差比例最大的主成分,这样既可减少变量的数目,又抓住了主要矛盾。nmnnmmxxxxxxxxxX.212222111211m)pp,1izi()m1(xiimnmnnmmxxxxxxaaaaaa.Z
16、21212222111211pzz,.,z21可以看出,主成分分析的数学实质是:寻找以取样点为坐标轴,以变量为矢量的m维空间中椭球体的主轴,主轴即为变量之间的相似稀疏矩阵中p个较大特征值所对应的特征向量。通常,可以用雅可比(Jacobi)法计算特征值和特征向量。五、层次分析法GIS中层次分析法(AHP,Analytic Hierarchy Process)实质上是一种基于地理区域的、模仿人的思维过程的、定性定量分析相结合的系统分析方法。该法把人的地理思维过程层次化和数量化,并用数学方法进行描述,进而为各类与地理区域相关的分析、决策、预报和控制提供定量依据。通常,层次分析中的最高层为目标层,该层
17、只有一个目标元素,当然,该目标也可以分解为若干个子目标;中间层为准则层,是为实现目标而采取的各类策略、约束、准则或因素的综合影响模式,也可以按分类等级将其分为若干子层;最低层为指标层,描述影响目标实现的各有关因素。研究与地理空间问题往往涉及大量相互关联、相互制约的复杂因素,而且各因素对问题的分析具有不同的重要性。AHP法的核心是:将相互关联的要素按隶属关系分为若干层次,并根据专家知识对不同层次的相对重要性给出定量指标,然后利用数学方法综合专家意见给出各层次要素的相对重要性权值,形成判断矩阵,以此作为综合分析和方案比较及形成决策的基础。判断矩阵构建及其一致性修正:设某一目标问题Y有m个影响因素,
18、其中每两个因素xi和 对Y的影响权之比为 ,满足 且 。由此所组成的矩阵A称为正互反矩阵)1(mixi)1,(mjixj)1,(mjiaij1,0iiijaaijjiaa/1mmmmmmaaaaaaaaaA.211222111211如果该矩阵满足那么,A具有一致性。数学上可以证明:m阶一致矩阵A的最大特征根 。实际上,在构建判断矩阵的过程中,由于要素的众多及其关联的复杂性,以及专家认识的主观片面性或逻辑非一致性,往往导致所构造的矩阵不满足一致性要求。此时,需要进行一致性判断和修正。)1,.(mkjiaaaikjkijmmax当所构造的判断矩阵非一致时,其特征根 。建立以下一致性检验指标:CI0
19、,说明所构造的判断矩阵是一致的;CI越大,说明非一致性越强。Saaty T.L.(1980)采用随机抽样的方法,得出不同阶数(m)矩阵的平均随机性指标RI,如表所示:平均随机一致性指标令 CR称为随机一次性比率。当CR0时有极小值;a10时有极大值);然后是常数增加(减少)到极大值(极小值),然后下降(增加)a1tsin(t+a2)+a3正弦振荡Z振幅周期性增大或减少剧变不连续无规律剧烈变化aeata 21两因素的影响权之比由于实际地理现象的复杂性和动态性,必然导致其影响因素的影响权之比也随时间发生变化。此时,需要构造一个基于时间函数的判断矩阵,该矩阵即称为动态判断矩阵。该矩阵中的各元素 的函
20、数形式可以参照上表选择,表中的参数是根据经验经曲线拟合得到的。某些情况下,比如当信息不足和知识不够,可能对判断矩阵中的某些项把握不准而无法确定,造成该项元素残缺。此时的判断矩阵即为残缺矩阵。如果一个残缺矩阵的任一残缺元素均可以通过矩阵中的已知信息间接获得,则该残缺矩阵是可接受的;否则,不可接受。)(taij可接受残缺矩阵的最大特征根和权重特征向量的算法如下:设 是残缺判断矩阵,为其中的残缺元素。构造一个辅助矩阵 如下:求辅助矩阵C的最大特征根 使得由于辅助矩阵C与 等价矩阵有相同的特征根及其对应的特征向量,所以可以通过求等价矩阵 的特征根来确定辅助矩阵C的最大特征根 :其最大特征根 满足 。1
21、 miW)(mmijaA)(immijcC )(),(,/)(,),(,jiajijiaaCijjiijij 1 Cmax WCWC max C CCmax ),(,)(,),(,行行中中残残缺缺元元素素的的个个数数为为第第 iiiijijijnjinajiaaC10 Cmax WWCC max 代代特征特征数据挖掘算法数据挖掘算法集成集成分布计算分布计算模型模型数据模型数据模型第一第一代代作为一个独作为一个独立的应用立的应用支持一个或者支持一个或者多个算法多个算法 独立的系统独立的系统单个机器单个机器向量数据向量数据第二第二代代和数据库以和数据库以及数据仓库及数据仓库集成集成多个算法:能多个
展开阅读全文