基于聚类的异常挖掘算法研究.pdf

《基于聚类的异常挖掘算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、学校代码：10255学号：107279基于聚类的异常挖掘算法研究StudyonOutlierMiningAlgorithmsBasedonClustering学院：信息科学与技术学院专业：模式识别与智能系统姓名：苏晓珂导师：秦玉明教授论文完成时间：：，2010年2月JJUli；IiililtiIJimJliJIJJJiIJIJlilIJJtJY2135795东华大学学位论文原创性声明本人郑重声明：我恪守学术道德，崇尚严谨学风。所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已明确注明和引用的内容外，本论文不包含任

2、何其他个人或集体已经发表或撰写过的作品及成果的内容。论文为本人亲自撰写，我对所写的内容负责，并完全意识到本声明的法律结果由本人承担。嚣文雾警糕哆日期：切扣年箩月诏日～东华大学学位论文版权使用授权书学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅或借阅。本人授权东华大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于保密口，在——年解密后适用本版权书。不保密函。学位论文作者戤皱呓纠指导教

3、师签纱芦一嗍一?口铋肋日醐2到删1日摘要在网络、金融、气象、医学、保险和电信等众多应用领域，稀有的、特殊的异常数据往往代表一种偏差或者新模式的开始，对这些异常数据的识别比对正常数据的分析更有价值，可从新的视角开启新的理论，从而带来新的应用。从数据分析的角度而言，识别这些异常数据就需要相应的异常挖掘算法。随着应用日益广泛以及数据不断积累，。。异常挖掘需处理的数据量越来越大，应用环境也越来越复杂。已存在方法主要针对中、小规模数值属性数据集，面对大规模混合属性数据集和动态数据流时，算法的可扩展性、时效性及准确性都难以满足实际应用的需求。在模式识别

4、领域，异常挖掘可看作是一种特殊的分类问题。作为无监督模式识别的一个重要分支，聚类具有不需要任何先验知识的特性，比较适合面向大规模数据集的异常挖掘。因此，基于聚类的异常挖掘得到了广泛研究，提出了许多有效的异常挖掘算法，但仍有许多问题尚待研究和解决。本文主要针对已有异常挖掘算法存在的不足，从不同角度研究了基于聚类的异常挖掘算法。一．目前，已有基于聚类的异常挖掘算法大多直接将聚类形成的小簇作为异常，由于采用的类球形聚类算法限制，有些小簇可能是任意形状正常簇的边界，从而导致较高的FR(FalsePositiveRate)。为了提高挖掘结果的准确性，

5、研究任意形状聚类对异常挖掘来说具有非常重要的意义。本文首先介绍了两种任意形状聚类算法OBASC和EASSC。算法OBASC针对小规模数据集，根据提出的可兼顾分类属性取值频率差异与频率高低的差异性度量方式，仅需输入一个近邻阈值参数就可发现任意形状的簇；增强的谱聚类算法EASSC使用改进的高斯核函数作为簇间相似性度量，可处理大规模高维变密度数据集。实验结果表明算法OBASC和EASSC聚类精度高，适用于混合属性数据集中任意形状聚类。这两种算法为设计高效的异常挖掘奠定了基础，但参数确定困难，必须经过多次试探。为减少用于预处理的聚类算法对用户的依赖

6、，本文提出了基于聚类融合的异常挖掘算法CEBOM，将任意形状聚类算法中的一种——OBASC作为基础聚类算法，对较大范围内不同阈值下得到的候选异常进行融合，识别真正的异常。实验结果表明，CEBOM算法可降低直接将小簇作为异常的高FR，并且能提供给用户更为“友好”的操作。基于任意形状聚类的异常挖掘虽然可有效检测到异常数据，但时间复杂度较高。在内存有限的情况下，处理大规模数据集需要频繁的内外存数据交换，从而导致难以容忍的时空复杂度。针对此种问题，本文提出了两种面向大规模混合属性数据集的异常挖掘算法ICBOM和SNNOM。算法ICBOM在对原始数据

7、集增量聚类的基础上，过滤掉大量正常数据，根据提出的异常簇定义识别数据集中的边界异常和内部异常，同时探讨了算法中的参数取值；算法SNNOM计算增量聚类结果簇间的共享最近邻相似度，不但能够发现任意形状的簇，还可挖掘到变密度数据集中的全局异常。理论分析与实验结果表明，这两种算法关于数据集的大小和属性个数呈近似线性时间复杂度，较●之同类算法具有更高的DR(DetectionRate)以及较低的FR。算法CEBOM、ICBOM和SNNOM挖掘到的都是全局异常，但由于现实世界复杂多变，所获得的数据集往往不完整，特别是在动态数据流环境下，数据具有时间特性

8、，且不断流逝，由此基于“在线聚类、离线异常挖掘”的一思想，提出了两种不同模型下的混合属性数据流异常挖掘算法DMDSOM和SWMSOM。算法DMDSOM基于衰减模型，在线维护具有时