高维空间中的离群点发现

《高维空间中的离群点发现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1000-9825/2002/13(02)0280-11©2002JournalofSoftware软件学报Vol.13,No.2高维空间中的离群点发现Ã魏藜,宫学庆,钱卫宁,周傲英(复旦大学计算机科学与工程系,上海200433)E-mail:{lwei,xqgong,wnqian,ayzhou}@fudan.edu.cnhttp://www.fudan.edu.cn摘要:在许多KDD(knowledgediscoveryindatabases)应用中,如电子商务中的欺诈行为监测,例外情况或离群点的发现比常规知识

2、的发现更有意义.现有的离群点发现大多是针对数值属性的,而且这些方法只能发现离群点,不能对其含义进行解释.提出了一种基于超图模型的离群点(outlier)定义,这一定义既体现了“局部”的概念,又能很好地解释离群点的含义.同时给出了HOT(hypergraph-basedoutliertest)算法,通过计算每个点的支持度、隶属度和规模偏差来检测离群点.该算法既能够处理数值属性,又能够处理类别属性.分析表明,该算法能有效地发现高维空间数据中的离群点.关键词:数据挖掘;离群点;超图模型;聚类中图法分类号:TP311文献

3、标识码:AKDD(knowledgediscoveryindatabases)是从大量数据中发现正确的、新颖的、潜在有用并能够被理解的[1]知识的过程.现有的KDD研究大多集中于发现适用于大部分数据的常规模式.但在一些应用中,如电子商务和金融服务领域中的欺诈等犯罪行为监测,有关例外情况的信息比常规模式更有价值.目前,这样的研究正得到越来越多的重视.[2][3][4][5][6][7][8]KDD中多数聚类算法(CLARANS,DBSCAN,BIRCH,STING,WaverCluster,DenClue,CLIQ

4、UE)能够发现一些例外情况.但是,因为聚类算法的主要目标是发现簇,而不是发现离群点(outlier),聚类算法或者对这些例外情况不敏感,或者忽视这些例外情况.最近,有一些研究是专门针对离群点发现的,例如文献[9~13].现有的离群点发现方法大多是针对数值属性的,而且只能发现离群点,不能对其含义进行解释.本文提出了一种基于超图模型的离群点检测方法HOT(hypergraph-basedoutliertest),它具有如下特点：·既能够处理数值属性,又能够处理类别(categorical)属性；·能有效并且高效地处理

5、高维数据；·离群点是在“窗口”中定义的,而窗口中的其他点与该点有许多相似之处,既体现了数据的局部性,又体现了属性的局部性,同时也能很好地解释离群点的物理含义——正是窗口规定的这些属性造成了它的离群.本文第1节简单介绍了超图聚类,传统的离群点发现方法和针对高维数据的离群点发现方法.第2节详细描述了发现离群点的问题,并给出了支持度、隶属度和规模偏差的定义.寻找离群点的具体算法步骤及算法复杂度分析在第3节中给出.第4节讨论HOT算法的特点.第5节总结全文,并给出了本文的后续工作.Ã收稿日期:2001-04-20;修改日

6、期:2001-09-20基金项目:国家自然科学基金资助项目(60003016;60003008);国家重点基础研究发展规划973资助项目(G1998030404)作者简介:魏藜(1978－),女,江西南昌人,硕士生,主要研究领域为数据挖掘技术;宫学庆(1974－),男,黑龙江饶河人,讲师,主要研究领域为WEB数据管理,数据挖掘;钱卫宁(1976－),男,浙江上虞人,博士生,主要研究领域为数据挖掘,Web数据管理;周傲英(1965－),男,安徽人,博士,教授,博士生导师,主要研究领域为Web数据管理,数据挖掘.魏藜

7、等:高维空间中的离群点发现2811相关工作1.1超图模型聚类文献[14]提出了一种基于超图(hypergraph)模型的,对高维空间数据进行聚类的方法.该方法将数据集中的每一条记录看作超图中的一个点,把具有公共频繁项集的点归结到一条超边中,并用基于关联规则的概念来衡量超边的权重.因此,该方法能够将数据之间的关系映射到超图上,其中超边表示数据点之间的关系,超边的权重反映这种关系的强弱.建立了超图模型以后,使用超边分割方法,每次打断权重最小的超边,直到每个分割中的数据都密切相关为止,最终得到的分割就是聚类的结果.在进

8、行超边分割的同时,用点与簇之间的连通度来评价得到的簇,因此可以有效地排除噪声数据对聚类结果的影响.1.2传统的寻找离群点的方法[15]到目前为止,离群点还没有一个正式的、为人们普遍接受的定义.Hawkin的定义揭示了离群点的本质:“离群点的表现与其它点如此不同,不禁让人怀疑它们是由另外一种完全不同的机制产生的.”(“Anoutlierisanobservationthat