李 萌，陳毓芬，方 瀟

（1. 信息工程大學(xué) 地理空間信息學(xué)院，河南 鄭州 450052）

個(gè)性化信息服務(wù)[1,2]主要有兩種形式：一種是根據(jù)用戶提出的明確要求提供被動(dòng)信息服務(wù)，另一種是通過分析、過濾用戶的個(gè)性、行為、習(xí)慣等數(shù)據(jù)信息，提供主動(dòng)服務(wù)。以用戶為中心是個(gè)性化地圖服務(wù)的重要特點(diǎn)，而如何從非結(jié)構(gòu)化的用戶屬性、要求、個(gè)性、行為等記錄數(shù)據(jù)中提取有效信息，并形成結(jié)構(gòu)化知識(shí)，是目前個(gè)性化研究的重中之重。FMM（maximum match）算法是知識(shí)發(fā)現(xiàn)技術(shù)中較為常用的信息提取方法，能夠有效地掃描中文文本，把文本分解成為詞的集合，從而實(shí)現(xiàn)中文文本的分詞提取[3]。本文將FMM算法進(jìn)行改進(jìn)，將其應(yīng)用于個(gè)性化地圖用戶的知識(shí)挖掘過程中。

1 相關(guān)理論概念

1.1 個(gè)性化地圖服務(wù)

1.1.1 相關(guān)理論研究

個(gè)性化地圖服務(wù)是以滿足用戶以地圖為載體的地理信息個(gè)性化需求為目標(biāo)，實(shí)現(xiàn)服務(wù)資源、服務(wù)方式、服務(wù)內(nèi)容個(gè)性化，來提高用戶效率、改善用戶體驗(yàn)的地圖服務(wù)[4]。個(gè)性化地圖服務(wù)分為定制服務(wù)和自適應(yīng)服務(wù)兩種。定制服務(wù)是按照用戶要求，被動(dòng)提供服務(wù)的一種模式，主要有：①地圖制圖軟件定制服務(wù)，如ArcInfo[5]、ArcIMS[6]、MapXtreme[7]等，可以通過一定的操作和規(guī)則實(shí)現(xiàn)用戶的需求；②移動(dòng)地圖定制服務(wù)，主要是在移動(dòng)設(shè)備上使用，可以更好地體現(xiàn)個(gè)性化；③網(wǎng)絡(luò)地圖定制服務(wù)，如Google Map、MapABC等。

自適應(yīng)地圖服務(wù)是根據(jù)用戶個(gè)性主動(dòng)提供服務(wù)的一種模式。Talhofer[8]提出能夠?qū)?dòng)態(tài)情境作出反應(yīng)的地圖，稱為自適應(yīng)地圖，這是一種基于情景的自適應(yīng)地圖概念。隨著自適應(yīng)地圖服務(wù)的升溫，凌云等[9]總結(jié)了用戶界面設(shè)計(jì)中的用戶認(rèn)知因素，提出一種可視化系統(tǒng)自適應(yīng)界面的初步系統(tǒng)。

1.1.2 用戶分析

個(gè)性化地圖服務(wù)的基本思想是以用戶為中心[4]。因此，從非結(jié)構(gòu)化的用戶信息數(shù)據(jù)中提取結(jié)構(gòu)化的用戶知識(shí)，是實(shí)現(xiàn)個(gè)性化地圖服務(wù)的基礎(chǔ)。用戶信息包括兩方面：①背景屬性信息，如性別、年齡、愛好、受教育程度、收入等；②行為信息，如地圖操作、數(shù)據(jù)查詢、定制操作等。只要掌握這兩部分信息，再加以分析總結(jié)，制定相應(yīng)的服務(wù)規(guī)則，便可以基本實(shí)現(xiàn)為其提供個(gè)性化服務(wù)。

1.2 正向最大匹配算法（FMM）

FMM[10,11]的基本思想為：①將文檔從左至右取長(zhǎng)度為n的字符串M；②將獲取的字符串M與詞典中的詞條進(jìn)行匹配，若存在則匹配成功，將該詞M從文檔中切分出來并保存，然后從文檔n+1處繼續(xù)取長(zhǎng)度為n的字符串進(jìn)行下一次匹配；③若M在詞典中不存在，即匹配不成功，則從M尾部去掉一個(gè)字，形成新的字符串繼續(xù)匹配，直到找到相應(yīng)的詞條，并切分出來；④重復(fù)上述過程，直到將文檔的全部詞提取保存下來。

例如，“正向最大匹配算法”這一字符串，我們?cè)O(shè)定n為4，則首先取字符串“正向最大”與詞典詞條進(jìn)行匹配，發(fā)現(xiàn)不存在該詞條，則去掉尾字取“正向最”繼續(xù)匹配，直到找到“正向”為止，然后切分出來；取“最大匹配”繼續(xù)循環(huán)，直到切分出“算法”為止。

2 基于FMM的改進(jìn)算法

通過分析用戶相關(guān)數(shù)據(jù)可以發(fā)現(xiàn)，雖然用戶的屬性、行為等信息因人而異，但是用戶數(shù)據(jù)中的特征關(guān)鍵詞具有相同性。因此，可以通過對(duì)MM算法進(jìn)行改進(jìn)，在用戶信息關(guān)鍵詞庫基礎(chǔ)上，借助關(guān)聯(lián)規(guī)則，對(duì)用戶信息進(jìn)行提取。改進(jìn)算法的思想為：兩次利用FMM算法先后對(duì)句首詞的首字和尾字進(jìn)行匹配分析，從而將數(shù)據(jù)拆分為信息單元，并同時(shí)標(biāo)記相應(yīng)特征屬性（如詞性、是否特征詞，所屬用戶信息類別等）。算法流程如圖1。

圖1 算法流程圖

通過總結(jié)分析部分用戶數(shù)據(jù)發(fā)現(xiàn)，在用戶知識(shí)中，用戶的信息單元詞性與用戶特征詞之間有著密切關(guān)聯(lián)。因此，根據(jù)TF·IDF公式計(jì)算其間的特征權(quán)重：

式中，tfi為與用戶屬性有關(guān)的ti詞性信息單元的詞頻；N為總的特征詞數(shù)；ni為與ti相關(guān)的特征詞數(shù)。權(quán)重結(jié)果如表1。

表1 信息單元詞性與用戶特征間權(quán)重分配

除了詞性與特征詞之間的關(guān)聯(lián)外，詞所處的位置也將直接影響其間的關(guān)聯(lián)度：①詞間距離與詞關(guān)聯(lián)成反比，信息單元離用戶特征詞越近，兩者之間的關(guān)聯(lián)越強(qiáng)；②同句兩者關(guān)系更密切，隔句關(guān)系驟減；③除了修飾性詞，關(guān)聯(lián)中信息單元處于特征詞之后遠(yuǎn)比之前重要。基于以上分析，根據(jù)知識(shí)發(fā)現(xiàn)中常見的關(guān)聯(lián)Apriori算法，以用戶特征詞C為中心，信息單元W為信息提取對(duì)象，建立整個(gè)用戶信息的關(guān)聯(lián)矩陣：

3 實(shí)驗(yàn)結(jié)果

采用C#語言，基于VS2008開發(fā)平臺(tái)實(shí)現(xiàn)基本算法。所用的訓(xùn)練語料庫是1998年1月份《人民日?qǐng)?bào)》切分標(biāo)注語料，帶有詞性標(biāo)注。并建立用戶特征詞典，收錄與用戶屬性相關(guān)的特征詞。抽取網(wǎng)絡(luò)旅游攻略5篇，經(jīng)過去除網(wǎng)頁效果和圖片、鏈接等數(shù)據(jù)預(yù)處理，保留文本部分進(jìn)行實(shí)驗(yàn)，設(shè)置合適閾值，實(shí)驗(yàn)結(jié)果如表2。其中，召回率=提取總數(shù)/詞總數(shù)，準(zhǔn)確率=有效總數(shù)/提取總數(shù)。

表2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)表明，在將非結(jié)構(gòu)化的文本數(shù)據(jù)提取整合成結(jié)構(gòu)化的信息知識(shí)時(shí)，通過改進(jìn)算法，可以有效提取不同詞性的詞語，其中數(shù)值型召回率最高，達(dá)到97.41%；形容詞、副詞最低，只有77.05%。另外，結(jié)合關(guān)聯(lián)分析技術(shù)，將提取出的詞進(jìn)行篩選方面有待加強(qiáng)，名詞最高，達(dá)到75.13，動(dòng)詞、形容詞、副詞偏低。將其中一篇旅游攻略中使用改進(jìn)算法提取出的用戶攻略中所走的景點(diǎn)路線通過地圖可視化，如圖2。

圖2 旅游路線圖

[1]范寶梅,韓勇,齊永陽.個(gè)性化電子地圖中用戶信息定制服務(wù)實(shí)現(xiàn)[J].地理空間信息,2011，9(2):144-146

[2]胡錫衡.正向最大匹配算法在中文分詞技術(shù)中的應(yīng)用[J].鞍山師范學(xué)院學(xué)報(bào),2008,10(2):42-45

[3]王翠萍.面向個(gè)性化服務(wù)的信息資源組織與集成研究[M].北京：科學(xué)出版社,2010

[4]吳增紅.個(gè)性化服務(wù)理論與方法[D].鄭州：信息工程大學(xué),2011

[5]張芬,高炎.桌面式ArcInfo的組成與定制開發(fā)[J].海洋測(cè)繪,2002,22(6):11-14

[6]陳勇.利用ArcIMS設(shè)計(jì)與實(shí)現(xiàn)WebGIS的新方法[J].測(cè)繪與空間地理信息,2005,28(2):47-50

[7]Talhofer V. Transport of Dangerous Chemical Substances and Its Cartographic Visualisation[C].10th AGILE International Conference on Geographic Information Science 2007,Denmark,2007

[8]凌云,陳毓芬,王英杰.基于用戶認(rèn)知特征的地圖可視化系統(tǒng)自適應(yīng)用戶界面研究[J].測(cè)繪學(xué)報(bào),2005,34(3):277-282

[9]王慧仙.基于改進(jìn)的正向最大匹配中文分詞算法研究[J].貴州大學(xué)學(xué)報(bào)：自然科學(xué)版,2011，28(5):112-115

[10]聞?dòng)癖?一種改進(jìn)的最大匹配中文分詞算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2011，21(10):92-94