PDF《机器学习》

2 2 xj∈Ci K i=1 . ? 问题求解复杂度: ? 组合优化问题 ? NP-hard! K-均值聚类 问题描述: 给定 n 个观察数据(x1, x2, … , xn),学习目标为将其 归入 K 个类中: C = {C1, C2,… , CK}, 对应类具有类 指示数据?? = (μ1, μ2, … , μK),从而使得以下目标函 数(类内数据最小二乘误差)最小: argmin C,?? ? ? ?xj ? μi?

2 2 xj∈Ci K i=1 . ? 解决之道: ? 迭代优化/搜索/更新算法 K-均值聚类 Althernative Optimization/S earch K-均值聚类 argmin S,?? ? ? ?xj ? μi?

2 2 xj∈Ci K i=1 . ? 初始化 k 个类中心 ?? = (μ1,μ2, … , μK) ? 迭代进行以下优化 ? 更新聚类:固定??,优化C ? 更新类中心:固定C,优化?? K-均值聚类 ? 更新聚类:固定??,优化C ? 等价于对每个xj单独计算以下优化问题 argmin xj ∈Ci ?xj ? μi?

2 2 s. t. i = 1,2, … , K ? 解是? argmin S,?? ? ? ?xj ? μi?

2 2 xj∈Ci K i=1 . K-均值聚类 ? 解是? ? 更新类中心:固定C,优化?? ? 等价于对每个类中心μi,计算以下优化问题: argmin μi ? ?xj ? μi?

2 2 xj∈Ci . argmin S,?? ? ? ?xj ? μi?

2 2 xj∈Ci K i=1 . ? K-均值算法基本步骤 K-均值聚类 输入:数据,聚类个数 K 1. 初始化 K 个聚类中心 2. 开始如下迭代 a) 对每一个样本进行归类, 距离哪个聚类中 心近,则将其归为哪一类;

b) 重新估计 K 个聚类中心 以上迭代当每个聚类数据不发生改变时终止. ? 完全对应于求解 的迭代优化方法! ? 目标函数单调递减,一定收敛! argmin S,?? ? ? ?xj ? μi?

2 2 xj∈Ci K i=1 . ? 初值问题 ? 为何依赖于初值? ? 目标函数非凸,因此不同初值会收 敛于不同局部极优点 ? 怎样选择相对较好初值 ? 利用启发式方法(将初值尽量散开 设置) ? 尝试多个初值 ? 使用其它方法运行结果作为初值 K-均值聚类 ? 什么是一个好的聚类 ?内部标准: ?类内相似度高 ?类间相似度低 ?使用相似度度量的合理性 ?外部标准 ?能否挖掘一些隐藏在数据中的有用模 式 ?能否恢复真实类别 K-均值聚类 ? k-medoid方法 K-均值聚类 argmin C,?? ? ? ?xj ? μi?

1 xj∈Ci K i=1 ? 仔细思考与K-均值求解方法的异同 argmin S,?? ? ? ?xj ? μi?

2 2 xj∈Ci K i=1 . ? 缺点? ? 归类方式为hard,而非soft ? 确定性模型而非生成模型 ? 如何预测? K-均值聚类 1. 聚类的基本概念与思想 2. 层次聚类的基本思想 3. K均值聚类算法、模型与优化原理 阅读: [1] Pattern Recognition and Machine Learning, Christopher , M. Bishop, Springer, 2006. 9. Mixture Models and EM 编程作业1: 1. 实现K-means方法 2. 在一组自己设计的人工数据上尝试K-means计算效果, 并从不同角度分析算法特点 3. 在UCI数据集或其他实际数据集上尝试K-means方法 要求