交易数据的聚类分析

论文摘要

聚类分析，是将物理或抽象对象集合划分为由相似对象组成的多个类的过程。近年来，随着数据挖掘技术的发展，聚类分析作为数据挖掘的重要内容得到了广泛的研究，并应用于许多领域中。随着信息与互联网技术的发展，人们拥有的数据不仅数量越来越庞大，而且数据类型越来越复杂、结构越来越多样。因此，现有的聚类算法在实际应用中仍然面临两个问题：1)算法在处理大规模数据时，性能急剧下降甚至无法完成数据分析，不具有可伸缩性；2)很多聚类算法局限于理论上的分析，较少考虑具体应用中的实际数据特征与差异，因而实用性差。交易数据是一类特殊的类别数据，具有数据量大和维数高的特点。典型的交易数据包括购物篮数据、WEB日志数据、客户信息、病人诊断记录以及图像信息等，通常产生于零售业、电子商务、医疗以及电信、保险、银行等行业。因此，针对交易数据，研究可伸缩聚类分析方法是一个同时具有挑战性和实际意义的课题。本论文以大规模交易数据为研究对象，重点研究大规模交易数据聚类分析中的一些问题。本文的主要研究内容和创新点包括以下几个方面：（1）提出了可伸缩的大规模交易数据聚类分析框架，即SCALE（Sampling，Clustering structure Assessment，cLustering and domain-specific Evaluation）。SCALE的设计具有下列特点：1)针对交易数据的特征，提出采用覆盖密度以及加权覆盖密度有效地测量一组交易数据的整体相似度；2)基于加权覆盖密度设计和实现可伸缩的WCD交易数据聚类算法；3)采用聚类结构探测方法生成候选的聚类数量，有效地减少聚类算法参数空间的搜索；4)将聚类结果评估集成到该框架下，用领域特定的度量辅助用户选择最优的聚类结果。实验结果表明SCALE框架下的交易数据聚类分析能生成高质量的交易数据聚类结果。（2）研究了交易数据聚类结构探测的问题。针对通用类别数据聚类结构识别方法BKPlot的两个弱点，即噪音候选聚类数量多以及处理具有大量数据项的交易数据集时算法性能下降，提出在交易数据集找出一组候选的最优聚类数量“Ks”的新方法，即DMDI方法。以自定义的交易聚类模式相异度度量为基础设计和开发出一种凝聚的层次聚类算法，即ACTD算法。利用ACTD算法在聚类过程中生成的合并索引值可发现候选的最优聚类数量。实验表明，DMDI方法能有效地识别交易数据聚类结构。（3）研究了交易数据聚类分析结果的稳定性问题。传统基于划分的聚类方法的聚类结果常常陷入局部最优，而SOM神经网络的聚类结果稳定，但只能处理数值型数据。为此，本文提出了一种基于GHSOM神经网络的交易数据聚类分析方法，即GHSOM-CD方法。该方法在GHSOM网络学习算法中引入覆盖密度的概念，改进了神经元权值更新方法以及网络训练停止条件。实验表明GHSOM-CD方法在交易数据集上产生的聚类结果更有意义，是SOM神经网络在类别数据聚类分析上的扩展应用。（4）研究了频繁项集的压缩问题。针对频繁项集挖掘中频繁项集数量过多的问题，研究并提出一种动态聚类的方法，即EESC算法，近似压缩频繁项集。该聚类方法基于自定义的频繁项集类内相似度度量：表达式相似度和支持度相似度。实验结果显示这种近似的频繁项集压缩方法是可行的并且压缩质量好。

论文目录

• 摘要
• ABSTRACT
• 第一章绪论
• 1.1 研究背景与意义
• 1.2 聚类分析
• 1.2.1 聚类分析步骤
• 1.2.2 数据类型以及相似度度量方法
• 1.2.3 聚类方法
• 1.2.4 聚类算法研究面临的挑战
• 1.3 论文的主要研究内容
• 1.4 论文章节安排
• 第二章 可伸缩的大规模交易数据聚类分析框架-SCALE
• 2.1 背景介绍
• 2.2 SCALE框架概述
• 2.3 WCD聚类算法
• 2.3.1 符号定义
• 2.3.2 覆盖密度与加权覆盖密度定义与比较
• 2.3.3 基于加权覆盖密度的交易数据聚类准则函数
• 2.3.4 WCD算法描述
• 2.3.5 算法复杂度分析
• 2.4 聚类质量评估度量
• 2.5 实验
• 2.5.1 实验数据集
• 2.5.2 聚类结构评估
• 2.5.3 性能测试
• 2.5.4 聚类结果质量评估
• 2.5.5 与CLUTO的聚类质量比较
• 2.6 相关工作
• 2.7 本章小结
• 第三章 交易数据聚类结构探测方法-DMDI
• 3.1 背景介绍
• 3.2 交易数据聚类模式相异度概念定义
• 3.3 基于交易聚类模式相异度的凝聚层次聚类算法-ACTD
• 3.4 通过DMDI图检测聚类结构
• 3.4.1 DMDI图定义
• 3.4.2 大规模交易数据的聚类结构估计
• 3.5 实验
• 3.5.1 性能测试
• 3.5.2 质量测试
• 3.5.3 采样数据集上的质量测试
• 3.5.4 DMDI方法处理有噪音数据的交易数据集能力
• 3.5.5 比较DMDI方法与BIC方法
• 3.6 本章小结
• 第四章 基于GHSOM神经网络的交易数据聚类方法
• 4.1 背景介绍
• 4.2 SOM与GHSOM
• 4.2.1 SOM
• 4.2.2 GHSOM
• 4.3 聚类交易数据的GHSOM-CD方法
• 4.3.1 GHSOM-CD方法中的相关概念
• 4.3.2 GHSOM-CD训练算法描述
• 4.4 实验
• 4.4.1 实验数据集
• 4.4.2 实验结果
• 4.5 本章小结
• 第五章 采用动态聚类方法的频繁项集压缩
• 5.1 背景
• 5.2 相关工作
• 5.2.1 关联规则定义
• 5.2.2 频繁项集挖掘Apriori算法
• 5.2.3 Apriori算法的优化方法
• 5.2.4 频繁项集压缩方法
• 5.3 问题的提出
• 5.3.1 频繁项集挖掘结果分析
• 5.3.2 频繁项集相似度定义
• 5.3.3 频繁项集聚类准则函数
• 5.4 频繁项集聚类算法
• 5.5 实验
• 5.6 本章小结
• 第六章 结束语
• 6.1 论文工作的主要贡献
• 6.2 进一步研究设想
• 致谢
• 参考文献
• 读博期间取得的研究成果