搜索引擎的分析--分类分析

搜索引擎的分析 （系列之三） 【原创】 首先需要说明的是，目前主流的搜索引擎直观上并没有提供分类的功能，但是分类的功能的的确确在搜索引擎中大量的使用着。其实，举一个最简单的例子，目前Google提供了新闻检索(虽然还是BETA版 http://news.google.com) 就使用了这样的技术。同样Baidu也提供了新闻检索。   进入到了Google News的页面后，我们可以看到，google除了提供关键词的新闻检索之外，还提供了新闻的分类检索。新闻被分成了：商业、科技、体育、娱乐等等主题。我们知道搜索引擎的前端是一个网络Spider，做一个新闻的Spider并不需要多大的改动就可以下载各地主要新闻网站的新闻了。在新闻网页中（目前Google News好像还没有采用RSS的方式获得新闻，处理非结构化的数据似乎是Google的强项，呵呵），通过分析自动获得新闻的主题和内容（这个并不是像表面中那么简单，实际上包括了网页分析、相似分析等等，这里不进行深入讨论，以后有机会再说吧）。即使获得了文本的新闻内容，如何自动知道这个新闻属于那个类呢？   网页的分类大体上可以分成两个大的步骤：   第一个是训练过程 首先搜集关于各个分类的新闻内容（这个过程通常都是手工标注完成的） 将所有收集到的每个分类的内容进行分词（如果是英文的相对容易，如果是中文的，也有相关的算法。常用的主要是基于词表的正反向最长匹配、Markov模型等等，当然对于人名、地名还是需要一些特殊处理的） 然后将分词后的结果提取特征（这个过程的好坏直接决定了分类的效果，通常我们可以采用TF-IDF等算法，当然也可以采用一些变形算法，将一篇文章变成一个词向量） 如果有必要的话，可以对这个分类的向量组进行降维处理（KL变换或者DCT等等） 构造一个分类模型（常用的有Rocchio、Bayes和SVM） 第二个是识别过程 对于一个需要识别的新闻内容，进行分词（算法同训练过程中的第二步） 然后提取特征（算法同训练过程中的第三步） 如果有必要的话，可以对这个向量进行降维处理（算法同训练过程中的第四步） 根据分类模型比较这个向量和各个分类的距离 找出最短距离，如果这个距离小于某个预先设定的值，就算命中了这个分类 上面的第一个过程是非实时完成的，可以训练过一次，然后将这个训练的结果一直使用。第二步是需要实时完成的。为了达到更好的识别效果，往往对第二步识别出来的结果在进行人工标注（即进行人工判断，标出正确的和错误的），将这个标注的结果再返回到第一步重新训练，以达到更好的识别效果。通常来说，分类比聚类简单了许多，而且识别的Precision和Recall都不错。 Precision是指分类的准确度，一个分类识别出来的N篇文章有多少篇真正属于这个分类 Recall是指分类的完整度，N片属于这个分类的文章有多少个被识别出来了 识别效果的好坏主要是特征提取的好坏决定的，通常的方法是大量收集原始文本（文本的规模越大、覆盖面越广，效果就越好），我们搜集了大量的新闻站点内容、小说、评论等等，过滤后的净文本大约1GB作为训练的背景样本，然后收集大量的分类样本，进行TF-IDF运算。 分类模型算法中的SVM是主要使用的方法之一，目前应该也是识别效果最好的。关于SVM的相关理论可以参考 http://www.kernel-machines.org/ 还有一些是基于人工神经网络的分类方法，同样也有不错的识别效果，不过好像由于算法常常出现overfit的原因，现在用在这个方面的比较少了（关于神经网络的算法效果，由于没有做过试验，我也不十分确定，欢迎排砖）   当然，我们上面讨论的主要是针对新闻站点，实际上，同样的算法也当然可以运用在其它方面，例如：网页的分类（Google News, Baidu News）、垃圾邮件过滤（Foxmail中的垃圾邮件过滤就是采用Bayes算法实现的）、自动问答系统（ask.com）等等。   南国暖风原创