本文所用的案例是检索文档
1 检索文档及测量文档相似度的算法（Algorithms for retrieval and measuring similarity of documents）
1.1 词袋模型（Bag of words model）
最常用的的一个模型是词袋模型
它忽略了文档中单词的顺序信息，需要做的只是计算每个单词在文档中出现的次数，形成一个系数矩阵
例如：
有一段文字：“Carlos calls the sport futbol. Emily calls the sport soccer.”
词袋模型：
|some|Carlos|the|happy|tree|calls|sport|cat|futbol|dog|nine|soccer|Emily|…|
|-|-|-|-|-|-|-|-|-|-|-|-|-|
|0|1|2|0|0|2|2|0|1|0|0|1|1|…|
1.2 测量相似度（Measuring similarity）
- 归一化
用单词的统计向量，计算其欧几里得范数（即向量元素绝对值的平方和再开方）
归一化后的向量为原向量除以其范数
例：上一节例子中的向量归一化后为 [0,1/6,2/6,0,0,2/6,2/6,0,1/6,0,0,1/6,1/6] - 计算向量的数量积
1.3 利用 TF-IDF 优先考虑关键词（Prioritizing important words with TF-IDF）
有一些词出现频繁但并不关键，如“the，he，···”，还有一些词出现不多但是非常关键，如果优先考虑这些关键词，那么对文章的判断的准确性将大大提高
生僻词（rare word）：在语料库中少见
所以对每个单词，我们根据其在语料库中出现的次数来决定其权重
关键词（important words）：
- 局部常见（common locally）：在文档中频繁出现
- 全局罕见（rare globally）：在语料库中相对少见
描述关键词的特征，就是某种局部出现率和全局罕见率的权衡
TF-IDF（词频-逆向文件分析法）
- 统计词频（同本文 1.1 节，只是单词计数）
- 根据逆向文件频率计算权重
$$log{\frac{语料库中文档数}{1+包含我们关心的单词的文档数}}$$ - 词频 * 权重
我们来分析一下为什么是这个公式：
- 对一个非常常用的单词，它出现在很多文档中，那么权重为：
$$log{\frac{非常大的数}{1+非常大的数}} \approx log1 = 0$$
所以这个公式可以极大的减小出现频率极高的，在所有文档中都出现的单词的权重 - 对一个生僻词，那么权重为：
$$log{\frac{非常大的数}{1+较小的数}}$$
上述公式里的“1”是为了防止某些单词没有出现在语料库中的任何文档时发生错误，避免除以 0
例如：有 64 篇文章，其中 63 篇出现了单词“the”，3 篇出现了单词“Messi”
TF-IDF：
- [63,3,…]
- the: $log{\frac{64}{1+63}}=0$ ;Messi: $log{\frac{64}{1+3}}=log16$
- [0,20,…]
1.4 利用最近邻域搜索法检索相似文档（Retrieving similar documents using nearest neighbor search）
k - 近邻搜索（k - Nearest neighbor）：输出最相关的 k 篇不同的文章
需要建立一个优先队列来存放目前找到的 k 篇最相关的文档
2 聚类模型和算法（Clustering models and algorithms）
我们的目标是对语料库中的文章进行分组（聚类）
集群（cluster）：中心、形状、边界
2.1 k - means 聚类算法
假设：相似度 = 到集群中心的距离（越小越好）
之所以叫“k - means”，是因为最终将得到 k 个集群，并且可以知道每个集群的平均值
步骤：
- 初始化集群中心位置（Initialize cluster centers）
- 将每个点分配给离它最近的集群中心（Assign observations to closest cluster center）
这个步骤用到的算法叫做“沃罗诺伊镶嵌算法（Voronoi tessellation）” - 根据数据点的分配情况更新集群中心的位置，进行步骤 1
重复这个过程直到结果收敛
3 案例研究：检索维基百科文章
代码在这里