第10章-聚类与集成算法ppt课件.pptx

《第10章-聚类与集成算法ppt课件.pptx》由会员分享，可在线阅读，更多相关《第10章-聚类与集成算法ppt课件.pptx（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、10.聚类与集成算法聚类(Clustering)在“无监督学习”任务中研究最多、应用最广目标：将数据样本划分为若干个通常不相交的“簇” (cluster)既可以作为一个单独过程（用于找寻数据内在的分布结构）也可作为分类等其他学习任务的前驱过程性能度量聚类性能度量，亦称聚类“有效性指标” (validity index)外部指标 (external index)将聚类结果与某个“参考模型”(reference model) 进行比较如 Jaccard 系数， FM 指数，Rand 指数内部指标 (internal index)直接考察聚类结果而不用任何参考模型如 DB 指数， Dunn 指数等基

2、本想法： “簇内相似度” （intra-cluster similarity）高，且 “簇间相似度” （inter-cluster similarity）低距离计算距离度量 (distance metric) 需满足的基本性质：常用距离形式：闵可夫斯基距离 (Minkowski distance)p = 2: 欧氏距离(Euclidean distance)p = 1: 曼哈顿距离(Manhattan distance)距离计算 (续） 对 无序 (non-ordinal)属性 ，可使用 VDM(Value Difference Metric)令表示属性 u 上取值为 a 的样本数，表示在第

3、i 个样本簇中在属性 u 上取值为 a 的样本数，k 为样本簇数，则属性 u 上两个离散值 a 与 b 之间的 VDM 距离为 对 混合属性 ，可使用 MinkovDM必须记住聚类的“好坏”不存在绝对标准the goodness of clustering depends onthe opinion of the user故事一则聚类的故事：老师拿来苹果和梨，让小朋友分成两份。小明把大苹果大梨放一起，小个头的放一起，老师点头，恩，体量感。小芳把红苹果挑出来，剩下的放一起，老师点头，颜色感。小武的结果？不明白。小武掏出眼镜：最新款，能看到水果里有几个籽，左边这堆单数，右边双数。老师很高兴：新的聚

4、类算法诞生了聚类也许是机器学习中“新算法”出现最多、最快的领域总能找到一个新的“标准”，使以往算法对它无能为力常见聚类方法 原型聚类亦称“基于原型的聚类”(prototype-based clustering)假设：聚类结构能通过一组原型刻画过程：先对原型初始化，然后对原型进行迭代更新求解代表：k均值聚类，学习向量量化 (LVQ)，高斯混合聚类 密度聚类亦称“基于密度的聚类” (density-based clustering)假设：聚类结构能通过样本分布的紧密程度确定过程：从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇代表：DBSCAN, OPTICS, DENCL

5、UE 层次聚类 (hierarchical clustering)假设：能够产生不同粒度的聚类结果过程：在不同层次对数据集进行划分，从而形成树形的聚类结构代表： AGNES (自底向上)，DIANA (自顶向下)k-means每个簇以该簇中所有样本点的“均值”表示Step1: 随机选取k个样本点作为簇中心Step2: 将其他样本点根据其与簇中心的距离，划分给最近的簇Step3: 更新各簇的均值向量，将其作为新的簇中心Step4: 若所有簇中心未发生改变，则停止；否则执行 Step 2若不以均值向量为原型，而是以距离它最近的样本点为原型，则得到 k-medoids算法高斯混合聚类(Gausian

6、 Mixture Clustering, GMM) 根据定义的先验分布选择高斯混合成分，其中为选择第 i 个混合成分的概率； 然后，根据被选择的混合成分的概率密度函数进行采样，从而生成相应的样本采用概率模型来表达聚类原型n 维样本空间中的随机向量 x 若服从高斯分布，则其概率密度函数为假设样本由下面这个高斯混合分布生成：生成式模型高斯混合聚类（续）样本 xj 由第 i 个高斯混合成分生成的后验概率为：简记为参数估计可采用极大似然法，考虑最大化对数似然EM 算法： (E步 ) 根据当前参数计算每个样本属于每个高斯成分的后验概率 (M步 ) 更新模型参数集成学习(Ensemble learning

7、)集成学习通过构建并结合多个学习器来完成学习任务 .Problem .ProblemLearnerLearnerLearnerLearner 同质(homogeneous)集成：集成中只包含同种类型的“个体学习器”相应的学习算法称为“基学习算法” (base learning algorithm)个体学习器亦称“基学习器” (base learner) 异质 (heterogeneous)集成：个体学习器由不同的学习算法生成不存在“基学习算法”Why Ensemble?集成的泛化性能通常显著优于单个学习器的泛化性能一组神经网络的平均性能选择最优神经网络两种简单的神经网络集成方法一个观察：误差（

8、曲线越低越好）Hansen & Salamon, TPAMI90令个体学习器 “好而不同”如何得到好的集成？想获胜，用集成现实各类机器学习、数据挖掘应用中，广泛使用集成学习技术很多成功的集成学习方法 序列化方法Freund & Schapire, JCSS97Friedman, AnnStat01Demiriz, Bennett, Shawe-Taylor, MLJ06 AdaBoost GradientBoost LPBoost 并行化方法Breiman, MLJ96Breiman, MLJ01Ho, TPAMI98 Bagging Random Forest Random Subspace

9、 Data set 1Data set 2Data set TLearner1Learner2LearnerT . . .by Learner1 will play more important roles inthe training of Learner2weighted combinationOriginal training setBoosting: A flowchart illustrationtraining instances that are wrongly predictedBaggingData set0Data set1Data set2Data setn . . .b

10、ootstrap a set of learnersgenerate many data sets fromthe original data set throughbootstrap sampling (randomsampling with replacement), thentrain an individual learner perdata setaveraging for regressionthe output is the average output ofthe individual learnersvoting for classificationthe output is

11、 the class labelreceiving the most number ofvotesLearner1Learner2Learnern学习器结合常用结合方法： 投票法 绝对多数投票法 相对多数投票法 加权投票法 平均法 简单平均法 加权平均法 学习法Stacking多样性“多样性”(diversity) 是集成学习的关键(error-ambiguity decomposition):误差-分歧分解多样性度量一般通过两分类器的预测结果列联表定义不合度量 (disagreement measure)相关系数 (correlation coefficient)Q-统计量 (Q-stati

12、stic)-统计量 （-statistic） -误差图每一对分类器作为图中的一个点多样性增强常用策略 数据样本扰动 例如 Adaboost 使用 重要性采样、Bagging 使用自助采样注意：对“不稳定基学习器” (如决策树、神经网络等 ) 很有效不适用于“稳定基学习器” （如线性分类器、SVM、朴素贝叶斯等） 输入属性扰动 例如 随机子空间(Random Subspace) 输出表示扰动 例如 输出标记随机翻转、分类转回归、 ECOC 算法参数扰动“越多越好”？选择性集成(selective ensemble):给定一组个体学习器，从中选择一部分来构建集成，经常会比使用所有个体学习器更好 (

13、更小的存储/时间开销，更强的泛化性能)ProblemLearner .Learner .Learner集成修剪 (ensemble pruning)Margineantu & Dietterich, ICML97较早出现，针对序列型集成减小集成规模 、降低泛化性能选择性集成 Zhou, et al, AIJ 02 稍晚，针对并行型集成， MCBTA (Many couldbe better than all)定理减小集成规模 、增强泛化性能目前“集成修剪”与“选择性集成”基本被视为同义词选择过程需考虑个体 性能 与 多样性 /互补性仅选出“精度最高的”通常不好！机Z.-H. Zhou.Ensemble Methods:Foundations and Algorithms,Boca Raton, FL: Chapman &Hall/CRC, Jun. 2012.(ISBN 978-1-439-830031)更多关于集成学习的内容，可参考：