一种基于图论方法的大规模数据集离群数据挖掘方法

技术领域

本发明涉及计算机模式识别及机器学习技术领域，具体涉及一种基于图论方法的大规模数据集离群数据挖掘方法。

背景技术

离群数据是指在大量数据存在的一些与数据的一般行为或模型不一致的数据。离群数据的产生一般认为有两种原因：

1)度量或执行错误所导致，对这类型离群数据的筛选，可以从大量数据中筛选出杂质或存在问题的数据，进而提高数据的总体质量。

2)固有的数据变异性的结果，这类型数据的客观存在决定了对该类型离群数据筛选的重要性。例如在科研数据发现客观存在的一些未知的离群数据，可以很好的提高相关理论的研究。

随着数据的不断积累及数据的规模不断的增大，传统离群数据挖掘算法利用现有计算条件在其中筛选离群数据越发地困难。

发明内容

本发明要解决的技术问题是：针对此问题，本发明提供了一种从基于图论方法的大规模数据集离群数据挖掘方法，其特征在于利用样本间的距离信息建立无环图，然后以此图为基础逐步通过裁剪图的方法删减图中的边，通过多次迭代后图中度为0的节点对应的样本即为本方法筛选的离群数据。本发明的方法可应用于各种离群数据挖掘的应用中。

本发明所采用的技术方案为：

一种基于图论方法的大规模数据集离群数据挖掘方法，的方法删减图中的边，通过多次迭代后图中度为0的节点对应的样本即为本方法筛选的离群数据。

所述无环图为基于距离的无向图，图中节点为数据集中的样本，边的权值为两个节点对应样本之间的距离。

所述方法包括以下步骤：

1)数据预处理

该步目的是对数据进行预处理，消除数据间的不一致性同时归一化各个数据，包括的具体操作有数据清理、数据集成、数据变换、数据归约等；

2)特征选取与变换

对于后续步骤来说，样本数据的某些属性并不是必须的；同时大量的属性导致高维空间中低密度甚至空洞的属性空间，这使得后续数据的归纳及结果的产生变的相对困难，因此需要对样本数据在保证保持尽量多信息的情况下，进行特征选取与变换；特征选取是从所有属性筛选去掉对后续操作贡献较小甚至于没有贡献的属性；特征变换是利用当前属性通过变换得到新特征空间的属性；

3)构建距离图G

假设数据集中共有样本n个，图G中共包含n个节点，包含条边，假设该图对应的链接矩阵为:

$>\mathrm{GM}=\left(\begin{array}{cccccc}0& d_{12}& ...& d_{1j}& ...& d_{1n}\\ d_{21}& 0& ...& d_{2j}& ...& d_{2n}\\ ...& ...& 0& ...& ...& ...\\ d_{i1}& d_{i2}& ...& d_{\mathrm{ij}}& ...& d_{\mathrm{in}}\\ ...& ...& ...& ...& 0& ...\\ d_{n1}& d_{n2}& ...& d_{\mathrm{nj}}& ...& 0\end{array}\right)$>

按照上述定义，矩阵中元素的取值：

d_ij＝distance(D_i,D_j)

其中，样本本身的距离定义为0，假定数据集中样本间的最大距离为1；

4)筛选离群数据

通过迭代逐渐裁剪距离图，进而搜寻出其中的离群数据；裁剪的目的是根据全体样本间的距离,逐步裁剪图中绝大部分的节点，裁剪方法为：

[1].从矩阵GM，选择1个距离最大的边；

[2].去掉图G中对应的边；

[3].迭代终止条件：

a)图G的联通子图个数小于某个阈值t1；

b)删除的最小距离已小于某个阈值t2；

c)度为0的节点到达一定个数k；

最终图G中度为0对应的样本数据即为筛选出来的离群数据。

t1、t2、k的取值可以根据实际情况的要求确定。

为保证流程的一致性及中间结果的可复用性，所述方法采用统一的开发编程语言来完成。

所述方法距离的定义是灵活的，可以采用欧氏距离、曼哈顿距离、余弦距离等，考虑到余弦距离计算时更简单且快速，优选使用余弦距离。

本发明的有益效果为：

本发明分类方法可应用于各种离群数据挖掘的应用中，适用于搜寻全局离群数据。

说明书附图

图1为本发明方法流程图。

具体实施方式

下面根据说明书附图，结合具体实施方式对本发明进一步说明：

一种基于图论方法的大规模数据集离群数据挖掘方法，的方法删减图中的边，通过多次迭代后图中度为0的节点对应的样本即为本方法筛选的离群数据。

所述无环图为基于距离的无向图，图中节点为数据集中的样本，边的权值为两个节点对应样本之间的距离。

如图1所示，所述方法包括以下步骤：

1)数据预处理

该步目的是对数据进行预处理，消除数据间的不一致性同时归一化各个数据，包括的具体操作有数据清理、数据集成、数据变换、数据归约等；

2)特征选取与变换

对于后续步骤来说，样本数据的某些属性并不是必须的；同时大量的属性导致高维空间中低密度甚至空洞的属性空间，这使得后续数据的归纳及结果的产生变的相对困难，因此需要对样本数据在保证保持尽量多信息的情况下，进行特征选取与变换；特征选取是从所有属性筛选去掉对后续操作贡献较小甚至于没有贡献的属性；特征变换是利用当前属性通过变换得到新特征空间的属性；

3)构建距离图G

假设数据集中共有样本n个，图G中共包含n个节点，包含条边，假设该图对应的链接矩阵为:

$>\mathrm{GM}=\left(\begin{array}{cccccc}0& d_{12}& ...& d_{1j}& ...& d_{1n}\\ d_{21}& 0& ...& d_{2j}& ...& d_{2n}\\ ...& ...& 0& ...& ...& ...\\ d_{i1}& d_{i2}& ...& d_{\mathrm{ij}}& ...& d_{\mathrm{in}}\\ ...& ...& ...& ...& 0& ...\\ d_{n1}& d_{n2}& ...& d_{\mathrm{nj}}& ...& 0\end{array}\right)$>

按照上述定义，矩阵中元素的取值：

d_ij＝distance(D_i,D_j)

其中，样本本身的距离定义为0，假定数据集中样本间的最大距离为1；

4)筛选离群数据

通过迭代逐渐裁剪距离图，进而搜寻出其中的离群数据；裁剪的目的是根据全体样本间的距离,逐步裁剪图中绝大部分的节点，裁剪方法为：

[1].从矩阵GM，选择1个距离最大的边；

[2].去掉图G中对应的边；

[3].迭代终止条件：

a)图G的联通子图个数小于某个阈值t1；

b)删除的最小距离已小于某个阈值t2；

c)度为0的节点到达一定个数k；

最终图G中度为0对应的样本数据即为筛选出来的离群数据。

t1、t2、k的取值可以根据实际情况的要求确定。

为保证流程的一致性及中间结果的可复用性，所述方法采用统一的开发编程语言来完成。

所述方法距离的定义是灵活的，可以采用欧氏距离、曼哈顿距离、余弦距离等，考虑到余弦距离计算时更简单且快速，优选使用余弦距离。

以上实施方式仅用于说明本发明，而并非对本发明的限制，有关技术领域的普通技术人员，在不脱离本发明的精神和范围的情况下，还可以做出各种变化和变型，因此所有等同的技术方案也属于本发明的范畴，本发明的专利保护范围应由权利要求限定。