面向网页内容的K-means聚类算法的研究

论文摘要

近年来,随着Internet的飞速发展和生活中信息化水平不断提高,数据资源呈爆炸式增长,导致获取目的信息困难,信息的利用率降低,而高维数据日益成为主流,所以在实际的聚类应用中,对高维数据聚类方法的研究有着越来越重要的意义。但高维数据本身独有的一些特点,使得高维数据挖掘变的非常困难,因此必须采用一些特殊的方法进行研究处理。本文研究聚类的对象是网页内容,是一种典型的高维聚类。从聚类的概念及高维数据的特点入手,围绕着高维空间相似性度量、权重表示和降低“噪音”特征属性影响这个三个问题,进行了研究和改进。由于文本数据的高维特征,适用于低维空间的相似度度量方法往往失效,对此本文采用一种适合文本数据高维和稀疏特征的Nsim（）相似度度量方法。实验证明这种相似度度量方法在高维空间中,仍能具有较好的稳定性和分辨性。特征的权重表示形成空间向量模型是具有决定性作用,从而对聚类结果有很大影响。HTML文件的标签信息对于网页的类别归属比一般特征属性具有更重要的作用,据此,本文提出了一种适合网页的改进TF-IDF权重计算方法。K-means方法是一种典型的基于划分的快速聚类算法,传统K-means算法的k个簇中心点的初始选择是随机的,这就往往使得聚类的结果不稳定,聚类效果没有保证。本文对中心点的确定提出改进,通过最大最小规则计算中心点。为了使K-means算法能够降低网页内容中“噪音”属性对聚类结果产生的负面影响,本文在聚类过程中,融入空间模型修正方法,通过使用一种比较全面的特征属性度量方法,进行特征属性重要性的判定,从而修正特征空间,达到“降噪”的目的。试验证明,改进后的算法在处理网页数据时,相比传统K-means算法的稳定性方面有明显优势,在聚类效果上也得到了提高。

论文目录

• 摘要
• Abstract
• 第1章 引言
• 1.1 研究背景和意义
• 1.2 研究现状及发展趋势
• 1.3 本文的工作
• 1.4 本文的组织
• 第2章 相关知识
• 2.0 聚类的思想和流程
• 2.1 文本的表示
• 2.2 特征选择方法
• 2.3 特征权重计算方法
• 2.4 文档相似度计算方法
• 2.5 聚类算法介绍
• 2.5.1 基于层次的聚类算法
• 2.5.2 基于划分的聚类算法
• 2.5.3 基于密度的聚类算法
• 2.5.4 基于模型的聚类算法
• 2.5.5 聚类算法比较
• 2.6 本章小结
• 第3章 网页内容聚类相似度度量和特征权重计算方法的改进
• 3.1 网页内容的特点分析
• 3.2 高维特征对数据挖掘的影响
• 3.3 高维空间的文档相似度计算方法
• k范数特性的探讨'>3.3.1 高维空间中L_k范数特性的探讨
• 3.3.2 高维空间相似度度量函数的重新设计
• 3.3.3 数据度量的规范化处理
• 3.3.4 Nsim（）与其他相似性度量方法的比较分析
• 3.4 基于网页标签的TF-IDF权重计算方法的改进
• 3.4.1 TF-IDF详述
• 3.4.2 适用于网页内容的TF-IDF权重计算方法
• 3.5 本章小结
• 第4章 基于网页内容的K-means聚类算法改进
• 4.1 K-means聚类算法的思想和流程
• 4.2 K-means算法缺点分析
• 4.3 问题的提出和方法的动机
• 4.3.1 问题的提出
• 4.3.2 方法的动机
• 4.4 K-means初始中心选择方法的改进
• 4.4.1 最大最小距离聚类算法
• 4.4.2 基于最大最小原则的K-means初始中心选择
• 4.4.3 初始距离最远的两个聚类中心的计算
• 4.5 空间模型修正
• 4.5.1 几种特征选择方法的比较
• 4.5.2 词频和文档频
• 4.5.3 簇间区分度
• 4.5.4 簇内分散偏差
• 4.5.5 位置重要性的度量
• 4.5.6 综合度量指标和算法描述
• 4.6 面向高维稀疏文本聚类的改进K-means算法的整体描述
• 4.7 本章小结
• 第5章 实验设计与分析
• 5.1 基于人工判定的外部评价方法
• 5.2 实验环境
• 5.2.1 测试平台
• 5.2.2 实验数据
• 5.3 实验设计及结果分析
• 5.3.1 欧式距离和Nsim（）度量比较实验
• 5.3.2 改进后的K-means算法与传统K-means聚类效果的比较
• 5.3.3 修正特征空间时不同特征选择方法的去噪效果比较
• 5.4 本章小结
• 第6章 总结及工作展望
• 6.1 总结
• 6.2 工作展望
• 参考文献
• 致谢