（产业经济学专业论文）聚类算法在中俄经贸合作网的应用.pdf

对外经济贸易大学硕士学位论文 摘要 w e b 站点的日志数据记录了浏览用户对此w e b 站点访问时的大量信息，对这些信 息的分析有利于网站设计人员掌握用户的爱好和习惯，网站设计人员可以据此对网站 的结构进行优化和页顽重组。 聚类分析是数据挖掘中的一个重要研究领域，是一种数据划分或分组处理的重要 手段和方法。目前，传统的聚类算法大体上分为划分的方法、层次的方法、基于密度 的方法、基于网格的方法和基于模型的方法。 本文首先对w e b 挖掘技术分类进行介绍，然后重点对本论文用到的算法进行了详 细的介绍。 k - m e a n s 算法是一种基于划分的聚类算法，它把n 个对象划分成k 个类，其中的 聚类数目k 是输入参数。该算法是通过不断地迭代来进行聚类，当算法收敛到一个结 束条件时，就终止迭代过程，输出一个聚类结果。 层次的方法对给定数据对象集合进行层次的分解，层次的聚类方法可以进一步分 为凝聚的和分裂的层次聚类。 模糊聚类分析的实质则是根据研究对象本身的属性来构造模糊矩阵，在此基础上根 据一定的隶属度来确定其分类关系。本文给出了科学文献的模糊聚类算法的具体算法 描述，对于新的用户，当他们第一次浏览网站的时候，通过计算他们和其他用户的相 似度对其进行归类。 最后，本文将k - m e a n s 算法和层次聚类算法应用到中俄经贸合作网的日志分析 系统中，对该网站的日志数据进行聚类，对模糊聚类算法进行了理论移植，实现了整 体架构和数据库的框架设计，对最初始的数据进行了预处理，可以为今后的个性化服 务做准备。 关键词：聚类算法模糊聚类w e b 日志网站 对外经济贸易大学硕士学位论文 a b s t r a c t t h ed a i l yl o gd a t ao fw e bs i t er e c o r d sl o t so fv i s i t i n gi n f o r m a t i o nf o rt h ew e b w ec a n d r a wt h eu s e rh o b b yi n f o r m a t i o nf r o ml o gf i l e w e bs i t e sd e s i g n e rp r o c e e d e dt h ep a g e r e o r g a n i z a t i o na n de v e ni n t e l l i g e n tw e bc a np r e d i c tt h en e x tv i s i t e dp a g e i nt h ef u t u r e c l u s t e r i n gi sa ni m p o r t a n ta r e ao fa p p l i c a t i o nf o rav a r i e t yo ff i e l d si n c l u d i n gd a t am i n i n g a n di sa l li m p o r t a n tm e t h o do fd a t ap a r t i t i o no rg r o u p i n g c l u s t e r i n gi sa ni m p o r t a n ta r e ao fa p p l i c a t i o nf o rav a r i e t yo ff i e l d si n c l u d i n gd a t am i n i n g a n di sa ni m p o r t a n tm e t h o do fd a t ap a r t i t i o no rg r o u p i n g s of a r , t h e r ea r e5k i n d so f c l u s t e r i n ga l g o r i t h m si n c l u d i n gp a r t i t i o na l g o r i t h m ，h i e r a r c h i c a la l g o r i t h m ，d e n s i t y b a s e d a l g o r i t h m ，g r i d b a s e da l g o r i t h ma n dm o d e l b a s e da l g o r i t h m t h ep a p e rf i r s ti n t r o d u c e sc l a s s i f i c a t i o no fw e b m i n i n gt e c h n i q u e s ，w i t ht h ee m p h a s i so n t h ea l g o r i t h mu s e di nt h i sp a p e r k - m e a n si sap a r t i t i o n - b a s e dc l u s t e r i n ga l g o r i t h m ，w h i c hd i v i d en o b j e c t si n t ok d i f f e r e n t k i n d s ，o f w h i c h , ki sa ni n p u tp a r a m e t e r t h i sa l g o r i t h mc l u s t e r st h r o u g hc o n t i n u o u si t e r a t i o n , b yw h i c hw h e nt h ea l g o r i t h mc o n v e r g e si n t oa ne n d i n gc o n d i t i o n ，i t e r a t i o ns t o p sw i t ht h e o u t p u to fo u e c l u s t e r t h eh i e r a r c h i c a lm e t h o di st h ed e c o m p o s i t i o no ft h eg i v e nd a t aa g g r e g a t eh i e r a r c h i c a l l y t h i sm e t h o dc a nb ef u r t h e rd i v i d e di n t ot h ea g g l o m e r a t i v ea n ds c h i s m a t i c a lc l u s t e r f u z z yc l u s t e ri sa c t u a l l yt h ef o r m a t i o no faf u z z ym a t r i xa c c o r d i n gt ot h ep r o p e r t i e so f t h er e s e a r c hs u b j e c t ，a n dt h ec o n f i r m a t i o no ft h ec a t e g o r i z a t i o nr e l a t i o ni nv i e wo ft h ed e g r e e o fm e m b e r s h i p t h i sp a p e rg i v e sad e t a i l e dd e s c r i p t i o no ft h ef u z z ya l g o r i t h mu s e di n s c i e n c el i t e r a t u r e f o rn e wu s e r s , w h e nt h e yb r o w s et h ew e b s i t ef o rt h ef i r s tt i m e ， c l a s s i f i c a t i o nc a nb em a d eb yc o m p u t i n gt h es i m i l a r i t yb e t w e e nt h en e wa n do t h e ru s e r s l a s t l y , t h ew r i t e rc o n d u c t sa n a l y s i so ft h ea p p l i c a t i o no fk m e a n sa n dh i e r a r c h i c a l c l u s t e ri nt h ed i a r ya n a l y s i ss y s t e mo ft h es i n o f o r e i g ne c o n o m i ca n dt r a d ew e b ，c l u s t e r i n g d i a r yd a t ao ft h ew e ba n dd o i n gt h e o r e t i c a lt r a n s p l a n t a t i o no ft h ef u z z yc l u s t e ra l g o r i t h mi n p r e p a r a t i o nf o rt h ef u t u r ep e r s o n a l i z e ds e r v i c e s k e yw o r d s ：w e bl o gm i n i n g , f u z z yc l u s t e r , l o gd a t ao fw e b ，w e bs i t e 2 对外经济贸易大学硕士学位论文 1 1 研究的目的及其意义 第一章绪论 本篇论文主要论述和研究的数据是基于目前信息学院承担的中俄经贸合作网 信息采编项目。可获取相关网站的w e b 日志文件和有关资料。通过对该网站w e b 日恚 的分析，运用本文要重点研究的聚类算法，希望对w e b 日志数据运用不同算法进行聚 类，分析得到的数据结果，通过研究不同的聚类算法，从中选择最合适的聚类算法。希 望通过聚类分析使得网站能够提供更好的个性化服务，完善系统性能，完善网站设计。 选择具体的算法运用到中俄经贸合作网这个具体事物中来，实现算法在具体环境和具 体事物中的具体应用，再对其进行总结，以便更好地运用算法，使其更加适用于更多 的事例中去。加强对数据挖掘应用系统研究。目前国内关于数据挖掘理论研究较多， 虽然可以说对算法本身的研究不少，但针对实际应用的研究却较少。由于国内对数据 挖掘应用系统的研究方面较少，所以应重视数据挖掘技术的实际应用。但目前国内有 关应用的成功案例较少。因为在w e b 日志中大数据量的情况，如何合理、准确的对用 户聚类是个难点。若能把聚类算法应用于w e b 日志中，可以从实际中充实了数据挖掘 的事例，实际数据挖掘应用的开发有助于对数据挖掘的理解，从而更好地推进数据挖 掘。 数据挖掘的目的是从大量的数据中找出潜在、有用的信息。面对海量的资料，首 要的任务是将它合理的归类。否则，在许多情况下，问题不是没有模式被发现，而是 模式太多了。而聚类分析就是将数据合理归类的一种方法，它把分类对象按一定的规 则分组或类，这些组或类不是事先给定的，而是根据数据特征而定的。在一个给定的 类里，这些对象在某种意义上是倾向于彼此相似，而在不同的类里的对象差别较大。 聚类分析是多元统计分析的重要组成部分，在传统的统计分析中已有多种算法，随着 数据挖掘技术的兴起，又有许多新的算法被提出。目前，聚类分析已经被广泛地用在 许多领域中，包括模式识别、数据分析、图像处理以及市场研究等。聚类是数据挖掘 中一门非常有用的技术，可以用于从大量数据中寻找隐含的数据分布和模式。通常， 聚类是为了需求数据的自然聚集结构，通过聚类，将数据划分为若干类，然后在每一 类中寻找模式和各种潜在的有用信息；此外，聚类还可用于对孤立点的监测。有时进 行聚类不是为了将对象聚集在一起而是为了更容易地使某个对象从其他对象中分离出 来。对于同一对象，聚类方法不唯一，这就产生了如何挑选其中“最好的”聚类方法， 这依赖于以下评判标准：( 1 ) 能够适用于大数据量；( 2 ) 能应付不同的数据类型：( 3 ) 能够 对外经济贸易大学硕士学位论文 发现不同类型的聚集：( 4 ) 使对专业知识的要求降到最低；( 5 ) 能应付脏数据；( 6 ) 对于数 据不同的顺序不敏感；能应付很多类型的数据；( 8 ) 模型可解释，可使用等1 。由于聚 类方法在数据挖掘中具有重要的意义和用途，因此研究和运用它就变得非常必要。 1 2 国内外研究现状 c h e r t 等人首先将数据挖掘技术应用于w e b 服务器日志文件，以期发现用户浏览模 式。h a r t 等人则根据w e b 日志建立数据立方体，然后对数据立方体进行数据挖掘和联机 分析处理。w e b 日志挖掘可以分为以c h e n 为代表的基于事务的方法和以h a n 为代表的基 于数据立方体的方法。 最初研究的重点放在对模式发现中挖掘算法的设计、分析和改进，现阶段对日志 文件预处理方法和模式分析的研究也有所增加。在现有的w e b 日志挖掘工具中，比较有 代表性的有：s i m o n f r a s e r 大学的w e b l o g m i n e r 2 将w e b f i 志中的数据组织为数据立方体， 然后在其上进行联机分析处理和数据挖掘。h u m b o l d t 大学的w u m ( w e bu t i l i z a t i o n m i n e r ) 能够挖掘w e b 日志中的序列模式，并提供一个集成了日志准备、模式查询以及 可视化的环境但其模式查询语言m i n t 在表达序列模式的约束时不够灵活。m i n n e s o t a 大学的w e b m i n e r 系统提出一种通用的w e b 日志挖掘的体系结构，该系统能自动从 w 曲日志中发现关联规则和序列模式等。w e b m i n e r 的思路是通过对w e b 站点的同志 进行处理，将数据组织成传统的数据挖掘方法能够处理的事务数据形式，然后利用传 统的数据挖掘方法( 如传统的关联规则发现算法) 进行处理i b m 公司的w e b 使用挖掘和 分析- r 具p e e d t r a c e r ，通过在用户会话上应用数据挖掘能够发现频繁遍历路径和频繁访 问页面组( 其中的页面经常被一起访问，但不一定位于同一条遍历路径上) 。 从收集到的文献来看，国内对挖掘算法研究较多的是关联规则挖掘和序列模式挖 掘，以及频繁遍历路径挖掘而对聚类挖掘的关注较少3 。现有的聚类主要集中在相似客 户群体的聚类和相关w e b 页面的聚类。对于相似客户群体聚类，国内的大多数研究者还 停留在主要依靠统计学方法和简单聚类方法的阶段，如采用基于模糊等价关系的聚类 算法。国内对于聚类的研究开展比较晚，研究主要方向包括： 1 2 1 对已经提出来的聚类算法进行分析和完善 在原有的d b s c a n 算法的基础上，以核心对象邻域中所有对象的代表对象为种子 对象来扩展类，提出了f d b s c a n 算法，该算法能够有效地对大规模数据库进行聚类， 速度上数倍于d b s c a n ，对原d b s c a n 算法进行改进，提出了基于数据分区的d b s c a n 1 李金易，徐啤琪数据挖掘质量问题探讨统计研究，2 0 0 47 期 2j w h a r t , m 1 ( a m b e f ：数据挖掘概念与技术 范研孟小峰机械t 业 ；版社，2 0 0 1 ，2 2 3 2 6 2 3 李婧靖，邵培桀，j 5 5 c 亦滞( 数据挖掘袖中田的现状和发展研究) 管理t 程学报，2 0 0 4 第3 期 2 对外经济贸易大学硕士学位论文 算法，提高了聚类速度，改善了聚类质量。 1 2 2 概念聚类的研究 概念聚类适用于领域知识不完整或领域知识缺乏时的数据挖掘任务。通过定义一 种基于语义的距离判定函数，提出了一种动态概念聚类的算法，该算法能够自动确定 聚类数目，依据聚类内部属性值的频繁程度修正聚类中心，通过概念归纳处理，用概 念合取表达式解释聚类输出。 1 2 3 复杂聚类方法的研究 目前聚类研究主要集中在对复杂聚类方法上，如对高维数据的可视化聚类方法以 及基于大规模交易数据库的二次聚类算法c a = l d 。该算法只需扫描一次数据库，聚 类过程在内存中进行，因此能处理大规模的数据库：聚类的各种方法的主要区别在于 实现算法的思想不同，聚类的各种方法各有其优缺点，算法的选择取决于数据的类型、 聚类的目的和应用。一些聚类算法可能集成了多种聚类算法的思想，此外，某些应用 可能有特定的聚类标准，要求综合使用多种聚类技术。 综上，目前大多数聚类算法存在以下几个缺陷：( 1 ) 一些算法假设聚类的数目已知， 然而这一假设在现实中往往难以满足；另一些算法能够通过试验确定聚类数，然而计 算非常复杂费时。( 2 ) 没有考虑聚类的健壮性问题，或假设噪音数据在数据集中所占的 比例和分布已知，这也是与现实情况不相符合的，因而当真实数据中含有大量噪音时， 算法就会失败。( 3 ) 忽略了算法的规模性问题，当所要处理的数据量急剧增大时，算法 的性能大大降低。本文希望针对规模性问题进行研究和运用，聚类是一个活跃的研究 领域，聚类就是将数据对象分组成为多个类或簇，在同一个簇中的对象之间具有较高 的相似度，而不同簇中的对象则差别较大，聚类算法具体可以分为：划分方法、层次 方法、基于密度的方法、基于网格的方法以及基于模型的方法等。聚类分析可以用作 独立的数据挖掘工具，来获得对数据分布的了解，也可以作为其它数据挖掘算法的预 处理步骤。 以上这些就是国内外的研究现状，数据挖掘相对还是比较新颖的东西，其算法还 有其适用性的一面，在国内，研究机构和大学的研究比较多，但在企业的应用还相对 少些，所以我研究算法并对其进行运用，以便更好的适用与各个企业的具体情况，从 实际应用中寻找经验以便能推进算法的进一步改进和发展。 1 3 研究内容 本文希望通过对聚类算法的研究和分析，选择出合适的聚类算法：对w e b 只志进 3 对外经济贸易大学硕十学位论文 行聚类分析，重点分析用户聚类和页面聚类：最终目标是能够根据分析结果对网站建 设、栏目设置等提出合理化的改进建议。本论文的主要工作有以下几个方面： ( 1 ) 对w e b 挖掘的定义、特征和分类和w e b 日志挖掘的定义和内容进行了详细的介 绍。 ( 2 ) 对聚类进行较系统而完整的分析，包括聚类的概念、聚类算法、以及聚类在其 它各种领域的应用。 ( 3 ) 运用s p s s 工具中的k - m e a n s 算法和层次算法对中俄经贸合作网的w e b 日志数 据进行了挖掘和具体的分析。 ( 4 ) 对科学文献的模糊聚类算法给出了详尽的说明和算法描述，并理论移植到中俄 经贸合作网上。并给出了系统的整体架构设计和数据库的框架设计，对最初始 的数据进行了预处理。 4 对外经济贸易大学硕士学位论文 2 1 引言 第二章w e b 数据挖掘与聚类算法 w e b 拥有巨大的信息资源，许多在线信息服务已经在互联网上迅速发展起来。互 联网已经成为一个巨大的、分布广泛的、全球性的信息服务中心，它提供新闻、广告、 消费信息、金融管理、商业信息发布、教育、政府、电子商务和许多其它信息服务。 电子商务w e b 还包含了丰富和动态的超链接信息，以及w e b 页面的访问和使用信息。 这为数据挖掘提供了丰富的资源。这一个巨大的信息资源为数据挖掘研究提供了良好 的数据背景，使得w e b 挖掘迅速成为数据挖掘的一个研究和应用的热点，w e b 挖掘的 目的就是发现w e b 的访问模式、w e b 的链接结构和w e b 的内容描述中存在的规律和动 态信息，从上述三个方面，一般将w e b 挖掘分为三类：w e b 内容挖掘、w e b 结构挖掘 和w e b 使用挖掘。w e b 挖掘分为四个子任务：资源搜索、信息选择和预处理、模式发 现和模式分析4 。 2 1 1w e b 挖掘的定义 w e b 挖掘是一门交叉性学科，涉及数据挖掘、机器学习、模式识别、人工智能、统 计学、计算机语言学、计算机网络技术、信息学等多个领域。对w e b 挖掘可以从不同角 度进行划分，从广义的角度出发，可以对w e b 挖掘作如下的定义5 ： 定义1 ：w e b 挖掘是指从大量非结构化、异构的w e b 信息源集合中发现有效的、新 颖的、潜在可用的及最终可理解的知识( 包括概念( c o n c e p t s ) 、模式( p a t t e r n s ) 、规则 ( r u l e s ) 、规律( r e g u l a r i t i e s ) 、约束( c o n s t r a i n t s ) 及可视化( v i s u a l i z a t i o n s ) 等形式) 的非平凡过程。以上定义借鉴了数据挖掘的传统定义。因此w e b 挖掘在部分方法和技术 研究方面也与数据挖掘相似，具有相通之处。 如果从实用性开发的角度来考虑的话，可以对w e b 挖掘作出如下的定义6 定义2 ：w e b 挖掘是针对包括w e b 页面内容、页面之间的结构、用户访问信息、电子 商务信息等在内的各种w e b 数据源，在一定基础上应用数据挖掘的方法以发现有用的知 识帮助人们从w w w 中提取知识，改进站点设计，更好地开展电子商务等应用。 4 林杰斌等编著数据挖掘与o l j j 理论与实务 第2 1 8 页 s 王继成，潘会贵，张福炎( w e b 文奉挖掘技术研究，计算机研究与发展，2 0 0 3 第4 期3 2 3 6 页 6 ，：实，商丈，段蚓鹑i n t c m c l 卜的文奉效据挖掘 计算机科学，2 0 0 0 第4 期3 2 - 3 6 页 5 对外经济贸易大学硕士学位论文 2 1 2w e b 挖掘的特征 i n t e r a c t 上存贮了大量的、非结构化的信息，无法使用现有的数据库管理系统来操 纵和管理。主要特点如下1 ： ( 1 ) w e b 页面的复杂性高于任何传统的文本，w e b 页面缺乏统一的结构，它大量存在 的文档、图形、图像、声音信息及大型的商业数据、天气、水文数据等表现出多种信 息类型，而且用户有充分的自由，可以随意链接至l j i n t e m e t 的任意站点上。因此，i n t e r n e t 本身体现了巨大的、分层的、多维的、非结构化、动态性、不完全的，混沌的特点； ( 2 ) w e b 面对的是一个广泛的形形色色的客户社区，全球信息网大约有数亿个工作 站，其客户群仍在不断的扩展当中，用户群体也表现出多样性，其用户具有不同的背 景、不同的兴趣和使用目的； ( 3 ) w e b 上的信息只有很小的一部分是相关的或是有用的，甚至可以说9 9 的w e b 信息对于9 9 的用户是无用的。虽然这看起来不是很明显，但一个人只是关，i 二, w e b 上的 很小很小一部分信息确是事实，w e b 所包含的其余信息对用户来说是不感兴趣的，而且 会淹没所希望得到的搜索结果s 。 ( 4 ) w e b 是一个动态性极强的信息源：w e b 不仅以极快的速度增长，而且其信息还在 不断地发生着更新。新闻、股票市场、公司广告和w e b 客服中心都在不断地更新着各自 的页面。联接信息和查找记录也在频繁地更新之中。 2 2w e b 挖掘的分类 一般可以将w e b 挖掘分为3 类：w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) ，w 曲内容它 掘( w e bc o n t e n tm i n i n g ) ，w e b 使用记录挖掘( w e bu s a g em i n i n g ) 。w e b 使用记录挖掘 处理关于网站结构方面的问题，关心的是如何从存储的w e b 访问日志中发现浏览者行为 的有趣信息。下面将分别讨论这三种w e b 挖掘。 7 j a t h 卸i i c c h c r n y k 。h 州n l o f i a l 。n e 删脯e 缸d a i c k s l r m m i n i 喀f j 哦s i a m i n 姥m a l i 。n 啦c f e l t n d a t am i n i n 9 2 0 0 1 4 8 林杰斌等编著数据挖掘。j o l a p 理论q 实务第2 1 8 页 6 对外经济贸易大学硕士学位论文 图2 1 w e b 挖掘的分类 资料来源：林杰斌数据挖掘与o l a p 理论与实务，第2 1 9 页 2 2 1w e b 内容挖掘 w e b 内容挖掘是从文件内容或其描述中提取知识的过程。w e b 内容挖掘可以协助用 户搜索信息或者根据用户的配置文件为用户过滤无用的信息。基于w e b 文档的文本挖掘 ( t e x tm i n i n g ) 是w e b 内容挖掘的主要研究内容，这里把基于w e b 的多媒体数据挖掘 ( m u l t i m e d i ad a t am i n i n g ) 也归为w e b 内容挖掘。文本挖掘目前主要用于w e b 页面归纳 和搜索结果归纳，例如： a h o y ! ( h t t p ：w w w c s w a s h i n g t o n e d u r e s e a r c h p r o j e e t s w e b w a r e l w w w a h o ”是用于 发现个人主页的工具。输入查询的个人信息，a h o y ! 搜索引擎、电子邮件列表等i n t e r n e t 服务查询有关的数据，应用启发式规则分析文档的特征来识别个人主页。e d g eg a i n ( h t t p ：w w w s h o p b o t t o o l s c o r n ) 分析商家的主页和电子商务站点的文档结构，抽取价 格列表。通过分析搜索引擎查询出的结果，收集u r l 、标题、内容类型、内容长度和 超文本链接等信息，然后利用类s q l 的查询语言进行提炼得到更合适的结果。则依赖 搜索结果中页面的标题、u r k 快照( 描述或页面内容的第一行) 等对文档进行聚集， 然后再将它们分类。 2 2 2w e b 结构挖掘 w e b 结构挖掘是从w w w 的组织结构和链接关系中推导知识。由于文件之间的相 7 对外经济贸易大学硕士学位论文 连，w w w 能够提供除文件内容之外的有用信息，利用这些信息，可以对页面进行排 序，发现重要的页面。这方面的工作的代表有p a g e r a n k 和h i t s 算法 ( 1 ) p a g e r a n g 算法9 ： 假设要搜索一个给定话题的w e b 页面，例如金融投资方面的页面。这时我们除了希 望得到与之相关的w e b 页面外，还希望所检索到的页面具有较高质量和权威性。 这里基于了一个有意思的发现，即权威性( a u t h o r i t y ) 可由w e b 页面链接来反映。 w e b 不仅由页面组成，而且还包含了从一个页面指向另一个页面的超联接，超链接包含 了大量人类潜在的语义，它有助于自动分折出权威性语义。因此，大量的w e b 链接信息 提供了丰富的关于w e b 内容相关性、品质和结构方面的信息，这对w 曲挖掘是可以利用 的一个重要资源。 基于以上考虑，人们提出了如下的权威页面识别算法。 首先，w e b 可以用一个有向图来表示，g = ( ve ) ，v 是页面的集合，e 是页面之间的 超链接集合，页面抽象为图中的顶点。而页面之间的超链接抽象为图中的有向边。顶 点y 的入边表示对该页面的引用，出边表示v 引用了其它的页面。所以，w e b 页面之间 的超链接揭示了w e b 结构。链接文本( a n c h o r t e x t s ) 可以用来对被引用的页面进行索引 ( 例如，w w w , g o o g l e ) 超链接可以用来计算页面的排行分类，通过超链棱可以将一 个页面的排行分类传递到相邻的页面。 p a g e r a n g 的基本思想是：一个页面被多次引用，则这个页面很可能是重要的；一 个页面尽管没有被多次引用，但被一个重要页面引用，则这个页面很可能是重要的； 一个页面的重要性被均分，并被传达到它所引用的页面。 ( 2 ) h n s 方法1 0 ： h i t s 算法是利用h u b a u t h o r i t y 方法的搜索算法。它的思想是：一个页面的权威性取 决于它被引用的次数以及链接它的页面的权威性。h u b 页面发挥了隐含说明某话题权威 页面的功能。通常，好的h u b 指向许多好的权威页面；好的权威是指由许多好的h u b 所 指向的页面，这种h u b 与a u t h o r i t y 之间的互动可用于权威页面的挖掘和高品质w e b 结构 和资源的自动发现。面向h i t s 的系统包括c l e v e r ，o o o # 。 2 2 3 w e b 使用记录挖掘 w e b 使用记录挖掘是指通过挖掘存储在w e b 上的访问日志来发现有趣的信息( 用户 访问w e b 页面的模式及潜在客户信息的发现) 的过程。而在开始挖掘之前，仍需要经过 清洗、浓缩和转换。 基于u r l 、时间、l p 地址和w 曲页面内容信息，可以在w e bl o g 数据库上构造多维 视图，进行多维分析，有助于发现潜在客户、用户和市场等。 9 刘栋，刘希_ 匠，郝婷婷基于p a 錾瑚k 和h i t s 的w e b 结构挖掘算法研究山东科学，2 0 0 6 第4 期 1 0 刘栋，刘希玉，郝婷婷肇十p a g c n n k 和h i t s 的w 曲结构挖掘算法研究山东科学，2 0 0 6 第4 期 8 对丹经济贸易大学硕士学位论文 可以在w e bl o g 进行数据挖掘，找出关联模式、序列模式和w c b 访问趋势等。通过 分析和探究w e b i 了志记录中的规律，可以合理建造网站及合理设计服务器；帮助更好地 组织设计w e b 主页，并改进w c b 服务器系统的性能；识别电子商务的潜在用户，增强对 最终用户的因特网信息服务的质量和交付：帮助改进市场营销决策，如把产品广告放 在适当的w e b 页上或更好地理解客户的兴趣，根据客户的爱好来量身定制个性化的w e b 界面。 2 3w e b 日志挖掘研究 2 3 1w e b 日恚挖掘的定义 w e b 日志挖掘是指采用数据挖掘的技术，通过对w 曲服务器日志中大量的用户访问 记录深入分析，发现用户的访问模式和兴趣爱好等有趣、新颖、潜在有用以及可理解 的未知信息和知识，用于分析站点的使用情况，从而辅助管理和支持决策。不同用户 对同一网站的兴趣存在差异，但多多少少会有某些相同之处，这能够从他们在服务器 日志中留下的访问记录反映出来，因此通过对日志的挖掘，可以发现用户的共同偏好 和交叉兴趣。另一方面，同一用户在不同时期可能有不同的访问模式，但从长期来看， 也会表现出一定的规律和趋势，能够反映用户的兴趣。因为统计数据表明：大多数用 户在网站上的活动范围是很有限的，因而他们的活动中必然包含了许多重复的动作， 也就是说，用户的行为是有规律可循的，w e b 日志挖掘能够发现这些规律1 1 。此外， 由于w e b 服务器日志中记录了该服务器被外部访问的所有过程信息，通过对这些过程信 息的分析，可以客观地反映服务器的内部结构、组成、内容、访问频度等有关该服务 器的重要信息，对于评价和改进网站的服务质量来说是非常宝贵的资源。同时，在任 何一个服务器上都可以很方便地得到它的日志文件，数据的来源很方便，文件结构较 为良好，且数据挖掘技术的日趋成熟使得对这一不断增长的巨大数据文件的处理变得 可能n 。因此，w e b 日志挖掘是有效的，也是可行的。 2 3 2 w e b 日志的内容 w e b 服务器都包括那些内容呢? 它响应用户浏览器发出的请求，将发出的请求文件 发送出去的同时，会把这次请求写入日志，所以服务器日志文件记录了用户访问本站 点的信息。 不同的w e b 服务器产品的日志记录格式不同。常见的日志文件有两种格式，一种是 通用日志格式( c o m m o nl o gf o r m a t ) 一种是组合日志格式( c o m b i n e dl o gf o r m a t ) ，有 1 l 刘振宇，阳小华( 基十w w w 用户谢览模式的路径提示算法) 汁算机工程，2 0 0 0 第5 期 1 2 苏中，马少卜，扬强堆十的n 尢顶测模型，软件学撒。2 0 0 2 第1 期 9 对外经济贸易大学硕士学位论文 时也称扩展日志格式( e x t e n d e d l o g f o r m a t ) 。典型的通用日志文件包含以下内容：客户 端主机的l p 地址，w 曲服务器接收到用户请求的日期、时间和时区，请求方法如( g e t , p o s t ) ，被请求文件的u r l 和查询关键字也可以是被请求的w e b 应用程序在服务器上的 路径和名字，传输协议一般是m 1 甲的版本号，返回码表示响应请求的结果状态( 如2 0 0 表示成功，3 0 l 表示页面己被永久删除，3 0 3 表示页面没有改变，4 0 4 表示找不到所请求 的页面，5 0 0 表示内部服务器错误) ，传输的字节数。组合日志文件增加了两个域：引 用页( 指向被请求文件的页面) 的u r l ( 若用户通过书签或直接键入u r t i 羞行访问， 则该域为空) 和代理( 通常记录用户使用的操作系统和浏览器的类型，有时也记录自 动搜索站点的s p i d e r 或r o b o t 软件的名称) 。引用和代理信息也可以保存在单独的引用目 志和代理日志中。 2 4 聚类的概念及形式描述 聚类是数据挖掘中的一种主要技术，但与分类不同的是，它要划分的类是未知的， 聚类( c l u s t e r i n g ) 就是将数据对象分组成为多个类或簇( d u s t e r ) ，按照相似性归成若 干类别，即“物以类聚”。它的目的是使得属于同一个簇的对象具有较高的相似度，而 不同簇中的对象差别教大。相异度是根据描述对象的属性值来计算的，距离是经常采 用的度量方式。聚类方法包括统计方法、机器学习方法、神经网络方法和面向数据库 的方法。 在统计方法中，聚类称聚类分析，它是多元数据分析的三大方法之一( 其它两种 是回归分析和判别分析) 。它主要研究基于几何距离的聚类，如欧式距离、明考斯基距 离等。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有 序样品聚类、有重叠聚类和模糊聚类等。在机器学习中聚类称作无监督或无指导学习 ( u n s u p e r v i s e dl e a r n i n g ) 。因为和分类学习相比，分类学习的例子或数据对象有类别标 记，而要聚类的例子则没有标记，需要由聚类学习算法来自动确定。机器学习领域中 的概念聚类算法通过符号属性来进行聚类，并褥出聚类的概念描述。在概念聚类 ( c o n c e p t u a lc l u s t e r i n g ) 中，一组对象只有当它们可以被一个概念描述时才形成一个簇。 这不同于基于几何距离来度量相似度的传统聚类。当聚类对象可以动态增加时，概念 聚类则称是概念形成。概念聚类由两部分组成：( 1 ) 发现合适的类；( 2 ) 形成对每个类的 描述。 在神经网络中，有一类无监督学习方法自组织神经网络方法：如k o h o n e n 自组 织特征映射网络、竞争学习网络等等。神经网络中的s o m 方法，通过反复的学习来聚 类数据，它由输入层和竞争层组成。输入层由n 个输入神经元组成，竞争层由m a x = m 个输出神经元组成，且形成一个二维平面阵列。输入层各神经元与竞争层各神经元之 自j 实现全互连接。矢量量化v o 方法中的l b g 方法只能对数值属性进行聚类，通常的做 法是将所有要识别矢量的集合分成若干子集，各子集中的矢量具有相似特征，因而能 对外经济贸易大学硕士学位论文 用一个具有代表性的矢量来表示。该具有代表性的矢量称为码字，全部码字的集合称 为码本。聚类分析问题可描述为：给m 维空间r m 中的n 个向量，把每个向量归属n 5 聚 类中的某一个，使得每个向量与其聚类中心的“距离”最小。聚类分析问题的实质是一 个全局最优问题。在这里m 可认为是样本参与聚类的属性个数，n 是样本的个数，5 是由 用户预先设定的分类数目。 ， 数据聚类正在蓬勃发展，有贡献的研究领域包括数据挖掘、统计学、机器准则函 数值越大，表示聚类结果的各个类型分离性好，所以聚类质量高。另外，还有散射矩 阵和近邻函数的准则函数。散射矩阵是对聚类质量进行一个全面的描述和考核标准， 它不但能反映同类样本的聚集程度，而且也反映不同类之间的分离程度。对于个聚 类结果，类内散射越小越好，类间散射越大越好。而近邻函数准则用以表示类内损失 和类问损失的和函数，该值越小聚类质量越高。 2 5 数据挖掘中的聚类算法 2 5 1 划分聚类算法 划分聚类：给定一个包含1 1 个数据对象的数据库，以及要生成的簇的数目k ，一个 划分类的算法将数据对象组织为k 个划分，( k = i i ) ，其实每个划分代表一个簇，也就是 说，它将数据划分为k 个组，n 应该满足如下的要求： ( 1 ) 每个组至少包括一个对象； ( 2 ) 每个对象必须属于且只属于一个组。但是在某些模糊划分技术中第二个要求可以放 宽。给定要构建的划分数目k 划分方法是由一个初始划分开始，通过优化一个评价函 数把数据划分成若干子类，因此事实上己经把聚类问题转化成了优化问题，划分聚类 方法输出的是多个互不相交的聚类集，如，k - 均值算法”、c l a r a 算法、c l a r a n s 算法。 k - 均值算法思想是：给定类的个数k 将n 个对象分到k 个类中去，以使得簇内具有较 高的相似度，而簇间相似性较低；k - m e d o i d s 方法选取一个对象m e d o i d 来代替聚类中 心的作用，这样的一个m e d o i d 就标识了这个类。这种算法计算量要比k - 均值要大，一 般只适合小数据量；c l a r a 算法是一种基于采样的方法，能够处理大量的数据，算法思 想就是用实际数据的抽样来代替整个数据，然后再在这些抽样数据上利用k - m e d o i d s 算法。c l a r a 算法的效率取决于采样的大小，一般不太可能得到最佳的结果。因此在 c l a r a 算法的基础上，提出了c l a r a n s 算法。与c l a r a 算法不同的是：c l a r a 算法寻找最 佳的m c d o i d s 过程中，采样都是不变的。而c l a r a n s 算法在每一次循环过程中所采用的 采样都是不一样的。 例如本文要用到的k - m e a n s 算法1 4 属于聚类分析的一种，就是将一组物理的或抽象 1 3h t l p w 吣m d e m c l u s l c f n 玑c x l 脚i n c r t h r y ，i 【m c a n 洳e 卸s h t m l 1 4 j w l i a n m 1 ( a m b e f 数据挖掘概念j 技术范叫盂小峰机械t 业；i ；版 i ：，2 0 0 1 ，2 2 3 2 6 2 对外经济贸易大学硕士学位论文 的对象，根据它们之间的相似程度，分为若干组：其中相似的对象构成一组，这一过程就称 为聚类过程。一个聚类就是由彼此相似的一组对象所构成的集合；不同聚类中对象是 不相似的。就是从给定的数据集中搜索数据项之间所存在的有价值联系。在许多应用 中，一个聚类中所有对象常常被当作一个对象来进行处理或分析： ( 1 ) 输入聚类个数l 【，以及包含n 个数据对象的数据库。 但) 输出满足方差最小标准的k 个聚类。 ( 3 ) 处理流程：从n 个数据对象任意选择k 个对象作为初始聚类中心；根据 每个聚类对象的均值( 中心对象) ，计算每个对象与这些中心对象的距离，并根据最小 距离重新对相应对象进行划分：重新计算每个( 有变化) 聚类的均值( 中心对象) ； 循环到直到每个聚类不再发生变化为止。 k - m e a n s 算法1 5 接受输入量k ；然后将n 个数据对象划分为k 个聚类以便使得所获 得的聚类满足：同一聚类中的对象相似度较高，而不同聚类中的对象相似度较小。聚类 相似度是利用各聚类中对象的均值所获得一个“中心对象”( 引力中心) 来进行计算的。 k - m e a n s 算法的工作过程说明如下：首先从n 个数据对象任意选择k 个对象作为 初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度( 距离) ， 分别将它们分配给与其最相似的( 聚类中心所代表的) 聚类；然后再计算每个所获新 聚类的聚类中心( 该聚类中所有对象的均值) ；不断重复这一过程直到标准测度函数开 始收敛为止。一般都采用均方差作为标准 f ，乏。，m 2 式中，e 为数据库中所有对象的平方误差的总和；p 为空间的点，表示给定的数 据对象；慨为簇g 的平均值( p 和都是多维的) 。 式所示聚类标准旨在使所获得的k 个聚类具有以下特点：各聚类本身尽可能紧凑， 而各聚类之间尽可能分开。k - m e a n s 算法的计算复杂度为o ( n k t ) ，因而它在处理大数 据库时也是相对有效的( 具有可扩展性) ；这里n 为对象个数；k 为聚类个数；而t 为 循环次数。通常有k = n 和t = n 。k m e a n s 算法常常终止于局部最优。 假设k = 3 ，即需要将这些对象聚类为3 个簇。根据上述算法，任意选择3 个对象作 为3 个初始簇中心，簇中心在图中用“+ ”来标注。根据与簇中心的距离，每个对象被分配 给最近的一个簇。这样的分布形成了图2 2 ( a ) 中虚线所描绘 1 5 n 巍，蒋波，陈i 弃堆十k m c a 惦算法的中因移动市场顾客行为细分策略研究，管理学： i ，2 0 0 5 年第1 期 对外经济贸易大学硕士学位论文 ，i ，l ： 。， 、：- u 、 ：。每 c a ) ( b ) 图2 2 基于k - m e a