《高维数据空间中离群点检测算法的研究》由会员分享，可在线阅读，更多相关《高维数据空间中离群点检测算法的研究（47页珍藏版）》请在金锄头文库上搜索。
1、南京财经大学 硕士学位论文 高维数据空间中离群点检测算法的研究 姓名：吴晓燕 申请学位级别：硕士 专业：计算机应用技术 指导教师：程国达 2010-03-10 I 摘 要 离群点挖掘由于其在检测金融欺诈和网络入侵、疾病预防和控制、灾害气象 预报等许多方面的广泛应用而成为数据挖掘领域中的一个重要研究方向。 随着研 究的进行，大型、低维数据中的离群点的检测已经有了比较深入的研究，取得了 比较多的成果。但是，在大型、高维数据中的离群点的检测则还面临许多的问题 和挑战，有许多问题需要进行深入、系统的研究。本文是在现有算法的基础上， 提出了基于遗传算法与模拟退火相结合的高维数据中离群点的挖掘方法。 本文
2、首先介绍了数据挖掘和离群数据挖掘的概念， 论述了已有的离群点检测 算法， 并对它们进行了比较和分析， 然后讨论了几种重要的高维离群点检测算法， 指出存在的问题， 在此基础上提出了基于遗传算法和模拟退火算法相结合的高维 空间离群数据检测方法。该方法首先将高维数据空间的每一维进行网络划分，为 了克服由于网络划分造成的相邻数据点的分裂，该方法采用两次划分的方法，并 将两次划分的结果压缩到同一棵网格计算树上， 然后对落在网格中的数据点进行 编码，再计算每个网格的稀疏系数。为了降低计算复杂度，在高维空间查找稀疏 系数最小的前 n 个网格及其中的点。本文采用了遗传算法，为了防止遗传算法的 “早熟” 现象，
3、 算法中引入了模拟退火算法的思想。 实验证明， 该方法是有效的。 关键词:关键词: 数据挖掘；离群点；稀疏系数；网格计算树；遗传算法；模拟退火算 法 II Abstract Outlier detection become an important research direction in the field of data mining,widely used in the field of financial fraud and network intrusion detection, disease prevention and control,disaster,and many ot
4、her aspects of weather forecasting.As the research proceeded,large-scale,low-dimensional data in the detection of outliers have a more in-depth study,which has been made many achievements.However,in the large,high-dimensional data in the detection of outliers is still faced with many problems and ch
5、allenges,a lot of problems need to be in-depth,systematic study.This paper is based on existing algorithms,presents a outlier mining method based on the combination of genetic algorithm and simulated annealing algorithm on the large,high-dimensional data. This paper introduces the data mining and ou
6、tlier mining concepts,compares and analyses the existing outlier detection algorithms,discusses several important high-dimensional outlier detection algorithms,and points out the drawback of them.On this basis,an new outlier detection methods of genetic algorithm and simulated annealing algorithm in
7、 the high-dimensional space is proposed.In this method,the high-dimensional data of each dimension is divided into grid,in order to overcome the crack caused by the grid of adjacent data points of the division,two grid classification methods have been used, and the results of the two have been store
8、d into the same grid computing tree, then the data points in each grid are coded, and the sparsity coefficient of each grid is calculated.To reduce the computational complexity,find the smallest factor of the top-n grid and the points in high-dimensional space,genetic algorithm is adopted in this pa
9、per.In order to prevent “premature“ phenomenon,simulated annealing algorithm is introduced.The experiments shows that the above method is effective. Keywords: data mining; outlier; sparsity coefficient; grid count tree; genetic algorithm; simulated annealing algorithm 学位论文独创性声明学位论文独创性声明 本论文是我个人在导师指导
10、下进行的研究工作及取得的研究成果。 论文中除 了特别加以标注和致谢的地方外， 不包含其他人或其它机构已经发表或撰写过的 研究成果。 其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名： 日期： 学位论文使用授权声明学位论文使用授权声明 本人完全了解南京财经大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵 守此规定。 作者签名：作者签名： 导师签名：导师签名： 日期：日期： 南京财经大学硕士学位论文 1 第 1 章 绪
11、论 1.1 数据挖掘概述 1.1 数据挖掘概述 在信息社会，数据的获取也许并不困难，而困难的是怎样从大量的数据中获 取有用的信息和知识，数据挖掘要解决的正是这个问题。什么是“数据挖掘” ， 以及数据挖掘的含义和功能，不同的学科有不同的认识。在机器学习中，数据挖 掘是从大量的数据中抽取出隐含的、未知的和潜在有用的信息的过程45。在统计 学中， 数据挖掘是通过对给定的数据集的分析和观察， 寻找出数据间的未知关系， 从而总结出便于理解的、新颖的和有用的数据31。现在，对于数据挖掘，更倾向 认为是数据库中的知识发现，即 KDD（Knowledge Discovery in Database） ，是指
12、从大量随机的实际应用数据中，提取出隐含在其中的、人们事先不知道的、潜在 有用的信息和知识的过程21。在 1989 年的第十一届国际人工智能学术会议上， KDD 第一次被提出来，随后又连续举行了四届 KDD 国际专题研讨会，由此， KDD 在学术界的影响越来越大， 1995 年国际 KDD 组委会把 KDD 专题讨论会改 名为国际会议，并在第一届 KDD 国际学术会议上决定以后每年召开一次 KDD 国际学术会议。到 1998 年，美国计算机学会成立了一个新的学术组织 ACM SIGMOD，即为 ACM Special Interested Group on Knowledge Discovery
13、 in Database，到 1999 年 ACM SIGMOD 共组织了五届知识发现与数据挖掘国际学 术会议(KDD99)。此外，还有一些国际和地区性的数据挖掘学术会议，如“知识 发现与数据挖掘太平洋亚洲会议(PAKDD)” ，“数据管理国际会议(SIGMOD)” ，“人 工智能国际联合会议(IJCAI)” 、 “美国人工智能学会会议(AAAI)” ， “数据库系统 高级应用国际会议(DASFAA)”等。近年来，数据挖掘已经涉及到工业、医疗、 金融、生命科学等众多领域，在这些领域里，已经储存和正在产生大量数据，迫 切需要从中获取有用的知识和信息， 数据挖掘的技术和功能已经引起了社会的广 泛关
14、注。 目前对数据挖掘的理解分为广义和狭义两种。 广义的理解是将数据挖掘等同 于 KDD 的近义词。 狭义的理解即是将数据挖掘视为知识发现过程中的一个步骤。 KDD 一般可以由数据清理、数据集成、数据选择、数据变换、数据挖掘、模式 评估和知识表示等步骤组成31。 南京财经大学硕士学位论文 2 1.2 数据挖掘的分类 1.2 数据挖掘的分类 数据挖掘涉及许多学科和技术，其中包括数据库和数据仓库、统计学、机器 学习、模式识别、人工神经网络、可视化技术、信号处理以及空间或时间数据分 析等。数据挖掘技术可以从不同的角度分类，有根据挖掘的数据种类进行分类、 根据发现知识的种类分类、 根据采用的技术进行分类
15、和根据应用领域分类等 4 种 31。从挖掘的数据类型来进行分类，可以分为时间序列的、文本的、空间的、流 数据的、多媒体、互连网等数据挖掘。从挖掘的知识类型分类，可以分为分类知 识（同类数据间具有共同性的知识和不同类数据间具有差异性的知识） 、广义型 知识（根据数据的微观特性发现的带有普遍性的知识） 、关联知识（反映一个事 物和另一个事物间的关联关系的知识） 、聚类知识（指根据事物的属性对应分类 的数据进行类别识别的过程） 、序贯模式（指在多个数据序列中发现数据共同的 行为模式） 、预测型知识（通过时间序列数据，由历史数据预测未来情况） 、偏差 型知识（通过分析数据聚类外的离群点，对差异特例进行
16、描述）等。从采用的技 术类型分类，可以分为决策树、人工神经网络、遗传算法、最近邻技术、统计分 析、机器学习方法、数据库方法和粗糙集方法等。此外，还可以从数据挖掘的应 用领域分类，因为可能有些数据挖掘系统特别适合金融、电信、DNA、股票市 场、E-mail 等。不同的应用通常需要集成对于该应用特别有效的方法。因此，泛 化的全能的数据挖掘系统可能并不适合特定领域的挖掘任务。 1.3 数据挖掘的方法 1.3 数据挖掘的方法 数据挖掘中常用的方法可以分为以下 5 种。 1.统计学方法 1.统计学方法 统计学中的许多知识，如多元统计分析、回归分析和主成分分析等均在数据 挖掘中有着重要应用 7。例如，用多元统计分析中的聚类分析可以发现超市数据 库中有类似购买行为的消费者群体，识别从天空测距红外线光谱的子类等。回归 分析则被用于估计给出诊断结果的情况下病人的存活率， 预测由微波遥感探测的 森林里生物的数量等。 主成分分析在数据挖掘中常用于数据的预处理， 消除噪声， 消除数据属性间的相关性，降低数据
