文档介绍：硕士学位论文

基于最大频繁项集 K-means 的文本聚类算法
研究及应用

RESEARCH AND APPLICATION OF TEXT
CLUSTERING METHOD BASED ON MAXIMAL
FREQUENT ITEMSETS K-MEANS

黄玉燕

哈尔滨工业大学
2011 年 12 月
国内图书分类号: 学校代码:10213
国际图书分类号: 密级:公开

工学硕士学位论文

基于最大频繁项集 K-means 的文本聚类算法
研究及应用

硕士研究生: 黄玉燕
导师: 王轩教授
申请学位: 工学硕士
学科: 计算机科学与技术
所在单位: 深圳研究生院
答辩日期: 2011 年 12 月
授予学位单位: 哈尔滨工业大学
Classified Index:
:

Dissertation for the Master Degree in Engineering

RESEARCH AND APPLICATION OF TEXT
CLUSTERING METHOD BASED ON MAIXMAL
FREQUENT ITEMSETS K-MEANS

Candidate: Yuyan Huang
Supervisor: Wang
Academic Degree Applied for: Master of Engineering
Speciality: Computer Science and Technology
Affiliation: School of Mechatronics Engineering
Date of Defence: December, 2011
Degree-Conferring-Institution: Harbin Institute of Technology
哈尔滨工业大学工学硕士学位论文
摘要
随着网络技术的发展,网络信息正在以几何级速度迅速膨胀。如何通过信息
融合进行在线信息的处理,特别是进行数据量巨大的文本信息处理,已成为一个
亟待解决的难题。文本聚类作为一种无监督的信息组织方法,在这一难题中发挥
着重要的作用。文本聚类通过将大量文档划分到几个有意义的分组,使得同一个
分组中的文档拥有更高的相关度,而不同分组间的文档则尽可能不同,从而达到
对文档信息进行有效的组织的目的。本文研究了现有的文本聚类算法,分析并总
结了每个算法的特点。引入关联规则中频繁项集的概念,研究基于频繁项集的聚
类算法。最终提出了一种新型的采用最大频繁项集与 K-means 相结合的二次聚类
算法,改进了算法的聚类效果。
本文通过建立文档数据库模型,进行最大频繁项集的挖掘。将包含相同最长
最大频繁项集的文档聚集在一起,形成初始类簇。接着,提出一种新的基类选择
算法筛选部分初始类簇,作为 K-means 算法的初始聚类中心。考虑到数据分布不
均和类簇大小不一的特点,本文提出了二次聚类的思想:首先,通过最大频繁项
集 K-means 算法进行一次聚类,得到特征明显或规模较大的类簇,保存他们的类
簇中心;然后,将这些类簇中的文档从文档数据库中去除,再次使用基于最大频
繁项集的算法选择剩余文档的聚类中心。最后,结合一次聚类结果中的类簇中心,
对所有未分类的文档进行 K-means 聚类。本文的文本聚类算法的改进和创新点主
要包括以下几个方面:
(1) 使用文档间共享的最长最大频繁项集进行初步聚类,提出最大频繁项集对
类簇的表达能力的概念,设计准则不等式,进行基类的筛选。
(2) 在一次聚类中,通过设置最小相似度阈值,改进了传统的 K-means 算法。
同时结合二次聚类思想,达到尽可能识别所有类簇,减少由于类簇识别不完全而
导致的误分类。
(3) 整个聚类过程回避 K-means 聚类算法需要输入预定义类簇数目的难题,通
过在类簇生成和选择的过程中设置参数的方式,达到自动获得类簇个数的目的。
最后,论文在多个语料集上验证本文提出的聚类算法。通过与同类算法的对
比实验表明,本文的聚类算法在聚类纯度和 F-值两个指标上都有 5%-10%的提高;
同时,实验也表明,本文的聚类算法能够得到与实际情况相近的类簇