统计自然语言处理--分类与聚类.pdf

《统计自然语言处理--分类与聚类.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、聚类与分类IRLAB聚类大纲•聚类分析简介•层次聚类–单连接和全连接聚类–组平均聚类–应用：改进语言模型–自顶向下聚类•非层次聚类–K-均值–EM算法什么是聚类分析?•聚类:数据对象的集合–在同一个类中，数据对象是相似的–不同类之间的对象是不相似的•聚类分析–一个数据集合分组成几个聚类•聚类是一种无监督分类:没有预定义的类•典型应用–作为一个独立的工具透视数据分布–可以作为其他算法的预处理步骤聚类在自然语言中的应用•探测数据分析（exploratorydataanalysis）–例如词性标注，将相似的词作为同一种词性，对前置词比较有效–对this和the这种语法语义特征不一致的词，不

2、总分在一组的词不适合•概化（generalization）–等价类，可以使用相同的上下文环境，解决数据稀疏问题–同时聚类是学习的一种方法（推理Friday的前置词）聚类算法类型•层次聚类与非层次聚类–层次聚类的每一个节点是其父节点的一个子类，叶节点对应的是类别中每一个单独的对象，常用算法自底向上与自上向下（凝聚与分裂）–非层次聚类只是简单的包括了每类的数量，体现不了他们之间的层次关系，常用算法K-均值•软聚类与硬聚类–硬聚类将每一个对象分到一个且只能是一个的类别中，例如K-均值–软聚类刻画的是将对象归属不同类的程度，模糊聚类（EM算法）层次聚类和非层次聚类的比较•层次聚类•非层次聚类

3、–适合于数据的详细–适合于大数据集合描述要求考虑效率较高的情况–提供更多的信息–K-均值是一种最简–没有单一的最好的单的方法，并且有算法效的–效率没有非层次的–K-均值采用欧氏好距，不能表达更广泛的数据–EM算法提供了类的定义以及基于复杂概率模型的数据的分配层次聚类•自底向下的聚类(凝聚）–每一项自成一类–不断地将最近的两类合为一类•自顶向下的聚类（分裂）–将所有项看作一类–找出最不相似的项分裂出去成为两类层次聚类¢这种方法不需要输入参数K，但需要一个终止条件。例如：相似度阈值Step0Step1Step2Step3Step4聚集(AGNES)aabbabcdeccdeddee分裂S

4、tep4Step3Step2Step1Step0(DIANA)类的相似度度量•三种度量：–单连接•两个最近成员的相似度–全连接•两个最远成员的相似度–组平均•类成员的平均相似度•不同的度量会导致不同的聚类形状，适用于不同的问题•在大多数NLP问题中，基于全连接聚类更适用•基于组平均方法比全连接效率高，并且避免了单连接聚类的狭长形状应用：改进语言模型•聚类通过概化改进语言模型•通过聚类进行推理，扩大训练语料•使对稀疏事件处理据有较好的精度非层次聚类•一般过程–随机选择种子–进行样本划分–通过迭代将样本进行重新分配–直到模型参数估计不再上升或呈下降趋势非层次聚类•K-均值–硬聚类–每个样

5、本点完全属于某一类–计算每个类的中心值•模糊k-均值–软聚类–每个样本点模糊隶属于某一类–用EM算法计算P(c

6、w)i1K-均值•将n个向量分到k个类别中去•选择k个初始中心•计算两项距离•计算n个向量均值K-均值算法•给定k,k-均值算法包括4个步骤:–将对象分成k个非空的子集–计算每个类的平均值作为中心点.–重新将对象，将对象划分到离它最近的聚类–重新计算聚类的中心，重新划分对象，直到所有的对象都不再发生变化.•注意与k-中心点的区别模糊聚类•经典的k-均值聚类算法在每一步迭代中，每一个样本点都被认为是完全属于某一类别•模糊聚类放松这一条件，假定每个样本是模糊隶属于某一类的–每类

7、是一个高斯分布–样本集合模拟为高斯混合分布EM算法•点集x1,……xn•K个类•Z为二维数组，z为1表示x在j类中，否iji则为0•每个类定义为一个高斯分布EM算法•用先前的概率累加•任意一项x的概率iEM算法•参数•给定参数下x的值EM算法•计算z的期望值（E-step)并用它计算最ij大似然估计(M-step)，反复迭代，直到收敛。EM算法特点•算法族•可以用于任意的概率模型的参数估计•结果是局部最优的•K-均值是用EM算法求解高斯混合分布的特例分类IRLAB大纲•分类技术在自然语言中的应用•决策树•贝叶斯分类•最大熵模型•K近邻•其他方法自然语言中的分类问题问题对象分类词性标注

8、词的上下文词性词义消歧词的上下文词义介词附着句子分析树命名实体识别句子实体类别作者识别文档作者语言识别文档语言类型文本分类文档主题分类的一般过程•训练集•数学模型•训练过程•测试集•评价本课介绍的几种方法•决策树•贝叶斯分类•最大熵模型•K近邻•神经网简介决策树•简介•决策树表示法•决策树学习的适用问题•基本的决策树学习算法•决策树学习中的假想空间搜索•决策树学习的常见问题简介•决策树方法的起源是概念学习系统CLS，然后发展到ID3方法而为高潮，最后又演化