机器学习 课件全套 第1-9章　绪论 - -矩阵与张量分解

机器学习AlphaGo5:0战胜欧洲冠军樊麾2段，法国围棋队总教练2015年10月5日-9日绪论AlphaGo4:1战胜世界冠军李世石9段。李世石被公认为过去10年间韩国最强棋手2016年3月9日-15日韩国首尔绪论AlphaGo3:0战胜围棋等级分当时世界第一的柯洁2017年5月23日-27日乌镇绪论金融商务股票交易投资顾问风险管理和反欺诈客户流失预警服务优化客户沟通绪论智能交通交通监控智能停车智能路灯车路信息管理……绪论能源开发绪论电力传输绪论军事绪论生物制药绪论机器人工业机器人娱乐机器人看护机器人绪论气象预报绪论智能家居绪论游戏绪论机器学习定义Wikipedia机器学习是人工智能的一个分支，即机器基于输入的原始数据生成规则。机器学习是一门系统的学科，它关注设计和开发算法，使得机器的行为随着经验数据的累积而进化，经验数据通常是传感器数据或数据库记录。机器学习（续）TomM.MitchellJasonBrownlee一个机器学习就是从数据中训练出一个模型，该模型有不低于某种评估指标的泛化能力。一个计算机程序能够从经验E中学习（学习任务是T，学习的表现用P衡量），这个程序在任务T与表现衡量P下，可以通过经验E得到改进。机器学习（续）中科院自动化所王珏研究员根据样本集合建立一个模型，并期望这个模型对问题空间中所有样本预测的正确率大于一个给定的常数。模型可以理解为对问题空间的一种统计描述：

①一致性假设

②划分

③泛化能力

发展时期 时间段 主流技术推理期 1956年-1970s初 基于符号知识表示的演绎推理技术知识期 1970s中期-1980s基于符号知识表示，通过获取和利用领域知识来建立专家系统学习期 1980s-至今 符号主义学习、基于神经网络的连接主义学习机器学习发展历程人工智能发展的三个时期机器学习发展历程时间段 机器学习理论 代表性成果1950s初期 人工智能研究处于推理期 A.Newell和H.Simon的“逻辑理论家”（LogicTheorist）程序证明了数学原理，以及“通用问题求解”（GeneralProblemSolving）程序。出现机器学习的相关研究 1952年，阿瑟·萨缪尔（ArthurSamuel）在IBM公司研制了一个西洋跳棋程序，这是人工智能下棋问题的由来。1950s中后期 出现基于神经网络的“连接主义”学习F.Rosenblatt提出感知机（Perceptron），处理线性分类问题，处理不了“异或”逻辑。B.Widrow提出Adaline。机器学习发展历程（续）1950s初期 人工智能研究处于推理期 H.Simon、A.Newell、J.C.Shaw“逻辑理论家”（LogicTheorist）程序证明了《数学原理》52个定理，以及“通用问题求解”（GeneralProblemSolving）程序。MarnivLeeMinskyJohnMcCarthyAllenNewellHerbertA.Simon人工智能之父JohnCliffordShaw机器学习发展历程（续）MarnivLeeMinskyJohnMcCarthy人工智能之父1951年提出思维如何萌发并形成的基本理论1956年达特茅斯会议的发起人之一，并提出“人工智能”的概念1958年在MIT创建世界上第一个AI实验室1969年首位图灵奖获得者1975年首创框架理论1956年达特茅斯会议的发起人之一，并提出“人工智能”的概念1958年与明斯基一起创建世界上第一个人工智能实验室发明α－β剪枝算法1959年开发LISP语言开创逻辑程序研究，用于程序验证和自动程序设计1971年获得图灵奖机器学习发展历程（续）1950s初期 人工智能研究处于推理期 H.Simon、A.Newell、J.C.Shaw“逻辑理论家”（LogicTheorist）程序证明了《数学原理》52个定理，以及“通用问题求解”（GeneralProblemSolving）程序。MarnivLeeMinskyJohnMcCarthyAllenNewellHerbertA.Simon人工智能之父JohnCliffordShaw机器学习发展历程（续）ArthurSamuel机器学习之父不需要确定性编程就可以赋予机器某项技能的研究领域1950s初期 出现机器学习的相关研究 1952年，阿瑟·萨缪尔（ArthurSamuel）在IBM公司研制了一个西洋跳棋程序，这是人工智能下棋问题的由来。机器学习发展历程（续）激活函数用阶跃函数换成了连续型函数，用一个Quantizer函数（量化函数，类似AD采样）进行类别预测F.Rosenblatt1950s后期 出现基于神经网络的“连接主义”学习F.Rosenblatt提出感知机（Perceptron），处理线性分类问题，处理不了“异或”逻辑。B.Widrow提出自适应线性神经元（Adaline）网络。机器学习发展历程（续）时间段 机器学习理论 代表性成果1960s-1970s基于逻辑表示的“符号主义”（Symbolism）学习PatrickH.Winston的结构化概念学习系统，R.S.Michalski的基于逻辑的归纳学习系统，E.B.Hunt的概念学习系统以决策理论为基础的学习技术强化学习技术N.J.Nilson的“学习机器”知识工程专家系统统计学习理论的一些奠基性成果支持向量，VC维，结构风险最小化原则机器学习发展历程（续）1960s-1970s基于逻辑表示的“符号主义”（Symbolism）学习P.H.Winston

的结构化概念学习系统，R.S.Michalski的基于逻辑的归纳学习系统，E.B.Hunt的概念学习系统。RyszardS.MichalskiPatrickH.WinstonEarlB.Hunt机器学习发展历程（续）1960s-1970s决策理论为基础的学习技术强化学习技术知识工程N.J.Nilson的“学习机器”专家系统NilsJ.NilssonEdwardA.Feigenbaum知识工程之父RajReddyA*路径算法斯坦福国际研究院Shakey

项目的领导人，Shakey是首批具有视觉感知和轨迹规划的移动机器人之一。机器学习发展历程（续）1960s-1970s统计学习理论的一些奠基性成果支持向量、VC维、结构风险最小化原则。支持向量机（SVM）源自模式识别中广义肖像算法（generalizedportraitalgorithm）

1963年，前苏联学者VladimirN.Vapnik和AlexanderY.Lerner发表研究1964年，Vapnik和AlexeyY.Chervonenkis，硬边距的线性SVM随着模式识别中最大边距决策边界理论研究，出现基于松弛变量（slackvariable）的规划问题求解技术，和VC维（Vapnik-Chervonenkisdimension,VCdimension）Vapnik,V.N.andLerner,A.Y.Recognitionofpatternswithhelpofgeneralizedportraits.Avtomat.iTelemekh.1963,24(6):774-780.TheEnd机器学习发展历程主讲人：李侃1980s机器学习成为独立的学科领域，各种机器学习技术1980年，CMU

第一届机器学习研讨会《策略分析与信息系统》三期机器学习专辑1983年，R.S.Michalski、J.G.Carbonell和T.M.Mitchell《机器学习：一种人工智能途径》1986年，《MachineLearning》创刊1989年，《ArtificialIntelligence》机器学习专辑1990年，《机器学习：风范与方法》MIT出版社机器学习发展历程（续）机械学习（死记硬背式学习）示教学习（从指令中学习）

类比学习（通过观察和发现学习）归纳学习（从样例中学习百花初绽1979年，J.R.Quinlan，ID3算法原型1986年，

J.R.Quinlan，ID3算法，决策树学习理论1986年，Schlimmer和Fisher，引入节点缓冲区，ID4算法1993年，Quinlan，C4.5算法ID3

的另一个分支：分类回归决策树算法(ClassificationRegressionTree，CART)，

主要用于预测。机器学习发展历程（续）1980s-1990s从样例中学习：（1）符号主义学习

（2）基于逻辑的学习决策树（decisiontree），覆盖分类和回归两个领域

归纳逻辑程序设计（InductiveLogicProgramming,ILP）具有很强的知识表示能力，但会导致学习过程面临的假设空间太大，复杂度高，因此，问题规模稍大就难以有效地学习。机器学习发展历程（续）1980s-1990s从样例中学习：（1）符号主义学习

（2）基于逻辑的学习决策树（decisiontree），覆盖分类和回归两个领域

归纳逻辑程序设计（InductiveLogicProgramming,ILP）具有很强的知识表示能力，但会导致学习过程面临的假设空间太大，复杂度高，因此，问题规模稍大就难以有效地学习。归纳逻辑程序设计：使用一阶谓词逻辑进行知识表示，通过修改和扩充逻辑表达式完成对数据的归纳。FOIL(FirstOrderInductiveLearner)[Quinlan,1990]D.E.Rumelhart,G.E.Hinton,andR.J.Williams,“Learningrepresentationsbyback-propagatingerrors,”Nature,1986,323(6088):533–536.机器学习发展历程（续）1980s-1990s从样例中学习：基于神经网络的连接主义学习1983年，J.J.Hopfield利用神经网络求解“流动推销员问题”这个NP难题。1986年，D.E.Rumelhart等人重新发明了BP算法。JohnJ.HopfieldRonaldJ.WilliamsDavid.E.RumelhartGeoffreyHinton机器学习发展历程（续）时间段 机器学习理论 代表性成果1990s中期统计学习支持向量机，基于核的学习方法21世纪初----深度学习深度卷积神经网络、循环神经网络、生成对抗网络、Seq2seq、Transformer……统计学习理论（StatisticalLearningTheory），也称VC理论（VapnikChervonenkistheory）机器学习发展历程（续）1990s中期统计学习支持向量机，基于核的学习方法VladimirNaumovichVapnikAlexeyChervonenkis1992年，BernhardE.Boser、IsabelleM.Guyon和Vapnik，核方法的非线性SVM1995年，CorinnaCortes和Vapnik，软边距的非线性SVM，并将其应用于手写字符识别问题机器学习发展历程（续）21世纪初----深度学习深度卷积神经网络、循环神经网络、生成对抗网络、Seq2seq、Transformer……2018年图灵奖序列的概率建模高维词嵌入与注意力机制生成对抗网络反向传播玻尔兹曼机对卷积神经网络的修正提出卷积神经网络改进反向传播算法拓宽神经网络的视角序列的概率建模高维词嵌入与注意力机制生成对抗网络机器学习发展历程（续）21世纪初----深度学习深度卷积神经网络、循环神经网络、生成对抗网络、Seq2seq、Transformer……2018年图灵奖反向传播玻尔兹曼机对卷积神经网络的修正提出卷积神经网络改进反向传播算法拓宽神经网络的视角序列的概率建模高维词嵌入与注意力机制生成对抗网络机器学习发展历程（续）21世纪初----深度学习深度卷积神经网络、循环神经网络、生成对抗网络、Seq2seq、Transformer……2018年图灵奖反向传播玻尔兹曼机对卷积神经网络的修正提出卷积神经网络改进反向传播算法拓宽神经网络的视角序列的概率建模高维词嵌入与注意力机制生成对抗网络机器学习发展历程（续）21世纪初----深度学习深度卷积神经网络、循环神经网络、生成对抗网络、Seq2seq、Transformer……2018年图灵奖反向传播玻尔兹曼机对卷积神经网络的修正提出卷积神经网络改进反向传播算法拓宽神经网络的视角TheEnd机器学习分类与性能度量主讲人：李侃机器学习分类机器学习分类（续）机器学习分类（续）机器学习分类（续）数据集：训练集（trainingset）、验证集（validationset）和测试集（testset）训练集：用来训练模型算法，通过设置分类器参数，训练分类模型。验证集：训练集训练出的多个模型对验证集数据进行预测，并记录模型准确率。

选出效果最佳的模型所对应的参数，即用来调整模型参数。测试集：用来测试模型的性能和分类能力。机器学习分类（续）

当模型无需人为设定超参数，所有参数都通过学习得到，则不需要验证集。验证集适用多个不同的超参数训练多个模型，通过验证集，选择最好的模型及其相应的超参数。

分类（classification）：输出是离散型变量(如:+1、-1)，是一种定性输出。

(预测明天天气是阴、晴还是雨)

回归(regression)

：输出是连续型变量，是一种定量输出。(预测明天的温度是多少度)。机器学习分类（续）监督学习（supervisedlearning），有导师学习：分类和回归从给定的训练数据集中学习出一个函数（模型参数），当输入新数据时，可以根据这个函数预测结果。输入数据没有标签，样本数据类别未知，需要根据样本间的相似性对样本集进行划分使类内差距最小化，类间差距最大化。基于概率密度函数估计的直接方法基于样本间相似性度量的聚类方法机器学习分类（续）无监督学习（unsupervisedlearning），无导师学习：聚类和维度约简用于描述和解决智能体（agent）在与环境的交互过程中通过学习策略以达成回报最大化或实现特定目标的问题。机器学习的范式和方法论之一。机器学习分类（续）强化学习（reinforcementlearning），再励学习、评价学习或增强学习不同于监督学习和无监督学习，强化学习不要求预先给定任何数据，而是通过接收环境对动作的奖励（反馈）获得学习信息并更新模型参数。绪论误差误差（error）指的是模型输出与真值（labels）的偏离程度，通常定义一个损失函数（lossfunction）来衡量误差的大小。

在训练集上的产生误差称为经验误差（empiricalerror）或者训练误差经验误差的大小反映了模型在训练数据上拟合效果的好坏模型在未知样本上的误差称为泛化误差（generalizationerror），通常将测试误差作为泛化误差的近似值泛化误差用于衡量训练好的模型对未知数据的预测能力绪论过拟合与欠拟合模型在训练样本中表现得过于优越，导致在验证数据集以及测试数据集中表现不佳。

指模型在训练和预测时表现得都不好。过拟合（overfitting）欠拟合（under-fitting）绪论评估方法常见方法：留出法（hold-out）交叉验证法（cross

validation）自助法（bootstrap）评估方法留出法ST数据集D训练集S测试集T已有的数据集分为两个互斥的部分

保证数据分布一致

测试集比例一般保持在1/3～1/5评估方法交叉验证法DN1N2N3N4N5Nk…训练测试N1N2N3Nk-1…Nk模型1N1N2Nk-2…Nk-1模型2Nk………………N2N3Nk-1…N1模型mNk求平均m个样本互斥保证数据分布一致

k=m,留一法评估方法自助法数据集D中包含m个样本，对数据集D进行m次有放回采样，采样到的数据构成数据集D′，将D′作为训练集，未出现在D′中的数据作为测试集

。

样本不出现在D′中的概率为：对m取极限数据集D中有大约36.8%的数据不会出现在D′中适用于小数据集改变了数据分布,易引起估计偏差不会减小训练集规模功能：主要用于比较分类结果和实例的真实信息性能度量分类以二分类（正、负）为例：真正(TP)：模型预测为正的正样本假正(FP)：模型预测为正的负样本假负(FN)：模型预测为负的正样本真负(TN)：模型预测为负的负样本混淆矩阵（confusionmatrix），误差矩阵：正确预测的正反例数

/总数性能度量（续）（续）分类准确率（accuracy）

：正确预测的正例数/预测正例总数精确率（precision）

：正确预测的正例数

/实际正例总数召回率（Recall）

：正确预测的正反例数

/总数性能度量（续）（续）分类准确率（accuracy）

：正确预测的正例数/预测正例总数精确率（precision）

：正确预测的正例数

/实际正例总数召回率（Recall）

：正确预测的正反例数

/总数性能度量（续）（续）分类准确率（accuracy）

：正确预测的正例数/预测正例总数精确率（precision）

：正确预测的正例数

/实际正例总数召回率（Recall）

：precision和recall的调和值性能度量（续）（续）分类F-score

β=1时，

F1-score或

F1-Measure，精确率和召回率都很重要，权重相同；β<1时，精确率更重要；β>1时，召回率更重要。：precision和recall的调和平均评估指标F1-score

（receiveroperatingcharacteristiccurve）性能度量（续）分类ROC曲线根据分类结果计算得到ROC空间中相应的点，连接这些点形成ROC曲线真正率(TPR)：预测为正的正样本数/正样本实际数假正率(FPR)：预测为正的负样本数/负样本实际数TPR=TP/(TP+FN)FPR=FP/(FP+TN)靠近左上角的ROC曲所代表的分类器准确性最高（areaundercurve）性能度量（续）分类AUCAUC=1：100%完美识别正负类，不管阈值怎么设定都能得出完美预测；0.5<AUC<1：优于随机猜测。这个分类器（模型）妥善设定阈值的话，可能有预测价值；AUC=0.5：跟随机猜测一样（例：随机丢N次硬币，正反面的概率为50%），模型无预测价值；AUC<0.5：比随机猜测还差，不存在AUC<0.5的情况：ROC曲线下的面积(ROC的积分)AUC=１AUC＝０.８AUC＝０.５（precisionrecallcurve）性能度量（续）分类PR：precision

对recall的曲线PR曲线与ROC曲线相同点：采用TPR

(Recall)，用AUC来衡量分类器效果；不同点：ROC曲线使用了FPR，PR曲线使用了precision在同一测试集，上面的曲线比下面的曲线好（绿线比红线好）；光滑曲线与不光滑曲线好：L1范数损失（L1-normloss）性能度量（续）（续）回归平均绝对误差（meanabsoluteerror，MAE）：L2范数损失（L2-normloss）平均平方误差（meansquarederror，MSE）均方根误差（RMSE）：

：L1范数损失（L1-normloss）性能度量（续）（续）回归平均绝对误差（meanabsoluteerror，MAE）：L2范数损失（L2-normloss）平均平方误差（meansquarederror，MSE）均方根误差（RMSE）：

：L1范数损失（L1-normloss）性能度量（续）（续）回归平均绝对误差（meanabsoluteerror，MAE）：L2范数损失（L2-normloss）平均平方误差（meansquarederror，MSE）均方根误差（RMSE）：

性能度量（续）（续）回归解释变异（explainedvariation)决定系数（coefficientofdetermination）

给定数据中的变异能被数学模型所解释的部分通常用方差来量化变异回归关系已经解释的y值变异在其总变异中所占的比率性能度量（续）聚类兰德指数（randindex)给定实际类别信息C，假设K是聚类结果，a表示在C与K中都是同类别的元素对数，b表示在C与K中都是不同类别的元素对数

RI取值范围为[0,1]调整兰德指数（adjustedrandindex)

ARI取值范围为[−1,1]性能度量（续）聚类互信息（mutualinformation,MI)假设U与V是对N个样本标签的分布情况，标准化后的互信息（

normalizedmutualinformation,NMI)调整互信息（adjustedmutualinformation,AMI)用来衡量两个数据分布的吻合程度。其中MI和NMI取值范围是[0,1]，AMI取值范围是[-1，1]性能度量（续）聚类

轮廓系数

（silhouettecoefficient)对于单个样本，设a是与它同类别中其他样本的平均距离，b是与它距离最近不同类别中样本的平均距离

轮廓系数取值范围是[−1,1]适用于实际类别信息未知的情况TheEnd期望最大化算法及其应用EM算法背景

当拥有缺失数据的时候，可以迭代地做参数估计

两个关键步骤:

期望步

[Expectation(E)]最大化步[Maximization(M)]

可以解决大量的实际问题

上世纪50年代就被提出，但形式化是由Dempster,LairdandRubin在1977年完成

更多的材料，可以参考McLachlan&Krishnanbook1997.期望最大化算法[ExpectationMaximization(EM)]EM的应用(1)概率隐语义分析[ProbabilisticLatentSemanticAnalysis(pLSA)]文本处理领域的常见技术之一P(w,d)P(w|z)P(z|d)ZWDZDWEM的应用(2)01-2-1-4-34523数据:模型:参数:目标:建模具有2个组件的高斯混合模型让

固定即仅仅估计xP(x|)这里，启发式的例子似然是参数

的一个函数

概率是随机变量x的一个函数似然函数想象模型去产生数据需要对每个数据点引入标签z标签被叫做隐变量，也叫做未观察或者缺失变量

c01-2-1-4-34523可以极大地简化问题:

如果我们知道标签，我们能够解耦各个组件，使得可以为每个组件单独估计参数概率模型E-步: 用当前的参数计算一个数据点标签的分布；M-步: 用当前标签分布的猜测去升级参数。EEMMEEM的直觉TheEnd理论Jensen不等式Jensen不等式定理：假设f是一个凸函数，X是一个随机变量然后：

E[f(X)]≥f(EX)进一步地，如果f是严格凸函数，然后E[f(X)]

=

f(EX)成立的条件是

P(X

=

E[X])

=

1,即X是一个常数理论准备证明：对n采用归纳法，当

n=1时，α1=1，因此

f(α1x1)≤

α1f(x1)，为真证明递归步:代数可知.证明（cont.）递归步:凸函数的性质.证明（cont.）递归步:归纳法.证明（cont.）递归步:

得证证明（cont.）TheEndEM算法推导似然按照下式进行估计：用最大似然估计非常难以进行参数估计，可以尝试优化其下界（lower-bound

）EM算法EM算法EM算法可以总结为:

EM算法TheEndEM算法的收敛性要证明:

然后,

收敛性EM算法例子最大似然例子-1期望最大化例子-1例子-2例子-2例子-2例子-2例子-2实践初始化

数据的平均值+随机

K-Means终止条件

最大迭代次数

log-likelihood变化情况

参数变化情况（parameterchange）收敛

局部最大（Localmaxima）

模拟退火方法（Annealedmethods(DAEM)）

生灭过程（Birth/deathprocess(SMEM)）数值问题

在协方差矩阵中注入噪音，可以阻止崩溃

单点可能给无穷似然组件的数量

开放问题

贝叶斯方法实践问题局部最优确定模型的结构

组件的个数

图结构找到全局最优解总是有很好的升级形式

优化只在E/M步内完成避免计算问题

计算期望时的采样方法EM不能与其它方法的比较

没有设置优化步长的问题

直接在参数空间中工作，因此参数的约束直接就满足

一般训练速度很快使用EM的原因：为什么不用标准的优化方法？EM

part,

/notes/cs229-notes8.pdf<TheEMalgorithmandextensions>,

BookbyGeoffreyJMcLachlanHMM

part,di.ubi.pt/~jpaulo/competence/tutorials/hmm-tutorial-1.pdfGMM

part,

/~cga/ai-course/gmm.pdf/~tibs/stat315a/LECTURES/em.pdfNotes:

Some

Slides

from

AndrewW.Moore参考资料TheEndD主题建模（Topic

Modeling）主题建模的背景主题建模的背景主题建模的背景怎么办?

主题建模（Topic

Modeling）主题建模的背景大数据时代主题建模的背景文档集合主题发展历程LSI/LSApLSALDA198819992003S-LDAMM-LDALLDAHDPPAM…………主题建模的背景主题建模研究趋势quickly！主题建模的背景什么是主题？文档集合主题什么是主题?字符串概率分布人类机器容易困难困难容易计算机0.440.220.110.070.060.050.0450.0430.0420.0410.0360.0290.0180.0130.009什么是主题？主题的定义什么是主题建模？DocsTopicsHypothesisH1H2?AssumethatatopicisaprobabilityoverwordsWhatistopics？Computer0.440.220.110.070.060.050.0450.0430.0420.0410.0360.0290.0180.0130.009什么是主题建模？主题建模基本构件北大信科环境坦克GDP…一个文档北大环保军事经济…主题建模（TopicModeling）TopicsWords0.30.10.50.050.20.10.40.10.15主题分布（TopicalDistribution）词分布（WordDistribution）什么是主题建模？主题建模的核心结果两种观点看待

主题建模两种观点文档表示（Documentrepresentation）写作模拟（Simulationofwriting）主题建模的两种观点文档表示（Documentrepresentation）北大信科环境坦克GDP…Doc北大信科环境坦克GDP…Doc北大环保军事经济…VSMTopicmodelingTopicsWordsWords主题建模的两种观点如何去写一篇文章？GeneNerveLifeComputerTopicsDocsWriteChoosetopics主题建模的两种观点gene0.04dna0.02genetic0.01…life0.04evolve0.02organism0.01…brain0.04neuron0.02nerve0.01…data0.04number0.02computer0.01…GeneNerveLifeComp2.Choosetopics0.30.10.20.4PropLearned1.Docs主题建模的两种观点写作模拟主题建模的关键关键:在一个文档中含有多少个主题？主题建模的关键pLSA/pLSI(SIGIR’99)主题建模的关键LDA(JMLR’03)主题建模的关键Conceptmodel(CIKM’08)主题建模的关键Conceptmodel(CIKM’08)主题建模的关键Authormodel(SIGKDD’04)主题建模的关键LabeledLDA(EMNLP’09)主题建模的关键HLDA(nips’04)主题建模的关键PAM(ICML’06)主题建模的关键TheEndLDA的基本结构LDA的基本结构M*K的矩阵K*V的矩阵隐狄利克雷分配模型（Latent

Dirichlet

Allocation，LDA）LDA的基本结构生成过程（generative

process）TheEnd吉布斯采样方法Gibbs采样算法，就是用条件分布的抽样来替代全概率分布的抽样。Gibbs采样算法的步骤：1.给定一个初始样本X0={x10,x20,...,xn0}2.已知一个样本Xi={x1i,x2i,...,xni}，对于x1i+1进行抽样，x1i+1~p(x1|Xi-1)3.对于x2i+1进行抽样，x2i+1~p(x2|x1i+1,x3i,...xni)................................................................4.对于xni+1进行抽样，xni+1~p(xn|x1i+1,x2i+1,...x(n-1)i+1)5.步骤2~4可以得到X的一个样本，然后重复步骤2~4可以不断地得到X的样本。吉布斯采样（GibbsSampling）LDA的参数学习P(θ,Z,φ,W;ɑ,β)

->

P(Z,W;ɑ,β)

->

P(Z;ɑ,β)

->

P(Z(m,n);Z-(m,n)ɑ,β)Using

Gibbs

SamplerLDA的参数学习参数推断（Inference）LDA的参数学习通过模型的描述，可知模型的全概率分布如下：其中，黑体变量表示变量的向量形式。首先，𝝋和𝝷需要被积分消除掉：参数推断（Inference）vLDA的参数学习所有的相互之间是独立的，而且对ϕ也是独立的，因此，我们可以单独地处理每个𝛳和每个ϕ。现在，我们仅仅聚焦在只有𝛳的部分：参数推断（Inference）LDA的参数学习我们进一步聚焦在只有一个𝛳的部分：实际上，它是模型在第j个文档的隐藏部分。现在，我们把每个概率分布的精确表达式写出来，就得到了下面的表达式：参数推断（Inference）LDA的参数学习假设是在第j个文档中被赋予第i个主题的第r个词总个数；因此，是三维的。如果这三维里面的任何一维没有被指定一个特定值，用()的形式表示。例如

表示第j个文档中被赋予第i个主题的所有词的数量。因此，上述表达式的最右边可以被写为：参数推断（Inference）LDA的参数学习因此，对𝛳j积分可以变为：清楚地，在这个积分里面的等式与狄利克雷分布的形式一样，而参数推断（Inference）LDA的参数学习因此，参数推断（Inference）LDA的参数学习现在，我们对𝝋部分进行处理。实际上，𝝋部分的处理与𝝷部分是非常类似的，因此我们将推导结果直接列出参数推断（Inference）LDA的参数学习因此，在将ϕ和𝛳都通过积分消除之后得到的最终表达式，如下：这里，吉布斯采样的目标是要去近似分布P(Z|W;

𝛼,𝛽)。因为P(W;𝛼,𝛽)对任何的Z都是不变的，所以吉布斯采样的等式可以等价于P(Z,

W;𝛼,𝛽)。关键在于要推导出下列条件概率：参数推断（Inference）LDA的参数学习这里，Z(m,n)表示在第m个文档中的第n个词对应的隐变量。进一步，我们假设这个词是词表里面的第v个词。

Z-(m,n)

表示除了Z(m,n)之外的所有Z。注意：吉布斯采样仅仅需要采样Z(m,n)的一个值，而不需要精确解本质上，只需要概率之间的比率就可以达到求取Z(m,n)的目标，因此上述公式可以简化为：参数推断（Inference）LDA的参数学习参数推断（Inference）LDA的参数学习最终，假设与具有同样的意义，除了Z(m,n)被排除在外。上述的公式能通过伽玛函数的性质进一步简化。参数推断（Inference）LDA的参数学习LDA的参数学习参数推断（Inference）TheEnd支持向量机基于统计学习理论的方法

定义最优超平面，并把寻找最优超平面归结为求解一个凸规划问题支持向量机（supportvectormachine，SVM）基本原理支持向量机能较好地解决小样本、非线性和高维数据、局部极小点等实际问题。H为线性超平面，H1、H2分别为过各类中离超平面最近的样本且平行于超平面

分类间隔（margin）：

|

H1H2

|。最优超平面

：将两类数据正确分开，并且使分类间隔最大。二分类支持向量机（supportvectormachine，SVM）基本原理

能将两类样本正确分开的超平面有无数多个。如何求得

最优超平面

？支持向量机（supportvectormachine，SVM）超平面

线性超平面非线性超平面线性可分情况线性不可分情况线性不可分情况线性最优超平面

线性支持向量机非线性最优超平面非线性支持向量机

支持向量机数据线性可分数据线性不可分核方法基于Mercer

核展开定理，通过用内积函数定义的非线性变换将输入空间映射到高维特征空间（Hilbert空间），在这个高维特征空间中寻找输入变量和输出变量之间的关系。

升维线性化线性可分情况设线性可分的训练样本线性支持向量机

分类超平面：

两类样本：

超平面H1到原点的距离：

超平面H2到原点的距离：分类间隔｜

H1H2｜=

约束的二次规划问题：

构造拉格朗日函数求解H1、H2上的训练样本点称作支持向量（supportvector，SV）线性支持向量机构造Lagrange函数：线性支持向量机满足约束：其中，D是阶对称矩阵，。为原问题中，与每个约束条件式对应的Lagrange乘子

最优分类函数：利用Lagrange优化方法，将其转化为对偶问题，即最大化线性不可分情况引入非负松弛变量约束方程：线性支持向量机

约束的二次规划问题：

构造拉格朗日函数求解

利用Lagrange优化方法，将转化为对偶问题，即最大化线性支持向量机满足约束：其中。KKT（Karush-KuhnTucker）条件：C为大于零的平衡常数TheEnd非线性支持向量机主讲人：李侃基于Mercer

核展开定理，通过用内积函数定义的非线性变换，将输入空间映射到高维特征空间（Hilbert空间），在这个高维空间中寻找输入变量和输出变量之间的关系。非线性支持向量机非线性支持向量机非线性超平面核方法

核函数

已知映射函数，通过内积求得核函数K，不用构造映射函数能否直接判断一个给定的函数是否是核函数K？或者说K满足什么条件才是核函数？核函数正定核的充要条件：设是对称函数，则K（x,z）为正定核函数的充要条件是对任意对应的Gram矩阵是半正定矩阵。Mercer定理可以得到Mercer核，正定核比Mercer更具一般性常用的核函数（1）多项式形式的核函数此时得到的支持向量机是一个d阶多项式分类器。核函数常用的核函数（2）径向基函数形式的核函数此时得到的支持向量机是一种径向基函数分类器。它与传统径向基核函数（RBF）方法的基本区别：每一个核函数的中心对应于一个支持向量，它们以及输出权值是由算法自动确定。核函数常用的核函数（3）Sigmoid函数形式的核函数得到的支持向量机实现的两层的多层感知器神经网络网络的权值、网络的隐层节点数目由算法自动确定。核函数常用的核函数（4）点积形式的核函数此时得到的支持向量机是线性的分类器。核函数常用的核函数判断一个支持向量机分类器性能的关键指标有两个：

学习能力

推广能力核函数常用的核函数学习能力：分类器从训练数据中建立正确的分类模型的能力推广能力：指这个模型对未知数据进行正确预测的能力。推广能力的强弱更能反映分类器性能的好坏，因为设计分类器的目的就是对未知数据进行分类。核函数非线性支持向量机

非线性映射把数据从输入空间映射到高维特征空间在高维特征空间中进行线性分类，映回到原空间后就成了输入空间中的非线性分类为避免高维空间的复杂计算，支持向量机采用核函数代替高维空间非线性支持向量机约束的二次规划问题：

构造拉格朗日函数求解：

优化问题的对偶形式：非线性支持向量机

该优化问题解的特点是大部分将为零，其中不为零的解对应的样本为支持向量

。TheEnd一分类/多分类支持向量机主讲人：李侃优化问题：一分类支持向量机(one-classsupportvectormachine，1-SVM)通过超球体来实现一类分类异常值检测实际上可视为一类分类问题设一个正类样本集为:找到一个以a为中心，以R为半径的包含样本点的最小超球

对偶形式：一分类支持向量机根据KKT条件，对应于样本满足：其中：给定新数据z:若，则z为正常点，否则z为异常点直接法：直接修改目标函数，将多个分类面的参数求解合并到一个最优化问题中，通过求解该最优化问题“一次性”实现多类分类。特点：简单，但计算复杂度较高，实现较困难，只适合小型问题。间接法：主要是通过组合多个二分类器来实现多分类器的构造，如：一对多（one-against-all）和一对一（one-against-one）方法。多分类支持向量机一对多法：训练时依次把某个类别的样本归为一类，其它样本归为另一类，这样k个类别的样本构造了k个SVM。分类时将未知样本分类为具有最大分类函数值的那类。多分类支持向量机优点训练k个分类器，个数较少，其分类速度相对较快缺点训练速度会随着训练样本的数量的增加而急剧减慢；样本不对称：负类样本的数据要远远大于正类样本的数据；

新的类别加入，需要对所有的模型重新训练从“一对多”的方法衍生出基于决策树的分类。解决不对称：引入不同的惩罚因子，对样本点较少的正类采用较大的惩罚因子C。一对一法：在任意两类样本之间设计一个SVM，因此k个类别的样本需要设计k(k-1)/2个SVM。当对一个未知样本进行分类时，得票最多的类别即为该未知样本的类别。多分类支持向量机当类别很多的时候，模型的个数是k(k-1)/2，代价相当大。从“一对一”的方式出发，有向无环图（directedacyclicgraph，DAG）分类方法多分类支持向量机在高维特征空间中对每一类样本求出一个超球体中心，计算待测试样本到每类中心的距离，根据最小距离来判断该点所属的类基于一分类思想的多分类支持向量机方法受到基于一类分类思想的启发训练样本为

第s类训练样本各个类别为多分类支持向量机优化问题：对偶形式：借助核映射思想多分类支持向量机根据KKT条件，对应于

样本满足：给定待识别样本z，计算它到各中心点的距离：找出最小的

，

则z属于第k类。TheEnd聚类分析数据相似性度量聚类分析的目标：使簇内数据之间具有高的相似性，不同簇数据之间具有高的差异性度量数据间的相似性数据相似性度量相似性度量方法欧氏距离切比雪夫距离闵可夫斯基距离标准化欧氏距离余弦距离马氏距离曼哈顿距离海明距离杰卡德距离相关距离信息熵基于核函数的度量相似性度量方法欧氏距离两个n维向量和之间的欧式距离（euclideandistance)为：

或向量运算：

相似性度量方法标准化欧氏距离根据数据各维分量的分布不同将各个分量都“标准化”到均值、方差相等。两个n维向量和之间的标准化欧氏距离为：

方差的倒数可以看作是一种权重，标准化欧氏距离本质上是一种加权欧氏距离。相似性度量方法曼哈顿距离两个n维向量和之间的曼哈顿距离为：

L1-距离、城市区块距离(cityblockdistance)在欧氏空间的直角坐标系上两点所形成的线段对轴产生的投影的距离总和。相似性度量方法切比雪夫距离两个n维向量和之间的切比雪夫距离为：

该公式等价为：

该等价性可以由放缩法和夹逼定理（squeezetheorem）证得由一致范数（uniformnorm）（或称为上确界范数）所衍生的度量，也是超凸度量（injectivemetricspace）的一种。

相似性度量方法闵可夫斯基距离两个n维向量和之间的闵可夫斯基距离：

当p分别取1，2，3时，会有什么样的效果呢？

相似性度量方法闵可夫斯基距离举例二维样本空间（身高，体重）中的三个样本：a(180,50)，b(190,50)，c(180,60)，其中a与b之间的闵氏距离（无论是曼哈顿距离、欧氏距离或切比雪夫距离）等于a与c之间的闵氏距离这意味什么？将各个分量的量纲，也就是“单位”当作相同看待没有考虑各个分量的分布（如期望、方差等）可能不同缺点相似性度量方法余弦距离向量的几何意义不只包含长度也包含方向，余弦距离（cosinedistance）是度量两个向量方向差异的一种方法。两个n维向量

和

之间的夹角余弦度量：

即：

相似性度量方法马氏距离马氏距离(mahalanobisdistance)是基于样本分布的一种距离，它是规范化的主成分空间中的欧氏距离。何谓规范化？规范化的主成分空间就是利用主成分分析对一些数据进行主成分分解，再对所有主成分分解轴做归一化，形成新的坐标轴，由这些坐标轴组成的空间就是规范化的主成分空间。相似性度量方法马氏距离设有M个向量，协方差矩阵记为S，均值记为向量μ

，则样本向量X到μ

的马氏距离：

向量Xi与Xj之间的马氏距离：若协方差矩阵是单位矩阵（各个样本向量之间独立同分布），则Xi与Xj之间的马氏距离等于它们的欧氏距离：若协方差矩阵是对角矩阵呢？标准化欧氏距离量纲无关，排除变量之间的相关性的干扰；马氏距离的计算是建立在总体样本的基础上；计算马氏距离过程中，要求总体样本数大于样本的维数。特点：相似性度量方法海明距离两个等长二进制串S1和S2将其中一个变换为另一个所需要的最小变换次数。例如：字符串“1111”与“1001”之间的汉明距离为2相似性度量方法杰卡德距离杰卡德相似系数(Jaccardsimilaritycoefficient)：两个集合A

和B的交集元素在A、B

的并集中所占的比例，称为两个集合的杰卡德相似系数，用符号J(A,B)表示：杰卡德距离(JaccardDistance)：与杰卡德相似系数相反，用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度：相似性度量方法

相关距离相关系数：衡量随机变量X与Y

相关程度的一种方法，相关系数的取值范围是[-1,1]。相关系数的绝对值越大，则表明X

与Y

相关度越高。当X

与Y

线性相关时，相关系数取值为1（正线性相关）或-1（负线性相关）相关距离(correlationdistance)：相似性度量方法信息熵以上的距离度量方法度量皆为两个样本（向量）之间的距离信息熵(informationentropy)描述的是整个系统内部样本之间的一个距离，或者称之为系统内样本分布的集中程度（一致程度）、分散程度、混乱程度（不一致程度）。分布越分散信息熵越大分布越有序信息熵越小相似性度量方法信息熵计算给定的信息熵：其中，n为样本集X的分类数；

为X中第

i

类元素出现的概率。

相似性度量方法基于核函数的度量把原始样本空间中线性不可分的数据点采用核函数映射到高维空间中使其线性可分的一种度量方法。距离函数需满足：d(x,x)=0，即自身的距离为0d(x,y)>=0，即距离要非负；对称性，即d(x,y)=d(y,x)三角形法则(两个之和大于第三边）即d(x,k)+d(k,y)>=d(x,y)经典聚类算法经典聚类算法分类聚类方法往往学术界对聚类算法并没有一个公认的分类方法某一聚类方法会具有几种类别的特征聚类算法：划分方法层次方法基于密度方法基于网格方法基于模型方法经典聚类算法划分方法

典型方法：K-means及其变种、K-中心点、CLARA、CLARANS等经典聚类算法层次聚类树的建立策略：

自底向上的策略，把小的类别逐渐合并为大的类别，这种方法称为凝聚；

自顶向下的策略，把大的类别逐渐分裂为小的类别，这种方法称为分裂层次聚类方法将数据对象建立一棵聚类树。经典聚类算法层次聚类经典方法：BRICH方法、ROCK方法和Chameleon方法在层次聚类算法的实际应用中，聚类通常终止于某个预先设定的条件，比如簇的数目达到某个预定的值，或者每个簇的直径都在某个阈值之内。簇间距离度量方法：最小距离（最近邻聚类算法）最大距离（最远邻聚类算法）均值距离平均距离是簇

的均值是簇

中对象个数经典聚类算法基于密度的聚类基于密度的方法将簇看作数据空间中被低密度区域分割开的稠密的对象区域，有时也将这种低密度区域看作噪声。经典方法：DBSCAN、OPTICS、DENCLUE等基于密度的聚类DBSCAN具有噪声的基于密度的聚类应用算法定义：

q基于密度的聚类DBSCAN

密度可达是直接密度可达的传递闭包，它是非对称的，只有核心对象之间互相密度可达。密度相连则是一种对称的关系。基于密度的簇，是基于密度可达性的最大的密度相连对象的集合，不包含在任何簇中的对象被认为是噪声基于密度的聚类DBSCAN算法：1.检查数据集中的每个点的𝜺邻域

3.当没有新的点可以添加到任何簇时，聚类过程结束

计算复杂度为

，在使用空间索引的数据库中计算复杂度可降为。在参数𝜺和MinPts

设置恰当的情况下，DBSCAN算法可有效地找到任意形状的簇

对参数非常敏感真实的高维数据常具有非常倾斜的分布，全局密度参数不能刻画其内在的聚类结构评价：经典聚类算法基于网格的方法它采用一个多分辨率的网格数据结构，将空间量化为有限数目的单元，这些单元形成了网格结构，所有的聚类操作都在网格上进行。经典方法：STING和WaveCluster等特点：直接聚类的对象是空间，而不是数据对象优点：处理速度快经典聚类算法基于模型的方法试图优化给定的数据和某些数学模型之间的拟合，即假设数据是根据潜在的概率分布生成的；基于模型的方法试图找到其背后的模型，并使用其概率分布特性进行聚类。经典方法：期望最大化方法、概念聚类、基于神经网络等TheEndK-means、K中心点方法及其改进方法主讲人：李侃K-means、K中心点方法及其改进方法K-means以簇数目k为输入参数，把n个对象划分为k个簇，使得簇内的相似度高，而簇间的相似度低。簇作为运算对象参与度量时，使用簇中对象的均值代表簇。随机地选择k个对象，每个对象代表一个簇的初始均值。对于剩余的每个对象，根据其与每个簇均值的距离，将它分配到最相似的簇。计算每个簇的新均值。这个过程不断重复，直到簇稳定不再变化。这里的不再变化，实质上是准则函数的收敛。K-means、K中心点方法及其改进方法K-meansK-means算法所选择的准则函数是平方误差函数：其中，p是空间中的点，表示给定对象；是簇的均值。K-means、K中心点方法及其改进方法K-means输入：n个对象的数据集D，簇数目k输出：k个簇1.从D中随机选择k个对象作为初始簇中心；2.将每个对象分配到中心与其最近的簇；3.重新计算簇的均值，使用新的均值作为每个簇的中心；4.重复步骤2、3直到所有簇中的对象不再变化算法K-means、K中心点方法及其改进方法K-meansK-means算法是一种期望最大化（expectation-maximization，EM）算法：

E步：每个对象分配到一个簇中。

M步：重新计算簇中心参数。K-means算法的计算复杂度是，其中n是数据对象的总数，k是簇的个数，t是迭代的次数，通常，K-means、K中心点方法及其改进方法K-means局限性算法可能终止于局部最优解算法只有当簇均值可求或者定义可求时才能使用簇的数目k必须事先给定，而在一些实际应用中是k是很难事先知道算法不适合发现非凸形状的簇，或者大小差别很大的簇算法对噪声和离群点数据敏感K-means、K中心点方法及其改进方法K中心点K中心点算法的过程：随机选择初始中心点在迭代过程中，只要能够提高聚类结果质量，就用非中心点替换中心点聚类结果的质量由代价函数评估，该函数度量对象与其簇的中心点之间的平均相异度。该算法也依靠迭代，最终使得所有点或者为簇中心或者属于离它最近的簇。K-means、K中心点方法及其改进方法K中心点用表示正在被考察的非中心点、表示中心点，p表示每一个非中心点对象，替换规则如下：p当前隶属于中心点。如果被所代替作为中心点，

p离最近，，那么p被重新分配给。

p离最近，那么p被重新分配给。p当前隶属于中心点，。如果被代替作为一个中心点，p离最近，那么对象的隶属不发生变化。

p离最近，那么p被重新分配给。规则一：规则二：K-means、K中心点方法及其改进方法K中心点K中心点算法采用的评判准则是绝对误差标准，定义：其中，p是空间中的点，代表簇中的一个给定对象；

是代表簇的对象。K-means、K中心点方法及其改进方法K中心点K中心点算法也有许多变种，其中最早提出的算法：围绕中心点的划分（PartitionAroundMedoids,PAM）算法K中心点输入：n个对象的数据集D，簇数目k输出：k个簇1.从D中随机选择k个对象作为初始的簇的中心点；2.将每个剩余对象分配到最近的中心点所对应的簇中；3.随机选择一个非中心点对象；4.计算用交换中心点的总代价S；5.如果S小于0，则用替换，形成新的k个中心点集；6.重复步骤2到步骤5，直到聚类稳定K-means、K中心点方法及其改进方法K中心点K中心点算法使用位于簇“中心”的实际点代表簇，所以它不易受到离群点之类的极端值的影响；当数据对象中存在噪声和离群点时，K中心点算法较之于K-means算法具有更高的鲁棒性；K中心点算法同K-means算法一样，需要事先由用户给出簇的数目k。K中心点K-means、K中心点方法及其改进方法核K-meansK-means算法中簇之间的分割边界是线性的，但它不适用非凸簇的数据。采用核（kernel）方法应用于K-means中，即：核K-means（kernelK-means）算法，通过核方法来提取簇之间的非线性边界。主要思想将输入空间中的数据点映射到某个高维特征空间中的点，其中是非线性映射。K-means、K中心点方法及其改进方法核K-means假设所有的点已经映射到特征空间中的。令代表n×