单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第,13,章,物联网中的,智能决策,内容提要,智能决策,是物联网“智慧”的来源。,本章将介绍数据挖掘的基本流程，基本类型和典型算法。,第,12,章介绍了搜索引擎的相关知识,搜索引擎的基本组成,搜索引擎的体系结构（信息采集，索引技术，搜索服务）,物联网中搜索引擎的挑战,本章介绍,数据挖掘的基本流程,（预处理，数据挖掘，知识评估与表示），重点介绍,几种典型的数据挖掘算法,，最后讨论,物联网中智能决策的新特点,。,内容回顾,13.1,数据挖掘概述,13.2,数据挖掘的基本类型和算法,*,13.3,智能决策与物联网,什么是数据挖掘？数据挖掘有哪三个步骤？,本章内容,13.1,数据挖掘概述,数据挖掘,（,Data Mining,）,从大量,数据,中获取潜在有用的并且可以被人们理解的,模式,的过程,是一个,反复迭代,的,人机交互和处理,的过程，历经多个步骤，并且在一些步骤中需要由用户提供决策,数据挖掘的过程：,数据预处理、数据挖掘和对挖掘结果的评估与表示,每一个阶段的输出结果成为下一个阶段的输入,13.1,数据挖掘概述,数据挖掘的过程,数据预处理阶段,数据准备：了解领域特点，确定用户需求,数据选取：从原始数据库中选取相关数据或样本,数据预处理：检查数据的完整性及一致性，消除噪声等,数据变换：通过投影或利用其他操作减少数据量,数据挖掘阶段,确定挖掘目标：确定要发现的知识类型,选择算法：根据确定的目标选择合适的数据挖掘算法,数据挖掘：运用所选算法，提取相关知识并以一定的方式表示,知识评估与表示阶段,模式评估：对在数据挖掘步骤中发现的模式,(,知识,),进行评估,知识表示：使用可视化和知识表示相关技术，呈现所挖掘的知识,13.1,数据挖掘概述,数据挖掘的过程,13.1,数据挖掘概述,13.2,数据挖掘的基本类型和算法,*,13.3,智能决策与物联网,数据挖掘的基本类型和算法有那些？,本章内容,13.2,数据挖掘的基本类型和算法,数据挖掘的基本类型,关联分析,(Association Analysis),聚类分析,(Clustering Analysis),离群点分析,(Outlier Analysis),分类与预测,(Classification and Prediction),演化分析,(Evolution Analysis),描述性,挖掘任务：刻划数据库中数据的一般特性,预测性,挖掘任务：在当前数据上进行推断和预测,关联分析,关联分析,的目标是从给定的数据中发现频繁出现的模式，即,关联规则,关联规则,通常的表述形式是,X Y,，表示“数据库中满足条件,X,的记录,(,元组,),可能也满足条件,Y”,以某电器商场销售记录为例：,含义：,4%(,支持度,),的顾客的年龄在,20,至,29,岁且月收入在,3000,至,5000,元，且这样的顾客中，,65%(,置信度,),的人购买了笔记本电脑,关联分析,挖掘关联规则，需要,置信度,和,支持度,越高越好,基本概念,项集,：满足若干条件的数据项的集合，如果条件数为,k,，则称,k,-,项集,满足年龄,(,顾客,“2029”),的项集是,1-,项集,满足年龄,(,顾客,“2029”),收入,(,顾客,“30005000”),的项集是,2-,项集,计算步骤,首先找到具备足够支持度的项集，即,频繁项集,然后由频繁项集构成关联规则，并计算置信度,关联分析,如何寻找频繁项集,Apriori,算法,基本思想：,利用已求出的,k,-,项集来计算,(,k,+1)-,项集,首先计算频繁,1-,项集,然后根据两个频繁,k,-,项集,p,1,p,2,.,p,k,，,q,1,q,2,.,q,k,计算频繁,(k+1)-,项集，其中,p,i,=,q,i,，,1=,i=k,-1,，且该,(,k,+1)-,项集为,p,1,p,2,.,p,k,q,k,最后判定该,(,k,+1)-,项集是否频繁即可,缺点：,可能产生大量候选项集，并需要重复地扫描数据库,FP-Growth,算法,利用树状结构保存项集，从而减小了计算频繁项集所需的存储空间,关联分析,如何由频繁项集构造关联规则，并计算置信度,关联规,A B,的置信度,其中,count(A AND B),为满足条件,A,以及,B,的数据项数目，,count(A),为满足条件,A,的数据项数目,计算步骤,对于每一个频繁项集,S,，计算,S,的所有非空子集,对于每个,S,的非空子集,F,，若 大于给定置信度阈值，则得到一个关联规则,分类和预测,分类和预测,的目标是,找出描述和区分不同数据类或概念的模型或函数,，以便能够使用模型预测数据类或标记未知的对象,所获得的,分类模型,可以采用多种形式加以描述输出,分类规则,判定树,数学公式,神经网络,分类与预测的区别：,分类通常指预测数据对象属于哪一类，而当被预测的值是数值数据时，通常称为预测,分类和预测,以,判定树,方法为例，简要介绍分类的基本步骤和结果表示,问题实例,：假定商场需要向潜在的客户邮寄新产品资料和促销信息。客户数据库描述的客户属性包括姓名、年龄、收入、职业和信用记录。,我们可以按是否会在商场购买计算机将客户分为两类，只将促销材料邮寄给那些会购买计算机的客户，从而降低成本。,分类和预测,用于预测客户是否可能购买计算机的,判定树,，其中,每个非树叶节点,表示一个,属性上的测试,，,每个树叶节点,代表,预测结果,分类和预测,如何构造上述判定树？,基本概念：,n,个客户中有,a,个购买了计算机的,期望信息,建立树节点时，选取合适的判定属性，以,最大化期望信息增益应,某种属性上的信息增益大小反映了该属性区分给定数据的的能力强弱,10,条客户记录，其中,6,人购买了计算机，,4,人没有购买。这,10,位客户中有,3,人的职业是学生，其中有,2,人购买计算机，而非学生客户购买计算机的有,4,人。在选择区分属性以前，数据的期望信息为 ，用职业区分之后的期望信息为 ，则选择职业作为区分属性的,信息增益,为,聚类分析,聚类的目的是,将数据对象划分为多个类或簇,，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大,聚类与分类的区别：,要划分的类是事先未知的,聚类分析的应用,聚类分析,聚类分析的方法,划分方法,：要求事先给定聚类的数目,k,。首先创建一个初始划分，然后通过对划分中心点的反复迭代来改进划分。典型算法包括,k,-means,算法和,k,-medoids,算法等,层次方法,：对给定数据集合进行逐层递归的合并或者分裂，因此可以被分为合并或分裂方法。合并方法首先将每个对象都作为独立的类，然后持续合并相近的类，直到达到终止条件为止。分裂方法首先将所有的数据对象置于一个类中，然后反复迭代并判定当前的类是否可以被继续分裂，直到达到终止条件为止,基于密度的方法,：只要某区域数据密度超过阈值，就将该区域的数据进行聚类。其优势在于噪音数据下的抗干扰能力，并能够发现任意形状的聚类,聚类分析,聚类分析的方法（续）,基于网格的方法,：把对象空间量化为具有规则形状的单元格，从而形成一个网格状结构。在聚类的时候，将每个单元格当作一条数据进行处理。优点是处理速度很快，因处理时间与数据对象数目无关，而只与量化空间中的单元格数目相关,基于模型的方法,：如果事先已知数据是根据潜在的概率分布生成的，基于模型的方法便可为每个聚类构建相关的数据模型，然后寻找数据对给定模型的最佳匹配。主要分两类：统计学方法和神经网络方法,离群点分析,离群点,(Outlier),：数据集合中存在的一些数据对象，它们与其余绝大多数数据的特性或模型不一致,寻找离群点的意义,发现信用卡诈骗,。通过检测购物地点、商品种类或者购物金额和频率，能够发现与绝大多数正常消费不一样的记录，这种行为就有可能属于信用卡诈骗性使用,预防网络诈骗,。在网络销售的时候，诈骗者往往冒充商家，出售报价比正常价格低出许多的商品，这样的行为也是可以通过离群点分析被找到的,离群点分析,寻找离群点的方法,基于统计的方法：,需要事先已知数据的分布或概率模型,(,例如一个正态分布,),，然后根据数据点与该模型的不一致性检验来确定离群点,基于距离的方法：,不需要数据模型，而是将那些没有足够邻居的数据对象看作是离群点，这里的邻居是基于距给定对象的距离来定义的。现有的基于距离的离群点探测算法又分为基于索引的算法，嵌套循环算法和基于单元的算法，其目的都是为了减小计算和,I/O,开销,基于偏移的方法：,不采用统计检验或基于距离的度量值来确定异常对象。相反，它通过检查数据对象的一组主要特征来确定离群点。偏离事先给出的特征描述的数据对象被认为是离群点,演化分析,演化分析,的目的是挖掘,随时间变化,的数据对象的变化规律和趋势，并对其建模，进而为相关决策提供参考,演化分析的应用,对股票的演化分析可以得出整个股票市场和特定的公司的股票变化规律，为投资者决策提供帮助,对生态和气候的演化分析可以知道人类活动对自然的影响程度，为环境保护提供重要依据,建模方法：,除了关联分析和分类分析，还包括与时间相关的数据分析方法，主要包括趋势分析、相似搜索、序列模式挖掘和与周期分析,演化分析,与时间相关的数据分析方法,趋势分析：,确定趋势的常见方法是计算数据,n,阶的变化平均值，或者采用最小二乘法等方法平滑数据变化曲线,相似搜索：,相似搜索用于找出与给定序列最接近的数据序列,序列模式挖掘：,挖掘相对时间或其它维属性出现频率高的模式,周期分析：,挖掘具有周期的模式或者关联规则，例如”若每周六公司的下班时间比平时晚半小时以上，则选择打车回家的人数大约增加,20%”,13.1,数据挖掘概述,13.2,数据挖掘的基本类型和算法,*,13.3,智能决策与物联网,数据挖掘在物联网背景下有着广泛的需求,本章内容,13.3,智能决策与物联网,数据挖掘技术在物联网中的需求,精准农业,市场行销,智能家居,金融安全,产品制造和质量监控,互联网用户行为分析,精准农业,精准农业,市场行销,智能家居,金融安全,产品制造和质量监控,互联网用户行为分析,通过植入土壤或暴露在空气中的传感器监控土壤性状和环境状况,。,数据通过物联网传输到远程控制中心，可及时查清当前农作物,的,生长环境现状和变化趋势，确定农作物的生产目标,。,通过数据挖掘的方法，可以知道：环境温度湿度和土壤各项参数等因素是如何影响农作物产量的，如何调节它们才能够最大限度地提高农作物产量,市场行销,精准农业,市场行销,智能家居,金融安全,产品制造和质量监控,互联网用户行为分析,利用数据挖掘技术通过对用户数据的分析，可以得到关于顾客购物取向和兴趣的信息，从而为商业决策提供依据,数据库行销,(Database Marketing),通过交互式查询、数据分割和模型预测等方法来选择潜在的顾客以便向它们推销产品,预测采用何种销售渠道和优惠条件，使得用户最有可能被打动,货篮分析,(Basket Analysis),通过分析市场销售数据,(,例如,POS,数据库,),来发现顾客的购买行为模式,智能家居,精准农业,市场行销,智能家居,金融安全,产品制造和质量监控,互联网用户行为分析,以获取天气信息为例：一方面，智能设备随时关注气象信息，并针对雨天发出报警提醒；另一方面，另外一些智能终端会随时跟踪主人的行踪，并通过数据挖掘方法由主人的历史行动特征数据预测他的去向,一旦预测到主人要出门，那么就在合适的时候由相应的智能终端提醒他不要忘记带雨伞。例如，如果主人在门口，就将由安装在门上的智能设备向他发出提醒，如果在车内，则由车载计算机发出提醒,金融安全,精准农业,市场行销,智能家居,金融安全,产品制造和质量监控,互联网用户行为分析,由于金融投资的风险很大，所以在进行投资决策时，需要通过对各种投资方向的数据进行分析，以选择最佳的投资方向。数据挖掘可以通过对已有数据的处理，找到数据对象之间的关系，然后利用学习得到的模式进行合理的预测,金融欺诈识别主要是通过分析正常行为和诈骗