最近看完了 Willi Richert的《机器学习系统设计》。书虽然有点薄但也比较全，内容感觉有点偏文本处理，里面介绍了一些文本处理的方法和工具。综合起来看作为机器学习入门还是挺不错的，这里就简单记一下我做的笔记，方便回顾。书中的代码可以通过它说到的网站下载，这里是第2部分笔记。

第三章 文本的聚类

这一章主要开始介绍文本的一些处理方法，并介绍了一下聚类的基本知识。

数据集

20newsgroup数据集是机器学习中的一个标准数据集，他包含18288个帖子，来自不同的新闻组。如果我们假定每个新闻组是一个簇，那么很容易测试出聚类的方法是否有效。这个数据集可以从 MLComp 下载。scikit可以直接对从MLComp上下载的数据进行处理，非常方便。

词袋

使用聚类前，需要有一个评价两个文章相似度的指标。有一种比较文本相似度的方法是计算编辑距离，但使用编辑距离不够稳健，没有考虑词语的重新排列，而且计算时间较长。我们使用另一种更简单有效的方法来进行比较–词袋（bag-of-word）。它基于简单的词频统计；对每一个文档中的词语，将它出现次数记录下来并表示成一个向量。我们之后可以把他们当作特征向量在后续步骤中使用。这样聚类的流程就变为：

  1. 对每个文档提取重要特征，并针对每个文档存储为一个向量
  2. 在这些向量上进行聚类计算
  3. 确定每个带聚类文档所在的簇

使用scikit的CountVectorizer可以方便的完成词袋。

1
2
from sklearn.feature_extraction.text import CountVectorizer
vectorizer = CountVectorizer(min_df=1)

min_df是一个参数，表示统计出来的如果只出现过一次的词，全部丢掉。类似的还有max_df表示所有出现次数大于这个值的词全部丢掉。

相似度的计算

两个词向量之间的相似度计算方法：将两个词向量做差，得到的结果计算欧几里得范数($\sqrt{x_1^2+x_2^2+x_3^2+…+x_n^2}$)。使用scipy.linalg.norm()函数可以计算欧几里得范数（最小距离）。这样就得到了第一个相似度计算方法。

根据相似度的计算，可以知道词向量特征越明显，计算得到的相似度越准确，要求我们做到：

  1. 词语频次向量的归一化: 解决有很多词反复出现的问题，得到单位长度为1的向量
    原始词向量的每一项都除以该词向量的欧几里得范数（$||v||$ 其实可以看成是向量的绝对值）
  2. 删除不重要的词语（去停用词）
    像“most”，“a”，“an”这类没有实际意义的词称为停用词，这类词在各个文档中一般都有出现，但并不能突出文档的特征信息，所以把他们去掉来突出文档特征
  3. 词干处理
    对于英语来说，名词、动词这类词在不同的时态下会有不同，如名词的单复数，所有格形式，动词的现在时或过去时等。对于这种问题，可以通过词干处理得到统一的形式，常用的工具有nltk，在nltk中有不同的词干处理器，可以使用SnowballStemmer来进行处理。例如
1
2
3
4
In [0]: import nltk.stem
In [1]: s = nltk.stem.SnowballStemer('english')
In [2]: s.stem('graphics')
Out[0]: u'graphic'

这样在预处理阶段，需要先进行词干处理，再交给CountVectorizer来处理得到词向量。

  1. TF-IDF
    对于很多情况，有一些词语经常大量出现在某些特定环境中，这时他们对于区分不同文档的帮助很小，此时使用基于词频的词袋方法就会出现问题，于是我们采用基于TF-IDF的方法，统计并生成词向量，其中TF是词频，IDF把权重折扣考虑了进去。 他的效果就是词频很高的和词频很低的得分都比较低，处于中间部分的得分比较高。在scikit中，使用TfidfVectorizer(继承自CountVectorizer)可以直接统计基于TF-IDF的词向量。

这样我们的处理工作就做完了。

虽然词袋模型及其扩展简单有效，但仍然有一些缺点：

  1. 它并不涵盖词语之间的关联关系。采用之前的向量化方法，文本“Car hits wall”和“Wall hits car”具有相同的特征向量
  2. 它没法正确捕捉否定关系。例如，文本“I will eat ice cream”和“I will not eat ice cream”，尽管他们的意思截然相反，但从特征向量来看它们非常相似。这个问题其实很容易解决，只需要既统计单个词语，又考虑bigrams（成对的词语）或者trigrams（每三个词语）即可
  3. 对于拼写错误的词语会处理失败。尽管读者能够很清楚地意识到“database”和“databas”传递了相同的意思，但我们的方法却把他们当成完全不同的词语。同义词的表示可能也会带来问题。

虽然它有一些问题，但他的错误率还是可以接受的。

k-means聚类

k均值聚类在各个机器学习库中都有实现，他的主要流程如下：

  1. 初始化选出k个任意的样本，并把它们的特征向量当作这些簇的质心。
  2. 遍历所有其他的文本，并将按照离他们最近的质心所在的簇分配给他们。
  3. 计算各个簇内文本的质心。
  4. 如果新计算出来的质心跟原来的质心不同，则用新的质心重复上面2-4步，直到质心不再变化。

由于K-means方法需要随机初始化质心，如果初始质心选的好，则很快就能得到全局最优解，但如果质心选的不好，则可能不仅花费的时间较长，而且还很可能陷入局部最优解。这是k-means方法最大的问题。代码可以参考下面的来使用：

1
2
3
4
from sklearn.clusert import KMeans
num_clusters = 10 # 举个例子，k=10,有10个簇
km = KMeans(n_clusters = num_clusters, init = 'random', n_init = 1,verbose = 1)
km.fit(data) # 训练数据, 假设data是包含了已经提取好特征的n组数据

关于聚类的效果，sklearn中有一个sklearn.metrics的包，包含了各种不同的指标，用来衡量聚类的质量。

k-means算法改进

1. 算法的计算复杂度分析
首先，在样本分配阶段，需要计算kn次误差平方和，计算复杂度为 *O(knd)*。 其次在更新聚类中心阶段，计算复杂度为 *O(nd)*，如果迭代次数为 t， 则算法的计算复杂度为 *O(kndt)*。因此k-means针对样本个数n具有现行的计算复杂度，是一种非常有效的大树据聚类算法。

2. 聚类中心初始化的改进
k-means对聚类中心的初始化很敏感，不同初始值会带来不同的聚类结果，一种简单有效的改进方式是David Arthur提出的k-means++算法，概算法能有效的产生初始聚类中心，可以得 O(logk) 的近似解。k-means++的计算复杂度为O(knd) 没有增加过多的计算负担，同时可以更有效的近似到最优解。

3. 类别个数的自适应确定
由于k-means事先需要确定聚类个数k，不具备自适应选择能力，选择不合适的k值会严重影响聚类效果。ISODATA算法引入类别的合并和分开机制，通过计算误差平方和最小来实现聚类，能够自适应决定类别个数。在每一次迭代中，ISODATA算法首先在固定类别个数的情况下进行聚类，然后根据设定样本之间的距离阈值进行合并操作，并根据每一组类别中的样本协方差矩阵信息来判断是否分开。

4. 面向非标准正态分布或非均匀样本集的算法改进
k-means采取二次欧式距离作为相似性度量，并且假设误差服从标准的正态分布，因此k-means在处理非标准正态分布和非均匀样本集合时聚类效果较差。为了有效客服该局限性假设，k-means被推广到更广义的度量空间。经典的两种改进框架为Kernel k-means和谱聚类Spectral Clustering。

Kernel k-means将样本点$x_i$通过某种映射方式$x_i\rightarrow\phi(x_i)$到新的高维空间$\phi$，在该空间中样本点之间的内积可以通过对应的核函数进行计算，即：
$$k(x_i,x_j)=\phi(x_i)^T\phi(x_j)$$
借助核函数的存在，可以在新空间进行k-means聚类，样本之间的相似性度量就取决于核函数的选择。

谱聚类算法尝试着变换样本的度量空间，首先需要求取样本集合的仿射矩阵，然后计算仿射矩阵的特征向量，利用得到的特征向量进行k-means聚类。仿射矩阵的特征向量隐含地重新定义样本点的相似性。