4- 聚类和相似度模型

聚类和相似度: 文档检索

我们想从数据中推断出某种潜在的结构。
结构是一组相关观测。对于一个实际应用进行研究。

检索感兴趣的文档。

文件检索

目前正在阅读你喜欢的文章
目标： 找出另一篇你可能感兴趣的文章

一种能自动检测出他感兴趣文章的方法。

面临的挑战

• 我们如何衡量相似度
• 如何在文章中进行搜索，找出下一篇它可能读的文章呢

用于测量相似度的单词计数表示

文档的单词计数表示

词袋模型

- 忽略单词的顺序

把所有单词拿出来扔进这个口袋摇一摇，打乱了单词的顺序。

- 对单词表中的每一个单词计数

对于上面句子我们进行考虑。我们定义了一个向量。

我们具有一个

如上图所示的向量表。单词与他出现的次数共同构成了一个向量。

这是一个稀疏向量。因为我们会有的单词只是其中的少数。

度量文档的相似度

假设对于这篇关于足球的文章。
我们对于两个向量进行点乘。这样可以计算出大家都有的单词数值。

只要对应位置一方为0，那么对应点乘这一项为0.

1*3 + 5*2 = 13

单词计数的问题 -文档长度

我们文章的字数如果增加为原来的两倍。也就是将复制了一遍的文档加入其中进行比较

那么我们的文档的相似度竟然变成52了。

内容之间的联系其实没有变，但是文章变长之后，联系变得更深了。

解决方法 归一化

计算向量的范数

计算出每一项向量值的数的平方的和。然后取其平方根。

得到的归一化之后的向量如图所示。使得我们将不同文章的数量置于同等地位

应用tf-idf 对于重要单词进行优先级排序

上次的归一化处理，解决了我们的文档长度对于单词的影响。

单词计数的问题 - 生僻字

我们所说的常用词语指语料库中出现频率高的词。

语料库：指我们在检索时查看的所有文档的总和。

常用词决定了我们文档间相似度的度量。

与之对应的是文档中的生僻词。

常用单词会淹没生僻单词。

什么是生僻词的特征？

• 在语料库中看起来出现频率不高

偏重于在少量文档中出现的单词

• 同样的，通过他们在以下量值缩放单词w
  包含w的文档数量

也就是包含w的文档越多，说明w越不重要。是一个常用词那么我们对它的次数进行缩放。

也就是除以他在多少个文档出现了。

关键词

只有生僻词才最重要么？

什么是关键词的特征？

• 在文档中频繁出现(局部常见)
• 在语料库中罕见出现(全局罕见)

个人思考: 提取出主题，与主题相关的。

关键词的特征就是 局部常见和全局罕见的平衡。

Tf-idf 文档表示

词频 逆向文档频率

词频 考虑局部情况 某人正在阅读的文章。

只是简单的统计该词出现的次数。

通过逆向文档频率来减少出现在很多文档的词的权重。

所以我们要考虑语料库中的所有文档:

语料库中的文档数除以(1+包含单词的文档)，再取商的对数。

这个数对于一个太多频繁出现的单词，后面值约为1，取了对数就是0了。
极大的减少在所有文档中都出现的单词的权重。直到极端情况0.

与之相反的是如果我们有一个生僻词，我们将计算出一个非常大的数。

一个非常的数，除以一个1+较小的数之商的对数。结果会较大。

之所以数字1出现在公式的下方。是因为我们无法假设每个单词都会出现在语料库的文档中。避免除0错误。

单词 the只在其中一篇文档没出现。所以单词the的权重完全减少到0.

梅西这个单词出现在3篇文档中。此时它的逆向文档频率将会是4。

简单的将两个向量相乘即可得到

tf * idf

常用词的权重减少了，而生僻词的权重增加了。

检索相似的文档

推荐文章

最近邻域搜索

查询文档: 正在阅读的文章。

语料库: 搜索文章时我们拥有的文章的总和。

为了实现最近的邻域搜索，我们需要定义一个距离

指定: 距离度量
输出: 最相似文档集合

特例: 1- 最邻近

输入: 查询文档
输出: 最相似的一篇文章

算法:
- 在语料库中搜索每个文档
- 计算 s = similarity(查询文档，语料库中某个文档)
- if s > Best_s, record 最相似文档就是当前文档。设定Best_s = s
当遍历完成之后，返回最优的推荐。

K - 最邻近

只需要将收集最终结果的best_s 换成一个列表。控制列表的len为k

文档聚类

对于相关联的文档进行聚类。

不是所有的文章都已经被标记好了。我们只有一堆文章。我们想找到文章中的潜在分类方法。

• 根据主题对文档分组
• 发现相似文档的组

如果一些标签已知会怎样？

已知标签文档的训练集:

这是一个多元分类问题

如果是上面这样，这是一个监督学习的例子。

聚类

不提供标签
想要发现集群结构

输入； 作为向量的文档。

我们假定这是一些只包含两个单词的文档。下图中横轴代表单词一数量，纵轴代表单词二数量。

现实中的文档拥有很多单词，他们会在高维空间中分布。

输出: 集群的标签

个人思考: 中间的可以被打上多个标签

事后人工回溯； 发现聚出来的类的真实标签。

这是一个无监督学习任务，因为我们的任务不需要任何给定的标签。
我们只使用到了观测量本身。

什么定义了集群

集群通过特定的集群中心和形状定义。

把观测(文档 ) 分配给集群 (主题标签)

• 把这个集群中的分数高于在其他聚类中的分数

• 通常， 与本集群中心点比其他集群中心点更相似。

• 鼠标所在位置的点因为更符合绿色集群向外扩张的形状。

另一种方法可以只看观测点到集群中心的距离。

K- 均值

它只用到了和集群中心点的距离。

假设: 相似性度量 = 与集群中心点的距离(越小越好)

以最终将得到k个集群的假设出发:

个人思考优化点； k的决定。

会看每个集群的平均值，只考虑集群的中心。
以此来将数据点分到不同的集群中。

初始化算法

很多方法来初始化集群中心的位置

暂时假设我们会随机选出三个不同的集群中心。

将观测分配给最近的中心点，判定的算法叫做沃罗诺伊向前算法

圆圈是集群中心。

由于初始的集群中心都是随机生成的。

• 将集群中心修改为被分配给原中心点观测的均值。

通过更新后的集群中心重新绘制。

一直重复这个过程直到结果收敛。

其他聚类例子

• 图像搜索:

聚类对于结构搜索颇有帮助

• 通过病况来分组病人

更好地表征疾病亚种和疾病

举例来说我们可以锁定一组癫痫患者。

癫痫发病的记录。

• Amazon 中的商品

从购买历史中发现未标定的商品类别。

婴儿车人为的只加上了家具的标签。但是我们可以从购买历史中发现更好的标签可能是baby

也可以发现用户群体，对于这些用户的定向产品推荐。

• 组织网页搜索结果

搜索的项可能有很多意思

使用聚类组织输出结果。

个人思考：遇到有明显多个聚类中心的，将输出结果聚类，提取关键词。

• 发现相似的邻居

• 估计一个小区域的价格。

挑战:

- 每个月对于每个区域只有很少的销售数据。

解决方案:

把有相似趋势的地区进行聚类然后在集群汇总共享信息。

• 预测暴力犯罪以便更好的协调分配警力。

开始编码实现。

我们已经讨论了一个文档检索的任务。
还讨论了一个聚类的概念用来揭示数据的潜在结构。
还谈到了一些聚类这个概念有用武之地的领域。

如上图所示是一个聚类算法的工作流程(与前几次的图不一样):

• 训练数据是用来进行文档聚类的文档代号和文本表

所以我们有一堆文档以及与他们对应的文本。

• 我们将会提取一些特征量。我们前面提到了一些描绘一个文档的不同方法。
  • 本例子中我们用到一个tf-idf的方法
  • 中文名全称词频-逆文档频率法

我们要通过这个表示方法对于我们的文档进行聚类。

• 所以我们把这些特征量放入到一些机器学习的模型中。

• 使用聚类模型，对于每个文档输出一个集群标签。

输出量y帽子就是我们的集群标签，因为我们打算评估我们聚类结果的准确度。
当然这里我们并没有真正的集群标签。因此还是将其称为预测或预估标签。

我们并没有一个可以用来比对的真实标签，也就是上图中的y并不存在。因为我们的设定是无监督式学习。

我们需要一种方法来评估我们的聚类准确度。我们准确度的度量方法也就是我们用来测量评估的是聚类的一致性。我们会测量每个观测点到他所在集群中心的距离，一个好的聚类算法中这些距离会很小。我们的目标是最小化这些距离。我们的准确度就是要测量这些距离，我们需要我们的原始数据，需要词频逆文档频率。所以那些值会从质量评估的右侧输入。然后我们还需要集群中心，所以这个w帽子也就是我们的当前估计值。是我们的模型参数。当然我们也需要用w帽子来测算距离。因此与其用真实标签评测准确度，不如用文档标识和集群中心。把原始数据输入到质量度量中用于计算到集群中心的距离(这是我们计算误差的度量，虽然它其实不是误差只是估计量)。我们的算法是k均值算法。

k均值是在试着最小化观测点到集群中心的距离，或者说这些距离的总和。

最小化的方式是通过不断的迭代循环，我们把w帽子不断更新成新的w帽子。用来表示观测点的新的质量中心，因此中心点会发生偏移。

我们拿到原始数据使用某种方法进行表示，可以是单词统计量，可以是词频逆文档频率，或者是这些数据的标准化值。用二元，三元词组来表示我们的文件，然后我们的聚类算法(如kmeans可以输出集群标签)，并且我们可以通过迭代来一次次的更新集群中心。也就是这个聚类模型的参数，迭代更新的依据是观测量到集群中心的距离。

大家学到了

详细的讲解了一些算法的背后细节。讨论了k均值算法和文件检索问题。相邻社区检索问题。并提供了解决问题的算法细节。尝试搭建一个新闻稿件检索系统。

• 表示文档的描述方法
• 度量两个文档中的相似性
• 讨论关于应用单词计数的问题
  • 通过标准化计数来适应文档的长度
  • 通过tf-idf 来强调关键词
• 描述聚类算法中的输入( 无标签预测)与输出(标签)

判断一个任务是监督的还是非监督的。
使用k-均值进行文档聚类。描述聚类的其他应用。

实践编码

见jupyter notebook