Web使用挖掘下的Web页面层次分类技术研究，本文主要内容关键词为：技术研究论文,层次论文,页面论文,Web论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
Web挖掘是数据挖掘技术在Web数据上的应用，同传统的数据库数据相比，Web数据有其特殊性，即没有严格的结构模式、含有不同格式的数据形式（文本、声音、图像等），并且存在大量的冗余和噪声，同时Web还是一个动态性极强的信息源。Web使用挖掘目的是从Web用户的访问行为和Web站点自身所蕴涵的信息中，挖掘出潜在的用户行为特征和规律。由于Web数据自身的复杂性，挖掘前须经过对海量Web数据的选择、抽取和净化[1,2]的处理过程，其中Web日志信息，站点内的结构信息和Web页面的内容是Web使用挖掘的主要数据来源。由于Web站点内的页面之间的链接关系体现的是一种有向图的结构，从站点的整体设计上考虑，一个规划较好的Web站点内的页面之间的链接关系隐含着一种树形的分类结构，不同树体现出不同Web主题，用户对不同主题页面的访问也体现出用户不同的行为特征，因此，有效地从Web站点的有向图中抽取出其分类清晰的“树”，即Web站点主页下的层次分类结构对Web使用挖掘具有重要意义。
1 Web站点结构分析
一般的Web站点通常具有成百上千个网页或者更多，每一个网页对应一个具体的URL，网页之间通过超链关联起来，Web站点内还包含一些特殊性质的网页，如动画、图像等，这些在站点的结构分析过程中应该作为干扰信息去除，同时现行Web站点往往采用一个Web站点多个主机实现，特别是对于规模较大的网站，如新浪网的主站点和新浪商城分站点是采用不同主机实现的，但是同属于新浪网，或者单位内基于局域网实现的部门网站往往也是这样实现的，网站结构分析时要考虑一个站点的分布式实现。
逻辑结构上，一个Web站点是一个特殊的有向图，图中有一个特殊的根节点，这就是主页，所有页面之间的每一个链接就是这个图的一个有向边。一个逻辑结构设计得较好的Web站点，页面之间的类属和层次关系是比较明晰的，可简化为一棵树，这种清晰的结构往往能从页面的URL反映出来，如Root/A/B/C/X.htm，在多站点主机的分布式架构下，不同主机上的URL会有很大的不同。考虑用户访问方便，设计者往往在站点内部不同页面之间加上超链接，这就破坏了页面之间的层次类属关系，同时从内容上分析，很多网页可以作为一个子类别，也可以作为另一个主题相近的子类别，这要求我们在对网页分类时，不仅要划分出整个站点的树形层次，还要决定相近或相关的主题网页最终归属那个子类，以解决网页的具体分类问题[2,3]。
2 Web站点页面分类
现行的网页分类技术主要有：概率模型、关系学习、支持向量机等方法，这些都利用网页上的文本信息和网页间超链接关系等重要信息，使得分类效果比起一般的文本分类方法有了很大的提高，如概率模型的Bayes网络分类的方法，基于Markov随机场理论的迭代算法[4,5]，以及关系学习的FLIPPER系统使用PROGOL算法结合语义信息进行网页分类，如Slattery将FOIL归纳算法用于网页分类[6,7]，等等。但这些方法都是基于文本和其他一些信息对随机的网页集进行自动分类，它们对网页间超链接结构的利用只是局限于所给定的网页集内部的超链接关系，而实际上网页是处于某个网站当中，网站的整体布局和结构也对网页的分类提供了重要的信息。
2.1 Web站点分类树的构造
网站一般被设计成具有较为清晰的层次分类结构，充分利用网站的层次分类结构对网页进行分类，可以大大提高网页分类的精度。考虑到某个具体页面的分类，首先涉及的是它在整个Web站点树形结构中的位置问题，因此我们首要解决的是一个Web站点的树形结构的构造，构造一个站点的“树”，这里采用的是有向图的广度遍历方法来实现Web站点层次分类树的构造，其算法描述如下：
(1)读入站点主页。
(2)将主页入队列，并以主页作为树的根节点。
(3)在队列非空的情形下重复以下过程：
读队头元素，队头元素出队列。
如果出队列元素没有链接其他页面，则跳到(3)的开始继续处理。
否则 如果该页面是无效的，则抛弃该页面。
否则 循环 读入该页面链接所有子页面，处理每一个子页面：
如果该子页面是有效的，且没有处理过，则将该页面作为当前页面的子节点。
否则抛弃该页面。
页面的有效性：如果该页面代表的是噪声页面（图片或者动画等）或者该页面是其他Web站点的页面，则该页面是无效的，否则是有效的。
算法执行完毕，将会得到Web站点的树形拓扑结构，但考虑到Web站点中页面之间的链接构成的是一个有向图，很多情形下页面间的链接是便于访问者在相关主题页面间跳转，因此可能存在这样的情形：同一个Web页被两个或者两个以上不同上层页面所链接，如图1所示，页面F同时存在两个上层面B、C，在分类时必须决定F是属于B或者C，对于页面H也存在同样的问题。从主题内容上看，这两个不同的上层页面可能存在一定的联系或者相似性，那么在具体确定该页面到底属于那个父页面时需要对这种相似性、或关联性进行取舍，决定该页面属于那个父页面，进而确定该页面的类别。确定的方法可以通过对页面内容的分析，比如页面的关键词语意的分析，内容相近的作为父页面，或者通过计算页面的相关性分析来实现，将该页面作为与之相关性最大的页面的子页面，本文采用第二种方法。
图1 页面链接图
2.2 Web站点的页面相关性
做页面相关性计算时，如果对页面的URL进行判断是简易可行的，则可以避免相关性的计算，比如B页面的URL是F页面URL的前缀表示，则从网站的设计意图出发，自然可以把F页面归属为B页面的子页面，也就是说，F页面是B页面的子类，但如果B页面的URL和C页面的URL都不是F页面的前缀表示，则情况要复杂些，可以采用的方法有两种，一种是通过F、B、C页面的语义分析，决定F的隶属，这涉及自然语言理解[5]问题，从现阶段研究成果来看，此种方法分类的结果并不理想；另一种是从网站内部结构来考虑，我们可以计算F页面和B、C页面的相关性，将F页面归属为与其相关性大的页面的子页面，在构造Web站点分类树的过程中，出现一个页面被两个上层父页面链接时，必须决定该页面隶属于那个父页面。
具体计算页面相关性时，可以通过页面的PageRank[8,9]值的计算来实现，页面的PageRank值表示的是一个页面在站点中的重要性程度，决定其是否为关键页面，PageRank值高的页面可以认为是Web站点内关键页面或者是一类的页面的“子主页”，计算PageRank的方法如下：定义一个Web站点的所有页面及页面间的链接构成一个有向图G=(V,E)，其中V代表页面集合，E代表页面间有向的链接集合，
在计算父页面B和子页面F的相关性时，通过计算B页面在去除子页面F的前后的PageRank值的变化来实现，如果页面F属于父类页面B，则由F页面及其链接的其他页面会对页面的PageRank的值有一定的增益，因为页面主题相关性，F页面及其子页面往往有反向的链接到页面B。
△(j,k)表示PR(j)的页面增益，如果计算结果△(j,k)的值大于一定的试验域值δ时，可以认为k页面是j页面的子类页面，因此在构造页面的层次分类树时可以把页面k作为页面j的子节点。
2.3 Web 页面编码表示
由于一个Web站点页面数量往往很多，页面之间的链接数量也是巨大的。分类的结果可能是一个父页面链接了多个相关的子页面，采用树来表示和存储是不现实的，必须把这种由大量页面所构成的树通过数据库方式存储，以实现对不同页面URL的分类表示。也就是说数据库不仅要存储每个页面的代码，还要存储由页面集合所构成的逻辑树，一种可行的方法是对每个页面进行编码，通过编码表示每个页面、页面的类别以及页面之间父子关系；借鉴哈夫曼树的前缀编码思想，我们采用页面的前缀编码来实现这种思想，为了描述问题简化起见，这里用二进制的页面编码来体现这种思想，如图2所示是一个简化的Web站点的层次分类树：
在我们的试验系统中，对内建的模拟站点（如模拟的苏州大学网站，其中192.168.1.7:8080是虚拟的IP地址）进行了数据分析，表1给出了在构造Web站点的层次分类树基础上的部分页面的层次编码。
3 层次分类的实践意义
3.1 页面分类的准确性
页面分类的准确性对用户聚类和关联规则的挖掘有着重要的意义。对于页面分类领域，有多种比较成熟的分类技术，如使用文本分类的相关方法，即在文本自动分类算法的基础上，结合网页的特点训练分类器，对网页进行分类，较为成熟的有支持向量机(Support Vector Machine,SVM)[10,11]分类技术，但该方法很容易产生“维数灾难”，即特征空间的维数过高问题——高维的特征向量产生极高的计算复杂度，一般的分类算法处理高维所带来的噪声会淹没对分类有用的信息，影响分类精度，其改进的重点是如何有效的进行降维，较新的改进方法有特征选择，即选择一些主要特征，通过评价函数进行降维以及利用映射的方法（特征提取），把原始项集映射到较低维的空间中，其中较经典的有主成分分析、Fisher线性判别分析[12,13]以及投影寻踪等方法；另一类重要的方法是结构语义的页面分类方法，超链接的结构语义主要考虑的是链源与链宿在Web结构中逻辑层次上的关系以及超链接的方向。超链接的内容语义则着重考虑链源与链宿在内容方面的相关问题。由于超链接的信息单元之间的内容语义关系大部分是隐式的，所以要确定信息单元之间潜在的内容语义关系，需要用到自然语言理解方面的技术，现阶段自然语言理解的技术还不成熟，因此该类方法实际上分类的效果还不很理想。
事实上，本文所讨论的分类方法近似于结构语义的分类方法，它既考虑到结构上的逻辑层次，又考虑网站构建者设计网页的意图——网站隐含的分类模型，通过页面之间链接的层次关系和分析设计者对页面的归类意图得到网页的分类结果，较通常的分类方法具有更简洁和更准确的特点。
表2给出了本文所阐述的分类方法在一些网站上的测试结果（测试考虑计算量的因素，分类结果精确到一级类别分类）。
从表中可以看出，该方法对一般类型的网站分类的准确率较经典的SVM算法和主成分分析方法一般达到的96%的准确率有一定的提高[10,11]；并且从计算效率上来说，本文采用的网站站点层次分类方法，较单纯的从语义上对网页分类分类算法，如主成分分析方法也有较大的提高。
3.2 用户行为的向量表示
在实现对Web页面分类编码表示之后，一个页面的编码能够体现出它在树中的层次和类属，因此，作为用户来说，访问某类页面的频繁程度能够反映出该用户的兴趣、爱好，即该用户的行为特征。假设用户访问了页面
，而它们的父页面分别为A，B，C，则该用户的访问行为可以用这样的行为向量来描述：
其中，
表示该类页面的访问频度，根据用户访问的页面及访问的频度，建立用户行为描述向量，向量的每一元素是一个二维向量（其中包括URL编码和权值，权值由访问频度决定），根据描述用户行为的精度需要对行为向量归约到站点树的某一类别层，形成多维向量空间基底表示的用户行为向量，即特定用户的行为向量用多维向量空间的基底线性表出，它能更准确地反映用户的行为特征。一般地，用户行为描述向量形式为：
其中，
表示一个二维子向量，包含页面的编码和此页面的访问频度；n的值与具体的网站有关系，它实际上是网页分类的种数，可以根据分类的精度要求来确定，具体每一种是一个n维空间的基底，而某一个用户行为向量由n个基底线性表出。这样可以较为精确的描述用户的访问行为，为挖掘用户的行为特征提供简洁有效的数据[14,16]，笔者已在文献[14][16]中给出了较为详细的论述，表3给出了试验系统中的部分注册用户的行为描述向量。
Web使用挖掘通过分析用户的访问行为来获得用户的行为特征模式，在建立了用户访问向量之后，可以通过描述用户行为特征向量对用户群体进行聚类[14,15,16]，此方法建立的用户向量由站点页面类别数n决定其空间维数n，具体类别n的值可以根据分类的粒度即分类到站点结构树的哪一层来确定，一般情形下，取到站点主页的下一层；由n维空间基底结合用户的页面访问频度产生描述用户行为特征的访问向量，该方法得到用户访问向量具有维数一定、数值小，且用户行为特征描述准确的特点，在提高计算精度的前提下大大降低了计算量，避免了维数灾难；同时还可以通过每个页面的编码表示描述用户行为特征的关联规则，为智能Web个性化推荐引擎提供知识依据，这些在我们的智能Web服务系统中得到了很好的应用[14,16]，限于篇幅，具体的实现过程本文作者在文献[14][16]中有较为详细的论述。
表3 用户行为向量表
4 结束语
通过挖掘Web站点的内在层次分类结构实现对网页的分类，在效率上和准确度较传统的一些只通过页面文本信息进行分类方法都有了较大的提高，这一点在试验数据中也得到了验证；并且通过建立用户行为向量，使用行为向量描述用户的行为特征，对用户群体进行聚类划分，挖掘一类用户的行为模式，为智能Web个性化服务提供良好的知识支持[14,16]，这些对于Web使用挖掘具有重要的理论和实践意义。
收稿日期：2007年3月26日