一种改进的个性化地图用户知识挖掘方法研究

李 萌，陈毓芬，方 潇

（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