登峰杯数据挖掘竞赛骨干教师培训课程-数据挖掘基本方法培训.pdf

数据挖掘基础知识、基本方法培训--学科概念、基本流程、模型算法、竞赛建议语义计算与数据挖掘实验室 郭光明“登峰杯”全国中学生数据挖掘竞赛课程提纲 学科概念辨析 基本流程介绍 基础方法  从最小二乘法开始  非线性的拓展 竞赛题目 / 现实生活的实例分析及建议2为什么区分基本概念 学习的第一步 新想法(idea)的基础 定义游戏用的规则 交流、写作的前提 数据挖掘较晚定型的新兴学科  数据是CS和EE交叉的交叉学科3数据挖掘最重要著作： 《数据挖掘--概念与技术》 URL: http://hanj.cs.illinois.edu/数据挖掘源流 知识发现与数据挖掘的意义几乎相同(KDD)  依赖高性能计算算法、计算复杂性分析4数据挖掘数据仓库数据库系统面向主题集成时变分类聚类模式挖掘商业智能口碑 营销欺诈 检测推荐 系统决策 支持个性 化知识发现增删 查改第四范式数学建模Jim Gray数据 密集科学 发现方法 论(1970s)(1990s)联机分析(2000s)(2000s)数据挖掘源流5专家系统知识库自动推理机器学习人工智能(1970s)包括学习、推理、规划、感知、语言 理解、机器人控制等大规模的人工智能系统，应用AI技术 到工程实践和商业决策(1980s)手工录入规则数据工程探索如何使计算机通过经验学习提高 性能数据挖掘从大规模、多个数据库中AI的方法发 现知识，并且用于预测、决策、排序 (2000s)数据库 知识管理、数据工程与数据挖掘的意义几乎相同(KDE)  依赖人工智能技术、交叉学科的知识Edward Feigenbaum机器学习与数据挖掘关系6偏理论统计学习偏数据知识工程 提供更好解法提供更好解法提供更好问题提供更好问题机器学习数据挖掘等应用 研究对象都不特定、交叉学科性质明显分类聚类模式挖掘监督学习无监督 学习模式识别数据挖据/机器学习的相关理论学科 概率论(Probability Theory) 研究随机现象数量规律的学科  极限定理、随机过程  保险赔率期望，接线员峰值估计，提供建模工具 数理统计(Mathematical Statistics) 以概率论为理论基础  仅仅是数量关系上分析，存在置信区间  不代表发现了实际物理过程或者因果关系  生物学、农业试验、医学实验、信号处理 计算机复杂性理论(Computational complexity)分析复杂性的理论上界分析是否可计算分析是否可学习7不被数学届承认机器学习与人工智能各子学科的关系8机器学习机器计算机学习积累经验机器学习数据挖掘语音识别计算机视觉多媒体处理自然语言处理 内容上看，机器学习(CS) 与模式识别(EE)的含义几乎相同信息检索多智能体专家系统人工智能/计算机科学 两个紧密相连的学科  “人工智能之父“ 和 ”计算机科学之父”  “人工智能” 亦可称 “复杂信息处理”(1950s) 已经做到的  IBM Waston自动知识问答世界冠军  DeepMind AlphaGo围棋竞赛排名世界第一  讯飞 IflyTek语音合成、转写速记超过普通人 未来的方向  辅助人开车，辅助人做实验，辅助人做决策  机器人参加高考并考上重点大学  机器人足球队成为世界杯冠军9艾兰· 图灵计算机这个学科 计算机科学与技术学院 计算机科学与工程系10 计算机是自然科学的一部分，但是工程化非常成功的一个学 科，成了各行各业的基础  计算机初始目标即解放人脑，制造像人脑一样复杂的信息处 理装置(人工智能、数据库系统)科学：简化、分类工程：复杂、精巧V.S.数据挖掘数据挖掘数据挖掘(Data Mining) 狭义语境下，数据一般指  存在数据库(Database)中的结构化、半结构化历史记录  存储、性能的要求高 广义语境下  所有数据的分析、理解都可归类到数据挖掘  气候数据、医疗数据、科学数据、教育数据 典型数据  互联网数据(文本、超链接、互动记录等)  社交关系、社交媒体数据  购物篮数据、商业交易记录  GPS轨迹数据11数据挖掘(Data Mining) 面向应用、实践性强  推荐系统  搜索引擎Google、Baidu 都可以看作是数据库系统的一个扩展  增删查改之外，具有强大的信息处理能力，算法复杂 新问题、新应用、交叉课题受欢迎  社会生活中新问题总是层出不穷  进而带来建模，算法，体系结构的要求12数据挖掘典型分支 序列数据挖掘 时空数据挖掘 图数据挖掘 / 社交网络数据挖掘  (计算复杂性) -> 复杂网络、复杂系统(物理学的分支) 移动数据挖掘  、GPS、基站 生物、医疗数据挖掘  教育数据挖掘13课程提纲 学科概念辨析 基本流程介绍 基础方法  从最小二乘法开始  非线性的拓展 竞赛题目 / 现实生活的实例分析及建议14数据挖掘/机器学习基本流程15问题描述数学表示评价函数优化算法计算资源大规模、分布式、专用芯片问题描述 确定 输入、输出的定义 二分类 (binary classification)  多分类 (multi-classification)  多标签分类 (multi-label classification)  线性回归(linear regression)  缺失值填充(matrix completion)  数据非平衡问题 (data imbalance)16𝑦𝐹(𝑦)𝑧类别估计值单一值 OR 向量分类回归 特征抽取 (Feature Extraction)  占据大部分工作量 特征选择 (Feature Selection) 数据结构 (Data Structure) 名称变量(nomial variable) -> 数值变量(numeric variable) 归一化 (Normalization) 缺失值填充(Default)17数学表示数学表示数学表示- 特征选择 特征相关性分析  舍弃不显著相关特征 最优子集  列举全部可能组合，选择最优  时间过长 前向逐步选择  逐次增加特征到模型  逐阶段不调整之前特征拟合的系数  后向逐步选择  逐次减少特征到模型18评价函数- 模型衡量 奥卡姆剃刀原则( Ocam razor Principle) 最小描述长度原则(Minimum Description Length) 一般而言是  错分率 + 模型的复杂程度之间的一个平衡  既不能欠拟合 、也不能 过拟合19 K-折交叉验证 (Cross Validation)评价函数- 模型选择 损失函数20优化目标 基本假设指数损失函数：Logistic损失函数： 一般还会增加正则化项/规范化项，防止过拟合优化算法 考虑的方面 精度  收敛速度 (时间)  内存消耗 (空间)21闭形闭形 式解式解求导证明 概率推断迭代公式 终止条件目标函数一般写成极小min评价函数的形式否是计算资源 程序设计语言(Matlab, Python, C/C++, Java, R) 并行、分布式运行环境 (OpenMP, SparK, Hadoop) 操作系统平台 (Linux, Windows) 芯片 (CPU, GPU, 专用芯片)22数据可视化23 安斯科姆四重数四组数据拥有相同的均值、方差和相关系数； 但是分布完全不同属性值x 均值9x 样本方差11y 均值7.50y 样本方差4.125x - y 相关系数0.816线性拟合y = 3.00 + 0.500x数据可视化 安斯科姆四重数 作图非线性、离群点、错误值导致线性拟合不再适用24课程提纲 学科概念辨析 基本流程介绍 基础方法  从最小二乘法开始  非线性的拓展 竞赛题目 / 现实生活的实例分析及建议25解方程组与最小二乘法26𝛾0+ 3𝛾1= 4𝛾0+ 2𝛾1= 3𝛾0+ 3𝛾1= 4 𝛾0+ 2𝛾1= 3 𝛾0+ 4𝛾1= 6𝑦y𝑧 = 1 ∗ 𝑦 + 1(2,3)(3,4)𝛾0= 1𝛾1= 1𝛾0= ?𝛾1= ?𝑦y𝑧 = 𝛾1𝑦 + 𝛾0(2,3)(3,4)(4,5) 矛盾方程组 -> 最小二乘法 如果多余数据不舍弃？线性回归+最小二乘法(Least Squares) 给定𝑋 是一个𝑝维的输入 对于N个输入观测数据 𝑦1,𝑧1,…, 𝑦𝑁,𝑧𝑁, 最小二乘法评价函数：27勒让德(1805). “一种计算彗星轨道的新方法“ . 72–80. 线性回归模型：最小二乘(LS)的闭形式解 目标是求解使得𝑆𝑇𝑇(𝛾) 最小的参数 𝛾28求导得：令：可得唯一解： 评价函数写成矩阵形式:亦可用最速下降法来优化 梯度𝑔 𝛾 ：29LS的更新公式：𝛾𝑡+1= 𝛾𝑡− 𝛽 𝑔(𝛾𝑡)最速下降法,也就是沿梯度(增长率)反方向按一定步长 𝛽下降𝛾𝑡+1= 𝛾𝑡− 𝛽 (−2𝐗𝑇(𝒛 − 𝐗𝛾𝑡))𝛾𝑡+1= 𝛾𝑡− 𝛽 (2𝐗𝑇(𝐗𝛾𝑡− 𝒛))一般的梯度下降法 非唯一解函数梯度下降有可能非最优解30最小二乘法的几何解释 解得的条件是：31假设𝐗 由𝒚𝟐,𝒚𝟑两个维度构成的平面即：𝐗𝑇与 (𝒛 − ෝ 𝒛) 正交也就是： 𝐗𝑇与 (𝒛 − 𝐗෡𝛾) 必须正交，其中𝐗෡𝛾 = ෝ 𝒛最小二乘法的概率解释 用 𝜃 代替 𝛾, 线性拟合：  其中，𝜖𝑖是第𝑖 个数据的未被拟合随机噪音32 最大似然估计等同于最小二乘 假设𝜖服从正太分布𝑁(0,𝜎),则：偏最小二乘法 输入数据的各位变量线性相关时  或者输入数据𝑁小于输入变量(特征)个数𝑝时 基本思想：  主成分分析法(PCA) 提取反映数据变异最大的成分(正交)  上次主成分线性拟合 𝒛 后的残差作为下次的输入  最小二乘法依次拟合各个主成分33决策树+最小二乘 决策树：  根据特定指标，选择划分点，划分特征空间一个个矩形中  然后用简单模型，比如(常量)来拟合各个矩形子空间34YesNoNoYes  Quinlan JR, Induction of decision trees.(ID3), Machine Learning, 1986, 1(1):81-106决策树+最小二乘 最小二乘回归树生成算法(CART)：  1）依次遍历每个特征j，以及该特征的每个取值s，计算每个切分 点（j, s）的损失函数，选择损失函数最小的切分点 2）使用上步得到的切分点将当前的输入空间划分为两个部分  3）然后将被划分后的两个部分再次计算切分点，依次类推，直到 不能继续划分  4）最后将输入空间划分为M个区域R1,R2,…,RM,生成的决策树为：其中cm为所在区域的输出值的平均。

35 Breiman L, Freidman J, Stone C., Olshen R. Classification and Regression Trees.(CART), Wadsworth Statistics/Probability, 1st, edition 1984 , 十大数据挖掘算法 - 2006 ICDM的一次投票 #1: C4.5 (61 票), presented by Hiroshi Motoda  #2: K-Means (60 票), presented by Joydeep Ghosh  #3: SVM (58 票), presented by Qiang Yang(杨强)  #4: Apriori(52 票), presented by Christos Faloutsos  #5: EM (4。