Notes on Text Mining and Analytics - 4

Text Clustering: Motivation

  • What is text clustering?
  • Why text clustering?
  • How to do text clustering?
    • Generative probabilistic models
    • Similarity based approaches
  • How to evaluate clustering results?
  • 文本聚类的应用场景:
    • 可以帮助用户快速了解文本中包含的主要内容;
    • 可以将相似的文本对象关联起来,比如:当文本中出现某些冗余的内容时,文本聚类可以有效的帮助我们消除冗余;
    • 文本聚类可以帮助我们关联一个话题的多个文本对象,也可以用于文本数据结构化,有时还可以建立结构的层次关系(在一些博客中也能看到文本聚类的应用,比如词云);
    • 用与搜索引擎,可以将用户的搜索结果进行聚类,这样用户就可以看到查询结果的大致结构。(当查询条件比较模糊时,文本聚类可以呈现没模糊词汇的不同意义);
    • 对用户的邮件进行文本聚类,可以了解他们的主要诉求。

文本聚类:生成概率模型 Text Clustering: Generative Probabilistic Models

生成概率模型和之前的主题概率模型非常相似,他们的不同之处在于,文本聚类模型中,一个文档只对应一个主题,这个文档关于其他主题的覆盖率为0。

Mixture Model for Document Clustering

Mixture Model for Document Clustering

我们选择最大似然法进行参数评估,文档d应该属于哪个主题,即Cd应该怎么算呢? Cluster Allocation After Parameter Estimation - Likelihood适用于生成模型中的计算; - Likelihood+prior(Bayesian)常用于大的聚类中的计算。

模型举例: 以这个模型为例,此模型有两个主题。 E-Step: E-Step

如果单词出现的次数多而概率又小的话,计算出来的将是一个非常小的值,可能就会导致下溢(underflow)的问题。 计算机的精度遭遇极限的挑战时候会出现两种情况,overflow和underflow。 为了解决underflow,我们使用normalization,有时候取log也是可以解决underflow的问题。 Normalization to avoid underflow

M-stepM-Step

文本聚类:基于相似度的方法 Text Clustering: Similarity-based Approaches

基于层次聚类的General idea: - 清晰的定义一个相似度函数,衡量两个文本对象之间的相似度 - 寻找一个最佳的划分数据的方式,最大化类内相似度(intro-group),最大化类间(inter-group)相似度 - 两种得到最优划分的方法 - 逐渐建立层次聚类 - 自底向上(Bottom-up, agglomerative): 逐渐将相似的类间的对象聚成更大的类 - 自顶向下(Top-down, divisive): 逐渐将数据划分成小的类 - 先随机聚类,然后迭代的优化(“flat” clustering, 比如,k-means)

下面介绍两种有代表性的方法: - Hierarchical Agglomerative Clustering (HAC),层次凝聚聚类 - k-means

HAC 层次凝聚聚类

算法思想: Agglomerative Hierarchical Clustering 那么,层次聚类应该如何计算类间的相似性呢?这个问题也可以是怎样计算类间的距离。 > - Single-link:又叫做 nearest-neighbor,就是取两个集合中距离最近的两个点的距离作为这两个集合的距离,容易造成一种叫做 Chaining 的效果,两个 cluster 明明从“大局”上离得比较远,但是由于其中个别的点距离比较近就被合并了,并且这样合并之后 Chaining 效应会进一步扩大,最后会得到比较松散的 cluster 。 > - Complete-link:这个则完全是 Single Linkage 的反面极端,取两个集合中距离最远的两个点的距离作为两个集合的距离。其效果也是刚好相反的,限制非常大,两个 cluster 即使已经很接近了,但是只要有不配合的点存在,就顽固到底,老死不相合并,也是不太好的办法。 > - Average-link:这种方法看起来相对有道理一些,也就是把两个集合中的点两两的距离全部放在一起求一个平均值,相对也能得到合适一点的结果。

Comparison of Single-Link, Complete-Link, and Average-Link

Comparison of Single-Link, Complete-Link, and Average-Link

K-Mean Cluster

算法思想: K-Means Clustering

Text Clustering: Evaluation

我们有许多种方式做text clustering,但是怎样才能知道哪一种方式最好呢?这就需要用到Evaluation。

Direct Evaluation of Text Clusters Direct Evaluation of Text Clusters

Indirect Evaluation of Text Clusters Indirect Evaluation of Text Clusters

Text Categorization: Motivation

文本对象是多样化的(e.g., 文章,段落,或者是文本的集合) 分类也可以是多样化的: - Internal:文本属性的分类,例如按照主题,情感的分类 - External:按照与文本有关联的或者有意义的实体分类(e.g., 作者)

一些文本分类的应用 - 新闻的分类,文章的分类 - 垃圾邮件检测,过滤 - 文章或Tweet所表达的情感分类 - 自动分类邮件 - 作者属性

不同问题对应的分类 - 二分类 Binary categorization - 垃圾邮件分类(是或不是) - 观点(正面或负面) - K-分类 - 主题分类(可能含有多个主题) - 邮件分类 - 层次分类 Hierarchical categorization - 连接分类 Joint categorization 但是在这中间,二分类是最基础的一个分类,可以支持所有分类

Text Categorization: Methods

朴素贝叶斯其实就是在理想状态下的贝叶斯,然而在大多数实际应用中,我们不可能得到符合完美假设条件。

Smoothing是一个通用的方法在评价language model中 为什么要使用Smoothing? - 解决数据稀疏的问题(有时候训练集可能会很小,导致zero prob) - 可以帮助我们合并先验知识 - 帮助我们得到不同的权值,比如 IDF weighting(不常见)

朴素贝叶斯分类和逻辑回归分类的关联

假设有两个类别,theta1和theta2,如果结果为正数,那么分类更有可能是在第一类。(其中使用log来避免过小的概率) Anatomy of Naïve Bayes Classifier

推广之后,我们可以用特征向量来表示一个文档,贝叶斯可以看作是general classifier的一个特例。这个形式和逻辑回归非常相似。 General form of bayes classifier

Reference

[1] C. Zhai and S. Massung, Text Data Management and Analysis: A Practical Introduction to Information Retrieval and Text Mining. ACM and Morgan & Claypool Publishers, 2016. Chapters 14 & 15. [2] Manning, Chris D., Prabhakar Raghavan, and Hinrich Schütze. Introduction to Information Retrieval. Cambridge: Cambridge University Press, 2007. Chapters 13-16. [3] Yang, Yiming. An Evaluation of Statistical Approaches to Text Categorization. Inf. Retr. 1, 1-2 (May 1999), 69-90. doi: 10.1023/A:1009982220290. [4] 漫谈 Clustering (5): Hierarchical Clustering