一种基于加权KNN的大数据集下离群检测算法_王茜(4)

大数据,数据挖掘

是离群点的数据点。运用本算法，文献［和传统ＫＮＮ算法寻找数据集中离群７］点。实验结果显示与传统的ＫＮＮ方法及只用权重来判断离离群检测的准确度为９而传统的群点的标准相比较，８％，且只用权重做判断标准时离群检测的ＫＮＮ方法只有９５％，精度为９６％。实验证明我们的方法更具精确度。

结束语　本文给出了一种基于加权ＫＮＮ的离群点挖掘通过优化候选划分单元提高算法的效率，并通过实验证算法，

明了算法的有效性。由于ＫＮＮ找到的是前ｎ个与第ｋ个邻居距离最大的点，而一些局部离群点却难以找到，以后的研究方向是使用一种聚类算法把整个数据集聚集成密度分布均匀的不同块，在每块上应用本文离群点挖掘的方法来找到离群点，这样就能有效地找到局部离群点。

４　实验与结果

在这部分，使用实验来比较我们的算法与传统的ＫＮＮ，算法。所有的实验采用平台为Ｃ内存为ｏｒｅ２Ｄｕｏ２．００ＧＨｚ　　操作系统为Ｗ２ＧＢ的ＰＣ，ｉｎｄｏｗｓＸＰ。　

（实验１算法的有效性）实验数据集为二　如图１所示，维模拟数据，包含１分布于１２００条记录，００＊１００的区域中。实验中最近邻居参数ｋ＝１离群点参数ｎ＝１０，２。与传统的实验结果如图１所示，算法能找到前１ＫＮＮ算法相比，２个离群点

。

参考文献

［］Ｂ［：１ａｒａｎｅｔｔＶ，ＬｅｗｉｓＴ．ＯｕｔｌｉｅｒｉｎＳｔａｔｉｓｔｉｃａｌＤａｔａＭ］．Ｎｅｗ　Ｙｏｒｋ　　　　　

，Ｊｏｈｎ　Ｗｉｌｅ１９９４ｒｅｓｓｙｐ　

［］Ｊ，２ｏｈｎｓｏｎＴ，ＫｗｏｋＩＮＲ．ＦａｓｔＣｏｍｕｔａｔｉｏｎｏｆ２ｉｍｅｎｓｉｏｎａｌ　　　　　－Ｄｇｐ　

图１　包含１２个离群点的二维数据集

Ｃｏｎｔｏｕｒｓ［Ｃ］∥Ｐｒｏｃｏｆ４ｔｈ．Ｉｎｔ．Ｃｏｎｆ．ｏｎＫＤＤ．ＮｅｗＤｅｔｈ　　　　ｐＹｏｒｋ，１９９８：２２４２２８－

［］Ｂ３ｒｅｕｉｎＭ　Ｍ，ＫｒｉｅｅｌＨ　Ｐ，ＮＲＴ．ＬＯＦ：Ｉｄｅｎｔｉｆｉｎｄｅｎｓｉｔ　　ｇｇｇｙｇｙ　　　

［ｂａｓｅｄｌｏｃａｌｏｕｔｌｉｅｒｓＣ］ｒｏｃｏｆＡＣＭ　Ｃｏｎｆｅｒｅｎｃｅ．１９９６：９３１０４　　∥Ｐ　　－［］Ｂ４ｉｒａｎｔＤ，ＫｕｔＡ．Ｓａｔｉｏｔｅｍｏｒａｌｏｕｔｌｉｅｒｄｅｔｅｃｔｉｏｎｉｎｌａｒｅｄａｔａ　　－　　　　　－ｐｐｇ

［ｂａｓｅｓＣ］ＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏＩｎｔｅｒｆａｃｅｓ．２００３：１７９１８４∥　－ｇｙ　［］Ｋ５ｎｏｒｒＥ，ＮＲ．Ａｌｏｒｉｔｈｍｓｆｏｒｍｉｎｉｎｄｉｓｔａｎｃｅｂａｓｅｄｏｕｔｌｉｅｒｓｉｎ　　　　　ｇｇｇ　　

ｔｈ　［，ｌａｒｅｄａｔａｓｅｔｓＣ］ｒｏｃｏｆｔｈｅ２４ＣｏｎｆｏｎＶＬＤＢ．Ｎｅｗ　Ｙｏｒｋ　∥Ｐ　　　　　ｇ

（实验２算法的执行时间）此　实验采用一组模拟数据，数据集上数据产生的概率都相同，且范围都一致。数据量Ｎ的大小从１数据的维数确定为２，实０００００到５０００００，４和８，需要找到的离群点数ｎ＝１算验设定的邻居参数ｋ＝１００，００，法执行时间与数据量的关系如图２所示。算法对数据量的大小和数据维数的大小具有线性的时间复杂度。通过计算候选划分，使用一些剪枝方法避免了计算数据集中大量的非离群点，从而节省了时间

。

１９９８：３９２４０３－

［］Ｒ６ａｍａｓｗａｍＳ，ＲａｓｔｏｉＲ，ＫｕｓｅｏｋＳ．ＥｆｆｉｃｉｅｎｔＡｌｏｒｉｔｈｍｓｆｏｒ　　　　ｙｇｙｇ　

［ｏｕｔｌｉｅｒｓｆｒｏｍｌａｒｅｄａｔａｓｅｔｓＣ］ｒｏｃｏｆｔｈｅＡＣＭ　ＳＩＧ－ｍｉｎｉｎ　　　∥Ｐ　　　ｇｇ　ＭＯＤＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＭａｎａｅｍｅｎｔｏｆＤａｔａ．Ｎｅｗ　　　　　　ｇ，Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ２０００：９３１０４－

［］Ａ７ｎｉｕｌｌｉＦ，ＰｉｚｚｕｔｉＣ．ＯｕｔｌｉｅｒＭｉｎｉｎｉｎＬａｒｅＨｉｈｉｍｅｎｓｉｏｎａｌ　　　　　－Ｄｇｇｇｇ　

Ｓｅｔｓ［Ｃ］ｒｏｃｏｆｔｈｅＩＥＥＥＴｒａｎｓａｃｔｉｏｎＯｎＫｎｏｗｌｅｄｅＤａｔａ　∥Ｐ　　　　　　ｇＤａｔａＥｎｉｎｅｅｒ．ＶＯＬ．１７，２００５：１０４１４３７４Ａｎｄ　　－ｇ

［］Ｏ８ｓｔｅｒｍａｒｋＲ．ＡｆｕｚｚｖｅｃｔｏｒｖａｌｕｅｄＫＮＮａｌｏｒｉｔｈｍｆｏｒａｕｔｏ　　　　－　　－ｙｇ　

［ｍａｔｉｃｏｕｔｌｉｅｒｄｉｃｔｉｏｎＣ］ｒｏｃｉｎｔｈｅＡｌｉｅｄＳｏｆｔＣｏｍｕｔｉｎ．　　∥Ｐ　　　　　ｐｐｐｇ２００９：１２６３１２７２－

［］Ｌ，９ｅｅＣＰ，Ｌｉｎ　Ｗ－ＳＣｈｅｎＹ－Ｍ，ｅｔａｌ．ＧｅｎｅＳｅｌｅｃｔｉｏｎａｎｄｓａｍｌｅ　－　　　　　ｐ

ｏｎｍｉｃｒｏａｒｒｄａｔａｂａｓｅｄｏｎａｄａｔｉｖｅａｌｏｃｌａｓｓｉｆｉｃａｔｉｏｎｅｎｅｔｉｃ　　　　　　　－ｙｐｇｇ　／［ｒｉｔｈｍｋｎｅａｒｅｓｔｎｅｉｈｂｏｒｍｅｔｈｏｄＣ］ｒｏｃｉｎｔｈｅＥｘｅｒｔＳｓ－　　∥Ｐ　　　　－ｇｐｙｔｅｍｓｗｉｔｈＡｌｉｃａｔｉｃａｔｉｏｎｓ．２０１０：０７　　ｐｐ

［］Ｍ１０ａｉｅｒＭ，ＨｅｉｎＭ，ｖｏｎＬｕｘｂｕｒＵ．Ｏｔｉｍａｌｃｏｎｓｔｒｕｃｔｉｏｎｏｆｋ　　　　　　－ｇｐ　

［ｎｅａｒｅｓｔｎｅｉｈｂｏｒｒａｈｓｆｏｒｉｄｅｎｔｉｆｉｎｎｏｉｓｃｌｕｓｔｅｒＣ］ｒｏｃ－　　　∥Ｐｇｙｇｙｇｐ　　ｔｈｅＴｈｅｏｒｅｔｉｃａｌＣｏｍｕｔｅｒＳｃｉｅｎｃｅ．２００９：１７４９１７６４ｉｎ　　　　－ｐ

［］Ｒ，，１１ｅｎＤｏｎｅｉＲａｈａｉＩＰｅｒｒｉｚｏＷ．Ａｖｅｒｔｉｃａｌｄｉｓｔａｎｃｅｂａｓｅｄｏｕｔ　－ｍ　　　　－　－ｇ

ｌｉｅｒｄｅｔｅｃｔｉｏｎｍｅｔｈｏｄｗｉｔｈｌｏｃａｌｒｕｎｉｎＣ］ｒｏｃｏｆＣＩＫＭ’　　　　　∥Ｐ　　ｐｇ［，０４．Ｗａｓｈｉｎｔｏｎ，ＤＣ，ＵＳＡ：ＡＣＭ　Ｐｒｅｓｓ２００４：２７９２８４－ｇ

［］Ｚ１２ｈａｎＴｉａｎ，ＲａｍａｋｒｉｓｈｎａｎＲ，ＬｉｖｎＭ．Ａｎｅｆｆｉｃｉｅｎｔｄａｔａｃｌｕｓｔｅ　　　　－ｇｙ　　

ｒｉｎｍｅｔｈｏｄｆｏｒｖｅｒｌａｒｅｄａｔａｂａｓｅｓ［Ｃ］ｒｏｃｅｅｄｉｎｓｏｆｔｈｅ　　　∥Ｐ　　ｇｙｇｇ　　ＡＣＭ　ＳＩＧＭＯＤＣｏｎｆｅｒｅｎｃｅｏｎＭａｎａｅｍｅｎｔｏｆＤａｔａ．１９９６：１０３　　　　　－ｇ１１４

［］ｈ：／／／／／１３ｔｔａｒｃｈｉｖｅ．ｉｃｓ．ｕｃｉ．ｅｄｕｍｌｄａｔａｓｅｔｓＢｒｅａｓｔ＋Ｃａｎｃｅｒ＋Ｗｉｓ－ｐ

ｃｏｎｓｉｎ＋％２８Ｏｒｉｉｎａｌ％２９ｇ

［］王越，刘亚辉，徐传运．基于距离和的孤立点用户意义分析算法１４

］（）：及应用［重庆理工大学学报：自然科学版，Ｊ．２０１０，２４１５５５９－

图２　算法扩展性测试

（实验３与传统ＫＮＮ算法在执行时间上的比较）　实验用一组模拟数据，数据集上数据产生的概率都相同，且范围都数据的维数为一致。数据量Ｎ的大小从１０００００到５０００００，实验设定的参数ｎ和ｋ都为１虽２，００。实验结果如图３所示，然我们的基于划分算法Ｗ－ＫＮＮ与传统ＫＮＮ的基于划分的

算法都具有与数据量的大小Ｎ线性的时间复杂度，但我们通过性质１进一步约减候选划分中不可能包含离群点的划分，缩短了算法的执行时间

。

图３　同原算法执行时间比较

（实验４与传统ＫＮＮ算法在精确性上的比较）　实验数

［３］

），据集为Ｂ此数ｒｅａｓｔＣａｎｃｅｒＷｉｓｃｏｎｓｉｎ（ＯｒｉｉｎａｌＤａｔａＳｅｔ１　　　ｇ

据集包含６每个实例包含１９９个实例，０个属性。数据集中良性数据有４恶性数据有２为了使恶性数据成为离６１条，３８条，群数据，随机去除其中的两百条恶性数据。设置参数ｎ＝４５，

·１８０·