论文部分内容阅读
〔摘 要〕针对信息挖掘中的网页自动分类问题，提出了一种基于向量空间模型和并联BP网络的分类方法。该网络由并行连接的多个子网络组成，每个子网络负责一类模式特征的提取，多个子网并行处理所有模式，将分类结果在总输出层表现出来。以因特网上旅游网页分类为例验证了该方法的有效性。
〔关键词〕数据挖掘；网页分类；神经网络；学习算法
〔中图分类号〕ＴＰ３９１ 〔文献标识码〕Ａ 〔文章编号〕１００８－０８２１（２００９）０５－０１６３－０３
BP Neural Network and Its Application in
Web Document Automatic ClassificationZhu Xiuhua
（School of Further Education，Daqing Petroleum Institute，Daqing 163318，China）
〔Ａｂｓｔｒａｃｔ〕Aiming to web document classification in data mining,a classification method is presented in this paper.The method is based on vector space model and parallel connection BP neural network.The model includes some parallel connecting sub-networks,each of which accounts for extracting a sort of pattern.Total sub-networks synchronously deal with all patterns,and present classification results in last output layer.The availability of model is proved by classification of some web documents in Internet.
〔Ｋｅｙｗｏｒｄｓ〕data mining;web document classification;neural network;learning algorithm
文本分类是文本信息处理的一个重要研究领域，对提高文本检索、文本存储等应用的处理效率有着重要意义。分类的目的是根据若干已知的规则，构造一个分类函数或分类模型（也常称作分类器），把数据库中的数据项映射到给定类别中的某一个。如何提高文本分类器的识别率和推广能力是这些方法面临的共同问题[１]。目前，不少学者已提出了多种统计方法和机器学习方法，例如，Apte用决策树技术来获取分类器；Yang构造了一种近邻算法进行分类；Lewis采用了一个线性分类器；Cohen设计了一种建立在权值更新基础上的休眠专家算法[２]。人工神经网络理论（Artificial Neural Network）是80年代中后期世界范围内迅速发展起来的一个前沿研究领域。该理论作为人工智能的一个重要分支领域，已显示了它活跃的生命力。近几年来，有关人工神经网络理论的新的研究成果不断涌现，目前我国人工智能及其他相关学科领域的专家、学者在人工神经元网络理论和应用研究方面做出了许多可喜的成绩。除了在语言识别、自动控制等领域应用外，已有实践证明，在文档分类、聚类分析等信息挖掘领域也有着相当高的实用价值[３]。基于向量空间模型的文档分类方法，由于文档特征向量维数一般较高（从几十维到上百维），虽然理论上三层反传播神经网络能够逼近任意非线性映射，但普通反传播神经网络对于高维映射问题往往收敛很慢，且容易发生过拟合现象，使泛化能力受到影响。针对这一问题，本文提出并联BP神经网络模型用于解决文档分类问题，该模型由多个子网并联组成，每个子网负责一类模式。子网的输入只与该类模式特征有关，从而大大降低了文档特征向量的维数。该模型既能分散网络负载，也能加速收敛速度。以中国期刊网全文数据库部分文档数据为例进行实验，应用结果表明了该方法的有效性。
１ 文档特征提取
特征提取是文档分类系统中十分关键的问题，文档分类特征选取恰当与否对文档分类的正确性和分类效率有重要影响。一个有效的特征项集，必须具备以下2个特征：(1)完全性，特征项能够体现全部文档内容；(2)可区分性，根据特征项集，能将目标文档同其它文档相区分。特征项集的构造可从构造每篇文档的模糊特征项集开始。如何根据正文的语义提取可近似表示正文语义的特征项集是一个复杂问题，严格讲除了要求理解正文的含义之外，尚需有总结概括的能力乃至有较深的领域知识才能较好地解决这个问题，这是难以用现有计算机技术来实现的。因此最好与语言学家们结合根据人类在抽取正文特征项时所遵循的一般原则进行手工抽取。
１.１ 特征项集的构造
假设有Ｐ篇待分类文档，特征项集的构造可描述如下：
Step 1：首先对Ｐ篇文档，进行手工抽取特征项，并记录特征项的文档频数（特征项在文档中出现的次数），构造特征项集：１，２，…，Ｐ；然后对各特征项集进行筛选，除去频数过低的特征项。即根据给定阈值λ，滤除各篇文档中频数低于λ的特征项，此时可以得到每篇文档的特征项集合：Ｃ１，Ｃ２，…，ＣＰ
Step 2：在以上集合中，将特征项的同义词、转义词、近义词看作同一特征项，计算Ｐ个集合的并集：Ｃ＝Ｃ１∪Ｃ２∪…∪ＣＰ＝｛Ｔ１，Ｔ２，…，ＴＮ｝，得到全部文档的特征项集｛Ｔ１，Ｔ２，…，ＴＮ｝。具体算法：令Ｃ＝Ｃ１，对征向量的构造
以特征项集｛Ｔ１，Ｔ２，…，ＴＮ｝为论域，根据每个特征项在某一文档中出现的频数构造该篇文档的特征向量。另外，构造特征向量时还应考虑特征项的专指度。特征项的专指度可用文档总数与含有该特征项的文档数的比值表示。专指度过低的特征项会抑制分类的精确性。因此对于专指度较高的特征项，应适当增加其文档频数；而对于专指度较低的特征项，则应适当减小其文档频数。具体构造过程可描述如下：
Step 1：分别对Ｐ篇文档，计算特征项集｛Ｔ１，Ｔ２，…，ＴＮ｝中每个特征项在该篇文档中出现的文档频数；
２ 多子网并联BP网络模型
２.１ BP网络模型
传统BP网络由输入层、隐含层、输出层组成。其突出特点是有很强的非线性映射能力和柔性的网络结构。网络的隐层数目及各层神经元数可根据具体情况设定。网络的响应函数通常取Sigmoid函数，信息正向传递，误差反向传播。经多次循环，将输入信息逐渐逼近到期望输出，完成学习功能[４]。网络结构如图１所示。
图１ 三层BP网络模型
设Ｗ为任意多层BP网络的连接权值(包括阈值)，即Ｗ＝（ｗ１，ｗ２，…，ｗｎ），ｇ（ｘ）＝１／（１＋ｅ－ｘ）为非线性传递函数。样本空间为（Ｘ，Ｙ），Ｘ为样本输入，Ｙ为样本输出(期望输出)。误差能量函数定义为：Ｅ＝‖Ｙｘ－Ｙ‖２，其中，‖•‖为某一范数，Ｙｘ为神经网络的实际输出。由于当样本空间确定以后，Ｅ只是权值向量Ｗ的函数，故上式可改写为：Ｅ＝Ｅ（Ｗ）。通常，训练多层神经网络的BP算法标准形式为[５]
２.２ 多子网并联BP网络模型
该模型是传统BP网络模型的一种拓扑变形。这种模型的引入，主要是满足多种辨识模式的精度需要。传统BP网络所有模式使用同一网络，而多子网并联模型每种模式采用一个子网实现。这种网络在模式的表达能力方面有所提高，但增加了网络结构的复杂度。本文采用多子网并联模型的主要目的是为了简化文档特征向量的输入。换言之，每个子网负责一个文档类别的特征获取。这样既分散了网络负载，又提高了网络精度。网络结构如图２所示。
３ 文档分类实施方案
假设有Ｐ篇已知类别的文档，分类实施方案的构造过程可描述如下：
①实施特征抽取，构造特征向量；
假设待分类模式共有ｎ类，每类抽取ｍ个特征项，则模式空间为ｎ维。记ｘｋｉｊ为第ｉ类中第ｊ个特征项第ｋ篇文档中的文档频数，编码后的输入向量如（3）式：
②初始化网络参数：子网数（ｎ个）；子网输入节点（ｍ个）；误差精度ε；学习速度α；惯性系数η；累计学习迭代次数ｓ；最大学习迭代次数Ｍａｘ；
③初始化各子网隐层及输出层权值和阀值（同普通BP网络）；
④计算网络输出和分类误差Ｅ；
⑤若（Ｅ＜ε）或（ｓ＞Ｍａｘ）转⑦；
⑥修正各层权值及阀值，ｓ＝ｓ＋１，转④；
⑦输出结果，训练结束。
上述经过训练的网络即可用于对未知类别文档的分类识别。
４ 实际应用分析
我们以Internet上旅游网页作为分类文档源，参考《中国分类主题词表》中的分类情况，将旅游网页分为如下8个子类别：(1)旅游景点；(2)旅游指南；(3)旅行社；(4)宾馆饭店；(5)租车服务；(6)旅游交通；(7)海外旅游；(8)旅游综合信息。考虑评价与测试文档自动分类算法需要两个重要指标：查全率和查准率，按下面公式计算类别Ｃｉ的查全率ｒｅｃａｌ确分类为Ｃｉ类的文档的数目；Ｃｎ为通过分类算法被分类为Ｃｉ类的文档的数目。
对以上8个子类别通过Google.com网站搜索简体中文网页，构造出规模为1 200个旅游类网页的自动分类样本集，其中800个用作训练集，400个用作测试集。综合考虑全部网页的特征及类属，共提取特征项64个（每类8个）。每类的第一个特征项为类属名称。对全部1 200个网页实施编码处理。部分网页编码结果见表１。
对训练集自身的平均查全率和平均查准率均达到了90%，网络的分类结果如表２所示。
将训练好的网络应用于测试集400个网页的分类，平均查全率和查准率也均达到86%以上，与训练集分类结果较为相近，说明所抽取出的文档类特征和类模式具有普遍性和有效性。关于此方法的有效性，我们与普通BP网络作了对比。采用三层BP网络结构，输入层64个节点，输出层3个节点。当隐层为80节点时，迭代11 038次收敛，对测试集网页的识别率仅为73%；当隐层为100节点时，迭代9 687次收敛，对测试集网页的识别率降为62%。说明普通BP网络对于高维样本的分类问题，不仅收敛速度慢，而且容易产生过拟合现象，影响了网络的泛化推广能力。而应用本文提出的模型就能较好的克服这些问题。
５ 结束语
并联BP神经网络是普通BP网络在空间上的拓展，该模型对多个模式分类问题具有良好的适应性。这种模型通过将高维输入向量分段提交各个子网的方式，简化了网络运算，提高了网络的映射能力及泛化能力。实际上，由于该模型的实质是分散了网络负载，因此该模型不仅对于多模式分类问题有效，对于任何高维映射问题，都是有效的。当全部样本只有一类模式时，该模型等价于普通BP网络模型，因此，普通BP网络可以看作是该模型的特例。本文应用该模型在文档分类问题上作了尝试，有关该模型在其他方面的应用是值得进一步研究的问题。
参考文献
［１］张新红.用神经网络综合评价模型评价高技术项目的投资风险［Ｊ］.情报学报,2001,20(5):608-611.
［２］周雪虹.新信息技术条件下成人高校图书馆员工的素质教育［Ｊ］.图书馆论坛,2003,23(1):49-51.
［３］鲁明羽,李凡.基于权值调整的文本分类改进方法［Ｊ］.清华大学学报：自然科学版,2003，(4):513-515.
［４］王伟.人工神经网络原理——入门与应用［Ｍ］.北京:北京航空航天大学出版,1995：38-43.
［５］Abhijit S.Pandya.神经网络模式识别极其实现［Ｍ］.北京:电子工业出版社,1999：58-69．
〔关键词〕数据挖掘；网页分类；神经网络；学习算法
〔中图分类号〕ＴＰ３９１ 〔文献标识码〕Ａ 〔文章编号〕１００８－０８２１（２００９）０５－０１６３－０３
BP Neural Network and Its Application in
Web Document Automatic ClassificationZhu Xiuhua
（School of Further Education，Daqing Petroleum Institute，Daqing 163318，China）
〔Ａｂｓｔｒａｃｔ〕Aiming to web document classification in data mining,a classification method is presented in this paper.The method is based on vector space model and parallel connection BP neural network.The model includes some parallel connecting sub-networks,each of which accounts for extracting a sort of pattern.Total sub-networks synchronously deal with all patterns,and present classification results in last output layer.The availability of model is proved by classification of some web documents in Internet.
〔Ｋｅｙｗｏｒｄｓ〕data mining;web document classification;neural network;learning algorithm
文本分类是文本信息处理的一个重要研究领域，对提高文本检索、文本存储等应用的处理效率有着重要意义。分类的目的是根据若干已知的规则，构造一个分类函数或分类模型（也常称作分类器），把数据库中的数据项映射到给定类别中的某一个。如何提高文本分类器的识别率和推广能力是这些方法面临的共同问题[１]。目前，不少学者已提出了多种统计方法和机器学习方法，例如，Apte用决策树技术来获取分类器；Yang构造了一种近邻算法进行分类；Lewis采用了一个线性分类器；Cohen设计了一种建立在权值更新基础上的休眠专家算法[２]。人工神经网络理论（Artificial Neural Network）是80年代中后期世界范围内迅速发展起来的一个前沿研究领域。该理论作为人工智能的一个重要分支领域，已显示了它活跃的生命力。近几年来，有关人工神经网络理论的新的研究成果不断涌现，目前我国人工智能及其他相关学科领域的专家、学者在人工神经元网络理论和应用研究方面做出了许多可喜的成绩。除了在语言识别、自动控制等领域应用外，已有实践证明，在文档分类、聚类分析等信息挖掘领域也有着相当高的实用价值[３]。基于向量空间模型的文档分类方法，由于文档特征向量维数一般较高（从几十维到上百维），虽然理论上三层反传播神经网络能够逼近任意非线性映射，但普通反传播神经网络对于高维映射问题往往收敛很慢，且容易发生过拟合现象，使泛化能力受到影响。针对这一问题，本文提出并联BP神经网络模型用于解决文档分类问题，该模型由多个子网并联组成，每个子网负责一类模式。子网的输入只与该类模式特征有关，从而大大降低了文档特征向量的维数。该模型既能分散网络负载，也能加速收敛速度。以中国期刊网全文数据库部分文档数据为例进行实验，应用结果表明了该方法的有效性。
１ 文档特征提取
特征提取是文档分类系统中十分关键的问题，文档分类特征选取恰当与否对文档分类的正确性和分类效率有重要影响。一个有效的特征项集，必须具备以下2个特征：(1)完全性，特征项能够体现全部文档内容；(2)可区分性，根据特征项集，能将目标文档同其它文档相区分。特征项集的构造可从构造每篇文档的模糊特征项集开始。如何根据正文的语义提取可近似表示正文语义的特征项集是一个复杂问题，严格讲除了要求理解正文的含义之外，尚需有总结概括的能力乃至有较深的领域知识才能较好地解决这个问题，这是难以用现有计算机技术来实现的。因此最好与语言学家们结合根据人类在抽取正文特征项时所遵循的一般原则进行手工抽取。
１.１ 特征项集的构造
假设有Ｐ篇待分类文档，特征项集的构造可描述如下：
Step 1：首先对Ｐ篇文档，进行手工抽取特征项，并记录特征项的文档频数（特征项在文档中出现的次数），构造特征项集：１，２，…，Ｐ；然后对各特征项集进行筛选，除去频数过低的特征项。即根据给定阈值λ，滤除各篇文档中频数低于λ的特征项，此时可以得到每篇文档的特征项集合：Ｃ１，Ｃ２，…，ＣＰ
Step 2：在以上集合中，将特征项的同义词、转义词、近义词看作同一特征项，计算Ｐ个集合的并集：Ｃ＝Ｃ１∪Ｃ２∪…∪ＣＰ＝｛Ｔ１，Ｔ２，…，ＴＮ｝，得到全部文档的特征项集｛Ｔ１，Ｔ２，…，ＴＮ｝。具体算法：令Ｃ＝Ｃ１，对征向量的构造
以特征项集｛Ｔ１，Ｔ２，…，ＴＮ｝为论域，根据每个特征项在某一文档中出现的频数构造该篇文档的特征向量。另外，构造特征向量时还应考虑特征项的专指度。特征项的专指度可用文档总数与含有该特征项的文档数的比值表示。专指度过低的特征项会抑制分类的精确性。因此对于专指度较高的特征项，应适当增加其文档频数；而对于专指度较低的特征项，则应适当减小其文档频数。具体构造过程可描述如下：
Step 1：分别对Ｐ篇文档，计算特征项集｛Ｔ１，Ｔ２，…，ＴＮ｝中每个特征项在该篇文档中出现的文档频数；
２ 多子网并联BP网络模型
２.１ BP网络模型
传统BP网络由输入层、隐含层、输出层组成。其突出特点是有很强的非线性映射能力和柔性的网络结构。网络的隐层数目及各层神经元数可根据具体情况设定。网络的响应函数通常取Sigmoid函数，信息正向传递，误差反向传播。经多次循环，将输入信息逐渐逼近到期望输出，完成学习功能[４]。网络结构如图１所示。
图１ 三层BP网络模型
设Ｗ为任意多层BP网络的连接权值(包括阈值)，即Ｗ＝（ｗ１，ｗ２，…，ｗｎ），ｇ（ｘ）＝１／（１＋ｅ－ｘ）为非线性传递函数。样本空间为（Ｘ，Ｙ），Ｘ为样本输入，Ｙ为样本输出(期望输出)。误差能量函数定义为：Ｅ＝‖Ｙｘ－Ｙ‖２，其中，‖•‖为某一范数，Ｙｘ为神经网络的实际输出。由于当样本空间确定以后，Ｅ只是权值向量Ｗ的函数，故上式可改写为：Ｅ＝Ｅ（Ｗ）。通常，训练多层神经网络的BP算法标准形式为[５]
２.２ 多子网并联BP网络模型
该模型是传统BP网络模型的一种拓扑变形。这种模型的引入，主要是满足多种辨识模式的精度需要。传统BP网络所有模式使用同一网络，而多子网并联模型每种模式采用一个子网实现。这种网络在模式的表达能力方面有所提高，但增加了网络结构的复杂度。本文采用多子网并联模型的主要目的是为了简化文档特征向量的输入。换言之，每个子网负责一个文档类别的特征获取。这样既分散了网络负载，又提高了网络精度。网络结构如图２所示。
３ 文档分类实施方案
假设有Ｐ篇已知类别的文档，分类实施方案的构造过程可描述如下：
①实施特征抽取，构造特征向量；
假设待分类模式共有ｎ类，每类抽取ｍ个特征项，则模式空间为ｎ维。记ｘｋｉｊ为第ｉ类中第ｊ个特征项第ｋ篇文档中的文档频数，编码后的输入向量如（3）式：
②初始化网络参数：子网数（ｎ个）；子网输入节点（ｍ个）；误差精度ε；学习速度α；惯性系数η；累计学习迭代次数ｓ；最大学习迭代次数Ｍａｘ；
③初始化各子网隐层及输出层权值和阀值（同普通BP网络）；
④计算网络输出和分类误差Ｅ；
⑤若（Ｅ＜ε）或（ｓ＞Ｍａｘ）转⑦；
⑥修正各层权值及阀值，ｓ＝ｓ＋１，转④；
⑦输出结果，训练结束。
上述经过训练的网络即可用于对未知类别文档的分类识别。
４ 实际应用分析
我们以Internet上旅游网页作为分类文档源，参考《中国分类主题词表》中的分类情况，将旅游网页分为如下8个子类别：(1)旅游景点；(2)旅游指南；(3)旅行社；(4)宾馆饭店；(5)租车服务；(6)旅游交通；(7)海外旅游；(8)旅游综合信息。考虑评价与测试文档自动分类算法需要两个重要指标：查全率和查准率，按下面公式计算类别Ｃｉ的查全率ｒｅｃａｌ确分类为Ｃｉ类的文档的数目；Ｃｎ为通过分类算法被分类为Ｃｉ类的文档的数目。
对以上8个子类别通过Google.com网站搜索简体中文网页，构造出规模为1 200个旅游类网页的自动分类样本集，其中800个用作训练集，400个用作测试集。综合考虑全部网页的特征及类属，共提取特征项64个（每类8个）。每类的第一个特征项为类属名称。对全部1 200个网页实施编码处理。部分网页编码结果见表１。
对训练集自身的平均查全率和平均查准率均达到了90%，网络的分类结果如表２所示。
将训练好的网络应用于测试集400个网页的分类，平均查全率和查准率也均达到86%以上，与训练集分类结果较为相近，说明所抽取出的文档类特征和类模式具有普遍性和有效性。关于此方法的有效性，我们与普通BP网络作了对比。采用三层BP网络结构，输入层64个节点，输出层3个节点。当隐层为80节点时，迭代11 038次收敛，对测试集网页的识别率仅为73%；当隐层为100节点时，迭代9 687次收敛，对测试集网页的识别率降为62%。说明普通BP网络对于高维样本的分类问题，不仅收敛速度慢，而且容易产生过拟合现象，影响了网络的泛化推广能力。而应用本文提出的模型就能较好的克服这些问题。
５ 结束语
并联BP神经网络是普通BP网络在空间上的拓展，该模型对多个模式分类问题具有良好的适应性。这种模型通过将高维输入向量分段提交各个子网的方式，简化了网络运算，提高了网络的映射能力及泛化能力。实际上，由于该模型的实质是分散了网络负载，因此该模型不仅对于多模式分类问题有效，对于任何高维映射问题，都是有效的。当全部样本只有一类模式时，该模型等价于普通BP网络模型，因此，普通BP网络可以看作是该模型的特例。本文应用该模型在文档分类问题上作了尝试，有关该模型在其他方面的应用是值得进一步研究的问题。
参考文献
［１］张新红.用神经网络综合评价模型评价高技术项目的投资风险［Ｊ］.情报学报,2001,20(5):608-611.
［２］周雪虹.新信息技术条件下成人高校图书馆员工的素质教育［Ｊ］.图书馆论坛,2003,23(1):49-51.
［３］鲁明羽,李凡.基于权值调整的文本分类改进方法［Ｊ］.清华大学学报：自然科学版,2003，(4):513-515.
［４］王伟.人工神经网络原理——入门与应用［Ｍ］.北京:北京航空航天大学出版,1995：38-43.
［５］Abhijit S.Pandya.神经网络模式识别极其实现［Ｍ］.北京:电子工业出版社,1999：58-69．