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