第1期 刘奕群，等：基于非内容信息的网络关键资源有效定位创 ·49· 比率与站点自身出链接个数是类似的非内容特征，2 和“1”2类.离散化属性取值的目的，是为了适应 者的不同在于，站点自身出链接文本比率一定程度 D3算法处理的要求，将取值类别局限在布尔变量 上反映了站点自身出链接质量的高低.仅仅列出导 上，则是出于减少算法复杂度的需要.离散化的具体 航信息的站点自身出链接，与给出子页面简要介绍 方式是选取特征阈值，比阈值大的样例特征取值为 的站点自身出链接，其质量是显然不同的.站点自身 1,否则取值为0.阈值的选取总体遵循保证信息增 出链接文本比率较高的页面，可以认为其出链接质 益最大的原则，但也可以作调整以得到满足不同需 量较高 要的决策树 关键资源页面一般都是关键资源站点的入口页 取值离散化后，根据D3算法的要求，信息增 面，其对应的站点自身出链接担负着引导用户访问 益最大的非内容特征（页面入度特征）选作决策树的 的任务，因此链接质量较高，这类页面也相应的拥有 根节点.训练样例集在根节点被分类后，每个子集重 较大的出链接文本比率.如图2所示 复计算信息增益的过程，并选取信息增益最大的非 内容特征作为这个子集对应的决策树节点的分类特 601 50 女.GOV语料库 征.当满足下列条件之一时算法结束： 40 兴关键资源练集 1)所有样例都具有近似相同的分类结果； 30 2)所有属性都已在每条从根节点到叶子节点的 20* 路径上被测试. 10 由上述步骤生成的决策树如图3所示，利用此 0 0.050.100.150.200.250.300.350.40othe 决策树，判定任意web页面是否可以归入关键资源 站点自身出链接比率 页面的范畴就成为可能，如果对全体web页面施行 图2站点自身出链接比率在关键资源训练集合和.GOV 决策树判定算法，就可以得到一个web页面全集的 语料库上的不同分布 子集一关键资源页面集合 Fig.2 Site self link anchor text rate of key resource 页面入度 training set and.GOV ≤0 >10 图中横坐标表示站点自身出链接文本比率的大 URL分极 小，而纵坐标表示.G0V语料库和关键资源训练集合 FE类 非FLE类 面页长度☐ 上的不同分布百分比.由数据可以看出，站点自身出 站点自身 <1000,/ >1000 链接文本比率较高的页面更可能是关键资源页面.此 出链接文本比案 非关键资源 关键资源 ≤0.17 、>0.1 页面 页面 特征的分布曲线与站点自身出链接个数特征非常类 非关键资源 页面长度 似，但在区分关键资源的能力上更强一些.有超过 页面 站点百身出链接数目 ≤1000/J000 76%的.G0V语料库页面出链接文本比率不足0.1， 50 、>50非关键资源页面关键资源页面 但在关键资源训练集中，这个比率只有39%. 非关键资源页面项面长度☐ 3非内容特征与关键资源页面判定 <1000/1000 非关键资源页面关键资源页面 决策树学习(decision tree learning)的方法被 图3利用非内容特征进行关键资源页面判定的决策树 选择用于进行web页面非内容特征的综合，这是由 Fig.3 Key resource decision tree constructed with ID3 于决策树算法自身的一些特点所决定的.决策树学 and nomcontent features 习适合解决目标函数具有离散输出值的问题，而且 4 往往是特征数目较少时，解决此类问题的最简单有 实验与结果分析 效的途径之一.文中使用的决策树学习算法，是由 本节将重点讨论根据.GOV数据得到的关键资 Quinlan在1986年提出的D3算法).算法引入了 源页面集合在实验中的若干统计与检索特性.在讨 信息增益的概念，并使用信息增益的多少来决定树 论这些特性之前，还将介绍文中实验所使用的训练 的结点需要测试的属性 与测试集合 具体到关键资源页面判定的问题，我们把页面 4.1训练集与测试集 非内容属性的取值离散化为一个布尔变量，即对于 文中所采用的实验数据均来源于.GOV语料库 某个非内容属性A而言，某页面P的取值只有“0” 中的页面，为获取可信的关键资源页面训练集与测 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net比率与站点自身出链接个数是类似的非内容特征 ,2 者的不同在于 ,站点自身出链接文本比率一定程度 上反映了站点自身出链接质量的高低. 仅仅列出导 航信息的站点自身出链接 ,与给出子页面简要介绍 的站点自身出链接 ,其质量是显然不同的. 站点自身 出链接文本比率较高的页面 ,可以认为其出链接质 量较高. 关键资源页面一般都是关键资源站点的入口页 面 ,其对应的站点自身出链接担负着引导用户访问 的任务 ,因此链接质量较高 ,这类页面也相应的拥有 较大的出链接文本比率. 如图 2 所示. 图 2 站点自身出链接比率在关键资源训练集合和. GOV 语料库上的不同分布 Fig. 2 Site self link anchor text rate of key resource training set and . GOV 图中横坐标表示站点自身出链接文本比率的大 小 ,而纵坐标表示. GOV 语料库和关键资源训练集合 上的不同分布百分比. 由数据可以看出 ,站点自身出 链接文本比率较高的页面更可能是关键资源页面. 此 特征的分布曲线与站点自身出链接个数特征非常类 似 ,但在区分关键资源的能力上更强一些. 有超过 76 %的. GOV 语料库页面出链接文本比率不足 0. 1 , 但在关键资源训练集中 ,这个比率只有 39 %. 3 非内容特征与关键资源页面判定 决策树学习 ( decision tree learning) 的方法被 选择用于进行 web 页面非内容特征的综合 ,这是由 于决策树算法自身的一些特点所决定的. 决策树学 习适合解决目标函数具有离散输出值的问题 ,而且 往往是特征数目较少时 ,解决此类问题的最简单有 效的途径之一. 文中使用的决策树学习算法 ,是由 Quinlan 在 1986 年提出的 ID3 算法[14 ] . 算法引入了 信息增益的概念 ,并使用信息增益的多少来决定树 的结点需要测试的属性. 具体到关键资源页面判定的问题 ,我们把页面 非内容属性的取值离散化为一个布尔变量 ,即对于 某个非内容属性 A 而言 ,某页面 P 的取值只有“0” 和“1”2 类. 离散化属性取值的目的 ,是为了适应 ID3 算法处理的要求 ,将取值类别局限在布尔变量 上 ,则是出于减少算法复杂度的需要. 离散化的具体 方式是选取特征阈值 ,比阈值大的样例特征取值为 1 ,否则取值为 0. 阈值的选取总体遵循保证信息增 益最大的原则 ,但也可以作调整以得到满足不同需 要的决策树. 取值离散化后 ,根据 ID3 算法的要求 ,信息增 益最大的非内容特征(页面入度特征) 选作决策树的 根节点. 训练样例集在根节点被分类后 ,每个子集重 复计算信息增益的过程 ,并选取信息增益最大的非 内容特征作为这个子集对应的决策树节点的分类特 征. 当满足下列条件之一时算法结束 : 1) 所有样例都具有近似相同的分类结果 ; 2) 所有属性都已在每条从根节点到叶子节点的 路径上被测试. 由上述步骤生成的决策树如图 3 所示 ,利用此 决策树 ,判定任意 web 页面是否可以归入关键资源 页面的范畴就成为可能. 如果对全体 web 页面施行 决策树判定算法 ,就可以得到一个 web 页面全集的 子集 ———关键资源页面集合. 图 3 利用非内容特征进行关键资源页面判定的决策树 Fig. 3 Key resource decision tree constructed with ID3 and non2content features 4 实验与结果分析 本节将重点讨论根据. GOV 数据得到的关键资 源页面集合在实验中的若干统计与检索特性. 在讨 论这些特性之前 ,还将介绍文中实验所使用的训练 与测试集合. 4. 1 训练集与测试集 文中所采用的实验数据均来源于. GOV 语料库 中的页面 ,为获取可信的关键资源页面训练集与测 第 1 期 刘奕群 ,等 :基于非内容信息的网络关键资源有效定位创 · 94 ·