[發(fā)明專(zhuān)利]基于決策樹(shù)規(guī)則和多種統(tǒng)計(jì)模型相結(jié)合的人名識(shí)別算法

有效

• 申請(qǐng)?zhí)枺?/td>: 201410060957.5
• 申請(qǐng)日: 2014-02-21
• 公開(kāi)（公告）號(hào): CN103823859B
• 公開(kāi)（公告）日: 2017-02-22
• 發(fā)明（設(shè)計(jì)）人: 鄭中華;周俊;周銀行
• 申請(qǐng)（專(zhuān)利權(quán)）人: 安徽博約信息科技股份有限公司
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30;G06F17/27
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

1.基于決策樹(shù)規(guī)則和多種統(tǒng)計(jì)模型相結(jié)合的人名識(shí)別算法，其特征在于包括離線(xiàn)統(tǒng)計(jì)和在線(xiàn)識(shí)別兩個(gè)過(guò)程：

1.離線(xiàn)統(tǒng)計(jì)

下面對(duì)本算法所定義的語(yǔ)義角色和所使用的統(tǒng)計(jì)模型加以說(shuō)明；

1.1.語(yǔ)義角色

語(yǔ)義角色包括人名姓氏、人名用字、人名上文特征和人名下文特征四種；

人名用字指構(gòu)成人名的單個(gè)漢字，人名上文特征和人名下文特征分別指在語(yǔ)言文本中出現(xiàn)在人名之前和之后的詞語(yǔ)；若使用“指數(shù)”來(lái)描述各語(yǔ)義角色需要統(tǒng)計(jì)的信息，則:

人名姓氏指數(shù)刻畫(huà)一個(gè)漢字或詞語(yǔ)在語(yǔ)言文本中出現(xiàn)時(shí)，擔(dān)任人名姓氏和常用詞的傾向，取值范圍為[0,1]，越趨向?1?表示做人名姓氏的可能性越大，做常用詞的可能性越小；人名姓氏指數(shù)的數(shù)學(xué)表示如下：

式?1.1?中：

S_w?表示漢字或詞語(yǔ)w的人名姓氏指數(shù)；

N_w?表示w在人名庫(kù)中做人名姓氏出現(xiàn)的次數(shù)；

N?表示w在訓(xùn)練語(yǔ)料庫(kù)中做常用詞出現(xiàn)的次數(shù)；

α?為調(diào)節(jié)因子，表示訓(xùn)練語(yǔ)料庫(kù)中人名個(gè)數(shù)與人名庫(kù)中人名個(gè)數(shù)的比值；

人名用字指數(shù)刻畫(huà)一個(gè)漢字在語(yǔ)言文本中出現(xiàn)時(shí)，擔(dān)任人名用字和常用詞的傾向，其取值范圍和數(shù)學(xué)表示與人名姓氏指數(shù)一致，不在贅述；

人名上文特征指數(shù)和人名下文特征指數(shù)分別刻畫(huà)一個(gè)詞語(yǔ)在語(yǔ)言文本出現(xiàn)時(shí)，之后或之前出現(xiàn)人名的概率，取值范圍為[0，1]，其數(shù)學(xué)表示為：

式?1.2?中：

F_w?表示詞語(yǔ)w的人名上文或下文特征指數(shù)；

N_w?表示w在訓(xùn)練語(yǔ)料庫(kù)中做人名上文或下文特征出現(xiàn)的次數(shù)；

N?表示w在訓(xùn)練語(yǔ)料庫(kù)中做常用詞出現(xiàn)的次數(shù)；

1.2統(tǒng)計(jì)模型

本算法利用統(tǒng)計(jì)模型計(jì)算給定單個(gè)或兩個(gè)連續(xù)漢字為人名名字的概率，并針對(duì)漢字串的兩類(lèi)構(gòu)成情況，設(shè)計(jì)了針對(duì)性的統(tǒng)計(jì)模型，且每個(gè)統(tǒng)計(jì)模型對(duì)于決策樹(shù)規(guī)則的每一個(gè)分支分別訓(xùn)練，從而實(shí)現(xiàn)多模型人名識(shí)別方法；

（1）情況一：漢字串不成詞

漢字串不成詞表示給定子串為單個(gè)漢字或兩個(gè)獨(dú)立漢字，本算法采用隱馬爾科夫模型進(jìn)行計(jì)算；

設(shè)隱狀態(tài)集合為S?=?{S₁?=?人名，S₂?=?非人名}，初始概率矩陣π?=?[π₁,?π₂]分別表示人名出現(xiàn)和不出現(xiàn)的先驗(yàn)概率，狀態(tài)轉(zhuǎn)移矩陣A為：

式(1.3)中，a_ij表示第i個(gè)隱狀態(tài)到第j個(gè)隱狀態(tài)的轉(zhuǎn)移概率；

設(shè)給定字串w?=?w₁w_2。。。w_n(n?=?1,?2)，d_i為漢字w_i的人名用字實(shí)體角色指數(shù)，則觀察值矩陣B為：

結(jié)合式(1.3)和式(1.4)，可得用于不成詞漢字串為人名名字隱馬爾科夫概率評(píng)估模型：

本算法利用前向算法對(duì)模型(1.5)進(jìn)行概率計(jì)算，得到給定不成詞漢字串作為人名名字的概率，并結(jié)合預(yù)設(shè)閾值得到最終的判定結(jié)果，模型參數(shù)和預(yù)設(shè)閾值根據(jù)本算法的決策樹(shù)規(guī)則分支分別進(jìn)行訓(xùn)練；

（2）情況二：漢字串成詞

漢字串成詞表示給定子串為兩個(gè)組合成詞的漢字，本算法采用線(xiàn)性加權(quán)法進(jìn)行計(jì)算；

設(shè)給定字串w?=?w₁w₂，d₁、d₂分別為漢字w₁、w₂的人名用字實(shí)體角色指數(shù)，F(xiàn)為詞w₁w₂做常用詞的使用頻數(shù)，使用頻數(shù)由語(yǔ)料庫(kù)統(tǒng)計(jì)，可通過(guò)詞典查詢(xún)獲得，則該字串做人名使用的概率計(jì)算模型為：

?????

其中:

h_1max和h_1min，h_2max和h_2min分別為漢字w₁，w₂預(yù)設(shè)的最小和最大閾值；

?為權(quán)重調(diào)節(jié)因子，用于調(diào)整人名用字指數(shù)和詞串使用頻數(shù)的權(quán)重；

F_max為預(yù)設(shè)詞串最大使用頻數(shù)，以上參數(shù)均由訓(xùn)練語(yǔ)料庫(kù)訓(xùn)練設(shè)定；

模型1.6表示，若字串的使用頻數(shù)大于等于F_max或者兩個(gè)字的人名用字指數(shù)小于預(yù)設(shè)最小閾值，則直接排除為人名；若字串使用頻數(shù)小于F_max，且兩個(gè)字的人名用字指數(shù)都大于預(yù)設(shè)閾值，則直接判定為人名；否則根據(jù)線(xiàn)性加權(quán)式計(jì)算其為人名名字的概率；

2.在線(xiàn)識(shí)別

在線(xiàn)識(shí)別包括中文分詞、角色矩陣構(gòu)建、候選人名搜索、決策樹(shù)規(guī)則分支和人名識(shí)別五個(gè)過(guò)程；

2.1中文分詞

中文分詞是將連續(xù)的語(yǔ)言文本字符串切分為詞序列，本算法采用改進(jìn)最大匹配算法實(shí)現(xiàn)；給定語(yǔ)言文本字符串，W=w1w2…wn，改進(jìn)最大匹配算法流程為：

（1）?遍歷字符串W，根據(jù)詞典對(duì)wi執(zhí)行最大匹配操作，并將匹配得到的詞依次添加到初始詞序列T，遍歷結(jié)束后，得到T={t1,?t2,?…,?tn}，其中，ti表示在W中，以wi開(kāi)頭的最長(zhǎng)詞條；

（2）?檢測(cè)T內(nèi)的任意兩相鄰詞條，若存在詞條ti和ti+1滿(mǎn)足交集條件ti∩ti+1!=??，則若ti與ti+1同時(shí)不滿(mǎn)足全集條件ti?!=?ti?∪ti+1,則將ti標(biāo)記為交叉歧義，然后令ti?=?ti?∪ti+1，并刪除ti+1，重復(fù)當(dāng)前步驟，直到T內(nèi)不存在任意兩相鄰詞條滿(mǎn)足交集條件；??

（3）?采用交叉歧義消解算法依次對(duì)T內(nèi)所有標(biāo)記為交叉歧義的元素執(zhí)行歧義消解，從而最終得到詞序列T；

2.2角色矩陣構(gòu)建

角色矩陣描述了給定語(yǔ)言文本詞序列中所有的人名實(shí)體相關(guān)信息，是本算法人名識(shí)別過(guò)程的數(shù)據(jù)基礎(chǔ)；通過(guò)引入角色矩陣，能夠以最簡(jiǎn)潔的方式提取和描述給定詞序列中所有人名識(shí)別相關(guān)信息，為后續(xù)的人名識(shí)別過(guò)程帶來(lái)極大便利；

設(shè)語(yǔ)言文本的詞序列為T(mén)={t1,?t2,?…,?tN}(N?>?0)，N為詞序列元素個(gè)數(shù)，人名實(shí)體角色類(lèi)別總數(shù)為M(M?>?0，本算法M?=?4)，則詞序列T的角色矩陣為：

其中，d_ij(1≤?i?≤?N,?1≤?j?≤?M)表示詞序列T中第i個(gè)詞的第j種實(shí)體角色指數(shù)，若第i個(gè)詞不擔(dān)任第j種實(shí)體角色，則d_ij=?0.0；當(dāng)N=1時(shí)，即詞序列中僅有一個(gè)詞，角色矩陣退化為該詞的角色向量；

角色矩陣的構(gòu)建包括兩個(gè)步驟：1）通過(guò)角色詞庫(kù)查詢(xún)給定詞序列中每個(gè)詞的角色向量；2）將所有詞的角色向量組合得到詞序列的角色矩陣；

2.3人名初定位

由于本算法對(duì)識(shí)別的人名范圍定義在同時(shí)存在姓氏和名字的中國(guó)人名，因此人名的初定位可以看做姓氏的識(shí)別，即遍歷角色矩陣，找到所有姓氏角色指數(shù)大于0.0位置；

連姓是人名初定位過(guò)程最困難的問(wèn)題，本算法采用回溯算法解決連姓情況，人名初定位算法如下：

（1）令i=0，設(shè)角色矩陣D_MN，回溯棧S，初始為空；

（2）獲取D中第i個(gè)詞的姓氏指數(shù)，若已到矩陣末尾，則未人名，算法終止；若姓氏指數(shù)值為0.0，則i?=?i?+?1，重復(fù)第（2）步；否則，執(zhí)行第（3）步；

（3）識(shí)別第i個(gè)詞是否存在連姓情況，若存在連姓，且最靠前的連姓位置為j，則將i壓入棧S，令i?=?j，重復(fù)第（3）步；若不存在，則以i為人名初定位位置，輸出；

2.4候選人名搜索

候選人名搜索以人名初定位位置為姓氏，根據(jù)決策樹(shù)規(guī)則從角色矩陣?yán)镎页鏊蟹先嗣麡?gòu)成特征的候選人名，得到給定姓氏的候選人名集合；候選人名搜索通過(guò)決策樹(shù)規(guī)則直接排除不符合人名構(gòu)成特征的情況，減少統(tǒng)計(jì)計(jì)算次數(shù)，從而提升算法整體效率；

本算法采用的人名構(gòu)成特征包括以下三點(diǎn)：

（1）去除姓氏后的人名總數(shù)不超過(guò)2個(gè)字；

（2）名字中所有字的人名用字指數(shù)都不得低于指定閾值；

（3）對(duì)于名字為2個(gè)字的情況，至少有1個(gè)字的人名用字指數(shù)大于指定閾值，本算法閾值設(shè)定為0.1，已通過(guò)實(shí)驗(yàn)證明該規(guī)則的有效性；

每個(gè)候選人名具有兩類(lèi)屬性，分別為：

（1）位置屬性；位置屬性描述候選人名在角色矩陣中的位置，包括姓氏位置，尾界位置和名字長(zhǎng)度三個(gè)屬性，姓氏位置和尾界位置分別表示候選人名的姓氏和名字的最后一個(gè)字在角色矩陣的列號(hào)，名字長(zhǎng)度表示候選人名名字的字?jǐn)?shù)；

（2）特征屬性；特征屬性描述候選人名的出現(xiàn)特征，包括姓氏指數(shù)、上文特征指數(shù)和下文特征指數(shù)；

2.5人名判定

人名判定過(guò)程是從指定姓氏在給定角色矩陣中的候選人名集合中判斷是否存在人名，若不存在則輸出非人名，否則輸出人名在角色矩陣中的位置信息；人名判定過(guò)程包括兩個(gè)步驟：（1）采用基于決策樹(shù)規(guī)則和多種統(tǒng)計(jì)模型相結(jié)合的方法判定候選人名集合中的人名；（2）根據(jù)第（1）步的判定結(jié)果，輸出識(shí)別結(jié)果，若判定結(jié)果為空，即所有候選人名都被判定為非人名，則輸出非人名；若判定結(jié)果為多個(gè)人名，表示出現(xiàn)人名歧義，則根據(jù)人名在語(yǔ)料文本中的出現(xiàn)特征選擇出現(xiàn)可能性最大的候選人名為識(shí)別結(jié)果；否則，直接輸出識(shí)別結(jié)果；

決策樹(shù)規(guī)則算法如下：

（1）給定候選人名P?=?{S,?E,?N,?}和對(duì)應(yīng)的角色矩陣D，設(shè)D[i]表示D中的第i列，即詞序列中的第i個(gè)詞的實(shí)體角色指數(shù)向量;

（2）決策樹(shù)第一層根據(jù)D[S]的姓氏指數(shù)和上下文特征指數(shù)判定該處出現(xiàn)人名的可能性，若姓氏指數(shù)或者上下文特征指數(shù)高于指定閾值，則表示此處出現(xiàn)人名的可能性很大，子分支判定的閾值應(yīng)當(dāng)適當(dāng)降低，且以提升人名識(shí)別召回率為識(shí)別目的；若姓氏指數(shù)或者上下文特征指數(shù)低于指定閾值，則表示此處出現(xiàn)人名的可能性較小，子分支判定閾值應(yīng)提高，且以提升人名識(shí)別準(zhǔn)確率為識(shí)別目的；

（3）決策樹(shù)第二層根據(jù)人名的構(gòu)成特征進(jìn)行決策，旨于選擇合適的統(tǒng)計(jì)模型進(jìn)行統(tǒng)計(jì)計(jì)算與人名判定；若構(gòu)成名字的漢字串不成詞，則采用單字模型計(jì)算，若構(gòu)成名字的漢字串成詞，則采用雙字詞模型計(jì)算；最后根據(jù)計(jì)算結(jié)果與預(yù)設(shè)閾值的對(duì)比得到判定結(jié)果，預(yù)設(shè)閾值由決策樹(shù)第一層得出。