一种基于自然共享最近邻居搜索的发现簇和离群点的算法

技术领域

本发明属于数据挖掘领域，尤其是涉及一种基于自然共享最近邻居搜索的发现簇和离群点的算法。

背景技术

随着数据爆炸性增长、云计算等大数据技术不断发展，人们对数据挖掘技术越来越重视。而簇和离群点的发掘是数据挖掘中一项非常重要的技术，它能够帮助发现有价值的信息，从而有效地对数据进行分析。

目前存在一种自然最近邻居算法，该算法不需要用户指定最近邻个数，自然形成邻域关系，从而对数据进行聚类，也已经有算法在聚类的基础上进行离群点检测。但已有的自然最近邻居算法中，自然邻居的定义及搜索算法的终止条件不够科学，导致数据的聚类效果不好，离群点检测精度不高，基于此，本发明提出一种基于自然共享最近邻居搜索的发现簇和离群点的算法，该算法中将自然邻居定义进行优化，形成共享最近邻居定义，并改善了搜索终止条件，使发现的邻居关系更加科学，从而使聚类结果更符合数据的真实分布，检测到的离群点准确度更高。

发明内容

为了解决上述问题，本发明提出了一种基于自然共享最近邻居搜索的发现簇和离群点的算法，其特征在于，所述算法的具体步骤为

步骤1、对植物各种生长参数组成的数据集D进行自然最近邻居搜索，每一个维度代表一种生长参数，且数据集的每个分类能从其它分类中先行分离出来；当发现数据集中没有共享最近邻居的点的数量不再变化时搜索结束，得到搜索最近邻个数n；根据提出的自然共享邻居定义，计算每个对象在n近邻下得到的自然共享最近邻居关系；

步骤2、基于共享最近邻的自然邻居搜索算法确定了每个对象的自然共享最近邻域关系，根据该自然共享最近邻居关系，对数据进行聚类和离群点判别。

所述自然共享最近邻居定义为若对象X认为对象Y是其近邻，Y认为X是其近邻，且X的近邻与Y的近邻至少有一个相同，则X和Y互为自然共享最近邻居。

所述步骤1中对数据集进行自然最近邻居搜索过程为

(1)将最近邻个数k设置为1；

(2)搜索数据集中每个对象的最近的k个邻居；

(3)搜索完成后计算每个对象的共享最近邻居；若对象a的k近邻中包含对象b，且b的k近邻中包含a，且a的k近邻与b的k近邻中有一个同样的对象，则成b是a的共享最近邻居；

(4)计算共享最近邻居为0的对象的个数n1；

(5)使k＝k+1，返回执行步骤(2)，计算此时的共享最近邻居为0的对象的个数n2；

(6)若n2＝n1，则停止搜索，得到的最终的k即为搜索算法中的最近邻居个数，在该值下计算每个对象的共享最近邻居，得到的就是自然共享最近邻居关系；否则将n1的值更新为此刻n2的值，返回步骤(5)。

所述步骤2中聚类过程为：

(1)初始数据集D中的所有点均未被标记，随机取数据集中的一点，将该点标记，同时将该点与它的自然最近邻形成一个类c(k)；

(2)随机取类c(k)中未被标记的点，将该点标记并将它的自然最近邻加入到该类中，直到该类中的所有点都被标记，则k＝k+1；

(3)随机取数据集中未被标记的点重复上述过程直到数据集中所有点被标记，则得到最终聚类结果。

所述步骤2中离群点判别过程为

将聚类得到的k个类从小到大排列，若第i个类c(i)满足条件一|c(i)|＜10％|D|和条件二则认为c(i)为离群点或离群簇；

条件一是将个数较少的簇认定为离群点或离群簇，而条件二是在数据集被分为很多个小簇时能避免这些小簇都被视为离群对象。

有益效果

针对现有技术的不足，本发明的目的是提供一种基于自然共享最近邻居搜索的发现簇和离群点的算法，本算法中提出一种新的共享最近邻居关系和自然邻居搜索终止条件，解决了现有算法因为自然邻居关系定义不够严密及搜索条件不够科学而引起的聚类效果不好和离群点检测精度不高的问题。

附图说明

图1为本发明一种基于自然共享最近邻居搜索的发现簇和离群点的算法的流程图。

具体实施方式

下面结合附图，对本发明作详细说明。图1为本发明一种基于自然共享最近邻居搜索的发现簇和离群点的算法的流程图。

一种基于自然共享最近邻居搜索的发现簇和离群点的算法，其特征在于，所述算法的具体步骤为

步骤1、对数据集进行自然最近邻居搜索，当发现数据集中没有共享最近邻居的点的数量不再变化时搜索结束，得到搜索最近邻个数n；根据提出的自然共享邻居定义，计算每个对象在n近邻下得到的自然共享最近邻居关系；

步骤2、基于共享最近邻的自然邻居搜索算法确定了每个对象的自然共享最近邻域关系，根据该自然共享最近邻居关系，对数据进行聚类和离群点判别。

所述自然共享最近邻居定义为若对象X认为对象Y是其近邻，Y认为X是其近邻，且X的近邻与Y的近邻至少有一个相同，则X和Y互为自然共享最近邻居。

所述步骤1中对数据集进行自然最近邻居搜索过程为

(1)将最近邻个数k设置为1；

(2)搜索数据集中每个对象的最近的k个邻居；

(3)搜索完成后计算每个对象的共享最近邻居；若对象a的k近邻中包含对象b，且b的k近邻中包含a，且a的k近邻与b的k近邻中有一个同样的对象，则成b是a的共享最近邻居；

(4)计算共享最近邻居为0的对象的个数n1；

(5)使k＝k+1，返回执行步骤(2)，计算此时的共享最近邻居为0的对象的个数n2；

(6)若n2＝n1，则停止搜索，得到的最终的k即为搜索算法中的最近邻居个数，在该值下计算每个对象的共享最近邻居，得到的就是自然共享最近邻居关系；否则返回步骤(5)。

所述步骤2中聚类过程为：

(1)初始数据集D中的所有点均未被标记，随机取数据集中的一点，将该点标记，同时将该点与它的自然最近邻形成一个类c(k)；

(2)随机取类c(k)中未被标记的点，将该点标记并将它的自然最近邻加入到该类中，直到该类中的所有点都被标记，则k＝k+1；

(3)随机取数据集中未被标记的点重复上述过程直到数据集中所有点被标记，则得到最终聚类结果。

所述步骤2中离群点判别过程为

将聚类得到的k个类从大到小排列，若第i个类c(i)满足条件一|c(i)|＜10％|D|和条件二则认为c(i)为离群点或离群簇；

条件一是将个数较少的簇认定为离群点或离群簇，而条件二是在数据集被分为很多个小簇时能避免这些小簇都被视为离群对象。

数据集采用UCI标准数据集中IrisPlants数据集。该数据集包含3个类共150个对象，每个对象有5个维度，本发明采用前两个类作为簇，在第三类中挑选出9个点作为离群点和离群簇，用本发明提出的算法对该数据集进行簇和离群点的检测，以验证该算法的有效性。

1、对该数据集进行自然最近邻居搜索，当发现数据集中没有共享最近邻居的点的个数不再变化时算法结束，得到搜索最近邻个数为11；

2、根据提出的自然共享邻居定义，计算每个对象在11近邻下得到的自然共享最近邻居关系；

3、基于自然共享最近邻居关系，对数据进行聚类，得到数量为49及50的两个类，1个离群点和一个数量为9的离群簇。

需要说明的是，得到的1个离群点并不是误检，它是第一类中的42号对象，它虽然不是我们设置的离群点，但它是远离簇核心点的对象，属于局部离群点，因此用本发明算法得到的类和离群簇完全符合数据集的正常分布情况，聚类精确度和离群点检测精确度均为100％。

而用基于已有的自然邻居搜索的聚类和离群检测对数据进行聚类，得到数量为42及67的两个类，这个算法将第一类中的7个数据错误地分配到第二类中，说明聚类效果出现偏差，不符合数据真实分布；此外，该方法没有检测出含有9个点的离群簇，而是将离群簇错误地分配到第二类中，因此该方法不能有效地检测出离群点。

通过本发明提出的基于自然共享最近邻居搜索的发现簇和离群点的算法与已有算法进行对比发现，本文算法能提高聚类效果和检测精度。