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

《基于单元孤立点提取算法探究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于单元孤立点提取算法探究　　摘要：该文介绍了孤立点、孤立点挖掘以及基于单元的孤立点提取算法的相关概念。主要讨论了应用于二维数据集的基于单元的孤立点提取算法，分析了该算法的程序实现过程和时间复杂度。关键词：数据挖掘；聚类分析；孤立点；孤立点挖掘；二维数据集中图分类号：TP311文献标识码：A文章编号：1009-3044（2013）17-3907-02当今社会，信息已经无所不在，每天都在产生大量的信息，为了更好的搜集、处理信息，产生了计算机信息技术，如今，计算机信息技术已成为计算机领域一个非常重要的部分，数据库、数据仓库和数据挖掘等技术已经被

2、应用到各行各业当中，如政府部门、科研机构、企业办公、商业管理等。当今社会，各行各业都存在着过量的信息，如何从海量的信息中及时发现有用的知识，提高信息的利用率，已成为一个越来越突出的问题。由此产生了数据挖掘和知识发现（DMKD）技术，这些技术在实际应用中得到不断的更新和发展。数据挖掘（DataMining），又称数据库中的知识发现（KnowledgeDiscoveryin6Database，KDD），就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程，它是数据库研究中的

3、一个很有应用价值的新领域，融合了数据库、人工智能、机器学习、统计学等多个领域的理论和技术[1]。数据融合（DataFusion）、数据分析、决策支持等术语，都有相似的含义。1孤立点挖掘1.1孤立点（outlier）的概念数据集合中存在着个别的数据对象，这些数据对象与数据集合中的大部分数据对象的属性、类型等都不同或者不相符，这部分数据就是孤立点。对孤立点进行探测的相当一部分工作来源于对数字的统计。1.2孤立点挖掘孤立点发现需要具备的知识包括探测依据分析、确定所需类、描述构造的类和孤立点探测等四个方面的内容。前三个方面的内容主要用来建立对海量数

4、据集中的一部分数据进行孤立点提取的模型，大部分的数据仓库和数据挖掘研究、分类数据研究以及概念性总结都属于这三个方面的内容。而第四个方面的内容则是一些经常被忽视或作为噪音被剔除的数据，通常集中于非常小的那一部分对象之中。6许多基于孤立点的数据挖掘算法的目标就是排除孤立点，或者使其对数据的影响达到最小，但是由于“一个人的噪声可能是另一个人的信号[2]”，所以说，孤立点可能包含了一些具有隐藏信息的重要数据，排除了孤立点，就有可能把这些重要数据也丢失了。因此，对孤立点进行挖掘就显得尤为重要。孤立点挖掘在实际生活中的应用非常广泛，例如，在商业或企业中

5、对客户的消费能力进行分析，得到极高或者极低收入的客户数据。1.3孤立点挖掘的描述给定一个N个数据点或对象的集合，及预期的孤立点的数目K，发现与剩余的数据相比是显著差异的、异常的或不一致的头K个对象[3]。1.4基于距离的孤立点[4]检测我们可以通过统计学的方法来获得数据中的孤立点，但是这些方法由于要进行大量的计算，所以在实际应用中受到许多限制，容易造成获得的孤立点不准确，因此，产生了基于距离的孤立点检测。而基于距离的孤立点检测进行的计算要少得多，其时间复杂度也相应得到了很大的改善，检测效率也大大的提高。目前，已有许多基于距离的孤立点挖掘算法

6、，这些算法有着比较高的运行效率，包括：基于索引的算法、嵌套-循环算法和基于单元（cell-based）的算法[4][5]等。我们主要是对基于单元（cell-based）的算法进行研究。2基于单元的孤立点提取算法62.1概述2.3算法流程Step1划分m个单元格，将每个单元格Cq中记录点的总数设为变量count0，开始的时候count0=0.Step2设P为数据集中的数据点，由于每一个P都对应一个单元格Cq，所以将P放到Cq之后，count0=count0+1.Step3ifcount0>M，则将相应的Cq转换为blue，设为CbStep4如

7、果Cb的第一层邻居不是blue，则将Cb转换为green.Step5设单元格Cw，Cw即不是blue也不是green：a.计算Cw的第二层邻居中所有点的个数CountCw2b.如果CountCw2>M，将Cw置为greenc.否则，⒈计算Cw的第二层邻居中所有单元中点的个数之和Countw3⒉如果Countw3≤M，将Cw中的所有点标记为孤立点⒊否则，对于Cw中的每一个对象P，设它的个数之和为Countp：3小结6经过上述研究，基于单元的孤立点提取算法能够解决二维或二维以上形式数据的孤立点提取的问题，提高了算法的时间复杂度。但对一些变量的计

8、算由于过高的时间复杂度，一度导致程序运行长时间毫无进展，如何进一步降低时间复杂度成为尚待解决的问题。参考文献：[1]范明，孟晓峰.数据挖掘概念与技术[M].北京：机械工业出版社，