基于决策树规则和多种统计模型相结合的人名识别算法

摘要

本发明公开了基于决策树规则和多种统计模型相结合的人名识别算法，采用决策树规则对人名构成特征和上下文特征进行分类，然后对每一类别人名采用针对性的统计模型，从而弥补目前主流技术采用单一模型无法全面覆盖所有人名构成特征和上下文特征的缺点，提升综合识别效果；而且，利用决策树规则可以快速准确的识别容易识别或排除的情况，从而减轻对训练语料库的依赖，提升识别算法可靠性；另外，对不同类别人名采用不同复杂度的统计模型，亦可提升综合识别效率。

主权项

1.基于决策树规则和多种统计模型相结合的人名识别算法，其特征在于包括离线统计和在线识别两个过程：1.离线统计下面对本算法所定义的语义角色和所使用的统计模型加以说明；1.1.语义角色语义角色包括人名姓氏、人名用字、人名上文特征和人名下文特征四种；人名用字指构成人名的单个汉字，人名上文特征和人名下文特征分别指在语言文本中出现在人名之前和之后的词语；若使用“指数”来描述各语义角色需要统计的信息，则:人名姓氏指数刻画一个汉字或词语在语言文本中出现时，担任人名姓氏和常用词的倾向，取值范围为[0,1]，越趋向1表示做人名姓氏的可能性越大，做常用词的可能性越小；人名姓氏指数的数学表示如下：式1.1中：S_w表示汉字或词语w的人名姓氏指数；N_w表示w在人名库中做人名姓氏出现的次数；N表示w在训练语料库中做常用词出现的次数；α为调节因子，表示训练语料库中人名个数与人名库中人名个数的比值；人名用字指数刻画一个汉字在语言文本中出现时，担任人名用字和常用词的倾向，其取值范围和数学表示与人名姓氏指数一致，不在赘述；人名上文特征指数和人名下文特征指数分别刻画一个词语在语言文本出现时，之后或之前出现人名的概率，取值范围为[0，1]，其数学表示为：式1.2中：F_w表示词语w的人名上文或下文特征指数；N_w表示w在训练语料库中做人名上文或下文特征出现的次数；N表示w在训练语料库中做常用词出现的次数；1.2统计模型本算法利用统计模型计算给定单个或两个连续汉字为人名名字的概率，并针对汉字串的两类构成情况，设计了针对性的统计模型，且每个统计模型对于决策树规则的每一个分支分别训练，从而实现多模型人名识别方法；（1）情况一：汉字串不成词汉字串不成词表示给定子串为单个汉字或两个独立汉字，本算法采用隐马尔科夫模型进行计算；设隐状态集合为S={S₁=人名，S₂=非人名}，初始概率矩阵π=[π₁,π₂]分别表示人名出现和不出现的先验概率，状态转移矩阵A为：式(1.3)中，a_ij表示第i个隐状态到第j个隐状态的转移概率；设给定字串w=w₁w_2。。。w_n(n=1,2)，d_i为汉字w_i的人名用字实体角色指数，则观察值矩阵B为：结合式(1.3)和式(1.4)，可得用于不成词汉字串为人名名字隐马尔科夫概率评估模型：本算法利用前向算法对模型(1.5)进行概率计算，得到给定不成词汉字串作为人名名字的概率，并结合预设阈值得到最终的判定结果，模型参数和预设阈值根据本算法的决策树规则分支分别进行训练；（2）情况二：汉字串成词汉字串成词表示给定子串为两个组合成词的汉字，本算法采用线性加权法进行计算；设给定字串w=w₁w₂，d₁、d₂分别为汉字w₁、w₂的人名用字实体角色指数，F为词w₁w₂做常用词的使用频数，使用频数由语料库统计，可通过词典查询获得，则该字串做人名使用的概率计算模型为：其中:h_1max和h_1min，h_2max和h_2min分别为汉字w₁，w₂预设的最小和最大阈值；为权重调节因子，用于调整人名用字指数和词串使用频数的权重；F_max为预设词串最大使用频数，以上参数均由训练语料库训练设定；模型1.6表示，若字串的使用频数大于等于F_max或者两个字的人名用字指数小于预设最小阈值，则直接排除为人名；若字串使用频数小于F_max，且两个字的人名用字指数都大于预设阈值，则直接判定为人名；否则根据线性加权式计算其为人名名字的概率；2.在线识别在线识别包括中文分词、角色矩阵构建、候选人名搜索、决策树规则分支和人名识别五个过程；2.1中文分词中文分词是将连续的语言文本字符串切分为词序列，本算法采用改进最大匹配算法实现；给定语言文本字符串，W=w1w2…wn，改进最大匹配算法流程为：（1）遍历字符串W，根据词典对wi执行最大匹配操作，并将匹配得到的词依次添加到初始词序列T，遍历结束后，得到T={t1,t2,…,tn}，其中，ti表示在W中，以wi开头的最长词条；（2）检测T内的任意两相邻词条，若存在词条ti和ti+1满足交集条件ti∩ti+1!=，则若ti与ti+1同时不满足全集条件ti!=ti∪ti+1,则将ti标记为交叉歧义，然后令ti=ti∪ti+1，并删除ti+1，重复当前步骤，直到T内不存在任意两相邻词条满足交集条件；（3）采用交叉歧义消解算法依次对T内所有标记为交叉歧义的元素执行歧义消解，从而最终得到词序列T；2.2角色矩阵构建角色矩阵描述了给定语言文本词序列中所有的人名实体相关信息，是本算法人名识别过程的数据基础；通过引入角色矩阵，能够以最简洁的方式提取和描述给定词序列中所有人名识别相关信息，为后续的人名识别过程带来极大便利；设语言文本的词序列为T={t1,t2,…,tN}(N>0)，N为词序列元素个数，人名实体角色类别总数为M(M>0，本算法M=4)，则词序列T的角色矩阵为：其中，d_ij(1≤i≤N,1≤j≤M)表示词序列T中第i个词的第j种实体角色指数，若第i个词不担任第j种实体角色，则d_ij=0.0；当N=1时，即词序列中仅有一个词，角色矩阵退化为该词的角色向量；角色矩阵的构建包括两个步骤：1）通过角色词库查询给定词序列中每个词的角色向量；2）将所有词的角色向量组合得到词序列的角色矩阵；2.3人名初定位由于本算法对识别的人名范围定义在同时存在姓氏和名字的中国人名，因此人名的初定位可以看做姓氏的识别，即遍历角色矩阵，找到所有姓氏角色指数大于0.0位置；连姓是人名初定位过程最困难的问题，本算法采用回溯算法解决连姓情况，人名初定位算法如下：（1）令i=0，设角色矩阵D_MN，回溯栈S，初始为空；（2）获取D中第i个词的姓氏指数，若已到矩阵末尾，则未人名，算法终止；若姓氏指数值为0.0，则i=i+1，重复第（2）步；否则，执行第（3）步；（3）识别第i个词是否存在连姓情况，若存在连姓，且最靠前的连姓位置为j，则将i压入栈S，令i=j，重复第（3）步；若不存在，则以i为人名初定位位置，输出；2.4候选人名搜索候选人名搜索以人名初定位位置为姓氏，根据决策树规则从角色矩阵里找出所有符合人名构成特征的候选人名，得到给定姓氏的候选人名集合；候选人名搜索通过决策树规则直接排除不符合人名构成特征的情况，减少统计计算次数，从而提升算法整体效率；本算法采用的人名构成特征包括以下三点：（1）去除姓氏后的人名总数不超过2个字；（2）名字中所有字的人名用字指数都不得低于指定阈值；（3）对于名字为2个字的情况，至少有1个字的人名用字指数大于指定阈值，本算法阈值设定为0.1，已通过实验证明该规则的有效性；每个候选人名具有两类属性，分别为：（1）位置属性；位置属性描述候选人名在角色矩阵中的位置，包括姓氏位置，尾界位置和名字长度三个属性，姓氏位置和尾界位置分别表示候选人名的姓氏和名字的最后一个字在角色矩阵的列号，名字长度表示候选人名名字的字数；（2）特征属性；特征属性描述候选人名的出现特征，包括姓氏指数、上文特征指数和下文特征指数；2.5人名判定人名判定过程是从指定姓氏在给定角色矩阵中的候选人名集合中判断是否存在人名，若不存在则输出非人名，否则输出人名在角色矩阵中的位置信息；人名判定过程包括两个步骤：（1）采用基于决策树规则和多种统计模型相结合的方法判定候选人名集合中的人名；（2）根据第（1）步的判定结果，输出识别结果，若判定结果为空，即所有候选人名都被判定为非人名，则输出非人名；若判定结果为多个人名，表示出现人名歧义，则根据人名在语料文本中的出现特征选择出现可能性最大的候选人名为识别结果；否则，直接输出识别结果；决策树规则算法如下：（1）给定候选人名P={S,E,N,}和对应的角色矩阵D，设D[i]表示D中的第i列，即词序列中的第i个词的实体角色指数向量;（2）决策树第一层根据D[S]的姓氏指数和上下文特征指数判定该处出现人名的可能性，若姓氏指数或者上下文特征指数高于指定阈值，则表示此处出现人名的可能性很大，子分支判定的阈值应当适当降低，且以提升人名识别召回率为识别目的；若姓氏指数或者上下文特征指数低于指定阈值，则表示此处出现人名的可能性较小，子分支判定阈值应提高，且以提升人名识别准确率为识别目的；（3）决策树第二层根据人名的构成特征进行决策，旨于选择合适的统计模型进行统计计算与人名判定；若构成名字的汉字串不成词，则采用单字模型计算，若构成名字的汉字串成词，则采用双字词模型计算；最后根据计算结果与预设阈值的对比得到判定结果，预设阈值由决策树第一层得出。