聚类 IRLAB
大纲 聚类分析简介 层次聚类 单连接和全连接聚类 组平均聚类 应用：改进语言模型 自顶向下聚类 非层次聚类 K-均值 EM算法
聚类算法类型 层次聚类与非层次聚类 自底向上与自上向下（凝聚与分裂） K-均值 软聚类与硬聚类 模糊聚类（EM算法）
层次聚类 自底向下的聚类 每一项自成一类 迭代，将最近的两类合为一类 自顶向下的聚类 将所有项看作一类 找出最不相似的项分裂出去成为两类
类的相似度度量 我们可以知道两个项之间的相似度，但是聚类要求知道类与类之间的相似度 三种方法： 单连接方法 全连接方法 组平均方法
非层次聚类 K-均值 硬聚类 计算每个类的中心 EM算法 考虑稀疏数据 公式 用EM算法计算P( ci|w1)
K-均值 将n个向量分到k个类别中去 选择k个初始中心 计算两项距离 计算均值
K-均值算法
EM-算法 算法族 以前的一个例子：前向后项算法是EM算法的一个例子 可以用于任意的概率模型E(likelihood)及max likelihood estimite估计
模糊聚类 经典的k均值聚类算法的一部迭代中，每一个样本点都被认为是完全属于某一类别。 模糊聚类放松这一条件，假定每个样本是模糊隶属于某一类的。 每类是一个高斯分布 样本集合模拟成一个高斯混合分布
EM算法 点集x1,……xn K个类 Z为二维数组，zij为1表示xi在j类中，否则为0 每个j类定义为一个高斯分布
EM算法 用先前的概率累加 任意一项xi的概率
EM算法 参数 给定参数下x的值
EM算法 找到zij的期望值并用它计算最大似然估计，反复迭代，直到收敛。
特点 我们从初始迭代直到收敛 是局部最优 K均值是用EM算法求解高斯混合分布的特例