PDF《机器学习》

机器学习 4.

聚类-k均值 主要内容 ? 什么是聚类 ? 层次聚类方法 ? k均值聚类 ? 在以上点集中是否存在"类" ? 几个类? ? 每个类是什么? ? 怎样识别这些类? 什么是聚类 ? 聚类:将同类型的对象聚为不同类别的过程 ?高类内相似性 ?低类间相似性 ?一种无监督学习的常见学习形式 什么是聚类 ?无监督学习: ?从原始样本(无标注信息)中学习知识 ?一种对于科学、工程很多领域非常常见的学习目标 ? 基因分类 ? 用户甄别 ? 文本主题分类 ? 图片/视频目标分类 ? ... ? 下面的例子怎样聚类? 什么是聚类 ? 基本问题 ? 什么是一群目标数据的自然聚类? ? 如何度量目标数据间的"关系" ? 数据如何表达 ? 类数目如何度量? ? 聚类算法 ? 算法是否收敛? 什么是聚类 什么是聚类 ? 聚类是主观的! ? 聚类最重要的概念: ? 相似度 什么是聚类 ? 相似度的定义是一个哲学问题 ? 依赖于数据表达方式与算法导向 ? 如何实际操作? ? 距离! 什么是聚类 直观意义? ? 典型相似度度量(距离) ?两个p维向量: ?Minkowski距离(Lp范数) ?最常见的Lp范数 什么是聚类 ? L2距离(欧氏距离): ? L1距离: ? L无穷距离(最大距离): 什么是聚类 ? 海明距离(曼哈顿距离):对全部特征 为二值的向量对定义 ?基因表达 ?文本分类 什么是聚类 关键词1

2 3

4 5

6 7

8 9

10 11

12 13

14 15 文本1

1 0

0 1

1 1

0 1

1 0

0 0

1 1

1 文本2

1 1

0 1

1 0

1 0

0 0

1 1

1 0

0 海明距离 = #01 + #10 =

9 ? 皮尔斯相关系数 什么是聚类 ? 余弦距离 ? 两类聚类问题 什么是聚类 Hierarchical Algorithms Partitional Algorithms ? 层次化方法 ? 分部方法 主要内容 ? 什么是聚类 ? 层次聚类方法 ? k均值聚类 ? 基本原理: 将聚类过程分层次进行 层次聚类方法 ? 与我们日常组织信息结构的方式非常类似 ? 图书馆书籍条目 ? 有用性:可获得任意尺度,任意层次的 聚类信息 ? 在需要的尺度切割聚类树 层次聚类方法 ? 自底而上 ? 首先把每个目标数据视为一类 ? 不断将最近邻数据加入当前类 ? 最终形成一类 层次聚类方法 Bottom-Up Agglomerative ? 自上而下 ? 首先把所有数据视为一类 ? 选择能将当前每类分离成两类 的最佳分割 ? 直到所有数据分类一类 Top-Down Divisive ? 自底而上 ? 首先把每个目标数据视为一类 ? 不断将最近邻数据加入当前类 ? 最终形成一类 层次聚类方法 层次聚类方法 ? 自上而下 ? 首先把所有数据视为一类 ? 选择能将当前每类分离成两类 的最佳分割 ? 直到所有数据分类一类 主要内容 ? 什么是聚类 ? 层次聚类方法 ? k均值聚类 ? 分部方法原理: ? 将n个目标数据分割到预设的K个聚类中 K-均值聚类 ? 人肉 K均值算法 K-均值聚类 ? 游戏 ? 迭代进行以下步骤: ? 每个人将自己归类于与自己最近的 队伍核心 ? 将位于自己类的成员中心更新为新 的队伍核心 K-means ? 算法基本步骤 K-均值聚类 输入:数据,聚类个数 K 1. 初始化 K 个聚类中心 2. 开始如下迭代 a) 对每一个样本进行归类, 距离哪个聚类中 心近,则将其归为哪一类;

b) 重新估计 K 个聚类中心 以上迭代当每个聚类数据不发生改变时终止. K-均值聚类 ?示例: K-均值聚类 K-均值聚类 K-均值聚类 K-均值聚类 1. 是否一定收敛? 2. 是否一定收敛到一个合理值? K-均值聚类 K-均值聚类 K-均值聚类 ? 效果与初值选择有关 ? 如何选择初值? K-均值聚类 ? K均值聚类算法有无目标函数(表现度量)? K-均值聚类 问题描述: 给定 n 个观察数据(x1, x2, … , xn),学习目标为将其 归入 K 个类中: C = {C1, C2,… , CK}, 对应类具有类 指示数据?? = (μ1, μ2, … , μK),从而使得以下目标函 数(类内数据最小二乘误差)最小: argmin C,?? ? ? ?xj ? μi?