论文摘要
离群点挖掘又称异常检测、小事件检测、例外挖掘、孤立点挖掘、偏差检测等。离群点可能是“脏数据”,也可能是与实际对应的有意义的事件。从知识发现的角度看,在某些应用中,那些很少发生的事情往往比经常发生的事情更有趣、也更有研究价值。因此,离群点挖掘是一项重要且有意义的研究工作。目前,离群挖掘正逐渐成为数据库、机器学习、统计学等领域研究人员的研究热点。由于信息数据的高维性、复杂性和巨量性,传统的离群点挖掘方法不能很好地适用于高维大数据集,且往往所获得数据是不完整的、用户也只关心局部不稳定的数据,故对局部离群点的挖掘是本文的重点。离群点快速挖掘算法需要解决邻域的确定和离群点的判断这两个主要问题。采用属性划分方法将数据对象的属性划分为环境属性和行为属性,用环境属性确定对象邻域,行为属性完成离群点的判断。面向高维数据降维、对海量数据的剪枝是本文离群点快速挖掘算法的两个关键点。本文的主要贡献如下:1、分析了高维数据的特点,提出一种基于属性划分局部线性嵌入降维算法（Locally Linear Embedding based on Attribute division,Ad-LLE）。Ad-LLE算法不但继承了局部线性嵌入（Locally Linear Embedding,LLE）算法的平移、旋转以及缩放不变性,同时运用环境属性确定对象的局部邻域,依据对象其近邻分布的不同设置相应的邻居权值及邻居个数,在局部邻居的搜索过程中采用R*-树索引环境属性以加快检索速度,分析证明Ad-LLE降维算法更高效、更合理;2、提出一种基于Ad-LLE降维算法的离群点挖掘算法。将上面提出的Ad-LLE降维算法运用到离群点挖掘中,先通过Ad-LLE算法对高维数据降维,使得高维数据能够直接运用传统的离群点挖掘算法进行离群点判断,并与基于距离的离群点检测和其它降维算法运用在离群点检测中的检测效果进行比较,从检测结果来看,本文所提出的算法适合高维数据的离群点挖掘,且在降维和离群点有效检测上都表现出较好的性能;3、结合局部离群点及离群点本身的特点,提出一种离群点快速挖掘算法（Fastoutlier detection,Fast-OD）。人们常常只关注局部离群点,且离群数据本身在整个数据集中只占极少的部分,当数据集较大时,在整个数据集上挖掘离群点是困难、低效的。于是运用两个启发式剪枝策略对数据集中大量存在的非离群数据进行剔除,以提高算法的检测效率,实验证明本文提出的Fast-OD算法具有减少用户依赖性、降低算法复杂度、提高精确度和可伸缩性的优点;4、通过抽样学习获得全局近似离群度GnGlobal Threshold,GT)和局部近似离群度LTN（JI）（Local Threshold,LT）值。Fast-OD算法中计算GT和LTN（yi）时,若数据集中对象个数N很大时,用整个数据集进行计算很困难、很耗时,采用均匀抽样的方法来获取GT和ITN（yi）值,大大降低了算法的复杂度,理论和分析表明采用抽样技术使Fast-OD算法更能适用于高维大型数据库。