一种基于K最近邻思想的快速网络文本分类模型
摘要
关键词
正文
1 引言
在信息时代，社会大众通过网络发表观点，具有突发性、互动性、丰富性等特点，需要利用技术手段进行网络舆情分析，实现舆情主题追踪、敏感话题识别、倾向性分析、舆情预警等。我们利用数据挖掘中的分类算法构建分类器，能够判断待分类文本所属类别，实现舆情主题跟踪的目的。K最近邻算法是用于分类和回归的较简单的机器学习算法，本文提出的基于K最近邻算法的快速网络文本分类方法，先使用预处理的相关技术获取到网页的纯文本内容，主要包括降噪处理和内容抽取，接下来对文本样本进行分词和去停用词处理，然后通过特征选择实现降维。为简化计算快速分类，假定样本文档集中的正例和反例样本数均为N，对于待分类文档d，基于K最近邻的思想计算余弦函数值，得到待分类文档d与正反例样本的相似度，设定相似度阈值r，统计相似度大于r的正反例数目，将待分类文本归为数目较大的类别。
2 模型中使用的技术
2.1 信息预处理技术
通过网络爬虫程序采集到的网络文档，需要使用清除噪音技术处理图片、无关链接、版权信息，广告等噪音，因为这类噪音占据大量的下载资源，浪费带宽，影响信息搜集的速度，并会影响准确识别主题内容，降低数据挖掘算法的分类效果。经过降噪处理后，还需要进行内容抽取。本文研究的网络文档采用HTML文档结构，HTML用各类标记符来标记文本的各个组成部分，如<head>、<body>、<title>、<script>、<style>、<table>、<div>等，当浏览器读取HTML文档时，标记符并不显示，只在浏览器中显示使用标签解释出的各块页面内容。HTML各标记间有种嵌套结构，可以将HTML文档转化成一棵文档对象模型，即DOM树结构。在DOM树中，每个文本、标签、属性都是一个节点，所有节点构成了一个文档树，如下图所示：左侧的html文档可以转化为右侧的DOM树。
遍历DOM树中的节点，对于<meta>、<style>、<script>、<form>等节点因为没有子节点，可以删除，并删除DOM树中的属性节点和属性值，仅保存清洗后的标题和正文纯文本内容，留待下一步处理。
2.2 中文分词和停用词处理
中文文本由中间没有空格分割的字词组成，例如“郑州市第七初级中学开学典礼”，需要对文本进行中文分词以提取特征项，得到结果“郑州市 第七初级中学 开学典礼”。本文中用到的中文分词方法是正向最大匹配算法，其思想是将文本中的内容按正向逐一与分词词典中的词条进行匹配。例如已知句子“郑州市教育局要求”，词最大长度设为5
分词结果：{“郑州市”，“教育局”，“要求”}
有些字词如“我们”“你们”“这里”等，没有实际意义，对文本分类不起作用，无需标识特征，可比较人工整理出的停用词表，从文档中直接删除掉，这就是去停用词。
2.3 特征选择
为便于建模，将文档进行向量化处理，即转换为数值向量格式。例如有文档1：“我来到郑州，郑州如意湖很开心” 文档2：“今天在紫荆山公园玩了一天”。词典集合为 [‘郑州’, ‘公园’, ‘玩’, ‘如意湖’, ‘来到’, ‘紫荆山’, ‘开心’]，则以上文档转换如下：文档1：[2, 0, 0, 1, 1, 0, 1]，文档2：[0, 1, 1, 0, 0, 1, 0]，其中数字代表文档相关词组在词典集合对应位置词组出现的次数，这样就把文档d表示成一个n维空间的向量d(t1,t2,t3......tn)。但文本数据通常特征词数量庞大，需要要对文本中出现的特征词进行选择，降低维度空间。本文中的模型根据特征词的信息增益完成特征选择，为便于计算信息增益，我们对文档集建立特征词词典索引和语料集。语料集记录的字段结构为（termID,textID,num,classification）,其中termID表示特征词索引号，textID表示文档的编号，num表示特征词出现的次数，classification表示文档所示类别。例如语料集中的一条记录为（876,332,4,1）表示的意思是索引号为876的特征词在332号文档中出现了4次，而332号文档为正例类文档。比对建立的特征词词典索引和语料集，也即“中提琴”在正例类里面编号为396的文档中出现了4次。
基于上述统计信息，计算每个特征词的信息增益值，取信息增益最大的前50个特征词构成50维的特征空间，结构如下图所示，从而实现对特征词的选取降维。
2.4 K最近邻分类算法概述
K最近邻(KNN，K-Nearest Neighbor)分类算法的核心思想是计算出一个样本在特征空间中的K个最相邻的样本，获取这K个最近邻样本中大多数样本所属的类别，判定待分类样本也属于该类别。利用K最近邻算法分类文本时，判别待分类文本和训练文本相似程度的标准是采用向量余弦相似度计算方法，假定
，
是n维空间中的两个向量，余弦函数的公式是
(2-1)
其中，
的模为
，
两个向量间余弦相似度量值越大，距离越小，余弦相似度量值越小，距离越大。计算两个文本的相似度时，可以先把文本表示成为n维空间的向量d(t1,t2,t3......tn)，计算两个向量的余弦相似度，值越大就表示两个文本越相似。
4算法基本思想
本文提出的基于K最近邻算法的快速网络文本分类方法，可对网络中新的文章进行分类，判断和事先给定的哪个主题相同，从而实现舆情主题跟踪。框架图如下图：
KnnD ( D，r) // D是训练文本集，含有N个正例文档和N个反例文档, r为设定的相似度阈值
方法：
（1）在D上对训练文本进行分词预处理和去除停用词处理，
（2）在D’中计算每个特征词的信息增益值，取信息增益最大的前300个特征词构成300维的特征空间，并把N个正例文档和N个反例训练文档表示为特征向量，得到文本集D’。
（4） while (有新的待分类文档d) {
对d进行样本分词、去停用词处理，表示为特征向量
，
While(
) {
计算
//按公式(2-1)
If(
){
将文档计入统计数组sum；
}
统计数组中正例和反例的数目，将待分类文本d归为数目较大的类别;
}
}
上文模型中提出的训练文档和待分类文档都可从网络获得，但需要先进性降噪处理和内容提取，以获得网页的纯文本内容。算法中为了快速计算，选取一定量N个正例和反例文档作为样本，N的值不易过大。并把相似度超过阈值r的样本作为分类决策的因素，而相似度低于阈值r的样本可认为与待分类文本差别较大，可不考虑。N和r的选值需要结合具体问题确定，以应用于实践。
参考文献：
【1】肖驰,徐林莉. 松耦合图卷积文本分类网络[J].小型微型计算机系统. 2021(03):449
...