数据挖掘与机器学习(非参数统计)课件.ppt

第10章数据挖掘与机器学习,1,概念：数据挖掘是从大量的数据中，抽取出潜在的、有价值的知识（模型或规则）的过程,2,工业控制技术研究所,数据挖掘概念,数据挖掘-从大量数据中寻找其规律的技术，是统计学、数据库技术和人工智能技术的综合。数据挖掘是从数据中自动地抽取模式、关联、变化、异常和有意义的结构；数据挖掘大部分的价值在于利用数据挖掘技术改善预测模型。,工业控制技术研究所,数据挖掘的社会需求,国民经济和社会的信息化,社会信息化后，社会的运转是软件的运转社会信息化后，社会的历史是数据的历史,工业控制技术研究所,数据挖掘的社会需求,有价值的知识,可怕的数据,工业控制技术研究所,数据挖掘的社会需求,数据爆炸，知识贫乏,数据挖掘功能,数据挖掘任务有两类：第一类是描述性挖掘任务：刻划数据库中数据的一般特性；第二类是预测性挖掘任务：在当前数据上进行推断，以进行预测。,工业控制技术研究所,数据挖掘技术,技术分类预言（Predication）：用历史预测未来描述（Description）：了解数据中潜在的规律数据挖掘技术关联分析序列模式分类（预言）聚集异常检测,工业控制技术研究所,数据挖掘系统的特征,数据的特征知识的特征算法的特征,矿山（数据）,挖掘工具（算法）,金子（知识）,工业控制技术研究所,数据的特征,大容量POS数据（某个超市每天要处理高达2000万笔交易）卫星图象（NASA的地球观测卫星以每小时50GB的速度发回数据）互联网数据含噪音（不完全、不正确）异质数据（多种数据类型混合的数据源，来自互联网的数据是典型的例子）,工业控制技术研究所,数据挖掘算法的特征,构成数据挖掘算法的三要素模式记述语言：反映了算法可以发现什么样的知识模式评价：反映了什么样的模式可以称为知识模式探索：包括针对某一特定模式对参数空间的探索和对模式空间的探索,工业控制技术研究所,数据挖掘的主要方法,分类（Classification）聚类(Clustering)相关规则(Association Rule)回归(Regression)其他,工业控制技术研究所,数据挖掘系统,工业控制技术研究所,数据挖掘系统,第一代数据挖掘系统 支持一个或少数几个数据挖掘算法，这些算法设计用来挖掘向量数据（vector-valued data），这些数据模型在挖掘时候，一般一次性调进内存进行处理。许多这样的系统已经商业化。第二代数据挖掘系统 目前的研究，是改善第一代数据挖掘系统，开发第二代数据挖掘系统。第二代数据挖掘系统支持数据库和数据仓库，和它们具有高性能的接口，具有高的可扩展性。例如，第二代系统能够挖掘大数据集、更复杂的数据集、以及高维数据。这一代系统通过支持数据挖掘模式（data mining schema）和数据挖掘查询语言（DMQL）增加系统的灵活性。,工业控制技术研究所,数据挖掘系统,第三代数据挖掘系统 第三代的特征是能够挖掘Internet/Extranet的分布式和高度异质的数据，并且能够有效地和操作型系统集成。这一代数据挖掘系统关键的技术之一是提供对建立在异质系统上的多个预言模型以及管理这些预言模型的元数据提供第一级别（first class）的支持。第四代数据挖掘系统 第四代数据挖掘系统能够挖掘嵌入式系统、移动系统、和普遍存在（ubiquitous）计算设备产生的各种类型的数据。,数据挖掘的功能/算法/应用的比较,数据挖掘常用方法的综合比较*,数据挖掘的具体应用,市场-购物蓝分析客户关系管理寻找潜在客户提高客户终生价值保持客户忠诚度行销活动规划预测金融市场方向,保险欺诈侦察客户信用风险评级电话盗打NBA球员强弱分析信用卡可能呆帐预警星际星体分类,数据挖掘的步骤*,一种步骤划分方式理解资料与进行的工作获取相关知识与技术（Acquisition）整合与查核资料（Integration and checking）去除错误、不一致的资料（Data cleaning）模式与假设的演化（Model and hypothesis development）实际数据挖掘工作测试与核查所分析的资料（Testing and verification）解释与运用（Interpretation and use）,工业控制技术研究所,数据挖掘软件的发展,第一代数据挖掘软件 CBA,新加坡国立大学。基于关联规则的分类算法，能从关系数据或者交易数据中挖掘关联规则，使用关联规则进行分类和预测,工业控制技术研究所,数据挖掘软件的发展,第二代数据挖掘软件,特点与数据库管理系统（DBMS）集成 支持数据库和数据仓库，和它们具有高性能的接口，具有高的可扩展性 能够挖掘大数据集、以及更复杂的数据集 通过支持数据挖掘模式（data mining schema）和数据挖掘查询语言增加系统的灵活性 典型的系统如DBMiner，能通过DMQL挖掘语言进行挖掘操作缺陷只注重模型的生成，如何和预言模型系统集成导致了第三代数据挖掘系统的开发,工业控制技术研究所,数据挖掘软件的发展,第二代数据挖掘软件 DBMiner,工业控制技术研究所,数据挖掘软件的发展,第二代软件 SAS Enterprise Miner,工业控制技术研究所,数据挖掘软件的发展,第三代数据挖掘软件,特点和预言模型系统之间能够无缝的集成，使得由数据挖掘软件产生的模型的变化能够及时反映到预言模型系统中 由数据挖掘软件产生的预言模型能够自动地被操作型系统吸收，从而与操作型系统中的预言模型相联合提供决策支持的功能 能够挖掘网络环境下（Internet/Extranet）的分布式和高度异质的数据，并且能够有效地和操作型系统集成 缺陷不能支持移动环境,工业控制技术研究所,数据挖掘软件的发展,第三代软件 SPSS Clementine,以PMML的格式提供与预言模型系统的接口,工业控制技术研究所,数据挖掘软件的发展,第四代数据挖掘软件,特点目前移动计算越发显得重要，将数据挖掘和移动计算相结合是当前的一个研究领域。第四代软件能够挖掘嵌入式系统、移动系统、和普遍存在（ubiquitous）计算设备产生的各种类型的数据第四代数据挖掘原型或商业系统尚未见报导，PKDD2001上Kargupta发表了一篇在移动环境下挖掘决策树的论文，Kargupta是马里兰巴尔的摩州立大学（University of Maryland Baltimore County）正在研制的CAREER数据挖掘项目的负责人，该项目研究期限是2001年4月到2006年4月，目的是开发挖掘分布式和异质数据（Ubiquitous设备）的第四代数据挖掘系统。,工业控制技术研究所,数据挖掘软件的发展,第一代系统与第二代相比因为不具有和数据管理系统之间有效的接口，所以在数据预处理方面有一定缺陷 第三、四代系统强调预测模型的使用和操作型环境的部署 第二代系统提供数据管理系统和数据挖掘系统之间的有效接口 第三代系统另外还提供数据挖掘系统和预言模型系统之间的有效的接口 目前，随着新的挖掘算法的研究和开发，第一代数据挖掘系统仍然会出现，第二代系统是商业软件的主流，部分第二代系统开发商开始研制相应的第三代数据挖掘系统，比如 IBM Intelligent Score Service。第四代数据挖掘原型或商业系统尚未见报导,工业控制技术研究所,数据挖掘软件的发展,数据挖掘软件发展的三个阶段独立的数据挖掘软件横向的数据挖掘工具集纵向的数据挖掘解决方案,工业控制技术研究所,数据挖掘软件的现状,国内大部分处于科研阶段各大学和科研机构从事数据挖掘算法的研究国内著作的数据挖掘方面的书较少（翻译的有）数据挖掘讨论组（）有一些公司在国外产品基础上开发的特定的应用IBM Intelligent MinerSAS Enterprise Miner自主知识产权的数据挖掘软件复旦德门（）等,工业控制技术研究所,数据挖掘应用,神经网络 Neural Networks,聚类分析 Clustering,OpenAccnt,Add NewProduct,DecreaseUsage,?,Time,序列分析 Sequence Analysis,决策树 Decision Trees,倾向性分析,客户保留 客户生命周期管理 目标市场 价格弹性分析,客户细分 市场细分,倾向性分析 客户保留 目标市场 欺诈检测,关联分析 Association,市场组合分析 套装产品分析 目录设计 交叉销售,10.1分类一般问题,定义：给定，为离散值，表示每个样例的分类，目标是找到一个函数，对于新观测点，能够用 预测分类。,工业控制技术研究所,分类 VS.预测,分类：(与回归相比较)预测分类标号（或离散值）（特点）根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据预测：建立连续函数值模型，比如预测空缺值典型应用信誉证实目标市场医疗诊断性能预测,工业控制技术研究所,数据分类：两步过程,第一步，建立一个模型，描述预定数据类集和概念集假定每个元组属于一个预定义的类，由一个类标号属性确定基本概念训练数据集：由为建立模型而被分析的数据元组形成训练样本：训练数据集中的单个样本（元组）学习模型可以用分类规则、判定树或数学公式的形式提供第二步，使用模型，对将来的或未知的对象进行分类首先评估模型的预测准确率对每个测试样本，将已知的类标号和该样本的学习模型类预测比较模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比测试集要独立于训练样本集，否则会出现“过分适应数据”的情况,工业控制技术研究所,第一步：建立模型,训练数据集,分类算法,IF rank=professorOR years 6THEN tenured=yes,分类规则,工业控制技术研究所,第二步：用模型进行分类,分类规则,测试集,未知数据,(Jeff,Professor,4),Tenured?,损失函数,损失函数评价法损失函数为，拟合函数 的预测风险定义为 估计方法为，由于数据联合分布未知，无法用E 计算。故用风险的矩 估计经验风险（代替预测风险）,36,估计方法为，如果，期望风险经验风险，当不满足，,37,根据Vladimir N.Vapnik(1995)估算：在 时，,38,以上给出了期望风险与经验风险之间的关系。结构风险最小化定义统计学习理论提出了一种新的策略,即把函数集构造为一个函数子集序列,使各个子集按照VC维的大小排列;在每个子集中寻找最小经验风险,在子集间折衷考虑经验风险和置信范围,取得实际风险的最小。这种思想称作结构风险最小化(Structural Risk Minimization)，即SRM准则。,39,vc维VC维（Vapnik-Chervonenkis Dimension）的概念是为了研究学习过程一致收敛的速度和推广性，由统计学习理论定义的有关函数集学习性能的一个重要指标。,40,结构风险最小化(SRM)的基本思想,所谓的结构风险最小化就是在保证分类精度（经验风险）的同时，降低学习机器的 VC 维，可以使学习机器在整个样本集上的期望风险得到控制。传统机器学习方法中普遍采用的经验风险最小化原则在样本数目有限时是不合理的,因此，需要同时最小化经验风险和置信范围。机器学习过程不但要使经验风险最小，还要使VC维尽量小以缩小置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性。,41,在有限训练样本下，学习机器的VC维越高则置信范围越大,真实风险与经验风险之间可能的差别越大.这就是为什么会出现过学习现象的原因。实现SRM的思路之一就是设计函数集的某种结构使每个子集中都能取得最小的经验风险（如使训练误差为0），然后只需选择适当的子集使置信范围最小，则这个子集中使经验风险最小的函数就是最优函数。SVM方法实际上就是这种思想的具体实现。,42,10.2 Logistic回归,普通回归是对连续变量依赖关系建模的过程。然而，分类在现实中经常发生。典型的是两类问题（0-1）变量。如发病，与不发病。,43,44,（一）基本概念和原理,1.应用背景 Logistic回归模型是一种概率模型，适合于病例对照研究、随访研究和横断面研究，且结果发生的变量取值必须是二分的或多项分类。可用影响结果变量发生的因素为自变量与因变量，建立回归方程。,45,设资料中有一个因变量y、p个自变量x1,x2,xp，对每个实验对象共有n次观测结果，可将原始资料列成表2形式。,2、Logistic回归模型的数据结构,46,表2 Logistic回归模型的数据结构实验对象 y X1 X2 X3.XP 1 y1 a11 a12 a13 a1p 2 y2 a21 a22 a23 a2p 3 y3 a31 a32 a33 a3p n yn an1 an2 an3 anp 其中：y取值是二值或多项分类,表3 肺癌与危险因素的调查分析例号 是否患病 性别 吸烟 年龄 地区 1 1 1 0 30 0 2 1 0 1 46 1 3 0 0 0 35 1 30 0 0 0 26 1 注：是否患病中，0代表否，1代表是。性别中1代表男，0代表女，吸烟中1代表吸烟，0代表不吸烟。地区中，1代表农村，0代表城市。,表4 配对资料(1:1)对子号 病例 对照 x1 x2 x3 x1 x2 x3 1 1 3 0 1 0 1 2 0 3 1 1 3 0 3 0 1 2 0 2 0 10 2 2 2 0 0 0注：X1蛋白质摄入量，取值：0，1，2，3 X2不良饮食习惯，取值：0，1，2，3 X3精神状况，取值：0，1，2,49,Logistic回归-Logistic回归与多重线性回归联系与区别,联系:用于分析多个自变量与一个因变量的关系，目的是矫正混杂因素、筛选自变量和更精确地对因变量作预测等。区别:线性模型中因变量为连续性随机变量，且要求呈正态分布.Logistic回归因变量的取值仅有两个，不满足正态分布。,50,3、Logistic回归模型,令：y=1 发病（阳性、死亡、治愈等）y=0 未发病（阴性、生存、未治愈等）将发病的概率记为P，它与自变量x1,x2,xp 之间的Logistic回归模型为：(10.4)P(Y=1|X)=可知，不发病的概率为：,经数学变换得：定义：为Logistic变换，即：,10.2.2Logistic回归模型的极大似然估计,Logistic回归模型是通过极大似然估计法得到的，应变量 取值为0和1，设事件发生记为y=1，否则为0，设自变量，n组观测数据记为,。记，则 与 的Logistic回归模型是：,2023年1月21日星期六,Data Mining:Concepts and Techniques,52,易知，是均值为 的0-1型分布，其分布律为，则 的似然函数和对数似然函数分别为：,2023年1月21日星期六,Data Mining:Concepts and Techniques,53,代入,得记，选取 的估计 使得 达到极大，这就是Logistic回归模型的极大似然估，该过程的求解需要采用牛顿（Newton-Raphson）迭代法。,2023年1月21日星期六,Data Mining:Concepts and Techniques,54,构造得分函数，共k+1个非线性方程组，令其=0求解，其中,2023年1月21日星期六,55,构造得分函数，共k+1个非线性方程组，令其=0求解，其中,2023年1月21日星期六,56,构造信息矩阵，即 二阶导矩阵的负矩阵，其中很明显，故 是一个对称矩阵。,2023年1月21日星期六,57,构造信息矩阵，即 二阶导矩阵的负矩阵，其中很明显，故 是一个对称矩阵。,2023年1月21日星期六,58,牛顿（Newton-Raphson）迭代法为,2023年1月21日星期六,59,10.2.3 Logistic 回归和线性判别函数LDA的比较,LDA,2023年1月21日星期六,60,牛顿（Newton-Raphson）迭代法,2023年1月21日星期六,61,62,用决策树归纳分类,决策树一个类似于流程图的数结构内部节点表示一个属性上的测试每个分支代表一个测试的输出叶结点代表类或类分布决策树的生成包括两个过程树的建构首先所有的训练样本都在根结点基于所选的属性循环的划分样本树剪枝识别和删除哪些反应映噪声或孤立点的分支决策树的使用:为一个未知的样本分类在决策树上测试样本的属性值,2023年1月21日星期六,Data Mining:Concepts and Techniques,63,2023年1月21日星期六,Data Mining:Concepts and Techniques,64,决策树归纳的算法,基本算法以自顶向下递归的各个击破方式构造决策树首先,所有的训练样本都在根结点所有属性都是分类的(如果值是连续的,它们应预先被离散化)基于所选属性递归的划分样本在启发式或统计度量的基础上选择测试属性(例如,信息增益)停止划分的条件给定节点的所有样本属于同一个类没有剩余属性可以用来进一步划分样本-使用多数表决来分类叶节点没有剩余的样本,