TF-IDF（term frequency–inverse document frequency）是一种用于资讯检索与文本挖掘的常用加权技术。TF-IDF是一种统计方法，用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。TF-IDF加权的各种形式常被搜索引擎应用，作为文件与用户查询之间相关程度的度量或评级。除了TF-IDF以外，互联网上的搜寻引擎还会使用基 于连结分析的评级方法，以确定文件在搜寻结果中出现的顺序。 在一份给定的文件里，词频（term frequency，TF）指的是某一个给定的词语在该文件中出现的次数。这个数字通常会被正规化，以防止它偏向长的文件。（同一个词语在长文件里可能会 比短文件有更高的词频，而不管该词语重要与否。）对于在某一特定文件里的词语 ti 来说，它的重要性可表示为： 以上式子中 ni,j 是该词在文件dj中的出现次数，而分 母则是在文件dj中所有字词的出现次数 之和。 逆向文件频率（inverse document frequency，IDF）是一个词语普遍重要性的度量。某一特定词语的IDF，可以由总文件数目除以包含该词语之文件的数目，再将得到的商取对数得到： 其中 |D|：语料库中的文件总数 ： 包含词语ti的文件数目（即的 文件数目） 然后 某一特定文件内的高词语频率，以及该词语在整个文件集合中的低文件频率，可以产生出高权重的TF-IDF。因此，TF-IDF倾向于过滤掉常见的词 语，保留重要的词语。 =================文本相似性度量======================= 方法一：向量空间模型 在向量空间模型中，文本泛指各种机器可读的记录。用D（Document）表示，特征项（Term，用t表示）是指出现在文档D中且能够代表该文档内容的 基本语言单位，主要是由词或者短语构成，文本可以用特征项集表示为D(T1，T2，…，Tn)，其中Tk是特征项，1<=k<=N。例如一篇 文档中有a、b、c、d四个特征项，那么这篇文档就可以表示为D(a，b，c，d)。对含有n个特征项的文本而言，通常会给每个特征项赋予一定的权重表示 其重要程度。即D＝D(T1，W1；T2，W2；…，Tn，Wn)，简记为D＝D(W1，W2，…，Wn)，我们把它叫做文本D的向量表示。其中Wk是 Tk的权重，1<=k<=N。在上面那个例子中，假设a、b、c、d的权重分别为30，20，20，10，那么该文本的向量表示为 D(30，20，20，10)。在向量空间模型中，两个文本D1和D2之间的内容相关度Sim(D1，D2)常用向量之间夹角的余弦值表示，公式为： 其 中，W1k、W2k分别表示文本D1和D2第K个特征项的权值，1<=k<=N。 在自动归类中，我们可以利用类似的方法来计算待归类 文档和某类目的相关度。例如文本D1的特征项为a，b，c，d，权值分别为30，20，20，10，类目C1的特征项为a，c，d，e，权值分别为 40，30，20，10，则D1的向量表示为D1(30,20,20,10,0),C1的向量表示为C1（40，0，30，20，10），则根据上式计算 出来的文本D1与类目C1相关度是0.86 方法二：字符串相似度 对于象字符串计算相似度的算法有很多，常用的有最大公共字串，编辑距离等。 编辑距离就是用来计算从原串（s）转换到目标串(t)所需要的最少的插入，删除和替换的数目，在NLP中应用比较广泛，如一些评测方法中就用到了 （wer,mWer等），同时也常用来计算你对原文本所作的改动数。编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫 Levenshtein Distance。
Posts Tagged: 算法
淘宝在数据处理领域的项目及开源产品介绍
淘宝在数据存储和处理领域在国内互联网公司中一直保持比较靠前的位置，而且由于电子商务领域独特的应用场景，淘宝在数据实时性和大规模计算及挖掘方面一直在国内保持着领先，因此积累了很多的实践的经验和产品。 TimeTunnel 基于Hbase打造的消息中间件，具有高可靠、消息顺序、事务等传统特性，还能按时间维度反复订阅最近历史的任意数据 高性能的broker，单节点达2万TPS，实际支持上千长链接并发 承载海量的数据传输，日同步数据达10TB，并且包含淘宝主营收入等关键性数据 在各IDC内，部署了超过2000个客户端，覆盖全网日志传输 Scribe、flume、activemq、ZeroMQ？我们可以做得更强大 TBFS 基于Hdfs 0.20进行全面改造，设计目标：单个集群可达10000台服务器，支持10亿文件、100PB的数据的存储 领先于社区的全新设计，彻底解决namenode单点问题，并可实现集群在线升级 期待你来挑战：snapshot、异地数据复制、多级的cache、软硬链接支持 Hbase 基于Hbase0.90.3进行改造，目前有上百台的Hbase服务器，支淘宝7个online应用，online数据存储达100T 支持本地化数据计算、二级引索 期待你来挑战：无阻塞的compact、更多的事务支持、更短的请求响应时间、更强大的索引（Lucene for hbase） Mapreduce 基于Hadoop0.19改造，最大单个集群规模达2000台服务器，兼容hadoop0.20 绝大多数API 实际存储数据超过10PB，日运行mapreduce job达5万个 期待你来挑战：更高效任务调度、更优雅的计算资源管理、更灵活的分布计算模型 Hive 基于hive0.6改造，修改的patch达上百个，支持SQL中间结果复用等众多特性 支持淘宝几乎所有的商业数据分析任务，是各行业数据分析师和数据开发工程师必备的技能 期待你来挑战：Hive & Pig能混合编程？现在不能，你敢想就可以来做！ Taobao-pamirs-schedule taobao-pamirs- schedule是一个基于分布式环境的多线程任务处理框架。目的是让一种批量任务或者不断变化的任务，能够被动态的分配到多个主机的JVM，不同的线程组中并执行。所有的任务能够被不重复，不遗漏的快速处理。它将需要执行的任务抽象成一致的任务模型，进行统一的管理和监控。运用schedule，任务能够比较均匀的分发到多台机器上进行处理，并且可以动态的进行水平扩展。 QLExpress 一个轻量级的脚本引擎，作为一个嵌入式规则引擎在业务系统中使用。让业务规则定义简便而不失灵活。让业务人员就可以定义业务规则。 支持标准的JAVA语法，还可以支持自定义操作符号、操作符号重载、函数定义、宏定义、数据延迟加载等。 UIC Uic是个海量数据的高稳定高并发高响应高可靠高一致性的系统。海量数据：现在整个用户中心的注册用户数接近6亿，加上地址，支付宝绑定数据，接近20亿。现在通过分库分表存在了16个库1024张表里面。高稳定,高可靠：用户中心是淘宝最为核心的系统之一，一个完整的交易流程需要访问UIC高达几十次，所以UIC的稳定是整个淘宝的重中之重，我们为了UIC的稳定做了很多容灾的方案，包括多机房的备份，缓存的容灾，mysql的容灾，流量的控制等等，可以说UIC的核心就是各种容灾体系和在各种极端情况的下解决措施高并发,高响应：每天访问UIC的数据在200亿左右，我们使用了tair做为缓存，使用protobuf序列化， 尽可能的提高缓存的命中率，现在用户数据的命中率在99%。 Prom 海量数据实时计算框架。基于搜索技术对海量明细数据做实时计算。目前主要对交易数据做分析，应用于数据魔方中 特点： 多维索引组合查询 支持任意维度的计算 实时响应(秒级) 结果精确 Andes Andes是基于HBase的任意数据长时间维度高性能数据查询集群系统。解放数据魔方在查询时间段上的限制。 采用key-list存储方式，对于任何时间长度的查询均仅需一次数据库访问即可完成，规避查询时间对于查询性能的影响。 KeyKeys 用户搜索query数据分析系统。应用于淘词中，提供实时匹配用户输入query做关键query、关键热词的查询计算。 Myfox/Nodefox MyFOX是一个针对海量统计数据设计的高性能分布式MySQL集群中间层，承担着数据魔方90%以上的数据存储和查询需求。MyFOX能够提供： •… Read more »
N-Gram学习笔记
统计语言模型 假设一个句子S可以表示为一个序列S=w1w2…wn，语言模型就是要求句子S的概率P(S)： 这个概率的计算量太大，解决问题的方法是将所有历史w1w2…wi-1按照某个规则映射到等价类S(w1w2…wi-1)，等价类的数目远远小于不同历史的数目，即假定： N-Gram模型 当两个历史的最近的N-1个词（或字）相同时，映射两个历史到同一个等价类，在此情况下的模型称之为N-Gram模型。 N-Gram模型被称为一阶马尔科夫链。 N的值不能太大，否则计算仍然太大。 根据最大似然估计，语言模型的参数： 其中，C(w1w2…wi)表示w1w2…wi在训练数据中出现的次数 平滑技术的引入 传统的估计方法对于随机变量£的N次独立观察的样本容量N有如下要求： N>>K 其中K为随机变量能够取到的值的个数。 实际语言模型中往往无法满足这个要求。 例如：词性标注问题，共有140个可能的标记，考虑当前词前后两个词的影响的三阶模型。 K=140*140*140=2,744,000 给定一个10万词左右的人工标注训练集，即 N=100,00，可见训练数据显得非常不足。 假设k泛指某一事件，N(k)表示事件k观察到的频数，极大似然法使用相对频数作为对事件k的概率估计： p(k)=N(k)/N 在语言模型中，训练语料中大量的事件N(k)=0，这显然没有反映真实情况。我们把这个问题称为数据稀疏问题。 这种零值的概率估计会导致语言模型算法的失败，例如：概率值作为乘数会使结果为0，而且不能做log运算。 计数等价类 根据对称性原理，事件除了出现次数之外不应具有细节特征，即所有具有相同计数r=N(k)的事件k（事件出现的次数称为事件的计数）应当具有相同的概率估计值，这些计数相同的事件称为计数等价，将它们组成的一个等价类记为计数等价类Gr。 对于计数为r的计数等价类，定义nr为等价类中成员的个数，pr为等价类中事件的概率，R是最大可能出现的计数次数，则 交叉检验 交叉检验就是把训练样本分为m份，其中一份作为保留部分，其余m-1份作为训练部分。训练部分作为训练集估计概率pr，保留部分作为测试集进行测试。 我们使用Cr表示保留部分中计数为r的计数等价类的观察个数。对于保留部分使用最大似然法对进行概率pr进行估计，即使对数似然函数最大化： 使用拉格朗日乘子解决约束条件下的最大值问题，即： 对pr求偏导，得到交叉检验估计： 如果测试部分也作为保留部分的话，就是典型的极大似然估计： 留一估计 留一方法是交叉检验方法的扩展，基本思想是将给定N个样本分为N-1个样本作为训练部分，另外一个样本作为保留部分。这个过程持续N次，使每个样本都被用作过保留样本。 优点：充分利用了给定样本，对于N中的每个观察，留一法都模拟了一遍没有被观察到的情形。 对于留一方法，pr的极大似然估计为： Turing-Good公式 因为nRpR与1相比一般可以忽略，留一估计公式可以近似为： 留一估计可以利用计数r=1的事件来模拟未现事件，对于未现事件有如下估计： 这个公式就是著名的Turing-Good公式。 空等价类 留一估计中要求么个nr均不为0，在实际问题中当r=5时，这个要求通常都不能满足，即计数等价类G1,…,GR中存在空的等价类。这时按照出现次数进行排序： 对应的出现r(l)次的事件的个数记为nr(l)，在进行留一估计时，使用下一个非空的等价类Gr(l+1)代替可能为空的等价类Gr(l)+1，留一估计公式变为： 式中对空的等价类没有估计概率，因为空等价类并没有对应任何有效事件。 Turing-Good估计的优缺点和适用范围 缺点：( 1 )无法保证概率估计的“有序性”，即出现次数多的事件的概率大于出现次数少的事件的概率。(2)pr与r/N不能很好地近似，好的估计应当保证pr<=r/N。 优点：其它平滑技术的基础。 适用范围：对0<r<6的小计数事件进行估计。 约束留一估计 单调性约束：pr-1<=pr；折扣约束：p<=r/N。 约束留一估计：让计数估计r*=pr•N处于距其最近的绝对频数之间： 在这个约束下，单调性约束自然满足。 计算方法：计算m时检查每个pr是否满足约束，不然就用约束的上下界进行裁剪，然后重新计算m，一直迭代下去直到所有pr满足约束。 折扣模型… Read more »
Recent Comments