分布式环境下聚类分析新方法的研究

论文摘要

随着计算机和存储技术的快速发展，人们已经积累了大量的历史数据，迫切需要将这些历史数据转化为知识。聚类分析，基于“物以类聚”的朴素思想，将物理或抽象对象集合划分为由相似对象组成的多个类，在数据挖掘领域得到了广泛的研究，并成功应用于各个领域。近年来，数据库规模持续增长，分布范围日益广泛，而大多数现有聚类分析方法需要一次性将所有数据载入内存，耗费大量计算时间，无法满足海量、分布式数据环境下的知识提取需要，因此分布式环境下聚类分析方法的研究是当今聚类分析领域富有挑战性的前沿课题。本论文致力于这一研究课题，以大规模、分布存储的数据集为研究对象，采用机器学习、人工智能和层次优化等技术和分布式计算相结合的方法，探索分布式环境下新的聚类技术，为高效、合理利用分布的、大规模数据提供理论和技术基础。本文的主要研究内容和创新点包括以下几个方面：1．对分布式环境下的聚类分析，从产生背景、算法研究、应用研究等方面进行了较为全面系统的分析和总结。2．针对分布式聚类的易实现性问题，利用弱聚类算法的易实现性，提出了一种基于Boosting技术的分布式聚类算法DBCA。DBCA算法在每次迭代中，将不同子数据库基于弱聚类算法建立的局部模型组装生成全局模型，各子数据库基于全局模型对其数据进行划分，再根据划分的质量确定下一次迭代的采样概率，通过加权投票集成前些次迭代的划分，并将最后一次集成得到的划分作为最后的聚类结果。分析表明DBCA算法具有可并行计算、良好的伸缩性和通讯代价小等特点，不仅有助于科学家对聚类分析的深入研究。还有助于普通工程技术人员利用分布式聚类技术来解决真实世界中的问题。实验表明DBCA算法可得到与集中数据库相似的结果。3．针对分布式聚类的集成伸缩性问题，根据数据库的网络分布、网络带宽等特点，利用层次设计思想，对OIKI DDM模型进行扩展，提出了基于移动代理的层次优化集成挖掘模型—HOIKI DDM模型，并相应提出一种分布式聚类算法HOIKIDC。实验和分析表明，HOIKIDC对于分布式环境具有更好的伸缩性，实现更加灵活，效率更高，并可有效降低通讯代价，特别适合于大规模异构分布式数据聚类问题。4．对分布式聚类的集成有效性问题进行研究。首先提出了集成有效性概念和局部结果不一致性概念，分析了局部结果不一致性的产生原因，提出了协同算法来降低这种不一致性，并相应地提出了一种分布式聚类算法CDCA，通过局部站点之间的信息交互和协同使全局聚类质量得到改善。实验结果表明，CDCA算法使结果集成更为有效。5．针对应用领域中的时间序列存在数据规模大且分布存储的特点，提出了一种分布式模糊短时间序列聚类算法DFSTS来分析这些时间序列的形状相似性从而更好的揭示序列的结构，并分析了该算法的收敛性。仿真结果表明DFSTS算法具有良好的伸缩性，具有与集中数据集同样的聚类质量，计算效率更高。6．以国家863计划项目为背景，以冶金生产过程质量预测与操作优化为研究对象，对分布式聚类技术在冶金工业中的应用进行了研究。首先设计了一个分布式数据挖掘系统原型。针对大规模、分布存储的连续退火生产过程数据，应用本文提出的分布式聚类算法完成了两个挖掘任务：1)带钢断带建模与预报；2)离群检测。实验结果表明，该方法对于连续退火过程数据的分析是有效的，对大规模冶金工业生产过程数据分析具有十分广阔的应用前景。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 研究背景和意义
• 1.2 聚类分析
• 1.2.1 聚类分析的概念及应用
• 1.2.2 聚类分析研究的重要性
• 1.2.3 聚类分析方法综述
• 1.2.4 聚类分析面临的挑战
• 1.3 分布式聚类
• 1.3.1 分布式聚类产生的背景
• 1.3.2 分布式聚类方法综述
• 1.3.3 分布式聚类的应用
• 1.3.4 分布式聚类问题面临的挑战
• 1.4 论文的研究动机和研究内容
• 1.4.1 论文的研究动机
• 1.4.2 论文的研究内容
• 1.5 小结
• 第2章 基于Boosting技术的分布式聚类
• 2.1 问题的提出
• 2.2 采样和集成学习技术介绍
• 2.2.1 采样技术
• 2.2.2 集成学习技术
• 2.3 Boosting聚类
• 2.4 分布式Boosting聚类算法
• 2.4.1 数据样本概率分布更新
• 2.4.2 数据样本采样
• 2.4.3 数据样本的聚类质量评价
• 2.4.4 聚类簇标号一致化
• 2.4.5 算法描述
• 2.4.6 算法复杂度分析
• 2.5 实验与讨论
• 2.5.1 实验数据
• 2.5.2 实验结果
• 2.5.3 讨论
• 2.6 小结
• 第3章 基于移动代理的层次优化聚类
• 3.1 问题的提出
• 3.2 DDM系统
• 3.2.1 多代理系统
• 3.2.2 DDM模型
• 3.2.3 基于移动代理的DDM模型
• 3.3 OIKI DDM模型
• 3.4 HOIKI DDM模型
• 3.4.1 模型原理
• 3.4.2 模型分析
• 3.4.3 代价函数计算
• 3.5 基于HOIKI DDM模型的分布式聚类算法
• 3.5.1 CHC算法
• 3.5.2 基于HOIKI DDM模型的层次聚类算法
• 3.6 实验与讨论
• 3.6.1 实验数据
• 3.6.2 实验结果
• 3.7 小结
• 第4章 基于协同的分布式聚类
• 4.1 引言
• 4.2 问题描述
• 4.3 局部结果不一致性的定义及分析
• 4.3.1 局部结果不一致性的定义
• 4.3.2 局部结果不一致性的分析
• 4.4 局部结果协同算法
• 4.4.1 算法原理
• 4.4.2 算法描述
• 4.4.3 算法收敛性分析
• 4.5 基于协同的分布式聚类算法
• 4.6 实验与讨论
• 4.6.1 实验数据
• 4.6.2 实验结果
• 4.6.3 讨论
• 4.7 小结
• 第5章 分布式环境下的时间序列聚类
• 5.1 问题的提出
• 5.2 模糊短时序列聚类
• 5.2.1 相似性度量
• 5.2.2 FSTS算法
• 5.3 分布式模糊短时间序列聚类算法
• 5.3.1 算法原理
• 5.3.2 算法描述
• 5.3.3 算法复杂性分析
• 5.3.4 算法收敛性分析
• 5.4 仿真与讨论
• 5.4.1 仿真数据
• 5.4.2 仿真结果
• 5.5 小结
• 第6章 分布式聚类在大型冶金企业质量管理中的应用
• 6.1 应用背景
• 6.1.1 连续退火线工艺流程
• 6.1.2 分布式聚类在断带分析与预报研究中的必要性
• 6.2 分布式数据挖掘系统
• 6.2.1 系统功能设计
• 6.2.2 系统结构设计
• 6.3 连续退火过程的带钢断带分析与预测
• 6.3.1 特征和数据选取
• 6.3.2 挖掘方案设计和挖掘结果
• 6.4 连续退火过程的离群点检测
• 6.4.1 数据准备
• 6.4.2 算法设计与挖掘结果
• 6.5 小结
• 第7章 结论与展望
• 7.1 研究工作总结
• 7.2 进一步的研究方向
• 7.3 小结
• 参考文献
• 攻读博士学位期间以第一作者完成的论文
• 攻读博士学位期间参与的科研项目
• 致谢