一種改進的個性化地圖用戶知識挖掘方法研究

李 萌，陳毓芬，方 瀟

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

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

1 相關理論概念

1.1 個性化地圖服務

1.1.1 相關理論研究

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

自適應地圖服務是根據用戶個性主動提供服務的一種模式。Talhofer[8]提出能夠對動態情境作出反應的地圖，稱為自適應地圖，這是一種基于情景的自適應地圖概念。隨著自適應地圖服務的升溫，凌云等[9]總結了用戶界面設計中的用戶認知因素，提出一種可視化系統自適應界面的初步系統。

1.1.2 用戶分析

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

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

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

例如，“正向最大匹配算法”這一字符串，我們設定n為4，則首先取字符串“正向最大”與詞典詞條進行匹配，發現不存在該詞條，則去掉尾字取“正向最”繼續匹配，直到找到“正向”為止，然后切分出來；取“最大匹配”繼續循環，直到切分出“算法”為止。

2 基于FMM的改進算法

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

圖1 算法流程圖

通過總結分析部分用戶數據發現，在用戶知識中，用戶的信息單元詞性與用戶特征詞之間有著密切關聯。因此，根據TF·IDF公式計算其間的特征權重：

式中，tfi為與用戶屬性有關的ti詞性信息單元的詞頻；N為總的特征詞數；ni為與ti相關的特征詞數。權重結果如表1。

表1 信息單元詞性與用戶特征間權重分配

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

3 實驗結果

采用C#語言，基于VS2008開發平臺實現基本算法。所用的訓練語料庫是1998年1月份《人民日報》切分標注語料，帶有詞性標注。并建立用戶特征詞典，收錄與用戶屬性相關的特征詞。抽取網絡旅游攻略5篇，經過去除網頁效果和圖片、鏈接等數據預處理，保留文本部分進行實驗，設置合適閾值，實驗結果如表2。其中，召回率=提取總數/詞總數，準確率=有效總數/提取總數。

表2 實驗結果

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

圖2 旅游路線圖

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

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

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

[4]吳增紅.個性化服務理論與方法[D].鄭州：信息工程大學,2011

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

[6]陳勇.利用ArcIMS設計與實現WebGIS的新方法[J].測繪與空間地理信息,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]凌云,陳毓芬,王英杰.基于用戶認知特征的地圖可視化系統自適應用戶界面研究[J].測繪學報,2005,34(3):277-282

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

[10]聞玉彪.一種改進的最大匹配中文分詞算法[J].計算機技術與發展,2011，21(10):92-94