一种基于线性规划的孤立点检测方法

摘要：

孤立点检测是数据挖掘中的重要问题,可以发现不具备一般特性的数据,进而发现潜在的有用信息.现有的孤立点检测算法对于孤立点组成小集群的情形,一般不能正确检出.针对这一问题,提出一种新的基于线性规划的孤立点检测方法,该方法基于一个简单的事实:紧邻的两个数据点,必然同时为孤立点或正常点.首先建立待检测数据点的图模型,通过构造顶点能量模型和边模型,建立孤立点检测问题的马尔科夫模型,之后通过求解线性规划问题,得到该模型的最优解,进而得到孤立点检测结果.最后,使用一个合成数据集和三个真实数据集进行实验,验证本文所提出的算法,实验结果表明,提出的算法对于普通数据集和含有孤立点组成小集群的数据集,都能够正确地检出,且具有较高的检测正确率.

关键词：线性规划、孤立点检测、马尔科夫模型

所属期刊栏目：20

分类号：TP27(自动化技术及设备)

资助基金：国家973重大基础研究计划2011CB302400

在线出版日期：2014-11-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：1123-1126,1130