第一章-机器学习及数据挖掘基础原理

第一章机器学习及数据挖掘基本原理王斌中国科学院信息工程研究所大数据核心技术之数据挖掘与机器学习技术探索及应用目录基本概念典型应用预备知识什么是机器学习(MachineLearning)•学习能力是人类智能的一种体现•机器学习是研究如何“利用经验来改善计算机系统自身的性能”的学科----FromT.M.MitchellTM.MachineLearning.NewYork:McGraw-Hill,1997.•机器学习是研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使不断改善自身的性能----来自《百度百科》机器学习vs.人类学习什么是数据挖掘(DataMining)•数据挖掘常常也叫知识发现(Knowledge)，有多种文字不同但含义接近的定义，例如“识别出巨量数据中有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程”。也可以顾名思义，数据挖掘就是试图从海量数据中找出有用的知识----FromU.Fayyad,G.Piatetsky-Shapiro,R.Smyth.Knowledgediscoveryanddatamining:Towardsaunifyingframework.In:Proc.KDD’96,Portland,OR,82-88.机器学习vs.数据挖掘周志华，机器学习与数据挖掘。《中国计算机学会通讯》，2007,3(12):35-44.本课程内容机器学习和其他学科什么是大数据(BigData)•4V理论•海量的数据规模（volume）•快速的数据流转和动态的数据体系（velocity）•多样的数据类型（variety）•巨大的数据价值（value）大数据的魔力•Google利用大数据预测了H1N1流感的爆发•百度利用大数据成功预测2014年世界杯(从淘汰赛到决赛全部正确)•核心原因：大数据+机器学习大数据vs.机器学习存储分析获取高性能计算机器学习数据“大”vs.机器学习•It’snotwhohasthebestalgorithmwins,it’swhohasthemostdata.(成功的机器学习应用不是拥有最好的算法，而是拥有最多的数据！)MicheleBanko,andEricBrill.ScalingtoVeryVeryLargeCorporaforNaturalLanguageDisambiguation.InproceedingsofACL2001,page26-33.机器学习方法分类•机械学习（Rotelearning）：学习者无需任何推理或其它的知识转换，直接吸取环境所提供的信息。如塞缪尔的跳棋程序。•示教学习（Learningfrominstruction）：学生从环境（教师或其它信息源如教科书等）获取信息，把知识转换成内部可使用的表示形式，并将新的知识和原有知识有机地结合为一体。•类比学习（Learningbyanalogy）：利用二个不同领域（源域、目标域）中的知识相似性，可以通过类比，从源域的知识（包括相似的特征和其它性质）推导出目标域的相应知识，从而实现学习。例如，一个从未开过货车的司机，只要他有开小车的知识就可完成开货车的任务。•归纳学习（Learningfrominduction）：教师或环境提供某概念的一些实例或反例，让学生通过归纳推理得出该概念的一般描述。归纳学习方法分类•监督学习(SupervisedLearning)：监督学习是从标记的训练数据来推断一个功能的机器学习任务。如分类、回归。•非监督学习(UnsupervisedLearning)：无监督学习的问题是，在未标记的数据中，试图找到隐藏的结构。如聚类、密度估计。•强化学习(ReinforcementLearning)：强化学习是机器学习中的一个领域，强调如何基于环境而行动，以取得最大化的预期利益。机器学习基本过程表示(Representation)训练(Training/Learning)测试(Testing/Predicting/Inference)将数据对象进行特征(feature)化表示给定一个数据样本集，从中学习出规律（模型）目标：该规律不仅适用于训练数据，也适用于未知数据(称为泛化能力)对于一个新的数据样本，利用学到的模型进行预测例子：天气预报•目标：预测明天北京会不会下雨•数据：过去10年北京每一天的天气数据•那天是否下雨：是/否•那天的前一天傍晚18点的气温、相对湿度、风向、风速、气压等(特征)•某条数据:18,20,东,15,80,是•训练：学习得到规律（模型）•预测：给定今天傍晚18点的气温、相对湿度、风向、风速、气压等、根据模型预测明天是否下雨机器学习的关键问题•【表示】如何表示数据样本？•通常用一个向量来表示一个样本，向量中选用哪些特征是关键•【训练】如何找出规律【模型+策略+算法】*•通常变成一个选择题，给你n个候选的模型让你选。【模型】•确定选择的标准（什么样的模型才叫好模型）【策略】•如何快速地从n个模型中选出最好的【算法】•【测试】如何根据找到的规律进行预测*李航，《统计学习方法》，清华大学出版社，2013年5月问题一：如何表示样本？•向量表示法【本课程重点】•图表示法[𝑥1,𝑥2,…𝑥𝑛]例子：图像识别例子：家庭用车判别•任务：把车分类家庭用车/非家庭用车•样本：车•问题：如何把车表示成一个向量？选取哪些特征？•特征：价格，排量例子：心脏病预测•任务：预测病人是否会发心脏病•样本：病人•问题：如何把病人表示成一个向量？选取哪些特征？•特征：血糖，血压，血脂，心率例子：预测天气•任务：预测每天的天气如何•样本：每一天•问题：如何把每天表示成一个向量？选取哪些特征？•特征：温度，相对湿度，风向，风速，气压问题二：如何找出规律？模型策略算法确定要找的是哪类规律（函数形式）或者说假设空间，比如线性函数从众多可能的规律中选出最好的选择标准，比如某个损失函数最小如何快速寻找到最好结果，比如牛顿法例子：房价预测策略：最小化损失函数(误差平方和)算法：梯度下降法模型：线性函数来自问题三：根据找到的规律进行预测•打分，根据分数作判别目录基本概念典型应用预备知识例子：网页分类例子：人脸识别例子：搜索引擎结果排序例子：垃圾邮件过滤例子：机器翻译例子：文档自动摘要例子：手写识别例子：图像去噪例子：视频跟踪和智能事件分析视频跟踪事件分析行人跟踪车辆跟踪打架交通事故例子：推荐系统例子：计算广告目录基本概念典型应用预备知识向量空间模型及文本向量向量•向量(vector，也称为矢量)：既有大小又有方向的量，通常用有向线段表示，记作或者•考虑从空间坐标系原点出发(其他向量可以平移到原点出发)的向量，终点坐标为x1,x2,…,xn，我们称之为一个n维向量x1M2M12MMx1M2M向量的运算•向量的运算：加、减、倍数、内积(innerproduct，也称点积)1122121,,...,,,...,nnnniiixyxyxyxyxxxxxyxy1,2,4∙1,3,5=1×1+2×3+4×5=27向量的模、距离和夹角•向量的模(大小)•向量的(欧氏)距离•夹角α22212||...nxxxxx2221122(,)()()...()nndistxyxyxyxycos||||xyxyt1t2𝑥𝑦𝛼dist(𝑥,𝑦)42向量空间模型•向量空间模型(VectorSpaceModel，VSM)由康奈尔大学Salton等人上世纪70年代提出并倡导，原型系统SMART*•每篇文档(或者每个查询)都可以转化为一个向量，于是文档之间的相似度可以通过向量之间的距离来计算•向量中的每一维对应一个词项(term)或者说文本特征*可从下载全部源码和相关语料文档-词项矩阵(Doc-TermMatrix)12111211221222*12...............nnnmnmmmmndddaaattaaaAtaaan篇文档，m个词项构成的矩阵Am*n，每列可以看成每篇文档的向量表示，同时，每行也可以可以看成词项的向量表示。每个文档之间可以计算相似度，每个词项之间也可以计算相似度一个例子•查询q：(2006,1,世界杯,2)•文档d1：(2006,1,世界杯,3,德国,1,举行,1)•文档d2：(2002,1,世界杯,2,韩国,1,日本,1,举行,1)1220022006010101322100010010110ddq世界杯德国韩国日本举行一个例子(续)•查询和文档进行向量的相似度计算：•采用内积：•文档d1与q的内积：1*1+3*2=7•文档d2与q的内积：2*2=4•夹角余弦：•文档d1与q的夹角余弦：•文档d2与q的夹角余弦：70.9012540.6358相似度的计算可以有很多种，可以选用内积进行计算向量空间模型VSM中三个关键问题•词项的选择：选择什么样的单位作为向量的每一维•权重计算：即计算每篇文档中每个词项的权重，即得到向量的每一维大小•相似度计算：计算向量之间的相似度词项选择•词项是能代表文档内容的特征•词项粒度：可以是字、词、短语、N-gram或者某种语义单元•降维：VSM中向量的维数很大时，往往也同时引入了很多噪音。因此，实际应用中，会采用一些降维策略(如：去停用词、对英文进行词干还原等)N-Gram是大词汇连续语音识别中常用的一种语言模型，对中文而言，我们称之为汉语语言模型(CLM,ChineseLanguageModel)。汉语语言模型利用上下文中相邻词间的搭配信息，在需要把连续无空格的拼音、笔划，或代表字母或笔划的数字，转换成汉字串(即句子)时，可以计算出具有最大概率的句子，从而实现到汉字的自动转换，无需用户手动选择，避开了许多汉字对应一个相同的拼音(或笔划串，或数字串)的重码问题。权重计算•布尔权重：词项i在文档j中的权重aij=0or1(出现则取1，否则取0)•TF权重：TF(TermFrequency)是词项在文档中出现的次数，表示的是词项在文档内的代表性。权重aij=TFij(原始TF)或者归一化后的TF值•TF权重还有多种计算方式•例子：我爱北京天安门，天安门上太阳升。•上述文档中，TF(北京)=1，TF(天安门)=2，……权重计算(续)•IDF权重：•词项的文档频率DF(DocumentFrequency)：整个文档集合中出现词项的文档数目。DF反映了词项的区分度，DF越高表示词项越普遍，因此其区分度越低，因此权重也越低。•逆文档频率(InverseDF，IDF)：DF的倒数，通常采用如下公式进行计算(N是文档集合中所有文档的数目)：•向量空间模型中通常采用TF*IDF的方式计算权重。即词项i在文档dj中的权重aij=TFij*IDFi某词项在某个文档很重要TF高，而其它文档所不具有的IDF高•例子：我爱北京天安门，天安门上太阳升•TF(天安门)=2，DF=20，N=100，于是TFIDF(天安门)=2*100/20=10NIDFDF相似度计算22222222Dotproduct):(,)()()Cosine:(,)||||||||2()2Dice:(,)||||||||Jaccard:(,)||||||||iiiiiiiiiiiiiiiiiSimdqdqababdqSimdqdqababdqSimdqdqabdqSimdqdqd内积(22(*)(*)iiiiiiiiiiabqababt1t2dq夹角余弦用得比较多，只考虑夹角概率论基础随机试验和随机事件•随机试验：可在相同条件下重复进行；试验可能结果不止一个