基于直方图和fp增长离群点关联规则挖掘

《基于直方图和fp增长离群点关联规则挖掘》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、MiningAssociationRulesamongOutliersBasedonHistogramandFP-GrowthADissertationSubmittedtoNanjingUniversityofFinanceandEconomicsFortheAcademicDegreeofMasterofEconomicsBYLiLongjiaoSupervisedbyProfessorChengGuodaSchoolofNanjingUniversityofFinanceandEconomicsNovem

2、ber2012学位论文独创性声明本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明并表示了谢意。作者签名：日期：学位论文使用授权声明本人完全了解南京财经大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此规定。作者签名：导

3、师签名：日期：摘要由于高维空间数据的稀疏性和维灾问题使得高维空间离群点的挖掘和分析始终是数据挖掘的难点之一，本文在现有高维空间离群点挖掘算法的基础上，提出了用数据直方图和FP增长(FrequentPattern-Growth)相结合的方法挖掘出现离群点的维之间的关联规则，从而能更好地认识离群点和解释离群点之间的关系。到目前为止，人们对高维离群点的挖掘提出了许多方法，比如数据约减、投影变换、特征选取等，但是在这些方法中也存在着各种不足和问题，其中不仅存在计算复杂度比较大问题，而且对离群点的产生机制、离群点之间的关

4、系缺乏深入的研究，为此本文在这两方面做了些工作，针对上述问题提出了基于直方图和FP增长的离群点关联规则挖掘的方法。该方法首先计算每一维上数据点的KNN(K-NearestNeighbors)距离，形成直方图，利用直方图判断在该维上哪些点是全局离群点，哪些点是局部离群点和边缘离群点，从而降低计算复杂度，然后用FP增长算法挖掘满足一定支持度和置信度的频繁出现离群点的维之间的关联规则，用于解释离群点之间的关系。利用本文提出的方法对合成数据和现实数据进行了详细的分析，实验表明该方法不仅提高了计算效率，而且挖掘出来的结果

5、能够很好地解释离群点产生的原因，揭示离群点发生的规律，这些都表明该方法不仅有效，而且具有很强的现实意义。关键词：数据挖掘；高维离群点；KNN距离；直方图；FP增长；离群点关联规则IABSTRACTOutlierdetectinginhigh-dimensionalspaceisoneofthedifficultissuesintheareaofdataminingbecauseofthesparsenessandthedimensionalitycurse.Basedontheexistingmethodson

6、highdimensionalspace,anewoutlierminingmethodbasedonhistogramandFP(frequent-pattern)growthtodiscovertheassociationrulesamongtheoutliersispresentedinthispaper,whichcanexplaintheoutliersandtherelationshipamongtheoutliersbetter.Inrecentyears,manyresearchershavef

7、ocusedonoutlierdetectinginhigh-dimensionalandverylargedatasetsandproposedmanyapproaches,suchasdatareduction,projection,featureselectionandsoon.Theexistingmethodsdoimprovesometraditionalapproaches,buttherearesomeproblemsanddrawbacks.Besidesthehighcostofcomput

8、ation,thecauseofoutliersandtheirgenerationmechanismhavenotbeenstudieddeeply.Tosolvetheproblems,anewoutlierminingmethodbasedonhistogramandFP(frequent-pattern)growthtodiscovertheassociationrulesin