基于免参数据挖掘的相异度度量研究

论文摘要

近年来随着数据挖掘的迅速发展，各种聚类、分类等技术已广泛应用于各种领域，但其中参数设置带来的问题也越来越引起研究人员的注意。于是，免参数据挖掘思想应运而生。本文深入分析了参数设置对数据挖掘结果的各种影响，大量研究表明参数的设定是影响甚至导致数据挖掘结果出错的重要因素之一，因此在数据挖掘的各个环节实现免参是解决这些问题的一个途径。文章从相异度度量方法入手，在对Kolmogorov（描述）复杂理论研究的基础上，将其和免参数据挖掘思想相结合，提出了一种基于压缩的相异度度量方法SCDM（Symmetrical Compression-BasedDissimilarity Measure）。该方法采用压缩算法估计Kolmogorov复杂度，由于压缩算法本身的高效性，使得该方法也具有较高的效率。本文使用MATLAB仿真软件、标准压缩软件以及DNA序列专用的GenCompress压缩软件实现了SCDM的功能，在DNA序列和实时序列上做了大量实验，与带参的距离度量方法及欧氏距离的结果进行了比较，分析了SCDM方法的正确率。本文还将SCDM方法应用到了层次聚类算法中，实验结果表明，由于SCDM方法采用了压缩算法，所以对被比较对象要求不高，只要维数相近就不需要标准化，也允许少量数据点的丢失，再加上压缩算法本身的时间空间高效性，对高维数据的处理也比较容易，可以省去其它方法对高维数据进行降维处理这一步骤。而且SCDM方法不需要参数设定，因而不需要参数训练和选择，避免了参数设置不当对聚类结果的影响，很好地提高了算法的正确率。应用SCDM方法的层次聚类算法的聚类准确率也较高。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第1章 引言
• 1.1 研究背景与意义
• 1.2 研究内容与思路
• 1.3 论文组织结构
• 第2章 相关知识介绍
• 2.1 数据挖掘概述
• 2.1.1 数据挖掘概念及发展简史
• 2.1.2 数据挖掘的对象
• 2.1.3 数据挖掘的方法
• 2.1.4 数据挖掘的应用
• 2.2 免参数据挖掘
• 2.3 Kolmogorov复杂度
• 2.3.1 Kolmogorov复杂度的通用性（Universality）
• 2.3.2 理论内容
• 第3章 相似/相异度度量
• 3.1 相似/相异度简介
• 3.2 一些常用的相似/相异度度量介绍
• 3.2.1 欧氏距离
• 3.2.2 DTW（Dynamic time warping）:动态时间规整
• 3.2.3 SVM（Support Vector Machines）:支持向量机
• 3.2.4 其他一些相异度度量
• 3.3 当前相异度度量存在的问题
• 第4章 基于压缩的相异度度量SCDM
• 4.1 免参距离公式
• 4.1.1 距离的定义
• 4.1.2 免参距离公式的通用性和正确性的证明
• 4.2 免参距离的实现
• 4.3 SCDM
• 4.3.1 对称性问题
• 4.3.2 简化
• 4.4 SCDM的实现
• 4.4.1 SCDM可作用的数据
• 4.4.2 SCDM的实现步骤
• 4.5 SCDM的特点及应用
• 4.5.1 SCDM的特点
• 4.5.2 SCDM的应用
• 第5章 SCDM方法在聚类算法中的应用
• 5.1 基于SCDM方法的聚类算法
• 5.1.1 传统的聚类方法
• 5.1.2 基于SCDM方法的聚类算法描述
• 5.2 基于SCDM方法的聚类算法分析
• 5.3 SCDM方法的实现工具及聚类结果分析
• 5.3.1 压缩工具的选择
• 5.3.2 使用SCDM方法对DNA串聚类的结果分析
• 5.3.3 SCDM方法对实时序列的聚类结果分析
• 5.4 结论
• 第6章 总结与展望
• 致谢
• 参考文献
• 攻读硕士学位期间的研究成果