【作者】 沙朝锋；

【导师】 周傲英；

【作者基本信息】 复旦大学 ， 计算机软件与理论， 2008， 博士

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

【Abstract】 Some notation in information theory can be used to measure the correlations, diversity in the researched objects, and the distance between probability distributions. Those techniques has found many applications in computer science areas. In this thesis, we propose some data mining problems based on information theory, and develop techniques for these tasks. The problem we address includes mining correlation patterns and diversity patterns, feature selection, and correlation clustering. We also discuss privacy preservation in the public data publishing for data mining applications, where we focus on the t-closeness privacy preservation model.The main contributions of this thesis can be summarized as follows:1. Based on the conditional entropy, we introduce a symmetric information distance which satisfying triangle inequality, define the problem of finding novel dependency trees and correlation patterns, and propose some algorithms for these mining tasks. We also propose a feature selection algorithm based on this new information distance which measures the correlation between features.2. Based on the joint entropy of random variables, we introduce the problem of finding entropy diversity patterns. By establishing serval bounds between entropy of different random variables, we propose some efficient algorithms to find these diversity patterns. We also develop an improved mining algorithm for non-redundant interacting feature subsets.3. Based on Kullback-Leibler divergence between continuous distributions, we develop a novel nonlinear correlation clustering algorithm.4. Based on Kullback-Leibler divergence between discrete distributions, we introduce a novel t-closeness privacy preservation model with Kullback-Leibler divergence, which addresses the drawback in the previous approaches. We also discuss the relationship between our new model with semantic privacy.In these work, we in turn present the problem definition, analyze the problem or the properties of researched objects, develop the mining or implementation algorithms. The efficiency and effectiveness of each technique is verified using simulations over both synthetic and real data sets.更多还原