论文部分内容阅读
数据挖掘是在海量数据中提取隐含的、未知的、潜在有用的知识或信息模式的决策支持方法,其在功能上的健壮性和应用领域的广泛性已被研究者一致认同.而取样是最通用有效的近似技术,在保证一定精确度的前提下,取样方法显著减小了所处理数据集的规模,使得众多数据挖掘算法得以应用到大规模数据集以及数据流数据上.由此,取样这种近似技术在数据挖掘,查询优化,统计评估,决策支持,数据流处理和机器学习中被普遍使用,另外,由于取样方法良好的伸缩性和灵活性,也使其成为构建数据流概要的一个非常重要的方法.
本文围绕着数据挖掘的取样技术进行研究,研究的过程中采用了比较研究的技术和方法,其主要内容包括:
(1)代表性取样方法之间的特性、应用与性能比较;
(2)偏倚取样与均匀取样方法之间的利弊与选用比较;
(3)取样方法与其他概要数据结构方法的比较;
(4)基本的最优K相异性取样算法(OptiSim)与扩展的OptiSim方法的比较;
(5)近似查询处理中在线处理方法与预计算处理方法的比较;
此外,本文提出了可应用于数据挖掘领域的一系列有效取样算法,并进行了理论分析和实验验证.具体而言。本论文研究的主要内容及创新点可以归纳为以下六个方面:
(1)综述了数据挖掘领域取样技术和方法的研究成果,在对代表性取样方法进行比较研究和分析总结的基础上,提出了一个能将现有的代表性取样方法纳入的一个通用取样算法分类框架.论述了均匀取样存在的应用局限与偏倚取样的必要性问题.阐述了数据挖掘取样技术的应用与发展,特别是传统取样技术在数据挖掘领域中的新拓展与新应用,指出了取样技术和方法面临的挑战和研究展望.
(2)在综述了数据挖掘领域中与取样技术相关的构造概要数据结构方法的基础上,进行取样方法与其他概要数据结构方法(如:哈希、小波、直方图和基本窗口)之间的多方位讨论与比较.着重研究了取样复杂性理论,取样尺寸对取样偏差的影响、适用的取样方法衡量标准以及影响取样方法选择的因素等问题.提出了能更好地评估取样质量,尤其是偏倚取样方法取样质量的”取样方法代表性”和”取样偏差(Sampie Deviation)”等概念,并在此基础上得出了若干能避免过取样问题的研究结论,最后通过实验验证了这些结论的可靠性.
(3)最优K相异性选择算法OptiSim是一些基于相异性选择算法的一个更加一般的、统一的方法,是一种能选择既有代表性又兼顾多样化的快速和通用的数据子集选择技术,而DBSCAN是一种优秀的密度聚类算法.本文提出了一个基于OptiSim的的密度聚类算法:OR-DBSCAN,它在DBSCAN处理之前应用代表性子集取样算法OptiSim作为数据预处理,由此来提高原DBSCAN算法的聚类效率.在研究了OptiSim存在的应用局限的基础上,提出了扩展的OptiSim(EOptiSim)方法,EOptiSim方法对OptiSim有三处关键的改进:偏好选择改进、旋转选择改进和不对称旋转选择改进,从而弥补了原OptiSim算法在处理组合数据库和分布式数据库方面的不足.最后,提出了一个基于相异性选择的数据流偏倚取样方法与有效性可行性分析.
(4)将EOptiSim技术和移动Agent技术结合起来,推广应用于分布式数据挖掘中,提出了一种适用于分布式数据挖掘环境的偏倚取样技术.该方法尤其适合于各场地数据是互相关联和互相依赖的分布式数据挖掘任务.在同样条件下,所提方法的CPU需求、I/O成本和网络通讯代价比集中式处理模型(Client-Server模型)的小,并且具有良好的实时性能.
(5)在对应用于近似聚集查询的取样技术和离群点检测技术深入研究的基础上,提出了一个能克服均匀取样局限的离群分治取样算法:Outlier-DivideConquer,其中的离群分离算法Outlier-Divide,只需单遍扫描数据集,无需对整个聚集属性集进行排序,与同类算法相比,运行效率有优势.Outlier-DivideConquer方法在数据集存在少量离群数据的情况下,能有效提高近似聚集查询的质量,实验结果验证了所提出算法的有效性和正确性.
(6)对近似聚集查询中有影响力、有代表性的Congressional Samples取样算法进行了优化.优化的算法以最小化MSE误差(均方差)作为取样数分配算法的依据,提出了一个新的组取样数分配算法,克服了原算法缺乏严格的公式描述,难以进行理论评估的不足;优化的算法还对原算法中未考虑组内数据呈高偏斜分布(存在少量离群数据)的问题进行了处理,有效降低了原Congress算法的查询误差.