无为

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

 

1 自动分类的种类和作用

1.1 自动分类的种类

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

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

1.2 自动分类的作用

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

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

2 自动分类的实现方法

2.1 自动归类的实现方法

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

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

其中，W_1k、W_2k分别表示文本D₁和D₂第K个特征项的权值，1<=k<=N。

在自动归类中，我们可以利用类似的方法来计算待归类文档和某类目的相关度。例如文本D₁的特征项为a，b，c，d，权值分别为30，20，20，10，类目C₁的特征项为a，c，d，e，权值分别为40，30，20，10，则D₁的向量表示为D₁(30,20,20,10,0),C₁的向量表示为C₁（40，0，30，20，10），则根据上式计算出来的文本D₁与类目C₁相关度是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]。下面对以上方法做一简要介绍。

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

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

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

 

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

3.1 WWlib 自动归类系统

     WWlib(http://www.scit.wlv.ac.uk/wwlib/) 是伍尔弗汉普顿网络图书馆的简称（Wolverhampton Web Library），它是使用了自动归类技术的网络信息检索系统。它的主要组成部分如下^[14－15]：

（1）蜘蛛：任务是自动从网络上抓取网页。

（2）索引器：它接收蜘蛛抓回来的网页并在本地服务器上储存一个副本，给网页一个唯一的索取号，同时创建一个新的元数据模板，将本地的副本分配给分析器，建造和增加分类器的元数据模板。

（3）分析器：对嵌入网页中的超链接进行分析。如果发现是有效的超链接，就将它的网址传递给索引器并检查它是否属于英国。

（4）分类器：在对索引网页进行分析的同时给出杜威十进分类法分类号。

（5）构建器：分析索引器提供的网页及其元数据，建立索引数据库，确定索引号和关键词之间的对应关系，使得使用索引号就可以迅速获得相应的关键词。

（6）搜索器：接受用户的检索提问，在构建器的索引数据库中进行查询，用得出的索取号获得相应的元数据和本地副本，使用以上的信息得到一个详细的结果，并按相关度排列检索结果。

WWlib 中分类器对网页的处理方法如下：首先，对网页进行自动标引，对网页中的语词根据它们的词频和网页中出现的位置赋予权重。然后将处理后得到的语词集合与杜威十进分类法分类表中的每一个款目进行比较。每个款目包括它们的分类号、一长串关键词和它们的同义词。从一级类目开始比较，直到出现比较显著的匹配值为止，此时将该网页归入此类。匹配值是在综合考虑到语词的相似度以及文档的长短等因素之后给出的。

WWlib 提供的检索途径有关键词检索、分类号检索、浏览类目下收录的网页等。WWlib也支持布尔逻辑检索和截词检索。检索结果分为两行，第一行为分类号、网页标题，第二行是网页内容摘要。WWlib主要的问题是数据库规模太小，笔者在2003年4月18日查看时其款目只有 4874 个。但是它的方法对于今后大规模网页的自动分类仍然有一定的借鉴意义。

3.2 Grouper 自动聚类系统

Grouper 是Oren Zamir和Oren Etzioni 研制的一个自动聚类系统，它的主要作用是对Huskysearch(这个是他们开发的一个元搜索引擎)返回的结果进行自动聚类。他们在Grouper: A dynamic clustering interface to web search results^[16]一文中详细描述了它的原理和功能，很遗憾的是随着Oren Zamir和Oren Etzioni的毕业离校，这两个系统也停止了对外服务，但是Grouper还是具有很大的参考价值。

Grouper 采用的是一种叫做后缀树聚类（Suffix Tree Clustering）的算法（下文简称STC）。STC是一种线性时间聚类算法，根据待聚类网页中的相似短语进行聚类。这里所说的短语就是指几个有序的词。此算法可以分为三个步骤。

(1) 网页“清洗”。这一步骤可以看作是网页特征的抽取。它对代表网页特征的字符串进行过滤，标明各句之间的间隔，去掉不是文字的标记符号（如HTML标记、大部分的标点）。

(2) 确定基本聚类串。基本聚类串是一些具有共同短语网页的集合。它是在对网页特征进行抽取的同时使用STC算法进行计算后得到的。对于每一个基本聚类串，根据它包含的网页特征的数量以及组成短语的词的个数赋予一定的权值。但是，在停用词表中出现的词或者过于高频词或者低频词对基本聚类串的权值没有贡献。

(3) 合并基本聚类串为最后的结果。其主要的依据是同一聚类中的网页在语义上的相关性，允许交叉聚类，也就是一篇网页可以在多个聚类中出现。

STC 算法的主要特点有：（1）它是一种模糊聚类方法，允许交叉聚类。（2）使用短语而不是词去判断网页的相似性，同时也考虑这些短语出现的位置和顺序。它用共同短语来揭示聚类的内容，对用户而言这个也是一个有丰富信息量的摘要。（3）速度快，它是对元搜索引擎的结果进行聚类，在元搜索引擎返回结果的同时就开始工作，通常情况下在接收到最后一篇网页之后就可以显示出结果，不会产生明显的迟滞现象。

Grouper 以表格形式来显示聚类结果。每一类用一行表示。首先是该类的大小，用它所包括的网页数量来标识；其次是共同短语，就是在该类中出现的高频词，同时用数字表示出该共同短语在此类中出现的百分比；最后是三个该类实例网页的标题。如果用户对某一类有兴趣，想深入看下去，可以点击“查看结果”这个链接，进入的页面就将该类中所有网页的标题都列出来了，点击网页的标题就可以看到具体的页面。

Grouper 还有一个相关反馈的功能，可以根据某类来对检索策略进行修改，也就是利用该类中的共同词语来重新检索。

3.3 Vivísimo 自动聚类系统

Vivísimo （Http://vivisimo.com）是个元搜索引擎，它调用 AltaVista 、MSN、 Netscape、 Lycos、 Looksmart、 FindWhat等搜索引擎 的结果（用户在它的高级检索中可以选择具体调用那一个或者那一些搜索引擎），对它们进行自动聚类后返回给用户。Vivísimo已经连续两年（2002年和2003年）被搜索引擎观察（Search Engine Watch）的专家评为“最好的元搜索引擎（ Best Meta-Search Engine ）”，英国物理学会出版社（ Institute of Physics Publishing ）也选择了 Vivísimo 来提供检索结果的自动聚类，以加强他们的电子期刊服务工作。^[17]

Vivísimo 基于的原理是一种叫做准确描述所有配对（concise all pairs profiling）（简称为CAPP）的方法。^[18-19]这种方法着眼于形成可描述的聚类。它的基本原理是将所有的类别成对的进行比较，找出能够将每一对类别区分开来的特征，然后对那些特征进行组织，形成最后的描述，保证每一对至少有一个特征能够将它和其他对区别出来。

Vivísimo 自动聚类所依据的是搜索引擎返回的网页的网址、标题和简单描述。而不是整个网页。我们可以通过下图来看Vivísimo的一些特点。

 

从图中我们可以清楚的看到 Vivísimo 采用类似于Windows资源管理器的界面来显示结果，非常直观。Vivísimo用一个词来对该类进行描述，点词语左边的“＋”号就可以展开下级类目（如果“＋”号是灰色的话就表示没有下位类了）。Vivísimo也允许交叉聚类。甚至有类目互为上下位类。 例如 Giant Panda( 图中的第一个类目 ) 的下位类是 Panda Bear ， Panda Cam ， National Zoo ， Bamboo 等，而与图中的第三个类（与第一个类目应该是同一级的就是 Panda Bear ，它的下位类是 Tare and Panda ， Panda Bear′s Playhouse ， Giant Panda 等。

尽管 Vivísimo 现在的性能不是令人很满意，但是毕竟它是少数几个投入商业营运并且取得不错口碑的自动聚类系统。如果不断对自动聚类系统进行改进，提高它的性能，自动聚类系统就可能有广阔的前景。

 

4 自动分类在搜索引擎中应用的策略分析

4.1 自动聚类和自动归类的应用

从上文的论述中，我们可以知道，就目前的情况而言，自动聚类在搜索引擎中的实现要比自动归类容易一些，聚类的效果也比较显著。因此，可以考虑在搜索引擎中首先采用自动聚类。

如果要使用自动归类的话，首先就要考虑使用什么分类法。现在使用的分类法中既有传统的图书馆分类法，也有适应网络环境而生的网络分类法。二者各有千秋，传统的图书馆分类法系统性强，使用范围广，网络分类法比较灵活。如果条件许可的话，最好是两种类型的分类法都使用。对于熟悉图书馆分类法的用户就提供图书馆分类法的结果，对于一般用户则提供自编的网络分类法。在使用分类法的时侯，还要考虑分类的粗细问题，也就是分到几级类目。对于网页的分类，可能没有必要分得很细。下面主要论述自动聚类实现时涉及到的问题。

4.2 应用的时机

应用的时机是指自动聚类是在对网页数据进行索引的时候实施，还是在搜索引擎返回检索结果之后实施。前者可以利用网页的全文，后者一般只是使用网页的网址、标题和摘要等少量信息。一般而言，前者的结果要准确一些，但是综合考虑，后者的精确度虽然不如前者，但是成本比较低，实用性更强。它不需要对网页进行标引等预处理，工作量会大大降低，并且随着技术的发展，结果也会越来越令人满意。对于结果相关性的判断，既有客观因素，也有主观因素。机器只能够模拟人的思维而不能取代人的活动。自动聚类只是帮助用户进行相关性的判断而已，想靠它一劳永逸的解决相关性判断是不太现实的。

4.3 应用的对象

自动聚类可以应用到元搜索引擎或者单个搜索引擎中。单个搜索引擎的覆盖范围有限，且随着网络信息资源的迅速增长而不断下降。所以将自动分类应用于元搜索引擎返回的结果要比应用到单个搜索引擎的效果要明显一些。当然，元搜索引擎的在对调用的搜索引擎进行选择必须要遵循一定的原则，要选取质量比较高的，覆盖面比较广的，力争扩大检全率和检准率。对于单个搜索引擎返回结果，也没有必要全部包括在内，只需要前面的一部分就可以了（例如50条左右）。因为一般情况下，前面的结果与检索要求的相关度要高一些，这样做对于系统的精确性不会有太大程度的影响，但是可以将系统的成本大大降低，实用性更高。

4.4 用户界面

用户界面的设计是一个经常被忽略的问题，实际上用户界面的设计对于自动分类系统的使用效果有很大的影响。一个有关这方面的实验就证明了这一点。这个实验是Hao Chen和Susan Dumais完成的^[20]。他们对七种检索界面的使用效果做了对比。这七种用户界面是：

（1）悬浮显示摘要的清单式界面（List with hover summary）,就是只有当鼠标移到返回的网页的标题时才显示出该网页内容的概要。

（2）内嵌摘要的清单是用户界面（List with summary inline），就是网页的摘要出现在返回网页的标题下面。

（3）显示类名的清单式界面（List with category names），就是在返回网页的标题后面出现其所属的类目名称，同时给出网页的摘要。

（4）悬浮显示摘要的分类界面（Category with hover summary），就是首先给出类目的名称，然后显示出该类目下网页标题，当鼠标移到该标题上的时候显示出该网页的摘要。

（5）内嵌显示摘要的分类界面（Category with summary inline），它与第四种界面基本上一样，除了是将网页的摘要显示在标题下面。

（6）无类名的分类界面（Category with no category names）,它将类目的名称和网页的摘要都去掉了。

（7）无网页标题的界面（Category with no page titles）,只显示出类目供浏览。

Hao Chen 和Susan Dumais的挑选了西雅图地区微软公司的雇员参加这次实验。他们代表着不同年龄、背景、工作和教育水平的人群。每个人的实验都被分为两个部分，每一部分完成15个检索提问。在这两部分中，使用不同的检索界面。在完成检索任务之后，参加者还要填写一份网上调查问卷。整个过程大概需要2个小时。

此次实验的30个检索提问涉及的主题非常广泛，包括运动、电影、旅行、新闻、电脑、汽车和地方事物等等。检索提问难易程度不一，但是在返回的前100个网页中都可以找到答案。有17个问题的答案出现在返回的前20个网页中，有13个问题的答案出现在返回的第21－100个网页中。为了消除其它因素的影响，Hao Chen和Susan Dumais将每一个检索提问所用的检索词固定下来，并且将结果缓存下来，保证同样的检索提问返回一样的结果。他们还检查了返回网页链接的有效性，这样影响检索效果的因素就只有用户界面了。

在实验过程中，检索者的屏幕会出现三个窗口。顶部的窗口是比较小的控制窗口，它显示检索提问、检索词及计时器和“找到它了”、“放弃此题”这两个按钮。左边窗口出现返回的结果（采用不同的用户界面），用户点击左边窗口中的结果时，右边窗口就显示出相应的网页。当参加者找到答案的时候，就点击控制窗口中的“找到它了”，如果没有找到，可以点击“放弃此题”。定时器每五分钟提醒一次用户是继续此次检索还是进行新的检索。

对于用户界面的评价，采用的是将用户的主观感受和客观结果（包括检索所花费的时间和准确度等）相结合的方式。结果发现所有的分类界面都要比清单式的界面效果好。效果最好的是内嵌显示摘要的分类界面。

Hao Chen 和Susan Dumais的实验说明自动分类系统用户界面的设计应该最大限度地帮助用户对返回结果的相关性进行判断。所以，不但要将类名显示出来还应包括类名的说明，使用户能够迅速了解该类的内容，做出相应的判断。类目结构之间的层次也不要过多，太多的话会使得用户在浏览的过程中迷失，感到无所适从。类目之间的排列可以按结果从多到少的顺序排列，同一类目中的网页可以按与该类目之间的紧密程度排列。每个类目中的相关网页给出与检索词内容相关的摘要。

 

 

凡是有该标志的文章，都是该blog博主Caoer（草儿）原创，凡是索引、收藏
、转载请注明来处和原文作者。非常感谢。