基于结构和链接分析的网页文档分类算法研究*

耿增民， 杜剑侠， 陈 迪， 周毅灵， 邵熙雯

(1. 北京服装学院 数字与交互媒体北京市重点实验室， 北京 100029；2. 北京服装学院 计算机信息中心， 北京 100029)

基于结构和链接分析的网页文档分类算法研究*

耿增民1,2， 杜剑侠2， 陈 迪2， 周毅灵2， 邵熙雯2

(1. 北京服装学院 数字与交互媒体北京市重点实验室， 北京 100029；2. 北京服装学院 计算机信息中心， 北京 100029)

互联网网页数量爆炸性地增长， 使得网页文档分类技术研究成为目前Web挖掘的一大热点. 针对面向某特定领域文档的特点， 提出一种基于层次特征词权重的文档特征表示方法， 以此为基础， 在网页文档分类时， 通过对网页结构和文本链接分析， 设计了网页文档分类算法HFSHA(Text Categorization Algorithm Based on Hierarchy Feature Word Weight and Structure and Hyperlink Analysis). 在服装网页文档语料库上的分类实验表明， 对服装专业文档HFSHA算法比基于向量空间模型(VSM)的普通文本分类算法的分类准确率高.

Web挖掘； 文本分类； 链接分析

0 引 言

文本分类算法对特征的标引方法主要采用向量空间模型(VSM)， 特征权重的计算主要采用TF-IDF公式， 将出现在文本中的每一个非停用词(Stop words)作为特征项， VSM在表示文本的特征维数可能高达上百万[1]. 故基于VSM的分类算法如支持向量机方法(SVM)、 神经网络方法(Nnet)、 最近K邻居方法(KNN)、 贝叶斯方法(Naïve Bayes)在进行分类前要进行降维以消除噪声， 常用的降维方法有互信息(Mutual information)、 文档频率(Document frequency)、 信息增益(Information gain)等[2-3]. 实践中， 有些分类算法对某些专业的文本(如体育、 新闻)效果很好， 分类准确率高达90%以上[4]， 但却对另外一些专业的文本(如计量)效果不理想， 分类准确率不到60%[5]. 其主要原因是因为一些频率低的专业词汇特征容易被当作噪音被删除， 或者即使没有被删除， 由于没有考虑领域专业词汇的强特征特点， 进行计算时可能被赋予较低的权重， 从而较大程度地影响了分类的准确率.

Web的蓬勃发展， 使得网页文档呈爆炸性增长的趋势， 文本分类的研究重点逐步转移到了网页文档. 同普通文本相比， 网页内容包含了结构化(XML)或半结构化(HTML)的数据. 若将一些超本文的标签去除后， 网页文档就可以像普通文本文档一样进行分类了. 但这种简易处理方法无疑会降低文档分类的准确率， 故更多的做法是考虑标签特性， 如文献[6-7]就使用了网页中的标签对关键词进行权重调整， 从而在一定程度上提高了分类的准确性. 但是， 网页文档除了自身的标签特性外， 还有更加重要的链接特性： 整个Web的拓扑结构是一张巨大的“网”， Web页面和页面内的超链接分别对应网中的结点和弧， 与某一领域相关的页面则以不同群聚群体的方式分散在整个网中[8]. 可是目前的分类研究很少考虑文档之间的这些链接特性， 因此， 如何充分利用这些文档间的链接特性， 全局考虑网页文档的类别属性， 从而提高网页文档的分类准确率， 是目前亟待解决的问题[9].

对特定专业领域网页文档的分类， 不仅要考虑算法、 特征表示方法， 而且要考虑领域特征及网页结构和链接特点. 在专业性很强的文本中， 领域词汇有着明显区别于其它词汇的特征， 领域词汇间有着明确的层次(级别)关系， 不同的领域词汇对不同类别的贡献不同； 对超文本文档， 要尽量利用除了文本以外的信息为分类服务. 本文基于上述思想， 并在计量文档分类实验成果的基础上， 对服装网页文档进行了分类研究.

1 层次特征词权重及其向量

通过分析一些行业领域的文档， 可以发现一些特点： ① 与体育、 新闻、 文学等文档不同， 含有大量的专业词汇或字母符号、 表格、 公式等领域特征符号； ② 有大量的数值数据， 有的以表格形式存储； ③ 明显含有分词词典中没有的专业词汇和术语， 并需要进行识别； ④ 领域知识具有一定的层次结构特点， 而且不同层次的专业词汇有不同的级别和权重.

对某些领域文档的分类实验中， 高达上万数目的特征不能达到理想的分类效果[5,10]， SVM、 KNN、 Rocchio是目前表现比较出众的分类算法[11]； NB分类算法则有严密的统计理论支持， 经常被作为基准来进行算法之间的比较[12-13]， 用上述4个算法对服装语料库进行了封闭实验， 但效果不理想. 于是产生了利用领域文档的层次特征， 提取数量少但信息丰富的特征进行文档标示和分类的想法， 就像我们在识别一个人时， 只需要他脸部的一些关键特征即可.

层次化的结构是信息表示、 组织和管理的非常自然的形式， 比如图书馆的图书层次化结构、 专利信息、 个人电脑的层次化的文件系统结构等. 某些专业领域的文档更是层次分明、 严格， 尤其网站在组织网页的时候， 更是特意使用了类别和层次信息， 所以应该充分挖掘这些额外信息为自动分类服务.

1.1 服装语料库的建立

语料库的规模要适中， 各个类别的文本分布要平衡， 采集的网站的要权威和专业. 通过互联网以机器和人工相结合的方式采集了总数为10 000篇， 分为男装、 女装、 运动和休闲等4个类别， 每个类别为2 500篇的服装文本语料库.

1.2 层次特征词库及特征向量的建立

服装专业的分类有3个层次， 不同的层次有不同的特征， 对文本分类的贡献也不同. 在GB/T 15557-2008《服装术语》的基础上建立三级特征词库： 一级特征词库、 二级特征词库、 外围特征词库. 其中外围特征词数量最多， 具有一定的类别特征信息， 但不丰富， 主要包含与该领域相关的信息； 二级特征词含有较丰富的特征词； 一级特征词的类别信息最丰富. 三级特征词与类别的关系及三级特征词之间的关系如图 1 所示.

图 1 类别特征词的组成Fig.1 Composition of category characteristic words

由级别特征词建立相应级别的特征向量， 每一层用一个包括权重在内的特征向量表示， 一篇文本用3层向量表示.

表 1 包含了服装各个类别的一、 二级特征词的数目.

表 1 各类别一、 二级特征词数目

1.3 文本相似度计算公式

图 2 各种特征选择在SVM算法中的分类表现Fig.2 Effect of various feature selections in SVM algorithm

一个服装文档可以形式化表示为：T={D1,D2,D3,D4,DN}.

对于服装语料库中某个类别的文档， 假设其文档数目为n， 定义其类别中心文档向量为所有向量的算术平均， 即

定义文档T和类别中心向量TCi的相似度计算公式为

式中：λ1,λ2,λ3分别为一级特征词、 二级特征词和外围特征词的权重， 具体值由机器训练产生.

对服装语料库的文档若不考虑链接特性进行分类实验， 其算法称之为基于层次特征词权重的文本分类算法(Text Categorization Algorithm Based on Hierarchy Feature Word Weight， HFWW)， 算法描述如下：

Step1： 对语料库中已标注好类别的每类文档， 根据式(1)分别计算出类别中心向量TC1～TC4；

Step2： 对每一待分类文档， 初始化其向量T；

Step3： 对T进行一、 二级特征词识别， 将识别结果填充进T中的D1,D2,D3,D4项， 若某一特征词有同义词存在， 就将同义词表中的第一项填入；

Step4： 对T的外围特征词进行分词处理， 以MI为特征选择测度， 选取8 000个外围词特征， 填充进T的DN项， 至此， 得到文档向量T；

Step5： 按照式(2)分别计算T和4个类别的中心向量的相似度；

Step6： 将T归入具有最大Sim(T,TCi)值的中心类别向量所在的类.

算法的时间主要消耗在分词和特征词提取的处理上， 算法复杂度可以近似表示为O(n*m)(其中n为文档长度，m为包括特征词在内的词典长度). 得到文档的向量表示后， 只需与类别中心向量进行4次比较便可确定文档的所属类别. HFWW和其它算法的实验比较数据如表 2 所示， 实验结果显示， HFWW大幅度地提高了服装文档的分类准确率和召回率， 其中评价指标为宏平均精度(MacroP)、 宏平均召回率(MacroR)、 宏平均F1(MacroF1).

表 2 HFWW和其它算法的实验比较数据

2 基于网页结构和链接分析的算法改进

HFWW算法没有考虑网页特点， 可以利用HTML文档结构特点， 将具有不同结构特点的文本特征赋予不同的权重， 提高分类的性能； 另外考虑到同类的文档容易聚类在一起， 通过分析一个待分类文档的导入和导出文档类别， 可以帮助确定其所属类别.

设原来处理过的文档的特征向量为F={(fi,wi)|i=1,2,…,n}， 其中wi为特征fi的权重， 现在根据网页的结构信息对wi进行权重调整， 最后进行聚类调整， 根据最终的实验效果， 调整规则如下：

1) 特征字体格式权值调整

2) 特征位置权值调整

若特征项fi出现在网页的〈meta name=“keyword” content=“XXXX…”〉、 〈title〉或〈Meta name=“Description” Content=“XXXX”〉时权重系数γ=0.8； 若出现在分级标题〈Hm〉， 则权重系数设置如下：

每出现一次， 权值调整一次：wi=wi*(1+γ).

3) 链接权重调整

很多网页分类算法对1)和2)的网页结构进行了权重调整[6,14-15]， 但没有考虑链接权重调整. 通过对一些网站的网页链接文本的分析， 发现网页除了核心文本外， 在网页的开头和结尾含有大量的类别信息， 比如， 在文档的结尾处， 有“相关链接”、 “相关文章”、 “相关阅读”等链接文本指向了与当前网页内容极为相似的网页文档； 在文档的开头处， 一般是网站的频道信息， 对明确网页所属的类别有一定的指导意义. 基于此， 进行下述调整：

若fi出现在核心文本之外， 网页开头或结尾处的链接文本(Anchor text)中， 设权重系数β=0.9. 经过链接权重调整后的权值为：wi=wi*(1+β).

4) 聚类调整

由于相同类别的文档容易聚集在一起(除了主题发生漂移的). 分类时， 若某Web文档和中心类别向量的相似度值很低时(通过实验设定一阈值)， 直接将其归到链接指向或被指向的Web文档的所属类别[16-17]. 实际分类实验中， 发现分类错误的文档和中心类别向量的相似度值都偏低， 说明按相似度将其归属到某类别比较勉强. 对相似度值偏低的文档进行类别调节， 有可能将其调到正确的类别. 实验中， 错误归到休闲类别的86篇文档经过调整后， 有18篇归到了运动类， 其中10篇调整正确.

把针对网页文档进行结构和链接分析(Text Categorization Algorithm Based on Hierarchy Feature Word Weight and Structure and Hyperlink Analysis)调整后的算法简称为HFSHA， 前5步同HFWW， 从第6步开始， 描述如下：

Step6： 对T进行HTML权重调整；

Step7： 按照式(2)分别计算T和4个类别的中心向量的相似度；

Step8： 若Sim(T,Ci)小于指定阈值， 转Step9， 否则将T归入具有最大Sim(T,Ci)值的中心类别向量所在的类， 算法结束；

Step9： 若T的指向或被指向文档簇更倾向于属于类别c， 将T归于类别c.

较HFWW， HFWWSHA的时间消耗主要增加了对HTML文档的权重调整， 权重调整主要消耗在扫描文档字符串； 聚类调整消耗时间正比于文档集总数. 故算法复杂度仍然可以近似表示为O(n*m). HFSHA和HFWW算法的比较实验数据如表 3 所示.

表 3 HFWW和HFSHA实验比较数据

3 结 论

通过实验数据表， 可以发现改进后的算法各项评测指标平均提高了数个百分点. 算法性能提高的原因是改进后的算法加强了针对HTML格式文档的特征提取和链接分析， 那些隐藏在HTML文档背后的信息， 如： 一些Meta信息、 链接文本信息、 链接指向文档等都对分类有贡献， 从而提高了改进后算法的效率.

对服装文档语料库的分类实验证实了本文提出的算法优于SVM、 KNN、 NB及Rochhio分类算法， 对专业领域文档有较好的适用性， 可以推广到其它受限领域， 根据不同的领域特点， 将领域文档分成不同的级别， 提取相应级别的特征词， 对HFWW和HFSHA进行改进， 使其适合用户的挖掘对象.

[1] Trejo J V C, Sidorov G, Miranda-Jiménez S, et al. Latent dirichlet allocation complement in the vector space model for multi-label text classification[J]. International Journal of Combinatorial Optimization Problems and Informatics, 2015, 6(1)： 7.

[2] Choi D, Ko B, Kim H, et al. Text analysis for detecting terrorism-related articles on the Web[J]. Journal of Network and Computer Applications, 2014, 38： 16-21.

[3] 张延祥, 潘海侠. 一种基于区分能力的多类不平衡文本分类特征选择方法[J]. 中文信息学报, 2015, 29(4)： 111-119.

Zhang Yanxiang, Pan Haixia. A feature sciection method based on diseriminative ability for multiclass text categorization on imbalanced data[J]. Journal of Chinese Information Processing, 2015, 29(4): 111-119. (in Chinese)

[4] Kenekayoro P, Buckley K, Thelwall M. Automatic classification of academic Web page types[J]. Scientometrics, 2014, 101(2)： 1015-1026.

[5] 周毅灵, 耿增民. 服装网页自动分类技术研究[J]. 北京服装学院学报(自然科学版), 2011, 31(1)： 55-59.

Zhou Yiling, Geng Zengmin. Research on automatic classification of clothing Webpage[J]. Journal of Beijing Institute of Clothing Technology, 2011, 31(1)： 55-59. (in Chinese)

[6] Huang Y, Wang X, Murphey Y L. Text categorization using topic model and ontology networks[C]. Proceedings of the International Conference on Data Mining (DMIN). The Steering Committee of The World Congress in Computer Science, Computer Engineering and Applied Computing, 2014.

[7] 兰均, 施化吉, 李星毅, 等. 基于特征词复合权重的关联网页分类[J]. 计算机科学, 2011, 38(3)： 187-190.

Lan Jun, Shi Huaji, Li Xingyi, et al. Associative Web document classification based on word mixed weight[J]. Computer Science, 2011, 38(3)： 187-190. (in Chinese)

[8] Aggarwal C C, Zhao Y, Yu P S. On text clustering with side information[C]. Data Engineering (ICDE), IEEE 28th International Conference, IEEE, 2012： 894-904.

[9] Aggarwal C C, Zhao Y, Yu P S. On the use of side information for mining text data[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(6)： 1415-1429.

[10] Chakravarthy S, Aery M, Venkatachalam A, et al. InfoSift： a novel, mining-based framework for document classification[J]. International Journal of Next-Generation Computing, 2014, 5(2): 84.

[11] Demidova L, Sokolova Y. Development of the SVM classifier ensemble for the classification accuracy increase[C]. ITM Web of Conferences. EDP Sciences, 2016.

[12] Jiang S, Pang G, Wu M, et al. An improved K-nearest-neighbor algorithm for text categorization[J]. Expert Systems with Applications, 2012, 39(1)： 1503-1509.

[13] Bijalwan V, Kumar V, Kumari P, et al. KNN based machine learning approach for text and document mining[J]. International Journal of Database Theory and Application, 2014, 7(1)： 61-70.

[14] 李保利. 基于类别层次结构的多层文本分类样本扩展策略[J]. 北京大学学报 (自然科学版), 2015, 51(2)： 357-366.

Li Baoli. Expanding training dataset with class hierarchy in hierarchical text categorization[J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2015, 51(2)： 357-366. (in Chinese)

[15] 王继成, 潘金贵, 张福炎.Web文本挖掘技术研究[J]. 计算机研究与发展， 2000, 37(5)： 513-520.

Wang Jicheng, Pan Jingui, Zhang Fuyan. Research on Web text mining[J]. Journal of Computer Research and Development, 2000, 37(5)： 513-520. (in Chinese)

[16] Hernández I, Rivero C R, Ruiz D, et al. CALA： an unsupervised URL-based Web page classification system[J]. Knowledge-Based Systems, 2014, 57： 168-180.

[17] Lee J H, Yeh W C, Chuang M C. Web page classification based on a simplified swarm optimization[J]. Applied Mathematics and Computation, 2015, 270： 13-24.

DocumentClassificationBasedonWebStructureandLinkAnalysis

GENG Zeng-min1,2, DU Jian-xia2, CHEN Di2, ZHOU Yi-ling2, SHAO Xi-wen2

(1. Beijing Lab of Digital and Interactive Media, Beijing Institute of Fashion Technology, Beijing 100029, China； 2. Computer Information Center, Beijing Institute of Fashion Technology, Beijing 100029, China)

The explosive growth of Web pages makes currently the research of Web document classification technology a hotspot of Web mining. Representation method of document characteristics based on hierarchy feature word weight was put forward aiming to document character of special domains. Based on this, the text classification algorithm named HFSHA(hierarchy feature word weight and structure and hyperlink analysis)was designed by considering the Web structure and link relationships. It shows that HFSHA has higher accuracy rate on the text classification than normal classification algorithm based VSM text representation in the experiment on fashion Web documents corpus.

Web mining; text classification; link analysis

1673-3193(2017)03-0354-06

2016-08-12

北京市教育科学“十二五”规划重点课题资助项目(AJA11174)； 教育部人文社科资助项目(12YJA760014)； 2014年度北京服装学院科学研究提升计划培育资助项目

耿增民(1968-)， 男， 博士， 副教授， 主要从事数据挖掘、 图形图像处理的研究.

TP391

A

10.3969/j.issn.1673-3193.2017.03.018