机器学习及数据挖掘基础原理

1、第一章 机器学习及数据挖掘基本原理,王斌 中国科学院信息工程研究所,大数据核心技术之数据挖掘与机器学习技术探索及应用,目录,什么是机器学习(Machine Learning),学习能力是人类智能的一种体现 机器学习是研究如何“利用经验来改善计算机系统自身的性能”的学科-From T. M. Mitchell TM. Machine Learning . New York: McGraw-Hill, 1997. 机器学习是研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使不断改善自身的性能-来自百度百科,机器学习 vs. 人类学习,什么是数据挖掘(Data M

2、ining),数据挖掘常常也叫知识发现(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. 数据挖掘,周志华，机器学习与数据挖掘。

3、中国计算机学会通讯， 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

4、, 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 instruc

5、tion）：学生从环境（教师或其它信息源如教科书等）获取信息，把知识转换成内部可使用的表示形式，并将新的知识和原有知识有机地结合为一体。 类比学习（Learning by analogy）：利用二个不同领域（源域、目标域）中的知识相似性，可以通过类比，从源域的知识（包括相似的特征和其它性质）推导出目标域的相应知识，从而实现学习。例如，一个从未开过货车的司机，只要他有开小车的知识就可完成开货车的任务。 归纳学习（Learning from induction）：教师或环境提供某概念的一些实例或反例，让学生通过归纳推理得出该概念的一般描述。,归纳学习方法分类,监督学习(Supervised Lea

6、rning)：监督学习是从标记的训练数据来推断一个功能的机器学习任务。如分类、回归。 非监督学习(Unsupervised Learning)：无监督学习的问题是，在未标记的数据中，试图找到隐藏的结构。如聚类、密度估计。 强化学习(Reinforcement Learning)：强化学习是机器学习中的一个领域，强调如何基于环境而行动，以取得最大化的预期利益。,机器学习基本过程,将数据对象进行特征(feature)化表示,给定一个数据样本集，从中学习出规律（模型） 目标：该规律不仅适用于训练数据，也适用于未知数据(称为泛化能力),对于一个新的数据样本，利用学到的模型进行预测,例子：天气预报,目标

7、：预测明天北京会不会下雨 数据：过去10年北京每一天的天气数据 那天是否下雨：是/否 那天的前一天傍晚18点的气温、相对湿度、风向、风速、气压等(特征) 某条数据: 训练：学习得到规律（模型） 预测：给定今天傍晚18点的气温、相对湿度、风向、风速、气压等、根据模型预测明天是否下雨,机器学习的关键问题,【表示】如何表示数据样本？ 通常用一个向量来表示一个样本，向量中选用哪些特征是关键 【训练】如何找出规律【模型+策略+算法】* 通常变成一个选择题，给你n个候选的模型让你选。【模型】 确定选择的标准（什么样的模型才叫好模型）【策略】 如何快速地从n个模型中选出最好的【算法】 【测试】如何根据找到的

8、规律进行预测,*李航，统计学习方法，清华大学出版社，2013年5月,问题一：如何表示样本？,向量表示法【本课程重点】 图表示法, 1, 2, ,例子：图像识别,例子：家庭用车判别,任务：把车分类 家庭用车/非家庭用车 样本：车 问题：如何把车表示成一个向量？选取哪些特征？ 特征：价格，排量,例子：心脏病预测,任务：预测病人是否会发心脏病 样本：病人 问题：如何把病人表示成一个向量？选取哪些特征？ 特征：血糖，血压，血脂，心率,例子：预测天气,任务：预测每天的天气如何 样本：每一天 问题：如何把每天表示成一个向量？选取哪些特征？ 特征：温度，相对湿度，风向，风速，气压,问题二：如何找出规律？,从

9、众多可能的规律中选出最好的选择标准，比如某个损失函数最小,如何快速寻找到最好结果，比如牛顿法,例子：房价预测,策略：最小化损失函数(误差平方和),算法：梯度下降法,模型：线性函数,来自,问题三：根据找到的规律进行预测,打分，根据分数作判别,目录,例子：网页分类,例子：人脸识别,例子：搜索引擎结果排序,例子：垃圾邮件过滤,例子：机器翻译,例子：文档自动摘要,例子：手写识别,例子：图像去噪,例子：视频跟踪和智能事件分析,视频跟踪,事件分析,行人跟踪,车辆跟踪,打架,交通事故,例子：推荐系统,例子：计算广告,目录,向量空间模型及文本向量,向量,向量(v

10、ector，也称为矢量)：既有大小又有方向的量，通常用有向线段表示，记作 或者 考虑从空间坐标系原点出发(其他向量可以平移到原点出发)的向量 ，终点坐标为，我们称之为一个n维向量,向量的运算,向量的运算：加、减、倍数、内积(inner product，也称点积),1,2,4 1,3,5 =11+23+45=27,向量的模、距离和夹角,向量的模(大小) 向量的(欧氏)距离 夹角,| |,| |,dist( , ),42,向量空间模型,向量空间模型(Vector Space Model，VSM)由康奈尔大学 Salton等人上世纪70年代提出并倡导，原型系统SMART* 每篇文档(或者每个查询)都

11、可以转化为一个向量，于是文档之间的相似度可以通过向量之间的距离来计算 向量中的每一维对应一个词项(term)或者说文本特征,*可从/pub/smart/下载全部源码和相关语料,文档-词项矩阵(Doc-Term Matrix),n篇文档，m个词项构成的矩阵Am*n，每列可以看成每篇文档的向量表示，同时，每行也可以可以看成词项的向量表示。,每个文档之间可以计算相似度，每个词项之间也可以计算相似度,一个例子,查询q：(,) 文档d1：(,) 文档d2：(,),一个例子(续),查询和文档进行向量的相似度计算： 采用内积： 文档d1与q的内积：1*1+3*2

12、=7 文档d2与q的内积：2*2=4 夹角余弦： 文档d1与q的夹角余弦： 文档d2与q的夹角余弦：,相似度的计算可以有很多种，可以选用内积进行计算,向量空间模型VSM中三个关键问题,词项的选择：选择什么样的单位作为向量的每一维 权重计算：即计算每篇文档中每个词项的权重，即得到向量的每一维大小 相似度计算：计算向量之间的相似度,词项选择,词项是能代表文档内容的特征 词项粒度：可以是字、词、短语、N-gram或者某种语义单元 降维：VSM中向量的维数很大时，往往也同时引入了很多噪音。因此，实际应用中，会采用一些降维策略(如：去停用词、对英文进行词干还原等),N-Gram是大词汇连续语音识别中常用

13、的一种语言模型，对中文而言，我们称之为汉语语言模型(CLM, Chinese Language Model)。汉语语言模型利用上下文中相邻词间的搭配信息，在需要把连续无空格的拼音、笔划，或代表字母或笔划的数字，转换成汉字串(即句子)时，可以计算出具有最大概率的句子，从而实现到汉字的自动转换，无需用户手动选择，避开了许多汉字对应一个相同的拼音(或笔划串，或数字串)的重码问题。,权重计算,布尔权重：词项 i在文档j中的权重aij=0 or 1 (出现则取1，否则取0) TF权重：TF (Term Frequency)是词项在文档中出现的次数，表示的是词项在文档内的代表性。权重aij=TFij (原

14、始 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 某词项

15、在某个文档很重要TF高，而其它文档所不具有的IDF高 例子：我 爱 北京 天安门，天安门 上 太阳 升 TF(天安门)=2， DF=20， N=100，于是TFIDF(天安门)=2*100/20=10,相似度计算,夹角余弦用得比较多，只考虑夹角,概率论基础,随机试验和随机事件,随机试验：可在相同条件下重复进行；试验可能结果不止一个，但能确定所有的可能结果；一次试验之前无法确定具体是哪种结果出现。 掷一颗骰子，考虑可能出现的点数 随机事件：随机试验中可能出现或可能不出现的情况叫“随机事件”，简称事件 掷一颗骰子，4点朝上,概率和条件概率,概率：直观上来看，事件A的概率是指事件A发生的可能性，记为

16、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是整个样本空间的一个划分,贝叶斯公式,先验概率：P(B) 后验概率：P(B|A)=P(A|B)P(B)/P(A) 例子：某个学校有60%男生，40%女生，男生都穿长裤，女生有一半长裤一半裙

17、子，求该学校穿长裤的学生是男生的概率。 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