高维数据挖掘中若干关键问题的研究

数据挖掘指的是从大量的数据中提取隐含的、事先未知的、并且潜在有用的知识的技术，是目前国际上数据库和信息决策领域最前沿的研究方向之一。在实际应用中经常会碰到高维数据，如交易数据、文档词频数据、用户评分数据、WEB使用数据及多媒体数据等。由于这种数据存在的普遍性，使得对高维数据挖掘的研究有着非常重要的意义。但由于“维灾”的影响，也使得高维数据挖掘变得异常地困难，必须采用一些特殊的手段进行处理。 随着数据维数的升高，高维索引结构的性能迅速下降，在低维空间中，我们经常采用Lp距离作为数据之间的相似性度量，在高维空间中很多情况下这种相似性的概念不复存在，这就给高维数据挖掘带来了很严峻的考验，一方面引起基于索引结构的数据挖掘算法的性能下降，另一方面很多基于全空间距离函数的挖掘方法也会失效。解决的方法可以有以下几种：一个可以通过降维将数据从高维降到低维，然后用低维数据的处理办法进行处理；对算法效率下降问题可以通过设计更为有效的索引结构、采用增量算法及并行算法等来提高算法的性能；对失效的问题通过重新定义使其获得新生。 本文对高维数据挖掘中的相似性搜索、高维数据聚类、高维数据异常检测及电子商务中的协同过滤技术进行了研究，指出了高维给这些领域带来的影响，提出了一些解决问题的方法，具有一定的理论意义和现实的指导意义。 本文的主要工作如下： （1）通过对高维数据特点的分析，提出了一种新的相似性度量函数Hsim（），该函数可以避免在高维空间中分辨能力下降的问题，还可以将数值型的数据和二值型数据相似性的计算整合在一个统一的框架中。并将它与其它的相似性函数进行了比较； （2）结合量化交易数据的特点，提出了一种新的量化交易数据相似性搜索方法，这种算法基于一种称为特征表的结构，对数据有较高的修剪率，能大大提高相似性搜索的速度； （3）提出了一种新的基于用户评分数据的协同过滤算法，并通过实验证明该算法不仅提高了推荐的效率，还对推荐精度有一定的提高； （4）分析了高维数据聚类的算法，提出了基于对象相似性的高维数据聚类框架； （5）对高维对异常检测算法的影响进行了分析，给出了投影异常检测的概念。提出了一种动态环境下局部异常的增量挖掘算法IncLOF，并通过实验和LOF算 摘 要 法进行了比较，结果表明在动态高维的环境下，当高维索引结构失效的情况下。 能大大提高局部异常的挖掘效率。