文本聚类

一. 划分法(基于划分的聚类算法)

k-means(k的选取,大规模文本计算距离复杂度高)

大样本采取Mini Batch K-Means算法

二. 层次法(基于层次的聚类算法)

  • 自底向上(合并聚类)
    • 将语料库中的任一数据都当作一个新的簇,计算所有簇相互之间的相似度,然后将相似度最大的两个簇进行合并,重复这个步骤直到达到某个终止条件,因此合并聚类方法也被称为由下而上的方法。
  • 自顶向下(分裂聚类)
    • 先将数据集中所有的对象都归为同一簇,并将不断地对原来的簇进行划分从而得到更小的簇,直到满足最初设定的某个终止条件。
  • 优缺点
    • 优点
      1. 适用于发现任意形状的簇;
      2. 适用于任意形式的相似度或距离表示形式;
      3. 聚类粒度的灵活性。
    •  缺点
      1. 算法终止的条件很模糊,难以精确表达并控制算法的停止;
      2. 一旦聚类结果形成,一般不再重新构建层次结构来提高聚类的性能;
      3. 难以处理大规模数据,也不能适应动态数据集的处理。

三. DBSCAN(密度聚类)

  • 由密度可达关系导出的最大密度相连的样本集合,即为我们最终聚类的一个类别,或者说一个簇
  • 先从数据集w中找到任意一个对象q,并查找w中关于R和最小下限数MinPts的从q密度到达的所有对象。如果q是核心对象,也就是说,q半径为R的领域中包含的对象数不少于MinPts,则根据算法可以找到一个关于参数R和MinPts的类。如果q是一个边界点,即q半径为R的领域包含的对象数小于MinPts,则没有对象从q密度到达,q被暂时标注为噪声点。然后,DBSCAN处理数据集W中的下一个对象。

四. Single-pass(增量聚类)

其顺序处理文本,以第一篇文档为种子,建立一个新主题。之后再进行新进入文档与已有主题的相似度,将该文档加入到与它相似度最大的且大于一定阈值的主题中。如果与所有已有话题相似度都小于阈值,则以该文档为聚类种子,建立新的主题类别。适合大规模文本聚类

五.BIRCH聚类算法原理

适合于数据量大,类别数K也比较多的情况

  • 1) 将所有的样本依次读入,在内存中建立一颗CF Tree, 建立的方法略。
  • 2)(可选)将第一步建立的CF Tree进行筛选,去除一些异常CF节点,这些节点一般里面的样本点很少。对于一些超球体距离非常近的元组进行合并
  • 3)(可选)利用其它的一些聚类算法比如K-Means对所有的CF元组进行聚类,得到一颗比较好的CF Tree.这一步的主要目的是消除由于样本读入顺序导致的不合理的树结构,以及一些由于节点CF个数限制导致的树结构分裂。
  • 4)(可选)利用第三步生成的CF Tree的所有CF节点的质心,作为初始质心点,对所有的样本点按距离远近进行聚类。这样进一步减少了由于CF Tree的一些限制导致的聚类不合理的情况。

HMM VS CRF

一、区别

  1. HMM是生成模型(由数据学习联合概率分布P(X,Y), 然后由P(Y|X)=P(X,Y)/P(X)求出概率分布P(Y|X)作为预测的模型),CRF是判别模型(由数据直接学习决策函数Y=f(X)或条件概率分布P(Y|X)作为预测模型)
  2. HMM是概率有向图CRF是概率无向图
  3. CRF由于得分进行全局softmax归一化,所以得到的是全局最优值;并且解决了最大熵马尔可夫模型(MEMM)中的标注偏置问题(MEMM只去除了观测独立性假设,没有去除齐次马尔科夫链假设 Thus, states with a single outgoing transition effectively ignore their observations. More generally, states with low-entropy next state distributions will take little notice of observations)。
  4. CRF打破了HMM的两种假设:
    • 齐次马尔科夫链假设。即任意时刻的隐藏状态只依赖于它前一个隐藏状态;
    • 观测独立性假设。即任意时刻的观察状态只仅仅依赖于当前时刻的隐藏状态
  5. CRF可以定义数量更多,种类更丰富的特征函数,并且加权求和(score)
  6. CRF在特征函数中还包含了整条观测序列的信息,都可以被利用
  7. 任意的HMM都可以由CRF表达出来

二、HMM

隐马尔可夫模型 HMM

三、CRF

CRF条件随机场

四、Refs

生成模型和判别模型

生成模型和判别模型

一、判别方法

1.定义

由数据直接学习决策函数Y=f(X)或者条件概率分布P(Y|X)作为预测的模型,即判别模型。基本思想是有限样本条件下建立判别函数,不考虑样本的产生模型,直接研究预测模型。典型的判别模型包括线性回归逻辑回归K近邻决策树支持向量机、条件随机场最大熵模型提升方法、感知机

  • 决策函数Y=f(X):你输入一个X,它就输出一个Y,这个Y与一个阈值比较,根据比较结果判定X属于哪个类别。例如两类(w1和w2)分类问题,如果Y大于阈值,X就属于类w1,如果小于阈值就属于类w2。这样就得到了该X对应的类别了。
  • 条件概率分布P(Y|X):你输入一个X,它通过比较它属于所有类的概率,然后输出概率最大的那个作为该X对应的类别。例如:如果P(w1|X)大于P(w2|X),那么我们就认为X是属于w1类的。
2.优缺点
  • 优点
    • 直接面对预测,往往学习的准确率更高
    • 由于直接学习 P(Y|X) 或 f(X),可以对数据进行各种程度的抽象,定义特征并使用特征,以简化学习过程
  • 缺点
    • 不能反映训练数据本身的特性。

二、生成模型

1.定义

由数据学习联合概率密度分布P(X,Y),然后求出条件概率分布P(Y|X)作为预测的模型,即生成模型:P(Y|X)= P(X,Y)/ P(X)。典型的生成模型包括朴素贝叶斯、贝叶斯网络隐马尔可夫模型、马尔可夫随机场混合高斯模型

2.优缺点
  • 优点
    • 可以还原出联合概率分布 P(X,Y),判别方法不能
    • 学习收敛速度更快——即当样本容量增加时,学到的模型可以更快地收敛到真实模型
    • 当存在“隐变量”时,只能使用生成模型
  • 缺点
    • 学习和计算过程比较复杂

三、联系

  • 由生成模型可以得到判别模型,但由判别模型得不到生成模型。
  • 当存在“隐变量”时,只能使用生成模型

四、Example

  • 生成式模型举例:利用生成模型是根据山羊的特征首先学习出一个山羊的模型,然后根据绵羊的特征学习出一个绵羊的模型,然后从这只羊中提取特征,放到山羊模型中看概率是多少,在放到绵羊模型中看概率是多少,哪个大就是哪个。
  • 判别式模型举例:要确定一个羊是山羊还是绵羊,用判别模型的方法是从历史数据中学习到模型,然后通过提取这只羊的特征来预测出这只羊是山羊的概率,是绵羊的概率。

五、Refs