基于Voronoi图的多尺度聚类数据挖掘开题报告.docxVIP

基于Voronoi图的多尺度聚类数据挖掘研究目的与意义近些年，数据挖掘（Data Mining， DM）和知识发现（Knowledge Discovery in Database， KDD）由于国际人工智能和数据库学界的重视[1]-[2]而得到学者广泛研究。KDD或DM的目的是从海量的数据集中提取人们感兴趣的、事先未知的、或潜在有用的信息或模式[3]，而聚类作为数据挖掘研究领域的一个重要研究分支[4]，在相关领域一度掀起研究热潮。然而学术界并未对聚类分析做过一个公认的定义，Everitt[5]于1974年对聚类分析定义如下：旨在将样本集按其身属性聚成若干类，以保证类内相本相似度尽可能高，而类间样本相似度尽可能低。有学者将聚类称作无监督的分类，是因为在进行聚类之前没有任何先验信息可以使用，并且将样本集聚成几类也是未知的。由于聚类在数据挖掘过程中的典型作用，因此数据挖掘对聚类亦有不同于其它研究分支的要求，如聚类过程要具有高度的可伸缩性、处理不同类型数据的能力[]、进行任意形状的聚簇[]、将输入参数的领域知识最小化[]、对噪声数据具有很好的处理能力[]、对数据的处理顺序不敏感性、对高维数据的处理能力[]、基于约束的聚类[]以及聚类结果的可用性和可解释性。这些要求使用聚类算法的研究面临着巨大的困难与挑战，而随着科学技术的发展，人们获取信息和存储信息的能力也日益增强，人们淹没在海量的数据之中却不知所措，如何使用数据挖掘技术从这些海量的数据中攫取有用的知识和信息是人们当前面临的重要问题[]，而聚类分析作为数据挖掘过程的重要一环为解决人们面临的重要科学难题提供了思路，提出了不少有效且高效的聚类挖掘算法[]。多尺度是各种数据类型自身的属性，如地学领域数据的多尺度特性主要表现在时间可伸缩性和地理空间的可扩展性[]，人口领域数据的地域属性、年龄属性、群体特征等都是多尺度特性的表现。而传统的聚类分析并未对数据的多尺度特性进行单独的研究，这对人们从多尺度的数据中提取有用信息造成了极大的妨碍，因此如何针对数据的多尺度特性进行聚类挖掘是目前人们所面临的一大难题。本文主要借助Voronoi图的良好性质对多尺度的聚类数据挖掘进行研究，实现数据聚类的多尺度化。这对于指导人们从海量的数据中获取有用知识进而进行后期的人工决策有着实质性的指导意义，亦将聚类研究推向了一个新的研究层次，对于数据挖掘功能的完善也有着理论研究意义。国内外研究现状聚类分析作为近几年热门研究领域，涉及数据挖掘、模式识别、机器学习、数据分析等众多学科，自Everitt给出了聚类的定义以来40多年的时间里，有不少学者均投身于聚类分析的研究，提出了不少聚类分析算法，取得了引人注目的成绩。在国外，Lloyd（1957）基于划分的思想首次提出了K-Means聚类算法，MacQueen（1967）亦对K-Means算法进行了研究；由于K-Means聚类算法通常会在获得一个局部最优值时终止，且只适合于数值型数据的聚类，只能发现聚类结果为凸形的数据集，Kaufman（1990）和Rousseeuw（1990）分别提出了K中心点算法PAM和CLARA；Huang（1998）亦针对K-Means算法存在的不足之处进行改进提出了一种适合于分类属性数据的K-Modes算法；Ng和Han（1994）针对大型应用的研究提出了CLARANS算法；Ester，Kriegel和Xu（1995）采用有效的空间存取方法，进一步改进了CLARANS的性能；Day和Edelsbrunner（1984）对凝聚层次聚类算法进行了早期综述，Kaufman和Rousseeuw（1990）提出了分裂层次聚类算法（DIANA）；Zhang，Ramakrishnan和Livny（1996）使用CF树进行层次聚类，提出了BIRCH聚类算法；Guha，Rastogi和Shim（1998）通过复杂的链接分析、变换和最近邻分析提出了CURE聚类算法；Ester，Kriegel，Sander和Xu（1996）抛弃了距离这一概念，基于密度的思想提出了新的聚类算法DBSCAN；Ankerst，Breunig，Kriegel和Sander（1999）为了减少算法对输入参数的依赖性提出了一种簇排序方法OPTICS，大大方便了基于密度的聚类；Wang，Yang和Muntz（1997）基于网格的思想提出了多分辨率方法STING；Sheikholeslami，Chatterjee和Zhang（1998）提出了一种通过小波变换来变换原特征空间的多分辨率的聚类算法WaveCluster；Dempster，Laird和Rubin（1977）基于模型思想提出了聚类算法EM，即期望最大算法；Agrawal，Gehrke，Gunopulos和Raghavan（1998）针对高维数据的