基于信息论的数据挖掘算法

论文摘要

信息论中的多个概念可用于衡量所研究的对象之间的相关性、多样性,以及衡量分布之间的距离,这些技术已被广泛应用于计算机科学的各个领域。本文我们使用信息论技术定义了几个数据挖掘问题,提出了相应的挖掘算法。其中我们所处理的问题包括相关性模式的挖掘,多样性模式的挖掘,特征选择和相关聚类等。另外我们也讨论了将数据公开发布为数据挖掘的应用提供实际数据时可能面临的隐私泄露问题,继续了对t-相近性隐私保护模型的讨论。本文的主要贡献可以总结如下:1.基于衡量随机变量之间依赖性的条件熵,我们引入了对称的、满足三角不等式的信息距离,使用该距离定义了新的依赖树和相关模式,提出了相应的挖掘算法,还使用了该距离来衡量特征之间的相关性进行特征选择。2.基于衡量随机变量之间依赖性的联合熵,我们引入了二值型数据上的熵多样性模式挖掘问题。通过建立不同随机变量联合熵之间的联系,提出了基于这些上下界的快速多样性模式挖掘算法;在此基础上提出了一个改进的非冗余交互特征子集挖掘算法。3.基于衡量连续分布之间距离的Kullback-Leibler divergence,我们提出了一个新的非线性相关聚类算法。4.基于衡量离散分布之间距离的Kullback-Leibler divergence,我们引入了新的t-相近性隐私保护模型,该模型可以解决已有的方法所存在的缺陷,并讨论了和语义隐私之间的联系。在这些工作中,我们都依次给出了问题定义,对问题或性质进行分析,提出挖掘或实现算法。最后都通过人工或者真实数据上进行的实验,验证了我们的算法的效率或所挖掘出来的对象的效用。

论文目录

• 中文摘要
• 英文摘要
• 第一章 前言
• 1.1 模式挖掘
• 1.2 特征选择
• 1.3 相关聚类
• 1.4 数据挖掘和隐私保护
• 1.5 本文的主要贡献
• 1.6 本文组织
• 第二章 信息距离及其应用
• 2.1 相关工作
• 2.2 信息距离
• 2.2.1 信息距离
• 2.3 应用一:依赖树
• 2.3.1 Chow-Liu树
• 2.3.2 低熵树
• 2.3.3 使用信息距离的依赖树
• 2.4 应用二:基于信息距离的特征选择
• 2.4.1 特征选择
• 2.4.2 几个相关性度量讨论
• 2.4.3 基于信息距离的特征选择方法
• 2.4.4 实验
• 2.5 应用三:相关性模式挖掘
• 2.5.1 全置信度定义
• 2.5.2 信息相关模式
• 2.5.3 信息相关模式挖掘算法
• 2.5.4 实验
• 2.6 本章小结
• 第三章 熵多样性模式和非冗余交互特征子集挖掘
• 3.1 相关工作
• 3.2 预备知识
• 3.3 熵l-多样性模式挖掘
• 3.3.1 问题定义
• 3.3.2 熵多样性的几个性质
• 3.3.3 项集联合熵之间的几个关系
• 3.3.4 挖掘算法
• 3.3.5 熵l-多样性模式挖掘实验
• 3.4 非冗余多样性模式
• 3.4.1 问题定义
• 3.4.2 与多样性模式相关的性质
• 3.4.3 联合熵界的新讨论
• 3.4.4 对基于Hamming距离的界的改进
• 3.4.5 挖掘算法
• 3.4.6 实验
• 3.5 非冗余交互特征子集
• 3.5.1 问题定义
• 3.5.2 新的基于特征对相关性的界
• 3.5.3 新的基于互信息量的界
• 3.5.4 NIFS挖掘算法
• 3.5.5 性能评估
• 3.6 本章小结
• 第四章 KLNCC:基于KL-Divergence的非线性相关聚类算法
• 4.1 相关工作
• 4.2 KLNCC算法
• 4.2.1 高斯混合模型
• 4.2.2 EM算法
• 4.2.3 合并微簇
• 4.2.4 时间复杂度分析
• 4.3 实验
• 4.4 本章小结
• 第五章 t-相近性隐私保护
• 5.1 相关工作
• 5.2 基本模型
• 5.3 使用Hellinger距离的相近性
• 5.3.1 Hellinger距离的性质
• 5.3.2 使用Hellinger距离的t-相近性的性质
• 5.3.3 具体的泛化算法
• 5.3.4 实验
• 5.4 语义隐私和使用KL-divergence的相近性
• 5.4.1 语义隐私
• 5.4.2 KL-divergence的性质
• 5.4.3 使用KL-divergence的t-相近性的性质
• 5.4.4 具体的泛化算法
• 5.4.5 实验
• 5.5 本章小结
• 第六章 总结和展望
• 参考文献
• 攻读博士期间完成的工作
• 致谢