学位论文 > 优秀研究生学位论文题录展示

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

作　者: 时英晋
导　师: 蒋学英
学　校: 东北大学
专　业: 计算机软件与理论
关键词: 高维稀疏相似度度量权重计算 K-means 特征选择最大最小规则
分类号: TP391.1
类　型: 硕士论文
年　份: 2011年
下　载: 0次
引　用: 0次
阅　读: 论文下载

内容摘要

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

全文目录

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

相似论文

基于仿生模式识别的文本分类技术研究,TP391.1
唇读中的特征提取、选择与融合,TP391.41
K-means聚类优化算法的研究,TP311.13
语音情感识别的特征选择与特征产生,TP18
基于遗传算法和粗糙集的聚类算法研究,TP18
基于机器视觉的车辆检测和车距测量方法研究,TP274
基于特征选择的入侵检测研究,TP393.08
基于数据分布特征的文本分类研究,TP391.1
Web使用挖掘与网页个性化服务推荐研究,TP311.13
基于粒子群优化的Fuzzy c-mean聚类算法的基因芯片图像处理,TP391.41
基于词跨度的中文文本关键词提取及在文本分类中的应用,TP391.1
基于标记样本和相似度调整的k均值算法在文本聚类中的应用,TP181
基于纹理特征的图像分类研究,TP391.41
复杂网络社团结构探测研究,O157.5
基于兴趣区域匹配图像检索系统的研究与实现,TP391.41
基于聚类算法的银行卡客户分类分析系统的设计与实现,TP311.52
应用于搜索引擎的人物分类系统设计与实现,TP391.3
面向短消息文本的聚类技术研究与应用,TP391.1
最小最大模块化支持向量机数据划分及其应用研究,TP311.13
车牌识别中车牌定位技术的研究,TP391.41
C电信公司中高端移动用户套餐适配研究,F626