基于单元孤立点提取算法探究.docVIP

基于单元孤立点提取算法探究 　　摘要：该文介绍了孤立点、孤立点挖掘以及基于单元的孤立点提取算法的相关概念。主要讨论了应用于二维数据集的基于单元的孤立点提取算法，分析了该算法的程序实现过程和时间复杂度。 关键词：数据挖掘；聚类分析；孤立点；孤立点挖掘；二维数据集 中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）17-3907-02 当今社会，信息已经无所不在，每天都在产生大量的信息，为了更好的搜集、处理信息，产生了计算机信息技术，如今，计算机信息技术已成为计算机领域一个非常重要的部分，数据库、数据仓库和数据挖掘等技术已经被应用到各行各业当中，如政府部门、科研机构、企业办公、商业管理等。当今社会，各行各业都存在着过量的信息，如何从海量的信息中及时发现有用的知识，提高信息的利用率，已成为一个越来越突出的问题。由此产生了数据挖掘和知识发现（DMKD）技术，这些技术在实际应用中得到不断的更新和发展。 数据挖掘（Data Mining），又称数据库中的知识发现（KnowledgeDiscovery in Database，KDD），就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程，它是数据库研究中的一个很有应用价值的新领域，融合了数据库、人工智能、机器学习、统计学等多个领域的理论和技术[1]。数据融合（Data Fusion）、数据分析、决策支持等术语，都有相似的含义。 1 孤立点挖掘 1.1 孤立点（outlier）的概念 数据集合中存在着个别的数据对象，这些数据对象与数据集合中的大部分数据对象的属性、类型等都不同或者不相符，这部分数据就是孤立点。对孤立点进行探测的相当一部分工作来源于对数字的统计。 1.2 孤立点挖掘 孤立点发现需要具备的知识包括探测依据分析、确定所需类、描述构造的类和孤立点探测等四个方面的内容。 前三个方面的内容主要用来建立对海量数据集中的一部分数据进行孤立点提取的模型，大部分的数据仓库和数据挖掘研究、分类数据研究以及概念性总结都属于这三个方面的内容。而第四个方面的内容则是一些经常被忽视或作为噪音被剔除的数据，通常集中于非常小的那一部分对象之中。 许多基于孤立点的数据挖掘算法的目标就是排除孤立点，或者使其对数据的影响达到最小，但是由于“一个人的噪声可能是另一个人的信号[2]”，所以说，孤立点可能包含了一些具有隐藏信息的重要数据，排除了孤立点，就有可能把这些重要数据也丢失了。因此，对孤立点进行挖掘就显得尤为重要。孤立点挖掘在实际生活中的应用非常广泛，例如，在商业或企业中对客户的消费能力进行分析，得到极高或者极低收入的客户数据。 1.3 孤立点挖掘的描述 给定一个N个数据点或对象的集合，及预期的孤立点的数目K，发现与剩余的数据相比是显著差异的、异常的或不一致的头K个对象 [3]。 1.4 基于距离的孤立点[4]检测 我们可以通过统计学的方法来获得数据中的孤立点，但是这些方法由于要进行大量的计算，所以在实际应用中受到许多限制，容易造成获得的孤立点不准确，因此，产生了基于距离的孤立点检测。而基于距离的孤立点检测进行的计算要少得多，其时间复杂度也相应得到了很大的改善，检测效率也大大的提高。 目前，已有许多基于距离的孤立点挖掘算法，这些算法有着比较高的运行效率，包括：基于索引的算法、嵌套-循环算法和基于单元（cell-based）的算法[4][5]等。我们主要是对基于单元（cell-based）的算法进行研究。 2 基于单元的孤立点提取算法 2.1 概述 2.3 算法流程 Step1 划分m个单元格，将每个单元格Cq中记录点的总数设为变量count0，开始的时候count0=0. Step2 设P为数据集中的数据点，由于每一个P都对应一个单元格Cq，所以将P放到Cq之后， count0= count0+1. Step3 if count0M，则将相应的Cq转换为blue，设为Cb Step4 如果Cb的第一层邻居不是blue，则将Cb转换为green. Step5 设单元格Cw，Cw即不是blue也不是green： a.计算Cw的第二层邻居中所有点的个数CountCw2 b.如果CountCw2M，将Cw置为green c.否则， ⒈计算Cw的第二层邻居中所有单元中点的个数之和Countw3 ⒉如果Countw3≤M，将Cw中的所有点标记为孤立点 ⒊否则，对于Cw中的每一个对象P，设它的个数之和为Countp： 3 小结 经过上述研究