 Computer Science and Application 计算机科学与应用, 2013, 3, 232-238 http://dx.doi.org/10.12677/csa.2013.34040 Published Online July 2013 (http://www.hanspub.org/journal/csa.html) The Study and Implementation of Web User Mining System Based on the Similarity of Words* Chengxia Liu1,2, Feiying Wu2 1Computer School, Beijing University of Posts and Telecommunications, Beijing 2Computer School, Beijing Information and Technology University, Beijing Email: cecilia7812@163.com Received: May 13th, 2013; revised: May 27th, 2013; accepted: Jun. 5th, 2013 Copyright © 2013 Chengxia Liu, Feiying Wu. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Abstract: Nowadays, as web mining is extremely prevalent, it is easy to collect huge amounts of data but to figure out which materials are useful to analyze after de-noising is more important. This article discusses how to use the result of user’s searching keywords clustering as the label of the client for operational analysts to refer to. The similarity between isolated words is calculated by turning the word semantic distance based on world knowledge or classification system. Then the similarity between clients (keyword sets) is defined as the Euclidean distance of a similarity matrix constituted by the similarities between keyword sets which determined by word frequency and word weight. The “depmix” package which based on the Hidden Markov Model in “R” software is used as the clustering algorithm and the user clustering result is displayed at last using the real data of the users of a search engine. Keywords: The Similarity of Words; The Similarity Between Clients (Keyword Sets); User Clustering 基于关键词相似度的 Web 用户挖掘研究与实现* 刘城霞 1,2，吴菲滢 2 1北京邮电大学计算机学院，北京 2北京信息科技大学计算机学院，北京 Email: cecilia7812@163.com 收稿日期：2013 年5月13 日；修回日期：2013年5月27日；录用日期：2013 年6月5日 摘 要：在Web 挖掘极度盛行的今天，收集大量网络数据已经不是问题，而如何在海量数据中抽取去噪后的有 用数据成为要解决的关键问题。本文研究将网站用户的搜索关键词分析聚类，作为用户的兴趣、爱好标签，以 供运营分析人员参考。文中根据世界知识或分类体系计算词语语义距离后转化为词语相似度的方法，将词语间 距离依据词频、词权重等因子加工计算出关键词集合间相似度矩阵后，用欧式距离表示其关键字集的相似度； 之后聚类算法利用现有R软件中开源算法包——基于隐马尔科夫模型的depmix 算法包进行的用户聚类算法。最 终用某搜索引擎用户的真实数据，经过数据去噪后所得实验数据进行聚类，并于前台展示聚类及用户周边相关 结果。 关键词：词语相似度；关键词集合相似度；用户聚类 1. 引言 近些年来互联网行业飞速发展，机构、团体和个 人越来越多地依赖互联网发布信息、查找信息，这成 就了互联网上的海量数据，但同时这些无结构的、动 *资助信息：北京市人才强教计划——骨干教师(PHR201008428)，北京 市教委科技发展计划项目(KM201110772013)资助。 Copyright © 2013 Hanspub 232  基于关键词相似度的 Web 用户挖掘研究与实现 态的 Web 页面的复杂程度远远超过了文本文档，所以 人们要想找到自己想要的数据依然犹如大海捞针一 般。Web 挖掘是将传统的数据挖掘技术和Web 结合起 来，就能解决这些问题。 如果说 Web 使用挖掘是通过挖掘访问者在网站 上留下的痕迹来获取有用的信息，那么Web 用户挖掘 则是要寻找 Web用户的根源。通过对 Web用户信息 的统计分析，能够帮助运营商以较低成本获得准确度 较高的客户兴趣倾向、个性化需求以及新业务发展趋 势等信息。 本文是基于搜索引擎用户进行的研究，致力于根 据不同用户的不同搜索关键词，为用户打上相应的个 性标签，以便运营分析人员对用户的兴趣、爱好有更 精确的方向上的把握，并且做出更好的信息推送及搜 索引擎优化。 2. 关键词间相似度算法 2.1. 相似度计算的基本概念 相似度计算中有两个主要的概念为：“概念”与 “义原”。“概念”是用来描述词汇的语义的，一个 词语可以用一个或多个概念来表示。这种描述方法叫 做用“知识表示语言”来描述词语的语义，而这种用 来构成“知识表示语言”的“词汇”就叫做“义原”。 与一般的语义词典不同，“知网”中的概念层次 树并不仅仅是一个归结了所有 “概念”的概念层次 体系树，而是将每一个“概念”用一系列的“义原” 来描述清晰。 “知网”将义原分为以下几个大类[1]： 1) Event|事件 2) entity|实体 3) attribute|属性值 4) aValue|属性值 5) quantity|数量 6) qValue|数量值 7) SecondaryFeature|次要特征 8) syntax|语法 9) EventRole|动态角色 10) EventFeatures|动态属性 这些义原大致被归为3组： 第1组，第1~7 类义原，称之为“基本义原”， 用来描述单个概念的语义特征； 第2组，第8类义原，称之为“语法义原”，用 于描述词语的语法特征，主要是词性的表达； 第3组，第9、10 类义原，称之为“关系义原”， 用于描述概念和概念之间的关系。 2.2. 词语相似度算法分析 对于两个词语 W1和W2，如果 W1有n个概念： S11，S12，…，S1n，W2有m个概念：S21，S22，…， S2m，把两词语间的相似度问题定义为两组概念间的相 似度问题。 1) 义原相似度的计算 义原间的相似度计算是概念相似度的计算的基 础，因为所有概念最终都会归结于用义原来表示。本 文采用通过语义距离来计算义原结点间相似度的办 法，即假设两个义原在此层次体系中的路径距离为d， 则这两个义原间的语义距离[2]可由 12 12 Sim ,, WW Dis WW (1) 计算得来，具体化为： 12 Sim ,PP d (2) 其中 为可调节参数，P1和P2表示两个不同义原，d 是P1和P2在层次树中的路径长度，记为一正整数。 2) 虚词概念的相似度的计算 因为在“知网”的知识描述语言中，虚词概念只 用“{句法义原}”或“{关系义原}”这两种方式进行 描述，所以计算虚词概念的相似度就等价于计算其对 应的句法义原或关系义原之间的相似度。 3) 实词概念的相似度的计算 本文采用的相似度计算方法是通过部分相似度 的合成来代替整体相似度。首先建立两个整体中的各 个部分之间一一对应的关系，随后计算各个配对间的 相似度，加权求和。若某一部分的对应为空时其相似 度定义为一个比较小的常数 δ，和具体词与义原的相 似度定义为同一级别。 4) 特征结构和集合的相似度计算 ①特征结构的相似度计算 特征的定义是一个“属性：值”对，特征结构就 是“属性：值”对的集合。在特征结构中，每个“特 Copyright © 2013 Hanspub 233  基于关键词相似度的 Web 用户挖掘研究与实现 征”的“属性”是唯一的。将特征结构的相似度转化 为各个特征之间的相似度的均值。两个特征的相似度 就等价于其“值”的相似度。 ②集合的相似度计算 两个集合的相似度计算的简单模型如下： m < n) 个元 阵； ) 在相似度矩阵中挑出最大相似度后，将其对应 的两 出这些已建立关联对的元 素及 直至某一集合中所有元素 都已 素对应。 关系 词概念相似度的计算 为一个特征结构，该 特征 最重要的一个基本义 原， 描述：即除第一基本义原以外所有 基本 系义原描述：即语义表达式中所有的关系义 原， ：即所有的关系符号描述式，也表示 为一 却相 其中，βi(1 ≤ i ≤ 4)是可调节的各部分相似度权重参数， stubborn| 倔， 文字，surname|姓，human|人， Prop vestock|牲畜 共有表示性格、姓氏以及动物 三个 为：“属性值”，“文字”， “牲 义原，默认最大距离20， 相似 似度 Sim1(文字) = 0.15 畜” 义原距离为 2，相似度 Sim1(牲畜) = 0.44 其它基本义原描述 义原:“举止”，“倔”， “莠 )/m，其中sum 为 两组 A．一个集合与它本身的相似度为 1； B．假设两个集合都有n个元素，其中m( 素相同，又假设两个元素的相似度只能是0(不同) 或1(相同)，那么这两个集合的相似度应该是m/n。 而两个集合各个元素之间的一一对应关系如下： a) 生成两个集合中所有元素两两间相似度的矩 b 个元素关联为一对； c) 从相似度矩阵中取 其相互间的相似度； d) 重复第 b、c两步， 与另一集合中某元素生成关联对； e) 将没有建立起对应关系的元素与空元 根据上述方法建立起两个集合元素的一一对应 后，集合的相似度等于其元素对的相似度的算术 平均。 5) 实 对一个实词的描述可以表示 结构含有以下四个特征： 第一基本义原描述：即实词 两个概念相对应的这一部分的相似度记为： Sim1(S1, S2)； 其它基本义原 义原的集合，这一部分的相似度记为：Sim2(S1, S2)； 关 表示为一个特征结构，这一部分的相似度记为： Sim3(S1, S2)； 关系符号描述 个特征结构，这一部分的相似度记为： Sim4(S1, S2)。 考虑以下情况：当Sim1非常小，但Sim3或者 Sim4 对较大时，若直接计算相似度平均值会导致整体 的相似度仍然较大，但不合理的现象。因此很多改进 的词语相似度算法也就应运而生[4-6]，本文改进实词间 相似度算法后公式如下： 4 12 1 12 1 Sim ,Sim, i ij j i SS SS (3) 且有：β1 + β2 + β3 + β4 = 1, β1 ≥ β2 ≥ β3 ≥ β4。β反映了 Sim1到Sim4对于总体相似度所起到的作用依次递减。 其意义在于，主要部分的相似度值对于次要部分的相 似度值起到制约作用，即若主要部分相似度比较低， 那么次要部分的相似度对于整体相似度所起到的作用 也要降低，且可以保证一个词和它本身的相似度为 1。 举例：两个实词“鸟”、“牛”的相似度计算。 查阅词库得到以下概念的解释： 牛 N——value|属性值，behavior|举止， undesired|莠 牛 N——character| erName|专 牛 N——li 鸟 N——bird|禽 可以看到，“牛” 解释，而“鸟”只有禽畜一种解释。下面来具体 分析这两个词的相似度： a) 第一基本义原描述 “牛”的三组基本义原 畜”；“鸟”的基本义原为：“禽”。 根据查询词库可得： “属性值”没有相同根 度Sim1(属性值) = 0.074， “文字” 义原距离为 9，相 1， “牲 。 b) “牛”的三组其它基本 ”；“姓”，“人”，“专”；空。 “鸟”的其它基本义原为空。 因此，由公式(sum + δ*(m − n) 其它基本义原中依次挑出相似度最大的义原对 直至一组基本义原被挑空的相似度之和(由于“鸟”没 有其他基本义原，因此 sum 为0)、m为两组其它基本 义原中较多义原一组的义原个数、n为较少一组的义 Copyright © 2013 Hanspub 234  基于关键词相似度的 Web 用户挖掘研究与实现 原个数，可得这两个关键词的其它基本义原的相似度 Sim2如表 1： c) 关系义原描述：此处两词没有关系义原的解 释， 两词没有关系义原的解 释， 似度描述 因此Sim3 默认为 1.0。 d) 关系符号描述：此处 因此 Sim4 默认为 1.0。 最终“牛”与“鸟”的相 112 1 2 SimSimSim Sim 312 3 41234 Sim Sim Sim Sim SimSimSim 取β1 = 0.5，β2 = 0.2，β3 = 0.17，β4 = 0.13 得 取最大值，得到“鸟”与“猪”的相似度为 Sim = 0.44。 2.3. 用户相似度算法 在确定独立关键词间相似度算法后，便可以得到 两用 矩阵，首先要生成每个用 户与 Table 1. Base similarity of bird and cow 表 牛 户–关键词相似度矩阵并不仅仅是将用户每个搜索 ，其相似 度、 先构 成了 0.5*0.0740.2*0.074*0.2 性值组 Sim 0.17*0.074*0.2*1 0.13*0.074*0.2*1*10.044 属 Sim0.5*0.151 0.2*0.151*0.2 0.17*0.151*0.2*1 0.13*0.151*0.2*1*10.091 文字组 Sim0.5*0.440.2*0.44*1 0.17 * 0.44*1*10.13*0.44*1*1*10.44 牲畜组 户关键词集合的相似度矩阵。传统的文本相似度 算法是基于关键词向量的算法[7,8]，通常可以通过文献 标题、关键词和摘要合并形成特征向量空间来提高文 献表示的精度[9]，但这增加了计算的维度。而且传统 的文本聚类方法都是将文档表示成关键词特征空间 中的一个向量，其取值非0即1，没有考虑关键词部 分的相似性。本文基于以上两点，采用了基于关键词 加权的文献相似度计算方法，在不增加特征向量空间 维数的情况下，考虑了关键词之间的部分相似性，提 高了相似度计算的精度。 要求得各用户之间距离 每个关键词之间的用户–关键词相似度矩阵。用 1. “鸟”与“牛”其它基本义原相似度 其他基本 属性值3个 3个 牲畜无 义原似度 文字 鸟 无 ((0.2 0.2*3)/3 = 0.2 2*3)/3 = 0.默认为1 关键词与关键词集合中关键词间的相似度计算算术 平均值罗列出来，而是加入词频、权重等因子的制衡 的加权平均相似度。其中：某关键词的词频即为该关 键词在所有的关键词总集合中出现的频次；某关键词 的权重为该关键词与所有的关键词总集合中的每一 个关键词相似度的最大值。那么最终用户(关键词集合) 与关键词间的相似度就由以下算法确定： 对于每一个关键词–用户搜索关键词对 用户搜索关键词词频以及用户搜索关键词的乘积 进行求和后比上每一对后两者的乘积求和所得的商 便是最终的用户–关键词的加权平均相似度。 n个关键词集合(用户)与m个特征关键词首 用户-关键词矩阵(n × m)，定义为： 11 1m QQ 1n QQ n m (5) ij Q 定义如下： 其中， 1 1 , it j tQkw kw it it ij it it t TkwW kw Q Tk w Wkw (6) 其中，Q(kwit, kwj)表示关键词集合(用户)i的第t个关 键词与关键词集合W中第j个关键词的相似度；T(kwit) 是关键词集合 i的第 t个关键词在关键词集合中出现 的频次；W(kwit)是关键词集合(用户)i的第 t个关键词 的权重。由于Q的取值在[0,1 ]之间，显然 ij Q ∈[0,1]。 ij Q 的定义考虑了将关键词综合加权来表示关键词集 用户)在特征空间中的取值。 使用欧式距离表示关键词与 合( 关键词集合(用户)的 相似度。即两用户间距离表示为两用户与每个关键词 相似度的差平方的和的开平方，相似度 S定义公式如 下： 2 1 m ik jk k SQQ (7) 由以上定义可得出关键词与用户 可以 描述： 的相似度(S)，并 以此为依据聚类出与关键词相关的用户群。 3. 相似度算法设计 3.1. 词语间相似度算法 词语间相似度计算算法 Copyright © 2013 Hanspub 235  基于关键词相似度的 Web 用户挖掘研究与实现 step1：若两词语中有一个词语未收录到词库中， 则默 两词语相关联的所有解释概念 (义原 ep3：计算两个解释概念的相似度时，若两概念 一为 3.2. 算法涉及 (KeywordVector)、关键词 与关 细 信息 述： 键词 算两用户 与同 与同 集合中所 有关 户间 get_sim_VV(int client1_id, int cli- ent2 i; sum = 0.0; 每一个关键词的相似度的差 平方 个数;i++){ 相似度矩阵中的位 置， = 取得 client1_id 的第 i个关键词； 相 似度 = temp_differ*temp_differ;//计算相似度，求 差平 th.sqrt(sum);//求和后的差平方开平方} 词 在 “用 得到两用户 与同 集合中所 有关 两用 户间 le getVWsim(int[] vcti, int j)//vcti为 关键 sum_sim_t_w, sum_t_w; 认相似度为0； step2：分别计算 /基本词)的相似度，取其最大值为两词语相似 度； st 实词一为虚词，则相似度默认为 0；若两概念均 为虚词，则返回其虚词义原间相似度；若两概念均为 实词，则分别计算其第一基本义原相似度、其他基本 义原相似度、关系义原相似度以及关系符号相似度， 依照(2)计算其相似度并返回。 用户间相似度算法 到关键词集合 键词集合相似度(Similarity_V_W) 和关键词集合 间相似度(VectorSimilarity)三个类，其关系如下： 一个 KeywordVector 实例提供所有关键词的详 及个关键词间相似度矩阵的map；一个 Similarity _V_W 实例在初始化时，便根据 clients文件计算出所 有不重复关键词向量及个个关键词的词频、id，并查 询KeywordVector 实例中的相似度矩阵生成所有用户 与关键词间的相似度矩阵。而一个 VectorSimilarity实 例通过查询一个Similarity_V_W 的实例，提供了计算 用户间相似度的计算方法。 用户–用户相似度算法描 依次从关键词集合中取出一个关 step1：根用户 id以及关键词 id分别计 一关键词在“用户–关键词”相似度矩阵中的 id； setp2：根据这两个 id 查询相似度矩阵得到两用户 一关键词的相似度，并求其差平方； step3：重 复 第step1-step3 步直至关键词 键词已使用过，过程中将相似度的差平方累加； step4：将最后的累加和开平方后得到的就是两用 的相似度。 public double _id) {int Double //将两关键词集合与 求和后再开平方 for(i = 0;i<关键词 //计算用户与关键词相似度在 即其 id int key1 int key2 = 取得 client2_id 的第 i个关键词； Double temp_differ = 两用户与同一关键词的 差； sum + 方求和} return Ma 用户–关键词相似度算法的算法描述： step1：依次从关键词集合中取出一个关键 step2：根据 id 分别计算两用户与同一关键词 户–关键词”相似度矩阵中的id ； step3：根据这两个 id 查询相似度矩阵 一关键词的相似度，并求其差平方； step4：重 复 第step1-step3 步直至关键词 键词已使用过，将相似度的差平方累加； step5：将最后的累加和开平方后得到的就是 的相似度。 private Doub 字集合 {D o u ble sum_sim_t_w = sum("stw",vcti,j); //计算 1tQk 1 , it jitit ij it it t wkwTkwW kw Q Tkw Wkw ()的分母 sum_t_w = sum("tw",vcti,j); //计算 1tQk 1 , it jitit ij it it t wkwTkwW kw Q Tkw Wkw ()的分子 Double vwSim = sum_sim_t_w/sum_t_w;//计算关 键词 4. 结 词语相似度结果分析 两组词语相似度对比如2： 较合理的： –用户相似度 return vwSim;} 果分析 4.1. 表 可以看到，绝大部分结果还是比 Copyright © 2013 Hanspub 236  基于关键词相似度的 Web 用户挖掘研究与实现 Table 2. Result of word similarity 表2. 词语相似度结果分析 词语相似度 鸟 服务 腐败 人 殡葬 主题 0. 0. 04295795 0.0429 0.0664 0.0429 器官 0.1493 0.1667 0.1404 0.0664 0.0429 捐献 0.0741 0.0741 0.0429 0.1379 0.0444 春天 0.4444 0.0444 0.0429 0.0740 0.0444 a) “主题”与另一组中关键词的“人”相似度最 大； ) “器官”与另一组中关键词的“人”相似度最 大； ) “捐献”与另一组中关键词的“服务”相似度 最大 春天”与另一组中关键词的“鸟”相似度最 大； 有部分结果不够合理，例如“捐献”与“人”、 “器 4.2. 用户相似度结果分析 用户关键 “默默”，“张歆艺”} 徐州”} 似度 理，其中 3、4 也有用户相似度结果不太合理的，原因主要 是用 4.3. 用户聚类结果分析 由于用户在进行搜索行为时，会主观根据某一词 条搜 开源软 件包 大联系， 而后 1 2 3 4 5 6 b c ； d) “ 也 官”与“人”的相似度都偏低，原因是“器官”、 “捐献”只有单一概念解释，因此计算相似度时含义 分析不够丰满。这也从一个侧面反映了某些定义不合 理或不一致之处，需要进一步改进。 词集合如下： 1 {“坚守”，“岗位”， 2 {“魅力”，“非凡”，“四季”，“女装”} 3 {“北京”，“企业”，“信用”，“网络”} 4 {“江泽民”，“九寨沟”，“互联网”} 5 {“中国”，“邮政”，“储蓄”} 6 {“银行”，“中国矿业大学”，“ 由于此处计算的是用户间欧氏距离，距离与其相 成反比，则没有绝对最大距离，只有当距离为 0.0 是其相似度确定为1，其距离对比如表3。 可以得到：3、4用户相似度较高比较合 用户都关心网络、地名；而1、5用户相似度较 高则无理可循；同样含有地名“徐州”的用户6与用 户3相似度也较高，他们还共同关心企业方面搜索内 容，反观用户6与用户4的相似度就相对较低，虽然 同样都包含地名，但两者间并无其他共性；用户 2与 所有其他用户的相似度中，与用户1距离最小也比较 合理。 当然 户的搜索关键词本身比较偏僻，导致计算词语相 似度是已经不合理或者该用户的搜索关键词词频较 低及该用户的搜索关键词在关键词集合中的权重较 低。 索结果的满意程度决定下一搜索关键词的内容。 同时随着时间的推移社会热点的变动，搜索关键词的 主流内容也会随之变动。因此可以认为用户的搜索关 键词与用户的兴趣[10]及时间有着密切联系。 在用户聚类过程中，实验采用了 R软件的 中的隐马尔科夫模型用于聚类。通过聚类，测试 数据中 84 位用户共聚类出 24 类用户群，以“电影” 主题相关的聚类结果结果为例分析如表 4： 可以看到前两位用户与“电影”主题有较 5位用户与“电影”主题关联渐弱。原因是挑选 主题相关用户类时是挑选与该主题相似度最大的用 户的所在类，所以并不是该类所有用户都与该主题相 Table 3. Result of user similarity 表3. 用户相似度结果分析 1 / 0.0.6248 0.6893 0.7352 5863 1.0148 2 / / 0.8427 0.9438 0.8142 1.2286 3 / / / 0.5975 0.8331 0.6917 4 / / / / 0.8488 0.9522 5 / / / / / 1.0764 Table 4. Clustef movie title 表4. 果 id r o 题相关的聚类结 “电影”主 注册方式 关键词标签 用户1 1 ipad，iteye 275 手机注册 明天，新闻， 用户2 1231 邮箱注册 2 小 有限公司，物流，公司 黄岩岛，油价，下调， 012，娱乐，音乐，李双江 用户3 1100 手机注册 升初，怪圈，安阳，教育局 用户4 1304 邮箱注册 洛阳，众，托，货运， 赛，成功 用户5 1616 邮箱注册 用户6 1631 手机注册 盘古，搜索，百度 用户7 1224 手机注册 我，爱，你 Copyright © 2013 Hanspub 237  基于关键词相似度的 Web 用户挖掘研究与实现 Copyright © 2013 Hanspub 238 似度很大就 果中聚为 户会 参考文献 (References) . http://wwwzhiwang_r.html 度计算[D]. 报, 2008, 22(5): 84-89. 究[J]. 计算 向量的词语相似度计算 on feature selection 度的中文文本相似度算法研究[D]. 浙 于关键词和摘要相关度的文献聚类研究 兴趣相似性的 Web 用户聚类[J]. 山东 ；还有 是聚类结一类的用有机 各自不同的关注面，因此被选用户类中只有部分用户 与主题相关较大。如希望得到更好的效果，可以参考 文献[3]的方法。 [1] 董振东, 董强. 知网[URL], 2003 .keenage.com/zhiwang/c_ [2] 刘群, 李素建. 基于《知网》的词汇语义相似 中国科学院计算技术研究所, 2002. 北京:[D]. 南京大学, 2008. [10] 张文东, 易轶虎. 基于 [3] 江敏, 肖诗斌, 王弘蔚, 施水才. 一种改进的基于《知网》的 词语语义相似度计算[J]. 中文信息学 [4] 王小林, 王义. 改进的基于知网的词语相似度算法[J]. 计算 应用, 2011, 31(11): 3075-3090. [5] 杨金柱, 刘金岭. 基于词语上下文的文本分类研 机技术与发展, 2011, 21(8): 145-149. [6] 张涛, 杨尔弘. 基于上下文词语同现 [J]. 电脑开发与应用, 2005, 18(3): 41-43. [7] Y. Yang, J. O. Pedersen. A comparative study in text categorization. Proceedings of the 14th International Con- ference on Machine Learning. San Francisco: Morgan Kauf- mann, 1997: 412-442. [8] 金希茜. 基于语义相似 江工业大学, 2009. [9] 魏建香, 苏新宁. 基 大学学报, 2006, 41(3): 45-48. |