2024年5月6日发(作者：勇绚)

维普资讯

第２４卷第７期　

计算机应用研究　

Ｖ０１．２４　Ｎ０．７　

２００７年７月　

Ａｐｐｌｉｃａｔｉｏｎ　Ｒｅｓｅａｒｃｈ　ｏｆ　Ｃｏｍｐｕｔｅｒｓ　

Ｊｕｌｙ　２００７　

面向Ｗｅｂ日志的语义聚类算法术　

潘钧　

（扬州大学信息工程学院，江苏扬州２２５００９）　

摘要：由于现有的Ｗｅｂ日志缺少明显语义，提出一种语义Ｗｅｂ日志模型——ｓｗＬＭ，并给出基于该模型的网　

页和用户聚类算法。通过日志概念的语义距离定量计算来聚类网页和用户，奠定了Ｗｅｂ个性化服务的基础。　

性能测试实验证明，该模型具有较好的整体性能，能有效地进行网页和用户聚类。　

关键词：Ｗｅｂ日志；挖掘；语义；本体　

中图分类号：ＴＰ３１１　文献标志码：Ａ　文章编号：１００１—３６９５（２００７）０７—０２６７—０３　

Ｓｅｍａｎｔｉｃ　Ｃｌｕｓｔｅｒｉｎｇ　Ａｌｇｏｒｉｔｈｍ　Ｏｒｉｅｎｔｅｄ　ｔｏ　Ｗｅｂ　Ｌｏｇ　

ＰＡＮ　Ｊｕｎ　

（Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｙａｎｇｚｈｏｕ　Ｕｎｉｖｅｒｓｉｔｙ，Ｙａｎｇｚｈｏｕ　¨２２５００９，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｅｘｉｓｔｅｄ　Ｗｅｂ　ｌｏｇｓ　ｗｅｒｅ　ｌａｃｋ　ｏｆ　ｓｅｍａｎｔｉｃｓ　ｏｂｖｉｏｕｓｌｙ．Ｔｏ　ｉｍｐｒｏｖｅｄ　ｔｈｅ　ｅｆｆｉｃｉｅｎｃｙ　ａｎｄ　ａｃｃｕｒａｃｙ　ｏｆ　Ｗｅｂ　ｍｉｎｉｎｇ，ａ　ｓｅ—　

ｍａｎｔｉｃ　Ｗｅｂ　ｌｏｇ　ｍｏｄｅｌ　ＳＷＬＭ　ｗａｓ　ｐｒｅｓｅｎｔｅｄ，ａｎｄ　ｔｗｏ　ａｌｇｏｒｉｔｈｍｓ　ｂａｓｅｄ　ｏｎ　ｔｈｉｓ　ｍｏｄｅｌ　ｗａｓ　ｇｉｖｅｎ　ｔｏ　ｃｌｕｓｔｅｒ　ｐａｇｅｓ　ａｎｄ　ｕｓｅｒｓ．　

Ｔｈｅｎ，ｔｈｅ　ｓｅｍａｎｔｉｃ　ｉｎｆｏｒｍａｔｉｏｎ　ｃｏｕｌｄ　ｂｅ　ｍｉｎｉｎｇ　ｆｒｏｍ　ｔｈｅ　Ｗｅｂ　ｌｏｇ，ａｎｄ　ｔｈｅ　ｓｅｍａｎｔｉｃ　ｄｉｓｔａｎｃｅｓ　ｏｆ　ｌｏｇ　ｃｏｎｃｅｐｔｓ　ｃｏｕｌｄ　ｂｅ　ｃｏｍｐｕ—　

ｔｅｄ．Ｔｈｅ　ｔｅｓｔ　ｅｘｐｅｒｉｍｅｎｔ　ｓｈｏｗｓ　ｔｈａｔ　ｔｈｉｓ　ｍｏｄｅｌ　ｈａｓ　ｂｅｔｔｅｒ　ｐｅｒｆｏｒｍａｎｃｅ　ａｎｄ　ｃｌｕｓｔｅｒｓ　ｐａｇｅｓ　ａｎｄ　ｕｓｅｒｓ　ｅｆｆｅｃｔｉｖｅｌｙ．Ｔｈｏｓｅ　ｒｅｓｕｌｔｓ　

ｃａｎ　ｆａｃｉｌｉｔａｔｅ　ｐｅｒｓｏｎａｌｉｚｅｄ　ｓｅｒｖｉｃｅｓ　ａｎｄ　ｕｓｅｒ　ｍｏｄｅｌｉｎｇ．　

Ｋｅｙ　ｗｏｒｄｓ：Ｗｅｂ　ｌｏｇ；ｍｉｎｉｎｇ；ｓｅｍａｎｔｉｃ；ｏｎｔｏｌｏｇｙ　

ｗｅｂ日志挖掘属于Ｗｅｂ使用挖掘。它通过挖掘相关的　基于这三个方面。在数据预处理阶段，文献［５］提出了挖掘异　

Ｗｅｂ日志记录，来发现用户访问Ｗｅｂ页面的模式，通过分析日　常数据的方法和途径。文献［６］提出了基于最大前向引用的事　

志记录中的规律，识别用户的忠实度、喜好、满意度，发现潜在　

务辨识。在模式发现阶段，文献［７］把服务器日志载人数据立　

用户，增强站点的服务竞争力。但是，现有的Ｗｅｂ日志挖掘是　

方体结构，执行ＯＬＡＰ。文献［８］使用Ｍａｒｋｏｖ模型生成序列模　

基于语法的数据挖掘，舍弃了数据之间丰富的语义关联信　

式，用于Ｗｅｂ预取和系统优化；在模式分析阶段，如ＷｅｂＷａｔｃｈｅｒ　

息　０　。为了使Ｗｅｂ上的信息具有计算机可理解的形式语义，　

跟踪用户的浏览行为，辨识出用户可能感兴趣的链接并推荐给　

满足智能软件代理（Ａｇｅｎｔ）对ｗｗｗ上异构和分布信息的有　

用户。对每个用户，ＷｅｂＷａｔｃｈｅｒ先对其兴趣进行简单的描述，　

效访问及检索　，在ＸＭＬ２０００的会议上，Ｂｅｒｎｅｒｓ—Ｌｅｅ提出语义　

然后基于该用户的浏览行为和具有相似兴趣的其他用户的浏览　

Ｗｅｂ及其层次关系——基于ＸＭＬ和ＲＤＦ／ＲＤＦＳ，并在此之上　

行为学习该用户的兴趣。但是现阶段的研究大多都是基于语法　

构建本体（Ｏｎｔｏｌｏｇｙ）和逻辑推理规则，以完成基于语义的知识　

的日志挖掘，随着语义Ｗｅｂ的逐渐升温　，把语义知识和领域　

表示和推理，从而能够被计算机所理解和处理。本体提供了语　

本体集成到Ｗｅｂ日志挖掘中去已经成为可能。　

义Ｗｅｂ上一切对象和行为描述的词汇集合，同时又是Ｗｅｂ上　

数据的解释模板。　

２　语义Ｗｅｂ日志模型——ＳＷＬＭ　

基于本体的语义Ｗｅｂ日志首先定义一个描述概念集，即　

２．１　语义日志模型　

建立符合学科领域要求、用开放语言描述的概念集体系（Ｏｎ—　

基于本体的领域建模的中心任务是建立可共享的领域词　

ｔｏｌｏｙｇ　Ｓｙｓｔｅｍｓ），利用概念集体系对Ｗｅｂ日志的内容进行语义　

标注或语义挖掘，形成基于语义的日志元数据。在此基础上，　

汇集。　

利用概念集中语义定义、语义关系定义和推理规则，实现基于　

定义１　领域本体（Ｄｏｍａｉｎ　Ｏｎｔｏｌｏｇｉｅｓ）可以定义为一个四　

元组：　

语义的Ｗｅｂ日志挖掘，如用户聚类　。　

Ｏ＝｛Ｃ，Ｒ，，，ＡＳ｝　

１　相关工作　

其中，Ｃ和尺分别为概念集合和角色集合。在形式本体中它们　

的定义和描述表现为公理集合，包括等价公理和包含公理。等　

Ｗｅｂ日志挖掘是Ｗｅｂ挖掘的重要内容之一，也是当前数据　价公理又叫做术语定义，包含公理用于描述概念层次或概念体　

挖掘研究的一个热点问题。Ｗｅｂ日志挖掘通常分为数据预处　

系；等价公理可以转换为包含公理。，是领域内个体的集合。　

理、模式发现和模式分析三个阶段　。现有的大量研究工作均　

Ｃ、Ｒ、，可以统称为领域术语集合　。Ａｓ是领域断言集合，是　

收稿日期：２００６　０６—０１；修返１５ｔ期：２００６—０８—０３　基金项目：国家自然科学基金资助项目（７０４７１０９０，７０４７２００５）；江苏省自然科学基金资　

助项目（ＢＫ２００５０４６）　

作者简介：潘钧（１９６６一），女，江苏江都人，实验师，主要研究方向为数据挖掘及语义Ｗｅｂ（ｊｐａｎ＠ｙｚｕ．ｅｄｕ　ｃｎ）　

维普资讯

・

２６８・　计算机应用研究　２００７生　

概念和角色到个体映射关系的集合。　

在语义Ｗｅｂ中，日志属性的解释是基于本体的。考虑到　

Ｗｅｂ的开放性、动态性和分布性，需要对分布式的本体进行集　

成、合并与映射等工作。　

定义２　本体集合及词汇表（Ｏｎｔｏｌｏｇｉｅｓ　Ｓｅｔ　ａｎｄ　Ｖｏｅａｂｕ—　

ｌａｒｙ）。Ｗｅｂ上一组本体的集合，记做：　

ＯＳ＝｛０　Ｉｉ∈，｝　

个语义对象组成，分别计算对应的单个语义对象的相似度；然　

后利用式（２）加权求和得到整个查询字符串的相似度，它也就　

代表了动态网页的语义相似度。利用这个相似度可以对动态　

网页按照一定的算法进行聚类，也可以根据不同用户的语义事　

务的相似度按照一定算法来对用户进行聚类。这样用户在查　

询相关网页时可以根据用户的查询信息对用户进行实时推荐　

语义相似度相对较高的网页，也可以对有较高语义相似度的用　

户进行类似推荐。　

ｍ　

其中，，＝｛ｉＩ　１≤ｉ≤ｎ，ｎ　Ｅ　Ｎ｝；ｎ表示本体数量，具体的　又是特　

定本体的指标。　

如果采用Ｖ（０　）表示本体０　的词汇，　（０　）、馏（０　）、　

ＶＩ（０　）分别表示本体０　的概念词汇、角色词汇和个体词汇，则　

Ｓｉｍ（Ｔｌ，　）＝　

…，　１　

ＳｅｍＳｉｍ（Ｏｌ，Ｏ２）／（ＩＴｌ　Ｉ　ＩＴｌ　Ｉ）　（２）　

下面给出利用语义相似进行网页聚类和用户聚类的两个　

有　

Ｖ（０　）＝　（Ｃ　）Ｕ　（Ｒ　）Ｕ　（，　）　

Ｖ（ｏｓ）＝｛ｕＩ＂∈Ｖ（０　），０　∈ＯＳ｝　

定义３语义Ｗｅｂ日志模型（Ｓｅｍａｎｔｉｃ　Ｗｅｂ　Ｌｏｇ　Ｍｏｄｅ１）一　

个语义Ｗｅｂ日志可以用下列三元组描述：　

ＳＷＬ（Ｐ，Ｏ，ＬＯＩ）　

其中，ＳＷＬ为语义Ｗｅｂ日志的名字；Ｐ是Ｗｅｂ日志属性集合；　

Ｏ是支持ＳＷＬ的本体；ＬＯＩ是Ｗｅｂ日志属性在本地的解释。　

一

般说来，在Ｗｅｂ的分布式环境中，本体是随着客户端访问传　

输的。　

２．２　基于本体的语义相似度计算　

在一个相应的本体概念层次树中，计算两个语义对象相似　

问题，应该主要考虑以下三个问题：　

（１）距离。这是主要的衡量标准，通常层次树中距离越远　

的语义对象其差异越大，即相似度就越小；距离越近的语义对　

象其差异越小，即相似度就越大。这是直观上容易得到的。　

（２）深度。路径长度相同的两个节点，如果位于概念层次　

的越底层，其语义距离较大。比如动物和植物、哺乳动物和爬　

行动物，这两对概念间的路径长度在一概念层次树中均是２。　

但前一对词处于语义树的较高层，因此认为其语义距离较大，　

后一对词处于语义树的较低层，其语义距离更小。　

（３）区域密度。路径长度相同的两个节点，如果位于概念　

层次树中高密度区域，其语义距离应大于位于低密度区域。本　

体中概念描述的粗细程度不均。假设某些区域概念的描述极　

其详尽，而有些区域的概念描述又较粗疏，所以加入了概念层　

次树区域密度对语义距离的影响。　

综合上面影响语义相似的主要因素，给出基于本体的语义　

相似度计算公式：　

Ｓｅｒ￣Ｓｉｍ（０ｌ，０２）＝［　Ｘ（　ｌ＋ｆ　）］／｛［Ｄｉｓ（０ｌ，０２）＋　］Ｘｍａｘ（Ｉ　ｌ—　

，

Ｉ，　）｝　（１）　

３基于ＳＷＬＭ的网页聚类与用户聚类算法　

对于一个包括一定数量的静态页面和大量的根据用户查　

询请求动态生成页面的网站来说，它的Ｌｏｇ中含有大量的语义　

信息。针对这些语义信息，用计算事务语义相似度的方法来对　

ｏＬｇ记录进行处理。为此，必须建立一个Ｗｅｂ与用户的交互模　

型，利用这个交互模型来处理语义。　

根据式（１）可以在概念层次树结构中判断两个语义对象　

的相似度。对于一个产生动态网页的查询字符串由一个或多　

算法：　

算法１　利用语义相似进行网页聚类的算法　

输入：网页集合｛Ｐｌ，Ｐ２，Ｐ３，…，Ｐ　｝，阈值０　

输出：语义相似类Ｃｌ＝｛Ｐｌ　，Ｐ２　，…，Ｐ　｝，Ｃ２＝｝Ｐｌ”，Ｐ２”　

Ｐ　｝，…，Ｃｋ＝｛Ｐｌ　，Ｐ２　，…，Ｐ。　｝　

算法描述：　

Ｐ；＝＜ｎｏｕｎ。＞＜ｖｅｒｂ。＞　

ｆｏｒ（ｉ＝１；ｉ＜＝ｎ；ｉ＋＋）　

｛ｆ０ｒ（．ｉ＝１；ｊ＜＝ｎ；ｊ＋＋）　

｛ｕｓｅ式（１）ｔｏｆｉｇｕｒｅ　ｏｕｔ　Ｓｉｍ（＜ｎｏｕｎｌ＞，＜ｎｏｕｎｌ＞）　

Ｓｉｍ（＜ｖｅｒｂ，＞，＜ｖｅｒｂ．＞）　

ｕｓｅ式（２）ｔｏ　ｆｉｕｇｒｅ　ｏｕｔ　Ｓｉｍ（Ｐ．，Ｐ．）　

ｉｆ　Ｓｉｍ（Ｐ。，Ｐ１）＞＝０，ｔｈｅｎ　ｐｕｔ　Ｐｌ　ｉｎｔｏ　Ｃ。　

｝　

算法２利用语义相似进行用户聚类的算法　

输入：语义事务集合Ｔ＝｛Ｔ。，Ｔ２，…，Ｔ　｝和阈值０　

输出：用户集合Ｕｌ＝｛Ｔｌ　，Ｔ２　，…，Ｔ　｝，Ｕ２＝｛Ｔｌ　，Ｔ２　

Ｔ　｝，…，Ｕｋ＝｛Ｔｌ　，Ｔ２　，…，Ｔ　｝　

算法描述：　

设Ｔ＝｛Ｐｌ，Ｐ２，Ｐ３，…，Ｐ。｝　

用算法１得到网页集合ｃｌ，ｃ２，…，ｃｋ　

ａ：０：　

ｆ０ｒ（ｉ＝１；ｉ＜：ｎ；ｉ＋＋）　

｛ｆｏｒ（Ｊ：１；ｊ＜＝ｎ；ｊ＋＋）　

｛ｉｆ　Ｐ　∈Ｔｉ　ａｎｄ　ＰＪ∈Ｔｊ　ａｎｄ　ＰＩ，ＰＪ∈Ｃ　ｔｈｅｎ　ａ＋＝１；｝　

ｉｆ　ａ／ｎ＞：０　，ｔｈｅｎ　ｐｕｔ　Ｔｊ　ｉｎｔｏ　Ｕ。　

ｌ　

４实验及分析　

使用ｗｗｗ．ａｎｉｍａ１．ｎｅｔ网站的Ｗｅｂ服务器的日志文件来测　

试算法和公式。为了加以对比，也使用传统的基于关键词匹配　

的方法来聚类网页和用户。选取网站日志文件２００５年１月１　

日００：００：００～１月３１日２３：５９：５９所有的访问信息。共有　

１２　３４５个不同的ＩＰ对１２３　４５６个网页进行了１　２３４　５６７次访　

问。以其中的１０２　３５４个由查询字符串生成的动态网页为测　

试源，并从中抽出了１２３　５６１次有效的会话过程。首先，用本　

体来描述整个站点的名词和动词，然后再通过把用于产生动态　

页面的查询词语集映射到相应的概念层次。根据公式计算对　

应词语的语义相似度，然后再利用算法对这些动态网页聚类，　

从而为用户提供推荐。　

ｓｅａｒｃｈ．ｐｈｐ？ｋｅｙ　ａｎｉｍａｌ＋ｃａｌｌ＋ｎｙ　

Ｃｌａｓｓｌ：ｓｅａｒｃｈ．ｐｈｐ？ｋｅｙ：ｂｉｒｄ＋ｈａｖｅ＋ｗｉｎｇ　

ｅｓａｒｃｈ．ｐｈｐ？ｋｅｙ＝ｂｉｒｄ　

ｓｅａｒｃｈ．ｐｈｐ？ｋｅｙ：ｅａｇｌｅ・・・　

ｓｅａｒｃｈ．ｐｈｐ？ｋｅｙ：ｗｉｌｄ＋ａｎｉｍａｌｓ　

Ｃｌａｓｓ２：ｓｅａｒｃｈ．ｐｈｐ？ｋｅｙ＝ｓｗａｎ　

ｓｅａｒｃｈ．ｐｈｐ？ｋｅｙ　ｃｒａｎｅ…　

Ｃｌａｓｓ３：ｓｅａｒｃｈ．ｐｈｐ？ｋｅｙ：ａｎｉｍａｌｓ＋ｓａｌｖａｔｉｏｎ　

ｓｅａｒｃｈ．ｐｈｐ？ｋｅｙ　ａｎｉｍａｌｓ　ｐｒｏｔｅｃｔ　

维普资讯

第７期　潘钧：面向Ｗｅｂ日志的语义聚类算法　・２６９・　

分别用本文中的算法和基于关键词匹配的算法进行用户　

键词匹配的不足。随着语义网的兴起，语义知识越来越多地受　

和网页聚类测试，并对聚类结果进行比较。图１给出了使用本　到人们的关注和利用。该算法只是阐述了一个可利用的方向，　

文算法和使用关键词匹配算法结果的比较。其中，　轴表示类　算法的效率问题、静态网页的语义表示问题等都是下一步的研　

的数量，Ｙ轴表示每一类的数量。从结果中可以清楚地看出，　究重点。　

使用基于关键词匹配的算法聚类，几乎大部分的用户都独自成　

参考文献：　

为一个类。这样显然忽视了用户之间的相似性和共性。表１　

［１］ＨＡＮ　Ｊ，ＫＡＭＢＥＲ　Ｍ．数据挖掘：概念与技术［Ｍ］．范明，盂小峰，　

给出的是使用本文算法聚类的部分结果。从表１可以明显看　

等译．北京：机械工业出版社，２００１：４４ｌ－４４３．　

出，如果使用基于关键词匹配的方法聚类，那么很多具有相似　

［２］王继成，潘金责，张福炎．Ｗｅｂ文本挖掘技术研究［Ｊ］．计算机研　

内容的网页均要被划分在不同的类中。而使用本文算法把页　

究与发展，１９９８，３７（５）：５１３・５加．　

面合理地分成相应数目的类，每个类的页面之间的确存在着相　

［３］王实．高文，李锦涛，Ｗｅｂ数据挖掘［Ｊ］．计算机科学，２０００，２１　

似的内容，可以一并推荐给用户。　

（４）：２８－３１．　

４０　

［４］ＣＨＥＮ　Ｈｓｉｎｃｈｕｎ，ＣＨＵＮＧ　Ｗｉｎｇｙａｎ，ＪＥＮＮＩＦＥＲ　Ｊ，ｅｔ　ａ１．Ｃｒｉｍｅ　ｄａｔａ　

３０　

ｍｉｎｉｎｇ：ａ　ｇｅｎｅｒａｌ　ｆｒａｍｅｗｏｒｋ　ａｎｄ　ｓｏｍｅ　ｅｘａｍｐｌｅｓ［Ｊ］．ＩＥＥＥ　Ｃｏｍｐｕｔ－　

ｅｒ，２００４，３７（４）：５０－５６．　

２０　

１０　

＿－　

［５］ＨＡＵＣＫ　Ｒ　Ｖ，ＣＨＥＮ　Ｈ．Ｃｏｐｌｉｎｋ：ａ　ｃａｓｅ　ｏｆ　ｉｎｔｅｌｌｉｇｅｎｔ　ａｎａｌｙｓｉｓ　ａｎｄ　

－＿

－＿＿　

Ｏ　

－　

ｋｎｏｗｌｅｄｇｅ　ｍａｎａｇｅｍｅｎｔ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　

Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍｓ．Ｎｏａｈ　Ｃａｒｏｌｉｎａ，ＵＳＡ：［ｓ．ｎ．］，１９９９：１５－２８．　

图１　用户语法聚类和语义聚类结果比较图　

［６］　ＡＧＲＡＷＡＬ　Ｒ，ＧＥＨＲＫＥ　Ｊ，ＧＵＮＯＰＵＬＯＳ　Ｄ．Ａｕｔｏｍａｔｉｃ　ｓｕｂ　ｓｐａｃｅ　

表１　页面聚类结果统计表　

ｃｌｕｓｔｅｒｉｎｇ　ｏｆｈｉｇｈ　ｄｉｍｅｎｓｉｏｎａｌ　ｄａｔａ　ｆｏｒ　ｄａｔａ　ｍｉｎｉｎｇ　ａｐｐｌｉｃａｔｉｏｎｓ［Ｃ］／／　

Ｐｒｏｃ　ｏｆ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ．Ｎｅｗ　Ｙｏｒｋ：　

ＡＣＭ　Ｐｒｅｓｓ，１９９８：９５－１０５．　

［７］ＣＡＮＮＡＴＡＲＯ　Ｍ，ＣＯＭＩＴＯ　Ｃ、Ａ　ｄａｔａ　ｍｉｎｉｎｇ　ｏｎｔｏｌｏｇｙ　ｆｏｒ　ｇｒｉｄ　ｐｒｏ—　

ｇｒａｍｍｉｎｇ［Ｃ］／／Ｔｈｅ　ｉ　ｓｔ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｗｏｒｋｓｈｏｐ　ｏｉ１　Ｓｅｍａｎｔｉｃｓ　ｉｎ　Ｐｅｅｒ－　

ｔｏ－Ｐｅｅｒ　ａｎｄ　Ｇｒｉｄ　Ｃｏｍｐｕｔｉｎｇ［Ｃ］．Ｂｕｄａｐｅｓｔ，Ｈｕｎｇａｒｙ：［ｓ．ｎ．］，２００３：　

５结束语　

１１３．１３４＂

．　

［８］ＭＥＨＴＡ　Ｍ，ＡＧＡＷＡＬ　Ｒ，ＲＩＳＳＡＮＥＮ　Ｊ．ＳＬＩＱ：ａ　ｆａｓｔ　ｓｃａｌａｂｌｅ　ｃｌａｓｓｉ—　

对于大部分由用户的查询生成动态网页的网站来说，采用　

ｉｔｅｒ　ｏｆｒ　ｄａｔａ　ｍｉｎｉｎｇ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　５ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　

本文的公式和算法来聚类网页及用户，向用户推荐相关的感兴　

Ｅｘｔｅｎｄｉｎｇ　Ｄａｔｂａａｓｅ　Ｔｅｃｈｎｏｌｏｇｙ（ＥＤＢＴ）．Ａｖｉｇｎｏｎ，Ｆｒｎａｃｅ：［ｓ．ｎ．］，　

趣的网页是合理有效的。该算法和公式克服了传统的只是关　

ｌ９９６：１８．３２．　

（上接第２６６页）太网的大规模分布式网络化控制随着计算机、　

ｐａｒｔ　Ｉ：ａｎａｌｙｓｉｓ［Ｊ］．ＡＳＭＥ　Ｊｏｕｒｎａｌ　ｏｆ　Ｄｙｎａｍｉｃ　Ｓｙｓｔｅｍｓ，Ｍｅａｓｕ－　

通信、控制技术的飞速发展而成为工业自动化领域不可逆转的　

ｒｅｍｅｎｔ　ａｎｄ　Ｃｏｎｔｒｏｌ，１９８８，１１０（４）：３６７－３７３．　

发展趋势。然而当工业以太网以总线型拓扑结构实现时，通常　

［３］ＪＯＡＣＨＩＭ　Ｆ．ＰＲＯＦＩＮＥＴ－Ｓｃａｌｂａｌｅ　ｆａｃｔｏｒｙ　ｃｏｍｍｕｎｉｃａｔｉｏｎ　ｆｏｒ　ａｌｌ印－　

会出现大量交换机级联的情况，从而降低了网络化控制系统的　

ｐｌｉｃａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ＩＥＥＥ　Ｉｎｔｅｎｒａｔｉｏｎａｌ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｆａｃｔｏｙｒ　Ｃｏｒｎ－　

性能和稳定性。本文研究了一类采用全双工以太网连接，通过　

ｍｕｎｉｃａｔｉｏｎ　Ｓｙｓｔｅｍ．［ｓ．１．］：［ｓ．ｎ．］，２００４．　

级联交换机构成类似工业控制领域中常见的总线型拓扑结构　

［４］ＭＩＬＬＳ　Ｄ　Ｌ．Ｅｘｅｃｕｔｉｖｅ　ｓｕｍｍａｒｙ－ｃｏｍｐｕｔｅｒ　ｎｅｔｗｏｒｋ　ｔｉｍｅ　ｓｙｎｃｈｒｏｎｉｚａ—　

的网络化控制系统。首先分析了系统的结构特征，并通过实验　

ｔｉｏｎ［ＥＢ／ＯＬ］．［２００３］．ｈｔｔｐ：／／ｗｗｗ．ｅｅｃｉｓ．ｕｄｅ１．ｅｄｕ／～ｍｉｌｌｓ／ｅｘ－　

ｅｃ．ｈｔｍｌ＃ｉｎｔｏｒ．　

详细分析了其网络时延特性；之后讨论了此类控制结构在基于　

［５］徐皑冬，王宏，邢志浩．工业以太网实时通信技术［Ｊ］．信息与控　

时间的系统分析和设计过程中的时钟误差成因；最后结合精确　

制，２００５，３４（１）：６０－６５．　

时钟同步协议，给出了一种基于边界时钟和旁路时钟的时钟同　

［６］　ＡＮＳ￣ＩＥＥＥ　Ｓｔｄ．１５８８－２００２．ＩＥＥＥ　ｓｔａｎｄａｒｄ　ｆｏｒ　ａ　ｐｒｅｃｉｓｉｏｎ　ｃｌｏｃｋ　

步实现模式，用于此类网络化控制系统的时钟同步方法的实　

ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ　ｐｒｏｔｏｃｏｌ　ｆｏｒ　ｎｅｔｗｏｒｋｅｄ　ｍｅａｓｕｒｅｍｅｎｔ　ａｎｄ　ｃｏｎｔｒｏｌ　ｓｙｓ－　

施。关于网络化控制系统的时钟同步还有许多研究内容。例　

ｔｅｍｓ［Ｓ］．［Ｓ．１．］：［ｓ．ｎ．］，２００２．　

如本文是在假设传输链路双向对称的情况下讨论时钟同步问　

［７］ＷＥＩＢＥＬ　Ｈ．Ｈｉｇｈ　ｐｒｅｃｉｓｉｏｎ　ｃｌｏｃｋ　ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ＩＥＥＥ　

题，而实际应用中，尤其是网络负载很大时，这种情况几乎很难　

１５８８　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ａｎｄ　ｐｅｒｆｏｒｍａｎｃｅ　ｉｓｓｕｅｓ［Ｃ］／／Ｔｈｅ　Ｅｍｂｅｄｄｅｄ　

实现。此外大规模分布式混杂网络化控制系统（如工业现场　

Ｗｏｒｌｄ　２００５　Ｃｏｎｆｅｒｅｎｃｅ［Ｃ］．［ｓ．１．］：［ｓ．ｎ．］，２００５．　

中同时存在现场总线、工业以太网构成的异构网络化控制系　

［８］ＣＲＩＳＴＩＡＮ　Ｆ．Ａ　ｐｒｏｂａｂｉｌｉｓｔｉｃ　ａｐｐｒｏａｃｈ　ｔｏ　ｄｉｓｔｉｒｂｕｔｅｄ　ｃｌｃｏｋ　ｓｙｎｃｈｒｏｎｉ－　

统）的分布式时钟同步问题还存在许多理论和实践工作，有待　

ｚａｔｉｏｎ［Ｊ］．Ｄｉｓｔｒｉｂｕｔｅｄ　Ｃｏｍｐｕｔｉｎｇ，１９９８，３：１４６—１５８．　

进一步研究。　

［９］ＡＲＶＩＮＤ　Ｋ．Ｐｒｏｂａｂｉｌｉｓｔｉｃ　ｃｌｃｏｋ　ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ　ｉｎ　ｄｉｓｔｉｒｂｕｔｅｄ　ｓｙｓｔｅｍ　

［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｐａｒａｌｌｅｌ　ａｎｄ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｓｙｓｔｅｍｓ，　

参考文献：　

ｌ９９４，５（５）：４７４—４８７．　

［１］ＷＡＬＳＨ　Ｇ　Ｃ，ＹＥ　Ｈ，ＢＵＳＨＥＬＬ　Ｌ　Ｇ．Ｓｔｂａｉｌｉｔｙ　ａｎａｌｙｓｉｓ　ｏｆ　ｎｅｔｗｏｒｋｅｄ　

［１０］ＪＡＳＰＥＲＮＥＩＴＥ　Ｊ，ＳＨＥＨＡＢ　Ｋ，ＷＥＢＥＲ　Ｋ．Ｅｎｈａｎｃｅｍｅｎｔｓ　ｔｏ　ｔｈｅ　ｔｉｍｅ　

ｃｏｎｔｒｏｌ　ｓｙｓｔｅｍｓ［Ｃ］／／Ｐｒｏｃ　ｏｆ　Ａｍｅｒｉｃａｎ　Ｃｏｎｔｒｏｌ　Ｃｏｎｆｅｒｅｎｃｅ．［Ｓ．１．］：　

ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ　ｓｍｎｄ￣ｄ　ＩＥＥＥ　１５８８　ｆｏｒ　ａ　ｓｙｓｔｅｍ　ｏｆ　ｃａｓｃａｄｅｄ　ｂｒｉｄｇｅｓ　

［ｓ．ｉ１．］，１９９９：２８７６—２８８０．　

［Ｃ］／／Ｔｈｅ　５ｔｈ　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｆａｃｔｏｒｙ　Ｃｏｍｍｕｎｉｃａ－　

［２］ＨＡＬＥＶＩ　Ｙ，ＲＡＹ　Ａ．Ｉｎｔｅｇｒａｔｅｄ　ｃｏｍｍｕｎｉｃａｔｉｏｎ　ａｎｄ　ｃｏｎｔｒｏｌ　ｓｙｓｔｅｍｓ：　

ｔｉｏｎ　Ｓｙｓｔｅｍｓ－【ｓ．１．］：［ｓ．ｎ．］，２００４．　

2024年5月6日发(作者：勇绚)

维普资讯

第２４卷第７期　

计算机应用研究　

Ｖ０１．２４　Ｎ０．７　

２００７年７月　

Ａｐｐｌｉｃａｔｉｏｎ　Ｒｅｓｅａｒｃｈ　ｏｆ　Ｃｏｍｐｕｔｅｒｓ　

Ｊｕｌｙ　２００７　

面向Ｗｅｂ日志的语义聚类算法术　

潘钧　

（扬州大学信息工程学院，江苏扬州２２５００９）　

摘要：由于现有的Ｗｅｂ日志缺少明显语义，提出一种语义Ｗｅｂ日志模型——ｓｗＬＭ，并给出基于该模型的网　

页和用户聚类算法。通过日志概念的语义距离定量计算来聚类网页和用户，奠定了Ｗｅｂ个性化服务的基础。　

性能测试实验证明，该模型具有较好的整体性能，能有效地进行网页和用户聚类。　

关键词：Ｗｅｂ日志；挖掘；语义；本体　

中图分类号：ＴＰ３１１　文献标志码：Ａ　文章编号：１００１—３６９５（２００７）０７—０２６７—０３　

Ｓｅｍａｎｔｉｃ　Ｃｌｕｓｔｅｒｉｎｇ　Ａｌｇｏｒｉｔｈｍ　Ｏｒｉｅｎｔｅｄ　ｔｏ　Ｗｅｂ　Ｌｏｇ　

ＰＡＮ　Ｊｕｎ　

（Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｙａｎｇｚｈｏｕ　Ｕｎｉｖｅｒｓｉｔｙ，Ｙａｎｇｚｈｏｕ　¨２２５００９，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｅｘｉｓｔｅｄ　Ｗｅｂ　ｌｏｇｓ　ｗｅｒｅ　ｌａｃｋ　ｏｆ　ｓｅｍａｎｔｉｃｓ　ｏｂｖｉｏｕｓｌｙ．Ｔｏ　ｉｍｐｒｏｖｅｄ　ｔｈｅ　ｅｆｆｉｃｉｅｎｃｙ　ａｎｄ　ａｃｃｕｒａｃｙ　ｏｆ　Ｗｅｂ　ｍｉｎｉｎｇ，ａ　ｓｅ—　

ｍａｎｔｉｃ　Ｗｅｂ　ｌｏｇ　ｍｏｄｅｌ　ＳＷＬＭ　ｗａｓ　ｐｒｅｓｅｎｔｅｄ，ａｎｄ　ｔｗｏ　ａｌｇｏｒｉｔｈｍｓ　ｂａｓｅｄ　ｏｎ　ｔｈｉｓ　ｍｏｄｅｌ　ｗａｓ　ｇｉｖｅｎ　ｔｏ　ｃｌｕｓｔｅｒ　ｐａｇｅｓ　ａｎｄ　ｕｓｅｒｓ．　

Ｔｈｅｎ，ｔｈｅ　ｓｅｍａｎｔｉｃ　ｉｎｆｏｒｍａｔｉｏｎ　ｃｏｕｌｄ　ｂｅ　ｍｉｎｉｎｇ　ｆｒｏｍ　ｔｈｅ　Ｗｅｂ　ｌｏｇ，ａｎｄ　ｔｈｅ　ｓｅｍａｎｔｉｃ　ｄｉｓｔａｎｃｅｓ　ｏｆ　ｌｏｇ　ｃｏｎｃｅｐｔｓ　ｃｏｕｌｄ　ｂｅ　ｃｏｍｐｕ—　

ｔｅｄ．Ｔｈｅ　ｔｅｓｔ　ｅｘｐｅｒｉｍｅｎｔ　ｓｈｏｗｓ　ｔｈａｔ　ｔｈｉｓ　ｍｏｄｅｌ　ｈａｓ　ｂｅｔｔｅｒ　ｐｅｒｆｏｒｍａｎｃｅ　ａｎｄ　ｃｌｕｓｔｅｒｓ　ｐａｇｅｓ　ａｎｄ　ｕｓｅｒｓ　ｅｆｆｅｃｔｉｖｅｌｙ．Ｔｈｏｓｅ　ｒｅｓｕｌｔｓ　

ｃａｎ　ｆａｃｉｌｉｔａｔｅ　ｐｅｒｓｏｎａｌｉｚｅｄ　ｓｅｒｖｉｃｅｓ　ａｎｄ　ｕｓｅｒ　ｍｏｄｅｌｉｎｇ．　

Ｋｅｙ　ｗｏｒｄｓ：Ｗｅｂ　ｌｏｇ；ｍｉｎｉｎｇ；ｓｅｍａｎｔｉｃ；ｏｎｔｏｌｏｇｙ　

ｗｅｂ日志挖掘属于Ｗｅｂ使用挖掘。它通过挖掘相关的　基于这三个方面。在数据预处理阶段，文献［５］提出了挖掘异　

Ｗｅｂ日志记录，来发现用户访问Ｗｅｂ页面的模式，通过分析日　常数据的方法和途径。文献［６］提出了基于最大前向引用的事　

志记录中的规律，识别用户的忠实度、喜好、满意度，发现潜在　

务辨识。在模式发现阶段，文献［７］把服务器日志载人数据立　

用户，增强站点的服务竞争力。但是，现有的Ｗｅｂ日志挖掘是　

方体结构，执行ＯＬＡＰ。文献［８］使用Ｍａｒｋｏｖ模型生成序列模　

基于语法的数据挖掘，舍弃了数据之间丰富的语义关联信　

式，用于Ｗｅｂ预取和系统优化；在模式分析阶段，如ＷｅｂＷａｔｃｈｅｒ　

息　０　。为了使Ｗｅｂ上的信息具有计算机可理解的形式语义，　

跟踪用户的浏览行为，辨识出用户可能感兴趣的链接并推荐给　

满足智能软件代理（Ａｇｅｎｔ）对ｗｗｗ上异构和分布信息的有　

用户。对每个用户，ＷｅｂＷａｔｃｈｅｒ先对其兴趣进行简单的描述，　

效访问及检索　，在ＸＭＬ２０００的会议上，Ｂｅｒｎｅｒｓ—Ｌｅｅ提出语义　

然后基于该用户的浏览行为和具有相似兴趣的其他用户的浏览　

Ｗｅｂ及其层次关系——基于ＸＭＬ和ＲＤＦ／ＲＤＦＳ，并在此之上　

行为学习该用户的兴趣。但是现阶段的研究大多都是基于语法　

构建本体（Ｏｎｔｏｌｏｇｙ）和逻辑推理规则，以完成基于语义的知识　

的日志挖掘，随着语义Ｗｅｂ的逐渐升温　，把语义知识和领域　

表示和推理，从而能够被计算机所理解和处理。本体提供了语　

本体集成到Ｗｅｂ日志挖掘中去已经成为可能。　

义Ｗｅｂ上一切对象和行为描述的词汇集合，同时又是Ｗｅｂ上　

数据的解释模板。　

２　语义Ｗｅｂ日志模型——ＳＷＬＭ　

基于本体的语义Ｗｅｂ日志首先定义一个描述概念集，即　

２．１　语义日志模型　

建立符合学科领域要求、用开放语言描述的概念集体系（Ｏｎ—　

基于本体的领域建模的中心任务是建立可共享的领域词　

ｔｏｌｏｙｇ　Ｓｙｓｔｅｍｓ），利用概念集体系对Ｗｅｂ日志的内容进行语义　

标注或语义挖掘，形成基于语义的日志元数据。在此基础上，　

汇集。　

利用概念集中语义定义、语义关系定义和推理规则，实现基于　

定义１　领域本体（Ｄｏｍａｉｎ　Ｏｎｔｏｌｏｇｉｅｓ）可以定义为一个四　

元组：　

语义的Ｗｅｂ日志挖掘，如用户聚类　。　

Ｏ＝｛Ｃ，Ｒ，，，ＡＳ｝　

１　相关工作　

其中，Ｃ和尺分别为概念集合和角色集合。在形式本体中它们　

的定义和描述表现为公理集合，包括等价公理和包含公理。等　

Ｗｅｂ日志挖掘是Ｗｅｂ挖掘的重要内容之一，也是当前数据　价公理又叫做术语定义，包含公理用于描述概念层次或概念体　

挖掘研究的一个热点问题。Ｗｅｂ日志挖掘通常分为数据预处　

系；等价公理可以转换为包含公理。，是领域内个体的集合。　

理、模式发现和模式分析三个阶段　。现有的大量研究工作均　

Ｃ、Ｒ、，可以统称为领域术语集合　。Ａｓ是领域断言集合，是　

收稿日期：２００６　０６—０１；修返１５ｔ期：２００６—０８—０３　基金项目：国家自然科学基金资助项目（７０４７１０９０，７０４７２００５）；江苏省自然科学基金资　

助项目（ＢＫ２００５０４６）　

作者简介：潘钧（１９６６一），女，江苏江都人，实验师，主要研究方向为数据挖掘及语义Ｗｅｂ（ｊｐａｎ＠ｙｚｕ．ｅｄｕ　ｃｎ）　

维普资讯

・

２６８・　计算机应用研究　２００７生　

概念和角色到个体映射关系的集合。　

在语义Ｗｅｂ中，日志属性的解释是基于本体的。考虑到　

Ｗｅｂ的开放性、动态性和分布性，需要对分布式的本体进行集　

成、合并与映射等工作。　

定义２　本体集合及词汇表（Ｏｎｔｏｌｏｇｉｅｓ　Ｓｅｔ　ａｎｄ　Ｖｏｅａｂｕ—　

ｌａｒｙ）。Ｗｅｂ上一组本体的集合，记做：　

ＯＳ＝｛０　Ｉｉ∈，｝　

个语义对象组成，分别计算对应的单个语义对象的相似度；然　

后利用式（２）加权求和得到整个查询字符串的相似度，它也就　

代表了动态网页的语义相似度。利用这个相似度可以对动态　

网页按照一定的算法进行聚类，也可以根据不同用户的语义事　

务的相似度按照一定算法来对用户进行聚类。这样用户在查　

询相关网页时可以根据用户的查询信息对用户进行实时推荐　

语义相似度相对较高的网页，也可以对有较高语义相似度的用　

户进行类似推荐。　

ｍ　

其中，，＝｛ｉＩ　１≤ｉ≤ｎ，ｎ　Ｅ　Ｎ｝；ｎ表示本体数量，具体的　又是特　

定本体的指标。　

如果采用Ｖ（０　）表示本体０　的词汇，　（０　）、馏（０　）、　

ＶＩ（０　）分别表示本体０　的概念词汇、角色词汇和个体词汇，则　

Ｓｉｍ（Ｔｌ，　）＝　

…，　１　

ＳｅｍＳｉｍ（Ｏｌ，Ｏ２）／（ＩＴｌ　Ｉ　ＩＴｌ　Ｉ）　（２）　

下面给出利用语义相似进行网页聚类和用户聚类的两个　

有　

Ｖ（０　）＝　（Ｃ　）Ｕ　（Ｒ　）Ｕ　（，　）　

Ｖ（ｏｓ）＝｛ｕＩ＂∈Ｖ（０　），０　∈ＯＳ｝　

定义３语义Ｗｅｂ日志模型（Ｓｅｍａｎｔｉｃ　Ｗｅｂ　Ｌｏｇ　Ｍｏｄｅ１）一　

个语义Ｗｅｂ日志可以用下列三元组描述：　

ＳＷＬ（Ｐ，Ｏ，ＬＯＩ）　

其中，ＳＷＬ为语义Ｗｅｂ日志的名字；Ｐ是Ｗｅｂ日志属性集合；　

Ｏ是支持ＳＷＬ的本体；ＬＯＩ是Ｗｅｂ日志属性在本地的解释。　

一

般说来，在Ｗｅｂ的分布式环境中，本体是随着客户端访问传　

输的。　

２．２　基于本体的语义相似度计算　

在一个相应的本体概念层次树中，计算两个语义对象相似　

问题，应该主要考虑以下三个问题：　

（１）距离。这是主要的衡量标准，通常层次树中距离越远　

的语义对象其差异越大，即相似度就越小；距离越近的语义对　

象其差异越小，即相似度就越大。这是直观上容易得到的。　

（２）深度。路径长度相同的两个节点，如果位于概念层次　

的越底层，其语义距离较大。比如动物和植物、哺乳动物和爬　

行动物，这两对概念间的路径长度在一概念层次树中均是２。　

但前一对词处于语义树的较高层，因此认为其语义距离较大，　

后一对词处于语义树的较低层，其语义距离更小。　

（３）区域密度。路径长度相同的两个节点，如果位于概念　

层次树中高密度区域，其语义距离应大于位于低密度区域。本　

体中概念描述的粗细程度不均。假设某些区域概念的描述极　

其详尽，而有些区域的概念描述又较粗疏，所以加入了概念层　

次树区域密度对语义距离的影响。　

综合上面影响语义相似的主要因素，给出基于本体的语义　

相似度计算公式：　

Ｓｅｒ￣Ｓｉｍ（０ｌ，０２）＝［　Ｘ（　ｌ＋ｆ　）］／｛［Ｄｉｓ（０ｌ，０２）＋　］Ｘｍａｘ（Ｉ　ｌ—　

，

Ｉ，　）｝　（１）　

３基于ＳＷＬＭ的网页聚类与用户聚类算法　

对于一个包括一定数量的静态页面和大量的根据用户查　

询请求动态生成页面的网站来说，它的Ｌｏｇ中含有大量的语义　

信息。针对这些语义信息，用计算事务语义相似度的方法来对　

ｏＬｇ记录进行处理。为此，必须建立一个Ｗｅｂ与用户的交互模　

型，利用这个交互模型来处理语义。　

根据式（１）可以在概念层次树结构中判断两个语义对象　

的相似度。对于一个产生动态网页的查询字符串由一个或多　

算法：　

算法１　利用语义相似进行网页聚类的算法　

输入：网页集合｛Ｐｌ，Ｐ２，Ｐ３，…，Ｐ　｝，阈值０　

输出：语义相似类Ｃｌ＝｛Ｐｌ　，Ｐ２　，…，Ｐ　｝，Ｃ２＝｝Ｐｌ”，Ｐ２”　

Ｐ　｝，…，Ｃｋ＝｛Ｐｌ　，Ｐ２　，…，Ｐ。　｝　

算法描述：　

Ｐ；＝＜ｎｏｕｎ。＞＜ｖｅｒｂ。＞　

ｆｏｒ（ｉ＝１；ｉ＜＝ｎ；ｉ＋＋）　

｛ｆ０ｒ（．ｉ＝１；ｊ＜＝ｎ；ｊ＋＋）　

｛ｕｓｅ式（１）ｔｏｆｉｇｕｒｅ　ｏｕｔ　Ｓｉｍ（＜ｎｏｕｎｌ＞，＜ｎｏｕｎｌ＞）　

Ｓｉｍ（＜ｖｅｒｂ，＞，＜ｖｅｒｂ．＞）　

ｕｓｅ式（２）ｔｏ　ｆｉｕｇｒｅ　ｏｕｔ　Ｓｉｍ（Ｐ．，Ｐ．）　

ｉｆ　Ｓｉｍ（Ｐ。，Ｐ１）＞＝０，ｔｈｅｎ　ｐｕｔ　Ｐｌ　ｉｎｔｏ　Ｃ。　

｝　

算法２利用语义相似进行用户聚类的算法　

输入：语义事务集合Ｔ＝｛Ｔ。，Ｔ２，…，Ｔ　｝和阈值０　

输出：用户集合Ｕｌ＝｛Ｔｌ　，Ｔ２　，…，Ｔ　｝，Ｕ２＝｛Ｔｌ　，Ｔ２　

Ｔ　｝，…，Ｕｋ＝｛Ｔｌ　，Ｔ２　，…，Ｔ　｝　

算法描述：　

设Ｔ＝｛Ｐｌ，Ｐ２，Ｐ３，…，Ｐ。｝　

用算法１得到网页集合ｃｌ，ｃ２，…，ｃｋ　

ａ：０：　

ｆ０ｒ（ｉ＝１；ｉ＜：ｎ；ｉ＋＋）　

｛ｆｏｒ（Ｊ：１；ｊ＜＝ｎ；ｊ＋＋）　

｛ｉｆ　Ｐ　∈Ｔｉ　ａｎｄ　ＰＪ∈Ｔｊ　ａｎｄ　ＰＩ，ＰＪ∈Ｃ　ｔｈｅｎ　ａ＋＝１；｝　

ｉｆ　ａ／ｎ＞：０　，ｔｈｅｎ　ｐｕｔ　Ｔｊ　ｉｎｔｏ　Ｕ。　

ｌ　

４实验及分析　

使用ｗｗｗ．ａｎｉｍａ１．ｎｅｔ网站的Ｗｅｂ服务器的日志文件来测　

试算法和公式。为了加以对比，也使用传统的基于关键词匹配　

的方法来聚类网页和用户。选取网站日志文件２００５年１月１　

日００：００：００～１月３１日２３：５９：５９所有的访问信息。共有　

１２　３４５个不同的ＩＰ对１２３　４５６个网页进行了１　２３４　５６７次访　

问。以其中的１０２　３５４个由查询字符串生成的动态网页为测　

试源，并从中抽出了１２３　５６１次有效的会话过程。首先，用本　

体来描述整个站点的名词和动词，然后再通过把用于产生动态　

页面的查询词语集映射到相应的概念层次。根据公式计算对　

应词语的语义相似度，然后再利用算法对这些动态网页聚类，　

从而为用户提供推荐。　

ｓｅａｒｃｈ．ｐｈｐ？ｋｅｙ　ａｎｉｍａｌ＋ｃａｌｌ＋ｎｙ　

Ｃｌａｓｓｌ：ｓｅａｒｃｈ．ｐｈｐ？ｋｅｙ：ｂｉｒｄ＋ｈａｖｅ＋ｗｉｎｇ　

ｅｓａｒｃｈ．ｐｈｐ？ｋｅｙ＝ｂｉｒｄ　

ｓｅａｒｃｈ．ｐｈｐ？ｋｅｙ：ｅａｇｌｅ・・・　

ｓｅａｒｃｈ．ｐｈｐ？ｋｅｙ：ｗｉｌｄ＋ａｎｉｍａｌｓ　

Ｃｌａｓｓ２：ｓｅａｒｃｈ．ｐｈｐ？ｋｅｙ＝ｓｗａｎ　

ｓｅａｒｃｈ．ｐｈｐ？ｋｅｙ　ｃｒａｎｅ…　

Ｃｌａｓｓ３：ｓｅａｒｃｈ．ｐｈｐ？ｋｅｙ：ａｎｉｍａｌｓ＋ｓａｌｖａｔｉｏｎ　

ｓｅａｒｃｈ．ｐｈｐ？ｋｅｙ　ａｎｉｍａｌｓ　ｐｒｏｔｅｃｔ　

维普资讯

第７期　潘钧：面向Ｗｅｂ日志的语义聚类算法　・２６９・　

分别用本文中的算法和基于关键词匹配的算法进行用户　

键词匹配的不足。随着语义网的兴起，语义知识越来越多地受　

和网页聚类测试，并对聚类结果进行比较。图１给出了使用本　到人们的关注和利用。该算法只是阐述了一个可利用的方向，　

文算法和使用关键词匹配算法结果的比较。其中，　轴表示类　算法的效率问题、静态网页的语义表示问题等都是下一步的研　

的数量，Ｙ轴表示每一类的数量。从结果中可以清楚地看出，　究重点。　

使用基于关键词匹配的算法聚类，几乎大部分的用户都独自成　

参考文献：　

为一个类。这样显然忽视了用户之间的相似性和共性。表１　

［１］ＨＡＮ　Ｊ，ＫＡＭＢＥＲ　Ｍ．数据挖掘：概念与技术［Ｍ］．范明，盂小峰，　

给出的是使用本文算法聚类的部分结果。从表１可以明显看　

等译．北京：机械工业出版社，２００１：４４ｌ－４４３．　

出，如果使用基于关键词匹配的方法聚类，那么很多具有相似　

［２］王继成，潘金责，张福炎．Ｗｅｂ文本挖掘技术研究［Ｊ］．计算机研　

内容的网页均要被划分在不同的类中。而使用本文算法把页　

究与发展，１９９８，３７（５）：５１３・５加．　

面合理地分成相应数目的类，每个类的页面之间的确存在着相　

［３］王实．高文，李锦涛，Ｗｅｂ数据挖掘［Ｊ］．计算机科学，２０００，２１　

似的内容，可以一并推荐给用户。　

（４）：２８－３１．　

４０　

［４］ＣＨＥＮ　Ｈｓｉｎｃｈｕｎ，ＣＨＵＮＧ　Ｗｉｎｇｙａｎ，ＪＥＮＮＩＦＥＲ　Ｊ，ｅｔ　ａ１．Ｃｒｉｍｅ　ｄａｔａ　

３０　

ｍｉｎｉｎｇ：ａ　ｇｅｎｅｒａｌ　ｆｒａｍｅｗｏｒｋ　ａｎｄ　ｓｏｍｅ　ｅｘａｍｐｌｅｓ［Ｊ］．ＩＥＥＥ　Ｃｏｍｐｕｔ－　

ｅｒ，２００４，３７（４）：５０－５６．　

２０　

１０　

＿－　

［５］ＨＡＵＣＫ　Ｒ　Ｖ，ＣＨＥＮ　Ｈ．Ｃｏｐｌｉｎｋ：ａ　ｃａｓｅ　ｏｆ　ｉｎｔｅｌｌｉｇｅｎｔ　ａｎａｌｙｓｉｓ　ａｎｄ　

－＿

－＿＿　

Ｏ　

－　

ｋｎｏｗｌｅｄｇｅ　ｍａｎａｇｅｍｅｎｔ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　

Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍｓ．Ｎｏａｈ　Ｃａｒｏｌｉｎａ，ＵＳＡ：［ｓ．ｎ．］，１９９９：１５－２８．　

图１　用户语法聚类和语义聚类结果比较图　

［６］　ＡＧＲＡＷＡＬ　Ｒ，ＧＥＨＲＫＥ　Ｊ，ＧＵＮＯＰＵＬＯＳ　Ｄ．Ａｕｔｏｍａｔｉｃ　ｓｕｂ　ｓｐａｃｅ　

表１　页面聚类结果统计表　

ｃｌｕｓｔｅｒｉｎｇ　ｏｆｈｉｇｈ　ｄｉｍｅｎｓｉｏｎａｌ　ｄａｔａ　ｆｏｒ　ｄａｔａ　ｍｉｎｉｎｇ　ａｐｐｌｉｃａｔｉｏｎｓ［Ｃ］／／　

Ｐｒｏｃ　ｏｆ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ．Ｎｅｗ　Ｙｏｒｋ：　

ＡＣＭ　Ｐｒｅｓｓ，１９９８：９５－１０５．　

［７］ＣＡＮＮＡＴＡＲＯ　Ｍ，ＣＯＭＩＴＯ　Ｃ、Ａ　ｄａｔａ　ｍｉｎｉｎｇ　ｏｎｔｏｌｏｇｙ　ｆｏｒ　ｇｒｉｄ　ｐｒｏ—　

ｇｒａｍｍｉｎｇ［Ｃ］／／Ｔｈｅ　ｉ　ｓｔ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｗｏｒｋｓｈｏｐ　ｏｉ１　Ｓｅｍａｎｔｉｃｓ　ｉｎ　Ｐｅｅｒ－　

ｔｏ－Ｐｅｅｒ　ａｎｄ　Ｇｒｉｄ　Ｃｏｍｐｕｔｉｎｇ［Ｃ］．Ｂｕｄａｐｅｓｔ，Ｈｕｎｇａｒｙ：［ｓ．ｎ．］，２００３：　

５结束语　

１１３．１３４＂

．　

［８］ＭＥＨＴＡ　Ｍ，ＡＧＡＷＡＬ　Ｒ，ＲＩＳＳＡＮＥＮ　Ｊ．ＳＬＩＱ：ａ　ｆａｓｔ　ｓｃａｌａｂｌｅ　ｃｌａｓｓｉ—　

对于大部分由用户的查询生成动态网页的网站来说，采用　

ｉｔｅｒ　ｏｆｒ　ｄａｔａ　ｍｉｎｉｎｇ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　５ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　

本文的公式和算法来聚类网页及用户，向用户推荐相关的感兴　

Ｅｘｔｅｎｄｉｎｇ　Ｄａｔｂａａｓｅ　Ｔｅｃｈｎｏｌｏｇｙ（ＥＤＢＴ）．Ａｖｉｇｎｏｎ，Ｆｒｎａｃｅ：［ｓ．ｎ．］，　

趣的网页是合理有效的。该算法和公式克服了传统的只是关　

ｌ９９６：１８．３２．　

（上接第２６６页）太网的大规模分布式网络化控制随着计算机、　

ｐａｒｔ　Ｉ：ａｎａｌｙｓｉｓ［Ｊ］．ＡＳＭＥ　Ｊｏｕｒｎａｌ　ｏｆ　Ｄｙｎａｍｉｃ　Ｓｙｓｔｅｍｓ，Ｍｅａｓｕ－　

通信、控制技术的飞速发展而成为工业自动化领域不可逆转的　

ｒｅｍｅｎｔ　ａｎｄ　Ｃｏｎｔｒｏｌ，１９８８，１１０（４）：３６７－３７３．　

发展趋势。然而当工业以太网以总线型拓扑结构实现时，通常　

［３］ＪＯＡＣＨＩＭ　Ｆ．ＰＲＯＦＩＮＥＴ－Ｓｃａｌｂａｌｅ　ｆａｃｔｏｒｙ　ｃｏｍｍｕｎｉｃａｔｉｏｎ　ｆｏｒ　ａｌｌ印－　

会出现大量交换机级联的情况，从而降低了网络化控制系统的　

ｐｌｉｃａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ＩＥＥＥ　Ｉｎｔｅｎｒａｔｉｏｎａｌ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｆａｃｔｏｙｒ　Ｃｏｒｎ－　

性能和稳定性。本文研究了一类采用全双工以太网连接，通过　

ｍｕｎｉｃａｔｉｏｎ　Ｓｙｓｔｅｍ．［ｓ．１．］：［ｓ．ｎ．］，２００４．　

级联交换机构成类似工业控制领域中常见的总线型拓扑结构　

［４］ＭＩＬＬＳ　Ｄ　Ｌ．Ｅｘｅｃｕｔｉｖｅ　ｓｕｍｍａｒｙ－ｃｏｍｐｕｔｅｒ　ｎｅｔｗｏｒｋ　ｔｉｍｅ　ｓｙｎｃｈｒｏｎｉｚａ—　

的网络化控制系统。首先分析了系统的结构特征，并通过实验　

ｔｉｏｎ［ＥＢ／ＯＬ］．［２００３］．ｈｔｔｐ：／／ｗｗｗ．ｅｅｃｉｓ．ｕｄｅ１．ｅｄｕ／～ｍｉｌｌｓ／ｅｘ－　

ｅｃ．ｈｔｍｌ＃ｉｎｔｏｒ．　

详细分析了其网络时延特性；之后讨论了此类控制结构在基于　

［５］徐皑冬，王宏，邢志浩．工业以太网实时通信技术［Ｊ］．信息与控　

时间的系统分析和设计过程中的时钟误差成因；最后结合精确　

制，２００５，３４（１）：６０－６５．　

时钟同步协议，给出了一种基于边界时钟和旁路时钟的时钟同　

［６］　ＡＮＳ￣ＩＥＥＥ　Ｓｔｄ．１５８８－２００２．ＩＥＥＥ　ｓｔａｎｄａｒｄ　ｆｏｒ　ａ　ｐｒｅｃｉｓｉｏｎ　ｃｌｏｃｋ　

步实现模式，用于此类网络化控制系统的时钟同步方法的实　

ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ　ｐｒｏｔｏｃｏｌ　ｆｏｒ　ｎｅｔｗｏｒｋｅｄ　ｍｅａｓｕｒｅｍｅｎｔ　ａｎｄ　ｃｏｎｔｒｏｌ　ｓｙｓ－　

施。关于网络化控制系统的时钟同步还有许多研究内容。例　

ｔｅｍｓ［Ｓ］．［Ｓ．１．］：［ｓ．ｎ．］，２００２．　

如本文是在假设传输链路双向对称的情况下讨论时钟同步问　

［７］ＷＥＩＢＥＬ　Ｈ．Ｈｉｇｈ　ｐｒｅｃｉｓｉｏｎ　ｃｌｏｃｋ　ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ＩＥＥＥ　

题，而实际应用中，尤其是网络负载很大时，这种情况几乎很难　

１５８８　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ａｎｄ　ｐｅｒｆｏｒｍａｎｃｅ　ｉｓｓｕｅｓ［Ｃ］／／Ｔｈｅ　Ｅｍｂｅｄｄｅｄ　

实现。此外大规模分布式混杂网络化控制系统（如工业现场　

Ｗｏｒｌｄ　２００５　Ｃｏｎｆｅｒｅｎｃｅ［Ｃ］．［ｓ．１．］：［ｓ．ｎ．］，２００５．　

中同时存在现场总线、工业以太网构成的异构网络化控制系　

［８］ＣＲＩＳＴＩＡＮ　Ｆ．Ａ　ｐｒｏｂａｂｉｌｉｓｔｉｃ　ａｐｐｒｏａｃｈ　ｔｏ　ｄｉｓｔｉｒｂｕｔｅｄ　ｃｌｃｏｋ　ｓｙｎｃｈｒｏｎｉ－　

统）的分布式时钟同步问题还存在许多理论和实践工作，有待　

ｚａｔｉｏｎ［Ｊ］．Ｄｉｓｔｒｉｂｕｔｅｄ　Ｃｏｍｐｕｔｉｎｇ，１９９８，３：１４６—１５８．　

进一步研究。　

［９］ＡＲＶＩＮＤ　Ｋ．Ｐｒｏｂａｂｉｌｉｓｔｉｃ　ｃｌｃｏｋ　ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ　ｉｎ　ｄｉｓｔｉｒｂｕｔｅｄ　ｓｙｓｔｅｍ　

［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｐａｒａｌｌｅｌ　ａｎｄ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｓｙｓｔｅｍｓ，　

参考文献：　

ｌ９９４，５（５）：４７４—４８７．　

［１］ＷＡＬＳＨ　Ｇ　Ｃ，ＹＥ　Ｈ，ＢＵＳＨＥＬＬ　Ｌ　Ｇ．Ｓｔｂａｉｌｉｔｙ　ａｎａｌｙｓｉｓ　ｏｆ　ｎｅｔｗｏｒｋｅｄ　

［１０］ＪＡＳＰＥＲＮＥＩＴＥ　Ｊ，ＳＨＥＨＡＢ　Ｋ，ＷＥＢＥＲ　Ｋ．Ｅｎｈａｎｃｅｍｅｎｔｓ　ｔｏ　ｔｈｅ　ｔｉｍｅ　

ｃｏｎｔｒｏｌ　ｓｙｓｔｅｍｓ［Ｃ］／／Ｐｒｏｃ　ｏｆ　Ａｍｅｒｉｃａｎ　Ｃｏｎｔｒｏｌ　Ｃｏｎｆｅｒｅｎｃｅ．［Ｓ．１．］：　

ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ　ｓｍｎｄ￣ｄ　ＩＥＥＥ　１５８８　ｆｏｒ　ａ　ｓｙｓｔｅｍ　ｏｆ　ｃａｓｃａｄｅｄ　ｂｒｉｄｇｅｓ　

［ｓ．ｉ１．］，１９９９：２８７６—２８８０．　

［Ｃ］／／Ｔｈｅ　５ｔｈ　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｆａｃｔｏｒｙ　Ｃｏｍｍｕｎｉｃａ－　

［２］ＨＡＬＥＶＩ　Ｙ，ＲＡＹ　Ａ．Ｉｎｔｅｇｒａｔｅｄ　ｃｏｍｍｕｎｉｃａｔｉｏｎ　ａｎｄ　ｃｏｎｔｒｏｌ　ｓｙｓｔｅｍｓ：　

ｔｉｏｎ　Ｓｙｓｔｅｍｓ－【ｓ．１．］：［ｓ．ｎ．］，２００４．