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

基于滑动窗口的密度聚类算法研究

作　者: 龚云
导　师: 赵鹏
学　校: 安徽大学
专　业: 计算机软件与理论
关键词: 数据流密度聚类时间衰减滑动窗口
分类号: TP311.13
类　型: 硕士论文
年　份: 2011年
下　载: 48次
引　用: 0次
阅　读: 论文下载

内容摘要

近年来,由于生产生活水平的不断提高和计算机在各行各业的应用技术的高速发展,人们获取数据的能力已经大大的提高,获取数据的渠道也急剧增加。随着信息管理与信息处理系统的应用和发展,现实生活中的许多数据呈现出“流”的特点。处理数据传统方法静态存储结构形式早已不再适用。数据流作为一类重要的数据来源,已受到越来越多的研究人员的关注。基于数据流模型的聚类算法的研究,已成为重要的前沿课题。与传统数据库不同的是,数据流具有很多特点：数据总量呈现无限性、数据快速到达、数据到达速率具有不可控性和不可预测性、数据到达无序性。鉴于数据流的诸多特点,若要对数据流中的数据进行挖掘分析得出可理解、可利用的结果,迫切需要开发出高效、精确的适用于数据流的聚类算法。学术界已经就数据流聚类方面做了大量的研究,提出了许多关于数据流聚类的优秀算法。数据流聚类的主要方法有基于划分、基于层次、基于密度、基于网格和基于模型的方法。基于划分方法的代表算法是k均值和k中心点方法。这类算法通过划分数据点到某个最近的中心点,不断的计算更新簇内距离以达到形成稳定的聚簇的状态。这种聚类方法适合于应用在球形簇的场合,对于中小型规模的数据库很适用。为了发现具有复杂形状的簇和对超大型数据集进行聚类,需要进一步扩展基于划分的方法。基于层次方法主要有自底向上的凝聚法和自顶向下的分裂法。为了节省计算开销,层次方法严格规定一旦聚类过程中的一个步骤完成后就不能撤销。这也是层次聚类的缺陷所在。为了解决基于距离聚类仅限于产生球形簇的结果的问题和过滤孤立点,人们提出了基于密度的聚类方法。只要邻域中的对象或数据点的数目超过某给定的阈值,就继续聚类直到邻域内无符合条件的数据点。基于网格的聚类算法把空间量化成一个多维的网格结构,所有的数据点都投影在这个网格结构中。基于网格聚类的优点是不需要考虑具体的数据点,只需要考虑某个网格中的点的数目或密度,提高了聚类速度。它的缺点是若数据点的维度增多则算法时间复杂度和空间复杂度急剧增大。基于模型的数据流聚类方法为每个簇假定一个模型,并寻找数据对给定模型的最佳拟合。本文综合研究了数据流聚类的问题和经典的数据流聚类算法,做了以下一些工作：(1)借鉴CluStream算法的双层结构的优点,提出了基于滑动窗口的双层数据流密度聚类算法(DStream算法)。(2)提出了基于滑动窗口与时间衰减相结合的改进点(3)实验验证了本文算法的有效性从所用的KDDCUP99数据集实验中可以看出,DStream算法能够在时间和空间代价较小的情况下有效的提高聚类结果的精确度。本文将DStream算法和CluStream算法的实验运行结果分别进行比较。DStream算法得出的聚类结果均优于CluStream算法。本文中衡量聚类结果的精确性指标是比较SSQ值的大小,对依次执行数量不同的样本所花费的时间和运行不同维数的样本所需的时间进行比较。

全文目录

摘要  3-5
Abstract  5-7
目录  7-9
第一章绪论  9-26
  1.1 研究背景及意义  9-15
    1.1.1 数据挖掘综述  9
    1.1.2 数据挖掘的功能  9-13
    1.1.3 数据挖掘系统的分类  13-15
  1.2 数据流的定义和特点  15-17
  1.3 数据流的挖掘技术  17-24
    1.3.1 数据流聚类概述  17-18
    1.3.2 传统的数据聚类的主要方法  18-22
    1.3.3 经典数据流聚类算法  22-24
  1.4 本文主要研究内容  24
  1.5 本文的组织结构  24-26
第二章数据流聚类技术  26-34
  2.1 聚类分析中的数据类型  26-27
  2.2 常用的聚类算法比较  27-28
  2.3 数据流处理方法和数据流系统  28-34
第三章基于时间衰减和合并簇的算法DStream  34-49
  3.1 基于密度划分的方法  34-38
    3.1.1 K均值方法  35-37
    3.1.2 K均值方法的变种  37
    3.1.3 STREAM算法  37-38
  3.2 基于时间衰减机制  38-42
    3.2.1 滑动窗口模型  39-40
    3.2.2 分层聚类合并簇  40-42
  3.3 DStream算法  42-49
    3.3.1 相关定义  42-44
    3.3.2 在线聚类  44-46
    3.3.3 离线聚类  46-49
第四章实验结果和算法性能分析  49-53
  4.1 KDDCUP99测试数据集  49
  4.2 实验结果分析  49-53
第五章总结与展望  53-55
  5.1 工作总结  53
  5.2 未来展望  53-55
参考文献  55-59
附录A 图索引  59
附录B 表索引  59-60
Appendix A Figure Index  60
Appendix B Table Index  60-61
致谢  61-62
读硕士学位期间发表学术论文情况  62

相似论文

二甲醚在Pt低指数晶面吸附的密度泛函研究,O485
基于图的标志SNP位点选择算法研究,Q78
基于超声波的泥浆密度测试机理的研究,TE256.7
电流及电场对结晶器铜板上电镀镍及其合金镀层性能的影响,TQ153.2
基于非规则LDPC码的BICM系统优化设计,TN911.2
LDPC码译码算法的研究,TN911.22
隐式用户兴趣挖掘的研究与实现,TP311.13
图像分割中阴影去除算法的研究,TP391.41
基于图分割的文本提取方法研究,TP391.41
牡丹EST-SSR引物开发及其亲缘关系分析,S685.11
高血压前期证候特征研究,R259
高忠英学术思想与经验总结及运用补肺汤加减治疗呼吸系统常见病用药规律研究,R249.2
K-均值聚类算法的研究与改进,TP311.13
大学生综合素质测评研究,G645.5
大豆品种对腐竹品质的影响及其品质评价体系的初步构建,TS214.2
液芯胶囊制备特性研究及在牛奶连续接种中的应用,TS252.4
密度和种植方式对夏玉米茎秆抗倒伏能力的影响,S513
21个荷花品种遗传多样性的ISSR分析,S682.32
基于聚类分析的P2P流量识别算法的研究,TP393.02
基于混合自适应遗传算法的动态网格调度问题研究,TP393.09
桃杂交后代（F₁）幼苗光合效能评价,S662.1