第一章-机器学习及数据挖掘基础原理ppt课件.pptx

第一章 机器学习及数据挖掘基本原理王斌中国科学院信息工程研究所大数据核心技术之数据挖掘与机器学习技术探索及应用目录基本概念典型应用预备知识什么是机器学习(Machine Learning) 学习能力是人类智能的一种体现 机器学习是研究如何“利用经验来改善计算机系统自身的性能”的学科-From T. M. Mitchell TM. Machine Learning . New York: McGraw-Hill, 1997. 机器学习是研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使不断改善自身的性能-来自百度百科机器学习 vs. 人类学习什么是数据挖掘(Data Mining) 数据挖掘常常也叫知识发现(Knowledge)，有多种文字不同但含义接近的定义，例如“识别出巨量数据中有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程” 。也可以顾名思义，数据挖掘就是试图从海量数据中找出有用的知识-From U. Fayyad, G. Piatetsky-Shapiro, R. Smyth. Knowledge discovery and data mining: Towards a unifying framework. In: Proc. KDD96, Portland, OR, 82-88.机器学习 vs. 数据挖掘周志周志华华，机器学习与数据挖掘。中国计算机学会通讯， 2007, 3(12): 35-44.机器学习和其他学科什么是大数据(Big Data)4V理论 海量的数据规模（volume） 快速的数据流转和动态的数据体系（velocity） 多样的数据类型（variety） 巨大的数据价值（value）大数据的魔力 Google利用大数据预测了H1N1流感的爆发 百度利用大数据成功预测2014年世界杯(从淘汰赛到决赛全部正确) 核心原因：大数据+机器学习大数据 vs. 机器学习存储分析获取高性能计算机器学习数据“大” vs. 机器学习 Its not who has the best algorithm wins, its who has the most data. (成功的机器学习应用不是拥有最好的算法，而是拥有最多的数据！)Michele Banko, and Eric Brill. Scaling to Very Very Large Corpora for Natural Language Disambiguation. In proceedings of ACL2001, page 26-33.机器学习方法分类 机械学习（Rote learning）：学习者无需任何推理或其它的知识转换，直接吸取环境所提供的信息。如塞缪尔的跳棋程序。 示教学习（Learning from instruction）：学生从环境（教师或其它信息源如教科书等）获取信息，把知识转换成内部可使用的表示形式，并将新的知识和原有知识有机地结合为一体。 类比学习（Learning by analogy）：利用二个不同领域（源域、目标域）中的知识相似性，可以通过类比，从源域的知识（包括相似的特征和其它性质）推导出目标域的相应知识，从而实现学习。例如，一个从未开过货车的司机，只要他有开小车的知识就可完成开货车的任务。 归纳学习（Learning from induction）：教师或环境提供某概念的一些实例或反例，让学生通过归纳推理得出该概念的一般描述。归纳学习方法分类 监督学习(Supervised Learning)：监督学习是从标记的训练数据来推断一个功能的机器学习任务。如分类、回归分类、回归。 非监督学习(Unsupervised Learning)：无监督学习的问题是，在未标记的数据中，试图找到隐藏的结构。如聚类聚类、密度估计。 强化学习(Reinforcement Learning)：强化学习是机器学习中的一个领域，强调如何基于环境而行动，以取得最大化的预期利益。机器学习基本过程表示表示(Representation)训练训练(Training/Learning)测试测试(Testing/Predicting/Inference)将数据对象进行特征(feature)化表示给定一个数据样本集，从中学习出规律（模型）目标：该规律不仅适用于训练数据，也适用于未知数据(称为泛化能力)对于一个新的数据样本，利用学到的模型进行预测例子：天气预报 目标：预测明天北京会不会下雨 数据：过去10年北京每一天的天气数据 那天是否下雨：是/否 那天的前一天傍晚18点的气温、相对湿度、风向、风速、气压等(特征) 某条数据: 训练：学习得到规律（模型） 预测：给定今天傍晚18点的气温、相对湿度、风向、风速、气压等、根据模型预测明天是否下雨机器学习的关键问题 【表示】如何表示数据样本？ 通常用一个向量来表示一个样本，向量中选用哪些特征是关键 【训练】如何找出规律【模型+策略+算法】* 通常变成一个选择题，给你n个候选的模型让你选。【模型】 确定选择的标准（什么样的模型才叫好模型）【策略】 如何快速地从n个模型中选出最好的【算法】 【测试】如何根据找到的规律进行预测*李航，统计学习方法，清华大学出版社，2013年5月问题一：如何表示样本？ 向量表示法【本课程重点】 图表示法例子：图像识别例子：家庭用车判别 任务：把车分类 家庭用车/非家庭用车 样本：车 问题：如何把车表示成一个向量？选取哪些特征？ 特征：价格，排量例子：心脏病预测 任务：预测病人是否会发心脏病 样本：病人 问题：如何把病人表示成一个向量？选取哪些特征？ 特征：血糖，血压，血脂，心率例子：预测天气 任务：预测每天的天气如何 样本：每一天 问题：如何把每天表示成一个向量？选取哪些特征？ 特征：温度，相对湿度，风向，风速，气压问题二：如何找出规律？模型策略算法确定要找的是哪类规律（函数形式）或者说假设空间，比如线性函数从众多可能的规律中选出最好的选择标准，比如某个损失函数最小如何快速寻找到最好结果，比如牛顿法例子：房价预测策略：最小化损失函数(误差平方和)算法：梯度下降法模型：线性函数来自http:/cs229.stanford.edu问题三：根据找到的规律进行预测 打分，根据分数作判别目录基本概念典型应用预备知识例子：网页分类例子：人脸识别例子：搜索引擎结果排序例子：垃圾邮件过滤例子：机器翻译例子：文档自动摘要例子：手写识别例子：图像去噪例子：视频跟踪和智能事件分析视频跟踪视频跟踪事件分析事件分析行人跟踪行人跟踪车辆跟踪车辆跟踪打架打架交通事故交通事故例子：推荐系统例子：计算广告目录基本概念典型应用预备知识向量空间模型及文本向量向量空间模型及文本向量向量 向量(vector，也称为矢量)：既有大小又有方向的量，通常用有向线段表示，记作 或者 考虑从空间坐标系原点出发(其他向量可以平移到原点出发)的向量 ，终点坐标为，我们称之为一个n维向量x1M2M 12M M x1M2M 向量的运算 向量的运算：加、减、倍数、内积(inner product，也称点积)1122121,.,.,nnnniiixyxy xyxyxxxxxyx y 向量的模、距离和夹角 向量的模(大小) 向量的(欧氏)距离 夹角22212|.nxxxxx2221122( , )()().()nndist x yxyxyxy cos| |xyxy t1t242向量空间模型 向量空间模型(Vector Space Model，VSM)由康奈尔大学 Salton等人上世纪70年代提出并倡导，原型系统SMART* 每篇文档(或者每个查询)都可以转化为一个向量，于是文档之间的相似度可以通过向量之间的距离来计算 向量中的每一维对应一个词项(term)或者说文本特征*可从ftp:/ftp.cs.cornell.edu/pub/smart/下载全部源码和相关语料文档-词项矩阵(Doc-Term Matrix)12111211221222*12 . . . . . nnnm nmmmmndddaaattaaaAtaaan篇文档，m个词项构成的矩阵Am*n，每列可以看成每篇文档的向量表示，同时，每行也可以可以看成词项的向量表示。每个文档之间可以计算相似度，每个词项之间也可以计算相似度一个例子 查询q：(,) 文档d1：(,) 文档d2：(,)1220022006 0 101 013 221 000 100 101 10ddq 世界杯德国韩国日本举行一个例子(续) 查询和文档进行向量的相似度计算： 采用内积： 文档d1与q的内积：1*1+3*2=7 文档d2与q的内积：2*2=4 夹角余弦： 文档d1与q的夹角余弦： 文档d2与q的夹角余弦：70.9012 540.635 8相似度的计算可以有很多种，可以选用内积进行计算向量空间模型VSM中三个关键问题 词项的选择：词项的选择：选择什么样的单位作为向量的每一维 权重计算权重计算：即计算每篇文档中每个词项的权重，即得到向量的每一维大小 相似度计算：相似度计算：计算向量之间的相似度词项选择 词项是能代表文档内容的特征 词项粒度：可以是字、词、短语、N-gram或者某种语义单元 降维：VSM中向量的维数很大时，往往也同时引入了很多噪音。因此，实际应用中，会采用一些降维策略(如：去停用词、对英文进行词干还原等)N-Gram是大词汇连续语音识别中常用的一种语言模型，对中文而言，我们称之为汉语语言模型(CLM, Chinese Language Model)。汉语语言模型利用上下文中相邻词间的搭配信息，在需要把连续无空格的拼音、笔划，或代表字母或笔划的数字，转换成汉字串(即句子)时，可以计算出具有最大概率的句子，从而实现到汉字的自动转换，无需用户手动选择，避开了许多汉字对应一个相同的拼音(或笔划串，或数字串)的重码问题。权重计算 布尔权重：词项 i在文档j中的权重aij=0 or 1 (出现则取1，否则取0) TF权重：TF (Term Frequency)是词项在文档中出现的次数次数，表示的是词项在文档内的代表性。权重aij=TFij (原始 TF)或者归一化后的TF值 TF权重还有多种计算方式 例子：我 爱 北京 天安门，天安门 上 太阳 升。 上述文档中，TF(北京)=1，TF(天安门)=2，权重计算(续) IDF权重： 词项的文档频率DF(Document Frequency)：整个文档集合中出现词项的文档数目文档数目。DF反映了词项的区分度，DF越高表示词项越普遍，因此其区分度越低，因此权重也越低。 逆文档频率(Inverse DF，IDF)：DF的倒数，通常采用如下公式进行计算(N是文档集合中所有文档的数目所有文档的数目)： 向量空间模型中通常采用TF*IDF的方式计算权重。即词项 i在文档dj中的权重aij=TFij *IDFi某词某词项在某个文档很重要项在某个文档很重要TFTF高，而其它文档所不具有的高，而其它文档所不具有的IDFIDF高高 例子：我 爱 北京 天安门，天安门 上 太阳 升 TF(天安门)=2， DF=20， N=100，于是TFIDF(天安门)=2*100/20=10NIDFDF相似度计算 22222222Dot product): ( , )( )( )Cosine: ( , )|2( )2Dice: ( , )|Jaccard: ( , )|iiiiiiiiiiiiiiiiiSim d qdqababdqSim d qdqababdqSim d qdqabdqSim d qdqd 内积(22( * )( * )iiiiiiiiiiabqababt1t2dq夹角余弦用得比较多，只考虑夹角概率论基础随机试验和随机事件 随机试验：可在相同条件下重复进行；试验可能结果不止一个，但能确定所有的可能结果；一次试验之前无法确定具体是哪种结果出现。 掷一颗骰子，考虑可能出现的点数 随机事件：随机试验中可能出现或可能不出现的情况叫“随机事件”，简称事件 掷一颗骰子，4点朝上概率和条件概率 概率：直观上来看，事件A的概率是指事件A发生的可能性，记为P(A) 掷一颗骰子，出现6点的概率为多少？ 条件概率：已知事件A发生的条件下，事件B发生的概率称为A条件下B的条件概率，记作P(B|A) 30颗红球和40颗黑球放在一块，请问第一次抽取为红球的情况下第二次抽取黑球的概率？1/69!54乘法公式、全概率公式和贝叶斯公式 乘法公式： P(AB)P(A)P(B|A) P(A1A2An)P(A1)P(A2|A1).P(An|A1An1) 全概率公式：A1A2An是整个样本空间的一个划分1( )() (|)niiiP BP A P B A贝叶斯公式 先验概率：P(B) 后验概率：P(B|A)=P(A|B)P(B)/P(A) 例子：某个学校有60%男生，40%女生，男生都穿长裤，女生有一半长裤一半裙子，求该学校穿长裤的学生是男生的概率。 B=是男生，A=穿长裤 P(B)=0.6, P(A)=0.6+0.2=0.8, P(A|B)=1.0, 于是 P(B|A)=P(A|B)P(B)/P(A)=1*0.6/0.8=0.75先验概率（prior probability）是指根据以往经验和分析得到的概率,如全概率公式,它往往作为由因求果问题中的因出现.后验概率是指通过调查或其它方式获取新的附加信息，利用贝叶斯公式对先验概率进行修正，而后得到的概率。先验概率不是根据有关自然状态的全部资料测定的，而只是利用现有的材料(主要是历史资料)计算的；后验概率使用了有关自然状态更加全面的资料，既有先验概率资料，也有补充资料；先验概率的计算比较简单，没有使用贝叶斯公式；而后验概率的计算，要使用贝叶斯公式，而且在利用样本资料计算逻辑概率时，还要使用理论概率分布，需要更多的数理统计知识。事件的独立性 两事件独立：事件A、B，若P(AB)=P(A)P(B)，则称A 、B独立 三事件独立：事件A B C，若满足P(AB)=P(A)P(B), P(AC)=P(A)P(C),P(BC)=P(B)P(C), P(ABC)=P(A)P(B)P(C)，则称A、B、C独立 多事件独立：两两独立、三三独立、四四独立.随机变量 随机变量：若随机试验的各种可能的结果都能用一个 变量的取值（或范围）来表示，则称这个变量为随机变量，常用X、Y、Z来表示 (离散型随机变量)：掷一颗骰子，可能出现的点数X (可能取值1、2、3、4、5、6) (连续型随机变量)：北京地区的温度(-1545)本章小结 机器学习的基本概念 机器学习的典型应用 预备知识 向量空间模型及文本向量：如何将很多篇文档中的每一篇文档转化成一个向量 概率论：概率、条件概率、贝叶斯公式谢谢！