NLPJob

标签热度

机器学习 coursera 斯坦福大学 公开课 斯坦福 深度学习 自然语言处理 python 数据科学 andrew ng 数学 nlp 数据分析 数据挖掘 神经网络 大数据 计算机科学 英语 算法 deep learning 统计学 课件 数据可视化 机器学习公开课 机器学习笔记 google 机器学习视频 计算机 商业 推荐系统 数据结构 r语言 java 密码学 udacity 金融 免费电子书 电子书 公开课笔记 计算机视觉 商务英语 学术英语 python数据可视化 机器学习课程 机器人 ted 文本挖掘 r 视频 领导力 java编程 回归模型 excel 深度学习课程 mysql cousera公开课 统计 大数据公开课 ted公开课 ted演讲 线性回归 javascript mit 概率图模型 金融市场 tensorflow 学习英语 物联网 大数据专项课程 python入门 大数据课程 英语写作 英语学习 算法课程 强化学习 高级机器学习 kaggle 文本分析 机器学习资料 函数式编程 scala 游戏设计 cousera 机器学习系统 机器人公开课 开源代码 人工智能 普林斯顿大学 machine learning 线性代数 代价函数 软件工程 伯克利 管理 市场营销 财务会计 沃顿商学院 网页开发 网站开发 web开发 网络安全 python数据科学 商业分析 非对称密码学 对称密码学 应用密码学 大规模数据科学 英语听说 概率 机器学习基石 python机器学习 算法公开课 源代码 数学思维 社交网络分析 微积分公开课 杜克大学 机器学习公开课视频 公开课视频 coursera公开课视频 coursera公开课 贝叶斯 信息论 离散数学 宾夕法尼亚大学 neural networks 伯克利大学 密歇根大学 成本函数 梯度下降 云计算 编译器 自动机 cs101 daphne koller spark 软件 会计 英语交流 商业策略 风险管理 资产管理 地理信息系统 gis 卷积神经网络 面向对象编程 序列模型 移动应用开发 数据库 计算机通信 敏捷开发 高级商务分析 商务分析 商务英语课程 c语言 c++ 数据管理 投资 计算原理 计算基础 推荐系统导论 学术英语写作 android应用开发 android开发 android 机器人课程 机器人学 数据科学竞赛 yandex 深度学习公开课 深度学习书籍 数据集 机器学习资源 分布式 微积分 大规模机器学习系统 统计推断 数据科学公开课 游戏 数学思维公开课 机器学习课件 数学公开课 微积分公开课视频 微积分公开课下载 mit微积分 mit公开课 龙星计划 神经网络公开课 coursera视频 斯坦福公开课 windows ios udacity公开课 无人驾驶汽车 人机交互公开课 人机交互 正则化 过拟合 逻辑回归 模型思维 网易公开课 acl net 逻辑 cmu 情感分析 我爱公开课 引言 普林斯顿 经济 saas 52opencourse 逻辑导引 图模型 chirs manning dan jurafsky ppt 编码 时间序列 go语言课程 go语言 工程师 语法 区块链基础 区块链 网页设计 软件开发 商务基础 运营管理 商务 机器学习实战 数据系统 投资管理 swift 计算机安全与系统管理 系统管理 计算机安全 seo策略 seo工具 seo 组织领导力 css3 html5 会计基础 c sharp 英语沟通 并发 并行 全栈开发 数据仓库 商业智能 投资策略 金融基础 数据工程 python零基础 安全系统 现代密码学 硬件安全 软件安全 网络安全基础 递归神经网络 信息检索 云计算网络 云计算应用 云计算基础 云计算概念 分组交换网络 局域网 创意写作 写作 数学基础 台湾大学 基因序列 生物信息学 斯坦福算法课程 软件架构 软件设计 java程序设计 r语言基础 图论 组合数学 python数据表示 python基础 深度学习专项课程 游戏设计与开发 游戏开发 游戏设计概念 游戏设计艺术 angular 恐龙古生物学 恐龙 古生物学 推荐系统评价 jquery 英语语法 c# 高级算法 算法专项 iot python专项课程 python入门课程 商务英语交流技巧 商务英语交流 python社交网络分析 python文本挖掘 机器学习专项 金融价值 金融决策 金融公开课 数据结构与算法 大数据机器学习 大数据分析 商业与金融建模 金融建模 学术英语听说 数据分析工具 编程入门 编程 编程基础 算法思维 计算机基础 秘钥管理 hdfs 数据工程师 hive 3d交互设计 3d建模 虚拟现实 vr 洛桑联邦理工学院 函数式编程入门 数据科学课程 数据科学专项课程 学术英语课程 学术英语写作课程 斯坦福算法专项课程 斯坦福算法 python数据分析 英文简历 英文面试 英文写作 贝叶斯方法 商业分析技术 大数据建模 数据获取 数据清洗 文本挖掘课程 聚类分析 python公开课 python课程 主成分分析 深度学习资料 词意消歧 词义消歧 推荐系统入门 python书籍 机器学习算法 数据结构课程 图像处理 贝叶斯方法实战 深度学习源代码 sibyl p2p 机器学习书籍 数据结构资料 凸优化 推荐系统入门资料 数据科学导论 可视化 机器学习开源工具包 jane mcgonigal 公开课社区 挖课 courseminer 文本情感分析 多变量微积分 社会计算 数学分析公开课 概率图模型公开课 百度 吴恩达 香港科技大学 函数式语言 scala公开课 class2go coursera无法连接 coursera打不开 keith devlin 数学思维简介 社交网络 余凯 张潼 机器人视频 robert sedgewick 算法上 多伦多大学 莱斯大学 华盛顿大学 佐治亚理工学院 神经网络视频

Text Summarization

Keyword Extraction

Text Processing

Word Similarity

Best Coursera Course

+2 投票

聚类任务面临的首要任务就是相似度矩阵的计算,如词聚类、文档聚类等,类似的问题在许多应用任务中都会遇到,如推荐系统。这里可以将问题拆分成如下关键子任务:

  1. 如何定义相似度函数?
  2. 如何高效计算相似度矩阵,尤其面对海量数据处理任务?
  3. 如何基于高维矩阵做运算?

大家有什么较好的解决方案呢?

分类:机器学习 | 用户: (2.4k 分)
修改于 用户:

求解高维相似度矩阵(All Pairs Similarity Search,or Pairwise Similarity),或者在大规模数据集上挖掘Top-K最相似的items(K-Nearest Neighbor Graph Construction, or TopK Set expansion),主要有如下几种方法(以Document Similarity为例):

  1. Brute Force:最直接、暴力的方法,两个for循环,计算任意两篇文档之间的相似度,时间复杂度为O(n^2)。这种方法可以得到最好的效果,但是计算量太大,效率较差,往往作为baseline。                                                       
  2. Inverted Index Based:由于大量文档之间没有交集term,为了优化算法性能,只需计算那些包含相同term文档之间的相似度即可,算法伪代码如下:基于MapReduce的分布式计算框架如下:为了进一步优化计算,节省空间,研究人员提出了一系列剪枝策略和近似算法,详细见:《Scaling Up All Pairs Similarity Search》、《Pairwise document similarity in large collections with MapReduce》、《Brute Force and Indexed Approaches to Pairwise Document Similarity Comparisons with MapReduce》。
  3. Locality Sensitive Hashing(LSH):通过对文档进行某种度量操作后将其分组散列在不同的桶中。在这种度量下相似度较高的文档被分在同一个桶中的可能性较高。主要用于Near-duplicate detectionImage similarity identification等,详细见:《Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality》、《Google news personalization: scalable online collaborative filtering》。

基于Inverted Index Based和Locality Sensitive Hashing(LSH)方法,利用MapReduce分布式计算框架,可以较好的解决高维相似度矩阵计算的问题,那么再抛一个实际中面临的问题:不断产生新的数据项,如何高效更新相似度矩阵?

基于Inverted Index Based的方法,因倒排拉链长短不一,较长的拉链难免成为短板,如何缓解、解决?

稍微转换一下思路:将问题从相似度矩阵计算变成相似对象计算,对于聚类等需要相似度计算的应用尽量保证最终结果不变。处理数据时的瓶颈主要由两个方面造成:1) 数据规模很大;2) 用来表示数据的特征维度很大。fandy这里介绍的是Jimmy Lin在SIGIR09上介绍的基于Map Reduce的pairwise similarity计算。除了简单粗暴的方法之外,还提出了使用Inverted Index来加速,这里基于的观察是对于特征没有交集的对象相似度自然为0,那么就无需比较。我们可以进一步考虑即使两者特征有重合,是否需要比较呢?答案是否定的,例如两个对象想重合的特征具有比较小的数值,那么他们的相似度远低于阈值,从而确定他们是不相似的。因此,可以借鉴similarity search中的不少研究成果(Near-duplicate detection也属于这个范畴),使用Prefix-filtering的方法快速缩小比较所用的搜索空间。最简单的做法是:利用常规的特征选择方法选出一定比例的特征作为对象prefix,这样等同于做了降维处理,同时基于inverted index本身对应的词汇V的大小也缩小了,从而进一步降低了比较的次数。我们可以将Prefix中任一特征重合的对象归入同一个block。一个对象可以属于多个blocks。这里block有点类似上文中提到的基于一个term或一维feature对应的对象集合。这里省去了理论部分来说明如何选择prefix,以及如何避免False negative(即应该相似,但是被排除在block之外)的产生的证明。这种方法可以是多阶段的(一般为2阶段),每一阶段的完成均缩小搜索空间。和基于map-reduce的pairwise similarity计算比较,该方法的初始阶段(或阶段1)由于维度比较小,可以直接放入内存在单机迅速完成,此后每阶段产生的block均相互独立,可进行更高级的相似度比较操作。我们可以在每次block内处理完根据对象对合并(类似reduce),也可以在分成block之后,根据对象来构建连通分量,基于连通分量进行独立相似度计算。如若连通分量很大,可以进一步分多阶段处理。当得到的连通分量大小适中时,可以分多核或多机独立运行。这里我们计算得到的pairwise 相似度不完整,不仅不包括不相关的,还排除弱相关的。和inverted index based相比,LSH-based是全局相似的,将相似的对象排放在一起,这样增加了访问的locality特性,从而支持快速scan,避免随机访问。类似地,LSH也可以被应用在多阶段相似对象计算中的block生成从而缩小搜索空间。

对于新产生的数据,根据其表示的特征(无论是基于prefix-filtering的还是完整的高维表示),插入到倒排索引相应的posting list中,或LSH相应的bucket中(注意,其实LSH或SimHash可以被看作是一种直接生成哈希(比如利用海明距离等)来保证全局相似和相似对象连续存储特点的高效算法)。这里相似度矩阵的更新分为新产生数据之间的相似度计算,以及新产生数据和原有关联数据之间的相似度计算。那么从矩阵上来看其实增加了3个子矩阵,如果相似度是对称的,那么其实就独立计算两块子矩阵,而其中每块均利用同样的map-reduce的思路,对于同一posting list中或bucket中的进行map,而之后根据对象配对进行reduce。这里无需对于posting list或bucket中的所有对象配对进行map,只需要针对新产生的数据,等于在map和reduce之上增加了一个filter减少了数据处理量。对于新产生数据量比较少的情况下,建议直接加载到内存来处理,并将shuffling变成基于内存形成流水线操作。如果新产生数据比较大时(可批量处理),操作和之前一致。对于删除,并不删除相似度矩阵中的行列,而是将单元格置0等作为标记。类似地,更新操作(虽然比较少见),可以简单地作为删除和新增操作的叠加。Inverted Index比较长的时候可以考虑将其分成不断的sub-posting-list,并设置landmark ID来管理sub lists和原本的long list的对应关系,这类方法也称之为block-based inverted index。当然过长的posting list就代表着是一个DF很高(即出现在很多对象(视为文档)中),通过合适的特征选择,即可排除在prefix之外,那么也间接解决了这个问题。

make sense

之前重点关注全局相似/非近似的解决方案,缺少Prefix-filtering的介绍,谢谢haofen补充。

其实,为了节省计算资源,完全可以将Scaling Up All Pairs Similarity Search》提到的许多优化思想、prefix filtering等策略引入到MapReduce框架中,因为的确存在这样的情况:即使两者特征有重合,也没必要做比较。因为最相似的往往只有少数,而且一般的需求也仅是Top-K。

总之,优化目的是缩小搜索空间,减少计算量,节省存储空间。

对,是这个意思。个人觉得单纯的Map Reduce其实是崇尚简单粗暴,会让人变懒。所以还是应该针对问题和数据,从算法本身出发来解决。

“和inverted index based相比,LSH-based是全局相似的,将相似的对象排放在一起,这样增加了访问的locality特性,从而支持快速scan,避免随机访问。” 请问这句是什么意思?inverted index based也是全局解吧?!

haofen提到的 “Inverted Index比较长的时候可以考虑将其分成不断的sub-posting-list,并设置landmark ID来管理sub lists和原本的long list的对应关系,这类方法也称之为block-based inverted index。当然过长的posting list就代表着是一个DF很高(即出现在很多对象(视为文档)中),通过合适的特征选择,即可排除在prefix之外,那么也间接解决了这个问题。”  优化也是很实用的策略。
 

2 个回答

+1 投票
1. constructing sparse matrix approximately.

2. Nyström approximation
用户:
0 投票

今天和同事聊天了解到开源工具Mahout,已经提供了all-pairs-similarity的计算功能,有兴趣的同学可以去阅读源码,简介如下(RowSimilarityJob

https://cwiki.apache.org/confluence/display/MAHOUT/RowSimilarityJob):

 

The goal is to compute all pairwise similarities between the rows of a
sparse matrix A.

The computation should be executed in a way that only rows that have at
least one non-zero value in the same dimension (column) are compared. We
need this to avoid a quadratic number of pairwise comparisons.
Furthermore we should be able to 'embed' arbitrary similarity measures
and we should always be able to use a combiner in all MapReduce steps.

The computation is executed using three MapReduce passes:

In the first step, the rows of A are preprocessed via
VectorSimilarityMeasure.normalize() (they could e.g. be binarized or
scaled to unit-length), a single number for each row of A is computed
via VectorSimilarityMeasure.norm() (e.g. L1 norm) and A' is formed.

The second steps operates on the rows of A' (the columns of A). The
mapper sums up all pairwise cooccurrences using
VectorSimilarityMeasure.aggregate() (as vectors, thereby using the so
called 'stripes' pattern). The reducers sums up all cooccurrence vectors
for one row and uses the similarity measure and the precomputed numbers
from step one to compute all similarities via
VectorSimilarityMeasure.similarity().

The third step ensures that only the top k similar rows per row are kept.

It's hard to see from the code but actually the job performs the matrix
multiplication AA' via outer products with a modified (similarity
measure specific) dot product.

用户: (2.4k 分)
...