张俐李星陆大：网络信息搜索器的自动分类算法

　　张俐李星陆大：网络信息搜索器的自动分类算法

　　张丽​​丽行路达

　　摘要：为了有效地组织互联网上极其丰富的信息资源，通过分析中文和中文网页的特征，提出了一种新的中文网页自动分类算法。该算法主要利用词，词频和页面标记信息之间的相关信息提取网页特征，计算出可调节的词频加权参数，然后通过这种类型和非类型训练来建立专家数据库。实验表明，该算法可以达到80％以上的网页分类准确率。

　　关键词：文本分类；搜索引擎;超文本描述语言（HTML）

　　分类号：TP 391； O 235文件识别码：A

　　文章序列号：1000-0054（200 0) 01-0039-04

　　新的中文首页自动分类算法

　　张丽​​丽行路大金

　　（清华大学电子工程系，北京100084）

　　摘要：当前可以在Internet上访问大量资源，但是没有有效的方法来组织信息。通过分析中文文本和中文主页的特征，提出了一种新的中文主页自动分类方法。该方法将主页中的汉字，术语频率和超文本标记语言（HTML）标签信息相关联，以计算可调整的术语频率加权参数。专家数据库是使用样本集和样本集进行训练的。实验表明，该方法的识别率约为80％。

　　关键字：文本分类；搜索引擎;超文本标记语言（HTML）▲

　　随着Internet在全世界的普及和发展，WWW页面已成为Internet上最重要的信息资源。 WWW网页采用超文本描述语言（HTML）格式，每个网页都可以引用为链接或指向任何其他网页。为了有效地组织和检索Web信息，人们开发了Web信息搜索器。网络信息搜索器使用给定的超链接（URL）作为入口，并根据HTTP协议，与WWW服务器建立连接以获取网页（如图1所示）。

　　图1搜索器

　　为了帮助互联网用户找到有趣的信息，*敏*感*词*研究开发了一些互联网搜索引擎，如国外的Alta Vista，Infoseek，Lycos等，国内的互联网罗盘[1]，网易，天网。但是，当前的中文搜索引擎存在以下问题：1)中文搜索采用基于单词或基于单词的方法。由于中文分词的不确定因素，中文的查全率和准确率均不高。 2)搜索引擎的分类信息资源主要依靠手动维护，这对于信息更新很不方便。因此，研究中文网页的自动分类，一方面可以根据类别建立相应的网页数据库，查询分类数据库，以提高中文的查全率和准确性。另一方面，可以建立自动分类的信息资源。 ，为用户提供分类信息的目录。

　　基于英文文本自动分类算法[2〜5]，结合中文网页的特点，采用非参数在线训练方法，提出了一种新的中文网页分类算法。实验证明，该算法对中文网页的自动分类具有良好的效果。

　　1种英语自动文本分类算法

　　自动文本分类是使用大量带有类标记的文本来训练分类标准或模型参数；然后，使用训练结果来识别未知类别的文本。

　　当前，英语[6]有两种类型的自动文本分类方法：一种是参数方法[7]，另一种是非参数方法[2〜5、8、9]。参数方法是假设文本的概率分布模型，并通过训练获得特定参数的估计值。非参数方法不采用任何概率分布形式，直接通过准则函数进行训练，获得各种权重向量，然后区分要识别的样本。由于分类文本的概率分布模型难以精确定义，因此非参数分类方法得到了广泛的应用。

　　2中文网页自动分类算法

　　中文分类不同于英文。英文分类算法主要将单词用作关键词，并使用空格作为分隔符来提取文章特征。但是中文通常是一串不分隔的字符，并且单词之间没有明显的分隔符，并且比较了单词分割。很难，您不能直接使用英语分类方法。

　　此外，与普通的纯文本文件不同，WWW网页是HTML格式的超文本。页面中有诸如和之类的标签，以及页面的标题和描述。 ，关键词（关键字），超链接（URL）等。它们收录重要的分类信息。

　　提出的中文网页分类算法是一种非参数的在线训练算法。基本思想是基于汉字与其他信息之间的相关性来提取中文网页的关键词。在文章分类中，每个关键词的作用包括正权重和负权重。通过训练，计算每个关键词的正负权重以形成这种类型的专家库。进行识别时，首先从文章中提取关键词，然后从专家数据库中读取相应的正负权重，并使用判别标准进行判断。

　　2. 1训练算法

　　对于中文，汉字之间的相关性收录重要的分类信息。如果将单个单词用作关键词，则无论单词之间的相关性如何，都会丢失文章的某些有用信息，这将影响分类结果。但是，如果您考虑所有前面和后面的词之间的相关性，只需将前面和后面的词定义为关键词，训练量就很大。因此，在训练期间使用中文字典，将文章切成单词，并将出现在字典中的单词视为关键词。这样，它不仅保留了必要的字符间相关信息，而且减少了训练量。

　　假设具有类别标识T = {tl，l = 1,2，... L}的训练样本库T。训练样本库T具有总共N种样本。假设训练样本tl的类别标识为cl，clε{0,1}，其中cl = 1表示样本属于第n个类别，cl = 0表示样本不属于第n个类别

　　训练下面的第n个类别。假设第n个类别的专家库是Pooln，并且在训练开始时Pooln =φ。对于每个训练样本tl∈T，l = 1，2，... L进行以下处理：

　　将字典设置为Dict，削减训练样本tl，并提取出现在字典Dict中的中文单词，形成关键词集合

　　（[1)

　　关键词对于判断tl是否属于第n个类别有两个贡献：属于第n个类别，不属于第n个类别。前者定义为1，后者定义为0。因此，形成了关键词训练集

　　（[2)

　　假设权重1为正权重，负数为负权重，并在关键词的训练集中初始化关键词的权重

　　（[3)

　　归一化关键词的权重，设置为归一化值，然后

　　（4)

　　当不考虑单词频率信息时，标准为

　　（[5)

　　选择参数θc∈（0，1)，计算公式（5)：如果yl>θc，则判断为n型，否则，判断为非n型。

　　由于文章中关键词的出现频率在一定程度上也反映了文章的主题，因此在分割中文单词的过程中，可以计算每个关键词的出现次数。令训练样本t1的关键词 w的词频为。这是中文网页文字部分的单词频率。

　　考虑到网页的特性，它与普通中文文本的不同之处在于，除了纯文本信息外，WWW页面还具有其他描述性信息，例如标题，页面描述，关键词和超链接。描述信息中出现的关键词收录网页的重要信息，对分类的影响更大。因此，从网页中提取这些信息并引入加权词频参数对于自动分类更为重要。

　　假设标题，页面描述，关键词和超链接中的训练样本tl的关键词的词频分别为和。总词频是

　　（[6)

　　其中：a，b，c，d是大于零的可调参数。

　　考虑关键词网页的字频和页面标记，请参见公式（6)，标准公式（5)可以写为

　　（[7)

　　那时，公式（7)与公式（5)；当a = b = c = d = 0时，此时，网页的标记信息被忽略，仅考虑网页文字部分的词频。

　　根据公式（7)，更新关键词的权重。将参数β∈（0，1)设置为衰减系数，并执行这种类型的样本训练（cl = 1)，

　　（[8)

　　设置关键词的总权重，这样，如果仅使用这种类型的样本进行训练，则某些对分类没有意义的关键词（例如“它们”，“什么都没有”等）会变得很高。正权重，即使它很棒。因此，在训练过程中，增加了非分类样本训练以减少关键词的总权重，这对每个类别的贡献更大。

　　使用非这种类型的样本训练时（cl = 0)，

　　（[9)

　　标准化关键词权重，以便更新前后的权重之和不变。令S0和S1为权重更新前后关键词的正负权重之和，即

　　（1 0)

　　（1 1)

　　然后，归一化权重为

　　（1 2)

　　使用此次培训的结果更新专家数据库，即

　　（1 3)

　　2. 2识别算法

　　有一个N型专家库P = {Pooln，n = 1，...，N}，其中Pooln是根据上述训练算法获得的第n型专家库，样本设置为被识别为R = {rm，m = 1，...，M}。

　　识别步骤与训练基本相同，除了不执行（8)公式之后的步骤。对于要识别的每个样本rm，根据（7)公式，计算rm的值ymn到第n个类别，并获得集合Ym = {ymn，n = 1，...，N}。如果ymj = maxYm，则将rm判断为第j个类型。

　　3实验结果与分析

　　定义分类识别率：要识别的样本类型为N，根据2. 2的算法进行分类。对于某种类型的样本，识别率是

　　（1 4)

　　从网络搜索者那里采集的大量中文网页中，总共选择了16,200个样本，包括足球，计算机，医学和杂志。在实验过程中，可调节参数为：β= 0. 5，θc= 0. 5，a = 1，b = 1，c = 1，d = 1。字典：32,826个两个字符的单词，7 195个三个字符的单词，16699个四个字符的单词和2,469个五个以上的字符。

　　3. 1个字符之间的相关性对识别性能的影响

　　不使用单词频率参数（即公式（6)，）），仅使用足球样本进行足球训练，即在训练过程中省略公式（9)），识别结果如表所示。 1。

　　p>

　　从表1中可以看出，对于中文网页，忽略单词之间的相关信息，而将单个单词用作关键词，则识别率很低。考虑到两个字符的相关性，识别率远高于单个字符。如果保留两个字符和三个字符的单词或将词典中的所有单词用作关键词，则识别率更高。因此，在培训过程中，保留必要的词间相关信息对于网页的分类非常重要。

　　表1足球类别识别结果

　　方法p×100

　　Word 6 2. 2

　　两个字符的单词8 8. 8

　　两个到三个字符8 9. 8

　　2至4个字符的单词9 0. 8

　　2至5个字符的单词9 0. 8

　　整个字典9 1. 4

　　3. 2此类和非同类样本的训练对自动分类的影响

　　使用足球和医学样本来训练各自的类别；然后，使用其他类型的样本进行足球和医疗方面的非标准培训。忽略关键词的词频参数（即在公式[6)中）。识别结果如表2所示。

　　表2足球和医学识别的准确性p

　　方法p×100

　　橄榄球医学课

　　仅使用这种训练类型7 9. 0 5 1. 6

　　参加非标准培训8 5. 9 7 0. 0

　　从表2中可以看出，通过添加非这种类型的样本训练，可以在很大程度上提高识别精度。

　　3. 3个词频对算法的影响

　　使用字典提取关键词，使用医学样本训练医学课程，并且不使用非课程训练，即省略（9)。比较添加词频参数和网页的识别结果标题和其他信息，如表3所示。

　　表3医疗识别结果

　　方法p×100

　　不管词项频率参数5 0. 6

　　文字频率5 1. 6

　　词频+标题5 2. 6

　　词频+描述5 2. 6

　　词频+ 关键词 5 1. 8

　　词频+超链接5 2. 2

　　词频+所有描述信息5 3. 6

　　从表3中可以看出，加权调整是通过单词频率和页面描述信息进行的。在训练和识别期间，经常出现在网页文本部分的单词以及标题，描述，关键词和超链接都会增加。单词的权重可以提高识别率。

　　4结论

　　鉴于Internet搜索引擎在信息资源组织方面的不足，提出了一种中文网页自动分类的训练和识别算法。该算法使用字典提取关键词，以保留必要的字符间相关信息，并对单词频率和网页描述信息进行加权。在训练过程中，请使用此类和非类别的样本进行训练。实验表明，该算法可以达到80％以上的识别率。 ■

　　基金项目：国家自然科学基金（6962510 3)）

　　关于作者：张莉（1972-），女（中文），河北，博士*敏*感*词*