基于改进K-Means的新闻聚类算法研究

摘要

随着各种网络媒体的迅猛发展，获取新闻信息愈发便捷，但是这也造成了数据积累。如何在海量数据发掘潜在信息并有效利用成为现今重点研究领域。聚类分析是数据挖掘重要方法之一，被广泛应用在生物信息、金融、医疗等领域中。本文主要对新闻文本聚类进行研究，提出了基于改进K-Means的新闻聚类算法。　　首先，结合新闻文本的结构特征提出了TI值概念。TI值是基于正文特征词的词频-逆向文本频率(Term Frequency-Inverse Document Frequency，TF-IDF)值，结合了新闻的标题与导语两个重要因素产生的，用于文本特征向量的提取，以便使文本特征向量具有代表性，提高聚类效果。　　其次，针对最大距离算法时间复杂度高，聚类效果不稳定等问题，对其进行了优化，并结合TI值形成TIM_K-Means算法。该算法将TI值用于构造文本特征向量，并且改变了最大距离算法中距离的计算方式，从而降低算法的时间复杂度。此外还在初始中心选择过程中加入了孤立点检测，以便能够在迭代过程中去除孤立点，得到更加合理的初始聚类中心。　　再次，为了应对算法在处理海量数据耗时严重的问题，对算法进行了并行化改造。本文利用 MapReduce 编程模型对 TIM_K-Means 算法进行并行化改造，使其能够在Hadoop平台上运行。　　最后，采用准确率和误差作为衡量指标，利用采集自腾讯新闻网的文本作为数据集进行实验，以验证 TI值和 TIM_K-Means 算法的正确性和有效性。并且利用阿里云服务器搭建 Hadoop 集群，采用加速比和可扩展性作为标准，对 TIM_K-Means算法并行化改造的可行性进行验证。

目录

声明

第1章 绪 论

1.1 课题背景及研究意义

1.2 国内外研究现状

1.2.1 新闻聚类研究现状

1.2.2 K-Means算法研究现状

1.3 主要研究内容

1.4 本文结构

第2章 聚类分析与并行基础

2.1 聚类概述

2.1.1 聚类分析过程

2.1.2 聚类分析度量

2.1.3 评价标准

2.2 K-Means算法简介

2.2.1算法流程

2.2.2算法优缺点

2.3 并行基础

2.3.1 文件系统HDFS

2.3.1 MapReduce模型

2.4 本章小结

第3章 基于改进K-Means的新闻聚类算法

3.1 TI值

3.1.1 文本特征提取

3.1.2 TI值计算

3.2 TIM_K-Means算法

3.2.1 最大距离算法的改进

3.2.2 TIM_K-Means算法流程

3.3 本章小结

第4章 算法并行化

4.1传统K-Means算法并行化

4.2 并行化求取方差

4.3 改进算法的并行化

4.3.1 初始中心选择算法并行化

4.3.2 TIM_K-Means算法并行化

4.4 本章小结

第5章 实验验证与分析

5.1 实验环境

(1) 单机实验环境设置

(2) 分布式环境设置

5.2 TI值验证与分析

5.3 TIM_K-Means算法验证与分析

5.4 算法并行化验证与分析

5.4.1 加速比验证与分析

5.4.2 可扩展性验证与分析

5.5 本章小结

结论

参考文献

攻读硕士学位期间承担的科研任务与主要成果

致谢