自动分类在搜索引擎性能优化中的应用

自动分类在搜索引擎性能优化中的应用

根据中国互联网信息中心2003年1月发布的《中国互联网络发展状况统计报告》，用户经常使用的网络服务中搜索引擎占68.3%，用户得知新网站的主要途径中搜索引擎占84.6[1]%。搜索引擎现在已成为用户利用因特网信息资源所不可缺少的工具。但是搜索引擎现在的性能还不能令人满意，性能亟待优化。本文就将探讨如何利用自动分类来对搜索引擎的性能进行优化。

1 自动分类的种类和作用 1.1自动分类的种类

自动分类就是用计算机系统代替人工对文献等对象进行分类，一般包括自动聚类和自动归类。自动聚类指的是由计算机系统按照被考察对象的内部或者外部特征，按照一定的要求（如类别的数量限制，同类对象的亲近程度等等），将相近、相似或者相同特征的对象聚合在一起的过程。自动归类是指计算机系统按照一定的分类标准或者分类参考，将被考察对象划归到不同类目的过程。

自动聚类和自动归类的主要区别就是自动聚类不需要事先定义好分类体系，而自动归类则需要确定好类别体系，并且要为每个类别提供一批预先分好的对象作为训练文集，分类系统先通过训练文集学习分类知识，在实际分类时，再根据学习到的分类知识为需要分类的文献确定一个或者多个类别。本文中所指的自动分类是指对网页的自动分类，包括网页的自动归类和自动聚类。

1.2自动分类的作用

目前搜索引擎提供两种信息查询方式：分类浏览和关键词检索。分类浏览一般是基于网站分类目录。它浏览的对象是网站，目录分类的质量较高，检索效果好；但是成本高、信息更新慢、维护的工作量大。关键词检索的对象不是网站，而是符合条件的网页。关键词检索信息量大、更新及时、不需要人工干预；但是返回信息过多，质量太低。

目前，很少搜索引擎提供对网页的分类浏览或检索，其原因之一是由人工进行网页的分类几乎是不可能的。如果能够实施网页的自动分分类，就可以实现网页标引和检索的分类主题一体化，搜索引擎就能够兼有分类浏览、检索和关键词检索的优点，同时具备族性检索和特性检索的功能；能够深入到网页层次，帮助用户迅速的判断返回的结果是否符合自己的检索要求。例如在关键词检索中用熊猫作为检索词，返回的结果中作为动物的熊猫、作为一种杀毒软件的熊猫和作为一种电子产品的熊猫等内容是夹杂在一起的，用户要对结果进行分析判断，才能确定那些是自己需要的。如果采用了自动分类技术，就可将不同的内容分到不同的类目中去，从而节省用户的判断时间，提高检索效率。

[2]

2 自动分类的实现方法

2.1 自动归类的实现方法

根据分类知识的获取方法不同，可以将文本自动分类系统分为两种类型：基于知识工程的分类系统和基于统计的分类系统。基于知识工程的方法主要依赖语言学知识，需要编制大量的推理规则作为分类知识，实现相当复杂，而且其开发费用相当昂贵。这方面的系统有卡内基集团为路透社开发的Construe系统。现在应用比较多的是基于统计的自动分类系统，它忽略文本的语言学结构，将文本作为特征项集合来看，利用加权特征项构成向量进行文本表示，利用词频信息对文本特征进行加权。它实现起来比较简单，并且分类准确度也高，能够满足一般应用的要求。向量空间模型是基于统计的分类系统中广泛采用的文本计算模型。向量空间模型可以将给定的文本转换成一个维数很高的向量。向量空间模型最突出的特点是可以方便的计算出两个向量的相似度，即向量所对应的文本的相似性。

在向量空间模型中，文本泛指各种机器可读的记录。用D（Document）表示，特征项（Term，用t表示）是指出现在文档D中且能够代表该文档内容的基本语言单位，主要是由词或者短语构成，文本可以用特征项集表示为D(T1，T2，?，Tn)，其中Tk是特征项，1<=k<=N。例如一篇文档中有a、b、c、d四个特征项，那么这篇文档就可以表示为D(a，b，c，d)。对含有n个特征项的文本而言，通常会给每个特征项赋予一定的权重表示其重要程度。即D＝D(T1，W1；T2，W2；?，Tn，Wn)，简记为D＝D(W1，W2，?，Wn)，我们把它叫做文本D的向量表示。其中Wk是Tk的权重，1<=k<=N。在上面那个例子中，假设a、b、c、d的权重分别为30，20，20，10，那么该文本的向量表示为D(30，20，20，10)。在向量空间模型中，两个文本D1和D2之间的内容相关度Sim(D1，D2)常用向量之间夹角的余弦值表示，公式为：

其中，W1k、W2k分别表示文本D1和D2第K个特征项的权值，1<=k<=N。

在自动归类中，我们可以利用类似的方法来计算待归类文档和某类目的相关度。例如文本D1的特征项为a，b，c，d，权值分别为30，20，20，10，类目C1的特征项为a，c，d，e，权值分别为40，30，20，10，则D1的向量表示为D1(30,20,20,10,0),C1的向量表示为C1（40，0，30，20，10），则根据上式计算出来的文本D1与类目C1相关度是0.86。

网页自动归类一般包括以下步骤： （1）网页特征的抽取和加权

网页特征的抽取是网页自动归类和自动聚类的前提。网页特征的抽取可以从以下几个方面提高网页自动分类系统的性能。首先是分类速度，通过网页特征的选择，可以大大减少特征集合中的特征数，从而提高网页自动归类系统的运行速度，使之能够满足现实需求。二是通过适当的特征选择，不但不会降低系统的准确性，反而会使系统的精度提高。这一点已经为实验所证明。[3]

为了使计算机能够更有效地处理网页特征，必须对网页特征进行特征加权，将网页特征表示成计算机能够处理的数学向量。网页数据是一种半结构化的数据，要比文本复杂的多。在网页

表示中，对任一特征而言，有两个影响它权值的因素。一是该词的词频，另一个是该词在网页中出现的位置，在网页中不同位置出现的语词的价值是不同的。正如张琪玉教授指出：“如果从针对文献整体的检准率的角度看，文献题名中的词最为有效。其次为文献中的小标题或者章节名、文献摘要。最后为文献中的词。”丁璇等人随机抽取了300篇经济类网页，对这些网页进行人工自由标引、人工打分、词频统计，并进行统计数据的分析、研究，得出了网页内容主题与网页题名、文章标题、第一段首句、第一段尾句、第二段首句、第二段尾句、第三段首句、第三段尾句、首段、尾段、HTML标记等12个标引源的主题表达能力的先后顺序。得出的结论是首段>文章标题>HTML标记>第一段首句>网页标题>第一段尾句>第二段首句>第二段尾句>尾段>第三段首句>其它>第三段尾句。并建议它们的加权值为5:5:5:4:4:4:2:2:2:2:2:2。[4]

（2）机器学习

机器学习的方法主要有支撑向量机（Support vector machine）、最近K邻居方法和贝叶斯算法等[5－9]。下面简要介绍支撑向量机和最近K邻居方法。

支撑向量机是建立在计算学习理论的结构风险最小化原则之上，其主要思想针对两类分类问题，在高维空间中寻找一个超平面作为两类的分割，以保证最小的分类错误率。支撑向量机的原理如左图所示，其中的实心点和空心点代表两个类别的训练样本，H为将这两个类别分开的分类线，H1和H2分别是经过这两个类别样本中距分类线最近的点且平行于分类线的直线，H1和H2之间的距离叫做这两个类别的分类间隙。支撑向量机的目标是找到最优分类线，最优分类线不但能将两个类别的样本准确分开，而且要使两类的分类间隙最大。

最近K邻居方法的基本思路是在给定新网页后，考虑在训练网页集中与该网页距离最近（最相似）的K篇文本，根据这K篇网页所属的类别判断新网页所属的类别。它首先根据特征项集合来对训练网页向量重新描述，在新的网页达到首先确定新网页的向量表示，然后在训练网页中选出与新网页最相似的K个网页。也是根据网页的向量之间的距离，具体如下：

其中K值的确定是一个关键的问题。现在的一般做法是先选定一个初始值（几百到几千之间），在进行自动归类的过程中根据结果进行调整。接下来在新网页的K个邻居中，依次计算每一类的权重，计算公式为：

其中， 为网页的特征向量， 为相似度计算公式，而为类别属性函数，如果 属于类，那么函

数值为1，否则为0。最后比较类的权重，将网页分到权重最大的那个类别中去。 2.2 自动聚类的实现方法

网页的自动聚类一般包括四个步骤：

（1）网页表示：包括特征抽取和特征选择。特征选择是选择那些最具有区分性的特征，也就是最能把不同类别区分开来的特征，而不是大多数对象都具有的特征。

（2）相似度计算。主要根据网页表示的距离函数来定义。

（3）聚类：根据网页表示和相似度计算的结果，按照一定的规则将聚类网页分成不同的类。 （4）给出聚类的标识。在最后形成的每一类中抽取一定具有代表性的特征，作为该类的标识。

常用的聚类方法有单遍聚类法、逆中心距聚类法、密度测试法、图聚类法等[10－13]。下面对以上方法做一简要介绍。

单遍聚类法是按照一定的顺序从待分类的网页集合中取出一篇网页，任意赋予它一个新的类别，其标引向量作为该新类的聚类中心向量，此后取出的各篇网页与该类中心向量进行运算得到相似系数，当相似系数大于给定的一个预定值的时候，就将该网页归入此类，同时调整类中心向量。如果相似系数不在给定的预定值范围内，则该网页就另立新类并且创建该类中心向量。要处理的每一篇网页依次与已有的类中心向量进行比较，将其归入相似度最大（且在预定值范围之内）的类中，并且及时调整该类的中心向量。

逆中心聚类法与单遍聚类法比较类似，具体过程如下：任取一篇网页作为第一个聚类中心，计算剩下的网页到该网页的距离，距离最大的作为第二个聚类中心。计算所有非聚类中心的网页到每个聚类中心的距离，将每一篇网页到每个中心距的最小距离求出，选择出最大的最小中心距者作为新的聚类中心。当然，这个还要结合所定义的中心距离制约机制等其它条件。聚类中心确定以后，其余文献就近聚类。

密度测试法的原理是如果某个网页的附近集聚有较多的网页，并且在其周围较广的范围内也分布有一定的网页，那么该网页可作为一个聚类中心。在密度测试中，网页被划分为三种类型：未聚类网页，即还没有被集聚到任何一类中的网页；松散型网页，它们与已经存在的类中心相似度比较小，尚不具备被聚于某类的条件；已被聚类的网页。在聚类开始时，所有的网页都可以看作未聚类网页。用Di表示某篇网页，如果它同时满足以下两个条件，则可以将Di作为类别中心：至少有n1篇网页，它们与Di的相似系数都超过T1；至少有n2篇网页，它们与Di的相似系数都超过T2，其中T1≥T2且n1≤n2。T1、T2、n1、n2都是事先给定的参数。聚类的过程如下：在未聚类网页中任取一篇，把它作为聚类中心并对其进行密度测试，测试范围为尚未聚类和松散型的网页。如果测试失败，即被测试的网页周围不具有指定数量的网页，则该网页被作为松散型网页。然后在未聚类网页中重新选取网页测试聚类中心；如果测试成功，即被测试网页周围集聚一定预定值范围内的相似网页，则该网页被作为一个聚类中心，并将其中相似度超过T1的网页视为已聚类网页，对于相似度小于T1又大于T2的网页，视为松散型网页，其他网页不改变原有类型。聚类过程一直持续下去到没有未聚类网页为止。最后将剩下的松散型网页就近聚集到已存在的类别中。

3 自动分类在搜索引擎中应用的实例