1 引言
搜索引擎是人们在因特网上获得信息的最主要手段, 最大限度地获得其中有用的信息是数据挖掘的目标。目前, 因特网上的各种类型的搜索引擎约有100多种, 它们显示的搜索结果页面形式多样, 但是大多数页面上都会包含一个指明有多少结果被找到的数字, 我们称为匹配数。匹配数在有些场合是非常有用的信息, 例如:获得搜索关键字的出现频率、评价引擎的数据库规模[1]、在程序中集成等等。通过对选取的多种搜索引擎页面进行观察可以看出, 搜索结果的显示方式没有规律性, 是不确定的。匹配数作为一个数字淹没在页面中, 很难自动、准确地提取出来, 孤立地查找匹配数显然相当困难。在研究中发现, 网页的一些特征属性可以用于匹配数判定, 如网页的布局结构、视觉特征、文本特性、链接特性等等, 决策树学习的方式适用于综合这些特征进行匹配数的判定。由于大多数情况下, 匹配数包含在一个整句中, 所以匹配数的判定分两步:第一步从整个页面中分离出包含匹配数的句子。如图1中由虚框标识的部份, 这种句子我们称为Match Count Unit (匹配数单元) , 简称为MCU。类似地, 一个页面中也有很多其它的整句单元, 通称为WEB Page Unit (WEB页面单元) , 简称WPU, 可见MCU也是WPU之一。由于MCU在页面中出现的位置和表现方式各不相同, 从众多的MPU中分离出MCU, 我们采用机器学习的决策树方法。第二步, 从MC U中获取匹配数。MCU中匹配数出现的形式多样, 须利用句型结构特征来标识匹配数, 所以仍然采用决策树方法。即本文中利用两棵顺序决策树来获取搜索结果页面的匹配数。
2 决策树概念
决策树算法的核心问题是选取树的每个结点的属性, 争取能够选择出最有助于分类实例的属性。为了解决这个问题, C4.5算法[2]用信息增益比率代替信息增益作为评价属性分类能力的度量, 从而避免使算法倾向于优先选择分支多的属性。C 4.5还可以通过自动离散化的方式处理取值连续的属性, 并借助决策树修剪的方式减少过学习情况的出现。
按照信息论的定义, 设有m类样本, 每类有Si个实例, 则把它们分类所需要的信息量 (任意样本分类的期望信息) 为:
S是s个数据样本的集合。类别属性具有m个不同值C i。
si是类Ci中的样本数。pi是任意样本属于Ci的概率, 并用si/s估计。
由非类别属性A划分为子集的熵:
非类别属性A具有v个不同值{a 1, a 2, …, a v}。利用A将S划分为v个子集{S1, S2, …, Sv};其中Sj包含S中在A上具有值aj的样本。Sij是子集Sj中类Ci的样本数。
信息增益:Gain (B) =I (s1, s2, ……, sm) -E (B)
增益比率衡量属性分裂数据的广度和均匀性, 其中, 分裂信息SplitInformation是S关于属性A的各值的熵:
得到信息增益比率为:
依据贪婪算法, 为了使下一步所需的信息量最小, 要求每一次都选择其信息增益比率最大的属性作为决策树的新结点[3]。
3 从WEB页面中标识MCU
对于搜索结果页面, 以HTML标记如DIV、TD、SPAN等为分隔符, 从网页DOM树的最底层标签开始, 把页面元素分成很多最小粒度的块, 然后忽略等表示颜色, 字体, 背景外观的标签, 将这些块聚合为一个成句, 从而将页面划分成了很多WPU。
为了从WPU中区别出MCU, 需要研究MCU与其它单元的不同特征, 网页的很多特征都可用来辅助识别MCU[4], 采用这些属性, 是因为MCU与其它的MPU在这些属性上有明显的取值差别, 分为以下几类:
页面布局属性:WPU的高度Height和宽度Width、WPU的页面边距TopDistance[5];
色彩相关特性:WPU背景色UnitColor;
M C U句法结构特征:句子中关键字出现的频数如result, of等;
以上这些特征在MCU的确定中所起的作用是不同的, 为了找出关键的特征, 采用机器学习的方法, 利用C4.5决策树的分类策略, 从这些属性中自动发现和选择对MCU的识别有用的特征。决策树算法与一般的机器学习算法一样, 都需要利用训练数据进行学习, 选择一些示例的网页, 手工地从所有的MPU中识别出符合条件的MCU, 对其中的所有单元都分别检验和计算各个不同属性的值, 构成训练集。
由于这些特征属性具有明显的连续性, 因此对于属性的度量标准, 需要先进行属性值离散化的工作, 选取合适的阈值, 阈值的选取要使该属性进行离散化后可能的信息增益值最大。在本文的实验研究中, 先按照属性值的分布特征选取相应的属性值之间的中间值为候选阈值, 然后计算候选属性的信息增益, 选择最好的作为离散化的阈值点:
For each连续特征Ai
根据Ai的值对样本排序
For each序列中的每对Xi, Xi+1,
If Xi和Xi+1的分类不同, 将Xi和Xi+1的中点作为可能的阈值进行检验,
如TopDistance, 通过进行信息增益比率的计算比较后, 发现属性阈值选择为18引起的信息增益最大。
图2给出的决策树是基于上述算法建立的。决策树根据信息增益数值比率的大小从这些特征中选取了10个作为树节点。从图中可以看出MPU中的Result这个词出现的数量是决定MCU的最重要的特征。决策树中的每一个分支对应于一个判断MCU的规则。
4 获取匹配数
在这里, 我们假定经过了第一步的处理, 已经确定了页面中的MCU, 下一步要从中提取出匹配数。通过归纳, 匹配数在MCU中的出现模式也有多种, 如表1所示, 在MCU中OF结构和N结构占了大多数情况, 约为8 2%。
由表中可以看出, N结构中只有一个数字, 由于我们已经假定MCU已经确定, 因此这个惟一的数字就是匹配数, 这种结构不必出现在决策树中。因此, 我们定义如表2属性:
通过类似的C4.5算法, 得出了从MCU中提取匹配数的决策树, 见图3。
在本文中, 我们采用了两棵独立的决策树顺序完成从搜索结果页面中提取匹配数的过程。当然这两棵树是可以合并成一棵树的, 下面我们从算法的时间复杂度和空间复杂度进行分析:
设树1的时间复杂度是O (N1) , 树2时间复杂度是O (N2) , 因此, 采用两棵独立树时, 最终整个系统的时间复杂度是O1 (N) =O (N1) +O (N2) 。而如果将它合并为一棵树, 则这棵树的时间复杂度O2 (N) =O (N1+5N2) (图2的决策树1中有5个正例) , 显然O1 (N)
5 实验与结果评价
5.1 数据集
通过向各种不同的搜索引擎提供查询获得了70个结果页面作为训练集, 用于产生决策树。在另选取的70个页面的测试集中, 利用决策树算法1, 产生了77个MCU, 利用算法2在这77个MCU中找对了76个匹配数。而利用手动验证结果为:页面中共有74个包含匹配数的MCU (一个页面可能包含重复的匹配数) 。
5.2 MCU发现算法评价
我们分别对于两个决策树算法进行评价, 再对整个系统进行评价。
对于算法1, 定义:CalMCU为算法中得到的MCB的数量7 7, Number MCU为实际的MCB的数量74, 那么算法1的精确度为
对于算法2, 定义:CalMN为算法中得到的匹配数76, NumberMN为手动获得的实际的区配数74, 那么算法2的精确度为
因此, 在页面中获得匹配数的算法的总精度为P 1*P 2=9 3%。
6 结语
试验结果表明, 本文所提出的匹配数析取方法是有效的。其中主要的任务是选择出有效的特征属性。将整个过程分为两个决策阶段, 识别特征大幅度减少, 降低了算法复杂度, 提高了算法精度。
摘要：匹配数是搜索引擎给出的信息查询结果数据。匹配数可以反映搜索关键字的出现频率和搜索引擎的数据库规模, 也可以集成在应用程序中。不同的搜索引擎中匹配数出现的方式是复杂和不确定的。决策树算法是机器学习中应用最广的归纳推理算法之一, 适用于不确定数的判定。本文提出了一种适用于多种搜索引擎的获取匹配数的方法, 利用两棵顺序决策树来进行匹配数的判定。实验证明准确率较高, 在本实验中达到93%。
关键词：匹配数,机器学习,决策树
参考文献
[1] King-Lup Liu, Clement T.Yu, Weiyi Meng, and Adrian Santoso.Discovering the representative of a search engine.In CIKM, pages577-579, 2001.
[2] Ian H.Witten and Eibe Frank.Data Mining:Practical machine learning tools and techniques (2nd edition) .Morgan Kaufmann, San Francisco, 2005.
[3] 刘奕群, 张敏, 马少平.基于改进决策树算法的网络关键资源页面判定[J].软件学报, 2005, 16 (11) 1:958-1966.
[4] Hongkun Zhao, Weiyi Meng, Zonghuan Wu, Vijay Raghavan, and Clement T.Yu.Fully automatic wrapper genera-tion for search engines.In WWW, pages2005:66-75.
[5] Bing Liu, Robert L.Grossman, and Yanhong Zhai.Mining web pages for data records.IEEE Intelligent Systems, 2004, 19 (6) :49-55.
