一种基于谱聚类的离群点检测方法

摘要

本发明公开了一种基于谱聚类的离群点检测方法，首先选取一个含有m个离群点的疾病数据集R，计算疾病数据集R中每个点pi的k个近邻，将pi和它的k个近邻记为S，计算小数据集S中两两点对之间的相似度，组成相似度矩阵，根据相似度矩阵计算出拉普拉斯矩阵Lap，计算拉普拉斯矩阵Lap的特征值，记为ev_arri，将疾病数据集R中每个元素对应的特征值存入一个数组array中，对于array中的每一个元素，计算其信息熵或基尼指数作为离群点得分，对所有离群点得分进行排序，选出前m个离群点作为结果输出。本发明解决了现有技术中检测离群点的时间复杂度高，效果不太好的问题。

说明书

技术领域

本发明属于数据挖掘技术领域，具体涉及一种基于谱聚类的离群点检测方法。

背景技术

由于科技的发展，越来越多的数据出现在各行各业，对于大数据的处理分析变得越来越重要。离群点检测是数据挖掘领域的一项重要技术且有着广泛的应用，比如可以应用到机器学习，数据挖掘，医疗诊断，网络入侵检测等领域。然而，由于高维数据的维度灾难的问题，现有的很多离群点检测算法不能很好的处理高维数据。谱聚类是聚类算法的一种，能够有效的对高维数据进行聚类，从而能够解决维度灾难的问题。其基本原理是是把给定数据集划分成多个簇，使得相同簇中的点的相似度尽可能大，不同簇之间的相似度尽可能小。但是对于现实世界中的大量数据，时间复杂度比较高，因此对于大规模的数据集不适用。且目前的基于谱聚类的离群点检测算法的效果不是很好。

发明内容

本发明的目的在于提供一种基于谱聚类的用信息熵和基尼指数的方法来进行离群点检测的技术，同时用K最近邻的技术来减少计算次数，从而提高时间效率，解决了现有技术中检测离群点的时间复杂度高，效果不太好的问题。

本发明将用信息熵表示离群点得分的算法简记为IESA，用基尼指数表示离群点得分的算法记为GISA。

为达到上述目的，本发明采用如下技术方案：

一种基于谱聚类的离群点检测方法，首先选取一个含有m个离群点的疾病数据集R，计算疾病数据集R中每个点p

进一步地，具体包括以下步骤：

1)选取一个含有m个离群点的疾病数据集R作为测试数据集，定义一个数组array，用来存放特征值；

2)对于疾病数据集R中每一个点计算k个近邻点，组成一个k+1大小的小数据集S；

3)用高斯核函数求取小数据集S中两两点对之间的相似度，组成相似度矩阵simMatrix，根据simMatrix计算拉普拉斯矩阵Lap；

4)计算拉普拉斯矩阵Lap的特征值存入ev_arr

5)对于数据集中每个点，重复步骤2)-步骤4)；

6)根据信息熵和基尼指数的计算公式，计算array中每一个元素的信息熵或基尼指数作为对应数据点的离群点得分；

7)对所有离群点得分按照从大到小的顺序进行排序，选出前m个离群点作为结果输出。

进一步地，步骤2)中采用coverTree数据结构计算疾病数据集R中每一个点的k个近邻点。

进一步地，步骤3)中计算两个点之间相似度的计算公式为：

其中，x

其中，p表示点的序号，“|x-y|”表示两个点x和y之间的距离，k为预定义的参数，计算拉普拉斯矩阵的方法为：

其中，I是单位矩阵，simMatrix是上一步计算的相似度矩阵，D是对角矩阵，其中的每一个元素d

其中，n为小数据集S中的点数，w

进一步地，步骤6)中信息熵的计算公式为：

其中，S指的是当前这个点及其k个近邻所组成的小数据集，n是该小数据集S中的元素个数；p

进一步地，步骤6)中基尼指数的计算公式为：

与现有技术相比，本发明具有以下有益的技术效果：

1)本发明从离群点的特点出发，即离群点是数据中偏离大多数数据的点或与其他数据存在明显差异的点，利用信息熵和基尼指数的原理，对数据点定义离群点得分，从而能够较为准确的发现数据集中包含较多信息的点，即离群点。

2)通过在一些二维数据集上进行实验，同时和其他的离群点检测算法进行对比，本发明能够较好的检测出离群点和正常点。

3)选取了不同离群点数量的数据集进行测试，结果表明本发明对于离群点的数量没有限制，可以检测出数据集中任意数量的离群点。

4)本发明能够同时识别全局离群点和局部离群点，相比基于距离的和基于密度的离群点检测算法有较好的改进。

5)能够运用到医学疾病数据集上，用来检测异常数据，即是否患病。

附图说明

图1是在1个离群点数据集上的测试结果，其中(a)为KNN算法的结果，(b)为LOF算法的结果，(c)为ABOD算法的结果，(d)为OCSVM算法的结果，(e)为IESA算法的结果，(f)为GISA算法的结果；

图2是在多个离群点数据集上的测试结果，其中(a)为KNN算法的结果，(b)为LOF算法的结果，(c)为ABOD算法的结果，(d)为OCSVM算法的结果，(e)为IESA算法的结果，(f)为GISA算法的结果；

图3是在球形簇上的测试结果，其中(a)为KNN算法的结果，(b)为LOF算法的结果，(c)为ABOD算法的结果，(d)为OCSVM算法的结果，(e)为IESA算法的结果，(f)为GISA算法的结果；

图4是在不同类型离群点上的测试结果，其中(a)为KNN算法的结果，(b)为LOF算法的结果，(c)为ABOD算法的结果，(d)为OCSVM算法的结果，(e)为IESA算法的结果，(f)为GISA算法的结果；

图5是在真实疾病数据集上的测试结果。

具体实施方式

下面对本发明作进一步详细描述：

一种基于谱聚类的离群点检测方法，用K最近邻的技术来减少计算次数，可以提高时间效率；信息熵和基尼指数能够有效的对数据集中点的离群度进行评估，计算小规模数据的拉普拉斯矩阵的特征值的概率值评估一个数据点的离群度，通过对离群度排名来选出离群度较大的数据点作为离群点。

先计算数据集中每个点的k个最近邻，然后把每个点和它的k个最近邻作为输入集合，计算通过该集合的Laplacian(拉普拉斯)矩阵的特征值来分析这个数据集的谱结构。然后计算该集合的信息熵和基尼指数作为评价该集合对应数据点的离群分值。

对于计算K最近邻的方法：

本发明用cover Tree的数据结构来高效的计算高维数据集的k最近邻。

对于计算相似度矩阵：

本发明计算点与点之间的相似度，用两个新的高斯核函数进行计算，从而提高离群点检测的质量，计算方法如下：

其中，x

其中，p表示点的序号，“|x-y|”表示两个点x和y之间的距离，k为预定义的参数。计算拉普拉斯矩阵的方法为：

其中，I是单位矩阵，simMatrix是上一步计算的相似度矩阵，D是对角矩阵，其中的每一个元素d

其中，n为小数据集S中的点数，w

具体如下：

本方法通过计算数据点和它的k个近邻组成的数据集的特征矩阵的特征向量的信息熵和基尼指数来找到离群度较大的数据点。

1)选取一个含有m个离群点的数据集R作为测试数据集，定义一个数组array，用来存放特征值；

2)对于数据集R中每一个点计算k个近邻点，组成一个k+1大小的小数据集S；

3)求取S的相似度矩阵simMatrix，根据simMatrix计算拉普拉斯矩阵lapMatrix；

4)计算lapMatrix的特征值存入ev_arr

5)对于数据集中每个点，重复步骤2)-步骤4)；

6)根据信息熵和基尼指数的计算公式，计算array中每一个元素的信息熵或基尼指数作为对应数据点的离群点得分；

信息熵也叫信息增益，是一种属性选择度量方法，计算信息熵的公式为：

其中，S指的是当前这个点及其k个近邻所组成的集合，n是数据集S中的元素个数；p

基尼指数一般用来度量数据集的纯度，计算公式如下：

7)对所有离群点得分按照从大到小的顺序进行排序，选出前m个离群点作为结果输出。

实施例

选取4个二维数据集和1个真实的心脏病数据集作为测试对象，对比本发明中的算法和一些其他的离群点检测方法。将检测结果用图表示，其中正常点用实心圆表示，离群点用实心五角星表示。结果见图1-5。

1)选取一个包含1个离群点和三个均匀分布的簇的数据集，本数据集中的离群点是全局离群点，通过和KNN、ABOD、LOF、OCSVM等已有的离群点算法进行对比，来检测本发明的效果。算法在该数据集上的测试结果见附图1。由结果可以看出，我们的算法能够准确找到唯一的离群点，OCSVM算法不能准确找到离群点，反而误把边界点作为离群点输出。其他的四个算法也能找到该离群点。

2)选取一个含有五个离群点和四个长条状簇的数据集，测试上述6个算法在该数据集上的结果，ABOD把所有的点当做离群点来处理，OCSVM算法不能识别离群点，而是把一些边界点当做离群点。KNN，LOF和本发明中的两个算法能够准确的识别出5个离群点。

3)选取一个包含4个圆形簇以及4个离群点、一个包含3个点的离群簇作为测试数据集，LOF只能发现离群点，不能识别出离群簇；OCSVM可以识别出离群簇中的2个离群点，另一个离群点被认为是正常点；ABOD错误地把两个正常点当做离群点。KNN和本发明的算法能够较好的识别离群点和离群簇。

4)在包含局部离群点和全局离群点的数据集上测试算法。选取含有3个簇以及5个离群点，包括3个全局离群点和2个局部离群点的数据集。KNN不能很好的检测局部离群点。OCSVM不能检测出该数据中任意离群点，ABOD把所有数据点看做是离群点。LOF以及本发明中的算法能够较好的检测出任意类型的数据点。

5)选取UCI数据集上HeartDisease心脏病数据集作为真实数据集测试对象，对本发明中提到的算法效果进行测试。该数据集一共包含153个数据对象，其中有三个是离群点，即病人，其他150个数据表示正常人。对比KNN，LOF、ABOD、OCSVM算法，用precision-recall曲线进行评估，即横坐标表示精确度，纵坐标表示召回率。实验结果表明，本发明提出的算法能够较好的检测出病人。