聚类 IRLAB.

Presentation on theme: "聚类 IRLAB."— Presentation transcript:

1 聚类 IRLAB

2 大纲 聚类分析简介 层次聚类 单连接和全连接聚类 组平均聚类 应用：改进语言模型 自顶向下聚类 非层次聚类 K-均值 EM算法

3 聚类算法类型 层次聚类与非层次聚类 自底向上与自上向下（凝聚与分裂） K-均值 软聚类与硬聚类 模糊聚类（EM算法）

4 层次聚类 自底向下的聚类 每一项自成一类 迭代，将最近的两类合为一类 自顶向下的聚类 将所有项看作一类 找出最不相似的项分裂出去成为两类

5 类的相似度度量 我们可以知道两个项之间的相似度，但是聚类要求知道类与类之间的相似度 三种方法： 单连接方法 全连接方法 组平均方法

6

7

8

9

10 非层次聚类 K-均值 硬聚类 计算每个类的中心 EM算法 考虑稀疏数据 公式 用EM算法计算P( ci|w1)

11 K-均值 将n个向量分到k个类别中去 选择k个初始中心 计算两项距离 计算均值

12

13

14

15

16

17

18 K-均值算法

19 EM-算法 算法族 以前的一个例子：前向后项算法是EM算法的一个例子
可以用于任意的概率模型E(likelihood)及max likelihood estimite估计

20 模糊聚类 经典的k均值聚类算法的一部迭代中，每一个样本点都被认为是完全属于某一类别。
模糊聚类放松这一条件，假定每个样本是模糊隶属于某一类的。 每类是一个高斯分布 样本集合模拟成一个高斯混合分布

21 EM算法 点集x1,……xn K个类 Z为二维数组，zij为1表示xi在j类中，否则为0 每个j类定义为一个高斯分布

22 EM算法 用先前的概率累加 任意一项xi的概率

23 EM算法 参数 给定参数下x的值

24 EM算法 找到zij的期望值并用它计算最大似然估计，反复迭代，直到收敛。

25 特点 我们从初始迭代直到收敛 是局部最优 K均值是用EM算法求解高斯混合分布的特例