基于信息论的高维海量数据离群点挖掘

《基于信息论的高维海量数据离群点挖掘》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据第38卷第7期2011年7月计算机科学ComputerScienceV01．38No．7July2011基于信息论的高维海量数据离群点挖掘张净1’2孙志挥1宋余庆3倪巍伟1晏燕华3(东南大学计算机科学与工程系南京210096)1(江苏大学电气与信息工程学院镇江212001)2(江苏大学计算机科学与通信工程学院镇江212001)3摘要针对高维海量数据集离群点挖掘存在“维数灾难”的问题，提出了基于信息论的高维海量数据的离群点挖掘算法。该算法采用属性选择，去除冗余属性降维。利用信息熵作为离群点判断的度量标准，消除

2、距离和密度量纲的弊端。在真实数据集上的实验结果表明，算法对高维海量数据离群点挖掘是有效可行的，其效率和精度得到了明显提高。关键词离群点挖掘，信息论，属性选择，熵，互信息中图法分类号TP311文献标识码AOutlierMiningoftheHigh-dimensionDatasetsBasedonInformationTheoryZHANGJin91’2SUNZhi-huilSONGYu-qing—NIWei—weilYANYan-huaa(DepartmentofComputerScienceandEngineer

3、ing，SoutheastUniversity，Nanjing210096，China)1(CollegeofElectronicandInformationEngineering，JiangsuUniversity，Zhenjiang212001，China)z(CollegeofComputerScienceandTelecommunicationsEngineering，JiangsuUniversity，Zhenjiang212001。China)3AbstractPhenomenaof“curseofdi

4、mensionality”deterioratelotsofexistingoutlierminingalgorithmsvalidity．Con—cerningthwproblem，theoutlierminingalgorithmofhigh-dimensionandlargedatasetsbasedoninformationtheorywasproposed．Thisalgorithmusedtheconceptofinformationentropyandthemutualinformationinthe

5、informationtheory，carriedonthefeatureselectionafterusingestimatedmutualinformationvalueobjectivebasisentropypowersorting，andeliminatedredundantattributefordimensionalityreduction．OutlierminingusinginformationentropyasameasurestandardtOjudgeeliminatedthedrawbac

6、ksofdistanceanddensitymetric．Theexperimentalresultintherealdatasetsindicatesthatthealgorithmforoutliermininginhigh-dimensionalnlassdataiseffectiveandfeasible，itsefficiencyandaccuracyaresignificantlyimproved．KeywordsOutliermining，Informationtheory，Featureselect

7、ion，Entropy，Mutualinforrnation1引言近年来随着应用的不断深入，基于数据挖掘概念的离群点挖掘算法取得了不少重要的成果，例如：Knorr等人提出的基于距离的算法FindALLOutsD[¨、面向大规模数据离群点挖掘算法FindOut[2]、Breuning等人提出的带离群度的离群点挖掘算法LOF(10caloutlierfactor)[3]和Papadimitirou等人提出的LOCI(10calcorrelationintegral)[4]等。这些算法对于一般低维度数据具有良好的性能。但

8、当数据维度较高时，这些算法在“维度灾难”的存在下，准确性和效率受到了严重的影响。目前，一些研究采用属性选择降维来解决高维问题。属性选择是指从已知的特征属性中，按照某一准则寻找特征子集，通过删除一些冗余的、不相关的属性降低数据集的维数、提高运行效率，同时改善算法性能，提高挖掘准确性和效率。在离群点挖掘算法中目前使用最多的属性选择方法就是子空间数据挖掘，例如：A