…研究生(大数据技术)报告

研研究究生生 大大数数据据技技术术 报报告告 题题 目 目 第第 2727 组组 基于基于 KNNKNN 文本分类分析文本分类分析 学学 号号 姓姓 名名 专专 业业 计算机技术计算机技术 指指 导导 教教 师师 院 系 所 院 系 所 计算机学院计算机学院 精品文档 1欢迎下载1欢迎下载1欢迎下载1欢迎下载1欢迎下载1欢迎下载1欢迎下载 填填表表注注意意事事项项 一 本表适用于攻读硕士学位研究生选题报告 学术报告 攻读 博士学位研究生文献综述 选题报告 论文中期进展报告 学术报 告等 二 以上各报告内容及要求由相关院 系 所 做具体要求 三 以上各报告均须存入研究生个人学籍档案 四 本表填写要求文句通顺 内容明确 字迹工整 精品文档 2欢迎下载2欢迎下载2欢迎下载2欢迎下载2欢迎下载2欢迎下载2欢迎下载 1 1研究背景研究背景 1 11 1 研究背景以及现实意义研究背景以及现实意义 随着 Internet 的迅速发展 现在处于一个信息爆炸的时代 人们可以 在网络上获取更多的信息 如文本 图片 声音 视频等 尤其是文本最为 常用和重要 因此文本的分类在发现有价值的信息中就显得格外重要 文本 分类技术的产生也就应运而生 与日常生活紧密联系 就有较高的实用价值 1 文本分类的目的是对文本进行合理管理 使得文本能分门别类 方便用 户获取有用的信息 一般可以分为人工 2 和自动分类 人工分类是早期的做 法 这种方式有较好的服务质量和分类精度 但是耗时 耗力 效率低 费 用高 而随着信息量以惊人的速度增长 这种方式就显得很困难 所以需要 一种自动分类的方式来代替人工分类 自动分类节省了人力财力 提高准确 力和速度 1 21 2 国内外研究现状国内外研究现状 国外对于文本分类的研究开展较早 20 世纪 50 年代末 H P Luhn 3 对 文本分类进行了开创性的研究将词频统计思想应用于文本分类 1960 年 Maro 发表了关于自动分类的第一篇论文 随后 K Spark GSalton R M Needham M E Lesk 以及 K S Jones 等学者在这一 领域进行了卓有成效的研究 目前 文本分类已经广泛的应用于电子邮件分 类 电子会议 数字图书馆 搜索引擎 信息检索等方面 4 至今 国外 文本分类技术在以下一些方面取得了不错的研究成果 1 向量空间模型 5 的研究日益成熟 Salton 等人在 60 年代末提出的向 量空间模型在文本分类 自动索引 信息检索等领域得到广泛的应用 已成 为最简便高效的文本表示模型之一 2 特征项的选择进行了较深入的研究对于英法德等语种 文本可以由 单词 单词簇 短语 短语簇或其他特征项进行表示 国内对于文本分类的研究起步比较晚 1981 年 侯汉清教授对于计算 机在文本分类工作中的应用作了探讨 并介绍了国外计算机管理分类表 计 算机分类检索 计算机自动分类 计算机编制分类表等方面的概况 此后 我国陆续研究出一批计算机辅助分类系统和自动分类系统 但是中英文之间 存在较大差异 国内的研究无法直接参照国外的研究成果 所以中文文本分 精品文档 3欢迎下载3欢迎下载3欢迎下载3欢迎下载3欢迎下载3欢迎下载3欢迎下载 类技术还存在这一些问题 1 缺少统一的中文语料库不存在标准的用于文本分类的中文语料库 各个学者分头收集自己的训练文本集 并在此基础上开展研究 因此 系统 的性能可比性不强 同时 由于财力人力有限 中文语料库的规模普遍不大 2 向量空间模型的研究还不十分成熟国内的学者 例如 吴立德和黄 萱菁也提出了如何选择特征项的问题 他们提出可以使用字 词 概念作为 特征项来构成向量空间模型 并对以此为基础的文本分类系统进行了初步的 性能比较 但是 在这方面的研究 6 还没有深入的开展 尤其是对于概念的 定义不清晰 没有全面的比较和测试系统 另外 在特征项抽取算法方面也 缺少深入的研究 3 文本分类算法的研究不十分完整每个分类器通常只实现一种分类算 法 然后进行测试和分析 缺少完整的多种分类算法性能的比较和测试 精品文档 4欢迎下载4欢迎下载4欢迎下载4欢迎下载4欢迎下载4欢迎下载4欢迎下载 2 2解决方案解决方案 2 12 1 KNNKNN 文本分类算法文本分类算法 KNN 7 算法最初由 Cover 和 Hart 于 1968 年提出 8 是一个理论上比较 成熟的方法 该算法的基本思想是 根据传统的向量空间模型 文本内容被 形式化为特征空间中的加权特征向量 即 D D T1 W1 T2 W2 Tn Wn 对于一个测试文本 计算它与训练样本集中每个文本的相似度 找出 K 个最 相似的文本 根据加权距离和判断测试文本所属的类别 具体算法步骤如下 1 对于一个测试文本 根据特征词形成测试文本向量 2 计算该测试文本与训练集中每个文本的文本相似度 计算公式为 式中 di 为测试文本的特征向量 dj 为第 j 类的中心向量 M 为特征向 量的维数 Wk 为向量的第 k 维 3 按照文本相似度 在训练文本集中选出与测试文本最相似的 k 个文 本 4 在测试文本的 k 个近邻中 依次计算每类的权重 计算公式如下 式中 x 为测试文本的特征向量 Sim x di 为相似度计算公式 b 为阈值 有待于优化选择 而 y di Cj 的取值为 1 或 0 如果 di 属于 Cj 则函数值 为 1 否则为 0 5 比较类的权重 将文本分到权重最大的那个类别中 KNN 方法基于 类比学习 是一种非参数的分类技术 在基于统计的模式识别中非常有效 对于未知和非正态分布可以取得较高的分类准确率 具有鲁棒性 概念清晰 等优点 但在文本分类中 KNN 方法也存在不足 如 KNN 算法是懒散的分类 算法 各维权值相同 使得特征向量之间的距离计算不够准确 影响分类精 度 针对这些不足 分别提出了相应的改进算法 下面将详细介绍 精品文档 5欢迎下载5欢迎下载5欢迎下载5欢迎下载5欢迎下载5欢迎下载5欢迎下载 2 22 2 改进的改进的 KNNKNN 文本分类算法文本分类算法 2 2 12 2 1 提高分类效率的改进算法提高分类效率的改进算法 KNN 算法的主要缺点是 当训练样本数量很大时将导致很高的计算开销 KNN 算法是懒散的分类算法 对于分类所需的计算都推迟到分类时才进行 在其分类器中存储有大量的样本向量 在未知类别样本需要分类时 再计算 和所有存储样本的距离 对于高维文本向量或样本集规模较大的情况 其时 间和空间复杂度较高 针对这个缺点 提出了一些改进算法 如基于 FuzzyART 的 K 最近邻分类改进算法 该算法用模糊自适应共振理论 FuzzyART 对 K 最近邻的训练样本集进行浓缩 以改善 K 最近邻的计算速 度 该算法首先用 FuzzyART 将训练样本集中的每一类样本进行聚类 减少 了训练样本集的数据量 提高了算法的计算速度 保持了预测精度 从而使 该算法适用于海量数据集的情况 试验表明 该算法适用于对复杂而数据量 较大的数据库进行分类 提出了一种基于 K 近邻方法的渐进式中文文本分 类技术 利用文本的标题 摘要 关键词 重点段落进行渐进式的分类处理 这样 不用分析全文就能将部分待分类文本成功分类 从而提高了文本分类 的效率 试验结果表明 该方法在保证分类准确率的基础上能够有效地提高 分类效率 对于减少 KNN 计算量的优化而做的研究主要是如何从原始数据集 中选取代表实例集 大部分仅对低维的情况适用 而且在代表实例集每增加 或删除一个代表实例时 都要对样本进行一次测试 工作量大 为此 根据 测试文档在各个样本类中的分布情况提出了基于 KNN 分类的两个有助于减少 大量计算的重要算法 排类算法和归类算法 从而构建了一个基于 KNN 的快 速文档分类方法 理论与实验证明 这种方法可以在不影响原有准确率的条 件下 提高文档的分类速度 2 2 22 2 2 基于模式聚合和特征降维的改进算法基于模式聚合和特征降维的改进算法 在计算相似度时 不考虑特征词间的关联关系 针对这一不足进行的改进 有 主要考虑文档间特征词属性关联与共现对相似度的作用 用一个匹配系数 调整两文档间的距离 它实质上是强化了文本中语义链属性因子的作用 修正 了次要因素的噪声影响 使文本分类结果更加理想 已有的测试结果证明了这 一点 尤其在测试文本与训练文本集中的某些文本直观上较相似时 结果更佳 通过分析特征词对分类贡献的大小 提出了一种应用向量聚合技术的 KNN 文本 分类方法 很好的解决了关联特征词的提取问题 该方法根据每个特征词的 精品文档 6欢迎下载6欢迎下载6欢迎下载6欢迎下载6欢迎下载6欢迎下载6欢迎下载 CHI 分布曲线来确定它们在分类中的贡献 应用向量聚合技术很好地解决了关 联特征词的提取问题 其特点在于 聚合文本向量中相关联的特征词作为特征 项 从而取代传统方法中一个特征词对应向量一维的做法 这样不但缩减了向 量的维数 而且加强了特征项对文本分类的贡献 试验表明 该方法明显提高 了分类的准确率和召回率 2 2 32 2 3 基于特征加权的改进算法基于特征加权的改进算法 KNN 方法是建立在 VSM 模型上的 其样本距离的测度使用欧式距离或余 弦距离 各维权值相同 也就是以为各维对于分类的贡献是相同的 这是不 符合实际情况的 同等的权重使得特征向量之间距离或夹角余弦的计算不够 准确 进而影响分类精度 针对这一不足 提出了基于神经网络和 CHI 的改 进 KNN 方法 应用 SOM 神经网络进行 VSM 模型各维权重的计算 该方法首先 运用 CHI 概率统计方法进行初步特征提取和模式聚合 其特征权重的计算原 理为 如果某一维在各个类别中取值基本相同 那么此维对于文本分类的贡 献率就相对较低 如果在各个类别中取值有较大的差异 那么就具有较强的 文本分类能力 而方差正好是反应变量分布均匀状态的主要指标 该方法有 效地提高了文本分类的精度 提出了利用 SVM 9 来确定特征的权重 即基于 SVM 特征加权算法 FWKNN featureweightedKNN 试验表明 在一定的条 件下 FWKNN 能够极大地提高分类准确率 该方法利用 SVM 可以定量确定样 本的每个特征与分类的相关度 由分类函数的权重向量给出 其中为每个样本对应的 Lagrange 乘子 特征权重确定后 就可以修改 样本之间的距离函数以便更好地反映实际问题 精品文档 7欢迎下载7欢迎下载7欢迎下载7欢迎下载7欢迎下载7欢迎下载7欢迎下载 3 3实验结果及分析实验结果及分析 3 13 1 数据集数据集 实验数据集由中科院计算所提供的中文文本分类语料库 TanCorpV1 0 本语料库收集了 12 类文本 共 14150 篇 该数据集中的文本已通过分词 去除停用词等预处理工作 可为实验节省一定的时间 本次实验在其中抽取 了财经 电脑 教育 科技 体育和娱乐 6 个类 每个类别随机抽取 600 篇 文本 共 3600 篇 计算出平均文本长度后 通过互联网各类论坛搜索出文 本长度约为每个类别平均文本长 1 5 1 2 的测试文本共 600 篇 每类 100 篇 3 23 2 改进的改进的 KNNKNN 实验方案实验方案 在 3600 篇文本中随机抽取每个类中的 400 篇作为训练文本 其余的 1200 篇作为待测文本 反复使用不同 Low 值 观察分类结果 直到找到合 适的值 3 33 3 改进的改进的 KNNKNN 实验结果及分析实验结果及分析 执行 3 2 中方案 其目的在于观测 Low 的取值的对查全率 查准率 F1 值以及分类耗时的影响 从中找到比较合适的 Low 值 其结果如图 3 1 和图 3 2 所示 图 3 1 Low Mid 0 1 的分类结果 精品文档 8欢迎下载8欢迎下载8欢迎下载8欢迎下载8欢迎下载8欢迎下载8欢迎下载 图 3 2 Low Mid 0 1 的分类耗时 可以看出 当 Low Mid 0 6 时 KNN 分类器的查全率 查准率和 F1 值开始趋于稳定 并且其分类耗时是随着 Low Mid 的增大成正比的 精品文档 9欢迎下载9欢迎下载9欢迎下载9欢迎下载9欢迎下载9欢迎下载9欢迎下载 4 4总结与展望总结与展望 本文系统地介绍了 KNN 文本分类算法基本原理 以及针对 KNN 算法的不 足而做的各种改进 对文本分类算法的理论研究和实际应用起了指导作用 目前 KNN 文本分类算法在科技文献分类 网络信息文本分类 中文不良文 本的过滤以及对未知病毒的检测等领域取得了一定的成果 总之 随着互联 网和多媒体技术的发展 要求文本分类技术在文本的处理方法 克服噪声干 扰 分类精度等方面有进一步的提高 如何利用 KNN 算法在这些方面做进一 步的改进依然是一个研究热点 精品文档 10欢迎下载10欢迎下载10欢迎下载10欢迎下载10欢迎下载10欢迎下载10欢迎下载 参 考 文 献 1 袁军鹏 朱东华 李毅 文本挖掘技术研究进展 计算机应用研究 2006 23 2 1 4 2 J W Han M Kamber 数据挖掘 概念与技术 北京 机械工业出版 2007 3 6 3 Luhn H P Auto encoding of documents for information retriveal systems In M Boaz Modem Trends in Documentation 1959 45 58 4 苏金树 张博锋 徐昕 基于机械学习的中文文本分类技术研究进展 软件 学报 2006 17 1848 1859 5 Salton G Wong A Yang C S A Vetor spaee Model for Automatic Indexing In Communications of ACM 1975 18 11 613 620 6 Nigam K Mccallum A Thrun S et al Learning to classify text from labeled and unlabeled documents In Mostow J Madison C R eds Proc Of the 15 th National Conf on Artificial Intelligence Wisconsin 1998 792 799 7 Yiming Yang An evaluation of statistical approaches to text categorization In Information Retrieval 1999 1 1 69 90 8 Cover T M Hart P E Nearest neighbor pattern Classification In IEEE Transon Information Theory 1967 13 1 21 27 9 Park SB Zhang BT Co Trained support vector machines for large scale unstructured docmuent classificaiton using unlabled data and syntactie information In Information processing and Management 2004 4 03 421 439 精品文档 11欢迎下载11欢迎下载11欢迎下载11欢迎下载11欢迎下载11欢迎下载11欢迎下载 精品文档 12欢迎下载12欢迎下载12欢迎下载12欢迎下载12欢迎下载12欢迎下载12欢迎下载 研究生签字研究生签字 指导教师签字指导教师签字 院院 系 所系 所 领导签字领导签字 年年 月月 日日 倚窗远眺 目光目光尽处必有一座山 那影影绰绰的黛绿色的影 是春天的 颜色 周遭流岚升腾 没露出那真实的面孔 面对那流转的薄雾 我会幻想 那里 有一个世外桃源 在天阶夜色凉如水的夏夜 我会静静地 静静地 等待一场流星 雨的来临 许下一个愿望 不乞求去实现 至少 曾经 有那么一刻 我那还未枯萎的 青春的 诗意的心 在我最美的年华里 同星空做了一次灵魂的交流 秋日里 阳光并不刺眼 天空是一碧如洗的蓝 点缀着飘逸的流云 偶尔 一 片飞舞的落叶 会飘到我的窗前 斑驳的印迹里 携刻着深秋的颜色 在一个落