机器学习聚类课件.ppt

1、统计与机器学习统计与机器学习统计学：从不完全的信息里取得准确知识的技巧。统计应用：用数理统计的原理和方法，分析和解释自然界界的种种现象和数据资料，以求把握其本质和规律性。机器学习：可以理解为计算机自动从数据中发现规律，并应用于解决新问题。内容比较杂，至今还没有统一的定义，而且也很难给出一个公认的和准确的定义。机器学习在大多数情况下应用概率论与统计学理论来设计算法；1 1机器学习机器学习给定数据 (X1,Y1),(X2,Y2),(Xn,Yn)，机器自动学习 X 和 Y 之间的关系，从而对新的 Xi，能够预测 Yi。垃圾邮件识别：(邮件 1,垃圾),(邮件 2,正常),(邮件 3,垃圾),(邮件

2、N,正常)邮件 X=垃圾 or 正常？2 2测试数据发现规律预测预测结果规则邮件邮件XiYi：垃圾：垃圾or正常正常1.发件人邮件地址异常；2.标题含有“低价促销”3.机器学习机器学习一般流程：3 3训练数据测试数据学习预测预测结果模型训练过程应用过程(X1,Y1)(X2,Y2)(Xn,Yn)XiYi机器学习机器学习模型：问题的影响因素(特征)有哪些？它们之间的关系如何？策略：什么样的模型是好的模型；算法：如何高效的找到最优参数；分类：有监督的学习；无监督的学习；半监督的学习；增强学习；多任务学习；4 4统计与机器学习统计与机器学习内容：聚类与分类；统计推断：参数检验，假设检验；回归分析；马尔

3、科夫链与隐马尔科夫模型。遗传算法与神经网络；。5 5机器学习：聚类机器学习：聚类(CLUSTERING)聚类就是对大量未知标注的数据集，按数据的内在相似性将数据集划分为多个类别，使类别内的数据相似度较大而类别间的数据相似度较小;簇（或类Cluster）：子集合最大化簇（或类）内的相似性；最小化簇（或类）间的相似性；聚类是一种无监督分类法：没有预先指定的类别；典型的应用作为一个独立的分析工具，用于了解数据的分布；作为其它算法的一个数据预处理步骤；6 6机器学习机器学习：聚类：聚类(CLUSTERING)简单示例：聚类后预测：7 7训练数据待分类数据机器学习机器学习：聚类：聚类(CLUSTERIN

4、G)基因表达芯片（微阵列）：预测新测序基因的功能是重要的生物学问题；基因表达微阵列提供了预测功能的途径；基因芯片对研究调控网络提供了最基本的数据；基因芯片可以衡量基因在不同条件下的表达量；基因如果被转录，就可以认为是处于激活状态；转录产物 mRNA 的数量代表基因的活性；8 8机器学习机器学习：聚类：聚类(CLUSTERING)DNA 芯片的应用：研究基因样本在在不同的时间段表达的差异；研究不同的基因样本在相同的条件下的表达差异9 9机器学习机器学习：聚类：聚类(CLUSTERING)DNA芯片数据：绿色：仅仅在参考状态表达；红色：仅仅在所研究的状态表达；黄色：在两种状态都表达；黑色：在两种状

5、态都不表达；表达强度数据会被标准化、组成表达强度矩阵。1010Time:Time XTime YTime ZGene 110810Gene 21009Gene 348.63Gene 4783Gene 5123机器学习机器学习：聚类：聚类(CLUSTERING)DNA 芯片数据的聚类：每组数据可以看做 n 维空间里的点；通过对每个点对计算距离构造距离矩阵；距离较近的基因表达情况相似、或许更有可能具有功能上的相关性；聚类能够构造功能相关基因集合；1111机器学习机器学习：聚类：聚类(CLUSTERING)DNA芯片数据的聚类：同质性：一个类中基因相似，即距离较小；差异性：不同类的基因非常不同，即距

6、离较大；聚类并非易事；算法不同可能得到不同的结果；1212机器学习机器学习：聚类：聚类(CLUSTERING)DNA芯片数据的聚类：两点之间的距离欧氏距离：平方欧氏距离：夹角余弦：绝对距离：Chebychev距离:皮尔森相关系数：Minkowski距离：13132()iiixy2()iiixy22(1)cosiiixyxyiiiix yCxy1()qqiiixy22()()(2)()()iiixyxyiiiixxyyCrxxyyiii-yx|maxiii-yx机器学习机器学习：聚类：聚类(CLUSTERING)DNA芯片数据的聚类：两类之间的距离最短距离法:最长距离法：重心法：类平均法：离差平

7、方和：1414min(,)pqijDd x x121 21 212()(),()(),()()ipjqkpqipipjqjqxGxGkipqxGGDxxxxDxxxxDxxxxDDDDmax(,)pqijDd x xmin(,)pqpqDd xx121(,)ipjqpqijxGxGDd x xn n 机器学习机器学习：聚类：聚类(CLUSTERING)聚类方法：k-均值法（k-means）给定 k,k-均值算法由以下四步来完成:把对象划分为 k 个非空的子集；随机的选择一些种子点作为目前划分的簇的质心。质心是簇的中心（平均点）；把每一个对象赋给最近的种子点；重复第二步，直到没有新的分配；151

8、5机器学习机器学习：聚类：聚类(CLUSTERING)聚类方法：k-均值法1616012345012345expression in condition 1expression in condition 2x1x2x3机器学习机器学习：聚类：聚类(CLUSTERING)聚类方法：k-均值法1717012345012345expression in condition 1expression in condition 2x1x2x3机器学习机器学习：聚类：聚类(CLUSTERING)聚类方法：k-均值法1818012345012345expression in condition 1expres

9、sion in condition 2x1x2x3机器学习机器学习：聚类：聚类(CLUSTERING)聚类方法：k-均值法1919012345012345expression in condition 1expression in condition 2x1x2x3机器学习机器学习：聚类：聚类(CLUSTERING)聚类方法：k-均值法优点：复杂度:O(tkn),其中 n 是对象的数目,k 是 cluster 的数目,t 是迭代的次数，通常 k,t 0，则判定 x 属于 H1，如果 g(x)0，则判定 x 属于 C2，如果 g(x)=0，则可以将 x 任意分到某一类或者拒绝判定。4646bxw

10、xgi)(0bxwiHC2C1机器学习：机器学习：支持向量机支持向量机方程 g(x)=0 定义了一个判定面，它把归类于 C1 的点与归类于 C2 的点分开来。当 g(x)是线性函数时，此平面被称为超平面(hyperplane)。方程 g(x)=0 实际上是 n-1维的线性子空间；4747-0.500.5-0.500.5-0.5-0.4-0.3-0.2-0.100.10.20.30.40.5X1X2X3机器学习：机器学习：支持向量机支持向量机如何找到最大间隔？为了将这个准则具体化，需要用数学式子表达。为了方便，将训练样本集表示成 xi,yi，i=1,N，其中 xi 为 d 维向量也就是特征向量，

11、而 yi-1,+1，即用 yi 是+1 或-1 表示其类别。对于分界面 H 表示成：并且满足：故 H1到 H2 的间隔为：目标：在满足约束条件的前提下达到间隔最大；前提：线性可分；4848Nibxwyii,2,1，1)(0bxwi|w|2机器学习：机器学习：支持向量机支持向量机转化为带约束的极值问题，或规划问题；对于这样一个带约束条件为不等式的条件极值问题，需要引用扩展的拉格朗日乘子理论，按这个理论构造拉格朗日函数的原则为：49492/minwwNibxwyii,2,1，1)(s.t.NiiiiPbxwywwL1)1)(21(3)机器学习：机器学习：支持向量机支持向量机上述方法线性可分条件为基

12、本前提；可否将不可分问题转化为可分？5050机器学习：机器学习：支持向量机支持向量机异或问题异或问题是最简单的一个无法直接对特征采用线性判别函数解决的问题。如图所示的四个样本点。利用 SVM 将他们映射到一个更高维的空间，使之线性可分。5151机器学习：机器学习：支持向量机支持向量机采用最简单且展开不超过二次的展开将上述问题的点映射到六维空间：最佳超平面是：其二维空间投影如图所示525222212121,2,2,2,1xxxxxx0),(2121xxxxg2221xx121xx机器学习：机器学习：支持向量机支持向量机特点：对特征空间划分的最优超平面是SVM的目标,最大化分类边际的思想是SVM方

13、法的核心；支持向量是SVM的训练结果,在SVM分类决策中起决定作用的是支持向量；模型为凸二次规划模型，没有陷入局部最优解的问题，任何局部最优解都是全局最优解；SVM 的最终决策函数只由少数的支持向量所确定,计算的复杂性取决于支持向量的数目,而不是样本空间的维数,这在某种意义上避免了“维数灾难”。少数支持向量决定了最终结果,这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本,而且注定了该方法不但算法简单,而且具有较好的“鲁棒”性。5353机器学习：分类结果的衡量机器学习：分类结果的衡量灵敏度（Sensitivity）与特异度（Specificity）假阳性（FP）、真阳性（TP）；假阴性（FN）、真阴性（FN）；5454机器学习机器学习：分类结果的衡量：分类结果的衡量Test!5555机器学习机器学习：分类结果的衡量：分类结果的衡量ROC曲线接收者操作特征（receiver operating characteristic）真阳性率（TPR）和假阳性率（FPR）5656THE END！5757