中国科学技术大学：《信息检索与数据挖掘》课程教学资源（课件讲稿）第11章 文本聚类

信息检索与数据挖掘 2019/4/28 1 信息检索与数据挖掘 第11章文本聚类

信息检索与数据挖掘 2019/4/28 1 信息检索与数据挖掘 第11章 文本聚类

信息检索与数据挖掘 2019/4/28 3 本讲内容：文本聚类 ·聚类概述 ·什么是聚类？在R中如何用聚类？聚类的几个术语 ·K-均值聚类算法 ·K-均值聚类中的基本准则 ·K-均值算法中簇的个数 ·聚类评价 ·purity、NMI(Normalized Mutual Information,)、RI(Rand Index)、F measure ·基于模型的聚类 ·层次聚类简介 ·层次聚类的簇相似度计算 ·四种HAC算法：单连接、全连接、组平均、质心法

信息检索与数据挖掘 2019/4/28 3 本讲内容：文本聚类 • 聚类概述 • 什么是聚类？在IR中如何用聚类？聚类的几个术语 • K-均值聚类算法 • K-均值聚类中的基本准则 • K-均值算法中簇的个数 • 聚类评价 • purity、NMI（Normalized Mutual Information，)、RI（Rand Index)、F measure • 基于模型的聚类 • 层次聚类简介 • 层次聚类的簇相似度计算 • 四种HAC算法：单连接、全连接 、组平均、质心法

信息检索与数据挖掘 2019/4/28 4 聚类(Clustering)的定义 ·(文档)聚类是将一系列文档按照相似性聚团成子集 或者簇(cluster)的过程 ·簇内文档之间应该彼此相似 •簇间文档之间相似度不大 ·聚类是一种最常见的无监督学习(unsupervised learning)方法 ·无监督意味着没有已标注好的数据集 拉道

信息检索与数据挖掘 2019/4/28 4 聚类(Clustering)的定义 • (文档)聚类是将一系列文档按照相似性聚团成子集 或者簇(cluster)的过程 • 簇内文档之间应该彼此相似 • 簇间文档之间相似度不大 • 聚类是一种最常见的无监督学习(unsupervised learning)方法 • 无监督意味着没有已标注好的数据集

信息检索与数据挖掘 2019/4/28 5 回顾示例3：文档-词项矩阵SVD分解 词项、文档的聚类 奇异值分解就是把上面这样一个大矩阵，分解成三个小矩阵相乘，如下图 所示。比如把上面的例子中的矩阵分解成一个一百万乘以一百的矩阵X, 一个一百乘以一百的矩阵B,和一个一百乘以五十万的矩阵Y。这三个矩阵 的元素总数加起来也不过1.5亿，仅仅是原来的三千分之一。相应的存储量 和计算量都会小三个数量级以上。 B X 100·100100*500000 1.Dd0.e0503.c00 100.000·100 三个矩阵有非常清楚的物理含义。第一个矩阵X中的每一行表示意思相关 的一类词，其中的每个非零元素表示这类词中每个词的重要性（或者说 相关性)，数值越大越相关。最后一个矩阵Y中的每一列表示同一主题 一类文章，其中每个元素表示这类文章中每篇文章的相关性。中间的矩 阵则表示类词和文章之间的相关性。因此，我们只要对关联矩阵A进 行一次奇异值分解，我们就可以同时完成了近义词分类和文章的分类

信息检索与数据挖掘 2019/4/28 5 回顾 示例3：文档-词项矩阵SVD分解 词项、文档的聚类 奇异值分解就是把上面这样一个大矩阵，分解成三个小矩阵相乘，如下图 所示。比如把上面的例子中的矩阵分解成一个一百万乘以一百的矩阵X， 一个一百乘以一百的矩阵B，和一个一百乘以五十万的矩阵Y。这三个矩阵 的元素总数加起来也不过1.5亿，仅仅是原来的三千分之一。相应的存储量 和计算量都会小三个数量级以上。 三个矩阵有非常清楚的物理含义。第一个矩阵X中的每一行表示意思相关 的一类词，其中的每个非零元素表示这类词中每个词的重要性（或者说 相关性），数值越大越相关。最后一个矩阵Y中的每一列表示同一主题 一类文章，其中每个元素表示这类文章中每篇文章的相关性。中间的矩 阵则表示类词和文章之间的相关性。因此，我们只要对关联矩阵A进 行一次奇异值分解，我们就可以同时完成了近义词分类和文章的分类

信息检索与数据挖掘 2019/4/28 8 一个具有清晰簇结构的数据集 •聚类算法的一个关键输 入是距离计算方法。图中， 计算距离时采用的是二维 O ● 平面上的距离计算方法。 基于这种距离计算方法在 o 图中得出了三个不同的簇。 在文档聚类当中，距离计 算方法往往采用欧氏距离。 o •不同的距离计算方法会 导致不同的聚类效果。因 ● 此，距离的计算方法是影 8 000 响聚类结果的一个重要因 素。 0.0 0.5 1.0 1.5 2.0

信息检索与数据挖掘 2019/4/28 8 一个具有清晰簇结构的数据集 •聚类算法的一个关键输 入是距离计算方法。图中， 计算距离时采用的是二维 平面上的距离计算方法。 基于这种距离计算方法在 图中得出了三个不同的簇。 在文档聚类当中，距离计 算方法往往采用欧氏距离。 •不同的距离计算方法会 导致不同的聚类效果。因 此，距离的计算方法是影 响聚类结果的一个重要因 素

信息检索与数据挖掘 2019/4/28 9 分类vs.聚类 ·分类：有监督的学习 。聚类：无监督的学习 。分类：类别事先人工定义好，并且是学习算法的输 入的一部分 ·聚类：簇在没有人工输入的情况下从数据中推理而 得 ·但是，很多因素会影响聚类的输出结果：簇的个数、相 似度计算方法、文档的表示方式，等等 乍看起来，聚类和分类的区别并不大，两种任务都会将文档分到不同的组中。 然而，这两个问题之间存在着本质的差异。分类是监督学习的一种形式，其 目标是对人类赋予数据的类别差异进行学习或复制。而在以聚类为重要代表 的无监督学习当中，并没有这样的人来对类别的差异进行引导

信息检索与数据挖掘 2019/4/28 9 分类 vs. 聚类 • 分类：有监督的学习 • 聚类：无监督的学习 • 分类：类别事先人工定义好，并且是学习算法的输 入的一部分 • 聚类：簇在没有人工输入的情况下从数据中推理而 得 • 但是，很多因素会影响聚类的输出结果：簇的个数、相 似度计算方法、文档的表示方式，等等 乍看起来，聚类和分类的区别并不大，两种任务都会将文档分到不同的组中。 然而，这两个问题之间存在着本质的差异。分类是监督学习的一种形式，其 目标是对人类赋予数据的类别差异进行学习或复制。而在以聚类为重要代表 的无监督学习当中，并没有这样的人来对类别的差异进行引导

信息检索与数据挖掘 2019/4/28 10 聚类假设 聚类假设：在考虑文档和信息需求之间的相关性时，同一 簇中的文档表现互相类似 ·聚类在R中的所有应用都直接或间接基于上述聚类假设 ·Van Rijsbergent的原始定义：closely associated documents tend to be relevant to the same requests'”(彼此密切关联的文 档和同一信息需求相关 聚类假设所表达的是，如果簇中某篇文档和查询需求相关， 那么同一簇中的其他文档也和查询需求相关。这是因为聚类 算法将那些共有很多词项的文档聚在一起。聚类假设实质上 就是第14章的邻近假设。两种情况下，我们都认为内容相 似的文档在相关性上的表现也相似

信息检索与数据挖掘 2019/4/28 10 聚类假设 • 聚类假设：在考虑文档和信息需求之间的相关性时，同一 簇中的文档表现互相类似。 • 聚类在IR中的所有应用都直接或间接基于上述聚类假设 • Van Rijsbergen的原始定义: “closely associated documents tend to be relevant to the same requests” （彼此密切关联的文 档和同一信息需求相关） 聚类假设所表达的是，如果簇中某篇文档和查询需求相关， 那么同一簇中的其他文档也和查询需求相关。这是因为聚类 算法将那些共有很多词项的文档聚在一起。聚类假设实质上 就是第14 章的邻近假设。两种情况下，我们都认为内容相 似的文档在相关性上的表现也相似

信息检索与数据挖掘 2019/4/28 11 C.J.van Rijsbergen C.J."Keith"van Rijsbergen (Cornelis Joost van Rijsbergen)(born 1943)is a professor of computer science and the leader of the Glasgow Information Retrieval Group based at the University of Glasgow. He is one of the founders of modern Information Retrieval and the author of the seminal monograph Information Retrieval and of the textbook The Geometry of Information Retrieval. In 2003 he was inducted as a Fellow of the Association for Computing Machinery.In 2004 he was awarded the Tony Kent Strix award.In 2006,he was awarded the Gerard Salton Award for Quantum haystacks. http://en.wikipedia.org/wiki/C.J._van_Rijsbergen http://www.dcs.gla.ac.uk/-keith/

信息检索与数据挖掘 2019/4/28 11 C. J. van Rijsbergen http://en.wikipedia.org/wiki/C._J._van_Rijsbergen http://www.dcs.gla.ac.uk/~keith/ C. J. "Keith" van Rijsbergen (Cornelis Joost van Rijsbergen) (born 1943) is a professor of computer science and the leader of the Glasgow Information Retrieval Group based at the University of Glasgow. He is one of the founders of modern Information Retrieval and the author of the seminal monograph Information Retrieval and of the textbook The Geometry of Information Retrieval. In 2003 he was inducted as a Fellow of the Association for Computing Machinery. In 2004 he was awarded the Tony Kent Strix award. In 2006, he was awarded the Gerard Salton Award for Quantum haystacks

信息检索与数据挖掘 2019/4/28 12 聚类在R中的应用 应用 聚类对象 优点 搜索结果聚类 搜索结果 提供面向用户的更有效 的展示 “分散一集中”界面 提供了另一种用户界面， 文档集和文档子集 即不需要人工输入关键 词的搜索界面 提供了一种面向探索式 文档集聚类 文档集 浏览的有效的信息展示 方法 基于语言建模的IR文档 提高了正确率和/或召回 集 文档集 率 基于聚类的检索 文档集 加快了搜索的速度

信息检索与数据挖掘 2019/4/28 12 聚类在IR中的应用 应 用 聚类对象 优 点 搜索结果聚类 搜索结果 提供面向用户的更有效 的展示 “分散—集中”界面 文档集和文档子集 提供了另一种用户界面， 即不需要人工输入关键 词的搜索界面 文档集聚类 文档集 提供了一种面向探索式 浏览的有效的信息展示 方法 基于语言建模的IR文档 集 文档集 提高了正确率和/或召回 率 基于聚类的检索 文档集 加快了搜索的速度

信息检索与数据挖掘 2019/4/28 13 Yahoo!目录式检索的效果 ..(30) ★ agriculture biology physics cs space dairy crops botany cell Al courses craft magnetism forestry agronomy evolution HCI missions relativity Hierarchy isnt clustering but is the kind of output you want from clustering

信息检索与数据挖掘 2019/4/28 13 Yahoo! 目录式检索的效果 dairy crops agronomy forestry AI HCI craft missions botany evolution cell magnetism relativity courses agriculture biology physics CS space ... ... ... … (30) ... ... Hierarchy isn’t clustering but is the kind of output you want from clustering