1、第10章数据挖掘与机器学习1概念：数据挖掘是从大量的数据中，抽取出潜在的、有价值的知识（模型或规则）的过程2工业控制技术研究所数据挖掘-从大量数据中寻找其规律的技术，是统计学、数据库技术和人工智能技术的综合。数据挖掘是从数据中自动地抽取模式、关联、变化、异常和有意义的结构；数据挖掘大部分的价值在于利用数据挖掘技术改善预测模型。工业控制技术研究所国民经济和社会的信息化国民经济和社会的信息化工业控制技术研究所数据挖掘数据挖掘数据库越来越大数据库越来越大有价值的知识有价值的知识可怕的数据可怕的数据工业控制技术研究所 苦恼: 淹没在数据中 ; 不能制定合适的决策! n模式模式n趋势趋势n事实事实n关系
2、关系n模型模型n关联规则关联规则n序列序列n目标市场目标市场n资金分配资金分配n贸易选择贸易选择n在哪儿做广告在哪儿做广告n销售的地理位置销售的地理位置n金融金融n经济经济n政府政府nPOS.n人口统计人口统计n生命周期生命周期数据挖掘功能数据挖掘任务有两类： 第一类是描述性挖掘任务：刻划数据库中数据的一般特性； 第二类是预测性挖掘任务：在当前数据上进行推断，以进行预测。工业控制技术研究所l技术分类 预言（Predication）：用历史预测未来 描述（Description）：了解数据中潜在的规律l数据挖掘技术 关联分析 序列模式 分类（预言） 聚集 异常检测工业控制技术研究所数据的特征知识
3、的特征算法的特征矿山（数据）挖掘工具（算法）金子（知识）工业控制技术研究所大容量POS数据（某个超市每天要处理高达2000万笔交易）卫星图象（NASA的地球观测卫星以每小时50GB的速度发回数据）互联网数据含噪音（不完全、不正确）异质数据（多种数据类型混合的数据源，来自互联网的数据是典型的例子）工业控制技术研究所构成数据挖掘算法的三要素模式记述语言：反映了算法可以发现什么样的知识模式评价：反映了什么样的模式可以称为知识模式探索：包括针对某一特定模式对参数空间的探索和对模式空间的探索工业控制技术研究所分类（Classification）聚类(Clustering)相关规则(Association
4、 Rule)回归(Regression)其他工业控制技术研究所代代特征特征数据挖掘算法数据挖掘算法集成集成分布计算分布计算模型模型数据模型数据模型第一代第一代数据挖掘作为数据挖掘作为一个独立的应一个独立的应用用支持一个或者支持一个或者多个算法多个算法 独立的系独立的系统统单个机单个机器器向量数据向量数据第二代第二代和数据库以及和数据库以及数据仓库集成数据仓库集成多个算法：能够多个算法：能够挖掘一次不能放挖掘一次不能放进内存的数据进内存的数据数据管理系数据管理系统，包括数统，包括数据库和数据据库和数据仓库仓库同质同质/ /局局部区域部区域的计算的计算机群集机群集有些系统支有些系统支持对象、文持对
5、象、文本、和连续本、和连续的媒体数据的媒体数据第三代第三代和预言模型和预言模型系统集成系统集成 多个算法多个算法数据管理和数据管理和预言模型系预言模型系统统intranet/extranet网网络计算络计算支持半结构支持半结构化 数 据 和化 数 据 和webweb数据数据第四代第四代和移动数据和移动数据/ /各种计算数各种计算数据联合据联合 多个算法多个算法数据管理、数据管理、预言模型、预言模型、移动系统移动系统移动和各移动和各种计算设种计算设备备普 遍 存 在普 遍 存 在的 计 算 模的 计 算 模型型工业控制技术研究所第一代数据挖掘系统 支持一个或少数几个数据挖掘算法，这些算法设计用来
6、挖掘向量数据（vector-valued data），这些数据模型在挖掘时候，一般一次性调进内存进行处理。许多这样的系统已经商业化。第二代数据挖掘系统 目前的研究，是改善第一代数据挖掘系统，开发第二代数据挖掘系统。第二代数据挖掘系统支持数据库和数据仓库，和它们具有高性能的接口，具有高的可扩展性。例如，第二代系统能够挖掘大数据集、更复杂的数据集、以及高维数据。这一代系统通过支持数据挖掘模式（data mining schema）和数据挖掘查询语言（DMQL）增加系统的灵活性。 工业控制技术研究所第三代数据挖掘系统 第三代的特征是能够挖掘Internet/Extranet的分布式和高度异质的数据，
7、并且能够有效地和操作型系统集成。这一代数据挖掘系统关键的技术之一是提供对建立在异质系统上的多个预言模型以及管理这些预言模型的元数据提供第一级别（first class）的支持。 第四代数据挖掘系统 第四代数据挖掘系统能够挖掘嵌入式系统、移动系统、和普遍存在（ubiquitous）计算设备产生的各种类型的数据 。数据挖掘的功能/算法/应用的比较 数据挖掘常用方法的综合比较*数据挖掘的具体应用市场-购物蓝分析客户关系管理寻找潜在客户提高客户终生价值保持客户忠诚度行销活动规划预测金融市场方向 保险欺诈侦察 客户信用风险评级 电话盗打 NBA球员强弱分析 信用卡可能呆帐预警 星际星体分类数据挖掘的步骤
8、*一种步骤划分方式理解资料与进行的工作获取相关知识与技术（Acquisition）整合与查核资料（Integration and checking）去除错误、不一致的资料（Data cleaning）模式与假设的演化（Model and hypothesis development）实际数据挖掘工作测试与核查所分析的资料（Testing and verification）解释与运用（Interpretation and use）工业控制技术研究所第一代数据挖掘软件第一代数据挖掘软件CBA 新加坡国立大学。基于关联规则的分类算法，能从关系数据或者交易数据中挖掘关联规则，使用关联规则进行分类和预测
9、工业控制技术研究所第二代数据挖掘软件第二代数据挖掘软件l特点 与数据库管理系统（DBMS）集成 支持数据库和数据仓库，和它们具有高性能的接口，具有高的可扩展性 能够挖掘大数据集、以及更复杂的数据集 通过支持数据挖掘模式（data mining schema）和数据挖掘查询语言增加系统的灵活性 典型的系统如DBMiner，能通过DMQL挖掘语言进行挖掘操作l缺陷 只注重模型的生成，如何和预言模型系统集成导致了第三代数据挖掘系统的开发工业控制技术研究所第二代数据挖掘软件第二代数据挖掘软件 DBMiner工业控制技术研究所第二代软件第二代软件 SAS Enterprise Miner工业控制技术研究
10、所第三代数据挖掘软件第三代数据挖掘软件l特点 和预言模型系统之间能够无缝的集成，使得由数据挖掘软件产生的模型的变化能够及时反映到预言模型系统中 由数据挖掘软件产生的预言模型能够自动地被操作型系统吸收，从而与操作型系统中的预言模型相联合提供决策支持的功能 能够挖掘网络环境下（Internet/Extranet）的分布式和高度异质的数据，并且能够有效地和操作型系统集成l缺陷不能支持移动环境工业控制技术研究所第三代软件第三代软件 SPSS Clementine工业控制技术研究所第四代数据挖掘软件第四代数据挖掘软件l特点 目前移动计算越发显得重要，将数据挖掘和移动计算相结合是当前的一个研究领域。 第四
11、代软件能够挖掘嵌入式系统、移动系统、和普遍存在（ubiquitous）计算设备产生的各种类型的数据第四代数据挖掘原型或商业系统尚未见报导，PKDD2001上Kargupta发表了一篇在移动环境下挖掘决策树的论文，Kargupta是马里兰巴尔的摩州立大学（University of Maryland Baltimore County）正在研制的CAREER数据挖掘项目的负责人，该项目研究期限是2001年4月到2006年4月，目的是开发挖掘分布式和异质数据（Ubiquitous设备）的第四代数据挖掘系统。 工业控制技术研究所l 第一代系统与第二代相比因为不具有和数据管理系统之间有效的接口，所以在数
12、据预处理方面有一定缺陷 l 第三、四代系统强调预测模型的使用和操作型环境的部署 l 第二代系统提供数据管理系统和数据挖掘系统之间的有效接口 l 第三代系统另外还提供数据挖掘系统和预言模型系统之间的有效的接口 l 目前，随着新的挖掘算法的研究和开发，第一代数据挖掘系统仍然会出现，第二代系统是商业软件的主流，部分第二代系统开发商开始研制相应的第三代数据挖掘系统，比如 IBM Intelligent Score Service。第四代数据挖掘原型或商业系统尚未见报导 工业控制技术研究所l 独立的数据挖掘软件l 横向的数据挖掘工具集l 纵向的数据挖掘解决方案工业控制技术研究所l国内大部分处于科研阶段
13、各大学和科研机构从事数据挖掘算法的研究 国内著作的数据挖掘方面的书较少（翻译的有） 数据挖掘讨论组（）l有一些公司在国外产品基础上开发的特定的应用 IBM Intelligent Miner SAS Enterprise Minerl自主知识产权的数据挖掘软件 复旦德门（）等工业控制技术研究所Debt$40KQ QQ QQ QQ QI II I1 12 23 34 45 56 6factor 1factor 2factor n神经网络神经网络 Neural NetworksNeural Networks聚类分析聚类分析 ClusteringClusteringOpenAccntAdd NewP
14、roductDecreaseUsage?Time序列分析序列分析 Sequence AnalysisSequence Analysis决策树决策树 Decision TreesDecision Trees 倾向性分析 客户保留 客户生命周期管理 目标市场 价格弹性分析 客户细分 市场细分 倾向性分析 客户保留 目标市场 欺诈检测关联分析关联分析 AssociationAssociation 市场组合分析 套装产品分析 目录设计 交叉销售10.1分类一般问题定义：给定 ， 为离散值，表示每个样例的分类，目标是找到一个函数 ，对于新观测点 ，能够用 预测分类 。11(,),(,)nnX YXYiY
15、fX( )f XY工业控制技术研究所分类：(与回归相比较)预测分类标号（或离散值离散值）（特点）根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据预测：建立连续函数值模型，比如预测空缺值典型应用信誉证实目标市场医疗诊断性能预测工业控制技术研究所第一步，建立一个模型建立一个模型，描述预定数据类集和概念集假定每个元组属于一个预定义的类，由一个类标号属性确定基本概念训练数据集：由为建立模型而被分析的数据元组形成训练样本：训练数据集中的单个样本（元组）学习模型可以用分类规则、判定树或数学公式的形式提供第二步，使用模型，对将来的或未知的对象进行分类进行分类首先评估模型的预测准确率对每个
16、测试样本，将已知的类标号和该样本的学习模型类预测比较模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比测试集要独立于训练样本集，否则会出现“过分适应数据”的情况工业控制技术研究所训练数据集NAME RANKYEARS TENUREDMikeAssistant Prof3noMaryAssistant Prof7yesBill Professor2yesJimAssociate Prof7yesDaveAssistant Prof6noAnneAssociate Prof3no分类算法IF rank = professorOR years 6THEN tenured = yes 分类规
17、则工业控制技术研究所分类规则测试集NAMERANKYEARS TENUREDTomAssistant Prof2noMerlisa Associate Prof7noGeorge Professor5yesJoseph Assistant Prof7yes未知数据(Jeff, Professor, 4)Tenured?损失函数损失函数评价法损失函数为 ，拟合函数 的预测风险定义为 估计方法为 ，由于数据联合分布未知，无法用E 计算。故用风险的矩风险的矩 估计经验风险（代替预测风险） 36( ,)L y ff*argmin( )R,( )( , ( , ),x yRE L y f x11()(,
18、(,)niiiRL yf xn估计方法为 ，如果 ，期望风险经验风险 ，当不满足 ，37*argmin( )R/n p *()(),RR*()()RR/n p 根据Vladimir N. Vapnik(1995)估算：在 时，38/( )20N VC n *4 ()()()11.2BRRRB以上给出了期望风险与经验风险之间的关系。结构风险最小化结构风险最小化定义定义统计学习理论提出了一种新的策略,即把函数集构造为一个函数子集序列,使各个子集按照VC维的大小排列;在每个子集中寻找最小经验风险,在子集间折衷考虑经验风险和置信范围,取得实际风险的最小。这种思想称作结构风险最小化(Structural
19、 Risk Minimization)，即SRM准则。39vc维VC维（Vapnik-Chervonenkis Dimension）的概念是为了研究学习过程一致收敛的速度和推广性，由统计学习理论定义的有关函数集学习性能的一个重要指标。40结构风险最小化结构风险最小化(SRM)的的基本思想基本思想所谓的结构风险最小化就是在保证分类精度（经验风险）的同时，降低学习机器的 VC 维，可以使学习机器在整个样本集上的期望风险得到控制。传统机器学习方法中普遍采用的经验风险最小化原则在样本数目有限时是不合理的,因此，需要同时最小化经验风险和置信范围。机器学习过程不但要使经验风险最小，还要使VC维尽量小以缩小
20、置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性。41在有限训练样本下，学习机器的VC维越高则置信范围越大,真实风险与经验风险之间可能的差别越大.这就是为什么会出现过学习现象的原因。实现实现SRM的思路的思路之一就是设计函数集的某种结构使每个子集中都能取得最小的经验风险（如使训练误差为0），然后只需选择适当的子集使置信范围最小，则这个子集中使经验风险最小的函数就是最优函数。SVM方法实际上就是这种思想的具体实现。4210.2 Logistic回归回归普通回归是对连续变量依赖关系建模的过程。然而，分类在现实中经常发生。典型的是两类问题（0-1）变量。如发病 ，与不发病 。431Y 0
21、Y 44（一）基本概念和原理（一）基本概念和原理 1.1.应用背景应用背景 LogisticLogistic回归模型是一种概率模型，适合于病例对照研究、随访研究和横断面研究，且结果发生的变量取值必须是二分的或多项分类。可用影响结果变量发生的因素为自变量与因变量，建立回归方程。45 设资料中有一个因变量y、p个自变量x1, x2,xp，对每个实验对象共有n次观测结果，可将原始资料列成表2形式。2、LogisticLogistic回归模型的数据结构46 表2 LogisticLogistic回归模型的数据结构实验对象 y X1 X2 X3 . XP 1 y1 a11 a12 a13 a1p 2 y
22、2 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
23、 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 49LogisticLogistic回归回归- Logistic- Logistic回归与回归与多重多重线性回归联系与区别线性回归联系与区别联系联系: : 用于分析多个自变量与一个因变量的关用于分析多个自变量与一个因变量的关系，目的是矫正混杂因素、筛选自变量和更系，目的是矫正混杂因素、筛选自变量和更精确地对因变量作预测等。精确地对因变量作预测等。区别区别: : 线性模型中因变量为连续性随机变量，线性模型中因变量为连续性随机变量，且要
24、求呈正态分布且要求呈正态分布. Logistic. Logistic回归因变量的回归因变量的取值仅有两个，不满足正态分布。取值仅有两个，不满足正态分布。503 3、 Logistic回归模型l 令：令： y=1 发病（阳性、死亡、治愈等）发病（阳性、死亡、治愈等）l y=0 未发病（阴性、生存、未治愈等）未发病（阴性、生存、未治愈等）l 将发病的概率记为将发病的概率记为P，它与自变量，它与自变量x x1 1, , x x2 2, ,x,xp p 之间的之间的Logistic回归模型为：回归模型为：(10.4) P(Y=1|X X)=l可知，不发病的概率为：可知，不发病的概率为：l )exp(1
25、)exp(110110ppppXXXXp )exp(111110ppXXp 经数学变换得：定义：为Logistic变换，即： ppXXpp 110)1/(ln)1/(ln)(logpppitppXXpLogit 110)(10.2.2Logistic回归模型的极大似然估计回归模型的极大似然估计Logistic回归模型是通过极大似然估计法得到的，应变量 取值为0和1，设事件发生记为y=1，否则为0，设自变量 ，n组观测数据记为 , 。记 ， ，则 与 的Logistic回归模型是：2022年6月22日星期三Data Mining: Concepts and Techniques52yTkxxxx
26、),(21),(21iikiiyxxxni, 2 , 1TikiiixxxX), 1 (2110ixiyikiixxx,21iXTiXTikxkixikxkixikkiiieeeexxfyE11)()(110110110易知， 是均值为 的0-1型分布，其分布律为 ，则 的似然函数和对数似然函数分别为： 2022年6月22日星期三Data Mining: Concepts and Techniques53iyiiyiiyiiyf1)1 ()(niyi, 2 , 1; 1 , 0nyyy,21niiyiiyiL11)1 (niiiiiniiiiiyyyL11)1ln(1ln)1ln()1 (ln
27、ln代入 ,得记 ，选取 的估计 使得 达到极大，这就是Logistic回归模型的极大似然估，该过程的求解需要采用牛顿（Newton-Raphson）迭代法。 2022年6月22日星期三Data Mining: Concepts and Techniques54ikxkixikxkixiee1101101niiXTiTiniikxkixikkiieXyexxyL11110110)1ln()1ln()(ln)(ln)(LLLTk),(10Tk),(10)(LL构造得分函数 ，共k+1个非线性方程组，令其=0求解 ，其中2022年6月22日星期三55( )( ),0,1,2,ggLLSgk0( )
28、,0,1,2,1TXiniggiigTXiix eSy xgke构造得分函数 ，共k+1个非线性方程组，令其=0求解 ，其中2022年6月22日星期三56( )( ),0,1,2,ggLLSgk0( ),0,1,2,1TXiniggiigTXiix eSy xgke构造信息矩阵 ，即 二阶导矩阵的负矩阵，其中很明显 ，故 是一个对称矩阵。2022年6月22日星期三57khghgLLIgh, 2 , 1 , 0,)()(2)(LLkhgeexxIniiXTiXTihiggh, 2 , 1 , 0,)1 ()(02)()(hgghII)(I构造信息矩阵 ，即 二阶导矩阵的负矩阵，其中很明显 ，故
29、是一个对称矩阵。2022年6月22日星期三58khghgLLIgh, 2 , 1 , 0,)()(2)(LLkhgeexxIniiXTiXTihiggh, 2 , 1 , 0,)1 ()(02)()(hgghII)(I牛顿（Newton-Raphson）迭代法为2022年6月22日星期三591111 ()()kkkkIF10.2.3 Logistic 回归和线性判别函数回归和线性判别函数LDA的比较的比较LDA2022年6月22日星期三60牛顿（Newton-Raphson）迭代法2022年6月22日星期三6162用决策树归纳分类用决策树归纳分类决策树一个类似于流程图的数结构内部节点表示一个属
30、性上的测试每个分支代表一个测试的输出叶结点代表类或类分布决策树的生成包括两个过程树的建构首先所有的训练样本都在根结点基于所选的属性循环的划分样本树剪枝识别和删除哪些反应映噪声或孤立点的分支决策树的使用:为一个未知的样本分类在决策树上测试样本的属性值2022年6月22日星期三Data Mining: Concepts and Techniques632022年6月22日星期三Data Mining: Concepts and Techniques64决策树归纳的算法决策树归纳的算法基本算法以自顶向下递归的各个击破方式构造决策树首先, ,所有的训练样本都在根结点所有属性都是分类的( (如果值是连续的, ,它们应预先被离散化) )基于所选属性递归的划分样本在启发式或统计度量的基础上选择测试属性( (例如, ,信息增益) )停止划分的条件给定节点的所有样本属于同一个类没有剩余属性可以用来进一步划分样本- -使用多数表决来分类叶节点没有剩余的样本
