企业命名实体发现

---

目标

1. 新兴企业种类多、创建流程短，传统人工搜集、分类的做法已不实用
2. 互联网语料发达、更新速度快

直接目标：从互联网的大规模语料中，发掘出企业名

难点

这其是一个二段式的问题：

1. 发现未登录词（新词发现问题）
2. 判断新词属于某一类企业（词聚类问题）

思路

1. 新词发现问题，可以考虑采用CRF，特征选用 左右信息熵(LE/RE)、互信息（MI） 、词频等，参考: 软件学报2013：基于条件随机场方法的开放领域新词发现[J]。(事实上，单单考虑左右信息熵(LE/RE)、互信息（MI）的大小已经足够判断一些字串能否构成词)

2. 词聚类问题，可以考虑两个词在一句话中两个词的共现关系（假设共现得越多，词之间的相似度越大），将其构建成一个词共引用图，再采用复杂网络上的聚类算法来进行计算。

3. 考虑中文中的特殊情况，“同义关系”的模板可以考虑成如下规则：

1. 基于特殊词语的： A(简称|简称为|中文简称|又称|又称为|亦称|亦叫|亦作|又叫|也称|也称为|俗称|又译|又译作|全称为|全称是)B
2. 基于标点符号的： A{:|、} <中文别名|通用名称{|:、} B

• 可以发现，中文中顿号是一个很明显的关系：顿号之内往往只有单独的实体名，且顿号表示着一种很明显的并列关系，我们可以用它来构建我们的词共引用图
• 进一步，为了降低词共引用图的复杂度，我们将从互联网上搜集到的语料文本进行话题识别，然后分类，降低该网络的节点数目

具体步骤

1. 从互联网上采集文档，形成语料文档集合
2. 在分词、过滤停用词之后，采用LDA话题模型来预测该语料中的话题数目，同时得到每个文档的话题分布，即一个以话题为维度的向量
3. 用K-means算法对文档进行聚类，按此将语料拆分为各类文档集合
4. 对聚好类的每一个文档集合，抽取每一句顿号之间的字串
5. 只有该句话中顿号个数大于等于3时才抽取，且用互信息、左右信息熵来对字串作最基本的判别，若太低则予以放弃(主要过滤掉我是城管、警察对街头小贩、消防隐患进行了清理这类句子)。
6. 构建共引用图，节点就是刚刚抽取出来的字串，分别为v1、v2.若S(v1)、S(v2)分别表示字串1、字串2在抽取时的次数，而S(v1,v2)表示字串1、字串2被同时抽取、出现在一个顿号并列中的次数，则定义v1、v2的边为S(v1,v2)/(S(v1)+S(v2))
7. 在图上运行基于随机行走的社区划分算法
8. 给社区打标签，找到京东、苏宁等所在的社区，当做电商类实体名社区；找到顺丰、全峰等所在的社区，当做快递业实体名社区
   
   下面具体分析 LDA主题模型、WalkTrap算法

LDA主题模型

简介

LDA(Latent Dirichlet allocation) 是隐含狄利克雷分布简称，是一种主题模型，它可以将文档集中每篇文档的主题按照概率分布的形式给出。同时它是一种无监督学习算法，在训练时不需要手工标注的训练集，需要的仅仅是文档集以及指定主题的数量k即可。此外LDA的另一个优点则是，对于每一个主题均可找出一些词语来描述它。

参考：Blei D M, Ng A Y, Jordan M I. Latent dirichlet allocation[J]. the Journal of machine Learning research, 2003, 3: 993-1022.

建模

如何生成M份包含N个单词的文档？LatentDirichlet Allocation介绍了3方法：

1. unigram model

   For each ofthe N words w_n: Choose a word w_n ～ p(w);

   其中N表示要生成的文档的单词的个数，w_n表示生成的第n个单词w，p(w)表示单词w的分布

   这种方法通过训练语料获得一个单词的概率分布函数，然后根据这个概率分布函数每次生成一个单词，使用这个方法M次生成M个文档。其图模型如下图所示：

   
   

2. Mixture of unigram

>Choose a topicz ～ p(z); For each ofthe N words w_n:  Choose a word w_n ～ p(w|z); 
>
>其中z表示一个主题，p(z)表示主题的概率分布，z通过p(z)按概率产生；N和w_n同上；p(w|z)表示给定z时w的分布，可以看成一个k×V的矩阵，k为主题的个数，V为单词的个数，每行表示这个主题对应的单词的概率分布，即主题z所包含的各个单词的概率，通过这个概率分布按一定概率生成每个单词。
>![](http://img.my.csdn.net/uploads/201209/03/1346652094_6771.PNG)
>
>从上图可以看出，z在w所在的长方形外面，表示z生成一份N个单词的文档时主题z只生成一次，即只允许一个文档只有一个主题，这不太符合常规情况，通常一个文档可能包含多个主题。

3. LDA(Latent Dirichlet Allocation)

>LDA方法使生成的文档可以包含多个主题，该模型使用下面方法生成1个文档
>
>Choose parameter θ ～ p(θ);For each of the N words w_n:Choose a topic z(n) ～ p(z|θ);Choose a word w_n ～ p(w|z); 
>![](http://img.my.csdn.net/uploads/201209/03/1346652226_5749.PNG)
>![](http://img.my.csdn.net/uploads/201209/03/1346652208_1834.PNG)
>
> 其中θ是一个主题向量，向量的每一列表示每个主题在文档出现的概率，该向量为非负归一化向量；p(θ)是θ的分布，具体为Dirichlet分布；N和wn同上；z(n)表示选择的主题，p(z|θ)表示给定θ时主题z的概率分布，具体为θ的值，即p(z=i|θ)= θ_i；p(w|z)同上。
> 
> 1.  corpus-level（红色）：α和β表示语料级别的参数，也就是每个文档都一样，因此生成过程只采样一次。 α：分布p(θ)需要一个向量参数，即Dirichlet分布的参数，用于生成一个主题θ向量；β：各个主题对应的单词概率分布矩阵p(w|z)。
> 2. document-level（橙色）：θ是文档级别的变量，每个文档对应一个θ，也就是每个文档产生各个主题z的概率是不同的，所有生成每个文档采样一次θ。
> 3. word-level（绿色）：z和w都是单词级别变量，z由θ生成，w由z和β共同生成，一个 单词w对应一个主题z。
> 
> 最主要的文档生成过程：
> ![](http://datalab-wordpress.stor.sinaapp.com/uploads/2013/06/LDA.png)
> 
> 1. 首先从以β为参数的Dirichlet分布中，抽样产生整个文档集的K个词分布，标记为φ1至φk，即左侧的K个主题；
> 2. 对于每一篇文档：
>   1. 从以α为参数的Dirichlet分布中，抽样产生一个主题分布θm，即这篇文档中各个主题的比重，图中为右侧的直方图；
>   2. 对于文章m中的每一个词：
>      1. 以概率分布θm，选择K个主题中的一个主题，例如为φi；
>      2. 以概率分布β，从该主题中选择一个词。 
>      
>**最终总结：**      
>![](http://datalab-wordpress.stor.sinaapp.com/uploads/2013/06/LDA%E5%9B%BE%E6%A8%A1%E5%9E%8B%E8%A1%A8%E7%A4%BA.jpg)
>
>**LDA的参数估计：**未仔细思考
>
>Gibbs 抽样容易实现并且能够有效地从大规模文集中抽取主题，是当前最流行的LDA 模型抽取算法。Gibbs 抽样并没有直接去计算主题-单词分布φk和文本上的主题分布θm，转而对每个位置上的词的主题进行迭代采样。一旦每个位置上的词的主题确定下来，那么φk和θm的值就可以在统计频次后计算出来。对每个位置上的词进行主题采样时，该词的主题以该词当时在各个主题上的概率分布采样获得。采样前需要计算该词属于每个主题的概率。

实际使用

1. 分词，用空格间隔
2. 去除停用词、标点
3. 设置α、β的值，一般选经验参数：0.5、0.1
4. 选择迭代次数、需要产生话题数目
5. src/lda -est -alpha 0.5 -beta 0.1 -ntopics 15 -niters 10 -savestep 1 -twords 20 -dfile /home/hadoop/Documents/testCompany.dat
6. 生成文件：
   • model-final.twords:

     n个topic，以及每个topic下面包含的具体的字词
     - model-final.theta:
     >每个doc内对应上面的n个topic的分布情况
     - model-final.phi:
     >每个topic内对doc的分布情况，与上面的互为转置
     - wordmap.txt:
     >词-id映射

随机漫步模型

社区划分定义

1. 假设构建了一个词语网络图G=(V,E)，其中V表示顶点（词语）集合， E表示词语共现关系的集合。这样的词语网络图同样可以表示为邻接矩阵A = a[ij] ，矩阵内的值极为边的权值 。
2. 若我们将该网络G分成k份，分别为k个节点集合φ = {N1,N2,N3...Nk} 。若该划分具有对于每个Ni，都满足Ni内的节点连接密集、与Ni外连接稀疏的特性，则称φ为G的社区划分。

随机漫步模型的建立

1. 在图G中，取节点Vi，从Vi出发开始随机游走，每走一步都要根据转移概率选择下一步所要到达的位置。

2. 假设随机游走的下一步到达邻接节点Vj的转移概率为Pij，而该网络图的邻接矩阵为A，则有：

   

3. 我们用矩阵D = [d1,d2,d3...dn]表示每个节点出度，则随机游走一次的转移概率矩阵为：

   

4. 显然，由于转移概率矩阵在图确定下来的时候，就已经确定好了，也就是说在随机游走的每一步，当前的状态只跟上一步的状态有关，我们便可以把整个随机漫步过程看作一个马尔科夫链，在知道随机游走上一步的状态后，我们可以通过乘上转移矩阵得到当前的状态。

5. 通过马尔科夫链的性质，我们可以知道，用转移概率矩阵P作为下一次游走的输入并重复迭代后， p^k就是第k步后的状态。在满足p不可约且非周期的前提下，lim(P^k)会收敛于一个平稳分布。这个时候我们就可以用任意两个节点Vi、Vj的转移概率 来表示它们之间的相似度。但由于词网络图的维度较大，且不一定满足“不可约”、“非周期”这两个条件，故我们只做有限次的状态转移，给定一个从顶点Vi开始的随机游走，用P(i,t)表示该随机游走从Vi经过t次游走到达个顶点的概率向量，并用下式来表示节点之间的相似度。

   

6. 同样的，我们考虑节点Vi和社区C之间的相似之间的相似度,|C|为社区内节点数目

   

7. 而社区和社区的相似度，我们定义为:

   

8. 在实验中，由于复杂度的原因，t的值不能选取过大。依据经验参数，一般取 。此外选取t= 4。

层次聚类

既然已经提出了如何通过随机漫步的方法计算两个节点的相似度得方法。
接下来的问题是如何将这些节点进行聚类，形成社区
采用自底向上的层次聚类算法：

1. 在进行n-1步迭代后，上述流程结束，并且我们得到最终的社区划分.
2. 在合并的过程中，每一步都有新的社区合并到最终社区中来
3. 依据节点们并入社区的先后顺序，构造出系统树图

   系统树图:

   1. 叶子节点是我们词网络图上的所有顶点
   2. 该树图结构的内部节点对应着我们刚刚算法中的“合并”步骤：即对应着一个合并了它两个孩子节点的新社区

模块度

获得了系统树图后，我们还是不确定该如何划分社区。这时候，我们一般采用模块度指标，来选择最优的社区划分。

模块度指标Q是用于刻画社团特性强弱的参数。 函数定义为社团内实际连接数目与随机连接情况下社团内期望连接数目之差，用来对网络中社团的整体质量作出一个定量的评价。

函数的主要思想基础是“网络社团结构越明显，它与随机网络的差异就越大”这个假设。
若将图划分成k个社团。用m表示网络连接总数，用mi表示社区Ci中的连接总数， di表示社区Ci中节点度之和: