0
推荐
1458
阅读
Trie树的应用：查询IP地址的ISP
1. 问题描述给定一个IP地址，如何查询其所属的ISP，如：中国移动（ChinaMobile），中国电信（ChinaTelecom），中国铁通（ChinaTietong)？现有ISP的IP地址区段可供下载，比如中国移动的IP地址段103.20.112.0/22103.21.176.0/22111.0.0.0/20112.0.0.0/10117.128.0.0/10120.192.0.0/10183.192.0.0/10211.103.0.0/17211.136....
1
推荐
1540
阅读
开源中文分词工具探析（五）：FNLP
1. 前言类似于THULAC，FNLP也是采用线性模型（linear model）作为基础分词模型。与对数线性模型（log-linear model）HMM/CRF所不同的是，线性模型没有归一化因子而直接建模Score函数：则序列标注问题对应于求解：THULAC是采用感知器来学习参数ws，而FNLP则是采用在线学习算法Passive-Aggressive(PA) [2]。PA算法结合感知...
0
推荐
1622
阅读
开源中文分词工具探析（四）：THULAC
1. 前言THULAC所采用的分词模型为结构化感知器（Structured Perceptron, SP），属于两种CWS模型中的Character-Based Model，将中文分词看作为一个序列标注问题：对于字符序列C=cn1，找出最有可能的标注序列Y=yn1。定义score函数S(Y,C)为在C的情况下标注序列为Y的得分。SP以最大熵准则建模score函数，分词结果则等同于最...
0
推荐
1386
阅读
开源中文分词工具探析（三）：Ansj
1. 前言Ansj支持多种分词方式，其中ToAnalysis为店长推荐款：它在易用性,稳定性.准确性.以及分词效率上.都取得了一个不错的平衡.如果你初次尝试Ansj如果你想开箱即用.那么就用这个分词方式是不会错的.因此，本文将主要分析ToAnalysis的分词实现。以下源码分析基于ansj-5.1.0版本。ToAnalysis继承自抽象类org.ansj.splitW...
0
推荐
1560
阅读
中文分词工具探析（二）：Jieba
1. 前言Jieba是由fxsjy大神开源的一款中文分词工具，一款属于工业界的分词工具——模型易用简单、代码清晰可读，推荐有志学习NLP或Python的读一下源码。与采用分词模型Bigram + HMM 的ICTCLAS 相类似，Jieba采用的是Unigram + HMM。Unigram假设每个词相互独立，则分词组合的联合概率：在Unigram分词后用HMM做未登录词...
0
推荐
2143
阅读
中文分词工具探析（一）：ICTCLAS (NLPIR)
1. 前言ICTCLAS是张华平老师推出的中文分词系统，于2009年更名为NLPIR。ICTCLAS是中文分词界元老级工具了，作者开放出了free版本的源代码（1.0整理版本在此). 作者在论文[1] 中宣称ICTCLAS是基于HHMM（Hierarchical Hidden Markov Model）实现，后在论文[2]中改成了基于层叠隐马尔可夫模型CHMM（Cascaded Hidden Markov ...
0
推荐
1511
阅读
【中文分词】结构化感知器SP
结构化感知器（Structured Perceptron, SP）是由Collins [1]在EMNLP'02上提出来的，用于解决序列标注的问题。中文分词工具THULAC、LTP所采用的分词模型便是基于此。1. 结构化感知器模型CRF全局化地以最大熵准则建模概率P(Y|X)；其中，XX为输入序列xn1，Y为标注序列yn1。不同于CRF建模概率函数，SP则是以最大熵准则建模sc...
0
推荐
1964
阅读
【中文分词】条件随机场CRF
之前介绍的MMEM存在着label bias问题，因此Lafferty et al. [1] 提出了CRF (Conditional Random Field). BTW：比较有意思的是，这篇文章的二作与三作同时也是MEMM的作者。1. 前言本节将遵从tutorial [2] 的论文结构，从概率模型（Probabilistic Models）与图表示（Graphical Representation）两个方面引出CRF。概率模型N...
2
推荐
1792
阅读
【中文分词】最大熵马尔可夫模型MEMM
Xue & Shen '2003 [2]用两种序列标注模型——MEMM (Maximum Entropy Markov Model)与CRF (Conditional Random Field)——用于中文分词；看原论文感觉作者更像用的是MaxEnt (Maximum Entropy) 模型而非MEMM。MEMM是由McCallum et al. '2000 [1]提出MEMM，针对于HMM的两个痛点：一是其为生成模型（generative model），二...
2
推荐
1746
阅读
【中文分词】二阶隐马尔可夫模型2-HMM
在前一篇中介绍了用HMM做中文分词，对于未登录词（out-of-vocabulary, OOV）有良好的识别效果，但是缺点也十分明显——对于词典中的（in-vocabulary, IV）词却未能很好地识别。主要是因为，HMM本质上是一个Bigram的语法模型，未能深层次地考虑上下文（context）。对于此，本文将介绍更为复杂的二阶HMM以及开源实现。1. 前...
0
推荐
1454
阅读
【中文分词】隐马尔可夫模型HMM
Nianwen Xue在《Chinese Word Segmentation as Character Tagging》中将中文分词视作为序列标注问题（sequence tagging problem），由此引入监督学习算法来解决分词问题。1. HMM首先，我们将简要地介绍HMM（主要参考了李航老师的《统计学习方法》）。HMM包含如下的五元组：状态值集合[Math Processing Error]Q={q1,q2,⋯,...
0
推荐
1193
阅读
【中文分词】简单高效的MMSeg
最近碰到一个分词匹配需求——给定一个关键词表，作为自定义分词词典，用户query文本分词后，是否有词落入这个自定义词典中？现有的大多数Java系的分词方案基本都支持添加自定义词典，但是却不支持HDFS路径的。因此，我需要寻找一种简单高效的分词方案，稍作包装即可支持HDFS。MMSeg分词算法正是完美地契合了这种需求。1. ...
0
推荐
1350
阅读
【十大经典数据挖掘算法】CART
1. 前言分类与回归树（Classification and Regression Trees, CART）是由四人帮Leo Breiman, Jerome Friedman, Richard Olshen与Charles Stone于1984年提出，既可用于分类也可用于回归。本文将主要介绍用于分类的CART。CART被称为数据挖掘领域内里程碑式的算法。不同于C4.5，CART本质是对特征空间进行二元划分（即CART生...
0
推荐
1486
阅读
【十大经典数据挖掘算法】Naïve Bayes
朴素贝叶斯（Naïve Bayes）属于监督学习的生成模型，实现简单，没有迭代，学习效率高，在大样本量下会有较好的表现。但因为假设太强——假设特征条件独立，在输入向量的特征条件有关联的场景下并不适用。1. 朴素贝叶斯算法朴素贝叶斯分类器的主要思路：通过联合概率P(x,y)=P(x|y)P(y)建模，运用贝叶斯定理求解后验概率P(y|...
0
推荐
1273
阅读
【十大经典数据挖掘算法】kNN
1. 引言顶级数据挖掘会议ICDM于2006年12月评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naïve Bayes与 CART。 以前看过关于这些数据挖掘算法，但对背后数学原理未做过多探究，因而借此整理以更深入地理解这些算法。本文讨论的kNN算法是监督学习中分类方法的一种。所...