一种高维数据异常检测方法

1.本发明属于数据处理技术领域，主要涉及一种数据集中异常数据检测方法，该方法根据数据集本身的特点，检测出数据集中异常的数据记录。异常检测可应用于银行欺诈检测、结构缺陷检测、系统健康检测、文本错误检测等很多领域。


背景技术：

2.目前，异常检测方法主要包括：通过概率分布进行异常检测，通过聚类进行异常检测，通过深度学习进行异常检测。
3.通过概率分布进行检测的理论基础是正常的数据分布是具有一定特点的，如果某个数据与正常的分布偏离较大，我们认为该数据很可能是不正常的，很可能就是异常值。这种方法能够很好利用数据的统计特性，在一定的领域表现较好，但该类方法需要对数据集进行统计分析，获取正常数据的分布特征，这个过程往往较困难，特别是对于数据量较大，数据维度较高的情况下，其运算代价较大。
4.通过聚类进行异常检测，首先对原始数据集进行聚类，然后根据每条记录距离聚类中心的距离来判断哪些数据是异常值，一般认为距离聚类中心较远的记录就是异常值。这种方法需要进行聚类，聚类的过程是比较耗时，且聚类数的多少对检测效果影响较大，目前对聚类数的确定没有统一的方法。
5.通过深度学习进行异常检测，主要通过训练一个深度神经网络来检测数据集中的异常值。就目前情况来看，这种方法多数情况下表现较好，但是，训练的神经网络高度依赖于样本数据集，对于不同类别的数据集上，很难训练出比较理想的网络模型，且训练网络的过程往往比较耗时。
6.综上所述，现存技术的主要问题是：计算量比较大，效率比较低。无论是采用统计、聚类还是深度学习的方法，进行异常检测时，计算量都比较大，尤其是对于高维数据，现有检测方法很难高效的进行异常检测。高维数据结构比较复杂，采用现有方法很难取得比较好的效果。
7.本发明基于随机抽样公开了以一种适用于高维数据的异常检测方法，该方法能够大大提高异常检测的效率。随机抽样大大提高了异常检测的效率，提高了异常检测的精度。


技术实现要素：

8.针对现有技术存在的问题，本发明公开了一种新的适用于高维数据的异常检测方法。
9.本发明：一种高维数据的异常检测方法，所述异常检测方法包括：
10.在高维数据上随机选择属性：随机在高维数据集上选择一个或多个属性(列),作为原始数据集的一次抽样，第i次抽样记为si，每个si称为原始数据集的一个样本，每个样本中可以包含原始数据集中的一个属性或多个属性的组合；
11.在每个样本上进行异常检测：若样本si抽取的数值属性，则对该样本中的数据进
行排序，求得si中记录2范数的最大值maxi和最小值mini，把区间[mini,maxi]平均分成kn个子区间，kn是随机从区间[|si|/20,|si|/10]随机选择的整数，|si|表示样本中记录的个数。统计2范数落在kn个子区间的记录数统计2范数落在kn个子区间的记录数做为该区间内包含记录的异常值打分；
[0012]
若样本si抽取的非数值属性，则首先随机选择一个记录作为基准记录r0，计算所有记录到该基准记录的距离，d
max
表示距离样本si中记录距离r0的最大距离，kc是从区间[|si|/20,|si|/10]随机选择的整数，把区间[0,d
max
]平均分成kc个子区间，根据记录与r0的距离所在的子区间，把样本si划分成kc个子类，计算每个子类的信息熵，作为该子类中包含元素的异常值打分；
[0013]
由不同的样本，得数据集中每条记录的多个异常值打分，求解异常值打分的加权和，作为判定数据集中每条记录是不是异常值的依据。
[0014]
进一步，在高维数据上随机选择属性，具体包括：
[0015]
输入：原始数据集r是数据集d中记录，r包含a1,a2,
…
,am个属性
[0016]
输出：抽样样本集
[0017]
算法：
[0018]
(1)s为空集
[0019]
(2)fori＝1tons其中ns表示需要产生的样本数
[0020]
(3)对数据集d中每记录r，随机选择a1,a2,
…
,am中一个或多个属性作为该记录的抽样记录
[0021]
(4)把所有抽样记录放入si[0022]
(5)把si放入s
[0023]
(6)endfor
[0024]
(7)返回s
[0025]
进一步，样本si抽取的数值属性，在每个样本上进行异常检测，具体包括：
[0026]
输入：样本si[0027]
输出：数据集中每条记录的异常值打分
[0028]
算法：
[0029]
(1)计算si中每条记录的2范数，2范数的最大值和最小值分别记为maxi，mini[0030]
(2)fori＝1ton
[0031]
(3)随机从区间[|si|/20,|si|/10]随机选择的整数kn
[0032]
(4)把区间[mini,maxi]平均分成kn个子区间
[0033]
(5)根据每条记录的2范数所在的子区间，把记录分开成kn个簇
[0034]
(6)计算每个簇中记录的个数ci，1/ci为该簇中每条记录的异常打分值
[0035]
(7)endfor
[0036]
(8)计算每个记录的∑1/ci作为记录的异常值最终打分
[0037]
进一步，样本si抽取的非数值属性，在每个样本上进行异常检测，具体包括：
[0038]
输入：样本si[0039]
输出：数据集中每条记录的异常值打分
[0040]
算法：
[0041]
(1)fori＝1ton
[0042]
(2)随机选择si中一条记录r
i0
[0043]
(3)计算其他记录与r
i0
的距离
[0044]
(4)kc是从区间[|si|/20,|si|/10]随机选择的整数
[0045]
(5)根据其他记录与r
i0
的距离，把si中数据划分成kc簇
[0046]
(6)计算各簇的信息熵entri，
[0047]
(7)endfor
[0048]
(8)计算各记录对应的entr＝∑entri[0049]
(9)每条记录的entr即为异常打分值
[0050]
进一步，在不同的样本上，在得数据集中每条记录的多个异常值打分，求解异常值打分的加权和，作为最终确定每条记录是否为异常值的依据。这里的权值可以是专家指定，也可以利用带标签的样本学习获得。
[0051]
本发明的另一目的在于提供一种高维数据异常检测实现方法的计算机程序。
[0052]
本发明的另一目的在于提供一种计算机可读存储介质，包括指令，当其在计算机上运行时，使得计算机执行所述的异常检测实现方法。
[0053]
本发明的另一目的在于提供一种实现所述新的异常检测实现方法的新的异常检测实现控制系统。
[0054]
综上所述，本发明的优点及效果为：
[0055]
本方法有别于传统方法，首先在高维数据集上抽取一部分属性作为一个样本，在多个样本上进行异常检测，最后计算不同样本上的检测结果的加权和，并作为最终判断异常数据的依据；本方案最大特点是更适用于高维数据的异常检测，能够大大降低高维数据异常检测的运算代价；通过多次随机采样，在数值属性和非数值属性上多次运行相应的检测方法，能够大大提高异常检测的精度。
附图说明
[0056]
图1是本发明实施例提供的异常检测方法的流程图。
[0057]
图2非数字属性泛化树结构图。
具体实施方式
[0058]
为了使本发明的目的、技术方案及优点更加清楚明白，以下结合实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。
[0059]
本发明的具体实施过程总体上分三个步骤：首先在原始数据集上进行抽样，然后再抽取的数据集上进行异常检测，最后把得到的异常检测值进行汇总得到最终异常检测的结果。下面结合实例对本发明的每个步骤做进一步的说明。
[0060]
本发明的随机抽样过程包括：
[0061]
本发明中的随机抽样有别于其他随机抽样，多数随机抽样为在数据集中抽取部分记录组成新的数据集，本方案中的随机抽样，是抽数据集中所有记录的部分属性。如某数据集中有10万条记录，每条记录有100个属性，本发明的随机抽样将抽取10万条记录，可能只
抽取100个属性的5个属性，这样抽样后得到的数据集将包含10万条记录，每条记录包含5个属性，通过抽样大大降低了数据的维度，所得的数据为原始数据集的一个样本。本抽样方法等同于原始数据集的记录在部分维度上的投影，每次投影类等同于一次特征提取，通过投影压缩了原始数据集的维度。每个随机抽样产生的样本均从不同角度反映了原始数据的部分特征，在不同的样本上异常检测值均在一定程度上反应原始数据集中部分记录偏离正常值的情况，最后根据各个样本上的异常检测结果，得出最终异常检测结果。
[0062]
本发明的异常检测方法包括适用于数值属性的异常检测方法和适用于非数字属性的异常检测方法，具体内容包括:
[0063]
对于数值属性异常检测方法具体内容包括：
[0064]
首先计算样本中每条记录的二范数，对于样本中的某条记录r，a1,a2,
…
,am为r的属性，则r的二范数为：
[0065][0066]
样本si中每条记录的2范数的最大值和最小值分别记为maxi和mini，把区间[mini,maxi]平均分成kn个子区间，其中kn值的确定取决于数据集的大小，如数据集中记录较多，kn值可以适当增大，依据样本中每条记录的2范数，把所有记录划分成kn类，如：把记录的2范数均落在第一个小区间的所有记录归为一个簇，这样若簇中记录说多，说明簇中的记录多，记录接近于正常值；若初中包含记录少，说明这些记录与正常数据记录偏离较大，更可能是异常值。运用每个簇记录数的倒数作为该簇中每条记录的异常值打分；打分值越高意味着该记录与正常记录偏离较大，更可能是异常值；打分值越低，说明该记录与数据集中的多数记录更接近，更可能是正常值。
[0067]
对于非数值属性异常检测方法具体内容包括：
[0068]
首先在数据集中随机选择一个记录作为基准值，然后计算各元素距离该基准值的距离，这里可以采用但不局限于基于泛化树的距离。
[0069]
含有非数值属性的记录e1与e2之间距离定义为：
[0070][0071]
其中表示属性ai的泛化树，如图2泛化树中其叶子节点该属性可能的取值，根据语义关系可以逐层向上泛化为唯一的根节点。表示泛化树的高度，如下图2中中表示属性ai的权重，e'是e1、e2的第一个共同泛化祖先。如e1、e2在该属性ai上取值分别为“个人企业”与“地方政府”，e'是e1、e2向上泛化的第一个共同祖先，即“有报酬”，那么e1、e2之间的距离计算公式方法为：
[0072][0073]
把各个样本上得到的对应记录的异常打分值进行汇总得到最终异常检测的结果，具体包括：
[0074]
设r是原始数据集d中的一条记录，则r的最终异常值打分为：
[0075][0076]
其中：为元素记录r在样本si上的异常值打分，ωi为权。权值的确定可以有专家指定，也可以通过带标签的样本数据集进行训练获得。
[0077]
最终根据vr的值及设定的阈值判定r是否为异常值。
[0078]
在上述实施例中，可以全部或部分地通过软件、硬件、固件或者其任意组合来实现。当使用全部或部分地以计算机程序产品的形式实现，所述计算机程序产品包括一个或多个计算机指令。在计算机上加载或执行所述计算机程序指令时，全部或部分地产生按照本发明实施例所述的流程或功能。所述计算机可以是通用计算机、专用计算机、计算机网络、或者其他可编程装置。所述计算机指令可以存储在计算机可读存储介质中，或者从一个计算机可读存储介质向另一个计算机可读存储介质传输，例如，所述计算机指令可以从一个网站站点、计算机、服务器或数据中心通过有线(例如同轴电缆、光纤、数字用户线(dsl)或无线(例如红外、无线、微波等)方式向另一个网站站点、计算机、服务器或数据中心进行传输)。所述计算机可读取存储介质可以是计算机能够存取的任何可用介质或者是包含一个或多个可用介质集成的服务器、数据中心等数据存储设备。所述可用介质可以是磁性介质，(例如，软盘、硬盘、磁带)、光介质(例如，dvd)、或者半导体介质(例如固态硬盘solidstatedisk(ssd))等。
[0079]
以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。

技术特征：
1.一种高维数据异常点检测方法公布了一种适用于高维数据的异常点检测的方法，其特征在于，基于一定的规则在高维数据上随机选择单个或多个属性，选择的单个属性或多个属性的组合作为异常点检测的特征，在每个特征上运行异常检测方法，得到每个数据点的异常值打分，运用各个数据点的异常值打分的和作为判断异常数据的标准；具体包括:随机在高维数据集上选择一个或多个属性(列)，作为原始数据集的一次抽样，第i次抽样记为s
i
，每个s
i
称为原始数据集的一个样本，每个样本中可以包含原始数据集中的一个属性或多个属性的组合；在每个样本上进行异常检测：若样本s
i
抽取的数值属性，则对该样本中的数据进行排序，求得s
i
中记录2范数的最大值max
i
和最小值min
i
，把区间[min
i
,max
i
]平均分成kn个子区间，kn是随机从区间[|s
i
|/20,|s
i
|/10]随机选择的整数，|s
i
|表示样本中记录的个数。统计2范数落在kn个子区间的记录数做为该区间内包含记录的异常值打分；若样本s
i
抽取的非数值属性，则首先随机选择一个记录作为基准记录r0，计算所有记录到该基准记录的距离，d
max
表示距离样本s
i
中记录距离r0的最大距离，kc是从区间[|s
i
|/20,|s
i
|/10]随机选择的整数，把区间[0,d
max
]平均分成kc个子区间，根据记录与r0的距离所在的子区间，把样本s
i
划分成kc个子类，计算每个子类的信息熵，作为该子类中包含元素的异常值打分；由不同的样本，得数据集中每条记录的多个异常值打分，求解异常值打分的加权和，作为判定数据集中每条记录是不是异常值的依据；进一步，在高维数据上随机选择属性，具体包括：输入：原始数据集r是数据集d中记录，r包含a1,a2,
…
,a
m
个属性输出：抽样样本集算法：(1)s为空集(2)for i＝1 to n
s
其中n
s
表示需要产生的样本数(3)对数据集d中每记录r，随机选择a1,a2,
…
,a
m
中一个或多个属性作为该记录的抽样记录(4)把所有抽样记录放入s
i
(5)把s
i
放入s(6)endfor(7)返回s进一步，样本s
i
抽取的数值属性，在每个样本上进行异常检测，具体包括：输入：样本s
i
输出：数据集中每条记录的异常值打分算法：(1)计算s
i
中每条记录的2范数，2范数的最大值和最小值分别记为max
i
，min
i
(2)for i＝1 to n(3)随机从区间[|s
i
|/20,|s
i
|/10]随机选择的整数kn(4)把区间[min
i
,max
i
]平均分成kn个子区间
(5)根据每条记录的2范数所在的子区间，把记录分开成kn个簇(6)计算每个簇中记录的个数c
i
，1/c
i
为该簇中每条记录的异常打分值(7)endfor(8)计算每个记录的∑1/c
i
作为记录的异常值最终打分；进一步，样本s
i
抽取的非数值属性，在每个样本上进行异常检测，具体包括：输入：样本s
i
输出：数据集中每条记录的异常值打分算法：(1)for i＝1 to n(2)随机选择s
i
中一条记录r
i0
(3)计算其他记录与r
i0
的距离(4)kc是从区间[|s
i
|/20,|s
i
|/10]随机选择的整数(5)根据其他记录与r
i0
的距离，把s
i
中数据划分成kc簇(6)计算各簇的信息熵entr
i
，(7)endfor(8)计算各记录对应的entr＝∑entr
i
(9)每条记录的entr即为异常打分值进一步，在不同的样本上，在得数据集中每条记录的多个异常值打分，求解异常值打分的加权和，作为最终确定每条记录是否为异常值的依据。这里的权可以是专家制定，也可以利用带标签的样本学习获得。2.根据权利要求1所述的一种高维数据异常检测方法，其特征在于，对于数值属性，以较高的概率选择属性值方差相对较大、极差相对较大的属性，对于非数字属性，以较高的概率选择信息熵较大的属性，选择的单个属性或多个属性的组合称为该数据集的一个特征，在各个特征上运行异常检测方法。3.根据权利要求1在每个特征上运行的异常检测方法，其特征在于，对于数值属性和数值属性的组合，把最小值到最大值之间，均匀的划分成几个区间，每个区间中包含数据记录数的倒数作为该区间内的每条记录的异常值打分；对于非数值属性和包含非数字属性的组合，把所有记录均匀的划分成几组，计算每个分组中数据的熵，熵的值作为该主数据中各个记录的异常值打分。4.一种计算机可读存储介质，包括指令，当其在计算机上运行时，使得计算机执行如权利要求1所述的高维数据异常检测方法。5.一种实现权利要求1所述高维数据异常检测方法的高维数据异常检测实现控制系统。

技术总结
本发明属于数据处理技术领域，公开了一种适用于高维数据异常检测的方法，在原始数据集上随机抽取一部分属性，分别在抽取的数值属性和非数字属性上进行异常检测，最后根据抽取属性上的检测结果判定原始数据集中的记录是否属于异常值；在数值属性上采用每个划分中包含记录个数的倒数作为异常打分值，在非数字属性上采用各簇的熵作为异常打分值，最后根据数值属性和非数字属性的异常打分值判定原始数据集中哪些记录属于异常值；本发明克服了高维数据异常检测计算代价大的缺点，能够大大提高异常检测的效率和精度。常检测的效率和精度。常检测的效率和精度。


技术研发人员：请求不公布姓名 陈传杰 花小朋 许贺洋 吴国民 周琦
受保护的技术使用者：盐城工学院技术转移中心有限公司
技术研发日：2023.05.10
技术公布日：2023/8/9