Google的吴军研究员写了数学之美系列,其中有“余弦定律与新闻的分类”和”矩阵运算和文本处理中的分类问题“对自动分类、相似度、去重等相关问题原理作了介绍,并找到一些相关算法:
余弦定律与新闻的分类
Google 的新闻是自动分类和整理的。所谓新闻的分类无非是要把相似的新闻放到一类中。计算机其实读不懂新闻,它只能快速计算。这就要求我们设计一个算法来算出任意两篇新闻的相似性。为了做到这一点,我们需要想办法用一组数字来描述一篇新闻。
我们来看看怎样找一组数字,或者说一个向量来描述一篇新闻。回忆一下我们在“如何度量网页相关性” 一文中介绍的TF/IDF 的概念。对于一篇新闻中的所有实词,我们可以计算出它们的单文本词汇频率/逆文本频率值(TF/IDF)。不难想象,和新闻主题有关的那些实词频率高, TF/IDF 值很大。我们按照这些实词在词汇表的位置对它们的 TF/IDF 值排序。比如,词汇表有六万四千个词,分别为
单词编号 汉字词
------------------
1 阿
2 啊
3 阿斗
4 阿姨
...
789 服装
....
64000 做作
在一篇新闻中,这 64,000 个词的 TF/IDF 值分别为
单词编号 TF/IDF 值
==============
1 0
2 0.0034
3 0
4 0.00052
5 0
...
789 0.034
...
64000 0.075
如果单词表中的某个次在新闻中没有出现,对应的值为零,那么这 64,000 个数,组成一个64,000维的向量。我们就用这个向量来代表这篇新闻,并成为新闻的特征向量。如果两篇新闻的特征向量相近,则对应的新闻内容相似,它们应当归在一类,反之亦然。
学过向量代数的人都知道,向量实际上是多维空间中有方向的线段。如果两个向量的方向一致,即夹角接近零,那么这两个向量就相近。而要确定两个向量方向是否一致,这就要用到余弦定理计算向量的夹角了。
当两条新闻向量夹角的余弦等于一时,这两条新闻完全重复(用这个办法可以删除重复的网页);当夹角的余弦接近于一时,两条新闻相似,从而可以归成一类;夹角的余弦越小,两条新闻越不相关。
矩阵运算和文本处理中的分类问题
分类的关键是计算相关性。我们首先对两个文本计算出它们的内容词,或者说实词的向量,然后求这两个向量的夹角。当这两个向量夹角为零时,新闻就相关;当它 们垂直或者说正交时,新闻则无关。当然,夹角的余弦等同于向量的内积。从理论上讲,这种算法非常好。但是计算时间特别长。通常,我们要处理的文章的数量都 很大,至少在百万篇以上,二次回标有非常长,比如说有五十万个词(包括人名地名产品名称等等)。如果想通过对一百万篇文章两篇两篇地成对比较,来找出所有 共同主题的文章,就要比较五千亿对文章。现在的计算机一秒钟最多可以比较一千对文章,完成这一百万篇文章相关性比较就需要十五年时间。注意,要真正完成文 章的分类还要反复重复上述计算。
在文本分类中,另一种办法是利用矩阵运算中的奇异值分解(Singular Value Decomposition,简称 SVD)。现在让我们来看看奇异值分解是怎么回事。首先,我们可以用一个大矩阵A来描述这一百万篇文章和五十万词的关联性。这个矩阵中,每一行对应一篇文 章,每一列对应一个词。
在上面的图中,M=1,000,000,N=500,000。第 i 行,第 j 列的元素,是字典中第 j 个词在第 i 篇文章中出现的加权词频(比如,TF/IDF)。读者可能已经注意到了,这个矩阵非常大,有一百万乘以五十万,即五千亿个元素。
奇 异值分解就是把上面这样一个大矩阵,分解成三个小矩阵相乘,如下图所示。比如把上面的例子中的矩阵分解成一个一百万乘以一百的矩阵X,一个一百乘以一百的 矩阵B,和一个一百乘以五十万的矩阵Y。这三个矩阵的元素总数加起来也不过1.5亿,仅仅是原来的三千分之一。相应的存储量和计算量都会小三个数量级以上。
三个矩阵有非常清楚的物理含义。第一个矩阵X中的每一行表示意思相关的一类词,其中的每个非零元素表示这类词中每个词的重要性(或者说相关性),数值越大 越相关。最后一个矩阵Y中的每一列表示同一主题一类文章,其中每个元素表示这类文章中每篇文章的相关性。中间的矩阵则表示类词和文章雷之间的相关性。因 此,我们只要对关联矩阵A进行一次奇异值分解,w 我们就可以同时完成了近义词分类和文章的分类。(同时得到每类文章和每类词的相关性)。
现在剩下的唯一问题,就是如何用计算机进行奇异值分解。这时,线性代数中的许多概念,比如矩阵的特征值等等,以及数值分析的各种算法就统统用上了。在很长时 间内,奇异值分解都无法并行处理。(虽然 Google 早就有了MapReduce 等并行计算的工具,但是由于奇异值分解很难拆成不相关子运算,即使在 Google 内部以前也无法利用并行计算的优势来分解矩阵。)最近,Google 中国的张智威博士和几个中国的工程师及实习生已经实现了奇异值分解的并行算法,我认为这是 Google 中国对世界的一个贡献。
相关算法
LSH, PartEnum, ALLPair and Google's
from: http://hi.baidu.com/arrowapex/blog/item/5a41dcd400af1903a18bb78d.html
分享到:
相关推荐
### 基于小波变换的红外和可见光图像融合算法的研究 #### 一、引言 随着图像处理技术的发展,图像融合作为一种重要的图像处理手段,已经在诸多领域得到了广泛的应用,如军事侦察、医学诊断、遥感监测等。其中,...
base zz zz zz zz zz base zz zz zz zz zz base zz zz zz zz zz base zz zz zz zz zz
朴素贝叶斯算法是一种基于概率的分类方法,它在机器学习领域被广泛应用。该算法假设特征之间相互独立...在实际应用中,还需要考虑如何处理异常值、优化模型参数以及应对不平衡数据集等问题,以提升模型的性能和实用性。
这通常可以通过哈希表、字典树(Trie树)等数据结构实现,这些结构可以帮助快速查找和匹配字符串。 2. 比较和排序:算法可能还需要对找到的重复项进行比较,以确定它们是否完全一致,或者仅是相似但不相同。 3. ...
遗传算法是一种受达尔文生物进化理论启发的搜索启发式算法,常用于解决优化和搜索问题。它通过模拟自然选择和遗传学中的机制来迭代地改进解集。遗传算法原理及应用是一个专门研究这种算法的理论基础以及实际应用的...
模型算法是指使用数学模型和计算方法来解决特定问题的一套规则和步骤,它们在数据挖掘、机器学习等领域中具有重要地位。统计分析则是指运用统计学原理和方法对数据进行整理、分析、解释和预测的过程。 模型算法统计...
在物流行业中,3D bin packing(三维箱包装)问题是一个重要的优化问题,它涉及到如何高效地将各种形状和尺寸的物体放入最小数量的箱子中,以节省存储和运输空间。"Best Fit"算法是一种常见的启发式策略,用于解决这...
在物流行业中,3D bin packing(三维箱包装)问题是一个重要的优化问题,它涉及到如何高效地将各种形状和尺寸的物体放入最小数量的容器(如箱子)中,以节省存储和运输成本。在这个问题中,First Fit 和 Best Fit 是...
5. 综合性问题:这涉及到物理理论与算法的综合应用,如通过算法优化对某个物理过程进行模拟,或者用算法来分析和优化物理实验结果等。 算法文档中通常不会包含具体的代码实现,而是提供算法的理论基础、数学模型、...
在物流行业中,3D bin packing问题是一个典型的优化问题,它涉及到...这个项目的源代码(3d-bin-packing-GA)可以作为一个学习和研究遗传算法在实际问题中应用的实例,帮助读者更好地理解和掌握这种强大的优化工具。
【标题】"zz.rar_hungarian algorithm_匈牙利_匈牙利算法"涉及的核心知识点是匈牙利算法,这是一门在图论中的优化算法,主要用于解决匹配问题,特别是指二分图的最大匹配问题。在计算机科学和运筹学中,匈牙利算法...
在MATLAB中实现这些算法,可以帮助用户解决诸如数据拟合、预测、自动控制、分类和聚类分析等复杂问题。 ### MATLAB中的智能算法实现 在MATLAB中实现智能算法,往往需要编写特定的函数或者使用内置的函数库。用户...
【51单片机实现的zz自动避障小车】是一个典型的计算机类毕业设计项目,主要涉及了嵌入式系统中的单片机编程技术。51单片机是微控制器的一种,广泛应用于各种电子设备中,尤其是对于初学者,它是学习嵌入式系统的基础...
常用的度量方法有欧几里得距离、曼哈顿距离和余弦相似度等。 2. 选择邻居:根据距离的大小,选取最近的K个样本作为邻居。 3. 决策边界:统计这K个邻居中各分类出现的频率,选择出现最多的类别作为未知样本的预测...
2. 算法分类:通常算法可以分为基本算法、排序算法、搜索算法、图算法、动态规划、分治算法、贪心算法、回溯算法等多种类型。《算法竞赛入门经典》一书涵盖了这些基础的算法类型,帮助读者全面认识和学习。 3. 数据...
遗传算法的基本原理是通过迭代过程不断地在解空间中搜索,通过选择、交叉(杂交)和变异三个主要操作来产生新一代的解。 在MATLAB中实现遗传算法时,通常需要进行以下几个步骤的操作: 1. 表示(Representation)...
现代通信原理考试试题zz现代通信原理考试试题zz
由于给定的文件信息中没有包含足够的内容来生成详细知识点,我将基于标题和描述中提到的主题“PID算法原理及调整规律”提供一份详尽的介绍。 PID(比例-积分-微分)控制器是一种常见的反馈回路控制器,广泛应用于...
PID控制器是一种常见的反馈控制器,广泛应用于工业控制系统中,用于控制电机、阀门等各种机械和电气系统的运行。PID是比例(Proportional)、积分(Integral)、微分(Derivative)三个英文单词首字母的缩写,分别...