﻿ 基于谱哈希的大规模网页分类算法 Large Scale Web Page Classification Algorithm Based on Spectral Hashing

Software Engineering and Applications
Vol.05 No.01(2016), Article ID:17003,10 pages
10.12677/SEA.2016.51008

Large Scale Web Page Classification Algorithm Based on Spectral Hashing

Dandan Tian

College of Computer Science, National University of Defense Technology, Changsha Hunan

Received: Feb. 2nd, 2016; accepted: Feb. 22nd, 2016; published: Feb. 25th, 2016

ABSTRACT

Nowadays, network information has been covered in all aspects of our lives, but with the development of the network, the problem of network information overload has become more and more prominent so that it is difficult for us to accurately locate the information we need in the network. The web classification can effectively improve the efficiency of web search and help us accurately locate the desired page. The current classification algorithm can handle a small amount of web pages classified, but the efficiency of large-scale web classification is not ideal. Recently, a distributed web classification is proposed. Although this method can improve the efficiency of web page classification, it does not improve classification algorithm itself. Therefore, this paper proposes a hashes and KNN method based on the design of a classification algorithm applied to large-scale web classification.

Keywords:Web Page Classification, Large Scale, Spectrum Hashing, KNN

1. 引言

2. 相关技术介绍

2.1. 当前网页分类技术及问题分析

2.2. 谱哈希

(1)

(1) 式中Yi表示Y的第i行，r表示哈希编码序列的长度，，W是原始空间中的邻接矩阵，Wij表示原始空间中两样本点Xi与Xj之间的相似度。约束条件中表示每个哈希值取0或1的概率相等，表示不同位上的哈希编码之间不相关。引入对角矩阵D，使得对角元素，则目标函数化为：

(2)

(2) 式中，称为拉普拉斯矩阵。众所周知，这是一个NP难的问题，但若放宽条件，使，则问题变为求拉普拉斯矩阵的较小的r个特征值对应的特征向量(不包括0特征)，通过选取合适的阈值对这些特征向量进行量化即可得到对像哈希码。

2.3. TF-IDF (Term Frequency-Inverse Document Frequency)

TF-IDF [6] 是一种统计方法，用以评估一个词对于一个文件集或一个语料库中的其中一份文件的重要程度。词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。TF-IDF的主要思想是：如果某个词或短语在一篇文章中出现的频率TF高，并且在其他文章中很少出现，则认为此词或者短语具有很好的类别区分能力，适合用来分类。

TF-IDF实际上是：TF * IDF，TF词频(Term Frequency)，TF表示词条在文档中出现的频率。其计算公式如下：

(3)

(3) 式中是t词在文档中的出现次数，而分母则是在文档中所有k个字词的出现次数之和。

IDF逆向文件频率(Inverse Document Frequency)，是一个词语普遍重要性的度量。某一特定词语的IDF，可以由总文件数目除以包含该词语之文件的数目，再将得到的商取对数得到，其公式如下：

(4)

(4) 式中表示语料库中的文档总数。表示包含t词的文档数。

(5)

2.4. KNN (K-Nearest Neighbor)最近邻规则分类

KNN (K-Nearest Neighbor, KNN)最近邻分类算法[7] ，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本dx在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则dx也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。具体的算法步骤如下：

(6)

(7)

3. 算法详细描述

Step1：从N个已分类的网页中，随机抽取X个网页作为训练集，将剩余的网页作为测试集。

Step2：对原始网页解析，去除网页中的噪音数据，抽取网页文本信息。

Step3：对网页的文本信息进行预处理，(预处理主要包括分词和词性标注、除去形容词、副词、介词、连词及感叹词等停用词)抽取特征词，生成特征词集，使用TF-IDF作为我们的特征词选择方法，特征选择流程的流程图如图1所示。(本文取文档中综合权值较高的前5个词加入特征集，即n = 5)。

Step4：以特征向量的形式表示网页[8] 。

Step5：利用谱哈希算法对特征向量进行降维，生成紧凑哈希码。

Step6：利用KNN算法对待分类网页进行分类，降维后我们使用汉明距离来度量两个散列的相似度[9] 。汉明距离公式列出如下：

(8)

hx和hy表示哈希码，代表i位的距离，当，否则

4. 算法测试

4.1. 数据集

Figure 1. Feature extraction process

Table 1. Detail of dataset

4.2. 实验结果

(9)

(10)

(11)

4.2.1. 实验1 (k值对KNN分类算法的影响)

4.2.2. 实验2 (训练集规模对算法的影响)

Figure 2. Classification result on choice of k value (1 ≤ K ≤ 9000)

Figure 3. Classification result on choice of k value (1 ≤ K ≤ 50)

Figure 4. Macro precision on different training set

Figure 5. Macro recall on different training set

Figure 6. MacroF1 value on different training set

Figure 7. Time cost on different training set

Figure 8. Comparison of MacroF1 value

Figure 9. Comparison of time cost

Figure 10. Storage cost of 10,000 pages

5. 结束语

Large Scale Web Page Classification Algorithm Based on Spectral Hashing[J]. 软件工程与应用, 2016, 05(01): 65-74. http://dx.doi.org/10.12677/SEA.2016.51008

1. 1. 贺海军, 王建芬, 周青, 等. 基于决策支持向量机的中文网页分类器[J]. 计算机工程, 2003, 29(2): 47-48.

2. 2. 李晋松. 基于朴素贝叶斯的网页自动分类技术研究[D]: [硕士学位论文]. 北京: 北京化工大学, 2008.

3. 3. 史国强. 基于RBF神经网络的网页分类技术研究[D]: [硕士学位论文]. 北京: 中国石油大学, 2011.

4. 4. Weiss, Y., Torralba, A. and Fer-gus, R. (2008) Spectral Hashing. Neural Information Processing Systems, 282, 1753- 1760.

5. 5. Charon, I., Cohen, G., et al. (2010) New Identifying Codes in the Binary Hamming Space. European Journal of Combinatorics, 31, 491-501. http://dx.doi.org/10.1016/j.ejc.2009.03.032

6. 6. 张瑾. 基于改进TF-IDF算法的情报关键词提取方法[J]. 情报杂志, 2014(4): 153-155.

7. 7. Song, Y., Huang, J., Zhou, D., et al. (2007) IKNN: Informative K-Nearest Neighbor Pattern Classification. Knowledge Discovery in Databases: PKDD. Springer Berlin Heidelberg, 248-264.

8. 8. 许阳, 刘功申, 孟魁. 基于句中词语间关系的文本向量化算法[J]. 信息安全与通信保密, 2014(4): 84-88.

9. 9. 李峰, 李芳. 中文词语语义相似度计算——基于《知网》2000 [J]. 中文信息学报, 2007, 21(3): 99-105.