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

数据流上的分类算法的研究

作　者: 王鹏
导　师: 施伯乐
学　校: 复旦大学
专　业: 计算机软件与理论
关键词: 数据挖掘数据流分类频繁模式关联规则负载均衡
分类号: TP301.6
类　型: 博士论文
年　份: 2007年
下　载: 833次
引　用: 12次
阅　读: 论文下载

内容摘要

我们现在已经生活在一个网络化的时代，通信、计算机和网络技术正改变着整个人类和社会。这些技术使得人们可以接触到大量数据。大量数据在给人们带来方便的同时也带来了另一个问题：“如何才能不被数据淹没，而是从中及时发现有用的信息?”。数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。经历了多年的研究，数据挖掘已发展成为一个庞大的学科，主要包含分类、关联规则、聚类等。最近几年出现了大量新类型的应用，传统的数据库管理系统无法很好的处理这些应用。这些应用的典型特点是数据以序列的形式出现，比如传感器数据、互联网数据、金融数据(股票价格等)、在线拍卖以及事务日志(网站访问日志、电话记录日志)等。这种数据形式称为数据流。由于数据流的特殊性：短时间内有大量数据连续到达，这些数据具有随时间动态变化的趋势，怎样对这些流数据使用有限存储空间进行快速处理以获取有用信息，为数据挖掘及其应用研究带来了新的机遇和挑战。数据流上的分类问题具有广泛的应用背景，包括：信用卡欺诈消费行为的监测、传感器网络数据中的异常监测、网络日志分析等。数据流的数据无限、概念漂移等特点使得数据流上的分类模型不同于传统的分类模型，需要能够快速的处理流入的数据，并且及时对模型进行调整已反映新的分类信息。本文中，对数据流上的分类问题从两方面进行了研究。一方面，针对数据快速流入，并且存在概念漂移的数据流提出了基于频繁模式和关联规则的分类算法。另一方面，研究了对多个数据流的数据进行分类时的负载均衡问题。本文主要贡献包括：●提出了基于频繁模式的数据流分类算法，利用频繁模式概括数据流中的类信息，通过动态的添加删除频繁模式、以及改变频繁模式的支持度和置信度表示概念漂移。使用衰减因子来保持频繁模式的时效性。基于频繁模式的数据流分类算法提高了现有算法的准确性。●从效率出发，提出了基于规则的数据流分类算法。使用高效的数据结构压缩训练集和规则集，并且使用基于错误分类记录集学习新规则的方法，从而提高了数据流分类算法的效率。●对基于规则的算法进一步进行了扩展，提出了两种扩展算法，用来解决类分布不均衡时的数据流分类问题。●对多数据流进行分类时的负载均衡问题进行了研究。针对带宽有限、服务器无法接收所有数据流产生的待分类数据的情况，提出了一种有效的负载均衡算法。算法使用保持分类信息的数据变换方法将分类信息进行压缩，然后使用多步数据获取机制从不同数据流获取数据。并且，使用布尔向量和负信息等技术结合真实数据和变化信息，进一步对需要传输的数据进行了压缩。

全文目录

摘要  3-5
Abstract  5-10
1. 前言  10-15
  1.1 引言  10-12
  1.2 分类  12
  1.3 频繁模式与关联规则  12-13
  1.4 本文结构及主要贡献  13-15
2. 数据流  15-20
  2.1 什么是数据流  15-16
  2.2 数据流上的应用  16-18
    2.2.1 传感器网络  16
    2.2.2 网络流量分析  16-17
    2.2.3 金融数据监控  17
    2.2.4 事务日志分析  17
    2.2.5 需求分析  17-18
  2.3 数据流上的数据挖掘  18-20
3. 数据流上的分类  20-23
  3.1 问题描述  20-21
  3.2 现有的数据流上的分类算法  21-23
4. 基于频繁模式的数据流分类算法  23-31
  4.1 预备知识  23-24
  4.2 P-tree  24-27
    4.2.1 P-tree的结构  24-25
    4.2.2 衰减因子  25
    4.2.3 P-tree的维护  25-27
  4.3 分类方法  27
  4.4 性能分析  27-31
5. 基于规则的数据流分类算法  31-52
  5.1 动机  31-32
    5.1.1 CVFDT的更新方式  31-32
    5.1.2 WEC的更新方式  32
    5.1.3 算法目标  32
  5.2 基于规则的数据流分类算法  32-33
    5.2.1 算法思想分析  32-33
    5.2.2 基于规则的分类模型  33
  5.3 检测概念漂移  33-36
  5.4 训练新规则  36-37
  5.5 算法  37-40
    5.5.1 数据结构RS-tree和REC-tree  37-38
    5.5.2 使用REC-tree更新分类器  38-39
    5.5.3 算法  39-40
  5.6 性能分析  40-41
  5.7 实验评估  41-48
    5.7.1 数据集  41-42
    5.7.2 算法中参数的设置  42-43
    5.7.3 模型更新的有效性  43
    5.7.4 N_(ij)和概念漂移的关系  43-44
    5.7.5 生成新规则方法的效果  44-45
    5.7.6 REC-tree和RS-tree  45
    5.7.7 其它数据集上的准确率和效率  45-48
  5.8 类不均衡问题的处理  48-52
    5.8.1 RBC-1  49
    5.8.2 RBC-2  49-50
    5.8.3 实验评估  50-52
6. 多数据流分类的负载均衡问题  52-73
  6.1 问题描述  52-53
  6.2 难点  53
  6.3 相关工作  53-54
  6.4 动机  54-57
    6.4.1 渐进式分类模型  54-56
    6.4.2 数据变换  56-57
    6.4.3 暂时局部性质  57
  6.5 算法总体结构  57-58
  6.6 保持类信息的数据变换  58-60
    6.6.1 主成分分析(PCA)  58-59
    6.6.2 KL-3变换  59
    6.6.3 KL-3变换的性质  59-60
  6.7 数据获取机制  60-65
    6.7.1 算法总体思想  61
    6.7.2 参照向量和布尔向量  61-62
    6.7.3 主动地数据获取机制  62-65
  6.8 渐进式分类器  65-66
  6.9 实验评估  66-73
    6.9.1 保持暂时局部性  67
    6.9.2 KL-3变换对准确性的影响  67-68
    6.9.3 负信息  68-69
    6.9.4 资源分配  69-70
    6.9.5 真实数据集上的准确性  70-71
    6.9.6 真实数据集上带宽分配情况  71-73
7. 总结  73-74
8. 参考文献  74-79
致谢  79-80
攻读博士期间发表论文  80-81

数据流上的分类算法的研究

内容摘要

全文目录

相似论文